Abstract

We consider the traffic grooming problem, a fundamental network design problem in optical networks. We review a typical integer linear program formulation considered in the literature, and we identify two challenges related to this formulation in terms of scalability and wavelength fragmentation. We then propose a new (to our knowledge) solution approach that decomposes the traffic grooming problem into two subproblems that are solved sequentially: 1) the virtual topology and traffic routing (VTTR) subproblem, which does not take into account physical topology constraints, and 2) the routing and wavelength assignment subproblem, which reconciles the virtual topology determined by VTTR with the physical topology. The decomposition is exact when the network is not wavelength limited. We also propose an algorithm that uses a partial linear programming relaxation technique driven by lightpath utilization information to solve the VTTR subproblem efficiently. Our approach delivers a desirable tradeoff between running time and quality of the final solution.

© 2013 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. F. Farahmand, X. Huang, and J. P. Jue, “Efficient online traffic grooming algorithms in WDM mesh networks with drop-and-continue node architecture,” in Proc. Broadnets, Oct. 2004, pp. 180–189.
  2. J. Q. Hu and B. Leida, “Traffic grooming, routing, and wavelength assignment in optical WDM mesh networks,” in Proc. IEEE INFOCOM, Mar. 2004, pp. 495–501.
  3. S. Huang and R. Dutta, “Research problems in dynamic traffic grooming in optical networks,” in Proc. First Workshop on Traffic Grooming, Apr. 2004.
  4. H. Zhu, H. Zang, K. Zhu, and B. Mukherjee, “A novel generic graph model for traffic grooming in heterogeneous WDM mesh networks,” IEEE/ACM Trans. Netw., vol.  11, no. 2, pp. 285–299, Apr. 2003.
    [CrossRef]
  5. S. Huang, R. Dutta, and G. N. Rouskas, “Traffic grooming in path, star, and tree networks: Complexity, bounds, and algorithms,” IEEE J. Sel. Areas Commun., vol.  24, no. 4, pp. 66–82, Apr. 2006.
    [CrossRef]
  6. 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.
  7. 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]
  8. A. L. Chiu and E. Modiano, “Traffic grooming algorithms for reducing electronic multiplexing costs in WDM ring networks,” J. Lightwave Technol., vol.  18, no. 1, pp. 2–12, Jan. 2000.
    [CrossRef]
  9. V. R. Konda and T. Y. Chow, “Algorithm for traffic grooming in optical networks to minimize the number of transceivers,” in IEEE Workshop on High Performance Switching and Routing, 2001, pp. 218–221.
  10. R. Dutta and G. N. Rouskas, “On optimal traffic grooming in WDM rings,” IEEE J. Sel. Areas Commun., vol.  20, no. 1, pp. 110–121, Jan. 2002.
    [CrossRef]
  11. E. Yetginer and G. N. Rouskas, “Power efficient traffic grooming in optical WDM networks,” in Proc. IEEE GLOBECOM, Dec. 2009.
  12. B. Chen, G. N. Rouskas, and R. Dutta, “On hierarchical traffic grooming in WDM networks,” IEEE/ACM Trans. Netw., vol.  16, no. 5, pp. 1226–1238, Oct. 2008.
    [CrossRef]
  13. K. Zhu and B. Mukherjee, “A review of traffic grooming in WDM optical networks: Architectures and challenges,” Opt. Netw. Mag., vol.  4, no. 2, pp. 55–64, Mar./Apr. 2003.
  14. W. Yao, G. Sahin, M. Li, and B. Ramamurthy, “Analysis of multi-hop traffic grooming in WDM mesh networks,” in Proc. Broadnets, Boston, MA, Oct. 2005, pp. 165–174.
  15. X. Munoz and I. Sau, “Traffic grooming in unidirectional WDM rings with bounded degree request graph,” in Graph-Theoretic Concepts in Computer Science (Lecture Notes in Computer Science, Vol. 5344). Springer, 2008, pp. 300–311.
  16. M. Dawande, R. Gupta, S. Naranpanawe, and C. Sriskandarajah, “A traffic-grooming algorithm in wavelength-routed optical networks,” INFORMS J. Comput., vol.  19, no. 4, pp. 565–574, 2007.
    [CrossRef]
  17. B. Vignac, B. Jaumard, and F. Vanderbeck, “A hierarchical optimization approach to optical network design where traffic grooming and routing is solved by column generation,” in Proc. INOC, Apr. 2009.
  18. J.-F. P. Labourdette and A. S. Acampora, “Logically rearrangeable multihop lightwave networks,” IEEE Trans. Commun., vol.  39, no. 8, pp. 1223–1230, Aug. 1991.
    [CrossRef]
  19. E. Yetginer, Z. Liu, and G. N. Rouskas, “Fast exact ILP decompositions for ring RWA,” J. Opt. Commun. Netw., vol.  3, no. 7, pp. 577–586, July 2011.
    [CrossRef]
  20. Z. Liu and G. N. Rouskas, “A fast path-based ILP formulation for offline RWA in mesh optical networks,” in Proc. IEEE GLOBECOM, Dec. 2012.
  21. Z. Liu and G. N. Rouskas, “Link selection algorithms for link-based ILPs and applications to RWA in mesh networks,” in Proc. ONDM, Apr. 2013.

