Algorithms for wavelength assignment and call control in optical networks

Routing and channel assignment is a fundamental problem in computer/communication networks. In wavelength division multiplexing (WDM) optical networks, the problem is called routing and wavelength assignment or routing and path coloring (RPC) problem: given a set of connection requests, find a routing path to connect each request and assign each path a wavelength channel (often called a color) subject to certain constraints. One constraint is the distinct channel assignment: the colors (channels) of the paths in the same optical fiber must be distinct. Another common constraint is the channel continuity: a path is assigned a single color. When a path may be assigned different colors on different fibers, the RPC problem is known as the routing and call control (RCC) problem. When the routing paths are given as part of the problem input, the RPC and RCC problems are called the path coloring and call control problems, respectively. Major optimization goals for the above problems include to minimize the number of colors for realizing a given set of requests and to maximize the number of accommodated requests using a given number of colors. Those optimization problems are NP-hard for most network topologies, even for simple networks like rings and trees of depth one. In this thesis, we make the following contributions. (1) We give better approximation algorithms which use at most 3L (L is the maximum number of paths in a fiber) colors for the minimum path coloring problem in trees of rings. The 3L upper bound is tight since there are instances requiring 3L colors. We also give better approximation algorithms for the maximum RPC problem in rings. (2) We develop better algorithms for the minimum and maximum RPC problems on multi-fiber networks. (3) We develop better algorithms for the call control problem on simple topologies. (4) We develop carving-decomposition based exact algorithms for the maximum edge-disjoint paths problem in general topologies. We develop and implement tools for computing optimal branch/carving decompositions of planar graphs to provide a base for the branch/carving-decomposition based algorithms. These tools are of independent interests.