公制(单位)
网络拓扑
计算机科学
有界函数
贪婪算法
节点(物理)
算法
中心性
序列(生物学)
鉴定(生物学)
数学优化
度量空间
布尔网络
数学
布尔函数
离散数学
工程类
数学分析
运营管理
植物
结构工程
组合数学
生物
遗传学
操作系统
作者
Viviana Arrigoni,Novella Bartolini,Annalisa Massini,Federico Trombetti
出处
期刊:International Conference on Computer Communications
日期:2021-05-10
被引量:2
标识
DOI:10.1109/infocom42981.2021.9488893
摘要
Boolean Network Tomography (BNT) allows to localize network failures by means of end-to-end monitoring paths. Nevertheless, it falls short of providing efficient failure identification in real scenarios, due to the large combinatorial size of the solution space, especially when multiple failures occur concurrently. We aim at maximizing the identification capabilities of a bounded number of monitoring probes. To tackle this problem we propose a progressive approach to failure localization based on stochastic optimization, whose solution is the optimal sequence of monitoring paths to probe. We address the complexity of the problem by proposing a greedy strategy in two variants: one considers exact calculation of posterior probabilities of node failures given the observation, whereas the other approximates these values through a novel failure centrality metric. We discuss the approximation of the proposed approaches. Then, by means of numerical experiments conducted on real network topologies, we demonstrate the practical applicability of our approach. The performance evaluation evidences the superiority of our algorithms with respect to state of the art solutions based on classic Boolean Network Tomography as well as approaches based on sequential group testing.
科研通智能强力驱动
Strongly Powered by AbleSci AI