Computer Networks

Transport layer

Transport layer -- May 2004 1

 Transport Layer
 Services
 Elements of transport protocol
 Simple transport protocol
 UDP
 Remote Procedure Call (see Distributed Systems)
 TCP

Transport layer -- May 2004 2

Layer overview

application
transport
network
data link network
physical data link
network physical

lo
data link

gi
physical

ca
network

le
data link

nd
physical network

-e
data link

nd
physical

tr
an
network
data link

sp
physical

or
t
application
transport
network
data link
physical

Transport layer -- May 2004 3

 Layer overview
Host 1 Transport Host 2
addresses
Application layer Application layer

Transport entity TPDU Transport entity

Network
Network layer Network layer
addresses

Transport layer -- May 2004 4

 Services
 To upper layer
o efficient, reliable, cost-effective service
o 2 kinds
• Connection oriented
• Connectionless

Transport layer -- May 2004 5

 Services
 needed from network layer
o packet transport between hosts
o relationship network <> transport
• Hosts <> processes
• Transport service
– independent network
– more reliable
• Network
– run by carrier
– part of communication subnet for WANs

Transport layer -- May 2004 6

 Simple service: primitives
 Simple primitives:
o connect
o send
o receive
o disconnect
 How to handle incoming connection request in
server process?
Wait for connection request from client!
o listen

Transport layer -- May 2004 7

 Simple service: primitives
listen Wait till a process wants a connection
No TPDU
connect Try to setup a connection
Connection Request TPDU
send Send data packet
Data TPDU
receive Wait for arrival of data packet
No TPDU
disconnect Calling side breaks up the connection
Disconnect TPDU

Transport layer -- May 2004 8

Simple service: state diagram

Transport layer -- May 2004 9

Simple service: state diagram

Transport layer -- May 2004 10

Simple service: state diagram

Transport layer -- May 2004 11

 Berkeley service primitives
 Used in Berkeley UNIX for TCP
 Addressing primitives: socket
bind

 Server primitives: listen

accept
send + receive
close
 Client primitives:
connect
send + receive
close

Transport layer -- May 2004 12

 Berkeley service primitives
socket create new communication end point

bind attach a local address to a socket

listen announce willingness to accept connections; give queue size

accept block caller until a connection request arrives

connect actively attempt to establish a connection

send send some data over the connection

receive receive some data from the connection

close release the connection

Transport layer -- May 2004 13

 Transport Layer
 Services
 Elements of transport protocol
 Simple transport protocol
 UDP
 Remote Procedure Call (see Distributed Systems)
 TCP

Transport layer -- May 2004 14

Elements of transport protocols (etp)
 Transport <> Data Link
 Addressing
 Establishing a connection
 Releasing a connection
 Flow control and buffering
 Multiplexing
 Crash recovery

Transport layer -- May 2004 15

 etp: Transport <> data link
 Physical channel <> subnet

Explicit addressing
Connection establishment
Potential existence of storage capacity in subnet
Dynamically varying number of connections
Transport layer -- May 2004 16
 etp: Addressing
 TSAP = transport service access point
o Internet: IP address + local port
o ATM: AAL-SAPs
 Connection scenario
 Getting TSAP addresses?
 From TSAP address to NSAP address?

Transport layer -- May 2004 17

 etp: Addressing
 Connection scenario

Transport layer -- May 2004 18

 etp: Addressing
 Connection scenario
o Host 2 (server)
• Time-of-day server attaches itself to TSAP 1522
o Host 1 (client)
• Connect from TSAP 1208 to TSAP 1522
• Setup network connection to host 2
• Send transport connection request
o Host 2
• Accept connection request

Transport layer -- May 2004 19

 etp: Addressing
 Getting TSAP addresses?
o Stable TSAP addresses
• For key services
• Not for user processes
– active for a short time
– number of addresses limited
o Name servers
• to find existing servers
• map service name into TSAP address
o Initial connection protocol

Transport layer -- May 2004 20

 etp: Addressing
 Getting TSAP addresses?
o Initial connection protocol
• to avoid many waiting servers  one process server
– waits on many TSAPs
– creates requested server

