Patent ID: 8873955

Claim:
A computer-implemented method for scheduling packets in a 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, the computer-implemented method comprising: a) 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; b) accepting a previous schedule which defines, for each input port i-output port j crosspoint i,j , whether the crosspoint i,j is in the previous schedule or not, wherein, 1) for each input port i, there is at most one crosspoint i,j scheduled in the previous schedule, and 2) for each output port j, there is at most one crosspoint i,j scheduled in the previous schedule; and c) at each input port i, for each crosspoint i,j merging the previous schedule with the Hamiltonian walk schedule to define an updated schedule such that: 1) for a crosspoint i,j that is not in the Hamiltonian walk schedule, maintaining a value of the crosspoint i,j in the updated schedule as that value of the corresponding crosspoint i,j in the previous schedule, and 2) for a crosspoint i,j that is in the Hamiltonian walk schedule, i) determining whether or not the crosspoint i,j belongs to the previous schedule, ii) responsive to a determination that the crosspoint i,j does belong to the previous schedule, determining whether or not to maintain the crosspoint i,j in the updated schedule as a function of an occupancy of a j th virtual output queue corresponding to the input port l and the output port j, and iii) responsive to a determination that the crosspointi,j does not belong to the previous schedule, A) determining whether or not any neighbor crosspoints k,l of crosspoint i,j belong to the previous schedule by observing a monitor of the switch to determine whether the output port j received a packet from an input port k, different from input port i, in a time slot immediately before a current time slot, and responsive to a determination that the output port j did receive a packet from an input port k, different from input port i, in the time slot immediately before the current time slot, determining that a crosspoint k,j belonged to the previous schedule, B) responsive to a determination that a neighbor crosspoint k,l of the crosspoint i,j belonged to the previous schedule, excluding the crosspoint i,j from the updated schedule, and C) responsive to a determination that a neighbor crosspoint k,l of the crosspoint i,j did not belong to the previous schedule, determining whether or not to add the crosspoint i,j to the updated schedule as a function of an occupancy of the j th virtual output queue corresponding to the input port i.