Granted Patent B2

US 6,944,171 · App. 09/804,591 · Granted Sep 13, 2005

Abstract

Claims (52)

1. A scheduling method in a switch in which an input data stream is received and stored in a number of output queues, the scheduling method handling the output queues and comprising the steps of:

set a flag of all queues as a first value (enabled);

polling all queues in order;

if the polled queue contains data, refill a deficit value indicating a maximum amount of data that may be sent from this queue;

if the deficit-value permits, then set a flag of the queue as a second value (active), send data, and decrease the deficit value a corresponding amount for the polled queue, else set a flag of the queue as a third value (disabled);

if any queue is active after all the queues have been polled, go to a local round, else set a flag of all queues as a enabled and start polling the first queue of the order again.

2. The scheduling method of claim 1 , wherein the local round comprises the steps of:

polling all queues in order;

if the polled queue is enabled, check for any data to be sent and refill the deficit value, if applicable, and set the flag to one of the three values as above, and send data, and decrease the deficit value a corresponding amount, if applicable;

if the polled queue is disabled, just poll the next queue;

if the polled queue is active, check the deficit, and if deficit value permits, check for any data to be sent and send data, and decrease the deficit value a corresponding amount, if applicable, else set the flag to the value disabled;

if any queue is active after all the queues have been polled, go to a new local round, else set a flag of all queues as a enabled and start polling the first queue of the order again.

3. The scheduling method of claim 2 , wherein the deficit value is reset (to zero) if the polled queue is active, has sufficient deficit but the queue is empty.

4. The scheduling method of claim 1 , wherein the deficit values to be assigned to the respective queues are weighted.

5. The scheduling method of claim 1 , wherein the deficit value is compared with a constant, e.g. zero, to check if the deficit value permits sending of data.

6. The scheduling method of claim 1 , wherein the deficit value is compared with a packet to be sent contained in the polled queue, to check if the deficit value permits sending of data.

7. The scheduling method of claim 1 , wherein a counter is incremented when a queue is set as active, and decremented when a queue is changed from active to another state, in order to check if any queue is active.

8. The scheduling method of claim 1 , wherein if all queues have been polled in a first order, the polling order is changed to a new order by sorting the queues according to the deficit value.

9. A scheduling device in a switch in which an input data stream is received in an enqueuer means and stored in a number of output queues, the scheduling device selecting data from the output queues to send, and comprising:

means for setting and keeping an order for polling the queues;

means for providing and storing a deficit for each queue, the deficit indicating the maximum amount of data which the queue may send;

means for providing a flag for each queue, the flag indicating if the queue can send data;

wherein the scheduling device is arranged to set a flag of all queues as a first value (enabled);

poll all queues in order;

if the polled queue contains data, refill the deficit value;

if the deficit value permits, then set a flag of the queue as a second value (active), send data, and decrease the deficit value a corresponding amount for the polled queue, else set a flag of the queue as a third value (disabled);

if any queue is active after all the queues have been polled, go to a local round, else set a flag of all queues as enabled and start polling the first queue of the order again.

10. The scheduling device of claim 9 , wherein the scheduling device is arranged to perform the following steps in the local round:

polling all queues in order;

if the polled queue is enabled, check for any data to be sent and refill the deficit value, if applicable, and set the flag to one of the three values as above, and send data, and decrease the deficit value a corresponding amount, if applicable;

if the polled queue is disabled, just poll the next queue;

if the polled queue is active, check the deficit, and if deficit value permits, check for any data to be sent and send data, and decrease the deficit value a corresponding amount, if applicable, else set the flag to the value disabled;

if any queue is active after all the queues have been polled, go to a new local round, else set a flag of all queues as a enabled and start polling the first queue of the order again.

11. The scheduling device of claim 10 , wherein the scheduling device is arranged to reset the deficit value (to zero) if the polled queue is active, has sufficient deficit but the queue is empty.

12. The scheduling device of claim 9 , wherein the deficit values to be assigned to the respective queues are weighted.

13. The scheduling device of claim 9 , wherein the scheduling device is arranged to compare the deficit value with a constant, e.g. zero, to check if the deficit value permits sending of data.

14. The scheduling device of claim 9 , wherein the scheduling device is arranged to compare the deficit value with a packet to be sent contained in the polled queue, to check if the deficit value permits sending of data.

15. The scheduling device of claim 9 , comprising a counter to be incremented when a queue is set as active, and decremented when a queue is changed from active to another state, in order to check if any queue is active.

16. The scheduling device of claim 9 , wherein the scheduling device is arranged to change the polling order to a new order by sorting the queues according to the deficit value, if all queues have been polled in a first order.

17. A scheduling method in a switch in which an input data stream is received and stored in a number of output queues, the scheduling method handling the output queues and comprising the steps of:

polling all queues in order;

if the polled queue contains data, refill a deficit value indicating a maximum amount of data that may be sent from this queue;

if the deficit value permits, send data, and decrease the deficit value a corresponding amount for the polled queue, else disable the queue;

if any queue is permitted to send after all the queues have been polled, go to a local round, else start polling the first queue of the order again.

18. A scheduling device in a switch in which an input data stream is received in an enqueuer means and stored in a number of output queues, the scheduling device selecting data from the output queues to send, and comprising:

means for setting and keeping an order for polling the queues;

means for providing and storing a deficit for each queue, the deficit indicating the maximum amount of data which the queue may send;

wherein the scheduling device is arranged to;

poll all queues in order;

if the polled queue contains data, refill the deficit value;

if the deficit value permits, then send data, and decrease the deficit value a corresponding amount for the polled queue, else disable the queue;

if any queue is permitted to send after all the queues have been polled, go to a local round, else start polling the first queue of the order again.

Assignments (7)