Computer Networks

Transport Layer

Mayank Pandey
Objectives
• understand principles behind transport layer
services:
– multiplexing/demultiplexing
– reliable data transfer
– flow control
– congestion control
• learn about transport layer protocols in the Internet:
– UDP: connectionless transport
– TCP: connection-oriented transport
– TCP congestion control

2
Transport services and protocols
applicatio
n
• provide logical communication transport
network
between app processes running data link
physical

lo
on different hosts

gi
ca
• transport protocols run in end

enl
systems

d-
en
d
– send side: breaks app

tr
a
messages into segments,

ns
po
passes to network layer

tr
– rcv side: reassembles applicatio
n
segments into messages, transport
network
passes to app layer data link
physical
• more than one transport protocol
available to apps
– Internet: TCP and UDP

3
Internet transport-layer protocols
• reliable, in-order delivery applicatio
n
transport
(TCP) network
data link
network
– congestion control physical

lo
data link
network

gi
physical
data link
– flow control

ca
physical

l en
– connection setup

d-
en
• unreliable, unordered network

d
data link

tr
a
delivery: UDP
physicalnetwork

ns
data link

po
physical
– no-frills extension of “best-

rt
network
data link
effort” IP physical network
applicatio
n
data link transport
• services not available: physical network
data link
– delay guarantees physical

– bandwidth guarantees

4
 Multiplexing/demultiplexing
Demultiplexing at rcv host: Multiplexing at send host:
delivering received segments gathering data from multiple
to correct socket sockets, enveloping data with
header (later used for
= socket = process demultiplexing)

application P3 P1
P1
application P2 P4 application

transport transport transport

network network network

link link link

physical physical physical

host 2 host 3
host 1
5
How demultiplexing works
• host receives IP datagrams
– each datagram has source IP 32 bits
address, destination IP
source port # dest port #
address
– each datagram carries 1
transport-layer segment other header fields
– each segment has source,
destination port number
• host uses IP addresses & application
port numbers to direct data
(message)
segment to appropriate
socket
TCP/UDP segment format

6
Connectionless demultiplexing
• create sockets with host-local • when host receives UDP
port numbers: segment:
– checks destination port
DatagramSocket mySocket1 = new
DatagramSocket(12534); number in segment
DatagramSocket mySocket2 = new – directs UDP segment to socket
DatagramSocket(12535); with that port number
• when creating datagram to send • IP datagrams with different
into UDP socket, must specify source IP addresses and/or
(dest IP address, dest port number) source port numbers
directed to same socket

7
 Connectionless demux (cont)
DatagramSocket serverSocket = new DatagramSocket(6428);

P2 P3 P1
P1

SP: 6428 SP: 6428

DP: 9157 DP: 5775

SP: 9157 SP: 5775

client DP: 6428 DP: 6428 Client
server
IP: A IP:B
IP: C

SP provides “return address”

8
Connection-oriented demux
• TCP socket identified by 4- • server host may support
tuple: many simultaneous TCP
– source IP address sockets:
– source port number – each socket identified by its
– dest IP address own 4-tuple
– dest port number • web servers have different
• recv host uses all four sockets for each connecting
values to direct segment to client
appropriate socket – non-persistent HTTP will have
different socket for each
request

9
Connection-oriented demux (cont)

P1 P4 P5 P6 P2 P1P3

SP: 5775
DP: 80
S-IP: B
D-IP:C

SP: 9157 SP: 9157

client DP: 80 DP: 80 Client
server
IP: A S-IP: A S-IP: B IP:B
IP: C
D-IP:C D-IP:C

10
Socket programming: System Calls

11
Attention: sendto() recvfrom()

12
UDP: User Datagram Protocol [RFC 768]
• “no frills,” “bare bones”
Internet transport protocol Why is there a UDP?
• “best effort” service, UDP • no connection establishment
segments may be: (which can add delay)
– lost • simple: no connection state at
– delivered out of order to sender, receiver
app • small segment header
• connectionless: • no congestion control: UDP can
– no handshaking between blast away as fast as desired
UDP sender, receiver
– each UDP segment handled
independently of others

