Create Presentation
Download Presentation

Download Presentation
## Network coding techniques

- - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - - -

**Wireless Systems - Lecture**Network coding techniques Elena Fasolo PhD Student - SIGNET Group fasoloel@dei.unipd.it March, 7th 2004**Definition of network coding (NC)**• Pioneering work: [1] R. Ahlswede, N. Cai, S.-Y. R. Li, and R.W. Yeung, “Network information flow,” IEEE Trans. on Information Theory, vol. 46, no. 4, July 2000. • Improves the performance in data broadcasting • Most suitable setting: all to all communications DEFINITION Network coding is a particular in-network data processing technique that exploits the characteristics of the wireless medium (in particular, the broadcast communication channel) in order to increase the capacity or the throughput of the network**Communication networks**TERMINOLOGY • Communication network = finite directed graph • Acyclic communication network = network without any direct cyclic • Source node = node without any incoming edges (square) • Channel = noiseless communication link for the transmission of a data unit per unit time (edge) • WX has capacity equal to 2**The canonical example (I)**• Without network coding • Simple store and forward • Multicast rate of 1.5 bits per time unit**The canonical example (II)**• With network coding • X-OR is one of the simplest form of data coding • Multicast rate of 2 bits per time unit • Disadvantages • Coding/decoding scheme has to be agreed upon beforehand**b1**C A r B NC and wireless communications (a) • Problem: send b1 from A to B and b2 from B to A using node C as a relay • A and B are not in communication range (r) • Without network coding, 4 transmissions are required. • With network coding, only 3 transmissions are needed (b) (c) b2 b2 b1 C C B A B A**Linear network coding**• When we refer to linear network coding [2], we intend that: The output flow at a given node is obtained as a linear combination of its input flows. The coefficients of the combination are, by definition, selected from a finite field • Coding can be implemented at low computational cost • Moreover, the information traversing a non source node has the following property: The content of any information flowing out of a set of non source nodes can be derived from the accumulated information that has flown into the set of nodes [2] S.-Y. R. Li, R. W. Yeung, and N. Cai, “Linear network Coding”, IEEE Trans. on Information Theory, vol. 49, no. 2, Feb. 2003.**Theoretical model for linear NC**• Graph (V,E) having unit capacity edges • Sender s in V, set of receivers T={t,…} in V Source node of h symbols Intermediate node Destination node**Linear coding phase**Transmitted symbol Local encoding vector Global encoding vector**-1**Decoding phase Node t can recover the source symbols x1, . . . , xhas long as the matrix Gt, formed by the global encoding vectors, has (full) rank h.**Inverting Gt**• Gtwill be invertible with high probability if local encoding vectors are random and the field size is sufficiently large [3] • P = 1 - |F| (where |F| is the cardinality of the finite field of coefficients) • Example: If field size = 216 and |E| = 28 then Gtwill be invertible with probability ≥ 1−2−8 = 0.996 [3] R. Koetter,M.Medard, “An algebraic approach to network coding”, IEEE/ACM Trans. on Networking, Nov.2003**Theory vs. Practice**• Theory: • Symbols flow synchronously throughout network • Edges have unit (or known integer) capacities • Centralized and full knowledge of topology, which is used to compute encoding and decoding functions • Practice: • Information travels asynchronously in packets • Packets subject to random delays and losses • Edge capacities often unknown, time-varying • Difficult to obtain centralized knowledge, or to arrange reliable broadcast of functions • Need for simple solutions, applicable in practice**Practical Random NC**• Main idea [4]: • Select the linear coefficients in a finite field of opportune size in a random way • Send the encoding vector within the same packet • Packetization: Header removes need for centralized knowledge of graph topology and encoding/decoding functions • Nodes stores within their buffers the received packets • Buffering: Allows asynchronous packets arrivals & departures with arbitrarily varying rates, delay, loss [4] P. A. Chou, T.Wu, and K. Jain, “Practical network coding”, in 51st Allerton Conf. Communication, Control and Computing, Oct. 2003.**Practical Algorithm**• Each node receives packets which are a linear combinations of source packets and it stores them into a matrix • Each nodes sends out packets obtained as a random linear combination of packets stored in its buffer • If the matrix of a node has full rank (h) or a submatrix with full rank (r < h) exists, the node can decode h (or r) packets at the same time**Innovative packets or not**• When a node receives a packet, it decides whether to store the packet or discard it • Innovative packet: it increases the current rank of the matrix • Non innovative packet: it does not increase the rank of the matrix. It means that the packet contains redundant information and it is not needed to decode the source packets • Hence, non innovative packets are dropped**Need to synchronize**All packets related to same source vectors x1,…, xhare said to be in the same generation; h is the generation size All packets in same generation are tagged with same generation number (one byte - mod 256 - is sufficient) Generations are useful to take into account the differences in data types, generation instants, priorities, etc. Generations**Packet Format**At source nodes At the intermediated nodes**Transmission opportunity:**generate packet edge Random Combination edge edge Buffer Arriving packets (jitter, loss, variable rate) Asynchronous transmission edge NODE Summarizing**0**aij Observations about the decoding phase • Block decoding: • Collect h or more packets, hope to invert Gt • Early decoding (recommended): • Perform Gaussian elimination after each RX packet • At every node, detect & discard non-innovative packets • Gttends to be lower triangular, so it is typically possible to decode x1,…,xkwith fewer more than k packets • Much shorter decoding delay than block decoding • Approximately constant, independent of block length h It can be decoded**Costs and benefits**• Cost: • Overhead of transmitting h extra symbols per packet • Example: h = 50 and field size = 28 overhead ≈ 50/1400 ≈ 3% • Benefits: • Receivers can decode even if • Network topology & encoding functions are unknown • Nodes & edges added & removed in ad hoc manner • Packet loss, node & link failures with unknown locations • Local encoding vectors are time-varying & random**Energy efficient broadcasting with NC [5]**RING NETWORK • All nodes are senders; all nodes are receivers • Tnc = # transmissions needed to broadcast with network coding • Tw = # transmissions without network coding • Lemma: Tnc/Tw ≥ ½ • Without NC = 6 transmissions (Tw ≥ n - 2) • With NC = Tnc ≥ (n – 1)/ 2 • Achievable by physical piggybacking [5] J. Widmer, C. Fragouli, and J.-Y. L. Boudec, “Low–complexity energy–efficient broadcasting in wireless ad–hoc networks usign network coding”, in Proc.IEEE Information Theory Workshop, Oct. 2004.**Energy efficient broadcasting with NC**GRID NETWORK • Consider grid network (toroidal) • n = m2 nodes • Lemma: Tnc/Tw ≥ ¾ • Without NC = Tw ≥ n2 / 3 • With NC = Tnc ≥ n2 / 4 • Achievable by physical piggybacking**Broadcasting in random networks [6]**• At each node v in the graph is associated a forwarding factor, dv. • Source nodev transmits its source symbols (or packets) • max{ 1, | dv | } times. • An additional time with probability p = dv - max{ 1, | dv | } if p > 0. • When a node receives an innovative symbol (packet), it broadcasts a linear combination over the span of the received coding vectors • int(dv) times • And TX a further copy with probability p = dv – int(dv) if p > 0 • Two heuristics: • dv = k / |N(v)| • dv = k / min |N2(v)| where N2(v) are the number of 2-hops neighbors [6] C. Fragouli, J. Widmer, and J.-Y. L. Boudec, “A network coding approach to energy efficient broadcasting”, Proceedings of INFOCOM06, April 2006.**Simulation results**All to all communication scenario Energy consumption: number of transmissions and receptions needed to gather all the required packets Delay: number of time units needed to decode all the required packets**Summary**• Network Coding can be used in practice • Packetization • Buffering • Generation • Network Coding is being applied to • Internet, Live broadcast, storage, messaging, peer2peer file sharing (“eMULE of the future”), … • Wireless ad hoc, mobile, and sensor networks • Many open issues**Wireless Systems - Lecture**Thank you!