To: ipng@sunroof.eng.sun.com cc: bound@zk3.dec.com, kkrama@research.att.com Subject: ECN - one bit or two? Date: Wed, 19 Nov 1997 17:45:56 PST From: Sally 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