Transport layer -- May 2004 21

 etp: Addressing
 From TSAP address to NSAP address?
o hierarchical addresses
• address = <country> <network> <host> <port>
– Examples: IP address + port
Telephone numbers (<> number portability?)
• Disadvantages:
– TSAP bound to host!
o flat address space
• Advantages:
– Independent of underlying network addresses
– TSAP address not bound to host
• Mapping to network addresses:
– Name server
– broadcast

Transport layer -- May 2004 22

 etp: Establishing a connection
 Problem: delayed duplicates!
 Scenario:
o Correct bank transaction
• connect
• data transfer
• disconnect
o Problem: same packets are received in same order a
second time!

Recognized?

Transport layer -- May 2004 23

 etp: Establishing a connection
 Unsatisfactory solutions:
o throwaway TSAP addresses
• need unlimited number of addresses?
• process server solution impossible
o connection identifier
• Never reused!
 Maintain state in hosts

 Satisfactory solutions

Transport layer -- May 2004 24

 etp: Establishing a connection
 Satisfactory solutions
o Ensure limited packet lifetime (incl. Acks)
o Mechanisms
• prevent packets from looping + bound congestion delay
• hopcounter in each packet
• timestamp in each packet
o Basic assumption

Maximum packet lifetime T

If we wait a time T after sending a packet all traces
of it (including Acks) are gone
Transport layer -- May 2004 25
 etp: Establishing a connection
 Tomlinson’s method
o requires: clock in each host
• Number of bits > number of bits in sequence number
• Clock keeps running, even when a hosts crashes
o Basic idea:

2 identically numbered TPDUs are

never outstanding at the same time!

Transport layer -- May 2004 26

 etp: Establishing a connection
 Tomlinson’s method
Never reuse a sequence number x within
the lifetime T for the packet with x
o Problems to solve
• Selection of the initial sequence number for a new connection
• Wrap around of sequence numbers for an active connection
• Handle host crashes

 Forbidden region
Transport layer -- May 2004 27
 etp: Establishing a connection
 Tomlinson’s method
o Initial sequence number
= lower order bits of clock
o Ensure initial sequence numbers are always OK
 forbidden region
o Wrap around
• Idle
• Resynchronize sequence numbers

Transport layer -- May 2004 28

 etp: Establishing a connection
 Tomlinson - forbidden region

Transport layer -- May 2004 29

 etp: Establishing a connection
 Tomlinson – three-way-handshake

No combination of
delayed packets can
cause the protocol to fail

Transport layer -- May 2004 30

 etp: Establishing a connection
 Tomlinson – three-way-handshake

Transport layer -- May 2004 31

 etp: Releasing a connection
 2 styles:
o Asymmetric
• Connection broken when one party hangs up
• Abrupt!  may result in data loss
o Symmetric
• Both parties should agree to release connection
• How to reach agreement? Two-army problem
• Solution: three-way-handshake
o Pragmatic approach
• Connection = 2 unidirectional connections
• Sender can close unidirectional connection

Transport layer -- May 2004 32

 etp: Releasing a connection
 Asymmetric: data loss

Transport layer -- May 2004 33

 etp: Releasing a connection
 Symmetric: two-army-problem

Simultaneous attack by blue army

Communication is unreliable

No protocol exists!!

Transport layer -- May 2004 34

 etp: Releasing a connection
 Three-way-handshake + timers
o Send disconnection request
+ start timer RS to resend (at most N times)
the disconnection request
o Ack disconnection request
+ start timer RC to release connection

Transport layer -- May 2004 35

etp: Releasing a connection

RC

Transport layer -- May 2004 36

 etp: Releasing a connection

RS

Transport layer -- May 2004 37

etp: Flow control and buffering
Transport Data link
connections, lines many few
varying fixed

(sliding) window size varying fixed

buffer management different sizes? fixed size

Transport layer -- May 2004 38

etp: Flow control and buffering
 Buffer organization

Transport layer -- May 2004 39

etp: Flow control and buffering
 Buffer management: decouple buffering from Acks

Transport layer -- May 2004 40

etp: Flow control and buffering
 Where to buffer?
