Transcript TCP and UDP

Reliable Byte-Stream (TCP)
Outline
Connection Establishment/Termination
Sliding Window Revisited
Flow Control
Adaptive Timeout
Read: Sections 5.1 - 5.2
Spring 2008
CPE 0907422 Computer Networks
1
Transport Layer
Our goals:
• understand principles
behind transport
layer services:
– multiplexing/demulti
plexing
– reliable data transfer
– flow control
– congestion control
Spring 2008
• learn about transport layer
protocols in the Internet:
– UDP: connectionless
transport
– TCP: connection-oriented
transport
– TCP congestion control
CPE 0907422 Computer Networks
2
End-to-End Protocols
• Underlying best-effort network
–
–
–
–
–
drop messages
re-orders messages
delivers duplicate copies of a given message
limits messages to some finite size
delivers messages after an arbitrarily long delay
• Common end-to-end services
–
–
–
–
–
–
–
guarantee message delivery
deliver messages in the same order they are sent
deliver at most one copy of each message
support arbitrarily large messages
support synchronization
allow the receiver to flow control the sender
support multiple application processes on each host
Spring 2008
CPE 0907422 Computer Networks
3
Transport services and protocols
• provide logical
communication between app
processes running on
different hosts
• transport protocols run in end
systems
application
transport
network
data link
physical
– send side: breaks app messages into
segments, passes to network layer
– rcv side: reassembles segments into
messages, passes to app layer
application
transport
network
data link
physical
• more than one transport
protocol available to apps
– Internet: TCP and UDP
Spring 2008
CPE 0907422 Computer Networks
4
Internet transport-layer protocols
• reliable, in-order delivery
(TCP)
application
transport
network
data link
physical
– congestion control
– flow control
– connection setup
• unreliable, unordered
delivery: UDP
– no-frills extension of “besteffort” IP
• services not available:
network
data link
physical
network
data link
physical
network
data link
physicalnetwork
network
data link
physical
data link
physical
network
data link
physical
application
transport
network
data link
physical
– delay guarantees
– bandwidth guarantees
Spring 2008
CPE 0907422 Computer Networks
5
User Datagram Protocol, UDP: Simple Demultiplexor
• Extends host-to-host delivery service of underlying network
into a process-to-process communication service
• Adds Demultiplexing
– allowing multiple application processes on each host to share
network
• UDP adds no other functionality to the best-effort service
provided by underlying network
– Unreliable and unordered datagram service
– No flow control
Spring 2008
CPE 0907422 Computer Networks
6
User Datagram Protocol, UDP: Simple Demultiplexor
• Endpoints identified by ports
– servers have well-known ports
 e.g. mail server: port 25
0
16
31
SrcPort
DstPort
Length
Checksum
Data
Header Format
• Optional checksum
– UDP header + data + pseudo header
 pseudoheader: from the IP header( Protocol number; source &
destination IP addresses) + UDP length field
 used to verify message delivered between the correct two
