Back to results
US 2009/0154483 A1Published application
A 3-level queuing scheduler supporting flexible configuration and etherchannel
AssigneeCisco Technology, Inc., a corporation of California
InventorJian Qu
Life of this patent
Estimating the term…
Abstract
In one embodiment, a scheduler for a queue hierarchy only accesses sub-groups of bucket nodes in order to determine the best eligible queue bucket to transmit next. Etherchannel address hashing is performed after scheduling so that an Etherchannel queue including a single queue in the hierarchy is implemented to guarantee quality of service.
Claims15
A method comprising:
- accessing only an updated adjacent group of first level queue buckets included in a first memory structure including N first level queue buckets each holding a token value associated with a transmission queue and with each first level queue bucket having a unique ID, with the updated adjacent group of first level queue buckets being a group of M first level queue buckets including a first level queue bucket holding a most recently updated token value, where N is a positive integer and M is a positive integer less than N and where the first level queue buckets are grouped into L first level queue adjacent groups where L is a positive integer equal to N divided by M;
- propagating a first level minimum token value accessed from the updated adjacent group of first level queue buckets and a first level MIN ID value equal to the unique ID of the first level queue bucket holding the minimum token value;
- storing the first level minimum token value and first level MIN ID in a second level bucket, associated with the updated first level adjacent group, included in a second memory structure including L second level buckets with a second level adjacent group being a group of M second level buckets and where the second level buckets are grouped into K second level adjacent groups where K is a positive integer equal to L divided by M;
- accessing only an updated second level adjacent group including the second level bucket holding the first level minimum token value and the first level MIN ID;
- propagating a second level minimum token value accessed from the updated adjacent group of second level queue buckets and a second level MIN ID value identifying the first level bucket holding the second level minimum token value;
- storing the minimum second level token value and second level MIN ID in a third level bucket, associated with the updated second level adjacent group, included in a third memory structure including K third level buckets;
- accessing all third level buckets;
- and
- propagating a third level minimum token value and a third level ID equal to the unique ID identifying the first level queue bucket holding the third level minimum token value so that the transmission queue associated with the third level ID can be scheduled for transmission.
6 more elements
A system comprising:
- a first memory level including N first level memory buckets, where N is a positive integer and where each first level memory bucket holds a token and where each first level memory bucket is identified by an ID;
- a second memory level including L second level memory buckets, where L is a positive integer and where each second level memory bucket holds a token and an ID;
- a third memory level including K third level memory buckets where K is a positive integer and where each third level memory bucket holds a token and an ID;
- L first level logic elements having M inputs and a single output where M is a positive integer and L is equal to N divided by M, with each input of a first level logic element coupled to a unique first level memory bucket and the output coupled to a second level memory bucket;
- K second level logic elements having M inputs and a single output where K is equal to L divided by M, with each input of a first level logic element coupled to a unique second level memory bucket and the output coupled to a third level memory bucket;
- a single third level logic element having K inputs and a single output, with each input coupled to a third level memory bucket and the output for providing a minimum token value and the ID of a first level bucket holding the minimum token value;
- with each logic element outputting the minimum token stored in a memory bucket coupled to any of its inputs and the ID of the first level bucket holding the token which is output.
4 more elements
The system of claim 8 where N is equal to 128 and M is equal to 8.
A system comprising:
- a first plurality of pipeline stages including a binary tree scheduling structure for scheduling a transmission queue for transmission from a virtual port;
- and
- a second plurality of pipeline stages coupled to an output of the first plurality of pipeline stages for assigning one of a plurality of physical links over which to transmit a frame from a scheduled transmission queue.
A system comprising:
- means for accessing only an updated adjacent group of first level queue buckets included in a first memory structure including N first level queue buckets each holding a token value associated with a transmission queue and with each first level queue bucket having a unique ID, with the updated adjacent group of first level queue buckets being a group of M first level queue buckets including a first level queue bucket holding a most recently updated token value, where N is a positive integer and M is a positive integer less than N and where the first level queue buckets are grouped into L first level queue adjacent groups where L is a positive integer equal to N divided by M;
- means for propagating a first level minimum token value accessed from the updated adjacent group of first level queue buckets and a first level MIN ID value equal to the unique ID of the first level queue bucket holding the minimum token value;
- means for storing the first level minimum token value and first level MIN ID in a second level bucket, associated with the updated first level adjacent group, included in a second memory structure including L second level buckets with a second level adjacent group being a group of M second level buckets and where the second level buckets are grouped into K second level adjacent groups where K is a positive integer equal to L divided by M;
- means for accessing only an updated second level adjacent group including the second level bucket holding the first level minimum token value and the first level MIN ID;
- means for propagating a second level minimum token value accessed from the updated adjacent group of second level queue buckets and a second level MIN ID value identifying the first level bucket holding the second level minimum token value;
- means for storing the minimum second level token value and second level MIN ID in a third level bucket, associated with the updated second level adjacent group, included in a third memory structure including K third level buckets;
- means for accessing all third level buckets;
- and
- means for propagating a third level minimum token value and a third level ID equal to the unique ID identifying the first level queue bucket holding the third level minimum token value so that the transmission queue associated with the third level ID can be scheduled for transmission.
6 more elements
Dependencies are inferred from the claim text.