Two-component bandwidth scheduler having application in multi-class digital communications systems

Abstract

The method for servicing queues holding messages, such as ATM data packets, for subsequent processing or transmission to a resource such as a communications link having a finite processing capability comprises the steps of servicing each queue by forwarding the messages thereof to the resource at time intervals corresponding to a guaranteed service rate of the queue, provided the queue is non-empty; and, during time intervals when none of the queues have messages being forwarded to the resource in conformance with the above step, servicing the queues in accordance with a proportion of a remaining or idle resource bandwidth allocated to each queue. The method is preferably carried out by a hierarchical scheduler comprising an exhaustive sub-scheduler servicing a plurality of lower level sub-schedulers in accordance with non-equal priority levels assigned thereto; M non-work conserving shaper sub-schedulers feeding the exhaustive sub-scheduler; and N work conserving idle bandwidth sub-schedulers feeding the exhaustive sub-scheduler. In such a scheduler, a queue concurrently contends for service by one of the shaper sub-schedulers and one of the idle bandwidth sub-schedulers, wherein the shaper sub-scheduler servicing the queue has a higher priority level with respect to the exhaustive sub-scheduler than the idle bandwidth sub-scheduler servicing the same queue. The technique distributes the idle bandwidth of the resource in a way which is de-coupled from the guaranteed service rates of the queues, thereby providing a more efficient bandwidth distribution.