Internet Engineering Task Force Hari Balakrishnan
Internet Draft MIT
Document: draft-ietf-pilc-asym-01.txt Venkata N. Padmanabhan
Microsoft Research
Category: Informational March 2000
TCP Performance Implications of Network Asymmetry
Status of this Memo
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts. Internet-Drafts are draft documents valid for a maximum of
six months and may be updated, replaced, or obsoleted by other
documents at any time. It is inappropriate to use Internet- Drafts
as reference material or to cite them other than as "work in
progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
1. Abstract
This document describes TCP performance problems that arise because
of asymmetric effects. These problems arise in several access
networks, including bandwidth-asymmetric networks and packet radio
networks, for different underlying reasons. However, the net effect
on TCP performance is the same in both cases: performance degrades
significantly because of imperfection and variability in the ACK
feedback from the receiver to the sender. This document details
several solutions to these problems, which use a combination of
local link-layer techniques and end-to-end mechanisms. Solutions to
the problem of asymmetry are two-pronged: (i) techniques to manage
the reverse channel used by ACKs, typically using header compression
or reducing the frequency of TCP ACKs, and (ii) techniques to handle
this reduced ACK frequency to retain the TCP sender's
acknowledgment-triggered self-clocking.
2. Conventions used in this document
FORWARD DIRECTION: The dominant direction of data transfer over an
asymmetric network. It corresponds to the direction with better link
characteristics in terms of bandwidth, latency, error rate, etc. We
term data transfer in the forward direction as a "forward transfer".
Expires September 2000 [page 1]
INTERNET DRAFT PILC - Asymmetric Links March 2000
REVERSE DIRECTION: The direction in which acknowledgments of a
forward TCP transfer flow. Data transfer could also happen in this
direction (and it is termed "reverse transfer"), but it is typically
less voluminous than that in the forward direction. The reverse
direction typically exhibits worse link characteristics than the
forward direction.
DOWNSTREAM: Same as the forward direction.
UPSTREAM: Same as the reverse direction.
ACK: A cumulative TCP acknowledgment. In this document, we use this
term to refer to a TCP segment that carries a cumulative
acknowledgement but no data.
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in
this document are to be interpreted as described in [RFC2119].
3. Motivation
Asymmetric characteristics are exhibited by several network
technologies, including cable modems, direct broadcast satellite,
ADSL, and several packet radio networks. Given that these networks
are increasingly being deployed as high-speed access networks, it is
highly desirable to achieve good TCP performance over such networks.
However, the asymmetry of the networks often makes this challenging.
For example, when bandwidth is asymmetric such that the reverse path
used by TCP ACKs is constrained, the slow or infrequent ACK feedback
degrades TCP performance in the forward direction. Even when
bandwidth is symmetric, asymmetry in the underlying medium access
control (MAC) protocol could make it expensive to transmit ACKs
(disproportionately to the size of the ACKs) in one direction, as in
wireless packet radio networks. This results in degradation of TCP
performance. The asymmetry of the MAC protocol is often a
fundamental consequence of the hub-and-spokes architecture of the
network (e.g., a single base station that communicates with multiple
mobile stations) rather than an artifact of poor engineering
choices.
Despite the technological differences between asymmetric-bandwidth
and packet radio networks, TCP performance suffers in both these
kinds of networks for the same fundamental reason: the imperfection
and variability of ACK feedback. This document discusses the problem
in detail and describes several solutions from the research
literature to overcome these problems [BPK97, BPK99, CR98, LMS97,
KVR98].
4. How does asymmetry degrade TCP performance?
Expires September 2000 [page 2]
INTERNET DRAFT PILC - Asymmetric Links March 2000
This section describes the implications of network asymmetry on TCP
performance. We refer the reader to [BPK99, Bal98, Pad98] for more
details and experimental results.
4.1 Bandwidth asymmetry
We first discuss the problems that degrade unidirectional transfer
performance in bandwidth-asymmetric networks. Depending on the
characteristics of the reverse path, two types of situations arise
for unidirectional traffic over such networks: when the reverse
bottleneck link has sufficient queuing to prevent packet (ACK)
losses, and when the reverse bottleneck link has a small buffer. We
consider each situation in turn.
If the reverse bottleneck link has deep queues so that ACKs do not
get dropped on the reverse path, then performance is a strong
function of the normalized bandwidth ratio, k, defined in [LMS97]. k
is the ratio of the raw bandwidths divided by the ratio of the
packet sizes used in the two directions. For example, for a 10 Mbps
forward channel and a 50 Kbps reverse channel, the raw bandwidth
ratio is 200. With 1000-byte data packets and 40-byte ACKs, the
ratio of the packet sizes is 25. This implies that k is 200/25 = 8.
Thus, if the receiver acknowledges more frequently than one ACK
every k = 8 data packets, the reverse bottleneck link will get
saturated before the forward bottleneck link does, limiting the
throughput in the forward direction.
If k > 1 and ACKs are not delayed (in the sense of TCP's delayed ack
algorithm) or dropped (at the reverse bottleneck router), TCP ACK-
clocking breaks down. Consider two data packets transmitted by the
sender in quick succession. En route to the receiver, these packets
get spaced apart according to the bottleneck link bandwidth in the
forward direction. The principle of ACK clocking is that the ACKs
generated in response to these packets preserve this temporal
spacing all the way back to the sender, enabling it to transmit new
data packets that maintain the same spacing. However, the limited
reverse bandwidth and queuing at the reverse bottleneck router
alters the inter-ACK spacing observed at the sender. When ACKs
arrive at the bottleneck link in the reverse direction at a faster
rate than the link can support, they get queued behind one another.
The spacing between them when they emerge from the link is dilated
with respect to their original spacing, and is a function of the
reverse bottleneck bandwidth. Thus the sender clocks out new data at
a slower rate than if there had been no queuing of ACKs. No longer
is the performance of the connection dependent on the forward
bottleneck link alone; instead, it is throttled by the rate of
arriving ACKs. As a side-effect, the sender's rate of congestion
window growth slows down too.
A different situation arises when the reverse bottleneck link has a
relatively small amount of buffer space to accommodate ACKs. As the
transmission window grows, this queue fills and ACKs are dropped. If
the receiver acknowledges every packet, only one of every k ACKs
Expires September 2000 [page 3]
INTERNET DRAFT PILC - Asymmetric Links March 2000
gets through to the sender, and the remaining (k-1) are dropped due
to buffer overflow at the reverse channel buffer (here k is the
normalized bandwidth ratio as before). In this case, the reverse
bottleneck link capacity and slow ACK arrival are not directly
responsible for any degraded performance. However, there are three
important reasons for degraded performance in this case because ACKs
are infrequent.
1. First, the sender transmits data in large bursts. If the sender
receives only one ACK in k, it transmits data in bursts of k (or
more) segments because each ACK shifts the sliding window by at
least k (acknowledged) segments. This increases the likelihood of
data loss along the forward path especially when k is large, because
routers do not handle large bursts of packets well.
2. Second, TCP sender implementations increase their congestion
window by counting the number of ACKs they receive and not on how
much data is actually acknowledged by each ACK. Thus fewer ACKs
imply a slower rate of growth of the congestion window, which
degrades performance over long-delay connections.
3. Third, the sender's fast retransmission and recovery algorithms
are less effective when ACKs are lost. The sender may not receive
the threshold number of duplicate ACKs even if the receiver
transmits more than the required number. Furthermore, the sender may
not receive enough duplicate ACKs to adequately inflate its window
during fast recovery.
4.2 MAC protocol interactions
The interaction of TCP with media-access protocols often degraded
end-to-end performance. Variable round-trip delays and ACK queuing
are the main symptoms of this problem. The need for the
communicating peers to first synchronize via the RTS/CTS protocol
before communication and the significant turn-around time for the
radios result in a high per-packet overhead. Furthermore, since the
RTS/CTS exchange needs to back-off exponentially when the polled
radio is busy (for example, engaged in a conversation with a
different peer), this overhead is variable. This leads to large and
variable communication latencies in packet-radio networks. In
addition, with an asymmetric workload with most data flowing in one
direction to clients, ACKs tend to get queued in certain radio units
(especially in the client modems), exacerbating the variable
communication latencies.
These variable latencies and queuing of ACKs adversely affect smooth
data flow. In particular, TCP ACK traffic interferes with the flow
of data and increases the traffic load on the system. Experiments
conducted on Metricom's Ricochet packet radio network [Met] clearly
demonstrated the effect of the radio turnarounds and increased RTT
variability, which degrade TCP performance. It is not uncommon for
TCP connections to experience timeouts that last between 9 and 12
seconds each. As a result, a connection may be idle for a very
Expires September 2000 [page 4]
INTERNET DRAFT PILC - Asymmetric Links March 2000
significant fraction of its lifetime. (We have seen instances in the
context of the Ricochet network where the idle time is 35% of the
total transfer time!) Clearly, this leads to gross under-utilization
of the available bandwidth.
Why are these timeouts so long in duration? Ideally, the round-trip
time estimate (srtt) of a TCP data transfer will be relatively
constant (i.e., have a low linear deviation, rttvar). Then the TCP
retransmission timeout, set to srtt + 4*rttvar, will track the
smoothed round-trip time estimate and respond well when multiple
losses occur in a window. Unfortunately, this is not true for
connections in the Ricochet network. Because of the high variability
in RTT, the retransmission timer is on the order of 10 seconds,
leading to the long idle timeout periods.
In general, it is correct for the retransmission timer to trigger a
segment retransmission only after an amount of time dependent on
both the round-trip time and the linear (or standard) deviation. If
only the mean or median round-trip estimates were taken into
account, the potential for spurious retransmissions of segments
still in transit is large.
Connections traversing multiple wireless hops are especially
vulnerable to this effect, because it is now more likely that the
radio units may already be engaged in conversation with other peers.
Note that the wireless MAC contention problem is a significant
function of the number of packets (e.g., ACKs) transmitted rather
than their size. In other words, there is a significant cost to
transmitting a packet regardless of its size.
4.3 Bi-directional traffic
We now consider the case when TCP transfers simultaneously occur in
opposite directions over an asymmetric network. An example scenario
is one in which a user sends out data upstream (for example, an e-
mail message) while simultaneously receiving other data downstream
(for example, Web pages). For ease of exposition, we restrict our
discussion to the case of one connection in each direction.
In the presence of bi-directional traffic, the effects discussed in
Section 4.1 are more pronounced, because part of the uplink
bandwidth is used up by the reverse transfer. This effectively
increases the degree of bandwidth asymmetry for the forward
transfer. In addition, there are other effects that arise due to the
interaction between data packets of the reverse transfer and ACKs of
the forward transfer. Suppose the reverse connection is initiated
first and that it has saturated the reverse channel and buffer with
its data packets at the time the forward connection is initiated.
There is then a high probability that many ACKs of the newly
initiated forward connection will encounter a full reverse channel
buffer and hence get dropped. Even after these initial problems,
Expires September 2000 [page 5]
INTERNET DRAFT PILC - Asymmetric Links March 2000
ACKs of the forward connection could often get queued up behind
large data packets of the reverse connection, which could have long
transmission times (e.g., it takes about 280 ms to transmit a 1 KB
data packet over a 28.8 Kbps line). This causes the forward transfer
to stall for long periods of time. It is only at times when the
reverse connection loses packets (due to a buffer overflow at an
intermediate router) and slows down that the forward connection gets
the opportunity to make rapid progress and quickly build up its
window.
In summary, the presence of bi-directional traffic exacerbates the
problems due to bandwidth asymmetry because of the adverse
interaction between data packets of an upstream connection and the
ACKs of a downstream connection.
5. Improving TCP performance over asymmetric networks
It should be clear by now that there are two key issues that need to
be addressed in order to improve TCP performance over asymmetric
networks. The first issue is to manage bandwidth usage on the
reverse link, used by ACKs (and possibly other traffic). Many of
these techniques work by reducing the number of ACKs that flow over
the reverse channel, which has the potential to destroy the
desirable self-clocking property of the TCP sender where new data
transmissions are triggered by incoming ACKs. Thus, the second issue
is to avoid any adverse impact of infrequent ACKs.
Each of these issues can be handled by local link-layer solutions
and/or by end-to-end techniques. In this section, we discuss several
proposed solutions of both kinds.
5.1 Reverse-link bandwidth management
5.1.1 TCP header compression
RFC 1144 describes TCP header compression for use over low-bandwidth
links running SLIP or PPP. Because it greatly reduces the size of
ACKs on the reverse link when losses are infrequent (a situation
that ensures that the state of the compressor and decompressor are
synchronized), we recommend its use over low-bandwidth reverse links
where possible. However, this alone does not address all of the
problems:
1. As discussed in Section 4.2, in certain networks there is a
significant per-packet MAC overhead that is independent of packet
size.
2. A reduction in the size of ACKs does not prevent adverse
interaction with large upstream data packets in the presence of
bi-directional traffic (discussed in Section 4.4).
Expires September 2000 [page 6]
INTERNET DRAFT PILC - Asymmetric Links March 2000
Hence in order to effectively address the performance problems
caused by asymmetry, there is a need for techniques over and beyond
TCP header compression.
5.1.2 ACK filtering
ACK filtering (AF) is a TCP-aware link-layer technique that reduces
the number of TCP ACKs sent on the reverse channel. The challenge is
to ensure that the sender does not stall waiting for ACKs, which can
happen if ACKs are removed indiscriminately on the reverse path. AF
removes only certain ACKs without starving the sender by taking
advantage of the fact that TCP ACKs are cumulative. As far as the
sender's error control mechanism is concerned, the information
contained in an ACK with a later sequence number subsumes the
information contained in any earlier ACK
When an ACK from the receiver is about to be enqueued at a reverse
direction router, the router or the end-host's link layer (if the
host is directly connected to the constrained link) checks its
queues for any older ACKs belonging to the same connection. If any
are found, it removes them from the queue, thereby reducing the
number of ACKs that go back to the sender. The removal of these
"redundant" ACKs frees up buffer space for other data and ACK
packets. AF does not remove duplicate or selective ACKs from the
queue to avoid causing problems to TCP's data-driven loss recovery
mechanisms.
The policy that the filter uses to drop packets is configurable and
can either be deterministic or random (similar to a random-drop
gateway, but taking the semantics of the items in the queue into
consideration). State needs to be maintained only for connections
with at least one packet in the queue (akin to FRED [LM97]).
However, this state is soft, and if necessary, can easily be
reconstructed from the contents of the queue.
5.1.3 ACK congestion control
ACK congestion control (ACC) is an alternative to ACK filtering that
operates end-to-end rather than at the upstream bottleneck router.
The key idea in ACC is to extend congestion control to TCP ACKs,
since they do make non-negligible demands on resources at the
bandwidth-constrained upstream link. ACKs occupy slots in the
reverse channel buffer, whose capacity is often limited to a certain
number of packets (rather than bytes).
ACC has two parts: (a) a mechanism for the network to indicate to
the receiver that the ACK path is congested, and (b) the receiver's
response to such an indication. One possibility for the former is
the RED (Random Early Detection) algorithm [11] at the upstream
bottleneck router. The router detects incipient congestion by
tracking the average queue size over a time window in the recent
past. If the average exceeds a threshold, the router selects a
Expires September 2000 [page 7]
INTERNET DRAFT PILC - Asymmetric Links March 2000
packet at random and marks it, i.e. sets an Explicit Congestion
Notification (ECN) bit in the packet header. This notification is
reflected back to the upstream TCP end-host by its downstream peer.
It is important to note that with ACC, both data packets and TCP
ACKs are candidates for being marked with an ECN bit. Therefore,
upon receiving an ACK packet with the ECN bit set, the TCP receiver
reduces the rate at which it sends ACKs. The TCP receiver maintains
a dynamically varying delayed-ack factor, d, and sends one ACK for
every d data packets received. When it receives a packet with the
ECN bit set, it increases d multiplicatively, thereby decreasing the
frequency of ACKs also multiplicatively. Then for each subsequent
round-trip time (determined using the TCP timestamp option) during
which it does not receive an ECN, it linearly decreases the factor
d, thereby increasing the frequency of ACKs. Thus, the receiver
mimics the standard congestion control behavior of TCP senders in
the manner in which it sends ACKs.
There are bounds on the delayed-ack factor d. Obviously, the minimum
value of d is 1, since at most one ACK should be sent per data
packet. The maximum value of d is determined by the sender's window
size, which is conveyed to the receiver in a new TCP option. The
receiver should send at least one ACK (preferably more) for each
window of data from the sender. Otherwise, it could cause the sender
to stall until the receiver's delayed-ack timer (usually set at 200
ms) kicks in and forces an ACK to be sent.
Despite RED+ECN, there may be times when the upstream router queue
fills up and it needs to drop a packet. The router can pick a packet
to drop in various ways. For instance, it can drop from the tail, or
it can drop a packet already in the queue at random.
5.1.4 Acks-first scheduling
In the case of bi-directional transfers, data as well as ACK packets
compete for resources in the reverse direction (Section 4.4). In
this case, a single FIFO queue for both data packets and ACKs could
cause problems. For example, if the reverse channel is a 28.8 Kbps
dialup line, the transmission of a 1 KB sized data packet would take
about 280 ms. So even if just two such data packets get queued ahead
of ACKs (not an uncommon occurrence since data packets are sent out
in pairs during slow start), they would shut out ACKs for well over
half a second. And if more than two data packets are queued up ahead
of an ACK, the ACKs would be delayed by even more.
A possible approach to alleviating this problem is to schedule data
and ACKs differently from FIFO. One algorithm, in particular, is
acks-first scheduling, which always accords a higher priority to
ACKs over data packets. The motivation for such scheduling is that
it minimizes the idle time for the forward connection by minimizing
the amount of time that its ACKs spend queued behind upstream data
packets. At the same time, with techniques such as header
compression [RFC1144], the transmission time of ACKs becomes small
Expires September 2000 [page 8]
INTERNET DRAFT PILC - Asymmetric Links March 2000
enough that its impact on subsequent data packets is minimal.
(Networks in which the per-packet overhead of the reverse channel is
large, e.g. packet radio networks, are an exception.)
Note that as with ACC, this scheduling scheme does not require the
gateway to explicitly identify or maintain state for individual TCP
connections.
Acks-first scheduling does not help avoid a delay due to a data
packet in transmission. On a slow uplink, such a delay could be
large if the data packet is large in size. One way of reducing the
delay is to fragment the data packet into small pieces before
transmission [RFC1990, RFC2686].
5.1.5 Backpressure and Fair Scheduling
Two techniques to address the problem of interference between data
packets and ACKs on the uplink are proposed in [KVR98]. The first
limits the number of data packets in the outgoing uplink queue by
applying backpressure to the TCP layer. In configurations where the
uplink network adapter is directly attached to the end-system,
backpressure limits the queuing delay caused by the accumulation of
data packets at the upstream queue.
Backpressure can be unfair to the upstream connection and make its
throughput highly sensitive to the dynamics of the downstream
connection. So an alternative, fair scheduling, is proposed in
[KVR98] where a limit is placed on the number of ACKs a node is
allowed to transmit upstream before transmitting a data packet
(assuming at least one data packet is waiting in the upstream
queue). This guarantees the upstream connection at least a certain
minimum share of the bandwidth while enabling the downstream
connection to achieve high throughput.
5.2 Handling infrequent ACKs
This can be done either end-to-end or locally at the constrained
reverse link.
5.2.1 TCP sender adaptation
ACC and AF alleviate the problem of congestion on the reverse
bottleneck link by decreasing the frequency of ACKs, with each ACK
potentially acknowledging several data packets. As discussed in
Section 4.1, this can cause problems such as sender burstiness and a
slowdown in congestion window growth.
Sender adaptation is an end-to-end technique for alleviating this
problem. A bound is placed on the maximum number of packets the
sender can transmit back-to-back, even if the window allows the
transmission of more data. If necessary, more bursts of data are
scheduled for later points in time computed based on the
connection's data rate. The data rate is estimated as the ratio
Expires September 2000 [page 9]
INTERNET DRAFT PILC - Asymmetric Links March 2000
cwnd/srtt, where cwnd is the TCP congestion window size and srtt is
the smoothed RTT estimate. Thus, large bursts of data get broken up
into smaller bursts spread out over time.
The sender can avoid a slowdown in congestion window growth by
simply taking into account the amount of data acknowledged by each
ACK, rather than the number of ACKs. So, if an ACK acknowledges s
segments, the window is grown as if s separate ACKs had been
received. (One could treat the single ACK as being equivalent to s/2
instead of s ACKs to mimic the effect of the TCP delayed ack
algorithm.) This policy works because the window growth is only tied
to the available bandwidth in the forward direction, so the number
of ACKs is immaterial.
5.2.2 ACK Reconstruction
ACK reconstruction is a technique to reconstruct the ACK stream
after it has traversed the reverse direction bottleneck link. AR is
a local technique designed to prevent the reduced ACK frequency from
adversely affecting the performance of standard TCP sender
implementations (i.e., those that do not implement sender
adaptation). This enables us to use schemes such as ACK filtering or
ACK congestion control without requiring TCP senders to be modified
to perform sender adaptation. This solution can be easily deployed
by Internet Service Providers (ISPs) of asymmetric access technol-
ogies in conjunction with AF to achieve good performance.
AR deploys a soft-state agent called the ACK reconstructor at the
upstream end of the constrained ACK bottleneck. The reconstructor
does not need to be on the forward data path. It carefully fills in
the gaps in the ACK sequence and introduces ACKs to smooth out the
ACK stream seen by the sender. However, it does so without violating
the end-to-end semantics of TCP ACKs, as explained below.
Suppose two ACKs, a1 and a2 arrive at the reconstructor after
traversing the constrained reverse link at times t1 and t2
respectively. Let a2 - a1 = delta_a > 1. If a2 were to reach the
sender soon after a1 with no intervening ACKs, at least delta_a
segments are burst out by the sender (if the flow control window is
large enough), and the congestion window increases by at most 1,
independent of delta_a. ACK reconstruction remedies this problematic
situation by interspersing ACKs to provide the sender with a larger
number of ACKs at a consistent rate, which reduces the degree of
burstiness and causes the congestion window to increase at a rate
governed by the forward bottleneck.
How is this done? One of the configurable parameters of the
reconstructor is ack_thresh, the ACK threshold, which determines the
spacing between interspersed ACKs at the output. Typically,
ack_thresh is set to 2, which follows TCP's standard delayed-ACK
policy. Thus, if successive ACKs arrive at the reconstructor
separated by delta_a, it interposes ceil(delta_a/ack_thresh) - 2
Expires September 2000 [page 10]
INTERNET DRAFT PILC - Asymmetric Links March 2000
ACKs, where ceil() is the ceiling operator. The other parameter
needed by the reconstructor is ack_interval, which determines the
temporal spacing between the reconstructed ACKs. To do this, it
measures the rate at which ACKs arrive at the input to the recon-
structor. This rate depends on the output rate from the constrained
reverse channel and on the presence of other traffic on that link.
The reconstructor uses an exponentially weighted moving average
estimator to monitor this rate; the output of the estimator is
delta_t, the average temporal spacing at which ACKs are arriving at
the reconstructor (and the average rate at which ACKs would reach
the sender if there were no further losses or delays).
If the reconstructor sets ack_interval equal to delta_t, then we
would essentially operate at a rate governed by the reverse
bottleneck link, and the resulting performance would be determined
by the rate at which unfiltered ACKs arrive out of the reverse
bottleneck link. If sender adaptation were being done, then the
sender behaves as if the rate at which acks arrive us
delta_a/delta_t. Therefore, a good method of deciding the temporal
spacing of reconstructed ACKs, ack_interval, is to equate the rates
at which increments in the ACK sequence happen in the two cases.
That is, the reconstructor sets ack_interval such that
delta_a/delta_t = ack_thresh/ack_interval, which implies that
ack_interval = (ack_thresh/delta_a)*delta_t. Therefore, the latest
ACK in current sequence, a2, is held back for a time roughly equal
to delta_t, and ceil(delta_a/ack_thresh) - 2 ACKs are evenly
interposed in this time.
Thus, by carefully controlling the number of and spacing between
ACKs, unmodified TCP senders can be made to increase their
congestion window at the right rate and avoid bursty behavior. ACK
reconstruction can be implemented by maintaining only "soft state"
[Clark88] at the reconstructor that can easily be regenerated if
lost. Note that the reconstructor generates no spurious ACKs and the
end-to-end semantics of the connection are completely preserved. The
trade-off in AR is between obtaining less bursty performance, a
better rate of congestion window increase, and a reduction in the
round-trip variation, versus a modest increase in the round-trip
time estimate at the sender. We believe that it is a good trade-off
in the asymmetric environments we are concerned with.
5.3 Alternatives to AF and AR
Techniques similar in vein to but more sophisticated than AF and AR
have also been proposed. One of them is ACK compaction and expansion
[Sam99] where the compacter discards older ACKs in the upstream
queue while retaining newer ACKs (just as in AF), but in addition
conveys the number of discarded ACKs and the total number of bytes
they acknowledge to its peer, the expander. The expander can then
regenerate the discarded ACKs without having to guess how many ACKs
had been discarded. This is an advantage compared to AF/AR. However,
it comes at the cost of new protocol machinery to convey the
Expires September 2000 [page 11]
INTERNET DRAFT PILC - Asymmetric Links March 2000
information about discarded ACKs from the compacter to the expander.
AF/AR does not require any new protocol machinery.
Another technique along similar lines is discussed in [Joh99]. An
ACK compressor concatenates multiple ACKs and sends them to the
decompressor together with the arrival time of the concatenated ACKs
into the queue. The decompressor then uses this information to
regenerate the individual ACKs. Like the ACK compacter/expander,
this scheme enables more accurate regeneration of ACKs compared to
AF/AR but at the cost of new protocol machinery.
6. Security Considerations
Security considerations in the context of this Internet Draft arise
primarily from the possible use of IPSEC by the end hosts:
1. With IPSEC ESP, the TCP header can neither be read nor modified
by intermediate entities. This rules out header compression, ACK
filtering, and ACK reconstruction.
2. With IPSEC AH or TF-ESP, the TCP header can be read but not
modified by intermediaries. This rules out ACK reconstruction but
allows ACK filtering. The enhanced header compression scheme
discussed in [RFC2505] would also work with AH.
7. Summary
In this Internet Draft, we have considered TCP performance problems
that arise from asymmetry in network links and have listed possible
solutions. We have considered asymmetry in bandwidth as well as
media-access. We have discussed techniques that alleviate congestion
due to ACKs and others that help a sender cope with infrequent ACKs.
Some of the techniques operate end-to-end while others operate
locally at the asymmetric link.
8. References
[Bal98] H. Balakrishnan, "Challenges to Reliable Data Transport over
Heterogeneous Wireless Networks", Ph.D. Thesis, University of
California at Berkeley, USA, August 1998
http://www.cs.berkeley.edu/~hari/thesis/
[BPK97] H. Balakrishnan, V. N. Padmanabhan, R. H. Katz, "The Effects
of Asymmetry on TCP Performance", Proc. ACM/IEEE Mobicom, Budapest,
Hungary, September 1997
[BPK99] H. Balakrishnan, V. N. Padmanabhan, R. H. Katz, "The Effects
of Asymmetry on TCP Performance", ACM Mobile Networks and
Expires September 2000 [page 12]
INTERNET DRAFT PILC - Asymmetric Links March 2000
Applications (MONET), 1999. This is an expanded journal version of
the Mobicom '97 paper.
[CR98] R. Cohen, S. Ramanathan, "TCP for High Performance in Hybrid
Fiber Coaxial Broad-Band Access Networks", IEEE/ACM Transactions on
Networking, February 1998.
[Joh99] G. Johansson, E-mail sent to the PILC mailing list, October
1999.
[KVR98] L. Kalampoukas, A. Varma, K. K. Ramakrishnan, "Improving TCP
Throughput over Two-Way Asymmetric Links: Analysis and Solutions",
Proc. ACM SIGMETRICS, June 1998.
[LM97] D. Lin, R. Morris, "Dynamics of Random Early Detection",
Proc. ACM SIGCOMM, 1997.
[LMS97] T. V. Lakshman, U. Madhow, B. Suter, "Window-based Error
Recovery and Flow Control with a Slow Acknowledgement Channel: A
Study of TCP/IP Performance", Proc. IEEE Infocom, Kobe, Japan, April
1997.
[Met] Metricom Inc., http://www.metricom.com
[Pad98] V. N. Padmanabhan, "Addressing the Challenges of Web Data
Transport", Ph.D. Thesis, University of California at Berkeley, USA,
September 1998 (also Tech Report UCB/CSD-98-1016)
http:// www.research.microsoft.com/~padmanab/phd-thesis.html
[RFC1144] V. Jacobson, "Compressing TCP/IP Headers for Low-Speed
Serial Links", RFC-1144, February 1990
[RFC1990] K. Sklower, B. Lloyd, G. McGregor, D. Carr, T. Coradetti,
"The PPP Multilink Protocol (MP)", RFC-1990, August 1996.
[RFC2026] S. Bradner, "The Internet Standards Process -- Revision
3", RFC-2026, October 1996.
[RFC2119] S. Bradner, " Key words for use in RFCs to Indicate
Requirement Levels", RFC-2119, March 1997.
[RFC2505] M. Degermark, B. Nordgren, S. Pink, "IP Header
Compression", RFC-2507, February 1999.
[RFC2686] C. Bormann, "The Multi-Class Extension to Multi-Link PPP",
RFC-2686, September 1999.
[Sam99] N. K. G. Samaraweera, "Return Link Optimization for Internet
Service Provision Using DVB-S Networks", ACM SIGCOMM CCR, July 1999.
Expires September 2000 [page 13]
INTERNET DRAFT PILC - Asymmetric Links March 2000
9. Acknowledgments
We are grateful to Randy Katz (UC Berkeley) for supervising our
research on asymmetric networks and contributing to some of the
ideas described in this document. We thank Metricom Inc. and Hybrid
Networks Inc. for providing us equipment to conduct experiments at
Berkeley, especially Mike Ritter (Metricom), Ed Moura (Hybrid), and
Subir Varma (Hybrid) for their support and comments.
We thank Spencer Dawkins, Aaron Falk, and the members of the PILC
mailing list for their valuable comments.
10. Authors' Addresses
Hari Balakrishnan
Laboratory for Computer Science
545 Technology Square
Massachusetts Institute of Technology
Cambridge, MA 02139
USA
Phone: +1-617-253-8713
Fax: +1-617-253-0147
Email: hari@lcs.mit.edu
Web: http://wind.lcs.mit.edu/~hari/
Venkata N. Padmanabhan
Microsoft Research
One Microsoft Way
Redmond, WA 98052
USA
Phone: +1-425-705-2790
Fax: +1-425-936-7329
Email: padmanab@microsoft.com
Web: http://www.research.microsoft.com/~padmanab/
Expires September 2000 [page 14]
INTERNET DRAFT PILC - Asymmetric Links March 2000
Full Copyright Statement
"Copyright (C) The Internet Society (date). All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph
are included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.
Expires September 2000 [page 15]