Techniques for the hardware implementation of random early detection mechanisms

[0002] The present invention relates to managing a queue of packets to avoid congestion. More specifically, the invention relates to improved techniques for implementing in hardware Random Early Detection (RED) mechanisms.

[0003] Random Early Detection (RED) was originally conceived as a congestion avoidance mechanism to be embedded in Internet routers. The basic principle behind RED is to control the average length of a router output queue in order to avoid long term congestion. For each incoming packet, the average queue length is calculated. If the average queue length is below a predefined minimum threshold, the packet is accepted and stored in the output queue for transmission.

[0004] If the average queue size is above the minimum threshold but below a predefined maximum threshold, a probability is computed and the packet gets dropped (or marked) according to this probability. The probability is proportional to the average queue size so the larger the queue size, the higher is the probability for an incoming packet to get dropped. Finally, if the average queue size is above the maximum threshold, all incoming packets are dropped until the average queue size falls again below the maximum threshold. More details on RED may be found in “Random Early Detection Gateways for Congestion Avoidance,” Sally Floyd et al., IEEE/ACM Transactions on Networking, August 1993, which is hereby incorporated by reference.

[0005] Depending on the particular transport layer protocol used, when packet drops are detected, the sources can take appropriate countermeasures such as, for instance, backing off their transmission rates in order to reduce the traffic volume at the congested router. For example, if the transport protocol exploited is the Transmission Control Protocol (TCP), the loss of a packet is interpreted as a congestion indication and the TCP sources immediately reduce their transmission rates. Discarding packets is also a useful means to control the average queue size when non-reactive transport protocols such as User Datagram Protocol (UDP) are utilized. If packets are not dropped but instead are marked, it is the responsibility of the transport protocol to take the appropriate counter measures when it detects packets that have been marked by RED.

[0006] There are a number of advantages in using RED. The stochastic nature of RED guarantees that the number of dropped packets for a connection is proportional to the bandwidth currently being used by the connection. Also, global synchronization phenomena among different TCP sources do not occur because RED routers drop packets individually rather than in bursts as tail drop routers do. Moreover, by keeping the average queue size low, RED is able to reduce the average end-to-end delay while allowing occasional traffic bursts to find enough room to be accommodated within queues without significant losses.

[0007] However, there are a number of disadvantages with conventional implementations of RED. Firstly, the probability of dropping packets RED relies upon should ensure that the distribution of dropped packets is relatively uniform. However, in most RED in hardware implementations based on simplifications of the conventional scheme it is very likely for the distribution of packet drops to be highly non-uniform (e.g., multiple packets are dropped in a row). Additionally, packets can be dropped even after the current queue size has fallen below the minimum threshold because the average queue size is still above the minimum threshold. Finally, conventional implementations of RED are not very suitable for a hardware implementation because they are based on computations that involve a number of noninteger multiplications and divisions and also exploit an exponential function.

[0008] It would be beneficial to have improved techniques for queue management schemes such as RED. It would also be beneficial to have techniques for improving the distribution of dropped packets and preventing packets from being dropped when the current queue size is below the minimum threshold. Additionally, it would be beneficial to have techniques for easily implementing RED hardware, in order to exploit this mechanism in high speed devices such as a local area network (LAN) switch.

[0009] The present invention provides techniques for managing queues of packets, such as in RED. When the size (average or otherwise) of the queue is greater than a minimum threshold, packets are dropped according to a probability. Once a packet is dropped, the minimum threshold is increased so that it is unlikely that subsequent packets will be dropped, unless the size of the queue is greater than a maximum threshold. As packets are received without being dropped, the minimum threshold is decreased until it reaches its original value. Thus, the distribution of dropped packets is more uniform. Some specific embodiments of the invention are described below.

[0010] In one embodiment, the invention provides a method of managing a queue of packets. A packet is received and the average queue size is calculated. If the average queue size is above a minimum threshold, the packet is dropped according to a probability and if the packet is dropped, the minimum threshold is increased. In a preferred embodiment, if the average queue size is greater than a maximum threshold, the probability is 1 so the packet is dropped with complete certainty.

[0011] In another embodiment, the invention provides a method of managing a queue of packets including receiving a packet. The average queue size is calculated and the current queue size is determined. Then, a comparison queue size is calculated as the lesser of the average queue size and the current queue size. The comparison queue size is utilized to determine whether to drop the packet, such as in RED. In a preferred embodiment, the average queue size is calculated at specified time intervals.