endpoints
» Example: Destination IP address modified
» packet misdelivered; would be detected by UDP
checksum
Spring 2008
CPE 0907422 Computer Networks
7
TCP Overview
• Connection-oriented
• Byte-stream
• Full duplex
• Flow control: keep sender
from overrunning receiver
• Congestion control: keep
sender from overrunning
network
– app writes bytes
– TCP sends segments
– app reads bytes
Application process
Application process
Write
bytes
Read
bytes
TCP
TCP
Send buffer
Receive buffer
Segment
Segment ■ ■ ■ Segment
Transmit segments
Spring 2008
CPE 0907422 Computer Networks
8
Sockets
Socket: a door between application process and end-endtransport protocol (UCP or TCP)
controlled by
application
developer
controlled by
operating
system
process
process
socket
TCP with
buffers,
variables
internet
controlled by
operating
system
host or
server
host or
server
Spring 2008
socket
TCP with
buffers,
variables
controlled by
application
developer
CPE 0907422 Computer Networks
9
Multiplexing/demultiplexing
Multiplexing at send host:
gathering data from multiple
sockets, enveloping data with
header (later used for
demultiplexing)
Demultiplexing at rcv host:
delivering received segments
to correct socket
= socket
application
transport
network
link
= process
P3
P1
P1
application
P2
transport
network
P4
application
transport
network
link
link
physical
host 1
Spring 2008
physical
host 2
CPE 0907422 Computer Networks
physical
host 3
10
Connectionless demux (cont)
P2
P1
P1
P3
SP: 6428
SP: 6428
DP: 9157
DP: 5775
SP: 9157
client
IP: A
SP: 5775
DP: 6428
server
IP: C
DP: 6428
Client
IP:B
SP provides “return address”
Spring 2008
CPE 0907422 Computer Networks
11
Using Sliding Window Algorithm:
Transport Versus Data Link Layer
• Potentially connects many different hosts
– need explicit connection establishment and termination
• Potentially different RTT
– need adaptive timeout mechanism
• Potentially long delay in network
– need to be prepared for arrival of very old segments
• Potentially different capacity at destination
– need to accommodate different node capacity (flowcontrol)
• Potentially different network capacity
– need to be prepared for network congestion
Spring 2008
CPE 0907422 Computer Networks
12
Segment Format
0
10
4
16
31
SrcPort
DstPort
SequenceNum
Acknow ledgment
HdrLen
0
Flags
AdvertisedWindow
Checksum
UrgPtr
Options (variable)
Data
Spring 2008
CPE 0907422 Computer Networks
13
Segment Format (cont)
• Each connection identified with 4-tuple:
– (SrcPort, SrcIPAddr, DsrPort, DstIPAddr)
• Sliding window (reliable transmission) + flow control
– acknowledgment(Num), SequenceNum,
AdvertisedWinow
Data (SequenceNum)
Receiver
Sender
Acknow ledgment +
AdvertisedWindow
• Flags
10
4
16
31
SrcPort
DstPort
SequenceNum
Acknow ledgment
– SYN, FIN, RESET, PUSH, URG, ACK
• Checksum
HdrLen
0
Flags
AdvertisedWindow
Checksum
UrgPtr
Options (variable)
– pseudo header + TCP header + data
Spring 2008
0
CPE 0907422 Computer Networks
Data
14
Segment Format (cont I)
• Flags
– SYN, FIN: used when establishing and terminating a TCP
connection
– RESET: receiver wants to abort the connection
– PUSH: the sender invoked the push operation
 the receiving side of TCP should notify the receiving process of
– URG: segment contains urgent data
 UrgPtr field indicates where the nonurgent data contained in this
