QUALITY OF SERVICE PACKET SCHEDULER DESIGN

• US 20130343194A1
• Filed: 08/28/2013
• Published: 12/26/2013
• Est. Priority Date: 07/13/2009
• Status: Active Grant

• Current Assignee: ViaSat Incorporated
• Original Assignee: ViaSat Incorporated
• Inventors: Agarwal, Anil
• Granted Patent: US 9,560,551 B2
• Time in Patent Office: Days
• US Class Current: 370/235
• 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 for a satellite communication system, the method comprising:

receiving a plurality of packets;

assigning a first subset of packets from the plurality of packets to a low latency queue from a plurality of queues;

assigning virtual departure times to one or more of the packets from the first subset of packets equal to a virtual departure time of a previous packet in the low latency queue; and

transmitting the one or more packets based on the virtual departure times assigned to the one or more packets.

2. The method of claim 1, further comprising:

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, further comprising:

assigning virtual departure times to one or more packets 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; and

wherein assigning the virtual departure time to the one or more packets from the first subset depends on the weight assigned to the low latency queue.

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;

assigning 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; and

assigning virtual departure times to the one or more packets assigned to the second queue that depend on the weight assigned to the second queue.

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 at least the first weight or the second weight depends on at least a source or a destination of the packets.

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

a sorter module configured to;

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

assign a first subset of packets from the plurality of packets to a low latency queue from a plurality of queues; and

a virtual departure time assigner module configured to;

assign virtual departure times to one or more of the packets from the first subset of packets equal to a virtual departure time of a previous packet in the low latency queue; and

an ordering module configured to order the one or more packets for transmission based on the virtual departure times assigned to the one or more 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; and

wherein assigning the virtual departure time to the one or more packets from the first subset depends on the weight assigned to the low latency queue.

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; and

assign virtual departure times to the one or more packets assigned to the second queue that depend on the weight assigned to the second queue.

13. The device of claim 10, wherein the ordering module configured to order the one or more packets for transmission based on the virtual departure times assigned to the one or more packets comprises ordering 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 one or more packets 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 for a satellite communication system, the device comprising

a means for receiving a plurality of packets;

a means for assigning a first subset of packets from the plurality of packets to a low latency queue from a plurality of queues;

a means for assigning virtual departure times to one or more of the packets from the first subset of packets equal to a virtual departure time of a previous packet in the low latency queue; and

a means for transmitting the one or more packets based on the virtual departure times assigned to the one or more packets.

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; and

wherein assigning the virtual departure time to the one or more packets from the first subset depends on the weight assigned to the low latency queue.

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 the packets from a second subset of packets from the plurality of packets to the second queue from the plurality of queues; and

a means for assigning virtual departure times to the one or more packets assigned to the second queue that depend on the weight assigned to the second queue.

20. The device of claim 17, wherein:

the means for transmitting the one or more packets based on the virtual departure times comprises a means for transmitting 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 one or more packets 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 queue.