Transcript 3rd Edition: Chapter 3 - Wayne State University

ECE 5650
TL: Reliable Data Transfer
Transport Layer
3-1
Recap: transport-layer protocols
 IP service model


Host-to-host best-effort delivery
service, datagram
Unreliable serivce
application
transport
network
data link
physical
 UDP: unreliable, unordered delivery


Proc to proc segment delivery: nofrills extension of “best-effort” IP
(Multiplexing /demultiplexing)
Error checking
 TCP:


reliable, in-order delivery: flow
control, sequence number, ack, timer,
etc
congestion control to prevent TCP
connection from swamping the links
and switches
 services not available in either TCP
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
application
transport
network
data link
physical
or UDP:


delay guarantees
bandwidth guarantees
Transport Layer
3-2
Recap: Multiplexing/demultiplexing (encode/decode)
Demultiplexing at rcv host:
Multiplexing at send host:
The job of delivering received
transport-layer segments to correct socket.
The job of gathering data from different
sockets, enveloping data with header
(later used for demultiplexing) and passing
the data to the network layer.
= socket
application
transport
network
link
Each socket has a unique identifier (a set of
fields in each segment)
= process
P3
P1
P1
application
transport
network
P2
P4
application
transport
network
link
link
physical
host 1
physical
host 2
physical
host 3
Transport Layer
3-3
Recap: Connectionless demux
DatagramSocket serverSocket = new DatagramSocket(6428);
P2
port 9157
One Server
Socket
P3
DP: 6428
port 6428
SP: 6428
SP: 6428
DP: 9157
DP: 5775
SP: 9157
client
IP: A
P1
P1
port 5775
SP: 5775
server
IP: C
DP: 6428
Client
IP:B
SP = Source Port, DP = Destination Port
Source Packet provides “return address” that destination host can use to reply
Transport Layer
3-4
Recap: Conn-oriented demux
P1
Three Server
Sockets
P4
P5
P2
P6
P1P3
SP: 5775
DP: 80
S-IP: B
D-IP:C
SP: 9157
client
IP: A
DP: 80
S-IP: A
D-IP:C
SP: 9157
server
IP: C
DP: 80
S-IP: B
D-IP:C
Client
IP:B
SP = Source Port, DP = Destination Port, S-IP = Source IP, D-IP = Destination IP
Transport Layer
3-5
Recap: UDP Segment Structure
 UDP segment has an 8 byte
header.
 Length of UDP segment, in
bytes, including header.
 Minimum length is 8 and
maximum is 64k.
32 bits
source port #
dest port #
length (16-bit)
checksum (16-bit)
Application
data
(message)
UDP segment format
Transport Layer
3-6
Recap: Internet Checksum: Sender Example
 Note

When adding numbers, a carryout from the most
significant bit needs to be added to the result
 Segment has two 16-bit integers and the checksum
 Add the two 16-bit integers
 compute the checksum by taking the 1’s complement of the
sum.
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
wraparound:
add carry to LSB
1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1
sum 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0
checksum 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1
Transport Layer
3-7
TL outline
 3.1 Transport-layer
services
 3.2 Multiplexing and
demultiplexing
 3.3 Connectionless
transport: UDP
 3.4 Principles of
reliable data transfer
 3.5 Connection-oriented
transport: TCP




segment structure
reliable data transfer
flow control
connection management
 3.6 Principles of
congestion control
 3.7 TCP congestion
control
Transport Layer
3-8
Principles of Reliable data transfer
 Reliable transfer: no data corrupted or loss, and in-order delivery


important in app., transport, link layers
top-10 list of important networking topics!
 characteristics of unreliable channel will determine
complexity of reliable data transfer protocol (rdt)
Transport Layer
3-9
Reliable data transfer: getting started
rdt_send(): called from above,
(e.g., by app.). Passed data to
deliver to receiver upper layer
send
side
udt_send(): called by rdt,
to transfer packet over
unreliable channel to receiver
deliver_data(): called by
rdt to deliver data to upper
receive
side
rdt_rcv(): called when packet
arrives on rcv-side of channel
Transport Layer 3-10
Reliable data transfer: getting started
We’ll:
 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