segment begins.
10
0
4
16
– ACK: set any time Acknowledgment field
SrcPort
DstPort
SequenceNum
is valid
Acknow ledgment
HdrLen
• Checksum
Flags
AdvertisedWindow
Checksum
– pseudo header + TCP header + data
Spring 2008
0
CPE 0907422 Computer Networks
UrgPtr
Options (variable)
Data
15
31
Establishing A Connection
Server
Client
SYN
ISN=X
1
ACK=Y+1
Spring 2008
time
2
SYN
ISN=Y ACK=X+1
3
CPE 0907422 Computer Networks
16
TCP 3-way handshake
1
Client: “I want to talk, and I’m starting with byte number
X+1”.
2
Server: “OK, I’m here and I’ll talk. My first byte will be
called number Y+1, and I know your first byte will be
number X+1”.
3
Client: “Got it - you start at byte number Y+1”.
Spring 2008
CPE 0907422 Computer Networks
17
Termination
• The TCP layer can send a RST segment that
terminates a connection if something is wrong.
• Usually when one of the two application processes
is finished using the connection it tells TCP to
terminate the connection
– TCP will send a FIN segment
Spring 2008
CPE 0907422 Computer Networks
18
FIN
• Either end of the connection can initiate
termination.
• A FIN sent means the application is done sending
data.
• The FIN is ACK’d.
• The other end must now send a FIN.
• That FIN must be ACK’d.
Spring 2008
CPE 0907422 Computer Networks
19
Terminating A Connection
App1
FIN
SN=X
1
2
...
ACK=X+1
App2
Spring 2008
FIN
SN=Y
3
ACK=Y+1
4
CPE 0907422 Computer Networks
20
TCP Termination
1
App1: “I have no more data for you”.
2
App2: “OK, I understand you are done sending.”
……. pause…
3
App2: “OK - Now I’m also done sending data”.
4
App1: “I understand , Goodbye”
Spring 2008
CPE 0907422 Computer Networks
21
State Transition Diagram
• A rectangle denotes a state that one end of a TCP
connection can find itself in
• A connection end moves from state to state
according to the arcs in the diagram
• An arc is labeled with a tag of event/action
• Connection ends start in the CLOSED state
• Two kinds of events trigger a state transition
(1) A segment arrives from peer
(2) The local application process invokes an operation on
TCP
Spring 2008
CPE 0907422 Computer Networks
22
State Transition Diagram I
CLOSED state to the
ESTABLISHED
1.
2.
3.
4.
5.
Server process invokes a passive
open operation on TCP
 TCP connection moves to
LISTEN
Client process invokes an active
open operation on TCP
 Client end of connection sends
a SYN to server and moves to
SYN_SENT
SYN arrives at server end
 Server end moves to
SYN_RCVD /responds with a
SYN+ACK
SYN+ACK arrives @ client
 Client end moves to
ESTABLISHED and sends
ACK
ACK arrives at server end
 Server end moves to