o datagram network  @ sender
o reliable network
+ Receiver process guarantees free buffers?
• No: for low-bandwidth bursty traffic
 @ sender
• Yes: for high-bandwidth smooth traffic
 @ receiver

Transport layer -- May 2004 41

etp: Flow control and buffering
 Window size?
o Goal:
• Allow sender to continuously send packets
• Avoid network congestion
o Approach:
• maximum window size = c * r
– network can handle c TPDUs/sec
– r = cycle time of a packet
• measure c & r and adapt window size

Transport layer -- May 2004 42

 etp: Multiplexing
 Upward: reduce number of network connections to reduce cost
 Downward: increase bandwidth to avoid per connection limits

Transport layer -- May 2004 43

 etp: Crash recovery
 recovery from network, router crashes?
o No problem
• Datagram network: loss of packet is always handled
• Connection-oriented network: establish new connection + use
state to continue service
 recovery from host crash?
o server crashes, restarts: implications for client?
Recovery from a layer N crash can only
o assumptions:
be •done bysaved
no state layer N+1 and
at crashed serveronly if the
• no simultaneous events
higher layer retains enough status
o NOT POSSIBLE
information.
Transport layer -- May 2004 44
 etp: Crash recovery
 Illustration of problem: File transfer:
o Sender: 1 bit window protocol: states S0, S1
• packet with seq number 0 transmitted; wait for ack
o Receiver: actions
• Ack packet
• Write data to disk
• Order?

Transport layer -- May 2004 45

 etp: Crash recovery
 Illustration of problem: File transfer

Transport layer -- May 2004 46

 Transport Layer
 Services
 Elements of transport protocol
 Simple transport protocol
 UDP
 Remote Procedure Call (see Distributed Systems)
 TCP

Transport layer -- May 2004 47

 Simple transport protocol
 Service primitives:
o connum = LISTEN (local)
• Caller is willing to accept connection
• Blocked till request received
o connum = CONNECT ( local, remote)
• Tries to establish connection
• Returns identifier (nonnegative number)
o status = SEND (connum, buffer, bytes)
• Transmits a buffer
• Errors returned in status
o status = RECEIVE (connum, buffer, bytes)
• Indicates caller’s desire to get data
o status = DISCONNECT (connum)
• Terminates connection

Transport layer -- May 2004 48

 Simple transport protocol
 Transport entity
o Uses a connection-oriented reliable network
o Programmed as a library package
o Network interface
• ToNet(…)
• FromNet(…)
• Parameters:
– Connection identifier (connum = VC)
– Q bit: 1 = control packet
– M bit: 1 = more data packets to come
– Packet type
– Pointer to data
– Number of bytes of data

Transport layer -- May 2004 49

 Simple transport protocol
 Transport entity: packet types

Network packet Meaning

Call request Sent to establish a connection

Call accepted Response to Call Request

Clear Request Sent to release connection

Clear confirmation Response to Clear request

Data Used to transport data

Credit Control packet to manage window

Transport layer -- May 2004 50

 Simple transport protocol
 Transport entity: state of a connection

State Meaning

Idle Connection not established

Waiting CONNECT done; Call Request sent

Queued Call Request arrived; no LISTEN yet

Established

Sending Waiting for permission to send a packet

Receiving RECEIVE has been done

Disconnecting DISCONNECT done locally

Transport layer -- May 2004 51

 Simple transport protocol
 Transport entity: code
o See fig 6-20, p. 514 – 517
o To read and study at home!
o Questions?
• Is it acceptable not to use a transport header?
• How easy would it be to use another network protocol?

Transport layer -- May 2004 52

Example Transport Entity (1)

Transport layer -- May 2004 53

Example Transport Entity (2)

Transport layer -- May 2004 54

Example Transport Entity (3)

Transport layer -- May 2004 55

Example Transport Entity (4)

Transport layer -- May 2004 56

Example Transport Entity (5)

Transport layer -- May 2004 57

Example Transport Entity (6)

Transport layer -- May 2004 58

Example Transport Entity (7)

Transport layer -- May 2004 59

Example Transport Entity (8)

