Network coding

Network coding

Network coding is a technique where, instead of simply relaying the packets of information they receive, the nodes of a network will take several packets and combine them together for transmission. This can be used to attain the maximum possible information flow in a network. Network coding is a field of information theory and coding theory.

A brief history

A network is represented by a directed graph $\mathcal{G}=(V, E, C)$. V is the set of nodes or vertices, E is the set of directed links (or edges), and C gives the capacity of each link of E. Let t(s,t) be the maximum possible throughput from node s to node t. It has long been known that t(s,t) is upper bounded by the minimum capacity of all cuts, which is the sum of the capacities of the edges on a cut, between these two nodes.

Karl Menger proved that there is always a set of edge-disjoint paths achieving the upper bound in a unicast scenario, known as the max-flow min-cut theorem. Later, the Ford-Fulkerson algorithm was proposed to find such paths in a polynomial time. Then, Edmonds proved in the paper "Edge-Disjoint Branchings" the upper bound in the broadcast scenario is also achievable, and proposed a polynomial time algorithm.

However, the situation in the multicast scenario is more complicated, and in fact, such an upper bound can't be reached using traditional routing ideas. Ahlswede, et al. proved that it can be achieved if additional computing tasks (incoming packets are combined into one or several outgoing packets) can be done in the intermediate nodes.[1]

In 2003, Li, et al. proved that linear coding is enough to achieve the upper bound in multicast problems [2] In 2005, Randall Dougherty, Chris Freiling, and Ken Zeger showed that the linear coding is not sufficient in general (multisource, multisink with arbitrary demands), even for more general versions of linearity such as convolutional coding, filter-bank coding, etc.[3]

Linear network coding

In a Linear Network coding problem, a group of nodes P are involved in moving the data from S source nodes to K sink nodes. Each node generates a new packet, which is a linear combination of the earlier received packets on the link, by coefficients in the finite field.

A message generated so Xk is related to the received messages Mi by the relation:

$X_k = \sum_{i=1}^{S}g_k^i\cdot M_i$

Each node forwards the computed value Xk along with all the coefficients used in the kth level, $g_k^i$.

The values $g_k^i$ are the coefficients from the Galois field GF(2s). Since the operations are computed in the finite field, the result of the operation is also of the same length, as the size of each vector M.

Each node produces a similar output, as computed above. This yields a linear problem of the type X = GM, where with the knowledge of the X,G we need to compute M. Each of the receivers in K, try to solve this linear equation, and for which at least $N \ge S$ packets must be received. The received packets are continually used in the Gaussian elimination method to reduce G matrix into the row-echelon form. Finally the resulting values of X = GechelonM are solved to obtain M.

Example

Butterfly Network.

In the butterfly network, there are two sources (at the top of the picture), each having knowledge of some value A and B. There are two destination nodes (at the bottom), which each want to know both A and B. Each edge can carry only a single value (we can think of an edge transmitting a bit in each time slot).

If we only used routing, then the central line would be able to carry A or B, but not both. Suppose we send A through the center; then the left destination would receive A twice and not know B at all. Sending B poses a similar problem for the right destination. We say that routing is insufficient because no routing scheme can transmit both A and B simultaneously to both destinations.

Using a simple code, as shown, we do get both A and B to both destinations simultaneously by sending the sum of the symbols through the center (in other words, we encode A and B using the formula "A+B"). The left destination receives A and A+B, and can find B by subtracting the two values. This is a linear code because the encoding and decoding schemes are linear operations.

Throughput

