Token bucket

Da Wikipedia, l'enciclopedia libera.

In informatica e telecomunicazioni, nell'ambito delle reti di calcolatori, con il termine token bucket si indica un comune algoritmo utilizzato per controllare la quantità di dati che viene iniettato in una rete e che consente ai dati stessi di essere inviati. Anche se ha diversi utilizzi la sua utilità si comprende meglio nel contesto del traffic control (traffic shaping o rate limiting in trasmissione e traffic policing in ricezione).

Algoritmi di Traffic Shaping (leaky bucket versus token bucket)[modifica | modifica sorgente]

Esistono due metodi per modellare il traffico predominante: l'implementazione leaky bucket (secchio che perde) e token bucket. A volte sono erroneamente raggruppate insieme sotto lo stesso nome. Entrambi questi sistemi hanno caratteristiche distinte e vengono utilizzati per scopi diversi. Esse differiscono principalmente in quanto il leaky bucket impone un limite rigido sulla velocità di trasmissione dati, mentre il token bucket consente una certa quantità di burstiness pur imponendo un limite al tasso medio di trasmissione dei dati.

Vista ad alto livello[modifica | modifica sorgente]

Il token bucket è un meccanismo di controllo di trasmissione che determina quando e quanto traffico dati (sotto forma di pacchetti) può essere trasmesso in base alla presenza o meno di token (gettoni) in un contenitore astratto, che detiene il traffico complessivo di rete da trasmettere, detto appunto bucket. Il bucket contiene dunque dei token, ciascuno dei quali può rappresentare una unità in byte o un singolo pacchetto di dimensioni predeterminate. Un flusso è autorizzato a trasmettere traffico solo quando sono presenti token nel bucket. L'amministratore di rete specifica quanti gettoni sono necessari per trasmettere una certa quantità di byte e i token vengono rimossi dal bucket quando si trasmette un pacchetto. Un flusso di traffico è in grado di trasmettere fino alla sua velocità del suo rate di picco se ci sono abbastanza token nel bucket e se la soglia di rottura è configurata in modo appropriato.

L'algoritmo token bucket[modifica | modifica sorgente]

L'algoritmo può essere concettualmente inteso come segue:

  • Un token è aggiunto al secchiello ogni 1/r secondi.
  • Il bucket può contenere al più b token. Se un token arriva quando il bucket è pieno viene scartato.
  • Quando un pacchetto (livello di rete PDU) di n bytes arriva, n token vengono rimossi dal bucket, e il pacchetto viene inviato alla rete.
  • Se meno di n token sono disponibili, nessun token viene rimosso dal bucket, e il pacchetto viene considerato come non conforme.

Proprietà[modifica | modifica sorgente]

Tasso medio[modifica | modifica sorgente]

Nel lungo periodo la produzione di pacchetti conforme è limitata dal tasso r di aggiunta dei token nel bucket.

Dimensione Burst[modifica | modifica sorgente]

Sia M il tasso massimo possibile trasmissione in byte al secondo.

Poi T_\text{max} =
\begin{cases}
b/(M -r) & \text{ se } r < M \\
\infty & \text{ altrimenti}
\end{cases}
è il tempo massimo di burst, che è il tempo per il quale il tasso M è pienamente utilizzato.

La dimensione massima del burst è quindi L_\text{max} = T_\text{max}*M

Bibliografia[modifica | modifica sorgente]

  • "Distribuzione di IP e MPLS QoS per reti multiservizio: Teoria e Pratica" di John Evans, Filsfils Clarence (Morgan Kaufmann, 2007, ISBN 0-12-370549-5)
  • Ferguson P., G. Huston, Quality of Service: Delivering QoS su Internet e nelle reti aziendali, John Wiley & Sons, Inc., 1998. ISBN 0-471-24358-2.
  • S. Tanenbaum Andrew,Reti di Calcolatori, 3ª edizione, Prentice-Hall, 1996.
  • Linux HTB Home Page http://luxik.cdi.cz/ devik ~ / QoS / HTB / ...
  • Attuazione del token bucket in python: http://code.activestate.com/recipes/511490/

Voci correlate[modifica | modifica sorgente]