Lecture 11
Mobile Networks:
TCP in Wireless Networks
Wireless and Mobile Systems Design
Mobile Networks: TCP in Wireless Networks 2
Lecture Objectives
Describe TCP’s flow control mechanism
Describe operation of TCP Reno and TCP Vegas, including congestion avoidance (congestion control), slow start, and fast retransmission and recovery mechanisms
Describe performance problems of TCP in wireless networks
Summarize proposed schemes to overcome performance limitations of TCP in wireless networks
Mobile Networks: TCP in Wireless Networks 3
Agenda
TCP overview
Flow control
Congestion avoidance, slow start, and retransmission
TCP Reno and TCP Vegas
TCP in wireless networks
Solutions to TCP performance problems in wireless networks
Mobile Networks: TCP in Wireless Networks 4
TCP Flow Control
TCP inherently supports flow control to prevent buffer overflow at the receiver
Useful for fast sender transmitting to slower receiver
Receiver advertises a window (wnd) in acknowledgements returned to the sender
Sender cannot send more than wnd unacknowledged bytes to the receiver
Src
Dest
Limits amount of
data that destination
must buffer
Mobile Networks: TCP in Wireless Networks 5
TCP Flow Control Example
Sender
Receiver
wnd = 1200
500 bytes
500 bytes
wnd = 200
200 bytes
wnd = 500
500 bytes
Mobile Networks: TCP in Wireless Networks 6
Flow Control Can Limit Throughput (1)
Let rtt be the round-trip time, i.e., the time from sending a segment until an acknowledgement (ACK) is received
Let t = wnd/b be the time to transmit a full “window” of data, where b is link bandwidth
Sender
Receiver
t
rtt
wnd
bytes
Mobile Networks: TCP in Wireless Networks 7
Flow Control Can Limit Throughput (2)
For a link with a high delay-bandwidth product (rttb), the flow control window can limit throughput for the connection
In this case, t  rtt
Throughput is wnd/rtt
Sender
Receiver
t
rtt
wnd
bytes
Mobile Networks: TCP in Wireless Networks 8
TCP Congestion Avoidance
Congestion avoidance (control) was added to TCP in an attempt to reduce congestion inside the network
A much harder problem …
Requires the cooperation of multiple senders
Must rely on indirect measures of congestion
Implemented at sender
Src
Dest
Attempts to reduce
buffer overflow inside
the network
Mobile Networks: TCP in Wireless Networks 9
Recent History of TCP
TCP has been improved over the years
More robust estimates of round-trip time
Faster recovery from packet loss
Congestion avoidance and improvements
TCP Reno
Developed by Van Jacobsen in 1990
Improvement to TCP Tahoe (1988)
Added fast recovery and fast retransmit
TCP Vegas
Developed by Brakmo and Peterson in 1995
New congestion avoidance algorithm
Mobile Networks: TCP in Wireless Networks 10
TCP Operation
Flow control (already discussed)
Congestion avoidance
Introduce a congestion window (cwnd), in addition to flow control window (wnd)
Need to manage size of congestion window
Slow start
Aggressively grow congestion window until congestion is detected
In Reno, aggressively reduce rate when invoked
Loss detection and retransmission
Fast retransmission and recovery
Less severe adjustment congestion window size
Mobile Networks: TCP in Wireless Networks 11
Congestion Avoidance: TCP Reno (1)
TCP can maintain a congestion window size, cwnd, at the sender
Sender can transmit up to minimum of cwnd and wnd bytes
TCP Reno uses packet loss as an indicator of network congestion
Most packet loss occurs due to congestion at intermediate routers since IP has no congestion control mechanism
Packet losses due to bit errors are rare
TCP Reno is reactive with respect to congestion
Responds to loss of packets indicated by timeout or duplicate ACKs
Mobile Networks: TCP in Wireless Networks 12
Congestion Avoidance: TCP Reno (2)
When packet loss occurs, congestion window size is reduced
Due to timeout: cwnd = 1 and enter slow start
Due to duplicate ACKs: cwnd = cwnd/2 + 3segment_size
Congestion window size is increased when data is successfully acknowledged
Slow start
Slow start active if cwnd  ssthresh (threshold)
During slow start, congestion window increased by segment_size for every ACK received  opens the window exponentially
Congestion avoidance
cwnd = cwnd + (1/cwnd) + segment_size/8 for every ACK received  additive growth in window size (about one segment every round trip time)
Mobile Networks: TCP in Wireless Networks 13
Congestion Window in TCP Reno
G. Xylomenos, G. C. Polyzos, P. Mahonen, and M. Saaranen, “TCP Performance Issues over Wireless Links,” IEEE Communications Magazine, Vol. 39, No. 4, pp. 52-58, April 2001.
Mobile Networks: TCP in Wireless Networks 14
Congestion Avoidance: TCP Vegas (1)
Sets congestion window size based on difference between the expected and actual data rates
Goal is to control the number of outstanding bytes in queues in the network (i.e., the backlog in queue)
Define…
cwnd: Current congestion window size
rtt*: Minimum (“congestion-free”) round-trip time
rtt: Actual (with congestion) round-trip time
diff: Estimated backlog in queue
: low threshold for diff (want diff > )
: high threshold for diff (want diff < )
diff = (cwnd/rtt* – cwnd/rtt)  rtt*
Mobile Networks: TCP in Wireless Networks 15
Congestion Avoidance: TCP Vegas (2)
Estimated backlog in queue (repeated here)
diff = (cwnd/rtt* – cwnd/rtt)  rtt*
TCP Vegas attempts to keep at least  bytes, but fewer than  bytes, in queue
If diff < , increase cwnd by 1
If diff > , decrease cwnd by 1
Otherwise (  diff  ), cwnd is not changed
TCP Vegas provides a proactive response to congestion
Congestion window changed gradually as observed backlog (delay) changes
Mobile Networks: TCP in Wireless Networks 16
cwnd+
Linearly
Increasing
cwnd+
cwnd
C
Expected
Throughput
Congestion Avoidance: TCP Vegas (3)
Actual
Throughput
Linearly
Decreasing
/rtt
/rtt
Throughput
Window Size
Mobile Networks: TCP in Wireless Networks 17
Slow Start Mechanism
The goal of the slow start mechanism is to detect and avoid congestion as a connection begins or after a timeout
Slow start threshold (sshtresh) set to half of cwnd when congestion is detected
Slow start is active if cwnd  ssthresh
Initially, cwnd = 1 segment
TCP Reno doubles the congestion window every round-trip time if no loss occurs
TCP Vegas doubles the congestion window every other round-trip time if no loss occurs
Mobile Networks: TCP in Wireless Networks 18
Loss Detection: TCP Reno
Coarse-grain timeout indicates packet loss
Sender starts a timer when TCP segment is sent
Timeout occurs if ACK not received before timeout
Retransmission occurs
Slow start is invoked (big reduction in rate!)
Three duplicate ACKs indicate packet loss
Receiver required to send an ACK if it receives an out of order segment – a segment may be out of order or lost
Sender assumes loss when it receives three duplicate ACKs
Fast retransmission and recovery mechanism – retransmit the requested segment (which is presumed lost after three duplicate ACKs) without waiting for a timeout
Congestion avoidance (smaller reduction in rate)
Mobile Networks: TCP in Wireless Networks 19
Loss Detection: TCP Vegas
Coarse-grain timeout mechanism
Same as for TCP Reno
Fine-grain timeout mechanism
If a duplicate ACK is received and the round-trip time of the first unacknowledged segment exceeds the fine-grain timeout value, then segment loss is assumed and requested segment is retransmitted
If a non-duplicate ACK is received after a retransmission and the round-trip time of the segment exceeds the fine-grain timeout value, then segment loss is assumed and retransmission occurs
Mobile Networks: TCP in Wireless Networks 20
cwnd  cwnd/2 + 3
TCP Reno Behavior
time
cwnd
SS
CA
SS
CA
CA
Duplicate ACK
 CA