event causing state transition (when..happens)
actions taken on state transition (then this happens)
state: when in this
“state” next state
uniquely determined
by next event
state
1
Symbol L above or below the line denote
the lack of an action or event
event
actions
state
2
Transport Layer
3-11
Finite State Machine
 FSM is a model of behavior
composed of states, transitions
and events



State stores info about the past,
reflecting the system start to the
present moment
Transition indicates a state
change, triggered by an event
Events: activity to be performed
at a given moment: entry, exit,
input
 FSM often represented using a
state diagram
Transport Layer 3-12
Rdt1.0: reliable transfer over a reliable channel
 underlying channel perfectly reliable
 no bit errors
 no loss of packets
 separate FSMs for sender, receiver:
 sender sends data into underlying channel
 receiver read data from underlying channel
Wait for
call from
above
rdt_send(data)
packet = make_pkt(data)
udt_send(packet)
sender
Wait for
call from
below
rdt_rcv(packet)
extract (packet,data)
deliver_data(data)
receiver
Transport Layer 3-13
Rdt2.0: channel with bit errors but does
not lose packets
 underlying channel may flip bits in packet
 Solution: checksum to detect bit errors

the question: how to recover from errors:

acknowledgements (ACKs): receiver explicitly tells sender

negative acknowledgements (NAKs): receiver explicitly

that pkt received “OK”
tells sender that pkt had errors “please repeat that”.
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
Transport Layer 3-14
Automatic Repeat reQuest protocols (ARQ)
 Protocols based on ACKs and NAKs.
 ARQ Protocols have 3 capabilities:
 Error detection of bit errors which requires additional
bits added to the transmitted packet.
 Receiver feedback: ACK and NAK bit (1=ACK, 0=NAK) to
be added to the transmitted packet.
 Retransmission: a packet with errors will be
