Leaky bucket | EPFL Graph Search

Are you an EPFL student looking for a semester project?

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

The leaky bucket is an algorithm based on an analogy of how a bucket with a constant leak will overflow if either the average rate at which water is poured in exceeds the rate at which the bucket leaks or if more water than the capacity of the bucket is poured in all at once. It can be used to determine whether some sequence of discrete events conforms to defined limits on their average and peak rates or frequencies, e.g. to limit the actions associated with these events to these rates or delay them until they do conform to the rates. It may also be used to check conformance or limit to an average rate alone, i.e. remove any variation from the average. It is used in packet-switched computer networks and telecommunications networks in both the traffic policing, traffic shaping and scheduling of data transmissions, in the form of packets, to defined limits on bandwidth and burstiness (a measure of the variations in the traffic flow). A version of the leaky bucket, the generic cell rate algorithm, is recommended for Asynchronous Transfer Mode (ATM) networks in Usage/Network Parameter Control at user–network interfaces or inter-network interfaces or network-to-network interfaces to protect a network from excessive traffic levels on connections routed through it. The generic cell rate algorithm, or an equivalent, may also be used to shape transmissions by a network interface card onto an ATM network. At least some implementations of the leaky bucket are a mirror image of the token bucket algorithm and will, given equivalent parameters, determine exactly the same sequence of events to conform or not conform to the same limits. Two different methods of applying this leaky bucket analogy are described in the literature. These give what appear to be two different algorithms, both of which are referred to as the leaky bucket algorithm and generally without reference to the other method. This has resulted in confusion about what the leaky bucket algorithm is and what its properties are.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (9)

Stability and bounds in aggregate scheduling networks

Gianluca Rizzo

We study networks of FIFO nodes, where flows are constrained by arrival curves. A crucial question with these networks is: Can we derive a bound to the maximum delay that a packet can experience when

EPFL2008

Aggregate scheduling is one of the most promising solutions to the issue of scalability in networks, like DiffServ networks and high speed switches, where hard QoS guarantees are required. For network

2008

Generalization of the RIN Result to Heterogeneous Networks of Aggregate Schedulers and Leaky Bucket Constrained Flows

Jean-Yves Le Boudec, Gianluca Rizzo

We consider networks of FIFO aggregate schedulers. Quite surprisingly, the natural condition (node utilization inferior to one) in general is not sufficient in these networks to ensure stability (boun

2007

Related people (2)

Jean-Yves Le Boudec, Gianluca Rizzo

Related concepts (7)

Related courses (2)

Related lectures (13)

Leaky bucket

Token bucket

The token bucket is an algorithm used in packet-switched and telecommunications networks. It can be used to check that data transmissions, in the form of packets, conform to defined limits on bandwidth and burstiness (a measure of the unevenness or variations in the traffic flow). It can also be used as a scheduling algorithm to determine the timing of transmissions that will comply with the limits set for the bandwidth and burstiness: see network scheduler.

Traffic policing (communications)

In communications, traffic policing is the process of monitoring network traffic for compliance with a traffic contract and taking steps to enforce that contract. Traffic sources which are aware of a traffic contract may apply traffic shaping to ensure their output stays within the contract and is thus not discarded. Traffic exceeding a traffic contract may be discarded immediately, marked as non-compliant, or left as-is, depending on administrative policy and the characteristics of the excess traffic.

This course provides a deep understanding of the concepts behind data management systems. It covers fundamental data management topics such as system architecture, data models, query processing and op

Multiprocessors are a core component in all types of computing infrastructure, from phones to datacenters. This course will build on the prerequisites of processor design and concurrency to introduce

Covers hashing, sorting, extendible hashing, linear hashing, and external sorting.

Explores hashing techniques like static, extendible, and linear hashing, along with sorting methods such as external merge sort and B+ trees.

Explores query processing operations, join conditions, set operations, and buffering impact on query performance.