Error correction and loss recovery of packets over a computer network

• US 6,000,053 A
• Filed: 06/13/1997
• Issued: 12/07/1999
• Est. Priority Date: 06/13/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chou, Phil, Levine, Earl
• Primary Examiner(s): De Cady, Albert
• Assistant Examiner(s): Chase, Shelly A
• Application Number:
  US08/876,139
• Time in Patent Office: 907 Days
• Field of Search: 371/37.01, 371/39.1, 371/38.1, 371/2.1, 371/2.2, 395/185.01, 395/185.02, 395/185.05, 364/266.3, 370/470, 370/472, 370/474, 370/476, 370/471, 370/465, 714/766
• US Class Current: 714/766
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• CPC Class Codes: H03M 13/19 Single error correction without using particular properties of the cyclic codes, e.g. Hamming codes, extended or generalised Hamming codes
• CPC Class Codes: H03M 13/2707 Simple row-column interleaver, i.e. pure block interleaving
• CPC Class Codes: H03M 13/2915 with an error detection code in one dimension
• 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

Abstract

A method of recovering a lost or corrupted data packet of a plurality of data packets transmitted by a transmitting computer system to a target computer system over an unreliable computer network. In one embodiment, the transmitting computer system generates parity information by padding the plurality of data packets to the length of the longest data packet with a suitable bit pattern. The parity information is then generated using a suitable algorithm, such as an exclusive OR (XOR) operation. The parity information and the packet lengths of the data packets are used to form the parity packet. The transmitting computer system then sends both the data packets and the parity packet to the target computer. If the target computer system detects a lost or corrupted data packet, the target computer attempts to reconstruct the lost or corrupted data packet. The received uncorrupted data packets are padded with the suitable bit pattern described above. Note that it is useful to pad up to the length of the lost data packet. The inverse operation of the parity generating algorithm is then applied to the padded data packets and the parity packet to reconstruct the lost or corrupted data packet.

Claims

1. In a transmitting computer system, a method for reliably transmitting a plurality of data packets from the transmitting computer system to a target computer system, the transmitting computer system and the target computer system coupled to each other via a computer network, wherein at least two of the plurality of data packets have different packet lengths, the method comprising:

determining the length of a longest data packet of said plurality of data packets;

padding the remaining data packets with a suitable bit pattern, thereby generating a plurality of padded data packets at least equal in packet length to the longest data packet;

generating a parity packet from said plurality of padded data packets; and

transmitting the plurality of data packets and the parity packet to the target computer system.

2. The method of claim 1 wherein said parity packet includes the packet lengths of the plurality of data packets.

3. The method of claim 1 wherein the parity packet is generated using an "XOR" operation on the plurality of padded data packets.

4. The method of claim 1 wherein the suitable bit pattern includes "0" bits.

5. The method of claim 1 wherein the plurality of data packets include video data packets and audio data packets.

6. The method of claim 1 wherein the plurality of data packets are interleaved.

7. A transmitting computer system useful in association with a target computer system, said transmitting computer system coupled to said target computer system via a network, said transmitting computer system comprising:

a parity packet generator configured to determine the length of a longest data packet of said plurality of data packets, and configured to pad the remaining data packets with a suitable bit pattern, thereby generating a plurality of padded data packets at least equal in packet length to the longest data packet, thereby generating a parity packet from said plurality of padded data packets; and

a packet transmitter configured to transmit the plurality of data packets and the parity packet to the target computer system.

8. The transmitting computer system of claim 7 wherein said parity packet includes the packet lengths of the plurality of data packets.

9. The transmitting computer system of claim 7 wherein the parity packet is generated using an "XOR" operation on the plurality of padded data packets.

10. The transmitting computer system of claim 7 wherein the suitable bit pattern includes "0" bits.

11. The transmitting computer system of claim 7 wherein the plurality of data packets include video data packets and audio data packets.

12. The transmitting computer system of claim 7 wherein the plurality of data packets are interleaved.

