Adaptive coding and modulation using linked list data structures

• US 7,675,842 B2
• Filed: 10/30/2006
• Issued: 03/09/2010
• Est. Priority Date: 10/28/2005
• Status: Active Grant

• Current Assignee: ViaSat Incorporated
• Original Assignee: ViaSat Incorporated
• Inventors: Thesling, William H.
• Primary Examiner(s): Harper; Vincent P
• Assistant Examiner(s): Patel; Mahendra R
• Application Number:
  US11/554,244
• Publication Number:
  US 20070096788A1
• Time in Patent Office: 1,226 Days
• Field of Search: 370/320, 370/338, 370/328, 370/350, 370/352, 455/438, 455/440, 455/445, 455/466, 455/528, 463/16, 463/25, 219/121, 229/72, 140/88
• 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 using a linked list, the method comprising:

associating a signal quality with each of a plurality of packets, the signal quality comprising a representative signal quality of a communication link to which the respective packet is destined;

assigning a different modcode to each of a plurality of signal quality ranges;

inserting, in a linked list, a plurality of elements each associated with one 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 corresponding to a sequence in which their associated elements are identified, the transmission according to a first modcode assigned to the first signal quality range.

2. The method of claim 1, further comprising:

interrupting, upon expiration of a timer, the iterating step before it has progressed through each element of the linked list to identify an out of order packet exceeding a threshold age and not included in the subset.

3. The method of claim 2, further comprising:

varying the period of the timer based at least in part on a latency measurement.

4. The method of claim 3, wherein the latency measurement comprises a delay associated with the out of order packet.

5. The method of claim 2, wherein,

the elements of the linked list are organized from an element associated with the oldest packet chronologically down to an element associated with a latest packet to be received;

and

the interrupting step comprises identifying the oldest packet.

6. The method of claim 1, wherein the iterating through the list further comprises:

iterating through the list from an element associated with an oldest remaining packet to an element associated with a newest remaining packet; and

removing the identified elements.

7. 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 a second signal quality range were identified.

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

9. The method of claim 7, 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 modcode.

10. The method of claim 1, further comprising:

blocking additional packets from being associated with elements in the linked list based at least in part on a latency measurement.

11. The method of claim 10, further comprising:

allowing packets associated with a threshold quality of service or class of service to be associated with elements in the linked list based at least in part on the latency measurement.

12. The method of claim 1, further comprising:

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

13. The method of claim 1, further comprising:

varying at least one of the plurality of signal quality ranges to decrease a reliability margin when a delay associated with the transmitting step increases.

14. The method of claim 1, wherein the transmitting step further comprises:

fragmenting an internet protocol packet of the plurality of packets into a first fragment and a second fragment, each fragment associated with a second signal quality range;

transmitting the first fragment according to the first modcode; and

transmitting the second fragment according to the second modcode, the second modcode of higher order than the first modcode.

15. The method of claim 1, wherein the adaptive coding and modulation is implemented in accordance with a DVB-S2 standard.

16. 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.

17. A device for implementing adaptive coding and modulation using a linked list, the device comprising:

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

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

assign a different modcode to each of a plurality of signal quality ranges;

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, in an order corresponding to a sequence in which their associated elements are identified, and according to a first modcode assigned to the first signal quality range.

18. The device of claim 17, 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.

19. The device of claim 18, wherein,

the processor is further configured to vary the period of the timer based at least in part on a delay associated with the transmission.

20. The device of claim 18, wherein the threshold age comprises an age of a second oldest remaining packet.

21. The device of claim 18, wherein,

the processor is further configured to block additional packets from being associated with elements and inserted in the linked list when the out of order packet exceeds a second threshold age.

22. The device of claim 21, wherein,

the processor is further configured to allow packets associated with a threshold quality of service or class of service to be associated with elements in the linked list.

23. The device of claim 17, wherein the elements of the linked list are organized from an element associated with the oldest packet chronologically down to an element associated with a latest packet to be received.

24. The device of claim 17, wherein,

the processor is further configured to:

iterate through the list from an element associated with an oldest remaining packet to an element associated with a newest remaining packet; and

remove the identified elements from the linked list.

25. The device of claim 17, 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.

26. The device of claim 25, wherein at least one packet from the second subset is transmitted according to the first modcode and at least one packet from the second subset is transmitted according to a second modcode of higher order than the first modcode.

27. The device of claim 26, 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 modcode.

28. The device of claim 17, wherein,

the processing unit is further configured to modify at least one of the plurality of signal quality ranges to modify a reliability margin when a latency measurement associated with the transmission changes.

29. The device of claim 17, wherein,

the processor is further configured to fragment an internet protocol packet of the plurality of packets into a first fragment and a second fragment, each fragment associated with a second signal quality range;

and

the transmitter is further configured to;

transmit the first fragment according to the first modcode; and

transmit the second fragment according to the second modcode, the second modcode of higher order than the first modcode.

30. A device for implementing adaptive coding and modulation using a linked list by assigning different modcodes for communication links of different signal qualities, the device comprising:

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

means for assigning a different modcode to each of a plurality of signal quality ranges;

means for inserting, into a linked list, a plurality of elements each associated with one of 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 corresponding to a sequence in which their associated elements were identified and according to the first modcode assigned to the first signal quality range.