Introduction to Congestion Control [3]
Samuel Cheng
April 3, 2009
Congestion control started around late 80’s when people found that the In-
ternet of the time died every once a while because of major congestion. The first
congestion c ontrol algorithm is introduced by Jacobson in 1988 [2]. The basic
idea behind congestion control algorithm is simple: detect cong e stion and re-
duce transmission rate if congestion is detected; otherwise, increase transmission
rate.
Most congestion control a lgorithms detect congestion through packet losses.
These include various versions of TCP, such as TCP-Tahoe, Reno, NewReno,
SACK. On the other hand, some algorithms, such as TCP Vegas algorithm,
detect congestion thro ugh packet delays .
1 A Simple Example
To illustrate the idea, we will describe a simple two sources example describ e d
by Chiu and Jain [1]. Consider a link with capacity c and let the traffic of two
sources at time t be x
1
(t) and x
2
(t). Consider a simple 1−bit feedback from the
link, I(x
1
+ x
2
> c), where I is an indicator function that is equal to 1 if the
argument is satisfied and 0 otherwise. In other words, the link only feedbacks
the information whether the total traffic is larger or smaller than the capacity.
For source i, define the time derivative of x
i
(t) as
dx
i
(t)
dt
= ˙x
i
(t) = I(x
1
+ x
2
≤ C) − βx
i
I(x
1
+ x
2
> c). (1)
Basically, the source increase its own traffic if the total traffic is smaller than the
capacity and decrease it with a rate proportional to the current traffic otherwise.
To analyze this simple model, let us define y = x
1
− x
2
. If x
1
+ x
2
≤ c, we
have ˙x
1
(t) = ˙x
2
(t) = 1. Thus,
˙y(t) = 0. (2)
On the other hand, if x
1
+ x
2
> c, ˙y = −βy. Combining the two c ases, we have
˙y = −βyI(x
1
+ x
2
> c).
Now let V = y
2
, note tha t
˙
V = 2y ˙y = −2βy
2
I(x
1
+ x
2
> c). Since V cannot
be smaller than 0 and
˙
V is negative whenever x
1
+ x
2
> c and 0 fo r x
1
+ x
2
≤ c,
V can only keep decrea sing as time goes and so doe s y since V = y
2
.
1
