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