COMP 3234B
Computer and Communication Networks
2nd semester 2020-2021
Transport Layer (V)
Prof. C Wu
Department of Computer Science The University of Hong Kong
Roadmap
Transport layer
Principles behind transport-layer services
multiplexing/demultiplexing (ILO1, 2) reliable data transfer:(ILO 2, 3)
rdt 1.0
rdt 2.0, 2.1, 2.2 rdt 3.0
GBN
selective repeat
Transport protocols in the Internet (ILO 2, 3) TCP: RDT, flow control, congestion control UDP
application
ttransporrtt
network
link
physical
Principles of congestion control
Congestion
informally: “too many sources sending too much data too fast for network to handle”
manifestations (or cost) of congestion
1. long queueing delays at the routers
2. retransmissions due to packet loss (buffer overflow at routers) 3. unnecessary retransmissions due to large delays
and more
Congestion control is a top-10 networking problem
Example congestion scenario
Scenario
two senders, two receivers, one router with finite buffers
in : ave. rate application layer at host A/B sends data to transport layer
R =>nocongestion < C
: ave. rate transport layer at host A/B sends in2 in 0
no loss occurs and data, including retransmissions ( in ) = = out: ave. receiving rate at application in
in in out layer of the receiver
R: maximum transmission rate at the router
Host A
λin : original data λout λ'in : original data, plus
retransmitted data
Host B
finite buffer with
finite shared output
shared output link
link buffers
Example congestion scenario (cont’d)
R
R/2
lin
C
=> congestion
in >
queueing delay is large (cost of congestion 1)
retransmissions due to packet loss (buffer overflow at routers) (cost of congestion 2) unnecessary retransmissions due to large delays (cost of congestion 3)
2
R/2
lin R/2
Host A
λin : original data λout λ’in : original data, plus
retransmitted data
Host B
finite buffer with
finite shared output
shared output link
link buffers
lout
delay
Congestion control approaches
Two broad approaches towards congestion control:
End-to-end congestion control:
no explicit feedback from network
congestion inferred from end-system observation: loss, delay
e.g., approach taken by TCP
Network-assisted congestion control:
routers provide feedback to end systems
proposed/implemented extensions to TCP and IP
TCP congestion control
End-to-end congestion control Approach
Have each sender limit its sending rate as a function of perceived network congestion level
little congestion (no packet loss) -> increase rate congestion (packet loss occurs) -> reduce rate
To implement such an approach, problems to resolve include
How does sender perceive congestion?
What does sender control in order to limit the sending rate? What algorithm does sender apply to adjust sending rates as a function of perceived congestion?
Limit sending rate
TCP flow control (cont’d)
How TCP flow control works
What does sender control to limit the sending rate?
congestion window (CongWin)
At TCP receiver
spare room in buffer = RcvWindow = RcvBuffe [LastByteRcvd – LastByteRead]
✦ a variable, whose value is dynamically changed with perceived network congestion Receiver advertises spare room by including value
✦ the amount of unacked bytes at sender cannot exceed min of CongWin and RcvWindow: RcvWindow in segments to sender
RcvBuffer size set via socket options (typical defau many operating systems auto-adjust RcvBuffer
lastByteSent-LastByteAcked <=min{CongWin, RcvWindow}
Sender
sender sequence number space
Receiver
cwnd
CongWin
Sender limits unACKed data to RcvWindow
guarantees receive buffer does not overflow
LastByteRcvd LastByteRead
last byte ACKed
sent, not- yet ACKed (“in- flight”)
last byte sent
r
o
l
Limit sending rate (cont’d)
Roughly (if ignoring loss, transmission delay of a segment)
rate =
lastByteSent-LastByteAcked
RTT
If RcvWindow large,
lastByteSent-LastByteAcked <= CongWin
lastByteAcked
lastByteSent
receiver
RTT: Round Trip Time
sender
RTT
ack
rate =
CongWin RTT
Bytes/sec
Sender adjusts sending rate by adjusting CongWin !
Perceive congestion
How does sender perceive congestion?
loss event= timeout or 3 duplicate acks
TCP sender reduces rate (CongWin) after loss event
Algorithm to adjust CongWin
What algorithm to adjust CongWin as a function of perceived congestion?
TCP congestion control algorithm (three components)
slow start
AIMD
reaction after loss events
Slow start
When connection begins, CongWin = 1 MSS (Maximum Segment Size)
Example: MSS = 500 bytes & RTT = 200 msec, initial rate = 20 kbps
Available bandwidth may be >> MSS/RTT; desirable to quickly ramp up to respectable rate
Increase rate exponentially by doubling CongWin every RTT implemented by incrementing CongWin for every ACK
received
Until
a slow start threshold (ssthresh) is reached => begin AIMD
or first loss occurs =>
begin a new slow start, if loss is detected by timeout
begin fast recovery, if loss is detected by 3 duplicated ACKs
Host A
Host B
time
Why is it called Slow Start?
Initial rate is slow but ramps up exponentially fast
RTT
one segment
two segments
four segments
AIMD
Additive-Increase, Multiplicative-Decrease
multiplicative decrease: halving CongWin after a loss event but no lower than 1 MSS
additive increase: increase CongWin by 1 MSS every RTT, until loss detected implemented by increasing CongWin by 1 MSS ⇥ MSS whenever a new ack arrives
e.g., MSS 500 Bytes, CongWin 5000 Bytes, increase 50 bytes upon each ack
CongWin
CongWin
Saw tooth behavior: probing for bandwidth
Reaction to loss events
After a timeout event, follow slow start
CongWin set to 1 MSS
ssthresh is set to 1/2 of CongWin just before loss event
CongWin then grows exponentially
After 3 dup ACKs received for segment k, follow fast recovery (fast recovery is
recommended but not required component of TCP; implemented in newer version of TCP, TCP Reno)
ssthresh is set to 1/2 of CongWin
CongWin is cut in half (adding 3MSS to account for
3 duplicated ACKs received)
CongWin increased by 1 MSS for every duplicated
ACK received (for the missing segment k), until ACK for segment k arrives => then follow AIMD
a timeout event occurs => then follow slow start
Philosophy:
3 dup ACKs indicates network capable of delivering some segments timeout indicates a “more alarming” congestion scenario
TCP Tahoe (another version of TCP) always sets CongWin to 1MSS (upon timeout or 3 duplicate acks), and then follows slow start
Reaction to loss events (cont’d)
3 dup acks
TCP Reno
slow start
TCP Tahoe
(RTT)
CongWin (in MSS)
TCP congestion control summary
duplicate ACK dupACKcount++
slow start
new ACK
cwnd = cwnd+MSS
dupACKcount = 0
transmit new segment(s), as allowed
cwnd > ssthresh
Λ
timeout
ssthresh = cwnd/2 cwnd = 1 MSS dupACKcount = 0
retransmit missing segment
new ACK.
cwnd = cwnd + MSS (MSS/cwnd)
dupACKcount = 0
transmit new segment(s), as allowed
Λ
cwnd = 1 MSS ssthresh = 64 KB dupACKcount = 0
timeout
ssthresh = cwnd/2 cwnd = 1 MSS dupACKcount = 0
retransmit missing segment
dupACKcount == 3
ssthresh= cwnd/2
cwnd = ssthresh + 3MSS retransmit missing segment
congestion avoidance
duplicate ACK dupACKcount++
timeout
ssthresh = cwnd/2 cwnd = 1 dupACKcount = 0
retransmit missing segment
fast recovery
New ACK
cwnd = ssthresh dupACKcount = 0
dupACKcount == 3
ssthresh= cwnd/2
cwnd = ssthresh + 3 MSS retransmit missing segment
TCP Reno
duplicate ACK
cwnd = cwnd + MSS
transmit new segment(s), as allowed
TCP throughput
What’s the average throughout of a TCP connection as a function of CongWin and RTT?
if consider AIMD only:
When CongWin is W MSS, throughput is W · MSS RTT
Just after loss, window drops to (W/2) MSS, throughput to
W · MSS 2 RTT
rate =
CongWin RTT
Bytes/sec
Average throughout: W
0.75W · MSS RTT
CongWin
sender
RTT
receiver
ack
(RTT)
CongWin (in MSS)
TCP throughput II
TCPtthrroughputtI(IcIont’d) TCP throughput II
TCP throughput II
Throughput in terms of loss rate
TThrhroTruouhgugrohghuphpgupuhtutpitiunitntienetrertmermrsmsosfofolflofolslosossrartatete Throughput in terms of loss rate
loss rate L: ratio of # of segments lost over # of segments sent
loss rate L: ratio of # of segments lost over # of segmeWnt/s2 sent llolosssraratteteLL:::rarattiiotoiooofff##oofffseseeggmeennttstslloloststtooveveerr##oofffseseeggmeennttstsseseennttt
loss rate L: ratio of # of segments lost over # of segments sent # of segment sent per cycle: W W W
3 3W 3
∑
WWW WW333
+ +1++W=W/2(+n)=W+ W W W 3 3
W/2 2 WW/2/2 2
# of segment sent per cycle:W
##ooffsseseggmeennttssesennttppeerrccycycyclcele:: 3
# of segment sent per cycle:
4
1 segment lost per cycle 2 1 segment lost per cycle
n=n0= 0 n=0
8
11sseseggmeennttlolosststppeerrccycycyclcele 1 segment lost per cycle
loss rate: loss rate:
lolosssraratete:: loss rate:
L
€
for large W, for large W,
2 €€3 88 44
4 2 2
=>
33
W+W
8
2 € W++W
2
4 8 4
3
W 2 >>€W =>8
foforrlalargrgeeW,,33W>>W=>L≈8/3W=> W
for large W, 8 88
W
€ Average through€out: Average throughout:
3 8 3 8
MSS MSS
€€ AAvveverraraggeetththrrorouugghhoouu€utt:t:
Average throughout
WWW322
+ + 1 + + W = ( + n ) = W + W2
22∑28
11 L= 3 1113
+ + 1 + + W ∑= ∑
+ + + +1 1 + ++ +WW = = ( ( + +n n) )= = WW + +
WW +W
22284 2222 n=022884
L=W+W
L ≈ 8 / 3W
8 4 =>LL≈≈88/3/W3W 2 =>
32 2 333 24
W => L≈8/3W =>
W+W
3332 2 333 824
W≈
n=0( +n)=W ∑
84 WW
≈ W≈≈
888 3L 3L
W>>>WW => W >> W
22
=>
W ≈3L3L 3L
8 444
Thursday, 15 March 2012 Thursday, 15 March 2012
20
20
€
L=
L==3 22 3
⋅⋅ ≈≈
33 88 MMSSS
3 8 MSS 4 3L RTT
€4 3L RTT
€
€
⋅⋅ ≈≈ ⋅≈
€
€ €€
€
(RTT)
€ €
€€ €
(RTT)
(R(RTRTT)T) (RTT)
44 3L3L RRTTT € €4 3L RTT
€ €
:
€€
CongWin
CongWin
CongWin CongWin
C(ionnMgWSSin) CongWin
(in MSS)
(in MSS) (in MSS)
(in MSS)
(in MSS)
TCP fairness
Fairness: if K sessions share same bottleneck link of bandwidth R, each should have average rate of R/K
TCP connection 1
TCP connection 2
bottleneck router
link capacity R
TCP fairness (cont’d)
TCP is fair
Two competing TCP sessions (operating in congestion avoidance mode with AIMD)
Additive increase gives slope of 1, as throughout increases multiplicative decrease decreases throughput proportionally
Converge to fluctuations along the equal share line regardless of the starting point in the space
R
equal bandwidth share
loss: decrease window by factor of 2
congestion avoidance: additive increase
Connection 1 throughput
R
Connection 2 throughput
TCP round trip time and timeout
Q: how to set TCP timeout value? longer than RTT
but RTT varies
too short: premature timeout and unnecessary retransmissions
too long: slow reaction to segment loss
Q: how to estimate RTT?
SampleRTT: measured time from segment transmission until ACK receipt
never measure SampleRTT for retransmitted segments
SampleRTT varies from segment to segment
Measure a typical RTT by averaging several recent measurements
EstimatedRTT = (1- α)*EstimatedRTT + α*SampleRTT
❒ Exponential weighted moving average
❒ influence of past sample decreases exponentially fast
❒ typical value: α = 0.125
TCP round trip time and timeout (cont’d)
Example RTT estimation
350
300
250
200
150
RTT: gaia.cs.umass.edu to fantasia.eurecom.fr
100
1 8 15 22 29 36 43 50 57 64 71 78 85 92 99 106
time (seconnds)
SampleRTT Estimated RTT
RTT (milliseconds)
TCP round trip time and timeout (cont’d)
Setting the timeout
EstimatedRTT plus “safety margin”
safety margin: variation in EstimatedRTT
large variation in EstimatedRTT -> larger safety margin Estimate variation
how much SampleRTT deviates from EstimatedRTT
DevRTT = (1-β)*DevRTT + β*|SampleRTT-EstimatedRTT|
(typically, β = 0.25)
Then set timeout interval:
TimeoutInterval = EstimatedRTT + 4*DevRTT
Network-assisted congestion control
Proposed/implemented extensions to TCP and IP
router sets ECN (Explicit Congestion Notification) bits in IP header to indicate congestion
upon receiving an ECN indicated datagram, destination sets ECE (Explicit Congestion Notification Echo) bit in TCP header, to notify sender congestion in the network
upon receiving an ACK segment with an ECE bit set, source halves the congestion window and sets CWR (Congestion Window Reduced) bit in header of next TCP segment to the destination
source
TCP ACK segment
destination
application
transport
application
ECE=1
transport
network
CWR=1
network
link
link
physical
physical
ECN=00
ECN=11
IP datagram
Required reading
Computer Networking: A Top-Down Approach (7th Edition) Ch 3.6, 3.7, 3.5.3
Acknowledgement:
Some materials are extracted from the slides created by Prof. Jim F. Kurose and Prof. Keith W. Ross for the textbook.