Data delivery system and method for delivering data and redundant information over a unidirectional network

• US 6,081,907 A
• Filed: 06/09/1997
• Issued: 06/27/2000
• Est. Priority Date: 06/09/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Moran, Brian, Birdwell, Kenneth J., Witty, Carl R., Sargent, James Randall
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): ELISCA, PIERRE E
• Application Number:
  US08/871,657
• Time in Patent Office: 1,114 Days
• Field of Search: 395/182.04, 395/182.09, 395/182.05, 395/182.14, 370/216, 370/218, 370/389, 370/409, 709/200, 709/201, 709/203, 709/212, 709/213, 709/227, 709/232, 709/238, 714/6, 714/18, 714/20, 714/716, 714/717, 714/761, 714/762, 714/755, 714/752
• US Class Current: 714/6.1
• CPC Class Codes: H04L 1/0041 Arrangements at the transmitter end
• CPC Class Codes: H04L 12/1877 Measures taken prior to transmission
• CPC Class Codes: H04L 12/189 in combination with wireless systems selective distribution or broadcast in wireless communication networks H04W4/06

Abstract

A data delivery system facilitates transmission of data packets from a content server to multiple clients over a unidirectional network. A redundancy formatter resident at the server groups multiple data packets into a redundancy group and generates at least one redundancy packet containing redundancy information derived from the data packets in the redundancy group. The data packets and redundancy packet are sent over the unidirectional network to the client. In the event that a packet is lost, a packet rebuilder resident at each client reconstructs the missing data packet from the successfully transmitted data packets in the redundancy group and the redundancy packet for the redundancy group.

Claims

1. A method for sending data packets over a unidirectional network, comprising the following steps:

grouping multiple data packets into a redundancy group;

forming at least one redundancy packet containing redundancy information generated from the data packets in the redundancy group; and

sending the data packets and the redundancy packet over the unidirectional network.

2. A method as recited in claim 1, wherein each data packet has multiple bytes, and further comprising the step of generating the redundancy packet to include multiple bytes which correspond to the multiple bytes of the data packets, each byte in the redundancy packet containing redundancy information that is computationally derived from the corresponding bytes in each of the data packets within the redundancy group.

3. A method as recited in claim 1, wherein each data packet has multiple bytes, and further comprising the step of generating the redundancy packet to include multiple bytes which correspond to the multiple bytes of the data packets, each byte in the redundancy packet containing redundancy information that is computationally derived according to an XOR function of the corresponding bytes in each of the data packets within the redundancy group.

4. A method as recited in claim 1, further comprising the step of assigning a redundancy group identifier to every data packet within the redundancy group to identify the data packets as belonging to the redundancy group.

5. A method as recited in claim 1, further comprising the step of assigning a unique packet identifier to each data packet within the redundancy group.

6. A method as recited in claim 1, further comprising the step of assigning a content identifier to each data packet to identify the data packet as belonging to a particular data transmission.

7. A method as recited in claim 1, further comprising the following steps:

receiving the data packets and redundancy packet;

reconstructing any data packet from the redundancy group using the received data packets and the redundancy packet.

8. A method as recited in claim 1, further comprising the following steps:

forming multiple redundancy groups, each redundancy group having multiple data packets and at least one redundancy packet;

interleaving data packets from different ones of the redundancy groups prior to sending the data packets over the unidirectional network.

9. A computer-readable medium having computer-executable instructions for performing the steps of the method as recited in claim 1.

10. A computer programmed to perform the steps of the method as recited in claim 1.

11. A method for serving multiple data packets for a data transmission over a unidirectional network, comprising the following steps:

assigning a content identifier to each data packet to identify the data packet as belonging to the data transmission;

assigning a unique packet identifier to each data packet;

grouping the data packets into multiple redundancy groups, each redundancy group having multiple data packets;

assigning a redundancy group identifier to every data packet within a particular redundancy group to identify the data packets as belonging to the particular redundancy group;

forming at least one redundancy packet for associated ones of the redundancy groups, the redundancy packet containing redundancy information generated from the data packets in the associated redundancy group; and

assigning a redundancy group count to each data packet within the particular redundancy group to represent a total number of packets within the particular redundancy group.

12. A method as recited in claim 11, wherein each data packet has multiple bytes, and further comprising the step of generating the redundancy packet for each redundancy group to include multiple bytes which correspond to the multiple bytes of the data packets in the redundancy group, each byte in the redundancy packet containing redundancy information that is computationally derived from the corresponding bytes in each of the data packets within the redundancy group.

13. A method as recited in claim 11, wherein each data packet has multiple bytes, and further comprising the step of generating the redundancy packet for each redundancy group to include multiple bytes which correspond to the multiple bytes of the data packets in the redundancy group, each byte in the redundancy packet containing redundancy information that is computationally derived according to an XOR function of the corresponding bytes in each of the data packets within the redundancy group.

14. A method as recited in claim 11, further comprising the step of sending the data packets and the redundancy packets over the unidirectional network.

15. A method as recited in claim 11, further comprising the following steps:

interleaving data packets from different ones of the redundancy groups; and

sending the interleaved data packets along with the redundancy packets over the unidirectional network.

16. A computer-readable medium having computer-executable instructions for performing the steps of the method as recited in claim 11.

17. A computer programmed to perform the steps of the method as recited in claim 11.

18. A method for handling data packets transmitted over a unidirectional network, comprising the following steps:

receiving data packets carried over the unidirectional network, the data packets belonging to various redundancy groups;

receiving redundancy packets carried over the unidirectional network, the redundancy packets belonging to the various redundancy groups and containing redundancy information generated from the data packets in associated redundancy groups;

gathering the data packets and the redundancy packets into respective ones of the redundancy groups;

checking each redundancy group to determine if any of the data packets are missing; and

in an event that a particular data packet is missing from a particular redundancy group, reconstructing the particular data packet from remaining ones of the data packets in the particular redundancy group and the redundancy packet for the particular redundancy group.

19. A method as recited in claim 18, wherein each data packet has a redundancy group identifier to identify the data packet as belonging to one of the redundancy groups, and said gathering step comprises gathering the data packets with like redundancy group identifiers to form the redundancy groups.

20. A method as recited in claim 18, wherein each data packet has a redundancy group count to represent a total number of packets contained within the redundancy group to which the data packet belongs, and said checking step comprises the step of detecting whether any data packet is missing from the particular redundancy group by comparing the redundancy group count in one of the data packets within the particular redundancy group with an actual number of packets gathered for the particular redundancy group.

21. A method as recited in claim 18, wherein each data packet has a unique packet identifier, and further comprising the step of determining which data packet is missing from the particular redundancy group.

22. A method as recited in claim 18, wherein each data packet and each redundancy packet has multiple bytes arranged in predefined positions so that byte positions within the redundancy packet correspond to byte positions within the data packet, and said reconstructing step comprises computationally deriving bytes in the particular data packet that is missing from the corresponding bytes in each of the remaining data packets and the redundancy packet within the particular redundancy group.

23. A method as recited in claim 18, wherein each data packet and each redundancy packet has multiple bytes arranged in predefined locations so that byte positions within the redundancy packet correspond to byte positions within the data packet, and said reconstructing step comprises XORing the corresponding bytes in each of the remaining data packets and the redundancy packet within the particular redundancy group to regenerate the bytes in the particular data packet that is missing.

24. A computer-readable medium having computer-executable instructions for performing the steps of the method as recited in claim 18.

25. A computer programmed to perform the steps of the method as recited in claim 18.

26. In a data delivery system for sending data packets from a server to a client over a unidirectional network, the client and the server each having a computer-readable medium, the computer-readable media on the server and the client having computer-executable instructions for performing steps comprising:

grouping multiple data packets into a redundancy group at the server;

generating at least one redundancy packet containing redundancy information derived from the data packets in the redundancy group;

sending the data packets and the redundancy packet over the unidirectional network; and

reconstructing at the client any data packet missing from the redundancy group using remaining ones of the data packets in the redundancy group and the redundancy packet for the redundancy group.

27. Computer-readable media having computer-executable instructions as recited in claim 26, further comprising computer-executable instructions to perform steps of forming multiple redundancy groups, each redundancy group having multiple data packets and at least one redundancy packet, and interleaving data packets from different ones of the redundancy groups at the server prior to sending the data packets over the unidirectional network.

28. A data delivery system for sending data packets from a server to a client over a unidirectional network, comprising:

a redundancy formatter located at the server, the redundancy formatter grouping multiple data packets into a redundancy group and generating at least one redundancy packet containing redundancy information derived from the data packets in the redundancy group; and

a packet rebuilder located at the client, the packet rebuilder reconstructing any data packet missing from the redundancy group using remaining ones of the data packets in the redundancy group and the redundancy packet for the redundancy group.

29. A data delivery system as recited in claim 28, wherein each data packet has multiple bytes at predefined positions within the packet, the redundancy formatter generating the redundancy packet to include multiple bytes which correspond in position to the bytes of the data packets, each byte in the redundancy packet containing redundancy information that is computationally derived from the corresponding bytes in each of the data packets within the redundancy group.

30. A data delivery system as recited in claim 28, wherein each data packet has multiple bytes at predefined positions within the packet, the redundancy formatter generating the redundancy packet to include multiple bytes which correspond in position to the bytes of the data packets, each byte in the redundancy packet containing redundancy information that is computationally derived according to an XOR function of the corresponding bytes in each of the data packets within the redundancy group.

31. A data delivery system as recited in claim 28, wherein each data packet comprises a redundancy group identifier to identify the data packet as belonging to the redundancy group.

32. A data delivery system as recited in claim 28, wherein each data packet comprises a unique packet identifier.

33. A data delivery system as recited in claim 28, wherein each data packet comprises a content identifier to identify the data packet as belonging to a particular data transmission.

34. A data delivery system as recited in claim 28, wherein the redundancy formatter forms multiple redundancy groups, with each redundancy group having multiple data packets and at least one redundancy packet, the redundancy formatter interleaving data packets from different ones of the redundancy groups prior to transmission over the unidirectional network to the client.

35. A computer-readable memory having a packet structure for a data packet to be carried by a unidirectional network as part of a data transmission, the data packet belonging to a group of data packets, the network packet structure comprising:

a header comprising;

a packet identifier field to uniquely identify the data packet;

a content identifier field to uniquely identify the data packet as belonging to a particular data transmission;

a redundancy group identifier field to identify the packet as belonging to a redundancy group of data packets, the redundancy group comprising multiple data packets and at least one redundancy packet derived from the data packets;

a redundancy group count to represent a total number of the packets contained within the redundancy group to which the data packet belongs; and

a data payload joined to the header to hold the data of the data packet.