Adaptive coding and modulation using linked list data structures

• US 8,072,873 B2
• Filed: 01/20/2010
• Issued: 12/06/2011
• Est. Priority Date: 10/28/2005
• Status: Active Grant

• Current Assignee: ViaSat Incorporated
• Original Assignee: ViaSat Incorporated
• Inventors: Thesling, William H.
• Primary Examiner(s): Corsaro, Nick
• Assistant Examiner(s): PATEL, MAHENDRA R
• Application Number:
  US12/690,572
• Publication Number:
  US 20100118768A1
• Time in Patent Office: 685 Days
• Field of Search: 463/16, 463/25, 463/42, 370/205, 370/483, 370/533, 219/121, 273/461, 705/26, 455/400, 455/438, 455/445, 455/528
• US Class Current: 370/205
• CPC Class Codes: H04B 7/18543 for adaptation of transmission parameters, e.g. power control for detecting or preventing errors in the information received H04L1/00
• CPC Class Codes: H04B 7/18582 Arrangements for data linking, i.e. for data framing, for error recovery, for multiple access
• CPC Class Codes: H04L 1/0003 by switching between different modulation schemes
• CPC Class Codes: H04L 1/0007 by modifying the frame length
• CPC Class Codes: H04L 1/0009 by adapting the channel coding H04L1/1812 takes precedence
• CPC Class Codes: H04L 1/0016 involving special memory structures, e.g. look-up tables
• CPC Class Codes: H04L 1/0021 in which the algorithm uses adaptive thresholds
• CPC Class Codes: H04L 1/0026 Transmission of channel quality indication
• CPC Class Codes: H04L 1/0083 Formatting with frames or packets; Protocol or part of protocol for error control
• CPC Class Codes: H04L 2001/0093 Point-to-multipoint
• CPC Class Codes: H04L 27/0008 arrangements for allowing a transmitter or receiver to use more than one type of modulation negotiating modulation type for two-way transmission paths H04L5/1453
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 5/023 Multiplexing of multicarrier modulation signals multicarrier modulation H04L27/2601
• CPC Class Codes: H04W 28/10 Flow control between communication endpoints
• CPC Class Codes: H04W 72/1221 based on age of data to be sent
• CPC Class Codes: H04W 72/542 using measured or perceived quality
• CPC Class Codes: H04W 80/00 Wireless network protocols or protocol adaptations to wireless operation
• CPC Class Codes: H04W 84/06 Airborne or Satellite Networks space-based or airborne stations H04B7/185

Abstract

A process is described to build physical layer frames with a modcode adapted to the signal quality of a destination terminal. Data packets assigned to the same modcode may be sent in the same frame, although packets associated with higher modcodes may be used to complete a frame before switching to the applicable higher modcode for construction of subsequent frames. After an interval, the order of progression is restarted with an out of order packet above a threshold age. Flow control filtering mechanisms and a variable reliability margin may be used to adapt dynamically to the current data traffic conditions.

Claims

1. A method of implementing adaptive coding and modulation, the method comprising:

identifying a modulation and coding format assigned to each of a plurality of different signal quality ranges;

identifying, for each packet of a plurality of packets, a signal quality representative of a communication link to which the respective packet is destined;

generating a linked list comprising a plurality of elements each associated with respective ones of the plurality of packets;

iterating through the linked list to identify a first subset of elements from the plurality of elements, the first subset of elements each associated with communication links in a first signal quality range of the plurality of ranges; and

transmitting a first subset of the plurality of packets, associated with the first subset of elements, in an order substantially corresponding to a sequence in which their associated elements are identified, the transmission according to a first modulation and coding format assigned to the first signal quality range.

2. The method of claim 1, wherein,

the elements of the linked list are organized in chronological order from an element associated with an earliest received packet to an element associated with a most recent packet received.

3. The method of claim 1, further comprising:

modifying an order of elements of the linked list responsive to a quality of service level associated with one or more of the plurality of elements.

4. The method of claim 1, further comprising:

removing the identified elements, wherein the linked list is substantially ordered chronologically from older packets to newer packets.

5. The method of claim 1, further comprising:

performing a second iteration through the linked list to identify a second subset of elements from the plurality of elements, the second subset associated with communication links in a second signal quality range of better quality than the first signal quality range; and

transmitting a second subset of the plurality of packets, associated with the second subset of elements, in an order corresponding to a sequence in which the elements associated with communication links in the second signal quality range were identified.

6. The method of claim 5, wherein the first signal quality range is adjacent to the second signal quality range.

7. The method of claim 5, wherein at least one packet from the second subset is transmitted according to the first modulation and coding format and at least one packet from the second subset is transmitted according to a second modulation and coding format of higher order than the first modulation and coding format.

8. The method of claim 5, wherein at least one packet from the first subset and at least one packet from the second subset are transmitted in a single frame according to the first modulation and coding format.

9. The method of claim 1, further comprising:

blocking additional packets from being associated with elements in the linked list when a latency measurement associated with the transmitting step exceeds a threshold.

10. The method of claim 9, further comprising:

allowing additional packets associated with a threshold quality of service level to be associated with elements in the linked list when the latency measurement exceeds the threshold.