Transport layer -- May 2004 60

 Transport Layer
 Services
 Elements of transport protocol
 Simple transport protocol
 UDP
 Remote Procedure Call (see Distributed Systems)
 TCP

Transport layer -- May 2004 61

 UDP
 User Data Protocol
o Datagram service between processes
• No connection overhead
o UDP header:
• Ports = identification of end points

Transport layer -- May 2004 62

 UDP
 Some characteristics
o Supports broadcasting, multicasting
(not in TCP)
o Packet oriented
(TCP gives byte stream)
o Simple protocol

o Why needed above IP?

Transport layer -- May 2004 63

 Transport Layer
 Services
 Elements of transport protocol
 Simple transport protocol
 UDP
 Remote Procedure Call (see Distributed Systems)
 TCP

Transport layer -- May 2004 64

 TCP service model
 point-to-point
o one sender, one receiver
 reliable, in-order byte stream
o no message/packet boundaries
 pipelined & flow controlled
o window size set by TCP congestion and flow control
algorithms
 connection-oriented
o handshaking to get at initial state
 full duplex data
o bi-directional data flow in same connection

Transport layer -- May 2004 65

 TCP service model
…
 send & receive buffers

a p p lic a t io n a p p lic a t io n
w r it e s d a t a re a d s d a ta
socket socket
door door
TC P TC P
s e n d b u ffe r r e c e iv e b u f f e r
segm ent

Transport layer -- May 2004 66

 TCP protocol
 Three-way handshake to set up connections
 Every byte has its own 32-bit sequence number
o Wrap around
o 32-bit Acks; window size in bytes
 Segment = unit of data exchange
o 20-byte header + options + data
o Limits for size
• 64Kbyte
• MTU, agreed upon for each direction
o Data from consecutive writes may be accumulated in a single
segment
o Fragmentation possible
 Sliding window protocol

Transport layer -- May 2004 67

TCP header

Transport layer -- May 2004 68

 TCP header
 source & destination ports (16 bit)
 sequence number (32 bit)
 Acknowledgement number (32 bit)
 Header length (4 bits) in 32-bit words
 6 flags (1 bit)
 window size (16 bit): number of bytes the sender is
allowed to send starting at byte acknowledged
 checksum (16 bit)
 urgent pointer (16 bit) : byte position of urgent data

Transport layer -- May 2004 69

 TCP header
 Flags:
o URG: urgent pointer in use
o ACK: valid Acknowledgement number
o PSH: receiver should deliver data without delay to user
o RST: reset connection
o SYN: used when establishing connections
o FIN: used to release connection
 Options:
o Maximum payload a host is willing to receive
o Scale factor window size
o Use selective repeat instead of go back n

Transport layer -- May 2004 70

 TCP connection management
 Three-way handshake
o Initial sequence number: clock based
o No reboot after crash for T (maximum packet lifetime=120 sec)
o Wrap around?
 Connection identification
o Pair of ports of end points
 Connection release
o Both sides are closed separately
o No response to FIN: release after 2*T
o Both sides closed: wait for time 2 * T

Transport layer -- May 2004 71

TCP connection management

Transport layer -- May 2004 72

Transport layer -- May 2004 73
TCP connection management
State Description

Closed No connection is active or pending

Listen The server is waiting for an incoming call
SYN rcvd A connection request has arrived; wait for ACK
SYN sent The application has started to open a connection
Established The normal data transfer state
FIN wait 1 The application has said it is finished
FIN wait 2 The other side has agreed to release
Timed wait Wait for all packets to die off
Closing Both sides have tried to close simultaneously
Close wait The other side has initiated a release
Last Ack Wait for all packets to die off

Transport layer -- May 2004 74

 TCP transmission policy
 Window size decoupled from Acks (ex. next slides)
 Window = 0  no packets except for
o Urgent data
o 1 byte segment to send Ack & window size
 Incoming user data may be buffered
o May improve performance: less segments to send
 Ways to improve performance:
o Delay acks and window updates for 500 msec
o Nagle’s algorithm
o Silly window syndrome

Transport layer -- May 2004 75

TCP transmission policy

Transport layer -- May 2004 76

