|
|
|
|
Introduction and History |
|
Data in Wireless Cellular Systems |
|
Data in Wireless Local Area Networks |
|
Internet Protocols |
|
Routing and Ad-Hoc Networks |
|
TCP over Wireless Link |
|
some slides in this section are from the Tutorial
on TCP for Wireless and Mobile Hosts, prepared by Nitin Vaidya, see
http://www.cs.tamu.edu/faculty/vaidya/presentations.html |
|
Services and Service Discovery |
|
System Support for Mobile Applications |
|
|
|
|
What is the role of the "Transport
Layer" ? |
|
|
|
|
The Internet uses 2 transport protocols |
|
|
|
|
UDP is much simpler protocol than TCP |
|
It is designed to transport individual datagrams
(no sequence numbers) |
|
No acknowledgment |
|
It is used when high reliability is not needed |
|
The most common use is by protocols that handle
name lookups |
|
Checksum is optional |
|
|
|
|
|
TCP in the main Internet transport
protocol. The UDP plays a
supporting role (mostly house keeping functions) |
|
The TCP performs the following functions: |
|
Divides the data into segments (21 to 64,000
bytes) |
|
The sending TCP stamps the segments with
sequence numbers |
|
The receiving TCP acknowledges the segments |
|
The receiving TCP controls the flow of segments |
|
The TCP can flag data segments with different
priorities (e.g. urgent, externally urgent/to be pushed ..) |
|
TCP performs error correction |
|
The header of the TCP segment has several other
fields and options |
|
|
|
|
Communications through the Internet occurs
between a "Client" application software and the same application
software running on a "server" |
|
Each connection is uniquely identified by 4
addresses: (1) Client IP address, (2) client application port #, (3) server
IP address and (4) server application port. |
|
Application ports on the server side are called:
"Well-known Sockets". The
port number for each application is known to all hosts |
|
|
|
|
Virtual circuit connection |
|
Full Duplex.
Two-way simultaneous data flow. |
|
Reliable.
Checks the integrity of the received data |
|
Allows for multiple connections |
|
|
|
|
|
Octet-stream-oriented error control |
|
Transmissions occur in segments. Each segment has a sequence number. The sequence number is the first octet
of the segment |
|
The receiving TCP host sends an
acknowledgment. The ACK number is
the next expected data octet. |
|
Data that has not been acknowledged are
re-transmitted. |
|
|
|
|
|
|
Reliable ordered delivery |
|
Implements congestion avoidance and control |
|
Reliability achieved by means of retransmissions
if necessary |
|
End-to-end semantics |
|
Acknowledgements sent to TCP sender confirm
delivery of data received by TCP receiver |
|
Ack for data sent only after data has reached
receiver |
|
|
|
|
A new cumulative acknowledgement is generated
only on receipt of a new in-sequence packet |
|
|
|
|
|
An ack is delayed until |
|
another packet is received, or |
|
delayed ack timer expires (200 ms typical) |
|
Reduces ack traffic |
|
|
|
|
A dupack is generated whenever an |
|
out-of-order segment arrives at the receiver |
|
|
|
|
|
Duplicate acks are not delayed |
|
Duplicate acks may be generated when |
|
a packet is lost, or |
|
a packet is delivered out-of-order (OOO) |
|
|
|
|
|
|
Sliding window protocol |
|
Window size minimum of |
|
receiver’s advertised window - determined by
available buffer space at the receiver |
|
congestion window - determined by the sender,
based on feedback from the network |
|
|
|
|
|
TCP window flow control is “self-clocking” |
|
New data sent when old data is ack’d |
|
Helps maintain “equilibrium” |
|
Congestion window size bounds the amount of data
that can be sent per round-trip time |
|
Throughput
<= W / RTT |
|
|
|
|
|
|
|
|
|
|
Ideal size = delay * bandwidth |
|
delay-bandwidth product |
|
|
|
|
|
|
|
|
|
What if window size < delay*bw ? |
|
Inefficiency (wasted bandwidth) |
|
What if > delay*bw ? |
|
Queuing at intermediate routers |
|
increased RTT due to queuing delays |
|
Potentially, packet loss |
|
|
|
|
Bandwidth & Delay x Bandwidth Product |
|
|
|
|
|
Two sides of the same coin |
|
pre-allocate resources to avoid congestion |
|
send data and control congestion if (and when)
is occurs |
|
|
|
|
|
|
|
|
|
|
|
|
|
Two points of implementation |
|
hosts at the edges of the network (transport
protocol) |
|
routers inside the network (queuing discipline) |
|
Underlying service model |
|
best-effort |
|
no quality of service guarantees |
|
|
|
|
|
Idea |
|
assumes best-effort network |
|
each source determines network capacity for
itself |
|
uses implicit feedback |
|
ACKs pace transmission (self-clocking) |
|
Challenge |
|
determining the available capacity in the first
place |
|
adjusting to changes in the available capacity |
|
|
|
|
|
|
Objective: adjust to changes in the available
capacity |
|
New state variable per connection:
CongestionWindow |
|
limits how much data source has in transit |
|
MaxWin = |
|
MIN(CongestionWindow,AdvertisedWindow) |
|
EffWin = MaxWin - (LastByteSent - LastByteAcked) |
|
|
|
|
|
Idea: |
|
increase CongestionWindow when congestion goes
down |
|
decrease CongestionWindow when congestion goes
up |
|
Question: how does the source determine whether
or not the network is congested? |
|
Answer: implicitly through packet loss |
|
timeout signals that a packet was lost |
|
packets are seldom lost due to transmission
error |
|
lost packet implies congestion |
|
|
|
|
|
Algorithm: |
|
increment CongestionWindow by one packet per RTT
(linear increase) |
|
divide CongestionWindow by two whenever a
timeout occurs (multiplicative decrease) |
|
In practice: increment a little for each ACK |
|
Increment = (MSS * MSS)/CongestionWindow |
|
CongestionWindow += Increment |
|
|
|
|
|
|
|
|
Retransmission timeout (RTO) |
|
|
|
|
|
Duplicate acknowledgements |
|
|
|
|
|
|
|
At any time, TCP sender sets retransmission
timer for only one packet |
|
If acknowledgement for the timed packet is not
received before timer goes off, the packet is assumed to be lost |
|
RTO dynamically calculated |
|
Connection may be between two machines on same
LAN (want low RTO value) or two machines on opposite sides of Atlantic
(need higher RTO value) |
|
Network connection between two machines
introduces predictable and constant delay per packet (can use tighter
bound) or highly variable packet delay (use less tight bound to avoid
unnecessary retransmissions) |
|
Use observed time difference between packet sent
and acknowledgment received to estimate RTO |
|
|
|
|
Karn/Partridge Algorithm |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Do not sample RTT when retransmitting |
|
Double timeout after each retransmission |
|
|
|
|
|
Jacobson/Karels Algorithm |
|
New calculation for average RTT |
|
Diff = SampleRTT - EstimatedRTT |
|
EstimatedRTT = EstimatedRTT + (d x Diff) |
|
Deviation = Deviation + d(|Diff|-
Deviation) |
|
where d is a fraction between 0 and 1 |
|
Consider variance when setting timeout value |
|
TimeOut = m x EstimatedRTT + f x Deviation |
|
where m = 1 and f = 4 |
|
Notes |
|
algorithm only as good as granularity of clock
(500ms on Unix) |
|
accurate timeout mechanism important to
congestion control |
|
|
|
|
|
|
|
Timeouts can take too long |
|
how to initiate retransmission sooner? |
|
|
|
Fast retransmit |
|
|
|
|
|
Dupacks may be generated due to |
|
packet loss, or |
|
out-of-order packet delivery |
|
TCP sender assumes that a packet loss has
occurred if it receives three dupacks consecutively |
|
|
|
|
|
Slow Start |
|
initially, congestion window size cwnd = 1 MSS
(maximum segment size) |
|
increment window size by 1 MSS on each new ack |
|
slow start phase ends when window size reaches
the slow-start threshold |
|
cwnd grows exponentially with time during slow
start |
|
factor of 2 per RTT |
|
Could be less if sender does not always have
data to send |
|
|
|
|
|
On each new ack, increase cwnd by 1/cwnd packets |
|
cwnd increases linearly with time during
congestion avoidance |
|
1 MSS per RTT |
|
|
|
|
|
|
On detecting a packet loss, TCP sender assumes
that network congestion has occurred |
|
On detecting packet loss, TCP sender drastically
reduces the congestion window |
|
Reducing congestion window reduces amount of
data that can be sent per RTT |
|
throughput may decrease |
|
|
|
|
|
On a timeout, the congestion window is reduced
to the initial value of 1 MSS |
|
The slow start threshold is set to half the
window size before packet loss |
|
more precisely, |
|
ssthresh =
maximum of min(cwnd,receiver’s advertised window)/2 and 2 MSS |
|
Slow start is initiated |
|
|
|
|
|
|
Fast retransmit occurs when multiple (>= 3)
dupacks come back |
|
Fast recovery follows fast retransmit |
|
Different from timeout : slow start follows
timeout |
|
timeout occurs when no more packets are getting
across |
|
fast retransmit occurs when a packet is lost,
but latter packets get through |
|
ack clock is still there when fast retransmit
occurs |
|
no need to slow start |
|
|
|
|
|
ssthresh = |
|
min(cwnd, receiver’s advertised window)/2
(at least 2 MSS) |
|
retransmit the missing segment (fast retransmit) |
|
cwnd = ssthresh + number of dupacks |
|
when a new ack comes: cwnd = ssthreh |
|
enter congestion avoidance |
|
Congestion window cut into half |
|
|
|
|
|
|
|
TCP is (most?) popular transport layer protocol |
|
designed for wired networks |
|
low error rate |
|
requirement to share bottlenecks |
|
key assumptions in TCP are: |
|
packet loss is indication of congestion, not
transmission error |
|
rather aggressive response to congestion is
needed to ensure fairness and efficiency |
|
wireless links and mobile computing violate
these assumptions: |
|
packets lost due to unreliable physical media |
|
packets can get lost due to handover |
|
|
|
|
|
|
packet losses over wireless link often in bursts |
|
will trigger slow start rather than fast
retransmit |
|
packet loss no indication of congestion |
|
reduction of congestion window will reduce
throughput |
|
getting back to previous window size may take
long |
|
problem caused by mismatch of wireless link
properties with assumptions underlying TCP design |
|
multiple suggestions to improve TCP performance: |
|
link-level retransmissions: improve reliability
of wireless link |
|
network layer solutions: SNOOP |
|
transport layer solutions: I-TCP (indirect TCP),
Mowgli |
|
session layer solutions: establish end-to-end
session layer connection, manages two separate TCP connections |
|
|
|
|
|
Forward Error Correction (FEC) can be use to correct small number
of errors |
|
Correctable errors hidden from the TCP sender |
|
FEC incurs overhead even when errors do not
occur |
|
Adaptive FEC schemes can reduce the overhead by
choosing appropriate FEC dynamically |
|
FEC does not guard/protect from packet loss due
to handover |
|
|
|
|
|
Link level retransmission schemes retransmit a
packet at the link layer, if errors are detected |
|
Retransmission overhead incurred only if errors
occur |
|
unlike FEC overhead |
|
In general |
|
Use FEC to correct a small number of errors |
|
Use link level retransmission when FEC
capability is exceeded |
|
|
|
|
|
|
How many times to retransmit at the link level
before giving up? |
|
Finite bound -- semi-reliable link layer |
|
No bound -- reliable link layer |
|
What triggers link level retransmissions? |
|
Link layer timeout mechanism |
|
Link level acks (negative acks, dupacks, …) |
|
Other mechanisms (e.g., Snoop, as discussed
later) |
|
How much time is required for a link layer
retransmission? |
|
Small fraction of end-to-end TCP RTT |
|
Large fraction/multiple of end-to-end TCP RTT |
|
|
|
|
|
|
|
Should the link layer deliver packets as they
arrive, or deliver them in-order? |
|
Link layer may need to buffer packets and
reorder if necessary so as to deliver packets in-order |
|
|
|
|
Retransmissions can cause head-of-the-line
blocking |
|
|
|
|
|
|
|
|
|
Although link to receiver 1 may be in a bad
state, the link to receiver 2 may be in a good state |
|
Retransmissions to receiver 1 are lost, and also
block a packet from being sent to receiver 2 |
|
|
|
|
Retransmissions can cause congestion losses |
|
|
|
|
|
|
|
|
|
|
|
|
|
Attempting to retransmit a packet at the front
of the queue, effectively reduces the available bandwidth, potentially
making the queue at base station longer |
|
If the queue gets full, packets may be lost,
indicating congestion to the sender |
|
Is this desirable or not ? |
|
|
|
|
|
The sender’s Retransmission Timeout (RTO) is a
function of measured RTT (round-trip times) |
|
Link level retransmits increase RTT, therefore,
RTO |
|
If errors not frequent, RTO will not account for
RTT variations due to link level retransmissions |
|
When errors occur, the sender may timeout &
retransmit before link level retransmission is successful |
|
Sender and link layer both retransmit |
|
Duplicate retransmissions (interference) waste
wireless bandwidth |
|
Timeouts also result in reduced congestion
window |
|
|
|
|
|
Early analysis does not accurately model real
TCP stacks |
|
With large RTO granularity, interference is
unlikely, if time required for link-level retransmission is small compared
to TCP RTO |
|
Standard TCP RTO granularity is often large (500
ms) |
|
Minimum RTO (2*granularity) is large enough to
allow a small number of link level retransmissions, if link level RTT is
relatively small |
|
Interference due to timeout not a significant
issue when wireless RTT small, and RTO granularity large |
|
|
|
|
|
Frequent errors increase RTO significantly on
slow wireless links |
|
RTT on slow links large, retransmissions result
in large variance, pushing RTO up |
|
Likelihood of interference between link layer
and TCP retransmissions smaller |
|
But congestion response will be delayed due to
larger RTO |
|
When wireless losses do cause timeout, much time
wasted |
|
|
|
|
|
|
Good for reducing interference with link level retransmits |
|
Bad for recovery from congestion losses |
|
Need a timeout mechanism that responds
appropriately for both types of losses |
|
Open problem |
|
|
|
|
|
Selective repeat protocols can deliver packets
out of order |
|
Significantly out-of-order delivery can trigger
TCP fast retransmit |
|
Redundant retransmission from TCP sender |
|
Reduction in congestion window |
|
Example: Receipt of packets |
|
3,4,5 triggers dupacks |
|
|
|
|
To avoid unnecessary fast retransmit, link layer
using retransmission should attempt to deliver packets “almost in-order” |
|
|
|
|
|
Not all connections benefit from retransmissions
or ordered delivery |
|
audio |
|
Need to be able to specify requirements on a
per-packet basis |
|
Should the packet be retransmitted? How many
times? |
|
Enforce in-order delivery? |
|
Need a standard mechanism to specify the
requirements |
|
open issue (IETF PILC working group) |
|
|
|
|
|
|
When is a reliable link layer beneficial to TCP
performance? |
|
if it provides almost in-order delivery |
|
TCP retransmission timeout large enough to
tolerate additional delays due to link level retransmits |
|
Basic ideas: |
|
Hide wireless losses from TCP sender |
|
Link layer modifications needed at both ends of
wireless link |
|
TCP need not be modified |
|
|
|
|
|
|
|
End-to-end TCP connection is broken into one
connection on the wired part of route and one over wireless part of the
route |
|
|
|
A single TCP connection split into two TCP
connections |
|
if wireless link is not last on route, then more
than two TCP connections may be needed |
|
|
|
|
Connection between wireless host MH and fixed
host FH goes through base station BS |
|
|
|
FH-MH
= FH-BS +
BS-MH |
|
|
|
|
Split connection results in independent flow
control for the two parts |
|
|
|
Flow/error control protocols, packet size,
time-outs, may be different for each part |
|
|
|
|
|
|
basic idea: split communication between mobile
host (MH) and fixed host (FH) into two separate interactions |
|
each connection can be tuned to accommodate the
special characteristics of the underlying physical media |
|
use standard TCP between MSR and FH, both on
wired backbone |
|
special wireless TCP between MH and MSR, where
packet loss does not trigger congestion avoidance |
|
|
|
|
|
throughput improved, particularly for wide-area
connections, compared to regular TCP |
|
|
|
|
|
|
Hides transmission errors from sender |
|
Primary responsibility at base station |
|
If specialized transport protocol used on
wireless, then wireless host also needs modification |
|
|
|
|
|
BS-MH connection can be optimized independent of
FH-BS connection |
|
Different flow / error control on the two
connections |
|
Local recovery of errors |
|
Faster recovery due to relatively shorter RTT on
wireless link |
|
Good performance achievable using appropriate
BS-MH protocol |
|
Standard TCP on BS-MH performs poorly when
multiple packet losses occur per window (timeouts can occur on the BS-MH
connection, stalling during the timeout interval) |
|
Selective acks improve performance for such
cases |
|
|
|
|
|
End-to-end semantics violated |
|
ack may be delivered to sender, before data
delivered to the receiver |
|
May not be a problem for applications that do
not rely on TCP for the end-to-end semantics |
|
|
|
|
|
|
|
|
|
BS (MSR in I-TCP) retains hard state |
|
BS failure can result in loss of data
(unreliability) |
|
If BS fails, packet 40 will be lost |
|
Because it is ack’d to sender, the sender does
not buffer 40 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
BS retains hard state |
|
Hand-off latency increases due to state
transfer |
|
Data that has been ack’d to sender, must be
moved to new base station |
|
|
|
|
|
Buffer space needed at BS for each TCP
connection |
|
BS buffers tend to get full, when wireless link
slower (one window worth of data on wired connection could be stored at the
base station, for each split connection) |
|
Window on BS-MH connection reduced in response
to errors |
|
may not be an issue for wireless links with
small delay-bw product |
|
|
|
|
|
Extra copying of data at BS |
|
copying from FH-BS socket buffer to BS-MH socket
buffer |
|
increases end-to-end latency |
|
May not be useful if data and acks traverse
different paths (both do not go through the base station) |
|
Example: data on a satellite wireless hop, acks
on a dial-up channel |
|
|
|
|
|
|
|
|
|
idea: modify network layer software at base
station |
|
changes are transparent to MH and FH |
|
no changes in TCP semantics (unlike I-TCP) |
|
less software overhead (packets pass TCP layer
only twice) |
|
no application relinking on mobile host |
|
modifications are mostly in caching packets and
performing local retransmissions across the wireless link by monitoring (snooping)
on TCP acks |
|
results are impressive: |
|
speedups of up to 20 times over regular TCP |
|
more robustness when dealing with multiple
packet losses |
|
|
|
|
|
|
|
|
processing packets from FH |
|
new packet in the normal TCP sequence: |
|
cache and forward to MH |
|
packet out-of sequence and cached earlier: |
|
sequence number > last ack from MH: packet
probably lost, forward it again |
|
otherwise, packet already received at MH, so
drop |
|
but: original ACK could have been lost, so fake
ACK again |
|
packet out-of sequence and not cached yet: |
|
packet either lost earlier due to congestion or
delivered out-of-order: cache packet and mark as retransmitted, forward to
MH |
|
|
|
|
|
|
processing ACKs from MH: |
|
new ACK: common case, initiates cleaning up of
snoop cache, update estimate of round-trip time for wireless link, forward
ACK to FH |
|
spurious ACK: less than last ACK seen, happens
rarely. Just drop ACK and continue |
|
duplicate ACK: indicates packet loss, one of
several actions: |
|
packet either not in cache or marked as
retransmitted: pass duplicate ACK on to FH |
|
first duplicated ACK for cached packet:
retransmit cached packet immediately and at high priority, estimate number
of expected duplicate ACKs, based on # of packets sent after missing one |
|
expected successive duplicate ACKs: ignore, we
already initiated retransmission. Since retransmission happens at higher
priority, we might not see total number of expected duplicate ACKs |
|
|
|
|
|
|
design does not cache packets from MH to FH |
|
bulk of packet losses will be between MH and
base |
|
but snooping on packets generates requests for
retransmissions at base much faster than from remote FH |
|
enhance TCP implementation at MH with “selective
ACK” option: |
|
base keeps track of packets lost in a
transmission window |
|
sends bit vector back to MH to trigger
retransmission of lost packets |
|
mobility handling: |
|
when handoff is requested by MH or anticipated
by base station, nearby base stations begin receiving packets destined for
MH, priming their cache |
|
caches synchronized during actual handoff (since
nearby bases cannot snoop on ACKs) |
|
|
|
|
no difference in very low error rate environment
(bit error rate < 5x10-7) |
|
for higher bit error rates, Snoop outperforms
regular TCP by a factor of 1 to 20, depending on the bit error rate (the
higher, the better Snoop’s relative performance) |
|
even when every other packet was dropped over
the wireless link, Snoop still allowed for progress in transmission, while
regular TCP came to a grinding halt |
|
Snoop provides high and consistent throughput,
regular TCP triggers congestion control often, which leads to periods of no
transmission and very uneven rate of progress |
|
|
|
|
|
|
most effort spent on direction FH->MH |
|
authors argue that not much can be done for
MH->FH |
|
losses occur over first link, the unreliable
wireless link |
|
Internet drops 2%-5% of IP packets, tendency
rising |
|
assume that IP packet is lost in wired part of
network: |
|
receiver (FH) will issue duplicate ACKs |
|
this should trigger fast retransmit rather than
slow start (?) |
|
nothing is done to ensure that ACKs are not
dropped over last link |
|
retransmission of data packet over wireless link
is subject to unreliable link and low bandwidth again |
|
Snoop could potentially benefit from caching
packets in both directions |
|
how would this differ from link-layer
retransmission policy? |
|
|
|
|
|
Discussed only a few ideas, for a more complete
discussion, see Tutorial on TCP for Wireless and Mobile Hosts by Nitin
Vaidya, http://www.cs.tamu.edu/faculty/vaidya/presentations.html |
|
Topics ignored: |
|
asymmetric bandwidth on uplink and downlink (for
example in some cable or satellite networks) |
|
wireless link extends over multiple hops, such
as in an ad-hoc network |
|
connections fail due to spurious disconnections
or route failures in ad-hoc networks |
|
Many proposals focus on downlink only |
|
Many proposals, most try to avoid changing TCP
interface or semantics, but more work necessary |
|