Deterministic distributed network coding

• US 9,699,104 B2
• Filed: 07/12/2013
• Issued: 07/04/2017
• Est. Priority Date: 07/16/2012
• Status: Active Grant

• Current Assignee: Code On Network Coding, LLC
• Original Assignee: Code On Network Coding, LLC
• Inventors: Ho, Tracey C., Effros, Michelle
• Primary Examiner(s): Lai, Andrew
• Assistant Examiner(s): ANDREWS, HOYET H
• Application Number:
  US13/940,703
• Publication Number:
  US 20140016469A1
• Time in Patent Office: 1,453 Days
• CPC Class Codes: H04L 1/0041 Arrangements at the transmitter end
• 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
• CPC Class Codes: H04L 2001/0097 Relays
• CPC Class Codes: H04L 47/38 by adapting coding or compression rate
• CPC Class Codes: H04W 4/38 for collecting sensor information

Abstract

A network and a communication method are described. The network comprises: source nodes, receiver nodes, and coding nodes. The coding nodes are connected with input links for communication of input signals to the coding nodes and output links for communication of output signals from the coding nodes. The output signals are a linear combination of the input signals. The coefficients of the linear combination are deterministically chosen based on local information available locally at the coding node.

Claims

1. A distributed network comprising:

one or more source nodes, wherein source data are observable at the source nodes;

one or more receiver nodes, wherein the source data are observable at the receiver nodes; and

a plurality of coding nodes, allowing communication of the source data to each receiver node, the plurality of coding nodes being connected with input links for communication of input data to the plurality of coding nodes and output links for communication of output data from the plurality of coding nodes,

wherein the output data from each coding node of the plurality of coding nodes are a linear combination of the input data to the said coding node, and wherein coefficients of the linear combination are deterministically locally generated at the each coding node based on local information available locally at the each coding node.

2. The distributed network of claim 1, wherein

an overall linear combination of the source data present in each data in the distributed network is specified as a vector of coefficients, each coefficient corresponding to a source data, and

the vector of coefficients is transmitted through the distributed network and updated at the each coding node by applying to the vector of coefficients linear combinations, wherein the linear combinations applied to the vector of coefficients are the same as the linear combinations applied to data transmitted through the distributed network.

3. The distributed network of claim 1, wherein the local information available locally at the each coding node comprises identifying characteristics of the each coding node or of the input links to the each coding node and output links from the each coding node, and a local time varying signal.

4. The distributed network of claim 3, wherein the identifying characteristics of the each coding node or of the input links or output links comprise arbitrary deterministic node or link indexes.

8. The distributed network of claim 1, wherein the distributed network further comprises bidirectional and/or reverse links.

9. The distributed network of claim 1, further comprising routing nodes, the routing nodes being connected with input links for communication of input data to the routing nodes and output links for communication of output data from the routing nodes, wherein the output data from a routing node are obtained through routing without coding of the input data to the routing node.

10. The distributed network of claim 1, wherein the distributed network is an acyclic network.

11. The distributed network of claim 1, wherein the distributed network comprises cycles and delays.

12. The distributed network of claim 1, wherein the distributed network is a computer network.

13. The distributed network of claim 1, wherein the input data comprise input bits and the output data comprise output bits.

14. The distributed network of claim 1, wherein at least some deterministically locally generated coefficients of an output data of a first coding node along a first output link of the first coding node are linearly independent from deterministically locally generated coefficients of an output data of the first coding node along a second output link of the first coding node.

15. The distributed network of claim 1, wherein at least some deterministically locally generated coefficients of an output data of a first coding node along an output link of the first coding node are linearly independent from deterministically locally generated coefficients of an output data of a second coding node along an output link of the second coding node.

16. The distributed network of claim 1, wherein at least some deterministically locally generated coefficients from a first output data of a first coding node along an output link of the first coding node at a first time are linearly independent from deterministically locally generated coefficient from a second output data of the first coding node along the output link of the first coding node at a second time.

5. A distributed network comprising:

one or more source nodes, wherein source data are observable at the source nodes;

one or more receiver nodes, wherein the source data are observable at the receiver nodes; and

