PowerPoint Presentation
Transport Layer
All material copyright 1996-2012
J.F Kurose and K.W. Ross, All Rights Reserved
George Parisis
School of Engineering and Informatics
University of Sussex
Transport Layer
3-*
Outline
transport-layer services
multiplexing and demultiplexing
connectionless transport: UDP
principles of reliable data transfer
connection-oriented transport: TCP
segment structure
reliable data transfer
flow control
connection management
principles of congestion control
TCP congestion control
Transport Layer
Transport Layer
3-*
Principles of reliable data transfer
important in application, transport, link layers
top-10 list of important networking topics!
characteristics of unreliable channel will determine complexity of reliable data transfer protocol (rdt)
Transport Layer
Transport Layer
3-*
characteristics of unreliable channel will determine complexity of reliable data transfer protocol (rdt)
Principles of reliable data transfer
important in application, transport, link layers
top-10 list of important networking topics!
Transport Layer
Transport Layer
3-*
characteristics of unreliable channel will determine complexity of reliable data transfer protocol (rdt)
important in application, transport, link layers
Principles of reliable data transfer
Transport Layer
Transport Layer
3-*
Reliable data transfer: getting started
send
side
receive
side
rdt_send(): called from above, (e.g., by app.). Passed data to
deliver to receiver upper layer
udt_send(): called by rdt,
to transfer packet over
unreliable channel to receiver
rdt_rcv(): called when packet arrives on rcv-side of channel
deliver_data(): called by rdt to deliver data to upper
Transport Layer
Transport Layer
3-*
we’ll:
incrementally develop sender, receiver sides of reliable data transfer protocol (rdt)
consider only unidirectional data transfer
but control info will flow on both directions!
use finite state machines (FSM) to specify sender, receiver
state
1
state
2
event causing state transition
actions taken on state transition
state: when in this “state” next state uniquely determined by next event
event
actions
Reliable data transfer: getting started
Transport Layer
Transport Layer
3-*
rdt1.0: reliable transfer over a reliable channel
underlying channel perfectly reliable
no bit errors
no loss of packets
separate FSMs for sender, receiver:
sender sends data into underlying channel
receiver reads data from underlying channel
Wait for call from above
packet = make_pkt(data)
udt_send(packet)
rdt_send(data)
extract (packet,data)
deliver_data(data)
Wait for call from below
rdt_rcv(packet)
sender
receiver
Transport Layer
Transport Layer
3-*
underlying channel may flip bits in packet
checksum to detect bit errors
the question: how to recover from errors:
acknowledgements (ACKs): receiver explicitly tells sender that pkt received OK
negative acknowledgements (NAKs): receiver explicitly tells sender that pkt had errors
sender retransmits pkt on receipt of NAK
new mechanisms in rdt2.0 (beyond rdt1.0):
error detection
receiver feedback: control msgs (ACK,NAK) rcvr->sender
rdt2.0: channel with bit errors
How do humans recover from “errors”
during conversation?
Transport Layer
Transport Layer
3-*
underlying channel may flip bits in packet
checksum to detect bit errors
the question: how to recover from errors:
acknowledgements (ACKs): receiver explicitly tells sender that pkt received OK
negative acknowledgements (NAKs): receiver explicitly tells sender that pkt had errors
sender retransmits pkt on receipt of NAK
new mechanisms in rdt2.0 (beyond rdt1.0):
error detection
feedback: control msgs (ACK,NAK) from receiver to sender
rdt2.0: channel with bit errors
Transport Layer
Transport Layer
3-*
rdt2.0: FSM specification
Wait for call from above
sndpkt = make_pkt(data, checksum)
udt_send(sndpkt)
extract(rcvpkt,data)
deliver_data(data)
udt_send(ACK)
rdt_rcv(rcvpkt) &&
notcorrupt(rcvpkt)
rdt_rcv(rcvpkt) && isACK(rcvpkt)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
isNAK(rcvpkt)
sender
receiver
rdt_send(data)
L
udt_send(NAK)
rdt_rcv(rcvpkt) &&
corrupt(rcvpkt)
Wait for ACK or NAK
Wait for call from below
Transport Layer
Transport Layer
3-*
rdt2.0: operation with no errors
Wait for call from above
snkpkt = make_pkt(data, checksum)
udt_send(sndpkt)
extract(rcvpkt,data)
deliver_data(data)
udt_send(ACK)
rdt_rcv(rcvpkt) &&
notcorrupt(rcvpkt)
rdt_rcv(rcvpkt) && isACK(rcvpkt)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
isNAK(rcvpkt)
Wait for call from below
rdt_send(data)
L
udt_send(NAK)
rdt_rcv(rcvpkt) &&
corrupt(rcvpkt)
Wait for ACK or NAK
Transport Layer
Transport Layer
3-*
rdt2.0: error scenario
Wait for call from above
snkpkt = make_pkt(data, checksum)
udt_send(sndpkt)
extract(rcvpkt,data)
deliver_data(data)
udt_send(ACK)
rdt_rcv(rcvpkt) &&
notcorrupt(rcvpkt)
rdt_rcv(rcvpkt) && isACK(rcvpkt)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
isNAK(rcvpkt)
Wait for call from below
rdt_send(data)
L
udt_send(NAK)
rdt_rcv(rcvpkt) &&
corrupt(rcvpkt)
Wait for ACK or NAK
Transport Layer
Transport Layer
3-*
rdt2.0 has a fatal flaw!
what happens if ACK/NAK corrupted?
sender doesn’t know what happened at receiver!
can’t just retransmit: possible duplicate
handling duplicates:
sender retransmits current pkt if ACK/NAK corrupted
sender adds sequence number to each pkt
receiver discards (doesn’t deliver up) duplicate pkt
stop and wait
sender sends one packet,
then waits for receiver
response
Transport Layer
Transport Layer
3-*
rdt2.1: sender, handles garbled ACK/NAKs
Wait for call 0 from above
sndpkt = make_pkt(0, data, checksum)
udt_send(sndpkt)
rdt_send(data)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
( corrupt(rcvpkt) ||
isNAK(rcvpkt) )
sndpkt = make_pkt(1, data, checksum)
udt_send(sndpkt)
rdt_send(data)
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
&& isACK(rcvpkt)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
( corrupt(rcvpkt) ||
isNAK(rcvpkt) )
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
&& isACK(rcvpkt)
L
L
Wait for ACK or NAK 0
Wait for
call 1 from above
Wait for ACK or NAK 1
Transport Layer
Transport Layer
3-*
sndpkt = make_pkt(NAK, chksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
not corrupt(rcvpkt) &&
has_seq0(rcvpkt)
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)
&& has_seq1(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
sndpkt = make_pkt(ACK, chksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)
&& has_seq0(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
sndpkt = make_pkt(ACK, chksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) && (corrupt(rcvpkt)
sndpkt = make_pkt(ACK, chksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
not corrupt(rcvpkt) &&
has_seq1(rcvpkt)
rdt_rcv(rcvpkt) && (corrupt(rcvpkt)
sndpkt = make_pkt(ACK, chksum)
udt_send(sndpkt)
sndpkt = make_pkt(NAK, chksum)
udt_send(sndpkt)
rdt2.1: receiver, handles garbled ACK/NAKs
Wait for
0 from below
Wait for
1 from below
Transport Layer
Transport Layer
3-*
rdt2.1: discussion
sender:
seq # added to pkt
two seq. #’s (0,1) will suffice. Why?
must check if received ACK/NAK corrupted
twice as many states
state must “remember” whether “expected” pkt should have seq # of 0 or 1
receiver:
must check if received packet is duplicate
state indicates whether 0 or 1 is expected pkt seq #
Transport Layer
Transport Layer
3-*
rdt2.2: a NAK-free protocol
same functionality as rdt2.1, using ACKs only
instead of NAK, receiver sends ACK for last pkt received OK
receiver must explicitly include seq # of pkt being ACKed
duplicate ACK at sender results in same action as NAK: retransmit current pkt
Transport Layer
Transport Layer
3-*
rdt2.2: sender, receiver fragments
Wait for call 0 from above
Wait for ACK
0
sndpkt = make_pkt(0, data, checksum)
udt_send(sndpkt)
rdt_send(data)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
( corrupt(rcvpkt) ||
isACK(rcvpkt,1) )
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
&& isACK(rcvpkt,0)
sender FSM
fragment
Wait for
0 from below
rdt_rcv(rcvpkt) &&
(corrupt(rcvpkt) ||
has_seq1(rcvpkt))
udt_send(sndpkt)
receiver FSM
fragment
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)
&& has_seq1(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
sndpkt = make_pkt(ACK1, chksum)
udt_send(sndpkt)
L
Transport Layer
Transport Layer
3-*
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
retransmits if no ACK received in this time
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
requires countdown timer
Transport Layer
Transport Layer
3-*
rdt3.0 sender
sndpkt = make_pkt(0, data, checksum)
udt_send(sndpkt)
start_timer
rdt_send(data)
rdt_rcv(rcvpkt) &&
( corrupt(rcvpkt) ||
isACK(rcvpkt,1) )
sndpkt = make_pkt(1, data, checksum)
udt_send(sndpkt)
start_timer
rdt_send(data)
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
&& isACK(rcvpkt,0)
rdt_rcv(rcvpkt) &&
( corrupt(rcvpkt) ||
isACK(rcvpkt,0) )
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
&& isACK(rcvpkt,1)
stop_timer
stop_timer
udt_send(sndpkt)
start_timer
timeout
udt_send(sndpkt)
start_timer
timeout
rdt_rcv(rcvpkt)
L
rdt_rcv(rcvpkt)
L
L
L
Wait for ACK0
Wait for
call 1 from above
Wait for
call 0from above
Wait for ACK1
Transport Layer
Transport Layer
3-*
sender
receiver
rcv pkt1
rcv pkt0
send ack0
send ack1
send ack0
rcv ack0
send pkt0
send pkt1
rcv ack1
send pkt0
rcv pkt0
(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
(b) packet loss
rdt3.0 in action
pkt0
pkt0
pkt1
ack1
ack0
ack0
pkt0
pkt0
ack1
ack0
ack0
pkt1
X
loss
pkt1
timeout
resend pkt1
Transport Layer
Transport Layer
3-*
rdt3.0 in action
rcv pkt1
send ack1
(detect duplicate)
sender
receiver
rcv pkt1
rcv pkt0
send ack0
send ack1
send ack0
rcv ack0
send pkt0
send pkt1
rcv ack1
send pkt0
rcv pkt0
(c) ACK loss
rcv pkt1
send ack1
(detect duplicate)
sender
receiver
rcv pkt1
send ack0
rcv ack0
send pkt1
send pkt0
rcv pkt0
(d) premature timeout/ delayed ACK
pkt1
pkt0
pkt0
ack1
ack0
ack0
ack1
X
loss
pkt1
timeout
resend pkt1
pkt1
pkt0
ack0
pkt1
timeout
resend pkt1
ack1
ack1
send pkt0
rcv ack1
pkt0
rcv pkt0
send ack0
send ack1
do nothing
rcv ack1
ack0
Transport Layer
Transport Layer
3-*
Performance of rdt3.0
rdt3.0 is correct, but performance stinks
e.g.: 1 Gbps link, 15 ms prop. delay, 8000 bit packet:
U sender: utilization – fraction of time sender busy sending
if RTT=30 msec, 1KB pkt every 30 msec: 33kB/sec thruput over 1 Gbps link
network protocol limits use of physical resources!
L
R
8000 bits
109 bits/sec
Dtrans =
=
=
8 microsecs
Transport Layer
Transport Layer
3-*
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
Transport Layer
Transport Layer
3-*
Summary
principles behind transport layer services:
reliable data transfer
Transport Layer
U
sender
=
.008
30.008
RTT + L / R
L / R
=
=
0.00027
U
sender
=
.008
30.008
RTT + L / R
L / R
=
=
0.00027
U
sender
=
.
008
30.008
=
0.00027
L / R
RTT + L / R
=
U
sender
=
.
008
30.008
=
0.00027
L / R
RTT + L / R
=