Method to optimize the load balancing of parallel coprocessors

• US 8,005,978 B1
• Filed: 03/01/2002
• Issued: 08/23/2011
• Est. Priority Date: 03/01/2002
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Sinclair, Bruce E., Shah, Jay S., Duffie, John B. III
• Primary Examiner(s): Follansbee; John
• Assistant Examiner(s): Daftuar; Saket K.
• Application Number:
  US10/087,376
• Time in Patent Office: 3,462 Days
• Field of Search: 718/100, 718/105, 718/102, 705/8, 709/226, 709/229, 709100-105, 709/225, 709/234, 709/235, 370/229, 370/230, 370/235, 370/238, 370/252, 370/392, 370/401
• US Class Current: 709/235
• CPC Class Codes: G06F 9/505 considering the load

Abstract

A technique for optimally balancing the load between a series of coprocessors that takes into consideration the load associated with each coprocessor. A cost associated with a packet is determined. This cost along with the coprocessor'"'"'s current load is used to determine an anticipated load. The anticipated load is used to select a coprocessor that is to process the packet. In one embodiment, the coprocessor with the minimal anticipated load is selected. In another embodiment, an output port associated with the packet is checked to determine if it is congested. If so, a coprocessor other than the coprocessor with the minimum load is selected.

Claims

1. A method for selecting a coprocessor from a plurality of coprocessors to process a packet, the method comprising steps of:

determining a size of the packet;

determining a cost associated with the packet in response to the size of the packet, the cost representing a load associated with processing the packet;

determining, by a processor, an anticipated load for each coprocessor in the plurality of coprocessors using the cost; and

selecting, by the processor, the coprocessor from the plurality of coprocessors based on the anticipated load.

2. The method of claim 1 wherein the step of determining a cost further comprises the step of:

calculating the cost using a rate associated with processing the packet.

3. The method of claim 2 wherein the rate is stored in a lookup table.

4. The method of claim 2 wherein the step of calculating the cost further comprising the step of:

dividing the packet'"'"'s size by the rate.

5. The method of claim 2 wherein the step of calculating the cost further comprises the step of:

multiplying the packet'"'"'s size by a multiplicative inverse of the rate.

6. The method of claim 1 wherein the step of determining a cost further comprises the step of:

applying the packet'"'"'s size to a lookup table containing one or more cost values to determine the cost.

7. The method of claim 1 wherein the step of determining an anticipated load further comprises the step of:

adding the cost to a cumulative load associated with each coprocessor in the plurality of coprocessors.

8. The method of claim 1 wherein the step of selecting the coprocessor further comprises the step of:

selecting the coprocessor from a group of one or more coprocessors whose anticipated load is a minimum load.

9. The method of claim 8 wherein the coprocessor is selected using a scheduling algorithm.

10. The method of claim 1 wherein the step of selecting the coprocessor further comprises the step of:

determining if a port associated with the packet is congested.

11. The method of claim 10 wherein the step of selecting the coprocessor further comprises the step of:

selecting the coprocessor from a group of one or more coprocessors whose anticipated load is not a minimum load.

12. The method of claim 10 wherein the step of selecting the coprocessor further comprises the step of:

selecting the coprocessor from a group of one or more coprocessors whose anticipated load is a minimum load.

13. The method of claim 1 further comprising the step of:

incrementing a cumulative load associated with the selected coprocessor.

14. The method of claim 13 wherein the step of incrementing a cumulative load further comprises the step of:

adding the cost to the cumulative load.

15. The method of claim 1 further comprising the step of:

decrementing a cumulative load associated with the selected coprocessor.

16. The method of claim 15 wherein the step of decrementing a cumulative load further comprises the step of:

subtracting the cost from the cumulative load.

17. An apparatus for selecting a coprocessor from a plurality of coprocessors to process a packet, the apparatus comprising:

a memory containing one or more software routines, including a software routine configured to determine a size of the packet, and to determine a cost associated with the packet in response to the size of the packet, the cost representing a load associated with processing the packet; and

a processor configured to execute the software routines to determine an anticipated load for each coprocessor in the plurality of coprocessors using the cost and to select the coprocessor from the plurality of coprocessors based on the anticipated load.

18. The apparatus of claim 17 further comprising:

a data structure;

wherein the cost is determined using information contained in the data structure.

19. The apparatus of claim 18 wherein the information contained in the data structure includes the cost.

