Article

Structural analysis of network traffic flows

Authors:

Anukool Lakhina,

Konstantina Papagiannaki,

Christophe Diot,

Eric D. Kolaczyk,

Nina TaftAuthors Info & Claims

SIGMETRICS '04/Performance '04: Proceedings of the joint international conference on Measurement and modeling of computer systems

Pages 61 - 72

https://doi.org/10.1145/1005686.1005697

Published: 01 June 2004 Publication History

Abstract

Network traffic arises from the superposition of Origin-Destination (OD) flows. Hence, a thorough understanding of OD flows is essential for modeling network traffic, and for addressing a wide variety of problems including traffic engineering, traffic matrix estimation, capacity planning, forecasting and anomaly detection. However, to date, OD flows have not been closely studied, and there is very little known about their properties.We present the first analysis of complete sets of OD flow time-series, taken from two different backbone networks (Abilene and Sprint-Europe). Using Principal Component Analysis (PCA), we find that the set of OD flows has small intrinsic dimension. In fact, even in a network with over a hundred OD flows, these flows can be accurately modeled in time using a small number (10 or less) of independent components or dimensions.We also show how to use PCA to systematically decompose the structure of OD flow timeseries into three main constituents: common periodic trends, short-lived bursts, and noise. We provide insight into how the various constitutents contribute to the overall structure of OD flows and explore the extent to which this decomposition varies over time.

References

[1]

P. Barford, J. Kline, D. Plonka, and A. Ron. A signal analysis of network traffic anomalies. In Internet Measurement Workshop, Marseille, November 2002.

Digital Library

[2]

S. Bhattacharyya, C. Diot, J. Jetcheva, and N. Taft. Pop-Level and Access-Link-Level Traffic Dynamics in a Tier-1 POP. In Internet Measurement Workshop, San Francisco, November 2001.

Digital Library

[3]

J. Brutlag. Aberrant behavior detection in timeseries for network monitoring. In USENIX LISA, New Orleans, December 2000.

Digital Library

[4]

J. Cao, D. Davis, S. V. Weil, and B. Yu. Time-Varying Network Tomography. J. of the American Statistical Association, pages 1063--1075, 2000.

[5]

Cisco NetFlow. At www.cisco.com/warp/public/732/Tech/netflow/.

[6]

M. Crovella and E. Kolaczyk. Graph Wavelets for Spatial Traffic Analysis. In IEEE INFOCOM, San Francisco, April 2003.

[7]

D. Donoho. High-Dimensional Data Analysis: The Curses and Blessings of Dimensionality. In American Math. Society. Available at: www-stat.stanford.edu/~donoho/Lectures/AMS2000/, 2000.

[8]

N. Duffield, C. Lund, and M. Thorup. Estimating Flow Distributions from Sampled Flow Statistics. In ACM SIGCOMM, Karlsruhe, August 2003.

Digital Library

[9]

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

Digital Library

[10]

N. Hohn and D. Veitch. Inverting Sampled Traffic. In Internet Measurement Conference, Miami, October 2003.

Digital Library

[11]

H. Hotelling. Analysis of a complex of statistical variables into principal components. J. Educ. Psy., pages 417--441, 1933.

[12]

Juniper Traffic Sampling. At www.juniper.net/techpubs/software/junos/junos60/swconfig60-policy/html/%sampling-overview.html.

[13]

M. Kirby and L. Sirovich. Application of the Karhunen-Loève procedure for the characterization of human faces. IEEE Trans. Pattern Analysis and Machine Intelligence, pages 103--108, 1990.

Digital Library

[14]

B. Krishnamurthy, S. Sen, Y. Zhang, and Y. Chen. Sketch-based Change Detection: Methods, Evaluation, and Applications. In Internet Measurement Conference, Miami, October 2003.

Digital Library

[15]

L. Sirovich and K. S. Ball and L. R. Keefe. Plane Waves and Structures in Turbulent Channel Flow. Phys. Fluids. A, page 2217--2226, 1990.

[16]

A. Lakhina, K. Papagiannaki, M. Crovella, C. Diot, E. D. Kolaczyk, and N. Taft. Analysis of Origin Destination Flows (Raw Data). Technical Report BUCS-2003-022, Boston University, 2003.

[17]

W. Leland, M. Taqqu, W. Willinger, and D. Wilson. On the Self-Similar Nature of Ethernet Traffic (Extended Version). Transactions on Networking, pages 1--15, Feburary 1994.

Digital Library

[18]

A. Medina, N. Taft, K. Salamatian, S. Bhattacharyya, and C. Diot. Traffic Matrix Estimation: Existing Techniques and New Directions. In ACM SIGCOMM, Pittsburgh, August 2002.

