计算机代考程序代写 dns database Java 3rd Edition: Chapter 3

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