2011 (1)

2008 (1)

B. Chen, G. N. Rouskas, and R. Dutta, “On hierarchical traffic grooming in WDM networks,” IEEE/ACM Trans. Netw., vol.  16, no. 5, pp. 1226–1238, Oct. 2008.
[CrossRef]

2007 (1)

M. Dawande, R. Gupta, S. Naranpanawe, and C. Sriskandarajah, “A traffic-grooming algorithm in wavelength-routed optical networks,” INFORMS J. Comput., vol.  19, no. 4, pp. 565–574, 2007.
[CrossRef]

2006 (1)

S. Huang, R. Dutta, and G. N. Rouskas, “Traffic grooming in path, star, and tree networks: Complexity, bounds, and algorithms,” IEEE J. Sel. Areas Commun., vol.  24, no. 4, pp. 66–82, Apr. 2006.
[CrossRef]

2003 (2)

K. Zhu and B. Mukherjee, “A review of traffic grooming in WDM optical networks: Architectures and challenges,” Opt. Netw. Mag., vol.  4, no. 2, pp. 55–64, Mar./Apr. 2003.

H. Zhu, H. Zang, K. Zhu, and B. Mukherjee, “A novel generic graph model for traffic grooming in heterogeneous WDM mesh networks,” IEEE/ACM Trans. Netw., vol.  11, no. 2, pp. 285–299, Apr. 2003.
[CrossRef]

2002 (3)

R. Dutta and G. N. Rouskas, “On optimal traffic grooming in WDM rings,” IEEE J. Sel. Areas Commun., vol.  20, no. 1, pp. 110–121, Jan. 2002.
[CrossRef]

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.

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]

2000 (1)

1991 (1)

J.-F. P. Labourdette and A. S. Acampora, “Logically rearrangeable multihop lightwave networks,” IEEE Trans. Commun., vol.  39, no. 8, pp. 1223–1230, Aug. 1991.
[CrossRef]

Acampora, A. S.

J.-F. P. Labourdette and A. S. Acampora, “Logically rearrangeable multihop lightwave networks,” IEEE Trans. Commun., vol.  39, no. 8, pp. 1223–1230, Aug. 1991.
[CrossRef]

Chen, B.

B. Chen, G. N. Rouskas, and R. Dutta, “On hierarchical traffic grooming in WDM networks,” IEEE/ACM Trans. Netw., vol.  16, no. 5, pp. 1226–1238, Oct. 2008.
[CrossRef]

Chiu, A. L.

Chow, T. Y.

V. R. Konda and T. Y. Chow, “Algorithm for traffic grooming in optical networks to minimize the number of transceivers,” in IEEE Workshop on High Performance Switching and Routing, 2001, pp. 218–221.

Dawande, M.

M. Dawande, R. Gupta, S. Naranpanawe, and C. Sriskandarajah, “A traffic-grooming algorithm in wavelength-routed optical networks,” INFORMS J. Comput., vol.  19, no. 4, pp. 565–574, 2007.
[CrossRef]

Dutta, R.