ESTABLISHED
Spring 2008
CLOSED
Active open /SYN
Passive open
Close
Close
LISTEN
SYN_RCVD
SYN/SYN + ACK
Send /SYN
SYN/SYN + ACK
ACK
SYN + ACK/ACK
ESTABLISHED
Close/FIN
Close /FIN
FIN/ACK
FIN_WAIT_1
ACK
FIN_WAIT_2
SYN_SENT
CLOSE_WAIT
AC FIN/ACK
K
+
FI
N/
AC
K
FIN/ACK
CPE 0907422 Computer Networks
Close/FIN
CLOSING
ACK Timeout after tw o
segment lifetimes
TIME_WAIT
LAST_ACK
ACK
CLOSED
23
State Transition Diagram II
1.
CLOSED state to the
ESTABLISHED : Notes
If the client’s ACK to the server
is lost
CLOSED
Active open /SYN
Passive open
Close
Close
•
Client side is in ESTABLISHED
•
Client process sends data
segments with ACK flag set, and
correct value in the
Acknowledgment field
•
LISTEN
SYN_RCVD
SYN/SYN + ACK
Send /SYN
SYN/SYN + ACK
ACK
SYN + ACK/ACK
ESTABLISHED
Close/FIN
Server moves to
ESTABLISHED when first data
segment arrives
Close /FIN
FIN_WAIT_2
CLOSE_WAIT
AC FIN/ACK
K
+
FI
N/
AC
K
FIN/ACK
Spring 2008
FIN/ACK
FIN_WAIT_1
ACK
SYN_SENT
CPE 0907422 Computer Networks
Close/FIN
CLOSING
ACK Timeout after tw o
segment lifetimes
TIME_WAIT
LAST_ACK
ACK
CLOSED
24
State Transition Diagram III
2.
CLOSED state to the
ESTABLISHED : Notes
There is a transition out of the
LISTEN state whenever local
process invokes a send operation
on TCP
CLOSED
Active open /SYN
Passive open
Close
Close
•
LISTEN
This is a feature of TCP that no
application process actually
takes advantage of
SYN_RCVD
3.
•
•
•
There are arcs not shown
States involving sending a
segment also schedule a timeout
that eventually could causes the
segment to be resent
These retransmissions are not
depicted in the state transition
diagram.
After several retransmissions,
TCP returns to the CLOSED
state terminating a connection
Spring 2008
SYN/SYN + ACK
Send /SYN
SYN/SYN + ACK
ACK
SYN + ACK/ACK
ESTABLISHED
Close/FIN
Close /FIN
FIN/ACK
FIN_WAIT_1
ACK
FIN_WAIT_2
SYN_SENT
CLOSE_WAIT
AC FIN/ACK
K
+
FI
N/
AC
K
FIN/ACK
CPE 0907422 Computer Networks
Close/FIN
CLOSING
ACK Timeout after tw o
segment lifetimes
TIME_WAIT
LAST_ACK
ACK
CLOSED
25
State Transition Diagram IV
CLOSED
ESTABLISHED state to the
CLOSED
1.
This side closes first:
ESTABLISHED >>
FIN_WAIT_1 >>
FIN_WAIT_2 >> TIMEWAIT
>> CLOSED
Active open /SYN
Passive open
Close
Close
LISTEN
SYN_RCVD
SYN/SYN + ACK
Send /SYN
SYN/SYN + ACK
ACK
2.
The other side closes first:
ESTABLISHED >>
CLOSE_WAIT >>
LAST_ACK >> CLOSED
SYN + ACK/ACK
ESTABLISHED
Close/FIN
Close /FIN
3.
4.
Both sides close at the same
time:
ESTABLISHED >>
FIN_WAIT_1 >> CLOSINC
>> TIME_WAIT >> CLOSED.
FIN_WAIT_1 to
TIME_WAIT (Exercise 4.4)
Spring 2008
FIN/ACK
FIN_WAIT_1
ACK
FIN_WAIT_2
SYN_SENT
CLOSE_WAIT
AC FIN/ACK
K
+
FI
N/
AC
K
FIN/ACK
Close/FIN
CLOSING
ACK Timeout after tw o
segment lifetimes
TIME_WAIT
CPE 0907422 Computer Networks
LAST_ACK
ACK
CLOSED
26
State Transition Diagram V
CLOSED
TIME _WAIT:
•
A connection in the TIME_WAIT
state waits for two times the
maximum amount of time an IP
datagram might live in the Internet
(i.e., 120 seconds)
Necessary because:
•
Local side of the connection sent
an ACK in response to the other
side’s FIN
•
If other side retransmits FIN and it
is delayed in network
•
If the connection were allowed to
move directly to the CLOSED
state, then another pair of
application processes might open
the same connection
•
Then, delayed FIN would
immediately initiate the
termination of the second
incarnation of connection
Spring 2008
Active open /SYN
Passive open
Close
Close
LISTEN
SYN_RCVD
SYN/SYN + ACK
Send /SYN
SYN/SYN + ACK
ACK
SYN + ACK/ACK
ESTABLISHED
Close/FIN
Close /FIN
FIN/ACK
FIN_WAIT_1
ACK
FIN_WAIT_2
SYN_SENT
CLOSE_WAIT
AC FIN/ACK
K
+
FI
N/
AC
K
FIN/ACK
Close/FIN
CLOSING
ACK Timeout after tw o
segment lifetimes
TIME_WAIT
CPE 0907422 Computer Networks
LAST_ACK
ACK
CLOSED
27
Reliability in TCP
• Checksum used to detect bit level errors
• Sequence numbers used to detect sequencing errors
– Duplicates are ignored
– Out of order segments are reordered (or dropped)
– Lost segments are retransmitted
• Timeouts used to detect lost segments
– Requires RTT calculation
– Requires sender to maintain data until it is ACKed
Spring 2008
CPE 0907422 Computer Networks
28
Sliding Window in TCP
• Guarantees reliable delivery of data
• Ensures data is delivered in order
• Enforces flow control
Spring 2008
CPE 0907422 Computer Networks
29
Sliding Window: Reliable and Ordered Delivery
Sending application
Receiving application
TCP
LastByteWritten
LastByteAcked
LastByteSent
(a)
NextByteExpected
LastByteRcvd
(b)
• Sending side
• Receiving side
– LastByteAcked < =
LastByteSent
– LastByteSent < =
LastByteWritten
– buffer bytes between
LastByteAcked and
LastByteWritten
Spring 2008
TCP
LastByteRead
– LastByteRead <
NextByteExpected
– NextByteExpected < =
LastByteRcvd + 1
– buffer bytes between
LastByteRead and
LastByteRcvd
CPE 0907422 Computer Networks
30
Sliding Window: Flow Control
• Receiver advertises a window size to the sender in the
AdvertisedWindow field in the TCP header
• Sender is limited to having no more than a value of
AdvertisedWindow bytes of unacknowledged data at
any given time
• Receiver selects a suitable value for
AdvertisedWindow based on the amount of memory
allocated to the connection for the purpose of buffering
data
 Keeps the sender from overrunning the receiver’s
