Abstract

Wavelength division multiplexing rings are now capable of supporting more than 100 wavelengths over a single fiber. Conventional link and path formulations for the routing and wavelength assignment problem are inefficient due to the inherent symmetry in wavelength assignment and the fact that the problem size increases fast with the number of wavelengths. Although a formulation based on maximal independent sets (MIS) does not have these drawbacks, it suffers from exponential growth in the number of variables with increasing network size. We develop a new ILP (integer linear program) formulation based on the key idea of partitioning the path set and representing the MIS in the original network using the independent sets calculated in each of these partitions. This exact decomposition trades off the number of variables with the number of constraints and, as a result, achieves a much better scalability in terms of network dimension. Numerical results on ring networks of various sizes demonstrate that this new ILP decomposition achieves a decrease of several orders of magnitude in running time compared to existing formulations. Our main contribution is a novel and extremely fast technique for obtaining, in a few seconds using commodity CPUs, optimal solutions to instances of maximum size SONET rings with any number of wavelengths; such instances cannot be tackled with classical formulations without vast investments in computational resources and time.

© 2011 OSA

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 [24], 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=(N,L), where N is the set of N network nodes and 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 tsd, and T=[tsd] forms the overall network traffic matrix.

The set of all node pairs in the network is denoted as Z, i.e., Z={(i,j):i,jN,ij} and Z=|Z|. In a ring network, there are two possible paths between the members of a node pair (i,j)Z: one in the clockwise and the other in the counter-clockwise direction, represented as pij,cw and pij,ccw, respectively. The set of all paths P is the union of the set of clockwise paths (denoted by Pcw) and the set of counter-clockwise paths (denoted by Pccw), where Pk={pij,k} for k=cw,ccw, and P=|P|.

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 Ln+ (respectively, Ln), the minRWA formulation can be stated as follows:

minV
subject to
lLn+cijw,llLncijw,l=0ni,jtijn=inN,tijn=j(i,j)Z,w,
(i,j)Zcijw,l1lL,w,
(i,j)ZlLcijw,luwZLw,
Vwuww,
where cijl,w=1 if there exists a lightpath from node i to node j that uses wavelength w on link l and is 0 otherwise. uw is a binary variable which indicates whether wavelength w is used, and V is the number of wavelengths used. Expressions (1) are the multi-commodity flow equations corresponding to the routing subproblem and expression (2) is the wavelength constraint. Constraints (3) ensure that uw is 1 whenever wavelength w is used by any lightpath on any node and expression (4) sets V to the index of the largest wavelength used. In the actual implementation, we use separate constraints for the incoming and outgoing lightpaths at source and destination nodes in expression (1) to improve efficiency.

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:

minV
subject to
k=cw,ccwwcij,kw=tij(i,j)Z,
(i,j)Zk=cw,ccwcij,kwXij,kl1lL,w,
(i,j)Zk=cw,ccwcij,kwuwPw,
Vwuww,
where cij,kw is the binary decision variable indicating whether there exists a lightpath on path pij,k which uses wavelength w. The variable Xij,kl=1 if pij,k uses link l and is 0 otherwise. Expression (5) ensures that all demands are satisfied, while expression (6) is the wavelength constraint.

C. MIS Formulation

The wavelength assignment problem can be transformed into a graph multi-coloring problem by defining a new graph Gp where each node corresponds to a path in G and two nodes are connected to each other in Gp if the corresponding paths in G share a common link. The problem is then equivalent to assigning separate colors to a node in Gp 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 Gp form an independent set.

We denote the number of lightpaths on path pij,k as bij,k, and let vm be the number of wavelengths assigned to the independent set m. Let M denote the set of all MISs in Gp, which can be calculated efficiently using the Bron–Kerbosch algorithm [18]. Also, let Yij,km be the path–path set incidence function defined as

Yij,km=1,if path set m contains path pij,k,0,otherwise.

The ILP formulation can now be written as

