Patent ID: 8145823

Claim:
A method for scheduling the transfer of cells in a switch, comprising: receiving a set of cells to be transferred from a set of inputs of the switch to a set of outputs of the switch; wherein the switch includes S subschedulers, wherein each subscheduler processes N scheduling waves to generate a conflict-free transfer schedule for a given time slot for a matrix of transfer elements in the switch, wherein each transfer element in the matrix of transfer elements includes one or more circuit elements that facilitate generating S transfer schedules in parallel; operating the subschedulers in parallel to generate S transfer schedules for transferring the cells from the set of inputs of the switch to the set of outputs of the switch during S time slots; wherein when generating the transfer schedules, each subscheduler processes each different scheduling wave only once, wherein each subscheduler processes a scheduling wave in time T, and wherein the N scheduling waves are processed in time NT to generate the conflict-free transfer schedule; and for each transfer schedule in the S transfer schedules, performing a set of input-to-output transfers for one time slot using the transfer schedule, wherein performing the set of input-to-output transfers comprises using the transfer schedules in a reverse order from the order the transfer schedules are generated.