Congestion Control In The Internet

Part 1:
Theory

1
Contents
1. What is the problem; congestion collapse
2. Efficiency versus Fairness
3. Definitions of fairness
4. Additive Increase Multiplicative Decrease (AIMD)
5. Slow start

No book; check the pdf uploaded on Moodle:

“Rate adaptation, Congestion Control and
Fairness: A tutorial”

2
1. Congestion Collapse

Jacobson, Van. "Congestion avoidance and control." ACM

SIGCOMM computer communication review. Vol. 18. No. 4.
ACM, 1988.
Example 1: Congestion due to greedy sources
Assume: Two flows S1 → D1 and S2 → D2.
Sources are greedy (i.e. send as much as they want); loss may happen
Loss is proportional to submitted traffic and links can be fully utilized
S1 D1
C1 = 100 Kb/s losses C4 = 100 Kb/s

C3 = 110 Kb/s

S2
C2 = 1000 Kb/s C5 = 10 Kb/s D2

What is the max throughput attained by flow S1 → D1?

A. 10 kb/s B. 50 kb/s. C. 100 kb/s. D. I don’t know
Solution
Answer A: Ratio of traffic that survives at 1: 110/(100 + 1000) = 10 %
Ratio of traffic that survives at 2: 100%
Ratio of traffic that survives at 3: 10/100 = 10 %
Both flows attain 10 kb/s even if the sources have different access links
and send at different rates!

S1 C1 = 100 Kb/s C4 = 100 Kb/s

D1
x41 = 10
C3 = 110 Kb/s

S2
C2 = 1000 Kb/s x52 = 10 D2
C5 = 10 Kb/s
Take-home message 1: greedy sources may be inefficient
A better allocation is:
S1: 100 kb/s
S2: 10 kb/s
The problem was that S2 sent too much (but it did not know)

S1 C1 = 100 Kb/s C4 = 100 Kb/s

D1
x4,1 = 10
C3 = 110 Kb/s

S2
C2 = 1000 Kb/s x5,2 = 10 D2
C5 = 10 Kb/s
 Example 2: Congestion collapse
Assume: Each source sends traffic 2 hops away at rate λ
e.g., source i, at node i, sends traffic to a destination at node i + 2
All links have the same capacity c
Loss is proportional to submitted traffic and links can be fully utilized

source i λ node
Let:
link i i+1
• λ′ = the survived rate of λ node i
at the first link link (i-1) λ′ link (i+1)
λ′′ = the survived rate of λ
λ′′
•
at the second link = throughput

➡ How much is λ′′ (i.e. the rate at which

destination i + 2 receive traffic)?
How much throughput each source can attain?








 Solution: Attained throughput λ′′
Observe that at each node i, the submitted traffic to link i equals: λ + λ′
c
If λ < there is no loss; so λ′′ = λ
•
2
c
If λ > there is loss:
•
2
Traffic survival ratio at each node = source i λ node
+ ′ link i i+1
Due to loss proportionality: node i
′= (1) link (i-1) λ′ link (i+1)
+ ′ λ′
λ λ′′
"= ′ (2)
+ ′

We solve (1) for ′,

plug the solution into (2)
and obtain a closed-form expression for "
λ
𝜆
𝜆
𝜆
𝜆

𝜆
𝜆




𝜆
𝜆

𝜆
𝜆






𝜆
𝜆



𝑐
𝑐
𝑐
 For large offered traffic load , the limit of throughput is 0
We obtain, for > :
2

2( )
λ 4
" = − −1 + 1+

λ′′

cong
estio
n col
lapse

So, as λ —> +∞, throughput —> 0

c/2 = 10
𝜆
λ
𝜆
𝑐
𝜆
𝑐
𝜆


𝑐
 Take-Home Message 2: Congestion collapse
• As the offered load increases, throughput decreases,
may even go to 0
• Sources must limit their sending rates and adapt to
network conditions;
otherwise inefficiency or congestion collapse may occur

λ′′

cong
estio
n col
lapse

c/2 = 10
λ


 2. Efficiency vs Fairness
