System and method for efficient broadcast of information over a network

• US 7,408,938 B1
• Filed: 01/05/2004
• Issued: 08/05/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., Wu, Yunnan
• Primary Examiner(s): Backer; Firmin
• Assistant Examiner(s): Faroul; Farah
• Application Number:
  US10/751,690
• Time in Patent Office: 1,674 Days
• Field of Search: 370/473, 370/474, 370/394, 370/395.41, 370/389
• US Class Current: 370/394
• CPC Class Codes: H04H 20/42 Arrangements for resource management
• CPC Class Codes: H04H 20/82 using signals not modulated onto a carrier
• CPC Class Codes: H04L 1/0076 Distributed coding, e.g. network coding, involving channel coding coding in both space and time H04L1/0618; cooperative diversity H04B7/022

Abstract

A system and method that can receive, buffer, and asynchronously combine data from various incoming data packets is disclosed. The system and method can do so by, first, receiving incoming packets of one or multiple generations that have incoming data and incoming metadata, with the incoming data of each of the incoming packets that are of a first generation being a combination of a first, original set of data vectors, and the incoming metadata of each of the first generation of incoming packets including an indicator for the first generation. Second, once these incoming packets are received, the system and method can buffer them based on the indicator and, asynchronously from the receiving and buffering, combine the incoming data in the buffered, first generation incoming packets into outgoing data in an outgoing packet.

Claims

1. A computer-readable medium comprising computer-executable instructions that perform the following when executed by a computer:

Receiving incoming packets of one or more generations, each of the incoming packets having incoming data and incoming metadata, the incoming data of each of the incoming packets that are of a first generation of the one or more generations being a linear combination of a first original set of data vectors;

Buffering the first generation incoming packets;

Asynchronously from the receiving and buffering, combining the incoming data in the buffered, first generation incoming packets into outgoing data in an outgoing packet, wherein the combining comprises linearly combining the incoming data in the buffered, first generation incoming packets into the outgoing data in the outgoing packet;

Performing a Gaussian elimination on data of the incoming packets as each packet is received; and

Decoding data in the incoming packets before all data packets of a particular generation are received.

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

including outgoing metadata in the outgoing packet, the outgoing metadata including an indicator for the first generation.

3. The computer-readable medium of claim 1, further comprising flushing the buffered, first generation incoming packets.

4. The computer-readable medium of claim 3, wherein the flushing is performed after receiving an incoming packet of a second generation on any incoming edge.

5. The computer-readable medium of claim 3, wherein the flushing is performed after receiving incoming packets of a second generation on every incoming edge from a higher node.

6. The computer-readable medium of claim 5, further comprising determining whether the higher node is higher using a strongly-connected-component analysis and a topological sort.

7. The computer-readable medium of claim 6 wherein the flushing is performed in accord with a pre-determined schedule.

8. The computer-readable medium of claim 7, wherein the pre-determined schedule is an optimization.

9. The computer-readable medium of claim 8, wherein the optimization is a mathematical program.

10. The computer-readable medium of claim 9, wherein the mathematical program is a linear program.

11. The computer-readable medium of claim 1, wherein the combining includes use of a random multiplier.

12. The computer-readable medium of claim 1, wherein the combining restricts the outgoing data to a subspace of the outgoing packet.

13. The computer-readable medium of claim 1, wherein the incoming packets are received through different channels and are of different generations, and the buffering includes use of different buffers for the incoming packets of different generations received through the different channels.

14. A system comprising:

Multiple intermediate nodes of a communication network, wherein each of the intermediate nodes is configured for;

Receiving from another node in the communication network, multiple incoming packets of data and metadata, the data in each of the multiple incoming packets being a linear combination of an original set of data vectors present in a packet; and

the metadata in each of the multiple incoming packets indicating the linear combination of the original set of data vectors present in the packet;

Linearly combining the data in the multiple incoming packets into outgoing data in an outgoing packet;

Recording outgoing metadata in the outgoing packet indicating the linear combination of the original set of data vectors present in the outgoing packet; and

Sending the outgoing packet; and

A receiver node of the communication network, wherein the receiver node is configured for;

Receiving from one or more intermediate nodes, two or more of the outgoing packets; and

Performing a Gaussian elimination on the outgoing data of each of the outgoing packets as each of the outgoing packets is received, based on the outgoing metadata in each of the outgoing packets.

15. The system of claim 14, wherein the receiver node is further configured for recovering a data vector in the original set of data vectors prior to receiving a number of the outgoing packets equal to a number of data vectors in the original set of data vectors.

16. The system of claim 14, wherein the receiver node is further configured for inferring, as each of the outgoing packets is received, whether the outgoing data in the received outgoing packet contains information not present in the outgoing packets previously received.

17. The system of claim 14, wherein the receiver is further configured for inferring, after one of the outgoing packets is just received, whether the outgoing data in the just-received outgoing packet contains information not present in the outgoing packets previously received, and estimating a rate of receiving outgoing packets inferred to contain information not present in the outgoing packets previously received.