Token bucket
 |
Token Bucket é um algoritmo usado para controlar a transmissão de pacotes de dados em uma rede de computadores.
Componentes[editar | editar código-fonte]
O Token Bucket é composto por três componentes:
- um tamanho de rajada de bits (ou burst size), que especifica o quanto pode ser enviado num determinado intervalo de tempo;
- uma taxa média em bps (ou mean rate ou ainda committed information rate), que especifica a quantidade de dados, em média, que pode ser enviada por unidade de tempo; e
- um intervalo de tempo (Tc), que caracteriza o tempo por rajada.
Funcionamento[editar | editar código-fonte]
Podemos considerar um Token Bucket como um balde furado em que a fila de pacotes pode ser considerada como o volume do balde. Independente de como cheguem os dados na fila, a saída é sempre uniforme em vazão e latência. Se a capacidade da fila for ultrapassada (volume de pacotes for maior que o volume do balde) então os pacotes serão descartados, o balde transborda os pacotes em excesso.
Comparação com leaky bucket[editar | editar código-fonte]
O algoritmo de token bucket é diretamente comparável a uma das duas versões do algoritmo leaky bucket descrito na literatura.[1][2][3][4]
Esta versão comparável do bucket com vazamento é descrita na página relevante da Wikipedia como o algoritmo do leaky bucket como um metro. Essa é uma imagem espelhada do balde de tokens, na qual pacotes em conformidade adicionam fluido, equivalente aos tokens removidos por um pacote em conformidade no algoritmo de balde de tokens, a um balde de capacidade finita, do qual esse fluido é drenado a uma taxa constante, equivalente ao processo no qual os tokens são adicionados a uma taxa fixa.
Existe, no entanto, outra versão do algoritmo de bucket com vazamento,[2] descrito na página relevante da Wikipedia como o algoritmo de leaky bucket como uma fila. Este é um caso especial do balde com vazamento como um medidor, que pode ser descrito pelos pacotes em conformidade que passam pelo balde. O bucket com vazamento como uma fila é, portanto, aplicável apenas à modelagem de tráfego e, em geral, não permite que o fluxo de pacotes de saída seja estourado, ou seja, é livre de tremores. Portanto, é significativamente diferente do algoritmo de token bucket.
Essas duas versões do algoritmo leaky bucket foram descritas na literatura com o mesmo nome. Isso levou a uma considerável confusão sobre as propriedades desse algoritmo e sua comparação com o algoritmo de token bucket. No entanto, fundamentalmente, os dois algoritmos são os mesmos e, se implementados corretamente e com os mesmos parâmetros, verão exatamente os mesmos pacotes que conformes e não conformes.
Referências
- ↑ Turner, J., New directions in communications (or which way to the information age?). IEEE Communications Magazine 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.
- ↑ ATM Forum, The User Network Interface (UNI), v. 3.1, ISBN 0-13-393828-X, Prentice Hall PTR, 1995.
- ↑ ITU-T, Traffic control and congestion control in B ISDN, Recommendation I.371, International Telecommunication Union, 2004, Annex A, page 87.
