Distributed scheduler for packet switches and passive optical networks
View Patent ↗Scheduling system and method for scheduling data packets from an input port ( 1 1 . . . 1 i ) to an output port ( 3 1 . . . 3 o ), comprising virtual output queues ( 6 1 . . . 6 n ) being arranged to store data packets from the input port ( 1 1 . . . 1 i ) destined for a specific output port ( 3 1 . . . 3 o ). The scheduling system comprises a scheduling tree ( 10 ) having a plurality of comparison layers, each comparison layer being arranged for pair-wise comparing requests received from the associated virtual output queues ( 6 1 . . . 6 n ) in parallel and sending the request with a higher priority to a higher level comparison layer until a single request remains, the single request indicating the virtual output queue ( 6 1 . . . 6 n ) scheduled to send its data packet to the associated output port ( 3 1 . . . 3 o ).
1. Method for scheduling data packets from a plurality of input ports to at least one output port comprising the steps of:
storing data packets in a plurality of virtual output queues, a virtual output queue being arranged to store data packets from one of the plurality of input ports destined for a specific one of the at least one output port; and
scheduling the plurality of virtual output queues,
wherein
the step of scheduling the plurality of virtual output queues comprises the steps of:
scheduling the virtual output queues associated with one of the at least one output port in parallel, by scheduling the virtual output queues associated with one of the at least one output port by means of a scheduling tree,
the scheduling tree comprising at least one comparison layer for executing the steps of:
pair-wise comparing requests received from the associated virtual output queues in parallel; and
sending the request with a higher priority to a higher level comparison layer until a single request remains, the single request indicating the virtual output queue scheduled to send its data packet to the associated output port;
in which the comparison layer executes the further step of storing the request with a higher priority, and after receiving a permit from a higher order level, the permit comprising the single request, sending the permit to a lower level comparison layer in accordance with the stored request associated with the higher priority.
2. Method according to claim 1 , in which the request comprises an identification of the associated virtual output queue.
3. Method according to claim 1 , in which the step of pair-wise comparing requests applies a fixed precedence for one of the two requests received.
4. Method according to claim 1 , in which the step of pair-wise comparing requests applies an alternating precedence for each of the two requests received.
5. Method according to claim 1 , in which the request comprises a priority level and the step of pair-wise comparing requests applies a comparison of the priority levels.
6. Method according to claim 1 , in which the comparison layer executes the further step of transporting the data packet associated with the higher priority request to the higher level comparison layer.
7. Scheduling system for scheduling data packets from a plurality of input ports to at least one output port, comprising virtual output queues being arranged to store data packets from one of the plurality of input ports destined for a specific one of the at least one output port, wherein
the scheduling system comprises a scheduling tree having a plurality of comparison layers, each comparison layer comprising at least one comparing element, the comparing element comprising two input gates and an output gate, the input gates of the comparing elements of the lowest level comparison layer being connected to the plurality of virtual output queues, the output gates of two comparing elements of a comparison layer being connected to the input gates of one comparing element of a higher level comparison layer, and each comparing element being arranged to evaluate requests received at its input gates and provide the highest priority request at its output gate;
in which the at least one comparing element comprises memory means for storing the request with a higher priority, and the comparing element is further arranged to receive a permit from a higher level comparison layer, the permit comprising the request having the highest priority at the highest level comparison layer, and to sending the permit to the comparing element of a lower level comparison layer in accordance with the stored request associated with the higher priority.
8. Scheduling system according to claim 7 , in which the request comprises an identification of the associated virtual output queue.
9. Scheduling system according to claim 7 , in which the at least one comparing element is arranged to apply a fixed precedence for one of its two input gates.
10. Scheduling system according to claim 7 , in which the at least one comparing element is arranged to apply an alternating precedence for its two input gates.
11. Scheduling system according to claim 7 , in which the request comprises a priority level and in which the at least one comparing element is arranged to compare the priority levels of the requests.
12. Scheduling system according to claim 7 , in which the at least comparing element comprises a data path for transporting a data packet associated with the highest priority request to the higher level comparison layer.
13. Scheduling system according to claim 7 , comprising a plurality of scheduling trees connected in series.
14. Scheduling system according to claim 7 , comprising a plurality of scheduling trees associated with a first and a second output port, the scheduling system being arranged to activate the scheduling tree associated with the second output port if the first port is unavailable for the associated virtual output queue.