Ranking Metric Anomaly in Invariant Networks
Ranking Metric Anomaly in Invariant Networks
复制标题
不变网络中的排名度量异常
DOI：
10.1145/2601436
复制
发表时间：
2014-05-01
影响因子：
3.6
通讯作者：
Xiong, Hui
中科院分区：
文献类型：
--
作者：
Ge, Yong;Jiang, Guofei;Xiong, Hui
大规模分布式信息系统的管理依赖于对分布式信息系统中各点采集的监测数据的有效利用和建模。传统的监测数据建模方法是发现监测数据之间的不变关系。实际上，我们可以发现所有监视数据对之间的所有不变关系，并生成不变网络，其中节点是监视数据源（度量），链路表示两个监视数据之间的不变关系。这种不变网络表示可以帮助系统专家通过检查那些被破坏的不变关系及其相关度量来定位和诊断系统故障，因为系统故障通常在监控数据之间传播，并最终导致一些被破坏的不变关系。然而，在一个不变的网络中，通常会有很多断裂的链接（不变的关系）。如果没有适当的指导，系统专家很难手动检查这大量的断开链接。为此，在本文中，我们提出了根据给定不变网络的异常水平对指标进行排序的问题，而由于不变网络的不确定性和复杂性，这是一项不平凡的任务。具体来说，我们提出了两种基于链路分析的不变网络度量异常排序算法。沿着这条线，我们首先定义了两个度量来量化每个度量的异常水平，并引入了mRank算法。此外，我们提供了一个加权评分机制，并开发了gRank算法，该算法涉及一个迭代过程，以获得一个分数来衡量异常水平。此外，在mRank和gRank算法的基础上开发了一些扩展算法，考虑了被破坏的概率和噪声链路。最后，我们在大量真实世界和合成数据集上验证了所有提出的算法，以说明不同算法的有效性和效率。
The management of large-scale distributed information systems relies on the effective use and modeling of monitoring data collected at various points in the distributed information systems. A traditional approach to model monitoring data is to discover invariant relationships among the monitoring data. Indeed, we can discover all invariant relationships among all pairs of monitoring data and generate invariant networks, where a node is a monitoring data source (metric) and a link indicates an invariant relationship between two monitoring data. Such an invariant network representation can help system experts to localize and diagnose the system faults by examining those broken invariant relationships and their related metrics, since system faults usually propagate among the monitoring data and eventually lead to some broken invariant relationships. However, at one time, there are usually a lot of broken links (invariant relationships) within an invariant network. Without proper guidance, it is difficult for system experts to manually inspect this large number of broken links. To this end, in this article, we propose the problem of ranking metrics according to the anomaly levels for a given invariant network, while this is a nontrivial task due to the uncertainties and the complex nature of invariant networks. Specifically, we propose two types of algorithms for ranking metric anomaly by link analysis in invariant networks. Along this line, we first define two measurements to quantify the anomaly level of each metric, and introduce the mRank algorithm. Also, we provide a weighted score mechanism and develop the gRank algorithm, which involves an iterative process to obtain a score to measure the anomaly levels. In addition, some extended algorithms based on mRank and gRank algorithms are developed by taking into account the probability of being broken as well as noisy links. Finally, we validate all the proposed algorithms on a large number of real-world and synthetic data sets to illustrate the effectiveness and efficiency of different algorithms.