SGER: Algorithm Design for Reconfiguration Problem in Optical Networks

SGER：光网络重配置问题的算法设计

• 批准号: 0443257
• 负责人: Baek-Young Choi
• 金额: --
• 依托单位: University of Missouri-Kansas City
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-09-01 至 2006-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0443257&HistoricalAwards=false
• 关键词: SGER; Algorithm; Design; Reconfiguration; Problem

The optical network is a promising high-speed backbone or transportation network that requiresan extremely caution in operations. The reconfiguration is one of the indispensable operations if avirtual topology no longer serves a traffic demand which is changed over time. We propose to develop an algorithm and a complete reconfiguration model for wavelengthroutedoptical networks which includes the reconfiguration process and the policy. The reconfigurationprocess provides the choices of the reconfiguration operations (e.g., add, delete or re-routelightpaths) to maintain the high performance of the network in any traffic demand volumes andpatterns while minimally disturbs the current virtual topology. The reconfiguration policy defineswhich choice to be selected that returns the optimal expected outcome based on the cost of operationand the performance reward. We have preliminary experimental results that show that selectingthe choice with the highest immediate outcome does not return the optimal expected outcome inthe long term. Although the reconfiguration problem is an NP-hard problem and is a trade-off between performanceand number of changes in virtual topology, we can still find the solutions using a multiobjectiveevolutionary algorithm with the concept of Pareto Optimal. The algorithm provides a setof solutions in the Pareto front while the policy picks one of solutions in the Pareto front that gainsthe optimal expected outcome. The policy depends on the pattern of traffic. If the future patternof traffic can be predicted or estimated, the Markov Decision Process (MDP) can define the policy.However, the status of network or the MDP's state which effects the Pareto front needs an intensivestudy. Our goal is to develop the theory and algorithms in accordance with realistic traffic demand andprotocol. The model will be the centralized control over the network, which will not be designedonly for the specific performance objective or traffic type but be applicable for various objectivesand traffic types. The development of practical algorithms for solving these problems represent animportant step in allowing reasonable scale implementation of optical networks. Intellectual Merit of the proposed research rests on the integration between the reconfigurationprocess and the policy based on the Pareto optimal concept and MDP that has not yet happened inthe Optical network reconfiguration field. Reconfiguration problems are among the most difficultin the areas of optical networks since such problems encompass the construction of algorithmsinvolving the extremely high-speed communication over an optical fiber. The consequence problemis how or when to perform the reconfiguration process. From the practical application viewpoint,we want to advance our model to the practical optical networks. Broader Impacts of the proposed research is expected to be strong since we are proposingto integrate two disciplines, the evolutionary computing and the stochastic process for the recon-figuration in the optical networks. We expect that the work will have broad impact in industrialpractices on network provisioning, protection and restoration areas.

光网络是一种很有前途的高速骨干网或传输网，在运行中需要非常谨慎。如果一个虚拟拓扑不再服务于随时间变化的流量需求，则重新配置是必不可少的操作之一。 本文提出了一种波长光网络重构算法和一个完整的重构模型，包括重构过程和重构策略。重新配置过程提供重新配置操作的选择（例如，添加、删除或重新路由光路径），以在任何业务需求量和模式下保持网络的高性能，同时最小地干扰当前虚拟拓扑。重新配置策略定义了基于操作成本和性能奖励的返回最优预期结果的选择。我们的初步实验结果表明，选择即时结果最高的选择并不能从长远来看返回最佳的预期结果。 虽然重构问题是一个NP难问题，是性能和虚拟拓扑变化数量之间的权衡，但我们仍然可以使用具有Pareto最优概念的多目标进化算法来求解。该算法在Pareto前沿提供一组解，而策略在Pareto前沿选择一个获得最优期望结果的解。该政策取决于交通模式。如果可以预测或估计未来的业务模式，马尔可夫决策过程（MDP）可以定义策略，但网络的状态或MDP的状态对Pareto前沿的影响需要深入研究。 我们的目标是发展符合实际业务需求和协议的理论和算法。该模型将是对网络的集中控制，它将不仅仅针对特定的性能目标或业务类型而设计，而是适用于各种目标和业务类型。解决这些问题的实用算法的发展代表了光网络合理规模实现的重要一步。 该研究的智能价值在于基于Pareto最优概念和MDP的重构过程和策略之间的集成，这在光网络重构领域还没有发生。重构问题是光网络领域中最困难的问题之一，因为这类问题包含了涉及光纤上极高速通信的算法的构建。结果问题是如何或何时执行重新配置过程。从实际应用的角度来看，我们希望我们的模型，以实际的光网络。 更广泛的影响所提出的研究预计将是强大的，因为我们正在proposingintegrate两个学科，进化计算和随机过程中的光网络中的重新配置。我们预计，这项工作将在网络配置、保护和恢复领域的工业实践中产生广泛的影响。