Method And Apparatus For Forward Error Correction At The IP Layer With Loss Adaptive Overhead Minimization

Abstract

Computer-implemented systems and methods for Forward Error Correction (FEC) at the IP-Layer with adaptive bandwidth overhead minimization in a packet transmission network, the system including an FEC encoder to process IP packets and generate FEC encoded packets and repair packets, an FEC decoder to receive and process the FEC encoded packets and repair packets, and an FEC controller that includes a set of computer-implemented instructions to carry out functions including configuring an FEC algorithm to control FEC encoding and decoding, packet recovery, and retrieve packet transmission statistics, determining if network bandwidth overhead needs adjustment, controlling tuning parameters, and implementing predictive analysis based at least in part on historic data.

Claims

1. A computer-implemented system for Forward Error Correction (FEC) at the IP-Layer with adaptive bandwidth overhead minimization in a packet transmission network, the system comprising: an FEC encoder to process IP packets and generate FEC encoded packets and repair packets; an FEC decoder to receive and process the FEC encoded packets and repair packets; and an FEC controller that comprises a set of computer-implemented instructions to cause a processor to carry out functions comprising: configuring an FEC algorithm to control FEC encoding and decoding, packet recovery, and retrieve packet transmission statistics; determining if network bandwidth overhead needs adjustment; controlling tuning parameters; and implementing predictive analysis based at least in part on historic data.

2. The computer-implemented system of claim 1 wherein the FEC encoder adds meta-information to the FEC encoded packets.

3. The computer-implemented system of claim 1 wherein the FEC encoder uses an encoding context provided by the FEC controller.

4. The computer-implemented system of claim 1 wherein the FEC decoder uses a decoding context provided by the FEC controller.

5. The computer-implemented system of claim 1 wherein the FEC encoder maintains an encoding state for processing the IP-packets.

6. The computer-implemented system of claim 1 wherein the FEC decoder maintains a decoding state for processing the IP-packets.

7. The computer-implemented system of claim 1 wherein the FEC controller controls tuning parameters that further comprise: (i) the number of original IP packets; (ii) the number of generated repair packets; and (iii) the on/off state of the FEC algorithm.

8. The computer-implemented system of claim 1 wherein the FEC encoder generates the FEC encoded packets to include an FEC block of predetermined length.

9. The computer-implemented system of claim 8 wherein the FEC encoder generates a predetermined number of repair packets per FEC block.

10. The computer-implemented system of claim 1 wherein the FEC encoder sends an FEC block length and the number of repair packets per FEC block via an FEC trailer.

11. The computer-implemented system of claim 1 wherein the FEC encoder sends an FEC block length and the number of repair packets per FEC block via a port in a UDP header.

12. A computer-implemented system for Forward Error Correction (FEC) at the IP-Layer, the system comprising: an FEC encoder to process IP packets and generate FEC repair packets and FEC encoded packets that further comprise an FEC trailer; an FEC decoder to receive and process the FEC encoded packets and FEC repair packets; and an FEC controller that controls an FEC algorithm for the FEC encoder and FEC decoder.

13. The computer-implemented system for FEC at the IP-Layer of claim 12 wherein the FEC trailer further comprises: a MAGIC #that indicates whether a particular packet is an FEC encoded packet or an FEC repair packet; a block ID that indicates a block of packets the particular packet belongs to; and a sequence #that indicates a position within the block of packet that the particular packet belongs to.

14. The computer-implemented system for FEC at the IP-Layer of claim 12 wherein the FEC repair packet further comprises: a UDP header comprising a source-port field.

15. The computer-implemented system for FEC at the IP-Layer of claim 12 wherein the FEC trailer further comprises: a block ID that indicates a block of packets the particular packet belongs to; and a sequence #that indicates a position within the block of packet that the particular packet belongs to.

16. The computer-implemented system for FEC at the IP-Layer of claim 15 wherein the FEC repair packet further comprises one or more tuning parameters in the FEC trailer.

17. A computer-implemented method for Forward Error Correction (FEC) at the IP-Layer with adaptive bandwidth overhead minimization in a packet transmission network, the method comprising: processing IP packets with an FEC encoder to generate FEC encoded packets and FEC repair packets; receiving at an FEC decoder the FEC encoded packets and FEC repair packets; and controlling with an FEC controller that comprises a set of computer-implemented instructions to cause a processor to carry out functions comprising: configuring an FEC algorithm to control FEC encoding and decoding, packet recovery, and retrieve packet transmission statistics; determining if network bandwidth overhead needs adjustment; controlling tuning parameters; and implementing predictive analysis based at least in part on historic data.