13
UDP: more
• often used for streaming
32 bits
multimedia apps
Length, in source port # dest port #
– loss tolerant
– rate sensitive bytes of UDP length checksum
segment,
• other UDP uses including
– DNS header
– SNMP
Application
• reliable transfer over UDP: data
add reliability at (message)
application layer
– application-specific error
recovery! UDP segment format

14
UDP checksum
Goal: detect “errors” (e.g., flipped bits) in transmitted
segment

Sender: Receiver:
• treat segment contents as • compute checksum of received
sequence of 16-bit integers segment
• checksum: addition (1’s • check if computed checksum
complement sum) of segment equals checksum field value:
contents – NO - error detected
• sender puts checksum value – YES - no error detected. But
into UDP checksum field maybe errors nonetheless?
More later ….

15
 Internet Checksum Example
• Note: When adding numbers, a carryout from the most
significant bit needs to be added to the result
• 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

wraparound 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

16
Pseudo Header

• Above is the example of UDP pseudo header

• This is added only for checksum calculation at the sender.
– It is never sent with the packet.
• Receiver also does the same. Includes Pseudo header in
checksum calculation
WHY?
17
Principles of Reliable data transfer
• 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)
18
Principles of Reliable data transfer
• 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)
19
Principles of Reliable data transfer
• 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)
20
 Reliable data transfer: getting started

rdt_send(): called from above, deliver_data(): called

(e.g., by app.). Passed data to by rdt to deliver data to
deliver to receiver upper layer upper

send receive
side side

udt_send(): called by rdt, rdt_rcv(): called when packet

to transfer packet over arrives on rcv-side of channel
unreliable channel to
receiver
21
 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
actions taken on state transition
state: when in this “state”
next state uniquely state state
1 event
determined by next 2
event actions

22
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 rdt_send(data) Wait for rdt_rcv(packet)

call from call from extract (packet,data)
above packet = make_pkt(data) below deliver_data(data)
udt_send(packet)

sender receiver

23
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
How do acknowledgements
– negative humans recover from “errors”
(NAKs): receiver explicitly tells sender
during
that pkt conversation?
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

24
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
– receiver feedback: control msgs (ACK,NAK) rcvr->sender

25
rdt2.0: FSM specification
rdt_send(data)
sndpkt = make_pkt(data, checksum) receiver
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
isNAK(rcvpkt)
Wait for Wait for rdt_rcv(rcvpkt) &&
call from ACK or udt_send(sndpkt) corrupt(rcvpkt)
above NAK
udt_send(NAK)

rdt_rcv(rcvpkt) && isACK(rcvpkt)

