Transcript ppt

Transport Layer
Flow control
Connection management
TCP, UDP
1
Announcements



I hope you had a very happy
Thanksgiving break!
My sincere apologies for the Monday
emergency cancellation!!
SM5 is out. Due in one week.
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
2
Introduction
Transport layer protocols are end-to-end protocols
Transport layer is only implemented at the hosts
HOST
HOST
Application
Application
Transport
Transport
Network
Data Link
Network
Data Link
Network
Data Link
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
Data Link
3
Functions of the Transport Layer





Reliability
Connection Establishment
Connection Termination
Flow control
Congestion control
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
4
Reliability

How to achieve it?
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
5
Reliability

How to achieve it?



Send data in chunks (called packets)
Number the packets sequentially at the sender
Make sure all numbers are received without gaps
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
6
Reliability

How to achieve it?



Send data in chunks (called packets)
Number the packets sequentially at the sender
Make sure all numbers are received without gaps


Acknowledge each packet number
If sender sees an ack gap  sender retransmits
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
7
Reliability

How to achieve it?



Send data in chunks (called packets)
Number the packets sequentially at the sender
Make sure all numbers are received without gaps



Acknowledge each packet number
If sender sees an ack gap  sender retransmits
Optimization: Cumulative acks (ACK N:
acknowledge that all packets up to but not
including packet N have been received).
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
8
Reliability

How to achieve it?



Send data in chunks (called packets)
Number the packets sequentially at the sender
Make sure all numbers are received without gaps




Acknowledge each packet number
If sender sees an ack gap  sender retransmits
Optimization: Cumulative acks (ACK N:
acknowledge that all packets up to but not
including packet N have been received).
What about the number of the first packet?
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
9
Connection Establishment

Connection establishment is asymmetric:


one side puts itself in a LISTEN state (server)
one side issues a request for connection
(client)
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
10
Simple Solution (which has
problems)
Two Way Handshake
Host A

Host B

CR (SeqN
o = x)
ACK (SeqNo =
y)

DATA(SeqN
o = x)
CR (SeqNo = x)
Connection Request, A
wants to start with
SeqNo = x
ACK (SeqNo = y)
Acknowledge request,
B will wants to start
with SeqNo = y
DATA (SeqNo = x)
Data transmission with
SeqNo x
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
11
Problems with Two-Way
Handshake

Host A
Host B
CR
(Seq
No
CR (SeqN
o = x)
= y)
qNo
e
S
(
ACK
DATA(SeqN
o = x)
= z)

B responds to
CR(SeqNo = z), an old
duplicate connection
requests from A
In the shown scenario, A believes that
the ACK is for the
connection request
CR(SeqNo = y)
Result: A starts to send data with Sequence x. B will
throw the data away since it expects SeqNo = z
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
12
Three-Way Handshake

