More Web Proxy on the site http://driver.im/

research-article

Optimal sampling in state space models with applications to network monitoring

Authors:

George MichailidisAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 36, Issue 1

Pages 145 - 156

https://doi.org/10.1145/1384529.1375474

Published: 02 June 2008 Publication History

Abstract

Advances in networking technology have enabled network engineers to use sampled data from routers to estimate network flow volumes and track them over time. However, low sampling rates result in large noise in traffic volume estimates. We propose to combine data on individual flows obtained from sampling with highly aggregate data obtained from SNMP measurements (similar to those used in network tomography) for the tracking problem at hand. Specifically, we introduce a linearized state space model for the estimation of network traffic flow volumes from combined SNMP and sampled data. Further, we formulate the problem of obtaining optimal sampling rates under router resource constraints as an experiment design problem. Theoretically it corresponds to the problem of optimal design for estimation of conditional means for state space models and we present the associated convex programs for a simple approach to it. The usefulness of the approach in the context of network monitoring is illustrated through an extensive numerical study.

References

[1]

P. Barford, J. Kline, D. Plonka, and A. Ron. A signal analysis of network traffic anomalies. In IMW '02: Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, pages 71--82, New York, NY, USA, 2002. ACM Press.

Digital Library

[2]

S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.

Digital Library

[3]

J. Cao, D. Davis, S. Wiel, and B. Yu. Time-varying network tomography - Router link data. Journal of the American Statistical Association, 95:1063--75, 2000.

[4]

A. Chen and J. Cao. Method of one dimensional projections for network tomography. Statistical Inverse Problems, R. Liu, W. Strawderman, C. H. Zhang (editors), IMS Lecture Note Series, 2006.

[5]

B. Choi and S. Bhattacharrya. On the accuracy and overhead of Cisco sampled netflow. In ACM Sigmetrics Workshop on Large-Scale Network Inference (LSNI), Banff, Canada, June 2005.

[6]

N. Duffield, C. Lund, and M. Thorup. Properties and prediction of flow statistics from sampled packet streams. In IMW '02: Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, pages 159--171, New York, NY, USA, 2002. ACM Press.

Digital Library

[7]

N. Duffield, C. Lund, and M. Thorup. Flow sampling under hard resource constraints. In SIGMETRICS '04/Performance '04: Proceedings of the joint international conference on Measurement and modeling of computer systems, pages 85--96, New York, NY, USA, 2004. ACM.

Digital Library

[8]

N. Duffield, C. Lund, and M. Thorup. Optimal combination of sampled network measurements. In IMC'05: Proceedings of the Internet Measurement Conference 2005, pages 8--8, Berkeley, CA, USA, 2005. USENIX Association.

Digital Library

[9]

N. G. Duffield, C. Lund, and M. Thorup. Learn more, sample less: control of volume and variance in network measurement. IEEE Transactions on Information Theory, 51(5):1756--1775, 2005.

Digital Library

[10]

V. Erramilli, M. Crovella, and N. Taft. An independent-connection model for traffic matrices. In IMC '06: Proceedings of the 6th ACM SIGCOMM on Internet measurement, pages 251--256, New York, NY, USA, 2006. ACM Press.

Digital Library

[11]

A. C. Harvey. Forecasting, structural time series models and the Kalman filter. Cambridge University Press, 1990.

[12]

A. Lakhina, M. Crovella, and C. Diot. Diagnosing network-wide traffic anomalies. In SIGCOMM '04: Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, pages 219--230, New York, NY, USA, 2004. ACM Press.

Digital Library

[13]

E. Lawrence, G. Michailidis, V. Nair, and B. Xi. Network tomography: a review and recent developments. In Frontiers in Statistics, pages 345--364. Fan and H. Koul (eds), Imperial College Press, London, 2006.

[14]

J. Lee. Semidefinite programming in experimental design. In H. Wolkowicz, R. Saigal and L. Vandenberghe, editors, "Handbook of Semidefinite Programming", International Series in Operations Research and Management Science, Vol. 27. Kluwer, 2000.

[15]

G. Liang, N. Taft, and B. Yu. A fast lightweight approach to origin-destination IP traffic estimation using partial measurements. IEEE Transactions on Information Theory, 52(6):2634--2648, 2006.