20. The apparatus of claim 18 wherein the information contained in the data structure includes a rate the coprocessor can process the packet.

21. An intermediate device configured to select a coprocessor from a plurality of coprocessors to process a packet, the intermediate device comprising:

means for determining a size of the packet, and for determining a cost associated with the packet in response to the size of the packet, the cost representing a load associated with processing the packet;

means for determining an anticipated load for each coprocessor in the plurality of coprocessors using the cost; and

means for selecting the coprocessor based on the anticipated load.

22. A non-transitory computer readable media comprising computer executable instructions for execution in a processor for selecting a coprocessor from a plurality of coprocessors to process a packet, the instructions for:

determining a size of the packet, and determining a cost associated with the packet in response to the size of the packet, the cost representing a load associated with processing the packet;

determining an anticipated load for each coprocessor in the plurality of coprocessors using the cost; and

selecting the coprocessor from the plurality of coprocessors based on the anticipated load.

23. A method for selecting a processor for processing a packet, the method comprising steps of:

determining a size of the packet;

determining a cost associated with the packet of that size, the cost representing a load associated with processing the packet;

determining, by a module of an intermediate node, an anticipated load for the processor using the cost of the packet if processed by the processor; and

selecting, by the module of the intermediate node, the processor based on the anticipated load.

24. The method of claim 23 wherein the step of determining a cost comprises the step of:

calculating the cost using a rate associated with processing of the packet; and

wherein the rate is stored in a lookup table.

25. The method of claim 23 wherein the step of determining a cost further comprises the step of:

applying the size of the packet to a lookup table containing cost values associated with particular sizes.

26. A method for selecting a coprocessor from a plurality of coprocessors to perform a processing operation on a received packet, the method comprising steps of:

determining a cumulative load for each coprocessor, the cumulative load representing load due to packets currently awaiting processing at that coprocessor;

determining a size of the received packet;

determining a cost for processing the received packet at each coprocessor, the cost determined, at least in part, in response to the size of the received packet and a processing rate of that coprocessor;

combining the cumulative load and the cost at each coprocessor, to create an anticipated load for each coprocessor;

comparing, by a processor, the anticipated loads of all the coprocessors; and

selecting, by the processor, in response to the comparing, a particular coprocessor of the plurality of coprocessors to perform the processing operation on the received packet.

27. The method of claim 26, wherein the step of selecting further comprises the step of:

selecting a coprocessor with minimum anticipated load to perform the processing operation on the received packet.

28. The method of claim 26, further comprising the step of:

determining if congestion is present at an output port associated with the received packet, and if congestion is present, selecting a coprocessor with non-minimum anticipated load to perform the processing operation on the received packet.

29. The method of claim 26, wherein the step of determining a cumulative load for each coprocessor further comprises the step of:

determining, for each coprocessor, sizes of the packets currently awaiting processing at that coprocessor and using the sizes in conjunction with the processing rate of that coprocessor to determine the cumulative load.

30. The method of claim 26 wherein the processing operation is an encryption operation.

31. An apparatus to select a coprocessor from a plurality of coprocessors to perform a processing operation on a received packet, the apparatus comprising:

a plurality of queues configured to store packets currently awaiting processing, each queue associated with one of the coprocessors, each queue associated with a cumulative load that represents a load to process packets in that queue;

a data structure configured to store processing rates, each processing rate associated with one of the coprocessors; and

a processor configured to determine a size of the received packet, and in response to the size of the received packet, and the processing rate of each coprocessor, determine a cost to perform a processing operation on the received packet at each coprocessor, the processor further configured to combine the cost at each coprocessor with the cumulative load at that coprocessor to create an anticipated load at each coprocessor, and to select a particular coprocessor to perform the processing operation on the received packet in response to comparison of the anticipated load at each coprocessor.

32. The apparatus of claim 31, wherein the processor is further configured to select a coprocessor with minimum anticipated load to perform the processing operation on the received packet.

33. The apparatus of claim 31, wherein the processor is further configured to determine if congestion is present at an output port associated with the received packet, and if congestion is present, select a coprocessor with non-minimum anticipated load to perform the processing operation on the received packet.

34. The apparatus of claim 31, wherein the cumulative load associated with each coprocessor is determined in response to sizes of packets awaiting processing in the queue associated with that coprocessor and the processing rate of that coprocessor.

35. The apparatus of claim 31, wherein the processing operation is an encryption operation.