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. --------------------------------------------- Further email, October 2000: --------------------------------------------- To: smd@ebone.net (Sean Doran) cc: end2end-interest@ISI.EDU Bcc: From: Sally Floyd Subject: Re: RED gateways in byte mode vs. packet mode Date: Fri, 06 Oct 2000 10:54:31 -0700 Sender: floyd@elk.aciri.org Sean - >| Since I assume that packets are rarely greater than >| 1500 bytes > >Today... however, as jhawk has pointed out from time to time, the >number of bigger packets is non-zero, and even if they meet some >definition of "rare", the network should be able to handle them. Yep, I agree. And I believe that RED in byte mode handles even very large packets perfectly well, as I will try to clarify with the example below. (This is a better answer than the somewhat-quick answer that I gave the first time around, I think...) For links that allow 8K-byte packets, it is true that running RED in byte mode means that if there is a 6.25% packet drop probability for a 500-byte packet. then an 8K-byte packet will be dropped with 100% probability. If the same 8K bytes was broken into sixteen 500-byte packets, and each of the small packets was dropped with prob. 6.25%, then there would be some probability that none of the sixteen small packets would have been dropped (and therefore that the flow would not have had to reduce its sending rate). However, that is not how RED works (at least, as described in the 1993 RED paper and as implemented in NS). RED would not drop each small packet with prob. 6.25% in this case, but would slowly increase the applied dropping probability for each packet, to give uniform instead of geometric intervals between packet drops. (This is described in Section 7 of the 1993 RED paper.) If none of the first i-1 small packets were dropped, then the probability of having the i-th small packet dropped would be p/(1-i*p), with p=0.0625 in this case. And the probability of having the 16-th small packet dropped, in the unlikely chance that none of the first 15 small packets were dropped, would be exactly 1.0 in this case. Thus, for a dropping probability of 6.25% or greater for a 500-byte packet, RED in byte mode will drop either an 8K packet, or at least one of sixteen 500-byte packets, with probability 1, resulting in a congestion signal to the transport. And for a dropping probability less than 6.25% for a 500-byte packet, the 8K packet is less likely to receive a congestion signal (that is, to be dropped), than are the sixteen 500-byte packets. The truth is that for RED in byte mode, for higher drop probabilities and very large packets, the very large packets are somewhat *less* likely to receive at least one drop than if they were broken into small packets, meaning that there is a mild incentive for larger packets. However, it is true that with RED in byte mode, with small drop probabilities the incentive for larger packets is quite small. (The goal for RED in byte mode was for there to be no incentive in the packet-dropping mechanism, in terms of packet size, one way or another.) ... >I believe this perversely rewards people who deliberately deflate >their TCP segment sizes. I don't think so. It is true that RED in packet mode has a very strong bias against flows with smaller packets - for RED in packet mode, halving the packet size means significantly increasing your chances for a packet drop in a window of data, keeping the sending rate in bytes/sec fixed. RED in byte mode has a very mild bias against smaller packets, as described above. But ignoring this mild incentive for the purposes of discussion, assume that RED in byte mode has no incentives for either smaller or larger packets for a congestion-controlled flow. Advocating RED in byte mode does not imply advocating that the network have no biases in favor of larger packets. It just says that this bias does not have to come from the packet-dropping mechanism. If the network is limited by per-packet processing time rather than by available bandwidth on the wire, then this inherently gives an incentive to end-nodes to use larger packets. That is, if it is going to take the congested router M ms to process your packet, regardless of its size in bytes, then you are better off sending a larger packet rather than a smaller one. And if the server at the other end is limited by per-packet processing time rather than by bandwidth, then you will get better performance using larger packets than if you use smaller ones. Thus, I would have thought that the appropriate incentives for end-nodes to use larger packets are already there in the network, and there is no need to add additional artificial incentives to the queue-management mechanisms (e.g., by using packet mode instead of byte mode) that give a strong additional bias against flows with smaller packets. - Sally (If someone wanted to write something evaluating more precisely the relative biases of RED in packet and byte mode against flows with smaller packets, I think that would be great. I am not likely to get to it...)