Method and apparatus using a random indication to map items to paths and to recirculate or delay the sending of a particular item when a destination over its mapped path is unreachable

One or more computer-readable media tangibly embodying computer-executable instructions for performing operations for mapping packets to paths during a current forwarding cycle in a packet switching device, said operations comprising:

• generating a random index, the random index identifying a current particular path of a plurality of paths in the packet switching device;
• starting at the current particular path identified from the random index, for each particular packet of a plurality of packets stored in a recirculation buffer:
• in response to determining that said particular packet can be sent over the current particular path based on a path occupancy of the current particular path, causing said particular packet to be sent over the current particular path and advancing the current particular path to a next path of the plurality of paths not already mapped for forwarding a packet during the current forwarding cycle, else (b) in response to determining that said particular packet cannot be sent over the current particular path based on the path occupancy of the current particular path:
• not advancing the current particular path and wherein the particular packet remains in the recirculation buffer for processing during the next forwarding cycle;
• and
• subsequent to the operation of said for each particular packet, while there remains at least one path of the plurality of paths not already mapped for forwarding a packet during the current forwarding cycle and at least one more input packet:
• identifying a next input packet of said input packets;
• and if the next input packet can be sent over the current particular path as determined based on a path occupancy of the particular path, then causing said next input packet to be sent over the current particular path and advancing the current particular path to a next path of the plurality of paths not already mapped for forwarding a packet during the current forwarding cycle if any such non-mapped paths remain, else moving said next input packet into the recirculation buffer.

An apparatus for mapping packets to paths during a current forwarding cycle in a packet switching device, the apparatus comprising:

• means for generating a random index, the random index identifying a current particular path of a plurality of paths in the packet switching device;
• means for, starting at the current particular path identified from the random index, processing each particular packet of a plurality of packets stored in a recirculation buffer, said processing including:
• in response to determining that said particular packet can be sent over the current particular path based on a path occupancy of the current particular path, causing said particular packet to be sent over the current particular path and advancing the current particular path to a next path of the plurality of paths not already mapped for forwarding a packet during the current forwarding cycle, else (b) in response to determining that said particular packet cannot be sent over the current particular path based on the path occupancy of the current particular path:
• not advancing the current particular path and wherein the particular packet remains in the recirculation buffer for processing during the next forwarding cycle;
• and
• means for assigning packets to remaining unused paths subsequent to said processing each particular packet, said operation of assigning including:
• while there remains a path of the plurality of paths not already mapped for forwarding a packet during the current forwarding cycle and at least one more input packet:
• (a) identifying a next input packet of said input packets;
• and (b) if the next input packet can be sent over the current particular path as determined based on a path occupancy of the particular path, then causing said next input packet to be sent over the current particular path and advancing the current particular path to a next path of the plurality of paths not already mapped for forwarding a packet during the current forwarding cycle if any such non-mapped paths remain, else moving said next input packet into the recirculation buffer.

An apparatus for mapping packets to paths during a current forwarding cycle in a packet switching device, the apparatus comprising:

• a plurality of paths;
• a recirculation buffer;
• and control logic;
• wherein the control logic is configured to:
• acquire a random index, the random index identifying a current particular path of the plurality of paths in the packet switching device;
• starting at the current particular path identified from the random index, for each particular packet of a plurality of packets stored in the recirculation buffer:
• in response to determining that said particular packet can be sent over the current particular path based on a path occupancy of the current particular path, causing said particular packet to be sent over the current particular path and advancing the current particular path to a next path of the plurality of paths not already mapped for forwarding a packet during the current forwarding cycle, else (b) in response to determining that said particular packet cannot be sent over the current particular path based on the path occupancy of the current particular path:
• not advancing the current particular path and wherein the particular packet remains in the recirculation buffer for processing during the next forwarding cycle;
• and
• subsequent to the operation of said for each particular packet, while there remains at least one path of the plurality of paths not already mapped for forwarding a packet during the current forwarding cycle and at least one more input packet:
• identifying a next input packet of said input packets;
• and if the next input packet can be sent over the current particular path as determined based on a path occupancy of the particular path, then causing said next input packet to be sent over the current particular path and advancing the current particular path to a next path of the plurality of paths not already mapped for forwarding a packet during the current forwarding cycle if any such non-mapped paths remain, else moving said next input packet into the recirculation buffer.