Back to results
US 2018/0123983 A1Published application
Programmable Broadband Gateway Hierarchical Output Queueing
AssigneeCenturyLink Intellectual Property LLC
InventorChristopher W. Gunner
Life of this patent
Estimating the term…
Abstract
An improved method of hierarchical output queuing of packets for a network scheduler of a network gateway that determines delays needed to conform to applicable rate shaping, and enqueues the packets based on the delay. Queues are associated with different classes of service (CoS), and within each class, each queue has a different scheduled time upon which it becomes available for dequeuing. A single set of CoS queues can support a large number of devices, improving the efficiency of software-based queuing by reducing the number of queues and simplifying queue polling.
Claims20
A method of scheduling packets for transmission over a network via a gateway device, comprising:
- configuring a first plurality of queues 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 stored in each respective queue of the first plurality of queues become available for dequeuing at the first scheduled time of the respective queue;
- configuring a second plurality of queues 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 stored in each respective queue of the second plurality of queues become available for dequeuing at the second scheduled time of the respective queue;
- receiving a first packet at the gateway device, directed to a first device;
- determining, by the gateway device, that the first packet is associated with the first CoS;
- determining, by the gateway device, that the first packet is to be enqueued in the first plurality of queues based on the first CoS;
- determining, by the gateway device, a first rate shaper and a second rate shaper of a plurality of rate shapers to apply to the first packet;
- computing, by the gateway device, a first future time for transmission of the first packet over the network to produce a first flow rate of the first rate shaper;
- computing, by the gateway device, a second future time for transmission of the first packet over the network to produce a second flow rate of the second rate shaper;
- determining, by the gateway device, that the first future time is later than the second future time;
- selecting, by the gateway device, a first queue of the first plurality of queues into which to enqueue the first packet based 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;
- enqueuing the first packet into the first queue;
- dequeuing 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 scheduled time of the first queue;
- and
- transmitting the first packet to the first device via the network after the first packet is dequeued.
11 more elements
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 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;
- and enqueue the first packet into the first queue.
12 more elements
Dependencies are inferred from the claim text.