B. Chen, G. N. Rouskas, and R. Dutta, “On hierarchical traffic grooming in WDM networks,” IEEE/ACM Trans. Netw., vol.  16, no. 5, pp. 1226–1238, Oct. 2008.
[CrossRef]

S. Huang, R. Dutta, and G. N. Rouskas, “Traffic grooming in path, star, and tree networks: Complexity, bounds, and algorithms,” IEEE J. Sel. Areas Commun., vol.  24, no. 4, pp. 66–82, Apr. 2006.
[CrossRef]

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.

R. Dutta and G. N. Rouskas, “On optimal traffic grooming in WDM rings,” IEEE J. Sel. Areas Commun., vol.  20, no. 1, pp. 110–121, Jan. 2002.
[CrossRef]

S. Huang and R. Dutta, “Research problems in dynamic traffic grooming in optical networks,” in Proc. First Workshop on Traffic Grooming, Apr. 2004.

Farahmand, F.

F. Farahmand, X. Huang, and J. P. Jue, “Efficient online traffic grooming algorithms in WDM mesh networks with drop-and-continue node architecture,” in Proc. Broadnets, Oct. 2004, pp. 180–189.

Gupta, R.

M. Dawande, R. Gupta, S. Naranpanawe, and C. Sriskandarajah, “A traffic-grooming algorithm in wavelength-routed optical networks,” INFORMS J. Comput., vol.  19, no. 4, pp. 565–574, 2007.
[CrossRef]

Hu, J. Q.

J. Q. Hu and B. Leida, “Traffic grooming, routing, and wavelength assignment in optical WDM mesh networks,” in Proc. IEEE INFOCOM, Mar. 2004, pp. 495–501.

Huang, S.

S. Huang, R. Dutta, and G. N. Rouskas, “Traffic grooming in path, star, and tree networks: Complexity, bounds, and algorithms,” IEEE J. Sel. Areas Commun., vol.  24, no. 4, pp. 66–82, Apr. 2006.
[CrossRef]

S. Huang and R. Dutta, “Research problems in dynamic traffic grooming in optical networks,” in Proc. First Workshop on Traffic Grooming, Apr. 2004.

Huang, X.

F. Farahmand, X. Huang, and J. P. Jue, “Efficient online traffic grooming algorithms in WDM mesh networks with drop-and-continue node architecture,” in Proc. Broadnets, Oct. 2004, pp. 180–189.

Jaumard, B.

B. Vignac, B. Jaumard, and F. Vanderbeck, “A hierarchical optimization approach to optical network design where traffic grooming and routing is solved by column generation,” in Proc. INOC, Apr. 2009.

Jue, J. P.

F. Farahmand, X. Huang, and J. P. Jue, “Efficient online traffic grooming algorithms in WDM mesh networks with drop-and-continue node architecture,” in Proc. Broadnets, Oct. 2004, pp. 180–189.

Konda, V. R.

V. R. Konda and T. Y. Chow, “Algorithm for traffic grooming in optical networks to minimize the number of transceivers,” in IEEE Workshop on High Performance Switching and Routing, 2001, pp. 218–221.

Labourdette, J.-F. P.

J.-F. P. Labourdette and A. S. Acampora, “Logically rearrangeable multihop lightwave networks,” IEEE Trans. Commun., vol.  39, no. 8, pp. 1223–1230, Aug. 1991.
[CrossRef]

Leida, B.

J. Q. Hu and B. Leida, “Traffic grooming, routing, and wavelength assignment in optical WDM mesh networks,” in Proc. IEEE INFOCOM, Mar. 2004, pp. 495–501.

Li, M.

W. Yao, G. Sahin, M. Li, and B. Ramamurthy, “Analysis of multi-hop traffic grooming in WDM mesh networks,” in Proc. Broadnets, Boston, MA, Oct. 2005, pp. 165–174.

Liu, Z.

E. Yetginer, Z. Liu, and G. N. Rouskas, “Fast exact ILP decompositions for ring RWA,” J. Opt. Commun. Netw., vol.  3, no. 7, pp. 577–586, July 2011.
[CrossRef]

Z. Liu and G. N. Rouskas, “A fast path-based ILP formulation for offline RWA in mesh optical networks,” in Proc. IEEE GLOBECOM, Dec. 2012.