buffer
Spring 2008
CPE 0907422 Computer Networks
31
Sliding Window: Flow Control (cont. I)
Sending application
Receiving application
TCP
LastByteWritten
LastByteAcked
LastByteSent
(a)
TCP
LastByteRead
NextByteExpected
LastByteRcvd
(b)
• Send buffer size: MaxSendBuffer
• Receive buffer size: MaxRcvBuffer
• Receiving side
– LastByteRcvd - LastByteRead < = MaxRcvBuffer
– AdvertisedWindow = MaxRcvBuffer (NextByteExpected - LastByteRead)
Spring 2008
CPE 0907422 Computer Networks
32
Sliding Window: Flow Control (cont. II)
Sending application
Receiving application
TCP
LastByteWritten
LastByteAcked
• Sending side
LastByteSent
(a)
TCP
LastByteRead
NextByteExpected
LastByteRcvd
(b)
– LastByteWritten - LastByteAcked < = MaxSendBuffer
– LastByteSent - LastByteAcked < = AdvertisedWindow
– EffectiveWindow = AdvertisedWindow - (LastByteSent LastByteAcked)
 EffectiveWindow = 0 if AdvertisedWindow = 0
– EffectiveWindow limits amount of data that can be sent without waiting for
acknowledgment
– Receiver throttles sender by advertising a window that is no larger than the
amount of data it can buffer
Spring 2008
CPE 0907422 Computer Networks
33
Sliding Window: Flow Control (cont. III)
Sending application
Receiving application
TCP
LastByteWritten
LastByteAcked
• Sending side
LastByteSent
(a)
TCP
LastByteRead
NextByteExpected
LastByteRcvd
(b)
– block sender if tries to write y bytes but
(LastByteWritten - LastByteAcked) + y >
MaxSenderBuffer
Spring 2008
CPE 0907422 Computer Networks
34
Sliding Window: Flow Control (cont. IV)
Sending application
Receiving application
TCP
LastByteWritten
LastByteAcked
LastByteSent
(a)
TCP
LastByteRead
NextByteExpected
LastByteRcvd
(b)
• Always send ACK in response to arriving data segment
• Sending side
– Persist when AdvertisedWindow = 0
send a segment with 1 byte of data every so often which
triggers a response that contains the current advertised
window (eventually nonzero)
Spring 2008
CPE 0907422 Computer Networks
35
Triggering Transmission:
If flow control is ignored (i.e. assume the receiver
window is wide open), then a segment is sent when
any of the three following conditions occur:
1. MSS bytes are collected from sending process
– MSS set to size of largest segment TCP can send without
causing the local IP to fragment
 MSS = MTU of directly connected physical network
