Network Alignment（PPT讲稿）Treating Networks as Wireless Interference Channel

Network Alignment: Treating Networks as Wireless Interference Channel Chun Meng Univ, of california Irvine

Network Alignment: Treating Networks as Wireless Interference Channel Chun Meng Univ. of California, Irvine

Outline o Motivation Network a Wireless Interference Channel approaches NA in the middle, Precoding- Based NA O PBNA Feasibility of PBna Conclusion

o Motivation: Network ≈ Wireless Interference Channel o Approaches: NA in the middle, Precoding-Based NA o PBNA Feasibility of PBNA o Conclusion 2 Outline

State of the art-I Intra-Session Nc Achievable rate min-cut[,] LP-formulation[31 v Code design: RNCI4], deterministic[5] 1R Ahlswede, et al, " Network information flow [2]R Koetter and M. M'edard, "An algebraic approach to network coding BJZ. Li, et al, "On Achieving Maximum Multicast Throughput in Undirected Networks 4]T Ho, et al, a random linear network coding approach to multicast [5]S Jaggi, et al, "Polynomial Time algorithms for Multicast Network Code Construction

Intra-Session NC ✓ Achievable rate = min-cut[1,2] LP-formulation[3] ✓ Code design: RNC[4], deterministic[5] 3 State of the Art - I [1] R. Ahlswede, et al, “Network information flow” [2] R. Koetter and M. M′edard, “An algebraic approach to network coding” [3] Z. Li, et al, “On Achieving Maximum Multicast Throughput in Undirected Networks” [4] T. Ho, et al, “A random linear network coding approach to multicast” [5] S. Jaggi, et al, “Polynomial Time Algorithms for Multicast Network Code Construction

State of the Art-工I Inter-session nc v Only approximation of bounds [I Exponential number of variables v Code design: NP-hard[5] LP evolutionary approach 1]N. Harvey, et al, "On the Capacity of Information Networks [2JAR Lehman and E Lehman, " Complexity classification of network information flow problems 3]D. Traskov, et al, "Network coding for multiple unicasts: An approach based on linear optimization 4 4]M. Kim, et al, " An evolutionary approach to inter-session network coding

Inter-Session NC ✓ Only approximation of bounds [1] Exponential number of variables ✓ Code design: NP-hard[5] LP, evolutionary approach 4 State of the Art - II [1] N. Harvey, et al, “On the Capacity of Information Networks” [2] A. R. Lehman and E. Lehman, “Complexity classification of network information flow problems” [3] D. Traskov, et al, “Network coding for multiple unicasts: An approach based on linear optimization” [4] M. Kim, et al, “An evolutionary approach to inter-session network coding

Restrictive Framework 1 1 Z1=m11x)X1+m21(x)X2+m31(x)X3 Interference must be canceled out 5 R Koetter and M. M'edard, "An algebraic approach to network coding

5 Restrictive Framework 𝑋1 𝑋2 𝑋3 𝑍2 𝑍1 𝑍3 R. Koetter and M. M′edard, “An algebraic approach to network coding” Interference must be canceled out

Network vs Wireless Channel-I Min-cut =1 x R Rx y2 R Network with multiple unicasts 21=m1(x)X1+m2(x)X2+m3(x)X3 yi= h1i 1+h2i C2+h3i3+n Transfer function introduced by network Channel gain: introduced by nature 6

6 Network vs. Wireless Channel - I Network with multiple unicasts SISO Channel gain: introduced by nature 𝑋1 𝑋2 𝑋3 𝑍2 𝑍1 𝑍3 𝑥1 𝑥2 𝑥3 𝑦1 𝑦2 𝑦3 Transfer function: introduced by network Min-cut = 1

Networks vs, ireless Channel-II Min -cut>1 Z 3 Network with multiple unicasts MIMO Z1=M1X1+M2X2+M32X3 yi=LixI +H2i X2+H3ix3+n Transfer matrⅸx Channel matrix

7 Networks vs. Wireless Channel - II Network with multiple unicasts MIMO 𝐗1 𝐗2 𝐗3 𝐙2 𝐙1 𝐙3 𝐱1 𝐱2 𝐱3 𝐲1 𝐲2 𝐲3 Min-cut > 1 Transfer matrix Channel matrix

Interference ali ignment Common problem Too MANy unknowns Solution: Align interferences to reduce the number of unknowns Benef计: Everyone gets one half of the cake V. Cadambe and S Jafar, " Interference Alignment and Degrees of Freedom of the K-User Interference Channel

8 Interference Alignment Common problem: Too MANY unknowns! Solution: Align interferences to reduce the number of unknowns V. Cadambe and S. Jafar, “Interference Alignment and Degrees of Freedom of the K-User Interference Channel” Benefit: Everyone gets one half of the cake

Brief Intro of ia o Originally introduced by cadambe& jafar pproaches Asymptotic alignment, Ergodic alignment Lattice alignment Blind alignment pplIcaTions K-user wireless interference channel K-user Mimo interference channe Cellular networks Multi-hop interference networks Exact repair in distributed storage Syed A Jafar, " Interference Alignment -A New Look at Signal Dimensions in a Communication Network

9 Brief Intro of IA o Originally introduced by Cadambe & Jafar o Approaches: • Asymptotic alignment, • Ergodic alignment, • Lattice alignment, • Blind alignment o Applications • K-user wireless interference channel, • K-user MIMO interference channel, • Cellular networks, • Multi-hop interference networks, • Exact repair in distributed storage Syed A. Jafar, “Interference Alignment — A New Look at Signal Dimensions in a Communication Network

Network Is Not wireless channel Zi=mi(x)X1+mi2(x)X2+mi3(x)X3 yi=h1:1+h2:2+h3i3+n o Xi, Zi symbols from finite field I o yi, xi: real complex numbers o mii(x): polynomial of coding variables I o hij; structureless 10

10 Network Is NOT Wireless Channel o 𝑋𝑖 , 𝑍𝑖 : symbols from finite field o 𝑚𝑖𝑗(𝐱): polynomial of coding variables o 𝑦𝑖 , 𝑥𝑖 : real & complex numbers o ℎ𝑖𝑗: structureless