PowerPoint Presentation
Computer Systems
Transport Layer
Dr. Mian M. Hamayun
m.m. .uk
Based on material and slides from
Computer Networking: A Top Down
Approach, 7th
Edition – Chapter 3
,
Pearson/
Slide# 2 of 63
Lecture Objective
The objective of this lecture is to understand the
conceptual and implementation aspects of
transport layer protocols
Slide# 3 of 63
Lecture Outline
Transport Layer Services & Protocols
Multiplexing / Demultiplexing
User Datagram Protocol (UDP)
Principles of Reliable Data Transfer
Transmission Control Protocol (TCP)
Flow Control
Connection Management
Summary
Slide# 4 of 63
Recap – Network Layers
Slide# 5 of 63
Transport Layer Services
Provide logical communication
between application processes
running on different hosts.
Transport protocols run in end
systems (not routers)
send side: breaks app
messages into segments,
passes to network layer
receive side: reassembles
segments into messages,
passes to application layer
More than one transport
protocol available to apps
Internet: TCP and UDP
Slide# 6 of 63
Transport vs. Network Layer
12 kids in Ann’s house sending
letters to 12 kids in Bill’s house:
hosts = houses
processes = kids
app messages = letters in
envelopes
transport protocol = Ann and
Bill who demux to in-house
siblings
network-layer protocol =
postal service
Household Analogy:
Network layer: logical
communication between
hosts.
Transport layer: logical
communication between
processes
relies on, enhances,
network layer services
Slide# 7 of 63
Internet Transport Layer Protocols
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
Slide# 8 of 63
Multiplexing / Demultiplexing
handle data from multiple
sockets, add transport
header (later used for
demultiplexing)
multiplexing at sender: demultiplexing at receiver:
use header info to deliver
received segments to
correct socket
Slide# 9 of 63
How Demultiplexing Works?
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
port numbers 0 – 65535
well-known ports 0 – 1023
Host uses IP addresses & port
numbers to direct segment to
appropriate socket
TCP/UDP segment format
Slide# 10 of 63
When a UDP Socket is created, a host-local port# is assigned
to it.
When creating a datagram to send into a UDP socket, we must
specify
Destination IP Addr
Destination Port #
When a host receives UDP
segment:
checks destination port# in
segment
directs UDP segment to
socket with that port #
IP datagrams with same
dest. port #, but different
source IP addresses and/
or source port numbers
will be directed to same
socket at destination
Slide# 11 of 63
– Example
Slide# 12 of 63
Connection-oriented Demultiplexing
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
Slide# 13 of 63
Connection-oriented Demultiplexing –
Example
Slide# 14 of 63
UDP: User Datagram Protocol [RFC 768]
“No Frills”, “Bare Bones”
Internet transport protocol
“ ” service, UDP
segments may be:
Lost
Delivered out-of-order
Connectionless:
no handshaking between UDP
sender, receiver
each UDP segment handled
independently of others
UDP used in:
streaming multimedia apps (loss
tolerant, rate sensitive)
DNS (Domain Name System)
SNMP (Simple Network
Management Protocol)
Reliable transfer over UDP:
add reliability at application layer
e.g. QUIC (Quick UDP Internet
Connections) protocol
application-specific error
recovery!
Slide# 15 of 63
UDP: Popular Internet Applications
Slide# 16 of 63
UDP: Segment Header
no connection establishment
(which can add delay)
simple: no connection state
at sender, receiver
small header size (8 bytes)
no congestion control: UDP
can blast away as fast as
desired
Why is there a UDP?
UDP segment format
length, in bytes of
UDP segment,
including header
Slide# 17 of 63
UDP Checksum
Sender:
Treat segment contents,
including header fields, as
sequence of 16-bit integers
Checksum: addition
(one’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.
But maybe errors nonetheless?
More later …
Goal: detect “errors” (e.g., flipped bits) in
transmitted segment
Slide# 18 of 63
UDP Checksum – Example
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 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
Slide# 19 of 63
Principles of Reliable Data Transfer
Slide# 20 of 63
Reliable Data Transfer over a Perfectly
Reliable Channel: rdt1.0
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
Slide# 21 of 63
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 packet
received OK
Negative Acknowledgements (NAKs): receiver explicitly tells sender that
packet had errors
sender retransmits packet on receipt of NAK
New mechanisms in rdt2.0 (beyond rdt1.0):
error detection
receiver feedback: control messages (ACK,NAK)
receiver->sender
Slide# 22 of 63
RDT2.0: FSM Specifications
Slide# 23 of 63
RDT2.0: Operation with No Errors
Slide# 24 of 63
RDT2.0: Operation with Errors
Slide# 25 of 63
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 corrupted
Sender adds sequence
number to each packet
Receiver discards (doesn’t
deliver up) duplicate packet
Stop and Wait
sender sends one
packet, then waits for
receiver response
Slide# 26 of 63
RDT2.1: Sender, handles garbled ACK/NAKS
Slide# 27 of 63
RDT2.1: Receiver, handles garbled
ACK/NAKS
Slide# 28 of 63
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 “expected” packet
should have seq # of 0 or 1
Receiver:
Must check if received
packet is duplicate
state indicates whether
0 or 1 is expected
packet seq #
Note: receiver can not
know if its last ACK/ NAK
received OK at sender
Slide# 29 of 63
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 packet being ACKed
Duplicate ACK at sender results in same action as
NAK: retransmit current packet
Slide# 30 of 63
RDT2.2: Sender, Receiver FSM Fragments
Slide# 31 of 63
RDT3.0: Channels with Errors and Loss
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 packet (or ACK) just delayed
(not lost):
retransmission will be
duplicate, but seq. #’s already
handles this
receiver must specify seq # of
packet being ACKed
Requires countdown timer
Slide# 32 of 63
RDT3.0: Channels with Errors and Loss
Slide# 33 of 63
RDT3.0 in Action!
Slide# 34 of 63
RDT3.0 in Action!
Slide# 35 of 63
Performance of RDT 3.0
rdt3.0 is correct, but performance stinks
e.g. 1 Gbps link, 15ms propagation delay, 8000 bit packet:
Usender: utilization – fraction of time sender busy sending
If RTT = 30ms, 1KB packet every 30ms: 33kB/sec
throughput over 1 Gbps link!
Network protocols limits use of physical resources!
Slide# 36 of 63
Pipelined Protocols
Pipelining: sender allows multiple, “in-flight”, yet-to-be-
acknowledged packets
range of sequence numbers must be increased
buffering at sender and/or receiver
Two generic forms of pipelined protocols:
Go-Back-N (GBN) and Selective Repeat (SR)
Slide# 37 of 63
TCP Overview
[RFCs 793, 1122, 1323, 2018, 2581]
Point-to-Point:
one sender, one receiver
Reliable, in-order byte
steam:
no “message
boundaries”
Pipelined:
TCP congestion and flow
control set window size
Full duplex data:
bi-directional data flow in same
connection
MSS: maximum segment size
(app data size, usually 1460
bytes)
Connection-oriented:
handshaking (exchange of
control messages) initializes
sender, receiver state before
data exchange
Flow controlled:
sender will not overwhelm the
receiver
Slide# 38 of 63
TCP: Segment Structure
# bytes
receiver
willing to
accept
counting
by bytes
of data
(not segments!)
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)
Slide# 39 of 63
TCP Sequence Numbers & ACKs
Implicit numbering for each byte of data
File Size = 500,000 bytes
MSS = 1000 bytes
Total Segments = 500
First Segment Seq. # = 0
Second Segment Seq. # 1000
Third Segment Seq. # 2000 & so on.
Slide# 40 of 63
TCP Sequence Numbers & ACKs
Sequence Numbers:
byte stream “number” of
first byte in segment’s data
Acknowledgments:
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 the implementer
(usually kept)
Slide# 41 of 63
TCP Sequence Numbers & ACKs
Slide# 42 of 63
TCP Round Trip Time (RTT), Timeout
Q: How to set TCP timeout
value?
longer than RTT
but RTT varies
too short: premature
timeout, unnecessary
retransmissions
too long: slow reaction to
segment loss
Q: How to estimate RTT?
SampleRTT: measured time
from segment transmission
until ACK receipt
ignore retransmissions
SampleRTT will vary, want
estimated RTT “smoother”
average several recent
measurements, not just
current SampleRTT
Slide# 43 of 63
TCP Round Trip Time (RTT), Timeout
Exponential
Weighted Moving
Average (EWMA)
Influence of past
sample decreases
exponentially fast
typical value:
= 0.125
EstimatedRTT = (1-)*EstimatedRTT + *SampleRTT
Slide# 44 of 63
TCP Round Trip Time (RTT), Timeout
Timeout Interval: EstimatedRTT plus “safety margin”
large variation in EstimatedRTT -> larger safety margin
Estimate SampleRTT deviation from EstimatedRTT:
DevRTT = (1-)*DevRTT +
*|SampleRTT-EstimatedRTT|
(typically, = 0.25)
TimeoutInterval = EstimatedRTT + 4*DevRTT
estimated RTT “safety margin”
Slide# 45 of 63
TCP Reliable Data Transfer
TCP creates reliable data
transfer service on top of
IP’s unreliable best-effort
service
pipelined segments
cumulative acks
single retransmission timer
Retransmissions are
triggered by:
timeout events
duplicate acks
Let’s initially consider
simplified TCP sender:
ignore duplicate acks
ignore flow control,
congestion control
Slide# 46 of 63
TCP Sender Events
Data Received from App:
Create segment with seq #
Seq # is byte-stream
number of first data byte in
segment
Start timer if not already
running
think of timer as for oldest
unacked segment
expiration interval:
TimeOutInterval
Timeout:
Retransmit segment that
caused timeout
Restart Timer
Ack Received:
If ack acknowledges
previously unacked
segments
update what is known to be
ACKed
start timer if there are still
unacked segments
Slide# 47 of 63
TCP Sender (Simplified)
Slide# 48 of 63
TCP Retransmission Scenarios
Lost ACK Scenario Time-out Scenario;
Seg#100 not retransmitted
Slide# 49 of 63
TCP Retransmission Scenarios
Cumulative ACK
Slide# 50 of 63
TCP ACK Generation
[RFC 1122, RFC 2581]
Event at Receiver
Arrival of in-order segment with
expected seq #. All data up to
expected seq # already ACKed
Arrival of in-order segment with
expected seq #. One other
segment has ACK pending
Arrival of out-of-order segment
higher-than-expect seq. # .
Gap detected
Arrival of segment that
partially or completely fills gap
TCP Receiver Action
Delayed ACK. Wait up to 500ms
for next segment. If no next segment,
send ACK
Immediately send single cumulative
ACK, ACKing both in-order segments
Immediately send duplicate ACK,
indicating seq. # of next expected byte
Immediate send ACK, provided that
segment starts at lower end of gap
Slide# 51 of 63
TCP Fast Retransmit
Time-out period often
relatively long:
Long delay before
resending lost packet
Detect lost segments via
duplicate ACKs.
Sender often sends many
segments back-to-back
If segment is lost, there
will likely be many
duplicate ACKs.
If sender receives 3 ACKs
for same data
(“triple duplicate ACKs”),
resend unacked segment
with smallest sequence #.
Likely that unacked
segment lost, so don’t
wait for timeout.
TCP Fast Retransmit
Slide# 52 of 63
TCP Fast Retransmit
Slide# 53 of 63
TCP Flow Control
[Speed-matching b/w Sender & Receiver]
Receiver controls sender,
so sender won’t overflow
receiver’s buffer by
transmitting too much
data, too fast.
Flow Control
Slide# 54 of 63
TCP Flow Control
[Speed-matching b/w Sender & Receiver]
Receiver “advertises” free
buffer space by including
rwnd value in TCP header of
receiver-to-sender segments
RcvBuffer size set via socket
options (typical default is 4096
bytes)
many operating systems autoadjust
RcvBuffer
Sender limits amount of
unacked (“in-flight”) data to
receiver’s rwnd value
Guarantees receive buffer
will not overflow
Receiver-side Buffering
Sender:
LastByteSent – LastByteAcked <= rwnd
Receiver:
rwnd = RcvBuffer –
[LastByteRcvd – LastByteRead]
Slide# 55 of 63
TCP Connection Management
Before exchanging data, sender/receiver “handshake”:
agree to establish connection (each knowing the other willing
to establish connection)
agree on connection parameters
Slide# 56 of 63
TCP 3-Way Handshake
SYNbit=1, Seq=x
choose init seq num, x
send TCP SYN msg
SYNbit=1, Seq=y
ACKbit=1; ACKnum=x+1
choose init seq num, y
send TCP SYNACK
msg, acking SYN
ACKbit=1, ACKnum=y+1
received SYNACK(x)
indicates server is live;
send ACK for SYNACK;
this segment may contain
client-to-server data
received ACK(y)
indicates client is live
SYNSENT
ESTAB
ESTAB
SYN RCVD
Client State
LISTEN
server state
LISTEN
Slide# 57 of 63
TCP 3-Way Handshake
closed
listen
SYN
rcvd
SYN
sent
ESTAB
Socket clientSocket =
newSocket("hostname","port
number");
SYN(seq=x)
Socket connectionSocket =
welcomeSocket.accept();
SYN(x)
SYNACK(seq=y,ACKnum=x+1)
create new socket for
communication back to client
SYNACK(seq=y,ACKnum=x+1)
ACK(ACKnum=y+1)
ACK(ACKnum=y+1)
Slide# 58 of 63
Closing a TCP Connection
Client, server each close their side of connection
send TCP segment with FIN bit = 1
Respond to received FIN with ACK
on receiving FIN, ACK can be combined with own FIN
Simultaneous FIN exchanges can be handled
Slide# 59 of 63
Closing a TCP Connection
FINbit=1, seq=y
ACKbit=1; ACKnum=y+1
ACKbit=1; ACKnum=x+1
wait for server
close
can still
send data
can no longer
send data
FINbit=1, seq=xcan no longer
send but can
receive data
clientSocket.close()
CLOSE_WAIT
LAST_ACK
CLOSED
ESTAB
FIN_WAIT_2
TIMED_WAIT
CLOSED
FIN_WAIT_1
ESTAB
Client state Server state
timed wait
for 2*max
segment lifetime
Slide# 60 of 63
TCP Client & Server States
Slide# 61 of 63
TCP Client & Server States
Slide# 62 of 63
Summary
We have studied:
Principles behind transport layer services:
multiplexing, demultiplexing
reliable data transfer
flow control
Implementation of the Internet Protocols
UDP
TCP
Slide# 63 of 63
References / Links
Chapter #3: Transport Layer, Computer Networking:
A Top-Down Approach (7th
edition) by Kurose & 1
Slide 2
Slide 3
Slide 4
Slide 5
Slide 6
Slide 7
Slide 8
Slide 9
Slide 10
Slide 11
Slide 12
Slide 13
Slide 14
Slide 15
Slide 16
Slide 17
Slide 18
Slide 19
Slide 20
Slide 21
Slide 22
Slide 23
Slide 24
Slide 25
Slide 26
Slide 27
Slide 28
Slide 29
Slide 30
Slide 31
Slide 32
Slide 33
Slide 34
Slide 35
Slide 36
Slide 37
Slide 38
Slide 39
Slide 40
Slide 41
Slide 42
Slide 43
Slide 44
Slide 45
Slide 46
Slide 47
Slide 48
Slide 49
Slide 50
Slide 51
Slide 52
Slide 53
Slide 54
Slide 55
Slide 56
Slide 57
Slide 58
Slide 59
Slide 60
Slide 61
Slide 62
Slide 63