Token bucket
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
Esistono due metodi per modellare il traffico predominante: l'implementazione leaky bucket (secchio che perde) e token bucket. A volte sono erroneamente raggruppati insieme sotto lo stesso nome. Questi sistemi hanno caratteristiche distinte e vengono utilizzati per scopi diversi. Essi 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
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
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
Tasso medio modifica
Nel lungo periodo la produzione di pacchetti conforme è limitata dal tasso r di aggiunta dei token nel bucket.
Dimensione Burst modifica
Sia M il tasso massimo possibile trasmissione in byte al secondo.
Poi è il tempo massimo di burst, che è il tempo per il quale il tasso M è pienamente utilizzato.
La dimensione massima del burst è quindi
Bibliografia modifica
- "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: https://code.activestate.com/recipes/511490/
