Interleaved weighted fair queuing mechanism and system

A method of scheduling packets from multiple queues onto a common output packet stream, the method comprising:

• maintaining a programmable interleaving table having multiple entries, each entry identifying one of the queues with an epoch value, each entry comprising an epoch counter field, wherein the number of entries in the programmable interleaving table exceeds the number of queues, such that at least some queues are identified more than once in the table, each entry containing a field explicitly identifying the queue associated with that entry;
• maintaining a pointer to a current table entry in the programmable interleaving table;
• for each epoch in a sequence of epochs, scheduling packets onto the output packet stream from the queue identified with the current table entry, and charging that entry for use of the epoch by changing the value of the epoch counter field by one;
• and
• moving the pointer to a next table entry when the current table entry has been charged with use of a number of epochs set aside for that entry, wherein moving the pointer to a next table entry when the current table entry has been charged with use of a number of epochs set aside for that entry comprises moving the pointer after the value in the epoch counter has been changed a number of times corresponding to the current table entry's epoch value.

A method of scheduling packets from multiple queues onto a common output packet stream, the method comprising:

• maintaining a programmable interleaving table having multiple entries, each entry identifying one of the queues with an epoch value, each entry comprising an epoch counter field, wherein the number of entries in the programmable interleaving table exceeds the number of queues, such that at least some queues are identified more than once in the table, each entry containing a field explicitly identifying the queue associated with that entry;
• maintaining a pointer to a current table entry in the programmable interleaving table;
• for each epoch in a sequence of epochs, scheduling packets onto the output packet stream from the queue identified with the current table entry, and charging that entry for use of the epoch by changing the value of the epoch counter field by one;
• and
• moving the pointer to a next table entry when the current table entry has been charged with use of a number of epochs set aside for that entry, wherein moving the pointer to a next table entry when the current table entry has been charged with use of a number of epochs set aside for that entry comprises moving the pointer after each epoch to the next table entry that has not yet changed the value of its epoch counter field a number of times corresponding to that entry's epoch value.

A method of scheduling packets from multiple queues onto a common output packet stream, the method comprising:

• maintaining a programmable interleaving table having multiple entries, each entry identifying one of the queues with an epoch value, wherein the number of entries in the programmable interleaving table equals the number of queues, wherein each entry comprises an epoch value field and an epoch counter field;
• maintaining a pointer to a current table entry in the programmable interleaving table;
• for each epoch in a sequence of epochs scheduling packets onto the output packet stream from the queue identified with the current table entry and charging that entry for use of the epoch, wherein charging an entry for use of an epoch comprises changing the value of that field's epoch counter by one;
• and
• moving the pointer to a next table entry when the current table entry has been charged with use of a number of epochs set aside for that entry, wherein moving the pointer to a next table entry when the current table entry has been charged with use of a number of epochs set aside for that entry comprises moving the pointer, after each epoch, to the next table entry that has not yet changed the value of its epoch counter field a number of times corresponding to that entry's epoch value.

An integrated circuit having a scheduler comprising:

• a programmable interleaving table having multiple entries, each entry identifying a queue with an epoch value;
• a pointer register identifying a current entry in the interleaving table;
• and
• a queue sequencer to supply, for each epoch, a queue identifier based on the current entry in the programmable interleaving table, to charge the current entry for use of the epoch, and to step the pointer register to a next table entry when the current entry has been charged with use of a number of epochs set aside for that entry wherein the queue sequencer has access to a queue status register that indicates whether each queue identified in the programmable interleaving table is empty or not, the queue sequencer using the queue status register contents to step the pointer register to a next table entry within an epoch, when the queue status of the queue identified with the current entry indicates that that queue is empty.

An apparatus comprising a computer-readable medium containing computer instructions that, when executed, cause a processor or multiple communicating processors to perform a method for scheduling packets from multiple queues onto a common output packet stream, wherein the common output packet stream serves multiples sets of queues the method comprising:

• maintaining a programmable interleaving table having multiple entries, each entry identifying one of the queues with an epoch value, each set of queues having its own programmable interleaving table;
• maintaining a separate pointer for each set of queues to a current table entry in the programmable interleaving table for that set of queues;
• selecting, for each epoch in the sequence of epochs, one of the sets of queues for packet scheduling during that epoch;
• selecting the pointer corresponding to the selected set of queues for use during that epoch;
• scheduling packets onto the output packet stream from the queue identified with the current table entry of the selected pointer, and charging that entry for use of the epoch;
• and
• moving the pointer to a next table entry when the current table entry has been charged with use of a number of epochs set aside for that entry.

An apparatus comprising a computer-readable medium containing computer instructions that, when executed, cause a processor or multiple communicating processors to perform a method for scheduling packets from multiple queues onto a common output packet stream, the method comprising:

• maintaining a programmable interleaving table having multiple entries, each entry identifying one of the queues with an epoch value, each entry comprising an epoch counter field, wherein the number of entries in the programmable interleaving table exceeds the number of queues, such that at least some queues are identified more than once in the table, each entry containing a field explicitly identifying the queue associated with that entry;
• maintaining a pointer to a current table entry in the programmable interleaving table;
• for each epoch in a sequence of epochs, scheduling packets onto the output packet stream from the queue identified with the current table entry, and charging that entry for use of the epoch by changing the value of the epoch counter field by one;
• and
• moving the pointer to a next table entry when the current table entry has been charged with use of a number of epochs set aside for that entry, wherein moving the pointer to a next table entry when the current table entry has been charged with use of a number of epochs set aside for that entry comprises moving the pointer after the value in the epoch counter has been changed a number of times corresponding to the current table entry's epoch value.

An apparatus comprising a computer-readable medium containing computer instructions that, when executed, cause a processor or multiple communicating processors to perform a method for scheduling packets from multiple queues onto a common output packet stream, the method comprising:

• maintaining a programmable interleaving table having multiple entries, each entry identifying one of the queues with an epoch value, each entry comprising an epoch counter field, wherein the number of entries in the programmable interleaving table exceeds the number of queues, such that at least some queues are identified more than once in the table, each entry containing a field explicitly identifying the queue associated with that entry;
• maintaining a pointer to a current table entry in the programmable interleaving table;
• for each epoch in a sequence of epochs, scheduling packets onto the output packet stream from the queue identified with the current table entry and charging that entry for use of the epoch by changing the value of the epoch counter field by one;
• and
• moving the pointer to a next table entry when the current table entry has been charged with use of a number of epochs set aside for that entry, wherein moving the pointer to a next table entry when the current table entry has been charged with use of a number of epochs set aside for that entry comprises moving the pointer after each epoch to the next table entry that has not yet changed the value of its epoch counter field a number of times corresponding to that entry's epoch value.