Report

Index Coding Part II of tutorial NetCod 2013 Michael Langberg Open University of Israel Caltech (sabbatical) 1 Outline This part of tutorial: Will show an equivalence between the network coding and index coding problems. Outline: • • • Preliminary: Network Coding model. • Preliminary: Index Coding model. • Equivalence for linear encoding/decoding . • Equivalence for general encoding/decoding . • Multicast vs. Unicast Index Coding • Open Questions. [ElRouayhebSprintsonGeorghiades] [EffrosElRouayhebLangberg] [MalekiCadambeJafar]. 2 • Network communication challenging: combines topology with information.theme General •Reduction separates information from topology. •Significantly simplifies the study of Network Comm. Will show an equivalence between the network •Index Coding is aindex simplecoding but representative coding and problems. instance of • An efficient reduction that allows to solve NC general network communication. using any scheme to solve IC. s1 NC s2 s1 s2 s3 s4 s5 s6 IC t3 t1 t2 Obtain solution to NC t1 t2 t3 t4 t5 t6 Solve IC 3 General Network Coding • Directed acyclic network N. • Edge e has capacity c . • Source vertices S. • Terminal vertices T. • Requirement matrix: s1 s3 s2 e • Transfer information from S to T. t3 t1 t2 • Objective: • Information flow using Network Coding that satisfies terminals. 4 S1 Assumptions • Sources S hold independent information. • Zero error in communication. • We consider the multiple unicast communication t1 i S2 t2 requirement (w.l.o.g. [DoughertyZeger]): • k source/terminal pairs (S ,T ) that wish to communicate over N. i i S1 T1 S2 T2 S3 S4 N T3 T4 5 NC preliminaries s1 t1 s3 t3 s2 t2 s4 t4 Communication at rate R = (R1,…,Rk) is achievable over instance NC with block length n if random variables {Si},{Xe}: • Rate: Source S = R.V. independent and uniform over [2 ]. • Edge capacity: For each edge e: X = R.V. with support [2 ]. • Functionality: for each edge e we have f = function from incoming R.V.’s X ,…,X to X (i.e., X =f (X ,…,X )). X f • Decoding: for each terminal t we define X X Rin i cen e e e1 e,in(e) e e i e e1 e,in(e) a decoding function yielding sources Si reqired. 1 2 e e X3 • R=(R ,…R ) is ”n-feasible” if code with block length n. • Alternatively we say that NC is (R,n)-feasible. 1 k 6 Index Coding [Birk,Bar-Yossef et al.] • IC is a special case of NC • A set S of sources. • A set T of terminals. • Each terminal has some subset of sources (as side info.) and wants some subset of sources. • Broadcast link has capacity c . •Other links have unlimited cap. s s s • Objective: To satisfy all terminals. B 1 2 3 s4 cB using broadcast rate cB. t1 t2 t3 t4 Index Coding Communication at rate R = (R1,…,Rk) is achievable with block length n if random variables {Si},XB: • Rate: Source S = R.V. independent and uniform over [2 ]. • Encoding: X = f (S ,…,S ) is R.V. with support [2 ]. • Decoding: for each terminal t we define a decoding function g Rin i B B 1 cBn k i taking as input the broadcasted message XB and the side information of ti; and returning the sources Si wanted by ti. s1 s2 s3 • R=(R ,…R ) is ”n-feasible” if 1 i s4 k code with block length n. cB •ICWill use notation: IC is (R,n)-feasible. is a simple instance of the NC problem: only a single encoding node. t1 t2 t3 t4 Connecting NC to IC s1 s2 s1 s2 s3 s4 s5 s6 NC IC t1 t2 Obtain solution to NC t1 t2 t3 t4 t5 t6 Solve IC • Step 1: Need to define reduction from NC to IC. • Step 2: Need to prove NC is (R,n)-feasible iff IC is (R’,n)-feasible. • Would like: Reduction/code const. to be very efficient. 9 Outline s1 s2 s1 s2 s3 s4 s5 s6 NC IC t1 t2 t1 t2 t3 t4 t5 t6 Theorem: For any NC, R one can construct IC, R’ such that for any n: NC is (R,n)-feasible iff IC is (R’,n)-feasible. • Step 1: Present reduction from NC to IC. • Step 2: Equivalence for linear and general encoding/decoding. [EffrosElRouayhebLangberg]. [ElRouayhebSprintsonGeorghiades], 10 The reduction NC sources NC NC edges NC sources X1 Network: Xe edges IC X2 X3 NC terminals •Index Coding instance: NC term. NC edges •Sources corresponding to NC sources, and NC edges. •Terminals corresponding to NC term., NC edges, special terminal. •For edge e: terminal t in IC wants IC source X and has as e side information all IC sources incoming to e in NC. e IC encodes topology of NC in its terminals! The reduction in more detail NC sources X1 Network: ti edges NC NC edges NC sources IC X2 X3 NC terminals NC term. NC edges •Sources: |S|+|E| sources, one for each source of NC and one for each edge of NC: {S ’} and {S ’}. •Terminals: |T|+|E|+1 terminals: i e •One terminal t ’ for each t : wants S ’ and has {S ’} for e in In(t ). •t ’ for each edge e: wants S ’ and has {S ’} for edge a in In(e). •One special terminal t : wants {S ’} and has {S ’}. i i e i e all e a e i i The reduction in more detail ReductionNC sources NC Sources IC S1,…,Sk {Si’}, {Se’} Network: t1,…,tk edges Terminals Capacities {ti’},{te’},tall ce cB=ce NC terminals R1,…,Rk Rate NC edges NC sources NC edges NC term. {Ri’}, {Re’} Ri’=Ri Sources: |S|+|E| sources, Re’=ce one for each source of NC and one for each • edge of NC: {S ’} and {S ’}. Wants •Terminals: Has |T|+|E|+1 terminals: foreeach terminal t ’ •One {S ’} for in In(t ). S ’ t : wants S ’ and has {S ’} for e in In(t ). foraeach edgeSe:’ wants S ’ and has {S ’} for edges a in In(e). t ’ •One {S ’} for in In(e). t •One {S ’} special terminal {S t’} : wants {S ’} and has {S ’}. X •Theorem: Bottle neck edge of capacity c =c For any NC, R one can construct IC, R’ such that •for Given rate vector R=(R ,…,R ) we construct rate vector R’=({R X ’};{R ’}): t n: NC is (R,n)-feasible iff IC is (R’,n)-feasible. •Rany ’=R and R ’=c . X i i e e a all i e i i i i e e 1 i i e e k i a e all e B e e. i 1 2 i 3 e i Theorem Reduction NC IC Sources S1,…,Sk {Si’}, {Se’} Terminals t1,…,tk {ti’},{te’},tall Capacities ce cB=ce Rate {Ri’}, {Re’} Ri’=Ri Re’=ce R1,…,Rk Has Wants ti’ {Se’} for e in In(ti). S i’ t e’ {Sa’} for a in In(e). Se ’ tall {Si’} •Theorem: {Se’} NC sources NC edges NC sources NC edges NC terminals s1 t1 s2 t2 . NC term NC edges s1 s2 s3 s4 s5 s6 t1 t2 t3 t4 t5 t6 NC is (R,n)-feasible iff IC is (R’,n)-feasible. Geometric view Reduction NC IC Sources S1,…,Sk {Si’}, {Se’} Terminals t1,…,tk {ti’},{te’},tall Capacities ce cB=ce Rate {Ri’}, {Re’} Ri’=Ri Re’=ce R1,…,Rk •Theorem: NC sources NC edges NC sources NC edges NC terminals s1 t1 s2 t2 . NC term NC edges s1 s2 s3 s4 s5 s6 t1 t2 t3 t4 t5 t6 NC is (R,n)-feasible iff IC is (R’,n)-feasible. e: Re’=ce What now? Outline: NC feasible implies IC feasible (works for both linear and non-linear). IC feasible implies NC feasible (will show new proof for linear that modifies to non linear). • • Theorem: For any NC, R one can construct IC, R’ such that for any n: NC is (R,n)-feasible iff IC is (R’,n)-feasible. 16 NC Reduction IC NC IC Sources S1,…,Sk {Si’}, {Se’} Terminals t1,…,tk {ti’},{te’},tall Capacities ce cB=ce Rate R1,…,Rk {Ri’}, {Re’} Ri’=Ri Re’=ce • Use global NC encoding functions. ••Rate: Source S = R.V. independent and uniform over [2 ]. Seen that X = f (X (e)). ••Edge capacity: For each edge e: X = R.V. with support [2 ]. Edge e also has a function F : •Functionality: for each edge e we have f = function from • X = F (S ,…,S ). incoming R.V.’s X ,…,X to X (i.e., X =f (X ,…,X )). • IC: We need to define X of rate c . •Decoding: for each terminal t we define a decoding function • Recall that c =Σc . yielding sources S required. • Recall that X of rate c . •Theorem: For all eFor let X (Scan ’,…,S ’). any(e)=S NC, R’+F one construct IC, R’ such that There is a separation between iff {S ’}IC andis{S(R’,n)-feasible. ’}. for•any n: NC is (R,n)-feasible • Lets see that this works (decoding …). e Has i e In e e e e 1 k e1 i B B RWants in ti’ {Se’} for e in In(ti). t e’ {Sa’} for a in In(e). tall e{Si’} e,in(e) e B e B e Si’ cen Se’ {Se’} e1 e,in(e) i e e e e e 1 k i e 17 NC • • • • • Reduction IC NC Sources S1,…,Sk {Si’}, {Se’} Terminals t1,…,tk {ti’},{te’},tall Capacities ce cB=ce Rate R1,…,Rk {Ri’}, {Re’} Ri’=Ri Re’=ce Use global encoding functions of NC. Each edge e has a function Fe such that Fe(S1,…,Sk)=Xe. Recall Xe of support [2cen]. Recall cB=Σce. We need to define XB of total support [2c n]. Basic idea: simulate the NC solution! • Let X (e)=S ’+F (S ’,…,S ’). • Decoding: B B e e 1 IC Xa1 fe(Xa1,Xa2,Xa3)=Xe Xa2 k Xe Xa3 • Consider terminal t ’: wants S ’ and has {S ’} for edges a in In(e). • t ’ also receives the broadcast X . • For each a compute X (a)-S ’ = S ’+F (S ’,…,S ’)-S ’ = F (S ’,…,S ’). • Usetlocal encoding function f to compute: t’ ’ will solution on edge e. ’) f (F simulate (S ’,…,S the ’),…, NC F (S ’,…,S ’)) = F (S ’,…,S t’ • Compute X (e)-F (S ’,…,S ’) = S ’+F (S t’,…,S ’)-F (S ’,…,S ’) = S ’. • Same process for other terminals. e e a e B B e a a a e e a1 B 1 k e 1 a3 k e 1 e 1 k Has a a 1 Wants k i {Se’} for e in In(ti). Si’ ek {Sa’} for e a1 in In(e). k Se’ k i’} e {S {See’} 1 all 1 k 18 What now? Outline: NC feasible implies IC feasible (works for both linear and non-linear). IC feasible implies NC feasible (will show new proof for linear that modifies to non linear). • • 19 Reduction Linear: IC NC NC IC Sources S1,…,Sk {Si’}, {Se’} Terminals T1,…,Tk {ti’},{te’},tall Capacities ce cB=ce Rate R1,…,Rk {Ri’}, {Re’} Ri’=Ri Re’=ce • Given a linear code for IC, how do we build one for NC? • Encoding for IC includes a linear encoding function f t only has {S ’} and A f ({S ’}, {S = ’},{S •Rate: Sources S’ =’})({S ’})+of Asupport wants [2 ],all[2{S ’}]. ••Bottleneck: = fA ({S ’}) of [2 ]. Can prove X that is ’},{S square andsupport full rank. • Crucial property: • Fix any value s ’ for S ’=S ’,…,S ’ • There exists unique value s ’ for S ’=S ’,…,S ’ such that f (s ’, s ’) =0. • This will allow the construction of a NC! B B i e B i B E I i S e e I I E Re’n i e cBn 1 k E B all Ri’n E ti’ t e’ tall Has {Se’} for e in In(ti). E e1 em {Sa’} for a in In(e). {Si’} Wants Si’ Se’ {Se’} 20 Reduction Linear: IC NC fB({Si’}, {Se’}) = AS + NC IC Sources S1,…,Sk {Si’}, {Se’} Terminals T1,…,Tk {ti’},{te’},tall Capacities ce cB=ce Rate R1,…,Rk {Ri’}, {Re’} Ri’=Ri Re’=ce AE • A is square and full rank. • Crucial property: For all s ’ exists s ’ s.t. f (s ’, s ’) =0. E I E B I E sE’ sI’ Will define NC by ‘projecting’ fB onto the white curve! Value = 0 fB(sI’, sE’) 21 Reduction Linear: IC NC • Consider edge e in NC. • We will define local encoding function f (X ,X ,X )=X . • Will define f based on decoding e a1 a2 e a3 e tall {Si’} {Se’} IC Sources S1,…,Sk {Si’}, {Se’} Terminals T1,…,Tk {ti’},{te’},tall Capacities ce cB=ce Rate R1,…,Rk {Ri’}, {Re’} Ri’=Ri Re’=ce sE’ sI’ ge’ function of IC for terminal te’. ge’(Sa1’,Sa2’,Sa2’, fB({Si’}, {Se’}))=Se’. fe(Xa1,Xa2 ,Xa3)=ge‘(X a1,Xa2,Xa3, 0). Has Wants valid function. {Sea’} for e in local In(ti). encoding Si’ ti’fe is decoding defined similarly. {S Se’ teNC ’ a’} for a in In(e). • • • NC Value = 0 Xa1 Xa2 Xe Xa3 22 Reduction Linear: IC NC • Consider terminal i in NC. • We need to define local decoding function g (X ,X ,X )=S . • Will define g based on decoding i a1 i a2 a3 all IC Sources S1,…,Sk {Si’}, {Se’} Terminals T1,…,Tk {ti’},{te’},tall Capacities ce cb=ce Rate R1,…,Rk {Ri’}, {Re’} Ri’=Ri Re’=ce sE’ i s’ I gi’ function of IC for terminal ti’. gi‘(Sa1’,Sa2’,Sa2’, fB({Si’}, {Se’}))=Si’. gi(Xa1,Xa2,Xa3)=gi‘(Xa1,Xa2,Xa3, 0). Recall: feHas (Xa1,Xa2,Xa3Wants )=ge‘(Xa1,Xa2,Xa3, 0). and valid {Sef ’} efor e ingIn(t Si’ ti’Both i are i). encoding/decoding functions. {Sa’} for a in In(e). S t e’ e’ {Si’}to prove correct {Se’} decoding! t Need • • • • NC Value = 0 Xa1 Xa2 Si Xa3 23 Reduction xe=fe(xa1,xa2,xa3) = gDecoding: e’(xa1,xa2,xa3, 0) = ge’(xa1,xa2,xa3, fB(sI’,sE’)) = ge’(sa1’,sa2’,sa3’, fB(sI’,sE’)) = se’ IC NC NC IC Sources S1,…,Sk {Si’}, {Se’} Terminals T1,…,Tk {Ti’},{Te’},Tall Capacities ce cE=ce Rate R1,…,Rk {Ri’}, {Re’} Ri’=Ri Re’=ce ,x ’(X ,x ,X) =,X , 0). •Decoder f (X ,X =g,X(x )=g We get a valid NC! 0) =’(X ,X ,X , 0). •g ’(x g (X ,x,X ,x,X , )=g s ’ g ’(s ’,s ’,s ’, f (s ’,s ’)) = s ’ s’ s •= Consider source info s =s ’=s ,…,s Value = 0 • Let s ’ be corresponding value on curve. • Will show by induction that running NC e a1 ia2 i a3a1 ea2 a1a3 a2 i i a1a1 a2a2 a3a3 i a1 a2 i a3 i B a1 I a2 a3 a3 E E i I I 1 k I E on input sI corresponds to running IC on input (sI’, sE’). Inductive claim: information xe in NC is exactly se’. Now idea: for decoding si at terminal usesolution! gi Basic NC is simulating thei IC • • Xa1 Xa2 Si/Sa Xa3 24 What now? Outline: NC feasible implies IC feasible (works for both linear and non-linear). IC feasible implies NC feasible (will show new proof for linear that modifies to non linear). • • 25 Reduction Has Wants {S ’} for e in In(t S’ General : ).IC ti’ e i NC i t e’ {Sa’} for a in In(e). Se’ tall {Si’} {Se’} NC IC Sources S1,…,Sk {Si’}, {Se’} Terminals T1,…,Tk {ti’},{te’},tall Capacities ce cB=ce Rate R1,…,Rk {Ri’}, {Re’} Ri’=Ri Re’=ce • We use exact same proof! Number of different X values is exactly equal to number of different S ’ values. • Where did we use linearity? Crucial property: For all s ’ exists s ’ s.t. f (s ’, s ’) =0. • Need to prove property for general encoding functions. • Property follows from terminal t . B E I E B I E • Given S ’ and X =f (S ’, S ’) we must be able to decode S ’ s ’ • Thus fixing s ’, f is 1-1 as a function of S ’ • Support of X equals support of S ’. s’ Value = 0 • Each row is a permutation. • Thus property holds! all I B I B B I E E B E E E I differ 26 What now? Outline: NC feasible implies IC feasible (works for both linear and non-linear). IC feasible implies NC feasible (will show new proof for linear that modifies to non linear). Multicast IC can be represented by Unicast IC (linear only) [MalekiCadambeJafar]. • • • 27 Multicast vs Unicast • In previous reduction we use an IC instance which “multicasts” information to different terminals. • Same information is wanted by more than one terminal. Has Wants ti’ {Se’} for e in In(ti). Si’ t e’ {Sa’} for a in In(e). Se’ tall {Si’} {Se’} Reduction NC IC Sources S1,…,Sk {Si’}, {Se’} Terminals T1,…,Tk {ti’},{te’},tall Capacities ce cB=ce Rate R1,…,Rk {Ri’}, {Re’} Ri’=Ri Re’=ce • In NC, any (multiple) multicast can be reduced to (multiple) unicast . • Does the same phenomena hold for IC? [DoughertyZeger] 28 Multicast vs Unicast • • • In previous reduction we use an IC instance which “multicasts” information to different terminals. Same information is wanted by more than one terminal. In NC, any (multiple) multicast can be reduced to (multiple) unicast. Does the same phenomena hold for IC? • • Recent work by • show that unicast suffices in case (if restricted to linear encoding/decoding). Implies that for linear encoding: NC reduces to (multiple) unicast IC! [MalekiCadambeJafar] • Each terminal wants different message. • Same number of sources and terminals. • IC can be characterized by side information graph, rather than side information hypergraph. 29 Some open problems • Multicast vs. Unicast for general encoding. • Would be surprising: problems known to be more difficult in the multiple-multicast setting (e.g., IC via cycle packing [ChaudhryAsadSprintsonLangberg]). • Capacity: can one determine if rate R is in capacity region of NC via knowledge of capacity region of IC? • Reduction is not robust enough to withhold the closure operation in the definition of capacity. • Answer is yes for linear case. Also for co-located NC sources [WongLangbergEffros]. e: Re’=ce 35 Some open problems • vs zero error in communication: • Does allowing some error increase rate in NC/IC? • IC there is no advantage to allowing small error in communication … can this extend to NC? • NC – not known! In NC “no advantage” known for co-located and other cases. • Can we use equivalence between NC and IC? • Intriguing connections to other problems such as the edge [LangbergEffros] [ChanGrant] [LangbergEffros] removal problem [HoEffrosJalali]. • Algorithms!: • Wide open … both in NC setting and IC setting … 36 Conclusions NC sources NC sources NC edges NC edges NC terminals . NC term NC edges • Network communication challenging: combines topology with information. • Discussed equivalence between the network coding and index coding problems. • Reduction separates information from topology. • Significantly simplifies the study of Network Comm. • Index Coding is a simple but representative instance of general network communication. Thanks! 37