top of page

Subscribe to Wisdom

Thanks for Subscribing!

  • Writer's pictureDimit Chadha

Leaky/Token Bucket Algorithm

  • Used in packet switched computer networks & Telecommunication Networks.

  • Define upper limits on bandwidth & burstiness on data transmission

  • Analogy of fixed capacity bucket into which tokens are added at a fixed rate

  • Used in application to provide download bandwidth limits in software applications like torrent & download managers.

  • To control the download speed on 3G network by our cellular provider.

  • Throttling mechanism – E.g. to limit the amount of web requests sent to a server. If there are too many submissions for a request, then the extra requests are queued until the resource becomes available.

  • method is executed no more than M times in a sliding window of N seconds.

  • It is about regulating average rate of data flow. May be termed as Traffic shaping

  • Method of congestion control by providing shape to data flow before entering packet into network

  • The packet does not conform if there are insufficient tokens in the bucket, and the contents of the bucket are not changed. Non-conformant packets can be treated in various ways:

    • They may be dropped.

    • They may be enqueued for subsequent transmission when sufficient tokens have accumulated in the bucket.

    • They may be transmitted, but marked as being non-conformant, possibly to be dropped subsequently if the network is overloaded.

  • Sender & carrier negotiate a traffic pattern

    • Token Bucket

    • Leaky Bucket

Leaky Bucket
  • Control rate in a network

  • Implemented as a single server queue with constant service time

  • If bucket full, packets are discarded

  • Input rate may vary but output rate remains constants

  • Saves busty traffic into fixed rate traffic by averaging the data rate.

  • Algorithm –

    1. Initialize counter to ‘n’ at every tick of clock

    2. If n is greater than size of packet in front of queue, send the packet into the network & decrement the counter by size of the packet. Repeat until n is less than size of packet

    3. Reset the counter & go to step 1



13 views0 comments

Recent Posts

See All

Comments


Modern Digital Watch
bottom of page