Browse Definitions :

leaky bucket algorithm

What is leaky bucket algorithm?

The leaky bucket algorithm is a "traffic shaping" algorithm to reduce the load the transport layer places on the network layer and reduce congestion in the network. Commonly used in asynchronous transfer mode (ATM) networks, the algorithm provides a way to temporarily store a variable number of requests and then organize them into a set-rate output of packets.

Network congestion and traffic shaping

Traffic congestion is a common problem in all networks. When too many packets flow through a network, packet delays or packet losses can occur, both of which degrade the network's performance. This situation is known as congestion.

Congestion in a network often happens when the traffic is bursty. In the seven-layer OSI model for networking system communications, the network and transport layers are layer 3 and layer 4, respectively. The two layers are jointly responsible for handling network congestion, which they do by "shaping" the traffic.

Chart showing the Open Systems Interconnection (OSI) network model
The 7 layers of the OSI model

Traffic shaping is a congestion management technique. It helps to control the amount of traffic sent to the network and regulates the rate of data transmission. The goal is to reduce the load the transport layer places on the network to reduce congestion and improve network performance. One commonly used method for traffic shaping is the leaky bucket algorithm.

Leaky bucket algorithm explained

The token bucket algorithm and leaky bucket algorithm are two ways to shape network traffic and reduce congestion. The leaky bucket controls both the total amount of traffic and the rate at which it is sent to the network. It can detect both gradually increasing and dramatic memory error increases by comparing how the average and peak data rates exceed set acceptable background amounts.

The algorithm works similarly to the way a real-world leaky bucket holds water: It collects data up to a maximum capacity. The data is released (leaked) from the bucket at a set rate and based on a fixed packet size. When the bucket runs out of data, the leaking stops. If incoming data would overfill the bucket, then the packet is considered "nonconformant," so the new data is not added to the bucket. Data is added to the bucket as space becomes available for conforming packets.

The leaky bucket is used to implement traffic policing and traffic shaping in Ethernet and cellular data networks. It can also be used to control metered-bandwidth internet connections to prevent users from going over the allotted bandwidth for a specified period, thereby avoiding extra charges.

Chart showing the structure of a network packet
Structure of a network packet: Leaky bucket algorithm helps regulate packet flow in a network.

How the leaky bucket algorithm works, with an example

The leaky bucket algorithm is ideal for smoothing out bursty traffic. Just like a hole at the bottom of a water bucket leaks water out at a fixed rate, the leaky bucket algorithm does the same with network traffic. Bursty chunks of traffic are stored in a "bucket" with a "hole" and sent out at a controlled, average rate.

The hole represents the network's commitment to a particular bandwidth. The leaky bucket shapes the incoming traffic to ensure it conforms to the commitment. Thus, regardless of how much data traffic enters the bucket, it always leaves at a constant output rate (the commitment). This mechanism regulates the packet flow in the network and helps to prevent congestion that leads to performance deterioration and traffic delays.

Leaky bucket example. Suppose data enters the network from various sources at different speeds. Consider one bursty source that sends data at 20 Mbps for 2 seconds for a total of 40 Mbps. Then it is silent, sending no data for 5 seconds. Then it again transmits data at a rate of 10 Mbps for 3 seconds, thus sending a total of 30 Mbps. So, in a time span of 10 seconds the source sends 70 Mb data.

However, the network has only committed a bandwidth of 5 Mbps for this source. Therefore, it uses the leaky bucket algorithm to output traffic at the rate of 5 Mbps during the same time period of 10 seconds, which smooths out the network traffic.

Without the leaky bucket algorithm in place, the initial burst of 20 Mbps would have consumed a lot more bandwidth than the network had reserved (committed) for the source, which would have caused congestion and a slowdown in the network.

Implementing the leaky bucket algorithm with a FIFO queue

A first-in, first-out (FIFO) queue enhances communications between applications. It is especially useful when the order of operations and events in the network is critical. Also known as first-come, first-served (FCFS) queuing, FIFO queuing means that the first packet that arrives at a router is also the first to be transmitted. Furthermore, if a packet arrives and the queue -- also known as the buffer space -- is full, it is discarded by the router.

A FIFO queue can be used to implement a leaky bucket algorithm in a network. The queue holds the packets and doesn't allow them to pass if they exceed the bandwidth committed by the network for a source. If the traffic consists of variable-length packets, the output rate is fixed based on the commitment in bytes or bits.

However, if the traffic consists of fixed-size packets, the algorithm will drop the packets arriving at the tail end of the FIFO. This phenomenon, known as a "tail drop," happens regardless of the packet's importance or which flow it belongs to.

Chart showing 10 essential network management tasks

Applications of leaky bucket algorithm

The traffic shaping capability of the leaky bucket algorithm is useful for both computing and telecommunications applications. In computing, the bucket is the server, which has fixed processing capability or size. The output that comes from the bucket is the processed data. This data leaves the bucket at a constant rate, depending on the server's processing speed, to smooth out the traffic and prevent bursts.

The algorithm is also implemented to prevent congestion in telecommunications networks. When subscribers sign a contract with a telecom provider, they can use a specific bandwidth within a specified period (per day, per month, etc.) If the subscriber uses more bandwidth than is allocated to them, excess packets will spill out of the bucket. The network will then prevent the subscriber from using more than their allocated bandwidth.

See also: traffic shaping

This was last updated in November 2022

Continue Reading About leaky bucket algorithm

  • identity management (ID management)

    Identity management (ID management) is the organizational process for ensuring individuals have the appropriate access to ...

  • single sign-on (SSO)

    Single sign-on (SSO) is a session and user authentication service that permits a user to use one set of login credentials -- for ...

  • fraud detection

    Fraud detection is a set of activities undertaken to prevent money or property from being obtained through false pretenses.

  • IT budget

    IT budget is the amount of money spent on an organization's information technology systems and services. It includes compensation...

  • project scope

    Project scope is the part of project planning that involves determining and documenting a list of specific project goals, ...

  • core competencies

    For any organization, its core competencies refer to the capabilities, knowledge, skills and resources that constitute its '...

  • Workday

    Workday is a cloud-based software vendor that specializes in human capital management (HCM) and financial management applications.

  • recruitment management system (RMS)

    A recruitment management system (RMS) is a set of tools designed to manage the employee recruiting and hiring process. It might ...

  • core HR (core human resources)

    Core HR (core human resources) is an umbrella term that refers to the basic tasks and functions of an HR department as it manages...

Customer Experience
  • martech (marketing technology)

    Martech (marketing technology) refers to the integration of software tools, platforms, and applications designed to streamline ...

  • transactional marketing

    Transactional marketing is a business strategy that focuses on single, point-of-sale transactions.

  • customer profiling

    Customer profiling is the detailed and systematic process of constructing a clear portrait of a company's ideal customer by ...