3rd Edition: Chapter 3
Advanced Network Technologies
Application layer
Transport layer
School of Computer Science
Dr. | Lecturer
1
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
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 capacity
u2
d2
u1
d1
di
ui
Let assume that U1 = … = UN = Us, then it is NF/Us.
But if they are different, we have: Max(NF/Us, F/U_1, …, F/U_N)
4
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}
client: each client must download file copy
dmin = min client download rate
(worst case) client download time: F/dmin
us
network
di
ui
F
5
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)}
client: each client must download file copy
client download time: F/dmin
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
6
client upload rate = u, F/u = 1 hour, us = 10u, dmin ≥ us
Client-server vs. p2p
7
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
37min
Source for the Internet traffic: http://www.scribd.com/doc/94722096/Sandvine-Global-Internet-Phenomena-Report-1H-2012
8
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
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
10
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
Choked: stopped
11
(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
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?
19
1
3
4
5
8
10
12
15
Circular DHT
each peer only aware of immediate successor.
20
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.
22
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
20min
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
20min
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
Demux = demultiplex
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
20min
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
P2
P1
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 #
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
Java DatagramSocket(port) takes the port to bind to on the local host machine.
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
P6
P5
P3
source IP,port: C,5775
dest IP,port: B,80
source IP,port: C,9157
dest IP,port: B,80
three 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
20min
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
UDP use:
streaming multimedia apps (loss tolerant, rate sensitive)
DNS
reliable transfer over UDP:
add reliability at application layer
application-specific error recovery!
UDP: User Datagram Protocol [RFC 768]
40
No frills, bare bones: pas de cartilages, a nu.
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
43
Kurose and Ross forgot to say anything about wrapping the carry and adding it to low order bit
Principles of Reliable Data Transfer
44
20min
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
Network
layer
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 below
sender
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
Pkt packet
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
Garble: deformer
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
if RTT=30 msec, 1KB pkt every 30 msec: 33kB/sec thruput over 1 Gbps link
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
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!
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
ACK(n): ACKs all pkts up to, including seq # n – “cumulative ACK”
may receive duplicate ACKs (see receiver)
timer for oldest in-flight pkt
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
ACK(n): ACKs all pkts up to, including seq # n – “cumulative ACK”
may receive duplicate ACKs (see receiver)
timer for oldest in-flight pkt
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 If (nextseqnum < base+N) it means we can still send, otherwise we have send N messages (not yet acknowledged). If base == nextseqnum, it means that we have not sent anything yet, so let’s start timer. If timer expires, resend N messages not yet acknowledged. If base == nextseqnum when we receive, it means everything has been acknowledged. 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 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 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] send ACK(n) out-of-order: buffer in-order: deliver (also deliver buffered, in-order pkts), advance window to next not-yet-received pkt pkt n in [rcvbase-N,rcvbase-1] ACK(n) otherwise: ignore receiver Selective repeat 78 The receiver still sends ack upon reception of an old packet already delivered. 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 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 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 Mark 2 as received, advance window base to 3, send pkt6 80 0 0.5 1 1.5 2 2.5 3 3.5 05101520253035 N Minimum Distribution Time P2P Client-Server Chart1 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 P2P Client-Server N Minimum Distribution Time 0.1 0.1 0.1666666667 0.2 0.2307692308 0.3 0.2857142857 0.4 0.3333333333 0.5 0.375 0.6 0.4117647059 0.7 0.4444444444 0.8 0.4736842105 0.9 0.5 1 0.5238095238 1.1 0.5454545455 1.2 0.5652173913 1.3 0.5833333333 1.4 0.6 1.5 0.6153846154 1.6 0.6296296296 1.7 0.6428571429 1.8 0.6551724138 1.9 0.6666666667 2 0.6774193548 2.1 0.6875 2.2 0.696969697 2.3 0.7058823529 2.4 0.7142857143 2.5 0.7222222222 2.6 0.7297297297 2.7 0.7368421053 2.8 0.7435897436 2.9 0.75 3 0.756097561 3.1 0.7619047619 3.2 Sheet1 L P2P Client-Server ratio factor 1 0.1 0.1 1 10 2 0.1666666667 0.2 3 0.2307692308 0.3 4 0.2857142857 0.4 5 0.3333333333 0.5 6 0.375 0.6 7 0.4117647059 0.7 8 0.4444444444 0.8 9 0.4736842105 0.9 10 0.5 1 11 0.5238095238 1.1 12 0.5454545455 1.2 13 0.5652173913 1.3 14 0.5833333333 1.4 15 0.6 1.5 16 0.6153846154 1.6 17 0.6296296296 1.7 18 0.6428571429 1.8 19 0.6551724138 1.9 20 0.6666666667 2 21 0.6774193548 2.1 22 0.6875 2.2 23 0.696969697 2.3 24 0.7058823529 2.4 25 0.7142857143 2.5 26 0.7222222222 2.6 27 0.7297297297 2.7 28 0.7368421053 2.8 29 0.7435897436 2.9 30 0.75 3 31 0.756097561 3.1 32 0.7619047619 3.2 33 0.7674418605 3.3 34 0.7727272727 3.4 35 0.7777777778 3.5 36 0.7826086957 3.6 37 0.7872340426 3.7 38 0.7916666667 3.8 39 0.7959183673 3.9 40 0.8 4 41 0.8039215686 4.1 42 0.8076923077 4.2 43 0.8113207547 4.3 44 0.8148148148 4.4 45 0.8181818182 4.5 46 0.8214285714 4.6 47 0.8245614035 4.7 48 0.8275862069 4.8 49 0.8305084746 4.9 Sheet1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 P2P Client-Server N Minimum Distribution Time 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Sheet2 Sheet3 U sender = . 008 30.008 = 0.00027 L / R RTT + L / R = 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 RTT + L / R L / R = = 0.00027 U sender = . 0024 30.008 = 0.00081 3 L / R RTT + L / R = U sender = .0024 30.008 RTT + L / R 3L / R = = 0.00081 /docProps/thumbnail.jpeg