Digital Library

[19]

A. Nucci, R. Cruz, N. Taft, and C. Diot. Design of IGP Link Weight Changes for Traffic Matrix Estimation. In IEEE INFOCOM, Hong Kong, April 2004.

[20]

K. Papagiannaki, N. Taft, and C. Diot. Impact of Flow Dynamics on Traffic Engineering Design Principles. In IEEE INFOCOM, Hong Kong, April 2004.

[21]

K. Papagiannaki, N. Taft, Z. Zhang, and C. Diot. Long-Term Forecasting of Internet Backbone Traffic: Observations and Initial Models. In IEEE INFOCOM, San Francisco, April 2003.

[22]

V. Paxson and S. Floyd. Wide Area Traffic: The Failure of Poisson Modeling. Transactions on Networking, pages 236--244, June 1995.

Digital Library

[23]

R. W. Preisendorfer. Principal Component Analysis in Meteorology and Oceanography. Elsevier, 1988.

[24]

M. Roughan and J. Gottlieb. Large scale measurement and modeling of backbone internet traffic. In SPIE ITCom, Boston, August 2002.

[25]

M. Roughan, A. Greenberg, C. Kalmanek, M. Rumsewicz, J. Yates, and Y. Zhang. Experience in measuring backbone traffic variability: Models, metrics, measurements and meaning. In International Teletraffic Conference (ITC-18), Berlin, September 2003.

[26]

S. Sarvotham, R. Riedi, and R. Baraniuk. Network Traffic Analysis and Modeling at the Connection Level. In Internet Measurement Workshop, San Francisco, November 2001.

Digital Library

[27]

A. Soule, A. Nucci, E. Leonardi, R. Cruz, and N. Taft. How to Identify and Estimate the Largest Traffic Matrix Elements in a Dynamic Environment. In ACM SIGMETRICS, New York, June 2004.

Digital Library

[28]

G. Strang. Linear Algebra and its Applications. Thomson Learning, 1988.

[29]

C. Tebaldi and M. West. Bayesian Inference of Network Traffic Using Link Data. J. of the American Statistical Association, pages 557--573, June 1998.

[30]

D. T'so, R. D. Frostig, E. E. Lieke, and A. Grinvald. Functional Organization of primate visual cortex revealed by high resolution optical imaging. Science, pages 417--420, 1990.

[31]

Y. Vardi. Network Tomography: Estimating Source-Destination Traffic Intensities from Link Data. J. of the American Statistical Association, pages 365--377, 1996.

[32]

V. Yegneswaran, P. Barford, and J. Ullrich. Internet Intrusions: Global Characteristics and Prevalence. In ACM SIGMETRICS, San Diego, June 2003.

Digital Library

[33]

Y. Zhang, M. Roughan, N. Duffield, and A. Greenberg. Fast Accurate Computation of Large-Scale IP Traffic Matrices from Link Loads. In ACM SIGMETRICS, San Diego, June 2003.

Digital Library

[34]

Y. Zhang, M. Roughan, C. Lund, and D. Donoho. An Information-Theoretic Approach to Traffic Matrix Estimation. In ACM SIGCOMM, Karlsruhe, August 2003.

Digital Library

Cited By

Borgianni LAdami DGiordano SPagano M(2024)Enhancing Reliability in Rural Networks Using a Software-Defined Wide Area NetworkComputers10.3390/computers1305011313:5(113)Online publication date: 28-Apr-2024
https://doi.org/10.3390/computers13050113
Shi X(2024)Dyadic Treatment Effects: Theory and Empirical ApplicationsSSRN Electronic Journal10.2139/ssrn.4813012Online publication date: 2024
https://doi.org/10.2139/ssrn.4813012
Babai EOkamura K(2024)A Contextual Approach for Improving Anomalous Network Traffic Flows Prediction2024 IEEE 48th Annual Computers, Software, and Applications Conference (COMPSAC)10.1109/COMPSAC61105.2024.00353(2203-2208)Online publication date: 2-Jul-2024
https://doi.org/10.1109/COMPSAC61105.2024.00353
Show More Cited By

Index Terms

Structural analysis of network traffic flows
1. Computing methodologies
  1. Modeling and simulation
    1. Model development and analysis
      1. Modeling methodologies
2. Networks
  1. Network services

Recommendations

Structural analysis of network traffic flows

Network traffic arises from the superposition of Origin-Destination (OD) flows. Hence, a thorough understanding of OD flows is essential for modeling network traffic, and for addressing a wide variety of problems including traffic engineering, traffic ...
Sensitivity of PCA for traffic anomaly detection
SIGMETRICS '07 Conference Proceedings

