全光网中定位故障链路的探测选择算法

Probe selection algorithm for faulty links localization in all-optical networks

文中研究了全光网中定位故障链路的探测选择算法.目前存在的随机游走算法可以惟一定位出每条故障链路,但在大型网络中定位故障链路时会消耗过多的探测以及平均波长数.首先建立关于故障检测需要的监测路径集合,其次在建立好的监测路径上同时发送探测信号,最后在有故障的路径上执行故障定位;证明了最小监测路径集合问题是非确定多项式完全问题,并提出启发式的监测路径选择算法来找最小监测路径集合;同时证明了用一个监测站来定位k条故障链路的充分必要条件是,网络为k+1边连通的.对比随机游走算法,探测选择算法在定位故障链路的过程中明显地减少了定位故障链路所需的探测数和每条链路上消耗的平均波长数.

This paper studies the probe selection problem in all-optical networks for achieving unambiguous faulty links localization.The existing random walk algorithm can find feasible solutions for localizing the faulty link unambiguously,but it consumes a large number of probes and wavelengths in large-size networks.First,monitoring paths arc set up for failure detection.Second,the probing signals arc sent out through all monitoring paths,and then the failure localization is performed on every faulty path.The proposed scheme proves that the problem of the minimal monitoring path set is NP-complctc and can be solved by the heuristic monitoring path selection algorithm.It is also proved that a network must be k+1 edge connectivity for localizing k faulty links with one monitoring node.Compared with random walk,the probe selection algorithm greatly shortens the number of probes and consumed wavelengths per link.