– (TCP & IP header)
2. Sending process invokes a push operation to flush
the buffer of unsent bytes
3. A timer fires
– segment contains as many bytes as are currently buffered
for transmission
Spring 2008
CPE 0907422 Computer Networks
36
Silly Window Syndrome
• Sender is accumulating bytes
– Receiver window is closed
• An ACK arrives
– Opens window enough for sender to transmit MSS/2 bytes
• Should sender transmit a half-full segment or wait for
window to open to a full MSS?
• Taking advantage of any available window leads to a
situation now known as the silly window syndrome
Spring 2008
CPE 0907422 Computer Networks
37
Silly Window Syndrome (cont.)
• How aggressively does sender exploit open window?
• Think of TCP stream a conveyer belt with “full”
containers (data segments) going in one direction
and empty containers (ACKs) going in the reverse
direction
– MSS-sized segments correspond to large containers
– 1-byte segments correspond to very small containers
Spring 2008
CPE 0907422 Computer Networks
38
Silly Window Syndrome (cont.I)
• sender fills an empty container as soon as it arrives
– small containers introduced into the system remain in the
system indefinitely
It is immediately filled and emptied at each end
Never coalesced with adjacent containers to create
larger containers
• Silly window syndrome is only a problem when
– Sender transmits a small segment
– Receiver opens the window a small amount
• It’s not possible to outlaw sending small segments
– application might do a push after sending a single byte
Spring 2008
CPE 0907422 Computer Networks
39
Silly Window Syndrome Solutions
Sender
Receiver
• Receiver-side solutions
– after advertising zero window, wait for space
equal to a maximum segment size (MSS) before it
advertises an open window
– delayed acknowledgements (mechanisms to
coalesce small segments)
receiver has no way of knowing how long to
wait
Spring 2008
for another segment to arrive
for the application to read more data (thus opening
the window)
CPE 0907422 Computer Networks
40
Nagle’s Algorithm
How long does the sender delay sending data?
– Use a timer and transmit when timer expires.
How long is the timer set?
too long: hurts interactive applications
(e.g. telnet)
too short: poor network utilization
Spring 2008
CPE 0907422 Computer Networks
41
Nagle’s Algorithm (continued)
• Answer to: “how long does the sender delay
sending data?”
• Self-clocking :
When application generates additional data
– if (both available data and window >
MSS) send a full segment
– else
 if (there is unack’ed data in transit) buffer it
