I. Introduction

Optical networking forms the foundation of the global network infrastructure; hence the planning and design of optical networks [1] is crucial to the operation and economics of the Internet and its ability to support critical and reliable communication services. In wavelength division multiplexing (WDM) networks, traffic is carried over lightpaths that are optically switched and, in the absence of wavelength converters, occupy the same wavelength on all of the fiber links along their path. Routing and wavelength assignment (RWA) is the problem of selecting a path and wavelength for each connection demand, subject to the constraint that no two paths sharing a link are assigned the same wavelength. RWA is one of the central problems in the dimensioning, control, and engineering of WDM networks, and it appears as a subproblem in most network design applications, including traffic grooming [2–4], survivability design [5,6], and traffic scheduling [7,8].

In offline RWA [9], the input typically consists of a set of (forecast) traffic demands (i.e., requested connections), and the objective is either to establish all the connections using a minimum number of wavelengths or to maximize the number of accepted connections (in which case the number of wavelengths is taken as a constraint). We refer to the former variant as the minRWA problem and to the latter as the maxRWA problem. Since both problems are NP-hard [10], existing optimization techniques cannot be used to solve optimally instances (with a ring or mesh topology) arising in practice. Consequently, many heuristic solution methods have been developed and evaluated under various assumptions and network settings [11,12].

In this work, we are interested in obtaining optimal solutions to the offline RWA problem. Several mixed integer linear program (MILP) formulations have been proposed in the literature for both the minRWA and maxRWA problems. Most formulations can be categorized as either link-based (see, e.g., [13]) or path-based (see, e.g., [14]), which suffer from two limitations: (1) their size increases rapidly with the number W of wavelengths, and (2) they have a symmetry problem in that multiple solutions with the same objective value can be obtained by simply changing the order of wavelengths. Since the ILP solver has to evaluate all $W!$ distinct optimal solutions, the running time can be unnecessarily long. Hence, these formulations do not scale to networks with 100 or more wavelengths per link that can be realized with current technology.

An alternative formulation was developed in [14] to capitalize on the fact that the wavelength assignment problem is equivalent to the graph multi-coloring problem. This formulation is based on maximal independent sets (MISs) and is such that the problem size is independent of the number of wavelengths. However, the number of MISs grows exponentially with the size n of the graph to be colored. For a general graph, the upper bound on the number of MISs is $3^{(n/3)}$. Note that, in the RWA problem formulation, the size of the graph is equal to the number of paths in the original network, which poses severe scalability challenges. Consequently, rather than solving the MIS formulation directly, the authors of [14] used its LP relaxation to obtain lower bounds.

To overcome this limitation, column generation techniques may be used. Column generation, first proposed in the context of graph coloring in [15], is an iterative technique which formulates the problem with a subset of MISs and adds any necessary additional variables on the fly by solving a second simpler LP. This technique has also been applied to solve the RWA problem in [16,17]. Although the column generation method does yield smaller problem sizes for each iteration, it nevertheless may require a large number of iterations and a recent comprehensive study specific to the RWA problem [17] reports low speed-up factors. Consequently, column generation in its basic form may not scale to realistic network sizes to be of practical value for network operators.

