Adaptive forward error correction system and method

• US 5,699,369 A
• Filed: 03/29/1995
• Issued: 12/16/1997
• Est. Priority Date: 03/29/1995
• Status: Expired due to Term

• Current Assignee: Network Systems Corp. (Oracle Corporation)
• Original Assignee: Network Systems Corp. (Oracle Corporation)
• Inventors: Guha, Aloke
• Primary Examiner(s): Baker, Stephen M.
• Application Number:
  US08/413,121
• Time in Patent Office: 993 Days
• Field of Search: 371/41
• US Class Current: 714/774
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/25 Error detection or forward error correction by signal space coding, i.e. adding redundancy in the signal constellation, e.g. Trellis Coded Modulation [TCM] modulation codes H03M13/31
• CPC Class Codes: H03M 13/35 Unequal or adaptive error protection, e.g. by providing a different level of protection according to significance of source information or by adapting the coding according to the change of transmission channel characteristics
• CPC Class Codes: H03M 13/373 with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes
• CPC Class Codes: H04L 1/0009 by adapting the channel coding H04L1/1812 takes precedence
• CPC Class Codes: H04L 1/0017 where the mode-switching is based on Quality of Service requirement
• CPC Class Codes: H04L 2012/5616 Terminal equipment, e.g. codecs, synch.
• CPC Class Codes: H04L 2012/5647 Cell loss
• CPC Class Codes: H04L 2012/5653 using the ATM adaptation layer [AAL]
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

An adaptive forward error correction (FEC) protocol for use in an asynchronous transfer mode (ATM) communication network is provided. Whether a feasibility condition is met indicating that FEC can compensate for an expected number of burst errors in a FEC encoded payload is determined. Subsequently, FEC encoding is performed on protocol data units (PDUs) within a payload to form the FEC encoded payload only when the feasibility condition is met. Adaptive FEC sending and receiving units which effectuate the adaptive FEC protocol are provided. In addition, an alternative adaptive FEC protocol is provided which determines a feasibility condition based on whether a PDU loss probability between connection service application points for a payload is greater than an effective PDU loss probability for the payload with associated FEC PDUs at a given load on the communication network. Also, a method for determining an overhead parameter for adaptive FEC in a communication network is provided.

Claims

1. An adaptive forward error correction protocol for use in an asynchronous transfer mode communication network, comprising the steps of:

(a) determining whether a feasibility condition is met based on indicating that forward error correction can compensate for an expected number of burst errors in a forward error correction encoded payload,

(b) performing forward error correction coding on protocol data units within a payload to form the forward error correction encoded payload only when the feasibility condition is met.

2. The method of claim 1 wherein the determining step is accomplished above an asynchronous transfer mode adaptation layer.

3. The method of claim 1 wherein the protocol data units are selected from the group consisting of service data units, cells, and frames.

4. The method of claim 1 wherein the expected number of burst errors for a forward error correction encoded payload is derived from a metric comprising a related function (B) defined as follows:

##EQU23## where, n=a number of protocol data units in an encoded form of the payload; and

P=a protocol data unit loss probability between connection service application points at a time that the payload is to be sent.

5. The method of claim 1 further comprising the step of initiating the determining and performing steps for each payload to be sent on a virtual circuit from a service application point in the asynchronous transfer mode communication network.

6. The method of claim 5 further comprising the step of sending the forward error correction encoded payload along with a corresponding predetermined overhead parameter on a virtual circuit from a source service application point to a destination service application point in the asynchronous transfer mode communication network, the predetermined overhead parameter representing a ratio of forward error correction protocol data units needed to correct the expected number of burst errors in the forward error correction encoded payload to other protocol data units in the forward error correction encoded payload.

7. The method of claim 6 further comprising the step of receiving the forward error correction encoded payload along with the corresponding predetermined overhead parameter on the virtual circuit at the destination service application point in the asynchronous transfer mode communication network, performing forward error correction to correct burst errors in the forward error correction encoded payload such that overall protocol data unit loss on the asynchronous transfer mode communication network is reduced.

8. The method of claim 1 wherein the performing step is accomplished in an asynchronous transfer mode adaptation layer, the asynchronous transfer mode adaptation layer having a service specific convergence sublayer, a common part convergence sublayer, and a segmentation and reassembly sublayer.

9. The method of claim 8 wherein the performing step is accomplished in the service specific convergence sublayer such that the protocol data units comprise frames for an asynchronous transfer mode adaptation layer 5 service class.