until ACK arrives
42
else: send it
Nagle’s Algorithm (cont.I)
• Interactive application like Telnet will send
data at a rate of one segment per RTT
– Some segments will contain a single byte
– Others will contain as many bytes as the user
was able to type in one round-trip time
Spring 2008
CPE 0907422 Computer Networks
43
Nagle’s Algorithm (cont.II)
• Socket interface allows applications to turn
off Nagle’s algorithm by setting the TCP
NO_DELAY option
– data is transmitted as soon as possible
Spring 2008
CPE 0907422 Computer Networks
44
Protection Against Wrap Around
• Segments sequence numbers take values from
the set {0, 1, 2, …., (232 - 1)}
• During the life time of a TCP connection, if
the sequence number wraps around [i.e. {0, 1,
2, …., (232 - 1), 0, 1, 2, ….} then
– a byte with sequence number x could be
sent at one time and at a later time a
different byte with the same sequence
number x will be sent.
The second byte will be discarded
Spring 2008
CPE 0907422 Computer Networks
45
Protection Against Wrap Around (cont.)
• Packets cannot survive for longer than
MSL
– Make sure sequence number does not
wrap around within a 120-second
i.e. separate the use of the same
sequence # by at least 120-second
Spring 2008
CPE 0907422 Computer Networks
46
Protection Against Wrap Around (cont )
• 32-bit SequenceNum
Bandwidth
T1 (1.5 Mbps)
Ethernet (10 Mbps)
T3 (45 Mbps)
FDDI (100 Mbps)
STS-3 (155 Mbps)
STS-12 (622 Mbps)
STS-24 (1.2 Gbps)
Spring 2008
Time Until Wrap Around
6.4 hours
57 minutes
13 minutes
6 minutes
4 minutes
55 seconds
28 seconds
CPE 0907422 Computer Networks
47
Keeping the Pipe Full
• AdvertisedWindow must be big enough to allow the sender
to keep the pipe full
• 16-bit AdvertisedWindow allows a window of only 64 KB
Bandwidth
T1 (1.5 Mbps)
Ethernet (10 Mbps)
T3 (45 Mbps)
FDDI (100 Mbps)
STS-3 (155 Mbps)
STS-12 (622 Mbps)
STS-24 (1.2 Gbps)
Delay x Bandwidth Product
18KB
122KB
549KB
1.2MB
1.8MB
7.4MB
14.8MB
assuming 100ms RTT
Spring 2008
CPE 0907422 Computer Networks
48
TCP Extensions
• Implemented as header options
• Because of the HdrLen field in TCP header the
header can be of variable length
Variable part of TCP header contains the options
that have been added
• Hosts can still communicate using TCP even if
they do not implement the options.
Spring 2008
CPE 0907422 Computer Networks
49
TCP Extensions: Protection Against
Wrap Around
• 32-bit timestamp used to effectively extend the
sequence number space
• TCP decides whether to accept or reject a segment
based on a 64-bit identifier
– the SequenceNum field in low-order 32 bits
– timestamp in the high-order 32 bits
• Timestamp is always increasing
– distinguishes between two different incarnations of the
same sequence number
Spring 2008
CPE 0907422 Computer Networks
50
TCP Extensions: Advertise A Larger
Window (to keep the pipe full)
Shift (scale) advertised window
• An option defines a scaling factor for the advertised
window
• Two sides of TCP to agree that AdvertisedWindow field
counts chunks of bytes rather than bytes
– e.g., 16-byte units of data
• Window scaling option specifies # of bits each side
should left-shift the AdvertisedWindow field before using
its contents to compute an effective window.
Spring 2008
CPE 0907422 Computer Networks
51
TCP Extensions: Improve TCP’s
Timeout Mechanism
Improve measurement of RTT:
• Store timestamp in outgoing segments
– TCP put actual system clock “32-bit time- stamp” in
the segment’s header.
• Receiver echoes this timestamp back to sender in
acknowledgment
• Sender subtracts timestamp from the current time
to measure RTT
Spring 2008
CPE 0907422 Computer Networks
52
Adaptive Retransmission(Original Algorithm)
• Keep a running average of RTT and compute timeout as
a function of this RTT
• Measure SampleRTT for each segment / ACK pair
• Compute an updated EstimatedRTT as a weighted
average between the previous estimate and new sample
–
–


EstRTT = a x EstRTT + b x SampleRTT
where a + b = 1
a between 0.8 and 0.9
b between 0.1 and 0.2
• Set timeout based on EstRTT
– TimeOut = 2 x EstRTT
Spring 2008
CPE 0907422 Computer Networks
53
Karn/Partridge Algorithm
Sender
(a) if you
assume that
the ACK is for
the original
transmission
but it was
really for the
second, then
the
SampleRTT is
too large
Receiver
Orig
Sender
inal
t
r ans
miss
ion
Retr
an
Orig
in
Receiver
al tra
n
smis
sion
ACK
Retr
ansm
smis
sion
ACK
(a)
issio
n
(b)
(b) if you
assume that
the ACK is
for the second
transmission
but it was
actually for
the first, then
the
SampIeRTT is
too small
• Do not sample RTT when retransmitting
• Also, because congestion is the most likely cause of lost
segments
– Double timeout after each retransmission (rather than basing it on the
last EstimatedRTT )
Spring 2008
CPE 0907422 Computer Networks
54