Leaky bucket
Il leaky bucket è un algoritmo utilizzato nelle reti di computer a commutazione di pacchetto e reti di telecomunicazioni. Può essere utilizzato per controllare che le trasmissioni di pacchetto dati,[1] siano ben delimitate in banda e velocità di trasmissione. Può inoltre essere utilizzato come scheduler di rete. L'algoritmo leaky bucket può infine essere utilizzato come contatore, ad esempio per rilevare quando il tasso medio o di picco di determinati processi stocastici eccedono limiti prestabiliti.
Funzionamento[modifica | modifica wikitesto]
L'algoritmo leaky bucket è basato su (e prende il nome da) l'analogia di un secchio con un buco sul fondo, attraverso il quale qualsiasi quantità d'acqua sia contenuta fluirà all'esterno sempre alla stessa velocità, a meno che (o fino a quando) il secchio non sia vuoto. Se l'acqua viene aggiunta troppo velocemente, supererà in volume la capacità del secchio e straborderà.
Questo meccanismo fissa un limite medio di trasmissione mediante il buco sul fondo, ma segna anche un limite al picco di trasmissione, tramite la capacità massima del secchio.
Nella letteratura vengono descritti due metodi differenti di applicare l'analogia del leaky bucket,[2][3][4][5] ciascuno dei quali viene spesso descritto senza citare l'altro. Ciò ha portato a molta confusione riguardo quale sia effettivamente l'algoritmo corretto e quali siano le sue proprietà.
In una versione, il secchio è rappresentato da un contatore o una generica variabile, ed è separato dal flusso di traffico e dallo scheduling degli eventi.[2][4][5] È infatti utilizzato solo per controllare che il traffico o gli eventi siano conformi ai limiti predefiniti: il contatore viene incrementato ad ogni pacchetto che arriva e decrementato in maniera costante. Di conseguenza, il valore del contatore nel momento in cui arriva un pacchetto indica la sua conformità ai limiti di banda o di burst. In questa versione, quindi, il leaky bucket viene utilizzato essenzialmente come strumento di misura.
Nella seconda versione, il secchio è rappresentato da una coda FCFS in un flusso di traffico.[3] La coda è utilizzata per controllare direttamente tale flusso: i pacchetti sono inseriti nella coda appena arrivano e rimossi secondo un rate costante. Di conseguenza, la velocità con cui la coda è servita controlla direttamente l'avanzamento della trasmissione, in modo tale da imporre conformità, anziché controllarla, e dove la coda viene servita ad un tasso fisso (e dove i pacchetti sono tutti della stessa lunghezza), il flusso di traffico risultante è necessariamente privo di jitter o di picchi troppo elevati.
Il leaky buket come coda può essere dunque visto come un caso particolare di token bucket.[6] L'implementazione del leaky bucket come coda non sfrutta le attuali risorse di rete in maniera efficiente. Infatti, siccome trasmette pacchetti solo ad intervalli prefissati, ci saranno parecchi casi in cui il volume del traffico sarà molto basso e ampie porzioni delle risorse di rete (larghezza di banda in particolare) non verranno utilizzate. Pertanto non esiste alcun meccanismo nell'attuazione del leaky bucket come coda per consentire singoli flussi di burst fino a velocità massima consentita, in maniera tale da consumare più risorse di rete nei momenti in cui non vi sarebbero conflitti.
Il leaky bucket come metro[modifica | modifica wikitesto]
Jonathan S. Turner è accreditato[7] come l'ideatore dell'algoritmo di leaky bucket. Lo descrisse inizialmente come segue: "Un contatore, associato con ciascun utente trasmittente, che è incrementato ogni volta che l'utente invia un pacchetto e viene decrementato periodicamente. Se il contatore supera una soglia mentre viene incrementato, la rete scarta il pacchetto. L'utente specifica la velocità in cui il contatore viene decrementato (il che determina una larghezza media di banda) e il valore della soglia (per misurare il burst)".[2]
Una versione sostanzialmente equivalente di questo algoritmo è il Generic Cell Rate Algorithm, descritto dalla ITU-T nella raccomandazione I.371[5] e nella specifica UNI dell'ATM Forum.[4]
Nel commentare la descrizione dell'algoritmo della ITU-T/ATM Forum, David E. McDysan e Darrel L. Spohn introducono la figura fittizia di un gremlin.[6] Questo gremlin ispeziona il livello d'acqua nel secchio e, quando il livello dell'acqua supera il limite prefissato, può agire secondo due modus operandi:
- Traffic policing ("gestione del traffico"): il gremlin verifica che il livello d'acqua ha superato il limite, di conseguenza apre una botola e scarta il pacchetto.
- Traffic shaping ("modellazione del traffico"): il gremlin verifica che il livello d'acqua ha superato il limite, di conseguenza alza uno sportello per bloccare temporaneamente lo scorrere dei pacchetti finché il livello d'acqua non torna sotto il limite consentito.
La differenza fra i due algoritmi è che quello di Turner si riferisce senza dubbio al traffic policing, mentre quello della ITU-T/ATM Forum è applicabile sia al traffic policing che al traffic shaping. Inoltre, Turner non afferma che il contatore debba essere incrementato solo quando il pacchetto è conforme, ovvero quando l'incremento non causerebbe il superamento del limite. Per conciliare la descrizione di Turner con quella della ITU-T/ATM Forum bisognerebbe cambiare la parte in cui Turner afferma "Se il contatore supera una soglia mentre viene incrementato, la rete scarta il pacchetto" in "Qualora il contatore, venendo incrementato, supererebbe la soglia, la rete scarta il pacchetto e il contatore non viene incrementato.
Confronto con il token bucket[modifica | modifica wikitesto]
Note[modifica | modifica wikitesto]
- ^ Nella gestione concreta del traffico, il leaky bucket è normalmente applicato nelle PDU del secondo strato della pila ISO/OSI (livello di collegamento dati), quindi potrebbe essere obiettato che si parli di "pacchetti" e non di "trame" (frame). Tuttavia il termine "pacchetto", oltre a riferirsi alla PDU del livello rete, è anche usato nella letteratura per riferirsi ad un generico insieme di dati. Con ciò non si vuole intendere che questo algoritmo può essere implementato solo nel datalink layer.
- ^ a b c Turner, J., New directions in communications (or which way to the information age?). Communications Magazine, IEEE 24 (10): 8–15. ISSN 0163-6804, 1986.
- ^ a b Andrew S. Tanenbaum, Computer Networks, Fourth Edition, ISBN 0-13-166836-6, Prentice Hall PTR, 2003., page 401.
- ^ a b c ATM Forum, The User Network Interface (UNI), v. 3.1, ISBN 0-13-393828-X, Prentice Hall PTR, 1995.
- ^ a b c ITU-T, Traffic control and congestion control in B ISDN, Recommendation I.371, International Telecommunication Union, 2004, Annex A, page 87.
- ^ a b McDysan, David E. and Spohn, Darrel L., ATM: Theory and Application, ISBN 0-07-060362-6, McGraw-Hill series on computer communications, 1995, pages 358–9.
- ^ Andrew S. Tanenbaum, Computer Networks, Fourth Edition, ISBN 0-13-166836-6, Prentice Hall PTR, 2003, Page 400.
Voci correlate[modifica | modifica wikitesto]
Altri progetti[modifica | modifica wikitesto]
Wikimedia Commons contiene immagini o altri file su leaky bucket
