Packet spraying for load balancing across multiple packet processors

A network device includes multiple packet processing engines implemented in parallel with one another. A spraying component distributes incoming packets to the packet processing engines using a spraying technique that load balances the packet processing engines. In particular, the spraying component distributes the incoming packets based on queue lengths associated with the packet processing engines and based on a random component. In one implementation, the random component is a random selection from all the candidate processing engines. In another implementation, the random component is a weighted random selection in which the weights are inversely proportional to the queue lengths.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates generally to data transfer and, more particularly, to systems and methods for allocating bandwidth for the processing of packets within a network device, such as a router.

2. Description of Related Art

Conventional networks typically include routers that route packets from one or more sources to one or more destinations. A packet carries data or control information and can be transmitted through a network. A router is a switching device that receives packets at input ports and, based on destination or other information included in the packets, routes the packets through output ports to final or intermediary destinations. Conventional routers determine the proper output port for a particular packet by evaluating header information included in the packet.

Conventional routers include buffers to support a particular bandwidth. If the input network traffic exceeds the bandwidth of the router, the router may drop packets. Expanding the bandwidth depends on a number factors, including the input line rate, the speed of the output determination process, and the blocking characteristics of the switching mechanisms of the router. Router bandwidth also relates to the processing power of the router. The processing power typically depends on the size of the memory (i.e., bigger and faster systems require larger memory capacities) and the ability of the router to determine where to route packets.

A key problem in designing routers is making them scale to higher aggregate bandwidths. To process higher bandwidths in a single conventional router, the size and configuration of the router typically has to be modified or redesigned. The process of modifying a router to increase bandwidth usually entails tedious design processes with the risk that the new design will not perform as intended or integrate well with other routers in the network, the outlay of resources (both monetary and human), as well as potential time delays.

One technique for increasing router bandwidth is to build a router with multiple packet processing components that operate in parallel. Incoming packet streams are divided among the packet processing components, processed, and then reassembled into the packet stream.

When dividing the packet stream among the number of packet processing components, one issue that arises is how to divide the packet stream so that the work load is evenly distributed among the packet processing components. One conventional solution to this problem is to use a packet sprayer to equitably distribute the packets to the processing components.

The sprayer maintains a counter for each packet processing component. The counters keep track of the packet stream being forwarded to each packet processing component by counting the number of bytes in the stream. An incoming packet is sprayed to the packet processing component corresponding to the counter with the lowest stream count value. In this manner, the sprayer balances the number of bytes transmitted to the packet processing components.

One problem with such a conventional sprayer is that, although it balances byte count very well, it does not necessarily do a good job of balancing packet count. For example, if there are four packet processing components, and the incoming traffic pattern includes three 4500-byte packets followed by 100 45-byte packets, the above-described sprayer may spray one of the 4500-byte packets to each of the first three packet processing components and the 100 45-byte packets to the last packet processing component. Because each individual packet requires a certain amount of processing regardless of its size, the packet processing component that receives the 100 smaller packets will have significantly degraded performance relative to the other three packet processing components. Thus, in this situation, the sprayer will not effectively load balance the packet processing components.

Therefore, there exists a need for systems and methods that increase the bandwidth for processing of packets in a router by more effectively load balancing across multiple parallel packet processing components.

SUMMARY OF THE INVENTION

Systems and methods consistent with the principles of the invention, among other things, provide for improved load balancing across packet processing components.

One aspect of the invention is directed to a load balancing device. The load balancing device includes multiple queues designated to process packets from a stream of packets received by the load balancing device. Further, the device includes spray logic configured to select one of the queues to receive each of the received packets based at least partially on a random selection function.

Another aspect of the invention is a network device that includes packet processors, a sprayer, and a desprayer. The packet processors process received packets by determining destination information for the received packets. The sprayer receives at least one packet stream and distributes the packets of the packet stream to selected ones of the packet processors. The sprayer selects the packet processor to receive a particular one of the packets based on a selection function. A desprayer receives the packets processed by the packet processors and assembles the packets into at least one outgoing packet stream.

