Network Coding

Network Coding

Sruthi Padmanabhan 2K4625 S7CSE

1

Presentation Flow      

Introduction Basic Concept Linear Network Coding Encoding & Decoding Applications Conclusion

2

Introduction  Conventional networks 

store and forward mechanism

 Goal: To transfer data at the maximum achievable throughput in a network.

 Solution: Network coding 

allow mixing of data at intermediate nodes

3

Basic Concept  Max Flow Min Cut Theorem.  Multicast problem.

4

Graph  Graph G(V,E): consists of a set V of vertices and a set E of edges.  

V consists of sources, sinks, and other nodes A member e(u,v) of E has a capacity c(u,v) to send information from u to v 3 S

A

3

2 3

D

B

2 T

4 2

C

3 5

Min-Cuts and Max-Flows    

Cuts: Partition of vertices into two sets Size of a Cut = Total Capacity Crossing the Cut Min-Cut: Minimum size of Cuts = 5 Max-Flow = Min-Cut

3 S 3

A

A

3 3 3 S2 2 2 D 3 2 D

3 3 2 2

B

32 B 2 2 1 4 3 4T T C 2 3 C 3 6

Max Flow Min Cut Theorem  Max-Flow Min-Cut theorem for network information flow states that the multicast capacity of a network is equal to the minimum value of the max-flows of all the receivers.  The maximum flow in a network is dictated by its bottleneck.

7

Butterfly Network Each edge’s capacity is 1.

8

Multicast Problem  Max-Flow from A to D = 2  Max-Flow from A to E = 2  Multicast Max-Flow from A to D and E = 1.5  Max-Flow for each individual connection is not achieved.

A B

C F

G D

E 9

Network Coding  With network coding, every sink obtains the maximum flow.  Linear network coding is enough to achieve the maximum flow

b1 B

A

b1

b2 b2

C

F b1

b1+b2

b2

b1+b2 G b1+b2 D

E 10

Linear Network Coding  Outgoing packets are linear combinations of the original packets.  Linear combination is not concatenation.  Each encoded packet contains only a fraction of the information contained in original packets.  Blocks of data as a vector over certain base field.

11

Algorithm for linear code multicast For all edges XY V (XY) = zero vector; // initialization Bring all nodes in a topological sort sequence and begin with the first: For j = 0 j<= n, j++ //n: number of nodes; //X{j} is the actual node { For all edges X{j}Y //X{j}Y is the actual outgoing edge { Choose a vector V from the space VR(X{j}):distinction of cases V(X{j}Y) = V; } VR(X{j+1}) := linear span of all vectors that are coming in vector X{j+1} }

case 1: Xj is the source  distribute all unit vectors. case 2: Xj is the sink  do nothing case 3: there is only a single incoming edge WXj to Xj  forward the vector case 4: else-case 

distribute the linear combinations.

12

Algorithm for linear code multicast 1. node S : ST 2. node S : SU 3. node T :TY 4. node T :TW 5. node U :UZ 6. node U :UW 7. node W :WX 8. node X :XY 9. node X :XZ 10. node Y 11. node Z

Case 1 : (1, 0) Case 1 : (0, 1) Case 3 : (1, 0) Case 3 : (1, 0) Case 3 : (0, 1) Case 3 : (0, 1) Case 4 : (1, 1) Case 3 : (1, 1) Case 3 : (1, 1) do nothing do nothing

13

Encoding and decoding  Encoding:

• Assume a node with B1 ,.., Bk blocks • Pick random numbers: c1, c2, …,ck. • Construct: E= c1B1+ c2B2+…+ ckBk. • Send: E and (c1, c2, …,ck).

 Decoding: 

Collect enough linearly independent E’s, solve a linear system. 14

Linear Network Coding  Conventions used   

Source Input: X (v, l) Info. Along Edges: Y (e) Sink Output: Z (v, l)

 Relationship among them

15