A network should be organized so as to avoid inefficiency,
but being maximally efficient may cause other problems
Total pse
Colla
2M s
r
surfe
lo s e
net
inter

Example: what is the maximum total throughput in this network ?

A. 5 Mb/s
B. 10 Mb/s 0 1 flow
C. 20 Mb/s c=10 Mb/s c = 10 Mb/s
D. None of the above
E. I don’t know

1
Go to web.speakup.info
2
1 flow or
9 flows download speakup app
Join room
46045
𝑥
𝑥
𝑥
 Solution
Answer C 0 1 flow
c=10 Mb/s c = 10 Mb/s

1
Total throughput = 0 + 1 + 9 2 2
Maximize = 0 + 1 + 9 2
1 flow
9 flows
subject to 0 + 1 ≤ 10, 0 + 9 2 ≤ 10
over 0 ≥ 0, 1 ≥ 0 2 ≥ 0
The max can be obtained by linear programming, or directly here by inspection:
• ≤ 20 because 0 + 1 ≤ 10, 9x2 ≤ 10 − x0 and x0 ≥ 0
• = 20 is achieved with 1 = 10 and x2 = 10/9
therefore the max is 20 Mb/s
𝑥
𝑥
𝑥
𝜃
𝜃
𝑥
𝑥
𝑥
𝜃
𝑥
𝜃
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
 Solution
0 1 flow
c=10 Mb/s c = 10 Mb/s
And we can also prove that this is
the only maximizing allocation:

Find all 0 ≥ 0 1 ≥ 0 2 ≥ 0 subject to 1

0 + 1 ≤ 10 (1) 2
1 flow
0 + 9 2 ≤ 10 (2) 9 flows
0 + 1 + 9 2 = 20 (3)

By (1) and (3): 9 2 ≥ 10

Compare to (2): 9 2 = 10
Thus 0 = 0 (and 1 = 10, 2 = 10/9)

So, the max is achieved only if x0 = 0 —> rather unfair

𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
 Pareto Efficiency
• A feasible allocation of rates → is called Pareto-efficient (or Pareto-optimal),
iff increasing the rate of a flow must be at the expense of decreasing the rate
of some other flow
→ →
I.e. is Pareto-efficient iff : for any other feasible ′, ∃ : ′ > ⇒∃ : ′<
⇔ every flow has a bottleneck link =
for every flow there exists a link, used by , which is saturated,
i.e. its constraint is satisfied with equality

• Conversely: An allocation → is not Pareto-efficient iff it can be improved unilaterally,

→
i.e. there exists a feasible allocation ′, such that ′ > for some and ′ ≥ for all
𝑖
𝑖
𝑗
𝑗
𝑥
𝑥


𝑖
𝑥

𝑥
𝑗
𝑥

𝑥
𝑖
𝑗
𝑖
𝑗
𝑥
𝑥
𝑥
𝑖𝑖𝑖
𝑥
𝑥
𝑖
𝑗


𝑥
𝑥
 Example 0 =0

Is the allocation
10
{x0 = 0, x1 = 10, x2 = }
9
Pareto-efficient? 1 = 10

• Link 1 is bottleneck for flows 0 and 1 10

• Link 2 is bottleneck for flow 0 and all flows of type 2 x2 = for each
9

➡ Every flow has a bottleneck and cannot be increased unilaterally:

The allocation is Pareto-efficient.

‣ Note: the throughput-maximizing allocation is always Pareto-efficient.

𝑥
𝑥
 Which allocations are Pareto-Efficient ?

A. 0 = 1, 1= 0.5, 2 = 8, 3 = 1
Go to web.speakup.info
B. 0 = 1, 1 = 1, 2 = 8, 3 = 1 or

0 = 1, 1 = 1, 2 = 2, 3 = 7
download speakup app
C. Join room
46045
D. A and B
E. A and C
flow 0
F. B and C
2 Gb/s 9 Gb/s 10 Gb/s
G. All
H. None flow 1 flow 2 flow 3
I. I don’t know
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
 Solution
Answer F (B and C)

0 =1 0 =1 0 =1

2 Gb/s 9 Gb/s 10 Gb/s

1 = 0.5
2 =8 2 =8
3=1

