IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 7, NO. 5, OCTOBER 1999 161 Provisioning Algorithms for WDM Optical Networks Murat Alanyali, Member, IEEE, and Ender Ayanoglu, Fellow, IEEE Abstract- This paper concerns connection provisioning for optical networks employing wavelength division multiplexing. A heuristic algorithm is developed and numerically studied for routing and wavelength assignment of a set of static connection requests. The algorithm runs much faster than the optimum solution of this problem. An adaptation of the algorithm is pro- posed to design restorable networks which can handle a specified set of failures. The proposed algorithm is based on taking all failures into consideration simultaneously, and performs better than developing independent designs for each failure. I. ~NTR~DUCTION T RANSPORT networks are WAN’s that provide con- nectivity for aggregated traffic streams. Modem trans- port networks increasingly employ wavelength division mul- tiplexing (WDM) technology to utilize the vast transmission bandwidth of fiber. WDM is based on transmission of data over separate wavelength channels on each fiber. At the present time, WDM is mainly employed as a point-to-point transmission technology. In such networks, optical signals on each wavelength are converted to electrical signals at each network node. On the other hand, WDM optical net- working technology, which has been developed within the last decade and is becoming commercially available [l]-[3], employs wavelengths on an end-to-end basis, without electrical conversion in the network. Provisioning of a transport network refers to assigning network resources to a static traffic demand. Efficient pro- visioning is essential in minimizing the investment made on the network required to accommodate a given demand. In the context of WDM optical networks, provisioning means routing and wavelength selection for a set of end-to-end wavelength allocation demands, given a demand distribution and a network topology. Naturally, provisioning of WDM networks has been subject to considerable interest. This interest concentrates on roughly two categories of settings: the case of limited deployed fiber, where provisioning seeks to minimize the number of required wavelengths [4]-[6], and the case of limited number of wavelengths per fiber, where provisioning Manuscript received February 2, 1998; revised March 18, 1999; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor K. N. Sivarajan. This work was supported in part by Defence Advanced Research Projects Agency under the Multiwavelength Optical Networking Consortium of Lucent Tech- nologies, AT&T, Bellcore, Bell Atlantic, Bell South, and SBC, with the participation of the Naval Research Laboratory and the National Security Agency. M. Alanyali is with the Department of Electrical and Electronics En- gineering, Bilkent University, Bilkent, Ankara TR-06533, Turkey (e-mail: alanyali @ee.bilkent.edu.tr). E. Ayanoglu is with Cisco Systems, San Jose, CA 95134 USA (e-mail: [email protected]). Publisher Item Identifier S 1063-6692(99)08251-5. seeks to minimize the amount of required fiber [7], [8] or to maximize accommodated traffic 191. In this paper, we focus on heuristic methods for provisioning a static set of connections on a given WDM optical network topology. It is assumed that each connection requires a ded- icated wavelength on each link of its path. We consider the setting where there is a fixed set of wavelengths available on each fiber and, therefore, the connections are established at the expense of possibly multiple fibers on network links. Each fiber has a cost which reflects the fiber material, optical amplifiers, and the optical termination equipment at both ends of the link. The objective of provisioning is taken as the minimization of the total network cost. Since transport networks are chartered to carry high volumes of traffic, network failures may have severe consequences. This imposes fault-tolerance as an essential feature for trans- port networks. Fault-tolerance refers to the ability of the network to reconfigure and reestablish communication upon failure, and is widely known as restoration. Restoration en- tails rerouting connections around failed components under a targeted time-to-restore. A neiwork with restoration capability requires redundant capacity to be used in the case of failures, and a primary concern in designing such networks is to provide robustness with. minimal redundancy. In principle, design methods devised for conventional, single-wavelength restorable networks [lo]-[12] can be employed in WDM optical networks as well. Such designs prescribe switching all wavelengths in a fiber together in the case of failure. WDM optical networking, however, provides the capability to switch individual wavelengths, thereby offers a richer set of design methods [13]-1151. The paper is comprised of two parts. The first part concerns provisioning in networks that do not account for restoration. Such a network is called a primary network, and the objective in primary-network design is to minimize the cost associated with the working fibers. This problem can be formulated as an integer linear program (ILP) in a straightforward manner; however, the computational complexity of the ILP is pro- hibitive for a network whose size is not trivial. Therefore, efficient heuristic solution methods are needed. We present such a heuristic algorithm that produces good solutions several orders of magnitude faster than general-purpose ILP packages. The second part of the paper involves an adaptation of this heuristic to provisioning in restorable networks. We consider precomputed restoration schemes where the reaction of the network to certain failures is computed in advance, so