Distributed scheduling for an optical switch

1. 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.

2. The method of claim 1 , wherein the switch is an optical fiber based switch.

3. The method of claim 1 , wherein the monitor is an energy detector that detects a wavelength of a signal received at each of the plurality of output ports.

4. The method of claim 3 , wherein each of the plurality of output ports is configured to receive a packet transmitted at a predetermined wavelength.

5. The method of claim 1 , wherein a crosspoint is a neighbor of crosspoint i,j if the crosspoint has the same input port i but a different output port j than the output port j, or the same output port j but a different input port ī than the input port i.

6. The method of claim 1 , wherein the act of determining whether or not to add the crosspoint i,j in the updated schedule as a function of an occupancy of the j th virtual output queue corresponding to the input port i,

determines a weight of the j th virtual output queue corresponding to the input port i as a function of the occupancy of the queue, the weight being denoted as weight i,j ,

determines a probability

p

i

,

j

=

ⅇ

weight

i

,

j

1

+

ⅇ

weight

i

,

j

,

and

adds the crosspoint i,j to the updated schedule with a probability p i,j , and otherwise does not add the crosspoint i,j to the updated schedule.

7. The method of claim 1 , wherein the act of 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,

determines a probability p i,j as a concave function of the occupancy of the j th virtual output queue corresponding to the input port i, and

adds the crosspoint i,j to the updated schedule with a probability p i,j , and otherwise does not add the crosspoint i,j to the updated schedule.

8. The method of claim 1 , wherein the schedule is generated at every M time slots, where M is a function of a round trip time for the packets in the switch.

9. The method of claim 8 , wherein the updated schedule is a schedule of the packets for a current time slot.

10. The method of claim 8 , wherein the previous schedule is a schedule of the packets at M time slots before a current time slot.

11. A scheduler 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 scheduler comprising:

at least one processor; and

at least one storage device storing program instructions which, when executed by the at least one processor, cause the processor to perform a method including:

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; and

b) accepting a previous schedule which defines, for each input port i-output j port 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 i and the output j, and

iii) responsive to a determination that the crosspoint i,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 the 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.

12. The scheduler of claim 11 , wherein the switch is an optical fiber based switch.

13. The scheduler of claim 11 , wherein the monitor is an energy detector that detects a wavelength of a signal received at each of the plurality of output ports.

14. The scheduler of claim 13 , wherein each of the plurality of output ports is configured to receive a packet transmitted at a predetermined wavelength.

15. The scheduler of claim 11 , wherein a crosspoint is a neighbor of crosspoint i,j if the crosspoint has the same input port i but a different output port j than the output port j, or the same output port j but a different input port ī than the input port i.

16. The scheduler of claim 11 , wherein the act of determining whether or not to add the crosspoint i,j in the updated schedule as a function of an occupancy of the j th virtual output queue corresponding to the input port i,

determines a weight of the j th virtual output queue corresponding to the input port i as a function of the occupancy of the queue, the weight being denoted as weight i,j

determines a probability

p

i

,

j

=

ⅇ

weight

i

,

j

1

+

ⅇ

weight

i

,

j

,

and

adds the crosspoint i,j to the updated schedule with a probability p i,j , and otherwise does not add the crosspoint i,j to the updated schedule.

17. The scheduler of claim 11 , wherein the act of 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,

determines a probability p i,j as a concave function of the occupancy of the j th virtual output queue corresponding to the input port i, and

adds the crosspoint i,j to the updated schedule with a probability p i,j , and otherwise does not add the crosspoint i,j to the updated schedule.

18. The scheduler of claim 11 , wherein the schedule is generated at every M time slots, where M is a function of a round trip time for the packets in the switch.

19. The scheduler of claim 18 , wherein the updated schedule is a schedule of the packets for a current time slot.

20. The scheduler of claim 18 , wherein the previous schedule is a schedule of the packets at M time slots before a current time slot.