Routing and channel assignment in optical and wireless networks

Optical networks and wireless networks are two important types of networks in the modern communication infrastructure. They share a common feature: the use of multiple channels. The channels are in terms of wavelengths for wavelength-division multiplexing (WDM) optical networks, and are in terms of radio frequencies for wireless networks. As both wavelengths and radio frequencies are scarce resources in the networks, they should be used efficiently so as to maximize the network performance. This involves the design of good routing and channel assignment (RCA) schemes. Most previous RCA schemes aim to maximize the utilization of the given channels, hence maximizing the system throughput or minimizing the overall blocking rate. With limited channels, however, achieving fairness among the flows or connections is also desirable. This thesis studies RCA schemes that take fairness into consideration. In particular, we propose to use rerouting and load-based channel assignment to achieve this goal. We apply the general strategy to two specifical problems, i.e., the multicast routing and wavelength assignment (MC-RWA) problem in wavelength-routed WDM networks and the RCA in a novel multi-channel wireless mesh network. In the WDM multicasting problem, we generalize the traditional MC-RWA system model by assigning a weight to each multicast group at each destination node to reflect the popularity of different multicast groups. We propose a largest weight first (LWF) heuristic to minimize the weighted overall blocking rate. We show that it significantly outperforms traditional schemes which do not take group weights into consideration. As LWF penalizes those groups of small weights, we also propose a fairness improvement (FI) heuristic which runs on top of LWF and achieves the goal through rerouting. We show that FI is effective in improving the fairness among the multicast groups in terms of their respective blocking rates. As to the RCA in the wireless mesh network, we consider a novel system architecture which we propose for wireless LAN (WLAN) coverage extension. WLAN is currently used by attaching its access point (AP) to the wired network to provide Internet access to mobile users, thus limiting the clients at most one hop away from the wired network. We propose to connect the WLAN APs through wireless links operating on multiple channels, such that the WLAN coverage can be extended to infrastructureless areas as long as one AP (namely, I-AP) is attached to the wired infrastructure. We propose a routing scheme which takes the traffic load into consideration and routes the traffic through a load balanced shortest path tree (LB-SPT) rooted at the I-AP. We show that such a routing scheme may significantly improve the system throughput, fairness among the flows, and the average packet delay, as compared with generic shortest path routing. We also propose a load-based channel assignment (L-CA) scheme to judiciously assign the channels among the links. We show that L-CA significantly improves both the system throughput and fairness among the connections, as compared with an uncoordinated random assignment