minV
subject to
k=cw,ccwbij,k=tij(i,j)Z,
bij,kmMvmYij,km(i,j)Z,k=cw,ccw,
mMvmV.

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 Gp increases exponentially with the number of paths, which in turn increases quadratically with the number of nodes in G. Therefore, the number of variables, vm, 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 Gp. 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 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, Gp, and dividing Gp into three components; two of these are the identified independent subgraphs and the third subgraph includes the rest of the nodes in Gp. We first illustrate how the MIS decomposition (MISD) technique works for two and four partitions of the link set and then generalize it to 2x partitions. We use the notation MISD-2x to denote the ILP formulation in which the link set is partitioned into 2x 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 Gp can be divided into two disconnected components, Gpcw and Gpccw, corresponding to the sets Pcw and Pccw, respectively. Let Mcw (respectively, Mccw) denote the set of MISs in Gpcw (respectively, Gpccw). Also, we define vmk as the number of wavelengths assigned to the MIS mMk for k=cw,ccw. Then expressions (11) and (12) in the basic MIS formulation are replaced with

bij,kmMkvmkXij,km(i,j)Z,k=cw,ccw,
mMkvmkVk=cw,ccw.

Note that, for each miMcw and mjMccw, mimj is an MIS for Gp. Hence, the number of MISs in the original path graph is |M|=|Mcw|×|Mccw|. Due to the construction of sets Mcw and Mccw, this MISD-2 formulation contains a number of MIS decision variables that are equal to 2|M|. 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, Gpk(k=cw,ccw) is divided recursively into three subgraphs: Gpk,core, Gpk,0, and Gpk,1. The partitions are selected such that there are no links between the nodes in Gpk,0 and the nodes in Gpk,1. The remaining nodes are collected in the set Gpk,core. This operation is equivalent to partitioning the path set Pk into three subsets, where none of the paths in Pk,0 intersect with any of the paths in Pk,1. Also, Pk,core includes the remaining paths in Pk, which may intersect with the paths in Pk,0 and/or Pk,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 Lcw (respectively, Lccw), the link set can be divided into four sets: two sets, Lcw,0 and Lccw,0, containing the links in Lcw and Lccw, respectively, among nodes {1,,N/2}, and two sets, Lcw,1 and Lccw,1, containing the links in Lcw and Lccw, respectively, among nodes {N/2+1,,N}. Accordingly, the path set can be divided into six sets:

  • Pk,0Pk(k=cw,ccw) is defined as the set of paths that use only links in Lk,0,
  • Pk,1Pk(k=cw,ccw) is defined as the set of paths that use only the links in Lk,1,
  • Pk,corePk(k=cw,ccw) consists of the paths that use links from both Lk,0 and Lk,1.

This partition results in four independent path sets, namely, Pcw,0, Pcw,1, Pccw,0, and Pccw,1; hence we refer to the resulting formulation as MISD-4.

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

Finally, for each core set qQk, the maximal sets of nodes in Gpk,r which are independent from each other and the nodes in q, Mqk,r, are calculated for k=cw,ccw,r=0,1. With these definitions, for each qQk and miMqk,0 and mjMqk,1, miqmj corresponds to an MIS in Gpk.

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

bij,kqQkvqk,coreXij,kqpij,kPk,core,k=cw,ccw,
bij,kqQkmMqk,rvq,mk,rXij,kmpij,kPk,r,k=cw,ccw,r=0,1,
qQkvqk,coreVk=cw,ccw,
mMqk,rvq,mk,r=vqk,coreqQk,r=0,1.
In this formulation, vqk,core is the number of wavelengths assigned to the core set qQk and vq,mk,r denotes the number of wavelengths assigned to the set mMqk,r. Expressions (15) and (16) ensure that each set is assigned a sufficient number of wavelengths that the number of wavelengths on each path is greater than or equal to the number of lightpaths on that path. Expression (17) sets V to the number of wavelengths used, while constraints (18) ensure consistency between wavelength assignments in different path partitions.

This decomposition approach can be further extended to develop formulations with 8 (MISD-8), 16 (MISD-16), or, in general, 2x independent path sets (MISD-2x). In this generalized MISD formulation, the ring topology (i.e., the link set) is partitioned in half recursively, resulting in more subgraphs in Gp but a smaller number of total independent sets in all subgraphs. The details of the general decomposition, MISD-2x, 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 | PPT Slide | PDF

