Seminar Report On

NETWORK CODING

Submitted by
SIYAMOL CHIRAKKAROTTU
DEPARTMENT OF COMPUTER SCIENCE
COCHIN UNIVERSITY OF SCIENCE AND TECHNOLOGY
KOCHI-682022
2007 2
ABSTRACT
The essence of network coding is a paradigm shift to allow coding at intermediate nodes between the source and the receivers in one or multiple communication sessions. The fundamental insight of network coding is that information to be transmitted from the source in a session can be inferred, or decoded, by the intended receivers, and does not have to be transmitted verbatim. Network coding has been recently proposed in information theory as a new dimension of the information multicast problem that helps achieve optimal transmission rate or cost. End hosts in overlay networks are natural candidates to perform network coding, due to its available computational capabilities. . Network coding provides the features like minimize latency, increased throughput, bandwidth efficiently etc in both wireless and wired networks With network coding, intermediate nodes between the source and the receivers of an end-to-end communication session are not only capable of relaying and replicating data messages, but also of coding incoming messages to produce coded outgoing ones. Recent studies have shown that network coding is beneficial for peer-to-peer content distribution, since it eliminates the need for content reconciliation, and is highly resilient to peer failures. I would like to present the important features of network coding, the major algorithms with which it is implemented, and the applications of network coding. KEYWORDS: Linear network coding, PDP algorithm, encoding, XOR based algorithm; Reed Solomon based coding, CODEB, applications of network coding, limitations.
1. INTRODUCTION
A communication network is a finite directed graph, where multiple edges from one node to another are allowed and the edges represent pathways for information. A node without any incoming edges is called a source node. Any other node is called a non-source node . Using the max-flow min-cut theorem, one can calculate the maximum amount of information that can be pushed through this network between two nodes . For a single-source multiple-terminal network, the information rate to each terminal is the minimum of the individual max-flow bounds over all source“terminal pairs under consideration and that in general we need to code over the links in the network to achieve the maximum capacity. It was shown that this max-flow value is achievable, but that routing is not capable of achieving it. Network coding is a field of information theory and coding theory and is a method of attaining maximum flow in a network. The core notion of network coding is to allow mixing of data at intermediate network nodes. A receiver sees these data packets and deduces from them the messages that were originally intended for that data sink. The fundamental concept of network coding was introduced for satellite communication networks. The theory of network coding has been developed in various directions, and new applications of network coding continue to emerge. Network coding can be implemented in both cyclic and acyclic networks
2. NETWORK CODING
The capacity of direct transmission from a node to a neighbour is determined by the multiplicity of the channels between them. A source node generates a message, which is propagated through the network in a multi-hop fashion. How much information is passed and how fast it can be received by the destination nodes depend on the channels between the nodes. However, this depends on the nature of data processing at the nodes in relaying the information. Consider a communication network where one source node wants to transmit information through a network to multiple terminal nodes.
Assume that two data bits b1 and b2 are from the source node S to both the nodes Y and Z in the acyclic network. Every channel carries either the bit b1 or the bit b2. Every channel carries either the bit b
1 or the bit b
2.Here maximum information flow is achieved by channel multiplicity between intermediate nodes. Multiplicity of channels can be reduced by applying network coding. Network coding on the butterfly network If we only used routing, then the central line would be able to carry b1 or b2, but not both. Suppose we send b1 through the center; then the left destination would receive b1
twice and not know b2 at all. Sending b2 posses a similar problem for the right
destination.Thus network coding allows mixing of data at the intermediate nodes to
reduce channel multiplicity
Network coding in wireless transmission 9


