Importance-based FEC-aware error-repair scheduling

• US 9,312,989 B2
• Filed: 07/07/2008
• Issued: 04/12/2016
• Est. Priority Date: 07/07/2008
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Begen, Ali C., Oran, David R.
• Primary Examiner(s): Torres, Joseph D
• Application Number:
  US12/168,772
• Publication Number:
  US 20100005360A1
• Time in Patent Office: 2,836 Days
• Field of Search: 714/748, 714/751
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1443 Transmit or communication errors
• CPC Class Codes: H04L 1/08 by repeating transmission, e.g. Verdan system H04L1/1858 and H04L1/189 take precedence
• CPC Class Codes: H04L 1/16 in which the return channel carries supervisory signals, e.g. repetition request signals
• CPC Class Codes: H04L 1/1614 using bitmaps
• CPC Class Codes: H04L 1/1621 Group acknowledgement, i.e. the acknowledgement message defining a range of identifiers, e.g. of sequence numbers
• CPC Class Codes: H04L 1/1628 List acknowledgements, i.e. the acknowledgement message consisting of a list of identifiers, e.g. of sequence numbers H04L1/1614 takes precedence
• CPC Class Codes: H04L 1/1819 with retransmission of additional or different redundancy
• CPC Class Codes: H04L 1/1845 Combining techniques, e.g. code combining
• CPC Class Codes: H04L 1/1867 Arrangements specially adapted for the transmitter end
• CPC Class Codes: H04L 2001/0092 Error control systems characterised by the topology of the transmission link
• CPC Class Codes: H04L 2001/0093 Point-to-multipoint

Abstract

A method is provided in one example and includes receiving a loss report usable to determine a plurality of missing packets at a first receiver; determining one or more retransmission packets for retransmission based on a forward error correction (FEC) scheme and the plurality of missing packets at the first receiver, where the one or more retransmission packets are determined to allow the first receiver to recover at least one of the missing source packets in the one or more source packets using the FEC scheme; and sending the one or more retransmission packets to the first receiver, the one or more retransmission packets allowing the first receiver to recover at least one of the missing source packets in the one or more source packets that it is missing using the forward error correction scheme after receiving the one or more retransmission packets.

Claims

1. A method comprising:

receiving a loss report, the loss report usable to determine a plurality of missing packets in a transmission received at a first receiver, the missing packets including one or more source packets, wherein the packets in the transmission are grouped into individual blocks and each individual block is an array of packets that includes a plurality of columns and a plurality of rows, whereby a representation of single packet resides at an intersection of each column and each row of the array, and wherein a row FEC packet is assigned to each row and a column FEC packet is assigned to each column in each of the individual blocks, wherein a block loss report for a specific block is sent from the first receiver before a complete FEC scheme for the specific block is received by the first receiver;

determining one or more retransmission packets for retransmission based on a 2-D parity FEC scheme and the plurality of missing packets at the first receiver, and wherein at least one of the plurality of missing packets is not sent, such that the number of retransmission packets is less than the plurality of missing packets determined from the loss report;

determining a relative importance for the one or more retransmission packets; and

sending the one or more retransmission packets to the first receiver, wherein a retransmission packet considered to have a high relative importance is sent before other retransmission packets are sent, the one or more retransmission packets allowing the first receiver to recover at least one of the missing source packets in the one or more source packets that it is missing using the forward error correction scheme after receiving the one or more retransmission packets, wherein a combination of one or more of the one or more retransmission packets, the row FEC packet assigned to each row, and the column FEC packet assigned to each column allows for recover of each of the plurality of missing packets.

2. The method of claim 1, wherein determining the one or more retransmission packets comprises determining which of FEC or source packets need to be retransmitted to allow the first receiver to recover all the missing source packets based on the FEC scheme used, wherein the FEC or source packets determined for retransmission are a minimum number of retransmission packets that can be sent to allow all of the missing source packets to be recovered using the FEC scheme.

3. The method of claim 2, wherein determining the one or more retransmission packets comprises:

determining a retransmission FEC packet that can be used to recover a missing source packet; and

sending the retransmission FEC packet instead of the missing source packet.

4. The method of claim 1, further comprising:

receiving a one or more additional loss reports that are used to determine one or more additional plurality of missing packets at one or more additional receivers, the one or more additional loss reports usable to determine a second one or more FEC packets and/or one or more source packets missing at the one or more additional receivers, wherein a plurality of the one or more source packets missing at the one or more additional receivers are different than the plurality of missing packets at the first receiver;

determining one or more retransmission packets for retransmission that can be sent to the first receiver and the one or more additional receivers based on the FEC scheme, source packets, and FEC packets received at the first receiver and the one or more additional receivers to allow the first receiver to recover at least a portion of the missing one or more source packets at the first receiver and the one or more additional receivers to recover at least a portion of the missing one or more source packets at the one or more additional receivers; and

sending the one or more retransmission packets to the first receiver and the one or more additional receivers.

5. The method of claim 4, wherein the one or more retransmission packets are sent via multicast to the first receiver and the one or more additional receivers.

