程序代写代做代考 ER Transport_Part2

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