Transcript End to End Protocols

End to End
Protocols
1
End to End Protocols
 Last week:
basic protocols
 Stop & wait (Correct but low performance)

 Today:
 Window based protocol.
• Go Back N
• Selective Repeat
TCP protocol.
 UDP protocol.

 Next week: Flow control & congestion control
2
rdt3.0: Stop-and-Wait Operation
 rdt3.0 works, but performance stinks
 example: 1 Gbps link, 15 ms e-e prop. delay, 1KB packet:
sender
receiver
first packet bit transmitted, t = 0
last packet bit transmitted, t = L / R
first packet bit arrives
RTT
last packet bit arrives, send ACK
ACK arrives, send next
packet, t = RTT + L / R
U
sender
=
L/R
RTT + L / R
=
.008
30.008
= 0.027%
%microse
conds
3
Last week: Performance of rdt3.0
 rdt3.0 works, but performance stinks
 example: 1 Gbps link, 15 ms e-e prop. delay, 1KB packet:
Ttransmit =
8kb/pkt
= 8 microsec
10**9 b/sec
8 microsec
fraction of time
=
= 0.00015
Utilization = U = sender busy sending
30.016 msec


1KB pkt every 30 msec -> 33kB/sec thruput over 1 Gbps link
transport protocol limits use of physical resources!
4
Pipelined protocols
Pipelining: sender allows multiple, “in-flight”, yet-tobe-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
5
Go Back N (GBN)
6
Go-Back-N
Sender:
 k-bit seq # in pkt header

Unbounded seq. num.
 “window” of up to N, consecutive unack’ed pkts allowed
 ACK(n): ACKs all pkts up to, including seq # n - “cumulative ACK”
may deceive duplicate ACKs (see receiver)
 timer for the packet at base
 timeout(n): retransmit pkt n and all higher seq # pkts in window

7
GBN: sender extended FSM
/*for the packet at the new base*/
8
GBN: receiver extended FSM
expectedseqnum=expectedseqnum+1
receiver simple:
 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!
 ACK pkt with highest in-order seq #
9
GBN in
action
window
size = 4
10
GBN: Correctness
 Claim I (safety):
The receiver outputs the data in the correct order
 Proof: unbounded seq. num. QED

 Claim I (seqnum):
 In the receiver:
• Value of expectedseqnum only increases

In the sender:
• The received ACK seqnum only increases.

This is why the sender does not need to test
getacknum(rcvpkt) when updating variable base!
11
GBN: correctness - liveness
 Let:

base=k; expecetdseqnum=m; nextseqnum=n;
 Observation: k ≤ m ≤ n
 Claim (Liveness):
If k<m then eventually base ≥ m
 If (k=m and m<n) then eventually:

• receiver outputs data item m
• Expectedseqnum ≥ m+1
12
GBN - Bounding seq. num.
Claim: After receiving Data k no Data i<k-N is received.
After receiving ACK k no ACK i<k is received.
Ack i<k
Clearing a FIFO channel:
Seq num only
Ack k
Ack i<k
increases
impossible
Data i<k-N Data k
impossible
Data i<k-N
Not in window with k
Corollary: Sufficient to use N+1 seq. num.
13
Selective Repeat
14
Selective Repeat
 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
 N consecutive seq #’s
 again limits seq #s of sent, unACKed pkts
 sender timer for each unACKed pkt
15
Selective repeat: sender, receiver windows
16
Selective repeat
sender
data from above :
receiver
pkt n in [rcvbase, rcvbase+N-1]
 if next available seq # in
 send ACK(n)
timeout(n):
 in-order: deliver (also
window, send pkt
 resend pkt n, restart timer
ACK(n) in [sendbase,sendbase+N]:
 mark pkt n as received
 if n smallest unACKed pkt,
advance window base to
next unACKed seq #
 out-of-order: buffer
deliver buffered, in-order
pkts), advance window to
next not-yet-received pkt
pkt n in
[rcvbase-N,rcvbase-1]
 ACK(n)
otherwise:
 ignore
17
Selective repeat in action
18
Selective Repeat in Action
19 19
Selective repeat in action
20
Selective Repeat - Correctness
 Infinite seq. Num.
Safety: immediate from the seq. Num.
 Liveness: Eventually data and ACKs get through.

 Finite Seq. Num.
 Idea: Re-use seq. Num.
 Use less bits to encode them.
 Number of seq. Num.:
 At
least N.
 Needs more!
21
Selective repeat:
dilemma
Example:
 seq #’s: 0, 1, 2, 3
 window size=3
 receiver sees no
difference in two
scenarios!
 Incorrectly


Passes duplicate data
as new in (a) or
Discards in (b)
Q: what relationship
between seq # size
and window size?
22
Choosing the window size
 Small window size:

idle link (under-utilization).
 Large window size:
 Buffer space
 Delay after loss
 Ideal window size (assuming very low loss)
 RTT =Round trip time
 C = link capacity
 window size = RTT * C
 What happens with no loss?
23
End to End
Protocols:
Multiplexing &
Demultiplexing
24
Multiplexing/demultiplexing
Recall: segment - unit of data
exchanged between
transport layer entities
 aka TPDU: transport
protocol data unit
application-layer
data
segment
header
segment
Ht M
Hn segment
P1
M
application
transport
network
P3
Demultiplexing: delivering
received segments to
correct app layer processes
receiver
M
M
application
transport
network
P4
M
P2
application
transport
network
25
Multiplexing/demultiplexing
Multiplexing:
gathering data from multiple
app processes, enveloping
data with header (later used
for demultiplexing)
multiplexing/demultiplexing:
 based on sender, receiver
port numbers, IP addresses
 source, dest port #s in
each segment
 recall: well-known port
numbers for specific
applications
 Using IP addresses –
layer violation.
32 bits
source port #
dest port #
other header fields
application
data
(message)
TCP/UDP segment format
26
Multiplexing/demultiplexing: examples
host A
source port: x
dest. port: 23
server B
source port:23
dest. port: x
Source IP: C
Dest IP: B
source port: y
dest. port: 80
port use: simple telnet app
Web client
host A
Web client
host C
Source IP: A
Dest IP: B
source port: x
dest. port: 80
Source IP: C
Dest IP: B
source port: x
dest. port: 80
Web
server B
port use: Web server
27
UDP Protocol
28
UDP: User Datagram Protocol [RFC 768]
 “no frills,” “bare bones”
Internet transport
protocol
 “best effort” service, UDP
segments may be:
 lost
 delivered out of order
to application
 connectionless:
 no handshaking between
UDP sender, receiver
 each UDP segment
handled independently
of others
Why is there a UDP?
 no connection
establishment (which can
add delay)
 simple: no connection state
at sender, receiver
 small segment header
 no congestion control: UDP
can blast away as fast as
desired
29
UDP: more
 often used for streaming
multimedia apps
 loss tolerant
 rate sensitive
 other UDP uses
(why?):
Length, in
bytes of UDP
segment,
including
header
DNS
 SNMP
 reliable transfer over UDP:
add reliability at
application layer
 application-specific
error recover!

32 bits
source port #
dest port #
length
checksum
Application
data
(message)
UDP segment format
30
UDP checksum
Goal: detect “errors” (e.g., flipped bits) in transmitted
segment
Sender:
 treat segment contents
as sequence of 16-bit
integers
 checksum: addition (1’s
complement sum) of
segment contents
 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.
31
TCP Protocol
32
TCP: Overview
 point-to-point:
 one sender, one receiver
 reliable, in-order byte
steam:

no “message boundaries”
 pipelined:
 TCP congestion and flow
control set window size
 send & receive buffers
socket
door
application
writes data
application
reads data
TCP
send buffer
TCP
receive buffer
RFCs: 793, 1122, 1323, 2018, 2581
 full duplex data:
 bi-directional data flow
in same connection
 MSS: maximum segment
size
 connection-oriented:
 handshaking (exchange
of control msgs) init’s
sender, receiver state
before data exchange
 flow controlled:
 sender will not
socket
door
overwhelm receiver
segment
33
TCP segment structure
32 bits
URG: urgent data
(generally not used)
ACK: ACK #
valid
PSH: push data now
(generally not used)
RST, SYN, FIN:
connection estab
(setup, teardown
commands)
Internet
checksum
(as in UDP)
source port #
dest port #
sequence number
acknowledgement number
head not
UA P R S F
len used
checksum
rcvr window size
ptr urgent data
Options (variable length)
counting
by bytes
of data
(not segments!)
# bytes
rcvr willing
to accept
application
data
(variable length)
34
Connection Management: Objective
 Agree on initial sequence numbers

a sender will not reuse a seq# before it is sure
that all packets with the seq# are purged from
the network
• the network guarantees that a packet too old will be
purged from the network: network bounds the life
time of each packet

To avoid waiting for the seq# to start a
session, use a larger seq# space
• needs connection setup so that the sender tells the
receiver initial seq#
 Agree on other initial parameters
35 35
TCP seq. #’s and ACKs
Seq. #’s:
 byte stream
“number” of first
byte in segment’s
data
ACKs:
 seq # of next byte
expected from
other side
 cumulative ACK
Q: how receiver handles
out-of-order segments
 A: TCP spec doesn’t
