W_HighSpeed/W_Standard times the throughput of a single Standard TCP
connection competing in the same environment.
This relative fairness is illustrated below in Table 5, for the
parameters used for the Highspeed response function in the section
above. The second column gives the relative fairness, for the
steady-state packet drop rate specified in the first column. To help
calibrate, the third column gives the aggregate average congestion
window for the two TCP connections, and the fourth column gives the
bandwidth that would be needed by the two connections to achieve that
aggregate window and packet drop rate, given 100 ms round-trip times
and 1500-byte packets.
Packet Drop Rate P Fairness Aggregate Window Bandwidth
------------------ -------- ---------------- ---------
10^-2 1.0 24 2.8 Mbps
10^-3 1.0 76 9.1 Mbps
10^-4 2.2 383 45.9 Mbps
10^-5 4.7 2174 260.8 Mbps
10^-6 10.2 13479 1.6 Gbps
10^-7 22.1 87776 10.5 Gbps
Table 5: Relative Fairness between the HighSpeed and Standard
Response Functions.
Thus, for packet drop rates of 10^-4, a flow with the HighSpeed
response function can expect to receive 2.2 times the throughput of a
flow using the Standard response function, given the same round-trip
times and packet sizes. With packet drop rates of 10^-6 (or 10^-7),
the unfairness is more severe, and we have entered the regime where a
Standard TCP connection requires at most one congestion event every
800 (or 2530) round-trip times in order to make use of the available
bandwidth. Our judgement would be that there are not a lot of TCP
connections effectively operating in this regime today, with
congestion windows of thousands of packets, and that therefore the
benefits of the HighSpeed response function would outweigh the
unfairness that would be experienced by Standard TCP in this regime.
However, one purpose of this document is to solicit feedback on this
issue. The parameter Low_Window determines directly the point of
divergence between the Standard and HighSpeed Response Functions.
The third column of Table 5, the Aggregate Window, gives the
aggregate congestion window of the two competing TCP connections,
with HighSpeed and Standard TCP, given the packet drop rate specified
in the first column. From Table 5, a HighSpeed TCP connection would
receive ten times the bandwidth of a Standard TCP in an environment
with a packet drop rate of 10^-6. This would occur when the two
flows sharing a single pipe achieved an aggregate window of 13479
packets. Given a round-trip time of 100 ms and a packet size of 1500
bytes, this would occur with an available bandwidth for the two
competing flows of 1.6 Gbps.
Next we consider the time that it takes a standard or HighSpeed TCP
flow to converge to fairness against a pre-existing HighSpeed TCP
flow. The worst case for convergence to fairness occurs when a new
flow is starting up, competing against a high-bandwidth existing
flow, and the new flow suffers a packet drop and exits slow-start
while its window is still small. In the worst case, consider that
the new flow has entered the congestion avoidance phase while its
window is only one packet. A standard TCP flow in congestion
avoidance increases its window by at most one packet per round-trip
time, and after N round-trip times has only achieved a window of N
packets (when starting with a window of 1 in the first round-trip
time). In contrast, a HighSpeed TCP flows increases much faster than
a standard TCP flow while in the congestion avoidance phase, and we
can expect its convergence to fairness to be much better. This is
shown in Table 6 below. The script used to generate this table is
given in Appendix C.
RTT HS_Window Standard_TCP_Window
--- --------- -------------------
100 131 100
200 475 200
300 1131 300
400 2160 400
500 3601 500
600 5477 600
700 7799 700
800 10567 800
900 13774 900
1000 17409 1000
1100 21455 1100
1200 25893 1200
1300 30701 1300
1400 35856 1400
1500 41336 1500
1600 47115 1600
1700 53170 1700
1800 59477 1800
1900 66013 1900
2000 72754 2000
Table 6: For a HighSpeed and a Standard TCP connection, the
congestion window during congestion avoidance phase (starting with a
congestion window of 1 packet during RTT 1).
The classic paper on relative fairness is from Chiu and Jain [CJ89].
This paper shows that AIMD (Additive Increase Multiplicative
Decrease) converges to fairness in an environment with synchronized
congestion events. From [CJ89], it is easy to see that MIMD and AIAD
do not converge to fairness in this environment. However, the
results of [CJ89] do not apply to an asynchronous environment such as
that of the current Internet, where the frequency of congestion
feedback can be different for different flows. For example, it has
been shown that MIMD converges to fair states in a model with
proportional instead of synchronous feedback in terms of packet drops
[GV02]. Thus, we are not concerned about abandoning a strict model
of AIMD for HighSpeed TCP. However, we note that in an environment
with Drop-Tail queue management, there is likely to be some
synchronization of packet drops. In this environment, the model of
completely synchronous feedback does not hold, but the model of
completely asynchronous feedback is not accurate either. Fairness in
Drop-Tail environments is discussed in more detail in Sections 9 and
12.
7. Translating the HighSpeed Response Function into Congestion Control
Parameters
For equation-based congestion control such as TFRC, the HighSpeed
Response Function above could be used directly by the TFRC congestion
control mechanism. However, for TCP the HighSpeed response function
has to be translated into additive increase and multiplicative
decrease parameters. The HighSpeed response function cannot be
achieved by TCP with an additive increase of one segment per round-
trip time and a multiplicative decrease of halving the current
congestion window; HighSpeed TCP will have to modify either the
increase or the decrease parameter, or both. We have concluded that
HighSpeed TCP is most likely to achieve an acceptable compromise
between moderate increases and timely decreases by modifying both the
increase and the decrease parameter.
That is, for HighSpeed TCP let the congestion window increase by a(w)
segments per round-trip time in the absence of congestion, and let
the congestion window decrease to w(1-b(w)) segments in response to a
round-trip time with one or more loss events. Thus, in response to a
single acknowledgement HighSpeed TCP increases its congestion window
in segments as follows:
w <- w + a(w)/w.
In response to a congestion event, HighSpeed TCP decreases as
follows:
w <- (1-b(w))w.
For Standard TCP, a(w) = 1 and b(w) = 1/2, regardless of the value of
w. HighSpeed TCP uses the same values of a(w) and b(w) for w <=
Low_Window. This section specifies a(w) and b(w) for HighSpeed TCP
for larger values of w.
For w = High_Window, we have specified a loss rate of High_P. From
[FRS02], or from elementary calculations, this requires the following
relationship between a(w) and b(w) for w = High_Window:
a(w) = High_Window^2 * High_P * 2 * b(w)/(2-b(w)). (2)
We use the parameter High_Decrease to specify the decrease parameter
b(w) for w = High_Window, and use Equation (2) to derive the increase
parameter a(w) for w = High_Window. Along with High_P = 10^-7 and
High_Window = 83000, for example, we specify High_Decrease = 0.1,
specifying that b(83000) = 0.1, giving a decrease of 10% after a
congestion event. Equation (2) then gives a(83000) = 72, for an
increase of 72 segments, or just under 0.1%, within a round-trip
time, for w = 83000.
This moderate decrease strikes us as acceptable, particularly when
coupled with the role of TCP’s ACK-clocking in limiting the sending
rate in response to more severe congestion [BBFS01]. A more severe
decrease would require a more aggressive increase in the congestion
window for a round-trip time without congestion. In particular, a
decrease factor High_Decrease of 0.5, as in Standard TCP, would
require an increase of 459 segments per round-trip time when w =
83000.
Given decrease parameters of b(w) = 1/2 for w = Low_Window, and b(w)
= High_Decrease for w = High_Window, we are left to specify the value
of b(w) for other values of w > Low_Window. From [FRS02], we let
b(w) vary linearly as the log of w, as follows:
b(w) = (High_Decrease - 0.5) (log(w)-log(W)) / (log(W_1)-log(W)) +
0.5,
for W = Low_window and W_1 = High_window. The increase parameter
a(w) can then be computed as follows:
a(w) = w^2 * p(w) * 2 * b(w)/(2-b(w)),
for p(w) the packet drop rate for congestion window w. From
inverting Equation (1), we get p(w) as follows:
p(w) = 0.078/w^1.2.
We assume that experimental implementations of HighSpeed TCP for
further investigation will use a pre-computed look-up table for
finding a(w) and b(w). For example, the implementation from Tom
Dunigan adjusts the a(w) and b(w) parameters every 0.1 seconds. In
the appendix we give such a table for our default values of
Low_Window = 38, High_Window = 83,000, High_P = 10^-7, and
High_Decrease = 0.1. These are also the default values in the NS
simulator; example simulations in NS can be run with the command
"./test-all-tcpHighspeed" in the directory tcl/test.
8. An alternate, linear response functions
In this section we explore an alternate, linear response function for
HighSpeed TCP that has been proposed by a number of other people, in
particular by Glenn Vinnicombe and Tom Kelly. Similarly, it has been
suggested by others that a less "ad-hoc" guideline for a response
function for HighSpeed TCP would be to specify a constant value for
the number of round-trip times between congestion events.
Assume that we keep the value of Low_Window as 38 MSS-sized segments,
indicating when the HighSpeed response function diverges from the
current TCP response function, but that we modify the High_Window and
High_P parameters that specify the upper range of the HighSpeed
response function. In particular, consider the response function
given by High_Window = 380,000 and High_P = 10^-7, with Low_Window =
38 and Low_P = 10^-3 as before.
Using the equations in Section 5, this would give the following
Linear response function, for w > Low_Window:
W = 0.038/p.
This Linear HighSpeed response function is illustrated in Table 7
below. For HighSpeed TCP, the number of round-trip times between
losses, 1/(pW), equals 1/0.38, or equivalently, 26, for W > 38
segments.
Packet Drop Rate P Congestion Window W RTTs Between Losses
------------------ ------------------- -------------------
10^-2 12 8
10^-3 38 26
10^-4 380 26
10^-5 3800 26
10^-6 38000 26
10^-7 380000 26
10^-8 3800000 26
10^-9 38000000 26
10^-10 380000000 26
Table 7: An Alternate, Linear TCP Response Function for HighSpeed
TCP. The average congestion window W in MSS-sized segments is given
as a function of the packet drop rate P.
Given a constant decrease b(w) of 1/2, this would give an increase
a(w) of w/Low_Window, or equivalently, a constant increase of
1/Low_Window packets per acknowledgement, for w > Low_Window.
Another possibility is Scalable TCP [K03], which uses a fixed
decrease b(w) of 1/8 and a fixed increase per acknowledgement of
0.01. This gives an increase a(w) per window of 0.005 w, for a TCP
with delayed acknowledgements, for pure MIMD.
The relative fairness between the alternate Linear response function
and the standard TCP response function is illustrated below in Table
8.
Packet Drop Rate P Fairness Aggregate Window Bandwidth
------------------ -------- ---------------- ---------
10^-2 1.0 24 2.8 Mbps
10^-3 1.0 76 9.1 Mbps
10^-4 3.2 500 60.0 Mbps
10^-5 15.1 4179 501.4 Mbps
10^-6 31.6 39200 4.7 Gbps
10^-7 100.1 383795 46.0 Gbps
Table 8: Relative Fairness between the Linear HighSpeed and Standard
Response Functions.
One attraction of the linear response function is that it is scale-
invariant, with a fixed increase in the congestion window per
acknowledgement, and a fixed number of round-trip times between loss
events. My own assumption would be that having a fixed length for
the congestion epoch in round-trip times, regardless of the packet
drop rate, would be a poor fit for an imprecise and imperfect world
with routers with a range of queue management mechanisms, such as the
Drop-Tail queue management that is common today. For example, a
response function with a fixed length for the congestion epoch in
round-trip times might give less clearly-differentiated feedback in
an environment with steady-state background losses at fixed intervals
for all flows (as might occur with a wireless link with occasional
short error bursts, giving losses for all flows every N seconds
regardless of their sending rate).
While it is not a goal to have perfect fairness in an environment
with synchronized losses, it would be good to have moderately
acceptable performance in this regime. This goal might argue against
a response function with a constant number of round-trip times
between congestion events. However, this is a question that could
clearly use additional research and investigation. In addition,
flows with different round-trip times would have different time
durations for congestion epochs even in the model with a linear
response function.
The third column of Table 8, the Aggregate Window, gives the
aggregate congestion window of two competing TCP connections, one
with Linear HighSpeed TCP and one with Standard TCP, given the packet
drop rate specified in the first column. From Table 8, a Linear
HighSpeed TCP connection would receive fifteen times the bandwidth of
a Standard TCP in an environment with a packet drop rate of 10^-5.
This would occur when the two flows sharing a single pipe achieved an
aggregate window of 4179 packets. Given a round-trip time of 100 ms
and a packet size of 1500 bytes, this would occur with an available
bandwidth for the two competing flows of 501 Mbps. Thus, because the
Linear HighSpeed TCP is more aggressive than the HighSpeed TCP
proposed above, it also is less fair when competing with Standard TCP
in a high-bandwidth environment.
9. Tradeoffs for Choosing Congestion Control Parameters
A range of metrics can be used for evaluating choices for congestion
control parameters for HighSpeed TCP. My assumption in this section
is that for a response function of the form w = c/p^d, for constant c
and exponent d, the only response functions that would be considered
are response functions with 1/2 <= d <= 1. The two ends of this
spectrum are represented by current TCP, with d = 1/2, and by the
linear response function described in Section 8 above, with d = 1.
HighSpeed TCP lies somewhere in the middle of the spectrum, with d =
0.835.
Response functions with exponents less than 1/2 can be eliminated
from consideration because they would be even worse than standard TCP
in accommodating connections with high congestion windows.
9.1. The Number of Round-Trip Times between Loss Events
Response functions with exponents greater than 1 can be eliminated
from consideration because for these response functions, the number
of round-trip times between loss events decreases as congestion
decreases. For a response function of w = c/p^d, with one loss event
or congestion event every 1/p packets, the number of round-trip times
between loss events is w^((1/d)-1)/c^(1/d). Thus, for standard TCP
the number of round-trip times between loss events is linear in w.
In contrast, one attraction of the linear response function, as
described in Section 8 above, is that it is scale-invariant, in terms
of a fixed increase in the congestion window per acknowledgement, and
a fixed number of round-trip times between loss events.
However, for a response function with d > 1, the number of round-
trip times between loss events would be proportional to w^((1/d)-1),
for a negative exponent ((1/d)-1), setting smaller as w increases.
This would seem undesirable.
9.2. The Number of Packet Drops per Loss Event, with Drop-Tail
A TCP connection increases its sending rate by a(w) packets per
round-trip time, and in a Drop-Tail environment, this is likely to
result in a(w) dropped packets during a single loss event. One
attraction of standard TCP is that it has a fixed increase per
round-trip time of one packet, minimizing the number of packets that
would be dropped in a Drop-Tail environment. For an environment with
some form of Active Queue Management, and in particular for an
environment that uses ECN, the number of packets dropped in a single
congestion event would not be a problem. However, even in these
environments, larger increases in the sending rate per round-trip
time result in larger stresses on the ability of the queues in the
router to absorb the fluctuations.
HighSpeed TCP plays a middle ground between the metrics of a moderate
number of round-trip times between loss events, and a moderate
increase in the sending rate per round-trip time. As shown in
Appendix B, for a congestion window of 83,000 packets, HighSpeed TCP
increases its sending rate by 70 packets per round-trip time,
resulting in at most 70 packet drops when the buffer overflows in a
Drop-Tail environment. This increased aggressiveness is the price
paid by HighSpeed TCP for its increased scalability. A large number
of packets dropped per congestion event could result in synchronized
drops from multiple flows, with a possible loss of throughput as a
result.
Scalable TCP has an increase a(w) of 0.005 w packets per round-trip
time. For a congestion window of 83,000 packets, this gives an
increase of 415 packets per round-trip time, resulting in roughly 415
packet drops per congestion event in a Drop-Tail environment.
Thus, HighSpeed TCP and its variants place increased demands on queue
management in routers, relative to Standard TCP. (This is rather
similar to the increased demands on queue management that would
result from using N parallel TCP connections instead of a single
Standard TCP connection.)
10. Related Issues
10.1. Slow-Start
A companion internet-draft on "Limited Slow-Start for TCP with Large
Congestion Windows" [F02b] proposes a modification to TCP’s slow-
start procedure that can significantly improve the performance of TCP
connections slow-starting up to large congestion windows. For TCP
connections that are able to use congestion windows of thousands (or
tens of thousands) of MSS-sized segments (for MSS the sender’s
MAXIMUM SEGMENT SIZE), the current slow-start procedure can result in
increasing the congestion window by thousands of segments in a single
round-trip time. Such an increase can easily result in thousands of
packets being dropped in one round-trip time. This is often
counter-productive for the TCP flow itself, and is also hard on the
rest of the traffic sharing the congested link.
[F02b] proposes Limited Slow-Start, limiting the number of segments
by which the congestion window is increased for one window of data
during slow-start, in order to improve performance for TCP
connections with large congestion windows. We have separated out
Limited Slow-Start to a separate draft because it can be used both
with Standard or with HighSpeed TCP.
Limited Slow-Start is illustrated in the NS simulator, for snapshots
after May 1, 2002, in the tests "./test-all-tcpHighspeed tcp1A" and
"./test-all-tcpHighspeed tcpHighspeed1" in the subdirectory
"tcl/lib".
In order for best-effort flows to safely start-up faster than slow-
start, e.g., in future high-bandwidth networks, we believe that it
would be necessary for the flow to have explicit feedback from the
routers along the path. There are a number of proposals for this,
ranging from a minimal proposal for an IP option that allows TCP SYN
packets to collect information from routers along the path about the
allowed initial sending rate [J02], to proposals with more power that
require more fine-tuned and continuous feedback from routers. These
proposals are all somewhat longer-term proposals than the HighSpeed
TCP proposal in this document, requiring longer lead times and more
coordination for deployment, and will be discussed in later
documents.
10.2. Limiting burstiness on short time scales
Because the congestion window achieved by a HighSpeed TCP connection
could be quite large, there is a possibility for the sender to send a
large burst of packets in response to a single acknowledgement. This
could happen, for example, when there is congestion or reordering on
the reverse path, and the sender receives an acknowledgement
acknowledging hundreds or thousands of new packets. Such a burst
would also result if the application was idle for a short period of
time less than a round-trip time, and then suddenly had lots of data
available to send. In this case, it would be useful for the