Academic Journals Database
Disseminating quality controlled scientific knowledge

Fast Indexing for Large-scale Networked System Modeling

Author(s): Hui Zhang | Haifeng Chen | Guofei Jiang | Xiaoqiao Meng | Kenji Yoshihira

Journal: Journal of Networks
ISSN 1796-2056

Volume: 4;
Issue: 8;
Start page: 734;
Date: 2009;
Original page

Keywords: network management | randomized algorithm | statistical modeling | data mining | data indexing | 3G mobile networks

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.
Why do you need a reservation system?      Save time & money - Smart Internet Solutions