|
Previous
|
Content
|
Next
|
|
|
6.0.-
TCP and Explicit Congestion Notification |
|
|
|
| In octuber 1994, S.Floyd published a
paper to discuss the use of Explicit Congestion Notification (ECN)
mechanism in the TCP/IP protocol: Here is a summary of this paper: |
| In current TCP networks, TCP
relies on packet drops as the indication of congestion. TCP
implementation also respond to ICMP source quench messages, but they
are rarely used because they consume network bandwidth in times of
congestion. |
|
Most current routers in TCP/IP networks have no provision for the
detection of incipient congestion. When a queue overflows, packets are
dropped. Future routers are likely to have more developed mechanism for the
detection of incipient congestion, as the recently proposed
Random Early Detection (RED)
gateways. These routers are not limited to packet drops as the method of
informing sources of congestion. |
| For networks with mechanism for the detection
of incipient congestion, the use of ECN mechanism for the
notification of congestion to the end nodes prevents unnecessary packet
drops. For low-bandwidth delay-sensitive TCP traffic, unnecessary
packet drops and packet retransmissions can result in noticeable and
unnecessary delays for the user. For some connections, these delays can be
exacerbated by a coarse-granularity TCP timer that delay the source's
retransmission of the packet. |
| A second benefit of ECN is that the
sources can be informed of congestion quickly and unambiguosly, without
the source having to wait for either a retransmit timer or three duplicate
ACKs to infer a dropped packet. For those cases where a dropped
packet is not detected by the Fast Retransmit procedure, the use of
ECN mechanisms can improve a bulk-data connection's response to
congestion. If the source is delayed in detecting a dropped packet, perhaps
due to small congestion control window and a coarse-grained TCP timer,
the source can lie idle. This delay, when combined with the global
synchronization, can result in substantial link idle time. |
|
Current ECN mechanism |
| Currently, ICMP Source Quench messages
are the only ECN mechanism in TCP/IP networks, but in fact
Source Quench is rarely used in the current Internet. While RFC 1009
requires routers to generate Source Quenches when they ran out of
buffers, the current draft on "Requirements for IP Routers" specifies
that a router should not originate Source Quench messages, and if it
does, must be able to limit the rate at which they are generated. In the
draft, Source Quench messages are criticized as consuming network
bandwidth, and as being both ineffective and unfair. |
| The guidelines for TCP's response to
Source Quench predate TCP congestion control mechanisms as
Fast Retransmit and Fast Recovery. From the guidelines, TCP
should respond to a Source Quench by "triggering a slow-start, as
if a retransmission timeout had ocurred". If the Source Quench
signals a dropped packet, and is therefore followed by either a
retransmit timer timeout or by the Fast Retransmission procedure,
then the Timeout Recovery code follows the Source Quench code.
In this case the slow start threshold ends up being set to one or
two segments, resulting in a very slow reopening of the congestion
window. |
|
|
|
| The role of the router |
|
Routers will be RED gateways, where they monitor the average queue
size and during congestion use a probabilistic algorithm to choose which
arriving packet to mark. In simulations, when using RED gateways with
ECN, the gateways set the ECN field in the packet header; when
using RED gateways without ECN, the gateways drop the packet
instead. In both variants, the gateways drop a packet when the queue is
above the maximun threshold. |
| Current routers generally have a single queue
for each output port. In the future, routers could have separate queues for
separate "classes" of traffic. In this case, the ECN mechanism
could apply separately to each queue. |
| Guidelines for TCP's response to ECN |
- TCP's response to ECN should be similar, over longer
time scales, to its response to a dropped packet as an indication of
congestion.
- Over smaller time scales (one or two round trip times), TCP's
response to ECN can be less conservative than its response to a
dropped packet as an indication of congestiom.
- For TCP, the receipt of a single ECN should trigger a
response to congestion.
- TCP should react to an ECN at most once per roundtrip
time. The TCP source should ignore succeeding ECNs if the
source has reacted to a previous ECN or to a dropped packet in the
last roundtrip time (inferred by a timeout or the receiving of 3
dupacks); in those cases the TCP source should not repeat the
reduction of the congestion window.
- TCP should follow the existing algorithm for sending data
packets in response to incoming ACKs. The response to an ECN
does not trigger the sending of any new (or retransmitted) data packet.
- TCP should follow the normal procedure after the timeout of a
retransmit timer. That is, after a timeout the source should slow-start
and retransmit the dropped packet. However, the slow-start threshold
should not be decreased, if it has been decreased within the last
roundtrip time.
|
| Implementing ECN in the simulator |
|
The implementation of ECN was made to a version of TCP that
incorporates the Fast Recovery, Slow Start, Congestion
Avoidance and Fast Retransmit algorithms. For the simulation the
RED gateways were given an option to set the ECN bit in the
packet header, as an indication of congestion. When the TCP receiver
receives a data packet with the ECN bit set, it sets the ECN
bit in the next outgoing ACK packet. |
| Following the ECN guidelines, upon
receiving an ECN message at time t when no response to
congestion have been made in roughly the last roundtrip time, the
TCP source halve both the congestion window cwnd and the
slow-start threshold ssthresh. Because there is no loss of incoming
ACKs to clock outgoing packets and no need for a short pause to recover
from severe short-term congestion, the TCP source doesn't
slow-start. The TCP source doesn't respond to succeeding ECNs
until all packets outstanding at time t have been acked. |
| After receiving three duplicate ACKs at
time t when no response to congestion have been made in roughly the
last roundtrip time, the TCP source follows the Fast Retransmit
and Fast Recovery procedures as usual. The source won't respond to an
ECN or to another set of three duplicate ACKs until all
packets outstanding at time t have been acked. |
| Finally, after receiving three duplicate
ACKs soon after responding to an ECN (when some of the packets
outstanding at the time of the response to the ECN have not yet been
acked), the source doesn't reduce ssthresh or cwnd, since that
has recently been done. After this, the source follows Reno's Fast
Recovery procedure, using incoming duplicate ACKs to clock
outgoing packets. |
| Simulation result of ECN in LANs |
| Simulations show that for networks with ECN,
the throughput of the bulk-data connection is high, and the telnet
packet delay is low, regardless of the buffer size, the TCP
granularity, the TCP window size, or the RED gateway
variation. Thus, the simulations with ECN are robust, delivering
essentially optimal performance over a wide range of conditions. With ECN
the performance is less sensitive to the network parameters and both, delay
and throughput, are improved. However, the simulations also show that under
proper conditions, it is possible to get reasonable performance without
using ECN. |
| The Lan simulation scenario |
|
The simulation scenario consists of five bulk-data TCP connections
and ten telnet connections from five sources feeding into a single
congested link; see figure below: |
|
|
|
Simulations are run for buffer sizes of 60, 120, 180 and 240KB in the RED
gateway (router); min.th is set to 1/12th of the buffer size
and max.th = 3 * min.th. When max.th is reached all arriving
packets are dropped. |
| TCP nodes use Reno congestion control,
with slow-start, fast retransmit and fast recovery,
modified to respond to ECN. Clock granularity is set to 0.1 msec,
which for simulation scenario reduces the wait for the retransmit timer
while at the same time avoiding false timeouts. Another set of simulations
use a clock granularity of 100 msec, which is closer to the value of
500 msec used by many current TCP implementation. Maximum
TCP window ranges from 8KB to 64KB. |
| The telnet connections send 40-byte
packets at random intervals; the ten connections send several hundred of
these packets in one 15-second simulation. The bulk-data connections
send 1000-byte data packets. Simulations compare behaviors with
DropTail gateways, RED gateways without ECN and RED
gateways with ECN. |
| Simulations show (graphs can be viewed in
original paper) that using RED gateway with ECN the
effective throughput is high and the telnet packet delay is low.
Personally (LB) I observed that improved behavior of telnet packet
delay is amazing. |
| Simulation results of ECN in
WANS. |
|
|
|
As figure above shows, this time simulation network has two-way traffic
consisting of sixteen telnet connections in each direction, ocasional
FTP connections with a limited amount of data to transfer (100-300
packets), and a number of bulk-data connections with an unlimited
amount of data to transfer. The RED gateways have the same minimum
and maximum threshold for the average queue size as described in the
previous section. However, as is appropriate for gateways intended for
wide-area traffic, the time constant for the low-pass filter used
to calculate the average queue size has been increased (the weight used by
the EWMA filter to calculate the average queue size has been
decreased from 0.002 to 0.001). |
| The results of the WAN
simulations show that, while throughput is similar in all three set of
simulations (DropTail, RED without ECN and RED
with ECN), the packet delay for low-bandwidth interactive traffic
is much better for the simulation with ECN. |
|
Advantage and disadvantages of ECN |
Advantages
| |
- Reduction in packet drop and packet delay for
low-bandwidth delay-sensitive TCP traffic.
- A prompt notification to end nodes of network congestion.
|
|
Disadvantages
| |
- A non-complaint TCP connection could set the ECN
field to indicate that it was ECN-capable, and then ignore
ECN notifications. However, as soon as it continue responding to
packet drop (as it should be) as a signal of congestion notification,
there will be no problem with this circumstance.
- Potential loss of ECN messages in the network. In this case
the congestion notification message could fail to reach the end node.
However, RED gateways will continue setting ECN field in
randomly-chosen packets as long as congestion persists. Also a
RED gateway is particulary unlikely to drop a high fraction of
packets. The ocassional loss of an ECN message should not be a
serious problem.
|
|
| ECN with other versions of TCP |
|
|
|
One proposed modification to TCP, the addition of SACK, would
reduce TCP's reliance on the retransmit timer when multiple packets
are dropped in one roundtrip time. While this would improve somewhat
the robustness of the response of bulk-data TCP connections to packet
drop as an indication of congestion, this would not reduce the ability of
ECN mechanism to reduce packet delay for low-bandwidth
delay-sensitive TCP connections. |
|
|
For a network such as the Internet without admission control, a
TCP source cannot completely avoid the network from dropping packets.
Nevertheless, with improved detection of incipient congestion, the TCP
source could reduce congestion and consequently reduce the number of packets
dropped. However, the improved congestion detection by the end nodes does
not eliminate the need for improved congestion detection at the gateways. In
the absence of prior information about the propagation delay of a path, it
is not possible for end nodes to distinguish between propagation delay and
persistent queueing delay. As the delay-bandwidth product of network
connections increase, the buffer capacity at the gateways also increase, and
it will become increasingly important that these large buffers not have
persistent large queues. |
|
It seems unlikely to us that modification of TCP with newer
end-to-end congestion avoidance mechanisms would significantly reduce
the usefulness of ECN. For example, the use of a separate traffic
class for interactive traffic would reduce packet drop for this traffic
during periods of low demand from the interactive traffic. However, for both
attended data traffic and interactive traffic, some notification of
congestion from the gateway will continue to be required. Thus, the use of
ECN mechanisms would still improve the promptness and robustness of
congestion notification for data transfer connections, and reduce
unnecessary packet drops for some connections in the interactive traffic
class. |
|
Forward ECN vs Backward ECN |
|
One advantage of Forward ECN is that it places no additional load on
the network in times of congestion. On the other hand, the use of
intelligent gateway mechanisms such as those in RED gateways would
limit the overhead of Backward ECN. An advantage of Backward ECN
over Forward ECN is that the notification of congestion arrives at
the source as quickly as possible; this promptness in the notification would
be an advantage in congestion control schemes. |
|
No matter what ECN scheme you were using (Forward or
Backward) one ECN packet could be dropped by a gateway and the
TCP source might never receive the congestion notification. If the
network drops a data packet that has the ECN bit set, the TCP
source will still infer congestion when it detects the dropped data packet.
However, if the network drops an ACK packet that has the ECN
bit set, and later the TCP source receives an ACK packet
without the ECN bit set, then the source will never receive the
notification of congestion. Thus, neither Forward or Backward ECN
schemes ensure reliable delivery of congestion notification. |
|
Improving the TCP granularity? |
|
Tha advantages of ECN mechanisms in TCP/IP networks are most
pronounced with TCP implementations limited by a
coarse-granularity TCP clock. This coarse-grained clock limits
the granularity of TCP's measurement of current roundtrip times, used
to determine the value for the retransmit timer. Simulation results argue in
favor of improving the TCP clock granularity. Just another problem is
that it is not obvious what the optimal value should be. It seems clear to
us that a clock granularity of 100ms (or slightly smaller) would be
more appropriate for current networks than the clock granularity of 500ms
in many current TCP implementations. |
|
However, in the current algorithms for setting the TCP retransmit
timer, the clock coarse granularity is deliberately used as a
low-pass filter to filter out common traffic variations. Changing the
clock granularity to an arbitrarily fine-grained TCP clock would
remove this filtering, resulting in false retransmits in many scenarios. If
a fine-grained clock were used, this filtering would have to be
replaced by a substantially more sophisticated estimation mechanism. The
addition of ECN has the advantage of reducing the importance of the
clock granularity, thereby increasing the general robustness of the
network. |
|
|
|
|
|
Previous
|
Content
|
Next
|