Article

Fast accurate computation of large-scale IP traffic matrices from link loads

Authors:

Matthew Roughan,

Albert GreenbergAuthors Info & Claims

SIGMETRICS '03: Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems

Pages 206 - 217

https://doi.org/10.1145/781027.781053

Published: 10 June 2003 Publication History

Abstract

A matrix giving the traffic volumes between origin and destination in a network has tremendously potential utility for network capacity planning and management. Unfortunately, traffic matrices are generally unavailable in large operational IP networks. On the other hand, link load measurements are readily available in IP networks. In this paper, we propose a new method for practical and rapid inference of traffic matrices in IP networks from link load measurements, augmented by readily available network and routing configuration information. We apply and validate the method by computing backbone-router to backbone-router traffic matrices on a large operational tier-1 IP network -- a problem an order of magnitude larger than any other comparable method has tackled. The results show that the method is remarkably fast and accurate, delivering the traffic matrix in under five seconds.

References

[1]

M. Grossglauser and J. Rexford, "Passive traffic measurement for IP operations," in The Internet as a Large-Scale Complex System (K.Park and W. Willinger, eds.), Oxford University Press, 2002.

[2]

M. Roughan, A. Greenberg, C. Kalmanek, M. Rumsewicz, J. Yates, and Y. Zhang, "Experience in measuring backbone traffic variability: Models, metrics, measurements and meaning (extended abstract)," in ACM SIGCOMM Internet Measurement Workshop, 2002.

Digital Library

[3]

D. Lam, D. Cox, and J. Widom, "Teletraffic modeling for personal communications services," IEEE Communications Magazine: Special Issues on Teletraffic Modeling Engineering and Management in Wireless and Broadband Networks, 35, pp. 79--87, February 1997.

Digital Library

[4]

J. Kowalski and B. Warfield, "Modeling traffic demand between nodes in a telecommunications network," in ATNAC'95, 1995.

[5]

J. Tinbergen, "Shaping the world economy: Suggestions for an international economic policy." The Twentieth Century Fund, 1962.

[6]

P. Pöyhönen, "A tentative model for the volume of trade between countries," Weltwirtschaftliches Archive, 90, pp. 93--100, 1963.

[7]

A. Medina, N. Taft, K. Salamatian, S. Bhattacharyya, and C. Diot, "Traffic matrix estimation: Existing techniques and new directions," in ACM SIGCOMM, (Pittsburg, USA), August 2002.

Digital Library

[8]

Y. Vardi, "Network tomography: estimating source-destination traffic intensities from link data," J. Am. Statist. Assoc.,91, pp.365--377,1996.

[9]

C. Tebaldi and M. West, "Bayesian inference on network traffic using link count data," J. Amer. Statist. Assoc, 93, pp. 557--576, 1998.

[10]

J. Cao, D. Davis, S. V. Wiel, and B. Yu, "Time-varying network tomography," J. Amer. Statist. Assoc, 95, pp. 1063--1075, 2000.

[11]

A. Adams, T. Bu, R. Cáceres, N. Duffield, T. Friedman, J. Horowitz, F. L. Presti, S. Moon, V. Paxson, and D. Towsley, "The use of end-to-end multicast measurements for characterizing internal network behavior," IEEE Communications Magazine, May 2000.

Digital Library

[12]

M. Coates, A. Hero, R. Nowak, and B. Yu, "Internet tomography," IEEE Signal Processing Magazine, May 2002.

[13]

A. Feldmann, A. Greenberg, C. Lund, N. Reingold, J. Rexford, and F. True, "Deriving traffic demands for operational IP networks: Methodology and experience," IEEE/ACM Transactions on Networking, pp. 265--279, June 2001.

Digital Library

[14]

W. Fang and L. Peterson, "Inter-AS traffic patterns and their implications," in Proceedings of IEEE GLOBECOM '99, (Rio de Janeiro, Brazil), pp. 1859--1868, 1999.

