Week 4-transport layer
Advanced Network Technologies
Application layer
Transport layer
School of Computer Science
Dr. Wei Bao| Lecturer
Peer-to-Peer
2
Pure peer-to-peer model architecture
› no always-on server
› arbitrary end systems directly
communicate
› peers are intermittently
connected and change IP
addresses
examples:
– file distribution (BitTorrent)
– Streaming (Zattoo, KanKan)
– VoIP (Skype)
3
File distribution: client-server vs. p2p
Question: how much time to distribute file (size F) from one server to N peers?
– peer upload/download capacity is limited resource
4
us
uN
dN
server
network (with abundant
bandwidth)
file, size F
us: server upload
capacity
ui: peer i upload
capacity
di: peer i download
capacityu2 d2
u1 d1
di
ui
File distribution time: client-server
› server transmission: must
sequentially send (upload) N
file copies:
– time to send one copy: F/us
– time to send N copies: NF/us
5
increases linearly in N
time to distribute F
to N clients using
client-server approach Dc-s > max{NF/us,,F/dmin}
v client: each client must
download file copy
§ dmin = min client download rate
§ (worst case) client download time: F/dmin
us
network
di
ui
F
6
› server transmission: must upload
at least one copy
– time to send one copy: F/us
time to distribute F
to N clients using
P2P approach
us
network
di
ui
F
DP2P > max{F/us,,F/dmin,,NF/(us + Sui)}
v client: each client must
download file copy
§ client download time: F/dmin
v clients: as aggregate must download NF bits = upload NF bits
§ Max upload rate us + Sui
§ NF/(us + Sui)
… but so does this, as each peer brings service capacity
increases linearly in N …
File distribution time: p2p
0
0.5
1
1.5
2
2.5
3
3.5
0 5 10 15 20 25 30 35
N
M
in
im
um
D
is
tr
ib
ut
io
n
T
im
e P2P
Client-Server
client upload rate = u, F/u = 1 hour, us = 10u, dmin ≥ us
Client-server vs. p2p
7
P2P file distribution: BitTorrent
› 20% of European internet traffic in 2012.
› Used for Linux distribution, software patches, distributing movies
› Goal: quickly replicate large files to large number of clients
› Web server hosts a .torrent file (w/ file length, hash, tracker’s URL…)
› A tracker tracks downloaders/owners of a file
› Files are divided into chunks (256kB-1MB)
› Downloaders download chunks from themselves (and owners)
› Tit-for-tat: the more one shares (server), the faster it can download (client)
8
BitTorrent, a file sharing application
tracker: tracks peers
participating in torrent
torrent: group of peers
exchanging chunks of a file
Alice arrives …
› file divided into 256KB chunks
› peers in torrent send/receive file chunks
… obtains list
of peers from tracker
… and begins exchanging
file chunks with peers in torrent
P2P file distribution: BitTorrent
9
P2P file distribution: BitTorrent
› peer joining torrent:
– has no chunks, but will accumulate
them over time from other peers
– registers with tracker to get list of
peers, connects to subset of peers
(“neighbors”)
10
› while downloading, peer uploads chunks to other peers
› peer may change peers with whom it exchanges chunks
› churn: peers may come and go
› once peer has entire file, it may (selfishly) leave or
(altruistically) remain in torrent
BitTorrent: requesting, sending file chunks
requesting chunks:
› at any given time, different
peers have different subsets
of file chunks
› periodically, Alice asks each
peer for list of chunks that
they have
› Alice requests missing chunks
from peers, rarest first
11
sending chunks: tit-for-tat
› Alice sends chunks to those four
peers currently sending her
chunks at highest rate
› other peers are choked by Alice (do not
receive chunks from her)
› re-evaluate top 4 every10 secs
› every 30 secs: randomly select
another peer, starts sending
chunks
› “optimistically unchoke” this peer
› newly chosen peer may join top 4
(1) Alice “optimistically unchokes” Bob
(2) Alice becomes one of Bob’s top-four providers; Bob reciprocates
(3) Bob becomes one of Alice’s top-four providers
higher upload rate: find better
trading partners, get file faster !
BitTorrent: tit-for-tat
12
Distributed Hash Table
13
Distributed hash table (DHT)
›DHT: a distributed P2P database
›database has (key, value) pairs; examples:
– key: social security number; value: human name
›distribute the (key, value) pairs over the many
peers
›a peer queries DHT with key
-DHT returns values that match the key
›peers can also insert (key, value) pairs
14
Distributed hash table (DHT)
›Assign the keys
›Lookup the keys
15
Assigning key to peer
›central issue:
– assigning (key, value) pairs to peers.
›basic idea:
-Key: generate an integer
-Assign an integer ID to each peer
– put (key,value) pair in the peer that is closest to
the key
16
Assigning key to peer
›distance: assign integer identifier to each peer in range
[0,2n-1] for some n.
– each identifier represented by n bits.
›Each key to be an integer in same range [0,2n-1]
› to get integer key, hash original key
– A hash function is any function that can be used to map data of
arbitrary size to data of fixed size (e.g., an integer in [0,2n-1] ).
– e.g., 15 = hash(“Led Zeppelin IV”)
– this is why its is referred to as a distributed “hash” table
17
Assigning key to peer
›rule: assign key to the peer that has the
closest ID.
›Here: closest is the immediate successor of the
key.
›e.g., n = 4; peers: 1, 3, 4, 5, 8, 10, 12, 14;
– key = 13, then successor peer = 14
– key = 15, then successor peer = 1
18
Lookup the keys
› Given a key, find the host that owns the key
19
Goal: to provide a distributed lookup service returning the host
that owns the key
i
a
k?
c
b
d
k? k?
k!
k?
1
3
4
5
8
10
12
15
Circular DHT
› each peer only aware of immediate successor.
20
0001
0011
0100
0101
1000
1010
1100
1111
Who’s responsible
for key 1110 ?
I am
O(N) messages
on average to resolve
query, when there
are N peers
1110
1110
1110
1110
1110
1110
Define closest
as closest
successor
Circular DHT (con’t)
21
key 1110 is
stored at node
1111
Circular DHT (con’t)
22
Example: Chord is an example of a Distributed Hash Table (DHT)
As a node:
› I have a successor peer
› I have a predecessor peer
› I have some shortcuts to other nodes
to speedup delivery of requests
› Chord: A scalable peer-to-peer lookup
service for internet applications. Stoica et
al. SIGCOMM 2001.
Circular DHT (con’t)
› each peer keeps track of predecessor, successor, short cuts.
› reduced from 6 to 2 messages.
› possible to design shortcuts so O(log N) neighbors, O(log N)
messages in query
23
1
3
4
5
8
10
12
15
Who’s responsible
for key 1110 (14) ?
Transport Layer
24
Transport Layer
our goals:
› understand principles
behind transport layer
services:
– multiplexing,
demultiplexing
– reliable data transfer
– flow control
– congestion control
› learn about Internet
transport layer protocols:
– UDP: connectionless transport
– TCP: connection-oriented
reliable transport
– TCP congestion control
25
Outline
› Transport-layer services
› Multiplexing/demultiplexing
› Connectionless transport (UDP)
› Principles of reliable data transfer
› TCP protocol
26
Transport Services
27
› provide logical communication
between app processes running on
different hosts
› 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
› more than one transport protocol
available to apps
– Internet: TCP and UDP
application
transport
network
data link
physical
logical end-end transport
application
transport
network
data link
physical
Transport services and protocols
28
›network layer: host-to-host communication
– best-effort, unreliable
› transport layer: process-to-process
communication
– relies on, enhances, network layer services
Transport vs. network layer
29
› IP: best effort service
› reliable, in-order delivery
(TCP)
– congestion control
– flow control
– connection setup
› unreliable, unordered
delivery: UDP
– no-frills extension of “best-
effort” IP
› services not available:
– delay guarantees
– bandwidth guarantees
application
transport
network
data link
physical
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
network
data link
physical
network
data link
physical
logical end-end transport
Internet transport-layer protocols
30
Transport Services
31
process
socket
use header info to deliver
received segments to correct
socket
demultiplexing at receiver:handle data from multiple
sockets, add transport header
(later used for demultiplexing)
multiplexing at sender:
transport
application
physical
link
network
P2P1
transport
application
physical
link
network
P4
transport
application
physical
link
network
P3
Multiplexing/demultiplexing
32
› host receives IP datagrams
– each datagram has source IP address,
destination IP address
– each datagram carries one transport-layer
segment
– each segment has source, destination port
number
› host uses IP addresses & port numbers to
direct segment to appropriate socket
source port # dest port #
32 bits
application
data
(payload)
other header fields
TCP/UDP segment format
How demultiplexing works
33
IP header
source IP address
destination IP address
› recall: created socket has host-
local port #:
›when host receives UDP
segment:
– Checks destination port # in
segment
– directs UDP segment to socket
with that port #
v recall: when creating
datagram to send into
UDP socket, must specify
§ destination IP address
§ destination port #
clientSocket.sendto(message,(desip,
des port))
Packets with same dest.IP
address, dest. port #, but
different source IP
addresses and/or source
port numbers will be
directed to same socket at
dest
Connectionless demultiplexing
34
› Receiver › Sender
DatagramSocket serverSocket =
new DatagramSocket(6428);
transport
application
physical
link
network
P3
transport
application
physical
link
network
P1
transport
application
physical
link
network
P4
DatagramSocket mySocket1 =
new DatagramSocket(5775);
DatagramSocket mySocket2 =
new DatagramSocket(9157);
source port: 9157
dest port: 6428
source port: 6428
dest port: 9157
source port: 6428
dest port: 5775
source port: 5775
dest port: 6428
Connectionless demux: example
35
›TCP socket identified by
4-tuple:
– source IP address
– source port number
– dest IP address
– dest port number
› demux: receiver uses all
four values to direct
segment to appropriate
socket
› server host may support
many simultaneous TCP
sockets:
– each socket identified by its
own 4-tuple
›web servers have different
sockets for each
connecting client
– non-persistent HTTP will
have different socket for each
request
Connection-oriented demux
36
transport
application
physical
link
network
P1
transport
application
physical
link
P4
transport
application
physical
link
network
P2
source IP,port: A,9157
dest IP, port: B,80
source IP,port: B,80
dest IP,port: A,9157
host: IP
address A
host: IP
address C
network
P6P5
P3
source IP,port: C,5775
dest IP,port: B,80
source IP,port: C,9157
dest IP,port: B,80three segments, all destined to IP address: B,
dest port: 80 are demultiplexed to different sockets
server: IP
address B
Connection-oriented demux: example
37
transport
application
physical
link
network
P1
transport
application
physical
link
transport
application
physical
link
network
P2
source IP,port: A,9157
dest IP, port: B,80
source IP,port: B,80
dest IP,port: A,9157
host: IP
address A
host: IP
address C
server: IP
address B
network
P3
source IP,port: C,5775
dest IP,port: B,80
source IP,port: C,9157
dest IP,port: B,80
P4
threaded server
Connection-oriented demux: example
38
Connectionless Transport UDP
39
› “no frills,” Internet transport
protocol
› “best effort” service, UDP
segments may be:
– lost
– delivered out-of-order to app
› connectionless:
– no handshaking between
UDP sender, receiver
– each UDP segment handled
independently of others
v UDP use:
§ streaming multimedia apps (loss
tolerant, rate sensitive)
§ DNS
v reliable transfer over UDP:
§ add reliability at application layer
§ application-specific error recovery!
UDP: User Datagram Protocol [RFC 768]
40
› no connection establishment
(which can add delay)
› simple: no connection state at
sender, receiver
› small header size
› no congestion control: UDP
can blast away as fast as
desired
source port # dest port #
32 bits
application
data
(payload)
UDP segment format
length checksum
length, in bytes of
UDP segment,
including header
why is there a UDP?
UDP: segment header
41
sender:
› treat segment contents,
including header fields, as
sequence of 16-bit integers
› sum: addition (one’s
complement sum) of segment
contents
› checksum: complement of
sum
› sender puts checksum value
into UDP checksum field
receiver:
› compute checksum of received
segment
› check if computed checksum
equals checksum field value:
– NO – error detected
– YES – no error detected.
Goal: detect “errors” (e.g., flipped bits) in transmitted
segment
UDP checksum
42
example: add two 16-bit integers
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
1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0
1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1
wraparound
sum
checksum
Note: when adding numbers, a carryout from the most
significant bit needs to be added to the result
Internet checksum: example
43
carryout
Principles of Reliable Data Transfer
44
› 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)
Principles of reliable data transfer
45
› 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)
Principles of reliable data transfer
46
› 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)
Principles of reliable data transfer
47
Ne
tw
or
k
la
ye
r
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
Principles of reliable data transfer
48
We will:
› 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 A causing state transition
action X taken on state transition
state: when in this
“state”, next state
and action uniquely
determined by next
event
event B
action Y
Principles of reliable data transfer
49
› 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
Principles of reliable data transfer
50
› 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
How do humans recover from “errors”
during conversation?
rdt2.0: channel with bit errors
51
› 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
52
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)
udt_send(NAK)
rdt_rcv(rcvpkt) &&
corrupt(rcvpkt)
Wait for
ACK or
NAK
Wait for
call from
belowsender
receiver
rdt_send(data)
L
53
rdt2.0: FSM specification
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)
udt_send(NAK)
rdt_rcv(rcvpkt) &&
corrupt(rcvpkt)
Wait for
ACK or
NAK
Wait for
call from
below
rdt_send(data)
L
rdt2.0: operation with no errors
54
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)
udt_send(NAK)
rdt_rcv(rcvpkt) &&
corrupt(rcvpkt)
Wait for
ACK or
NAK
Wait for
call from
below
rdt_send(data)
L
rdt2.0: error scenario
55
what happens if ACK/NAK
corrupted?
› sender does not know what
happened at receiver!
› cannot just retransmit:
possible duplicate
handling duplicates:
› sender retransmits current pkt
if ACK/NAK corrupted
› sender adds sequence number
to each pkt
› receiver discards (does not
deliver up) duplicate pkt
stop and wait
sender sends one packet,
then waits for receiver
response
rdt2.0 has a fatal flaw!
56
Wait for
call 0 from
above
sndpkt = make_pkt(0, data, checksum)
udt_send(sndpkt)
rdt_send(data)
Wait for
ACK or
NAK 0 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)
Wait for
call 1 from
above
Wait for
ACK or
NAK 1
L
L
rdt2.1: sender, handles garbled ACK/NAKs
57
Wait for
0 from
below
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)
Wait for
1 from
below
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
58
sender:
› seq # added to pkt
› two seq. #’s (0,1) will
suffice.
›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 #
rdt2.1: discussion
59
› 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
› “unexpected” ACK at sender results in same action as
NAK: retransmit current pkt
rdt2.2: a NAK-free protocol
60
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) ||
isACK(rcvpkt,1) )
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
&& isACK(rcvpkt,0)
Wait for
ACK
0
sender FSM
fragment
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)
&& has_seq1(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
sndpkt = make_pkt(ACK1, chksum)
udt_send(sndpkt)
Wait for
0 from
below
rdt_rcv(rcvpkt) &&
(corrupt(rcvpkt) ||
has_seq1(rcvpkt))
udt_send(sndpkt)
receiver FSM
fragment
L
rdt2.2: sender, receiver fragments
61
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
rdt3.0: channels with errors and loss
62
sndpkt = make_pkt(0, data, checksum)
udt_send(sndpkt)
start_timer
rdt_send(data)
Wait
for
ACK0
rdt_rcv(rcvpkt) &&
( corrupt(rcvpkt) ||
isACK(rcvpkt,1) )
Wait for
call 1 from
above
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)
Wait for
call 0from
above
Wait
for
ACK1
L
rdt_rcv(rcvpkt)
L
L
L
rdt3.0 sender
63
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
64
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
rcv ack1
(do nothing)
ack1
send pkt0
rcv ack1 pkt0
rcv pkt0
send ack0
rdt3.0 in action
65
ack0
› 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
U
sender =
.008
30.008
= 0.00027
L / R
RTT + L / R
=
§ if RTT=30 msec, 1KB pkt every 30 msec: 33kB/sec thruput
over 1 Gbps link
v network protocol limits use of physical resources!
Dtrans =
L
R
8000 bits
109 bits/sec= = 8 microsecs
Performance of rdt3.0
66
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 =
.008
30.008
= 0.00027
L / R
RTT + L / R
=
rdt3.0: stop-and-wait operation
67
pipelining: sender allows multiple, “in-flight”, yet-to-
be-acknowledged 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
Pipelined protocols
68
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
=
Pipelining: increased utilization
69
Go-back-N:
› sender can have up to N
unacked packets in
pipeline
› receiver only sends
cumulative ack
– does not ack packet if there
is a gap
› sender has timer for
oldest unacked packet
– when timer expires,
retransmit all unacked
packets
Selective Repeat:
› sender can have up to N
unacked packets in pipeline
› receiver sends individual ack
for each packet
› sender maintains timer for
each unacked packet
– when timer expires, retransmit
only that unacked packet
Pipelined protocols: overview
70
› “window” of up to N, consecutive unacked 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
Go-Back-N: sender
71
› “window” of up to N, consecutive unacked 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
Go-Back-N: sender
72
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)
L
GBN: sender extended FSM
73
ACK-only: always send ACK for correctly-received pkt with
highest in-order seq #
- may generate duplicate ACKs
- need only remember expectedseqnum
› 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
L
GBN: receiver extended FSM
74
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
GBN in action
75
› receiver individually acknowledges all correctly
received pkts
- buffers pkts, as needed, for eventual in-order delivery to
upper layer
› sender only resends pkts for which ACK not
received
- sender timer for each unACKed pkt
› sender window
› receiver window
Selective repeat
76
Selective repeat: sender, receiver windows
77
data from above:
› if next available seq # in
window, send pkt
timeout(n):
› resend pkt n, restart timer
ACK(n) in [sendbase,sendbase+N-1]:
› mark pkt n as received
› if n is 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
Selective repeat
78
3-79
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
record ack4 arrived
record ack5 arrived
Q: what happens when ack2 arrives?
Selective repeat in action
80
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 9