11/28/12

The Problem
•  Given: Best-effort network in which
– Packets may be lost arbitrarily
– Packets may be reordered arbitrarily
– Packet delays are variable (queueing)
– Packets may even be duplicated

•  Sender S and receiver R want to communicate reliably

– Application at R wants all data bytes in exactly the same
6.02 Fall 2012 order that S sent them
– Each byte must be delivered exactly once
Lecture #21: Reliable Data Transport
•  These functions are provided by a reliable transport
•  Redundancy via careful retransmission
protocol
•  Sequence numbers & acks
•  Two protocols: stop-and-wait & sliding window – Application layered above transport protocol
•  Timeouts and round-trip time (RTT) estimation

6.02 Fall 2012 Lecture 21, Slide #1 6.02 Fall 2012 Lecture 21, Slide #2

Proposed Plan Stop-and-Wait Protocol

•  Transmitter Sender Receiver S R S R
Data
– Each packet includes a sequentially increasing sequence number 1
– When transmitting, save (xmit time,packet) on un-ACKed list Data Data
1 1
– When acknowledgement (ACK) is received from the destination 1 1
ACK
for a particular sequence number, remove the corresponding RTT X
entry from un-ACKed list Data
2 X

R TT = round-trip time
– Periodically check un-ACKed list for packets sent awhile ago
•  Retransmit, update xmit time in case we have to do it again! 2
ACK Timeout Data
•  “awhile ago”: xmit time < now  timeout 1
Data Retransmit
3
Data
•  Receiver 1
1
3 ACK
– Send ACK for each received packet, reference sequence number ACK
– Deliver packet payload to application

Normal behavior Data loss + Duplicate

(no losses) retransmission packet reception

Wanted “exactly once”, got “at least once”

6.02 Fall 2012 Lecture 21, Slide #3 6.02 Fall 2012 Lecture 21, Slide #4

1
 11/28/12

Revised Plan Issues

•  Transmitter •  Protocol must handle lost packets correctly
– Each packet includes a sequentially increasing sequence number – Lost data: retransmission will provide missing data
– When transmitting, save (xmit time,packet) on un-ACKed list – Lost ACK: retransmission will trigger another ACK from receiver
– When acknowledgement (ACK) is received from the destination
for a particular sequence number, remove the corresponding •  Size of packet buffers
entry from un-ACKed list – At transmitter
– Periodically check un-ACKed list for packets sent awhile ago •  Buffer holds un-ACKed packets
•  Retransmit, update xmit time in case we have to do it again! •  Stop transmitting if buffer space an issue
•  “awhile ago”: xmit time < now  timeout – At receiver
•  Receiver •  Buffer holds packets received out-of-order
– Send ACK for each received packet, reference sequence number •  Stop ACKing if buffer space an issue
– Deliver packet payload to application in sequence number order
•  By keeping track of next sequence number to be delivered to app, it’s •  Choosing timeout value: related to RTT
easy to recognize duplicate packets and not deliver them a second – Too small: unnecessary retransmissions
time.
– Too large: poor throughput
•  Delivery stalled while waiting for missing packets

6.02 Fall 2012 Lecture 21, Slide #5 6.02 Fall 2012 Lecture 21, Slide #6

Throughput of Stop-and-Wait The Best Case

•  We want to calculate the expected time, T (in seconds) •  Occurs when RTT is the same for every packet, so
between successful deliveries of packets. If N data packets timeout is slightly larger than RTT
are sent (N large), the time to send them will be N*T, so
L 1
Throughput = N/NT = 1/T data packets per second T = RTT + RTT = RTT
1− L 1− L
(1− L)
•  We can’t just assume T = RTT because packets get lost Throughput =
– E.g.: N links in the round trip between sender and receiver RTT
– If the per-link probability of losing a data/ACK packet is p, then
the probability it’s delivered over the link is (1-p), and thus the •  If bottleneck link can support 100 packets/sec and the RTT
probability it’s delivered over N links is (1-p)N. is 100 ms, then, using stop-and-wait, the maximum
–  So the probability a data/ACK packet gets lost is L = 1 – (1-p)N. throughput is at most only 10 packets/sec.
– Urk! Only 10% utilization
•  Now we can write an equation for T in terms of RTT and the – We need a better reliable transport protocol…
timeout, RTO: T = (1− L)⋅ RTT + L ⋅ ( RTO + T )
L
= RTT + RTO
1− L
6.02 Fall 2012 Lecture 21, Slide #7 6.02 Fall 2012 Lecture 21, Slide #8

2
 11/28/12

Idea: Sliding Window Protocol Sliding Window in Action

window = 1-5
•  Use a window window = 2-6
SENDER RECEIVER –  Allow W packets outstanding (i.e.,
unack’d) in the network at once 1 2 3 4 5 6
(W is called the window size). Sndr
–  Overlap transmissions with ACKs
a1 a2
•  Sender advances the window by 1 for
each in-sequence ack it receives
– I.e., window slides
– So, idle period reduces Rcvr
– Pipelining p1 p2
•  Assume that the window size, W, is
fixed and known
– Later, we will discuss how one might W = 5 in this example
set it
– W = 3 in the example on the left
6.02 Fall 2012 Lecture 21, Slide #9 6.02 Fall 2012 Lecture 21, Slide #10

