Design of optical networks: Performance bounds, complexity and algorithms

Optical networks that employ wavelength division multiplexing (WDM) are promising candidates for meeting the high bandwidth requirements of emerging communication applications. This thesis focuses on algorithmic and complexity issues of fundamental, but NP-hard, resource allocation problems arising in the design of multifiber WDM networks.; In the routing and wavelength assignment (RWA) problem, we are given a multifiber network with limited fiber and wavelength resources, and a set of connection requests between pairs of nodes. We seek to allocate paths and wavelengths to the connection requests as to maximize the carried traffic of connections. We show that provably optimal solutions to the linear programming (LP-) relaxation of this problem can be obtained by considering only one wavelength. This leads to an upper bound on the carried traffic that scales to an arbitrarily large number of wavelengths. We also introduce a greedy algorithm that provides integer solutions guaranteed to be within a factor of (1 - 1e ) of the optimal solution by considering one wavelength at a time.; The adaptability to dynamically changing traffic patterns has been identified as one of the most important features of WDM networks. Given a new set of connection requests, we investigate the problem of reconfiguring the network such the carried traffic of connections is maximized while the disruption of ongoing connections and services is completely avoided. We present an algorithm that considers one wavelength at a time, provides optimal and near-optimal solutions and tends to balance loads among wavelengths.; Given a combination of unprotected and dedicated edge-disjoint path (1 + 1) protected connection requests and a finite set of fiber types whose costs reflect an economy of scale, we consider the WDM network design problem of allocating fibers on the links of a multifiber WDM network with wavelength converters at minimum cost, such that all connection requests can be simultaneously routed. It is known that a solution induced by "simply" routing each connection along the shortest path (pair) minimizes the total wavelength mileage, but may not minimize the total fiber cost. We theoretically 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. We also demonstrate that shortest path routing is asymptotically cost-optimal in heavily loaded networks with general topologies, and in large networks with some special topologies, e.g., the ring, the ShuffleNets and the mesh(-torus). We extend most of these results to networks with no wavelength conversion and a single fiber type.