TWO-COMPONENT BANDWIDTH SCHEDULER HAVING APPLICATION IN MULTI-CLASS DIGITAL COMMUNICATION SYSTEMS

摘要

The method for servicing queues holding messages, such as ATM datapackets, for subsequent processing or transmission to a resource such as acommunications link having a finite processing capability comprises the stepsofservicing each queue by forwarding the messages thereof to the resource attimeintervals corresponding to a guaranteed service rate of the queue, providedthe queue isnon-empty; and, during time intervals when none of the queues have messagesbeingforwarded to the resource in conformance with the above step, servicing thequeues inaccordance with a proportion of a remaining or idle resource bandwidthallocated toeach queue. The method is preferably carried out by a hierarchical schedulercomprising an exhaustive sub-scheduler servicing a plurality of lower levelsub-schedulers in accordance with non-equal priority levels assigned thereto;M non-workconserving shaper sub-schedulers feeding the exhaustive sub-scheduler; and Nworkconserving idle bandwidth sub-schedulers feeding the exhaustive sub-scheduler.Insuch a scheduler, a queue concurrently contends for service by one of theshapersub-schedulers and one of the idle bandwidth sub-schedulers, wherein theshapersub-scheduler servicing the queue has a higher priority level with respect tothe exhaustivesub-scheduler than the idle bandwidth sub-scheduler servicing the same queue.Thetechnique distributes the idle bandwidth of the resource in a way which is de-coupledfrom the guaranteed service rates of the queues, thereby providing a moreefficientbandwidth distribution.