Allocation A: 0 = 1, 1 = 0.5, 2 = 8, 3 = 1
Flow 1 does not have a bottleneck.
Its rate can be increased unilaterally.
For example, we can increase 1 to ′1 = 0.6 while leaving the other rates
unchanged and still obtain a feasible allocation.
Allocation A is not Pareto-efficient
𝑥
𝑥
𝑥

𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
 Solution
Allocation B: 0 = 1, 1 = 1, 2 = 8, 3 =1

Link 1 is bottleneck for 0 =1 0 =1 0 =1

flows 0 and 1
2 Gb/s 9 Gb/s 10 Gb/s
Link 2 is bottleneck for =1
1
flows 0 and 2 2 =8 2 =8
3=1
Link 3 is bottleneck for
flows 0, 2 and 3

Every flow has a bottleneck. None can be increased unilaterally.

Allocation B is Pareto-efficient.
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
 Solution
Allocation C: 0 = 1, 1 = 1, 2 = 2, 3 =7

Link 1 is bottleneck for 0 =1 0 =1 0 =1

sources 0 and 1
2 Gb/s 9 Gb/s 10 Gb/s
Link 3 is bottleneck for =1
1
sources 0, 2 and 3 2 =2 2 =2
3=7

Every flow has a bottleneck. None can be increased unilaterally.

Allocation C is Pareto-efficient.

Observation: link 2 is not saturated in this Pareto-efficient allocation.

𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
Recap
• Maximizing total throughput is Pareto efficient, but may be unfair
- e.g. in figure: max efficiency means Pareto efficiency,
but also means “shutting down flow 0”

So:
➡ Are there Pareto efficient allocations that are fair ?
➡ What is a good definition of fairness?
 3. Definition 1: Egalitarianism (or Neutrality):
”Allocate as much as possible but same to all.”
Go to web.speakup.info
or
download speakup app
Join room
In this example, what is a fair/egalitarian allocation? 46045

A. 0= 1=
= 0.5 2 /
B. 0= 2=11= /
10
C. 0= 1= 2= /
9
D. All of them
E. None of the above
F. I don’t know
𝑥
𝑥
𝑥
𝑀
𝑏
𝑠
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑀
𝑀
𝑏
𝑏
𝑠
𝑠
 Solution
Maximize = 0 = 1 = 2 subject to
2 ≤ 10
10 ≤ 10
with ≥ 0

The solution is = 1 Mb/s

Answer B
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
 Egalitarianism is not always Pareto-efficient
• Egalitarianism gives = 1 Mb/s to all
but, we could give more to 1
without hurting anyone
➡ So, allocation is not Pareto-efficient

• A better allocation would be:

{ 0 = 1, 1 = 9, 2 = 1}, which is
- Pareto-efficient (= every resource has a bottleneck)
- but also “fair” (= it gives to every one at least as much as egalitarianism)
- in fact, this is a max-min fair allocation [see next slide]
𝑥
𝑥
𝑥
𝑥
𝑥
 Max-Min fairness
A feasible allocation
→ is max-min fair iff for any other feasible allocation
→
′, ( ∃ : ′ > ⇒ ∃ : ′ < and ≤ )

I.e. for every flow , increasing its rate must force the rate of some other, not richer
flow j to decrease

Note: the max-min fairness implies Pareto-efficiency (converse is not true)

𝑖
𝑖
𝑗
𝑗
𝑥

𝑖
𝑥

𝑥
𝑗
𝑥

𝑥
𝑗
𝑖
𝑥
𝑥
𝑖
𝑥
Which allocations are max-min fair ?
A B
x0 = 0 Mb/s x0 = 1 Mb/s
x1 = 10 Mb/s x1 = 9 Mb/s
10
x2 = Mb/s x2 = 1 Mb/s
9

A. A
B. B
C. A and B
D. None Go to web.speakup.info
or
E. I don’t know download speakup app
Join room
46045
 A B
Solution x0 = 0 Mb/s x0 = 1 Mb/s
x1 = 10 Mb/s x1 = 9 Mb/s
10
x2 = Mb/s x2 = 1 Mb/s
9