2.1 WHY NETWORK CODING?
To avoid repeated usage of same channel To minimize latency and energy consumption To maximize bit rate Improve transmissions efficiency in used n/w To increase throughput To use the bandwidth efficiently 2.2 LINEAR NETWORK CODING Encoding function maps the received symbols from all incoming channels to a symbol for each outgoing channel.
2.2.1
Local description of a linear network code on an acyclic network For every node T, let In (T) denote the set of incoming channels to T and Out (T) the set of outgoing channels from T. Meanwhile, let In(S) denote a set of imaginary channels, which terminate at the source node S but are without originating nodes. The number of these imaginary channels is context dependent and always denoted by w. Let F be a finite field and w be a positive integer. An w-dimensional F-valued linear network code on an acyclic communication network consists of a scalar kd,e, called the local encoding kernel, for every adjacent pair (d,e). Meanwhile, the local encoding kernel at the node T means the |In(T)| × |Out(T)| matrix KT = [kd,e]d?In(T),e2Out(T). The vector fe is called the local encoding kernel for the channel e. 2.2.2 Global description of a linear network code on an acyclic network Let F be a finite field and w a positive integer. An w-dimensional F-valued linear network code on an acyclic communication network consists of a scalar kd,e for every adjacent pair(d,e) in the network as well as an w-dimensional column vector fe for every channel e such that:
fe =Sd?In(T) kd,efd, where e ? Out(T). The vectors fe for the w imaginary channels e ? In(S) form the natural basis of the vector space Fw The vector fe is called the global encoding kernel for the channel e.The vector fe is called the global encoding kernel for the channel e.
3. NETWORK CODING BASED BROADCAST IN MOBILE
ADHOC NETWORKS
Ad-hoc networks, a concept different from and complimentary to fractured networks, can improve the system performance significantly by relaying signals in multiple hops between the source and the destination without any central control. As a cost to the flexibility of ad-hoc networks, ad-hoc networks suffer from the complexity of the routing problem, which is a critical issue to the system performance. From the coding perspective, however, repeating the message bit-on-bit is very inefficient, since repetition codes are the weakest type of practical codes. A varietyof insightful network examples have been constructed, first in the context of lossless networks and later extended to lossy and wireless networks, which demonstrate that (i) the traditional routing strategy does not come close to achieving the communication capacity in network settings, and (ii) network coding, generalization of repetition- forwarding by allowing intermediate relaying nodes to perform intelligent packet combining in the symbol level, is crucial in delivering end-to-end optimal network performance networks. Hence, networking coding can also be considered as generalization of routing.
Network coding, allow each relay node in the ad-hoc networks to gather all they hear from previous hops, decode segments altogether, and reencode and transmit a different (sub-) codeword. Hence, the message propagates along the route from the source to the destination in a wave-like fashion: The destination will, conceptually, receive all the (sub) codewords from the original source as well as each and every participating relay along the route, however weak some signals may be. It can therefore launch an iterative decoding by treating the (sub) codewords as outputs from the parallel branches of a giant parallelly concatenated (network) code. In practice, depending on the length of the routes and the severity of signal attenuation, it may suffice for the destination to include only the last few (sub) codewords in its iterative decoding. Mobile ad hoc networks (MANETs) enable communication between a group of nodes to form a network in absence of infrastructure components such as base stations and power sources. Efficient support for group broadcast semantics, where data is sent to all or most of the nodes, is critical for these networks . Using broadcasting not all nodes need to transmit in order for the message to reach every node. Efficient broadcast support in mobile Adhoc networks has proceeded along two main approaches : Probabilistic (each node rebroadcasts a packet with a given probability) Deterministic approaches (nodes pre-select a few neighbors for rebroadcasting) Probabilistic or gossiping-based approaches require each node to rebroadcast the packet to its neighbors with a given forwarding probability. The key challenge with these approaches is to tune the forwarding probability: keeping it as low as possible for maximum efficiency while maintaining it high enough, so that all the nodes are able to receive the broadcast packets. Deterministic approaches predetermine and select the neighboring nodes that forward the broadcast packet. Network coding allows intermediate nodes to combine packets before forwarding.
Network coding is adapted to a probabilistic approach for supporting broadcast in mobile ad hoc networks. This approach has several drawbacks. Fine-tuning the forwarding probability in probabilistic approaches is a hard problem - in order to ensure that most nodes receive the broadcast, one typically chooses a higher forwarding probability that results in inefficiencies compared to a deterministic approach. Also, this approach in has to group packets transmitted from various sources into globally unique sets called generations - solving this in a distributed manner is a hard problem and limits coding gains. Furthermore, the use of a globally unique set of coded packets implies that decoding delay can be large.
Network-coding can be applied to a deterministic broadcast approaches, resulting in significant reductions in the number of transmissions in the network. Coding can be implemented in the partial dominant pruning (PDP)-based deterministic approach. The three steps in network coding are Packet encoding, packet decoding and Pruning
3.1. PARTIAL DOMINANT PRUNING (PDP) ALGORITHM
Network coding can be applied to PDP algorithm in deterministic broadcast approach. In this algorithm 2 hop neighbourhood nodes ie adjacent to adjacent nodes are selected for retransmission Let N(u) represents neighbour nodes of node u and N(v) represents neighbour nodes of node v .Nodes for retransmission are selected as N (N (v)) - N (v) - N (u) - (N (u) nN (v)) All the nodes are represented in a neighbor reception table, in the basic PDP algorithm. Coding is implemented either using XOR based algorithm or Reed Solomon based algorithm.
3.2 PACKET ENCODING
Network coding has been adapted to support unicast and multicast applications in wireless networks. It is implemented using two algorithms which rely on local two-hop topology information and makes extensive use of opportunistic listening to reduce the number of transmissions.
1) A simple XOR-based coding algorithm that provides up to 45% gains compared to a non-coding approach.
2) A Reed-Solomon based coding algorithm that determines the optimal coding gain achievable for a coding algorithm that relies only on local information, with coding gains up to 60%.
3.2.1 XOR-based coding algorithm XOR based algorithm is the simplest algorithm to encode the data packets. In this algorithm if the neighbor reception table of a node u is accurate and u sends an XORed packet p, a neighbour v of u should be able to decode p using stored native packets. That is, a XOR-ed packet can be decoded by each of uâ„¢s neighbour without waiting for further coded packets to arrive. In more detail each node u with a set of native packets P in its output queue seeks to find a subset of native packets Q to XOR. XOR based coding algorithm for node u is illustrated below. getCodeSet () 14


10
Pick packet p at the head of the output queue
1 B=p
2 for each remaining packet q in the Queue
3 for each neighbour v
4 if (cannotdecode(p XOR q) then
5 go to line 10
6 endif
7 endfor
8 B=B U q
9 p=p XOR q
10 continue
11 endfor
12 return B
The packets are encoded using XOR algorithm and send to the receiver. The packets are stored in a packet pool at the receiver and each of these packets is identified with a packetID and decoded. 3.2.2 Reed - Solomon based algorithm The Reed-Solomon code (RScode) based algorithm is an optimal algorithm. It r educes the no. of coded transmission along the network. Reed-Solomon codes are the most popular codes in practical use. Their main advantage lies in two facts: high capability of correcting both random and burst errors; and existence of efficient decoding algorithm for them. A packet p denotes the vector where each element in index i is the corresponding byte in p. An ordered set of packets P also denotes the matrix where row i corresponds to the ith packet in P.
Theorem:
Let P be the ordered set of n native packets in uâ„¢s output queue. Let Pv be the set of packets v received for each v in N (u).Let k = max {P-Pv, v in N (u)}.Let O be k x n Vandermonde matrix, representing reed Solomon code. Then the minimal number of encoded packets that needs to send such that each neighbour v can decode the packets in P-Pv is k and the set of k packets are given by Q = O x P
getcodeSet( )
Pick native packet set P in the output queue
K=maxMissingPackets(N(u),P)
Construct encoded packetset Q=AP
Add packetID of each packet to qi
Add the row matrix i of A to qi
Return( );
Coding procedure for node u using Reed Solomon code
3.3 PACKET DECODING
Each node maintains a Packet Pool, in which it keeps a copy of each native packet it has received or sent out. The packets are stored in a hash table keyed on packet ID, and the table is garbage collected every few seconds. When a coded packet is received, the node decodes and then processes the packet. In the case of the XOR-based algorithm, when a node v receives an encoded packet consisting of n native packets the nodes go through the IDs of the native packets one by one and retrieves the corresponding packets from its packet pool if possible. In the end it XORs the n-1 packets with the received encoded packets to retrieve the missing packet .thus node can process the packet q.
For Reed Solomon based algorithm, when a node v receives an encoded packet consisting of n native packets, v first goes over all native packets received in packet pool. It collects Pv, the subset of packets in P, that it has already received. It then constructs Av, and adds the new coefficient vector to matrix Av. For each decoded native packet q, node v can now process q.
3.4. PRUNING
For each packet p received the reception status of each neighbour u in the neighbour table based on the two hop neighbour set N(N(u)).based on the neighbour table if a node is designated as forwarded for packet p determines that all its neighbours have already received p it can prune that transmission. When receiving a native or coded packet the neighbours of the sender of packet p as having received the native packet or all the packets in the coded packet. For Reed Solomon coded packet this updation prevents a node from purging already scheduled coded packets based on newly snooped packets. The reason is that for a neighbour w to decode the missing packet, resulting in w not receiving any packets. Therefore to prune the scheduled coded packets, the following priority rule node v can assume w in N (u) n N (v) has received all underlying native packets (packetIDs are in the header) if and only if ID(v) >ID(u). This is not needed if all coded packets are transmitted instead of opportunistically purged.
4. CODING BASED BROADCASTING PRTOCOL (CODEB)
CODEB is a new coding-based broadcast protocol for ad-hoc networks. It inserts a coding layer between the IP and MAC layer which detects coding opportunities and exploits them to reduce the number of transmissions needed. CODEB incorporates three main techniques:
Opportunistic listening:
Nodes in CODEB operate in promiscuous mode equipped with omni-directional antennae. Nodes snoop all communications over the wireless medium and store the overheard packets for a limited period T;. Nodes also periodically broadcasts the set of nodes it can hear (i.e., its one-hop neighbors) to all its one-hop neighbors. This allows each node to build a two-hop neighbor graph; given this and the previous hop u of a packet p, node v can infer that the neighbors of v have received p. If p is a coded packet, other inferences are possible as discussed later. Based on this, each node creates a neighbor reception table. If a new packet can not find any coding opportunities, the packet can either be sent to the interface queue directly, or be buffered in the coding layer for sometime. For delay tolerant applications, buffering can increase coding opportunities.
Forwarder selection and pruning:
A subset of neighbors is selected as forwarders. We use the PDP algorithm to select forwarders and maintain forwarder selection independent of coding, thereby allowing our scheme to be used with other forwarder selection algorithms. The forwarder set is stamped in the packet header and a node only rebroadcasts a packet when it is chosen as a forwarder. Note that, due to opportunistic listening, even if a node is a forwarder of a given packet, it does not necessarily have to send it if it determines that all its neighbors have received the given packet.
Opportunistic coding:
Each node examines its set of to-be-forwarded packets and its current neighbor table obtained through opportunistic listening, and dynamically determines if it can exploit coding opportunities to send coded packet, instead of sending native (non- encoded) packet. Two algorithms are used for coding packets: 1) a simple XOR-based algorithm that tries to XOR a number of packets in the buffer to enable the maximum number of nodes to decode a new packet and 2) an optimal coding scheme that makes use of Reed - Solomon code as the coefficients for linearly combining native packets. Note that, opportunistic coding for broadcast is very different from coding for unicast. In unicast, only the intended next hop needs to receive a given packet. However, for broadcast, all the neighbors must receive the given packet.). It is actually the same as finding a maximum hypergraph matching which is also hard to approximate within a constant factor. For the linear code-based solution, there exist optimal and efficient polynomial algorithms for CODEB.
5. APPLICATIONS OF NETWORK CODING
Network coding is seen to be useful in the following areas:
5.1 Alternative to forward error correction and ARQ in traditional and wireless
networks:
Network codes are used for error correction when a source message is transmitted to a set of receiving nodes on a network. The usual approach in existing networks, namely page link by-link error correction, is a special case of network error correction. The network generalizations of the Hamming bound and the Gilbert- Varshamov bound are derived.
5.2 Digital file distribution and P2P file sharing:
Network Coding is practical in a P2P setting since it incurs little overhead, both in terms of CPU processing and I/O activity, and it results in smooth, fast downloads, and efficient server utilization. A prototype Network Coding P2P filecasting system is implemented which provides efficient support against corruption attacks that try to disrupt the download. In P2P systems the benefits of network coding mostly stem from solving the block scheduling problem at large scales. In particular, network coding improves performance when the number of users in the system increases while the information that each node has about others remains constant. More specifically network coding provides the following benefits:
5.2.1 The capacity of the seed server is fully utilized by constantly serving innovative
information:
This is a critical point; at time zero the seed server is the only node holding a copy of the full file. Thus, the download time achieved by the earliest finishing node is lower bounded by the time that it takes to put a single copy of each block in the network. Network coding ensures that this time is optimal since every block served by the server is unique. To guarantee that an individual node does not request a block from the server that has already been requested by other nodes in the system, that individual node needs to know what the other nodes have downloaded and what they are currently downloading. However, a particular node often only knows about the content in the nodes in its neighborhood. As scale increases, the information that each node has about others in the system decreases, thus, increasing the probability of requesting overlapping blocks. The best a node can do is to assume that other nodes in the system have a similar set (or subset) of the blocks existing in its neighborhood and request non-overlapping blocks accordingly.
5.2.2 Innovative information in a node propagates in optimal time to those nodes needing it, regardless of the number of hops between the source and the sink:
Assuming that all nodes have the same capacity, then, the speed at which information propagates over the P2P network is determined by the block selection policies and the distance between nodes. In the case that a given node (source) holds a particular block which is required in other parts of the network (sinks), network coding will ensure that such block will propagate in a number of rounds equal to the distance between the source and the sinks. However, if no coding is used (or even if only source coding is used), then, the nodes in the path may waste several rounds downloading blocks that the sinks already has. For instance if the nodes in the path are empty, they will likely request blocks that the sinks already posses. Compared to traditional approaches, network coding makes optimal use of the available resources in the network without the need for sophisticated scheduling algorithms and provides a high degree of robustness, even if nodes suddenly depart the system or if decisions are based only on partial information.
5.3 Network coding for large scale content distribution:
With network coding, each node of the distribution network is able to generate and transmit encoded blocks of information. The randomization introduced by the coding process eases the scheduling of block propagation, and, thus, makes the distribution more efficient. This is particularly important in large unstructured overlay networks, where the nodes need to make block forwarding decisions based on local information only. File download time improves by more than 20-30% with network coding compared to coding at the server only and, by more than 2-3 times compared to sending unencoded information. Network coding makes optimal use of the available network resources and, moreover, computing a scheduling scheme that achieves such rate is computationally. Every time a client needs to send a packet to another client, the source client generates and sends a linear combination of all the information available to it (similarly to XORing multiple packets). After a client receives enough linearly independent combinations of packets, the client can reconstruct the original information. The decision on which packets to generate and send does not require extra information about the downloads in the rest of the network; thus the content distribution effort is greatly simplified.
5.3 Buffer and Delay reduction in spatial sensor networks: Spatial Buffer
Multiplexing:
To make sensor network deployments economically and technologically feasible, it is necessary to drastically reduce the cost, size and energy consumption of the nodes. By using random linear network coding, achievable throughput of the network is same order as in a fully coordinated network of tuned radios. Network coding reduces latency and unreliability between query time and the time that the desired data is made available to the data collector.
5.5 Throughput increase in wireless mesh networks:
Network coding does have practical benefits, and can substantially improve wireless throughput. Usually All links have a capacity of one message per unit of time. In the case of wireless multihop networks, applying network coding can potentially improve the performance on throughput, energy efficiency and congestion control using network coding a node can potentially deliver to multiple neighboring nodes multiple data flows with a single broadcast transmission.. By sending the XOR of the packets on the middle link, we can deliver two messages per unit of time to both receivers. Network coding provides bidirectional low energy transmission in wireless sensor networks.
5.6 Robust and resilient to network attacks like snooping, eavesdropping or replay attacks. Because coded information is send along the network, network security can be assured up to a limit. Network coding is used for detecting attacks and for checking requirements for robustness. Peer-to-peer content distribution networks can suffer from malicious participants that corrupt content. Architectures that use network coding are prone to jamming attacks where the introduction of a few corrupted blocks can quickly result in a large number of bad blocks propagating through the system. The level of information security provided by random linear network coding in network scenarios in which all nodes comply with the communication protocols yet are assumed is potential to eavesdroppers
6. LIMITATIONS OF Although network coding provides security in data transmission, it has some limitations also. The limitations of implementing network coding are listed below: One peer may need to spend a huge amount of time on decoding data they receive The resources (CPU, etc.) one needs to spend on decoding. Time and effort should be dedicated to decode the coded packets. How to ensure the uniqueness coefficients when there are a lot of file pieces in the transferred file The topology of network is changing in mobile Adhoc networks which results in complexity in coded transmission In P2P networks, Peers may depart the network anytime they want. This causes change in network topology.
7. CONCLUSION
Based on a prototype implementation of our system and the result of several live distributions, network coding overhead is relatively small, both in terms of CPU processing and I/O activity. A scheme for efficient verification of encoded blocks is described and the verification process is very efficient. We also observed a smooth file download progress and very efficient utilization of the server capacity. Network coding becomes more beneficial when more data pieces are combined; Due to the potentially dynamic nature of Adhoc networks, localized algorithms are much more robust and effective with less maintenance overhead. Here we show how to incorporate network coding into a non-coding based localized algorithm called PDP for improving broadcast efficiency. Extensive simulation shows that non-coding based scheme sends as much as 60% more packets with reduced packet delivery ratio. For future work, we intend to explore more on the reliability issue and implement CODEB in a real 802.11-based mobile ad hoc network in order to thoroughly evaluate its efficiency.
8. REFERENCES
[1] C. Fragouli, J. Widmer, and J.-Y. L. Boudec, A network coding approach to energy
efficient broadcasting: from theory to practice, in Proceedings of IEEE INFOCOM, Apr
2006.
[2] Z. Haas, J. Halpern, and L. Li, Gossip-based ad hoc routing, in Proceedings of
IEEE INFOCOM, June 2002.
[3] H. Lim and C. Kim, Flooding in wireless ad hoc networks, Computer
Communications Journal, 2001.
[4] S. Katti, D. Katabi, W. Hu, H. Rahul, and M. Medard, The importance of being
opportunistic: Practical network coding for wireless environments, in Proceedings of
ACM SIGCOMM, Sep 2006.
[5] S. Ni, Y. Tseng, Y. Chen, and J. Sheu, The broadcast storm problem in a mobile ad
hoc network, in Proceedings of ACM MOBICOM, 1999.
[6] I. F. Akyildiz, D. Pompili, and T. Melodia, Challenges for efficient communication
in underwater acoustic sensor networks, vol. 1, July 2004.
[7] P. Chou, Y. Wu, and K. Jain, Practical Network Coding, in Proc. Of Allerton
Conference on Communication, Control, and Computing, October 2003.
[8] wikipedia.org