The design space of probing algorithms for network-performance measurement
Open Access
- 14 June 2013
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 41 (1) , 105-116
Abstract
We present a framework for the design and analysis of probing methods to monitor network performance, an important technique for collecting measurements in tasks such as fault detection. We use this framework to study the interaction among numerous, possibly conflicting, optimization goals in the design of a probing algorithm. We present a rigorous definition of a probing-algorithm design problem that can apply broadly to network-measurement scenarios. We also present several metrics relevant to the analysis of probing algorithms, including probing frequency and network coverage, communication and computational overhead, and the amount of algorithm state required. We show inherent tradeoffs among optimization goals and give hardness results for achieving some combinations of optimization goals. We also consider the possibility of developing approximation algorithms for achieving some of the goals and describe a randomized approach as an alternative, evaluating it using our framework. Our work aids future development of low-overhead probing techniques and introduces principles from IP-based networking to theoretically grounded approaches for concurrent path-selection problems.Keywords
This publication has 19 references indexed in Scilit:
- Disjoint-Path Facility Location: Theory and Practice2011
- The Weighted Coupon Collector’s Problem and ApplicationsLecture Notes in Computer Science, 2009
- Path Hitting in Acyclic GraphsAlgorithmica, 2007
- NetDiagnoser2007
- Strong Colorings of HypergraphsLecture Notes in Computer Science, 2005
- Internet tomographyIEEE Signal Processing Magazine, 2002
- The stable paths problem and interdomain routingIEEE/ACM Transactions on Networking, 2002
- Hardness results for approximate hypergraph coloring2002
- On the marginal utility of network topology measurements2001
- The NP-Completeness of Edge-ColoringSIAM Journal on Computing, 1981