Transport layer -- May 2004 77
 TCP transmission policy
 Telnet scenario: interactive editor reacting on each
keystroke: One character typed
 21 byte segment or 41 byte IP packet
 (packet received) 20 byte segment with Ack
 (editor has read byte) 20 byte segment with window update
 (editor has processed byte; sends echo) 21 byte segment
 (client gets echo) 20 byte segment with Ack
 Solutions:
o delay acks + window updates for 500 msec
o Nagle’s algorithm:
• Receive one byte from user; send it in segment
• Buffer all other chars till Ack for first char arrives
• Send other chars in a single segment
• Disable algorithm for X-windows applications (do not delay sending
of mouse movements)

Transport layer -- May 2004 78

 TCP transmission policy
 Silly window syndrome
o Problem:
• Sender transmits data in large blocks
• Receiver reads data 1 byte at a time
o Scenario: next slide
o Solution:
• Do not send window update for 1 byte
• Wait for window update till
– Receiver can accept MTU
– Buffer is half empty

Transport layer -- May 2004 79

TCP transmission policy

Transport layer -- May 2004 80

 TCP transmission policy
 General approach:
o Sender should not send small segments
• Nagle: buffer data in TCP send buffer
o Receiver should not ask for small segments
• Silly window: do window updates in large units

Transport layer -- May 2004 81

 Principles of Congestion Control
Congestion:
 informally: “too many sources sending too much data too
fast for network to handle”
 different from flow control!
= end-to-end issue!
 manifestations:
o lost packets (buffer overflow at routers)
o long delays (queue-ing in router buffers)
 a top-10 problem!

Transport layer -- May 2004 82

 Causes/costs of congestion: scenario

 two senders, two

receivers
 one router, infinite
buffers
 no retransmission

 large delays
when congested
 maximum
achievable
throughput
Transport layer -- May 2004 83
Approaches towards congestion control
Two broad approaches towards congestion control:
end-to-end congestion Network-assisted
control: congestion control:
 no explicit feedback from  routers provide feedback
network to end systems
 congestion inferred from o single bit indicating
end-system observed loss, congestion (SNA, ATM)
delay o explicit rate sender
 approach taken by TCP should send at

Transport layer -- May 2004 84

 TCP Congestion Control
 How to detect congestion?
 Timeout caused by packet loss: reasons
o Transmission errors : Rare for wired networks
o Packed discarded at congested router

Packet loss

Hydraulic example illustrating two limitations

for sender!

Transport layer -- May 2004 85

TCP congestion control

Transport layer -- May 2004 86

 TCP Congestion Control
 How to detect congestion?
 Timeout caused by packet loss: reasons
o Transmission errors : Rare
o Packed discarded at congested router

Packet loss  congestion

Approach: 2 windows for sender

Receiver window
Minimum of  Congestion window

Transport layer -- May 2004 87

 TCP Congestion Control
 end-end control (no network assistance)
 transmission rate limited by congestion window size, Congwin, over
segments:

Congwin

 w segments, each with MSS bytes sent in one RTT:

w * MSS
throughput = Bytes/sec
RTT

Transport layer -- May 2004 88

 TCP Congestion Control:
 “probing” for usable  two “phases”
bandwidth: o slow start
o ideally: transmit as fast as o congestion avoidance
possible (Congwin as large as 
important variables:
possible) without loss
o Congwin
o increase Congwin until loss
o threshold: defines
(congestion)
threshold between two
o loss: decrease Congwin, then
phases:
begin probing (increasing)
• slow start phase
again
• congestion control phase

Transport layer -- May 2004 89

 TCP Slow start
Host A Host B
Slow start algorithm one segm
ent

RTT
initialize: Congwin = 1
for (each segment ACKed) two segm
ents
Congwin++
until (loss event OR
four segm
CongWin > threshold) ents

 exponential increase (per RTT)

in window size (not so slow!)
 loss event: timeout (Tahoe
time
TCP) and/or three duplicate
ACKs (Reno TCP)

Transport layer -- May 2004 90

 TCP Congestion Avoidance

