Dynamics of AIMD For A Single Flow

Published by Keyboard Banger on

  • AIMD is a mechanism used by TCP to manage congestion on bottleneck link. the figure below shows a sample bottleneck link.
aimd-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.
tcp-congestion-control-sawtooth-AIMD

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.
AIMD-congestion-control-window-RTT

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.
AIMD-rate-window-size-rtt

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.
AIMD-congestion-control-buffer

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.
aimd-buffer-rtt-line-rate

There are intervals where the buffer is empty – © Nick McKeown, Stanford University

Categories: Networking Basics

Keyboard Banger

Keyboard Banger is a network engineer from Africa. He has been working in network support and administration since 2008. He started writing study notes about certification exams and technology topics a couple of years ago. When he's not writing articles, he can be found wandering on technical forums.

0 Comments

Leave a Reply

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