[0012] In another embodiment the invention provides a method of managing a queue of packets including receiving a packet. A random number is generated and a bit-mask is utilized to mask the random number. If the sum of a queue size and the masked random number is greater than a maximum threshold, the packet is dropped and the mask is reset. When a specified number of packets is received without dropping a packet, the mask is shifted to increase the potential size of the masked random number. In a preferred embodiment, the queue size is a lesser of an average queue size and the current queue size.

[0013] Other features and advantages of the invention will become readily apparent upon review of the following description in association with the accompanying drawings.

[0014] FIG. 1 shows an example of a LAN including a switch.

[0015] FIGS. 2A-2F show graphical plots of drop probability versus average queue size in an embodiment of the invention.

[0016] FIG. 3 shows a graphical plot of drop probability versus average queue size similar to FIG. 2E except that the current queue size is greater than the minimum threshold.

[0017] FIG. 4 shows a flow chart of a process of managing a queue of packets.

[0018] FIG. 5 shows a flow chart of a process of periodically calculating the average queue size.

[0019] FIG. 6 shows a graphical plot of size of the queue versus time in order to illustrate that only utilizing the average queue size can result in dropped packets when the current queue size is less than the minimum threshold.

[0020] FIG. 7 shows a flow chart of another process of managing a queue of packets.

[0021] FIG. 8 shows a graphical plot of drop probability versus average queue size for another embodiment of the invention that has different thresholds and probabilities for different classes of packets.

[0022] In the description that follows, the present invention will be described in reference to embodiments that manage queues of packets such as in a LAN switch. More specifically, the embodiments will be described in reference to techniques that are particularly well suited for hardware implementations. However, the invention is not limited to devices within LANs such as switches, routers, bridges, and the like as the invention can be advantageously applied to devices in wide area networks (WANs) such as the Internet. Furthermore, the invention is not limited to hardware implementations or the specific techniques described herein as the invention can be implemented in different ways both in hardware and software. Therefore, the description of the embodiments that follows is for purposes of illustration and not limitation.

[0023] FIG. 1 shows a LAN including a switch. LAN 101 includes multiple computer systems 103 in communication with each other through a switch 105. Switch 105 directs the flow of electrical or optical signals representing packets among computer systems 103. Within switch 105, there are a number of queues (at least one per port) not shown in FIG. 1, that store incoming packets before they are sent to their intended destination. Additionally, in preferred embodiments there is an integrated circuit, such as an Application Specific Integrated Circuit (ASIC), that manages the queues within switch 105. In other embodiments, computer code that implements the invention can be stored in a computer readable medium, such as memory or a disk, that is executed by a processor within switch 105.

[0024] RED is a congestion avoidance mechanism conceived to operate on Internet routers. However, LANs are different from the Internet in a number of ways: low propagation delay, high bandwidth links, a larger percentage of UDP traffic, and the like. To deal with this high speed environment, it would be beneficial to have a hardware implementation of RED for LAN switches. In order to make this possible, it would be preferable if the computations involved were fairly simple so they can be easily implemented in the hardware of a LAN switch. Switch 105 is representative of any device in a LAN such as a switch, router, bridge, and the like.

[0025] FIGS. 2A-2F show graphical plots of drop probability versus average queue size in order to illustrate an embodiment of the invention. In the graphical plots, the average queue size increases along the x axis. Along the y axis, the drop probability can vary between 0 and 1. Now it may be useful to describe the graphical plots in more detail.

[0026] In FIG. 2A, it can be seen that when the average queue size is between 0 (or some small value) and a minimum threshold, the drop probability is 0 meaning that no packets will be dropped. When the average queue size is between the minimum threshold and a maximum threshold, packets will be dropped according to a drop probability that increases in proportion to the average queue size. As an example, if the average queue size is as shown by an arrow 201, a received packet would be dropped according to the probability shown, roughly a probability of 0.25 or 25%. The drop probability would increase if the average queue size increased. When the average queue size is above the maximum threshold, packets will be dropped according to probability of 1, which means that all packets that are received when the average queue size is above the maximum threshold will be dropped.

[0027] In an aspect of the invention, once a packet is dropped, the likelihood that a subsequent packet will be dropped is drastically reduced, virtually to 0. Conceptually, this can be viewed as increasing the minimum threshold so that subsequent packets will not be dropped unless the average queue size is greater than the maximum threshold. This can be seen more clearly in reference to FIG. 2B.

[0028] In FIG. 2B, assume that the received packet was dropped when the average queue size in FIG. 2A was as represented by arrow 201. Thus, the minimum threshold was increased to be equal to the maximum threshold as shown in FIG. 2B. In this manner, a subsequent packet will not be dropped unless the average queue size is above the maximum threshold, but this is virtually impossible because the average queue size cannot increase past the maximum threshold with just a single packet. This acts to prevent consecutive packets from being dropped. Although in preferred embodiments the minimum threshold is increased to equal the maximum threshold, in other embodiments, the minimum threshold may be increased to a lesser extent.