At the middle of the butterfly network, 3 messages are being transmitted (A, A+B, B). However 4 messages are being received at the endpoints at the bottom (receive 4 messages for the cost of 3 messages, Note that a message storage in the middle center router could store messages A and B and still provide all 4 messages to the endpoints (receive 4 messages for the cost of 2 messages, a 100% improvement).

Random network coding

Random Network Coding relies on using random codes at nodes for multicast or in cast networks. It was originally proposed in - T. Ho, R. Koetter, M. Medard, D. R. Karger and M. Effros, "The Benefits of Coding over Routing in a Randomized Setting" 2003 IEEE International Symposium on Information Theory. In random network coding, interior network nodes independently choose random linear mappings from inputs to outputs. The effect of the network is that of a transfer matrix from sources to receivers. To recover symbols at the receivers, we require sufficient degrees of freedom – an invertible matrix in the coefficients of all nodes. Receiver nodes can decode if they receive as many independent linear combinations as the number of source processes.

Coding-aware routing

The example of coding-aware routing was first proposed in ROCX.[4] Consider the scenario in Fig. 2 with three flows f1 : 2→1, f2 : 1→3, f3 : 3→2. If all the links are perfect with no loss, the corresponding shortest paths are 2→5→7→4→1, 1→4→7→6→3, and 3→9→8→2 respectively. Without coding, the total number of transmissions needed to deliver one packet of each flow is 11. Under COPE, since nodes 4, 5 and 6 can not overhear each other, there is only one coding opportunity at node 4 as node 1 and node 7 exchange packets through node 4, reducing the total from 11 to 10. On the other hand, if the route of f3 is changed to 3→6→7→5→2, we need no more than 9 transmissions. Though this path has one more hop (one more transmission) than the shortest path, it creates coding opportunities at nodes 5 and 6. This leads us to investigate the extent of gain possible when routing is performed with the awareness of coding opportunities.

Applications

Network coding is seen to be useful in the following areas:

• Alternative to forward error correction and ARQ in traditional and wireless networks. eg: Multi-user ARQ[5]
• Robust and resilient to network attacks like snooping, eavesdropping or replay attacks.[6]
• Digital file distribution and P2P file sharing. eg: Avalanche from Microsoft
• Throughput increase in wireless mesh networks. eg : COPE,[7] Coding-aware routing[8][9]
• Bidirectional low energy transmission in wireless sensor networks.
• Many-to-many broadcast network capacity augmentations.
• Buffer and Delay reduction in spatial sensor networks: Spatial buffer multiplexing [10]
• Reduce the number of packet retransmission for a single-hop wireless multicast transmission, and hence improve network bandwidth.[11]
• Packet collision.[12]

Network coding and Peer-to-Peer Networks

Network coding may be used in a peer-to-peer network to reduce the amount of routing information required by peers to achieve near optimal throughput[citation needed]. In large networks this can be a significant advantage, since otherwise the amount of routing overhead would scale with the size of the network. Unlike scenarios such as the butterfly network example above, network coding does not increase the maximum achievable throughput of a peer-to-peer network.[13]

However there are several difficulties when utilising network coding in peer-to-peer networks.

• A peer may need to spend a large amount of time and resources decoding received data.
• It can be difficult to ensure the uniqueness of the coefficients when there are many pieces in the transferred data.
• The topology of a peer-to-peer network is constantly changing through the addition and removal of peers.

• Secret sharing protocol
• Homomorphic Signatures for Network Coding

References

Wikimedia Foundation. 2010.

См. также в других словарях:

• Coding theory — is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error correction and more recently also for network coding. Codes are studied by various scientific… …   Wikipedia

• Network Crack Program Hacker (NCPH) Group — Formation 1994 (1994) Type hacker group Location Sichuan Province, China Membership 4 core members, aprox. 10 members ( …   Wikipedia

• Network Abstraction Layer — The Network Abstraction Layer (NAL) is a part of the H.264/AVC Video Coding Standard. The main goal of the H.264/AVC NAL is the provision of a network friendly video representation addressing conversational (video telephony) and non… …   Wikipedia

• Network operations center — Overview of a typical NOC. Lot of monitors (front), backbone overview (back) and news broadcast on TV set (right) A network operations center (or NOC, pronounced like the word knock ) is one or more locations from which control is exercised over… …   Wikipedia

• Network Voice Protocol — NVP redirects here. For other uses, see NVP (disambiguation). The Network Voice Protocol (NVP) was a pioneering computer network protocol for transporting human speech over packetized communications networks. It was an early example of Voice over …   Wikipedia

• Omega network — An Omega network is a network configuration often used in parallel computing architectures. It is an indirect topology that relies on the perfect shuffle interconnection algorithm. Omega network with 8 processing elements Contents …   Wikipedia

• Advanced Audio Coding — AAC redirects here. For other uses, see AAC (disambiguation). Advanced Audio Codings iTunes standard AAC file icon Filename extension .m4a, .m4b, .m4p, .m4v, .m4r, .3gp, .mp4, .aac Internet media type audio/aac, audio/aacp, au …   Wikipedia

• Long non-coding RNA — Long noncoding RNAs (long ncRNAs) are generally considered (somewhat arbitrarily) as non protein coding transcripts longer than 200 nucleotides. This limit is due to practical considerations including the separation of RNAs in common experimental …   Wikipedia

• Distributed source coding — (DSC) is an important problem in information theory and communication. DSC problems regard the compression of multiple correlated information sources that do not communicate with each other.[1] By modeling the correlation between multiple sources …   Wikipedia

• Neural network — For other uses, see Neural network (disambiguation). Simplified view of a feedforward artificial neural network The term neural network was traditionally used to refer to a network or circuit of biological neurons.[1] The modern usage of the term …   Wikipedia

Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»