Transcript TCP for wireless links

TCP for wireless links
Dario Maggiorini
[email protected]
TCP
TCP congestion control
The algorithm for TCP congestion
control is the main reason we can
use the Internet successfully today
despite largely unpredictable user
access patterns and despite
resource bottlenecks and
limitations. Without TCP congestion
control, the Internet could have
become history a long time ago.
Resource Management
Solutions
• Handling congestion
– pre-allocate resources so as to avoid congestion 
– control congestion if (and when) is occurs 
Router
1.5-Mbps T1 link
Destination
Source
2
• Two points of implementation
– routers inside the network (queuing discipline) 
– hosts at the edges of the network (transport protocol) 
Detecting Congestion
• Packet drops indicate congestion
– Is that really true?
– Why does it work?
Packet
Dst
Src
Drop
Ack
Timeout! No Ack
= Congestion!
Controlling Congestion – The
Effect of Window Size
• Note that sender’s window is equal to the
number of sender packets in flight (in the
network). Why?
Window
Source
Destination
Controlling Congestion
• Reduce window  less packets in the
network
• Increase window  more packets in the
network
• Idea: Concept of a congestion window –
window is smaller when congestion is
larger and vice versa
Additive Increase, Multiplicative
Decrease
• Each time a packet drop occurs, slash
window size in half (multiplicative
decrease)
– Multiplicative decrease is necessary to avoid
congestion
• When no losses are observed, gradually
increase window size (additive increase)
AIMD (cont)
– increment CongestionWindow by
one packet per RTT (linear increase)
– divide CongestionWindow by two
whenever a timeout occurs
(multiplicative decrease)
Destination
…
• Algorithm
Source
• In practice: increment a little for each ACK
Increment = (MSS*MSS)/CongestionWindow
CongestionWindow += Increment
TCP Reno (Jacobson 1990)
window
SS
time
CA
SS: Slow Start
CA: Congestion Avoidance
Fast retransmission/fast recovery
Problems
• What should the window size be
– Initially?
– Upon packet loss and timeout?
• Pessimistic window size? (e.g., 1)
– Additive increase is too slow in ramping up window
size – short connections will not fully utilize available
bandwidth
• Optimistic window size?
– Large initial burst may cause router queue overflow
Slow Start
– Use CongestionThreshold as an
optimistic CongestionWindow estimate
– begin with CongestionWindow = 1
packet
– double CongestionWindow each RTT
(increment by 1 packet for each ACK)
– When CongestionThreshold is
crossed, use additive increase
Source
Destination
…
• Objective: determine the available
capacity quickly
• Idea:
Fast Retransmit
Sender
• Problem: coarse-grain
TCP timeouts lead to idle
periods
• Fast retransmit:
– Send an ack on every
packet reception
– Send duplicate of last ack
when a packet is received
out of order
– Use duplicate ACKs to
trigger retransmission
Receiver
Packet 1
Packet 2
Packet 3
ACK 1
Packet 4
ACK 2
Packet 5
ACK 2
Packet 6
ACK 2
ACK 2
Retransmit
packet 3
ACK 6
Self Clocking and Slow Start
• Each packet’s transmission is “clocked” by an
ACK – no bursts develop
…
W=1
W=2 W=4
Slow Start
W=5
W=6
W=7
Self Clocking in Operation
• Each packet’s transmission is “clocked” by an
ACK – no bursts develop
…
…
W=32
Self Clocking Interrupted
• During timeouts, ACKs are drained from the
network. Self clocking is interrupted. Next
transmission causes a burst. Hence, slow start!
…
Lost
ACKs
Drained!!
Ack32
…
16 packet burst
W=32
Timeout
Retransmission
Cut window in 1/2
Self Clocking and Fast
Retransmit / Fast Recovery
• When fast retransmit is used, the packet is
retransmitted before all ACKs are drained. Slow
start is not needed
…
Lost
…
Fast
Retransmission
W=32
Cut window in 1/2
Problems with TCP Reno
• During slow start
– Underutilizes and then swamps path
• No “right rate”: cwnd traces a sawtooth
– Underutilizes path
– Increases queuing delay
– Causes loss, reducing throughput
– Inherently biased against long RTTs
TCP Vegas
• Uses congestion avoidance instead of
congestion control
– Vegas: Congestion avoidance: Predict and
avoid congestion before it occurs
– Tahoe, Reno: Congestion control: React to
congestion after it occurs
• Question: How to predict congestion?
– RTT grows
– sending rate
flattens
70
60
50
40
30
20
10
0.5
1.0 1.5
2.0 2.5 3.0
3.5 4.0 4.5
Time (seconds)
5.0
5.5 6.0
6.5
7.0 7.5 8.0 8.5
0.5 1.0 1.5
2.0 2.5 3.0
3.5 4.0 4.5
Time (seconds)
5.0
5.5 6.0
6.5
7.0 7.5 8.0 8.5
0.5 1.0 1.5
2.0 2.5 3.0
3.5 4.0 4.5
Time (seconds)
5.0
5.5 6.0
6.5
7.0 7.5 8.0 8.5
Sending KBps
1100
900
700
500
300
100
Queue size in router
• Idea: source
watches for some
sign that router’s
queue is building
up and congestion
will happen too;
e.g.,
KB
TCP Vegas
10
5
TCP Vegas
• In congestion avoidance
– cwnd = (actual rate)x(baseRTT) + 2 pkts
– Each RTT, tweak cwnd by 1 pkt if needed
• During slow start
– To reduce overshoot, increase cwnd only
every other RTT
– Exit slow start when
• cwnd > (actual rate)x(baseRTT) + 1 pkt
TCP Vegas (Brakmo & Peterson 1994)
window
SS
CA
• Converges, no retransmission
• … provided buffer is large enough
time
TCP Westwood
• Sender side only modification of TCP Reno
Congestion control that exploits end to end
bandwidth estimation.
• The bandwidth is estimated by low pass filtering
the rate of returning acks.
• The bandwidth is used to compute congestion
window and slow start threshold.
TCP Westwood Overview
• Slow Start and Congestion window aware
of Bandwidth at time of congestion
• The increase after congestion is additive
but decrease Adaptive (AIAD) as
compared to AIMD (Additive Increase
Multiplicative decrease) of Reno
TCPW implementation
• Sender side Bandwidth Estimation by measuring and low pass
filtering the rate of returning acks
• When 3 DUPACKS are received
ssthresh=(Bandwidth*RTT)/seg_size cwnd =ssthresh
• When a coarse timeout expires
ssthresh =(B*RTT)/seg_size
cwnd =1
• When acks are successfully received TCPW increases cwnd
according to Reno’s congestion control algorithm
TCPW Advantage over Reno
• In case of sudden increase in bottleneck
load, reduction can be more drastic then a
reduction by half and can be less drastic in
other cases. This features improves
stability and utilization
Go Back N Protocol (GBN)
Sender
1
New Packet
2
3
4
1
2
1
2
3
4
3
Receiver
Sender
1
Time Out
2
3
Copies (Go Back)
4
1
2
2
3
4
Receiver
3
Selective Repeat Protocol
Time Out
Sender
1
2
3
4
5
3
4
6
2
Receiver
1
1
5
2
2, 3, 4, 5
7
Wireless networks
Hidden node problem
•
•
A and C can send to B but can’t hear
each other
CSMA will be ineffective here
A
B
A’s transmit range
C
C’s transmit range
Exposed node problem
•
B and C can hear each other but could
safely send simultaneously to A, D
A
B
C
C’s transmit range
B’s transmit range
• Compare to spatial reuse
in cellular
D
Strategy
CSMA with Collision Avoidance
Fundamentally, a less greedy approach than
Ethernet
•
When medium busy, choose random backoff
interval
–
–
Wait for that many idle timeslots to pass before
sending
Remember p-persistence … a refinement
CSMA/CA
•
When a collision is inferred, retransmit with
binary exponential backoff (like Ethernet)
–
Use CRC and ACK from receiver to infer
“no collision”
–
Again, exponential backoff helps us adapt “p” as
needed
TCP over wireless
The wireless problem
In Wireless lossy links, the sporadic losses are
not due to congestion thus it leads to
unnecessary window and transmission rate
reduction
Sources of Errors in Wireless
Links
• Pauses due to handoff between cells
• Packet losses due to futile transmissions:
mobile host out of reach of other
transceivers (little or no overlap between
cells);
• Packet losses due to transmission errors
in wireless links.
Improving the Performance of
TCP
SH
MSS 1
Cell 1
MH
MSS 2
Cell 2
Smooth Handoff
• Cellular networks should strive to provide
smooth handoffs in order to eliminate
packet losses during cell crossings.
• No overlaps are also good!!!
– High aggregate bandwidth: adjacent cells can
use the same portion of the spectrum;
– Support for low-powered mobile receivers;
– Accurate location information
Comparision of Mechanisms
• End-to-end protocols
• Split-connection protocols
• Link-layer protocols
• Hybrid protocols
End-to-end Protocols
• Sender is aware of the existence of wireless
hops.
• Selective Acknowledgments (SACKs): sender
can recover from multiple packet losses without
resorting to a coarse timeout.
• Explicit Loss Notification (ELFN): the sender can
distinguish between congestion and other forms
of losses.
Split-connection Protocols
• Aims to hide any non-congestion-related
losses from the TCP sender.
• TCP connection is split between a sender
and receiver into two separate
connections at the base station:
– TCP connection over wired link;
– Specialized protocol over wireless link.
I-TCP: Indirect TCP
I-TCP
TCP
MSR
MH
• MH = Mobile Host
• MSR = Mobile Support Router
• FH = Fixed Host
FH
TCP/IP in Mobile Environment
• Main reason for throughput degradation:
– Loss of TCP segments during cell crossovers,
especially with non-overlapped cells.
• Effects:
– Lost segments trigger exponential back off
and congestion control at the transmitting
host.
– Congestion recovery phase may last for
several seconds.
Indirect Protocol
• Different flow control and congestion control for
wireless and wired links;
• Separate transport protocol supports
disconnections, moves and other wireless
related features;
• MSR manages much of the overhead;
• Faster reaction to mobility due to proximity
between MSR and MH.
I-TCP Basics
MH socket
MH socket
move
MH
MH
Wireless TCP
I-TCP Handoff
MSR-1
MSR1
fhsocket
MSR-1
Regular TCP
MSR1
mhsocket
MSR2
fhsocket
MSR-2
MSR2
mhsocket
FH
FH socket
Link-layer Protocols
• Two main classes:
– Error correction using techniques such as
Forward Error Correction;
– Retransmission of lost packets in response to
automatic repeat request (ARQ) messages.
• Tuned to the characteristics of the wireless
link.
Hybrid Protocols:
The Snoop Prootocol
• An agent monitors every packet and maintains a
cache of TCP segments that have not yet been
acknowledged.
• Packet loss is detected by the arrival of a small
number of duplicate acks or by a local timeout.
• The agent retransmits the lost packet and
suppresses the duplicate acks.
Observations
• TCP-aware link-layer protocol with
selective acknowledgments performs the
best;
• Split-connection approaches is not a
requirement for good performance.
• Selective acknowledgment is very useful
in lossy links, especially for burst losses.
• Explicit Loss Notification is worth to try.
TCP over satellite links
Why Satellite?
• Affordable Access to Interactive Broadband
Communication to all Areas of the Earth
• To Serve users who can not get Service
economically by other means
• Satellite Types
Altitude (km)
RTT (ms)
GEO
36,000
588
MEO
10,390
250
LEO
1,375
70
• Transmission Quality
Characteristics of Satellite Network
•
•
•
•
•
•
Long Feedback Loop
Large Delay-Bandwidth Product
Transmission Errors
Variable RTT
Frequent Hand off
Asymmetric Use
Corresponding Problems
• Slow Start
– For single TCP
– For HTTP applications
• Congestion Avoidance
– Congestion vs. Transmission Error
• TCP Window Size
TCP Window Size
• Throughput = Window size / RTT
• Max TCP Window Size = 216 = 65535 (bytes)
• Throughput <= 65535 bytes / 560 ms
= 117,027 bytes /second
Cannot utilize a T1 rate GEO satellite
Standard TCP Enhancements
• Fast Retransmit & Fast Recovery
• TCP SACKs
• TCP Large Windows
Other Enhancements
• Increasing Initial Window (IIW)
• Fast Start
• Teaching TCP to Ignore Transmission
Errors
• Split TCP
• TCP Peach
Split TCP
TCP Peach
•
•
•
•
Sudden Start
Congestion Avoidance
Fast Retransmit
Rapid Recovery
Sudden Start
Rapid Recovery (Link Error)
Rapid Recovery (Congestion)