网络测量部署模型及其优化算法
作者:
基金项目:

Supported by the National Natural Science Foundation of China under Grant Nos.60603062, 60373023 (国家自然科学基金); the National Basic Research Program of China under Grant No.2007CB310901 (国家重点基础研究发展计划(973)); the Natural Science Foundation of Hu'nan Province of China under Grant No.06JJ3035 (湖南省自然科学基金)

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

    ISP(Internet service providers)和企业部署网络监测系统以获取网络的性能数据,确保网络的安全性和连通性,最终加强和改善全局的网络性能.网络监测系统的设计和优化是目前的一个研究热点,其优化目标是最小化监测系统的部署代价和维护代价,并使得对网络的影响尽可能地小.根据测量方式和收集框架的不同,可以设计出不同的网络测量部署模型.这些模型的最优化问题通常是NP难的,一般采用整数规划、设计近似算法和映射到经典优化问题等方法来求取模型的优化解.总结了网络测量部署模型及其优化算法的研究现状,指出了该领域中需要进一步研究的热点问题.

    Abstract:

    Network monitoring systems are deployed by Internet Service Providers (ISP) and enterprises to obtain network performance information and enhance the global network performance. A constant monitoring is also required to enforce and ensure both connectivity and security of the infrastructure. Designing and developing the infrastructure and optimization algorithms for network monitoring system have raised a great deal of interest recently. One of the key issues in this domain is to minimize the overhead in terms of deploying cost, maintenance cost and additional traffic. Due to different measurement approaches and polling infrastructure, there are many network measurement deploying models. Unfortunately, the optimization problems of these models are generally NP-hard. These optimization problems used to be solved by integer programming, designing approximation algorithms or mapping it to classic optimization problems. In this paper, the chief researches of network measurement deploying models and optimization algorithms in the world are introduced. Lastly, some open issues are presented to be further studied in the network measurement deploying models field.

    参考文献
    [1]Asgari A,Trimintzios P,Irons M,Pavlou G,Egan R,den Berghe SV.A scalable real-time monitoring system for supporting traffic engineering.In:Proc.of the IEEE Workshop on IP Operations and Management.IEEE Communication Society,2002.202-207.
    [2]Zhang HL,Fang BX,Hu MZ,Jiang Y,Zhan CY,Zhang SF.A survey of Internet measurement and analysis.Journal of Software,2003,14(1):110-116 (in Chinese with English abstract).http://www.jos.org.cn/1000-9825/14/110.htm
    [3]Lin Y,Cheng SD,Wu HY,Jin YH,Wang WD.The achievement of end-to-end performance measurement technology in IP networks.Acta Electronica Sinica,2003,31(8):1227-1233 (in Chinese with English abstract).
    [4]Chaudet C,Fleury E,Guérin Lassous I,Rivano H,Voge ME.Optimal positioning of active and passive monitoring devices.In:Proc.of the CoNEXT 2005.New York:ACM Press,2005.71-82.
    [5]Moore D,Shannon C,Brown D,Voelker GM,Savage S.Inferring Internet denial-of-service activity.ACM Trans.on Computer System,2006,24(2):115-139.
    [6]Paxson V,Mahdavi J,Adams A,Mathis M.An architecture for large-scale Internet measurement.IEEE Communications,1998,36(8):48-54.
    [7]Claffy K,Monk TE,McRobb D.Internet tomography.Nature,1999.http://www.nature.com/nature/webmatters/tomog/tomog.html
    [8]Kalidindi S,Zekauskas MJ.Surveyor:An infrastructure for Internet performance measurements.In:Proc.of the INET'99.IEEE Communication Society,1999.
    [9]Stallings W.SNMP,SNMPv2,SNMPv3,and RMON 1 and 2.3rd ed.,Boston:Addison-Wesley Professional,1998.
    [10]Cisco System.NetFlow services and application.Cisco System White Paper,1999.
    [11]Hochbaum DS.Approximation Algorithm for NP-Hard Problems.Boston:PWS Publishing Company,1997.
    [12]Suh K,Guo Y,Kurose J,Towsley D.Locating network monitors:Complexity,heuristics and coverage.In:Proc.of the IEEE INFOCOM 2005.IEEE Communication Society,2005.351-361.
    [13]Khuller S,Moss A,Naor J.The budgeted maximum coverage problem.Information Processing Letters,1999,7(1):39-45.
    [14]Slavik P.Improved performance of the greedy algorithm for the minimum set cover and minimum partial cover problems.Electronic Colloquium on Computational Complexity,1995,2(53).
    [15]Chudak F,Shmoys D.Improved approximation algorithms for the uncapacitated facility location problems.ACM SIAM Journal on Computing,2003,33(1):1-25.
    [16]Breitbart Y,Chan CY,Garofalakis M,Rastogi R,Silberschatz A.Efficiently monitoring bandwidth and latency in IP networks.In:Proc.of the IEEE INFOCOM 2001.IEEE Communication Society,2001.933-942.
    [17]Liu XH,Yin JP,Tang LL,Zhao JM.Analysis of efficient monitoring method for the network flow.Journal of Software,2003,14(2):300-304 (in Chinese with English abstract).http://www.jos.org.cn/1000-9825/14/300.htm
    [18]Liu XH,Yin JP,Lu XC,Zhao JM.A monitoring model for link bandwidth usage of network based on weak vertex cover.Journal of Software,2004,15(4):545-549 (in Chinese with English abstract).http://www.jos.org.cn/1000-9825/15/545.htm
    [19]Zhang Y,Zhu H.Approximation algorithm for weighted weak vertex cover.Journal of Computer Science and Technology,2004,19(6):782-786.
    [20]Zhang Y,Zhu H.An approximation algorithm for weighted weak vertex cover problem in undirected graphs.In:Chwa KY,Munro JI,eds.Proc.of the COCOON 2004.LNCS 3106,Berlin:Springer-Verlag,2004.143-150.
    [21]Cai ZP,Yin JP,Liu XH,Liu F,Lü SH.Efficiently monitoring link bandwidth in IP networks.In:Proc.of the IEEE GLOBECOM 2005.IEEE Communication Society,2005.354-358.
    [22]Liu XH,Yin JP,Cai ZP.The analysis of algorithm for efficient network flow monitoring.In:Proc.of the IEEE Workshop on IP Operations and Management.IEEE Communication Society,2004.29-33.
    [23]Cooperative association for Internet data analysis (CAIDA).http://www.caida.org/
    [24]Active measurement project (AMP).http://amp.nlanr.net/
    [25]IP Performance Metrics Working Group.http://www.ietf.org/html.charters/ ippm-charter.html
    [26]Cohen R,Raz D.The Internet dark matter-On the missing links in the AS connectivity map.In:Proc.of the IEEE INFOCOM 2006.IEEE Communication Society,2006.
    [27]Oliveira R,Lad M,Zhang B,Pei D,Massey D,Zhang L.Placing BGP monitors in the Internet.Technical Report,TR 060017,CS Department,UCLA,2006.
    [28]Walz J,Levine B.A hierarchical multicast monitoring scheme.In:Proc.of the NGC on Networked Group Communication.ACM Press,2000.105-116.
    [29]Bejerano Y,Rastogi R.Robust monitoring of link delays and faults in IP networks.In:Proc.of the IEEE INFOCOM 2003.IEEE Communication Society,2003.134-144.
    [30]Kumar R,Kaur J.Efficient beacon placement for network tomography.In:Proc.of the ACM SIGCOMM IMC.ACM Press,2004.181-186.
    [31]Jamin S,Jin C,Jin Y,Raz D,Shavitt Y,Zhang L.On the placement of Internet instrumentation.In:Proc.of the IEEE INFOCOM 2000.IEEE Communication Society,2000.295-304.
    [32]Horton J,Lopez-Ortiz A.On the number of distributed measurement points for network tomography.In:Proc.of the ACM SIGCOMM IMC.ACM Press,2003.204-209.
    [33]Breitbart Y,Dragan F,Gobjuka H.Effective network monitoring.In:Proc.of the IEEE ICCCN 2004.IEEE Communication Society,2004.394-399.
    [34]Francis P,Jamin S,Paxson V,Zhang L,Raz D,Jin Y.An architecture for a global Internet host distance estimation service.In:Proc.of the IEEE INFOCOM'99.IEEE Communication Society,1999.210-217.
    [35]Francis P,Jamin S,Jin C,Jin Y,Paxson V,Raz D,Shavitt Y,Zhang L.IDMaps:A global Internet host distance estimation service.IEEE/ACM Trans.on Networking,2001,9(5):525-540.
    [36]Bartal Y.Probabilistic approximation of metric space and its algorithmic applications.In:Proc.of the 37th Annual IEEE Symp.on Foundations of Computer Science.IEEE Communication Society,1996.184-193.
    [37]Adler M,Bu T,Sitaraman B,Towsley D.Tree layout for Internet network characterizations in multicast networks.In:Proc.of the NGC 2001.Springer-Verlag,2001.189-204.
    [38]Reddy A,Govindan R,Estrin D.Fault isolation in multicast trees.In:Proc.of the ACM SIGCOMM 2000.ACM Press,2000.29-40.
    [39]Markopoulou A,Iannaccone G,Bhattacharyya S,Chuah C,Diot C.Characterization of failures in an IP backbone.In:Proc.of the IEEE INFOCOM 2004.IEEE Communication Society,2004.7-11.
    [40]Nguyen H,Thiran P.Active measurement for multiple link failures diagnosis in IP networks.In:Proc.of the Passive and Active Measurement Workshop (PAM 2004).Springer-Verlag,2004.185-194.
    [41]Lin YJ,Chan MC.A scalable monitoring approach based on aggregation and refinement.IEEE Journal on Selected Areas in Communications,2002,20(4):677-690.
    [42]Li L,Thottan M,Yao B,Paul S.Distributed network monitoring with bounded link utilization in IP networks.In:Proc.of the IEEE INFOCOM 2003.IEEE Communication Society,2003.1189-1198.
    [43]Cai ZP,Yin JP,Liu XH,Liu F,Lü SH.Distributed network monitoring model with link constraints.Journal of Computer Research and Development,2006,43(4):601-606 (in Chinese with English abstract).
    [44]SIGCOMM.http://www.sigcomm.org/
    [45]INFOCOM.http://www.ieee-infocom.org/
    [46]SIGMETRICS (Int'l Conf.on measurement and modeling of computer systems).http://www.sigmetrics.org/
    [47]IMC (Internet measurement Conf.).http://www.imconf.net/
    [48]PAM (passive and active measurement Conf.).http://www.pamconf.org/
    [49]Aida M,Miyoshi N,Ishibashi K.A scalable and lightweight QoS monitoring technique combining passive and active approaches.In:Proc.of the IEEE INFOCOM 2003.IEEE Communication Society,2003.125-133.
    [50]Ishibashi K,Kanazawa T,Aida M.Active/Passive combination-type performance measurement method using change-of-measure framework.Computer Communications,2004,E87-B(1):132-141.
    [51]Cai ZP,Yin JP,Liu XH,Lü SH,Liu F.Passive calibration of active measuring latency method.Acta Electronica Sinica,2005,33(11):9-12 (in Chinese with English abstract).
    [52]Hu NN,Li L,Mao ZMM,Steenkiste P,Wang J.A measurement study of Internet bottlenecks.In:Proc.of the IEEE INFOCOM 2005.IEEE Communication Society,2005.1689-1700.
    [53]Thottan M,Li L,Yao B,Mirrokni VS,Paul S.Distributed network monitoring for evolving IP networks.In:Proc.of the 24th Int'l Conf.on Distributed Computing Systems.IEEE Communication Society,2004.712-719.
    [54]Cai ZP,Yin JP,Liu F.,Liu XH.Distributed monitoring model with bounded delay.Journal of Software,2006,17(1):117-123 (in Chinese with English abstract).http://www.jos.org.cn/1000-9825/17/117.htm
    [55]Duffield N,Lund C,Thorup M.Learn more,sample less:Control of volume and variance in network measurement.IEEE Trans.on Information Theory,2005,51(5):1756-1775.
    [56]Choi B,Park J,Zhang ZL.Adaptive random sampling for traffic load measurement.In:Proc.of the IEEE ICC 2003.IEEE Communication Society,2003.1552-1556.
    [57]Bar-Ford P,Bestavros A,Byers J,Crovella M.On the marginal utility of network topology measurements.In:Proc.of the ACM SIGCOMM Internet Measurement Workshop.ACM Press,2001.291-302.
    [58]Liotta A,Pavlou G,Knight G.Active distributed monitoring for dynamic large-scale networks.In:Proc.of the IEEE Int'l Conf.on Communications (ICC 2001).IEEE Communication Society,2001.1544-1550.
    [59]Liotta A,Pavlou G,Knight G.Exploiting agent mobility for large scale network monitoring.IEEE Network,2002,16(3):7-15.
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

蔡志平,刘 芳,赵文涛,刘湘辉,殷建平.网络测量部署模型及其优化算法.软件学报,2008,19(2):419-431

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

京公网安备 11040202500063号