18. The computer-implemented method of claim 17 further comprising adding meta-information to the FEC encoded packets with the FEC encoder.

19. The computer-implemented method of claim 17 further comprising providing an encoding context from the FEC controller to the FEC encoder.

20. The computer-implemented method of claim 17 further comprising providing a decoding context from the FEC controller to the FEC decoder.

21. The computer-implemented method of claim 17 further comprising maintaining an encoding state for processing the IP-packets by the FEC encoder.

22. The computer-implemented method of claim 17 further comprising maintaining a decoding state for processing the IP-packets by the FEC decoder.

22. The computer-implemented method of claim 17 wherein the FEC controller controls tuning parameters that further comprise: (i) the number of original IP packets; (ii) the number of generated repair packets; and (iii) the on/off state of the FEC algorithm.

23. The computer-implemented method of claim 17 further comprising generating, with the FEC encoder, the FEC encoded packets to include an FEC block of predetermined length.

24. The computer-implemented method of claim 23 further comprising generating, with the FEC encoder, a predetermined number of repair packets per FEC block.

25. The computer-implemented method of claim 17 further comprising sending, with the FEC encoder, an FEC block length and the number of repair packets per FEC block via an FEC trailer.

26. The computer-implemented method of claim 17 further comprising sending, with the FEC encoder, an FEC block length and the number of repair packets per FEC block via a port in a UDP header.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0019] FIG. 1 is a schematic illustration of components of systems for FEC at the IP layer in accordance with disclosed embodiments.

[0020] FIG. 2 illustrates FEC packet encoding which is agnostic to any specific FEC algorithm in accordance with disclosed embodiments.

[0021] FIG. 3 illustrates another FEC packet encoding system that is agnostic to any specific FEC algorithm in accordance with disclosed embodiments.

[0022] While the disclosure is susceptible to various modifications and alternative forms, specific embodiments have been shown by way of example in the drawings and will be described in detail herein. However, it should be understood that the disclosure is not intended to be limited to the particular forms disclosed. Rather, the intention is to cover all modifications, equivalents and alternatives falling within the spirit and scope of the invention as defined by the appended claims.

DETAILED DESCRIPTION

[0023] The general principles of FEC are known and many types of FEC algorithms exist. Also, FEC has been used over lossy mediums in a variety of applications. The usual deployment of FEC is at the application layer and is typically end-to-end.

[0024] For example, the Internet Engineering Task Force (IETF) has published requests for comments (RFCs) relating to FEC at the IP-layer such as RFC-5052, RFC-5445, RFC-6363, and RFC-8680. Of these, RFC-8680 aims to minimize bandwidth overhead due to FEC by using a sliding-window based FEC codes. Further, RFC-5052 and RFC-5445 are for applications used for sending files (i.e., content) end-to-end. None of the aforementioned proposals are adaptive given their use-case and they aren't relevant for packet forwarding systems and methods.

[0025] Likewise, RFC-6363 defines FEC for use above the transport layer and is, thus, end-to-end, however, it does not provide for adaptiveness. RFC-8680 is an update to RFC-6363 to enable use of sliding-window FEC codes. However, it, too, does not describe any method for adaptiveness in the face of varying packet loss. Other drawbacks and issues also exist with present systems and methods. In contrast, the presently disclosed embodiments provide bandwidth overhead reduction for both block FEC codes and sliding-window FEC codes.

[0026] FIG. 1 is a schematic illustration of components of systems 100 for FEC at the IP layer in accordance with disclosed embodiments. As illustrated, at the sender side an FEC encoder 102 component processes the original packets 104 for FEC to generate FEC encoded packets 104, adds any meta-information as desired at the receiver side to process the packets 104, and generates the required number of repair packets 106. The input original packets 104 to the FEC encoder 102 are IP-packets.

[0027] As illustrated schematically, an FEC encoder 102 uses encoding context 110 to perform an FEC operation on the sending side. The encoding context 110 contains the FEC algorithm 114 to use as well as any parameters needed for the FEC.