Wait for
L
call from
below
sender
rdt_rcv(rcvpkt) &&
notcorrupt(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
udt_send(ACK)

26
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 rdt_rcv(rcvpkt) &&
call from ACK or udt_send(sndpkt) corrupt(rcvpkt)
above NAK
udt_send(NAK)

rdt_rcv(rcvpkt) && isACK(rcvpkt)

Wait for
L call from
below

rdt_rcv(rcvpkt) &&
notcorrupt(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
udt_send(ACK)

27
rdt2.0: error scenario
rdt_send(data)
snkpkt = make_pkt(data, checksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
isNAK(rcvpkt)
Wait for Wait for rdt_rcv(rcvpkt) &&
call from ACK or udt_send(sndpkt) corrupt(rcvpkt)
above NAK
udt_send(NAK)

rdt_rcv(rcvpkt) && isACK(rcvpkt)

Wait for
L call from
below

rdt_rcv(rcvpkt) &&
notcorrupt(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
udt_send(ACK)

28
rdt2.0 has a fatal flaw!
What happens if ACK/NAK corrupted?
Handling
• sender doesn’t know what happened duplicates:
at receiver!
• sender retransmits current pkt
• can’t just retransmit: possible duplicate
if ACK/NAK garbled
• sender adds sequence number
to each pkt
• receiver discards (doesn’t
deliver up) duplicate pkt

stop and wait

Sender sends one packet,
then waits for receiver
response

29
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
ACK or
isNAK(rcvpkt) )
call 0 from
NAK 0 udt_send(sndpkt)
above
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt) rdt_rcv(rcvpkt)
&& isACK(rcvpkt) && notcorrupt(rcvpkt)
&& isACK(rcvpkt)
L
L
Wait for Wait for
ACK or call 1 from
rdt_rcv(rcvpkt) && NAK 1 above
( corrupt(rcvpkt) ||
isNAK(rcvpkt) ) rdt_send(data)

udt_send(sndpkt) sndpkt = make_pkt(1, data, checksum)

udt_send(sndpkt)

30
 rdt2.1: receiver, handles garbled ACK/NAKs
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) && rdt_rcv(rcvpkt) &&
(corrupt(rcvpkt) (corrupt(rcvpkt)
sndpkt = make_pkt(NAK, chksum) sndpkt = make_pkt(NAK, chksum)
udt_send(sndpkt) udt_send(sndpkt)
Wait for Wait for
rdt_rcv(rcvpkt) && 0 from 1 from rdt_rcv(rcvpkt) &&
not corrupt(rcvpkt) && below below not corrupt(rcvpkt) &&
has_seq1(rcvpkt) has_seq0(rcvpkt)
sndpkt = make_pkt(ACK, chksum) sndpkt = make_pkt(ACK, chksum)
udt_send(sndpkt) udt_send(sndpkt)
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)
&& has_seq1(rcvpkt)

extract(rcvpkt,data)
deliver_data(data)
sndpkt = make_pkt(ACK, chksum)
udt_send(sndpkt)
31
rdt2.1: discussion
Receiver:
Sender:
• must
seq # check
addediftoreceived
pkt packet is duplicate
– state
• two seq.indicates
#’s (0,1)whether 0 or 1 isWhy?
will suffice. expected pkt seq #
•• note: receiver
must check can not know
if received ACK/NAKif itscorrupted
last ACK/NAK received OK at
• sender
twice as many states
– state must “remember” whether “current” pkt has 0 or 1 seq. #

32
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

33
 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
ACK isACK(rcvpkt,1) )
call 0 from
above 0 udt_send(sndpkt)
sender FSM
fragment rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt)
rdt_rcv(rcvpkt) && && isACK(rcvpkt,0)
(corrupt(rcvpkt) || L
has_seq1(rcvpkt)) Wait for receiver FSM
0 from
udt_send(sndpkt) below fragment
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)
&& has_seq1(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
sndpkt = make_pkt(ACK1, chksum)
udt_send(sndpkt) 34
rdt3.0: channels with errors and loss

New assumption: underlying channel can also lose packets (data

or ACKs) Approach: sender waits
“reasonable”
– checksum, seq. #, ACKs, retransmissions amount of
will be of help, but not
enough 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

35
rdt3.0 sender
rdt_send(data)
rdt_rcv(rcvpkt) &&
sndpkt = make_pkt(0, data, checksum) ( corrupt(rcvpkt) ||
udt_send(sndpkt) isACK(rcvpkt,1) )
rdt_rcv(rcvpkt) start_timer L
L Wait for Wait
for timeout
call 0from
ACK0 udt_send(sndpkt)
above
start_timer
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt) rdt_rcv(rcvpkt)
&& isACK(rcvpkt,1) && notcorrupt(rcvpkt)
stop_timer && isACK(rcvpkt,0)
stop_timer
Wait Wait for
timeout for call 1 from
udt_send(sndpkt) ACK1 above
start_timer rdt_rcv(rcvpkt)
rdt_send(data) L
rdt_rcv(rcvpkt) &&
sndpkt = make_pkt(1, data, checksum)
( corrupt(rcvpkt) || udt_send(sndpkt)
isACK(rcvpkt,0) ) start_timer
L

36
rdt3.0 in action

37
rdt3.0 in action

38
Performance of rdt3.0

• rdt3.0 works, but performance stinks

• ex: 1 Gbps link, 15 ms prop. delay, 8000 bit packet:

