Monitoring Trail Allocation in all-optical networks with the Random Next Hop Policy
Monitoring Trail Allocation in all-optical networks with the Random Next Hop Policy
复制标题
DOI：
10.1109/hpsr.2012.6260849
复制
发表时间：
2012-06
期刊：
影响因子：
--
通讯作者：
Yangming Zhao;Shizhong Xu;Bin Wu;Xiong Wang;Sheng Wang
中科院分区：
文献类型：
--
作者：
Yangming Zhao;Shizhong Xu;Bin Wu;Xiong Wang;Sheng Wang
监测跟踪(M-TRAIL)的概念为全光网络中快速、明确的链路故障定位提供了一种引人注目的机制。针对最优的整数线性规划模型，提出了两种有效的启发式算法RCA+RCS和MTA，以实现大规模网络中的快速m路径设计。然而，RCA+RCS存在不相交的路径问题，这增加了所需的m条路径数，而MTA总是找到一个确定解，但由于解空间的限制，这个解可能不够好。在本文中，我们提出了一种新的启发式RNH-MTA(监视路径分配与随机下一跳策略)来解决这些问题。与MTA算法类似，RNH-MTA算法确保每个m-轨迹的有效光学结构，并在解中依次添加必要的m-轨迹，从而避免了不相交的轨迹问题。RNH-MTA用随机下一跳策略代替MTA中的确定性搜索，建立了扩展每条m条路径的概率模型。这不仅扩大了解的空间，增加了解的多样性，而且可以在解的质量和算法的运行时间之间进行可控的权衡。数值结果表明，RNH-MTA算法优于RCA+RCS算法和MTA算法。
The concept of monitoring trail (m-trail) provides a striking mechanism for fast and unambiguous link failure localization in all-optical networks. To achieve fast m-trail design in large-size networks, two efficient heuristics RCA+RCS and MTA are proposed against the optimal ILP (Integer Linear Program) model. However, RCA+RCS suffers from the disjoint trail problem which increases the required number of m-trails, and MTA always finds a deterministic solution which may not be good enough due to the limited solution space. In this paper, we propose a new heuristic RNH-MTA (Monitoring Trail Allocation with the Random Next Hop policy) to solve those issues. Similar to MTA, RNH-MTA ensures a valid optical structure of each m-trail and sequentially adds necessary m-trails to the solution, and thus is free of the disjoint trail problem. By replacing the deterministic searching in MTA using the Random Next Hop policy, RNH-MTA sets up a probabilistic model in extending each m-trail. This not only enlarges the solution space and increases the solution diversity, but also enables a controllable tradeoff between the solution quality and the running time of the algorithm. Our numerical results show the advantages of RNH-MTA over both RCA+RCS and MTA.