CN 08 Transport Layer - TCP Congestion Control

Chapter 3
Transport Layer
A note on the use of these PowerPoint slides:
We’re making these slides freely available to all (faculty, students,
readers). They’re in PowerPoint form so you see the animations; and
can add, modify, and delete slides (including this one) and slide content
to suit your needs. They obviously represent a lot of work on our part.
In return for use, we only ask the following:
 If you use these slides (e.g., in a class) that you mention their
source (after all, we’d like people to use our book!)
 If you post any slides on a www site, that you note that they are
adapted from (or perhaps identical to) our slides, and note our
copyright of this material.
Computer Networking: A
For a revision history, see the slide note for this page.
Top-Down Approach
Thanks and enjoy! JFK/KWR 8th edition
All material copyright 1996-2020
Jim Kurose, Keith Ross
J.F Kurose and K.W. Ross, All Rights Reserved Pearson, 2020
Transport Layer: 3-1
Transport layer: overview
Our goal:
 understand principles  learn about Internet transport
behind transport layer layer protocols:
services: • UDP: connectionless transport
• multiplexing, • TCP: connection-oriented reliable
demultiplexing transport
• reliable data transfer • TCP congestion control
• flow control
• congestion control

Transport layer: roadmap
 Transport-layer services
 Multiplexing and demultiplexing
 Connectionless transport: UDP
 Principles of reliable data transfer
 Connection-oriented transport: TCP
 Principles of congestion control
 TCP congestion control
 Evolution of transport-layer
functionality
Transport services and protocols
application
transport
 provide logical communication mobile network

network
data link
physical
between application processes national or global ISP
running on different hosts

 transport protocols actions in end
systems: local or
• sender: breaks application messages regional ISP
into segments, passes to network layer home network content

• receiver: reassembles segments into provider
network datacenter
messages, passes to application layer application
transport
network
network
 two transport protocols available to data link

physical
Internet applications enterprise

network
• TCP, UDP
Chapter 3: roadmap
• segment structure
• reliable data transfer
• flow control
• connection management
TCP: overview RFCs: 793,1122, 2018, 5681, 7323
 point-to-point:  cumulative ACKs
• one sender, one receiver  pipelining:
 reliable, in-order byte • TCP congestion and flow control
steam: set window size
• no “message boundaries"  connection-oriented:
 full duplex data: • handshaking (exchange of control
• bi-directional data flow in messages) initializes sender,
same connection receiver state before data exchange
• MSS: maximum segment size  flow controlled:
• sender will not overwhelm receiver

TCP segment structure
32 bits
source port # dest port # segment seq #: counting

ACK: seq # of next expected sequence number bytes of data into bytestream
byte; A bit: this is an ACK (not segments!)
acknowledgement number
head not
length (of TCP header) len used C EUAP R SF receive window flow control: # bytes
Internet checksum checksum Urg data pointer receiver willing to accept
options (variable length)

C, E: congestion notification
TCP options
application data sent by
RST, SYN, FIN: connection data application into
management (variable length) TCP socket

TCP sequence numbers, ACKs
outgoing segment from sender
Sequence numbers: source port # dest port #
sequence number
• byte stream “number” of acknowledgement number
rwnd
first byte in segment’s data checksum urg pointer
window size
Acknowledgements: N
• seq # of next byte expected

from other side sender sequence number space
• cumulative ACK sent sent, not- usable not

ACKed yet ACKed but not usable
(“in-flight”) yet sent
Q: how receiver handles out-of-
order segments outgoing segment from receiver
• A: TCP spec doesn’t say, - up

source port # dest port #
sequence number
to implementor acknowledgement number

A rwnd
checksum urg pointer
TCP sequence numbers, ACKs
Host A Host B
User types‘C’
Seq=42, ACK=79, data = ‘C’
host ACKs receipt
of‘C’, echoes back ‘C’
Seq=79, ACK=43, data = ‘C’
host ACKs receipt
of echoed ‘C’
Seq=43, ACK=80
simple telnet scenario

