Method and apparatus for operating fast switches using slow schedulers
The invention includes an apparatus and method for switching packets through a switching fabric. The apparatus includes a plurality of input ports and output ports for receiving arriving packets and transmitting departing packets, a switching fabric for switching packets from the input ports to the output ports, and a plurality of schedulers controlling switching of packets through the switching fabric. The switching fabric includes a plurality of virtual output queues associated with a respective plurality of input-output port pairs. One of the schedulers is active during each of a plurality of timeslots. The one of the schedulers active during a current timeslot provides a packet schedule to the switching fabric for switching packets through the switching fabric during the current timeslot. The packet schedule is computed by the one of the schedulers active during the current timeslot using packet departure information for packets departing during previous timeslots during which the one of the schedulers was active and packet arrival information for packets arriving during previous timeslots during which the one of the schedulers was active.
1. An apparatus, comprising:
a plurality of input ports for receiving arriving packets;
a plurality of output ports for transmitting departing packets;
a switching fabric for switching packets from the input ports to the output ports, the switching fabric comprising a plurality of virtual output queues for queuing packets based on the respective input ports on which the packets are received and the respective output ports for which the packets are destined; and
a plurality of schedulers for computing packet schedules for use by the switching fabric in switching packets, wherein the schedulers are active during timeslots, wherein during a given timeslot only one of the schedulers is active for exchanging information with the switching fabric;
wherein each of the schedulers is configured to, during a current timeslot in which the scheduler is active:
receive, from the switching fabric, packet arrival information for packets arriving at the virtual output queues during the current timeslot; and
provide, to the switching fabric, a packet schedule for use by the switching fabric in switching packets from selected ones of the virtual output queues to associated ones of the output ports during the current timeslot, wherein the packet schedule is computed by the scheduler using packet departure information for packets departing from the virtual output queues during at least one previous timeslot during which the scheduler was active and packet arrival information for packets arriving at the virtual output queues during at least one previous timeslot during which the scheduler was active.
2. The apparatus of claim 1 , wherein each of the schedulers is configured to:
determine the packet departure information for the current timeslot from the packet schedule.
3. The apparatus of claim 1 , wherein each scheduler comprises a respective plurality of counters;
wherein, for each scheduler, the plurality of counters of the scheduler are associated with the respective plurality of virtual output queues.
4. The apparatus of claim 3 , wherein each of the schedulers is configured to:
during the current timeslot in which the scheduler is active, update counters of the scheduler using the packet departure information for packets departing from the virtual output queues during the current timeslot and the packet arrival information for packets arriving to the virtual output queues during the current timeslot.
5. The apparatus of claim 1 , wherein the schedulers become active in a round-robin manner.
6. The apparatus of claim 1 , wherein each of the schedulers is configured to:
compute the packet schedule for the current timeslot during a plurality of timeslots between a previous timeslot in which the scheduler was active and the current timeslot.
7. The apparatus of claim 1 , wherein each of the schedulers is configured to:
compute a next packet schedule over a plurality of timeslots between the current timeslot in which the scheduler is active and a next timeslot in which the scheduler is active.
8. The apparatus of claim 7 , wherein each of the schedulers is configured to:
compute the next packet schedule using packet arrival information associated with the current timeslot and packet departure information associated with the current timeslot.
9. The apparatus of claim 1 , wherein each of the schedulers is configured to:
compute the packet schedule for the current timeslot using a maximum weight matching algorithm.
10. The apparatus of claim 9 , wherein the maximum weight matching algorithm uses values of the counters, of the scheduler computing the packet schedule, as weights.
11. A method for switching packets via a switching fabric, the switching fabric comprising a plurality of virtual output queues for queuing packets being switched between a plurality of input ports and a plurality of output ports, the switching fabric having a plurality of schedulers associated therewith, the method comprising:
queuing packets received during a current timeslot, wherein the packets are queued using the virtual output queues based on the respective input ports on which the packets are received and the respective output ports for which the packets are destined; and
polling one of the schedulers for a current packet schedule for use in switching packets during the current time slot, wherein the current packet schedule is computed using packet departure information for packets departing from the virtual output queues during at least one previous timeslot during which the polled one of the schedulers was active and packet arrival information for packets arriving at the virtual output queues during at least one previous timeslot during which the polled one of the schedulers was active; and
switching packets from selected ones of the virtual output queues to associated ones of the output ports using the current packet schedule.
12. The method of claim 11 , further comprising:
providing current packet arrival information to the polled one of the schedulers during the current timeslot, wherein the current packet arrival information identifies packets arriving at the virtual output queues during the current timeslot.
13. The method of claim 12 , further comprising:
receiving, at the polled one of the schedulers, the current packet arrival information; and
updating, at the polled one of the schedulers, selected ones of a plurality of counters associated with respective ones of the virtual output queues associated with input ports on which packets were received during the current timeslot, wherein the selected ones of the counters are updated using the packet arrival information.
14. The method of claim 11 , further comprising:
updating, at the polled one of the schedulers, selected ones of a plurality of counters associated with respective ones of the virtual output queues associated with output ports on which packets were transmitted during the current timeslot, wherein the selected ones of the counters are updated using the current packet schedule.
15. The method of claim 11 , further comprising:
computing, at the polled one of the schedulers, a next packet schedule, wherein the polled one of the schedulers computes the next packet schedule over a plurality of timeslots between the current timeslot in which the polled one of the schedulers is polled and a next timeslot in which the polled one of the schedulers is polled.
16. A method for switching packets though a switching fabric, the switching fabric comprising a plurality of virtual output queues and having a plurality of schedulers associated therewith, wherein for one of the schedulers active during a current timeslot the method comprises:
providing a current packet schedule from the active one of the schedulers to the switching fabric during the current timeslot, wherein the current packet schedule identifies selected ones of the virtual output queues from which packets are scheduled to depart during the current timeslot;
receiving packet arrival information at the active one of the schedulers from the switching fabric during the current timeslot, wherein the packet arrival information identifies selected ones of the virtual output queues at which packets arrive during the current timeslot; and
computing a next packet schedule using the current packet schedule and the packet arrival information.
17. The method of claim 16 , wherein the schedulers become active in a round-robin manner in response to polling by the switching fabric.
18. The method of claim 16 , wherein the current packet schedule is computed using packet departure information for packets departing from the virtual output queues during at least one previous timeslot during which the active one of the schedulers was active and packet arrival information for packets arriving at the virtual output queues during at least one previous timeslot during which the active one of the schedulers was active.
19. The method of claim 16 , wherein the one of the schedulers active during the current timeslot computes the next packet schedule using a maximum weight matching algorithm.
20. The method of claim 16 , wherein the active one of the schedulers computes the next packet schedule over a plurality of timeslots between the current timeslot in which the active one of the schedulers is active and a next timeslot in which the active one of the schedulers is active.