OSA's Digital Library

Journal of Optical Communications and Networking

Journal of Optical Communications and Networking

  • Editors: K. Bergman and V. Chan
  • Vol. 3, Iss. 7 — Jul. 1, 2011
  • pp: 577–586
« Show journal navigation

Fast Exact ILP Decompositions for Ring RWA

Emre Yetginer, Zeyu Liu, and George N. Rouskas  »View Author Affiliations


Journal of Optical Communications and Networking, Vol. 3, Issue 7, pp. 577-586 (2011)
http://dx.doi.org/10.1364/JOCN.3.000577


View Full Text Article

Acrobat PDF (540 KB)





Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

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

In offline RWA [9

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.

], 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

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, July1992. [CrossRef]

], 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

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

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.

].

An alternative formulation was developed in [14

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]

] 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

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]

] 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

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]

], 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

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

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]

]. 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

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]

] 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.

II. Notation and Existing RWA Formulations

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

A. Link Formulation

B. Path Formulation

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

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]

]. 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.
(9)

The ILP formulation can now be written as
minV
subject to
k=cw,ccwbij,k=tij(i,j)Z,
(10)
bij,kmMvmYij,km(i,j)Z,k=cw,ccw,
(11)
mMvmV.
(12)

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.

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

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,
(13)
mMkvmkVk=cw,ccw.
(14)

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

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,
(15)
bij,kqQkmMqk,rvq,mk,rXij,kmpij,kPk,r,k=cw,ccw,r=0,1,
(16)
qQkvqk,coreVk=cw,ccw,
(17)
mMqk,rvq,mk,r=vqk,coreqQk,r=0,1.
(18)
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.

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.

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. 3 Path graph Gpcw for clockwise paths in a four-node ring network.

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

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

Fig. 5 (Color online) Comparison of formulations in terms of MIS decision variables.
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.

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.

Fig. 7 (Color online) Solution times as a function of Tmax;N=16.

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.

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

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.

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,
(19)
bij,kqk,1Qk,1qk,rQk,rqk,1Vqk,rXij,kqk,rpijGpk,r,k=cw,ccwr=2,3,
(20)
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,
(21)
qk,rQk,rqk,1Vqk,r=Vqk,1k=cw,ccwr=2,3,
(22)
mk,rsMk,rsqk,rs1Vmk,rs=Vqk,rs1s=x,2x1rs2x1,rs1=rs2k=cw,ccw,
(23)
VqQkvqk,1k=cw,ccw.
(24)

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, July1992. [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]

OCIS Codes
(060.4250) Fiber optics and optical communications : Networks
(060.4251) Fiber optics and optical communications : Networks, assignment and routing algorithms

ToC Category:
Research Papers

History
Original Manuscript: January 31, 2011
Revised Manuscript: June 13, 2011
Manuscript Accepted: June 15, 2011
Published: June 27, 2011

Virtual Issues
September 27, 2011 Spotlight on Optics

Citation
Emre Yetginer, Zeyu Liu, and George N. Rouskas, "Fast Exact ILP Decompositions for Ring RWA," J. Opt. Commun. Netw. 3, 577-586 (2011)
http://www.opticsinfobase.org/jocn/abstract.cfm?URI=jocn-3-7-577


Sort:  Author  |  Year  |  Journal  |  Reset  

References

  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]

Cited By

Alert me when this paper is cited

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited