Patent ID: 8737414

Claim:
A processor-implemented scheduling method for use in a buffered crossbar switch having a plurality of output ports, a plurality of input ports, each of the plurality of input ports having a virtual output queue corresponding to each of the plurality of output ports, and a switch fabric coupling each of the input ports with each of the output ports, defining crosspoints and including a buffer in the switch fabric at each input port-output port crosspoint, the processor-implemented scheduling method comprising: a) accepting an initial priority schedule which defines, for each input port i-output port j crosspoint i,j , whether the crosspoint i,j is in the initial priority schedule or not, wherein, 1) for each input port i, there is at most one crosspoint i,j scheduled in the initial priority schedule, and 2) for each output port j, there is at most one crosspoint i,j scheduled in the initial priority schedule; b) generating or receiving a Hamiltonian walk schedule which defines, for each input port i-output port j crosspoint i,j , whether the crosspoint i,j is in the Hamiltonian walk schedule or not; and c) merging the initial priority schedule with the Hamiltonian walk schedule to define an updated priority schedule such that: 1) for each crosspoint i,j that is not in the Hamiltonian walk schedule, maintaining a value of the crosspoint i,j in the updated priority schedule as that value of the corresponding crosspoint i,j in the initial priority schedule, and 2) for each crosspoint i,j that is in the Hamiltonian walk schedule, A) determining whether or not the crosspoint i,j belongs to the initial priority schedule, B) responsive to a determination that the crosspoint i,j does belong to the initial priority schedule, determining whether or not to maintain the crosspoint i,j in the updated priority schedule based on an occupancy of the j th virtual output queue corresponding to the input port i, and C) responsive to a determination that the crosspoint i,j does not belong to the initial priority schedule, i) determining whether or not any neighbor crosspoints k,l of crosspoint i,j belong to the initial priority schedule, ii) responsive to a determination that a neighbor crosspoint k,l of the crosspoint i,j belongs to the initial priority schedule, determining whether or not to add the crosspoint i,j to the updated priority schedule based on an occupancy of the j th virtual output queue corresponding to the input port i, and iii) responsive to a determination that a neighbor crosspoint k,l of the crosspoint i,j does not belong to the initial priority schedule, excluding the crosspoint i,j from the updated priority schedule.