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

摘要

The method for servicing queues (14) holding data (12) packets for subsequent transmission to a communications link (16) processing comprises the steps of servicing each queue by forwarding its data packets to the link 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 packets being forwarded to the link in conformance with the above step, servicing the queues in accordance with a proportion of idle bandwidth allocated to each queue. The method is preferably carried out by a hierarchical scheduler (10) comprising an exhaustive scheduler (30) servicing a plurality of lower level schedulers in accordance with non-equal priority levels assigned thereto; a non-work conserving shaper scheduler (20) feeding the exhaustive scheduler; and a work conserving idle bandwidth scheduler (25) feeding the exhaustive scheduler (30). Each queue (14) concurrently contends for service from the shaper scheduler (20) and the idle bandwidth schedulers (25). The shaper scheduler (20) servicing the queue has a higher priority level with respect to the exhaustive scheduler (30) than the idle bandwidth scheduler (25) servicing the same queue. The technique distributes the idle bandwidth of the communications link (16) in a way which is de-coupled from the guaranteed service rates of the queues, thereby providing a more efficient distribution of the total available bandwidth.