retrasmitted.
Transport Layer 3-15
rdt2.0: FSM specification
rdt_send(data)
sndpkt = make_pkt(data, checksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
isNAK(rcvpkt)
Wait for
Wait for
call from
ACK or
udt_send(sndpkt)
above
NAK
rdt_rcv(rcvpkt) && isACK(rcvpkt)
L
sender
Sender can not send another packet until receiver
sends back ACK/NAK. (send-and-wait protocols)
receiver
rdt_rcv(rcvpkt) &&
corrupt(rcvpkt)
udt_send(NAK)
Wait for
call from
below
rdt_rcv(rcvpkt) &&
notcorrupt(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
udt_send(ACK)
Transport Layer 3-16
rdt2.0: operation with no errors
rdt_send(data)
snkpkt = make_pkt(data, checksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
isNAK(rcvpkt)
Wait for
Wait for
call from
ACK or
udt_send(sndpkt)
above
NAK
rdt_rcv(rcvpkt) && isACK(rcvpkt)
L
rdt_rcv(rcvpkt) &&
corrupt(rcvpkt)
udt_send(NAK)
Wait for
call from
below
rdt_rcv(rcvpkt) &&
notcorrupt(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
udt_send(ACK)
Transport Layer 3-17
rdt2.0: error scenario
rdt_send(data)
snkpkt = make_pkt(data, checksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
isNAK(rcvpkt)
Wait for
Wait for
call from
ACK or
udt_send(sndpkt)
above
NAK
rdt_rcv(rcvpkt) && isACK(rcvpkt)
L
rdt_rcv(rcvpkt) &&
corrupt(rcvpkt)
udt_send(NAK)
Wait for
call from
below
rdt_rcv(rcvpkt) &&
notcorrupt(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
udt_send(ACK)
Transport Layer 3-18
rdt2.0 has a fatal flaw!
What happens if
ACK/NAK corrupted?
 sender doesn’t know what
happened at receiver!
 can’t just retransmit:
possible duplicate
Handling duplicates:
 sender retransmits current
packet if ACK/NAK
garbled/corrupt
 sender adds sequence number to
each packet, 1-bit that changes
if a new packet is sent
 receiver discards (doesn’t
deliver up) duplicate pkt
 ACK/NAK packets do not need
the sequence number of the
packet acknowledged since
sender knows it is for the last
packet (we assume no packet
loss)
Transport Layer 3-19
rdt2.1: sender, handles garbled ACK/NAKs
rdt_send(data)
sndpkt = make_pkt(0, data, checksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
( corrupt(rcvpkt) ||
Wait
for
Wait for
isNAK(rcvpkt) )
ACK or
call 0 from
udt_send(sndpkt)
NAK 0
above
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
&& isACK(rcvpkt)
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
&& isACK(rcvpkt)
L
rdt_rcv(rcvpkt) &&
( corrupt(rcvpkt) ||
isNAK(rcvpkt) )
udt_send(sndpkt)
L
Wait for
ACK or
NAK 1
Wait for
call 1 from
above
rdt_send(data)
sndpkt = make_pkt(1, data, checksum)
udt_send(sndpkt)
Transport Layer 3-20
rdt2.1: receiver, handles garbled ACK/NAKs
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)
&& has_seq0(rcvpkt)
rdt_rcv(rcvpkt) && (corrupt(rcvpkt))
extract(rcvpkt,data)
deliver_data(data)
sndpkt = make_pkt(ACK, chksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) && (corrupt(rcvpkt)
sndpkt = make_pkt(NAK, chksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
not corrupt(rcvpkt) &&
has_seq1(rcvpkt)
sndpkt = make_pkt(ACK, chksum)
udt_send(sndpkt)
sndpkt = make_pkt(NAK, chksum)
udt_send(sndpkt)
Wait for
0 from
below
Wait for
1 from
below
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)
&& has_seq1(rcvpkt)
rdt_rcv(rcvpkt) &&
not corrupt(rcvpkt) &&
has_seq0(rcvpkt)
sndpkt = make_pkt(ACK, chksum)
udt_send(sndpkt)
extract(rcvpkt,data)
deliver_data(data)
sndpkt = make_pkt(ACK, chksum)
udt_send(sndpkt)
Transport Layer 3-21
rdt2.1: discussion
Sender:
 seq # added to pkt
 two seq. #’s (0,1) will
suffice. Why?
 must check if received
ACK/NAK corrupted
 twice as many states

state must “remember”
whether “current” pkt
has 0 or 1 seq. #
Receiver:
 must check if received
packet is duplicate

state indicates whether
0 or 1 is expected pkt
seq #
 note: receiver can
not
know if its last
ACK/NAK received OK
at sender
Transport Layer 3-22
rdt2.2: a NAK-free protocol
 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
 duplicate ACK at sender results in same action as
NAK: retransmit current pkt
Transport Layer 3-23
rdt2.2: sender, receiver fragments
rdt_send(data)
sndpkt = make_pkt(0, data, checksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
( corrupt(rcvpkt) ||
Wait for
Wait for
isACK(rcvpkt,1) )
ACK
call 0 from
0
udt_send(sndpkt)
above
sender FSM
fragment
rdt_rcv(rcvpkt) &&
(corrupt(rcvpkt) ||
has_seq1(rcvpkt))
udt_send(sndpkt)
Wait for
0 from
below
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
&& isACK(rcvpkt,0)
receiver FSM
fragment
L
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)
&& has_seq1(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
sndpkt = make_pkt(ACK1, chksum)
udt_send(sndpkt)
Transport Layer 3-24
rdt3.0: channels with errors and loss
New assumption:
underlying channel can
also lose packets (data
or ACKs)

checksum, seq. #, ACKs,
retransmissions will be
of help, but not enough
timeout is worst-case time
(taking all types of delays into account)
for packet to reach receiver and
for an ACK to be received
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 use of seq.
#’s already handles this
 receiver must specify seq
# of pkt being ACKed
 requires countdown timer
Transport Layer 3-25
rdt3.0 sender
rdt_send(data)
sndpkt = make_pkt(0, data, checksum)
udt_send(sndpkt)
start_timer
rdt_rcv(rcvpkt)
L
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
&& isACK(rcvpkt,1)
rdt_rcv(rcvpkt) &&
( corrupt(rcvpkt) ||
isACK(rcvpkt,0) )
timeout
udt_send(sndpkt)
start_timer
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
&& isACK(rcvpkt,0)
stop_timer
stop_timer
timeout
udt_send(sndpkt)
start_timer
L
Wait
for
ACK0
Wait for
call 0from
above
L
rdt_rcv(rcvpkt) &&
( corrupt(rcvpkt) ||
isACK(rcvpkt,1) )
Wait
for
ACK1
Wait for
call 1 from
above
rdt_send(data)
rdt_rcv(rcvpkt)
L
sndpkt = make_pkt(1, data, checksum)
udt_send(sndpkt)
start_timer
Transport Layer 3-26
rdt3.0 in action
Alternating-bit protocol because packet sequence numbers
alternate between 0 and 1
Transport Layer 3-27
rdt3.0 in action
Transport Layer 3-28
Performance of rdt3.0
 rdt3.0 works, but performance stinks
 example: 1 Gbps link, 15 ms e-e propagation delay,
1KByte packet:
Ttransmit =
L (packet length in bits)
8kb/pkt
=
= 8 microsec
R (transmission rate, bps)
10^9 b/sec
last bit arrives at receiver at 15 ms + 8 microsec = 15.008 ms
ACK comes back at sender at 15.008 ms + 15 ms = 30.008 ms (assuming ACK size is small)
U
sender
=
L/R
RTT + L / R
=
.008
30.008
= 0.00027
microsec
onds
 U sender: utilization – fraction of time sender busy sending


1 KByte packet every 30 msec -> 267 kbps throughput over 1
Gbps link
network protocol limits use of physical resources!
Transport Layer 3-29
rdt3.0: stop-and-wait operation
sender
receiver
first packet bit transmitted, t = 0
last packet bit transmitted, t = L / R
first packet bit arrives
last packet bit arrives, send ACK
RTT
ACK arrives, send next
packet, t = RTT + L / R
U
sender
=
L/R
RTT + L / R
=
.008
30.008
= 0.00027
microsec
onds
Transport Layer 3-30
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:
selective repeat
go-Back-N,
Transport Layer 3-31
Pipelining: increased utilization
sender
receiver
first packet bit transmitted, t = 0
last bit transmitted, t = L / R
first packet bit arrives
last packet bit arrives, send ACK
last bit of 2nd packet arrives, send ACK
last bit of 3rd packet arrives, send ACK
RTT
ACK arrives, send next
packet, t = RTT + L / R
Increase utilization
by a factor of 3!
U
sender
=
3*L/R
RTT + L / R
=
.024
30.008
= 0.0008
microsecon
ds
Transport Layer 3-32
Go-Back-N (Sliding Window)
Sender:



There is a k-bit sequence # in packet header
“window” of up to N, consecutive unacknowledged sent/can-be-sent packets allowed
window moves by 1 packet at a time when its 1st sent pkt is acknowledged (standard behavior)
window cannot contain acknowledged pkts
Sender must respond to three types of events:
 1- Invocation from above: application layers tries to send a packet, if window is full then
packet is returned otherwise the packet is accepted and sent.
 2- Receipt of an ACK: One ACK(n) received indicates that all pkts up to, including seq # n
have been received - “cumulative ACK”
 may receive duplicate ACKs (when receiver receives out-of-order packets)

3- A timeout event (only cause of retransmission):


timer for each in-flight pkt.
if timeout occurs: retransmit packets that have not been acknowledged.
Transport Layer 3-33
GBN: sender extended FSM
rdt_send(data)
L
base=1
nextseqnum=1
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)
Wait
rdt_rcv(rcvpkt)
&& corrupt(rcvpkt)
timeout
start_timer
udt_send(sndpkt[base])
udt_send(sndpkt[base+1])
…
udt_send(sndpkt[nextseqnum-1])
rdt_rcv(rcvpkt) &&
notcorrupt(rcvpkt)
base = getacknum(rcvpkt)+1
If (base == nextseqnum)
stop_timer
else
start_timer
Transport Layer 3-34
GBN: receiver extended FSM
default
udt_send(sndpkt)
L
Wait
expectedseqnum=1
sndpkt =
make_pkt(expectedseqnum,ACK,chksum)
rdt_rcv(rcvpkt)
&& notcurrupt(rcvpkt)
&& hasseqnum(rcvpkt,expectedseqnum)
extract(rcvpkt,data)
deliver_data(data)
sndpkt = make_pkt(expectedseqnum,ACK,chksum)
udt_send(sndpkt)
expectedseqnum++
ACK-only: always send ACK for correctly-received pkt
with highest in-order seq #

need only remember expectedseqnum
 When out-of-order pkt is received:
 discard (don’t buffer) -> no receiver buffering!
 Re-ACK pkt with highest in-order sequence #
Transport Layer 3-35
GBN in
action
Window-size = 4
Transport Layer 3-36
Notes on GBN:
 Receiver discards out-of-order packets and does not
even buffer them for future use:




Receiver must deliver data in order to application layer
If out-of-order packets are buffered and in-order packets
are lost then a retransmission will re-send the out-of-order
packets.
Simplicity of receiver buffering due to discarding
One disadvantage of not buffering is that a retransmission
could be also lost which would require additional
retransmissions.
 A single packet error can cause GBN sender to
retransmit larger #pkts as the window size
increases.
Transport Layer 3-37
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
Transport Layer 3-38
Selective repeat: sender, receiver windows
Window may contain acknowledged pkts (unlike GBN)
Transport Layer 3-39
Selective repeat
sender events
data from above :
receiver events
pkt n in window
 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 window:
 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 previously
acknowledged
 ACK(n), necessary to move
sender’s window
otherwise:
 ignore
Transport Layer 3-40
Selective repeat in action
Transport Layer 3-41
Selective repeat:
too large window
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)
 To avoid this
condition:the sequence
number space (k) must
be at least twice as
large as the window
size (w) or k >= 2w
Transport Layer 3-42
Reliable Data Transfer Mechanisms
 Checksum: used to detect bit errors in transmitted pkt.
 Timer: used to retransmit a packet when the packet or its ACK was





lost. Duplicate copies of pkt could be received due to premature
timeouts when the packet or its ACK are delayed.
Sequence number: used for sequential numbering of packets sent.
Gaps in seq #s indicate lost/delayed packts while duplicate seq #s
indicate duplicate pkts.
Acknowledgement (ACK): used by receiver to tell sender a packet
(individual ACK) or packets (cumulative) have been received.
Negative Acknowledgement (NAK): used by receiver to tell sender
a packet has not been received correctly.
Pipelining: used to allow sending packets even if prior ones were not
acknowledged and hence increasing the utilization of the sender.
Window: used to restrict sender to send packets with seq #s within
a range (window size) without waiting for an acknowledgement.
Transport Layer 3-43
Summary
 Automatic Repeat reQuest protocols (ARQ)
 Send-and-wait protocols
 The use of Sequences numbers in reliable data
transfers
 Low Utilization of the Send-and-wait protocols
 2 approaches to Pipelined error recovery:


Go-Back-N (GBN)/sliding-window protocol
Selective Repeat (SR)
Transport Layer 3-44