[15]

N. Feamster, J. Borkenhagen, and J. Rexford, "Controlling the impact of BGP policy changes on IP traffic," Tech. Rep. 011106-02-TM, AT&T Labs -- Research, Nov 2001.

[16]

A. Dempster, N. Laird, and D. Rubin, "Maximum likelihood from incomplete data via the em algorithm (with discussion)," J. Roy. Statist. Soc. Ser., 39, pp. 1--38, 1977.

[17]

J. Cao, S. V. Wiel, B. Yu, and Z. Zhu, "A scalable method for estimating network traffic matrices from link counts." preprint.

[18]

J. G. Klincewicz. private communications, 2000.

[19]

A. Feldmann, A. Greenberg, C. Lund, N. Reingold, and J. Rexford, "Netscope: Traffic engineering for IP networks," IEEE Network Magazine, pp. 11--19, March/April 2000.

Digital Library

[20]

A. Medina, C. Fraleigh, N. Taft, S. Bhattacharyya, and C. Diot, "A taxonomy of IP traffic matrices," in SPIE ITCOM: Scalability and Traffic Control in IP Networks II, (Boston, USA), August 2002.

[21]

E. Anderson, Z. Bai, C. Bischof, S. Blackford, J. Demmel, J. Dongarra, J. D. Croz, A. Greenbaum, S. Hammarling, A. McKenney, and D. Sorense, LAPACK Users' Guide. SIAM, 3rd ed., 1999.

Digital Library

[22]

B. Fortz and M. Thorup, "Optimizing OSPF/IS-IS weights in a changing world," To appear in IEEE JSAC Special Issue on Advances in Fundamentals of Network Management, Spring 2002.

Digital Library

Cited By

Zilli CSacco AMonaco DOkafor OEsposito FMarchetto G(2024)Inferring Visibility of Internet Traffic Matrices Using eXplainable AINOMS 2024-2024 IEEE Network Operations and Management Symposium10.1109/NOMS59830.2024.10575173(1-6)Online publication date: 6-May-2024
https://doi.org/10.1109/NOMS59830.2024.10575173
Schynol LPesavento M(2023)Deep Unrolling for Anomaly Detection in Network Flows2023 IEEE 9th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP)10.1109/CAMSAP58249.2023.10403513(61-65)Online publication date: 10-Dec-2023
https://doi.org/10.1109/CAMSAP58249.2023.10403513
Iwata TShimizu HMarumo N(2022)Probabilistic Pedestrian Models for Estimating Unobserved Road PopulationsIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2020.303028123:4(3037-3047)Online publication date: Apr-2022
https://doi.org/10.1109/TITS.2020.3030281
Show More Cited By

Index Terms

Fast accurate computation of large-scale IP traffic matrices from link loads
1. Networks
  1. Network services
    1. Network monitoring

Recommendations

An information-theoretic approach to traffic matrix estimation
SIGCOMM '03: Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications

Traffic matrices are required inputs for many IP network management tasks: for instance, capacity planning, traffic engineering and network reliability analysis. However, it is difficult to measure these matrices directly, and so there has been recent ...
Fast accurate computation of large-scale IP traffic matrices from link loads

A matrix giving the traffic volumes between origin and destination in a network has tremendously potential utility for network capacity planning and management. Unfortunately, traffic matrices are generally unavailable in large operational IP networks. ...
Traffic engineering with estimated traffic matrices
IMC '03: Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement

Traffic engineering and traffic matrix estimation are often treated as separate fields, even though one of the major applications for a traffic matrix is traffic engineering. In cases where a traffic matrix cannot be measured directly, it may still be ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMETRICS '03: Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems

June 2003

338 pages

ISBN:1581136641

DOI:10.1145/781027

General Chairs:
Bill Cheng
TeleGIF
,
Satish Tripathi
University of California at Riverside
,
Program Chairs:
Jennifer Rexford
AT&T Labs -- Research, Florham Park, NJ
,
William H. Sanders
University of Illinois at Urbana-Champaign

