Abstract
In all-optical WDM networks, routing algorithms play an important role in the performance of the networks. In this thesis, we consider some research topics related to routing algorithms in all-optical WDM networks. Among the three categories of unicast routing algorithms for all-optical WDM networks, alternate routing algorithms are computationally efficient and able to yield low connection blocking probability. In the first part, we propose a new approach to designing alternate routing algorithms for all-optical WDM networks in order to reduce the connection blocking probability. The key idea is to try to route traffic in approximately the optimal way of splitting the traffic among the multiple routing paths between each source-destination pair. Two alternate routing algorithms are proposed based on this approach. Our simulation results show that the alternate routing algorithms designed according to the optimal way of splitting the traffic can effectively reduce the connection blocking probability. In the second part, we consider the routing paths for alternate routing algorithms. Depending on the traffic requirements of all source-destination pairs, hop-count based \mbox{$k$-shortest} link-disjoint paths used in previous works may not be the best choice for the predetermined routing paths. We propose a method to find a set of link-disjoint routing paths between each source-destination pair to be used by an alternate routing algorithm in order to reduce the connection blocking probability. The key idea is to find a set of link-disjoint routing paths based on the routing paths that are utilized by the optimal traffic pattern in the network. Our simulation results show that using the link-disjoint routing paths found by the proposed method yields significantly lower connection blocking probability than employing the hop-count based \mbox{$k$-shortest} link-disjoint paths and using the routing paths found by the capacity-balanced alternate routing method~\cite{ho02}. In the third part, multicast routing is taken into account. To reduce the cost, splitters which are used to realize multicast trees can be placed at a subset of nodes. The problem of selecting a subset of nodes to place the splitters such that certain performance measure is optimized is called the splitter placement problem. The goal is to place a given number of splitters in the network such that the average per link wavelength resource usage of multicast connections is minimized. Two splitter placement methods are proposed. The two proposed splitter methods are shown to yield significant lower average wavelength resource usage than the random placement method. One of the methods is shown to produce near minimum average wavelength resource usage.