[0028] Embodiments of FEC encoder 102 may require the packet data in order to generate the repair codes. As also indicated, FEC encoder 102 also maintains the encoding state for processing (e.g., block-id to use, next sequence number to use, timestamps, etc.) and also maintains statistics related to encoding operation as indicated at 112.

[0029] As illustrated schematically, an FEC decoder 108 on the receiver side processes the received FEC processed packet 104, which could be original packet 104 with FEC meta-information (e.g., FEC encoded packet 104) or a FEC repair packet 106. If any packet loss is detected, the FEC decoder 108 invokes the FEC algorithm 114 to recover the packet. As will be understood by those of ordinary skill in the art, the recovery may or may not succeed. Again, the inputs to the FEC decoder 108 are IP-packets.

[0030] Embodiments of FEC Decoder 108 use decoding context 116 to perform FEC recovery operations at the receiving side. Embodiments of decoding context 116 contain the FEC algorithm 114 to use as well as any other parameters needed for the FEC.

[0031] Embodiments of the FEC decoder 108 may require packet data in order to perform recovery of lost packets. As also indicated, FEC decoder 108 also maintains state to perform the decode processing (e.g., current block-id, re-sequence queues, timestamps etc.) and also maintains statistics such as recovered packets, missing packets, un-recoverable packets, etc., as indicated at 118.

[0032] An FEC controller 120 is a central management component that, among other things, creates/removes the FEC encoding context 110 and decoding context 116, modifies the algorithm 114 properties and the like. Embodiments of FEC controller 120 are responsible for retrieving the statistics from both the encoding (e.g., statistics 112) and decoding (e.g., statistics 118) side and determine if the bandwidth overheads should be adjusted. For example, if there are un-recoverable packets, then system 100 increases the number of repair packets 106. Likewise, if the missing packets are less than the repair packets 106 being generated, the system 100 reduces the repair packets 106. Other embodiments and logic are possible as disclosed herein.

[0033] FIG. 2 illustrates an FEC packet encoding system 200 that is agnostic to any specific FEC algorithm in accordance with disclosed embodiments. As part of FEC encoding processing, the FEC encoder 102 provides the packet 104 with its contents, as indicated in FIG. 2, to the FEC algorithm 114. As indicated packet 104 may comprise an FEC protected packet that is a shorter packet in an FEC block and includes an IP header 202 and an IP payload 204. The FEC encoder 102 then adds a FEC trailer 206 and adjusts the IP-header 202 length and checksum (e.g., by padding 208 with a known pattern to the length of the largest packet 104B in the FEC block 212) to account for the added length of the packet 104. The packet buffer metadata, not shown in FIG. 2, may also be suitably adjusted.

[0034] As also indicated on FIG. 2, the portion 210 of packet 104 is the portion of the packet that is sent to the remote receiver (e.g., FEC decoder 108). However, FEC encoder 102 operates over the whole packet 104 as indicated by bracket for FEC block 212.

[0035] In some embodiments, the FEC trailer 206 comprises the following components, a MAGIC #214 (e.g., MAGIC1, MAGIC2, etc.) that indicates if the packet is an original packet 104 or a repair packet 106, a Block-ID 216 that indicates which block of packets the given packet belongs to, and a Sequence #218 that indicates the position within the block of packets the given packet belongs to.

[0036] Embodiments maintain a notion of block (e.g., FEC block 212), irrespective of whether the particular FEC algorithm 114 is a block FEC algorithm, a sliding window FEC algorithm, or some other variant. An FEC block 212 defines the number of original packets 104 and the number of repair packets 106. Once a FEC block 212 is in processing, no changes are made to the FEC algorithm 114 parameters. Any changes to adjust the repair packets 106 to generate is performed in the next block (e.g., a subsequent FEC Block 212).

[0037] As will be apparent to those of skill in the art having the benefit of this disclosure, the notion of the FEC block 212 does not limit implementation using a sliding-window FEC code. What matters is how a sliding-window FEC algorithm implementation views the arrival of the original packets 104 and the repair packets 106. The FEC block 212 notion need not be known to a sliding-window FEC algorithm 114.

