ftp.ee.lbl.gov/2014.05.ftp.ee.lbl.gov.tar/ftp.ee.lbl.gov/email/sf.97nov19.txt

Text File | 1997-11-19 | 7KB | 144 lines

To: [e-mail]
cc: [e-mail], [e-mail]
Subject: ECN - one bit or two?
Date: Wed, 19 Nov 1997 17:45:56 PST
From: Sally Floyd <floyd>

Jim -

>The only issue is
>that you say you can do it with one bit but its easier to explain with
>two bits.  I don't mind using up two bits if it will make the
>implementation and execution clearer and better, but not just for
>clarity of explaining the behavior.

Fair enough.

(My original assumption had been that this one-bit or two-bit
discussion would happen on end2end-interest, but it seems that the
people who most want to have this discussion are on ipng, so I will try
to have this discussion there.  Clearly any detailed discussion about
allocating bits for ECN in IPv6 should happen on this list, and any
detailed discussion about allocating bits for ECN in IPv4 would happen
on the int-serv list, and detailed discussions about adding ECN to TCP
will happen on either tcplw or tcp-impl.  I am hoping that more
general research discussions related to ECN will happen on
end2end-interest.)

THE TWO-BIT APPROACH:

The recent internet draft submitted by KK and myself discusses a
two-bit approach to ECN:  an ECN-Capable bit set by the sender,
indicating to the router that the session is ECN-capable: and an ECN
bit set by the router to indicate congestion to the receiver.

THE ONE-BIT APPROACH:

Section 9.2 of the 1994 ECN paper discusses a one-bit approach as well,
where the ECN-Capable bit and the ECN bit are overloaded in a single
bit.  This single bit would have two values:  one value to indicate
"ECN-Capable", and the other value to indicate "either not ECN-Capable,
or Congestion Notification".  My own opinion is that that the two-bit
approach is preferable to the one-bit approach, for reasons discussed
below, and that the one-bit approach is preferable to no ECN at all.

WHY THE ECN-CAPABLE INDICATION IS NEEDED:

The need for both bits is motivated by the fact that ECN will be
deployed incrementally in an Internet where some transport protocols
understand ECN and some do not.  With the ECN-capable bit, the router
can drop packets from flows that are not ECN-capable, but can
**instead** set the ECN bit in flows that **are** ECN-capable.  Because
ECN means that an end node can have the ECN bit set in packets instead
of having the packet dropped, an end node might have some incentive to
deploy ECN.  A flow that advertised itself as ECN-Capable but does not
respond to ECN bits is functionally equivalent to a flow that turns off
congestion control;  this is discussed in Section 8 of the ECN internet
draft.

If there is no ECN-Capable indication, and the router simply
sets the ECN bit whether or not the transport protocol is
ECN-Capable, then there is no incentive for end-nodes to deploy
ECN, and no viable path of incremental deployment from a non-ECN
world to an ECN-capable world.  Consider the first stages of such
an incremental deployment, where a subset of the TCP flows have
end-node pairs that understand ECN.  Then when there is mild congestion,
the routers will only set ECN bits, rather than dropping packets.
However, only those flows that are ECN-capable will respond to those
ECN bits.  The result is that the ECN-capable flows will back off,
and the non-ECN-capable flows will be unaware of the ECN signals and
will continue to open their congestion windows.

In this case, there are two possible outcomes:
(1) the ECN-capable flows back off, the non-ECN-capable flows
get all of the bandwidth, and congestion remains mild, or
(2) the ECN-capable flows back off, the non-ECN-capable flows
don't, and congestion increases until the router transitions from
setting the ECN bit to dropping packets.  While this evens out
the fairness, this means that the ECN-capable flows get no
benefit from being ECN-capable, because the router has no choice
but to resort to packet-dropping instead.

In this world when a subset of the flows are ECN-capable,
but where ECN-capable flows have no mechanism for indicating that
fact to the routers, there would be less effective and less
fair congestion control in the Internet, and a strong incentive
for end nodes not to deploy ECN.

ASSUMING THAT THE ECN-CAPABLE INDICATION IS NEEDED, THE RELATIVE
ADVANTAGES OF ONE AND TWO BITS:

Functionally, the one-bit approach and the two-bit approach are
similar.  The one-bit approach has the functional limitation that if
one router sets the ECN bit in a packet that is "ECN-Capable", so that
the ECN bit now represents "either not ECN-Capable, or Congestion
Notification", then a second router has to assume that that packet is
not ECN-Capable, and has to drop that packet if it also wants to
indicate congestion to the end nodes.  This seems to me like a rather
minor limitation.

A critical issue in the implementation of ECN is that by default, the
IP header should indicate that the packet is **not** ECN-capable.  (If
the IP header indicates that a packet is ECN-capable while the
underlying transport protocol ignores the ECN bit in received packets,
this is roughly equivalent to the transport protocol "turning off"
congestion control.  Not acceptable behavior.)  So in the two-bit
approach, the requirement is that by default, the ECN-Capable bit be in
the "off" position, or set to "0".  This seems relatively clear and
straightforward, and not likely to get mixed up, and the router should
never change the value of the ECN-Capable bit in any case.  In the
one-bit approach, the requirement is that by default, the ECN bit be in
the "either not ECN-Capable, or Congestion Notification" position.
Less clear, robust, and straightforward.  I assumed that it was not a
show-stopper...

A second issue lies in the danger that the receiver will misinterpret
the received ECN signal.  In the two-bit approach, an ECN-capable
receiver has to respond if it receives a packet with both the
ECN-Capable and the ECN bits set.  This is clear.  In the one-bit
approach, ECN should only be used when the receiver knows in advance
that the sender is sending all of its packets with the ECN bit set to
"ECN-Capable".  In this case, if the receiver receives a packet with
the ECN bit set to "either not ECN-Capable, or Congestion
Notification",  then the receiver knows to interpret that as
"Congestion Notification", and to respond appropriately.  While this is
not a problem if all ECN-capable transport protocols are implemented
carefully and correctly, it is clearly less robust than the two-bit
approach.  In addition, the one-bit approach does not allow the sender
to selectively set the ECN-Capable bit on some packets but not others,
because the receiver has no way to distinguish between a packet that
was sent as "not ECN-Capable", and a packet whose ECN bit was set by
the router to "Congestion Notification".

CONCLUSION:

My conclusion would be that the two-bit approach is more robust
than the one-bit approach.  As far as I know, there is consensus that
the two-bit approach is viable;  I don't know that there is rough
consensus that the one-bit approach is viable.

- Sally

I am putting a copy of this note on the newly-created ECN web page at:
http://www-nrg.ee.lbl.gov/floyd/ecn.html