Internet DRAFT - draft-tcp-dcr
draft-tcp-dcr
Internet Engineering Task Force Sumitha Bhandarkar
INTERNET DRAFT A. L. Narasimha Reddy
draft-tcp-dcr-00.txt Texas A&M University
Expires : April 2004 October 2003
Improving the robustness of TCP to Non-Congestion Events.
Status of this Memo
This document is an Internet-Draft and is subject to 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.
Abstract:
This document proposes TCP-DCR, a simple modification to the TCP
congestion control algorithm to make it more robust to non-congestion
events. In the absence of explicit notification from the network, the
TCP congestion control algorithm treats the receipt of three
duplicate acknowledgements as an indication of congestion in the
network. This is not always correct, notably so in wireless networks
with channel errors or networks prone to excessive packet reordering,
resulting in degraded performance. TCP-DCR aims to remedy this by
delaying the congestion response of TCP for a short interval of time
tau, thereby creating room to handle any non-congestion events that
may have occurred. If at the end of the delay tau, the event is not
handled, then it is treated as a congestion loss. The modifications
themselves do not handle the non-congestion event, but rather rely on
some underlying mechanism to do this. This document discusses the
implications of delaying congestion response on the fairness, TCP-
compatibility and network dynamics, and the benefits to be gained by
applying the TCP-DCR modifications to TCP.
Bhandarkar/Reddy Expires April 2004 [Page 1]
draft-tcp-dcr-00 October 2003
1. Introduction
In the absence of explicit notification from the network, the TCP
sender treats the receipt of three duplicate acknowledgements
(dupacks, for short) as an indication of congestion in the network.
It responds by triggering the fast retransmit/fast recovery
algorithm, where the packet perceived to be lost is retransmitted and
the congestion window is reduced by half to relieve the congestion in
the network. When the reason for the generation of dupacks is not
congestion related, this reduction of the congestion window results
in sub-optimal performance.
The two chief non-congestion events that might cause the generation
of dupacks considered in this document are channel errors in wireless
networks and excessive packet reordering. Several different solutions
have been proposed in literature to improve the performance of TCP in
the presence of channel errors
[BB95,BPSK97,BS97,BSAK95,CLM99,MCGSW01,SVSB99,VMPM02,WT98,YB94] or
packet reordering[BA02,ZKFP02]. This document proposes TCP-DCR which
is a simple and unified solution to improve the robustness of TCP to
any non-congestion event. Even though the discussion here is focussed
on the two chief causes mentioned above, the solution is general
enough to be extended to other non-congestion events resulting in the
generation of dupacks.
Throughout the rest of this document, the term "TCP-DCR" is used to
refer to the modifications that need to be made to TCP to make it
robust to non-congestion events as well as to refer to the TCP flavor
to which the modifications have been applied.
2. Problem Description
The strength of TCP lies in its ability to adjust its sending rate
according to the perceived congestion in the network. In the absence
of explicit notification of congestion from the network, the
traditional TCP flavors use the loss of a packet as an indication of
congestion. In order to help the sender identify a lost packet the
receiver sends acknowledgements for every packet received in-order
and duplicate acknowledgements (dupacks) for every packet received
out-of-order. The acks were specified originally in order to clock
out new packets. The use of three dupacks as an indication of
congestion was added later. When the sender receives three
consecutive dupacks, it concludes that the packet is lost due to
congestion.
The TCP sender does not respond to the very first dupack, but waits
for three dupacks to allow for a mildly reordered packet to reach the
receiver, and possibly result in a cumulative acknowledgement.
Bhandarkar/Reddy Expires April 2004 [Page 2]
draft-tcp-dcr-00 October 2003
Limited Transmit, which is now Proposed Standard, allows the sender
to send new packets in response to the first and second dupacks. The
choice of waiting for three dupacks is purely heuristic. When the
network is responsible for non-negligible amounts of non-congestion
events, this trigger of three dupacks tends to be short and drastic.
The persistent occurance of non-congestion events causes the TCP
sender window to oscillate around a smaller value than what is
actually allowed by the congestion in the network, resulting in
degraded performance.
It is interesting at this point to review the prevalence of non-
congestion events on the Internet. The two chief causes that are
identified and targeted in this document are - wireless channel
errors, and packet reordering within the network. While the existence
of channel errors in the wireless networks is a well accepted fact,
there is a general perception that packet reordering within the
Internet is a rare phenomenon. Several recent measurement studies
[BPS99,JIDKT03] though have shown results contrary to this popular
sentiment. Even if we were to suppose that the amount of packet
reordering in the current Internet is negligibly small, the need for
almost in-order packet delivery places a severe constraint on the
design of novel routing algorithms, network components and
applications. For instance, high speed packet switches could cause
resequencing of packets and there has been work proposed in the
literature to ensure that packet ordering is maintained in such
switches [KM02]. Other examples are multi-path routing, high-delay
satellite links and some of the schemes proposed for differentiated
services architecture. By making TCP more robust to non-congestion
events, we aim to ease this restriction of always in-order delivery
on the design of the future Internet components.
3. Design Guidelines
The proposal for TCP-DCR in this document is motivated by the
following requirements -
* Improve the robustness of TCP to non-congestion events in general,
rather than on a case-by-case basis.
* Maintain the end-to-end TCP semantics.
* Require a minimal amount of modification to the network
infrastructure.
* The solution should lend itself to incremental deployment.
* After the modifications, the protocol should remain compatible with
existing flavors of TCP.
Bhandarkar/Reddy Expires April 2004 [Page 3]
draft-tcp-dcr-00 October 2003
4. Modifications to TCP
The TCP-DCR modifications involve simple changes regarding when the
fast retransmit/recovery algorithms should be triggered. The current
TCP flavors wait for three dupacks before responding as if a packet
is lost due to congestion. This document extends the concept further
by allowing the TCP-DCR sender to wait for an interval of tau after
receiving the first dupack before responding to it as if it were a
packet lost due to congestion. During the period tau, the TCP sender
sends one new packet for every incoming dupack, if the congestion
window allows it, similar to what is proposed by the Limited Transmit
algorithm [ABF01]. The sender also continues to increase the
congestion window during this period. However, since only one packet
is allowed to be sent in response to each dupack, the number of
packets on the link at any point remains the same as (or less than)
the number of packets on the link when the first dupack was received.
The following figure illustrates the behavior of TCP in the presence
of packet reordering, when the TCP-DCR modifications are applied.
|<-------- tau -------->|
Cong Response Delay Timer
Limited Transmit/Additive Increase
No Retransmission/Window Reduction ----+
|
Set Cong Response ------+ | Cong Resp Delay
Delay Timer | | Timer Cancelled
| | |
| <-- Round Trip Time --> | v v |
|
1 2 3 4 5 6 7 8 9 10 11 v
Sender ---,--,--,--,--,--,----------,-----,--,--,--,----------,-------
\ * \ \ \ \ / \ / \/ \/ \/ \ /
\ *\ \ \ \ / / / / / /
\ \* \ \ \ / / /
\ \ * \ \ / / / / / /
\ \ \ *\ \/ / / / / /
\ \ \ \*/\ / / / / /
\ \ \ \ * / / / / /
\ \ \/ \ \/* / / / /
\ \ /\ \ /\ / */ / /
\ \ \ \ \ / * /
\ / \ \/ \/ \/ / * /
\ / \ /\ /\ /\ / * /
Rcvr ----------------`-----`--`--`--`----------*--------------------
2 2 2 2 2 8
Figure 1: Behavior of TCP-DCR in the presence of packet reordering.
Bhandarkar/Reddy Expires April 2004 [Page 4]
draft-tcp-dcr-00 October 2003
As it can be seen from the figure, when the first dupack is received,
the congestion response delay timer is set. When three dupacks are
received, if the congestion response delay timer has not expired, the
fast retransmit/recovery algorithm is not triggered. If the
acknowledgement for the reordered packet reaches the sender before
the delay timer expires, then the timer is cancelled and the sender
does not suffer unnecessary reduction in the sending rate.
The following figure illustrates the behavior of TCP in the presence
of packet loss due to congestion, when the TCP-DCR modifications are
applied.
| <-------- tau ---------> |
Cong Response Delay Timer
Limited Transmit
Additive Window Increase
No Retransmission ------------+
No Window Reduction |
|
Set Cong Response ------+ |
Delay Timer | | Retransmission -+
| | Window Reduction |
| | |
| <-- Round Trip Time --> | v v v
1 2 3 4 5 6 7 8 9 10 11 12 2
---,--,--,--,--,--,----------,-----,--,--,--,----------,-----,--,--,--
\ \ \ \ \ \ / \ / \/ \/ \/ \ / \ / \/ /
\ \ \ \ \ \ / \ / /\ /\ /\ \ / / / /
\ \ \ \ \ \ / \ / \ \ \ \ / / / / /
\ \ \ \ \ \ / / \/ / \/ \ \ \ / / / / /
\ \ \ \ \ \/ / /\ / /\ \ \ \/ / / / /
\ \ \ \ \ /\ / / / / \ \ \ /\ / / / /
Cong Drop --> X \ \ \ \ / / / \/ \ \ \ \ / / / /
\ \ \/ \ \/ / / /\ \ \/ \ \/ / / /
\ \ /\ \ /\ / / / \ \ /\ \ /\ / / /
\ \ \ \ \ / / \ \ \ \ \ / /
\ / \ \/ \/ \/ / \ / \ \/ \/ \/ /
\ / \ /\ /\ /\ / \ / \ /\ /\ /\ /
----------------`-----`--`--`--`----------`-----`--`--`--`-----------
2 2 2 2 2 2 2 2 2 2
Figure 2: Behavior of TCP-DCR in presence of packet loss due to congestion.
The figure above shows the behavior of a TCP flow with the TCP-DCR
modifications when a packet has been dropped due to congestion in the
Bhandarkar/Reddy Expires April 2004 [Page 5]
draft-tcp-dcr-00 October 2003
network. In this case a cumulative acknowledgement is not received
before the congestion delay timer expires. As a result, as soon as
the congestion delay timer expires, the fast retransmit/recovery
algorithm is triggered. The next section discusses the upper
threshold on the delay tau so that this delay in congestion response
does not adversely affect the throughput obtained by the flow using
TCP-DCR modifications or the non TCP-DCR flows competing with it.
4.1. Choice of the delay duration (tau)
The current implementations of TCP wait for three dupacks before
treating them as an indication of packet loss due to congestion. The
choice of waiting for three dupacks is heuristic. This document
proposes that the delay before responding to congestion should be
longer, so that underlying schemes have time to recover from non-
congestion events. There is no optimal value for this delay such that
all possible non-congestion events can be recovered. It is
essentially a tradeoff between unnecessarily inferring congestion,
and unnecessarily waiting for a long time before retransmitting a
lost packet. Therefore, the choice of the delay is really choosing a
place on the spectrum for the tradeoffs between these two concerns.
This document aims to provide guidelines for reasonable bounds on the
delay to make it useful, without adversely modifying the TCP
behavior.
Consider the case of wireless channel errors. The figure below shows
a general scenario where the TCP sender is connected to the base
station by a wired link and the TCP receiver is connected to a base
station over a wireless link. The wired path between the base station
and the sender TCP could consist of several hops, but would not
affect the discussion here and so is shown as a single hop. The round
trip time between the base station and wireless link is indicated by
'rtt' and the end-to-end round trip time between the TCP sender and
the TCP receiver is indicated by 'RTT'.
+---------------+
| rtt |
| |
wired | wireless |
TCP link V link | TCP
Sender 0-----------------0---------------0 Receiver
^ Base |
| Station |
| |
| RTT |
+---------------------------------+
Figure 3: General scenario for a wireless network.
Bhandarkar/Reddy Expires April 2004 [Page 6]
draft-tcp-dcr-00 October 2003
In the above scenario, if we ignore ambient delays (e.g., inter-
packet delay, queuing delay, etc.), a packet sent by the TCP sender
at some time 't0' reaches the base station at 't0 + (RTT/2 - rtt/2)'
and the receiver at time 't0 + RTT/2'. Suppose, a packet 'k' sent at
time 't0' is lost on the wireless link due to channel errors. Then at
't0 + RTT/2 + rtt/2' the base station receives an indication that the
packet 'k' is lost. If it immediately retransmits the packet, then
the packet 'k' is recovered at the receiver at time 't0 + RTT/2 +
rtt'. The sender receives an acknowledgement for the packet 'k' at
't0 + RTT/2 + rtt + RTT/2'. Hence the sender would have to delay the
congestion response by at least 'rtt' time units, to allow the link
layer to recover the packet. In practice, the inter-packet delays are
non-zero and the TCP sender does not know the value of 'rtt'. Hence,
a simple solution would be to set the lower bound on the delay in
congestion response to one 'RTT'.
The upper bound on the delay is imposed by the retransmission timer
of TCP. The delay should be chosen such that the RTO timeout is
avoided, because a timeout would be detrimental to the performance of
protocol. The RTO is usually set to (RTT + 4 * RTTVAR). The standard
recommends a minimum of 1 second, but many TCP implementations have a
much smaller minimum, e.g., 100 ms. This forms the upper bound on the
value for the congestion response delay tau.
Based on the above discussion, this document recommends the value of
tau to be set as one RTT. In the case of packet reordering, the
amount by which the packet is reordered could be highly variable. The
time to recover the lost packet is the time that the reordered packet
takes to reach the receiver. Hence there is no preset lower bound for
the delay tau, that will facilitate the recovery of a packet
reordered by any amount. However, the upper bound is still decided by
the discussion above. So, a value of one RTT for tau is still a
reasonable choice. We conducted the analysis of the steady state
bandwidth realized by TCP-DCR [BR03]. The results of the analysis
show that the TCP-DCR modifications do not affect the steady state
bandwidth.
TCP-DCR does not increase the per-packet delivery time when there is
no congestion in the network. However, when a packet is dropped, the
choice of tau = one RTT may add upto one additional RTT of delay in
recovering the lost packet. An important fact to remember here is
that, the choice of tau does not cause the TCP-DCR sender to
dramatically over-send packets because the protocol is still ACK-
clocked. That is, a new packet is sent only upon the receipt of a
dupack. If there is suddenly very high congestion in the network
resulting in the drop of several packets, the TCP sender will have
reduced its sending rate simply because not many dupacks are coming
back.
Bhandarkar/Reddy Expires April 2004 [Page 7]
draft-tcp-dcr-00 October 2003
4.2. Implementation Details
The TCP-DCR modifications need to be applied only to the sender and
the receiver remains unmodified. The sender can implement the delay
in congestion response (tau) by using either a timer or by modifying
the threshold on the number of duplicate acknowledgements to be
received before triggering fast retransmit/recovery. The timer-based
implementation is quite straight forward, but is influenced by the
coarseness in the clock granularity. In the ack-based delay
implementation, the sender could delay responding to congestion for
the number of duplicate acknowledgements corresponding to the delay
required. Thus, if 'tau' is chosen to be one RTT, the sender would
wait for the receipt of 'W' duplicate acknowledgements before
responding to congestion, where 'W' is the size of the congestion
window when the packet loss is detected.
The TCP-DCR modifications work with most flavors of the TCP protocol.
However, this document advocates the use of TCP-DCR with TCP-SACK to
ensure that the performance can be maintained high even under the
conditions of multiple losses per round trip time. When used with
TCP-SACK, the only thing modified by TCP-DCR is the time at which the
fast retransmit/recovery algorithm is triggered in response to
dupacks generated by the first loss within a window of packets. All
subsequent losses within the same window (irrespective of whether
they are congestion related or non-congestion events) are handled in
exactly the same way as TCP-SACK would in the absence of TCP-DCR
modifications. If the receiver is not SACK-capable, however, then the
sender will have to use TCP-DCR with NewReno.
4.3. Receiver Buffer Requirement when TCP-DCR is used
When TCP-DCR is used, the receiver will need to have additional
buffer space to accommodate the extra packets corresponding to the
delay 'tau', when a packet is lost due to congestion. Having these
extra buffers allows TCP-DCR to achieve the best performance.
However, if the buffers are not available, it does not degrade the
performance, but the maximum performance improvement is not achieved.
This is because, apart from congestion control, TCP also provides
flow control such that a faster sender does not flood a slow
receiver. The flow control is achieved by using a receiver advertised
window, such that at any point the TCP sender may not send more
packets than that allowed by 'min(cwnd,rwnd)' where 'cwnd' is the
congestion window and 'rwnd' is the receiver advertised window. When
the buffer space is not available, the receiver advertised window is
small. As a result, during the delay 'tau' even though the limited
transmit and congestion window allow a packet to be transmitted it
will not be sent if the 'rwnd' (and hence the receiver buffer) does
not allow it. However, the TCP sender can still delay the congestion
Bhandarkar/Reddy Expires April 2004 [Page 8]
draft-tcp-dcr-00 October 2003
response by 'tau' allowing the local recovery mechanism to recover
from non-congestion event.
4.4. Underlying mechanisms for recovering from non-congestion events
The performance benefits to be gained from using the TCP-DCR
modifications depends heavily on the existence of an underlying
scheme for recovering from the non-congestion events. In the case of
packet reordering, no explicit scheme is required to recover the
reordered packet; the reordered packet reaches the receiver after the
delay that caused it to appear out-of-order. In the case of wireless
networks, a packet corrupted due to channel errors might be recovered
through link-level mechanisms such as link-level retransmissions or
FEC (Forward Error Correction). If the corrupted packet is not
recovered through link-level mechanisms, it will be interpreted by
TCP as a packet lost due to congestion, and retransmitted by TCP.
5. Performance Evaluation
This section of the document provides a glimpse of the performance
improvements to be gained by the use of TCP-DCR modifications. The
results presented here are only a small subset of the results
presented in [BR03]. The results are based on simulations on the ns-2
simulator [NS-2].
5.1. Network with packet reordering
The table below shows the effect of delayed packets on the
performance of TCP-SACK and the corresponding improvement in the
performance in case of TCP-DCR. The experiment is conducted with a
dumbell topology with the bottleneck link bandwidth set to 8Mbps.
The end-to-end RTT is set to 104ms. The receiver advertises a very
large window such that the sending rate is not clamped by the
receiver dynamics. There is no congestion in the network. The
topology consists of a single flow. The packet delay is picked from a
normal distribution with a mean of 25ms and a standard deviation of
8ms. Thus, most packets chosen for delaying are delayed in the range
0 to 50ms, simulating mild but persistent reordering. The throughput
of TCP-SACK without the TCP-DCR modifications degrades drastically.
However, when the TCP-DCR modifications are applied the performance
is very good even when a large percentage of the packets are delayed.
Percentage Throughput of Throughput of
of Packets TCP-SACK without TCP-SACK with
Delayed TCP-DCR modifications TCP-DCR modifications
(%) (Mbps) (Mbps)
---------- --------------------- ---------------------
0.0 7.325 7.352
Bhandarkar/Reddy Expires April 2004 [Page 9]
draft-tcp-dcr-00 October 2003
1.0 1.043 7.339
2.0 0.795 7.309
5.0 0.571 7.185
8.0 0.498 7.095
10.0 0.476 7.061
15.0 0.440 7.000
20.0 0.410 7.008
25.0 0.409 7.014
30.0 0.404 7.006
5.2. Wireless Networks with Channel Errors
The table below shows the effect of channel errors on the performance
of TCP-SACK with and without the TCP-DCR modifications. The topology
for the experiment consists of a sender connected via a wired link to
a router which in turn is connected to the base station by a wired
link. The bandwidth of the wired links is 100Mbps and the delay is
5ms. The receiver is connected to the base station by a link
simulating a satellite connection with a lower bandwidth and a larger
delay. The bandwidth of this link is 1Mbps and the delay is 250ms.
Packets are randomly chosen to be corrupted by channel errors. Link
level retransmission is simulated by retransmitting the corrupted
packet after a delay corresponding to the round trip time of the
wireless link.
Channel Throughput of Throughput of
Error TCP-SACK without TCP-SACK with
Rate TCP-DCR modifications TCP-DCR modifications
(%) (Mbps) (Mbps)
---------- --------------------- --------------------
0.0 0.962 0.962
0.5 0.261 0.957
1.0 0.186 0.952
2.0 0.131 0.943
3.0 0.107 0.934
4.0 0.094 0.925
5.0 0.086 0.917
6.0 0.081 0.908
7.0 0.078 0.900
8.0 0.073 0.892
5.3. Fairness Implications
This section of the document addresses the fairness issues raised by
delaying congestion response. The steady state analysis of TCP-DCR
[BR03] shows that the throughput of the TCP-DCR protocol is similar
to that of TCP [PFTK98]. Thus, the congestion control dynamics of
Bhandarkar/Reddy Expires April 2004 [Page 10]
draft-tcp-dcr-00 October 2003
TCP-DCR are TCP-friendly. Essentially, TCP-DCR can be seen as a
slowly-responsive TCP-friendly flow as explained in [BBFS01]. It has
been shown in that paper that such flows are TCP-compatible.
Simulation results agree with the discussion above. The following
table shows the average throughput achieved by flows using TCP-SACK
without the TCP-DCR modifications compared to flows using TCP-SACK
with the TCP-DCR modifications in a congested network. The dumbell
topology is used for this experiment with the bottleneck link
capacity of 10Mbps being shared by 12 flows, half of which are TCP-
SACK without TCP-DCR modifications and the other half are TCP-SACK
with the TCP-DCR modifications. There are no non-congestion losses in
the network and congestion is induced by modifying the buffers
available at the bottleneck router. The throughput of each individual
flow varies only slightly from the average throughput.
Congestion Avg. Throughput Avg. Throughput
Droprate of TCP-SACK without of TCP-SACK with
(%) TCP-DCR Modifications TCP-DCR Modifications
(Mbps) (Mbps)
----------- ---------------------- ---------------------
0.06 0.808 0.795
0.36 0.820 0.782
1.51 0.837 0.765
1.86 0.828 0.774
2.44 0.836 0.767
3.43 0.767 0.835
4.57 0.724 0.874
5.76 0.719 0.788
5.4. Effect on Network Dynamics
When the loss of a packet is indeed due to congestion, delaying the
congestion response could make the protocol sluggish at relieving
congestion in the network. However, when the delay is bounded by one
RTT, the behavior of TCP-DCR is not significantly different from a
TCP flow with high variance in RTT measurements. During the
congestion response delay, the TCP-DCR flow appears like a flow whose
RTT is twice the value when there is no congestion in the network.
Performance evaluation through simulations has validated this view
[BR03].
6. Implementation Issues
The TCP-DCR modifications presented by this document are quite simple
and do not require complicated changes. When the delay "tau" is
implemented based on a timer, the timer value can be set to the
Bhandarkar/Reddy Expires April 2004 [Page 11]
draft-tcp-dcr-00 October 2003
smoothed value of RTT (SRTT). However, when the delay "tau" is
implemented by modifying the threshold on the number of dupacks to be
received before responding, the RTT value being used is essentially
the instantaneous value. The upper bound on the congestion response
delay is established by the RTO estimate which is computed based on
the smoothed RTT. This could potentially lead to a situation where
the value of the congestion response delay is larger than the value
of the RTO. Though such a situation could be fairly rare, even few
unnecessary timeouts can degrade the performance drastically. So,
this document recommends that the new threshold on the number of
dupacks to wait before responding be scaled by the factor
(SRTT)/(Current RTT Estimate).
We have implemented the TCP-DCR modifications in the Linux 2.4.20
kernel. The modifications require changes of only a few lines of
code. Currently, we are in the process of evaluating the reordering
robustness provided by native Linux implementations against that of
TCP-DCR.
7. Incremental Deployment
The TCP-DCR modifications proposed in this document lend themselves
to incremental deployment. Only the TCP protocol on the sender side
needs to be modified. The modifications themselves are minor and can
be distributed easily as kernel patches. The use of TCP-DCR does not
require the sender and receiver to negotiate any conditions during
connection setup. Neither the receivers nor the routers need to be
aware that the sender has been enhanced with the TCP-DCR
modifications. Availability of additional buffers at the receiver
will help maximize the benefits of using TCP-DCR but are not
necessary.
8. Relationship to other work
Over the past few years, several solutions have been proposed to
improve the performance of TCP over wireless networks. These
solutions fall in one of the following broad categories: split
connection approaches [BB95,BS97,WT98,YB94], TCP-aware link layer
protocols [BSAK95,CLM99], explicit loss notification approaches
[BK98,KAPS02,RF99] and receiver-based approaches [SVSB99,VMPM02]. All
the above mentioned schemes are proposed explicitly for improving the
performance of TCP in wireless networks. While some of them could
possibly be used in situations with other types of non-congestion
events, the simplicity of TCP-DCR in our opinion, makes it a far more
compelling solution for the problem.
It has been shown that the performance of TCP over wireless networks
can be improved by using other flavors of TCP. For example, by using
Bhandarkar/Reddy Expires April 2004 [Page 12]
draft-tcp-dcr-00 October 2003
TCP-SACK [MMFR96] or TCP-westwood [MCGSW01] instead of standard
implementations of TCP Reno, performance can be improved. The
performance improvement by using TCP-SACK protocol however, is due to
its ability to recover from multiple losses in one RTT and does not
necessarily indicate robustness to non-congestion events. This
document advocates the use of TCP-DCR modifications with the TCP-SACK
flavor.
Different solutions have been proposed in the literature to improve
the performance of TCP when the network reorders packets
persistently. In [BA02] the authors present several schemes which use
DSACKs [FMMP00] (or could alternatively use timestamps [LM03] or
other methods) to identify a false fast retransmit. In response, the
sending rate is restored back to the level it was before the false
fast retransmit. The reordering length for the packet is measured
using the information available from DSACKs and the threshold on the
number of dupacks to be received before responding (dupthresh) is
increased to avoid future false fast retransmits. If a RTO timeout
occurs, then it is presumed that the dupthresh has grown too large
and it is reset to 3. In [ZKFP02] this process is further refined at
the cost of maintaining significantly more state at the sender and
using complicated algorithms for finding the optimal value for
dupthresh such that costly RTO timeouts are avoided, while the
performance is optimized to provide maximum reordering robustness.
These solutions rely on some additional scheme for identifying
reordering in the network (such as DSACKs or timestamps) and the
perceived reordering information is collected from the network to set
an optimal value for dupthresh. The Linux TCP provides an option of
using either of these additional schemes or just the information from
SACK to estimate the reordering length. The intent is to estimate the
optimal amount of time to delay the triggering of fast
retransmit/recovery algorithms to provide maximum reordering
robustness, without resorting to RTO timeouts too often. By using
TCP-DCR, this goal can be met without having to use complex state or
algorithms for tuning the value of dupthresh. While TCP-DCR does not
tune the dupthresh based on the perceived reordering in the network,
when it is set to one RTT, it provides a simple and effective
mechanism for providing reordering robustness without causing RTO
timeouts. If the actual reordering within the network is less than
one RTT, then no harm is done since no action is necessary when the
packet is recovered. When the packet is reordered by more than one
RTT, TCP-DCR does not wait for it it to be recovered, but in doing so
avoids costly retransmission timeouts.
9. Security Considerations
This proposal makes no changes to the underlying security of TCP.
Bhandarkar/Reddy Expires April 2004 [Page 13]
draft-tcp-dcr-00 October 2003
10. Conclusions
This document has proposed TCP-DCR modifications to TCP's congestion
control mechanism to make it more robust to non-congestion events. We
have explored this proposal though analysis and simulations, and are
currently in the process of evaluating it through experiments on the
Linux platform. We believe that TCP-DCR provides a simple, unified
solution to improve the the robustness of TCP to non-congestion
events, and that the solution is safe to deploy on the Internet. We
would welcome additional analysis, simulations, and experimentation.
We are bringing this proposal to the IETF to be considered as an
Experimental RFC.
11. Acknowledgements
We would like to thank Dr. Nitin Vaidya and Nauzad Sadry for their
invaluable help with the wireless simulations. Comments from Sally
Floyd have helped immensely in improving the quality of this
document.
12. References
[ABF01] M. Allman, H. Balakrishnan, and S. Floyd, "Enhancing TCP's
Loss Recovery Using Limited Transmit," RFC 3042, Proposed Standard,
January 2001.
[BA02] E. Blanton and M. Allman, "On Making TCP More Robust to Packet
Reordering," ACM Computer Communication Review, January 2002.
[BB95] A. Bakre and B. R. Badrinath, "I-TCP: indirect TCP for mobile
hosts," Proceedings of the 15th. International Conference on
Distributed Computing Systems (ICDCS), May 1995.
[BBFS01] D. Bansal, H. Balakrishnan, S. Floyd and Scott Shenker,
"Dynamic Behavior of Slowly Responsive Congestion Control
Algorithms," Proceedings of ACM SIGCOMM, Sep. 2001.
[BK98] H. Balakrishnan and R. H. Katz, "Explicit Loss Notification
and Wireless Web Performance," Proc. of IEEE GLOBECOM, Nov. 1998.
[BPS99] J. Bennett, C. Partridge, and N. Shectman, "Packet reordering
is not pat hological network behavior," IEEE/ACM Transactions on
Networking, December 1999.
[BPSK97] H. Balakrishnan, V. Padmanabhan, S. Seshan, and R. H. Katz,
"A Comparison of Mechanisms for Improving TCP Performance over
Wireless Links," IEEE/ACM Transactions on Networking, 1997.
Bhandarkar/Reddy Expires April 2004 [Page 14]
draft-tcp-dcr-00 October 2003
[BR03] Sumitha Bhandarkar, and A. L. N. Reddy, "TCP-DCR: Making TCP
Robust to Non-Congestion Losses," Technical Report TAMU-ECE-2003-04,
July 2003.
[BS97] K. Brown and S. Singh, "M-TCP: TCP for mobile cellular
networks," ACM Computer Communications Review, vol. 27, no. 5,
1997.
[BSAK95] H. Balakrishnan, S. Seshan, E. Amir and R. Katz, "Improving
TCP/IP performance over wireless networks," Proc. of ACM MOBICOM,
Nov. 1995.
[CLM99] H. M. Chaskar, T. V. Lakshman, and U. Madhow, "TCP Over
Wireless with Link Level Error Control: Analysis and Design
Methodology", IEEE Trans. on Networking, vol. 7, no. 5, Oct. 1999.
[FMMP00] Sally Floyd, Jamshid Mahdavi, Matt Mathis and Matt Podolsky,
"An Extension to the Selective Acknowledgement (SACK) Option for
TCP," RFC 2883, July 2000.
[JIDKT03] S. Jaiswal, G. Iannaccone, C. Diot, J. Kurose, and D.
Towsley, "Measur ement and Classification of Out-of-Sequence Packets
in a Tier-1 IP Backbone," Pr oceedings of IEEE INFOCOM, 2003.
[KAPS02] R. Krishnan, M. Allman, C. Partridge and J. P.G. Sterbenz,
"Explicit Transport Error Notification for Error-Prone Wireless and
Satellite Networks," BBN Technical Report No. 8333, BBN Technologies,
February, 2002
[KM02] I. Keslassy and N. McKeown, "Maintaining packet order in
twostage switche s," Proceedings of the IEEE Infocom, June 2002
[LM03] R. Ludwig and M. Meyer, "The Eifel Detection Algorithm for
TCP," RFC 3522, April 2003.
[MCGSW01] S. Mascolo, C. Casetti, M. Gerla, M. Sanadidi and R. Wang,
"TCP Westwood: Bandwidth Estimation for Enhanced Transport over
Wireless Links," Proceedings of ACM MOBICOM, 2001.
[MMFR] M. Mathis, J. Mahdavi, S. Floyd and A. Romanow, "TCP selective
acknowledgment options," Internet RFC 2018.
[NS-2] ns-2 Network Simulator. http://www.isi.edu/nsnam/
[RF99] K. Ramakrishnan and S. Floyd, "A Proposal to add Explicit
Congestion Notification (ECN) to IP," RFC 2481, January 1999.
[SVSB99] P. Sinha, N. Venkitaraman, R. Sivakumar and V. Bhargavan,
Bhandarkar/Reddy Expires April 2004 [Page 15]
draft-tcp-dcr-00 October 2003
"WTCP: A Reliable Transport Protocol for Wireless Wide-Area
Networks," Proceedings of ACM MOBICOM, August 1999.
[VMPM02] N. H. Vaidya, M. Mehta, C. Perkins and G. Montenegro,
"Delayed Duplicate Acknowledgement: a TCP-unaware Approach to Improve
Performance of TCP over Wireless," Journal of Wireless Communications
and Mobile Computing, special issue on Reliable Transport Protocols
for Mobile Computing, February 2002.
[WT98] K.-Y. Wang and S. K. Tripathi, "Mobile-end transport protocol:
An alternative to TCP/IP over wireless links," IEEE INFOCOM'98,
vol. 3, p. 1046, 1998.
[YB94] R. Yavatkar and N. Bhagawat, "Improving End-to-End Performance
of TCP over Mobile Internetworks," Workshop on Mobile Computing
Systems and Applications, December 1994.
[ZKFP02] M. Zhang, B. Karp, S. Floyd, and L. Peterson, "RR-TCP: A
Reordering-Robust TCP with DSACK," ICSI Technical Report TR-02-006,
Berkeley, CA, July 2002.
13. Author's Addresses
Sumitha Bhandarkar
Dept. of Elec. Engg.
214 ZACH
College Station, TX 77843-3128
Phone: (512) 468-8078
Email: sumitha@tamu.edu
URL : http://students.cs.tamu.edu/sumitha/
A. L. Narasimha Reddy
Associate Professor
Dept. of Elec. Engg.
315C WERC
College Station, TX 77843-3128
Phone : (979) 845-7598
Email : reddy@ee.tamu.edu
URL : http://ee.tamu.edu/~reddy/
Bhandarkar/Reddy Expires April 2004 [Page 16]