ACM SIGMETRICS Performance Evaluation Review Volume 31, Issue 1
June 2003
325 pages
ISSN:0163-5999
DOI:10.1145/885651
Issue’s Table of Contents

Copyright © 2003 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMETRICS: ACM Special Interest Group on Measurement and Evaluation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 June 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SIGMETRICS03

Sponsor:

SIGMETRICS

SIGMETRICS03: International Conference on Measurement and Modeling of Computer Systems

June 11 - 14, 2003

CA, San Diego, USA

Acceptance Rates

SIGMETRICS '03 Paper Acceptance Rate 26 of 222 submissions, 12%;

Overall Acceptance Rate 459 of 2,691 submissions, 17%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

523
Total Citations
View Citations
2,157
Total Downloads

Downloads (Last 12 months)62
Downloads (Last 6 weeks)3

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zilli CSacco AMonaco DOkafor OEsposito FMarchetto G(2024)Inferring Visibility of Internet Traffic Matrices Using eXplainable AINOMS 2024-2024 IEEE Network Operations and Management Symposium10.1109/NOMS59830.2024.10575173(1-6)Online publication date: 6-May-2024
https://doi.org/10.1109/NOMS59830.2024.10575173
Schynol LPesavento M(2023)Deep Unrolling for Anomaly Detection in Network Flows2023 IEEE 9th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP)10.1109/CAMSAP58249.2023.10403513(61-65)Online publication date: 10-Dec-2023
https://doi.org/10.1109/CAMSAP58249.2023.10403513
Iwata TShimizu HMarumo N(2022)Probabilistic Pedestrian Models for Estimating Unobserved Road PopulationsIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2020.303028123:4(3037-3047)Online publication date: Apr-2022
https://doi.org/10.1109/TITS.2020.3030281
Xue GChen YLyu FLi MXue GChen YLyu FLi M(2022)Robust Compressive SensingRobust Network Compressive Sensing10.1007/978-3-031-16829-1_4(35-59)Online publication date: 2-Sep-2022
https://doi.org/10.1007/978-3-031-16829-1_4
Asudeh AAugustine JThirumuruganathan SNazi AZhang NDas GSrivastava D(2021)Scalable signal reconstruction for a broad range of applicationsCommunications of the ACM10.1145/344168964:2(106-115)Online publication date: 25-Jan-2021
https://dl.acm.org/doi/10.1145/3441689
Alparslan OArakawa SMurata M(2020)SDN-Based Control of IoT Network by Brain-Inspired Bayesian Attractor Model and Network SlicingApplied Sciences10.3390/app1017577310:17(5773)Online publication date: 20-Aug-2020
https://doi.org/10.3390/app10175773
Bouleanu IBechet PSârbu A(2020)A Survey on Network Planning and Traffic Engineering for Deployable NetworksInternational conference KNOWLEDGE-BASED ORGANIZATION10.2478/kbo-2020-011326:3(43-48)Online publication date: 20-Jul-2020
https://doi.org/10.2478/kbo-2020-0113
Avin CGhobadi MGriner CSchmid S(2020)On the Complexity of Traffic Traces and ImplicationsProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/33794864:1(1-29)Online publication date: 5-Jun-2020
https://dl.acm.org/doi/10.1145/3379486
Zhao SLu ZWang C(2020)How Can Randomized Routing Protocols Hide Flow Information in Wireless Networks?IEEE Transactions on Wireless Communications10.1109/TWC.2020.300983919:11(7224-7236)Online publication date: Nov-2020
https://doi.org/10.1109/TWC.2020.3009839
Pereira VRocha MSousa P(2020)Traffic Engineering With Three-Segments RoutingIEEE Transactions on Network and Service Management10.1109/TNSM.2020.299320717:3(1896-1909)Online publication date: Sep-2020
https://doi.org/10.1109/TNSM.2020.2993207
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents