Programmable broadband gateway hierarchical output queueing

A computing device comprising:

• a processor;
• a network interface;
• and
• a memory including instruction operable to be executed by the processor to perform a set of actions to configure the processor to:
• configure a first plurality of queues in the memory to each have a first scheduled time, where the first plurality of queues is associated with a first class of service (CoS), the first scheduled time of each of queue of the first plurality of queues is different, and packets to be stored in each respective queue of the first plurality of queues will become available for dequeuing in accordance with the first scheduled time of the respective queue;
• configure a second plurality of queues in the memory to each have a second scheduled time, where the second plurality of queues is associated with a second CoS, the second scheduled time of each of queue of the second plurality of queues is different, and packets to be stored in each respective queue of the second plurality of queues will become available for dequeuing in accordance with the second scheduled time of the respective queue;
• receive a first packet directed to a first recipient device;
• determine that the first packet is associated with the first CoS;
• determine that the first packet is to be enqueued in the first plurality of queues based on the first CoS;
• determine a first rate shaper and a second rate shaper of a plurality of rate shapers to apply to the first packet;
• compute a first future time for transmission of the first packet via the network interface to produce a first flow rate of the first rate shaper;
• compute a second future time for transmission of the first packet via the network interface to produce a second flow rate of the second rate shaper;
• determine that the first future time is later than the second future time;
• select a first queue of the first plurality of queues into which to enqueue the first packet based on the first queue having a first scheduled time that is closest to the first future time while being equal-to-or-sooner than the first future time;
• enqueue the first packet into the first queue;
• dequeue packets from the first plurality of queues and from the second plurality of queues for transmission over the network, where the first packet is dequeued from the first queue at or after the first schedule time of the first queue;
• transmit the first packet to the first device via the network after the first packet is dequeued;
• configure a third plurality of queues to each have a third scheduled time, where the third plurality of queues is associated with the first CoS, the third scheduled time of each of queue of the third plurality of queues is different, and packets stored in each respective queue of the third plurality of queues become available for dequeuing at the third scheduled time of the respective queue;
• configure a fourth plurality of queues to each have a fourth scheduled time, where the fourth plurality of queues is associated with the second CoS, the fourth scheduled time of each of queue of the fourth plurality of queues is different, and packets stored in each respective queue of the fourth plurality of queues become available for dequeuing at the fourth scheduled time of the respective queue;
• impose a first aggregate rate to packets dequeued from the first plurality of queues and the second plurality of queues prior to transmitting those packets over the network to a first plurality of devices;
• impose a second aggregate rate to packets dequeued from the third plurality of queues and the fourth plurality of queues prior to transmitting those packets over the network to a second plurality of devices;
• and
• determine whether the first device is of the first plurality of devices or of the second plurality of devices, wherein the enqueuing of the first packet to the first queue of the first plurality of queues is further based on the first device being of the first plurality of devices.

A non-transitory computer-readable storage medium storing processor-executable instructions for controlling a processor of a computing device, comprising program code to configure the processor to:

• configure a first plurality of queues in a memory to each have a first scheduled time, where the first plurality of queues is associated with a first class of service (CoS), the first scheduled time of each of queue of the first plurality of queues is different, and packets to be stored in each respective queue of the first plurality of queues will become available for dequeuing in accordance with the first scheduled time of the respective queue;
• configure a second plurality of queues in the memory to each have a second scheduled time, where the second plurality of queues is associated with a second CoS, the second scheduled time of each of queue of the second plurality of queues is different, and packets to be stored in each respective queue of the second plurality of queues will become available for dequeuing in accordance with the second scheduled time of the respective queue;
• receive a first packet directed to a first recipient device;
• determine that the first packet is associated with the first CoS;
• determine that the first packet is to be enqueued in the first plurality of queues based on the first CoS;
• determine a first rate shaper and a second rate shaper of a plurality of rate shapers to apply to the first packet;
• compute a first future time for transmission of the first packet via a network interface to produce a first flow rate of the first rate shaper;
• compute a second future time for transmission of the first packet via the network interface to produce a second flow rate of the second rate shaper;
• determine that the first future time is later than the second future time;
• select a first queue of the first plurality of queues into which to enqueue the first packet based on the first queue having a first scheduled time that is closest to the first future time while being equal-to-or-sooner than the first future time;
• enqueue the first packet into the first queue
• dequeue packets from the first plurality of queues and from the second plurality of queues for transmission over the network, where the first packet is dequeued from the first queue at or after the first schedule time of the first queue;
• transmit the first packet to the first device via the network after the first packet is dequeued;
• configure a third plurality of queues to each have a third scheduled time, where the third plurality of queues is associated with the first CoS, the third scheduled time of each of queue of the third plurality of queues is different, and packets stored in each respective queue of the third plurality of queues become available for dequeuing at the third scheduled time of the respective queue;
• configure a fourth plurality of queues to each have a fourth scheduled time, where the fourth plurality of queues is associated with the second CoS, the fourth scheduled time of each of queue of the fourth plurality of queues is different, and packets stored in each respective queue of the fourth plurality of queues become available for dequeuing at the fourth scheduled time of the respective queue;
• impose a first aggregate rate to packets dequeued from the first plurality of queues and the second plurality of queues prior to transmitting those packets over the network to a first plurality of devices;
• impose a second aggregate rate to packets dequeued from the third plurality of queues and the fourth plurality of queues prior to transmitting those packets over the network to a second plurality of devices;
• and
• determine whether the first device is of the first plurality of devices or of the second plurality of devices, wherein the enqueuing of the first packet to the first queue of the first plurality of queues is further based on the first device being of the first plurality of devices.