Bandwidth Allocation Models
- Open loop: reserve bandwidth before use
- Closed loop: use feedback to adjust rates
- Does host enforce allocation, or does network enforce it?
TCP uses additive-increase/multiplicative decrease
The additive-increase/multiplicative-decrease (AIMD) algorithm is a feedback control algorithm best known for its use in TCP congestion control.
AIMD combines linear growth of the congestion window when there is no congestion with an exponential reduction when congestion is detected.
Multiple flows using AIMD congestion control will eventually converge to an equal usage of a shared link.
The related schemes of multiplicative-increase/multiplicative-decrease (MIMD) and additive-increase/additive-decrease (AIAD) do not reach stability.1
The intuition is that all network participants approach the bandwidth efficient frontier at equal rates, but when the network becomes congested, those with larger allocations lose more bandwidth than those with smaller allocations, since the amount we decrease an actor's bandwidth is proportional to their allocation.
Utilization sawtooths along the efficient frontier towards the efficient point where bandwidth is fully utilized and shared fairly among participants.
AIMD only requires binary feedback from the network.
Feedback signals
Packet loss is a signal from the network that it's congested. It's hard to get wrong, but we hear about congestion late, since the network is already congested to the point where packets are dropped.
Using packet delay as a congestion has the advantage that we hear about congestion early, but we need to infer congestion from delay times.
Router indications of congestion mean we hear congestion early, but it requires router support.
This lecture video is useful.