Thursday, November 22, 2012

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

No comments:

Post a Comment