DETERMINISTIC DISTRIBUTED NETWORK CODING

• US 20140016469A1
• Filed: 07/12/2013
• Published: 01/16/2014
• 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
• Granted Patent: US 9,699,104 B2
• Time in Patent Office: Days
• US Class Current: 370/235
• 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 network comprising:

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

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

coding nodes, allowing communication of the source processes to each receiver node, the coding nodes being 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,

wherein the output signals from a coding node are a linear combination of the input signals and wherein coefficients of the linear combination are deterministically chosen based on local information available locally at the coding node.

2. The network of claim 1, wherein

the overall linear combination of source processes present in each signal in the network is specified as a vector of coefficients, each coefficient corresponding to a source process, and

the vector of coefficients is transmitted through the network and updated at 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 network.

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

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

5. The network of claim 1, wherein the coefficients of the linear combination are deterministically chosen based on a mapping of the local information through a deterministic function.

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

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

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

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

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

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

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

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

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

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

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

17. A network comprising:

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

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

coding nodes, allowing communication of the source processes to each receiver node, the coding nodes being 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,

wherein the output signals from a coding node are a linear combination of the input signals and wherein coefficients of the linear combination are deterministically chosen based on an adjustable mapping through a deterministic function.

18. A method for transmitting processes from one or more sources to each receiver of one or more receivers in a network, the method comprising:

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

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

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

wherein the vector of coefficients is transmitted through the network and updated at 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 network.

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

20. The method of claim 18, wherein the network comprises cycles and delays.

21. The method of claim 18, wherein the network is a computer network.

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

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

24. The method of claim 22, wherein the coefficients of the linear combination are deterministically chosen based on a mapping of the local information through a deterministic function.

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

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

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

28. The method of claim 18, wherein at least some deterministically chosen coefficients of an output signal of a first coding node along a first outgoing link of the first coding node are linearly independent from deterministically chosen coefficients of an output signal of the first coding node along a second outgoing link of the first coding node.

29. The method of claim 18, wherein at least some deterministically chosen coefficients of an output signal of a first coding node along an outgoing link of the first coding node are linearly independent from deterministically chosen coefficients of an output signal of a second coding node along an outgoing link of the second coding node.

30. The method of claim 18, wherein at least some deterministically chosen coefficients from a first output signal of a first coding node along an outgoing link of the first coding node at a first time are linearly independent from deterministically chosen coefficient from a second output signal of the first coding node along the outgoing link of the first coding node at a second time.