10. The method of claim 8 wherein the performing step is accomplished in the segmentation and reassembly sublayer such that the protocol data units comprise cells for an asynchronous transfer mode adaptation layer 3/4 service class.

11. The method of claim 1 wherein the performing step comprises using an error correction scheme selected from the group consisting of a convolutional code error correction scheme and a block code error correction scheme.

12. The method of claim 11 wherein the block code error correction scheme is a Reed-Solomon (RS) coding scheme.

13. The method of claim 5 wherein the feasibility condition is derived from an inequality comprising related functions defined as follows:

##EQU24## where, λ

=a communication network load at a time that the payload is to be sent;

P=protocol data unit loss probability between connection service application points at a time that the payload is to be sent; and

##EQU25## =a rate of change of P with respect to λ

.

14. The method of claim 11 wherein the performing step comprises determining a quantity of forward error correction protocol data units needed for a predetermined number of protocol data units in the payload based on a predetermined overhead parameter, generating the quantity of forward error correction protocol data units based on the block code error correction coding scheme, appending the generated forward error correction protocol data units to the protocol data units in the payload to form the forward error correction encoded payload.

15. The method of claim 14 wherein the predetermined overhead parameter is derived from protocol data unit loss information from a layer selected from the group consisting of a segmentation and reassembly sublayer of an asynchronous transfer mode adaptation layer and an Open Systems Interconnection (OSI) layer above the network layer.

16. The method of claim 14 wherein the predetermined errors in a forward error correction encoded payload;

and overhead parameter is derived from a metric comprising a related function (α

) defined as follows;

##EQU26## where, λ

=communication network load at a time that the payload is to be sent;

P=protocol data unit loss probability between connection service application points at a time that the payload is to be sent; and

##EQU27## =a rate of change of P with respect to λ

.

17. An adaptive forward error correction protocol for use in an asynchronous transfer mode communication network, comprising the steps of:

(a) determining whether a feasibility condition is met based on indicating that forward error correction can compensate for an expected number of burst errors in a forward error correction encoded payload;

(b) performing forward error correction on protocol data units within the payload to form a forward error correction encoded payload only when the feasibility condition is met;

(c) sending the forward error correction encoded payload along with a corresponding predetermined overhead parameter on a virtual circuit from a source service application point to a destination service application point in the asynchronous transfer mode communication network, the predetermined overhead parameter representing a ratio of forward error correction protocol data units needed to correct the expected number of burst errors in the forward error correction encoded payload to other protocol data units in the forward error correction encoded payload; and

(d) receiving the forward error correction encoded payload along with the corresponding predetermined overhead parameter on the virtual circuit at the destination service application point in the asynchronous transfer mode communication network, performing forward error correction to correct burst errors in the forward error correction encoded payload such that overall protocol data unit loss on the asynchronous transfer mode communication network is reduced.

18. The method of claim 17 further comprising the step of initiating the determining and performing steps for each payload to be sent on a virtual circuit from a service application point in the asynchronous transfer mode communication network.

19. The method of claim 17 wherein the determining step is accomplished above an asynchronous transfer mode adaptation layer.

20. The method of claim 17 wherein the performing step is accomplished in an asynchronous transfer mode adaptation layer, the asynchronous transfer mode adaptation layer having a service specific convergence sublayer, a common part convergence sublayer, and a segmentation and reassembly sublayer, the forward error correction being accomplished in the service specific convergence sublayer such that the protocol data units comprise frames for an asynchronous transfer mode adaptation layer 5 service class.

21. The method of claim 17 wherein the performing step is accomplished in an asynchronous transfer mode adaptation layer, the asynchronous transfer mode adaptation layer having a service specific convergence sublayer, a common part convergence sublayer, and a segmentation and reassembly sublayer, the forward error correction being accomplished in the segmentation and reassembly sublayer such that the protocol data units comprise cells for an asynchronous transfer mode adaptation layer 3/4 service class.

22. The method of claim 17 wherein the expected number of burst errors for a forward error correction encoded payload is derived from a metric comprising a related function (B) defined as follows:

##EQU28## where, n=a number of protocol data units in an encoded form of the payload; and

P=a protocol data unit loss probability between connection service application points at a time that the payload is to be sent.

23. The method of claim 17 wherein the performing step comprises determining a quantity of optimal block erasure correction protocol data units needed for a predetermined number of protocol data units in the payload based on the corresponding predetermined overhead parameter, generating the quantity of forward error correction protocol data units based on an optimal block erasure correction scheme, appending the generated forward error correction protocol data units to the protocol data units in the payload to form the forward error correction encoded payload, the corresponding predetermined overhead parameter being derived from a metric comprising a related function (α

) defined as follows;

