Transcript EECS 122 Communications Networks

Congestion Control - Supplementary
Slides are adapted on Jean Walrand’s
Slides
TOC: Congestion Control
Congestion control for bandwidth sharing
Cheating TCP
Buffer Size
ECN
RED
TCP Unfairness
TCP Vegas
2
Congestion Control: Questions
How to avoid network congestion?
How to recover from congestion?

Congestion occurs at access link and access
network
How to share the links bandwidth?


If bandwidth is allocated and enforced
properly, no congestion should occur.
Can improve treatment of flows
 E.g., one flow should not get a much smaller
fraction of bandwidth
 Some flows might need some guaranteed
bandwidth


Discovering available bandwidth
What is fair?
3
Questions: Available bandwidth?
Example:
x
A
10
10
C
y
= router
3
3
10
E z
6
10
D
3
10
F
B
10
= host
= link with bandwidth of 3Mbps
(same for 6 and 10)
x, y, z = throughput of flows
4
Questions: Available bandwidth?
Example:
x
A
10
10
C
y
3
10
E z
6
10
D
3
10
F
B
10
• What is available bandwidth? (See later)
• How does A “discover” the available bandwidth to B?
• Some approaches:
1. Reservation: e.g., Telephone
2. Adapt to congestion: TCP
3. Pricing congestion: research topic
5
Available bandwidth: Reservation
x
A
10
10
C
y
3
10
E z
6
10
D
3
10
F
B
10
1.
2.
3.
4.
Routers (or manager) keep track of reserved rates
A requests a rate R to B from the network
The network figures out if R is available
If R is available, routers (or manager) update
reservations and confirm to A
5. Note: complex, slow, requires connection setup and
enforcement
6
Available bandwidth: Adapt
x
A
10
10
C
y
3
10
E z
6
10
D
3
10
F
B
10
1. Transmit and slow down if congestion occur
2. Example:
• Initially: x= 0, y = 3, z = 3
• Then A increases its rate; C and E notice congestion
and slow down
• Later, C stops: A and E increase rates
3. Notes:
• No guarantees: throughput may drop
• Key question: how to adapt rates, e.g., TCP
7
Available bandwidth: Pricing
Example:
A
10
10
C
y
x
3
10
E z
6
10
D
3
10
F
B
10
• When they get saturated, routers mark packets
• If a flow with rate R uses saturated links, it
gets marks with rate R
• Each mark costs one unit
• Source slows down if price becomes excessive
• x= 1+, y = 2+, z = 2+
 pA = 1 + 1; pC = pE = 2
• x = 2+, y = 1+, z = 1+
 pA = 2 + 2; pC = pE = 1
8
Questions: What is Fair?
Example:
A
10
10
C
y
x
3
10
E z
6
10
D
3
10
F
B
10
• x = y = z = 1.5: fair in max-min sense
• x = 0, y = z = 3: maximizes x + y + z
• 5x = 4y = 4z: equalizes resources flows use
with x = 1.33, y = z = 1.67
• What if AB needs 2Mbps?
(and is willing to pay for it)
9
Cheating: Increase Faster
A
D
C
x
C
B
y
E
y
x increases by 2 MSS/RTT per RTT
y increases by 1 MSS/RTT per RTT
Limit rates:
x = 2y
x
10
Cheating: Increase Faster
C = 50
x
A
B
y
D
E
60
50
40
20
10
time
487
460
433
406
379
352
325
298
271
244
217
190
163
136
109
82
55
28
0
1
Rate
30
11
Cheating: Start SS with CongWin > 1
A
D
x
y
C
B
E
x starts SS with CongWin = 4
y starts SS with CongWin = 1
12
Cheating: Open Many Connections
A
D
x
C
y
B
E
Assume
• A starts 10 connections to B
• D starts 1 connection to E
• Each connection gets about the same throughput
Then A gets 10 times more throughput than D
13
ECN: Explicit Congestion Notification
Standard TCP:


Losses needed to detect congestion
Wasteful and unnecessary
ECN:



When congested, routers mark (IP) packets instead of
dropping them
Destination marks ACKs of marked packets
Source set CongWin = CongWin/2 when it sees mark
Advantages:


No time wasted to retransmit
Link errors not confused with congestion
 Example: without ECN, at wireless link, packets can get
corrupted by noise and interference, and get dropped
eventually. Sender will think congestion has occurred.
14
Explicit Congestion Notification
Illustration:
A
B
A
B
CongWin =
CongWin/ 2
15
Explicit Congestion Notification
Backward Compatibility:
Unused bits from TCP and IP headers are used
for ECN.
One bit in IP header indicates if hosts
implement ECN
If it does, router marks packet
If it does not, router drops packet
16
RED
Random Early Detection:
As queue builds up, drop or mark packets
with increasing probability (before queue
gets full)
Advantages:

Avoids penalizing streams with large bursts
 This is done by keeping the queue size smaller than
the buffer size


Earlier marking reduces dropped packets
De-synchronizes the source behaviors
17
RED: Illustration
C Mbps
PACKETS
• Calculate recent average of queue length: Qav
Qav(n+1) = (1 – b) Qav(n) + b Q(n)
0<b<1
• Determine drop or mark probability p(Qav):
1
k
0
L
Qav
H
18
Router Buffers: Rule of Thumb
Imagine that all connections on input port with rate R
“burst” for RTT seconds (until stopped by RED)
Router must store RxRTT for each port
Example:



40 Gbps throughput (sum of port rates)
RTT = 200 ms (worst case?)
Then storage = 8 Gbits = (about) 1 GByte
Question: Is this reasonable?
19
Unfairness
Fact:

TCP favors connections with short RTT
Cause:


Increase rate is 1 MSS/RTT, so that it is faster for
connections with small RTT
Recall our discussion of “Cheating RTT”
It is quite possible for a connection to get only a
few percent of its fair share
Solutions:


Modify TCP to increase in proportion to RTT?
Problem: Estimate of RTT is noisy
TCP Vegas (see next)
20
TCP Vegas
Consider one queue:
A
D
x
y
C
B
E
Assume both connections have the same backlog
Then they have the same throughput …
Vegas Algorithm:
Estimate backlog by
Q = Outstanding – Rate  Base_RTT
Rate = Bytes_Sent_Successfully / Current_RTT
If Q > 3 MSS, then slow down; otherwise, speed up
Problem: Reno clobbers Vegas (unlike in real life)
21