In-Depth Notes on Network Algorithms

Token Bucket Algorithm

• Definition: The Token Bucket Algorithm is a network traffic management mechanism to control data transmission rates, allowing for bursts of data.
• Conceptual Explanation:
  • Envision a bucket filled with tokens, added at a constant rate.
  • To send a data packet, a token must be removed from the bucket.
  • If enough tokens are available, packets can be sent immediately, even if that involves bursts of packets.
  • If tokens are exhausted, packets have to wait or may be dropped.
• Key Characteristics:
  • Tokens accumulate at a predetermined rate.
  • Transmission is dependent on the availability of tokens.
  • Supports bursty traffic as long as there are tokens present.
  • Offers greater flexibility than the leaky bucket method by accommodating short-term traffic spikes.
• Functionality: Ensures consistent average rate control while providing room for occasional spikes in traffic.

Leaky Bucket Algorithm

• Definition: The Leaky Bucket Algorithm is a technique used for traffic shaping and rate limiting in networks to manage data flow effectively.
• Conceptual Explanation:
  • Visualize a bucket with a small hole at the bottom that represents the exit for data packets.
  • Packets can enter the bucket at any rate, but they exit through the hole at a fixed, steady rate.
  • If data enters too quickly and fills the bucket, the excess gets discarded, preventing overflow.
• Key Characteristics:
  • Incoming packets can arrive at any speed.
  • Outgoing packets are sent at a constant rate.
  • Overflow of the bucket causes incoming packets to be dropped.
  • Aims to maintain smooth and predictable data traffic, preventing congestion.
  • Commonly utilized in routers and switches to enforce bandwidth limits.

Comparison of Leaky Bucket and Token Bucket Algorithms

• Purpose:
  • Leaky Bucket: Primarily for traffic shaping and rate limiting.
  • Token Bucket: Aimed at policing traffic while allowing bursts.
• Bucket Content:
  • Leaky Bucket: Stores packets.
  • Token Bucket: Stores tokens.
• Packet Handling:
  • Leaky Bucket: Sends packets at a constant rate.
  • Token Bucket: Sends packets if sufficient tokens are present.
• Burst Handling:
  • Leaky Bucket: Does not permit bursts; provides smooth output.
  • Token Bucket: Allows bursts, provided enough tokens exist.
• Traffic Flow:
  • Leaky Bucket: Provides strict and uniform flow.
  • Token Bucket: Offers flexible flow, accommodating bursty and idle periods.
• Bucket Fullness:
  • Leaky Bucket: Incoming packets are discarded if full.
  • Token Bucket: Accumulation stops; incoming packets may have to wait or be dropped.
• Risk of Packet Loss:
  • Leaky Bucket: Higher likelihood during bursts.
  • Token Bucket: Lower likelihood due to burst management.
• Use Cases:
  • Leaky Bucket: Best for streaming applications where a smooth delivery is crucial.
  • Token Bucket: Ideal for web browsing where burst transmissions are common.
• Flexibility:
  • Leaky Bucket: Less flexible for variable traffic.
  • Token Bucket: More versatile and adaptable to traffic changes.

Congestion Control Algorithms

• Definition: Congestion Control Algorithms are techniques used in networks to prevent excessive data from saturating the network, contributing to packet loss, increased delay, and subpar performance.
• Main Functions:
  • Monitor network conditions such as packet loss and delay.
  • Adjust data sending rates to maintain smooth traffic flow.
  • Use commonly in TCP for efficient resource utilization.
• Common Algorithms:
  • TCP Tahoe/Reno: React to packet loss by reducing transmission rates.
  • TCP Vegas: Detects early congestion by monitoring delay.
  • Random Early Detection (RED): Implements early packet drops before queues reach capacity to signal congestion.
  • Explicit Congestion Notification (ECN): Uses packet markings to inform senders of congestion without dropping packets.
• Goals:
  • Maximize throughput, minimize delay, and ensure fairness among users in a network.

Comparison of Congestion Control Algorithms

• TCP Tahoe:
  • Congestion Detection: Packet loss.
  • Reaction: Initiates slow start, transitions to congestion avoidance.
  • Packet Loss Handling: Drops packets and resets connections.
  • Fairness: Moderate, generally suitable for legacy TCP networks.
• TCP Reno:
  • Congestion Detection: Packet loss.
  • Reaction: Uses fast retransmit & fast recovery strategies.
  • Packet Loss Handling: Partial recovery of the transmission window.
  • Fairness: Moderate, widely practiced within traditional TCP networks.
• TCP Vegas:
  • Congestion Detection: Delays increase.
  • Reaction: Adjusts sending rate preemptively to avoid loss.
  • Packet Loss Handling: Very little, aims to prevent altogether.
  • Fairness: High, useful in delay-sensitive networks.
• RED:
  • Congestion Detection: Average queue length.
  • Reaction: Uses probabilistic approach to drop packets early.
  • Packet Loss Handling: Reduces queue overflow risk.
  • Fairness: High, adapted for routers and gateways.
• ECN:
  • Congestion Detection: Marks packets with congestion signals.
  • Reaction: Sender reduces data transmission rate upon receiving marked packets.
  • Packet Loss Handling: Strives to eliminate packet drops entirely.
  • Fairness: High, suitable for modern TCP/IP network applications.
• CUBIC:
  • Congestion Detection: Time since last loss event.
  • Reaction: Employs rapid growth rates and stable probing for effective throughput.
  • Packet Loss Handling: Accepts less sensitivity to delay.
  • Fairness: Good, optimized for high-speed and long-distance communications.

Summary of Key Algorithms

• Loss-based Algorithms: Such as TCP Tahoe and Reno, react to congestion only after it has occurred.
• Delay-based Algorithms: Such as TCP Vegas, work to prevent congestion from escalating.
• RED and ECN: Operate on the network level to manage congestion proactively.