##EQU29## where, λ

=a communication network load at a time that the payload is to be sent;

P=protocol data unit loss probability between connection service application points at a time that the payload is to be sent; and

##EQU30## =a rate of change of P with respect to λ

.

24. The method of claim 17 wherein the feasibility condition is based on an optimal block erasure correction scheme, the feasibility condition being derived from an inequality comprising related functions defined as follows:

##EQU31## where, λ

=a communication network load at a time that the payload is to be sent;

P=protocol data unit loss probability between connection service application points at a time that the payload is to be sent; and

##EQU32## =a rate of change of P with respect to λ

.

25. The method of claim 24 wherein the optimal block erasure correction scheme comprises a Reed-Solomon decoding scheme.

26. An adaptive forward error correction sending unit for use in an asynchronous transfer mode communication network, comprising:

(a) feasibility means for determining whether a feasibility condition is met indicating that forward error correction can compensate for an expected number of burst errors in a forward error correction encoded payload;

(b) determining means, operatively coupled to the feasibility means, for determining an overhead parameter representing a ratio of forward error correction protocol data units to protocol data units in the forward error correction encoded payload needed to correct the expected number of burst errors in the forward error correction encoded payload; and

(c) forward error correction means, operatively coupled to the feasibility means and the determining means, for performing forward error correction coding on protocol data units within the payload based on the overhead parameter to form a forward error correction encoded payload only when the feasibility condition is met.

27. The adaptive forward error correction sending unit of claim 26 further comprising transmission means, operatively coupled to the determining means and the forward error correction means, for sending the forward error correction encoded payload along with the overhead parameter on a virtual circuit from a source service application point to a destination service application point in the asynchronous transfer mode communication network.

28. The adaptive forward error correction sending unit of claim 26 wherein the forward error correction means comprises means for determining a quantity of optimal block erasure correction protocol data units needed for a predetermined number of protocol data units in the payload based on the overhead parameter, generating the quantity of forward error correction protocol data units based on the optimal block erasure correction scheme, and appending the generated forward error correction protocol data units to the protocol data units in the payload to form the forward error correction encoded payload, the predetermined overhead parameter being derived from a metric comprising a related function (α

) defined as follows;

##EQU33## where, λ

=a communication network load at a time that the payload is to be sent;

P=protocol data unit loss probability between connection service application points at a time that the payload is to be sent; and

##EQU34## =a rate of change of P with respect to λ

.

29. The adaptive forward error correction sending unit of claim 26 wherein determining means derives the overhead parameter from protocol data unit loss information from a layer selected from the group consisting of a segmentation and reassembly sublayer of an asynchronous transfer mode adaptation layer and an Open Systems Interconnection (OSI) layer above the network layer.

30. The adaptive forward error correction sending unit of claim 26 wherein the feasibility condition is based on an optimal block erasure correction scheme, the feasibility condition being derived from an inequality comprising related functions defined as follows:

##EQU35## where, λ

=a communication network load at a time that the payload is to be sent;

P=protocol data unit loss probability between connection service application points at a time that the payload is to be sent; and

##EQU36## =a rate of change of P with respect to λ

.

31. The adaptive forward error correction sending unit of claim 30 wherein the optimal block erasure correction scheme comprises a Reed-Solomon decoding scheme.

32. The adaptive forward error correction sending unit of claim 26 wherein the forward error correction means operates in an asynchronous transfer mode adaptation layer, the asynchronous transfer mode adaptation layer having a service specific convergence sublayer, a common part convergence sublayer, and a segmentation and reassembly sublayer.

33. The adaptive forward error correction sending unit of claim 32 wherein the forward error correction means operates in the service specific convergence sublayer such that the protocol data units comprise frames for an asynchronous transfer mode adaptation layer 5 service class.

34. The adaptive forward error correction sending unit of claim 32 wherein the forward error correction means operates in the segmentation and reassembly sublayer such that the protocol data units comprise cells for an asynchronous transfer mode adaptation layer 3/4 service class.

35. An adaptive forward error correction receiving unit for use in an asynchronous transfer mode communication network, comprising:

(a) receiving means for receiving a forward error correction encoded payload along with a corresponding overhead parameter on a virtual circuit at a destination service application point from a source service application point in the asynchronous transfer mode communication network;