say - up to
implementor
Host A
User
types
‘C’
Host B
host ACKs
receipt of
‘C’, echoes
back ‘C’
host ACKs
receipt
of echoed
‘C’
simple telnet scenario
time
36
Three Way Handshake (TWH) [Tomlinson 1975]
Host A
Host B
accept?
accept data only after
verified x is the init. seq
SYN: indicates connection setup
37 37
Scenarios with Duplicate Request
Host A
Host B
accept?
no such
request
reject
38 38
Three Way Handshake (TWH) [Tomlinson 1975]
 To ensure that the other side does want to send a request
Host A
Host B
Host A
Host B
accept?
no such
request
reject
39 39
Connection Close
 Objective of closure
handshake:

each side can release
resource and remove
state about the
connection
client
server
init. close
release
resource?
close
close
release
resource?
release
resource?
40 40
TCP: reliable data transfer
event: data received
from application above
create, send segment
wait
wait
for
for
event
event
simplified sender, assuming
•one way data transfer
•no flow, congestion control
event: timer timeout for
segment with seq # y
retransmit segment
event: ACK received,
with ACK # y
ACK processing
41
TCP:
reliable
data
transfer
Simplified
TCP
sender
00 sendbase = initial_sequence number
01 nextseqnum = initial_sequence number
02
03 loop (forever) {
04
switch(event)
05
event: data received from application above
06
create TCP segment with sequence number nextseqnum
07
start timer for segment nextseqnum
08
pass segment to IP
09
nextseqnum = nextseqnum + length(data)
10
event: timer timeout for segment with sequence number y
11
retransmit segment with sequence number y
12
compue new timeout interval for segment y
13
restart timer for sequence number y
14
event: ACK received, with ACK field value of y
15
if (y > sendbase) { /* cumulative ACK of all data up to y */
16
cancel all timers for segments with sequence numbers < y
17
sendbase = y
18
}
19
else { /* a duplicate ACK for already ACKed segment */
20
increment number of duplicate ACKs received for y
21
if (number of duplicate ACKS received for y == 3) {
22
/* TCP fast retransmit */
23
resend segment with sequence number y
24
restart timer for segment y
25
}
26
} /* end of loop forever */
42
TCP ACK generation
[RFC 1122, RFC 2581]
Event
TCP Receiver action
in-order segment arrival,
no gaps,
everything else already ACKed
delayed ACK. Wait up to 500ms
for next segment. If no next segment,
send ACK
in-order segment arrival,
no gaps,
one delayed ACK pending
immediately send single
cumulative ACK
out-of-order segment arrival
higher-than-expect seq. #
gap detected
send duplicate ACK, indicating seq. #
of next expected byte
arrival of segment that
partially or completely fills gap
immediate ACK if segment starts
at lower end of gap
43
TCP: retransmission scenarios
time
Host A
Host B
X
loss
lost ACK scenario
Host B
Seq=100 timeout
Seq=92 timeout
timeout
Host A
time
premature timeout,
cumulative ACKs
44
TCP Connection Management
Recall: TCP sender, receiver
establish “connection”
before exchanging data
segments
 initialize TCP variables:
 seq. #s
 buffers, flow control
info (e.g. RcvWindow)
 client: connection initiator
 server: contacted by client
Three way handshake:
Step 1: client end system
sends TCP SYN control
segment to server
 specifies initial seq #
Step 2: server end system
receives SYN, replies with
SYN-ACK control segment



ACKs received SYN
allocates buffers
specifies server->
receiver initial seq. #
45
TCP Connection Management (cont.)
Step 3: client receives SYN-
client
server
ACK and replies with ACK
(possibly with data).
SYN_sent
SYN_rcvd
ESTABLISHED
ESTABLISHED
46
TCP Connection Management (cont.)
Closing a connection:
client closes socket:
clientSocket.close();
client
close
Step 1: client end system
close
FIN, replies with ACK.
Closes connection, sends
FIN.
timed wait
sends TCP FIN control
segment to server
Step 2: server receives
server
closed
47
TCP Connection Management (cont.)
Step 3: client receives FIN,
replies with ACK.

client
server
closing
Enters “timed wait” will respond with ACK
to received FINs
closing
Step 4: server, receives
Note: with small
modification, can handle
simultaneous FINs.
timed wait
ACK. Connection closed.
closed
closed
48
TCP Connection Management (cont)
TCP server
lifecycle
TCP client
lifecycle
49
TCP
state
transition
diagram
50
Simultaneous open
SYN
Seq=100
SYN-ACK
Seq=101
Ack=330
SYN
Seq=330
SYN_SENT
SYN-ACK
Seq=331
Ack=100
SYN_RCVD
ACK+Data
ESTABLISHED
ACK+Data
51