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-2
Outline
v transport-layer services
v multiplexing and demultiplexing
v connectionless transport: UDP
v principles of reliable data transfer
v connection-oriented transport: TCP
§ segment structure
§ reliable data transfer
§ flow control
§ connection management
v principles of congestion control
v TCP congestion control
Transport Layer 3-3
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 protocols: go-
Back-N, selective repeat
Transport Layer 3-4
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 =
.0024
30.008
= 0.00081
3L / R
RTT + L / R
=
Transport Layer 3-5
Pipelined protocols: overview
Go-back-N:
v sender can have up
to N unacked packets
in pipeline
v receiver only sends
cumulative ack
§ doesn’t ack packet if
there’s a gap
v sender has timer for
oldest unacked
packet
§ when timer expires,
retransmit all unacked
packets
Selective Repeat:
v sender can have up to
N unacked packets in
pipeline
v rcvr sends individual
ack for each packet
v sender maintains timer
for each unacked
packet
§ when timer expires,
retransmit only that
unacked packet
Transport Layer 3-6
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
Transport Layer 3-7
GBN: sender extended FSM
Wait start_timer udt_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)
Λ
Λ
Transport Layer 3-8
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)
Λ
GBN: receiver extended FSM
Transport Layer 3-9
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 ack1 rcv ack0, send pkt4
rcv ack1, send pkt5
pkt 2 timeout
send pkt2
send pkt3
send pkt4
send pkt5
X loss
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
Transport Layer 3-10
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 number of sent, unACKed pkts
Transport Layer 3-11
Selective repeat: sender, receiver windows
Transport Layer 3-12
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
Transport Layer 3-13
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 ack3 rcv ack0, send pkt4
rcv ack1, send pkt5
pkt 2 timeout
send pkt2
X loss
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?
Transport Layer 3-14
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 2 X
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)?
Reordering
v Old copies of a packet with a sequence or
acknowledgment number of x can appear
§ neither the sender’s nor the receiver’s window contains x
v Channel can be thought of as essentially buffering packets
and spontaneously emitting these packets at any point in
the future
v Care must be taken to guard against duplicate sequence
numbers.
v A sequence number must not be reused until the sender is
“sure” that any previously sent packets with sequence
number x are no longer in the network.
v This is done by assuming that a packet cannot “live” in the
network for longer than some fixed maximum amount of
time.
Transport Layer 3-15
Transport Layer 3-16
Summary
v principles behind transport layer services:
§ reliable data transfer
§ GBN
§ Selective repeat