Z. Liu and G. N. Rouskas, “Link selection algorithms for link-based ILPs and applications to RWA in mesh networks,” in Proc. ONDM, Apr. 2013.

Modiano, E.

Mukherjee, B.

K. Zhu and B. Mukherjee, “A review of traffic grooming in WDM optical networks: Architectures and challenges,” Opt. Netw. Mag., vol.  4, no. 2, pp. 55–64, Mar./Apr. 2003.

H. Zhu, H. Zang, K. Zhu, and B. Mukherjee, “A novel generic graph model for traffic grooming in heterogeneous WDM mesh networks,” IEEE/ACM Trans. Netw., vol.  11, no. 2, pp. 285–299, Apr. 2003.
[CrossRef]

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]

Munoz, X.

X. Munoz and I. Sau, “Traffic grooming in unidirectional WDM rings with bounded degree request graph,” in Graph-Theoretic Concepts in Computer Science (Lecture Notes in Computer Science, Vol. 5344). Springer, 2008, pp. 300–311.

Naranpanawe, S.

M. Dawande, R. Gupta, S. Naranpanawe, and C. Sriskandarajah, “A traffic-grooming algorithm in wavelength-routed optical networks,” INFORMS J. Comput., vol.  19, no. 4, pp. 565–574, 2007.
[CrossRef]

Ramamurthy, B.

W. Yao, G. Sahin, M. Li, and B. Ramamurthy, “Analysis of multi-hop traffic grooming in WDM mesh networks,” in Proc. Broadnets, Boston, MA, Oct. 2005, pp. 165–174.

Rouskas, G. N.

E. Yetginer, Z. Liu, and G. N. Rouskas, “Fast exact ILP decompositions for ring RWA,” J. Opt. Commun. Netw., vol.  3, no. 7, pp. 577–586, July 2011.
[CrossRef]

B. Chen, G. N. Rouskas, and R. Dutta, “On hierarchical traffic grooming in WDM networks,” IEEE/ACM Trans. Netw., vol.  16, no. 5, pp. 1226–1238, Oct. 2008.
[CrossRef]

S. Huang, R. Dutta, and G. N. Rouskas, “Traffic grooming in path, star, and tree networks: Complexity, bounds, and algorithms,” IEEE J. Sel. Areas Commun., vol.  24, no. 4, pp. 66–82, Apr. 2006.
[CrossRef]

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.

R. Dutta and G. N. Rouskas, “On optimal traffic grooming in WDM rings,” IEEE J. Sel. Areas Commun., vol.  20, no. 1, pp. 110–121, Jan. 2002.
[CrossRef]

E. Yetginer and G. N. Rouskas, “Power efficient traffic grooming in optical WDM networks,” in Proc. IEEE GLOBECOM, Dec. 2009.

Z. Liu and G. N. Rouskas, “A fast path-based ILP formulation for offline RWA in mesh optical networks,” in Proc. IEEE GLOBECOM, Dec. 2012.

Z. Liu and G. N. Rouskas, “Link selection algorithms for link-based ILPs and applications to RWA in mesh networks,” in Proc. ONDM, Apr. 2013.

Sahin, G.

W. Yao, G. Sahin, M. Li, and B. Ramamurthy, “Analysis of multi-hop traffic grooming in WDM mesh networks,” in Proc. Broadnets, Boston, MA, Oct. 2005, pp. 165–174.

Sau, I.

X. Munoz and I. Sau, “Traffic grooming in unidirectional WDM rings with bounded degree request graph,” in Graph-Theoretic Concepts in Computer Science (Lecture Notes in Computer Science, Vol. 5344). Springer, 2008, pp. 300–311.

Sriskandarajah, C.

M. Dawande, R. Gupta, S. Naranpanawe, and C. Sriskandarajah, “A traffic-grooming algorithm in wavelength-routed optical networks,” INFORMS J. Comput., vol.  19, no. 4, pp. 565–574, 2007.
[CrossRef]

Vanderbeck, F.

B. Vignac, B. Jaumard, and F. Vanderbeck, “A hierarchical optimization approach to optical network design where traffic grooming and routing is solved by column generation,” in Proc. INOC, Apr. 2009.

Vignac, B.

