ITR: Optimal and Suboptimal Routing and Wavelength Assignment in Optical and Circuit Switched Networks

本文研究了光数据网络中的路由和波长分配问题。这个问题被广泛认为是至关重要的波长路由全光网络的效率提高。在数学上，这个问题包含了一个重要的特殊情况下，在电路交换网络的路由问题，我们提出了几个新的优化问题的配方，提供了根本性的改进现有的方法，这主要是启发式的字符的承诺。我们的工作旨在使用分析和算法开发的混合，以获得更好的理解RWA，并制定有效的和实用的方法来计算最佳或接近最佳的RWA和电路交换policies在现实的assumptions.We计划使用两种类型的方法来解决这个问题：随机优化，基于动态规划（DP），和确定性优化，基于线性规划（LP）。在这两种方法之间存在一些方法学上的耦合，因为确定性方法可以用来获得成本的近似值，而成本的近似值又可以作为近似DP方法的基础。在随机模型的框架下，我们允许网络资源的需求是动态和随机变化的，以及一种决策机制，该决策机制是前瞻性的，并且考虑了阻挡未来光路请求的成本。这种得到的优化模型是DP类型的，但通常由于高维数而不能精确求解。我们建议使用近似和神经动态规划（NDP），最近的方法，已被用来解决具有挑战性的DP problems.In框架的确定性模型，我们提出了一个新的整数/线性规划制定这样的问题。我们的方法的显着特点，区别于文献中提出的类似方法，是它不需要耗时和缺乏洞察力的混合整数规划的机器。我们已经证明了这对于一些实际上有用的环形网络拓扑结构，我们提出了进一步的调查和扩展我们的方法更一般的拓扑结构。这是一个令人惊喜的情况下，并提供了壮观的改进的承诺，目前的艺术状态。我们计划调查和开发的算法，可用于网络的设计或重新配置，以及在其上线操作。我们还计划探索如何使用确定性线性规划方法在随机/动态的背景下，并结合NDP方法。

We propose to investigate the problem of routing and wavelength assignment (RWA) in optical data networks. This problem is widely viewed as critically important for increasing the efficiency of wavelength-routed all-optical networks. Mathematically, this problem contains an important special case the problem of routing in circuit switched networks.We propose several novel optimization problem formulations that offer the promise of radical improvements over the existing methods, which are mainly heuristic in character. Our work aims to use a blend of analysis and algorithmic development to obtain a better understanding of RWA, and to develop efficient and practical methods for computing optimal or near-optimal RWA and circuit switching policies under realistic assumptions.We plan to address the problem using two types of methodology: stochastic optimization, based on dynamic programming (DP), and deterministic optimization, based on linear programming (LP). There is some methodological coupling between the two types of methodology, because the deterministic methodology can be used to obtain cost-to-go approximations, which can in turn be used as the basis for an approximate DP method.In the framework of a stochastic model, we allow a dynamic and stochastically varying demand of the network resources, and a decision-making mechanism that is forward-looking and takes into account the cost of blocking future lightpath requests. This resulting optimization models are of the DP type, but typically cannot be solved exactly because of high dimensionality. We propose to address such problems using approximations and neuro-dynamic programming (NDP), a recent methodology that has been used to address challenging DP problems.In the framework of a deterministic model, we propose a new integer/linear programming formulation. The salient feature of our approach, which distinguishes it from similar approaches proposed in the literature, is that it does not require the time-consuming and uninsightful machinery of mixed integer programming. We have shown this for some practically useful ring network topologies, and we propose further investigation and extension of our methodology to more general topologies. This is a pleasantly surprising circumstance, and offers the promise of spectacular improvements over the current state of the art. We plan to investigate and develop algorithms that may be used during the design or reconfiguration of a network, as well as during its on-line operation. We also plan to explore ways to use the deterministic linear programming methodology in the stochastic/dynamic context and in combination with the NDP methodology.