New algorithm for variable-rate linear broadcast network coding

Abstract

To adjust the variance of source rate in linear broadcast networks, global encoding kernels should have corresponding dimensions to instruct the decoding process. The algorithm of constructing such global encoding kernels is to adjust heterogeneous network to possible link failures. Linear algebra, graph theory and group theory are applied to construct one series of global encoding kernels which are applicable to all source rates. The effectiveness and existence of such global encoding kernels are proved. Based on information flow, the algorithm of construction is explicitly given within polynomial time O(|E|·|T|·ω_max²), and the memory complexity of algorithm is O(|E|). Both time and memory complexity of this algorithm proposed can be O(ω_max) less than those of algorithms in related works.

Keywords

network coding / variable-rate / linear broadcast / heterogeneous network / code construction algorithm

References

[1] YeungR. W., LiS. R., CaiN., ZhagZhen.Network coding theory [M], 2005, Boston-Delft, Now Publisher Inc: 11-50

[2] YeungR.-W.Information theory and network coding [M], 2008, New York, Springer: 411-541

[3] YangY.-xian.Network coding theory and technology [M], 2009, Beijing, National Defense Industry Press: 1-229

[4] FanP.-yi.Network information theory [M], 2009, Beijing, Tsinghua University Press: 109-147

[5] FragouliC., SoljaninE.. Network coding fundamentals [J]. Foundations and Trends in Networking, 2007, 1(2): 1-133

[6] HoT., LunD. S.Network coding: An introduction [M], 2008, Cambridge, UK, Cambridge University Press: 13-85

[7] AhlswedeR., CaiN., LiS. R., YeungR. W.. Network information flow [J]. IEEE Transactions on Information Theory, 2000, 46(4): 1204-1216

[8] LiS. R., YeungR. W., CaiNing.. Linear network coding [J]. IEEE Transactions on Information Theory, 2003, 49(2): 371-381

[9] KoetterR., MedardM.. An algebraic approach to network coding [J]. IEEE Transactions on Networking, 2003, 11(5): 782-795

[10] JaggiS., SandersP., ChouP. A., EffrosM., EgnerS., JainS., TolhuizenL.. Polynomial time algorithms for multicast network code construction [J]. IEEE Transactions on Information Theory, 2005, 51(6): 1973-1982

[11] HoT., MedardM., KoetterR., KargerD., EffrosM., ShiJ., LeongB.. A random linear network coding approach to multicast [J]. IEEE Transactions on Information Theory, 2004, 52(10): 4413-4430

[12] MA W Y, BEDNER I, CHANG G., KUCHINSKY A, ZHANG H J. A framework for adaptive content delivery in heterogeneous network environments [C]// Proc 2000 MMCN. San Jose, USA, 2000: 86–100.

[13] SADEGHI P, TRASKOV D, KOETTER R. Adaptive network coding for broadcast channels [C]// Workshop on Digital Object Identifier NetCod. Lausanne, Switzerland, 2009: 80–85

[14] LI S R, CAI] Ning, YEUNG R W. On theory of linear network coding [C]// ISIT Inf Theory. Adelaide, Austrialia, 2005: 273–277.

[15] FongS. L., YeungR. W.. Variable-rate linear network coding [C]. Information Theory Workshop, 2006, Uruguary, Puntadel Este: 409-412

[16] GOSELING J, WEBER J H. Multi-rate network coding for minimum-cost multicasting [C]// IEEE Symposium on Information Theory. 2008: 36–40.

[17] GUO Qin, ZHUO Xin-jian, MA Song-ya, LUO Ming-xing, YANG Yi-xian. Algorithms of variable-rate linear network coding [C]// Proc of Triangle Symposium on Advanced ICT. Daejeon, Republic of Korea, 2008: 1–6.

[18] MaS.-y., ChenX.-b., LuoM.-x., YangY.-xian.. Variable-rate Convolutional network coding [J]. The Journal of China Universities of Post and Telecommunications, 2010, 17(3): 91-96