Transcript udt_send(sndpkt)

Transport Overview
10/7/2009
1
Outline
 Recap
 Overview of transport layer
 UDP
 Reliable data transfer, the stop-and-wait
protocol
2
Recap: P2P
 The Lookup problem
 More generally, moving from a host-centric Internet to a
“data-centric” Internet supporting data persistency,
availability, and authenticity
 The scalability problem
3
Key Design Issues
 Robustness: Resistant
to churn and failures
 Efficiency: A client
has content that
others need;
otherwise, its upload
capacity may not be
utilized
 Incentive: clients are
willing to upload
 Lookup problem
servers
C0
client
1
C1
C2
Cn
C3
client
2
client
3
client
n
4
Recap: BitTorrent Robustness
 A swarming protocol: peers exchange piece
availability and request blocks from peers
Piece: unit of information exchange among peers
Block: unit of download
File
2
1
3
4
Piece
256KB
Block
16KB
Incomplete Piece
0
1
0
1
5
BitTorrent: Incentive
 Periodically (typically
every 10 seconds) calculate
data-receiving rates from
all peers
requests/
interests
requests/
interests
 Upload to (unchoke) the
fastest
- constant number (4) of
unchoking slots
requests/
interests
requests/
interests
- partition upload bw
equally among unchoked
commonly referred to as “tit-for-tat” strategy
requests/
interests
Optimistic Unchoking
 Periodically select a peer at random
and upload to it

typically every 3 unchoking rounds (30 seconds)
 Multi-purpose mechanism
 allow bootstrapping of new clients
 continuously look for the fastest peers
(exploitation vs exploration)
Block Availability
 Request (local) rarest first
 achieves the fastest replication of rare pieces
 obtain something of value
Block Availability: Revisions
 When downloading starts (first 4 pieces):
choose at random and request them from
the peers
get pieces as quickly as possible
 obtain something to offer to others

 Endgame mode
 defense against the “last-block problem”: cannot
finish because missing a few last pieces
 send requests for missing sub-pieces to all
peers in our peer list
 send cancel messages upon receipt of a sub-piece
BitTorrent Fluid Analysis
 Normalize file size to 1
 x(t): number of downloaders (also known as leechers)
 y(t): number of seeds in the system at time t.
 : the arrival rate of new requests.
 : the uploading bandwidth of a given peer.
 c: the downloading bandwidth of a given peer,
assume c ≥ μ.
 : the rate at which downloaders abort download.
 : the rate at which seeds leave the system.
 : indicates the effectiveness of downloader
sharing, η takes values in [0, 1].
10
System Evolution
Solving steady state:
Define
11
System Evolution: Download Time T
 Look at system state, # of downloaders that
will finish download and become seed:
=>
12
BitTorrent: Summary
 Very widely used
 mainline: written in Python
 Azureus and μTorrent: the
most popular
 Other popular clients: ABC,
BitComet, BitLord, BitTornado,
Opera browser
 Many explorations, e.g.,
 BitThief
 BitTyrant
 Better understanding
is needed
requests/
interests
requests/
interests
requests/
interests
requests/
interests
requests/
interests
Summary: P2P
 Widely considered to be a key component for
the next-generation Content distribution
system
 Many issues remaining, e.g.,
 Streaming
 ISP/P2P integration
…
14
Outline
 Recap
 Overview of transport layer
 UDP
 Reliable data transfer, the stop-and-go
protocols
15
Transport Layer vs. Network Layer
 Provide logical communication
between app’ processes
 Transport protocols run in
end systems
 send side: breaks app
messages into segments,
passes to network layer
 rcv side: reassembles
segments into messages,
passes to app layer
 Transport vs. network layer
services:


Network layer: data transfer
between end systems
Transport layer: data
transfer between processes
application
transport
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
application
transport
network
data link
physical
• relies on, enhances network
layer services
16
Transport Layer Services and Protocols
 Reliable, in-order delivery (TCP)
 multiplexing
 reliability and connection setup
 congestion control
 flow control
 Unreliable, unordered delivery: UDP
 multiplexing
 Services not available:
 delay guarantees
 bandwidth guarantees