13. In a target computer system, a method for recovering a corrupted or lost data packet, wherein the corrupted or lost data packet is one of a plurality of data packets transmitted from a transmitting computer system to the target computer system, the transmitting computer system and the target computer system coupled to each other via a computer network, and wherein at least two of said plurality of data packets having different packet lengths, the method comprising:

receiving at least one data packet of said plurality of data packets;

receiving a parity packet;

padding the received at least one data packet with a suitable bit pattern upon detecting a lost or corrupted data packet of said plurality of data packets, the received at least one data packet padded to at least the length of the lost or corrupted data packet; and

computing the lost or corrupted data packet from said padded at least one data packet and said parity packet upon detecting a lost or corrupted data packet of said plurality of data packets.

14. The method of claim 13 wherein the parity packet was previously generated using an "XOR" operation on the plurality of data packets by said transmitting computer system.

15. The method of claim 13 wherein the suitable bit pattern includes "0" bits.

16. The method of claim 13 wherein the plurality of data packets include video data packets and audio data packets.

17. The method of claim 13 wherein the plurality of data packets are interleaved.

18. A target computer system useful in association with a transmitting computer system, said transmitting computer system coupled to said target computer system via a network, said target computer system comprising:

a packet receiver configured to receive at least one data packet of a plurality of data packets from said transmitting computer system, and configured to receive a parity packet, and wherein at least two of said plurality of data packets having different packet lengths;

a packet loss detector configured to detect a lost or corrupted data packet of said plurality of data packets; and

a packet reconstructor configured to pad the received at least one data packet with a suitable bit pattern, the received at least one data packet padded to at least the length of the lost or corrupted data packet, and configured to compute the lost or corrupted data packet from said padded at least one data packet and said parity packet.

19. The target computer system of claim 18 wherein the parity packet was previously generated using an "XOR" operation on the plurality of data packets by said transmitting computer system.

20. The target computer system of claim 18 wherein the suitable bit pattern includes "0" bits.

21. The target computer system of claim 18 wherein the plurality of data packets include video data packets and audio data packets.

22. The target computer system of claim 18 wherein the plurality of data packets are interleaved.

23. A computer readable medium having computer-executable instructions comprising:

determining the length of a longest data packet of a plurality of data packets, wherein at least two of the plurality of data packets have different packet lengths;

padding the remaining data packets with a suitable bit pattern, thereby generating a plurality of padded data packets at least equal in packet length to the longest data packet;

generating a parity packet from said plurality of padded data packets; and

transmitting the plurality of data packets and the parity packet.

24. The computer readable medium of claim 23, wherein said parity packet includes the packet lengths of the plurality of data packets.

25. The computer readable medium of claim 23, wherein the parity packet is generated using an "XOR" operation on the plurality of padded data packets.

26. The computer readable medium of claim 23, wherein the suitable bit pattern includes "0" bits.

27. The computer readable medium of claim 23, wherein the plurality of data packets include video data packets and audio data packets.

28. The computer readable medium of claim 23, wherein the plurality of data packets are interleaved.

29. A computer readable medium having computer-executable instructions comprising:

receiving at least one data packet of a plurality of data packets;

receiving a parity packet;

padding the received at least one data packet with a suitable bit pattern upon detecting a lost or corrupted data packet of said plurality of data packets, the received at least one data packet padded to at least the length of the lost or corrupted data packet; and

computing the lost or corrupted data packet from said padded at least one data packet and said parity packet upon detecting a lost or corrupted data packet of said plurality of data packets.

30. The computer readable medium of claim 29, wherein the parity packet was previously generated using an "XOR" operation on the plurality of data packets by said transmitting computer system.

31. The computer readable medium of claim 29, wherein the suitable bit pattern includes "0" bits.

32. The computer readable medium of claim 29, wherein the plurality of data packets include video data packets and audio data packets.

33. The computer readable medium of claim 29, wherein the plurality of data packets are interleaved.