[16]

H. Lutkepohl. Introduction to multiple time series analysis. Springer-Verlag, New York, 1993.

[17]

A. Medina, N. Taft, K. Salamatian, S. Bhattacharyya, and C. Diot. Traffic matrix estimation: existing techniques and new directions. In Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications. ACM Press, 2002.

Digital Library

[18]

L. Peterson and B. Davie. Computer Networks: A Systems Approach. Morgan Kaufmann, San Francisco, 2003.

Digital Library

[19]

F. Pukelsheim. Optimal Design of Experiments. John Wiley & Sons, Inc., 1993.

[20]

H. Singhal and G. Michailidis. Identifiability of flow distributions from link measurements with applications to computer networks. Inverse Problems, 23(5):1821--1849, 2007.

[21]

A. Soule, A. Lakhina, N. Taft, K. Papagiannaki, K. Salamatian, A. Nucci, M. Crovella, and C. Diot. Traffic matrices: Balancing measurements, inference and modeling. In Proceedings of the joint international conference on Measurement and modeling of computer systems. ACM Press, 2005.

Digital Library

[22]

A. Soule, A. Nucci, R. Cruz, E. Leonardi, and N. Taft. How to identify and estimate the largest traffic matrix elements in a dynamic environment. In SIGMETRICS '04/Performance '04: Proceedings of the joint international conference on Measurement and modeling of computer systems, pages 73--84, New York, NY, USA, 2004. ACM Press.

Digital Library

[23]

L. Yang and G. Michailidis. Estimation of flow lengths from sampled data. In Proceedings of IEEE GLOBECOM, 2006.

[24]

L. Yang and G. Michailidis. Sample based estimation of network traffic characteristics. In Proceedings of IEEE INFOCOM, 2007.

[25]

Y. Zhang, M. Roughan, N. G. Duffield, and A. G. Greenberg. Fast accurate computation of large-scale IP traffic matrices from link loads. In Proceedings of the International Conference on Measurements and Modeling of Computer Systems, SIGMETRICS 2003, pages 206--217, 2003.

Digital Library

[26]

Q. Zhao. Towards Ideal Network Traffic Measurement: A Statistical Algorithmic Approach. PhD thesis, College of Computing, Georgia Institute of Technology, Atlanta, Georgia, USA, 2007.

Digital Library

[27]

Q. Zhao, Z. Ge, J. Wang, and J. Xu. Robust traffic matrix estimation with imperfect information: making use of multiple data sources. In SIGMETRICS '06/Performance '06: Proceedings of the joint international conference on Measurement and modeling of computer systems, pages 133--144, New York, NY, USA, 2006. ACM.

Digital Library

Cited By

Müller CSchorning K(2023)A-optimal designs for state estimation in networksStatistical Papers10.1007/s00362-023-01435-y64:4(1159-1186)Online publication date: 24-Mar-2023
https://doi.org/10.1007/s00362-023-01435-y
Pan SLi PYi CZeng DLiang YHu G(2021)Edge Intelligence Empowered Urban Traffic Monitoring: A Network Tomography PerspectiveIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2020.302482422:4(2198-2211)Online publication date: Apr-2021
https://doi.org/10.1109/TITS.2020.3024824
Li TZeng CJiang YZhou WTang LLiu ZHuang Y(2017)Data-Driven Techniques in Computing System ManagementACM Computing Surveys10.1145/309269750:3(1-43)Online publication date: 27-Jul-2017
https://dl.acm.org/doi/10.1145/3092697
Show More Cited By

Index Terms

Optimal sampling in state space models with applications to network monitoring
1. Networks
  1. Network services
    1. Network monitoring

Recommendations

Optimal sampling in state space models with applications to network monitoring
SIGMETRICS '08: Proceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systems

Advances in networking technology have enabled network engineers to use sampled data from routers to estimate network flow volumes and track them over time. However, low sampling rates result in large noise in traffic volume estimates. We propose to ...
Sampling Decisions in Optimum Experimental Design in the Light of Pontryagin's Maximum Principle

