微信服务号

微信订阅号

2025-4-22- 19
Home > Archive>Volume 18, Issue 11, 2007 >2669-2682
PDF HTML XML Export Cite reminder
Research on Traffic Matrix Estimation
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [57]
    • |
  • Related [20]
    • |
  • Cited by [8]
    • | |
  • Comments
    Abstract:

    The traffic matrix is one of the crucial inputs in many network planning and traffic engineering tasks,it is agreed that accurate traffic matrices are crucial,but it is usually impossible to directly measure traffic matrices. So,it is an important research topic to infer traffic matrix by reasonably modeling,and incorporating the measurement data of limited links,as well as other prior information.This paper presents the basic concept of traffic matrix and its estimation mechanism,categorizes and analyzes more than twenty different approaches to traffic matrix estimation problem proposed recently,and summarizes current research achievements on traffic matrix estimation problem.This paper also discusses the performance and estimation errors of current approaches. Finally,future research directions and potential applications of these researches are identified.

    Reference
    [1]Medina A,Fraleigh C,Taft N,Bhattacharyya S,Diot C.A taxonomy of IP traffic matrices.In:Firoiu V,Zhang ZL,eds.Proc.of the SPIE Scalability and Traffic Control in IP Networks II.SPIE Vol.4868,Boston:SPIE Publishers,2002.200-213.
    [2]Vardi Y.Network Tomography:Estimating source-destination traffic intensities from link data.Journal of the American Statistical Association,1996,91(433):365-377.
    [3]Callon RW.RFC1195:Use of OSI IS-IS for routing in TCP/IP and dual environments.Internet RFCs,1990.http://rfc.net/ rfc1195.html
    [4]Kowalski J,Warfield B.Modeling traffic demand between nodes in a telecommunications network.In:Proc.of the Australian Telecommunications and Networks Conf.(ATNAC'95).Sydney:IEEE Press,1995.705-710.
    [5]Zhang Y,Roughan M,Duffield N,Greenberg A.Fast accurate computation of large-scale IP traffic matrices from link loads.ACM SIGMETRICS Performance Evaluation Review,2003,31(1):206-217.
    [6]Medina A,Taft N,Salamatian K,Bhattacharyya S,Diot C.Traffic matrix estimation:existing techniques and new directions.In:Paxson V,Balakrishnan H,eds.Proc.of the ACM SIGCOMM 2002 on Applications,Technologies,Architectures,and Protocols for Computer Communications.Pittsburgh:ACM Press,2002.161-174.
    [7]Medina A,Salamatian K,Taft N,Matta I,Tsang Y,Diot C.On the convergence of statistical techniques for inferring network traffic demands.Technical Report,BUCS-2003-003,Boston:Computer Science,Boston University,2003.
    [8]Medina A,Salamatian K,Taft N,Matta I,Diot C.A two-step statistical approach for inferring network traffic demands.Technical Report,BUCS-2004-011,Boston:Computer Science,Boston University,2004.
    [9]Gunnar A,Johansson M,Telkamp T.Traffic matrix estimation on a large IP backbone:A comparison on real data.In:Lombardo A,Kurose JF,eds.Proc.of the ACM SIGCOMM Internet Measurement Conf.(IMC).Sicily:ACM Press,2004.149-160.
    [10]Zhang Y,Roughan M,Lund C,Donoho D.An information-theoretic approach to traffic matrix estimation.In:Feldmann A,Zitterbart M,Crowcroft J,Wetherall D,eds.Proc.of the ACM SIGCOMM 2003,on Applications,Technologies,Architectures,and Protocols for Computer Communications.Karlsruhe:ACM Press,2003.301-312.
    [11]Tebaldi C,West M.Bayesian inference on network traffic using link count data.Journal of the American Statistical Association,1998,93(442):557-576.
    [12]Vaton S,Gravey A.Network Tomography:An iterative Bayesian analysis.In:Charzinski J,Lehnert R,Tran-Gia P,eds.Proc.of the 18th Int'l Teletraffic Congress (ITC).Berlin,2003.261-270.
    [13]Cao J,Davis D,Wiel SV,Yu B.Time-Varying network Tomography:Router link data.Journal of the American Statistical Association,2000,95(452):1063-1075.
    [14]Cao J,Vander Wiel S,Yu B,Zhu Z.A scalable method for estimating network traffic matrices from link counts.Technical Report,Bell Labs,2000.
    [15]Liang G,Yu B.Maximum pseudo likelihood estimation in network Tomography.IEEE Trans.on Signal Processing,2003,51(8):2043-2053.
    [16]Juva I,Vaton S,Virtamo J.Quick traffic matrix estimation based on link count covariances.In:Proc.of the IEEE Int'l Conf.on Communications (ICC).Istanbul:IEEE Communications Society,2006.603-608.
    [17]Goldschmidt O.ISP backbone traffic inference methods to support traffic engineering.In:Internet Statistics and Metrics Analysis (ISMA) Workshop.San Diego,2000.http://www.caida.org/workshops/isma/0012/talks/olivier/
    [18]Eum S,Murphy J,Harris RJ.A fast accurate LP approach for traffic matrix estimation.In:Liang XJ,Xin ZH,Iversen VB,KUO GS,eds.Proc.of the 19th Int'l Teletraffic Congress (ITC19).Beijing:Beijing University of Posts and Telecommunications Press,2005.243-252.
    [19]Soule A,Nucci A,Cruz R,Leonardi E,Taft N.How to identify and estimate the largest traffic matrix elements in a dynamic environment.ACM SIGMETRICS Performance Evaluation Review,2004,32(1):73-84.
    [20]Soule A,Lakhina A,Taft N,Papagiannaki K,Salamatian K,Nucci A,Crovella M,Diot C.Traffic matrices:Balancing measurements,inference and modeling.ACM SIGMETRICS Performance Evaluation Review,2005,33(1):362-373.
    [21]Erramill V,Crovella M,Taft N.An independent-connection model for traffic matrices.In:Almeida JM,Almeida VAF,Barford P,eds.Proc.of the ACM SIGCOMM Internet Measurement Conf.(IMC).Rio de Janeriro:ACM Press,2006.251-256.
    [22]Zhang Y,Roughan M,Lund C,Donoho DL.Estimating point-to-point and point-to-multipoint traffic matrices:An information-theoretic approach.Networking.IEEE/ACM Trans.on Networking (TON),2005,13(5):947-960.
    [23]Vaton S,Bedo JS.Network traffic matrix:How can one learn the prior distributions from the link counts only-In:Gelfand S,ed.Proc.of the IEEE Int'l Conf.on Communications (ICC).Parris:IEEE Communications Society,2004.2138-2142.
    [24]Juva I,Kuusela P,Virtamo J.A case study on traffic matrix estimation under Gaussian distribution.In:Proc.of the 17th Nordic Teletraffic Seminar.2004.49-60.
    [25]Dempster AP,Laird NM,Rubin DB.Maximum likelihood from incomplete data via the EM algorithm (with discussion).Journal of the Royal Statistical Society (Series B),1977,39(1):1-38.
    [26]Dellaert F.The expectation maximization algorithm.Technical Report,GIT-GVU-02,College of Computing,Georgia Institute of Technology,2002.
    [27]Roy R,Trappe W.An introduction to network tomography techniques.Technical Report,Piscataway,2004.
    [28]Liang G,Yu B.Maximum pseudo likelihood estimation in network Tomography.IEEE Trans.on Signal Processing,2003,51(8):2043-2053.
    [29]Bermolen P,Vaton S,Juva I.Search for optimality in traffic matrix estimation:A rational approach by Cramér-Rao lower bounds.In:Proc.of the 2nd EuroNGI NGI Conf.on Next Generation Internet Design and Engineering.Valencia:IEEE Communications Society,2006.224-231.
    [30]Vaton S,Bedo JS,Gravey A.Advanced methods for the estimation of the origin destination traffic matrix.In:Performance Evaluation and Planning Methods for the Next Generation Internet.2005.Springer-Verlag,2005.189-225.
    [31]Shaikh A,Greenberg A.OSPF monitoring:Architecture,design,and deployment experience.In:Proc.of the USENIX Symp.on Networked Systems Design and Implementation (NSDI).San Francisco:ACM Press,2004.
    [32]Teixeira R,Agarwal S,Rexford J.BGP routing changes:Merging views from two ISPs.ACM SIGCOMM Computer Communication Review,2005,35(3):79-82.
    [33]Wu J,Mao ZM,Rexford J,Wang J.Finding a needle in a haystack:Pinpointing significant BGP routing changes in an IP network.In:Proc.of the USENIX Symp.on Networked System Design and Implementation (NSDI).New York:ACM Press,2005.
    [34]Nucci A,Cruz R,Taft N,Diot C.Design of IGP link weight changes for estimation of traffic matrices.In:Li VOK,ed.Proc.of the IEEE INFOCOM.Piscataway:IEEE Communications Society,2004.
    [35]Soule A,Nucci A,Cruz R,Leonardi E,Taft N.Estimating dynamic traffic matrices by using viable routing changes.IEEE/ACM Trans.on Networking,2007,15(3):485-498.
    [36]Papagiannaki K,Taft N,Lakhina A.A distributed approach to measure IP traffic matrices.In:Lombardo A,Kurose JF,eds.Proc.of the ACM SIGCOMM Internet Measurement Conf.(IMC).Taormina:ACM Press,2004.161-174.
    [37]Lakhina A,Papagiannaki K,Crovella M,Diot C,Kolaczyk ED,Taft N.Structural analysis of network traffic flows.In:Coffman E,ed.Proc.of the ACM SIGMETRICS/Performance.New York:ACM Press,2004.61-72.
    [38]Soule A,Salamatian K,Taft N.Traffic matrix tracking using Kalman filters.ACM SIGMETRICS Performance Evaluation Review,2005,33(3):24-31.
    [39]Rahman MM,Saha S,Chengan U,Alfa AS.IP traffic matrix estimation methods:Comparisons and improvements.In:Proc.of the IEEE Int'l Conf.on Communications (ICC).Istanbul:IEEE Communications Society,2006.90-96.
    [40]Zhang Y,Ge Z.Finding critical traffic matrices.In:Tsuchiya T,ed.Proc.of the 2005 Int'l Conf.on Dependable Systems and Networks (DSN).Yokohama:IEEE Computer Society,2005.188-197.
    [41]Shioda S,Ohtani K.Proposals on the source-destination traffic matrix estimation for IP-based VPNs.Proc.of IEEE GLOBECOM,2005,1(28):348-353.
    [42]Zhao Q,Kumar A,Wang J,Xu J.Data streaming algorithms for accurate and efficient measurement of traffic and flow matrices.In:Eager DL,Williamson CL,Borst SC,Lui JCS,eds.Proc.of the ACM SIGMETRICS.Banff:ACM Press,2005.350-361.
    [43]Zhao Q,Ge Z,Wang J,Xu J.Robust traffic matrix estimation with imperfect information:Making use of multiple data sources.ACM SIGMETRICS Performance Evaluation Review,2006,34(1):133-144.
    [44]Liang G,Taft N,Yu B.A fast lightweight approach to origin-destination IP traffic estimation using partial measurements.IEEE/ACM Trans.on Networking (TON),2006,14(S1):2634-2648.
    [45]Zhao GF,Wang LJ,Tang H,Cheng DJ.Dynamic traffic matrix measurement model of network based IP/MPLS.Journal of China Institute of Communications,2003,24(10):145-152 (in Chinese with English abstract).
    [46]Liu ZQ,Chen CJ.Routing inference based on traffic matrix estimation.Journal of the China Railway Society,2005,27(6):66-70 (in Chinese with English abstract).
    [47]Hong T,Tong LF,Guo GZ.An assignment model on traffic matrix estimation.In:Jiao L,et al.,eds.Proc.of the Int'l Conf.on Natural Computation (ICNC 2006).Xi'an:Springer-Verlag,2006.295-304.
    [48]Juva I.Traffic matrix estimation[MS.Thesis].Helsinki:Helsinki University of Technology,2005.
    [49]Liu ZQ,Chen CJ.Routing inference based on pseudo traffic matrix estimation.In:Cao J,Mu Y,Feng B,Perez-Hernandez M,Xiao B,eds.Proc.of the 20th Int'l Conf.on Advanced Information Networking and Applications (AINA).Washington:IEEE Computer Society,2006.159-164.
    [50]Lakhina A,Crovella M,Diot C.Diagnosing network-wide traffic anomalies.In:Yavatkar R,Zegura EW,Rexford J,eds.Proc.of the ACM SIGCOMM 2004 Conf.on Applications,Technologies,Architecures,and Protocols for Computer Communications.New York:ACM Press,2004.219-230.
    [51]Jin S,Yeung DS,Wang X,Tsang ECC.A covariance matrix based approach to internet anomaly detection.In:Yeung DS,Liu ZQ,Wang XZ,Yan H,eds.Proc.of the Int'l Conf.on Machine Learning and Cybernetics (ICMLC).Guangzhou:IEEE Press,2005.691-700.
    [52]Roughan M,Thorup M,Zhang Y.Traffic engineering with estimated traffic matrices.In:Bieber G,Kirste T,eds.Proc.of the ACM SIGCOMM Internet Measurement Conf.(IMC).San Diego:ACM Press,2003.248-258.
    [53]Nucci A,Sridharan A,Taft N.The problem of synthetically generating IP traffic matrices:Initial recommendations.ACM SIGCOMM Computer Communication Review,2005,35(3):19-32.
    [54]Roughan M.Simplifying the synthesis of Internet traffic matrices.ACM SIGCOMM Computer Communication Review,2005,35(3):93-96.
    [55]Uhlig S,Quoitin B,Lepropre J,Balon S.Providing public intradomain traffic matrices to the research community.ACM SIGCOMM Computer Communication Review,2006,36(1):83-86.
    [45]赵国锋,王灵矫,唐红,程代杰.基于IP/MPLS网络的动态业务流量矩阵测量模型.通信学报,2003,24(10):145-152.
    [46]刘紫千,陈常嘉.基于流量矩阵估计的路由推断算法.铁道学报,2005,27(6):66-70.
    Comments
    Comments
    分享到微博
    Submit
Get Citation

周静静,杨家海,杨扬,张辉.流量矩阵估算的研究.软件学报,2007,18(11):2669-2682

Copy
Share
Article Metrics
  • Abstract:8515
  • PDF: 9744
  • HTML: 0
  • Cited by: 0
History
  • Received:April 05,2007
  • Revised:June 30,2007
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2037274Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063