MIS Formulation. The basic algorithm calculates the set of MISs, M, using the whole set of paths, 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 Pcw={12,23,34,41,123,234,341,412,1234,2341,3412,4123}, and the set of counter-clockwise paths is Pccw={14,43,32,21,143,432,321,214,1432,4321,3214,2143}. Then, the MISs in Pcw and Pccw are calculated as follows: Mcw={{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}},Mccw={{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 Mcw and Mccw (each of size 11) is equal to the set 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 | PPT Slide | PDF

  • Pcw,0={34,41,341}: the set of paths that use only the first two clockwise links, links 34 and 41, shown as partition 0 in Fig. 2.
  • Pcw,1={12,23,123}: the set of paths that use only the other two clockwise links, links 12 and 23, shown as partition 1 in Fig. 2.
  • Pcw,core={412,231,1234,2341,3412,4123}: the remaining set of paths that use any of the four clockwise links, shown as the core partition in Fig. 2.

 

Fig. 3 Path graph Gpcw for clockwise paths in a four-node ring network.

Download Full Size | PPT Slide | PDF

The next step is to include the paths into the path graph Gpcw, as shown in Fig. 3. No two paths in Gpcw,0 and Gpcw,1 share a common link. Then, the set of core sets for the clockwise paths, Qcw, is calculated in Gpcw,core as follows:

  • • Initialize Qcw to the MIS set of Gpcw,core: Qcw={{3412},{2341},{1234},{4123},{412,234}}.
  • • For q={412,234}, path 234 intersects with path 123, but path 412 does not intersect with path 123; hence, set {412} is added to Qcw.
  • • For q={412,234}, path 412 intersects with path 41, but path 234 does not intersect with path 41; hence, set {234} is added to Qcw.
  • • 0 is added to Qcw.

As a result, Qcw={{3412},{2341},{1234},0,{412,234},{412},{234}}. Then, for each qQcw, Mqcw,0 and Mqcw,1 are obtained as in Fig. 4. Comparing with the set Mcw obtained above for MISD-2, we observe that, for each qQcw, miMqcw,0 and mjMqcw,1, miqmj is an MIS in graph Gpcw corresponding to set Pcw. For instance, the top left part of Fig. 4 shows that, for q1={3412}, M1cw,0=0 as q1 intersects with links 34 and 41, while M1cw,1={23} as q1 intersects only with link 12; the union of these three sets, i.e., {3412,23} is an MIS for Gpcw. The sets Qccw, Mqccw,0, and Mqccw,1 are similarly obtained for the counter-clockwise paths.

 

Fig. 4 Representation of MISs in Gpcw by the MISs in Gpcw,0 and Gpcw,1 and core sets in Gpcore.

Download Full Size | PPT Slide | PDF

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

 

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

Download Full Size | PPT Slide | PDF

In Fig. 5 we plot the number of independent sets in the basic MIS formulation, as well as the MISD-2, MISD-4, and MISD-8 formulations, using a logarithmic y-axis, against the number N of ring nodes. We observe that the number of independent sets in MISD-2 is just the square root of the corresponding number in the basic MIS formulation. This is due to the fact that the path graph for a ring network is composed of two disconnected subgraphs, and, as we observed earlier, |M|=|Mcw|×|Mccw|. We also note that the MISD-4 and MISD-8 formulations achieve a further significant reduction in the number of MISs. For instance, on a 16-node (respectively, 32-node) ring network, the number of MISs in MISD-8 is more than one order (respectively, about four orders) of magnitude smaller than in MISD-2. This decrease in MIS size comes at the expense of additional constraints (i.e., those corresponding to expression (18)), the number of which is equal to the total number of core sets. However, the number of additional constraints is low relative to the great reduction in the number of independent sets. As an example, for a 16-node ring, the number of core sets in the MISD-4 formulation is just 953. In other words, by adding a small number of constraints, MISD successfully eliminates a large number of variables in the MILP formulation.

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,,24), the number W of wavelengths per link (W=10,20,,160), and the traffic demands tsd (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,Tmax], where Tmax is the maximum traffic demand. Figure 6(a) presents results with Tmax=3 while Fig. 6(b) shows results for Tmax=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 | PPT Slide | PDF

The results in Fig. 6(a) (Tmax=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 N16, 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 N18 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 Tmax=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 Tmax, 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,Tmax]. 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 Tmax;N=16.

Download Full Size | PPT Slide | 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 Nmax that can be solved with each minRWA formulation for a given number W of wavelengths, within 3000 s of CPU time.

Download Full Size | PPT Slide | 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 2x Independent Sets: MISD-2x

 

Fig. 9 Path graph of MISD-2x.

Download Full Size | PPT Slide | 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 2z2N. 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 24 link sets (for each directional ring) comprising a single link; hence the constraint 2zN.

Consider now the MISD-2x formulation, xz, and let Lk(k=cw,ccw) denote the link sets of the clockwise and counter-clockwise rings, respectively. In effecting the xth decomposition, each of these link sets is divided into 2x1 sets: Lk,1,,Lk,2x1. Accordingly, the path sets Pk(k=cw,ccw) are partitioned into 2x1 sets following a tree topology with x levels (refer to Fig. 9):

  • Pk,2x1,,Pk,2x1, the lowest levels of path partitions, consist of paths containing only links within each link set Lk,s(s=1,,2x1);
  • Pk,2x2,,Pk,2x11, the second-lowest levels of path partitions, include paths containing only links from the two adjacent path partitions Lk,2s1 and Lk,2s(s=1,,2x2);
  • ;
  • Pk,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-2x approach (without loss of generality, only the clockwise subgraph is presented). Gpcw,s(s=1,,2x1) denotes the subgraph corresponding to path set Pcw,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, Gpk,2x1,,Gpk,2x1, are mutually independent. The only connections among the subgraphs are between the child subgraphs and parent subgraphs. Therefore, an MIS in Gpcw 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 mcw in Gpcw is represented by the union of an MIS mcw,2 in Gpcw,2, a core set qcw,1 in Gpcw,1, and an MIS mcw,3 in Gpcw,3, i.e., mcw=mcw,2qcw,1mcw,3. Recursively, the MIS mcw,2 is equal to the union of mcw,4 in Gpcw,4, core set qcw,2 in Gpcw,2, and mcw,5 in Gpcw,5, i.e., mcw,2=mcw,4qcw,2mcw,5. Similarly, we have that mcw,3=mcw,6qcw,3mcw,7. As shown in Fig. 10, these substitutions result in mcw=(mcw,4qcw,2mcw,5)qcw,1(mcw,6qcw,3mcw,7). This substitution process continues recursively until it reaches the leaf subgraph in the path graph tree. Therefore, an MIS in Gpcw will be represented by the union of MISs in the leaf subgraphs and core sets in non-leaf subgraphs, i.e., mk=s=12x11qk,ss=2x12x1mk,s(k=cw,ccw).

 

Fig. 10 MIS Representation in MISD-2x.

Download Full Size | PPT Slide | PDF

To describe the exact MISD-2x formulation we introduce additional notation. We define qk,r as the core sets in the non-leaf subgraph Gpk,r(k=cw,ccw,r=1,,2x11) and define mk,r as MISs in the leaf subgraph Gpk,r,(k=cw,ccw,r=2x1,,2x1). To include the network topology in the formulation, we define Xij,kqk,r as a binary variable that indicates whether pij,kqk,r and define Xij,kmk,r as a binary variable that indicates whether pij,kmk,r. We also let Mk,rqk,r be the set of MISs in the leaf subgraph Gpk,r that corresponds to core set qk,r and let Qk,rqk,r be the set of core sets in the non-leaf subgraph Gpk,r that corresponds to core set qk,r.

The two sets of decision variables in the formulation are

  • Vqk,r: number of wavelengths assigned to core set qk,r; and
  • Vmk,r: number of wavelengths assigned to MIS mk,r.

The MISD-2x 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 x1 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:

bij,kqk,1Qk,1Vqk,1Xij,kqk,1pijGpk,1,k=cw,ccw,
bij,kqk,1Qk,1qk,rQk,rqk,1Vqk,rXij,kqk,rpijGpk,r,k=cw,ccwr=2,3,
bij,kqk,1Qk,r1qk,r2Qk,r2qk,1qk,rs1Qk,rs1qk,rs2mk,rsMk,rsqk,rs1Vmk,rsXij,kmk,rspij,kGpk,rs,s=x,2x1rs2x1,rs1=rs2,rs2=rk12,,r1=r22=1,k=cw,ccw,
qk,rQk,rqk,1Vqk,r=Vqk,1k=cw,ccwr=2,3,
mk,rsMk,rsqk,rs1Vmk,rs=Vqk,rs1s=x,2x1rs2x1,rs1=rs2k=cw,ccw,
VqQkvqk,1k=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]  