Allocation A
Increase 0 (e.g. 0 ← 1 ) and decrease 1 ( 1 ← 9) and 2 ( 2 ← 1);
this does not contradict fairness because 1 and 2 are larger than 0
So, there exists one increase that does not contradict fairness
A is not max-min fair

Allocation B
If I increase 0 I must decrease 2 ⇒ contradicts fairness
If I increase 1 I must decrease 0 ⇒ contradicts fairness
If I increase 2 I must decrease 0 ⇒ contradicts fairness
Any increase contradicts fairness
B is max-min fair
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
Max-Min fairness: properties and computation
Given a set of constraints, i.e. a set of feasible allocations:
a. if it exists, the max-min fair allocation is unique
b. there does exist a max-min fair allocation, if the set of feasible allocations is
convex (which is the case in networks, as we have linear constraints)
c. the max-min fair allocation is Pareto-efficient (converse is not true)

For a convex set of feasible rates (as in our case), the unique max min fair
allocation is obtained by the water-filling algorithm:
1. mark all flows as non frozen
2. do
3. increase the rate of all non frozen flows to the largest possible common value
4. mark flows that use a saturated link as frozen
5. until all flows are frozen
 Water-Filling:
Example

Step 1:
• maximize such that 0= 1= 2= and all constraints are satisfied;
we find = 1, hence 0= 1= 2=1;
• link 2 is saturated, is used by flows 0 and 2 ⇒ mark flows 0 and 2 as frozen
Step 2 :
• maximize such that 1 = , with 0= 1, 2 = 1 and all constraints are satisfied; we
find = 9, hence 0 = 2 = 1 and 1=9
• link 1 is saturated, is used by sources 0 and 1 ⇒ mark flow 1 as frozen; all flows are
frozen, STOP.
The max-min fair allocation is 0 = 2 = 1 and 1 = 9
𝑥
𝑥
𝑥
𝑡𝑥
𝑥
𝑡
𝑡𝑥
𝑥
𝑥
𝑡
𝑥
𝑥
𝑥
𝑡
𝑥
𝑥
𝑥
𝑥
𝑡
 What is the max-min fair allocation ?
0
c c c c

1 2 3 4

A. = ∀
2
2
B. 0= , ∀ ≠0 =
3 3
3
C. 0= , = ∀ ≠0
4 4
4
D. 0 = , = ∀ ≠0
5 5 Go to web.speakup.info
or
E. None of the above download speakup app
F. I don’t know Join room
𝑖
𝑖
𝑖
46045
𝑖
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑖
𝑖
𝑖
𝑥
𝑖
𝑥
𝑥
𝑥
𝑥
𝑥
𝑐
𝑐
𝑐
𝑐
𝑐
𝑐
𝑐
 Solution
0
c c c c

1 2 3 4

Answer A
The max-min fair allocation via water-filling gives the same rate to all flows
2

But this seems “not fair enough” in terms of resource usage!

Actually, one could claim that x0 should be penalized and get 5x less, because it uses 5x more
resources (answer D).
This is what led to the definition of proportional fairness…
𝑥
𝑥
𝑥
𝑥
𝑥
𝑐
 Definition of Proportional Fairness
→
A feasible allocation → is proportionally fair iff → > 0 and for any other feasible ′, it holds:
x′i − xi
∑ xi
≤0
i

I.e.: An allocation is proportionally fair, if for any other allocation, the total rate of change or
Δxi
∑ xi
relative change is non-positive, i.e. “the other rates are relatively worse in total”
i

→ → x′i − xi
∑ xi
Conversely: An allocation > 0 is not proportionally fair iff there exists ′ s.t.: > 0.
i

Two important points:

- Sum of all rates of changes matters, not only one
- Relative changes matter, not absolute
𝑥
𝑥


𝑥
𝑥
𝑥


Which
allocations
are
proportionally
fair ?
A. A
B. B
C. A and B
D. None
E. I don’t know
Go to web.speakup.info
or
download speakup app
Join room
46045
 Solution

