Network Coding

  • Uploaded by: Anjali
  • 0
  • 0
  • May 2020
  • PDF

This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA


Overview

Download & View Network Coding as PDF for free.

More details

  • Words: 1,632
  • Pages: 28
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

Related Documents

Network Coding
May 2020 13
Coding
December 2019 22
Coding
July 2020 13
Coding
November 2019 26
Coding
April 2020 13
Coding
November 2019 26

More Documents from ""