Yet another aspect of the invention is a method of distributing incoming data items to one of a number of queues. The method includes determining whether a queue is a candidate to receive a data item based on a comparison of a predetermined threshold value to a sum of a length of the data item to a length of the queue. The method includes selecting, when at least one queue is determined to be a candidate queue, one of the candidate queues based on a random selection process. Further, the method includes selecting, when none of the queues are determined to be a candidate queue, one of the queues based on the length of the queues.

Still another aspect of the invention is a circuit for selecting from among a number of queues. The circuit comprises a series of weight compute components configured to calculate a probability value associated with each of the queues and a series of summers configured to receive the probability values and generate a series of cumulative probability values. Further, a random generator generates a random number and a multiplication component multiplies the random number by a final value in the series of cumulative probability values to obtain a multiplied value. A series of comparators determine whether the multiplied value is less than the values of the series of cumulative probability values.

DETAILED DESCRIPTION

As described herein, a sprayer distributes packets to multiple parallel packet processors. The sprayer distributes packets using a spraying method based on, for example, byte count. Additionally, a random component is introduced into the spraying algorithm. The random component may be a straightforward random selection or other type of random selection, such as a weighted random selection.

Exemplary Router Configuration

FIG. 1is a diagram of an exemplary router100consistent with aspects of the invention. Router100may include a sprayer110, multiple packet processors120(120A,120B,120C, and120D), and a desprayer130. Sprayer110may include a bandwidth divider that receives an incoming packet stream containing one or more packets and distributes the packets to packet processors120A-120D.

Packet processors120may include packet forwarding engines that process the packets to forward the packets through router100. For example, packet processors120may analyze the contents of a packet and, using routing and/or forwarding tables, identify the output port through which to transmit the packet. Packet processors120may attach an identifier to the packets to identify the output port. Desprayer130may include a bandwidth combiner that receives the processed packets from packet processors120A-120D and transmits the packets on an outgoing packet stream.

FIG. 1illustrates a very simple router configuration. In practice, the router may have more of these components and/or other components. For example,FIG. 2is an exemplary diagram of an alternate router200consistent with the principles of the invention. Router200may include a sprayer210, packet processors220(220A,220B,220C, . . . ,220N), and a desprayer230. In this case, sprayer210may receive multiple incoming packet streams, each containing one or more packets and distribute the packets to packet processors220A-220N.

Packet processors220may process the packets to forward the packets through router200. For example, packet processors220may analyze the contents of a packet to identify the output port through which to transmit the packet. Desprayer230may receive the processed packets from packet processors220A-220N and transmit the packets on outgoing packet streams, as instructed by packet processors220.

FIG. 3is another exemplary diagram of an alternate router300consistent with the principles of the invention. Router300may include multiple sprayers310(310A,310B,310C, . . . ,310M), packet processors320(320A,320B,320C,320N), and desprayers330(330A,330B,330C, . . . ,330M). In this implementation, each of sprayers310may receive multiple incoming packet streams, each containing one or more packets and distribute the packets to the packet processors320A-320N. Each of sprayers310A-310M may, for example, connect to the same port of each of the packet processors320. In other words, sprayer310A may connect to port A of packet processor320A,320B,320C, . . .320N; sprayer310B may connect to port B of packet processor320A,320B,320C, . . . ,320N; etc.

Packet processors320may process the packets to forward the packets through router300. For example, packet processors320may analyze the contents of a packet to identify the output port through which to transmit the packet. Each of desprayers330may receive the processed packets from the packet processors320A-320N and transmit the packets on outgoing packet streams, as instructed by packet processors320. Each of desprayers330A-330M may connect to the same port of each of packet processors320. In other words, desprayer330A may connect to port A of packet processor320A,320B,320C, . . . ,320N; desprayer330B may connect to port B of packet processor320A,320B,320C, . . . ,320N; etc.