Answer D
Let ← + for = 1…4 and 0 ← 0 − .
If is small enough (i.e. 0 < ≤ ), the new allocation is feasible (= within constraints).
2
The total rate of change is − +4 > 0.
2 2
So, we could change the allocation and obtain a positive total rate of change.

A is not proportionally fair

𝑐
𝑐
𝛿
𝑖
𝑖
𝑥
𝑥
𝑖
𝛿
𝑥
𝑥
𝛿
𝛿
𝛿
𝛿
𝑐
 Solution

Let 2 ← 2 + and 0 ← 0 − 9 ; 1 ← 1 + 9 .
1
If is small enough (i.e. 0 < ≤ ), the new allocation is feasible.
9
9 9
The total rate of change is − + + 9 = > 0.
1 9 1
So, we could change the allocation and obtain a positive total rate of change.

B is not proportionally fair

So, min-max fairness does not imply proportional fairness

𝛿
𝛿
𝑥
𝑥
𝑥
𝛿
𝑥
𝑥
𝑥
𝛿
𝛿
𝛿
𝛿
𝛿
𝛿
 Proportional Fairness: properties and computation
a. A proportionally fair allocation is Pareto-efficient
b. Given a convex set of constraints for the rates (as in our case),
the proportionally fair allocation exists and is unique
c. It is obtained by maximizing

( ) ∑ log
→ ≔

over all feasible allocations

( ) ∑
Intuitive explanation via gradient: → = .

So, deviating from the maximum means going towards a non-positive gradient
=> the total rate of change is non-positive
𝑖
𝑖
=> the maximizing allocation is proportionally fair!
𝑖
𝑥
𝑖
𝑑
𝐽
𝑥
𝐽
𝑥
𝑥
𝑖
𝑑
𝑥
 Let us compute the proportionally fair allocation
0
c c c c

1 2 3 4

We have to solve the optimization problem:

max = log 0 + log 1 + log 2 + log 3 + log 4
subject to
0+ 1≤

0+ 2≤

0+ 3≤

0+ 4≤
We can use convex optimization techniques to solve this, but here we can also do a direct solution…
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑈
𝑥
𝑥
𝑥
𝑥
𝑐
𝑐
𝑐
𝑐
𝑥
𝑥
𝑥
𝑥
𝑥
 Let us compute the proportionally fair allocation
0
c c c c

1 2 3 4

We have to solve the optimization problem:

max = log 0 + log 1 + log 2 + log 3 + log 4
subject to
0+ 1≤

0+ 2≤

0+ 3≤

0+ 4≤
Observe: at the maximum point, we must have equality in all constraints otherwise we can increase
(i ≠ 0) and increase U (i.e. find a better maximum).
Therefore, for any choice of 0 = ∗, we must have 1 = 2 = 3 = 4 = − ∗.
𝑖
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑈
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑐
𝑐
𝑐
𝑐
𝑥
𝑥
𝑥
𝑥
𝑐
𝑥
𝑥
𝑥
𝑥
 Let us compute the proportionally fair allocation
0
c c c c

1 2 3 4

So, we rewrite the optimization problem as:

max = log ∗ + 4log( − ∗
)
subject to 0 < ∗ <
This is a 1d problem, can be solved by computing the derivative
1 4
We find = −
∗ ∗ − ∗
∗ − ∗
There is a maximum for = i.e. ∗ =
4 5
The proportionally fair allocation is
4
0 = , 1 = 2 = 3 = 4 =
5 5
𝑑
𝑥
𝑥
𝑐
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑈
𝑥
𝑐
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑐
𝑑
𝑈
𝑐
𝑐
𝑐
𝑥
𝑐
 Which one is the
proportionally fair
allocation? (in Mb/s)
(only one answer)

A. 0 = 1, 1 = 9, 2 = 1
B. 0 = 0.909, 1 = 9, 2 = 1 . 010
C. 0 = 1 . 009, 1 = 8.991, 2 = 0.999
D. 0 = 0.909, 1 = 9 . 091, 2 = 1 . 010
E. I don’t know
Go to web.speakup.info
or
download speakup app
Join room
46045
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
Solution

Answer D. Why?

• We saw earlier that A is not proportionally fair