B. Vignac, B. Jaumard, and F. Vanderbeck, “A hierarchical optimization approach to optical network design where traffic grooming and routing is solved by column generation,” in Proc. INOC, Apr. 2009.

Yao, W.

W. Yao, G. Sahin, M. Li, and B. Ramamurthy, “Analysis of multi-hop traffic grooming in WDM mesh networks,” in Proc. Broadnets, Boston, MA, Oct. 2005, pp. 165–174.

Yetginer, E.

E. Yetginer, Z. Liu, and G. N. Rouskas, “Fast exact ILP decompositions for ring RWA,” J. Opt. Commun. Netw., vol.  3, no. 7, pp. 577–586, July 2011.
[CrossRef]

E. Yetginer and G. N. Rouskas, “Power efficient traffic grooming in optical WDM networks,” in Proc. IEEE GLOBECOM, Dec. 2009.

Zang, H.

H. Zhu, H. Zang, K. Zhu, and B. Mukherjee, “A novel generic graph model for traffic grooming in heterogeneous WDM mesh networks,” IEEE/ACM Trans. Netw., vol.  11, no. 2, pp. 285–299, Apr. 2003.
[CrossRef]

Zhu, H.

H. Zhu, H. Zang, K. Zhu, and B. Mukherjee, “A novel generic graph model for traffic grooming in heterogeneous WDM mesh networks,” IEEE/ACM Trans. Netw., vol.  11, no. 2, pp. 285–299, Apr. 2003.
[CrossRef]

Zhu, K.

H. Zhu, H. Zang, K. Zhu, and B. Mukherjee, “A novel generic graph model for traffic grooming in heterogeneous WDM mesh networks,” IEEE/ACM Trans. Netw., vol.  11, no. 2, pp. 285–299, Apr. 2003.
[CrossRef]

K. Zhu and B. Mukherjee, “A review of traffic grooming in WDM optical networks: Architectures and challenges,” Opt. Netw. Mag., vol.  4, no. 2, pp. 55–64, Mar./Apr. 2003.

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]

IEEE J. Sel. Areas Commun. (3)

S. Huang, R. Dutta, and G. N. Rouskas, “Traffic grooming in path, star, and tree networks: Complexity, bounds, and algorithms,” IEEE J. Sel. Areas Commun., vol.  24, no. 4, pp. 66–82, Apr. 2006.
[CrossRef]

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]

R. Dutta and G. N. Rouskas, “On optimal traffic grooming in WDM rings,” IEEE J. Sel. Areas Commun., vol.  20, no. 1, pp. 110–121, Jan. 2002.
[CrossRef]

IEEE Network (1)

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.

IEEE Trans. Commun. (1)

J.-F. P. Labourdette and A. S. Acampora, “Logically rearrangeable multihop lightwave networks,” IEEE Trans. Commun., vol.  39, no. 8, pp. 1223–1230, Aug. 1991.
[CrossRef]

IEEE/ACM Trans. Netw. (2)

B. Chen, G. N. Rouskas, and R. Dutta, “On hierarchical traffic grooming in WDM networks,” IEEE/ACM Trans. Netw., vol.  16, no. 5, pp. 1226–1238, Oct. 2008.
[CrossRef]

H. Zhu, H. Zang, K. Zhu, and B. Mukherjee, “A novel generic graph model for traffic grooming in heterogeneous WDM mesh networks,” IEEE/ACM Trans. Netw., vol.  11, no. 2, pp. 285–299, Apr. 2003.
[CrossRef]

INFORMS J. Comput. (1)

M. Dawande, R. Gupta, S. Naranpanawe, and C. Sriskandarajah, “A traffic-grooming algorithm in wavelength-routed optical networks,” INFORMS J. Comput., vol.  19, no. 4, pp. 565–574, 2007.
[CrossRef]

J. Lightwave Technol. (1)

J. Opt. Commun. Netw. (1)

Opt. Netw. Mag. (1)

K. Zhu and B. Mukherjee, “A review of traffic grooming in WDM optical networks: Architectures and challenges,” Opt. Netw. Mag., vol.  4, no. 2, pp. 55–64, Mar./Apr. 2003.

Other (10)

