Network Resilience Assessment via QoS Degradation Metrics: An Algorithmic Approach
Network Resilience Assessment via QoS Degradation Metrics: An Algorithmic Approach
复制标题
通过 QoS 降级指标进行网络弹性评估：一种算法方法
DOI：
10.1145/3311072
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Thai, My T
中科院分区：
文献类型：
--
作者：
Nguyen, Lan;Thai, My T
本文主要研究网络对边权值扰动的弹性。除了连通性之外，现在许多网络应用程序都依赖于一对连接节点之间的网络距离的某种度量。在这些系统中，与网络功能相关的度量与每个边缘相关联。一对节点只有在两个节点之间的加权最短路径距离低于给定阈值T时才起作用。因此，一个自然的问题是边权重的变化会在多大程度上损害网络功能？在此基础上，我们研究了一个新的问题，服务质量降级：给定一组对，找到一个最小的预算，以增加边的权重，确保每个对之间的距离超过T。我们介绍了四个算法与理论性能保证这个问题。这两种算法在效率和运行时间的权衡上各有优势，理论和综合实验评价都说明了这一点。
This paper focuses on network resilience to perturbation of edge weight. Other than connectivity, many network applications nowadays rely upon some measure of network distance between a pair of connected nodes. In these systems, a metric related to network functionality is associated to each edge. A pair of nodes only being functional if the weighted, shortest-path distance between the pair is below a given threshold T. Consequently, a natural question is on which degree the change of edge weights can damage the network functionality? With this motivation, we study a new problem, Quality of Service Degradation : given a set of pairs, find a minimum budget to increase the edge weights which ensures the distance between each pair exceeds T . We introduce four algorithms with theoretical performance guarantees for this problem. Each of them has its own strength in trade-off between effectiveness and running time, which are illustrated both in theory and comprehensive experimental evaluation.