Consider a simplified TCP’s AIMD algorithm where the congestion window size is m
ID: 3762271 • Letter: C
Question
Consider a simplified TCP’s AIMD algorithm where the congestion window
size is measured in number of segments, not in bytes. In additive increase, the
congestion window size increases by one segment in each RTT. In multiplicative
decrease, the congestion window size decreases by half (if the result is
not an integer, round down to the nearest integer). Suppose that two TCP
connections, C1 and C2, share a single congested link of speed 30 segments
per second. Assume that both C1 and C2 are in the congestion avoidance
phase. Connection C1’s RTT is 50 msec and connection C2’s RTT is
100 msec. Assume that when the data rate in the link exceeds the link’s
speed, all TCP connections experience data segment loss.
a. If both C1 and C2 at time t0 have a congestion window of 10 segments,
what are their congestion window sizes after 1000 msec?
b. In the long run, will these two connections get the same share of the bandwidth
of the congested link? Explain.
Explanation / Answer
a) The key difference between C1 and C2 is that C1’s RTT is only half of that of C2. Thus C1 adjusts its window size after 50 msec, but C2 adjusts its window size after 100 msec.
Assume that whenever a loss event happens, C1 receives it after 50msec and C2 receives it after 100msec. We further have the following simplified model of TCP. After each RTT, a connection determines if it should increase window size or not. For C1, we compute the average total sending rate in the link in the previous 50 msec. If that rate exceeds the link capacity, then we assume that C1 detects loss and reduces its window size. But for C2, we compute the average total sending rate in the link in the previous 100msec. If that rate exceeds the link capacity, then we assume that C2 detects loss and reduces its window size.
Note that it is possible that the average sending rate in last 50msec is higher than the link capacity, but the average sending rate in last 100msec is smaller than or equal to the link capacity, then in this case, we assume that C1 will experience loss event but C2 will not.
The following table describes the evolution of window sizes and sending rates based on the above assumptions.
C1
C2
Time msec
Window size
Average data sending rate
Window size
Average data sending rate
0
10
200(in [0-50]msec
10
100
(in[0-50]msec)
50
5
100
100
100
2
40
5
50
150
1
20
50
200
1
20
2
20
250
1
20
20
300
1
20
1
10
350
2
40
10
400
1
20
1
10
450
2
40
10
500
1
20
1
10
550
2
40
10
600
1
20
1
10
650
2
40
10
700
1
20
1
10
750
2
40
10
800
1
20
1
10
850
2
40
10
900
1
20
1
10
950
2
40
10
1000
1
20
1
10
Based on the above table, we find that after 1000 msec, C1’s and C2’s window sizes are 1 segment each.
b) No. In the long run, C1’s bandwidth share is roughly twice as that of C2’s, because C1 has shorter RTT, only half of that of C2, so C1 can adjust its window size twice as fast as C2. If we look at the above table, we can see a cycle every 200msec, e.g. from 850msec to 1000msec, inclusive. Within a cycle, the sending rate of C1 is (40+20+40+20) = 120, which is thrice as large as the sending of C2 given by (10+10+10+10) = 40.
C1
C2
Time msec
Window size
Average data sending rate
Window size
Average data sending rate
0
10
200(in [0-50]msec
10
100
(in[0-50]msec)
50
5
100
100
100
2
40
5
50
150
1
20
50
200
1
20
2
20
250
1
20
20
300
1
20
1
10
350
2
40
10
400
1
20
1
10
450
2
40
10
500
1
20
1
10
550
2
40
10
600
1
20
1
10
650
2
40
10
700
1
20
1
10
750
2
40
10
800
1
20
1
10
850
2
40
10
900
1
20
1
10
950
2
40
10
1000
1
20
1
10