SS: Slow start
CA: Collision avoidance
cwnd  1
Timeout
 SS
Mobile Networks: TCP in Wireless Networks 21
SS
TCP Vegas Behavior
Converges more smoothly … assuming sufficiently large buffers
time
cwnd
CA
Mobile Networks: TCP in Wireless Networks 22
TCP Reno Pros and Cons (1)
TCP Reno benefits
Simple bandwidth estimation scheme
Aggressive congestion avoidance mechanism ensures bandwidth when connected to TCP Vegas connections
More widely deployed, probably due to its maturity and aggressiveness
TCP Reno problems
Constantly updates window size
Can lead to periodic oscillation in window size
Can lead to oscillation in round trip times, causing delay jitter and inefficient bandwidth utilization
Can have many retransmissions of the same packets after a packet is dropped
Mobile Networks: TCP in Wireless Networks 23
TCP Reno Pros and Cons (2)
TCP Reno problems (continued)
Connections with shorter round trip times can update congestion window sizes more quickly
Such connections can received an unfair share of network capacity
TCP Reno is biased against connections with longer delays
Mobile Networks: TCP in Wireless Networks 24
TCP Vegas Pros and Cons
TCP Vegas benefits
Fair bandwidth estimation scheme
Window update rate does not depend only on round-trip time as in TCP Reno
Smooth sending rate and efficient link utilization when queue sizes are large (window stabilizes between  and )
TCP Vegas detects losses faster than TCP Reno and can recover from multiple drops more efficiently
TCP Vegas problems
Cannot compete with more aggressive TCP Reno connections
Vegas may not stabilize if buffers are small, leading to behavior that is similar to that of TCP Reno
Mobile Networks: TCP in Wireless Networks 25
TCP Reno versus TCP Vegas
TCP Vegas generally outperforms TCP Reno in a homogeneous environment
TCP Vegas achieves between 40% and 70% better throughput
TCP Vegas has 20% to 50% of the losses compared to the TCP Reno
Factors
Slow-start and congestion avoidance have the greatest influence on throughput
Congestion detection mechanism during congestion avoidance has only minor or negative effect on throughput
Congestion detection mechanism may exhibit problems related to fairness among competing connections
Mobile Networks: TCP in Wireless Networks 26
Agenda
TCP overview
Flow control
Congestion avoidance, slow start, and retransmission
TCP Reno and TCP Vegas
TCP in wireless networks
Solutions to TCP performance problems in wireless networks
Mobile Networks: TCP in Wireless Networks 27
TCP Problems with Wireless
Packet loss in wireless networks typically due to…
Bit errors due to wireless channel impairments
Handoffs due to mobility
Possibly congestion, but not often
As we’ve seen, TCP assumes packet loss is due to…
Congestion in the network
Packet reordering, but not often
In a wireless network, TCP congestion avoidance can be triggered by packet loss
TCP’s mechanisms do not respond well to packet loss due to bit errors or handoffs
Performance of TCP-based applications can suffer
Mobile Networks: TCP in Wireless Networks 28
More TCP Problems with Wireless
Bursts of errors may occur due to low signal strength or longer period of noise
More than one packet lost in TCP
More likely to be detected as a timeout  enter slow start!
Delay is often very high
Round-trip time can be very long and variable
TCP’s timeout mechanisms may not work well
Problem exacerbated by link-level retransmission
Links may be asymmetric
Delayed ACKs in the slow direction can limit throughput in the fast direction
Mobile Networks: TCP in Wireless Networks 29
Week 13 In-Class Laboratory
Experiments to consider…
Influence of bit errors in the wireless channel on TCP performance
TCP Reno versus TCP Vegas in this environment
Interactions are relatively complex
Typical studies use simulation, which provides a very controlled environment
We’re being a bit bold in trying to do experimental measurements
There is no at-home exercise for this week
You will be responsible for findings and observations on the final exam
Mobile Networks: TCP in Wireless Networks 30
Agenda
TCP overview
Flow control
Congestion avoidance, slow start, and retransmission
TCP Reno and TCP Vegas
TCP in wireless networks
Solutions to TCP performance problems in wireless networks
Mobile Networks: TCP in Wireless Networks 31
General Solution Approaches
Link-layer approaches
Split-connection approaches
End-to-end approaches
Mobile Networks: TCP in Wireless Networks 32
Link-Layer Protocols (1)
Hide losses not due to congestion from the sender by making link appear to be more reliable
Link-level automatic retransmission request (ARQ)
Forward error correction (FEC) codes
Hybrid ARQ and FEC
Advantages
Requires no change to existing sender behavior
Matches layered protocol model
Problem
Interactions with TCP, e.g., fast retransmission by TCP can be triggered by delays due to link-level timeout and retransmission
Mobile Networks: TCP in Wireless Networks 33
Link-Layer Protocols (2)
Negative interactions with TCP can be reduced by making the link-level protocol TCP-aware
Example: Snoop TCP
Advantages
Attempts to retransmit locally and suppress duplicate acknowledgements
State is soft, so handoff is simplified
Disadvantage
May not completely shield TCP from the effects of mobility and the wireless link
Mobile Networks: TCP in Wireless Networks 34
Split-Connection Protocols (1)
Hide the wireless link entirely by terminating the TCP connection prior to the wireless link
At the base station or access point
Use a special protocol or regular TCP over the wireless link
Example: Indirect TCP
Problems
Extra protocol overhead
Violates end-to-end semantics of TCP
Complicates handoff due to state information at the access point or base station where the protocol is “split”
Mobile Networks: TCP in Wireless Networks 35
Split-Connection Protocols (2)
TCP
TCP*
Logical TCP Connection
Split
Connection
Host
Host
AP
Mobile Networks: TCP in Wireless Networks 36
End-to-End Protocols (1)
Make TCP sender aware that some losses are not due to congestion and, thus, avoid congestion control when not needed
Use selective acknowledgement (SACKs) for “fine-grained” error recovery
SACK RFC
SMART
Use explicit loss notification (ELN) to distinguish between congestion and other losses
Mobile Networks: TCP in Wireless Networks 37
End-to-End Protocols (2)
Advantages
Maintains end-to-end semantics of TCP
Introduces no extra overhead at base stations for protocol processing or handoff
Disadvantages
Requires modified TCP
May not operate efficiently, e.g., for packet reordering versus packet loss
Mobile Networks: TCP in Wireless Networks 38
Indirect TCP: Overview
Wired
Network
Fixed
Host
Mobile
Host
TCP
Proxy
Standard TCP
Standard
TCP
“Wireless” TCP*
Indirect TCP
(* Normal TCP or modified transport protocol)
Mobile Networks: TCP in Wireless Networks 39
Indirect TCP: Handoff
An access point or router can act as a Mobile IP foreign agent and as the TCP proxy for Indirect TCP (I-TCP)
If the mobile host moves to a different foreign agent, a handoff is needed for Mobile IP
If the mobile host moves to a different proxy, a handoff of the full TCP state is needed for I-TCP
Buffered data
Sequence numbers
Port
Mobile Networks: TCP in Wireless Networks 40
Indirect TCP: Advantages
Does not require changes to TCP at the hosts in the fixed network
Errors from the wireless link are corrected at the TCP proxy and, thus, do not propagate through the fixed network
New protocol affects only a limited part of the Internet
Optimizations possible over wireless link
Variance in delay between proxy and mobile host may be small, permitting optimized TCP
Opportunity for header compression, etc.
Opportunity for a different transport protocol
Mobile Networks: TCP in Wireless Networks 41
Indirect TCP: Disadvantages
Loss of TCP’s end-to-end semantics
What happens if the proxy or the mobile host fails?
Handoff overhead can be significant
Overhead at the proxy for per packet processing (up to TCP and back down)
Can be reduced by good design
TCP proxy must be trusted
Obvious opportunities for snooping and denial of service
End-to-end IP-level privacy and authentication (e.g., using IPSec) must terminate at the proxy
Mobile Networks: TCP in Wireless Networks 42
Indirect TCP: Wireless Transport
I-TCP as originally proposed uses TCP as the wireless transport protocol
Timeouts at the wireless sender may stall the original sender on the fixed network
Selective acknowledgement protocols have been shown to provide better performance
Better suited to wireless link with higher error rate
Mobile Networks: TCP in Wireless Networks 43
Snoop TCP: Overview
Provide reliable link layer that is TCP aware
Snoop agent at the access point or foreign agent
Buffers data at the ends of the links for retransmissions (instead of going back to TCP end points)
“Snoops” on acknowledgements and filters duplicate acknowledgements
Wired
Network
Fixed
Host
Mobile
Host
Standard TCP
Snoop
Agent
Mobile Networks: TCP in Wireless Networks 44
Snoop TCP: Operation (1)
Snoop agent monitors and buffers data sent from fixed network to mobile host
Snoop agent monitors ACKs from the mobile host
Can discard buffer data when acknowledged
Can retransmit data when …
Delayed ACK, or
Duplicate ACK
Timeout can be relatively short leading to a fast retransmission
Snoop Agent discards duplicate ACKs from mobile host
Mobile Networks: TCP in Wireless Networks 45
Snoop TCP: Operation (2)
Snoop agent discards duplicate data that has already been sent by the agent and acknowledged
Snoop agent cannot generate ACKs that are sent back to the fixed host
Unlike split-connection schemes, Snoop TCP preserves end-to-end TCP semantics
Mobile Networks: TCP in Wireless Networks 46
Snoop TCP: Reverse Direction
Snoop monitors traffic from mobile host back to fixed host and detects missing segments
A negative ACK (NACK) is sent immediately to the mobile host
Mobile host can retransmit missing segment, hopefully in time to avoid a TCP timeout at the fixed host
Mobile Networks: TCP in Wireless Networks 47
Snoop TCP: Advantages
Preserves end-to-end TCP semantics
Requires no changes in TCP for fixed hosts
No changes in TCP are possible for the mobile hosts, but reverse direction traffic can benefit from changes at mobile host
There is no need for handoff
Automatic fallback to standard TCP
No need to ensure that all foreign networks provide a Snoop agent
Mobile Networks: TCP in Wireless Networks 48
Snoop TCP: Disadvantages
Does not fully isolate wireless link errors from the fixed network
Mobile host must be modified to handle NACKs for reverse (mobile to fixed) traffic
Cannot snoop encrypted datagrams
Cannot use with privacy
Retransmission of data from agent not authenticated due to protection from replay attacks
Cannot use with authentication
Mobile Networks: TCP in Wireless Networks 49
Summary
TCP is a complex protocol
Minimal support from underlying protocols
Indirect observation of network environment
Large number of competing flows from different hosts
Congestion avoidance is still a research issue
TCP does not perform well in a wireless environment where packets are usually lost due to bit errors, not congestion
Schemes have been proposed to address TCP performance problems
Link-level recovery
Split protocols
End-to-end protocols