Deficit and group round robin scheduling for efficient network traffic management
View Patent ↗Data traffic is scheduled by, in a first scheduler, selecting a source of traffic from a plurality of sources of traffic, each source being associated with a second scheduler, in a second scheduler associated with the selected source of traffic, selecting a type of traffic from a plurality of types of traffic within the source selected by the first scheduler, and transmitting data of the selected type and source. Scheduling data traffic apparatus and method using deficit and group ratio round robin budgeting.
1. A link scheduler apparatus to determine an order to schedule links comprising:
a processor configured by computer instructions encoded onto a non-transitory tangible mass storage device to:
group together links that have similar weights, and
maintain a list of groups of links having similar weights based on a guaranteed or actual rate;
select a group to transmit packets based on the ratio of bandwidth needed by each group to the bandwidth needed by every other group whereby each group transmits an amount of data in turn, and
within each group, select an individual link to transmit packets based on the ratio of its traffic volume to that of the other links in the selected group;
another scheduler to manage all of its children wherein the schedulers are run independently of each other but ensure precise service intervals for all items within the overall scheduler wherein each scheduler is a process of the processor; and
an other processor for rate limitation to represent the physical capacity of a link wherein the processor is configured by computer instructions encoded onto the non-transitory tangible mass storage device to:
calculate an average time spent per byte for each link and link group object when it is running at its limit,
track the next time to send, and an “average idle time” variable,
track the variance with the actual next time data is sent,
send if the next time is past (or not set) because the link or link group is not rate limited, and
skip if the link or link group has exceeded its rate.
2. A link scheduler apparatus to determine an order to schedule links comprising:
a processor configured by a software program to group together links that have similar weights, and maintain a list of groups of links having similar weights based on a guaranteed or actual rate;
a pointer to contain a current weight group being serviced;
a quantum counter to determine when a current weight group ratio is satisfied and move the pointer back to the start of the list, wherein on a next invocation of the scheduler, that weight group is serviced and the quantum counter is decreased by an amount of data sent; and
a deficit counter to determine when to move to a next weight group, said deficit counter to enable each group to exceed its ratio during one transmission but to decrease a volume of data that group can send by that amount the next time it comes to be serviced, bounded by the smaller of maximum packet size or quantum size per service interval.
3. The apparatus of claim 2 further comprising the processor to move the pointer between weight groups by application of the following ordered rules after servicing the current weight group:
1, if the deficit and quantum counters are both above zero, then the pointer stays with current weight group;
2, if the deficit is at or below zero,
add the deficit credit to the deficit counter, add the quantum credit to the quantum counter, and move the pointer to next weight group;
3, if only the quantum is at or below zero, then add the quantum credit to the quantum counter and set the pointer to the first weight group.
4. The apparatus of claim 2 wherein the number of weight groups is between three and eight wherein
weight groups are defined as weights within a power of 2, thereby providing a maximum of 32 groups possible to cover all link types between 1 b/s (2.sup.0) and 2 Gb/s (2.sup.31).
5. The apparatus of claim 2 further comprising the processor further configured by computer instructions encoded onto the non-transitory tangible mass storage device to:
recalculate the ratios and credits for the affected groups periodically,
if the group does not shift in its sorted location then only the credit for the current group and the one that has larger weight needs to be updated,
if the adjusted weights for a group cause it to exceed the total weight of group in front of or behind it in the original list,
update the credit on three groups: the current group, the group that has larger weight, and the group above the previous location.
6. The apparatus of claim 5 wherein periodically is at the end of each Nth service frame wherein N is an integer variable under algorithmic or manual control.
7. The apparatus of claim 2 further comprising a management processor for idle link management wherein the management processor is configured by computer instructions encoded onto the non-transitory tangible mass storage device to:
on the condition every link within a weight group is flagged as idle and will give up its slot:
credit the smaller of its quantum or next weight group credit, remove this weight group at the end of the frame, recalculate the ratios and credits from the group in front of where it had resided,
on the condition of any link within a weight group flagged as idle becomes active:
move the weight group back into the correct location, and adjust the ratios/credits for the group and its preceding group.
8. The apparatus of claim 2 for nested link groups in a hierarchy further comprising an other scheduler to manage all of its children wherein the schedulers are run independently of each other but ensure precise service intervals for all items within the overall scheduler wherein the other scheduler is a process of the processor.
9. The apparatus of claim 2 further comprising a rate limiting processor for rate limitation to represent the physical capacity of a link wherein the rate limiting processor is configured by computer instructions encoded onto the non-transitory tangible mass storage device to:
calculate an average time spent per byte for each link and link group object when it is running at its limit, track the next time to send, and an “average idle time” variable, track the variance with the actual next time data is sent, send if the next time is past or not set because the link or link group is not rate limited, and skip if the link or link group has exceeded its rate.