• B is not Pareto-efficient (you can increase x1 only)—therefore is also not
proportionally fair
• C goes in the wrong direction (gives more to 0 than to 2) and is probably not
proportionally fair
• D is probably the correct answer
 Solution

We can compute the proportionally fair allocation

with the same trick as before; and obtain
∗
0 =
∗
1 = 10 −
∗
10 −
2=
9
∗ 10 −
with that maximizes log + log(10 − ) + 9log
9
∗ 10
= Mb/s
11
This is allocation D
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
𝑥
 Utility Fairness
One can interpret proportional fairness as the allocation that maximizes a
∑ ( )
global utility with ( ) = log .

If we take some other utility function, we have what is called a utility fairness.
It can be shown that max-min fairness is the limit of utility fairness when the
utility function converges to a step function.
But max-min fairness cannot be expressed exactly as a utility fairness (only at the limit).

( ) = log : proportional fairness

Utility

1
( )= 1− : large ⇒ ≈ max min fairness
𝑖
𝑥
𝑚
Rate
𝑈
𝑥
𝑖
𝑖
𝑖
𝑖
𝑖
𝑈
𝑥
𝑈
𝑥
𝑥
𝑈
𝑥
𝑚
𝑥
𝑥
Recap
Sources should adapt their rate to the state of the network in order to avoid
inefficiencies and congestion collapse.
This is called “congestion control”.

Such control mechanism should target a form of fairness that is Pareto-efficient

e.g. max-min fairness or proportional fairness.
4. Towards a practical implementation of congestion control
How can congestion control be implemented ?
Explicit/ Rate-based: tell every host how fast it can send
MPLS networks (smart grid)
Cellular networks

Hop by hop = backpressure: STOP/GO signals sent upstream

Gigabit LAN switches

Fair Queuing per Flow: One queue per flow / per user, served round robin
Cellular networks, industrial networks, in-vehicle networks

End-to-end: hosts “taste the water” and increase or decrease their sending rate
using a host congestion control algorithm
The solution in the Internet
Additive Increase Multiplicative Decrease (AIMD)
• First congestion control algorithm deployed in the Internet and before that, in
Decnet (the “Decbit”)
• Still widely deployed today

Raj Jain

Raj Jain, K.K. Ramakrishnan,

and Dah-Ming Chiu.
Congestion avoidance in
computer networks with a
connectionless network layer.
Technical Report DEC-TR-506,
Digital Equipment Corporation,
August 1987 August 1987.
 A Simple Network Model
Feedback ( )

Rate ( ) Capacity

Network sends a one-bit feedback :

∑
( ) = 0 if ()≤ —> positive feedback

∑
( ) = 1 if ()> —> negative feedback

Sources reduce rate ( + 1) if ( ) = 1, increase otherwise

➡ Question: what form of increase/decrease laws should one pick?
𝑖
𝑖
𝑖
𝑖
𝑖
𝑖
𝑥
𝑥
𝑡
𝑡
𝑐
𝑐
𝑦
𝑦
𝑥
𝑦
𝑥
𝑐
𝑦
𝑡
𝑡
𝑡
𝑡
𝑡
𝑡
 Linear Laws
We consider linear laws
if ( ) = 1 then xi(t + 1) = u1 ⋅ xi(t) + v1
if ( ) = 0 then xi(t + 1) = u0 ⋅ xi(t) + v0

We want to decrease when ( ) = 1, so

1 ≤ 1 and 1 ≤ 0 and at least one inequality must be strict
Multiplicative Additive
decrease factor decrease term

We want to increase when ( ) = 0, so

0 ≥ 1 and 0 ≥ 0 and at least one inequality must be strict
Multiplicative Additive
increase factor increase term
𝑦
𝑦
𝑡
𝑡
𝑦
𝑦
𝑣
𝑢
𝑣
𝑢
𝑡
𝑡
 1 = 0.5, 1 = 0 (multiplicative decrease)
Example = 1, 0 = 1 (Mb/s) (additive increase)
0

So fairness seems to be achieved using this idea,

but after some time and oscillations!
𝑢
𝑢
𝑣
𝑣
 Analysis of Linear Control schemes