[0029] Continuing with this example, assume that the average queue size remains roughly equal to what is represented by arrow 201. After a specified number of packets are accepted (e.g., 5 packets), the minimum threshold is decreased as shown in FIG. 2C.

[0030] If the average queue size remains as represented by arrow 201 in FIG. 2C, packets will continue to be accepted. After a specified number of packets are accepted, once again the minimum threshold is decreased as shown in FIG. 2D. Assuming another specified number of packets is accepted, the minimum threshold is decreased as shown in FIG. 2E.

[0031] It should be clear that as more and more packets are accepted, the minimum threshold moves from the maximum threshold back to its original location. This change in the minimum threshold as packets are accepted is shown in FIG. 2F. The specified number of packets that are accepted before the minimum threshold is decreased can either be constant or varied according to some criteria such as, for example, the number of different flows across the queue or the total number of packets accepted since the last packet drop. In preferred embodiments, the specified number of packets is a constant that has been determined to be efficient for the specific environment. Additionally, in preferred embodiments the minimum threshold is decreased in an exponential manner such as by an amount that increases exponentially each time a specified number of packets are received without dropping a packet. More specifically, the distance between the minimum threshold and the maximum threshold is a power of 2 (as shown in FIG. 2F as 2^R). More details on the exponential nature of the decreases in the minimum threshold will be described in more detail in reference to FIG. 7.

[0032] In the preceding discussion, it was assumed that the average queue size remained fairly constant as represented by arrow 201. This assumption was for the purposes of simplifying the discussion of the graphical plots in FIGS. 2A-2F. As one would expect, the average queue size is not necessarily constant and may be increasing if packets are continually accepted, depending upon the frequency and size of the packets.

[0033] FIG. 3 shows a graphical plot that is similar to FIG. 2E except that in this case the average queue size has increased to what is represented by an arrow 203. Since the average queue size is now greater than the minimum threshold, the received packet would be dropped with probability P and the graphical plot would once again resemble that which is shown in FIG. 2B. In other words, once a packet is dropped, the minimum threshold is increased to make it more unlikely that a subsequent packet will be dropped. As packets are accepted, however, the minimum threshold is decreased to its original value so that it becomes more and more likely that a packet will be dropped. In this manner, the resulting distribution of packet drops is extremely uniform and does not rely solely upon the drop probability to distribute the packet drops.

[0034] Now that aspects of the invention have been described in reference to graphical plots it may be beneficial to describe a process of managing a queue of packets. FIG. 4 shows a flow chart of a process of managing a queue of packets according to one embodiment of the invention. At a step 301, a packet is received. An average queue size is calculated at a step 303. As with all the flow charts described herein, no order of the steps should necessarily be implied by the flow charts. Steps may be added, deleted, reordered, and combined without departing from the spirit and scope of the invention. As an example, in preferred embodiments, the average queue size is not calculated when a packet is received but instead at periodic intervals. This process will be described in more detail in reference to FIG. 5 but it illustrates that an order to the steps should not necessarily be implied by the order in which the steps are described in reference to the flow charts.

[0035] The average queue size can be calculated according to the following equation:

[0036] new_avg=(1−w_q)·prev_avg +w_qq

[0037] In the above equation, the prev_avg is the previous value of the average queue size, q is the current (or instantaneous) queue size and w_qis a weighting factor that is tuned in order to make the average queue size more or less sensitive to the current queue size.

[0038] At a step 305, the average queue size is tested to assess if it is above a minimum threshold. If the average queue size is determined to be above a minimum threshold at a step 307, the packet is dropped according to a probability at a step 309. Typically, the drop probability increases in proportion to the average queue size. However, the drop probability can be calculated in a variety of different ways to suit the specific environment.

[0039] At a step 310, it is determined if the packet has been dropped. If the packet has actually been dropped, the minimum threshold is increased at a step 311. In a preferred embodiment, the minimum threshold is increased to be equal to a maximum threshold but the minimum threshold can be increased less if desired. The flow then returns to step 301 where the next packet is received.

[0040] If at step 307 it is determined that the average queue size is not above a minimum threshold, the number of packets that have been received without being dropped is tested to see if it is enough to decrease the minimum threshold at a step 313. Each time a specified number of packets is received without being dropped, the minimum threshold is decreased so that if enough packets are received without being dropped, the minimum threshold returns to its original value. The specified number of packets can be a constant (e.g., 5) or it can vary depending on the total number connections across the queue or other criteria such as the total number of packets received without dropping, the average queue size, or the current queue size.

