Fast Indexing for Large-scale Networked System Modeling
|
| Title | Fast Indexing for Large-scale Networked System Modeling |
| Authors | |
| Abstract | Today’s networked systems are extensively instrumented for collecting a wealth of monitoring data. Statistical techniques like regression analysis can be applied to uncover rich relationships (e.g., correlation, causality, independence) between the measurement data which are further utilized for systems management tasks including fault diagnosis, configuration management, performance analysis, etc. However, one problem during this system modeling process comes from the heavy computation overhead in statistical relationship discovery. In this paper, we propose a fast indexing technique to alleviate this problem by helping guide the discovery process in an optimal order. We model the optimal discovery process as the classic vertex cover problem in graph theory which is NP-complete. We use the heuristic of greedy vertex selection based on vertex degree and propose two simple algorithms for generating an estimated ranking (indexing) on the vertices (i.e., measurement points) based on the edges (the existing statistical relationships) incident to them. The two algorithms are based on random sampling and we analyze their output accuracy as a function of the sampling trials. On data traces from an operational 3G mobile network, our indexing technique performed close to the optimal solution (e.g., no more than 10% discovery time) and significantly better than random discovery (e.g., 70% less discovery time) on finding a specified percentage (e.g., 90%) of the existing relationships. |
| Publisher | ACADEMY PUBLISHER |
| Date | 2009-10-01 |
| Source | Journal of Networks Vol 4, No 8 (2009): Special Issue: Performance Evaluation of Communication Networks |
| Rights | Copyright © ACADEMY PUBLISHER - All Rights Reserved.To request permission, please check out URL: http://www.academypublisher.com/copyrightpermission.html. |