We want to achieve efficiency and fairness
We could target either max-min fair or proportionally fair allocations
Here (in the example with 1 link) they are the same
We will now analyze the impact of each of the four coefficients 0, 1, 0 and 1.
𝑢
𝑣
𝑢
𝑣
 Zoom on 2 sources using a single link
1= 2
target
Rate of source 2
2
()=1
()=0
→
()=0

1 + 2 ≤

Rate of source 1

1
𝑥
𝑥
𝑥
𝑥
𝑥
𝑦
𝑦
𝑦
𝑡
𝑡
𝑡
𝑥
𝑥
𝑐
 1 = 2
Zoom on 2
sources ;
1
say what is →
true 2
2

A. 1 = additive increase,
1
2 = multiplicative increase
B. 1 = multiplicative increase
2 = additive increase,
C. None of the above Go to web.speakup.info
D. I don’t know or
download speakup app
Join room
46045
𝑥
𝑥
𝑥
𝑥
𝑥
 1 = 2

→+( , )
0 0
→
Solution 1 0
→
2
2

1 = additive increase,
2 = multiplicative increase

Answer A
𝑢
𝑥
𝑥
𝑥
𝑣
𝑣
𝑥
𝑥
𝑥
𝑥
 → + ( , Additive increase
0 0)
→
0

Multiplicative decrease Multiplicative increase

Additive decrease

1. Additive decrease worsens fairness (goes away from 1 = 2)

and should be avoided ⇒ decrease should be mutiplicative
2. Additive increase is the only move that increases fairness and
should be therefore be included ⇒ increase should be additive
𝑢
𝑥
𝑥
𝑣
𝑣
𝑥
𝑥
More generally…

Among the linear controls, only additive increase – multiplicative decrease (AIMD)
tends to bring the allocation towards fairness and efficiency.

This is what was implemented in the Internet after the first congestion collapses.
In a more complex network setting, what type of
fairness does AIMD achieve?
A. Max-min
B. Proportional
C. None of the above
D. I don’t know
 Fairness of AIMD
Answer C
AIMD with: additive increase + , multiplicative decrease × (1 − ), and one update
per time unit implements utility fairness, with utility of flow given by

( ) = log , where xi = rate.

+
The fairness of AIMD is between max-min and proportional fairness, closer to
proportional fairness. [see “Rate adaptation, Congestion Control and Fairness: A Tutorial”]

≈maxmin AIMD
proportional fairness

rescaled utility functions;

AIMD is for = 0.5 = 1MSS per RTT = 100 ms
maxmin approx. is ( ) = 1 − −5
𝑖
𝑟
𝜂
𝑥
𝑖
𝑈
𝑥
𝑖
𝑟
𝜂
𝑖
𝑈
𝑥
𝑥
𝑟
𝜂
𝑥
5. Slow Start
• AIMD convergence can be accelerated when initial conditions are very different
• Slow start is an additional method, added to AIMD
• Used at beginning of connection and when losses are detected by timeout

Source 3

Source 1
 Slow Start
rate of this source
• For a short period of time increase the rate
multiplicatively (by 0, e.g. 0 = 2) until a
target rate is reached or negative feedback
target
is received

• If negative feedback is received, apply

multiplicative decrease (by 1, e.g.
1 = 0.25) to target rate and restart.
rate

time
• Exit slow start when target rate is reached
𝑢
𝑢
𝑤
𝑤
 Source 3
Target rate

Actual rate
End of slow start

Source 3 rate (all 3 sources)

With Slow Start

End of slow start

Source 1 time
 Source 3 3 sources
u1 = 0.5, v1 =0, u0 = 0, v0 = 0.01 (unit: Mb/s)
3rd source starts with rate v0

Without Slow Start

Source 1 time

Source 3 rate (all 3 sources)

With Slow Start

Source 1 time
Conclusion
Congestion control is necessary to avoid inefficiencies and collapses
A congestion control scheme aims at allocating rates according to some
form of fairness
In the internet, we use end-to-end congestion control with
≈ AIMD
Slow Start
and other refinements – see part 2: Congestion Control — Implementation