Optimum experimental design (OED) problems are optimization problems in which an experimental setting and decisions on when to measure---the so- called sampling design---are to be determined such that a follow-up parameter estimation yields accurate ...
Sampling time-based sliding windows in bounded space
SIGMOD '08: Proceedings of the 2008 ACM SIGMOD international conference on Management of data

Random sampling is an appealing approach to build synopses of large data streams because random samples can be used for a broad spectrum of analytical tasks. Users are often interested in analyzing only the most recent fraction of the data stream in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review

ACM SIGMETRICS Performance Evaluation Review Volume 36, Issue 1

SIGMETRICS '08

June 2008

469 pages

ISSN:0163-5999

DOI:10.1145/1384529

Issue’s Table of Contents

SIGMETRICS '08: Proceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systems
June 2008
486 pages
ISBN:9781605580050
DOI:10.1145/1375457
General Chair:
Zhen Liu
IBM T. J. Watson Research Center, USA
,
Program Chairs:
Vishal Misra
Columbia University, USA
,
Prashant Shenoy
University of Massachusetts, USA

Copyright © 2008 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 June 2008

Published in SIGMETRICS Volume 36, Issue 1

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
361
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Müller CSchorning K(2023)A-optimal designs for state estimation in networksStatistical Papers10.1007/s00362-023-01435-y64:4(1159-1186)Online publication date: 24-Mar-2023
https://doi.org/10.1007/s00362-023-01435-y
Pan SLi PYi CZeng DLiang YHu G(2021)Edge Intelligence Empowered Urban Traffic Monitoring: A Network Tomography PerspectiveIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2020.302482422:4(2198-2211)Online publication date: Apr-2021
https://doi.org/10.1109/TITS.2020.3024824
Li TZeng CJiang YZhou WTang LLiu ZHuang Y(2017)Data-Driven Techniques in Computing System ManagementACM Computing Surveys10.1145/309269750:3(1-43)Online publication date: 27-Jul-2017
https://dl.acm.org/doi/10.1145/3092697
Otoshi TOhsita YMurata MTakahashi YIshibashi KShiomoto KHashimoto T(2016)Framework for traffic engineering under uncertain traffic information2016 International Conference on Information and Communication Technology Convergence (ICTC)10.1109/ICTC.2016.7763482(264-266)Online publication date: Oct-2016
https://doi.org/10.1109/ICTC.2016.7763482
He TLiu CSwami ATowsley DSalonidis TBejan AYu P(2015)Fisher Information-based Experiment Design for Network TomographyACM SIGMETRICS Performance Evaluation Review10.1145/2796314.274586243:1(389-402)Online publication date: 15-Jun-2015
https://dl.acm.org/doi/10.1145/2796314.2745862
He TLiu CSwami ATowsley DSalonidis TBejan AYu PLin BXu JSengupta SShah D(2015)Fisher Information-based Experiment Design for Network TomographyProceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems10.1145/2745844.2745862(389-402)Online publication date: 15-Jun-2015
https://dl.acm.org/doi/10.1145/2745844.2745862
Jiang DXu ZZhang PZhu T(2014)A transform domain-based anomaly detection approach to network-wide trafficJournal of Network and Computer Applications10.5555/2773807.277406140:C(292-306)Online publication date: 1-Apr-2014
https://dl.acm.org/doi/10.5555/2773807.2774061
Jiang DXu ZZhang PZhu T(2014)A transform domain-based anomaly detection approach to network-wide trafficJournal of Network and Computer Applications10.1016/j.jnca.2013.09.01440(292-306)Online publication date: Apr-2014
https://doi.org/10.1016/j.jnca.2013.09.014
Kallitsis MStoev SMichailidis G(2013)Fast Algorithms for Optimal Link Selection in Large-Scale Network MonitoringIEEE Transactions on Signal Processing10.1109/TSP.2013.224206661:8(2088-2103)Online publication date: 1-Apr-2013
https://dl.acm.org/doi/10.1109/TSP.2013.2242066
Michailidis G(2013)Power allocation to a network of charging stations based on network tomography monitoring2013 18th International Conference on Digital Signal Processing (DSP)10.1109/ICDSP.2013.6622681(1-6)Online publication date: Jul-2013
https://doi.org/10.1109/ICDSP.2013.6622681
Show More Cited By

View Options

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 Issue’s Table of Contents