Receiver
Sender1 Sender s window size = 5
Sliding Window in Action 2 ACKs
3 1
window = 2-6
window = 3-7 4 2
5 3
1 2 3 4 5 6 7
4
5
Sndr
6
a1 a2 a3 7
8 6
9 XPacket lost 7
TIMEOUT 10
1
Rcvr 9
p1 p2 p3 10
1
1
11
Window definition: If window is W, then max number of 1
12
unacknowledged packets is W
11
1
133 12
RXMIT
This is a fixed-size sliding window 8
144 13
6.02 Fall 2012 Lecture 21, Slide #11 6.02 Fall 2012
012
2 Lecture
Lectu
Lect
L 8
turre
tu e 21,
2 Slide #12

3
 11/28/12

Data/ACK sequence trace

Sliding Window Implementation
"trace2-seq"
680
"trace2-ack" •  Transmitter
– Each packet includes a sequentially increasing sequence number
Data/ACK sequence number

Window – When transmitting, save (xmit time,packet) on un-ACKed list

660
– Transmit packets if len(un-ACKed list) ≤ window size W
Ks
AC – When acknowledgement (ACK) is received from the destination
ta for a particular sequence number, remove the corresponding
Da
640
entry from un-ACKed list
RTT – Periodically check un-ACKed list for packets sent awhile ago
620 •  Retransmit, update xmit time in case we have to do it again!
RTO
•  “awhile ago”: xmit time < now  timeout
•  Receiver
600
Rxmit ACKs for rxmitted
– Send ACK for each received packet, reference sequence number
packets (most probably)
– Deliver packet payload to application in sequence number order
580 •  Save delivered packets in sequence number order in local buffer
(remove duplicates). Discard incoming packets which have already
been delivered (caused by retransmission due to lost ACK).
560 •  Keep track of next packet application expects. After each reception,
800 820 840 860 880 900
deliver as many in-order packets as possible.
Time (ms)
6.02 Fall 2012 Lecture 21, Slide #13 6.02 Fall 2012 Lecture 21, Slide #14

RTT Measurements

Courtesy of the Cooperative Association for Internet Data Analysis. Used with permission. http://nms.csail.mit.edu/papers/index.php?detail=208
© Association for Computing Machinery. All rights reserved. This content is excluded from our
Creative Commons license. For more information, see http://ocw.mit.edu/fairuse.
6.02 Fall 2012 Lecture 21, Slide #15 6.02 Fall 2012 Lecture 21, Slide #16

4
 11/28/12

RTTs can be highly variable

AT&T Wireless on iPhone 3G Ping Data from Verizon Wireless 3G network
latency
mu: 1697.2 ms
stddev: 2346.5 ms mu: 1554.8 ms
min:155.6 ms stddev: 1563.8 ms
Delay (milliseconds)

max:12126.6 ms min: 82.5 ms

max: 9912.4 ms







17 Time (s)
6.02 Fall 2012 Lecture 21, Slide #17 6.02 Fall 2012 Lecture 21, Slide #18

CDF of RTT over Verizon Wireless 3G Network Estimating RTT from Data
Cumulative probability (CDF)
•  Gather samples of RTT by comparing time when ACK arrives
with time corresponding packet was transmitted
– Sample of random variable with some unknown distribution (not
necessarily Gaussian!)

•  Chebyshev’s inequatility tells us that for a random variable X

Mean > 1.5 seconds with mean µ and finite variance σ2:
Std dev > 1.5 seconds 1
In this data set, P( X − μ ≥ kσ ) ≤
if we pick a timeout k2
of 6 seconds, then – To reduce the chance of a spurious (i.e., unnecessary)
retransmission – packet wasn’t lost, just the round trip time for
P(spurious rxmit) is
packet/ACK was long – we want our timeout to be greater than
about 3%. most observed RTTs
– So choose a k that makes the chances small…
– We need an estimate for µ and σ

2000 4000 6000 RTT value (ms)

6.02 Fall 2012 Lecture 21, Slide #19 6.02 Fall 2012 Lecture 21, Slide #20

5
 11/28/12

Exponential Weighted Moving Average (EWMA)

[A low-pass filter – see frequency response] Response to One Long RTT Sample
srtt ← α*rtt_sample + (1-α)*srtt
|H|

α decreases

α = 0.1 α = 0.5
Responds too quickly?

6.02 Fall 2012 Ω

Lecture 21, Slide #21 6.02 Fall 2012 Lecture 21, Slide #22

RTT changes from 1 to 2 Timeout Algorithm

•  EWMA for smoothed RTT (srtt)
– srtt 
*rtt_sample + (1-
)*srtt
– Typically 0.1 ≤
≤ 0.25 on networks prone to congestion.
TCP uses
=0.125.

•  Use another EWMA for smoothed RTT deviation (srttdev)

– Mean linear deviation easy to compute (but could also do std
deviation)
– dev_sample = |rtt_sample – srtt|
– srttdev  *dev_sample + (1-)*srttdev
TCP uses = 0.25

•  Retransmit Timeout, RTO

– RTO = srtt + k·srttdev
α = 0.1 α = 0.5 – k = 4 for TCP
– Makes the tail probability of a spurious retransmission low
Doesn’t respond quickly enough? – On successive retransmission failures, double RTO
(exponential backoff)

6.02 Fall 2012 Lecture 21, Slide #23 6.02 Fall 2012 Lecture 21, Slide #24

6
MIT OpenCourseWare
http://ocw.mit.edu

6.02 Introduction to EECS II: Digital Communication Systems

Fall 2012

For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.