Virtual topology design for optical WDM networks

Abstract

Virtual Topology Design (VTD) is an important design issue in wide area Optical WDM networks. It is to optimize a target function and is formulated as a mixed integer linear programming (MILP) problem. A crucial issue on VTD is to look for fast and accurate algorithms to obtain its optimized target value without the need to perform exhaustive computation. Hence, heuristic algorithms are used especially when the number of nodes in the network is large. We first improve the existing heuristic algorithms which using congestion control as the target function. We formulate VTD in two novel ways. One is to minimize traffic-weighted virtual hops by removing the virtual degree (VD) constraints for all the nodes in the network, and replace them by a single constraint related to the total VD of the entire network. We design a heuristic algorithm, RLL algorithm, to solve this formulated problem. We show that it yields better performance by having lower congestion level when compared with solutions obtained from existing heuristic algorithms with unique VD constraint on each node. In the second way, we decompose VTD problems into four sub-problems, each with its target function. MTN (Maximum-Traffic-Net) heuristic algorithms are proposed and shows that its approach the solution given by using MILP method. Finally we analyze and formulate VTD as a bi-target problem. Sum weighted method is applied to solve the bi-target problem that demonstrating the existence of discrete Pareto solutions.