RED: Discussions of Byte and Packet Modes Sally Floyd, from a March 1997 email message. In RED, the average queue size can be measured either in packets or in bytes. This is discussed briefly in Section XII of the paper on ``Random Early Detection gateways for Congestion Avoidance''. For the RED implementation in the ns-2 simulator, setting the parameter ``ns_link(queue-in-bytes)'' to ``true'' results in a queue that is measured in bytes rather than in packets. In addition, there is a choice between operating the algorithm for choosing arriving packets to drop in ``byte mode'' or in ``packet mode''. This is discussed in Section 3 of the paper on ``Router Mechanisms to Support End-to-End Congestion Control''. For the RED implementation in the ns-2 simulator, setting the parameter ``ns_red(bytes)'' to ``true'' results in a RED packet-dropping probability that is a function of the packet size in bytes. The choice between per-packet vs. per-byte drop depends on the dominant end-to-end congestion control mechanisms. (This is discussed some in a draft paper by Kevin Fall and myself on "Router Mechanisms to Support End-to-End Congestion Control", ftp://ftp.ee.lbl.gov/papers/collapse.ps.) For protocols such as TCP, where a single packet drop is taken as an indication of congestion, the question (in terms of congestion control) is not what fraction of the bytes of that flow were dropped, or even what fraction of the packets were dropped in the most recent window of data. The question is simply whether or not one or more packets were dropped from the most recent window of data. When RED is deployed in a world dominated by such end-to-end congestion control mechanisms where a single packet drop is an indication of congestion, flows will rarely have more than one packet dropped from a window of data. If the scarce resource is link bandwidth in bytes per second, then per-byte drops would be appropriate. In this case, two flows with the same arrival rate in bytes per second but different arrival rates in packets per second would have the same probability of having a congestion indication (in the form of a packet drop) sent to the end nodes. On the other hand, if the scarce resource is CPU processing in packets per second, then per-packet drops would be better. I generally think that per-byte dropping is more useful, because I generally assume that the scarce resource is the link bandwidth in bytes per second. At the same time, I don't think that the basic RED queue management mechanism necessarily has to bear the responsibility of being able to respond appropriately to any evasive actions that any malicious users might come up with (such as decreasing their packets-per-second rate but increasing their bytes-per-second rate). Our paper on "Router Mechanisms to Support End-to-End Congestion Control" assumes that the scarce resource is bandwidth in bytes per second, and therefore assumes that per-byte drops are used. Per-byte drops have the added advantage that over a longish period of many roundtrip times, a flow's fraction of the packet drops is then a good indication of that flow's fraction of the link bandwidth in bytes per second. This is used by the mechanisms in our "Router Mechanisms" paper to detect and later restrict the bandwidth of various flavors of high-bandwidth flows using a disproportionate share of the link bandwidth in times on congestion. I would assume that some such mechanisms (e.g., our router mechanisms added to RED, Curtis's *FQ scheduling, other proposals for detecting and preferentially dropping packets from high-bandwidth flows) will be needed to offer protection against flows that are not responding to congestion indications (and to provide concrete incentives for using end-to-end congestion control). --------------------------------------------------- Additional comments, January 1998: MEASURING THE QUEUE IN BYTES OR IN PACKETS: Even with Drop-Tail queue management, queues with a capacity in units of bytes would give different performance that queues with a capacity in units of packets. For a Drop-Tail queue in units of packets, each packet occupies one buffer in the queue, regardless of the size of the packet. In this case, a small packet and a large packet take up the same amount of space in the queue, and are equally likely to be dropped on arriving to a full queue. For a Drop-Tail queue with capacity in units of bytes, a packet of B bytes would require exactly B bytes of space in the queue. In this case, during periods of congestion the queue could have enough room for a small packet but not enough room for a large one. In this case, given an environment with a mix of packet sizes, the smaller packets would be less likely to be dropped than the larger ones. Because one of the purposes of RED queue management is to give indications of congestion to the end nodes **before** congestion becomes sufficiently heavy that the queue overflows, RED should measure the queue size in packets for a queue whose capacity is in units of packets, and in bytes for a queue whose capacity is in units of bytes. Consider the problems that could result if the queue capacity was in fact in units of packets, while RED was estimating the current queue size only in term of the total bytes of data currently in the queue. If all of the packets in the queue were small, then RED's estimate in bytes would not be sufficient to distinguish between a full queue (with many small packets) or an nearly empty queue (with a few large packets). For a router where the transmission delay for a packet is largely a function of the size of the packet in bytes, then measuring the queue in bytes has the advantage that the average queue size corresponds to the average queueing delay for a packet, in seconds. For a router where the transmission delay for a packet is fixed, regardless of the size of the packet in bytes, then measuring the queue in packets gives the most accurate indication of the average queueing delay for an arriving packet. AN ORTHOGONAL QUESTION: PER-PACKET OR PER-BYTE DROPPING: The choice between per-packet vs. per-byte dropping is orthogonal to the choice between units of packets or bytes for the estimated average queue size. In particular, it is possible to have a queue capacity and estimated average queue size in units of packets, while at the same time using per-byte dropping, where the size of an arriving packet in bytes is a factor in deciding whether to drop the arriving packet. In this case, in mild congestion when the queue has not yet overflowed, the probability that a flow was notified of congestion would be a function of the flow's arrival rate in **bytes** per second. However, in high congestion with occasional queue overflow, when queue buffer space also becomes one of the scarce resources, a flow's chance of having a packet dropped during overload would be more closely related to the flow's arrival rate in **packets** per second.