(b) forward error correction means, operatively coupled to the receiving means, for performing forward error correction to correct burst errors in the forward error correction encoded payload based on the corresponding overhead parameter such that overall protocol data unit loss on the asynchronous transfer mode communication network is reduced, the overhead parameter representing a ratio of forward error correction protocol data units needed to correct the expected number of burst errors in the forward error correction encoded payload to other protocol data units in the forward error correction encoded payload.

36. The adaptive forward error correction receiving unit of claim 35 wherein the forward error correction means operates in an asynchronous transfer mode adaptation layer, the asynchronous transfer mode adaptation layer having a service specific convergence sublayer, a common part convergence sublayer, and a segmentation and reassembly sublayer.

37. The adaptive forward error correction receiving unit of claim 35 wherein the forward error correction means operates in the service specific convergence sublayer such that the protocol data units comprise frames for an asynchronous transfer mode adaptation layer 5 service class.

38. The adaptive forward error correction receiving unit of claim 35 wherein the forward error correction means operates in the segmentation and reassembly sublayer such that the protocol data units comprise cells for an asynchronous transfer mode adaptation layer 3/4 service class.

39. An adaptive forward error correction protocol for use in an asynchronous transfer mode communication network, comprising the steps of:

(a) determining whether a feasibility condition is met indicating that a protocol data unit loss probability between connection service application points for a payload is greater than an effective protocol data unit loss probability for the payload with associated forward error correction protocol data units at a given load on the communication network; and

(b) performing forward error correction coding on protocol data units within a payload to form a forward error correction encoded payload only when the feasibility condition is met.

40. An adaptive forward error correction sending unit for use in an asynchronous transfer mode communication network, comprising:

(a) feasibility means for determining whether a feasibility condition is met indicating that a protocol data unit loss probability between connection service application points for a payload is greater than an effective protocol data unit loss probability for the payload with associated forward error correction protocol data units at a given load on the communication network;

(b) determining means, operatively coupled to the feasibility means, for determining an overhead parameter representing a ratio of forward error correction protocol data units to other protocol data units in a forward error correction encoded payload needed to correct burst errors; and

(c) forward error correction means, operatively coupled to the feasibility means and the determining means, for performing forward error correction coding on protocol data units within the payload based on the overhead parameter to form a forward error correction encoded payload only when the feasibility condition is met.

41. The adaptive forward error correction sending unit of claim 40 further comprising transmission means, operatively coupled to the determining means and the forward error correction means, for sending the forward error correction encoded payload along with the overhead parameter on a virtual circuit from a source service application point to a destination service application point in the asynchronous transfer mode communication network.

42. An adaptive forward error correction receiving unit for use in an asynchronous transfer mode communication network, comprising:

(a) receiving means for receiving a forward error correction encoded payload along with a corresponding overhead parameter on the virtual circuit at a destination service application point from a source service application point in the asynchronous transfer mode communication network;

(b) forward error correction means, operatively coupled to the receiving means, for performing forward error correction to correct burst errors in the payload based on the corresponding overhead parameter such that overall protocol data unit loss on the asynchronous transfer mode communication network is reduced, the overhead parameter representing a ratio of forward error correction protocol data units to other protocol data units in the forward error correction encoded payload needed to correct burst errors.

43. A device-implemented method for determining an overhead parameter for adaptive forward error correction in a communication network which multiplexes connections between multiple nodes, comprising the steps of:

(a) obtaining a protocol data unit loss probability between connection service application points for a payload at a time that the payload is to be sent;

(b) obtaining a load on the communication network between connection service application points for a payload at a time that the payload is to be sent;

(c) determining a rate of change of the obtained protocol data unit loss probability with respect to the obtained load on the communication network; and

(d) deriving an overhead parameter for forward error correction of a particular payload to be sent as a function of the obtained protocol data unit loss probability, the obtained load, and the determined rate of change.

44. The method of claim 43 wherein the communication network is selected from the group consisting of a frame relay communication network and an asynchronous transfer mode communication network.

45. The method of claim 43 wherein the communication network uses adaptive forward error correction having an optimal block erasure correction scheme such that deriving step derives the overhead parameter from a metric at least comprising a related function (α

) defined as follows;

##EQU37## where, λ

=communication network load at a time that the payload is to be sent;

P=protocol data unit loss probability between connection service application points at a time that the payload is to be sent; and

##EQU38## =a rate of change of P with respect to λ

.

46. The method of claim 45 wherein the optimal block erasure correction scheme comprises a Reed-Solomon decoding scheme.