网络断层扫描:理论与算法
作者:
作者简介:

李惠康(1993-),男,博士,主要研究领域为网络测量,物联网系统与网络,无线与移动计算.
高艺(1987-),男,博士,副教授,博士生导师,CCF专业会员,主要研究领域为物联网与传感网,边缘计算,无线与移动计算,软件定义网络.
董玮(1982-),男,博士,教授,博士生导师,CCF高级会员,主要研究领域为物联网系统与网络,无线与移动计算,智能感知技术,边缘计算.
陈纯(1955-),男,博士,教授,博士生导师,CCF会士,主要研究领域为计算机软件与理论,大数据实时智能处理技术.

通讯作者:

董玮,E-mail:dongw@zju.edu.cn

基金项目:

国家自然科学基金(61872437,61772465);浙江省自然科学基金(LR19F020001)


Network Tomography: Theory and Algorithm
Author:
Fund Project:

National Natural Science Foundation of China (61872437, 61772465); Zhejiang Provincial Natural Science Foundation (LR19F020001)

  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [86]
  • |
  • 相似文献 [20]
  • |
  • 引证文献
  • | |
  • 文章评论
    摘要:

    网络测量为网络设计者与管理者提供网络内部细粒度的运行状态信息,是对网络进行高效管理与优化的基础.网络断层扫描是网络测量领域的一个研究热点,是一种端到端的网络测量方法.与传统网络内部测量方法不同,网络断层扫描利用端到端的测量信息计算和推断网络内部性能和状态,从而实现与网络组成和协议无关的网络测量,具有较低的测量开销.对近年来国内外学者在网络断层扫描研究领域取得的成果进行了系统的总结.首先介绍了网络断层扫描的基本模型,并指出了影响网络断层扫描性能的3个重要因素:监测节点部署、测量路径构造和测量数据分析;接着,依次归纳了这3个方面的研究进展和研究成果;随后分析了已有网络断层扫描方法在实际应用中存在的缺陷,并给出了应对这些核心缺陷的理论和关键算法;最后,基于现有研究成果讨论了网络断层扫描的发展趋势和进一步的研究方向.

    Abstract:

    Network measurement provides the network designers and managers with fine-grained information on the operational statuses of the network and is the basis for efficient network management and optimization. Network tomography is a hot topic in the field of network measurement and is an end-to-end approach for network measurement. Unlike the traditional internal approaches for network measurement, network tomography uses the end-to-end measurements to infer the internal network performance and network states, thereby incurring low overhead to achieve the network measurement that is independent of the network composition and the network protocols. This paper systematically summarizes the representative research works about network tomography in the past few years. First, the basic model of network tomography is given and three key factors that impact the performance of network tomography are identified: the monitoring node placement, the measurement path construction, and the measurement data analysis. Then, the related works are reviewed on these three factors separately. In particular, the major limitations of existing network tomography methods in practical applications are explored, and the efficient solutions proposed in recent years are introduced. Lastly, some challenges and future research directions are discussed in the field of network tomography based on existing research works.

    参考文献
    [1] Zhou AP, Cheng G, Guo XJ. High-speed network traffic measurement method. Ruan Jian Xue Bao/Journal of Software, 2014,25(1):135-153(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4445.htm[doi:10. 13328/j.cnki.jos.004445]
    [2] Yang H, Li CL, Sun Z, et al. A survey of Internet topology data acquisition methods. Communications Technology, 2019,52(8):1811-1817(in Chinese with English abstract).
    [3] Hu ZG, Tian CQ, Du L, Guan XQ, Cao F. Current research and future perspective on IP network performance measurement. Ruan Jian Xue Bao/Journal of Software, 2017,28(1):105-134(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5127. htm[doi:10.13328/j.cnki.jos.005127]
    [4] Zhang R, Jin YH, Yang T, Rong ZZ. Intelligent selection algorithm of measurement nodes in distributed network measurement. Computer Science, 2015,42(9):70-78(in Chinese with English abstract).[doi:10.11896/j.issn.1002-137X.2015.9.015]
    [5] Vardi Y. Network tomography:Estimating source-destination traffic intensities from link data. Journal of the American Statistical Association, 1996,91(433):365-377.
    [6] Zhang HL, Fang BX, Hu MZ, Jiang Y, Zhan CY, Zhang SF. A survey on Internet measurement and analysis. Ruan Jian Xue Bao/Journal of Software, 2003,14(1):110-116(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/14/110.htm
    [7] Sunshine CA. Source routing in computer networks. In:Proc. of the ACM SIGCOMM Computer Communication Review. ACM, 1977. 29-33.
    [8] Xia Y, Tse D. Inference of link delay in communication networks. IEEE Journal of Selected Areas in Communications, 2006, 24(12):2235-2248.
    [9] Gurewitz O, Sidi M. Estimating one-way delays from cyclic-path delay measurements. In:Proc. of the IEEE INFOCOM. IEEE, 2001. 1-7.
    [10] Downey AB. Using pathchar to estimate internet link characteristics. In:Proc. of the ACM SIGCOMM. ACM, 1999. 241-250.
    [11] Kumar R, Kaur J. Practical beacon placement for link monitoring using network tomography. IEEE Journal on Selected Areas in Communications, 2006,24(12):2196-2209.
    [12] Bejerano Y, Rastogi R. Robust monitoring of link delays and faults in IP networks. In:Proc. of the IEEE INFOCOM. IEEE, 2003. 1-11.
    [13] Horton JD, Ortiz AL. On the number of distributed measurement points for network tomography. In:Proc. of the ACM IMC. ACM, 2003. 204-209.
    [14] Mahajan R, Spring NT, Wetherall D, Anderson TE. Inferring link weights using end-to-end measurements. In:Proc. of the ACM Internet Measurement Workshop. ACM, 2002. 1-6.
    [15] Gopalan A, Ramasubramanian S. On identifying additive link metrics using linearly independent cycles and paths. IEEE/ACM Trans. on Networking, 2011,20(3):906-916.
    [16] Ma L, He T, Leung KK, Swami A, Towsley D. Inferring link metrics from end-to-end path measurements:Identifiability and monitor placement. IEEE/ACM Trans. on Networking, 2014,22(4):1351-1368.
    [17] Ma L, He T, Leung KK, Swami A, Towsley D. Identifiability of link metrics based on end-to-end path measurements. In:Proc. of the ACM IMC. ACM, 2013. 391-404.
    [18] Ma L, He T, Leung KK, Swami A, Towsley D. Link identifiability in communication networks with two monitors. In:Proc. of the IEEE GLOBECOM. IEEE, 2013. 1513-1518.
    [19] Ma L, He T, Leung KK, Swami A, Towsley D. Monitor placement for maximal identifiability in network tomography. In:Proc. of the IEEE INFOCOM. IEEE, 2014. 1447-1455.
    [20] Gao Y, Dong W, Wu WB, Chen C, Li XY, Bu JJ. Scalpel:Scalable preferential link tomography based on graph trimming. IEEE/ACM Trans. on Networking, 2016,24(3):1392-1403.
    [21] Dong W, Gao Y, Wu WB, Bu JJ, Chen C, Li XY. Optimal monitor assignment for preferential link tomography in communication networks. IEEE/ACM Trans. on Networking, 2017,25(1):210-223.
    [22] Zhang Y, Roughan M, Willinger W, Qiu LL. Spatio-temporal compressive sensing and internet traffic matrices. In:Proc. of the ACM SIGCOMM. ACM, 2009. 1-12.
    [23] Firooz M, Roy S. Network tomography via compressed sensing. In:Proc. of the IEEE GLOBECOM. IEEE, 2010. 1-5.
    [24] Xu WY, Mallada E, Tang A. Compressive sensing over graphs. In:Proc. of the IEEE INFOCOM. IEEE, 2011. 1-9.
    [25] Kompella RR, Yates J, Greenberg AG, Snoeren AC. Detection and localization of network black holes. In:Proc. of the IEEE INFOCOM. IEEE, 2007. 2180-2188.
    [26] Zeng HY, Kazemian P, Varghese G, McKeown N. Automatic test packet generation. In:Proc. of the ACM CoNEXT. ACM, 2012. 241-252.
    [27] Dhamdhere A, Teixeira R, Dovrolis C, Diot C. NetDiagnoser:Troubleshooting network unreachabilities using end-to-end probes and routing data. In:Proc. of the ACM CoNEXT. ACM, 2007. 1-12.
    [28] Huang YY, Feamster N, Teixeira R. Practical issues with using network tomography for fault diagnosis. ACM SIGCOMM Computer Communication Review, 2008,38(5):53-57.
    [29] Nguyen HX, Thiran P. The Boolean solution to the congested IP link location problem:Theory and practice. In:Proc. of the IEEE INFOCOM. IEEE, 2007. 1-9.
    [30] Ghita D, Karakus C, Argyraki K, Thiran P. Shifting network tomography toward a practical goal. In:Proc. of the ACM CoNEXT. ACM, 2011. 1-12.
    [31] Duffield N. Simple network performance tomography. In:Proc. of the ACM IMC. ACM, 2003. 1-6.
    [32] Ahuja S, Ramasubramanian S, Krunz M. SRLG failure localization in all-optical networks using monitoring cycles and paths. In:Proc. of the IEEE INFOCOM. IEEE, 2008. 700-708.
    [33] Ma L, He T, Swami A, Towsley D, Leung KK, Lowe J. Node failure localization via network tomography. In:Proc. the ACM IMC. ACM, 2014. 195-208.
    [34] Ma L, He T, Swami A, Towsley D, Leung KK. On optimal monitor placement for localizing node failures via network tomography. Performance Evaluation, 2015,91:16-37.
    [35] Ma L, He T, Swami A, Towsley D, Leung KK. Network capability in localizing node failures via end-to-end path measurements. IEEE/ACM Trans. on Networking, 2017,25(1):434-450.
    [36] He T, Bartolini N, Khamfroush H, Kim I, Ma L, Porta TL. Service placement for detecting and localizing failures using end-to-end observations. In:Proc. of the IEEE ICDCS. IEEE, 2016. 560-569.
    [37] Bartolini N, He T, Khamfroush H. Fundamental limits of failure identifiability by Boolean network tomography. In:Proc. of the IEEE INFOCOM. IEEE, 2017. 1-9.
    [38] Gopalan A, Ramasubramanian S. On the maximum number of linearly independent cycles and paths in a network. IEEE/ACM Trans. on Networking, 2014,22(5):1373-1388.
    [39] Wing O, Kim W. The path matrix and its realizability. IRE Trans. on Circuit Theory, 1959,6(3):267-272.
    [40] Ma L, He T, Leung K, Towsley D, Swami A. Efficient identification of additive link metrics via network tomography. In:Proc. of the IEEE ICDCS. IEEE, 2013. 1-10.
    [41] Li F, Thottan M. End-to-end service quality measurement using source-routed probes. In:Proc. of the IEEE INFOCOM. IEEE, 2006. 1-12.
    [42] Nguyen HX, Thiran P. Active measurement for multiple link failures diagnosis in IP networks. In:Proc. of Passive and Active Measurement. 2004. 1-10.
    [43] Agrawal S, Naidu KVM, Rastogi R. Diagnosing link-level anomalies using passive probes. In:Proc. of the IEEE INFOCOM. IEEE, 2007. 1757-1765.
    [44] Barford P, Duffield N, Ron A, Sommers J. Network performance anomaly detection and localization. In:Proc. of the IEEE INFOCOM. IEEE, 2009. 1377-1385.
    [45] Chen Y, Bindel D, Song HH, Katz RH. Algebra-based scalable overlay network monitoring:Algorithms, evaluation, and applications. IEEE/ACM Trans. on Networking, 2007,15(5):1084-1097.
    [46] Zhao Y, Chen Y, Bindel D. Towards unbiased end-to-end network diagnosis. In:Proc. of the ACM SIGCOMM. ACM, 2006. 219-230.
    [47] Shavitt Y, Sun XD, Wool A, Yener B. Computing the unmeasured:An algebraic approach to internet mapping. IEEE Journal on Selected Areas in Communications, 2004,22(1):67-78.
    [48] Tang CP, McKinley PK. On the cost-quality tradeoff in topology-aware overlay path probing. In:Proc. of the IEEE ICNP. IEEE, 2003. 1-12.
    [49] Zheng Q, Cao GH. Minimizing probing cost and achieving identifiability in probe-based network link monitoring. IEEE Trans. on Computers, 2011,62(3):510-523.
    [50] Li GS, Cai WD. Research and development of network tomography. Measurement and Control Technology, 2008,27(2):1-4(in Chinese with English abstract).[doi:10.3969/j.issn.1000-8829.2008.02.001]
    [51] Coceres R, Duffield N, Horowitz J, Towsley D, Bu T. Multicast-based inference of network-internal characteristics:Accuracy of packet loss estimation. In:Proc. of the IEEE INFOCOM. IEEE, 1999. 371-379.
    [52] Coates M, Castro R, Nowak R. Maximum likelihood network topology identification from edge-based unicast measurements. Performance Evaluation Review, 2002,30(1):11-20.
    [53] Shih MF, Hero AO. Unicast-based inference of network link delay distributions with finite mixture models. IEEE Trans. on Signal Processing, 2003,51(8):2219-2228.
    [54] Zhang JZ. Origin-destination network tomography with Bayesian inversion approach. In:Proc. of the IEEE/ACM WI. IEEE, 2006. 1-4.
    [55] Lawrence E, Michailidis G, Nair VN, Xi BW. Network tomography:A review and recent developments. Frontiers in Statistics, 2006,54:345-366.
    [56] Bu T, Duffield N, Presti FL, Towsley D. Network tomography on general topologies. In:Proc. of the ACM SIGMETRICS. ACM, 2002. 1-10.
    [57] Chen AY, Cao J, Bu T. Network tomography:Identifiability and Fourier domain estimation. In:Proc. of the IEEE INFOCOM. IEEE, 2007. 1875-1883.
    [58] He T, Liu C, Swami A, Towsley D, Salonidis T, Bejan AI, Yu P. Fisher information-based experiment design for network tomography. In:Proc. of the ACM SIGMETRICS. ACM, 2015. 389-402.
    [59] Trienekens JJM, Bouman JJ, Zwan MVD. Specification of service level agreements:Problems, principles and practices. Software Quality Journal, 2004,12:43-57.
    [60] Feng CY, Wang LN, Wu K, Wang JP. Bound-based network tomography with additive metrics. In:Proc. of the IEEE INFOCOM. IEEE, 2019. 316-324.
    [61] Wu J, Wang Y, Mao ZM, Shin KG. Internet routing resilience to failures:Analysis and implications. In:Proc. of the CoNEXT. ACM, 2007. 1-12.
    [62] Liu YH, He Y, Li M, Wang JL, Liu KB, Li XY. Does wireless sensor network scale? A measurement study on greenorbs. IEEE Trans. on Parallel and Distributed Systems, 2013,24(10):1983-1993.
    [63] Li HK, Gao Y, Dong W, Chen C. Bound-based network tomography for inferring interesting link metrics. In:Proc. of the IEEE INFOCOM. IEEE, 2020. 1-10.
    [64] Yang RW, Feng CY, Wang LN, Wu WW, Wu K, Wang JP, Xu YL. On the optimal monitor placement for inferring additive metrics of interested paths. In:Proc. of the IEEE INFOCOM. IEEE, 2018. 2141-2149.
    [65] Zhang H, Cai ZP, Li Y. An overview of software-defined network measurement technologies. Scientia Sinica Informationis, 2018, 48(3):293-314(in Chinese with English abstract).[doi:10.1360/N112017-00203]
    [66] Vasseur JP, Agarwal N, Hui J, Shelby Z, Bertrand P, Chauvenet C. RPL:The IP routing protocol designed for low power and lossy networks. Internet Protocol for Smart Objects (IPSO) Alliance, 2011. 1-20. http://www.cse.chalmers.se/edu/year/2019/course/DAT300/PAPERS/rpl.pdf
    [67] Kang NX, Ghobadi M, Reumann J, Shraer A, Rexford J. Efficient traffic splitting on commodity switches. In:Proc. of the ACM CoNEXT. ACM, 2015. 1-13.
    [68] Yang BH, Liu JD, Shenker S, Li J, Zheng K. Keep forwarding:Towards k-link failure resilient routing. In:Proc. of the IEEE INFOCOM. IEEE, 2014. 1617-1625.
    [69] He T, Gkelias A, Ma L, Leung KK, Swami A, Don T. Robust and efficient monitor placement for network tomography in dynamic networks. IEEE/ACM Trans. on Networking, 2017,25(3):1732-1745.
    [70] Li HK, Gao Y, Dong W, Chen C. Preferential link tomography in dynamic networks. IEEE/ACM Trans. on Networking, 2019,27(5):1801-1814.
    [71] Turner D, Levchenko K, Snoeren AC, Savage S. California fault lines:Understanding the causes and impact of network failures. In:Proc. of the ACM SIGCOMM. ACM, 2010. 1-12.
    [72] Ren W, Dong W. Robust network tomography:k-identifiability and monitor assignment. In:Proc. of the IEEE INFOCOM. IEEE, 2014. 1-9.
    [73] Ren W. Study and design of a monitor assignment algorithm based on network tomography[MS. Thesis]. Hangzhou:Zhejiang University, 2017(in Chinese with English abstract).
    [74] Han HS, Qiu LL, Zhang Y. NetQuest:A flexible framework for large-scale network measurement. IEEE/ACM Trans. on Networking, 2009,17(1):106-119.
    [75] Zhao M, Wang WY. Analyzing topology dynamics in ad hoc networks using a smooth mobility model. In:Proc. of the IEEE WCNC. IEEE, 2007. 3279-3284.
    [76] Gu Y, He T. Dynamic switching-based data forwarding for low duty-cycle wireless sensor networks. IEEE Trans. on Mobile Computing, 2011,10(12):1741-1754.
    [77] Li HK, Gao Y, Dong W, Chen C. Taming both predictable and unpredictable link failures for network tomography. IEEE/ACM Trans. on Networking, 2018,26(3):1460-1473.
    附中文参考文献:
    [1] 周爱平,程光,郭晓军.高速网络流量测量方法.软件学报,2014,25(1):135-153. http://www.jos.org.cn/1000-9825/4445.htm[doi:10. 13328/j.cnki.jos.004445]
    [2] 杨慧,李春林,孙治,等.互联网拓扑数据获取方法研究综述.通信技术,2019,52(8):1811-1817.
    [3] 胡治国,田春岐,杜亮,关晓蔷,曹峰.IP网络性能测量研究现状和进展.软件学报,2017,28(1):105-134. http://www.jos.org.cn/1000-9825/5127.htm[doi:10.13328/j.cnki.jos.005127]
    [4] 张荣,金跃辉,杨谈,荣自瞻.分布式网络测量中测量节点的智能选择算法.计算机科学,2015,42(9):70-78.[doi:10.11896/j.issn. 1002-137X.2015.9.015]
    [6] 张宏莉,方滨兴,胡铭曾,姜誉,詹春艳,张树峰.Internet测量与分析综述.软件学报,2003,14(1):110-116. http://www.jos.org.cn/1000-9825/14/110.htm
    [50] 李贵山,蔡皖东.网络断层扫描技术的研究与发展.测控技术,2008,27(2):1-4.[doi:10.3969/j.issn.1000-8829.2008.02.001]
    [65] 张恒,蔡志平,李阳.SDN网络测量技术综述.中国科学:信息科学,2018,48(3):293-314.[doi:10.1360/N112017-00203]
    [73] 任伟.基于网络断层扫描的监测节点部署算法的研究与设计[硕士学位论文].杭州:浙江大学,2017.
    引证文献
引用本文

李惠康,高艺,董玮,陈纯.网络断层扫描:理论与算法.软件学报,2021,32(2):475-495

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2020-05-30
  • 最后修改日期:2020-07-22
  • 在线发布日期: 2020-09-10
  • 出版日期: 2021-02-06
文章二维码
您是第19794375位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号