Packet spraying for load balancing across multiple packet processors

• US 7,382,782 B1
• Filed: 04/12/2002
• Issued: 06/03/2008
• Est. Priority Date: 04/12/2002
• Status: Expired due to Fees

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Skibo, Thomas M., Ferguson, Dennis C., Chen, Chi-Chung
• Primary Examiner(s): Vu; Huy D.
• Assistant Examiner(s): Nguyen; Toan D.
• Application Number:
  US10/120,610
• Time in Patent Office: 2,244 Days
• Field of Search: None
• US Class Current: 370/395.41
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 47/522 Dynamic queue service slot or variable bandwidth allocation

Abstract

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.

Claims

1. A load balancing device, comprising:

a plurality of queues designated to process packets from a stream of packets; and

spray logic configured to select one of the plurality of queues to receive a packet based on a random selection function, wherein the spray logic includes;

weight compute components configured to calculate a probability value associated with each of the queues;

a series of summers configured to receive the probability values and generate a series of cumulative probability values;

a random generator configured to generate a random number; and

a series of comparators configured to select one of the series of cumulative probability values based on the random number.

2. The device of claim 1, further comprising:

a memory buffer configured to store the packets; and

a multiplexing component configured to receive a selection signal from the spray logic and to forward the packets from the memory buffer to the selected one of the plurality of queues based on the selection signal.

3. The device of claim 1, further including:

packet processing components that determine destination information for the packets.

4. The device of claim 1, wherein the spray logic randomly selects from a subset of the plurality of queues meeting a predetermined threshold criteria.

5. The device of claim 1, wherein the random selection function is based on a weighted probability assigned to each of the queues.

6. The device of claim 5, wherein the weighted probability of selecting a particular one of the queues is proportional to a difference between a threshold level and a queue length.

7. The device of claim 1, wherein the spray logic selects the one of the plurality of queues to receive each of the received packets as a first queue corresponding to a positive comparison by the series of comparators.

8. The network device of claim 1, wherein the device is a router.

9. The network device of claim 1, wherein the spray logic randomly selects from a subset of the plurality of queues meeting a predetermined threshold criteria.

10. The device of claim 1, wherein a probability of selecting a particular one of the queues is proportional to a difference between a threshold level and a queue length associated with the particular queue.

11. A circuit for selecting from among a plurality of queues, the circuit comprising:

a series of weight compute components configured to calculate a probability value associated with each of the queues;

a series of summers configured to receive the probability values and generate a series of cumulative probability values;

a random generator configured to generate a random number;

a multiplication component configured to multiply the random number by a final value in the series of cumulative probability values to obtain a multiplied value; and

a series of comparators configured to determine whether the multiplied value is less than the values of the series of cumulative probability values, wherein

one of the queues is selected based on the comparison by the series of comparators.

12. The circuit of claim 11, wherein the circuit selects a first queue corresponding to a positive comparison by the series of comparators.

13. The circuit of claim 11, wherein the random generator includes:

a linear feedback shift register (LFSR).

14. The circuit of claim 11, wherein each of the series of weight compute components subtracts a value based on a length of one of the queues from a predetermined threshold value.

15. The circuit of claim 11, wherein the series of weight compute components includes a single weight compute component associated with each of the queues and the series of summers includes a summer associated with each of the weight compute components except for a first of the weight compute components.

16. An apparatus comprising:

means for calculating a series of probability values each based on a length of a plurality of queues that store packet data;

means for converting the series of probability values into a series of cumulative probability values;

means for generating a random number; and

means for selecting one of the plurality of queues as a function of the random number and the series of probability values, wherein the means for selecting includes;

means for multiplying the random number by one of the series of cumulative probability values to generate a multiplied value, and

means for comparing the multiplied values to the values in the series of cumulative probability values.

17. An apparatus comprising:

means for calculating a series of probability values each based on a length of a plurality of queues that store packet data, wherein the means for calculating the series of probability values calculates each probability value in the series of probability values as a predetermined threshold value minus the length of one of the queues minus a length of the packet;

means for generating a random number;

means for selecting one of the plurality of queues as a function of the random number and the series of probability values; and

means for transmitting a packet to the selected one of the plurality of queues.

18. A method of selecting from among a plurality of queues, the method comprising:

calculating a probability value associated with respective ones of the queues;

generating a series of cumulative probability values based on the respective probability values;

generating a random number;

multiplying the random number by a final value in the series of cumulative probability values to obtain a multiplied value;

determining whether the multiplied value is less than values of the series of cumulative probability values; and

selecting one of the queues based on the determination.

19. The method of claim 18, wherein the calculating the probability value comprises subtracting a value based on a length of the respective ones of the queues from a predetermined threshold value.