Hardware efficient system and method for load balancing using a random number

1. A resource selection circuit for selecting one of a plurality of resources, each of the resources being identified by a resource number and associated with a respective sub-range of numbers, the circuit comprising:

a first sub-range test circuit having an indexing number input for receiving an indexing number; and

a second sub-range test circuit having an indexing number input for receiving the indexing number,

the first sub-range test circuit being configured to:

determine whether the indexing number is within a first sub-range of numbers; and

output a first resource number when the indexing number is within the first sub-range of numbers, the first resource number identifying a resource associated with the first sub-range of numbers,

the second sub-range test circuit being configured to:

determine whether the indexing number is within a second sub-range of numbers; and

output a second resource number when the indexing number is within the second sub-range of numbers, the second resource number identifying a resource associated with the second sub-range of numbers, and

the first sub-range of numbers and the second sub-range of numbers being contiguous and non-overlapping,

wherein the first sub-range test circuit has:

an indexing number output connected to an indexing number input of the second sub-range test circuit; and

a selected resource output connected to a selected resource input of the second sub-range test circuit, and

the first sub-range test circuit is configured to send:

to the indexing number input of the second sub-range test circuit, the indexing number; and

to the selected resource input of the second sub-range test circuit:

the first resource number, when the indexing number is within the first sub-range of numbers; and

a reserved value indicating that a resource has not been selected, otherwise.

2. The resource selection circuit of claim 1 , wherein the first sub-range of numbers has the same size as the second sub-range of numbers.

3. The resource selection circuit of claim 1 , further comprising a random number generating circuit having an output connected to:

the indexing number input of the first sub-range test circuit; and

the indexing number input of the second sub-range test circuit.

4. The resource selection circuit of claim 3 , wherein the random number generating circuit is configured to receive a first number and a second number and generate a random number comprising the bit-wise exclusive OR of the first number and the second number.

5. The resource selection circuit of claim 1 , wherein:

the first sub-range test circuit and the second sub-range test circuit are constructed as synchronous logic having a common clock, and

the second sub-range test circuit is configured to determine, one clock cycle after the first sub-range test circuit has determined whether the indexing number is within the first sub-range of numbers, whether the indexing number is within the second sub-range of numbers.

6. The resource selection circuit of claim 1 , wherein

the first sub-range test circuit has an upper limit input, and

the first sub-range of numbers extends from zero to a number received at the upper limit input of the first sub-range test circuit.

7. The resource selection circuit of claim 6 , wherein:

the first sub-range test circuit further has a delta input and an upper limit output;

the second sub-range test circuit further has an upper limit input connected to the upper limit output of the first sub-range test circuit; and

the first sub-range test circuit is configured to form the sum of a number received at the upper limit input of the first sub-range test circuit and a number received at the delta input of the first sub-range test circuit, and transmit the sum through the upper limit output of the first sub-range test circuit.

8. The resource selection circuit of claim 7 , wherein the second sub-range test circuit is configured to determine whether the indexing number is within the second sub-range of numbers by:

determining that the indexing number is within the second sub-range of numbers if:

the selected resource input of the second sub-range test circuit has a value equal to the reserved value; and

the indexing number is less than or equal to a number received at the upper limit input of the second sub-range test circuit; and

determining that the indexing number is not within the second sub-range of numbers, otherwise.

9. The resource selection circuit of claim 1 , further comprising a pre-selection circuit having an indexing number input for receiving the indexing number, the pre-selection circuit being connected to the first sub-range test circuit and being configured to send, to a selected resource input of the first sub-range test circuit:

a number identifying a selected resource when the indexing number is not within a total range, the total range being the union of a plurality of sub-ranges of numbers, each of the sub-ranges of numbers being associated with a respective sub-range test circuit of a plurality of sub-range test circuits including the first sub-range test circuit and the second sub-range test circuit; and

the reserved value, otherwise.

10. The resource selection circuit of claim 9 , wherein the pre-selection circuit is configured to calculate the number identifying the selected resource by subtracting a largest number in the total range from the indexing number.

11. A packet switch having an ingress port and a plurality of egress ports, and comprising the resource selection circuit of claim 1 , the packet switch being configured to employ the resource selection circuit, upon receipt of a packet at the ingress port, to select an egress port from among a plurality of egress ports suitable for routing the packet to a destination identified in the packet.

12. The packet switch of claim 11 , wherein the resource selection circuit is configured to receive flow information and generate the indexing number based on the flow information.

13. A method for selecting from among a plurality of resources, the method comprising:

associating each of the resources with a respective sub-range of consecutive integers of a plurality of sub-ranges of consecutive integers, the sub-ranges of consecutive integers being non-overlapping and together including all of the integers of a total range of consecutive integers;

generating a first indexing number within the total range of consecutive integers;

selecting the resource associated with the sub-range of consecutive integers including the first indexing number; and

executing a task using the selected resource,

wherein the generating of the first indexing number consists of generating a first random number, and

wherein:

each of the resources is identified by one of a set of consecutive integers beginning with the integer 1; and

the method further comprises:

generating a second random number greater than the largest integer in the total range of consecutive integers, and

selecting the resource associated with the integer equal to the difference between second random number and the largest integer in the total range of consecutive integers.