L 8000bits
d trans   9 8 microseconds
R 10 bps
 U sender: utilization – fraction of time sender busy sending

L/ R .008
U = = = 0.00027
sender 30.008
RTT +L / R microsec
onds
 if RTT=30 msec, 1KB pkt every 30 msec -> 33kB/sec thruput over
1 Gbps link
 network protocol limits use of physical resources!

39
 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

RTT last packet bit arrives, send ACK

ACK arrives, send next

packet, t = RTT + L / R

L/ R .008
U = = = 0.00027
sender 30.008
RTT +L / R microsec
onds
40
Pipelined protocols
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
41
 Pipelining: increased utilization
sender receiver
first packet bit transmitted, t = 0
last bit transmitted, t = L / R

first packet bit arrives

RTT last packet bit arrives, send ACK
last bit of 2nd packet arrives, send ACK
last bit of 3rd packet arrives, send ACK
ACK arrives, send next
packet, t = RTT + L / R

Increase utilization
by a factor of 3!
3*L/ R .024
U = = = 0.0008
sender 30.008
RTT +L / R microsecon
ds
42
Pipelined Protocols
Selective Repeat:
Go-back-N: big picture:
big pic
• sender can have up to N unack’ed
unacked packets
packetsininpipeline
pipeline
• rcvr sends
only sends
individual
cumulative
ack foracks
each packet
– doesn’t
• sender ack packettimer
maintains if there’s
for aeach
gap unacked packet
• sender
– whenhas timer
timer forretransmit
expires, oldest unacked packet
only unack’ed packet
– if timer expires, retransmit all unack’ed packets

43
Go-Back-N
Sender:
• k-bit seq # in pkt header
• “window” of up to N, consecutive unack’ed pkts allowed

 ACK(n): ACKs all pkts up to, including seq # n - “cumulative ACK”

 may receive duplicate ACKs (see receiver)
 timer for each in-flight pkt
 timeout(n): retransmit pkt n and all higher seq # pkts in window

44
GBN: sender extended FSM
rdt_send(data)
if (nextseqnum < base+N) {
sndpkt[nextseqnum] = make_pkt(nextseqnum,data,chksum)
udt_send(sndpkt[nextseqnum])
if (base == nextseqnum)
start_timer
nextseqnum++
}
L else
refuse_data(data)
base=1
nextseqnum=1
timeout
start_timer
Wait
udt_send(sndpkt[base])
rdt_rcv(rcvpkt) udt_send(sndpkt[base+1])
&& corrupt(rcvpkt) …
udt_send(sndpkt[nextseqnum-
1])
rdt_rcv(rcvpkt) &&
notcorrupt(rcvpkt)
base = getacknum(rcvpkt)+1
If (base == nextseqnum)
stop_timer
else
start_timer 45
GBN: receiver extended FSM
default
udt_send(sndpkt) rdt_rcv(rcvpkt)
&& notcurrupt(rcvpkt)
L && hasseqnum(rcvpkt,expectedseqnum)
expectedseqnum=1 Wait extract(rcvpkt,data)
sndpkt = deliver_data(data)
make_pkt(expectedseqnum,ACK,chksum) sndpkt = make_pkt(expectedseqnum,ACK,chksum)
udt_send(sndpkt)
expectedseqnum++

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 #
46
GBN in action

47
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, unACK’ed pkts

48
Selective repeat: sender, receiver windows

49
Selective repeat
sender receiver
data from above : pkt n in [rcvbase, rcvbase+N-1]
• if next available seq # in window,  send ACK(n)
send pkt  out-of-order: buffer
timeout(n):  in-order: deliver (also deliver
• resend pkt n, restart timer buffered, in-order pkts),
advance window to next not-
ACK(n) in [sendbase,sendbase+N]: yet-received pkt
• mark pkt n as received
pkt n in [rcvbase-N,rcvbase-1]
• if n smallest unACKed pkt,  ACK(n)
advance window base to next
unACKed seq # otherwise:
 ignore

50
Selective repeat in action

3-51
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)

Q: what relationship between

seq # size and window
size?
52