Detecting anomalous traffic is a crucial part of managing IP networks. In recent years, network-wide anomaly detection based on Principal Component Analysis (PCA) has emerged as a powerful method for detecting a wide variety of anomalies. We show that ...
Sensitivity of PCA for traffic anomaly detection
SIGMETRICS '07: Proceedings of the 2007 ACM SIGMETRICS international conference on Measurement and modeling of computer systems

Detecting anomalous traffic is a crucial part of managing IP networks. In recent years, network-wide anomaly detection based on Principal Component Analysis (PCA) has emerged as a powerful method for detecting a wide variety of anomalies. We show that ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMETRICS '04/Performance '04: Proceedings of the joint international conference on Measurement and modeling of computer systems

June 2004

450 pages

ISBN:1581138733

DOI:10.1145/1005686

General Chair:
E. G. Coffman
Columbia University
,
Program Chairs:
Zhen Liu
IBM Research
,
Arif Merchant
HP Labs

ACM SIGMETRICS Performance Evaluation Review Volume 32, Issue 1
June 2004
432 pages
ISSN:0163-5999
DOI:10.1145/1012888
Issue’s Table of Contents

Copyright © 2004 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SIGMETRICS04

Sponsor:

SIGMETRICS04: SIGMETRICS 2004 / PERFORMANCE 2004

June 10 - 14, 2004

NY, New York, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

391
Total Citations
View Citations
4,332
Total Downloads

Downloads (Last 12 months)222
Downloads (Last 6 weeks)20

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Borgianni LAdami DGiordano SPagano M(2024)Enhancing Reliability in Rural Networks Using a Software-Defined Wide Area NetworkComputers10.3390/computers1305011313:5(113)Online publication date: 28-Apr-2024
https://doi.org/10.3390/computers13050113
Shi X(2024)Dyadic Treatment Effects: Theory and Empirical ApplicationsSSRN Electronic Journal10.2139/ssrn.4813012Online publication date: 2024
https://doi.org/10.2139/ssrn.4813012
Babai EOkamura K(2024)A Contextual Approach for Improving Anomalous Network Traffic Flows Prediction2024 IEEE 48th Annual Computers, Software, and Applications Conference (COMPSAC)10.1109/COMPSAC61105.2024.00353(2203-2208)Online publication date: 2-Jul-2024
https://doi.org/10.1109/COMPSAC61105.2024.00353
Muhammad MCaraffini FFasanmade AIshola OMohammed KMorden J(2023)Data-Driven Design for Anomaly Detection in Network Access Control Systems2023 International Conference on Business Analytics for Technology and Security (ICBATS)10.1109/ICBATS57792.2023.10111130(1-10)Online publication date: 7-Mar-2023
https://doi.org/10.1109/ICBATS57792.2023.10111130
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
Kwon JJung BLee HLee S(2022)Anomaly Detection in Multi-Host Environment Based on Federated Hypersphere ClassifierElectronics10.3390/electronics1110152911:10(1529)Online publication date: 11-May-2022
https://doi.org/10.3390/electronics11101529
Xie KTian JWang XXie GCao JJiang HWen J(2022)Fast Retrieval of Large Entries With Incomplete Measurement DataIEEE/ACM Transactions on Networking10.1109/TNET.2022.316023330:5(1955-1969)Online publication date: Oct-2022
https://doi.org/10.1109/TNET.2022.3160233
Houidi OBakri SZeghlache D(2022)Multi-Agent Graph Convolutional Reinforcement Learning for Intelligent Load BalancingNOMS 2022-2022 IEEE/IFIP Network Operations and Management Symposium10.1109/NOMS54207.2022.9789872(1-6)Online publication date: 25-Apr-2022
https://doi.org/10.1109/NOMS54207.2022.9789872
Li XXie KWang XXie GLi KZhang DWen J(2022)Order-preserved Tensor Completion For Accurate Network-wide Monitoring2022 IEEE/ACM 30th International Symposium on Quality of Service (IWQoS)10.1109/IWQoS54832.2022.9812910(1-11)Online publication date: 10-Jun-2022
https://doi.org/10.1109/IWQoS54832.2022.9812910
Ouyang YXie KWang XWen JZhang G(2022)Lightweight Trilinear Pooling based Tensor Completion for Network Traffic MonitoringIEEE INFOCOM 2022 - IEEE Conference on Computer Communications10.1109/INFOCOM48880.2022.9796873(2128-2137)Online publication date: 2-May-2022
https://doi.org/10.1109/INFOCOM48880.2022.9796873
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