Hierarchical prioritized round robin (HPRR) scheduling
The HPRR method uses “token bucket” rate classifiers to mark each individual packet as conforming or not conforming to a traffic specification for the flow. Flows are considered to be in a single service class. One such class is distinguished as a default “best effort” service class. Each service class is assigned a weight corresponding to its fraction of bandwidth granted to the class when all classes are active. The HPRR method allows a packet from a flow to be forwarded in one of two ways, either as part of its class's allocated bandwidth or as part of the “best effort” bandwidth. By always providing two paths for a flow to send its packets, a flow is always given its “fair share” of two different classes: its primary or configured class and the best effort class. An overbooked class will have each of its flows compete for the inadequate bandwidth allocated to the class, but because each flow can use the best effort bandwidth it also gets a fair share of that bandwidth to allow the classes bandwidth guarantees to be when other classes are inactive.
1. A method for scheduling the transmission of packets onto a data communications link, comprising the steps of:
a) receiving a plurality of packets of a data flow;
b) configuring said flow to a service class;
c) scheduling transmission bandwidth of said service class to a selected limit;
d) forwarding packets of said flow that conform to said selected limit;
e) identifying a default class having a default class bandwidth; and
f) forwarding packets using both the bandwidth allocated to the service class and the bandwidth allocated to the default class.
2. A method for selecting among a plurality of prioritized packet queues for a next packet for transmission in a network, comprising the steps of:
a) assigning to each queue in the plurality of prioritized packet queues a quantum of allocated bandwidth of a shared bandwidth;
b) assigning to each queue in the plurality of prioritized packet queues a deficit representing a permitted amount of data to be forwarded by said queue;
c) selecting a next packet for transmission from a queue having a high priority and a deficit value that exceeds the size of said next packet;
d) reducing the deficit of the queue selected in step c by the size of said selected next packet; and
e) if all backlogged queues in said plurality of prioritized packet queues have insufficient deficit to forward a next packet, adding the value of the quantum to the deficit in each said backlogged queue, whereby a new round of selection from among the set of prioritized packet queues is started.
3. The method of claim 2 further comprising the step of
f) if all queues are empty, adding the value of the deficit to the value of the quantum in each said empty queue, whereby a new round of selection from the set of prioritized packet queues is started.