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

Full Article  |  PDF Article

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 .