Presentation Description

The advantages are plotted out when network coding is used along with routing in internet and how it overcomes the traditional routing only method. The key issues are noted when network coding in kept in to practice


Presentation Transcript

A Presentation onNetwork coding for internet and wireless networks : 

A Presentation onNetwork coding for internet and wireless networks Presented by: Ravi Teja Reddy Levaka 209cs2089 M.Tech 1st Yr Information Security. 1

What is Network Coding? How it overcomes the traditional method ie; routing only in internet? Potential Advantages Issues in practical Network Coding in Wireless Networks. How it is useful in real-time applications? 2

Network Coding : 

Network Coding 3

Network coding Advantages : 

Network coding Advantages Maximize throughput Minimize average energy required per bit Minimize delay in the network 4

Slide 5: 

let a network (,,) be represented by a set of nodes (or vertices) , a set of directed links (or edges) , and real-valued capacities () on each link ∈ let a session (,) be represented by a sender ∈ and a set of receivers ⊆. r (s,t) is the achievable rate of capacity for the session communication from s to t. If the set of receivers consists of only a single node , then the session is said to be a unicast session otherwise multicast session. 5

Maximizing throughput : 

Maximizing throughput B bits per second of uniform capacity c – d: bottleneck link 6

Slide 7: 

At what rates r1 and r2 , the two sessions communicate reliably? Achievable rates: {(r1,r2):0<=r1,0<=r2,r1+r2<=B} {(r1,r2): 0<=r1<=B, 0<=r1<=B} Capacity region is the set of all achievable rates for the sessions in the network. 7

Slide 8: 

“Is the vector of communication rates (1,…,) for a multicast session {(S1,T1),….(Sn,Tn)} achievable, or not?” is still a difficult problem. However, for a single session in network (v,e,s) the capacity region [0,c] is well characterised. 8

Single session network coding : : 

Single session network coding : UniCast case: ≤ MinCut(s,t) BroadCast case: ≤ min∈ (,). Multicast case: < min∈ (,). 9

Unicast case: : 

Unicast case: r(s,t) <= MinCut(s,t) Menger’s Theorem: (unit-capacited edges) 10

Broadcast case: : 

Broadcast case: Edger proved that the maximum number of edge-disjoint directed spanning trees rooted at is equal to min∈(,) So the achievable rate (,V) ≤min∈ (,). By routing information over these spanning trees, we can achieve reliable broadcast from to at the maximum possible rate, (,) =min∈ (,) . 11

Multicast case: : 

Multicast case: 12

Slide 13: 

Upper bound rate cant be achieved in Multicast case. But with network coding it is possible. What is multicast capacity here. Linear Network coding is sufficient to achieve the multicast capacity. Using linear network coding, the multicast capacity in a directed network can always be achieved, and the coding coefficients necessary to achieve the capacity can be computed in polynomial time. In contrast, if only routing can be used, not only is it generally impossible to achieve the multicast capacity, but computing the set of edge-disjoint multicast trees necessary to achieve the best possible routing is a problem that is NP-hard in general. 13

Minimizing energy per bit : 

Minimizing energy per bit 14

Minimizing delay : 

Minimizing delay 15

Practical Network Coding : 

Practical Network Coding Making network coding practical relies on three key ideas: random coding, packet tagging, and buffering. But before, the general algebraic framework behind Linear Network coding should be framed. 16

Local and global encoding vectors : 

Local and global encoding vectors consider an acyclic network (,,) with unit capacity edges, i.e., ()=1 for all ∈, meaning that each edge can carry one symbol per unit of time. Assume also that each symbol is an element of a finite field . Let there be a single sender ∈ and a set of receivers ⊆. Let h=(,) be the multicast capacity. Let 1,…,h be the h symbols that we wish to multicast from to in each unit of time. 17

Slide 18: 

() = [′(e)] () = () g 18

Random encoding : 

Random encoding This is the first key idea towards making network coding practical, since each node can, in a distributed way, choose its own encoding coefficients at random, independently of the other nodes. Based on the uniformity and randomness, the invertibility of the global encoding vector matrix varies. 19

Packet tagging : 

Packet tagging Symbols are grouped into packets. Packets are viewed as vector of code symbols. By prefixing the th information vector with the th unit vector and applying the usual algebraic operations to the resulting vector,each packet is automatically tagged with the appropriate global encoding vector ,since Benefit of the tag (,) < h : decoding not possible 20

Buffering : 

Buffering 21

Slide 22: 

Packets within a generation can now be synchronized by buffering, which is the third key idea for making network coding practical. 22

An example : 

An example 23

applications : 

applications File download -Bit- Torrent protocol - Avalanche (using network coding) Video on Demand Live Media Broadcast Game Spectating Instant Messaging Distributed Storage 24

Advanced topics : 

Advanced topics Security Resource Optimization Multi-session Network Coding Join network coding and Distributed Source Coding Join network coding and channel coding 25

Joint Network Coding and Channel Coding : 

Joint Network Coding and Channel Coding 26

Conclusion : 

Conclusion ………….to be filled 27

references : 

references Zur allgemeinen Kurventheorie. Menger. 1927, Fund. Math., Vol. 10, pp. 95--115. Ford, L. R. and Fulkerson, D. R. Flows in Networks. Princeton : Princeton University Press, 1962. Note on Maximum Flow through a Network. Elias, P., Feinstein, A. and Shannon, C. E. s.l. : IRE, 1956, Trans. Information Theory, Vol. 2. An Algebraic Approach to Network Coding. Koetter, R. and Médard, M. 5, s.l. : IEEE/ACM, October 2003, Trans. Networking, Vol. 11, pp. 782-795. Linear Network Coding. Li, S.-Y. R., Yeung, R. W. and Cai, N. s.l. : IEEE, 2003, Trans. Information Theory, Vol. 49, pp. 371-381. Polynomial time algorithms for multicast network code construction. Jaggi, S., et al. 6, s.l. : IEEE, 2005, Trans. Information Theory, Vol. 51, pp. 1973-1982. 28

Slide 29: 

Thank U 29