| In SONET/WDM networks, the bandwidth requirement of an individual network traffic demand is normally much lower than the capacity provided by a wavelength channel. Therefore multiple low-rate traffic demands are usually multiplexed together to share a high-speed wavelength channel during the transmission, and demultiplexed when arriving at corresponding destinations. This multiplexing/demultiplexing is known as traffic grooming and carried out by SONET Add-Drop Multiplexers (SADM). Since SADMs are expensive network devices, optimization problems in traffic grooming have been focusing on making efficient use of the SADMs. Traffic grooming has attracted a lot of research attention, and the optimization problems are challenging and NP-hard for almost all possible problem settings. In this thesis, we will study the traffic grooming problem and focus on designing efficient performance guaranteed algorithms for Unidirectional Path-Switch Ring (UPSR) networks in the following three categories: Firstly, we study the traffic grooming problem to minimize the total number of required SADMs in order to satisfy a given set of traffic demands, and aim to get better upper bounds on the number of SADMs than those achieved by previous algorithms. Secondly, we analyze the computational complexity and propose an efficient approximation algorithm for grooming the regular traffic pattern, which has not been studied previously. Thirdly, we study the computational complexity and propose efficient approximation algorithms for the Min-Max traffic grooming problem and the Maximum Throughput traffic grooming problem. We will also study the traffic grooming problems in Bidirectional Line-Switched Ring (BLSR) networks and discuss the extensions of our results for UPSR networks to BLSR networks. Finally, we will survey existing research problems on traffic grooming in other network topologies, for which we will discuss possible future research directions. |