17
Transport Layer: Road Ahead
 Class 1:



transport layer services
connectionless transport: UDP
reliable data transfer using stop-and-wait
 Class 2:


sliding window reliability
TCP reliability
• overview of TCP
• TCP RTT measurement
• TCP connection management
 Class 3:


principles of congestion control
TCP congestion control; AIMD
 Class 4:


performance modeling; TCP variants
the analysis and design framework for congestion control
18
Outline
 Recap
 Overview of transport layer
 UDP
 Reliable data transfer, the stop-and-go
protocols
19
UDP: User Datagram Protocol [RFC 768]
 Often used for
streaming
multimedia apps Length, in
loss tolerant
 rate sensitive

Other UDP
uses
DNS
SNMP
bytes of
UDP
segment,
including
header
32 bits
source port # dest port #
checksum
length
Application
data
(message)
UDP segment format
UDP Checksum
Goal: end-to-end detection of “errors” (e.g., flipped bits) in
transmitted segment
Sender:
 treat segment contents as
sequence of 16-bit integers
 checksum: addition of
segment contents to be
zero
 sender puts checksum
value into UDP checksum
field
Receiver:
 compute checksum of
received segment
 compute sum of segment and
checksum; check if sum zero
 NO - error detected
 YES - no error detected.
But maybe errors
nonetheless?
One’s Complement Arithmetic
 UDP checksum is based on one’s complement
arithmetic

one’s complement was a common representation of signed
numbers in early computers
 One’s complement representation
 bit-wise NOT for negative numbers
 example: assume 8 bits
•
•
•
•
•

00000000:
00000001:
01111111:
10000000:
11111111:
0
1
127
?
?
addition: conventional binary addition except adding any
resulting carry back into the resulting sum
• Example: -1 + 2
22
UDP Checksum: Algorithm
 Example checksum:
1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0
1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
wraparound 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1
sum 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0
checksum
0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1
- For fast implementation of computing UDP checksum,
see http://www.faqs.org/rfcs/rfc1071.html
UDP Checksum: Coverage
Calculated over:
 A pseudo-header




IP Source Address
(4 bytes)
IP Destination Address
(4 bytes)
Protocol (2 bytes)
UDP Length (2 bytes)
 UDP header
 UDP data
Outline
 Recap
 Overview of transport layer
 UDP
 Reliable data transfer
25
Principles of Reliable Data Transfer
 Important in app., transport, link layers
 top-10 list of important networking topics!
26
Reliable Data Transfer
27
Reliable Data Transfer: Getting Started
rdt_send(): called from above,
(e.g., by app.)
send
side
udt_send(): called by rdt,
to transfer packet over
unreliable channel to receiver
deliver_data(): called by
rdt to deliver data to upper
receive
side
rdt_rcv(): called from below;
when packet arrives on rcv-side of
channel
28
Reliable Data Transfer: Getting Started
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: when in this
“state” next state
uniquely determined
by next event
state
1
event causing state transition
actions taken on state transition
event
actions
state
2
29
Outline
 Review
 Overview of transport layer
 UDP
 Reliable data transfer

perfect channel
30
Rdt1.0: reliable transfer over a reliable channel
 separate FSMs for sender, receiver:
 sender sends data into underlying channel
 receiver reads data from underlying channel
Wait for
call from
above
rdt_send(data)
packet = make_pkt(data)
udt_send(packet)
sender
Wait for
call from
below
rdt_rcv(packet)
extract (packet,data)
deliver_data(data)
receiver
31
Potential Channel Errors
 bit errors
 loss (drop) of packets
 reordering or duplication
Characteristics of unreliable channel will determine complexity of
reliable data transfer protocol (rdt).
32
Outline
 Recap
 Overview of transport layer
 UDP
 Reliable data transfer
