Dynamics of AIMD For A Single Flow

  • AIMD is a mechanism used by TCP to manage congestion on bottleneck link. the figure below shows a sample bottleneck link.
Both hosts compete on using the bottleneck link © Ratul Mahajan, Washington University
  • AIMD increases and decreases the size of the window to control the rate of the transmitter (the sending rate). AIMD increases the amount of outstanding segments to the point of network congestion. Once a congestion occurs, AIMD decreases that amount.
  • AIMD does not impact the egress link rate. The egress link will stay at 100% usage.
  • With AIMD, if we had to draw geometric intuition of the cumulative bits of outstanding segments sent per time, we will get a sawtooth shape. That’s why we call it AIMD Sawtooth.
AIMD sawtooth – © imada.sdu.dk
  • Does WFQ solve the congestion problem? no. it’s true that each flow will be put in its own queue and that the scheduler will serve queues in a fair manner. But the source host will not be notified in times of congestion. So it will still send at a constant rate.
  • Just like we saw that, in AIMD, the congestion window size has a geometric intuition of a sawtooth, RTT follows the variation of the congestion window size and so its geometric intuition has the same sawtooth form.
Both the congestion control window and RTT have a AIMD sawtooth form – © Nick McKeown, Stanford University
  • If R is the sending rate, then R = Window size (t) / RTT (t) , where R is a constant because RTT varies in the same shape as the variation of the window size. One thing to note is that the sending rate is not the same as the link speed.
The rate is constant in time – © Nick McKeown, Stanford University
  •  The buffer occupancy B has a geometric intuition in the form of a sawtooth also.
The buffer occupancy over time in the AIMD algorithm follows a sawtooth shape – © Nick McKeown, Stanford University
  • If C is the egress line rate, then the buffer size B must be at least equal to RTT * C if we want to have a constant ingress link rate R:

 condition: B >= RTT * C

  • If B < RTT * C, then at each AIMD drop, the buffer will stay empty for a period of time before filling up again when the transmitter resumes sending packets, and the egress link will be unused for that same duration of time. This is an unwanted behaviour because we don’t want the egress link to be idle.
There are intervals where the buffer is empty – © Nick McKeown, Stanford University

Be First to Comment

Leave a Reply

Your email address will not be published. Required fields are marked *