TCP connection management
before exchanging data, sender/receiver “handshake”:
 agree to establish connection (each knowing the other willing to establish connection)
 agree on connection parameters (e.g., starting seq #s)
application application
connection state: ESTAB connection state: ESTAB

connection variables: connection Variables:
seq # client-to-server seq # client-to-server
server-to-client server-to-client
rcvBuffer size rcvBuffer size
at server,client at server,client
network network
Socket clientSocket = Socket connectionSocket =

newSocket("hostname","port number"); welcomeSocket.accept();
TCP 3-way handshake
Server state
serverSocket = socket(AF_INET,SOCK_STREAM)
Client state serverSocket.bind((‘’,serverPort))
serverSocket.listen(1)
clientSocket = socket(AF_INET, SOCK_STREAM) connectionSocket, addr = serverSocket.accept()
LISTEN
clientSocket.connect((serverName,serverPort)) LISTEN
choose init seq num, x
send TCP SYN msg
SYNSENT SYNbit=1, Seq=x
choose init seq num, y
send TCP SYNACK
msg, acking SYN SYN RCVD
SYNbit=1, Seq=y
ACKbit=1; ACKnum=x+1
received SYNACK(x)
ESTAB indicates server is live;
send ACK for SYNACK;
this segment may contain ACKbit=1, ACKnum=y+1
client-to-server data
received ACK(y)
indicates client is live
ESTAB

Closing a TCP connection
client state server state
ESTAB ESTAB
clientSocket.close()
FIN_WAIT_1 can no longer FINbit=1, seq=x
send but can
receive data CLOSE_WAIT
ACKbit=1; ACKnum=x+1
can still
FIN_WAIT_2 wait for server send data
close
LAST_ACK
FINbit=1, seq=y
TIMED_WAIT can no longer
send data
ACKbit=1; ACKnum=y+1
timed wait
for 2*max CLOSED
segment lifetime
CLOSED

Closing a TCP connection
 client, server each close their side of connection
• send TCP segment with FIN bit = 1
 respond to received FIN with ACK
• on receiving FIN, ACK can be combined with own FIN
 simultaneous FIN exchanges can be handled

TCP round trip time, timeout
Q: how to set TCP timeout Q: how to estimate RTT?
value?  SampleRTT:measured time
 longer than RTT, but RTT varies! from segment transmission until
ACK receipt
 too short: premature timeout,
• ignore retransmissions
unnecessary retransmissions
 SampleRTT will vary, want
 too long: slow reaction to estimated RTT “smoother”
segment loss • average several recent
measurements, not just current
SampleRTT

EstimatedRTT = (1- )*EstimatedRTT + *SampleRTT
 exponential weighted moving average (EWMA)
 influence of past sample decreases exponentially fast
RTT: gaia.cs.umass.edu to fantasia.eurecom.fr
 typical value:  = 0.125 350
RTT: gaia.cs.umass.edu to fantasia.eurecom.fr
RTT (milliseconds)
300
250
RTT (milliseconds)
200
sampleRTT
150
EstimatedRTT
100
1 8 15 22 29 36 43 50 57 64 71 78 85 92 99 106
time (seconnds)
time (seconds)
SampleRTT Estimated RTT
 timeout interval: EstimatedRTT plus “safety margin”
• large variation in EstimatedRTT: want a larger safety margin
TimeoutInterval = EstimatedRTT + 4*DevRTT
estimated RTT “safety margin”
 DevRTT: EWMA of SampleRTT deviation from EstimatedRTT:

DevRTT = (1-)*DevRTT + *|SampleRTT-EstimatedRTT|
(typically,  = 0.25)
* Check out the online interactive exercises for more examples: http://gaia.cs.umass.edu/kurose_ross/interactive/
TCP Sender (simplified)
event: data received from event: timeout
application  retransmit segment that
caused timeout
 create segment with seq #
 restart timer
 seq # is byte-stream number
of first data byte in segment
event: ACK received
 start timer if not already
running  if ACK acknowledges
previously unACKed segments
• think of timer as for oldest
unACKed segment • update what is known to be
ACKed
• expiration interval:
TimeOutInterval • start timer if there are still
unACKed segments
TCP: retransmission scenarios
Host A Host B Host A Host B
SendBase=92
Seq=92, 8 bytes of data Seq=92, 8 bytes of data
Seq=100, 20 bytes of data

timeout
timeout
ACK=100
X
ACK=100
ACK=120
Seq=92, 8 bytes of data Seq=92, 8

SendBase=100 bytes of data send cumulative
SendBase=120 ACK for 120
ACK=100
ACK=120
SendBase=120
lost ACK scenario premature timeout

TCP: retransmission scenarios
Host A Host B

ACK=100
X
ACK=120
cumulative ACK covers

for earlier lost ACK

TCP fast retransmit
Host A Host B
TCP fast retransmit
if sender receives 3 additional
ACKs for same data (“triple
duplicate ACKs”), resend unACKed
segment with smallest seq # X
 likely that unACKed segment lost,
so don’t wait for timeout
timeout
Receipt of three duplicate ACKs
indicates 3 segments received Seq=100, 20 bytes of data
after a missing segment – lost

segment is likely. So retransmit!

Chapter 3: roadmap
• segment structure
• reliable data transfer
• flow control
• connection management
TCP flow control
application
Q: What happens if network Application removing
process
layer delivers data faster than data from TCP socket
buffers
application layer removes TCP socket
data from socket buffers? receiver buffers
TCP
code
Network layer
delivering IP datagram
payload into TCP
IP
socket buffers
code
from sender
receiver protocol stack

TCP flow control
application
process
buffers
TCP
code
receive window
flow control: # bytes
receiver willing to accept IP
code
from sender

TCP flow control
application
process
buffers
TCP
code
flow control
receiver controls sender, so
sender won’t overflow IP
code
receiver’s buffer by
transmitting too much, too fast
from sender

TCP flow control
 TCP receiver “advertises” free buffer
space in rwnd field in TCP header to application process
• RcvBuffer size set via socket
options (typical default is 4096 bytes) RcvBuffer buffered data
• many operating systems autoadjust
RcvBuffer
rwnd free buffer space
 sender limits amount of unACKed

(“in-flight”) data to received rwnd TCP segment payloads
 guarantees receive buffer will not TCP receiver-side buffering

overflow

TCP flow control
flow control: # bytes receiver willing to accept
 TCP receiver “advertises” free buffer

space in rwnd field in TCP header
• RcvBuffer size set via socket
receive window
options (typical default is 4096 bytes)
• many operating systems autoadjust
RcvBuffer
 sender limits amount of unACKed
(“in-flight”) data to received rwnd
 guarantees receive buffer will not
overflow
TCP segment format

Chapter 3: roadmap
functionality
Principles of congestion control
Congestion:
 informally: “too many sources sending too much data too fast for
network to handle”
 manifestations:
• long delays (queueing in router buffers)
• packet loss (buffer overflow at routers)
 different from flow control! congestion control:
 a top-10 problem! too many senders,
sending too fast
flow control: one sender

too fast for one receiver
Causes/costs of congestion: scenario 1
original data: lin throughput: lout
Simplest scenario:
Host A
 one router, infinite buffers
 input, output link capacity: R infinite shared
output link buffers
 two flows
R R
 no retransmissions needed
Host B
R/2
Q: What happens as
arrival rate lin lout
delay
throughput:
approaches R/2?
lin R/2 lin R/2
maximum per-connection large delays as arrival rate
throughput: R/2 lin approaches capacity
 one router, finite buffers
 sender retransmits lost, timed-out packet
• application-layer input = application-layer output: lin = lout
• transport-layer input includes retransmissions : l’in lin
Host A lin : original data

lout
l'in: original data, plus
retransmitted data
R R
Host B finite shared output

link buffers
Idealization: perfect knowledge R/2
 sender sends only when router buffers available
throughput: lout
Host A lin : original data lin
lout R/2
copy l'in: original data, plus
retransmitted data
free buffer space!
R R

link buffers
Idealization: some perfect knowledge
 packets can be lost (dropped at router) due to
full buffers
 sender knows when packet has been dropped:
only resends if packet known to be lost

copy l'in: original data, plus
retransmitted data
no buffer space!
R R

link buffers
Idealization: some perfect knowledge R/2
“wasted” capacity due
 packets can be lost (dropped at router) due to to retransmissions
throughput: lout
full buffers
when sending at
 sender knows when packet has been dropped: R/2, some packets
only resends if packet known to be lost are needed
retransmissions
Host A lin : original data lin R/2

retransmitted data
free buffer space!
R R

link buffers
Realistic scenario: un-needed duplicates R/2
 packets can be lost, dropped at router due to “wasted” capacity due
throughput: lout
to un-needed
full buffers – requiring retransmissions retransmissions
 but sender times can time out prematurely,
sending two copies, both of which are delivered when sending at
R/2, some packets
are retransmissions,
including needed
Host A lin : original data lin
and un-needed
duplicates, that are
R/2
timeout
copy l'in: original data, plus delivered!
retransmitted data
free buffer space!
R R

link buffers
Realistic scenario: un-needed duplicates R/2
 packets can be lost, dropped at router due to “wasted” capacity due
throughput: lout
to un-needed
full buffers – requiring retransmissions retransmissions
 but sender times can time out prematurely,
sending two copies, both of which are delivered when sending at
R/2, some packets
are retransmissions,
including needed
and un-needed
lin R/2 duplicates, that are
delivered!
“costs” of congestion:
 more work (retransmission) for given receiver throughput
 unneeded retransmissions: link carries multiple copies of a packet
• decreasing maximum achievable throughput

 four senders Q: what happens as lin and lin’ increase ?
 multi-hop paths A: as red lin’ increases, all arriving blue pkts at upper
 timeout/retransmit queue are dropped, blue throughput g 0
Host B
retransmitted data
finite shared
output link buffers
Host D
lout
Host C

R/2
lout
lin’ R/2
another “cost” of congestion:

 when packet dropped, any upstream transmission capacity and
buffering used for that packet was wasted!

Causes/costs of congestion: insights
R/2
 throughput can never exceed capacity
throughput: lout
lin R/2
 delay increases as capacity approached
delay
R/2
lin R/2
lout
 loss/retransmission decreases effective
throughput:
throughput
lin R/2 R/2
 un-needed duplicates further decreases
throughput: lout
effective throughput
R/2
lin
 upstream transmission capacity / buffering

R/2
lout
wasted for packets lost downstream
lin’ R/2

Approaches towards congestion control
End-end congestion control:
 no explicit feedback from
network
 congestion inferred from data data
ACKs
observed loss, delay ACKs
 approach taken by TCP

Approaches towards congestion control
Network-assisted congestion
control: explicit congestion info
 routers provide direct feedback
to sending/receiving hosts with data data
ACKs
flows passing through congested ACKs
router
 may indicate congestion level or
explicitly set sending rate
 TCP ECN, ATM, DECbit protocols
Explicit congestion notification (ECN)
TCP deployments often implement network-assisted congestion control:
 two bits in IP header (ToS field) marked by network router to indicate congestion
• policy to determine marking chosen by network operator
 congestion indication carried to destination
 destination sets ECE bit on ACK segment to notify sender of congestion
 involves both IP (IP header ECN bit marking) and TCP (TCP header C,E bit marking)
source TCP ACK segment
destination
TCP ECE=1
TCP
network network
link link
physical physical
ECN=10 ECN=11
IP datagram
Chapter 3: roadmap
functionality
TCP congestion control: details
sender sequence number space
cwnd TCP sending behavior:
 roughly: send cwnd bytes,
wait RTT for ACKS, then
send more bytes
last byte
available but ~
cwnd
ACKed sent, but not- TCP rate ~ bytes/sec
yet ACKed not used RTT
(“in-flight”) last byte sent
 TCP sender limits transmission: LastByteSent- LastByteAcked < cwnd
 cwnd is dynamically adjusted in response to observed

network congestion (implementing TCP congestion control)
TCP slow start
Host A Host B
 when connection begins,
increase rate exponentially
until first loss event:
RTT
• initially cwnd = 1 MSS
• double cwnd every RTT
• done by incrementing cwnd
for every ACK received
 summary: initial rate is
slow, but ramps up
exponentially fast time

TCP: from slow start to congestion avoidance
Q: when should the exponential
increase switch to linear?
X
A: when cwnd gets to 1/2 of its
value before timeout.
Implementation:
 variable ssthresh
 on loss event, ssthresh is set to
1/2 of cwnd just before loss event
* Check out the online interactive exercises for more examples: http://gaia.cs.umass.edu/kurose_ross/interactive/
Summary: TCP congestion control
New
New ACK!
ACK! new ACK
duplicate ACK
dupACKcount++ new ACK .
cwnd = cwnd + MSS (MSS/cwnd)
dupACKcount = 0
cwnd = cwnd+MSS transmit new segment(s), as allowed
dupACKcount = 0
L transmit new segment(s), as allowed
cwnd = 1 MSS
ssthresh = 64 KB cwnd > ssthresh
dupACKcount = 0
slow L congestion
start timeout avoidance
ssthresh = cwnd/2
cwnd = 1 MSS duplicate ACK
timeout dupACKcount = 0 dupACKcount++
ssthresh = cwnd/2 retransmit missing segment
cwnd = 1 MSS
dupACKcount = 0
retransmit missing segment New
timeout
ACK!
ssthresh = cwnd/2
cwnd = 1 New ACK
dupACKcount = 0
cwnd = ssthresh dupACKcount == 3
dupACKcount == 3 retransmit missing segment dupACKcount = 0
ssthresh= cwnd/2 ssthresh= cwnd/2
cwnd = ssthresh + 3 cwnd = ssthresh + 3
retransmit missing segment retransmit missing segment
fast
recovery
duplicate ACK
cwnd = cwnd + MSS
transmit new segment(s), as allowed

TCP congestion control: AIMD
 approach: senders can increase sending rate until packet loss
(congestion) occurs, then decrease sending rate on loss event
Additive Increase Multiplicative Decrease
increase sending rate by 1 cut sending rate in half at
maximum segment size every each loss event
RTT until loss detected
TCP sender Sending rate
AIMD sawtooth
behavior: probing
for bandwidth
time Transport Layer: 3-47

TCP and the congested “bottleneck link”
 TCP (classic, CUBIC) increase TCP’s sending rate until packet loss occurs
at some router’s output: the bottleneck link
source destination
TCP TCP
network network
link link
physical physical
packet queue almost
never empty, sometimes
overflows packet (loss)
bottleneck link (almost always busy)

TCP fairness
Fairness goal: if K TCP sessions share same bottleneck link of
bandwidth R, each should have average rate of R/K
TCP connection 1
bottleneck
TCP connection 2 router
capacity R

Q: is TCP Fair?
Example: two competing TCP sessions:
 additive increase gives slope of 1, as throughout increases
 multiplicative decrease decreases throughput proportionally
R equal bandwidth share

Is TCP fair?
A: Yes, under idealized
loss: decrease window by factor of 2 assumptions:
congestion avoidance: additive increase  same RTT
loss: decrease window by factor of 2
congestion avoidance: additive increase  fixed number of sessions
only in congestion
avoidance
Connection 1 throughput R
Fairness: must all network apps be “fair”?
Fairness and UDP Fairness, parallel TCP
 multimedia apps often do not connections
use TCP  application can open multiple
• do not want rate throttled by
congestion control parallel connections between two
hosts
 instead use UDP:
• send audio/video at constant rate,  web browsers do this , e.g., link of
tolerate packet loss rate R with 9 existing connections:
 there is no “Internet police” • new app asks for 1 TCP, gets rate R/10
policing use of congestion • new app asks for 11 TCPs, gets R/2
control

CN 08 Transport Layer - TCP Congestion Control

Uploaded by

Copyright:

Available Formats

CN 08 Transport Layer - TCP Congestion Control

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

CN 08 Transport Layer - TCP Congestion Control

Uploaded by

Copyright:

Available Formats

Chapter 3

Transport Layer: 3-2

 provide logical communication mobile network

running on different hosts

into segments, passes to network layer home network content

 two transport protocols available to data link

Internet applications enterprise

Transport Layer: 3-6

source port # dest port # segment seq #: counting

options (variable length)

Transport Layer: 3-7

• seq # of next byte expected

• cumulative ACK sent sent, not- usable not

• A: TCP spec doesn’t say, - up

to implementor acknowledgement number

simple telnet scenario

connection state: ESTAB connection state: ESTAB

Socket clientSocket = Socket connectionSocket =

Transport Layer: 3-11

Transport Layer: 3-12

Transport Layer: 3-13

Transport Layer: 3-14

RTT: gaia.cs.umass.edu to fantasia.eurecom.fr

estimated RTT “safety margin”

 DevRTT: EWMA of SampleRTT deviation from EstimatedRTT:

Seq=100, 20 bytes of data

Seq=92, 8 bytes of data Seq=92, 8

lost ACK scenario premature timeout

Transport Layer: 3-18

Seq=92, 8 bytes of data

Seq=100, 20 bytes of data

Seq=120, 15 bytes of data

cumulative ACK covers

Transport Layer: 3-19

after a missing segment – lost

Transport Layer: 3-20

receiver protocol stack

Transport Layer: 3-22

receiver protocol stack

Transport Layer: 3-23

receiver protocol stack

Transport Layer: 3-24

 sender limits amount of unACKed

 guarantees receive buffer will not TCP receiver-side buffering

Transport Layer: 3-25

 TCP receiver “advertises” free buffer

Transport Layer: 3-26

flow control: one sender

Host A lin : original data

Host B finite shared output

 sender sends only when router buffers available

free buffer space!

Host B finite shared output

Host A lin : original data

Host B finite shared output

Host A lin : original data lin R/2

free buffer space!

Host B finite shared output

free buffer space!

Host B finite shared output