COMP 3234B
Computer and Communication Networks
2nd semester 2020-2021
Transport Layer (II)
Prof. C. Wu
Department of Computer Science The University of Hong Kong
Roadmap
Transport layer
Principles behind transport-layer services
multiplexing/demultiplexing (ILO1, 2) reliable data transfer:(ILO 2, 3)
rdt 1.0
rdt 2.0, 2.1, 2.2 rdt 3.0
GBN
selective repeat
flow control (ILO 2, 3) congestion control (ILO 2, 3)
Transport protocols in the Internet (ILO 2, 3) TCP
UDP
application
ttransporrtt
network
link
physical
Pipelining
Sender can send multiple packets without waiting for acknowledgements
Pipelining: performance
increased utilization
Rdt3.0:
R
R
sender
receiver
performance
first packet bit transmitted, t = 0
ata transfer proto
r
, propagation delay 15
sender
ted, t = 0
t = L/ R
last bit transmitted, t = L / R
dt 3.0 is a working reliable d col
last packet bit arrives, send ACK
last bit of 2nd packet arrives, send ACK
first packet bit arrives
dt3.0 performance very poo
RTT
example: link rate R=1 Gbps link ms (milliseconds),
each packet L= 8000 bit
last bit of 3rd packet arrives, send ACK receiver
first packet bit arrives
ACK arrives, send next packet, t = RTT + L / R
first packet bit transmit last packet bit transmitted,
link rate R=1 Gbps, propagation delay 15 ms, each packet L= 8000 bit
dtrans = L = 8000bits = 8microseconds R 109bps
RTT = 2 ¡Á15ms = 30ms
RTT
ACK arrives, send next packet, t = RTT + L / R
last packet bit arrives, send ACK
3-packet pipelining increases utilization
U sender: sender utilization (fraction of time sender is busy sending)
Increase utilization
by a factor of 3!
by a factor of 3!
-> 1000bytes/30.008ms=33kB/sec data throughput over 1 Gbps link
Pipelining protocols
New requirements for rdt
range of sequence numbers must be increased
buffering more than one packet at sender and/or receiver
Two generic forms of pipelined reliable data transfer protocols
Go-back-N
Sender can have up to N unacked packets in pipeline
Receiver only sends cumulative acks
Sender has timer for oldest
unacked packet
If timer expires, retransmit all
unacked packets
Selective Repeat
Sender can have up to N unacked packets in pipeline
Receiver acks individual packets
Sender maintains timer for each
unacked packet
When timer expires, retransmit only
unack packet
Seq # of the next packet to send
Seq # of the oldest unacked packet
Go-Back-N (GBN): sender
Sender protocol
k-bit seq # carried in a field in packet header seq#range:0to2k 1
sender allows up to N consecutive unack¡¯ed packets sender has timer for the oldest unacked packet
timeout(n): retransmit packet n and all packets in window with higher seq #
base
Q: why do we limit the number of unacked packets to N?
A: flow control, congestion control
Seq # of the next packet to send
Seq # of the oldest unacked packet
Go-Back-N (GBN): sender (cont¡¯d)
Sender protocol
4 intervals of seq #
[1, base – 1]: packets already transmitted and acked [base, nextseqnum-1]: packets sent but not yet acked
[nextseqnum, base+N-1]: packets that can be sent immediately (when data from upper layer arrive)
[base+N, — ]: cannot be used until an unacked packet has been acked Window of size N slides forward over the seq # space
GBN: sliding-window protocol
base
Go-Back-N (GBN): receiver
Receiver protocol
sends ACK for correctly-received packet with highest in-order seq # i.e., cumulative ACK
ACK(n): ACKs all packets up to, including seq # n
in any other case, discards packet and resends ACK for the most recently received
packet with highest in-order seq #
e.g., corrupted packet, out-of-order packet => may generate duplicate ACKs
Why discarding out-of-order packets? (e.g., if packet n+1 is received while packet n is expected, discard packet n+1)
reason: if packet n is lost, packet n+1 will anyway be retransmitted advantage: no receiver buffering! it need only remember expectedseqnum
disadvantage: more retransmissions needed if subsequent retransmission of packet n+1 is lost or corrupted
expectedseqnum
out-of-order (discarded)
expected, not yet received
received, acked
Go-Back-N (GBN): sender FSM
Sender FSM
base
rdt_send(data)
N
invocation from above
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)
timeout
L
base=1 nextseqnum=1
rdt_rcv(rcvpkt)
&& corrupt(rcvpkt)
¦«
upper layer has to try again later
a timeout event
Wait
start_timer udt_send(sndpkt[base]) udt_send(sndpkt[base+1])
... udt_send(sndpkt[nextseqnum-1])
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)
base = getacknum(rcvpkt)+1 If (base == nextseqnum)
stop_timer else
receipt of an ACK
start timer when there are additional transmitted but unacked packets whose timer has not been started
start_timer
Go-Back-N (GBN): receiver FSM
expectedseqnum
Receiver FSM
any other cases
correctly receiving packet with in-order seq #
¦«
expectedseqnum=1 sndpkt =
default udt_send(sndpkt)
Wait
rdt_rcv(rcvpkt)
&& notcurrupt(rcvpkt)
&& hasseqnum(rcvpkt,expectedseqnum)
extract(rcvpkt,data) deliver_data(data)
sndpkt = make_pkt(expectedseqnum,ACK,chksum) udt_send(sndpkt)
expectedseqnum++
make_pkt(0,ACK,chksum)
GBN in action (1)
sender window (N=4)
012345678 012345678
012345678 012345678
12345678 12 345678
12 78 12 78
12 78 12 78
Xloss
sender
send pkt1 send pkt2 send pkt3 send pkt4
(wait)
rcv ack1, send pkt5 rcv ack2, send pkt6
pkt3 timeout
send pkt3 send pkt4 send pkt5 send pkt6
receiver
receive pkt1, send ack1 receive pkt2, send ack2
receive pkt4, discard, (re)send ack2
receive pkt5, discard,
(re)send ack2 receive pkt6, discard,
receiver
expectedseqnum
(after receipt)
1 2 3
3
3 3
packet to deliver
to upper layer
1 2
3456
3456
3456
3456
(re)send ack2
rcv pkt3, deliver, send ack3 4
rcv pkt4, deliver, send ack4 5 rcv pkt5, deliver, send ack5 6 rcv pkt6, deliver, send ack6 7
3 4
5 6
GBN in action (2)
sender window (N=6)
[1,6] [1,6]
[1,6]
[1,6] [2,7]
[2,7] [2,7] [2,7]
[2,7]
[2,7] [8,13]
[8,13] [8,13]
Sender Send pkt 1
Send pkt 2
Send pkt 3
Send pkt 4 Rev ACK 1
Send pkt 5 Send pkt 6 Send pkt 7
pkt 2 timeout
Send pkt 2
Send pkt 3 Rev ACK 7
Send pkt 8 Send pkt 9
Receiver
Rev pkt 1 send ACK 1
Rev pkt 2 send ACK 2
Rev pkt 3 send ACK 3
Rev pkt 4 send ACK 4
Rev pkt 5 send ACK 5
Rev pkt 6 send ACK 6
Rev pkt 7 send ACK 7
receiver
expectedseqnum
(after receipt)
pkts to deliver to upper layer
1 21
loss
3 4
5
2 3 4
6 5
7 6 8 7
...
...
...
Go-Back-N (GBN): a major problem
A major problem
many packets in pipeline when
window size large and bandwidth-delay product large
single packet error causes retransmission of many packets
not necessary
Selective Repeat
Receiver individually acknowledges all correctly received packets
buffers packets as needed, for eventual in-order delivery to upper layer
Sender only resends packets for which ACK not (correctly) received
sets timer for each unACKed packet sender window
N consecutive seq #¡¯s
limits seq #s of sent, unACKed pkts
Selective Repeat: sender/receiver windows
Sender window
Receiver window
Selective Repeat: sender protocol
sender
data received from above:
¡ì if next available seq # in window, send pkt and start timer on the pkt; otherwise, refuse data
timeout(n):
¡ì resend pkt n, restart timer on n ACK(n) in [send_base,send_base+N-1]
correctly received:
¡ì mark pkt n as received and stop its timer
¡ì if n is smallest unACKed pkt, advance send_base to next unACKed seq #
Selective Repeat: receiver protocol
receiver
pkt n in [rcv_base, rcv_base+N-1]
correctly received:
¡ì send ACK(n)
¡ì out-of-order: buffer
¡ì in-order: deliver (also deliver buffered, in-order pkts), advance rcv_base to next not-yet- received pkt
pkt n in [rcv_base-N,rcv_base-1]
¡ì Send ACK(n)
otherwise:
¡ì ignore
Why?
Sender
Receiver
Selective Repeat in action (1)
sender window (N=4)
012345678 012345678
012345678 012345678
12345678 12345678
12345678
12 78 12 78 12 78
sender
receiver
receive pkt1, send ack1 receive pkt2, send ack2
receive pkt4, buffer, send ack4
receive pkt5, buffer,
send ack5 receive pkt6, buffer,
send ack6
receive pkt3; send ack3
receiver window (after receipt)
pkts to
deliver to upper
send pkt1 send pkt2 send pkt3 send pkt4
layer 12345678 1
Xloss (wait)
012345678 12345678 2
rcv ack1, send pkt5 rcv ack2, send pkt6
record ack4 arrived
pkt 3 timeout
send pkt3
record ack5 arrived record ack6 arrived
Q: what happens when ack3 arrives?
Sender window: 1 2 3 4 5 6 7 8 9 10
12345678 12345678
12345678
1 2 3 4 5 6 7 8 9 10
3,4,5,6
3456
3456
3456
Selective Repeat in action (2)
ACKs in buffer
sender window
[1,6]
[1,6] [1,6]
[1,6] [2,7]
[2,7] [2,7]
[2,7] [2,7]
[2,7] [2,7]
[4,9]
Sender
Send pkt 1 Send pkt 2
Send pkt 3
Send pkt 4 Rev ACK 1
Send pkt 5 Rev ACK 3
Send pkt 6 Send pkt 7
pkt 2 timeout
Send pkt 2
Rev ACK 7
Rev ACK 2 Send pkt 8
N=6
loss
Receiver
Rev pkt 1 send ACK 1
Rev pkt 3 send ACK 3
Rev pkt 4
send ACK 4 Rev pkt 5
send ACK 5
Rev pkt 6 send ACK 6
Rev pkt 7 send ACK 7
Rev pkt 2 send ACK 2
receiver window (after receipt)
pkts in buffer
pkts to deliver to upper layer
1
3
[1,6]
[2,7]
[2,7]
[2,7] [2,7]
[2,7] [2,7]
[8,13]
3
3, 4 3,4,5
3,4,5,6 3,4,5,6,7
3, 7 7
2,3,4,5,6,7
...
...
Selective Repeat: window size vs. seq # size
sender window (after receipt)
receiver window (after receipt)
Q: what relationship between seq. # size and window size?
pkt0
X
will accept packet with seq number 0
receiver can¡¯t see sender side. receiver behavior identical in both cases! something¡¯s (very) wrong!
pkt0
pkt1
pkt2 0123012
0123012 0123012 0123012
0123012 0123012
pkt1
0123012 pkt3 0123012
pkt2 0123012
Example
window size: N=3 seq #¡¯s: 0,1,2,3
Receiver sees no difference in two scenarios!
in (b), incorrectly passes duplicate data as new
pkt0 (a) no problem
0123012 0123012 0123012
0123012 X 0123012
timeout retransmit pkt0
X X
pkt0 (b) oops!
0123012
will accept packet with seq number 0
Selective Repeat: window size vs. seq # size (cont¡¯d)
Relationship between window size N and seq. # size q ( k) 2
seq. # space must be large enough to fit the entire receiver window and the entire sender window
The extreme scenario
receiver expects pkts [m, m+N-1]
ACKs for pkt [m-N,m-1] are still propagating back sender window [m-N,m-1]
Sender
Therefore
Selective Repeat: q 2N
Others
GBN: q N+1 Stop-and-Wait: q 2
Receiver
Required reading
Computer Networking: A Top-Down Approach (7th Edition) Ch 3.4.2, 3.4.3, 3.4.4
Interactive animation of GBN:
https://media.pearsoncmg.com/aw/ecs_kurose_compnetwork_7/ cw/content/interactiveanimations/go-back-n-protocol/index.html
Interactive animations on SR:
https://media.pearsoncmg.com/aw/ecs_kurose_compnetwork_7/cw/ content/interactiveanimations/selective-repeat-protocol/index.html
Acknowledgement:
Some materials are extracted from the slides created by Prof. Jim F. Kurose and Prof. Keith W. Ross for the textbook.