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

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

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.