References

  • View by:
  • |
  • |
  • |

  1. J. M. Simmons, Optical Network Design and Planning, Springer, 2008.
  2. R. Dutta, A. E. Kamal, and G. N. Rouskas, ed., 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 16, (6), 46‒56 (2002).
    [CrossRef]
  4. K. Zhu and B. Mukherjee, "Traffic grooming in an optical WDM mesh network," IEEE J. Sel. Areas Commun. 20, (1), 122‒133 (2002).
    [CrossRef]
  5. S. Ramamurthy, L. Sahasrabuddhe, and B. Mukherjee, "Survivable WDM mesh networks," J. Lightwave Technol. 21, (4), 870‒883 (2003).
    [CrossRef]
  6. S. Ramamurthy and B. Mukherjee, "Survivable WDM mesh networks, part I—protection," 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. 21, (8), 1231‒1240 (2003).
    [CrossRef]
  8. W. Su and G. Sasaki, "Scheduling periodic transfers with flexibility," Proc. of 41st Allerton Conf., Oct. 2003.
  9. B. Jaumard, C. Meyer, and B. Thiongane, "ILP formulations and optimal solutions for the RWA problem," Proc. of IEEE GLOBECOM’04, Vol. 3, Nov. 29–Dec. 3 2004, pp. 1918‒1924.
  10. I. Chlamtac, A. Ganz, and G. Karmi, "Lightpath communications: an approach to high bandwidth optical WANS," IEEE Trans. Commun. 40, (7), 1171‒1182 (1992).
    [CrossRef]
  11. R. Dutta and G. N. Rouskas, "A survey of virtual topology design algorithms for wavelength routed optical networks," Opt. Networks Mag. 1, (1), 73‒89 (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. 1, (1), 47‒60 (2000).
  13. R. M. Krishnaswamy and K. N. Sivarajan, "Algorithms for routing and wavelength assignment based on solutions of LP-relaxations," IEEE Commun. Lett. 5, (10), 435‒437 (2001).
    [CrossRef]
  14. R. Ramaswami and K. Sivarajan, "Routing and wavelength assignment in all-optical networks," IEEE/ACM Trans. Netw. 3, (5), 489‒500 (1995).
    [CrossRef]
  15. A. Mehrotra and M. Trick, "A column generation approach for graph coloring," INFORMS J. Comput. 8, (4), 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. 18, (10), 2146‒2154 (2000).
    [CrossRef]
  17. B. Jaumard, C. Meyer, and B. Thiongane, "On column generation formulations for the RWA problem," Discrete Appl. Math. 157, (6), 1291‒1308 (2009).
    [CrossRef]
  18. C. Bron and J. Kerbosch, "Algorithm 457: finding all cliques of an undirected graph," Commun. ACM 16, (9), 575‒577 (1973).
    [CrossRef]

2009 (1)

B. Jaumard, C. Meyer, and B. Thiongane, "On column generation formulations for the RWA problem," Discrete Appl. Math. 157, (6), 1291‒1308 (2009).
[CrossRef]

2003 (2)

S. Ramamurthy, L. Sahasrabuddhe, and B. Mukherjee, "Survivable WDM mesh networks," J. Lightwave Technol. 21, (4), 870‒883 (2003).
[CrossRef]

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. 21, (8), 1231‒1240 (2003).
[CrossRef]

2002 (2)

R. Dutta and G. N. Rouskas, "Traffic grooming in WDM networks: past and future," IEEE Network 16, (6), 46‒56 (2002).
[CrossRef]

K. Zhu and B. Mukherjee, "Traffic grooming in an optical WDM mesh network," IEEE J. Sel. Areas Commun. 20, (1), 122‒133 (2002).
[CrossRef]

2001 (1)

R. M. Krishnaswamy and K. N. Sivarajan, "Algorithms for routing and wavelength assignment based on solutions of LP-relaxations," IEEE Commun. Lett. 5, (10), 435‒437 (2001).
[CrossRef]

2000 (3)

R. Dutta and G. N. Rouskas, "A survey of virtual topology design algorithms for wavelength routed optical networks," Opt. Networks Mag. 1, (1), 73‒89 (2000).

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. 1, (1), 47‒60 (2000).

T. Lee, K. Lee, and S. Park, "Optimal routing and wavelength assignment in WDM ring networks," IEEE J. Sel. Areas Commun. 18, (10), 2146‒2154 (2000).
[CrossRef]

1996 (1)

A. Mehrotra and M. Trick, "A column generation approach for graph coloring," INFORMS J. Comput. 8, (4), 344‒354 (1996).
[CrossRef]

1995 (1)

R. Ramaswami and K. Sivarajan, "Routing and wavelength assignment in all-optical networks," IEEE/ACM Trans. Netw. 3, (5), 489‒500 (1995).
[CrossRef]

1992 (1)

I. Chlamtac, A. Ganz, and G. Karmi, "Lightpath communications: an approach to high bandwidth optical WANS," IEEE Trans. Commun. 40, (7), 1171‒1182 (1992).
[CrossRef]

1973 (1)

C. Bron and J. Kerbosch, "Algorithm 457: finding all cliques of an undirected graph," Commun. ACM 16, (9), 575‒577 (1973).
[CrossRef]

Bron, C.

C. Bron and J. Kerbosch, "Algorithm 457: finding all cliques of an undirected graph," Commun. ACM 16, (9), 575‒577 (1973).
[CrossRef]

Chlamtac, I.

I. Chlamtac, A. Ganz, and G. Karmi, "Lightpath communications: an approach to high bandwidth optical WANS," IEEE Trans. Commun. 40, (7), 1171‒1182 (1992).
[CrossRef]

Dotaro, E.

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. 21, (8), 1231‒1240 (2003).
[CrossRef]

Douville, R.

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. 21, (8), 1231‒1240 (2003).
[CrossRef]

Dutta, R.

R. Dutta and G. N. Rouskas, "Traffic grooming in WDM networks: past and future," IEEE Network 16, (6), 46‒56 (2002).
[CrossRef]

R. Dutta and G. N. Rouskas, "A survey of virtual topology design algorithms for wavelength routed optical networks," Opt. Networks Mag. 1, (1), 73‒89 (2000).

Gagnaire, M.

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. 21, (8), 1231‒1240 (2003).
[CrossRef]

Ganz, A.

I. Chlamtac, A. Ganz, and G. Karmi, "Lightpath communications: an approach to high bandwidth optical WANS," IEEE Trans. Commun. 40, (7), 1171‒1182 (1992).
[CrossRef]

Jaumard, B.

B. Jaumard, C. Meyer, and B. Thiongane, "On column generation formulations for the RWA problem," Discrete Appl. Math. 157, (6), 1291‒1308 (2009).
[CrossRef]

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

Jue, J. P.

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. 1, (1), 47‒60 (2000).

Karmi, G.

I. Chlamtac, A. Ganz, and G. Karmi, "Lightpath communications: an approach to high bandwidth optical WANS," IEEE Trans. Commun. 40, (7), 1171‒1182 (1992).
[CrossRef]

Kerbosch, J.

C. Bron and J. Kerbosch, "Algorithm 457: finding all cliques of an undirected graph," Commun. ACM 16, (9), 575‒577 (1973).
[CrossRef]

Krishnaswamy, R. M.

R. M. Krishnaswamy and K. N. Sivarajan, "Algorithms for routing and wavelength assignment based on solutions of LP-relaxations," IEEE Commun. Lett. 5, (10), 435‒437 (2001).
[CrossRef]

Kuri, J.

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. 21, (8), 1231‒1240 (2003).
[CrossRef]

Lee, K.

T. Lee, K. Lee, and S. Park, "Optimal routing and wavelength assignment in WDM ring networks," IEEE J. Sel. Areas Commun. 18, (10), 2146‒2154 (2000).
[CrossRef]

Lee, T.

T. Lee, K. Lee, and S. Park, "Optimal routing and wavelength assignment in WDM ring networks," IEEE J. Sel. Areas Commun. 18, (10), 2146‒2154 (2000).
[CrossRef]

Mehrotra, A.

A. Mehrotra and M. Trick, "A column generation approach for graph coloring," INFORMS J. Comput. 8, (4), 344‒354 (1996).
[CrossRef]

Meyer, C.

B. Jaumard, C. Meyer, and B. Thiongane, "On column generation formulations for the RWA problem," Discrete Appl. Math. 157, (6), 1291‒1308 (2009).
[CrossRef]

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

Mukherjee, B.

S. Ramamurthy, L. Sahasrabuddhe, and B. Mukherjee, "Survivable WDM mesh networks," J. Lightwave Technol. 21, (4), 870‒883 (2003).
[CrossRef]

K. Zhu and B. Mukherjee, "Traffic grooming in an optical WDM mesh network," IEEE J. Sel. Areas Commun. 20, (1), 122‒133 (2002).
[CrossRef]

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. 1, (1), 47‒60 (2000).

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

Park, S.

T. Lee, K. Lee, and S. Park, "Optimal routing and wavelength assignment in WDM ring networks," IEEE J. Sel. Areas Commun. 18, (10), 2146‒2154 (2000).
[CrossRef]

Puech, N.

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. 21, (8), 1231‒1240 (2003).
[CrossRef]

Ramamurthy, S.

S. Ramamurthy, L. Sahasrabuddhe, and B. Mukherjee, "Survivable WDM mesh networks," J. Lightwave Technol. 21, (4), 870‒883 (2003).
[CrossRef]

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

Ramaswami, R.

R. Ramaswami and K. Sivarajan, "Routing and wavelength assignment in all-optical networks," IEEE/ACM Trans. Netw. 3, (5), 489‒500 (1995).
[CrossRef]

Rouskas, G. N.

R. Dutta and G. N. Rouskas, "Traffic grooming in WDM networks: past and future," IEEE Network 16, (6), 46‒56 (2002).
[CrossRef]

R. Dutta and G. N. Rouskas, "A survey of virtual topology design algorithms for wavelength routed optical networks," Opt. Networks Mag. 1, (1), 73‒89 (2000).

Sahasrabuddhe, L.

Sasaki, G.

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

Simmons, J. M.

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

Sivarajan, K.

R. Ramaswami and K. Sivarajan, "Routing and wavelength assignment in all-optical networks," IEEE/ACM Trans. Netw. 3, (5), 489‒500 (1995).
[CrossRef]

Sivarajan, K. N.

R. M. Krishnaswamy and K. N. Sivarajan, "Algorithms for routing and wavelength assignment based on solutions of LP-relaxations," IEEE Commun. Lett. 5, (10), 435‒437 (2001).
[CrossRef]

Su, W.

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

Thiongane, B.

B. Jaumard, C. Meyer, and B. Thiongane, "On column generation formulations for the RWA problem," Discrete Appl. Math. 157, (6), 1291‒1308 (2009).
[CrossRef]

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

Trick, M.

A. Mehrotra and M. Trick, "A column generation approach for graph coloring," INFORMS J. Comput. 8, (4), 344‒354 (1996).
[CrossRef]

Zang, H.

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. 1, (1), 47‒60 (2000).

Zhu, K.

K. Zhu and B. Mukherjee, "Traffic grooming in an optical WDM mesh network," IEEE J. Sel. Areas Commun. 20, (1), 122‒133 (2002).
[CrossRef]

Commun. ACM (1)

C. Bron and J. Kerbosch, "Algorithm 457: finding all cliques of an undirected graph," Commun. ACM 16, (9), 575‒577 (1973).
[CrossRef]

Discrete Appl. Math. (1)

B. Jaumard, C. Meyer, and B. Thiongane, "On column generation formulations for the RWA problem," Discrete Appl. Math. 157, (6), 1291‒1308 (2009).
[CrossRef]

IEEE Commun. Lett. (1)

R. M. Krishnaswamy and K. N. Sivarajan, "Algorithms for routing and wavelength assignment based on solutions of LP-relaxations," IEEE Commun. Lett. 5, (10), 435‒437 (2001).
[CrossRef]

IEEE J. Sel. Areas Commun. (3)

T. Lee, K. Lee, and S. Park, "Optimal routing and wavelength assignment in WDM ring networks," IEEE J. Sel. Areas Commun. 18, (10), 2146‒2154 (2000).
[CrossRef]

K. Zhu and B. Mukherjee, "Traffic grooming in an optical WDM mesh network," IEEE J. Sel. Areas Commun. 20, (1), 122‒133 (2002).
[CrossRef]

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. 21, (8), 1231‒1240 (2003).
[CrossRef]

IEEE Network (1)

R. Dutta and G. N. Rouskas, "Traffic grooming in WDM networks: past and future," IEEE Network 16, (6), 46‒56 (2002).
[CrossRef]

IEEE Trans. Commun. (1)

I. Chlamtac, A. Ganz, and G. Karmi, "Lightpath communications: an approach to high bandwidth optical WANS," IEEE Trans. Commun. 40, (7), 1171‒1182 (1992).
[CrossRef]

IEEE/ACM Trans. Netw. (1)

R. Ramaswami and K. Sivarajan, "Routing and wavelength assignment in all-optical networks," IEEE/ACM Trans. Netw. 3, (5), 489‒500 (1995).
[CrossRef]

INFORMS J. Comput. (1)

A. Mehrotra and M. Trick, "A column generation approach for graph coloring," INFORMS J. Comput. 8, (4), 344‒354 (1996).
[CrossRef]

J. Lightwave Technol. (1)

Opt. Networks Mag. (2)

R. Dutta and G. N. Rouskas, "A survey of virtual topology design algorithms for wavelength routed optical networks," Opt. Networks Mag. 1, (1), 73‒89 (2000).

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. 1, (1), 47‒60 (2000).

Other (5)

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

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

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

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

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

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (10)

Fig. 1
Fig. 1

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

Fig. 2
Fig. 2

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

Fig. 3
Fig. 3

Path graph G p c w for clockwise paths in a four-node ring network.

Fig. 4
Fig. 4

Representation of MISs in G p c w by the MISs in G p c w , 0 and G p c w , 1 and core sets in G p c o r e .

Fig. 5
Fig. 5

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

Fig. 6
Fig. 6

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

Fig. 7
Fig. 7

(Color online) Solution times as a function of T max ; N = 16 .

Fig. 8
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.

Fig. 9
Fig. 9

Path graph of MISD- 2 x .

Fig. 10
Fig. 10

MIS Representation in MISD- 2 x .

Equations (27)

Equations on this page are rendered with MathJax. Learn more.

min V
l L n + c i j w , l l L n c i j w , l = 0 n i , j t i j n = i n N , t i j n = j ( i , j ) Z , w ,
( i , j ) Z c i j w , l 1 l L , w ,
( i , j ) Z l L c i j w , l u w Z L w ,
V w u w w ,
min V
k = c w , c c w w c i j , k w = t i j ( i , j ) Z ,
( i , j ) Z k = c w , c c w c i j , k w X i j , k l 1 l L , w ,
( i , j ) Z k = c w , c c w c i j , k w u w P w ,
V w u w w ,
Y i j , k m = 1 , if path set  m  contains path  p i j , k , 0 , otherwise.
min V
k = c w , c c w b i j , k = t i j ( i , j ) Z ,
b i j , k m M v m Y i j , k m ( i , j ) Z , k = c w , c c w ,
m M v m V .
b i j , k m M k v m k X i j , k m ( i , j ) Z , k = c w , c c w ,
m M k v m k V k = c w , c c w .
b i j , k q Q k v q k , c o r e X i j , k q p i j , k P k , c o r e , k = c w , c c w ,
b i j , k q Q k m M q k , r v q , m k , r X i j , k m p i j , k P k , r , k = c w , c c w , r = 0 , 1 ,
q Q k v q k , c o r e V k = c w , c c w ,
m M q k , r v q , m k , r = v q k , c o r e q Q k , r = 0 , 1 .
b i j , k q k , 1 Q k , 1 V q k , 1 X i j , k q k , 1 p i j G p k , 1 , k = c w , c c w ,
b i j , k q k , 1 Q k , 1 q k , r Q k , r q k , 1 V q k , r X i j , k q k , r p i j G p k , r , k = c w , c c w r = 2 , 3 ,
b i j , k q k , 1 Q k , r 1 q k , r 2 Q k , r 2 q k , 1 q k , r s 1 Q k , r s 1 q k , r s 2 m k , r s M k , r s q k , r s 1 V m k , r s X i j , k m k , r s p i j , k G p k , r s , s = x , 2 x 1 r s 2 x 1 , r s 1 = r s 2 , r s 2 = r k 1 2 , , r 1 = r 2 2 = 1 , k = c w , c c w ,
q k , r Q k , r q k , 1 V q k , r = V q k , 1 k = c w , c c w r = 2 , 3 ,
m k , r s M k , r s q k , r s 1 V m k , r s = V q k , r s 1 s = x , 2 x 1 r s 2 x 1 , r s 1 = r s 2 k = c w , c c w ,
V q Q k v q k , 1 k = c w , c c w .