System and method for efficient broadcast of information over a network

• US 7,760,728 B2
• Filed: 08/04/2008
• Issued: 07/20/2010
• 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, Wu, Yunnan, Chou, Philip A.
• Primary Examiner(s): Pham; Chi H
• Assistant Examiner(s): Faroul; Farah
• Application Number:
  US12/185,720
• Publication Number:
  US 20080291834A1
• Time in Patent Office: 715 Days
• Field of Search: 370/390, 370/432, 370/473
• US Class Current: 370/390
• 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 method, comprising:

determining a sub-network in an asynchronous communication network between a single sender and multiple receivers, wherein the sub-network is defined by a union of flows, and the union of flows is determined by restricting a magnitude of each flow of the union of flows between the sender and the multiple receivers to a same value; and

communicating, in the asynchronous communication network, from the single sender to the multiple receivers over edges in the sub-network,

wherein the determining comprises reducing transmission rates on edges in the asynchronous communication network that lie between the single sender and the multiple receivers that have a low rate of transmission of innovative information.

2. The method of claim 1, wherein the reducing also comprises back-tracking from the multiple receivers to the single sender.

3. The method of claim 1, wherein determining the sub-network comprises eliminating non-contributing edges in the asynchronous communication network.

4. The method of claim 3, wherein the reducing comprises back-tracking contributing nodes from the receivers.

5. The method of claim 1, wherein the sub-network is defined by a union of flows, and the union of flows is determined by using an optimization comprising a linear program, assuming a pricing function regarding a usage of each edge is linear.

6. The method of claim 1, wherein determining the sub-network is performed by a union of flows determined by:

running a distributed max-flow algorithm for every receiver;

adding up communication costs across the receivers; and

reducing the communications costs by computing all flows at a same time;

wherein each message exchange may convey a vector of elementary messages, one for finding a max-flow of each receiver.

7. The method of claim 1, wherein determining the sub-network comprises:

flooding the asynchronous communication network for a first few generations of packets;

collecting sufficient amounts of data to obtain statistics, wherein the statistics obtained including finding what proportions of packets flowing on each edge are innovative; and

restricting the flooding of the asynchronous communication network into a sub-network, wherein the restricting comprises;

eliminating non-contributing edges in the asynchronous communication network; and

back-tracking contributing nodes from the receivers.

8. A method, comprising:

determining a sub-network in an asynchronous communication network between a single sender and multiple receivers, wherein determining the sub-network comprises;

flooding the asynchronous communication network for a first few generations of packets;

collecting sufficient amounts of data to obtain statistics, wherein the statistics obtained including finding what proportions of packets flowing on each edge are innovative; and

restricting the flooding of the asynchronous communication network into a sub-network, wherein the restricting comprises;

eliminating non-contributing edges in the asynchronous communication network; and

back-tracking contributing nodes from the receivers; and

communicating, in the asynchronous communication network, from the single sender to the multiple receivers over edges in the sub-network,

wherein the determining includes restricting a magnitude of each flow in the sub-network between the sender and each of the multiple receivers to a value that is less than or equal to a broadcast capacity.

9. The method of claim 8, wherein determining the sub-network comprises back-tracking from the multiple receivers to the single sender.

10. The method of claim 8, wherein the sub-network is defined by a union of flows, and the union of flows is determined by restricting a magnitude of each flow of the union of flows between the sender and the multiple receivers to a same value.

11. The method of claim 8, wherein the sub-network is defined by a union of flows, and the union of flows is determined by using an optimization comprising a linear program, assuming a pricing function regarding a usage of each edge is linear.

12. The method of claim 8, wherein determining the sub-network is performed by a union of flows determined by:

finding two or more flows, using a distributed algorithm, each from the sender to a receiver;

synchronizing the distributed algorithm for finding two or more flows; and

exchanging combined messages between neighboring nodes.

13. The method, comprising:

determining a sub-network in an asynchronous communication network between a single sender and multiple receivers, wherein determining the sub-network is performed by a union of flows determined by;

running a distributed max-flow algorithm for every receiver;

adding communication costs across the receivers; and

reducing the communications costs by computing all flows at a same time;

wherein each message exchange may convey a vector of elementary messages, one for finding the max-flow of each receiver; and

communicating, in the asynchronous communication network, from the single sender to the multiple receivers over edges in the sub-network,

wherein the determining includes use of a distributed process for finding two or more flows between the sender and the multiple receivers, the distributed process including exchange of messages for each of the flows and combination of the messages for one of the flows with the messages for another of the flows.

14. The method of claim 13, wherein the sub-network is defined by a union of flows, and the union of flows is determined by restricting a magnitude of each flow of the union of flows between the sender and the multiple receivers to a same value.

15. The method of claim 13, wherein the sub-network is defined by a union of flows, and the union of flows is determined by using an optimization comprising a linear program, assuming a pricing function regarding a usage of each edge is linear.

16. The method of claim 13, wherein determining the sub-network is performed by a union of flows determined by:

finding two or more flows, using a distributed algorithm, each from the sender to a receiver;

synchronizing the distributed algorithm for finding two or more flows; and

exchanging combined messages between neighboring nodes.

17. The method of claim 13, wherein determining the sub-network comprises:

flooding the asynchronous communication network for a first few generations of packets;

collecting sufficient amounts of data to obtain statistics, wherein the statistics obtained including finding what proportions of packets flowing on each edge are innovative; and

restricting the flooding of the asynchronous communication network into a sub-network, wherein the restricting comprises;

eliminating non-contributing edges in the asynchronous communication network; and

back-tracking contributing nodes from the receivers.