Computer Science ›› 2016, Vol. 43 ›› Issue (Z6): 242-248.doi: 10.11896/j.issn.1002-137X.2016.6A.059

Previous Articles     Next Articles

Network Coding Based Topology Inference:A Survey

XU Jing, LIU Yan-tao, XIA Gui-yang and Yasser MORGAN   

  • Online:2018-11-14 Published:2018-11-14

Abstract: Topology structure is one of the important parameters in a network.Acquiring network topology is a very meaningful fundamental problem,especially for the purpose of monitoring and managing a network.The birth of network coding offers new ideas and methods for network topology inference.There exist close relationships introduced by network coding operations of network nodes between encoded data and network topology,which can be further exploited to acquire network topologies.Compared to network tomography based methods,the network coding based topology inference outperforms them in many aspects,such as improving inference accuracy,lowering algorithm complexity,etc.This paper investigated the state-of-the-art studies of network coding on topology inference.

Key words: Network topology,Network coding,Network tomography,Topology inference

[1] Lowekamp B,O′Hallaron D R,Gross T.Topology discovery for large Ethernet networks[J].ACM SIGCOMM Computer Communication Review,2001,31(4):237-248
[2] Breitbart Y,Garofalakis M,Martin C.Topology discovery inheterogeneous networks[C]∥Proceedings of IEEE,INFOCOM’ 00.2000:265-274
[3] Cheswick B,Burch H,Branigan S.Mapping and visualizing the Internet[C]∥Proc of the USENIX Annual Technical Confe-rence.San Diego,CA,2000
[4] Donnet B,Raoult P,Friedman T,et al.Deployment of an Algorithm for Large-Scale Topology Discovery [J].IEEE Journal on Selected Areas in Communications,2006,24(12):2210-2220
[5] Huffaker B,Plummer D,Moore D,et al.Topology discovery by active probing[C]∥Proceedings.Symposium on Applications and the Internet (SAINT) Workshops,2002.IEEE,2002:90-96
[6] Spring N,Mahajan R,Wetherall D,et al.Measuring ISP topologies with rocketfuel[J].IEEE/ACM Transactions on Networking,2004,12(1):2-16
[7] Andersen D G,Feamster N,Bauer S,et al.Topology inference from BGP routing dynamics[C]∥Proceeding of the 2nd ACM SIGCOMM Workshop on Internet Measurement ACM.2002:234-248
[8] Vardi Y.Network tomography:estimating source-destination tr-affic intensities from link data [J].Journal of the American statistical association,1996,91(433):365-377
[9] Castro R,Coates M,Liang G,et al.Network tomography:recent developments [J].Statistical Science,2004,19(3):499-517
[10] 赵洪华,陈鸣.基于网络层析成像技术的拓扑推断[J].软件学报,2010,1(1):133-146
[11] Duffield N,Horowitz J,Presti F L,et al.Multicast topology inference from end-to-end measurements[C]∥Proc.of the ITC Seminar on IP Traffic,Measurement and Modeling.Monterey,2000:1-10
[12] Castro R,Coates M,Nowak R,et al.Likelihood based hierarchical clustering [J].IEEE Transactions on Signal Processing,2004,52(8):2308-2321
[13] Shih M F,Hero A O.Hierarchical inference of unicast network topologies based on end to end measurements [J].IEEE Tran-sactions on Signal Processing,2007,55(5):1708-1718
[14] Coates M,Castro R,Nowak R.Maximum likelihood network topology identification from edge based unicast measurements [J].SIGMETRICS Performance Evaluation Review,2002,30(1):11-20
[15] Yeung R W,Li S Y R,Cai N,et al.Network Coding Theory [M].Foundations and Trends in Communications and Information Theory,Now Publishers Inc,2006
[16] Ho T,Lun D S.Network Coding:An Introduction [M].Cambridge,UK:Cambridge University Press,2008
[17] Yeung R W.Information Theory and Network Coding [M].New York,Springer Science & Business Media,2008
[18] Fragouli C,Soljanin E.Network Coding Applications [J].Foundations and Trends in Networking,2007,2(2):136-269
[19] Dimakis A G,Ramchandram K,Wu Y,et al.A survey on network codes for distributed storage [J].Proceedings of the IEEE,2011,99(3):476-489
[20] Ahlswede R,Cai N,Li S Y R,et al.Network information flow [J].IEEE Transactions on Information Theory,2000,46(4):1204-1216
[21] Fragouli C,Markopoulou A.A network coding approach tooverlay network monitoring [C]∥Proceedings of the 43rd Allerton Conference of Communication,Control and Computing.2005:774-783
[22] Fragouli C,Markopoulou A,Srinivasan R,et al.Network monitoring:It depends on your points of view[C]∥Proceedings of the ITA Workshop.San Diego,CA,USA,January 2007
[23] Gjoka M,Fragouli C,Sattari P,et al.Loss tomography in general topologies with network coding[C]∥Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM 2007).Washington DC,USA,Nov 2007:381-386
[24] Lin Y,Liang B,Li B.Passive loss inference in wireless sensor networks based on network coding [C]∥INFOCOM 2009.IEEE,2009:1809-1817
[25] Shah-Mansouri V,Wong V W.Link loss inference in wireless sensor networks with randomized network coding[C]∥Global Telecommunications Conference (GLOBECOM 2010).IEEE,Dec 2010:1-6
[26] Gui J,Shah-Mansouri V,Wong V W.A linear algebraic ap-proach for loss tomography in mesh topologies using network coding[C]∥Proceedings of the IEEE International Conference on Communications (ICC 2010).South Africa,May 2010:1-6
[27] Qin P,Dai B,Wu K,et al.Dce:A novel delay correlation mea-surement for tomography with passive realization.http://arxiv.org/abs/1307.5085,July 2013:1-5
[28] Qin P,Dai B,Huang B,et al.A Survey on Network Tomography with Network Coding [J].Communications Surveys&Tutorials,IEEE,2014,16(4):1981-1995
[29] Rabbat M,Coates M,Nowak R.Multiple source Internet tomography [J].IEEE Journal on Selected Areas in Communications,2006,24(12):2221-2234
[30] Fragouli C,Markopoulou A,Diggavi S N.Topology inference using network coding[C]∥Proceedings of the 44th Alerton Conference on Communication,Control and Computing.2006
[31] Tang Dong-ming,Lu Xian-liang,Li Ju -guang.An Improved Topology Inference Algorithm via Network Coding [J].Journal of Information and Computational Science,2012,9(17):5111-5118
[32] 唐东明,卢显良,李驹光.网络编码在拓扑推断中的应用研究[J].电子测量与仪器学报,2012,26(11):960-965
[33] 唐东明.网络编码关键问题研究[D].成都:电子科技大学,2013
[34] Jithin R,Dey B K.Exact topology inference for DAGs usingnetwork coding [C]∥2012 International Symposium on Network Coding (NetCod).2012:73-78
[35] Rabbat M,Nowak R,Coates M.Multiple source multiple destination network tomography[C]∥Proceedings of IEEE INFOCOM.Hong Kong,2004:1628-1639
[36] Coates M,Rabbat M,Nowak R.Merging logical topologies using end-to-end measurements [C]∥Proceedings of the 3rd ACM SIGCOMM Conference on Internet Measurement.2003:192-203
[37] Sattari P,Markopoulou A,Fragouli C.Multiple source multiple destination topology inference using network coding[C]∥NetCod’09 Workshop on Network Coding,Theory and Applications.2009:36-41
[38] Sattari P,Fragouli C,Markopoulou A.Active topology inference using network coding [J].Physical Communication,2012,6(5):142-163
[39] Sattari P.Network coding for network tomography[D].University of California,2012
[40] Ho T,Koetter R,M′edard M,et al.The Benefits of Coding over Routing in a Randomized Setting [C]∥ISIT.2003
[41] Ho T,Medard M,Koetter R,et al.A Random Linear Network Coding Approach to Multicast [J].IEEE Transactions on Information Theory,2003,52(10):4413-4430
[42] Sharma G,Jaggi S,Dey B K.Network tomography via network coding[C]∥Proceedings of the Information Theory and Applications Workshop 2008.San Diego,CA,USA,February 2008:151-157
[43] Yao H,Jaggi S,Chen M.Network coding tomography for network failures[C]∥INFOCOM,2010 Proceedings IEEE.San Die-go,CA,USA,March 2010:1-5
[44] Yao H,Jaggi S,Chen M.Passive network tomography for erroneous networks:A network coding approach [J].IEEE Transactions on Information Theory,2012,58(9):5922-5940
[45] Siavoshani M J,Fragouli C,Diggavi S.Subspace properties ofrandomized network coding[C]∥2007 IEEE Information Theory Workshop Information Theory for Wireless Networks.2007:1-5
[46] Siavoshani M J,Fragouli C,Diggavi S.Subspace Properties of Network Coding and their Applications [J].IEEE Transactions on Information Theory,2012,58(5):2599-2619
[47] Koetter R,Kschischang F.Coding for errors and erasures in random network coding [J].IEEE Transactions Information Theory,2008,54(8):3579-3591
[48] Ho T,Leong B,Chang Y,et al.Network monitoring in multicast networks using network coding [C]∥Proc.of IEEE ISIT.2005:1977-1981
[49] Firooz M H,Roy S,Bai L,et al.Link status monitoring using network coding[R].UW Technical Report,Sept 2009
[50] Firooz M H,Roy S,Bai L,et al.Link Failure Monitoring viaNetwork Coding[C]∥2010 IEEE 35th IEEE Conference on Local Computer Networks.2010:1068-1075
[51] Siavoshani M J,Fragouli C,Diggavi S,et al.Bottleneck discovery and overlay management in network coded peer-to-peer systems[C]∥Proceedings of the 2007 SIGCOMM Workshop on Internet Network Management ACM.Aug.2007:293-298
[52] Siavoshani M J,Fragouli C,Diggavi S.On locating byzantine attackers[C]∥Fourth Workshop onNetwork Coding Theory and Applications,2008(NetCod 2008).2008:1-6
[53] Duan Q,Cai W,Tian G.A simple graph-structure network to-mography topology identification method[C]∥Proceedings of the International Joint Conference on Artificial Intelligence (JCAI 2009).Hainan Island,China,April 2009:337-340
[54] 戴斌,秦鹏,等.基于网络编码的被动式动态网络拓扑层析方法:CN201110254234.5[P]

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!