a plurality of coding nodes, allowing communication of the source data to each receiver node, the plurality of coding nodes being connected with input links for communication of input data to the plurality of coding nodes and output links for communication of output data from the plurality of coding nodes,

wherein the output data from each coding node of the plurality of coding nodes are a linear combination of the input data to the said coding node, and wherein the coefficients of the linear combination are deterministically locally generated at the each coding node based on a mapping through a deterministic function of local information available locally at the each coding node.

6. The distributed network of claim 5, wherein the mapping is an adjustable mapping.

7. The distributed network of claim 6, wherein the distributed network further comprises bidirectional and/or reverse links and wherein the adjustable mapping is adjustable through feedback from the receiver nodes.

17. A method for transmitting source data from one or more sources to each receiver of one or more receivers in a distributed network, the method comprising:

providing a plurality of coding nodes between the one or more sources and the one or more receivers; and

providing, for each coding node of the plurality of coding nodes, input links for transmitting input data to the each coding node, and output links for transmitting output data from the each coding node, the output data being a linear combination of the input data;

wherein an overall linear combination of the source data transmitted from the one or more sources present in each data in the distributed network is specified as a vector of coefficients, each coefficient being deterministically locally generated at the each coding node of the plurality of coding nodes based on local information available locally at the each coding node and corresponding to a source data to be transmitted from the one or more sources, and

wherein the vector of coefficients is transmitted through the distributed network and updated at the each coding node by applying to the vector of coefficients linear combinations, wherein the linear combinations applied to the vector of coefficients are the same as the linear combinations applied to data transmitted through the distributed network.

18. The method of claim 17, wherein the distributed network is an acyclic network.

19. The method of claim 17, wherein the distributed network comprises cycles and delays.

20. The method of claim 17, wherein the distributed network is a computer network.

21. The method of claim 17, wherein the local information available locally at the each coding node comprises identifying characteristics of the each coding node or of the input links to the each coding node and output links from the each coding node, and a local time varying signal.

22. The method of claim 21, wherein the identifying characteristics of the each coding node or of the input links to the each coding node and output links from the each coding node comprise arbitrary deterministic node or link indexes.

26. The method of claim 17, further comprising providing routing nodes, the routing nodes being connected with input links for communication of input data to the routing nodes and output links for communication of output data from the routing nodes, wherein the output data from a routing node are obtained through routing without coding of the input data to the routing node.

27. The method of claim 17, wherein at least some deterministically locally generated coefficients of an output data of a first coding node along a first output link of the first coding node are linearly independent from deterministically locally generated coefficients of an output data of the first coding node along a second output link of the first coding node.

28. The method of claim 17, wherein at least some deterministically locally generated coefficients of an output data of a first coding node along an output link of the first coding node are linearly independent from deterministically locally generated coefficients of an output data of a second coding node along an output link of the second coding node.

29. The method of claim 17, wherein at least some deterministically locally generated coefficients from a first output data of a first coding node along an output link of the first coding node at a first time are linearly independent from deterministically locally generated coefficient from a second data of the first coding node along the output link of the first coding node at a second time.

23. A method for transmitting source data from one or more sources to each receiver of one or more receivers in a distributed network, the method comprising:

providing a plurality of coding nodes between the one or more sources and the one or more receivers;

providing, for each coding node of the plurality of coding nodes, input links for transmitting input data to the each coding node, and output links for transmitting output data from the each coding node, the output data being a linear combination of the input data;

wherein an overall linear combination of the source data transmitted from the one or more sources present in each data in the distributed network is specified as a vector of coefficients, each coefficient being deterministically locally generated at the each coding node of the plurality of coding nodes based on a mapping through a deterministic function of local information available locally at the each coding node and corresponding to a source data to be transmitted from the one or more sources, and

wherein the vector of coefficients is transmitted through the distributed network and updated at the each coding node by applying to the vector of coefficients linear combinations, wherein the linear combinations applied to the vector of coefficients are the same as the linear combinations applied to data transmitted through the distributed network.

24. The method of claim 23, wherein the mapping is an adjustable mapping.

25. The method of claim 24, wherein the distributed network further comprises bidirectional and/or reverse links and wherein the adjustable mapping is adjustable through feedback from the receiver nodes.