Title: Design of Optical Networks: Performance Bounds, Complexity and Algorithms

In the first part of my talk I will addresses the problem of routing and wavelength assignment (RWA) in multifiber WDM networks with limited resources. Given a traffic matrix, the number of fibers per link, and the number of wavelengths a fiber can support, we seek to maximize the carried traffic of connections. We formulate the problem as an integer linear program (ILP), and show that the lightpaths selected by this formulation can indeed be established by properly configuring the optical switches. An upper bound on the carried traffic can be computed by solving the linear programming (LP-) relaxation of the ILP formulation. It is shown that this bound can be also computed exactly, and in polynomial-time, by solving a significantly simplified LP which considers only one wavelength. The bound can thus easily scale to an arbitrarily large number of wavelengths. Furthermore, we demonstrate that any instance of the RWA problem is also an instance of the more general maximum coverage problem. This allows us to take a greedy algorithm for maximum coverage and obtain an algorithm which provides solutions for the RWA problem that are guaranteed to be within a factor of (1 - 1/e) of the optimal solution. Each iteration of the greedy algorithm selects a set of lightpaths that realizes, using one wavelength, the maximum number of connection requests not previously realized. Computational results confirm the high efficiency of our proposed algorithm.
Given a combination of unprotected and dedicated edge-disjoint path (1+1) protected connection requests and a finite set of fiber types, we consider, in the second part of the talk, the problem of allocating fibers on the links of a WDM network at minimum cost, such that all connection requests can be simultaneously realized. Each fiber type is characterized by its capacity and its cost per unit length, where costs reflect an economy of scale. It is known that a solution induced by "simply" routing each unprotected (respectively 1+1 protected) connection along the shortest path (respectively shortest pair of edge-disjoint paths) minimizes the total wavelength mileage, but may not minimize the total fiber cost. In this work, we quantify the increase in fiber cost due to shortest path routing. In particular, we prove that the total cost of a shortest path based solution is guaranteed to lie within a certain factor of the minimum possible cost. This leads also to the fact that shortest path routing is asymptotically cost-optimal for a large total number of connection requests. Furthermore, for some special topologies, e.g., the ring, the ShuffleNet and the mesh(-torus), we show that shortest path routing is asymptotically cost-optimal for a large network size. En route, we prove that by shortest path routing we obtain a provably optimal solution to the linear programming (LP-) relaxation of the problem. We have thus presented a provably good upper bound and a lower bound on the total fiber cost, that can be computed in polynomial-time. These bounds can be used as benchmarks against which exact and heuristic approaches are compared.