Quality of service packet scheduler design

• US 9,560,551 B2
• Filed: 08/28/2013
• Issued: 01/31/2017
• Est. Priority Date: 07/13/2009
• Status: Active Grant

• Current Assignee: ViaSat Incorporated
• Original Assignee: ViaSat Incorporated
• Inventors: Agarwal, Anil
• Primary Examiner(s): Weidner, Timothy J
• Application Number:
  US14/012,135
• Publication Number:
  US 20130343194A1
• Time in Patent Office: 1,252 Days
• US Class Current: 1/1
• CPC Class Codes: H04B 7/185 Space-based or airborne stations; Stations for satellite systemsH04B7/204 takes precedence
• CPC Class Codes: H04L 47/564 Attaching a deadline to packets, e.g. earliest due date first
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04W 28/10 Flow control between communication endpoints
• CPC Class Codes: H04W 28/14 using intermediate storage

Abstract

Systems, methods, devices, and processors are described for quality of service (QoS) packet scheduling in satellite communications systems. A packet received at the QoS packet scheduler may be assigned a virtual departure time utilizing novel self-clocked fair queuing techniques. The virtual departure time for a packet assigned to a queue may depend on a different weight assigned to the queues. Queues may be treated as low latency queues in some cases and may be provided with committed information rates in other cases. Low latency queues may be assigned weights equal to infinity, or the reciprocal of the weight equal to zero. Queues with committed information rates may assign different weights to packets depending on whether the rate that packets are received exceeds the committed information rate. Packets may then be scheduled based on their virtual departure time order.

Claims

1. A method of self-clocked fair queuing with low latency in a satellite communication system, the method comprising:

receiving a plurality of packets;

assigning each of the plurality of packets to one of a plurality of queues, wherein a first subset of packets from the plurality of packets is assigned to a low latency queue from the plurality of queues;

assigning virtual departure times to the plurality of packets based on weights of respective queues to which the plurality of packets are assigned, wherein one or more of the packets from the first subset of packets is assigned a virtual departure time equal to a virtual departure time of a previous packet in the low latency queue;

ordering the plurality of packets for transmission from the plurality of queues based on the virtual departure times assigned to the plurality of packets; and

transmitting the plurality of packets based on the ordering.

2. The method of claim 1, wherein ordering the plurality of packets for transmission comprises:

scheduling the one or more packets for transmission before a packet from another queue of the plurality of queues that is assigned the same virtual departure time.

3. The method of claim 1, wherein assigning the virtual departure times comprises:

assigning virtual departure times to a packet from the first subset equal to a virtual departure time of a last scheduled packet from another queue from the plurality of queues.

4. The method of claim 1, further comprising:

assigning a weight to the low latency queue such that a reciprocal of the weight of the low latency queue equals substantially zero.

5. The method of claim 4, further comprising:

assigning a weight to a second queue from the plurality of queues such that the reciprocal of the weight of the second queue is greater than zero; and

assigning one or more packets from a second subset of packets from the plurality of packets to the second queue from the plurality of queues.

6. The method of claim 5, further comprising:

assigning a weight to a third queue such that the weight of the third queue is at least two orders of magnitude larger than the weight assigned the second queue.

7. The method of claim 5, wherein the weight assigned to at least one of the queues depends on a type of traffic of the packets received by the respective queue.

8. The method of claim 5, wherein the weight assigned to at least one of the queues is changed to reflect the priority of the first subset of packets.

9. The method of claim 5, wherein the weight assigned to at least one of the queues depends on at least a source or destination of the packets.

10. A self-clocked fair queuing device with low latency in a satellite communication system, the device comprising:

a sorter module configured to;

receive a plurality of packets from a plurality of terminals in the satellite communication system; and

assign each of the plurality of packets to one of a plurality of queues, wherein a first subset of packets from the plurality of packets is assigned to a low latency queue of the plurality of queues; and

a virtual departure time assigner module configured to;

assign virtual departure times to the plurality of packets based on weights of respective queues to which the plurality of packets are assigned, wherein one or more of the packets from the first subset of packets is assigned a virtual departure time equal to a virtual departure time of a previous packet in the low latency queue; and

an ordering module configured to order the plurality of packets for transmission from the plurality of queues based on the virtual departure times assigned to the plurality of packets.

11. The device of claim 10, wherein the virtual departure time assigner module is further configured to:

assign a weight to the low latency queue such that a reciprocal of the weight of the low latency queue equals substantially zero.

12. The device of claim 11, wherein the virtual departure time assigner module is further configured to:

assign a weight to a second queue from the plurality of queues such that the reciprocal of the weight of the second queue is greater than zero;

assign one or more the packets from a second subset of packets from the plurality of packets to the second queue from the plurality of queues.

13. The device of claim 10, wherein the ordering module is further configured to order for transmission the one or more packets before a packet from another queue of the plurality of queues that is assigned the same virtual departure time.

14. The device of claim 10, wherein the virtual departure time assigner module is further configured to:

assign virtual departure times to a packet from the first subset equal to a virtual departure time of a last scheduled packet from another queue from the plurality of queues.

15. The device of claim 12, wherein the virtual departure time assigner module is further configured to:

assign a weight to a third queue such that the weight of the third queue is at least two orders of magnitude larger than the weight assigned the second queue.

16. The device of claim 12, wherein the weight assigned to at least one of the queues depends on a type of traffic of the packets received by the respective queue.

17. A self-clocked fair queuing device with low latency in a satellite communication system, the device comprising

a means for receiving a plurality of packets;

a means for assigning each of the plurality of packets to one of a plurality of queues, wherein a first subset of packets from the plurality of packets is assigned to a low latency queue from the plurality of queues;

a means for assigning virtual departure times to the plurality of packets based on weights of respective queues to which the plurality of packets are assigned, wherein one or more of the packets from the first subset of packets is assigned a virtual departure time equal to a virtual departure time of a previous packet in the low latency queue;

a means for ordering the plurality of packets for transmission from the plurality of queues based on the virtual departure times assigned to the plurality of packets; and

a means for transmitting the plurality of packets based on the ordering.

18. The device of claim 17, further comprising:

a means for assigning a weight to the low latency queue such that a reciprocal of the weight of the low latency queue equals substantially zero.

19. The device of claim 18, further comprising:

a means for assigning a weight to a second queue from the plurality of queues such that the reciprocal of the weight of the second queue is greater than zero;

a means for assigning one or more packets from a second subset of packets from the plurality of packets to the second queue from the plurality of queues.

20. The device of claim 17, wherein:

the means for transmitting the plurality of packets transmits the one or more packets before a packet from another queue of the plurality of queues that is assigned the same virtual departure time.

21. The device of claim 19, further comprising:

a means for assigning a weight to a third queue such that the weight of the third queue is at least two orders of magnitude larger than the weight assigned the second queue.

22. The device of claim 17, further comprising:

a means for assigning virtual departure times to a packet from the first subset equal to a virtual departure time of a last scheduled packet from another queue from the plurality of queues.

23. The device of claim 19, wherein the weight assigned to at least one of the queues depends on a type of traffic of the packets received by the respective queue.