o

perfect channel
channel with bit errors
33
Rdt2.0: Channel With Bit Errors
 Underlying channel may flip bits in packet
 New mechanisms in rdt2.0 (beyond rdt1.0):



receiver error detection: recall: UDP checksum to detect
bit errors
sender retransmission
receiver feedback: control msgs (ACK,NAK) rcvr->sender
• 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
34
rdt2.0: FSM Specification
rdt_send(data)
snkpkt = make_pkt(data, checksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
isNAK(rcvpkt)
Wait for
Wait for
data
ACK or
udt_send(sndpkt)
NAK
rdt_rcv(rcvpkt) && isACK(rcvpkt)
L
sender
receiver
rdt_rcv(rcvpkt) &&
corrupt(rcvpkt)
udt_send(NAK)
Wait for
data
rdt_rcv(rcvpkt) &&
notcorrupt(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
udt_send(ACK)
35
rdt2.0: Operation with No Errors
rdt_send(data)
snkpkt = make_pkt(data, checksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
isNAK(rcvpkt)
Wait for
Wait for
data
ACK or
udt_send(sndpkt)
NAK
rdt_rcv(rcvpkt) && isACK(rcvpkt)
L
rdt_rcv(rcvpkt) &&
corrupt(rcvpkt)
udt_send(NAK)
Wait for
data
rdt_rcv(rcvpkt) &&
notcorrupt(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
udt_send(ACK)
36
rdt2.0: Error Scenario
rdt_send(data)
snkpkt = make_pkt(data, checksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
isNAK(rcvpkt)
Wait for
Wait for
data
ACK or
udt_send(sndpkt)
NAK
rdt_rcv(rcvpkt) && isACK(rcvpkt)
L
rdt_rcv(rcvpkt) &&
corrupt(rcvpkt)
udt_send(NAK)
Wait for
data
rdt_rcv(rcvpkt) &&
notcorrupt(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
udt_send(ACK)
37
Big Picture of rdt2.0
sender
receiver
waiting
for N/ACK
waiting
for data
38
rdt2.0 is Incomplete!
What happens if ACK/NAK corrupted?
 Although sender receives feedback, but doesn’t know
what happened at receiver!
sender
waiting
for
N/ACK
39
sender
Two Possibilities
rdt_send(data)
snkpkt = make_pkt(data, checksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
isNAK(rcvpkt)
Wait for
Wait for
data
ACK or
udt_send(sndpkt)
NAK
rdt_rcv(rcvpkt) && isACK(rcvpkt)
L
sender
receiver
sender
waiting
for
N/ACK
waiting
for
N/ACK
deliver
receiver
deliver
waiting
for data
40
Handle Control Message Corruption
It is always harder to deal with control
message errors than data message errors
 sender can’t just retransmit: possible duplicate
Handling duplicates:
 sender adds sequence
number to each pkt
 sender retransmits current
pkt if ACK/NAK garbled
 receiver discards (doesn’t
deliver up) duplicate pkt
stop and wait
sender sends one packet,
then waits for receiver
response
41
rdt2.1b: Sender, Handles Garbled
ACK/NAKs
rdt_send(data)
sndpkt = make_pkt(n, data, checksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
( corrupt(rcvpkt) ||
Wait
for
Wait for
isNAK(rcvpkt) )
ACK or
pkt n from
udt_send(sndpkt)
NAK
above
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
&& isACK(rcvpkt)
L
Wait for
ACK or
NAK
Wait for
pkt n+1 from
above
rdt_send(data)
sndpkt = make_pkt(n+1, data, checksum)
udt_send(sndpkt)
42
rdt2.1b: Receiver, Handles Garbled
ACK/NAKs
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)
&& has_seq(n, rcvpkt)
rdt_rcv(rcvpkt) && corrupt(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
sndpkt = make_pkt(ACK, chksum)
udt_send(sndpkt)
sndpkt = make_pkt(NAK, chksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
not corrupt(rcvpkt) &&
! has_seq(n,rcvpkt)
Wait for
n from
below
Wait for
n+1 from
below
sndpkt = make_pkt(ACK, chksum)
udt_send(sndpkt)
43
rdt2.1b: Summary
Sender:
 seq # added to pkt
 must check if received ACK/NAK corrupted
Receiver:
 must check if received packet is duplicate

by checking if the packet has the expected pkt seq #
44
Another Look at rdt2.1b
sender
receiver
waiting for n
sending n
waiting n+1
sending
n+1
waiting for n+2
45
State Relationship of rt2.1b
first
time
rcvs
ack 0
s0
w0
W1: wait for data with seq. 1
S1: sending data with seq. 1
w1 s1 w2
w0
first
time
rcvs 0
w1
w2
s2
w3
w3
sender
receiver
State invariant:
- When receiver’s state is waiting for seq
#n, sender’s state can be sending either
seq#n-1or seq#n
46
rdt2.1c: Sender, Handles Garbled
ACK/NAKs: Using 1 bit
rdt_send(data)
sndpkt = make_pkt(0, data, checksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
( corrupt(rcvpkt) ||
Wait
for
Wait for
isNAK(rcvpkt) )
ACK or
call 0 from
udt_send(sndpkt)
NAK
above
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
&& isACK(rcvpkt)
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
&& isACK(rcvpkt)
L
rdt_rcv(rcvpkt) &&
( corrupt(rcvpkt) ||
isNAK(rcvpkt) )
udt_send(sndpkt)
L
Wait for
ACK or
NAK 1
Wait for
call 1 from
above
rdt_send(data)
sndpkt = make_pkt(1, data, checksum)
udt_send(sndpkt)
47
rdt2.1c: Receiver, Handles Garbled
ACK/NAKs: Using 1 bit
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)
&& has_seq0(rcvpkt)
rdt_rcv(rcvpkt) && (corrupt(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
sndpkt = make_pkt(ACK, chksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) && (corrupt(rcvpkt)
sndpkt = make_pkt(NAK, chksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
not corrupt(rcvpkt) &&
has_seq1(rcvpkt)
sndpkt = make_pkt(ACK, chksum)
udt_send(sndpkt)
sndpkt = make_pkt(NAK, chksum)
udt_send(sndpkt)
Wait for
0 from
below
Wait for
1 from
below
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)
&& has_seq1(rcvpkt)
rdt_rcv(rcvpkt) &&
not corrupt(rcvpkt) &&
has_seq0(rcvpkt)
sndpkt = make_pkt(ACK, chksum)
udt_send(sndpkt)
extract(rcvpkt,data)
deliver_data(data)
sndpkt = make_pkt(ACK, chksum)
udt_send(sndpkt)
48
rdt2.1c: Discussion
Sender:
 state must “remember”
whether “current” pkt
has 0 or 1 seq. #
Receiver:
 must check if received
packet is duplicate

state indicates whether
0 or 1 is expected pkt
seq #
49
A Flavor of Protocol Correctness
Analysis: rdt2.1c
 Combined states of sender and channel
 Assume the sender always has data to send
corrupt
sender state: sending 0 and waiting for ACK
receiver state: waiting for 0
channel state: packet seq#
ok
corrupt
00N
000
010
corrupt
ok
01A
ok
ok
ok
100
corrupt
10N
corrupt
111
10A
corrupt
01N
11N
ok
50
rdt2.2: a NAK-free protocol
 Same functionality as rdt2.1c, 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
51
rdt2.2: Sender, Receiver Fragments
rdt_send(data)
sndpkt = make_pkt(0, data, checksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
( corrupt(rcvpkt) ||
Wait for
Wait for
isACK(rcvpkt,1) )
ACK
call 0 from
0
udt_send(sndpkt)
above
sender FSM
fragment
rdt_rcv(rcvpkt) &&
(corrupt(rcvpkt) ||
has_seq1(rcvpkt))
sndpkt=
make_pkt(ACK,1,
chksum)
udt_send(sndpkt)
Wait for
0 from
below
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
&& isACK(rcvpkt,0)
receiver FSM
fragment
L
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)
&& has_seq0(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
sndpkt = make_pkt(ACK,0, chksum)
udt_send(sndpkt)
52
Outline
 Review
 Overview of transport layer
 UDP
 Reliable data transfer
o
o

perfect channel
channel with bit errors
channel with bit errors and losses
53
rdt3.0: Channels with Errors and Loss
New assumption:
underlying channel can
also lose packets (data
or ACKs)

checksum, seq. #, ACKs,
retransmissions will be
of help, but not enough
Q: how to deal with loss?
Approach: sender waits
“reasonable” amount of
time for ACK
 requires countdown timer
 retransmits if no ACK
received in this time
 if pkt (or ACK) just delayed
(not lost):
 retransmission will be
duplicate, but use of seq.
#’s already handles this
 receiver must specify seq
# of pkt being ACKed
54
rdt3.0 Sender
rdt_send(data)
sndpkt = make_pkt(0, data, checksum)
udt_send(sndpkt)
start_timer
rdt_rcv(rcvpkt)
L
Wait for
call 0 from
above
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
&& isACK(rcvpkt,1)
timeout
udt_send(sndpkt)
start_timer
rdt_rcv(rcvpkt) &&
( corrupt(rcvpkt) ||
isACK(rcvpkt,0) )
L
Wait
for
ACK0
timeout
udt_send(sndpkt)
start_timer
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
&& isACK(rcvpkt,0)
stop_timer
stop_timer
L
rdt_rcv(rcvpkt) &&
( corrupt(rcvpkt) ||
isACK(rcvpkt,1) )
Wait
for
ACK1
Wait for
call 1 from
above
rdt_send(data)
rdt_rcv(rcvpkt)
L
sndpkt = make_pkt(1, data, checksum)
udt_send(sndpkt)
start_timer
55
rdt3.0 in Action
Question to think about: How to determine a good timeout value?
56
rdt3.0 in Action
57
rdt3.0
sender
receiver
waiting
for 0
(n-1)
sending 0
(n-1)
waiting
for 1
(n)
sending 1
(n)
waiting
for 0
(n+1)
State consistency:
When receiver’s state is
waiting n, the state of the
sender is either sending
for n-1 or sending for n
When sender’s state is
sending for n, receiver’s
state is waiting for n or n
+1
58
rdt3.0: Stop-and-Wait Operation
sender
receiver
first packet bit transmitted, t = 0
last packet bit transmitted, t = L / R
RTT
first packet bit arrives
last packet bit arrives, send ACK
ACK arrives, send next
packet, t = RTT + L / R
What is Usender: utilization – fraction of time sender busy sending?
Assume: 1 Gbps link, 15 ms e-e prop. delay, 1KB packet
59
Performance of rdt3.0
 rdt3.0 works, but performance stinks
 Example: 1 Gbps link, 15 ms e-e prop. delay, 1KB packet:
Ttransmit =
U


L (packet length in bits)
8kb/pkt
=
= 8 microsec
R (transmission rate, bps)
10**9 b/sec
=
sender
L/R
RTT + L / R
=
.008
30.008
= 0.00027
microsec
onds
1KB pkt every 30 msec -> 33kB/sec thruput over 1 Gbps link
network protocol limits use of physical resources !
60
A Summary of Questions
 How to improve the performance of rdt3.0?
 What if there are reordering and
duplication?
 How to determine the “right” timeout value?
61
62
Sliding Window Protocols: Pipelining
Pipelining: sender allows multiple, “in-flight”, yet-to-beacknowledged pkts


range of sequence numbers must be increased
buffering at sender and/or receiver
 Two generic forms of pipelined protocols: go-Back-N,
selective repeat
63
Pipelining: Increased Utilization
sender
receiver
first packet bit transmitted, t = 0
last bit transmitted, t = L / R
first packet bit arrives
last packet bit arrives, send ACK
last bit of 2nd packet arrives, send ACK
last bit of 3rd packet arrives, send ACK
RTT
ACK arrives, send next
packet, t = RTT + L / R
increase utilization
by a factor of 3!
U
sender
=
3*L/R
RTT + L / R
=
.024
30.008
= 0.0008
microsecon
ds
Question: a rule-of-thumb window size?
64
Go-Back-n
Sender:
 k-bit seq # in pkt header
 “window” of up to W, consecutive unack’ed pkts allowed
W
 ACK(n): ACKs all pkts up to, including seq # n - “cumulative ACK”
note: ACK(n) could mean two things: I have received upto and
include n, or I am waiting for n
 timer for the packet at base
 timeout(n): retransmit pkt n and all higher seq # pkts in window

65
GBN: Sender Extended FSM
rdt_send(data)
L
if (nextseqnum < base+W) {
sndpkt[nextseqnum] = make_pkt(nextseqnum,data,chksum)
udt_send(sndpkt[nextseqnum])
if (base == nextseqnum) start_timer
nextseqnum++
} else
block sender
base=1
nextseqnum=1
Wait
rdt_rcv(rcvpkt)
&& corrupt(rcvpkt)
timeout
start_timer
udt_send(sndpkt[base])
udt_send(sndpkt[base+1])
…
udt_send(sndpkt[nextseqnum-1])
rdt_rcv(rcvpkt) &&
notcorrupt(rcvpkt)
if (new packets ACKed) {
advance base;
if (more packets waiting)
send more packets
}
if (base == nextseqnum)
stop_timer
else
start_timer for the packet at new base
66
GBN: Receiver Extended FSM
default
udt_send(sndpkt)
L
Wait
expectedseqnum=1
sndpkt =
make_pkt(expectedseqnum,ACK,chksum)
rdt_rcv(rcvpkt)
&& notcurrupt(rcvpkt)
&& hasseqnum(rcvpkt,expectedseqnum)
extract(rcvpkt,data)
deliver_data(data)
sndpkt = make_pkt(expectedseqnum,ACK,chksum)
udt_send(sndpkt)
expectedseqnum++
ACK-only: always send ACK for correctly-received pkt
with highest in-order seq #

need only remember expectedseqnum
 out-of-order pkt:
 discard (don’t buffer) -> no receiver buffering!
 re-ACK pkt with highest in-order seq #
 may generate duplicate ACKs
67
GBN in
Action
window
size = 4
68
Discussion: Efficiency of Go-Back-n
 Assume window size W
 Assume each packet is lost with probability p
 On average, how many packets do we send
for each data packet?
69
Selective Repeat
 Sender window
 Window size W: W consecutive unACKed seq #’s
 Receiver individually acknowledges correctly
received pkts



buffers pkts as needed, for eventual in-order delivery
to upper layer
ACK(n) means received packet with seq# n only
buffer size at receiver: window size
 Sender only resends pkts for which ACK not
received

sender timer for each unACKed pkt
70
Selective Repeat: Sender, Receiver Windows
W
W
71
Selective Repeat
sender
data from above :
 unACKed packets is less than
window size W, send;
otherwise block app.
timeout(n):
 resend pkt n, restart timer
ACK(n) in [sendbase,sendbase+W-1]:
 mark pkt n as received
 update sendbase to the first
receiver
pkt n in [rcvbase, rcvbase+W-1]
 send ACK(n)
 if (out-of-order)
mark and buffer pkt n
else /*in-order*/
deliver any in-order
packets
otherwise:
 ignore
packet unACKed
72
Selective Repeat in Action
73
Discussion: Efficiency of Selective Repeat
 Assume window size W
 Assume each packet is lost with probability p
 On average, how many packets do we send
for each data packet?
74
State Invariant: Window Location

Go-back-n (GBN)
sender window
receiver window

Selective repeat (SR)
sender window
receiver window
75
Window Location

Q: what relationship
between seq # size and
window size?
Go-back-n (GBN)
sender window
receiver window

Selective repeat (SR)
sender window
receiver window
76
Selective Repeat:
Seq# Ambiguity
Example:
 seq #’s: 0, 1, 2, 3
 window size=3
 receiver sees no
difference in two
scenarios!
 incorrectly passes
duplicate data as new
in (a)
77
Sliding Window Protocols:
Go-back-n and Selective Repeat
Go-back-n
data bandwidth: sender
to receiver
(avg. number of times a
pkt is transmitted)
ACK bandwidth
(receiver to sender)
Relationship between M (the
number of seq#) and W
(window size)
Buffer size at
receiver
Complexity
Less efficient
1 p  pw
1 p
Selective Repeat
More efficient
1
1 p
More efficient
Less efficient
M>W
M ≥ 2W
1
W
Simpler
More complex
p: the loss rate of a packet; M: number of seq# (e.g., 3 bit M = 8); W: window size 78
Question: What is Initial Seq#?
sender
receiver
accept
79
Question: What is Initial Seq#?
sender
receiver
accept
accept?
 To avoid the scenario, a sender should not reuse a seq# before
it is sure the packet has left the network
80
Outline
 Recap
 Sliding window protocols
 Go-back-n
 Selective repeat
 Connection management
81
Connection Management: Objective
 Agree on initial sequence numbers

a sender will not reuse a seq# before it is sure
that all packets with the seq# are purged from
the network
• the network guarantees that a packet too old will be
purged from the network: network bounds the life time
of each packet

To avoid waiting for the seq# to start a session,
use a larger seq# space
• needs connection setup so that the sender tells the
receiver initial seq#
 Agree on other initial parameters
82
Three Way Handshake (TWH) [Tomlinson 1975]
Host A
Host B
accept?
accept data only after
verified x is the init. seq
SYN: indicates connection setup
83
Scenarios with Duplicate Request
Host A
Host B
accept?
no such
request
reject
84
Three Way Handshake (TWH) [Tomlinson 1975]
 To ensure that the other side does want to send a request
Host A
Host B
Host A
Host B
accept?
no such
request
reject
85
Connection Close
 Objective of closure
handshake:

each side can release
resource and remove
state about the
connection
client
server
init. close
release
resource?
close
close
release
resource?
release
resource?
86
General Case: The Two-Army Problem
The two blue armies need to agree on whether or not they will attack the white army. They achieve
agreement by sending messengers to the other side. If they both agree, attack; otherwise, no. Note
that a messenger can be captured!
87
Four Way Teardown
Host A
Host B
propose close close
A->B
A->B closed
close propose close
- can retransmit the
ACKif its ACK is lost
closed
all states removed
timed wait
A->B closed
B->A
closed
all states removed
88
A Summary of Questions
 How to improve the performance of rdt3.0?

sliding window protocols
 What if there are duplication and
reordering?



network guarantee: max packet life time
transport guarantee: not reuse a seq# before life
time
seq# management and connection management
 How to determine the “right” parameters?
89
Backup Slides
90
Reordering and Duplication
 Out-of-order and/or duplicated packets could be accepted by
the receiver if not handled correctly
 There are many solutions each with its own pitfalls
 Internet solution: for each connection (sender-receiver pair),
ensuring that two identically numbered packets are never
outstanding at the same time


network bounds the life time of each packet
a connection will not reuse a seq# before it is sure that all
packets with the seq# are purged from the network
• seq. number space should be large enough to not limit transmission
rate
• needs connection setup so that the sender tells the receiver initial
seq#
91
Scenarios with Duplicate Request/Reply
Host A
Host B
accept?
no such
request
reject
92
Backup Slides
93