Token-Bucket Algorithm

from Wikipedia, the free encyclopedia

The token-bucket algorithm is an algorithm for shaping traffic in packet-switched data networks . It regulates the average data rate and maximum burst size using a network scheduler .

functionality

Certain quotas are regularly allocated to the data stream, which can be used or accumulated up to a certain limit. To make things clearer, we imagine the allocation pictorially in the form of "tokens" (English tokens ) before the (English at regular intervals in a metaphorical "bucket" bucket ) are thrown. Each token represents a certain amount of data that can be transferred. When the bucket is full, no tokens are given.

When a data packet is to be transmitted, tokens are removed from the bucket corresponding to the equivalent of the amount of data in the packet.

What happens if there are not enough tokens in the bucket depends on the implementation. Either the data packet is placed in a queue until enough tokens have accumulated due to the regular allocation, or it is discarded. Another possibility is to send the data packet immediately anyway, but to mark it as "non-compliant" so that it can be discarded on its way if there should be bottlenecks.

If less data is transferred than tokens are allocated over a period of time, these will accumulate in the bucket. This creates a credit that makes it possible to transfer large amounts of data at short notice. In the long term, however, the transfer rate is limited by the rate at which tokens are allocated.

The size (capacity) of the bucket determines the maximum credit that can be accumulated. This prevents the average data rate from being exceeded for too long.

See also

literature

  • Panos Lekkas: Network Processors. Architectures - Protocols and Platforms, McGraw Hill Professional, 2003, ISBN 978-0-0714-0986-5 .
  • Ralf Steinmetz: Multimedia technology. Basics - Components and Systems, 2nd edition, Springer Verlag, Berlin / Heidelberg 1999, ISBN 978-3-662-08882-1 .
  • Christoph Meinel, Harald Sack: Internetworking. Technical basics and applications. Springer-Verlag, Berlin / Heidelberg 2012, ISBN 978-3-540-92940-6 .

Web links