In this paper, we consider the offline RWA problem in WDM ring networks. Although operators have started to transition to mesh networks, vast parts of the current infrastructure are based on SONET/SDH rings; for instance, AT&T operates more than 6700 rings in North America (http://www.isp-planet.com/resources/backbones/att.html). Furthermore, DWDM transport networks with topological rings are being deployed that are based on technologies other than SONET (e.g., Ethernet, IP/MPLS, etc.). Hence, optimal solutions for WDM rings will be important for the foreseeable future, and they may also provide insight as regards extending the techniques to mesh networks.

Starting with the MIS formulation, we develop a decomposition approach to obtain an equivalent formulation with a much smaller number of variables. Our approach consists of partitioning the path set and representing the MIS in the original network using the independent sets calculated in each of these partitions. The result is a suite of formulations that trades off the number of variables with the number of constraints and, as a result, achieves a much better scalability in terms of network size. We present numerical results to demonstrate that our new formulation achieves a reduction in running time of several orders of magnitude compared to the link, path, or original MIS formulation. Specifically, we show that ring networks of least 16 nodes (the maximum size of a SONET ring) can be solved in just a few seconds, while larger rings up to 24 nodes (e.g., for transport technologies other than SONET) can be solved efficiently. Therefore, our new approach has several unique practical benefits for network designers and operators, including (1) the ability to solve the RWA problem optimally for any existing WDM ring network and for any number of wavelengths, (2) the ability to perform extensive “what-if” analysis to evaluate the sensitivity of the optimal solution to uncertainties in forecast traffic demands, and (3) the potential to speed up the solution of other hard network design problems for which RWA is a subproblem. While it may not be possible to obtain optimal solutions to all hard network design problems that include RWA as a subproblem, the capability of solving larger instances to optimality makes it possible to evaluate the performance of heuristics and develop more efficient ones.

The rest of the paper is organized as follows. In the next section, we introduce the network model and notation, and, for the sake of completeness, we review earlier link, path, and MIS formulations of the minRWA problem. In Section III, we describe a new and exact formulation based on a decomposition of the MIS. We present numerical results in Section IV, and we conclude in Section V.

II. Notation and Existing RWA Formulations

The physical topology of an optical network can be represented as a graph $G=(\mathcal{N},\mathcal{L})$, where $\mathcal{N}$ is the set of N network nodes and $\mathcal{L}$ is the set of L physical links connecting the nodes. We assume that each physical link is directed and consists of a single fiber supporting W wavelength channels. Nodes are connected with two links in opposite directions. The amount of traffic demand from node s to node d, in terms of the number of lightpaths (connections) to be set up, is represented as $t_{sd}$, and $T=\left[t_{sd}\right]$ forms the overall network traffic matrix.

The set of all node pairs in the network is denoted as $\mathcal{Z}$, i.e., $\mathcal{Z}=\{(i,j):i,j\in \mathcal{N},i\ne j\}$ and $Z=\left|\mathcal{Z}\right|$. In a ring network, there are two possible paths between the members of a node pair $(i,j)\in \mathcal{Z}$: one in the clockwise and the other in the counter-clockwise direction, represented as $p_{ij,cw}$ and $p_{ij,ccw}$, respectively. The set of all paths $\mathcal{P}$ is the union of the set of clockwise paths (denoted by ${\mathcal{P}}^{cw}$) and the set of counter-clockwise paths (denoted by ${\mathcal{P}}^{ccw}$), where ${\mathcal{P}}^k=\left\{p_{ij,k}\right\}$ for $k=cw,ccw$, and $P=\left|\mathcal{P}\right|$.

Using the above notation, the minRWA problem can be defined as determining the minimum number of wavelengths to satisfy all the demands in T, subject to the constraint that no two lightpaths sharing a common link use the same wavelength. On the other hand, the maxRWA problem can be defined as maximizing the number of satisfied demands for a given number of wavelengths, subject to the same constraint. In the following subsections, we present link, path, and MIS formulations of the minRWA problem, using consistent notation. To avoid repetition, we omit the formulations for the maxRWA problem; however, these can be derived from the formulations presented here by appropriately adapting the objective function and some of the constraints.

A. Link Formulation

Denoting the set of links outgoing from (respectively, incoming to) node n as ${\mathcal{L}}_n^{+}$ (respectively, ${\mathcal{L}}_n^{-}$), the minRWA formulation can be stated as follows:

B. Path Formulation

For ring networks, there are only two possible paths between the members of each node pair. Hence, the routing subproblem reduces to selecting either the clockwise or the counter-clockwise path for each lightpath between the members of a node pair, which results in significant reduction in problem size compared to that for arbitrary network topologies. The path formulation for the minRWA problem is given as follows:

C. MIS Formulation

The wavelength assignment problem can be transformed into a graph multi-coloring problem by defining a new graph $G_p$ where each node corresponds to a path in G and two nodes are connected to each other in $G_p$ if the corresponding paths in G share a common link. The problem is then equivalent to assigning separate colors to a node in $G_p$ for each lightpath established over the corresponding path in G such that the two adjacent nodes are not assigned the same color. Thus, a set of paths in G can be assigned the same wavelength if the corresponding nodes in $G_p$ form an independent set.

We denote the number of lightpaths on path $p_{ij,k}$ as $b_{ij,k}$, and let $v_m$ be the number of wavelengths assigned to the independent set m. Let $\mathcal{M}$ denote the set of all MISs in $G_p$, which can be calculated efficiently using the Bron–Kerbosch algorithm [18]. Also, let $Y_{ij,k}^m$ be the path–path set incidence function defined as

The ILP formulation can now be written as

The first set of constraints ensures that the traffic demand between the members of each node pair is satisfied by using lightpaths over the clockwise and counter-clockwise paths. Since the number of wavelengths assigned to a path is the sum of the number of wavelengths assigned to MISs which include that path, the second set of constraints ensures that each path is assigned a sufficient number of wavelengths.

The MIS formulation has the clear advantage of being independent of the number W of wavelengths, whereas the sizes of the path-based and link-based formulations increase with W. Moreover, the link and path formulations have a symmetry problem, as we discussed earlier. On the other hand, the number of MISs in $G_p$ increases exponentially with the number of paths, which in turn increases quadratically with the number of nodes in G. Therefore, the number of variables, $v_m$, grows rapidly with the size of the network, limiting the applicability of the MIS formulation to small networks.

III. Maximal Independent Set Decomposition (MISD) and RWA Formulations Based on MISD

Recall that the limiting factor for the basic MIS formulation of [14] is the exponential increase in the number of MISs with the number of vertices of $G_p$. We now present a decomposition approach to obtain a formulation equivalent to expressions (10)–(12) with a much smaller number of MIS decision variables. This is achieved by partitioning the path set $\mathcal{P}$ and representing the MISs in the original network using the independent sets calculated in each of these partitions. The method is based on recursively identifying two nearly equal and preferably large independent subgraphs in the path graph, $G_p$, and dividing $G_p$ into three components; two of these are the identified independent subgraphs and the third subgraph includes the rest of the nodes in $G_p$. We first illustrate how the MIS decomposition (MISD) technique works for two and four partitions of the link set and then generalize it to $2^x$ partitions. We use the notation MISD-$2^x$ to denote the ILP formulation in which the link set is partitioned into $2^x$ groups. We emphasize that the decomposition is exact, not a heuristic approach, and thus yields optimal results for ring networks.

A. Maximal Independent Set Decomposition With Two Independent Path Sets: MISD-2

MISD-2 is based on the observation that the clockwise paths of a ring do not intersect with counter-clockwise paths. Therefore $G_p$ can be divided into two disconnected components, $G_p^{cw}$ and $G_p^{ccw}$, corresponding to the sets ${\mathcal{P}}^{cw}$ and ${\mathcal{P}}^{ccw}$, respectively. Let ${\mathcal{M}}^{cw}$ (respectively, ${\mathcal{M}}^{ccw}$) denote the set of MISs in $G_p^{cw}$ (respectively, $G_p^{ccw}$). Also, we define $v_m^k$ as the number of wavelengths assigned to the MIS $m\in {\mathcal{M}}^k$ for $k=cw,ccw$. Then expressions (11) and (12) in the basic MIS formulation are replaced with

Note that, for each $m_i\in {\mathcal{M}}^{cw}$ and $m_j\in {\mathcal{M}}^{ccw}$, $m_i\cup m_j$ is an MIS for $G_p$. Hence, the number of MISs in the original path graph is $\left|\mathcal{M}\right|=\left|{\mathcal{M}}_{cw}\right|\times \left|{\mathcal{M}}_{ccw}\right|$. Due to the construction of sets ${\mathcal{M}}^{cw}$ and ${\mathcal{M}}^{ccw}$, this MISD-2 formulation contains a number of MIS decision variables that are equal to $2\sqrt{\left|\mathcal{M}\right|}$. This is a substantial decrease in the size of the problem compared to the basic formulation above that becomes more significant as the number of ring nodes increases.

B. Maximal Independent Set Decomposition With Four Independent Path Sets: MISD-4

In order to further decrease the number of variables in the formulation, the network topology can be partitioned into four parts, so as to represent the MISs in the path graph using smaller independent sets from the smaller subgraphs. Specifically, $G_p^k(k=cw,ccw)$ is divided recursively into three subgraphs: $G_p^{k,core}$, $G_p^{k,0}$, and $G_p^{k,1}$. The partitions are selected such that there are no links between the nodes in $G_p^{k,0}$ and the nodes in $G_p^{k,1}$. The remaining nodes are collected in the set $G_p^{k,core}$. This operation is equivalent to partitioning the path set ${\mathcal{P}}^k$ into three subsets, where none of the paths in ${\mathcal{P}}^{k,0}$ intersect with any of the paths in ${\mathcal{P}}^{k,1}$. Also, ${\mathcal{P}}^{k,core}$ includes the remaining paths in ${\mathcal{P}}^k$, which may intersect with the paths in ${\mathcal{P}}^{k,0}$ and/or ${\mathcal{P}}^{k,1}$.

For the ring network case, an appropriate partitioning can be obtained, based on the links that each path uses. Assuming that nodes in the ring network are numbered from 1 to N in the clockwise direction, and denoting the clockwise (respectively, counter-clockwise) set of links as ${\mathcal{L}}^{cw}$ (respectively, ${\mathcal{L}}^{ccw}$), the link set can be divided into four sets: two sets, ${\mathcal{L}}^{cw,0}$ and ${\mathcal{L}}^{ccw,0}$, containing the links in ${\mathcal{L}}^{cw}$ and ${\mathcal{L}}^{ccw}$, respectively, among nodes $\{1,\dots ,\lfloor N/2\rfloor \}$, and two sets, ${\mathcal{L}}^{cw,1}$ and ${\mathcal{L}}^{ccw,1}$, containing the links in ${\mathcal{L}}^{cw}$ and ${\mathcal{L}}^{ccw}$, respectively, among nodes $\{\lfloor N/2\rfloor +1,\dots ,N\}$. Accordingly, the path set can be divided into six sets:

This partition results in four independent path sets, namely, ${\mathcal{P}}^{cw,0}$, ${\mathcal{P}}^{cw,1}$, ${\mathcal{P}}^{ccw,0}$, and ${\mathcal{P}}^{ccw,1}$; hence we refer to the resulting formulation as MISD-4.

Unlike in the MISD-2 formulation, the three subgraphs in $G_p^k(k=cw,ccw)$ are not completely disjoint, so MISs in $G_p^k$ cannot be represented simply by the union of MISs in smaller subgraphs. Therefore, we introduce the notion of a “core” set. Core sets for $G_p^k$ are denoted as ${\mathcal{Q}}^k$ and defined as the sets of nodes in $G_p^{k,core}$ which are maximal subsets of any MIS in $G_p^k$. In other words, ${\mathcal{Q}}^k$ includes the intersection of any MIS in $G_p^k$ with the node set $G_p^{k,core}$ as an element. Consequently, any MIS in $G_p^k$ can be written as the union of a set in ${\mathcal{Q}}^k$ and some nodes in $G_p^{k,0}$ and/or $G_p^{k,1}$. The core sets are calculated using the following algorithm, called Algorithm 1. The running time complexity of the algorithm is $O\left(\right|{\mathcal{Q}}^k\left|N^2\right)$.

Finally, for each core set $q\in {\mathcal{Q}}^k$, the maximal sets of nodes in $G_p^{k,r}$ which are independent from each other and the nodes in q, ${\mathcal{M}}_q^{k,r}$, are calculated for $k=cw,ccw,r=0,1$. With these definitions, for each $q\in {\mathcal{Q}}^k$ and $m_i\in {\mathcal{M}}_q^{k,0}$ and $m_j\in {\mathcal{M}}_q^{k,1}$, $m_i\cup q\cup m_j$ corresponds to an MIS in $G_p^k$.

The MISD-4 formulation can now be obtained by replacing expressions (11) and (12) in the basic MIS formulation with the following equations:

This decomposition approach can be further extended to develop formulations with 8 (MISD-8), 16 (MISD-16), or, in general, $2^x$ independent path sets (MISD-$2^x$). In this generalized MISD formulation, the ring topology (i.e., the link set) is partitioned in half recursively, resulting in more subgraphs in $G_p$ but a smaller number of total independent sets in all subgraphs. The details of the general decomposition, MISD-$2^x$, are presented in Appendix A.

C. Illustrative Example

To better clarify the operation of the MISD algorithms, in this section we present a simple illustration using the four-node ring network depicted in Fig. 1. Each path is denoted as the sequence of nodes that it traverses.

 

Fig. 1 (Color online) The four-node ring network for the example in Subsection III.C.

Download Full Size | PDF

MIS Formulation. The basic algorithm calculates the set of MISs, $\mathcal{M}$, using the whole set of paths, $\mathcal{P}$, without partitioning. The number of MISs is found to be 121.

MISD-2 Formulation. The MISD-2 algorithm partitions the sets into two subsets. The set of clockwise paths is ${\mathcal{P}}^{cw}=\{12,23,34,41,123,234,341,412,1234,2341,3412,4123\},$ and the set of counter-clockwise paths is ${\mathcal{P}}^{ccw}=\{14,43,32,21,143,432,321,214,1432,4321,3214,2143\}.$ Then, the MISs in ${\mathcal{P}}^{cw}$ and ${\mathcal{P}}^{ccw}$ are calculated as follows: ${\mathcal{M}}^{cw}=\{\{12,23,341\},\{23,34,412\},\{34,41,123\},\{12,2341\},\{41,12,234\},\{23,3412\},\{34,4123\},\{41,1234\},\{123,341\},\{234,412\},\{12,23,34,41\}\},{\mathcal{M}}^{ccw}=\{\{14,43,321\},\{43,32,214\},\{32,21,143\},\{14,4321\},\{21,14,432\},\{43,3214\},\{32,2143\},\{21,1432\},\{143,321\},\{432,214\},\{14,43,32,21\}\}$, respectively.

The cross-product of sets in ${\mathcal{M}}^{cw}$ and ${\mathcal{M}}^{ccw}$ (each of size 11) is equal to the set $\mathcal{M}$ (of size 121) for the original MIS formulation above.

MISD-4 Formulation. The MISD-4 algorithm partitions the clockwise paths into two independent sets and a core set as in Fig. 2:

 

Fig. 2 (Color online) MISD-4 path set partitions in a four-node ring network.

Download Full Size | PDF

 

Fig. 3 Path graph $G_p^{cw}$ for clockwise paths in a four-node ring network.

Download Full Size | PDF

The next step is to include the paths into the path graph $G_p^{cw}$, as shown in Fig. 3. No two paths in $G_p^{cw,0}$ and $G_p^{cw,1}$ share a common link. Then, the set of core sets for the clockwise paths, ${\mathcal{Q}}^{cw}$, is calculated in $G_p^{cw,core}$ as follows:

As a result, ${\mathcal{Q}}^{cw}=\{\left\{3412\right\},\left\{2341\right\},\left\{1234\right\},0,\{412,234\},\left\{412\right\},\left\{234\right\}\}$. Then, for each $q\in {\mathcal{Q}}^{cw}$, ${\mathcal{M}}_q^{cw,0}$ and ${\mathcal{M}}_q^{cw,1}$ are obtained as in Fig. 4. Comparing with the set ${\mathcal{M}}^{cw}$ obtained above for MISD-2, we observe that, for each $q\in {\mathcal{Q}}^{cw}$, $m_i\in {\mathcal{M}}_q^{cw,0}$ and $m_j\in {\mathcal{M}}_q^{cw,1}$, $m_i\cup q\cup m_j$ is an MIS in graph $G_p^{cw}$ corresponding to set ${\mathcal{P}}^{cw}$. For instance, the top left part of Fig. 4 shows that, for $q_1=\left\{3412\right\}$, $M_1^{cw,0}=0$ as $q_1$ intersects with links 34 and 41, while $M_1^{cw,1}=\left\{23\right\}$ as $q_1$ intersects only with link 12; the union of these three sets, i.e., $\{3412,23\}$ is an MIS for $G_p^{cw}$. The sets ${\mathcal{Q}}^{ccw}$, ${\mathcal{M}}_q^{ccw,0}$, and ${\mathcal{M}}_q^{ccw,1}$ are similarly obtained for the counter-clockwise paths.

 

Fig. 4 Representation of MISs in $G_p^{cw}$ by the MISs in $G_p^{cw,0}$ and $G_p^{cw,1}$ and core sets in $G_p^{core}$.

Download Full Size | PDF

D. Comparison of the MIS and MISD-$2^x$ Formulations

 

Fig. 5 (Color online) Comparison of formulations in terms of MIS decision variables.

Download Full Size | PDF

IV. Numerical Results

We now present numerical results in order to compare the efficiency of the link, path, MIS, MISD-2, MISD-4, and MISD-8 formulations of the RWA problem. To this end, we used the CPLEX 11 optimization software to solve the corresponding formulations of identical problem instances on a cluster of compute nodes with dual Woodcrest Xeon processors running at 2.33 GHz with a 1333 MHz memory bus, 4 GB of memory, and a 4 MB L2 cache.

In our comparisons, we used a large set of random problem instances that were generated by varying the number N of nodes in the ring network ($N=6,7,\dots ,24$), the number W of wavelengths per link ($W=10,20,\dots ,160$), and the traffic demands $t_{sd}$ (in lightpaths) between the members of the various source–destination pairs $(s,d)$ in the network. We also imposed a time limit of 2 CPU hours for CPLEX to find a solution for a given formulation and problem instance; if it failed to do so within the 2 h limit, we terminated the execution run and report this fact in the figures shown in this section.

Figure 6 compares the various formulations of minRWA in terms of the CPU time (on a log scale) that it takes for CPLEX to find an optimal solution against the size N of the ring network. Each data point in the figure represents the average of 30 random instances generated by drawing traffic demands (in lightpaths) uniformly at random in the interval $[0,T_{\max }]$, where $T_{\max }$ is the maximum traffic demand. Figure 6(a) presents results with $T_{\max }=3$ while Fig. 6(b) shows results for $T_{\max }=9$. The data points in the light gray area of the figures labeled “tLim” correspond to instances that could not be solved within the 2 h time limit that we mentioned above. On the other hand, the data points in the top dark gray area of the figures labeled “Mem” correspond to instances for which the formulation could not fit in the available memory for CPLEX to run.

 

Fig. 6 (Color online) Solution times as a function of N.

Download Full Size | PDF

The results in Fig. 6(a) ($T_{\max }=3$) indicate that the link formulation fails to solve instances with $N>10$ nodes within the time limit. The path formulation is more efficient: CPLEX is able to find the optimal solution for $N\le 16$, but the running time exceeds the 2 h limit for all instances with $N>16$. MIS runs faster than the path and link formulations up to 8 and 10 nodes, respectively. However, the formulation size becomes too large for CPLEX to solve beyond 10 nodes. The new MISD formulations perform much better, with running times below 1 s up to 14–15 nodes (for MISD-4 and MISD-8), several orders of magnitude less than those for the other three. Beyond 12 nodes, MISD-2 performs noticeably worse than MISD-4 and MISD-8, and beyond 20 nodes its size becomes too large to fit in memory; similarly, MISD-8 starts outperforming MISD-4 for networks with $N\ge 18$ nodes. MISD-8 is able to obtain the optimal solution for 24 nodes, 8 nodes more than for the path formulation in about the same amount of time.

Let us turn our attention to Fig. 6(b), which compares the various formulations for instances with $T_{\max }=9$. Despite the much larger traffic demand between the members of the node pairs, the running times of the MISD formulations remain almost the same, and MISD-8 is again able to solve up to 24-node networks within the imposed 2 h limit. On the other hand, the running time of the path and link formulations increase significantly compared to that for the same ring size in Fig. 6(a), and the path formulation can no longer solve 16-node networks within the same time limit. This result is due to the fact that, as the traffic load increases, a larger number of wavelengths are needed to carry the traffic, which in turn increases the number of variables in the link and path formulations. On the other hand, the number of variables in all MISD formulations is independent of the number of wavelengths; hence their running times are not affected by the traffic demands. This behavior is illustrated in Fig. 7, which plots the running times of three MISD formulations, against the maximum traffic demand $T_{\max }$, for 16-node rings. Again, each data point in the figure represents the average of 30 random instances generated by drawing traffic demands (in lightpaths) uniformly at random in the interval $[0,T_{\max }]$. As we can see, the running time of the MISD formulations remains almost constant across the range of traffic loads.

 

Fig. 7 (Color online) Solution times as a function of $T_{\max };N=16$.

Download Full Size | PDF

Figure 8 presents another set of experiments that we performed to determine the maximum number of nodes in a problem instance that can be solved by each formulation for different values of the number W of wavelengths within 3000 s. The problem instances were generated in the same manner as those shown in Fig. 6(a). The dark gray area in the figure denotes instances that are infeasible. Note that, since the MIS and MISD-z formulations are independent of W, the corresponding curves are straight lines parallel to the x-axis; also, these formulations find optimal solutions even when the problem is infeasible for the indicated number of wavelengths (of course, the optimal solution in this case is a value of W higher than the indicated one). As we can see, among the MIS-based formulations, MISD-8 has the best scalability (it can find solutions for $N=24$ nodes), followed by MISD-4 and MISD-2 (the latter can find solutions for $N=16$ nodes, i.e., a maximum size SONET ring), while MIS can only solve instances up to $N=10$ nodes due to excessive memory requirements. Within the 3000 s limit, the link formulation can obtain solutions for up to $N=10$–11 nodes for a moderate number of wavelengths, but as W increases, it is limited to small networks. Finally, the path formulation performs better than the link formulation, but is also severely restricted as W increases to the limits of current technology.

 

Fig. 8 (Color online) Size of the largest network size $N_{\max }$ that can be solved with each minRWA formulation for a given number W of wavelengths, within 3000 s of CPU time.

Download Full Size | PDF

From a practical perspective, MISD-4 and MISD-8 make it possible to solve RWA optimally for maximum size (16-node) SONET rings in only a few (i.e., 2–3) seconds; importantly, the running times are not sensitive to the traffic load. Such instances can only be tackled using the path formulation, but, depending on the traffic load, CPLEX may take several hours or more, on average, to find the optimal solution. Consequently, MISD-4 and MISD-8 allow network designers and operators to perform extensive “what-if” analysis by investigating large numbers of scenarios regarding forecast demands, cost and price structures, etc.; such analysis would either not have been possible previously or would require vast amounts of computational resources and time.

V. Concluding Remarks

RWA is one of the most important problems arising in the design of WDM networks, and it has been studied extensively. However, existing formulations face significant scalability challenges as the number of wavelengths supported by optical transmission technology continues to increase. We have developed an exact ILP formulation that is based on recursive graph partitioning and has the advantage that its size is independent of the number of wavelengths and the traffic load. We have demonstrated that the new approach enables the solution of problems in times that are several orders of magnitude faster than conventional methods, making it possible to solve network instances of practical size to optimality. We are currently working to extend this work in two directions: (1) develop efficient MISD techniques for networks of general topology, and (2) investigate the impact of these more efficient RWA formulations on the complexity of other important network design problems, including traffic grooming, which include RWA as a subproblem.

Appendix A Generalized MIS Decomposition With $2^x$ Independent Sets: MISD-$2^x$

 

Fig. 9 Path graph of MISD-$2^x$.

Download Full Size | PDF

Consider a ring network with N nodes. In such a network, the MISD approach that we discussed in Section III can be applied recursively up to z times, where z is the largest integer such that $2^z\le 2N$. Recall that the first decomposition (MISD-2) divides the link set of the ring network into two directional rings, i.e., those consisting of the clockwise and counter-clockwise links, respectively. Consider now the clockwise directional ring; similar observations apply to the counter-clockwise ring. The next decomposition (i.e., MISD-4) divides the link set of the clockwise ring into two link sets by bisecting the ring (e.g., in the north-to-south direction) to create two half-rings; as a result, either the two link sets are of equal size (if N is even) or their size differs by 1 (if N is odd). Each subsequent decomposition divides the link sets from the previous decomposition in the same manner. Consequently, for, say, a 16-node ring, the fifth decomposition will result in 2⁴ link sets (for each directional ring) comprising a single link; hence the constraint $2^z\le N$.

Consider now the MISD-$2^x$ formulation, $x\le z$, and let ${\mathcal{L}}^k(k=cw,ccw)$ denote the link sets of the clockwise and counter-clockwise rings, respectively. In effecting the $x\mathrm{th}$ decomposition, each of these link sets is divided into $2^{x-1}$ sets: ${\mathcal{L}}^{k,1},\dots ,{\mathcal{L}}^{k,2^{x-1}}$. Accordingly, the path sets ${\mathcal{P}}^k(k=cw,ccw)$ are partitioned into $2^x-1$ sets following a tree topology with x levels (refer to Fig. 9):

• • ${\mathcal{P}}^{k,2^{x-1}},\dots ,{\mathcal{P}}^{k,2^x-1}$, the lowest levels of path partitions, consist of paths containing only links within each link set ${\mathcal{L}}^{k,s}(s=1,\dots ,2^{x-1})$;
• • ${\mathcal{P}}^{k,2^{x-2}},\dots ,{\mathcal{P}}^{k,2^{x-1}-1}$, the second-lowest levels of path partitions, include paths containing only links from the two adjacent path partitions ${\mathcal{L}}^{k,2s-1}$ and ${\mathcal{L}}^{k,2s}(s=1,\dots ,2^{x-2})$;
• • $\dots ;$
• • ${\mathcal{P}}^{k,1}$, the highest level of path partitions, consists of paths which use links from both half-rings; this corresponds to the core partition in Fig. 2.

Figure 9 presents the path graph topology of the MISD-$2^x$ approach (without loss of generality, only the clockwise subgraph is presented). $G_p^{cw,s}(s=1,\dots ,2^{x-1})$ denotes the subgraph corresponding to path set ${\mathcal{P}}^{cw,s}$. Two subgraphs are connected with a dotted line if the paths in the two subgraphs can share a common link. It is easily seen that all the leaf subgraphs, $G_p^{k,2^{x-1}},\dots ,G_p^{k,2^x-1}$, are mutually independent. The only connections among the subgraphs are between the child subgraphs and parent subgraphs. Therefore, an MIS in $G_p^{cw}$ can be represented by the union of core sets in the parent subgraph and MISs in the child subgraph. Starting from the root of the subgraph tree, an MIS $m_{cw}$ in $G_p^{cw}$ is represented by the union of an MIS $m_{cw,2}$ in $G_p^{cw,2}$, a core set $q_{cw,1}$ in $G_p^{cw,1}$, and an MIS $m_{cw,3}$ in $G_p^{cw,3}$, i.e., $m_{cw}=m_{cw,2}\cup q_{cw,1}\cup m_{cw,3}$. Recursively, the MIS $m_{cw,2}$ is equal to the union of $m_{cw,4}$ in $G_p^{cw,4}$, core set $q_{cw,2}$ in $G_p^{cw,2}$, and $m_{cw,5}$ in $G_p^{cw,5}$, i.e., $m_{cw,2}=m_{cw,4}\cup q_{cw,2}\cup m_{cw,5}$. Similarly, we have that $m_{cw,3}=m_{cw,6}\cup q_{cw,3}\cup m_{cw,7}$. As shown in Fig. 10, these substitutions result in $m_{cw}=(m_{cw,4}\cup q_{cw,2}\cup m_{cw,5})\cup q_{cw,1}\cup (m_{cw,6}\cup q_{cw,3}\cup m_{cw,7})$. This substitution process continues recursively until it reaches the leaf subgraph in the path graph tree. Therefore, an MIS in $G_p^{cw}$ will be represented by the union of MISs in the leaf subgraphs and core sets in non-leaf subgraphs, i.e., $m_k={\bigcup }_{s=1}^{2^{x-1}-1}{q}_{k,s}{\bigcup }_{s^{\prime }=2^{x-1}}^{2^x-1}{m}_{k,s^{\prime }}(k=cw,ccw)$.

 

Fig. 10 MIS Representation in MISD-$2^x$.

Download Full Size | PDF

To describe the exact MISD-$2^x$ formulation we introduce additional notation. We define $q_{k,r}$ as the core sets in the non-leaf subgraph $G_p^{k,r}(k=cw,ccw,r=1,\dots ,2^{x-1}-1)$ and define $m_{k,r}$ as MISs in the leaf subgraph $G_p^{k,r},(k=cw,ccw,r=2^{x-1},\dots ,2^x-1)$. To include the network topology in the formulation, we define $X_{ij,k}^{q_{k,r}}$ as a binary variable that indicates whether $p_{ij,k}\in q_{k,r}$ and define $X_{ij,k}^{m_{k,r}}$ as a binary variable that indicates whether $p_{ij,k}\in m_{k,r}$. We also let $M_{k,r\prime }^{q_{k,r}}$ be the set of MISs in the leaf subgraph $G_p^{k,r\prime }$ that corresponds to core set $q_{k,r}$ and let $Q_{k,r\prime }^{q_{k,r}}$ be the set of core sets in the non-leaf subgraph $G_p^{k,r\prime }$ that corresponds to core set $q_{k,r}$.

The two sets of decision variables in the formulation are

• • $V_{q_{k,r}}$: number of wavelengths assigned to core set $q_{k,r}$; and
• • $V_{m_{k,r}}$: number of wavelengths assigned to MIS $m_{k,r}$.

The MISD-$2^x$ formulation can now be obtained by replacing expressions (11) and (12) in the basic MIS formulation with constraints (19) to (24). Expressions (19) to (21) are x sets of constraints making sure that a sufficient number of wavelengths is assigned to each path in different path subgraphs and are a generalization of constraints (15) and (16) in the MISD-4 formulation. Specifically, constraint (19) accounts for paths in the top level subgraph, constraint (20) accounts for paths in the second-level subgraphs, etc., and finally constraint (21) accounts for paths in the leaf subgraphs. Expressions (22) to (23) are $x-1$ sets of constraints used to ensure consistency between wavelength assignments in different subgraphs and are generalizations of constraints (18) in the MISD-4 formulation. Finally, expression (24) sets V to the number of wavelengths used and is equivalent to (17) in the MISD-4 formulation:

(19)$${\displaystyle b_{ij,k}\le \sum _{q_{k,1}\in Q_{k,1}}{V}_{q_{k,1}}\underset{ij,k}{\overset{q_{k,1}}{X}}\forall p_{ij}\in \underset{p}{\overset{k,1}{G}},k=cw,ccw,}$$

(20)$${\displaystyle b_{ij,k}\le \sum _{q_{k,1}\in Q_{k,1}}\sum _{q_{k,r}\in \underset{k,r}{\overset{q_{k,1}}{Q}}}{V}_{q_{k,r}}\underset{ij,k}{\overset{q_{k,r}}{X}}\forall p_{ij}\in G_p^{k,r},k=cw,ccwr=2,3,}$$

(21)$${\displaystyle \dots \dots b_{ij,k}\le \sum _{q_{k,1}\in Q_{k,r_1}}\sum _{q_{k,r_2}\in \underset{k,r_2}{\overset{q_{k,1}}{Q}}}\cdots \sum _{q_{k,r_s-1}\in \underset{k,r_{s-1}}{\overset{q_{k,r_{s-2}}}{Q}}}\sum _{m_{k,r_s}\in \underset{k,r_s}{\overset{q_{k,r_{s-1}}}{M}}}{V}_{m_{k,r_s}}\underset{ij,k}{\overset{m_{k,r_s}}{X}}\forall p_{ij,k}\in \underset{p}{\overset{k,r_s}{G}},s=x,2^{x-1}\le r_s\le 2^x-1,r_{s-1}=⌊\frac{r_s}{2}⌋,r_{s-2}=⌊\frac{r_{k-1}}{2}⌋,\dots ,r_1=⌊\frac{r_2}{2}⌋=1,k=cw,ccw,}$$

(22)$${\displaystyle \sum _{q_{k,r}\in \underset{k,r}{\overset{q_{k,1}}{Q}}}{V}_{q_{k,r}}=V_{q_{k,1}}k=cw,ccwr=2,3,}$$

(23)$${\displaystyle \dots \dots \sum _{m_{k,r_s}\in \underset{k,r_s}{\overset{q_{k,r_{s-1}}}{M}}}{V}_{m_{k,r_s}}=V_{q_{k,r_{s-1}}}s=x,2^{x-1}\le r_s\le 2^x-1,r_{s-1}=⌊\frac{r_s}{2}⌋k=cw,ccw,}$$

(24)$${\displaystyle V\ge \sum _{q\in Q_k}\underset{q}{\overset{k,1}{v}}k=cw,ccw.}$$

References

1. J. M. Simmons, Optical Network Design and Planning. Springer, 2008.

2. R. Dutta, A. E. Kamal, and G. N. Rouskas, Eds., Traffic Grooming in Optical Networks: Foundations, Techniques, and Frontiers, Springer, 2008.

3. R. Dutta and G. N. Rouskas, “Traffic grooming in WDM networks: past and future,” IEEE Network , vol. 16, no. 6, pp. 46‒56, Nov./Dec. 2002. [CrossRef]  

4. K. Zhu and B. Mukherjee, “Traffic grooming in an optical WDM mesh network,” IEEE J. Sel. Areas Commun. , vol. 20, no. 1, pp. 122‒133, Jan. 2002. [CrossRef]  

5. S. Ramamurthy, L. Sahasrabuddhe, and B. Mukherjee, “Survivable WDM mesh networks,” J. Lightwave Technol. , vol. 21, no. 4, pp. 870‒883, Apr. 2003. [CrossRef]  

6. S. Ramamurthy and B. Mukherjee, “Survivable WDM mesh networks, part I—protection,” in Proc. of INFOCOM ’99, Mar. 1999, pp. 744‒751.

7. J. Kuri, N. Puech, M. Gagnaire, E. Dotaro, and R. Douville, “A review of routing and wavelength assignment of scheduled lightpath demands,” IEEE J. Sel. Areas Commun. , vol. 21, no. 8, pp. 1231‒1240, Oct. 2003. [CrossRef]  

8. W. Su and G. Sasaki, “Scheduling periodic transfers with flexibility,” in Proc. of 41st Allerton Conf., Oct. 2003.

9. B. Jaumard, C. Meyer, and B. Thiongane, “ILP formulations and optimal solutions for the RWA problem,” in Proc. of IEEE GLOBECOM’04, Nov. 29–Dec. 3 2004, vol. 3, pp. 1918‒1924.

10. I. Chlamtac, A. Ganz, and G. Karmi, “Lightpath communications: an approach to high bandwidth optical WANS,” IEEE Trans. Commun. , vol. 40, no. 7, pp. 1171‒1182, July 1992. [CrossRef]  

11. R. Dutta and G. N. Rouskas, “A survey of virtual topology design algorithms for wavelength routed optical networks,” Opt. Networks Mag. , vol. 1, no. 1, pp. 73‒89, Jan. 2000.

12. H. Zang, J. P. Jue, and B. Mukherjee, “A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks,” Opt. Networks Mag. , vol. 1, no. 1, pp. 47‒60, Jan. 2000.

13. R. M. Krishnaswamy and K. N. Sivarajan, “Algorithms for routing and wavelength assignment based on solutions of LP-relaxations,” IEEE Commun. Lett. , vol. 5, no. 10, pp. 435‒437, Oct. 2001. [CrossRef]  

14. R. Ramaswami and K. Sivarajan, “Routing and wavelength assignment in all-optical networks,” IEEE/ACM Trans. Netw. , vol. 3, no. 5, pp. 489‒500, Oct. 1995. [CrossRef]  

15. A. Mehrotra and M. Trick, “A column generation approach for graph coloring,” INFORMS J. Comput. , vol. 8, no. 4, pp. 344‒354, 1996. [CrossRef]  

16. T. Lee, K. Lee, and S. Park, “Optimal routing and wavelength assignment in WDM ring networks,” IEEE J. Sel. Areas Commun. , vol. 18, no. 10, pp. 2146‒2154, Oct. 2000. [CrossRef]  

17. B. Jaumard, C. Meyer, and B. Thiongane, “On column generation formulations for the RWA problem,” Discrete Appl. Math. , vol. 157, no. 6, pp. 1291‒1308, Mar. 2009. [CrossRef]  

18. C. Bron and J. Kerbosch, “Algorithm 457: finding all cliques of an undirected graph,” Commun. ACM , vol. 16, no. 9, pp. 575‒577, Sept. 1973. [CrossRef]