Telecommunication

What is WRR Weighted Round Robin

Admin

— 2 min read

Weighted Round Robin (WRR)

Weighted Round Robin (WRR) is a scheduling algorithm commonly used in networking to distribute network traffic across multiple servers or links. It's an enhancement over the basic Round Robin algorithm, which distributes traffic equally.

How WRR Works

  • Weight Assignment: Each server or link is assigned a weight, which represents its capacity or processing power. A higher weight indicates a more capable server.
  • Token Bucket: A token bucket is maintained for each server. The size of the bucket is equal to the server's weight.
  • Token Distribution: Initially, each token bucket is filled with tokens equal to its weight.
  • Scheduling Process:
    • When a new request arrives, the scheduler selects the server with the highest number of tokens.
    • The selected server processes the request.
    • After processing, one token is removed from the server's token bucket.
    • If a server's token bucket is empty, it is skipped until it receives more tokens.
    • The scheduler then moves to the next server in a round-robin fashion.
  • Token Replenishment: At regular intervals, each server's token bucket is refilled with tokens equal to its weight.

Key Points

  • Fairness: WRR provides a fair distribution of traffic based on the assigned weights.
  • Flexibility: The weights can be adjusted dynamically to adapt to changing server capacities or traffic patterns.
  • Simplicity: The algorithm is relatively simple to implement and understand.
  • Potential Starvation: Servers with low weights might experience starvation, especially under heavy load.

Example

Consider three servers with weights 2, 3, and 1. The token buckets will initially have 2, 3, and 1 tokens respectively. The scheduler will first send two requests to server 1, then three requests to server 2, and finally one request to server 3, before starting a new cycle.

WRR vs. Round Robin

  • Round Robin distributes traffic equally among servers, regardless of their capacity.
  • WRR distributes traffic proportionally based on the assigned weights, providing a more efficient and flexible approach.

Applications of WRR

  • Load Balancing: Distributing incoming traffic across multiple servers to improve performance and reliability.
  • Network Switches: Scheduling packet forwarding between different output ports.
  • Operating Systems: Scheduling CPU time among multiple processes.

Limitations of WRR

  • Starvation: Servers with low weights might experience starvation under heavy load.
  • Head-of-Line Blocking: If the first packet in a queue is delayed, subsequent packets in the same queue are also delayed.

Enhancements to WRR

To address the limitations of WRR, various enhancements have been proposed, such as:

  • Weighted Fair Queuing (WFQ): Provides more precise control over bandwidth allocation.
  • Credit-Based Shaper (CBS): Combines the advantages of WRR and WFQ.

WRR is a fundamental scheduling algorithm widely used in networking due to its simplicity and effectiveness in distributing traffic across multiple resources.

Read more