Transport_Part2
Transport Layer (contd.)
COMP 3331/9331:
Computer Networks and
Applications
Week 5
Transport Layer (Continued)
Reading Guide: Chapter 3, Sections: 3.4, 3.5
Transport Layer
Transport Layer Outline
3.1 transport-layer
services
3.2 multiplexing and
demultiplexing
3.3 connectionless
transport: UDP
3.4 principles of reliable
data transfer
3.5 connection-oriented
transport: TCP
§ segment structure
§ reliable data transfer
§ flow control
§ connection management
3.6 principles of congestion
control
3.7 TCP congestion control
2
rdt2.0 has a fatal flaw!
what happens if
ACK/NAK corrupted?
v sender doesn’t know
what happened at
receiver!
v can’t just retransmit:
possible duplicate
handling duplicates:
v sender retransmits
current pkt if ACK/NAK
corrupted
v sender adds sequence
number to each pkt
v receiver discards (doesn’t
deliver up) duplicate pkt
stop and wait
sender sends one packet,
then waits for receiver
response
3
rdt2.1: discussion
sender:
v seq # added to pkt
v two seq. #’s (0,1) will
suffice. Why?
v must check if received
ACK/NAK corrupted
v twice as many states
§ state must
“remember” whether
“expected” pkt should
have seq # of 0 or 1
receiver:
v must check if received
packet is duplicate
§ state indicates whether
0 or 1 is expected pkt
seq #
v note: receiver can not
know if its last
ACK/NAK received
OK at sender
4
• New Measures: Sequence Numbers, Checksum for ACK/NACK,
Duplicate detection
Another Look at rdt2.1
sender receiver
waiting for 0
sending #
0
waiting for 1
sending
# 1
waiting for 0
Duplicate Packet
Discard !!
Dotted line: erroneous transmission
Solid line: error-free transmission
5
rdt2.2: a NAK-free protocol
v same functionality as rdt2.1, using ACKs only
v instead of NAK, receiver sends ACK for last pkt
received OK
§ receiver must explicitly include seq # of pkt being ACKed
v duplicate ACK at sender results in same action as
NAK: retransmit current pkt
6
rdt2.2: Example
sender receiver
waiting for 0
sending #
0
waiting for 1sending
# 1
waiting for 0
sending #
0
Duplicate ACK
Resend old
packet
Dotted line: erroneous transmission
Solid line: error-free transmission
7
rdt3.0: channels with errors and loss
new assumption:
underlying channel can
also lose packets
(data, ACKs)
§ checksum, seq. #,
ACKs, retransmissions
will be of help … but
not enough
approach: sender waits
“reasonable” amount of
time for ACK
v retransmits if no ACK
received in this time
v if pkt (or ACK) just delayed
(not lost):
§ retransmission will be
duplicate, but seq. #’s
already handles this
§ receiver must specify seq
# of pkt being ACKed
v requires countdown timer
8
sender receiver
rcv pkt1
rcv pkt0
send ack0
send ack1
send ack0
rcv ack0
send pkt0
send pkt1
rcv ack1
send pkt0
rcv pkt0
pkt0
pkt0
pkt1
ack1
ack0
ack0
(a) no loss
sender receiver
rcv pkt1
rcv pkt0
send ack0
send ack1
send ack0
rcv ack0
send pkt0
send pkt1
rcv ack1
send pkt0
rcv pkt0
pkt0
pkt0
ack1
ack0
ack0
(b) packet loss
pkt1
X
loss
pkt1
timeout
resend pkt1
rdt3.0 in action
9
rdt3.0 in action
rcv pkt1
send ack1
(detect duplicate)
pkt1
sender receiver
rcv pkt1
rcv pkt0
send ack0
send ack1
send ack0
rcv ack0
send pkt0
send pkt1
rcv ack1
send pkt0
rcv pkt0
pkt0
pkt0
ack1
ack0
ack0
(c) ACK loss
ack1
X
loss
pkt1
timeout
resend pkt1
rcv pkt1
send ack1
(detect duplicate)
pkt1
sender receiver
rcv pkt1
send ack0
rcv ack0
send pkt1
send pkt0
rcv pkt0
pkt0
ack0
(d) premature timeout/ delayed ACK
pkt1
timeout
resend pkt1
ack1
send ack1
(do nothing)
rcv ack1
ack1
send pkt0
rcv ack1 pkt0
rcv pkt0
send ack0ack0
10
Transport Layer 11
rdt3.0: stop-and-wait operation
first packet bit transmitted, t = 0
sender receiver
RTT
last packet bit transmitted, t = L / R
first packet bit arrives
last packet bit arrives, send ACK
ACK arrives, send next
packet, t = RTT + L / R
U sender =
L / R
RTT + L / R
12
Performance of rdt3.0
Ø rdt3.0 is correct, but performance stinks
Ø e.g.: 1 Gbps link, 8000 bit packet and 30msec RTT:
• U sender: utilization – fraction of time sender busy sending
U
sender =
.008
30.008
= 0.00027
L / R
RTT + L / R
=
• RTT=30 msec, 1KB pkt every 30.008 msec: 33kB/sec
thruput over 1 Gbps link
Ø Network protocol limits use of physical resources!
Dtrans =
L
R
8000 bits
109 bits/sec= = 8 microsecs
Transport Layer
Pipelined protocols
pipelining: sender allows multiple, “in-flight”, yet-
to-be-acknowledged pkts
§ range of sequence numbers must be increased
§ buffering at sender and/or receiver
v two generic forms of pipelined (sliding window)
protocols: go-Back-N, selective repeat
13
Pipelining: increased utilization
first packet bit transmitted, t = 0
sender receiver
RTT
last bit transmitted, t = L / R
first packet bit arrives
last packet bit arrives, send ACK
ACK arrives, send next
packet, t = RTT + L / R
last bit of 2nd packet arrives, send ACK
last bit of 3rd packet arrives, send ACK
3-packet pipelining increases
utilization by a factor of 3!
U sender =
3L / R
RTT + L / R
14
Pipelined protocols: overview
Go-Back-N: Selective Repeat:
16
Ø Sender can have up to N
unacked packets in pipeline
Ø Sender can have up to N
unacked packets in pipeline
Ø Sender has single timer for
oldest unacked packet, when
timer expires, retransmit all
unacked packets
Ø Sender maintains timer for
each unacked packet, when
timer expires, retransmit
only that unacked packet
Ø Receiver only sends
cumulative ack, doesn’t ack new
packet if there’s a gap
Ø Receiver sends individual
ack for each packet
ØThere is no buffer available
at Receiver, out of order
packets are discarded
Ø Receiver has buffer, can
accept out of order packets
Transport Layer
Go-Back-N: sender
v k-bit seq # in pkt header
v “window” of up to N, consecutive unack’ed pkts allowed
v ACK(n): ACKs all pkts up to, including seq # n – “cumulative ACK”
§ may receive duplicate ACKs (see receiver)
v timer for oldest in-flight pkt
v timeout(n): retransmit packet n and all higher seq # pkts in
window
Applets: http://media.pearsoncmg.com/aw/aw_kurose_network_2/applets/go-back-n/go-back-n.html
http://www.ccs-labs.org/teaching/rn/animations/gbn_sr/
16
Transport Layer
GBN: sender extended FSM
Wait start_timerudt_send(sndpkt[base])
udt_send(sndpkt[base+1])
…
udt_send(sndpkt[nextseqnum-1])
timeout
rdt_send(data)
if (nextseqnum < base+N) { sndpkt[nextseqnum] = make_pkt(nextseqnum,data,chksum) udt_send(sndpkt[nextseqnum]) if (base == nextseqnum) start_timer nextseqnum++ } else refuse_data(data) base = getacknum(rcvpkt)+1 If (base == nextseqnum) stop_timer else start_timer rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) base=1 nextseqnum=1 rdt_rcv(rcvpkt) && corrupt(rcvpkt) L 17 Transport Layer ACK-only: always send ACK for correctly-received pkt with highest in-order seq # § may generate duplicate ACKs § need only remember expectedseqnum v out-of-order pkt: § discard (don’t buffer): no receiver buffering! § re-ACK pkt with highest in-order seq # Wait udt_send(sndpkt) default rdt_rcv(rcvpkt) && notcurrupt(rcvpkt) && hasseqnum(rcvpkt,expectedseqnum) extract(rcvpkt,data) deliver_data(data) sndpkt = make_pkt(expectedseqnum,ACK,chksum) udt_send(sndpkt) expectedseqnum++ expectedseqnum=1 sndpkt = make_pkt(expectedseqnum,ACK,chksum) L GBN: receiver extended FSM 18 Transport Layer GBN in action send pkt0 send pkt1 send pkt2 send pkt3 (wait) sender receiver receive pkt0, send ack0 receive pkt1, send ack1 receive pkt3, discard, (re)send ack1rcv ack0, send pkt4 rcv ack1, send pkt5 pkt 2 timeout send pkt2 send pkt3 send pkt4 send pkt5 Xloss receive pkt4, discard, (re)send ack1 receive pkt5, discard, (re)send ack1 rcv pkt2, deliver, send ack2 rcv pkt3, deliver, send ack3 rcv pkt4, deliver, send ack4 rcv pkt5, deliver, send ack5 ignore duplicate ACK 0 1 2 3 4 5 6 7 8 sender window (N=4) 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 19 Transport Layer Selective repeat v receiver individually acknowledges all correctly received pkts § buffers pkts, as needed, for eventual in-order delivery to upper layer v sender only resends pkts for which ACK not received § sender timer for each unACKed pkt v sender window § N consecutive seq #’s § limits seq #s of sent, unACKed pkts Applet: http://media.pearsoncmg.com/aw/aw_kurose_network_3/applets/SelectRepeat/SR.html 20 Transport Layer Selective repeat: sender, receiver windows 21 Transport Layer Selective repeat data from above: v if next available seq # in window, send pkt timeout(n): v resend pkt n, restart timer ACK(n) in [sendbase,sendbase+N]: v mark pkt n as received v if n smallest unACKed pkt, advance window base to next unACKed seq # sender pkt n in [rcvbase, rcvbase+N-1] v send ACK(n) v out-of-order: buffer v in-order: deliver (also deliver buffered, in-order pkts), advance window to next not-yet-received pkt pkt n in [rcvbase-N,rcvbase-1] v ACK(n) otherwise: v ignore receiver 22 Transport Layer Selective repeat in action send pkt0 send pkt1 send pkt2 send pkt3 (wait) sender receiver receive pkt0, send ack0 receive pkt1, send ack1 receive pkt3, buffer, send ack3rcv ack0, send pkt4 rcv ack1, send pkt5 pkt 2 timeout send pkt2 Xloss receive pkt4, buffer, send ack4 receive pkt5, buffer, send ack5 rcv pkt2; deliver pkt2, pkt3, pkt4, pkt5; send ack2 record ack3 arrived 0 1 2 3 4 5 6 7 8 sender window (N=4) 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 record ack4 arrived record ack5 arrived Q: what happens when ack2 arrives? 23 Transport Layer Selective repeat: dilemma example: v seq #’s: 0, 1, 2, 3 v window size=3 receiver window (after receipt) sender window (after receipt) 0 1 2 3 0 1 2 0 1 2 3 0 1 2 0 1 2 3 0 1 2 pkt0 pkt1 pkt2 0 1 2 3 0 1 2 pkt0 timeout retransmit pkt0 0 1 2 3 0 1 2 0 1 2 3 0 1 2 0 1 2 3 0 1 2X X X will accept packet with seq number 0(b) oops! 0 1 2 3 0 1 2 0 1 2 3 0 1 2 0 1 2 3 0 1 2 pkt0 pkt1 pkt2 0 1 2 3 0 1 2 pkt0 0 1 2 3 0 1 2 0 1 2 3 0 1 2 0 1 2 3 0 1 2 X will accept packet with seq number 0 0 1 2 3 0 1 2 pkt3 (a) no problem receiver can’t see sender side. receiver behavior identical in both cases! something’s (very) wrong! v receiver sees no difference in two scenarios! v duplicate data accepted as new in (b) Q: what relationship between seq # size and window size to avoid problem in (b)? 24 A: window size must be less than or equal to half the size of the sequence number space Recap: components of a solution v Checksums (for error detection) v Timers (for loss detection) v Acknowledgments § cumulative § selective v Sequence numbers (duplicates, windows) v Sliding Windows (for efficiency) v Reliability protocols use the above to decide when and what to retransmit or acknowledge Transport Layer 25 26 Transport Layer Outline 3.1 transport-layer services 3.2 multiplexing and demultiplexing 3.3 connectionless transport: UDP 3.4 principles of reliable data transfer 3.5 connection-oriented transport: TCP § segment structure § reliable data transfer § flow control § connection management 3.6 principles of congestion control 3.7 TCP congestion control Transport Layer Practical Reliability Questions v How do the sender and receiver keep track of outstanding pipelined segments? v How many segments should be pipelined? v How do we choose sequence numbers? v What does connection establishment and teardown look like? v How should we choose timeout values? 27Transport Layer TCP: Overview RFCs: 793,1122,1323, 2018, 2581 v full duplex data: § bi-directional data flow in same connection § MSS: maximum segment size v connection-oriented: § handshaking (exchange of control msgs) inits sender, receiver state before data exchange v flow controlled: § sender will not overwhelm receiver v point-to-point: § one sender, one receiver v reliable, in-order byte stream: § no “message boundaries” v pipelined: § TCP congestion and flow control set window size v send and receive buffers socket door TCP send buffer TCP receive buffer socket door segment application writes data application reads data Transport Layer 28 TCP segment structure source port # dest port # 32 bits application data (variable length) sequence number acknowledgement number receive window Urg data pointerchecksum FSRPAU head len not used options (variable length) URG: urgent data (generally not used) ACK: ACK # valid PSH: push data now (generally not used) RST, SYN, FIN: connection estab (setup, teardown commands) # bytes rcvr willing to accept counting by bytes of data (not segments!) Internet checksum (as in UDP) Transport Layer 29 TCP segment structure Transport Layer 30 TCP Segments source port # dest port # 32 bits application data (variable length) Urg data pointer F S R P A U head len not used checksum receive window sequence number acknowledgement number options (variable length) 20 Bytes (UDP was 8) Transport Layer Outline 3.1 transport-layer services 3.2 multiplexing and demultiplexing 3.3 connectionless transport: UDP 3.4 principles of reliable data transfer 3.5 connection-oriented transport: TCP § segment structure § reliable data transfer § flow control § connection management 3.6 principles of congestion control 3.7 TCP congestion control 31Transport Layer Recall: Components of a solution for reliable transport v Checksums (for error detection) v Timers (for loss detection) v Acknowledgments § cumulative § selective v Sequence numbers (duplicates, windows) v Sliding Windows (for efficiency) §Go-Back-N (GBN) § Selective Repeat (SR) 32Transport Layer What does TCP do? Many of our previous ideas, but some key differences v Checksum 33Transport Layer 34 TCP Header Source port Destination port Sequence number Acknowledgment Receive windowHdrLen Flags0 Checksum Urgent pointer Options (variable) Data Computed over header and data Transport Layer What does TCP do? Many of our previous ideas, but some key differences v Checksum v Sequence numbers are byte offsets 35Transport Layer TCP “Stream of Bytes” Service .. Application @ Host A Application @ Host B 36Transport Layer .. Provided Using TCP “Segments” Host A Host B TCP Data TCP Data Segment sent when: 1. Segment full (Max Segment Size), 2. Not full, but times out 37Transport Layer TCP Segment Size v IP packet § No bigger than Maximum Transmission Unit (MTU) § E.g., up to 1500 bytes with Ethernet v TCP packet § IP packet with a TCP header and data inside § TCP header ³ 20 bytes long v TCP segment § No more than Maximum Segment Size (MSS) bytes § E.g., up to 1460 consecutive bytes from the stream § MSS = MTU – (IP header) – (TCP header) IP Hdr IP Data TCP HdrTCP Data (segment) 38Transport Layer Sequence Numbers Host A ISN (initial sequence number) Sequence number = 1st byte in segment = ISN + k k bytes 39Transport Layer Sequence numbers: • byte stream “number” of first byte in segment’s data Sequence & Ack Numbers Host B TCP Data TCP Data TCP HDR TCP HDR ACK sequence number = next expected byte = seqno + length(data) Host A ISN (initial sequence number) Sequence number = 1st byte in segment = ISN + k k 40Transport Layer 41 TCP seq. numbers, ACKs User types ‘C’ host ACKs receipt of echoed ‘C’ host ACKs receipt of ‘C’, echoes back ‘C’ simple telnet scenario Host BHost A Seq=42, ACK=79, data = ‘C’ Seq=79, ACK=43, data = ‘C’ Seq=43, ACK=80 What does TCP do? Most of our previous tricks, but a few differences v Checksum v Sequence numbers are byte offsets v Receiver sends cumulative acknowledgements (like GBN) 42Transport Layer ACKing and Sequence Numbers v Sender sends packet § Data starts with sequence number X § Packet contains B bytes [X, X+1, X+2, ….X+B-1] v Upon receipt of packet, receiver sends an ACK § If all data prior to X already received: • ACK acknowledges X+B (because that is next expected byte) § If highest in-order byte received is Y s.t. (Y+1) < X • ACK acknowledges Y+1 • Even if this has been ACKed before 43Transport Layer 44 TCP seq. numbers, ACKs Host BHost A Seq=100, Data=50 ISN=100 Seq=150, Data=50 Seq=200, Data=50 Seq=250, Data=50 ACK=200, Received 150-199 Seq=???, Data=50 Seq 100 to Seq 149 ACK=150, Received 100-149 ACK=250, Received 200-249 ACK=300, Received 250-299 45 TCP seq. numbers, ACKs Host BHost A Seq=100, Data=50 ISN=100 Seq=150, Data=50 Seq=200, Data=50 Seq=250, Data=50 ACK=150, Received 100-149 ACK=???, Received 200-249 ACK=???, Received 250-299 Normal Pattern v Sender: seqno=X, length=B v Receiver: ACK=X+B v Sender: seqno=X+B, length=B v Receiver: ACK=X+2B v Sender: seqno=X+2B, length=B v Seqno of next packet is same as last ACK field 46Transport Layer Packet Loss v Sender: seqno=X, length=B v Receiver: ACK=X+B v Sender: seqno=X+B, length=B v Sender: seqno=X+2B, length=B v Receiver: ACK = X+B LOST 47Transport Layer 48 TCP Header Source port Destination port Sequence number Acknowledgment Receive windowHdrLen Flags0 Checksum Urgent pointer Options (variable) Data Acknowledgment gives seqno just beyond highest seqno received in order (“What Byte is Next”) Transport Layer Piggybacking v So far, we’ve assumed distinct “sender” and “receiver” roles v In reality, usually both sides of a connection send some data 49 Piggybacking • So far, we’ve assumed distinct “sender” and “receiver” roles • In reality, usually both sides of a connection send some data – request/response is a common pattern Client Server Without Piggybacking … Client Server With Piggybacking … Transport Layer Quiz ACK = 101 + 2048 = 2149 ACK = 1024 + 1024 = 2048 Seq = 2149 50Transport Layer What does TCP do? Most of our previous tricks, but a few differences v Checksum v Sequence numbers are byte offsets v Receiver sends cumulative acknowledgements (like GBN) v Receivers can buffer out-of-sequence packets (like SR) 51Transport Layer Loss with cumulative ACKs v Sender sends packets with 100Bytes and sequence numbers: § 100, 200, 300, 400, 500, 600, 700, 800, 900, … v Assume the fifth packet (seq. no. 500) is lost, but no others v Stream of ACKs will be: § 200, 300, 400, 500, 500, 500, 500,… 52Transport Layer What does TCP do? Most of our previous tricks, but a few differences v Checksum v Sequence numbers are byte offsets v Receiver sends cumulative acknowledgements (like GBN) v Receivers do not drop out-of-sequence packets (like SR) v Sender maintains a single retransmission timer (like GBN) and retransmits on timeout 53Transport Layer 54 TCP round trip time, timeout Transport Layer TCP round trip time, timeout Q: how to set TCP timeout value? v longer than RTT § but RTT varies v too short: premature timeout, unnecessary retransmissions v too long: slow reaction to segment loss and connection has lower throughput Q: how to estimate RTT? v SampleRTT: measured time from segment transmission until ACK receipt § ignore retransmissions v SampleRTT will vary, want estimated RTT “smoother” § average several recent measurements, not just current SampleRTT 55Transport Layer RTT: gaia.cs.umass.edu to fantasia.eurecom.fr 100 150 200 250 300 350 1 8 15 22 29 36 43 50 57 64 71 78 85 92 99 106 time (seconnds) RT T (m ill is ec on ds ) SampleRTT Estimated RTT EstimatedRTT = (1- a)*EstimatedRTT + a*SampleRTT v exponential weighted moving average v influence of past sample decreases exponentially fast v typical value: a = 0.125 TCP round trip time, timeout RT T (m ill is ec on ds ) RTT: gaia.cs.umass.edu to fantasia.eurecom.fr sampleRTT EstimatedRTT time (seconds) 56Transport Layer v timeout interval: EstimatedRTT plus “safety margin” § large variation in EstimatedRTT -> larger safety margin
v estimate SampleRTT deviation from EstimatedRTT:
DevRTT = (1-b)*DevRTT +
b*|SampleRTT-EstimatedRTT|
TCP round trip time, timeout
(typically, b = 0.25)
TimeoutInterval = EstimatedRTT + 4*DevRTT
estimated RTT “safety margin”
57
Practice Problem:
http://wps.pearsoned.com/ecs_kurose_compnetw_6/216/55463/14198700.cw/index.html
Transport Layer
58
TCP round trip time, timeout
TimeoutInterval = EstimatedRTT + 4*DevRTT
estimated RTT “safety margin”
(EstimatedRTT+4*DevRTT)
DevRTT
EstimatedRTT
RTT
Transport LayerFigure: Credits Prof David Wetherall UoW
Why exclude retransmissions in RTT
computation?
v How do we differentiate between the real ACK, and ACK of
the retransmitted packet?
Sa
m
pl
eR
T
T
Sender Receiver
SampleRTT
Sender Receiver
59Transport Layer
TCP sender events:
data rcvd from app:
v create segment with
seq #
v seq # is byte-stream
number of first data
byte in segment
v start timer if not
already running
§ think of timer as for
oldest unacked
segment
§ expiration interval:
TimeOutInterval
timeout:
v retransmit segment
that caused timeout
v restart timer
ack rcvd:
v if ack acknowledges
previously unacked
segments
§ update what is known
to be ACKed
§ start timer if there are
still unacked segments
60
PUTTING IT
TOGETHER
Transport Layer
TCP sender (simplified)
wait
for
event
NextSeqNum = InitialSeqNum
SendBase = InitialSeqNum
L
create segment, seq. #: NextSeqNum
pass segment to IP (i.e., “send”)
NextSeqNum = NextSeqNum + length(data)
if (timer currently not running)
start timer
data received from application above
retransmit not-yet-acked segment
with smallest seq. #
start timer
timeout
if (y > SendBase) {
SendBase = y
/* SendBase–1: last cumulatively ACKed byte */
if (there are currently not-yet-acked segments)
start timer
else stop timer
}
ACK received, with ACK field value y
61
PUTTING IT
TOGETHER
Transport Layer
TCP: retransmission scenarios
lost ACK scenario
Host BHost A
Seq=92, 8 bytes of data
ACK=100
Seq=92, 8 bytes of data
Xtim
eo
ut
ACK=100
premature timeout
Host BHost A
Seq=92, 8 bytes of data
ACK=100
Seq=92, 8
bytes of data
tim
eo
ut
ACK=120
Seq=100, 20 bytes of data
ACK=120
SendBase=100
SendBase=120
SendBase=120
SendBase=92
62Transport Layer
TCP: retransmission scenarios
X
cumulative ACK
Host BHost A
Seq=92, 8 bytes of data
ACK=100
Seq=120, 15 bytes of data
tim
eo
ut
Seq=100, 20 bytes of data
ACK=120
63Transport Layer
X
cumulative ACK
Host BHost A
Seq=92, 8 bytes of data
tim
eo
ut
Seq=100, 20 bytes of data
ACK=?
Quiz
ACK = 101 + 2048 = 2149
ACK = 1024 + 1024 = 2048
Seq = 2149
64Transport Layer
Suppose host A sends two TCP segments back to back to Host B
over a TCP connection. The first segment has sequence number 90;
the second has sequence number 110.
v Q1: How much data is in the first segment ?
v Q2: Suppose that the first segment is lost but the second segment
arrives at B. In the acknowledgement that Host B sends to Host A,
what will be the acknowledgement number?
TCP ACK generation [RFC 1122, RFC 2581]
event at receiver
arrival of in-order segment with
expected seq #. All data up to
expected seq # already ACKed
arrival of in-order segment with
expected seq #. One other
segment has ACK pending
arrival of out-of-order segment
higher-than-expect seq. # .
Gap detected
arrival of segment that
partially or completely fills gap
TCP receiver action
delayed ACK. Wait up to 500ms
for next segment. If no next segment,
send ACK
immediately send single cumulative
ACK, ACKing both in-order segments
immediately send duplicate ACK,
indicating seq. # of next expected byte
immediate send ACK, provided that
segment starts at lower end of gap
65Transport Layer
What does TCP do?
Most of our previous tricks, but a few differences
v Checksum
v Sequence numbers are byte offsets
v Receiver sends cumulative acknowledgements (like GBN)
v Receivers may not drop out-of-sequence packets (like SR)
v Sender maintains a single retransmission timer (like GBN) and
retransmits on timeout
v Introduces fast retransmit: optimisation that uses duplicate
ACKs to trigger early retransmission
66Transport Layer
X
fast retransmit after sender
receipt of triple duplicate ACK
Host BHost A
Seq=92, 8 bytes of data
ACK=100
tim
eo
ut ACK=100
ACK=100
ACK=100
TCP fast retransmit
Seq=100, 20 bytes of data
Seq=100, 20 bytes of data
Transport Layer 67
tim
eo
ut
TCP fast retransmit
v time-out period often
relatively long:
§ long delay before resending
lost packet
v “Duplicate ACKs” are a
sign of an isolated loss
§ The lack of ACK progress
means that packet hasn’t
been delivered
§ Stream of ACKs means some
packets are being delivered
§ Could trigger resend on
receiving “k” duplicate ACKs
(TCP uses k = 3)
if sender receives 3
duplicate ACKs for
same data
(“triple duplicate ACKs”),
resend unacked
segment with smallest
seq #
§ likely that unacked
segment is lost, so
don’t wait for timeout
TCP fast retransmit
Transport Layer 68
What does TCP do?
Most of our previous ideas, but some key
differences
v Checksum
v Sequence numbers are byte offsets
v Receiver sends cumulative acknowledgements (like GBN)
v Receivers do not drop out-of-sequence packets (like SR)
v Sender maintains a single retransmission timer (like GBN) and
retransmits on timeout
v Introduces fast retransmit: optimization that uses duplicate
ACKs to trigger early retransmission
Transport Layer 69
Transport Layer Outline
3.1 transport-layer
services
3.2 multiplexing and
demultiplexing
3.3 connectionless
transport: UDP
3.4 principles of reliable
data transfer
3.5 connection-oriented
transport: TCP
§ segment structure
§ reliable data transfer
§ flow control
§ connection management
3.6 principles of congestion
control
3.7 TCP congestion control
Transport Layer 70
TCP flow control
application
process
TCP socket
receiver buffers
TCP
code
IP
code
application
OS
receiver protocol stack
application may
remove data from
TCP socket buffers ….
… slower than TCP
receiver is delivering
(sender is sending)
from sender
receiver controls sender, so
sender won’t overflow
receiver’s buffer by transmitting
too much, too fast
flow control
Transport Layer 71
TCP flow control
buffered data
free buffer spacerwnd
RcvBuffer
TCP segment payloads
to application process
v receiver “advertises” free
buffer space by including
rwnd value in TCP header
of receiver-to-sender
segments
§ RcvBuffer size set via
socket options (typical default
is 4096 bytes)
§ many operating systems
autoadjust RcvBuffer
v sender limits amount of
unacked (“in-flight”) data to
receiver’s rwnd value
v guarantees receive buffer
will not overflow
receiver-side buffering
Transport Layer
72
http://media.pearsoncmg.com/aw/aw_kurose_network_4/applets/flow/FlowControl.htm
73
TCP Header
Source port Destination port
Sequence number
Acknowledgment
Receive windowHdrLen Flags0
Checksum Urgent pointer
Options (variable)
Data
Transport Layer
Transport Layer Outline
3.1 transport-layer
services
3.2 multiplexing and
demultiplexing
3.3 connectionless
transport: UDP
3.4 principles of reliable
data transfer
3.5 connection-oriented
transport: TCP
§ segment structure
§ reliable data transfer
§ flow control
§ connection management
3.6 principles of congestion
control
3.7 TCP congestion control
Transport Layer 74