System and method for broadcasting information over a network

• US 7,349,440 B1
• Filed: 10/15/2003
• Issued: 03/25/2008
• Est. Priority Date: 10/15/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Jain, Kamal, Chou, Philip A.
• Primary Examiner(s): Rao; Seema S.
• Assistant Examiner(s): Davenport; Mon Cheri S
• Application Number:
  US10/686,952
• Time in Patent Office: 1,623 Days
• Field of Search: 370/229, 370/395.62, 370503-520, 370/390
• US Class Current: 370/503
• CPC Class Codes: H04J 3/0664 unidirectional timestamps
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast

Abstract

A system and method that enables broadcasting of data in packets across a network using network coding is described. This system and method enables a network to broadcast information in packets without full knowledge of the network'"'"'s topology. Further, it enables broadcasting of data in packets with a low probability of failure.

Claims

1. One or more computer-readable media encoded with computer-executable instructions that perform the following when executed by a computer:

receiving incoming packets of data and metadata, wherein the metadata comprises a synchronization information and a linear combination coefficients;

synchronizing the incoming packets; and

linearly combining the data and the linear combination coefficients part of the metadata of each of synchronized incoming packets into a new data portion of an outgoing packet, and inserting in a new metadata portion that is part of the outgoing packet, new linear combination coefficients that identify the data and the linear combination coefficients of the metadata within the synchronized incoming packets.

2. The computer-readable media of claim 1, further comprising:

sending the outgoing packet.

3. The computer-readable media of claim 1, further comprising including synchronization information in the metadata of the outgoing packet.

4. The computer-readable media of claim 1, wherein the synchronizing includes reading the synchronization information from the metadata, the synchronization information including a sequence number.

5. The computer-readable media of claim 1, wherein the synchronizing includes reading the synchronization information from the metadata, the synchronization information including time slots, wherein the incoming packets having matching time slots are deemed synchronized.

6. The computer-readable media of claim 1, wherein the synchronizing includes reading the synchronization information from the metadata.

7. The computer-readable media of claim 1, further comprising:

receiving the outgoing packet and other outgoing packets;

synchronizing the outgoing packet and the other outgoing packets;

linearly combining the new data portion of the outgoing packets into a second generation outgoing packet;

inserting in a second generation metadata portion that is part of the second generation outgoing packet, linear combination coefficients that identify each new data portion of synchronized outgoing packets; and

sending the second generation outgoing packet of data.

8. The computer-readable media of claim 1, wherein the data of each of the incoming packets includes one or more parts, or a linear combination of one or more parts, of a set of data and further comprising recording, within the outgoing packet, a complete linear combination of the set of data that is present within the outgoing packet.

9. The computer-readable media of claim 1, wherein the data of each of the incoming packets includes one or more vectors, or a linear combination of one or more vectors, of a set of data vectors and further comprising recording, within the outgoing packet, coefficients representing all linear combinations of the set of data vectors present within the data of the outgoing packet.

10. The computer-readable media of claim 1, wherein the data of each of the incoming packets includes one or more vectors, or a linear combination of one or more vectors, of a set of data vectors and further comprising recording, within the outgoing packet, information sufficient to disassemble the data in the outgoing packet into the set of data vectors if all but one of each of the vectors in the set of data vectors is known.

11. The computer-readable media of claim 10, wherein the recording is made into a header of the outgoing packet.

12. A system comprising:

a node of a communication network, wherein the node is capable of;

linearly combining data from multiple incoming packets of data into an outgoing packet of data, the data from each of the multiple incoming packets being a linear combination of an original set of data vectors and each of the multiple incoming packets including incoming metadata indicating the linear combination of the original set of data vectors present in each of the multiple incoming packets, wherein the metadata comprises a synchronization information and a linear combination coefficient; and

recording into the outgoing packet, based on the linear combination performed on the data and the linear combination coefficient of the metadata from the multiple incoming packets, outgoing metadata indicating the linear combination of the original set of data vectors and the linear combination coefficient of the metadata present in the outgoing packet.

13. The system of claim 12, wherein the node is further capable of:

receiving the incoming packets of data; and

sending the outgoing packet of data.

14. The system of claim 12, wherein the node includes a computer server.

15. The system of claim 12, wherein the node includes a computer.

16. The system of claim 12, wherein the node includes a router.

17. One or more computer-readable media encoded with computer-executable instructions that perform the following when executed by a computer:

receiving incoming packets of data and metadata, the data of each incoming packet being a linear combination of an original set of data vectors, the data vectors in the original set of data vectors being identically partitioned into a first number of layers of data, wherein at least one of the data vectors contains a layer of data that is set to elements computable from the other data vectors;

determining, based on the metadata in each of the incoming packets, the linear combination of the original set of data vectors that is present within each of the incoming packets; and

inverting the data in each of the incoming packets to obtain a second number of layers of data of the original set of data vectors, wherein the second number is less than the first number.

18. The computer-readable media of claim 17, wherein the elements computable from the other data vectors are zero.

19. The computer-readable media of claim 17, wherein the metadata of each incoming packet indicates the linear combination of the original set of data vectors that is present within the incoming packet.

20. An apparatus comprising:

means for receiving incoming packets of information, each of the incoming packets having incoming data and incoming metadata, each of the incoming data being a linear combination of an original set of data vectors and each of the incoming metadata indicating the linear combination present in each of the incoming data, wherein the incoming metadata comprises a synchronization information and a linear combination coefficients;

means for linearly combining the incoming data and the linear combination coefficients of the incoming metadata of the incoming packets of information into an outgoing packet of information; and

means for recording outgoing metadata within the outgoing packet, the outgoing metadata indicating a linear combination of the original set of data vectors present in the outgoing packet.

21. The apparatus of claim 20, further comprising:

means for disassembling, with aid from the outgoing metadata, the linear combination within the outgoing packet into the original set of data vectors.