6. The method of claim 1, wherein determining the relative importance comprises:

determining a missing packet that carries a more important payload compared to other missing packets; and

retransmitting the most important missing packet before other missing packets.

13. The method of claim 1, wherein a column FEC packet is assigned to each column in each of the individual blocks and a row FEC packet is assigned to each row in each of the individual blocks.

14. The method of claim 1, wherein the FEC scheme uses one or more of the FEC packet assigned to each row in each of the individual blocks.

7. An apparatus comprising:

one or more processors; and

logic encoded in one or more tangible media for execution by the one or more processors and when executed operable to;

receive a loss report, the loss report usable to determine a plurality of missing packets in a transmission received at a first receiver, the missing packets including one or more source packets, wherein the packets in the transmission are grouped into individual blocks and each individual block is an array of packets that includes a plurality of columns and a plurality of rows, whereby a representation of a single packet resides at an intersection of each column and each row of the array, and wherein a row FEC packet is assigned to each row and a column FEC packet is assigned to each column in each of the individual blocks, wherein a block loss report for a specific block is sent from the first receiver before a complete FEC scheme for the specific block is received by the first receiver;

determine one or more retransmission packets for retransmission based on a 1-D or 2-D parity FEC scheme and the plurality of missing packets at the first receiver, and wherein the number of retransmission packets is less than the plurality of missing packets determined from the loss report;

determine a relative importance for the one or more retransmission packets; and

send the one or more retransmission packets to the first receiver, wherein a retransmission packet considered to have a high relative importance is sent before other retransmission packets are sent, the one or more retransmission packets allowing the first receiver to recover at least one of the missing source packets in the one or more source packets that it is missing using the forward error correction scheme after receiving the one or more retransmission packets, wherein a combination of one or more of the one or more retransmission packets, the row FEC packet assigned to each row, and the column FEC packet assigned to each column allows for recover of each of the plurality of missing packets.

8. The apparatus of claim 7, wherein logic operable to determine the one or more retransmission packets comprises logic operable to determine which of FEC or source packets need to be retransmitted to allow the first receiver to recover all the missing source packets based on the FEC scheme used, wherein the FEC or source packets determined for retransmission are a minimum number of retransmission packets that can be sent to allow all of the missing source packets to be recovered using the FEC scheme.

9. The apparatus of claim 7, wherein the logic when executed is further operable to:

receive a one or more additional loss reports that are used to determine one or more additional plurality of missing packets at one or more additional receivers, the one or more additional loss reports usable to determine a second one or more FEC packets and/or one or more source packets missing at the one or more additional receivers;

determine one or more retransmission packets for retransmission that can be sent to the first receiver and the one or more additional receivers based on the FEC scheme, source packets, and FEC packets received at the first receiver and the one or more additional receivers to allow the first receiver to recover at least a portion of the missing one or more source packets at the first receiver and the one or more additional receivers to recover at least a portion of the missing one or more source packets at the one or more additional receivers; and

send the one or more retransmission packets to the first receiver and the one or more additional receivers.

10. The apparatus of claim 9, wherein the one or more retransmission packets are sent via multicast to the first receiver and the one or more additional receivers.

11. The apparatus of claim 7, wherein logic operable to determine the relative importance comprises logic operable to:

determining a missing packet that carries a more important payload compared to other missing packets; and

retransmitting the most important missing packet before other missing packets.

12. A method comprising:

receiving a first loss report that defines a plurality of missing packets in a transmission received at a first receiver, the first loss report usable to determine one or more source packets missing at the first receiver, wherein the packets in the transmission are grouped into individual blocks and each individual block is an array of packets that includes a plurality of columns and a plurality of rows, whereby a representation of a single packet resides at an intersection of each column and each row of the array, and wherein a row FEC packet is assigned to each row and a column FEC packet is assigned to each column in each of the individual blocks, wherein a block loss report for a specific block is sent from the first receiver before a complete FEC scheme for the specific block is received by the first receiver;

receiving a second loss report that defines a plurality of missing packets at a second receiver, the second loss report usable to determine one or more FEC packets or one or more source packets missing at the second receiver or one or more FEC packets and one or more source packets missing at the second receiver;

determining one or more retransmission packets for retransmission based on a FEC scheme and the plurality of missing packets defined in the first loss report and the second loss report, wherein the one or more retransmission packets are sent to both the first receiver and the second receiver, and wherein the number of retransmission packets is less than the plurality of missing packets determined from the first loss report and the second loss report; and

determining a relative importance for the one or more retransmission packets;

sending the one or more retransmission packets to the first receiver and the second receiver, wherein a retransmission packet considered to have a high relative importance is sent before other retransmission packets are sent, the one or more retransmission packets allowing the first receiver to recover at least one of the missing source packets that the first receiver is missing after receiving the one or more retransmission packets and allowing the second receiver to recover at least one of the missing source packets that the second receiver is missing after receiving one or more retransmission packets, wherein a combination of one or more of the one or more retransmission packets, the row FEC packet assigned to each row, and the column FEC packet assigned to each column allows for recover of each of the plurality of missing packets.