Granted Patent B2

US 7,227,866 · App. 10/273,857 · Granted Jun 5, 2007

Assignee: Tropic Networks Inc.

Abstract

Claims (66)

1. A method for selecting one of a plurality of queues of data packets, for switching to an output port in a current timeslot, for achieving work conserving Round Robin (RR) scheduling, the method comprising the steps of:

generating a mask for a given queue for masking all queues outside a consideration range of the given queue; and

applying the mask and a queue ready flag for the given queue for determining if the given queue is to be selected for switching to the output port in the current timeslot;

wherein the consideration range is a set of queues having priority over the given queue;

wherein the step of generating a mask for the given queue, comprising the steps of:

generating the consideration range for the given queue;

setting an Nth bit in said mask for the given queue to 1, if a queue with index N is in the consideration range of the given queue; and

setting an Nth bit in said mask for the given queue to 0, if the queue with an index N is outside the consideration range of the said queue;

wherein generating the consideration range of the given queue, comprising a step of:

assigning a set of queues with indices higher than the index of a queue served in a previous timeslot, but lower than the index of said queue, to the consideration range of said queue;

wherein the given queue has a higher index than the index of the queue served in the previous time slot.

2. A method for selecting one of a plurality of queues of data packets, for switching to an output port in a current timeslot, for achieving work conserving Round Robin (RR) scheduling, the method comprising the steps of:

generating a mask for a given queue for masking all queues outside a consideration range of the given queue; and

applying the mask and a queue ready flag for the given queue for determining if the given queue is to be selected for switching to the output port in the current timeslot;

wherein the consideration range is a set of queues having priority over the given queue;

wherein the step of generating a mask for the given queue, comprising the steps of:

generating the consideration range for the given queue;

setting an Nth bit in said mask for the given queue to 1, if a queue with index N is in the consideration range of the given queue; and

setting an Nth bit in said mask for the given queue to 0, if the queue with an index N is outside the consideration range of the said queue;

wherein generating the consideration range of the given queue comprising a step of:

assigning the set of queues with indices higher than the index of the queue served in the previous timeslot, as well as the queues with indices lower than the index of said queue, to the consideration range of the given queue;

wherein the given queue has a tower index than the index of the queue served in the previous timeslot.

3. A method as claimed in claim 1 , wherein the queue ready flag is set to 1, if the given queue is non-empty.

4. A method as in claim 1 , wherein the queue ready flag is set to 0, if the given queue is empty.

5. A method as claimed in claim 1 , wherein the step of applying the masks and the queue ready flags, further comprising the steps of:

applying an AND operation on the queue ready flags with the mask for the given queue;

applying a Bitwise NOR operation on each of the results of the And operations;

combining the result of the Bitwise NOR operation for each queue with the corresponding queue ready flag; and

storing the result in a service bit for the given queue.

6. A method as claimed in claim 5 , wherein the step of storing the result further comprising the steps of:

storing a 1 in the service bit of only one of the plurality of queues, when the given queue is selected for switching to the output port, in the current timeslot; and

storing a 0 in the service bit of all queues other than the selected queue, in the current timeslot.

7. A system for selecting one of a plurality of queues of data packets for switching to an output port in a current timeslot, for achieving work-conserving Round Robin scheduling, the system comprising:

means for generating a mask for a given queue for masking all queues outside a consideration range of the given queue; and

means for applying the mask and a queue ready flag for the given queue, for determining if the given queue is to be selected for switching to the output port, in the current timeslot;

wherein the consideration range is a set of queues having priority over the given queue;

the system further comprises:

means for generating the consideration range of the given queue;

means for setting an Nth bit in said mask for the given queue to 1, if a queue with an index N is in the consideration range of the given queue; and

means for setting an Nth bit in said mask for the given queue to 0, if the queue with an index N;

wherein the means for generation of the consideration range of the given queue further comprises:

means for assigning the set of queues with indices higher than the index of a queue served in a previous timeslot, but lower than the index of said queue, to the consideration range of said queue;

wherein the given queue has a higher index than the index of the queue served in the previous timeslot.

8. A system for selecting one of a plurality of queues of data packets for switching to an output port in a current timeslot, for achieving work-conserving Round Robin scheduling, the system comprising:

means for generating a mask for a given queue for masking all queues outside a consideration range of the given gueue; and

means for applying the mask and a queue ready flag for the given queue, for determining if the given queue is to be selected for switching to the output port, in the current timeslot;

wherein the consideration range is a set of queues having priority over the given queue;

the system further comprises:

means for generating the consideration range of the given queue;

means for setting an Nth bit in said mask for the given queue to 1, if a queue with an index N is in the consideration range of the given queue; and

means for setting an Nth bit in said mask for the given queue to 0, if the queue with an index N

wherein the means for generation of the consideration range of the given queue further comprises:

means for assigning the set of queues with indices higher than that of the queue served in the previous timeslot as well as the queues with indices lower than the index of the given queue, to consideration range of said queue;

wherein the given queue has a lower index than the index of the queue served in the previous timeslot.

9. A system as claimed in claim 7 , the queue ready flag is set to 1;

wherein the queue is non-empty.

10. A system as claimed in claim 7 , the queue ready flag is set to 0;

wherein the queue is empty.

11. A system as claimed in claim 7 , wherein the means for application of the masks and queue ready flags, further comprises:

means for applying an AND operation on the queue ready flags with the mask for said queue;

means for applying a Bitwise NOR operation on each of the results of the And operations;

means for combining the result of the Bitwise NOR operation for each queue with its queue ready flag; and

means for storing the result in the service bit for said queue.

12. A system as claimed in claim 11 , wherein the means for storing the result further comprises:

storing a 1 in the service bit of only one of the plurality of queues, when the given queue is selected for switching to the output port in the current timeslot; and

storing a 0 in the service bit of all queues other than the selected queue in the current timeslot.

Assignments (10)

Continuity (1)