Patent ID: 7706386
Filing Date: 2010-04-27
Classification: H04L

Abstract:
1. A system for scheduling packets from different flows for transmission via a channel, said system comprising: a scheduling engine; a memory configured to store: with the scheduling engine configured to: queue packets from each flow; characterize each flow by a traffic class comprising key_ dequeue a traffic class into a node of a calendar represented by a radix tree having a plurality of levels, with the leaf nodes of the radix tree corresponding to time slots of the calendar with each leaf node identified by an index being a k bit number, where k is a positive integer, and with the radix tree recursively formed by assigning nodes having a set of identical most significant bits to a parent node having an index equal to the set of most significant bits, with the set most significant bits being the prefix of the parent node, where the leaf nodes define slots of maximum precision and each internal node corresponds to a slot that includes time between the nodes prefix and the prefix of the next node in the same level of the tree; for traffic classes with different burst tolerances, dequeue a traffic class with a minimum burst tolerance into the leaf nodes according to key_ augment the radix tree with a heap to form an augmented radix tree by utilizing key_ prune the augmented radix tree to form a topiary tree with only 4C nodes disposed about a current time value are included in each level, where C is a constant and where for any traffic class the burst tolerance divided by the time slot size must be less than or equal to C; detach a time-ineligible node from its current time-ineligible parent node and attach the time-ineligible node to a time-eligible parent node while maintaining a prefix portion of the time-ineligible node that identifies the location of the time-ineligible node in a group of siblings to wrap the topiary tree as the current time value moves forward; and select a node to service by fetching all root nodes, selecting a first eligible root node holding a key_