[0041] If it is determined that the number of packets received without dropping a packet is enough to decrease the minimum threshold at a step 315, the minimum threshold is decreased at a step 317. The minimum threshold can be decreased by a constant amount or in preferred embodiments, the minimum threshold is decreased in an exponential manner. In other embodiments, the minimum threshold can be decreased in other ways depending on the environment and desired operation.

[0042] At a step 319, the packet is accepted. Accepting the packet typically means that the packet will be stored in the queue until it is the packet's turn to be output to its destination. Accordingly, accepting the packet increases the current queue size and possibly the average queue size depending on how often and the manner in which it is calculated.

[0043] In one aspect of the invention, the average queue size is calculated periodically as shown in the flow chart of FIG. 5. Instead of calculating the average queue size when a packet is received, the average queue size is calculated at specific time intervals as follows.

[0044] At a step 401, a counter is initialized to the sampling interval. For example, the sampling interval can be the number of clock “ticks” between the periodic calculation of the average queue size.

[0045] At each clock cycle, the counter is decremented at a step 403. If it is determined that the counter is equal to zero at a step 405, the average queue size is calculated at a step 407. The average queue size can be calculated according to the equation shown above or any other calculation that one deems suitable. In a preferred embodiment, the average queue size is calculated according to the free pool that is remaining instead of the actual queue size.

[0046] At a step 409, the counter is reset to the sampling interval. The flow chart of FIG. 5 shows a process of periodically calculating the average queue size in a manner that can be advantageously applied to hardware implementations.

[0047] There are benefits for using the average queue size instead of the current (or instantaneous) queue size. However, there are times when utilizing the average queue size can result in dropped packets even when the current queue size is below the minimum threshold. In order to illustrate this, FIG. 6 shows a graphical plot of an example of the average and current queue sizes versus time.

[0048] As a current queue size 501 increases, an average queue size 503 also increases but at a slower rate as would be expected for an average. Similarly, when current queue size 501 decreases, average queue size 503 decreases also but at a slower rate.

[0049] During a time interval 505, current queue size 501 has fallen below the minimum threshold. However, as shown in FIG. 6, average queue size 503 still remains above the minimum threshold. This means that during time interval 505, packets can be dropped even though the current queue size is below the minimum threshold.

[0050] In order to avoid dropping packets when the current queue size is below the minimum threshold, a comparison average can be calculated as follows:

[0051] comp_avg=min{new_avg,q}

[0052] The comparison average comp_avg is the minimum of the average queue size (here denoted new_avg to be consistent with the previous equation) and q, which is the current queue size. The comparison average can be utilized in the process of managing the queue of packets so that whenever the current queue size falls below the minimum threshold, no packets will be dropped.

[0053] In one aspect of the invention, the process of managing a queue of packets is particularly well suited for a hardware implementation. The following is pseudo-code that can be utilized to generate a hardware implementation in an Application Specific Integrated Circuit (ASIC):

[0054] The above pseudo-code represents a possible implementation of the techniques that have been described previously. In order to make this implementation better suited for hardware, a mask that is stored in a shift register is utilized to mask bits off of a random number. As discussed above, a comparison average COMP_AVG is calculated and the sum of the COMP_AVG and the masked random number is compared to the maximum threshold MAX_TH.

[0055] If the COMP_AVG plus the masked random number is greater than the MAX_TH, the received packet is dropped. Additionally, the mask is reset to zero, which means that the mask will mask out all of the bits of the random number. In effect, this conceptually increases minimum threshold to the maximum threshold. However, as can be seen, the source code does not utilize an actual minimum threshold.

[0056] After a specified number of packets have been received without being dropped, this number being represented by N, the MASK is shifted to the left and a “1” is inserted from the right. This operation allows one less bit (the most significant bit) of the random number to be masked out. Accordingly, the range of the masked random number will increase in size exponentially by a power of 2.

[0057] With the embodiment shown above, a set of predefined dropping probability curves are exploited from time to time. The actual dropping curve utilized is selected according to the number of packets accepted in the queue since the last packet drop. When the queue is idle or after a period of moderate activity, the average queue size may be below the minimum threshold, which in this embodiment means that the mask will be all 1s and therefore the masked random number will represent its maximum potential range. In other words, the minimum threshold will be set to its lowest or original value.