Host A
Host B
CR (SeqN
o = x)
y, ACK = x)
ACK (SeqNo =
DATA(SeqN
o = x, ACK
= y)

Note: A and B
acknowledge the
sequence number
from the other side
This solution
provides protection
from old duplicate
connection requests
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
13
Scenario 1
Duplicate connection request (CR) appears
Host B
Host A
CR
(Seq
No

= z)
CR (SeqN
o = x)
=z)
y, ACK
=
o
N
q
e
CK = x)
A
ACK (S
,
u
=
eqNo
ACK (S
REJ (ACK
= y)
DATA(S
eqNo =
x, ACK
= u)

Host A rejects the
invalid connection
request in the
REJ(ACK=y)
packet
Note: The
connection request
CR(SeqNo=x) is
completed
successfully
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
14
Scenario 2
A duplicate acknowledgement (ACK) appears
Host B
Host A
z)
CR (SeqN
o = x)
S
K(
C
A
eqN
o=
ACK
y, A

=
CK
= u, A
(SeqNo
CK = x)
REJ (ACK
DATA(S
eqNo =
x
, ACK =
u)

= y)
Host A rejects the
invalid ACK by
sending
REJ(ACK=y)
Note: The
connection request
CR(SeqNo=x) is
completed
successfully
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
15
Connection Termination

A connection release should involve both sides of the
connection (otherwise data is lost)
Host A
Host B
CR ()
ACK ()
DATA()
Here: B should wait
after Disconnection
Request (DR) is sent
until all data has arrived
DATA()
DATA()
DATA()
DR ()
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
16
Connection Termination in 4
steps



An elegant way to terminate connections is to
have each end shut down independently (“halfclose”)
If one end wants to shut down, it sends a DR
message
Four steps involved:
(1) A sends a DR to B (active close)
(2) B ACKs the DR,
(at this time: B can still send data to A)
(3) and B sends a DR to A (passive close)
(4) A ACKs the DR
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
17
Connection Termination in 4
steps
Host B
Host A
DR
A CK
To account for packet
losses, a timer is
needed to limit the
waiting time of a side
DR
ACK
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
18
TCP Segment Format
• TCP segments have a 20 byte header with >= 0 bytes of data.
IP header TCP header
20 bytes
TCP data
20 bytes
0
15 16
Source Port Number
31
Destination Port Number
Sequence number (32 bits)
header
length
0
Flags
TCP checksum
20 bytes
Acknowledgement number (32 bits)
window size
urgent pointer
Options (if any)
DATA
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
19
Flow Control

Notion of window-based flow control:



Have a window of packets ready for
transmission
Can send only those packets that are in the
window up to the end of the window
Every time an acknowledgement is
received, window slides (and its size may
be increased).
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
20
Flow Control


Flow Control is a technique for speed-matching
of transmitter and receiver. Flow control
ensures that a transmitting station does not
overflow a receiving station with data
We will discuss two protocols for flow control:




Stop-and-Wait
On-Off
Sliding Window
For the time being, we assume that we have a
perfect channel (no errors)
21
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
Stop-and-Wait Flow Control



Simplest form of flow control
In Stop-and-Wait flow control, the receiver
indicates its readiness to receive data for
each frame
Operations:
1. Sender: Transmit a single frame
2. Receiver: Transmit acknowledgment (ACK)
3. Goto 1.
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
22
Analysis of Stop-and-Wait
End of Transmit of
ACK
Last bit received
Receiver
propagation
delay
Frame
Frame
ACK
Efficiency = ?
ACK
Sender
transmission
delay
Start Transmit
End Transmit
Last bit of ACK received
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
23
Sliding Window Flow Control

Sliding Window Flow Control



Allows transmission of multiple frames
Assigns each frame a k-bit sequence number
Range of sequence number is [0..2k-1], i.e.,
frames are counted modulo 2k
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
24
Operation of Sliding Window

Sending Window:

At any instant, the sender is permitted to send
frames with sequence numbers in a certain
range (the sending window)
Frames already
transmitted
Window of frames that may
be transmitted
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6
Frame
sequence
number
Last frame
transmitted
Window shrinks as
frames are sent
Window expands as
acknowledgements are
received
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
25
Operation of Sliding Window

Receiving Window:

The receiver maintains a receiving window
corresponding to the sequence numbers of
frames that are accepted
Frames already received
Window of frames that are
accepted by receiver
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6
Last frame
acknowledged
Window shrinks as
frames are received
Window expands as
acknowledgements are
sent
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
26
Operation of Sliding Window

How is “flow control” achieved?



Receiver can control the size of the sending
window
By limiting the size of the sending window data
flow from sender to receiver can be limited
Interpretation of ACK N message:

Receiver acknowledges all packets until (but not
including) sequence number N
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
27
Example
Receiver
Transmitter
0 1 2 3 4 5 6 7 0 1 2 3
F0
F1
F2
0 1 2 3 4 5 6 7 0 1 2 3
0 1 2 3 4 5 6 7 0 1 2 3
0 1 2 3 4 5 6 7 0 1 2 3
ACK43
0 1 2 3 4 5 6 7 0 1 2 3
0 1 2 3 4 5 6 7 0 1 2 3
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
28
Example Continued
Transmitter
Receiver
0 1 2 3 4 5 6 7 0 1 2 3
F3
0 1 2 3 4 5 6 7 0 1 2 3
F4
F5
F6
0 1 2 3 4 5 6 7 0 1 2 3
0 1 2 3 4 5 6 7 0 1 2 3
ACK3
4 4
0 1 2 3 4 5 6 7 0 1 2 3
0 1 2 3 4 5 6 7 0 1 2 3
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
29
Slow Start

Whenever starting traffic on a new connection, or
whenever increasing traffic after congestion was
experienced:



Set cwnd = MSS bytes (=1 segment)
Each time an ACK is received, slide the congestion window and
increase size by 1 segment (= MSS bytes).
Does Slow Start increment slowly? Not really.
In fact, the increase of cwnd can be exponential
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
30
Slow Start Example


The congestion
window size grows
very rapidly
 For every ACK, we
increase cwnd by
1 irrespective of
the number of
segments ACK’ed
TCP slows down the
increase of cwnd
when
cwnd > ssthresh
cwnd =
1xMSS
segment 1
t1
ACK for segmen
cwnd =
2xMSS
cwnd =
4xMSS
cwnd =
7xMSS
segment 2
segment 3
ts 2
ACK for segmen
ts 3
ACK for segmen
segment 4
segment 5
segment 6
ts 4
ACK for segmen
ts 5
ACK for segmen
ts 6
ACK for segmen
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
31
Slow Start


“Slow Start” slows down if the congestion
window is larger than a threshold value
If cwnd > ssthresh then each time an ACK is
received, increment cwnd as follows:



cwnd = cwnd + MSS * MSS / cwnd
So cwnd is increased by one only if all segments
have been acknowledged.
ssthresh is modified if there is congestion in the
network
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
32
Slow Start Example
cwnd = 1
Assume that
cwnd = 2
ssthresh = 8
14
cwnd = 4
Cwnd (in segments)
12
10
cwnd = 8
ssthresh
8
6
4
cwnd = 9
2
0
0
t=
2
t=
4
t=
6
t=
Roundtrip times
cwnd = 10
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
33
Slow Start / Congestion
Avoidance

Here we give a more accurate version than in
our earlier discussion of Slow Start:
If cwnd <= ssthresh then
Each time an Ack is received:
cwnd = cwnd + MSS
else /* cwnd > ssthresh */
Each time an Ack is received :
cwnd = cwnd + MSS * MSS / cwnd
endif
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
34
Slow Start / Congestion
Avoidance

Each time when congestion occurs
(timeout or receipt of duplicate ACK),

cwnd is reset to one:


cwnd = 1
ssthresh is set to half the current size of
the congestion window:

ssthressh = cwnd / 2
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
35
Slow Start / Congestion
Avoidance

A typical plot of cwnd for a TCP connection (MSS =
1500 bytes) :
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
36
Round-Trip Time
Measurements


The retransmission mechanism of TCP is adaptive
The retransmission timers are set based on roundtrip time (RTT) measurements that TCP performs
Segment 1
RTT #1
ent 1
ACK for Segm
Segment 2
Segment 3
RTT #2
egment 2
ACK for S
Segment
5
RTT #3
The RTT is based on time
difference between segment
transmission and receipt of ACK
But:
TCP does not ACK each
segment
Each connection has only
one timer
+3
Segme
nt 4
egment 4
ACK for S
egment 5
ACK for S
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
37
Round-Trip Time
Measurements



Retransmission timer is set to a Retransmission
Timeout (RTO) value
RTO is calculated based on the RTT measurements
The RTT measurements are smoothed by the following
estimators srtt and rttvar:
srttn+1 = a RTT + (1- a ) srttn
rttvarn+1 = b ( | RTT - srttn+1 | ) + (1- b ) rttvarn
RTOn+1 = srttn+1 + 4 rttvarn+1

The gains are set to a =1/4 and b =1/8

srtt0 = 0 sec, rttvar0 = 3 sec, Also: RTO0 = srtt0 + 2 rttvar0
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
38
TCP header fields

Port Number:



A port number identifies the endpoint of a connection.
A pair <IP address, port number> identifies one endpoint of a
connection.
Two pairs <client IP address, server port number> and
<server IP address, server port number> identify a TCP
connection.
Applications
Ports:
23 80 104
Applications
7
80 16
TCP
TCP
IP
IP
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
Ports:
39
TCP header fields

Sequence Number (SeqNo):


Sequence number is 32 bits long.
So the range of SeqNo is



0 <= SeqNo <= 232 -1  4.3 Gbyte
Each sequence number identifies a byte in the
byte stream
Initial Sequence Number (ISN) of a connection is
set during connection establishment
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
40
TCP header fields

Acknowledgement Number (AckNo):



Acknowledgements are piggybacked
A hosts uses the AckNo field to send
acknowledgements. (If a host sends an AckNo in a
segment it sets the “ACK flag”)
The AckNo contains the next SeqNo that a hosts
wants to receive
Example: The acknowledgement for a segment
with sequence numbers 0-1500 is AckNo=1501
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
41
TCP header fields

Flag bits:

URG: Urgent pointer is valid



If the bit is set, the following bytes contain an urgent
message in the sequence number range “SeqNo <=
urgent message <= SeqNo+urgent pointer”
ACK: Segment carries a valid acknowledgement
PSH: PUSH Flag


Notification from sender to the receiver that the receiver
should pass all data that it has to the application.
Normally set by sender when the sender’s buffer is empty
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
42
TCP header fields

Flag bits:

RST: Reset the connection



SYN: Synchronize sequence numbers


The flag causes the receiver to reset the connection
Receiver of a RST terminates the connection and indicates
higher layer application about the reset
Sent in the first packet when initiating a connection
FIN: Sender is finished with sending


Used for closing a connection
Both sides of a connection must send a FIN
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
43
TCP States in Connection
Lifetime
SYN_SENT
(active open)
SYN (SeqNo = x)
No = x + 1 )
k
c
A
,
y
=
o
N
q
SYN (Se
LISTEN
(passive open)
SYN_RCVD
(AckNo = y + 1 )
EST ABLISHED
EST ABLISHED
FIN_WAIT_1
(active close)
FIN_WAIT_2
T IME_WAIT
FIN (SeqNo = m)
(AckNo = m+ 1 )
CLOSE_WAIT
(passive close)
FIN (SeqNo = n )
(AckNo =
LAST_ACK
n+1)
CLOSED
Copyright Jorg Liebeherr 98, Modified with permission, Abdelzaher
44