Sprayer

FIG. 4is a diagram illustrating portions of sprayer110ofFIG. 1in additional detail. One of ordinary skill in the art will recognize that sprayers210and310may be implemented similarly to sprayer110. Accordingly, further details relating to the construction of these sprayers will not be described herein.

As shown, sprayer110includes a memory buffer410, control logic411, spray logic412, and a multiplexing component413. Buffers414-417represent input queues (Q0-Q3) of packet processors120A-120D, respectively.

Packets input to sprayer110are initially stored in memory buffer410. Control logic411receives information relating to each input packet. For example, control logic411may receive information identifying each arriving packet in memory410and an indication of the packet's length. Control logic411forwards this information to spray logic412, which is connected to multiplexing component413. Spray logic412controls multiplexing component413to output the packets stored in memory buffer410to a selected one of buffers414-417.

Exemplary Processing

Consistent with an aspect of the invention, sprayer110sprays its input packets using a spraying method based on, for example, byte count. Additionally, a random component may be introduced into the spraying method. The spraying method tends to avoid the uneven load balancing situations that may occur with conventional spraying algorithms that are based on stream flow.

FIG. 5is a flow chart illustrating one embodiment consistent with the principles of the invention through which sprayer110sprays its input packets to packet processors120A-120D.

To begin, for each input packet, spray logic412compares an expected actual queue length of buffers414-417to a threshold value (acts501and502). More specifically, spray logic412adds the actual queue length of each of buffers414-417(i.e., the amount of space used in buffers414-417) to the length of the packet under consideration (act501). This summed value is then compared to a threshold value (act502). The threshold value is a predetermined value, which may, for example, be selected by an operator. Queues with summed values that are less than the threshold value are candidates for the packet that is to be sprayed (act503). Otherwise, queues with summed values that are greater than the threshold value are removed as candidates for the packet that is to be sprayed (act504). Acts501-504are repeated for each queue (act505).

When the queues have been initially processed to create a set of candidate queues, spray logic412determines if at least one queue was determined to be a candidate queue (act506). If so, spray logic412selects one of the candidate queues using a random selection process (act507). If not, spray logic412selects the queue having the minimum queue length (act508). Spray logic412controls multiplexing component413to transmit the packet to the selected queue (act509).

In one embodiment consistent with aspects of the invention, the random selection process in act507is a simple random selection among the candidate queues in which each candidate queue has an equal probability of being selected. In a second embodiment, the random selection may be based on another criteria, such as a weighted probability.

FIGS. 6A-6Bare diagrams that conceptually illustrate the process described with regard toFIG. 5. Four queues, labeled as Q0, Q1, Q2, and Q3, are illustrated. In this example, each queue begins below the threshold level (Thresh). The length of the arriving packet is illustrated as the shaded portion corresponding to each queue inFIG. 6A. As can be seen, if the packet were added to each queue, Q3would be above the threshold. Accordingly, only queues Q0, Q1, and Q2are taken into consideration as a possible selection candidate. Assume that the random selection process chooses queue Q1as the queue to which the packet is to be sprayed. The random selection process may be implemented as a straight random selection in which each of queues Q0, Q1, and Q2have a one-third chance of being selected or as a weighted random selection based on the queue length (described in more detail below).

As shown inFIG. 6B, when queue Q1is selected to receive the packet, the length of Q1will increase by the length of the packet. Queues Q0, Q2, and Q3, which did not receive the packet, remain at their prior levels

FIGS. 7A-7Bare diagrams, similar toFIGS. 6A-6B, that conceptually illustrate the selection process shown inFIG. 5. In this example, however, Q0is chosen as the randomly selected queue.

Weighted Random Selection

