CS计算机代考程序代写 dns database Week 4-transport layer

Week 4-transport layer

Advanced Network Technologies
Application layer
Transport layer

School of Computer Science
Dr. Wei Bao| Lecturer

Peer-to-Peer

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)

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

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

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

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

network
di

› 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

network
di

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.5

1.5

2.5

3.5

0 5 10 15 20 25 30 35

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

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)

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

› 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”)

› 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

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

Distributed Hash Table

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

Distributed hash table (DHT)

›Assign the keys
›Lookup the keys

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

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

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

Lookup the keys

› Given a key, find the host that owns the key

Goal: to provide a distributed lookup service returning the host
that owns the key

a
k?

k? k?

k!
k?

8
10

Circular DHT

› each peer only aware of immediate successor.

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

Define closest
as closest
successor

Circular DHT (con’t)

key 1110 is
stored at node
1111

Circular DHT (con’t)

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

8
10

Who’s responsible
for key 1110 (14) ?

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

Outline

› Transport-layer services

› Multiplexing/demultiplexing

› Connectionless transport (UDP)

› Principles of reliable data transfer

› TCP protocol

Transport Services

› 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

›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

› 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

network
data link
physical

logical end-end transport

Internet transport-layer protocols

Transport Services

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

transport

application

physical
link

network

Multiplexing/demultiplexing

› 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

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

› Receiver › Sender

DatagramSocket serverSocket =
new DatagramSocket(6428);

transport

application

physical
link

network

P3
transport

application

physical
link

network

transport

application

physical
link

network

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

›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

transport

application

physical
link

network

P1
transport

application

physical
link

transport

application

physical
link

network

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

transport

application

physical
link

network

P1
transport

application

physical
link

transport

application

physical
link

network

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

source IP,port: C,5775
dest IP,port: B,80

source IP,port: C,9157
dest IP,port: B,80

threaded server

Connection-oriented demux: example

Connectionless Transport UDP

› “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]

› 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

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

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

carryout

Principles of Reliable Data Transfer

› 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

› 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

› 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

Ne
tw

or
k

la
ye

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

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

› 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

› 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

› 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

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)

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)

rdt2.0: operation with no errors

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)

rdt2.0: error scenario

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!

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

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

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

› 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

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

rdt2.2: sender, receiver fragments

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

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

rdt3.0 sender

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

pkt1

ack1

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

ack1

ack0

(b) packet loss

pkt1
X

loss

pkt1
timeout

resend pkt1

rdt3.0 in action

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

ack1

ack0

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

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

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

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

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

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

› “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

› “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

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

Related Posts