COMP 3234B
Computer and Communication Networks
2nd semester 2020-2021
Transport Layer (I)
Prof. C Wu
Department of Computer Science The University of Hong Kong
Roadmap
Transport layer
Principles behind transport-layer services
multiplexing/demultiplexing (ILO1, 2) reliable data transfer (ILO 2, 3)
flow control (ILO 2, 3)
congestion control (ILO 2, 3)
Transport protocols in the Internet (ILO 2, 3) TCP
UDP
application
ttransporrtt
network
link
physical
Transport-layer services
Provide logical end-to-end communication between application processes running
on different hosts
Transport protocols run in end systems
sender
breaks application messages into segments passes to network layer
receiver
reassembles segments into messages passes to application layer
application
transport
network data link physical
network data link physical
network data link physical
network data link network physical
data link physical
network data link physical
network data link physical
network data link physical
application
transport
network data link physical
logical end-end transport
Transport layer vs. network layer
Transport layer
logical communication between processes on different hosts
relies on, enhances network layer services
Network layer
logical communication between hosts
household analogy:
4 kids in Ann’s house sending letters to 4 kids in Bill’s house:
§ hosts = houses
§ processes = kids
§ app messages = letters in envelopes
§ transport protocol = Ann and Bill who distribute letters to in-house kids
§ network-layer protocol = postal service
application
ttrransport
network
network
link
physical
Ann
Transport-layer protocols
Available Internet transport protocols
TCP: reliable, in-order segment delivery
connection setup flow control congestion control
UDP: unreliable, unordered segment delivery
“best effort”
application
transport
network data link physical
network data link physical
network data link physical
network data link network physical
network data link physical
network data link physical
data link physical
network data link physical
application
transport
network data link physical
logical end-end transport
Transport-layer multiplexing/demultiplexing
Transport-layer multiplexing
multiple process-to-process deliveries on a host utilize the host-to-host delivery service provided by the network layer
multiplexing at sender:
handle data from multiple sockets, envelop data with transport header to create segments, and pass segments to network layer
Each process can have one or more sockets
demultiplexing at receiver:
use header info to deliver received segments to correct socket
application
P1 P2
transport
network
link
physical
application
P3
transport
network
link
physical
application
P4
transport
network
link
physical
socket
process
Transport-layer multiplexing/demultiplexing (cont’d
)
How transport-layer demultiplexing works
host receives IP datagrams (network-layer data format)
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
32 bits
P1 application
P2
application
P3
src port
dest port
data
src port
dest port
data
s
datadatagram network
transport network
segment datagram src
egment
transport
dest IP
src port
dest port
data
src IP
src port
link
source port #
other header fields
application data (message)
TCP/UDP segment format
IP
dest port #
dest IP
dest port
link
physical
physical
host 2
host 1
Demultiplexing in UDP
Recall how UDP socket is created and every datagram has to be tagged with destination IP address and port number:
serverSocket = socket(AF_INET, SOCK_DGRAM) serverSocket.bind( (“”, serverPort) )
clientSocket = socket(AF_INET, SOCK_DGRAM) clientSocket.sendto(sentence.encode(), (serverName, serverPort))
UDP socket identified by two-tuple: (IP address, port number)
Demultiplexing in UDP (cont’d)
IP datagrams with different source IP addresses/port numbers but the same destination IP address/port number are directed to the same socket
application
P1
transport
network
link
physical
application
P3
transport
network
transport
network
link
link
physical
physical
source port: 6428 dest port: 9157
source port: 6428 dest port: 5775
source port: 5775 dest port: 6428
source port: 9157 dest port: 6428
application
P4
Demultiplexing in TCP
Recall how TCP socket is created:
serverSocket = socket(AF_INET, SOCK_STREAM) serverSocket.bind( (“”, serverPort) ) serverSocket.listen()
connectionSocket, addr = serverSocket.accept()
clientSocket = socket(AF_INET, SOCK_STREAM) clientSocket.connect( (serverName, serverPort) )
all connectionSockets handling client connections use the same serverPort; they are distinguished using client IP address and port number
TCP socket identified by 4-tuple:
(source IP address, source port number, dest IP address, dest port number)
Receiving host uses all 4 values to direct (demultiplex) segment to appropriate socket
IP datagrams with different source IP addresses or source port numbers directed to different sockets!
Demultiplexing in TCP (cont’d)
Server host may support many simultaneous TCP sockets
each identified by its own 4-tuple
e.g., web server has different socket for each connecting client
concurrent server
application
P4
transport
network
link
physical
application
P3
application
P2 P3
transport
transport
network
network
link
link
physical
physical
host: IP address A
source IP,port: B,80 dest IP,port: A,9157
source IP,port: A,9157 dest IP, port: B,80
server: IP address B
source IP,port: C,5775 dest IP,port: B,80
source IP,port: C,9157 dest IP,port: B,80
host: IP address C
three segments, all destined to IP address: B, dest port: 80 are demultiplexed to different sockets
UDP: connectionless transport protocol
User Datagram Protocol [RFC 768]
“best effort” service
UDP segments may be lost or delivered out of order to application
connectionless
no handshaking between UDP sender and receiver
each UDP segment handled independently of others
no flow control
no congestion control
Why is there UDP?
lower delay
TCP is slow (3-way handshake, congestion control, retransmission due to reliable data transfer)
no need to maintain connection states at sender, receiver
a server can support many more UDP connections than TCP connections
smaller packet header
UDP: connectionless transport protocol (cont’d)
source port #
length
32 bits
Length, in bytes of UDP segment, including header
UDP segment format
dest port #
Application data (message)
checksum
Applications
Often used for streaming multimedia applications
loss tolerant, delay sensitive
others: DNS,SNMP (for network monitoring)
Reliable data transfer (rdt) over UDP
implement rdt at application layer application-specific error recovery
Checksum
Checksum
detect bit errors
whether bits within the segment have been altered (flipped)
use checksum field of the packet
e.g., checksum field in a TCP/UDP header
sender:
§ treat segment contents, including header fields, as sequence of 16-bit integers
§ checksum: addition (one’s complement of the 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.
Checksum (cont’d)
Checksum
Example
adding two 16-bit integers
when adding numbers, a carryout from the most significant bit needs to be added to the result
checksum is obtained by 1s complement of the sum (converting all the 0s to 1s and all the 1s to 0s)
11110011001100110 11101010101010101
wraparound
sum checksum
11011101110111011
11011101110111100 10100010001000011
Principles of reliable data transfer
among top-10 important networking problems
can be implemented in application, transport, link layers
complexity of reliable data transfer depends on characteristics of unreliable underlying channel
network
layer
Principles of reliable data transfer
among top-10 important networking problems
can be implemented in application, transport, link layers
complexity of reliable data transfer depends on characteristics of unreliable underlying channel
network
layer
Principles of reliable data transfer
among top-10 important networking problems
can be implemented in application, transport, link layers
complexity of reliable data transfer depends on characteristics of unreliable underlying channel
network
layer
Principles of reliable data transfer (cont’d)
rdt_send(): called from above,
(e.g., by app.). Passed data to deliver to receiver upper layer
deliver_data(): called by rdt to deliver data to upper
send receive side side
udt_send(): called by rdt,
to transfer packet over unreliable channel to receiver
In the following, we will:
incrementally develop sender, receiver sides of rdt protocol
consider only unidirectional data transfer (but control info will flow on both directions)
use finite state machines (FSM) to describe sender/receiver behavior (state changes, actions)
rdt_rcv(): called when packet arrives on rcv-side of channel
state: when in this “state” next state uniquely determined by next event
state 1
event causing state transition actions taken on state transition
event actions
state 2
Finite state machine
A model of behavior composed of
a finite number of states transitions between those states events triggering the transition actions performed upon transition
Example of turnstile
Tap card Unlock
Pass Lock
Reliable data transfer protocols
Protocols to achieve reliable data transfer (rdt) from sender to receiver
rdt 1.0 rdt 2.x
TCP
increasing complexity with increasing levels of unreliability of the underlying channel
rdt 3.0, Go-Back-N (GBN), Selective Repeat
no loss, no bit error
no loss, with bit error
loss and bit error
Reliable transfer over a reliable channel (Rdt1.0)
Underlying channel perfectly reliable
no bit error
no loss of packets
FSMs for sender and receiver protocols
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
sender sends data into underlying channel
receiver reads data from underlying channel
Reliable transfer over a channel with bit errors (RDT 2.x)
Underlying channel
packet received (no loss)
bits possibly corrupted (flipped) in packet
How can sender know something’s wrong with the packet sent?
acknowledgements (ACKs): receiver explicitly tells sender that packet received OK negative acknowledgements (NAKs): receiver explicitly tells sender that packet
had errors
ACK and NAK: 1 bit long
What should sender do to recover from bit errors?
retransmits packet on receipt of NAK
How can receiver know something’s wrong with the packet received?
checksum: to detect bit errors
Mechanisms used
error detection using checksum
receiver feedback (receiver->sender):control msgs (ACK, NAK) sender retransmission
ARQ (Automatic Repeat reQuest) protocols
ARQ
Automatic repeat request protocols
reliable data transfer protocols based on acknowledgments/timeouts and retransmissions
stop-and-wait (rdt 2.x, rdt 3.0) Go-Back-N
Selective Repeat
Stop-and-wait protocol: sender sends one packet, waits for receiver response, and meanwhile cannot receive more data from upper layer
Rdt2.0: FSM specification
rdt_send(data)
snkpkt = make_pkt(data, checksum)
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)
udt_send(sndpkt)
rdt_rcv(rcvpkt) && isNAK(rcvpkt)
udt_send(sndpkt)
Wait for call from
above
Wait for ACK or
NAK
rdt_rcv(rcvpkt) && isACK(rcvpkt)
Λ
sender
Rdt2.0: operation without bit errors
rdt_send(data)
snkpkt = make_pkt(data, checksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) && isNAK(rcvpkt)
udt_send(sndpkt)
Wait for call from
above
Wait for ACK or
NAK
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)
rdt_rcv(rcvpkt) && isACK(rcvpkt)
Λ
Rdt2.0: operation with bit errors
rdt_send(data)
snkpkt = make_pkt(data, checksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) && isNAK(rcvpkt)
udt_send(sndpkt)
Wait for call from
above
Wait for ACK or
NAK
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)
rdt_rcv(rcvpkt) && isACK(rcvpkt)
Λ
Rdt2.0: discussions
A fatal flaw: what happens if ACK/NAK corrupted?
sender doesn’t know whether receiver correctly received or not
Possible solutions
checksum
detect bit error but not recover from errors
sender simply retransmits current packet if ACK/NAK garbled
possibly introduce duplicate packets
=> receiver does not know whether the arriving packet contains new data or is a retransmission!
sender adds sequence number into each packet and retransmits if ACK/ NAK corrupted
receiver discards duplicate packet
Rdt2.1 (fixed version of rdt2.0): sender FSM
Sender handles garbled ACK/NAKs
rdt2.0 sender
rdt_send(data)
sndpkt = make_pkt(0, data, checksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) || isNAK(rcvpkt) )
udt_send(sndpkt)
Wait for call 0 from
above
Wait for ACK or NAK 1
Wait for ACK or NAK 0
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt) && isACK(rcvpkt)
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt) && isACK(rcvpkt)
Λ
Λ
rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) || isNAK(rcvpkt) )
udt_send(sndpkt)
Wait for call 1 from above
sndpkt = make_pkt(1, data, checksum) udt_send(sndpkt)
rdt_send(data)
For a stop-and-wait protocol, 1 bit sequence number is enough, i.e., 0 or 1
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)
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq0(rcvpkt)
extract(rcvpkt,data) deliver_data(data)
sndpkt = make_pkt(ACK, chksum) udt_send(sndpkt)
Wait for 0 from below
Wait for 1 from below
rdt_rcv(rcvpkt) && (corrupt(rcvpkt)
sndpkt = make_pkt(NAK, chksum) udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
not corrupt(rcvpkt) && has_seq0(rcvpkt)
sndpkt = make_pkt(ACK, chksum) 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)
Q1: Why is there out-of- order packet received at receiver?
Q2: Does receiver need to include seq # of the packet to be acked/ NAKed into sndpkt?
Rdt2.1 (fixed version of rdt2.0): receiver FSM
Receiver handles garbled ACK/NAKs
rdt2.0 receiver
Rdt2.2: a NAK-free protocol
Compared to rdt2.1
same functionality
no NAK, using ACKs only
Approach
receiver
– always sends ACK for last packet that was received OK, and explicitly includes seq # of the packet into the ACK message
sender
– if receiving duplicate ACKs for the same packet k, knows receiver does not correctly receive the current packet following packet k
– retransmits the current packet
refer to textbook Ch. 3.4.1 for sender/receiver FSMs
Reliable transfer over a channel with errors and losses (Rdt3.0)
Underlying channel can both corrupt bits or lose packets (data or ACKs)
how to detect packet loss
what to do when packet loss occurs
Mechanisms we have learned in a rdt protocol:
checksum seq. #
ACKs retransmission
Additional mechanism: Timer
sender waits “reasonable” amount of time for ACK
retransmission if no ACK received in this time
to implement the above, sender manipulates a countdown timer
starts a timer whenever a packet is sent
if no correct ACK received when timer times out, retransmit the packet and restart the timer
if correct ACK received before timer times out, stop the timer and send the next packet
Rdt3.0: sender FSM
sender FSM
Q: Why do nothing here when receiving wrong ACK packets?
rdt_rcv(rcvpkt)
Λ
rdt_send(data)
sndpkt = make_pkt(0, data, checksum) udt_send(sndpkt)
start_timer
rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) || isACK(rcvpkt,1) )
Λ
timeout
udt_send(sndpkt) start_timer
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt) && isACK(rcvpkt,0)
stop_timer
Wait for call 0from
above
Wait for
ACK0
rdt_rcv(rcvpkt)
&& notcorrupt(rcvpkt) && isACK(rcvpkt,1)
stop_timer
timeout
udt_send(sndpkt) start_timer
Wait for
ACK1
Wait for call 1 from
above
rdt_rcv(rcvpkt)
Λ
rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) || isACK(rcvpkt,0) )
Λ
rdt_send(data)
sndpkt = make_pkt(1, data, checksum) udt_send(sndpkt)
start_timer
Q: Why do nothing here when receiving ACK packets?
Rdt3.0: receiver FSM
Receiver FSM
Λ
oncethru=0
rdt_rcv(rcvpkt) && (corrupt(rcvpkt) ||
has_seq1(rcvpkt))
If (Oncethru==1)
udt_send(sndpkt)
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq0(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
sndpkt = make_pkt(ACK,0, chksum) udt_send(sndpkt)
oncethru=1
rdt_rcv(rcvpkt) && (corrupt(rcvpkt) ||
has_seq0(rcvpkt)) udt_send(sndpkt)
Wait for 0 from below
Wait for 1 from below
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq1(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
sndpkt = make_pkt(ACK,1, chksum) udt_send(sndpkt)
Rdt3.0: in action
sender
send pkt0
rcv ack0 send pkt1
rcv ack1 send pkt0
receiver
pkt0 rcv pkt0 ack0
pkt1
ack1 rcv pkt1 pkt0
ack0 rcv pkt0 (a) no loss
sender
send pkt0
rcv ack0 send pkt1
receiver
rcv pkt0 send ack0
pkt1X loss
pkt1
ack1
pkt0
rcv pkt0 ack0 send ack0
pkt0
ack0
timeout
resend pkt1
rcv pkt1 send ack1
rcv ack1 send pkt0
(b) packet loss
Rdt3.0: in action (cont’d)
sender
send pkt0
rcv ack0 send pkt1
pkt0
ack0
pkt1
receiver
rcv pkt0 send ack0
rcv pkt1 send ack1
ack1
X
loss
timeout
resend pkt1
pkt1
ack1
pkt0
ack0
(c) ACK loss
rcv pkt1 (detect duplicate)
rcv ack1 send pkt0
send ack1
rcv pkt0 send ack0
Rdt3.0: in action (cont’d)
How long should the sender wait?
wait too short:
premature timeout when packet (or ACK) is just delayed (not lost)
introduce duplicate packets
send pkt1 pkt1 cannot recover from packet loss as soon ack1
as possible
wait for a round-trip time between sender and receiver
round-trip time (RTT): the time interval between the moment a packet is sent out and the moment its ACK is received
sender
send pkt0 pkt0 rcv ack0 ack0
receiver
rcv pkt0 send ack0
rcv pkt1 send ack1
wait too long:
timeout
resend pkt1 pkt1 rcv ack1 pkt0
send pkt0 ack1 rcv ack1 ack0
do nothing
rcv pkt1 (detect duplicate)
send ack1
rcv pkt0 send ack0
(d) premature timeout/ delayed ACK
Rdt3.0: performance
Rdt3.0: performance
Rdt 3.0 is a working reliable data transfer protocol
Rdt3.0 ips earwforkminagncreliaisblveedraytapotroarnsfer protocol
example: link rate R=1 Gbps link, propagation delay 15 ms (milliseconds),
Rdt3.0 performance very poor
each packet L= 8000 bit
example: link rate R=1 Gbps link, propagation delay 15 ms (milliseconds), each packet L=
la
8000 bit
sender first packet bit transmseitntededr, t = 0
last packet bit transmitted, t = L / R first packet bit transmitted, t = 0
st packet bit transmitted, t = L / R
receiver receiver
first packet bit arrives
arrives
last packet bit arrives, send ACK
first packet bit last packet bit
RTT
RTT arrives, send ACK
ACK arrives, send next ACK arrives, send next
packet,pta=cRkTeTt,+tL=/RTT+L/R
dtrans = L = 8000bits = 8microseconds R 109bps
RTT = 2 ×15ms = 30ms
U sender: sender utilization (fraction of time sender is busy sending)
U sender: sender utilization (fraction of time sender is busy sending)
-> 1000bytes/30.008ms=33kB/sec data throughput over 1 Gbps link
-> 1000bytes/30.008ms=33kB/sec data throughput over 1 Gbps link
Reason for bad performance: a stop-and-wait protocol!
Wednesday, 8 February 2012 Reason for bad performance: a stop-and-wait protocol! 34
Required reading:
Computer Networking: A Top-Down Approach (7th Edition) Ch 3.1, 3.2, 3.3, 3.4.1
Acknowledgement:
Some materials are extracted from the slides created by Prof. Jim F. Kurose and Prof. Keith W. Ross for the textbook.