Too many packets present in (a part of) the network causes packet delay and loss that degrades performance. This situation is called congestion. The network and transport layers share the responsibility for handling congestion.

1. Common reasons for congestion on router - Congestion can occur on a router when packets arrive at a greater rate than possible to forward. Congestion can be sporadic or long term. When congestion occurs, packets must be discarded by the router. Congestion occurs at a bottleneck when:

   i. Packets arrive on several channels to be forwarded on a single channel.

   ii. Incoming channel has a higher bandwidth than outgoing channel.

   iii. Channel bandwidth is sufficient but router CPU processing is too slow to handle bookkeeping (queuing, routing table updates, etc).

   iv. Router lacks sufficient memory buffer space.

   v. Under an end-to-end reliable protocol (e.g. TCP), even with infinite memory, congestion can get worse because packets have timed out (e.g. moving from queue back to front on router or due to delay in acknowledging on a receiver) resulting in duplicates, adding to the congestion.

   2. General Principles of Congestion Control

   i. Open loop - Example: doctors office that schedules patients into time slots with no information about future office congestion state attempting to prevent congestion by estimating the time the doctor will spend with each patient.

• Design attempts to prevent congestion from occurring through decisions on accepting new traffic, when to discard packets, and scheduling.

• Decisions made without regard to current state depending upon good design to avoid congestion.

  ii. Closed loop - Example: heating control system. Uses feedback to adjust to traffic changes. Has three parts:

• Monitor system to detect when and where congestion occurs. Congestion measured by percentage of packets discarded, average packet delay, etc.

• Pass information to places where action can be taken, usually along the path back to the traffic source. Congested router sending notice to source increases traffic.
• Adjust system operation to correct the problem.
• If router claims congestion too soon and source stops sending completely on receipt of congestion notice but restarts at same rate, traffic will oscillate and never converge to a steady rate.
• Waiting too long makes system sluggish, nullifying benefit of congestion control.

• Averaging of congestion over time can provide better overall measure of when to act.

  Traffic shaping is a technique for regulating the average rate and burstiness of a flow of data that enters the network. Monitoring a traffic flow is called traffic policing.

  Traffic can be characterized using Leaky and token bucket algorithms. This bucket can be used to shape or police packets entering the network, as shown in Fig. (a).

  Token bucket algorithm:

  Imagine the network interface as a bucket that is being filled, as shown in Fig (b). The tap is running at rate R and the bucket has a capacity of B, as before. Now, to send a packet we must be able to take water, or tokens, as the contents are commonly called, out of the bucket (rather than putting water into the bucket). No more than a fixed number of tokens, B, can accumulate in the bucket, and if the bucket is empty, we must wait until more tokens arrive before we can send another packet. This algorithm is called the token bucket algorithm.