Notes - Congestion Control Algorithms

The following are notes from Tanenbaum's Computer Networks 5th Edition.

• congestion is when too many packets are in the network which causes delays and reduces performance
• unless a network is well designed, its possible to experience a congestion collapse where performance plummets as load increases beyond capacity
• goodput rate at which useful packets are delivered by the network
• Congestion control has to do in making sure the network can carry the offered traffic, flow control deals with the traffic between a sender and a receiver

Approaches to Congestion Control

• provisioning 
• links and routers that are heavily utilized are upgraded at earliest opportunity
• traffic-aware routing
• account for daily changes to shift traffic away from heavily used paths
• admission control
• decrease the load by denying connections
• load shedding
• discard packets it cannot deliver
• used only to prevent congestion collapse

Traffic-Aware Routing

• schemes adapt to changes in load
• set the link weight to be a function of link bandwidth and propagation delay
• this solves an issue where if we set the link weight as a function of load, it causes oscillations as packets are routed in one direction only at first then heavily favors another and repeats between the two
• multipath routing multiple routse from source to destination
• shift through routes slowly so that it can converge
• topic is called traffic engineering

Admission Control

• do not set up new virtual circuit unless the network can handle it without being congested
• work out when virtual circuit exists
• leaky bucket
• two parameters that bound the average rate and instant burst size of traffic
• token bucket
• will fill as long as it has token, detailed later
• Choose whether to admit virtual circuit depending on traffic description
• can be combined with traffic aware routing consider traffic hotspots as part of setup procedure

Traffic Throttling

• Congestion avoidance, if feedback is exceptional we can tell senders to throttle their transmissions and slow down
• queuing delay d, instantaneous queue length s, constant alpha which is how fast the router forgets recent history can be made and updated according to

• EWMA(Exponentially Weighted Moving Average)
• smooths out fluctuations like a low pass filter
• Choke Packets
• notify sender of congestion is to tell it directly
• contains source and destination information and required to reduce traffic to destination by a certain percent
• SOURCE-QUENCH message used in early internet
• Explicit Congestion Notification
• ECN(Explicit Congestion Notification)
• instead of generating additional packets like using a choke packet, signal to warn of congestion by tagging a packet it forwards, two bits in the IP packet header DECNET architecture
• Hop by Hop Backpressure
• at high speeds over long distances, new packets may be transmitted after congestion signaled
• choke packet take effect at every hop it passes through rather than just at destination

Load Shedding

• when router can't handle it we just start throwing away packets
• wine
• throw away newest packets
• milk
• throw away oldest packets
• More intelligent load shedding involves cooperation from senders
• applications must mark their packets to inform the network
• Random Early Detection
• Dealing with congestion before it starts is the most effective way
• RED(Random Early Detection)
• determines when to start discarding, routers maintain running average of queue lengths
• when queue length too long, drop small fraction of packets at random
• randomness makes it more likely that fastest senders will see a packet drop the sender will notice this since there is no ack and protocol will slow down

Back to ToC