As previously mentioned, in one embodiment, the random selection of candidate queues may be performed based on a weighted random selection process. The weighting for each candidate queue may be inversely proportional to the length of the queue. One way to achieve this type of weighting is to subtract the queue length from the threshold value.

For example, if there are three candidate queues, after eliminating queues that would go over the threshold with the arriving packet, and the candidate queues have expected queue byte counts of x, y, and z, and three corresponding weights, called w1, w2, and w3, respectively, the weights may be calculated as follows:w1=Threshold −x,w2=Threshold −y, andw3=Threshold −z.
The first queue has the probability w1/(w1+w2+w3) of being selected. Similarly, the second queue has the probability w2/(w1+w2+w3) of being selected and the third queue has the probability w3/(w1+w2+w3) of being selected.

By weighting the selection probabilities inversely proportional to the lengths of the queues, higher selection priority is given to shorter queues (i.e., less filled queues). This minimizes the chance of spraying into queues that are almost full, yet still balances packet distribution.

FIG. 8is a diagram illustrating an implementation of the portions of spray logic412for performing the weighted random selection.

Spray logic412includes registers801-804and weight compute components806-809. These elements compute the individual probability weights (e.g., w1, w2, and w3) for each queue. More particularly, registers801-804store the queue length of queues Q0-Q3. Weight compute components806-809receive the queue lengths from registers801-804. Based on the queue lengths and the threshold value, each weight compute component806-809calculates the weight corresponding to the queue by subtracting the queue length (plus the arriving packet length) from the predetermined threshold value. For queues with lengths greater than the threshold, weight compute components806-809may output a value of zero, indicating a zero probability of that queue being selected.

The weight output from weight compute component806is buffered in register810. The weight output from weight compute component807is summed with the weight from weight compute component806by summer815and then buffered in register811. Similarly, register812buffers the sum of the output of weight compute components806-808, as summed by summer816. Register813buffers the sum of all of the weight compute components806-809, as summed by summer817. The value stored in register813corresponds to the denominator in the probability calculation for the queues (e.g., w1+w2+w3in the previous example).

Multiplication component821multiplies the output of register813by a random number generated by pseudo-random number generator820. Pseudo-random number generator820may be, for example, a 31-bit LFSR (linear feedback shift register) in which the upper16output bits are used as the random number. The polynomial used for the LSFR may, for example, be as follows: x31+x27+x23+x19+x15+x11+x10+x9+x7+x6+x5+x3+x2+x1+1. In one embodiment, the output of multiplication component821may be scaled. For example, the output may be right shifted 32 bits.

Comparator825compares the output of register810(i.e., w1) to the output of multiplication component821. If the value from multiplication component821is less than w1, the comparison result is positive. Similarly, comparator826compares the output of register811to the output of multiplication component821and comparator827compares the output of register812to the output of multiplication component821. Spray logic412selects the queue corresponding to the first positive comparison by comparators825,826, and827. Thus, if comparator825outputs a logic one (positive comparison), queue Q0is selected. If, however, only comparators826and827output a logic one, queue Q1is selected. If none of comparators825-827output a logic one, queue Q3is selected.

FIG. 9is a diagram conceptually illustrating the relationship of the values calculated by spray logic412. As can be seen, the values from registers810-813form a cumulative probability distribution against which the value from multiplication component821is compared.

CONCLUSION

As described above, a sprayer equitably distributes packets to a number of packet processing components such that packet load at the packet processing components is balanced.

The foregoing description of preferred embodiments of the invention provides illustration and description, but is not intended to be exhaustive or to limit the invention to the precise form disclosed. Modifications and variations are possible in light of the above teachings or may be acquired from practice of the invention. Moreover, while a series of acts has been presented with respect toFIG. 5, the order of the acts may be different in other implementations consistent with principles of the invention.

Certain portions of the invention have been described as “logic” that performs one or more functions. This logic may include hardware, such as an application specific integrated circuit, software, or a combination of hardware and software.