DocumentCode :
24846
Title :
Fast Algorithms for Optimal Link Selection in Large-Scale Network Monitoring
Author :
Kallitsis, Michael G. ; Stoev, S.A. ; Michailidis, George
Author_Institution :
Department of Statistics, University of Michigan, Ann Arbor,
Volume :
61
Issue :
8
fYear :
2013
fDate :
15-Apr-13
Firstpage :
2088
Lastpage :
2103
Abstract :
The robustness and integrity of IP networks require efficient tools for traffic monitoring and analysis, which scale well with traffic volume and network size. We address the problem of optimal large-scale monitoring of computer networks under resource constraints. Specifically, we consider the task of selecting the “best” subset of at most K links to monitor, so as to optimally predict the traffic load at the remaining ones. Our notion of optimality is quantified in terms of the statistical error of network traffic predictors. The optimal monitoring problem at hand is akin to certain combinatorial constraints, which render the algorithms seeking the exact solution impractical. We develop a number of fast algorithms that improve upon existing algorithms in terms of computational complexity and accuracy. Our algorithms exploit the geometry of principal component analysis, which also leads us to new types of theoretical bounds on the prediction error. Finally, these algorithms are amenable to randomization, where the best of several parallel independent instances often yields the exact optimal solution. Their performance is illustrated and evaluated on simulated and real-network traces.
Keywords :
Algorithm design and analysis; Approximation algorithms; Covariance matrix; Monitoring; Network topology; Prediction algorithms; Principal component analysis; Approximation algorithms; IP network; computer networks; optimization; prediction methods; principal component analysis; signal processing algorithms;
fLanguage :
English
Journal_Title :
Signal Processing, IEEE Transactions on
Publisher :
ieee
ISSN :
1053-587X
Type :
jour
DOI :
10.1109/TSP.2013.2242066
Filename :
6418047
Link To Document :
بازگشت