[0058] When the queue gets congested, the average queue size will start to increase and after it crosses the minimum threshold (e.g., average queue size plus the masked random number is greater than the maximum threshold), sooner or later a packet will be dropped. After a packet is dropped, the mask is reset to 0, meaning that the probability to drop another packet in a row becomes drastically lower and is in fact virtually zero, unless the average queue size becomes greater than the maximum threshold.

[0059] The bit mask to be applied to the random number is extended by one bit by every N packets accepted in the queue. Each mask extension results in a doubling of the random number range, so the more packets are accepted in the queue and the less steep the probability curve becomes. The region with 0 drop probability shrinks and thus, the probability that the next packet will be dropped increases.

[0060] The mask extension process, if no drops occur, proceeds until the full random number range is used again. If a drop occurs earlier, the mask is reset to 0 and the whole process described above is repeated. In other words, the dropping probability curve moves towards the average queue size with a pace that depends on the packet arrival rate and the actual curve to be used depends on the number of accepted packets since the last drop.

[0061] The process described above is straightforward to implement in hardware because it does not involve any multiplication, division and/or other complex mathematical functions. The minimum and maximum thresholds are separated by a power of 2, namely 2^R, where R is the number of bits in the random number (e.g., R=17). Although it is not necessary for a power of 2 to be utilized, it makes the hardware implementation of the techniques for managing a queue of packets extremely simple and more efficient.

[0062] FIG. 7 shows a flow chart of a process of managing a queue of packets according to the pseudo-code shown above. At a step 501, a packet is received. A comparison average is calculated at a step 503. The comparison average can be calculated as the minimum of the average queue size and the current queue size. In other embodiments, the comparison average can be calculated in different ways and can be equivalent to the average queue size.

[0063] At a step 505, a test is performed to determine if the comparison average plus a random size is greater than the maximum threshold. The random size can be calculated as above by a bit wise AND of a mask and a random number.

[0064] If it is determined that the sum of the comparison average and the random size is greater than the maximum threshold at a step 507, the packet is dropped at a step 509. At a step 511, the mask is reset (i.e., set equal to 0).

[0065] At a step 513, it is determined if the number of packets received without being dropped is enough to increase the mask. If it is enough to increase the mask at a step 515, the mask is increased at a step 517. The mask can be increased by shifting the mask to the left and inserting a “1” from the right utilizing a shift register or any other way known in the art. At a step 519, the packet is accepted.

[0066] The above discussion has described embodiments where each of the packets is treated the same way. In other embodiments, packets can belong to different classes of service that need to be serviced differently. For example, a packet belonging to a “standard” class of service could be discarded with a higher probability with respect to a packet belonging to a “premium” class of service. This can be accomplished by assigning to each class of service different thresholds (or marking probabilities).

[0067] In order to further illustrate how to differentiate the treatment between or among a number of classes of service, FIG. 8 shows a graphical plot of the drop probability versus the average queue size for packets belonging to a standard and to a premium class of service. As shown, there is a minimum and maximum threshold for the standard class of service, denoted by the subscript S. Additionally, there is a minimum and maximum threshold for the premium class of service, denoted by the subscript P.

[0068] As can be seen, the minimum and maximum thresholds for the standard packets are lower than the premium packets. Accordingly, the standard packets will be dropped earlier and at a higher rate or probability than the premium packets when the average queue size increases.

[0069] For each incoming packet the average queue size is compared against the threshold associated with the packet's class of service and the appropriate drop probability curve is selected. Once the probability curve is selected, the process can proceed as described above for a single class of service for packets.

[0070] The following is pseudo-code that can be utilized to support multiple classes of service for packets:

[0071] As can be seen above, the support for multiple classes of service for packets can basically be summed up as making many of the variables into arrays of variables where each variable in the array is for a specific class of service. Although the above has described only two classes of service for simplicity, as the source code illustrates, the different classes of service can be extended to any number of classes.

[0072] As described above, the average queue size can be calculated according the free pool size rather than the queue size. Many ASIC designers prefer to deal with the free pool size rather than the queue size. Accordingly, the following pseudo-code is one implementation that utilizes the free pool size:

[0073] The above source code illustrates an embodiment that provides multiple classes of service for packets and additionally utilizes the average free pool size and the current free pool size in determining whether to drop a packet. The random number and mask operate substantially as described above in the other embodiments.

[0074] While the above is a complete description of preferred embodiments of the invention, alternatives, modifications and equivalents could be used. It should be evident that the invention is equally applicable by making appropriate modifications to the embodiments described above. For example, although the above has described processes of managing a queue of packets in a LAN, the invention can be advantageously applied to queues in other networks including WANs like the Internet. Therefore, the above description should not be taken as limiting the scope of the invention that is defined by the metes and bounds of the appended claims along with their full scope of equivalents.