Wavelength Assignment to Minimize the Numberof SONET ADMs in WDM RingsXin Yuan Amit FulayDepartment of Computer Science, Florida State University, Tallahassee, FL 32306{xyuan, fulay}@cs.fsu.eduAbstract—Optical Wavelength Division Multiplexing (WDM) rings arebeing deployed to support SONET/SDH self-healing rings. The cost of sucha system is dominated by the SONET Add/Drop Multiplexers (ADMs). Tominimize the system cost, algorithms must be developed to assign wave-lengths to lightpaths in the system so that the number of ADMs requiredis minimized. This problem of optimal wavelength assignment to minimizethe number of SONET ADMs is NP–hard. In this paper, we develop an in-teger linear programming (ILP) formation for this problem, propose a newwavelength assignment heuristic, and evaluate the existing and the newlyproposed heuristic using the ILP formation. We conclude that the perfor-mance of the newly proposed heuristic is very close to optimal.I. INTRODUCTIONOptical Wavelength Division Multiplexing (WDM) rings arebeing deployed to support SONET/SDH self-healing rings. Oneof the fundamental design problems for such networks is how toassign wavelengths to the lightpaths in the system so as to mini-mize the system cost. Since the system cost is dominated by theSONET Add/Drop Multiplexers (ADMs)[3], [4], we must de-velop effective wavelength assignment algorithms to minimizethe number of SONET ADMs in the system.In a WDM ring supporting multiple SONET/SDH rings, theSONET ADMs are used to terminate lightpaths. Each lightpathuses two ADMs, one at each end of the lightpath. Although theorigin node only needs the downstream ADM function and thetermination node only needs the upstream ADM function, fullADMs are installed on both nodes to complete the protectionpath around the ring. Each wavelength around the ring providesthe connectivity for a single SONET ring. Two adjacent light-paths that are assigned the same wavelength can share an ADMat the common node. Fig. 1 shows an example of ADM sharing.In the figure, we use the notion (s, t) to represent a lightpathfrom node s to node t. Fig. 1 (a) depicts the case when light-path l1= (a, b) and lightpath l2= (b, c) are assigned differentwavelengths. In this case, 4 ADMs are needed to support thetwo lightpaths. Fig. 1 (b) depicts the case when l1and l2areassigned the same wavelength. In this case, the ADM at node bis shared by both lightpaths and only 3 ADMs are needed. Thisexample shows that wavelength assignment directly affects thenumber of SONET ADMs needed in the system. Notice thatthe wavelength assignment problem has been extensively stud-ied [1], [2]. However, most of the existing wavelength assign-ment algorithms have a different optimization objective, that is,to minimize the total number of wavelengths required in the sys-tem. These algorithms cannot be directly applied to solve theproblem of minimizing the number of SONET ADMs and newThis project was supported in part by NSF grants: CCR-9904943, CCR-0073482 and ANI-0106706.node anode bnode clightpath (a, b) lightpath(b, c)an ADM(a) The lightpaths are assigned different wavelengths.node anode bnode clightpath (a, b)lightpath(b, c)shared ADM(b) The lightpaths are assigned the same wavelength.Fig. 1. An example of sharing ADMsalgorithms must be developed.It has been shown in [5] that the optimal wavelength as-signment problem to minimize the number of SONET ADMsis NP-hard. Heuristic algorithms to solve this problem in-clude Cut–First[3], Assign–First[3], Iterative Merging[5] andIterative Matching[5]. While the relative performance of theseheuristics has been studied in [3], [5], it is unclear how theseheuristics perform with respect to the optimal solutions. In thispaper, we develop an integer linear programming (ILP) forma-tion for this problem, propose a new wavelength assignmentheuristic that improves over the existing most effective heuristic,and evaluate the existing and the newly proposed wavelength as-signment heuristics using the ILP formation. We conclude thatthe performance of the newly proposed wavelength assignmentheuristic is close to that of the optimal algorithm.The rest of the paper is structured as follows. Section II intro-duces the notations and the assumptions. Section III presents theILP formation. Section IV describes our heuristic. Section V re-ports the results of the performance study. Section VI concludesthe paper.II. NOTATIONS AND ASSUMPTIONSGiven an N -node WDM ring network with the nodes la-beled from 0 to N − 1 and a set of full–duplex lightpaths,R = {(si, ti)}, a wavelength assignment assigns a wavelength,2λ, to each of the lightpaths in R. For a duplex lightpath (s, t),we will call s the origin node and t the termination node. Awavelength assignment is valid if no two lightpaths that share acommon link are assigned the same wavelength.When two adjacent lightpaths l1= (a, b) and l2= (b, c) areassigned the same wavelength, an ADM can be shared in nodeb. The process of finding two lightpaths sharing an ADM iscalled merging the two lightpaths. A segment contains one ormore merged lightpaths such that the termination of a lightpath(except the last one) is the origin of the subsequent lightpathsand no two lightpaths share a common link. A segment is saidto be a circle if the segment occupies the whole ring.In this paper, we will focus on the maximum ADM sharingproblem, that is, finding a valid wavelength assignment schemesuch that the number of shared ADMs is maximum. The wave-length assignment to maximize ADM sharing can be solved intwo phases. In the first phase, individual lightpaths are mergedinto segments such that the number of shared ADMs is max-imum. In the second phase, wavelengths are assigned to thesegments. Since the second phase only affects the number ofwavelengths used, but not the number of shared ADMs, this pa-per will focus on the first phase. We will approach this problemwith the following assumptions:• We consider static wavelength assignment. The set of light-paths to assign wavelengths is known a prior.• We do not consider the routing issue in this paper. We willassume that a lightpath is routed clockwise on the ring. The pre-vious work in this problem [3], [5] made the same assumption.• We focus on minimizing the number of ADMs and assumethat the number of wavelength is infinite. As pointed out in[3], [5], minimizing the number of ADMs and minimizing thenumber of wavelengths in the system can sometimes be