Congestion avoidance
/* slowstart is over */
/* Congwin > threshold */
Until (loss event) {
every w segments ACKed:
Congwin++
}
threshold = Congwin/2
Congwin = 1
1
perform slowstart
1: TCP Reno skips slowstart (fast
recovery) after three duplicate ACKs
Transport layer -- May 2004 91
TCP congestion control

Transport layer -- May 2004 92

 TCP timer management
 How long should the timeout interval be?
o Data link: expected delay predictable
o Transport: different environment; impact of
• Host
• Network (routers, lines)
unpredictable
 Consequences
o Too small: unnecessary retransmissions
o Too large: poor performance
 Solution: adjust timeout interval based on continuous
measurements of network performance
Transport layer -- May 2004 93
TCP timer management

Data link layer Transport layer

Transport layer -- May 2004 94

 TCP timer management
 Algorithm of Jacobson:
Timeout = RTT + 4 * D
o RTT = best current estimate of the round-trip time
o D = mean deviation (cheap estimator of the standard
variance)
o 4?
• Less than 1% of all packets come in more than 4 standard
deviations late
• Easy to compute

Transport layer -- May 2004 95

 TCP timer management
 Algorithm of Jacobson:
Timeout = RTT + 4 * D
o RTT =  RTT + (1 -) M  = 7/8
M = last measurement of round-trip time

o D =  D + (1 - ) RTT - M
 Karn’s algorithm: how handle retransmitted segments?
o Do not update RTT for retransmitted segments
o Double timeout

Transport layer -- May 2004 96

 TCP timer management
 Other timers:
o Persistence timer
• Problem: lost window update packet when window is 0
• Sender transmits probe; receivers replies with window size
o Keep alive timer
• Check whether other side is still alive if connection is idle for
a long time
• No response: close connection
o Timed wait
• Make sure all packets are died off when connection is closed
• =2T

Transport layer -- May 2004 97

 Wireless TCP & UDP
 Transport protocols
o Independent of underlying network layer
o BUT: carefully optimized for wired networks
o Assumption:
• Packet loss caused by congestion
• Invalid for wireless networks: always loss of packets
 Congestion algorithm:
o Timeout ( = congestion)  slowdown
Wireless: Lower throughput – same loss  NO solution

 Solution for wireless networks:

o Retransmit asap
Transport layer -- May 2004 98
 Wireless TCP
 Heterogeneous networks

 Solutions?
o Retransmissions can cause congestion in wired network

Transport layer -- May 2004 99

 Wireless TCP
 Solutions for heterogeneous networks
o Indirect TCP
+ 2 homogeneous connections
– violates TCP semantics

Transport layer -- May 2004 100

 Wireless TCP
 Solutions for heterogeneous networks
o Snooping agent at base station

Snooping k e d
nvo
e i
agent
• Cashes segments for mobile host b
• m ay
Retransmits segment if ack is missingm
i t h
• Removes duplicate acks gor
a l
• n requests for segments originating at
Generates selectiveorepeat
i
t
ges
mobile host
Con
Transport layer -- May 2004 101
 Wireless UDP
 UDP = datagram service  loss permitted
no problems?

 Programs using UDP expect it to be

highly reliable
 Wireless UDP: far from perfect!!!

 Implications for programs recovering from lost

UDP messages

Transport layer -- May 2004 102

 Transactional TCP
 How to implement RPC?
o On top of UDP?
o Yes if
• Request and reply fit in a single packet
• Operations are idempotent
o Otherwise
• Reimplementation of reliability

o On top of TCP?

Transport layer -- May 2004 103

 Transactional TCP
How to implement RPC?
 On top of UDP?
o Yes if
• Request and reply fit in a single
packet
• Operations are idempotent
o Otherwise
• Reimplementation of reliability
 On top of TCP?
o Unattractive because of connection
set up
 Solution: transactional TCP

Transport layer -- May 2004 104

Transactional TCP
How to implement RPC?
 On top of UDP?
o Problems withreliability
 On top of TCP?
o Overhead of connection set up
 Solution: transactional TCP
o Allow data transfer during setup
o Immediate close of stream

Transport layer -- May 2004 105

Computer Networks

Transport layer

Transport layer -- May 2004 106