11. The method of claim 1, further comprising:

changing at least one of the plurality of signal quality ranges to increase a reliability margin when a latency measurement decreases.

12. The method of claim 1, further comprising:

receiving the plurality of packets; and

changing at least one of the plurality of signal quality ranges to decrease a reliability margin when a delay between the receiving step and the transmitting step increases past a threshold.

13. The method of claim 1, wherein the signal quality comprises at least one of a signal to noise ratio, an estimated signal to noise ratio, a bit error rate, a receive power level, and another communication link quality indicator.

14. The method of claim 1, wherein the transmitting step is performed according to the digital video broadcasting—

satellite—

second generation standard.

15. A device for implementing adaptive coding and modulation, the device comprising:

a memory storing a linked list including a plurality of elements, each element associated with one of a plurality of packets, wherein each of the plurality of packets is further associated with a signal quality representative of a communication link to which the respective packet is destined; and

a processor, communicatively coupled with the memory, and configured to;

identify a modulation and coding format assigned to each of a plurality of signal quality ranges; and

iterate through the linked list to identify a first subset of elements from the plurality of elements, the first subset of elements each associated with communication links in a first signal quality range of the plurality of ranges; and

a transmitter, communicatively coupled with the processor, and configured to transmit a first subset of the plurality of packets, associated with the first subset of elements, and according to a first modulation and coding format assigned to the first signal quality range.

16. The device of claim 15, wherein the transmitter is further configured to transmit the first subset of the plurality of packets in an order substantially corresponding to a sequence in which their associated elements are identified.

17. The device of claim 15, wherein the processor is further configured to:

interrupt, upon expiration of a timer, the iteration before it has progressed through each element of the linked list; and

identify an out of order packet exceeding a threshold age and not included in the subset.

18. The device of claim 17, wherein the processor is further configured to change a period of the timer responsive to a latency measurement associated with the transmission of packets from the device.

19. The device of claim 15, wherein the processor is further configured to:

identify when a packet associated with the plurality of elements exceeds a threshold age;

block additional packets from being associated with elements and inserted in the linked list when the selected packet exceeds a threshold age; and

allow packets associated with a threshold quality of service or class of service to be associated with elements and inserted in the linked list when the selected packet exceeds a threshold age.

20. The device of claim 15, the elements of the linked list are organized in substantially chronological order from an element associated with an earliest received packet to an element associated with a most recent packet received.

21. The device of claim 15, wherein the processor is further configured to modify an order in which elements are placed into the linked list responsive to a quality of service level associated with one or more of the plurality of elements.

22. The method of claim 15, wherein the processor is further configured to remove the identified elements substantially upon identification.

23. The device of claim 15, wherein,

the processor is further configured to perform a second iteration through the linked list to identify a second subset of elements from the plurality of elements, the second subset associated with communication links in a second signal quality range of better quality than the first signal quality range;

and

the transmitter is further configured to transmit a second subset of the plurality of packets, associated with the second subset of elements, in an order corresponding to a sequence in which the elements associated with communication links in a second signal quality range were identified.

24. The device of claim 15, wherein,

the processor is further configured to modify at least one of the plurality of signal quality ranges to modify a reliability margin when a traffic load at the device exceeds a threshold.

25. A device for implementing adaptive coding and modulation, the device comprising:

means for identifying a modulation and coding format assigned to each of a plurality of different signal quality ranges;

means for identifying, for each packet of a plurality of packets, a signal quality representative of a communication link to which the respective packet is destined;

means for generating a linked list comprising a plurality of elements each associated with respective ones of the plurality of packets;

means for iterating through the linked list to identify a first subset of elements from the plurality of elements, the first subset of elements each associated with communication links in a first signal quality range of the plurality of ranges; and

means for transmitting a first subset of the plurality of packets, associated with the first subset of elements, in an order substantially corresponding to a sequence in which their associated elements are identified, the transmission according to a first modulation and coding format assigned to the first signal quality range.

26. A system for implementing adaptive coding and modulation, the system comprising:

a gateway configured to;

identify a modulation and coding format assigned to each of a plurality of different signal quality ranges;

identify, for each packet of a plurality of packets, a signal quality representative of a communication link to which the respective packet is destined;

generate a linked list comprising a plurality of elements each associated with respective ones of the plurality of packets;

iterate through the linked list to identify a first subset of elements from the plurality of elements, the first subset of elements each associated with communication links in a first signal quality range of the plurality of ranges; and

transmit a first subset of the plurality of packets, associated with the first subset of elements, in an order substantially corresponding to a sequence in which their associated elements are identified, the transmission according to a first modulation and coding format assigned to the first signal quality range; and

a plurality of terminals, each in communication with the gateway via satellite, and configured to received the transmitted first subset of the plurality of packets.

27. The system of claim 26, wherein the gateway is further configured to modify an order in which elements are placed into the linked list responsive to a quality of service level associated with one or more of the elements to be placed in the linked list.

28. The system of claim 26, wherein the gateway is further configured to remove the identified elements, wherein the linked list is substantially ordered chronologically from older packets to newer packets.