http://douc54.cs.edinboro.edu/~bennett/class/csci475/spring2007/notes/ch20/seven.html

Approaches to congestion control.

• End to End control
  • Stallings appears to call this Implicit Congestion Signaling
  • For systems like TCP where there is no underlying congestion control.
  • Congestion must be detected in terms of observed network behavior
    • packet loss
    • Delay
  • TCP Decreases the window size when it detects delay
• Network Assisted congestion control
  • Some form of explicit feedback is available from the underlying network.
  • ICMP source quench for example.
  • Also back pressure
    • As upstream nodes become overfilled, they tell down stream nodes to slow down.
    • Apparently, most networks don't support this.
    • And this is not a transport level issue.

TCP Congestion Control

• The sender responds to perceived congestion.
  • When perceived congestion is low, the sending rate increases.
  • When perceived congestion is high, the sending rate decreases.
• To do this each side of a connection keeps track of a congestion control window or CongWin.
• The formula LastByteSent-LastByteAcked ≤ min{CongWin, RcvWin}
• TCP defines a loss event as
  • a timeout
  • The receipt of three duplicate ACKs
• When a loss even occurs, TCP declares the network to be congested.
• When no loss is occurring, TCP uses a round trip time (RTT) estimate to adjust CongWin.
  • The RTT is the time between when a segment is handed to TCP and when the ACK is received.
  • A sample RTT is measured periodically for one packet at a time.
  • But only for segments transmitted once.
  • The average RTT is computed by means of a weighted average.
  • EstimatedRTT = (1-α)EstimatedRTT + &alpah;SampleRTT
  • It is suggested α=0.125
  • This average puts more weight on recent samples than older ones.
  • This allows response to changing network conditions.
  • In statistics this is called an Exponential weighted Moving Average.
  • This is because the weight of old values decay exponentially fast.
  • A deviation in RTT can be found in the same manner.
  • DevRTT = (1-Β)DevRTT + Β |Sample RTT- Estimated RTT|
  • Kurose mentions that TimeoutInterval = EstimatedRTT + 4 DevRTT
  • Stallings has a nice picture of this on page 685
• TCP uses the RTT to adjust the window.
  • If ACK rate is slow, (RTT high) the window is made slightly bigger.
  • If ACK rate is fast (RTT low) the window is made much bigger.
  • Thus TCP is called self clocking
• The TCP Congestion Control Algorithm consists of three parts.
  • Additive increase, multiplicative decrease
  • slow start
  • reaction to timeout events.
• Additive Increase, Multiplicative Decrease
  • When a decrease needs to occur, the packet that tells us to decrease has probably been delayed.
  • In the case of a loss event, the window is cut in half.
  • When a new ACK (not a dup) arrives the window size is increased
  • Kurose suggests that the window size be increased by MSS(MSS/CongWin) each time this occurs.
  • This is known as congestion avoidance
  • And tends to produce a saw-toothed pattern in TCP connection.
  • 
• Slow Start
  • At the beginning of a connection, TCP sets CongWin to be 1
  • Since this will require a long time to ramp up, it will double the size
  • Consider the sequence:
    • Packet 1 is sent, CongWin = 1 (Iteration 1)
    • Packet 1 is ACKed, CongWin = 2
    • Packets 2 and 3 are sent, CongWin = 2 (Iteration 2)
    • Packet 2 is ACKed, CongWin = 3
    • Packet 3 is ACKed, CongWin = 4
  • Reaction to Timeout Events
    • After a triple duplicate ACK the window size is cut in half
    • After a timeout,
      • the window size is set to 1
      • It is allowed to grow as in slow start until the window size reaches 1/2 of the level where the timeout occurs.
      • Then it grows normally.