Browse Definitions :
Definition

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

Networking
  • firewall as a service (FWaaS)

    Firewall as a service (FWaaS), also known as a cloud firewall, is a service that provides cloud-based network traffic analysis ...

  • private 5G

    Private 5G is a wireless network technology that delivers 5G cellular connectivity for private network use cases.

  • NFVi (network functions virtualization infrastructure)

    NFVi (network functions virtualization infrastructure) encompasses all of the networking hardware and software needed to support ...

Security
  • virus (computer virus)

    A computer virus is a type of malware that attaches itself to a program or file. A virus can replicate and spread across an ...

  • Certified Information Security Manager (CISM)

    Certified Information Security Manager (CISM) is an advanced certification that indicates that an individual possesses the ...

  • cryptography

    Cryptography is a method of protecting information and communications using codes, so that only those for whom the information is...

CIO
  • B2B (business to business)

    B2B (business-to-business) is a type of commerce involving the exchange of products, services or information between businesses, ...

  • return on investment (ROI)

    Return on investment (ROI) is a crucial financial metric investors and businesses use to evaluate an investment's efficiency or ...

  • big data as a service (BDaaS)

    Big data as a service (BDaS) is the delivery of data platforms and tools by a cloud provider to help organizations process, ...

HRSoftware
  • talent acquisition

    Talent acquisition is the strategic process an organization uses to identify, recruit and hire the people it needs to achieve its...

  • human capital management (HCM)

    Human capital management (HCM) is a comprehensive set of practices and tools used for recruiting, managing and developing ...

  • Betterworks

    Betterworks is performance management software that helps workforces and organizations to improve manager effectiveness and ...

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 ...

Close