基于扩展状态空间识别拥塞链路
Identify Congested Links Based on Enlarged State Space
-
摘要: 当路径共享同一拥塞链路时,它们将都会遭受到性能损失。布尔层析成像正是利用这些性能级相关性来识别网络拥塞链路。当一条路径经过多条拥塞链路时,我们清楚地知道它的拥塞程度将会异常剧烈。不同于布尔层析成像使用的布尔方程,我们采用一个扩展状态空间来反映拥塞程度的差异,并通过建立整型方程组来描述路径状态与链路状态之间的关系。我们将网络拥塞链路识别转化为一个约束最优化问题,并包含布尔层析成像为该问题的一种特殊情况。我们提出一个自顶向下的用于树型网络的拥塞链路识别算法,并理论证明所提算法总能够找到该约束最优化问题的一个解。相较于现有算法,仿真结果表明我们所提的算法能够在取得更高检测率的同时保持一个低误检率水平。Abstract: When paths share a common congested link, they will all suffer from a performance degradation. Boolean tomography exploits these performance-level correlations between different paths to identify the congested links. It is clear that the congestion of a path will be distinctly intensive when it traverses multiple congested links. We adopt an enlarged state space model to mirror different congestion levels and employ a system of integer equations, instead of Boolean equations, to describe relationships between the path states and the link states. We recast the problem of identifying congested links into a constraint optimization problem, including Boolean tomography as a special case. For a logical tree, we propose an up-to-bottom algorithm and prove that it always achieves a solution to the problem. Compared with existing algorithms, the simulation results show that our proposed algorithm achieves a higher detection rate while keeping a low false positive rate.