High integrity transport for time critical multimedia networking applications

• US 6,079,042 A
• Filed: 05/11/1998
• Issued: 06/20/2000
• Est. Priority Date: 04/27/1995
• Status: Expired due to Term

• Current Assignee: Zarbana Digital Fund LLC (Intellectual Ventures LLC)
• Original Assignee: The Trustees of The Stevens Institute of Technology (Stevens Institute Of Technology)
• Inventors: Chakravarthy, Cadathur V., Hong, Kicheon, Vaman, Dhadesugoor R.
• Primary Examiner(s): Baker, Stephen M.
• Application Number:
  US08/945,453
• Time in Patent Office: 771 Days
• Field of Search: 714/755, 714/776
• US Class Current: 714/755
• CPC Class Codes: H03M 13/11 using multiple parity bits
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/2921 wherein error correction coding involves a diagonal direction
• 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/0041 Arrangements at the transmitter end
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence
• 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: H04L 2012/5654 using the AAL1
• CPC Class Codes: H04L 2012/5658 using the AAL5
• CPC Class Codes: H04L 2012/5673 Coding or scrambling
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A method is provided for recovery of lost cells in a telecommunications infrastructure such as an ATM network wherein an error recovery scheme is incorporated into the network infrastructure to allow recovery of cells along the network.

Claims

1. A method of recovering lost packets of data transported through an ATM network comprising the steps of:

segmenting data into blocks of predetermined size;

computing vertical and diagonal parity packets for the blocks;

eliminating unnecessary redundant diagonal parity bits from the diagonal parity packet;

adding the vertical and diagonal parity packets to the blocks;

transmitting the blocks with the vertical and diagonal parity packets to a receiving side of an ATM network;

identifying errored or missing packets at a receiving side of an ATM network; and

recovering data for errored or missing packets by computing the lost or missing data from the vertical and diagonal parity packets and from other information packets.

2. The method of claim 1 wherein packet recovery capability is increased by the step of adding parity packets which are linearly independent of previously constructed parity packets.

3. The method of claim 1 wherein the step of computing vertical and diagonal parity packets for the blocks comprises modulo 2 additions.

4. The method of claim 3 wherein the step of computing the lost or missing data from the vertical and diagonal parity comprises modulo 2 additions.

5. The method of claim 1 wherein the vertical and diagonal parity packets are formed in an ATM adaptation layer.

6. The method of claim 5 wherein the ATM adaptation layer selectively implements the step of recovering data.

7. The method of claim 6 wherein the detection of errored or missing packets is accomplished along the network itself and does not require that the blocks of data reach their respective destinations.

8. The method of claim 1 wherein errored or missing packets are detected and recovered or corrected prior to receiving a successive block at the receiving side of an ATM network.

9. The method of claim 8 wherein the step of identifying and recovering errored or missing packets at a receiving side of an ATM network creates no more than a one packet receiving time delay.

10. The method of claim 9 wherein errored or missing packets are detected and recovered in parallel.

11. A method of recovering lost data transmitted through an ATM network comprising the steps of:

grouping data into blocks;

forming a vertical parity packet by modulo-2 addition of data along block verticals;

forming a diagonal parity packet by modulo-2 addition of data along block diagonals;

eliminating unnecessary redundant diagonal parity bits from the diagonal parity packet;

inserting the vertical and diagonal parity packets into an ATM cell;

transmitting the ATM cell through an ATM network;

identifying lost or erroneous information in an ATM cell; and

recovering the lost or erroneous information in an ATM cell by computing the lost or erroneous information from the vertical and diagonal parity packets.

12. The method of claim 11 wherein errored or missing packets are detected and recovered or corrected prior to receiving a successive block at the receiving side of an ATM network, and the step of identifying and recovering errored or missing packets at a receiving side of an ATM network creates no more than a one packet receiving time delay.

13. The method of claim 11 wherein the step of computing vertical and diagonal parity packets for the blocks comprises modulo 2 additions.

14. The method of claim 13 wherein the step of computing the lost or missing data from the vertical and diagonal parity comprises modulo 2 additions.

15. The method of claim 11 wherein the vertical and diagonal parity packets are formed in an ATM adaptation layer.

16. The method of claim 15 wherein the ATM adaptation layer selectively implements the step of recovering data.

17. The method of claim 16 wherein the detection of errored or missing packets is accomplished along the network itself and does not require that the blocks of data reach their respective destinations.

18. A method of recovering lost packets of data transported through an ATM network comprising the steps of:

grouping data into blocks of predetermined size;

computing vertical and diagonal parity packets for the blocks;

eliminating unnecessary redundant diagonal parity bits from the diagonal parity packet;

adding the vertical and diagonal parity packets to the blocks;

transmitting the blocks;

identifying errored or missing packets within the blocks; and

recovering data for errored or missing packets by computing the lost or missing data from the vertical and diagonal parity packets through modulo 2 addition.

19. The method of claim 18 wherein the detection of errored or missing packets is accomplished along the network itself and does not require that the blocks of data reach their respective destinations.

20. The method of claim 18 wherein errored or missing packets are detected and recovered or corrected prior to receiving a successive block at the receiving side of an ATM network, and the step of identifying and recovering errored or missing packets at a receiving side of an ATM network creates no more than a one packet receiving time delay.

21. A method of recovering lost packets of data transported through an ATM network comprising the steps of:

segmenting data into blocks of predetermined size having m horizontal bits;

computing vertical and diagonal parity packets for the blocks;

eliminating unnecessary redundant diagonal parity bits from the diagonal parity packet to form a parity packet having m bits;

adding the parity packets to the blocks;

transmitting the blocks with the parity packets to a receiving side of an ATM network;

identifying errored or missing packets at a receiving side of an ATM network; and

recovering data for errored or missing packets by computing the lost or missing data from the parity packets and from other information packets.

22. The method of claim 21 wherein errored or missing packets are detected and recovered or corrected prior to receiving a successive block at the receiving side of an ATM network.

23. The method of claim 22 wherein the step of identifying and recovering errored or missing packets at a receiving side of an ATM network creates no more than a one packet receiving time delay.

24. The method of claim 21 wherein the packets are formed in an ATM adaptation layer.

25. The method of claim 24 wherein the ATM adaptation layer selectively implements the step of recovering data.

26. The method of claim 25, wherein the detection of errored or missing packets is accomplished along the network itself and does not require that the blocks of data reach their respective destinations.

27. A method of recovering lost data transmitted through an ATM network comprising the steps of:

grouping data into blocks of a predetermined size having m horizontal bits;

forming a vertical parity packet by modulo-2 addition of data along block verticals;

forming a diagonal parity packet by modulo-2 addition of data along block diagonals;

eliminating unnecessary redundant diagonal parity bits from the diagonal parity packet to form a parity packet having m bits;

inserting the parity packets into an ATM cell;

transmitting the ATM cell through an ATM network;

identifying lost or erroneous information in an ATM cell; and

recovering the lost or erroneous information in an ATM cell by computing the lost or erroneous information from the parity packets.

28. The method of claim 27 wherein errored or missing packets are detected and recovered or corrected prior to receiving a successive block at the receiving side of an ATM network, and the step of identifying and recovering errored or missing packets at a receiving side of an ATM network creates no more than a one packet receiving time delay.

29. The method of claim 27 wherein the vertical and diagonal parity packets are formed in an ATM adaptation layer.

30. The method of claim 29 wherein the ATM adaptation layer selectively implements the step of recovering data.

31. The method of claim 30 wherein the detection of errored or missing packets is accomplished along the network itself and does not require that the blocks of data reach their respective destinations.