Patent ID: 7613200

Claim:
A method for mapping packets to paths during a current forwarding cycle in a packet switching device, the method 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: (a) 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.