W. Yao, G. Sahin, M. Li, and B. Ramamurthy, “Analysis of multi-hop traffic grooming in WDM mesh networks,” in Proc. Broadnets, Boston, MA, Oct. 2005, pp. 165–174.

X. Munoz and I. Sau, “Traffic grooming in unidirectional WDM rings with bounded degree request graph,” in Graph-Theoretic Concepts in Computer Science (Lecture Notes in Computer Science, Vol. 5344). Springer, 2008, pp. 300–311.

Z. Liu and G. N. Rouskas, “A fast path-based ILP formulation for offline RWA in mesh optical networks,” in Proc. IEEE GLOBECOM, Dec. 2012.

Z. Liu and G. N. Rouskas, “Link selection algorithms for link-based ILPs and applications to RWA in mesh networks,” in Proc. ONDM, Apr. 2013.

V. R. Konda and T. Y. Chow, “Algorithm for traffic grooming in optical networks to minimize the number of transceivers,” in IEEE Workshop on High Performance Switching and Routing, 2001, pp. 218–221.

E. Yetginer and G. N. Rouskas, “Power efficient traffic grooming in optical WDM networks,” in Proc. IEEE GLOBECOM, Dec. 2009.

F. Farahmand, X. Huang, and J. P. Jue, “Efficient online traffic grooming algorithms in WDM mesh networks with drop-and-continue node architecture,” in Proc. Broadnets, Oct. 2004, pp. 180–189.

J. Q. Hu and B. Leida, “Traffic grooming, routing, and wavelength assignment in optical WDM mesh networks,” in Proc. IEEE INFOCOM, Mar. 2004, pp. 495–501.

S. Huang and R. Dutta, “Research problems in dynamic traffic grooming in optical networks,” in Proc. First Workshop on Traffic Grooming, Apr. 2004.

B. Vignac, B. Jaumard, and F. Vanderbeck, “A hierarchical optimization approach to optical network design where traffic grooming and routing is solved by column generation,” in Proc. INOC, Apr. 2009.

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 (7)

Fig. 1.
Fig. 1.

Wavelength usage comparison for five traffic instances, ring network with N=6 nodes.

Fig. 2.
Fig. 2.

Solution quality as a function of (Ul,Uh), tmax=30.

Fig. 3.
Fig. 3.

CPU time as a function of (Ul,Uh), N=16.

Fig. 4.
Fig. 4.

CPU time as a function of Ul, N=24, tmax=30.

Fig. 5.
Fig. 5.

CPU time as a function of N, (Ul,Uh)=(0.5,0.6), tmax=30.

Fig. 6.
Fig. 6.

CPU time comparison as a function of network size N, tmax=30.

Fig. 7.
Fig. 7.

Wavelength usage comparison, six-node ring network, tmax=12.

Tables (2)

Tables Icon

TABLE I CPU Time Comparison of VTTR and VTTR-rlx, N=16

Tables Icon

TABLE II Objective Value Comparison of VTTR and VTTR-rlx, N=16

Equations (25)

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

minimize:i,jNbij,
s,dtijsdbijC,i,jN,
jtijsdjtjisd=0,iN{s,d},s,dN,
jtsjsd=tsd,s,dN,
jtjssd=0,s,dN,
jtdjsd=0,s,dN,
jtjdsd=tsd,s,dN,
lLn+bijllLnbijl=0,nN{i,j},i,jN,
lLi+bijl=bij,i,jN,
lLibijl=0,i,jN,
lLj+bijl=0,i,jN,
lLjbijl=bij,i,jN,
wcijw,l=bijl,i,jN,lL,
i,jcijw,l1,w,lL,
lLn+cijw,l=lLncijw,l,nN{i,j},i,jN,w,
lLi+cijw,lbij,i,jN,w,
lLicijw,l=0,i,jN,w,
lLj+cijw,l=0,i,jN,w,
lLjcijw,lbij,i,jN,w,
tijsd,bij,bijl:integer;cijl,w:0,1;w=1,2,,W.
PVTTRPTG.
Uij=b¯ijb¯ij,b¯ij>0.
b¯ij=b¯iji,j:UijUh,
b¯ij=b¯iji,j:UijUl.
ijb¯ijijbij.