Encoding Let x = ( X (v1 ,1), X (v1 ,2), X (v1 ,3)) Y (e1 ) = α 1,e1 X (v,1) + α 2,e1 X (v,2) + α 3,e1 X (v,3) z = (Z (v4 ,1), Ze1(v4 ,2),vZ (v4 ,3)) Y (e2 ) = α 1,e2 X (v,1) + α 2,e2 X (v,2) + α 3,e2 X (v,3) 2 e5 Y (e3 ) = α 1,e3 X (v,1) + α 2,e3 X (v,2) + α 3,e3 X (v,3) z = x ⋅ M X (v1 ,1) e2 Z (v4 ,1) Y (e ) = β Y (e ) + β Y (e ) 4 e1 ,e4 1 e2 , e4 2  vβ e1 ,e5 β ee1 ,e4 β e4e,e66 β e1v,e4 β e4 ,e7 Z (v4 ,2) X (v1 ,2) 4 4 Y (e5 ) = β e1 ,e5 Y (e1 ) + β e2 ,e5 Y (e2 )  1  X (vM ) A ⋅  β e ,e β e ,e β e ,e β e ,e β e ,eZ (⋅ vB4 ,3) 1 ,3= 2 5 2 4 4 6 2 4 4 7 Y (e6 ) = β e3 ,e6 Y (e3 ) + β e4 ,e6 Y (e4 ) e 3 e   7 v β e33,e6 β e3 ,e7  Y (e ) = β Y (e ) + β Y (e )  0

α ε1,e1 ,1  5 AB==α ε2,e1 e6 ,1  αε3,e1



e7 ,1

α ε1,ee2 , 2 α 1ε,ee3 ,3  5 5  αε2,e2 αε2,e3   e6 , 2 e6 , 3  αε3,e2 α ε3,e3   e7 , 2

e7 , 3



7

e3 ,e7

3

e 4 , e7

4

Z (v4 ,1) = ε e5 ,1Y (e5 ) + ε e6 ,1Y (e6 ) + ε e7 ,1Y (e7 ) Z (v4 ,2) = ε e5 , 2Y (e5 ) + ε e6 , 2Y (e6 ) + ε e7 , 2Y (e7 ) Z (v4 ,3) = ε e5 ,3Y (e5 ) + ε e6 ,3Y (e6 ) + ε e7 ,3Y (e7 ) 16

Network Coding Solution z = x⋅M

 We want z = x  β e ,e β e ,e β e , e β e , e β e ,e   Choose A to be an   M = A ⋅  β e , e β e , e β e ,e β e , e β e ,e  ⋅ B identity matrix.   β e ,e β e ,e   Choose B to be the  0 α1,e α1,e α1,e  inverse of  CODING NETWORK A = α 2,e α 2,e α 2,e ,  β e ,e β e , e β e ,e β e ,e β e , e  SOLUTION EXISTS IF     α α α 3, e 3, e   β e , e β e ,e β e , e β e ,e β e , e   3, e DETERMINANT OF M   0 β β ε e ,1 ε e , 2 ε e ,3  e ,e e ,e   IS NON-ZERO   1 5

1 4

4 6

2 5

2 4

4 6

3 6

1

5

2

1 4

2 4

4 7

4 7

3 7

3

1

2

3

1 5

1 4

4 6

1

2

3

2 5

2 4

4 6

5

5

B = ε e6 ,1 ε e6 , 2 ε e6 ,3    ε ε ε e7 , 3   e7 ,1 e7 , 2

3 6

1 4

2 4

4 7

4 7

3 7

17

Advantages  Achieve maximum throughput

18

Advantages  Load balancing and bandwidth utilization

19

Advantages  Robustness and adaptability  Recovery

from link failure without rerouting  Network management overhead in multicast connection is less

20

Disadvantages  The loss of one packet in the network equal several losses at the receiver.  Data can’t be recovered until all the information necessary is received Delay

21

Disadvantages  Synchronization needed for real-time networks  Some centralized knowledge of topology is needed  Can design encoding to withstand failures, but decoders must know failure pattern

22

Applications  P2P file distribution  The

blocks sent out by the server are random linear combinations of all original blocks.  It minimizes download times.  Performance of the system depends much less on the specific

overlay topology and schedule.  Robustness.

 Avalanche: a real content distribution system using network coding 23

Applications  Bidirectional traffic in a wireless network 

Effectively doubles the capacity of the path

24

Applications  Residential wireless mesh networks:  Information

about which nodes hold which packets is distributed within the neighborhood.

 Network coding is used to infer the loss rates of links 

Reduce the number of active probes and the link stress generated by these probes.

25

Future Work  The multisource network coding problem.  Improve network code creation algorithms.  Incorporate security applications and network management applications in network coding

26

Conclusion  An emerging area in coding theory  Network coding renders a new view on multicasting in a network  Offers additional benefits compared to traditional routing techniques:   

fewer network resources consumed, ease of Network management robustness against link failures

 Some difficulties have to be over come before the commercial application  Still very theoretical

27

Thank You

28