[0038] Since the sender (e.g., FEC encoder 102 where FEC encoding is done) generates the repair packets 106, the receiver (e.g., FEC decoder 108) needs to be aware whenever the algorithm 114 properties change. This signaling is done via the source-port field of the UDP header 220 added to the repair packets 106 of the FEC block 212. IP header 202 of repair packet 106 (indicated with bracket 222 on FIG. 2) has the same source/destination-IP as the FEC protected packet (e.g., packet 104). Embodiments of UDP header 220 may comprise a dummy header to make the FEC data 212 middle box safe. Note that in some embodiments the FEC recovery may be done only when at least one repair packet 106 is available, in which case sending the information in the repair packet 106 and not in the FEC trailer 206 of the original packets 104, may suffice.

[0039] Embodiments of FEC algorithms 114 may require some mathematical state to be maintained at the FEC encoder 102 and FEC decoder 108. In some block FEC algorithms, such as Reed-Solomon, the state is based on the number of original packets 104 and repair packets 106 in an FEC block 212. This means a huge set of state combinations are possible. In such situations, and to allow variability of the parameters for adaptiveness, the solution can ensure that only a few selected combinations of the two parameters can be supported. This ensures that the receiver (FEC decoder 108) tunes itself automatically while still not requiring a large memory for maintaining all possible combinations of the mathematical state.

[0040] As will be apparent, FEC controller 120 essentially controls three tuning parameters 224 (shown schematically in FIG. 3) (other than any algorithm 114 specific parameters): (i) number of original packets 104, (ii) number of repair packets 106, and (iii) turning FEC on/off. Embodiments of FEC controller 120 may get information from the encoding states 112 and decoding states 118, as shown schematically in FIG. 1 and also from other components 122 of system 100 such as QoE monitoring components, user inputs components, or the like. For example, in some embodiments, a QoE monitoring component (e.g., one exemplary other component 122) may provide FEC controller 120 with information such as actual bandwidth, utilization, etc., and a user input component may provide target maximum FEC overhead in terms of percentage of link bandwidth, or the like. Other components 122 may also be in communication with FEC controller 120.

[0041] Embodiments of FEC controller 120 may correlate loss/recovery rates across multiple FEC encode 110/decode 116 contexts. For example, when different contexts 110, 116 are used for different types of traffic between the same sender (e.g., FEC encoder 102) and the same receiver (e.g., FEC decoder 108), the contexts 110, 116 may be amended such that more important traffic types are given priority FEC handling over other traffic types. Thus, while the bandwidth overhead per FEC context 110, 116 may be more, overall, on the lossy link between the sender and receiver, the FEC overhead may be reduced and, thereby, still meet any user set threshold.

[0042] Using these various sources of information, FEC controller 120 maintains a history of data and uses it for predictive analysis. In some embodiments, predictive analysis by FEC controller 120 may adjust the traffic parameters pro-actively to compensate for any trend towards more packet loss, less packet loss, or other conditions. For example, if the data collected over a period indicates increasing packet loss, the FEC controller 120 may add more repair packets 106. Likewise, a trend indicating reducing losses may be used to reduce the repair packets 106 per FEC block 212. Such adjustments lead to faster system 100 response to many predictable loss situations.

[0043] Embodiments of FEC controller 120 may also ensure that certain minimum number of repair packets 106 are always maintained in order to respond to unpredictable and bursty loss situations or the like. In some embodiments, if the FEC controller 120 determines that there has been no loss for a predetermined period of time, it may disable the FEC. Other embodiments are also possible.

[0044] FIG. 3 illustrates another FEC packet encoding system 300 that is agnostic to any specific FEC algorithm in accordance with disclosed embodiments. As shown in this embodiment, MAGIC #214 field may be omitted in the FEC trailer 202. In these embodiments, based on packet 104 size difference between IP-header 202 and overall packet 104 size (e.g., as known from the device driver or the like), system 300 may detect the presence of FEC trailer 206. Additionally, in some embodiments the IP-protocol field in the IP Header 202 (e.g., repair packet 106 IP header indicated at 222) may be used to indicate a repair packet 106. As also indicated in FIG. 3, in some embodiments the UDP header 220 in repair packets 106 may be omitted and instead the FEC algorithm 114 tuning parameters 224 may be part of FEC trailer 206, in addition to blk-id 216 and seq #218. Other embodiments are also possible.

[0045] Although various embodiments have been shown and described, the present disclosure is not so limited and will be understood to include all such modifications and variations would be apparent to one skilled in the art.