Abstract

For the first time a real-time and distributed routing algorithm based on Simulated Annealing (SA) algorithm is proposed to promote the intelligence, survivability, and interworking in optical mesh networks. Further, a SA-based Two-steps Optimization Routing Algorithm (SATORA) is proposed to obtain the inter-domain routing of global optimization. Compared with the previous approaches, this SA-based routing algorithm can achieve the routing optimization under multi-constraint condition, and can acquire the working and backup paths at one time for network survivability as well. Two crucial factors, the path hop count and the network congestion degree, are considered evaluating the cost of the path. Simulation experiments on different networks indicate that the SATORA can reduce the congestion degree of the networks and enhance the blocking performance of routing calculation for traffic requests when the inter-domain path protection is required.

© 2004 Optical Society of America

Full Article  |  PDF Article
Related Articles
Dimensioning WDM Networks for Dynamic Routing of Evolving Traffic

Xiaolan J. Zhang, Sun-il Kim, and Steven S. Lumetta
J. Opt. Commun. Netw. 2(9) 730-744 (2010)

Best Effort SRLG Failure Protection for Optical WDM Networks

Xu Shao, Yuebin Bai, Xiaofei Cheng, Yong-Kee Yeo, Luying Zhou, and Lek Heng Ngoh
J. Opt. Commun. Netw. 3(9) 739-749 (2011)

Survivable Path Computation in PCE-Based Multi-domain Networks

Qiong Zhang, Mohammad M. Hasan, Xi Wang, Paparao Palacharla, and Motoyoshi Sekiya
J. Opt. Commun. Netw. 4(6) 457-467 (2012)

References

  • View by:
  • |
  • |
  • |

  1. M. Blanchet, F. Parent, and B. St-Arnaud, “Optical BGP (OBGP): InterAS Lightpath Provisioning,” ietf-draft-parent-obgp-01, March 2001
  2. G. Bernstein, D. Cheng, and D. Pendarakis, et al. “Domain to Domain Routing using GMPLS, OSPF Extension V1.1 (Draft),” OIF2002.23.06, July 2002
  3. L. Wang, H. Zhang, and X. Zheng, et al. “A Novel OBGP-based Mechanism for Lightpath Establishment in WDM Mesh Networks,” in Proceedings of European Conference on Optical Communication, (Academic, Rimini, Italy, 2003), We4.P.136, vol. 3, pp. 828–829
  4. R. Bhandari, Survivable Networks: Algorithms for Diverse Routing (Kluwer, Boston, Mass., 1999)
  5. H. Qin, Z. Liu, S. Zhang, and A. Wen, “Routing and wavelength assignment based on genetic algorithm,” IEEE Commun. Lett. 6, 455–457 (2002)
    [Crossref]
  6. C. Ersoy and S. S. Panwar, “Topological design of multihop lightwave networks,” in Proceedings of IEEE Global Communications Conference, (Institute of Electrical and Electronics Engineering, Houston, TX, 1993), pp.1803–1807
  7. M. Ktao and Y. Oie, “Reconfiguration algorithms based on metaheuristics for multihop WDM lightwave networks,” in Proceedings of IEEE International Conference on Communications, (Institute of Electrical and Electronics Engineering, New Orleans, LA, 2000), pp.1638–1644
  8. T. Qin, H. Zhang, and Y. Guo, “A modified simulated annealing algorithm for Joint configuration of the optical and electrical layer in intelligent optical networks,” in Proceedings of IEEE Global Communications Conference, (Institute of Electrical and Electronics Engineering, Taipei, China, 2002), OPNT-05-8
  9. P. Datta, M. Sridharan, and A. K. Somani, “A simulated annealing approach for topology planning and evolution of mesh-restorable optical networks,” in Proceedings of IFIP Working Conference on Optical Network Design and Modeling, (Budapest, Hungary, 2003), vol. 1, pp. 23–40

2002 (1)

H. Qin, Z. Liu, S. Zhang, and A. Wen, “Routing and wavelength assignment based on genetic algorithm,” IEEE Commun. Lett. 6, 455–457 (2002)
[Crossref]

Bernstein, G.

G. Bernstein, D. Cheng, and D. Pendarakis, et al. “Domain to Domain Routing using GMPLS, OSPF Extension V1.1 (Draft),” OIF2002.23.06, July 2002

Bhandari, R.

R. Bhandari, Survivable Networks: Algorithms for Diverse Routing (Kluwer, Boston, Mass., 1999)

Blanchet, M.

M. Blanchet, F. Parent, and B. St-Arnaud, “Optical BGP (OBGP): InterAS Lightpath Provisioning,” ietf-draft-parent-obgp-01, March 2001

Cheng, D.

G. Bernstein, D. Cheng, and D. Pendarakis, et al. “Domain to Domain Routing using GMPLS, OSPF Extension V1.1 (Draft),” OIF2002.23.06, July 2002

Datta, P.

P. Datta, M. Sridharan, and A. K. Somani, “A simulated annealing approach for topology planning and evolution of mesh-restorable optical networks,” in Proceedings of IFIP Working Conference on Optical Network Design and Modeling, (Budapest, Hungary, 2003), vol. 1, pp. 23–40

Ersoy, C.

C. Ersoy and S. S. Panwar, “Topological design of multihop lightwave networks,” in Proceedings of IEEE Global Communications Conference, (Institute of Electrical and Electronics Engineering, Houston, TX, 1993), pp.1803–1807

Guo, Y.

T. Qin, H. Zhang, and Y. Guo, “A modified simulated annealing algorithm for Joint configuration of the optical and electrical layer in intelligent optical networks,” in Proceedings of IEEE Global Communications Conference, (Institute of Electrical and Electronics Engineering, Taipei, China, 2002), OPNT-05-8

Ktao, M.

M. Ktao and Y. Oie, “Reconfiguration algorithms based on metaheuristics for multihop WDM lightwave networks,” in Proceedings of IEEE International Conference on Communications, (Institute of Electrical and Electronics Engineering, New Orleans, LA, 2000), pp.1638–1644

Liu, Z.

H. Qin, Z. Liu, S. Zhang, and A. Wen, “Routing and wavelength assignment based on genetic algorithm,” IEEE Commun. Lett. 6, 455–457 (2002)
[Crossref]

Oie, Y.

M. Ktao and Y. Oie, “Reconfiguration algorithms based on metaheuristics for multihop WDM lightwave networks,” in Proceedings of IEEE International Conference on Communications, (Institute of Electrical and Electronics Engineering, New Orleans, LA, 2000), pp.1638–1644

Panwar, S. S.

C. Ersoy and S. S. Panwar, “Topological design of multihop lightwave networks,” in Proceedings of IEEE Global Communications Conference, (Institute of Electrical and Electronics Engineering, Houston, TX, 1993), pp.1803–1807

Parent, F.

M. Blanchet, F. Parent, and B. St-Arnaud, “Optical BGP (OBGP): InterAS Lightpath Provisioning,” ietf-draft-parent-obgp-01, March 2001

Pendarakis, D.

G. Bernstein, D. Cheng, and D. Pendarakis, et al. “Domain to Domain Routing using GMPLS, OSPF Extension V1.1 (Draft),” OIF2002.23.06, July 2002

Qin, H.

H. Qin, Z. Liu, S. Zhang, and A. Wen, “Routing and wavelength assignment based on genetic algorithm,” IEEE Commun. Lett. 6, 455–457 (2002)
[Crossref]

Qin, T.

T. Qin, H. Zhang, and Y. Guo, “A modified simulated annealing algorithm for Joint configuration of the optical and electrical layer in intelligent optical networks,” in Proceedings of IEEE Global Communications Conference, (Institute of Electrical and Electronics Engineering, Taipei, China, 2002), OPNT-05-8

Somani, A. K.

P. Datta, M. Sridharan, and A. K. Somani, “A simulated annealing approach for topology planning and evolution of mesh-restorable optical networks,” in Proceedings of IFIP Working Conference on Optical Network Design and Modeling, (Budapest, Hungary, 2003), vol. 1, pp. 23–40

Sridharan, M.

P. Datta, M. Sridharan, and A. K. Somani, “A simulated annealing approach for topology planning and evolution of mesh-restorable optical networks,” in Proceedings of IFIP Working Conference on Optical Network Design and Modeling, (Budapest, Hungary, 2003), vol. 1, pp. 23–40

St-Arnaud, B.

M. Blanchet, F. Parent, and B. St-Arnaud, “Optical BGP (OBGP): InterAS Lightpath Provisioning,” ietf-draft-parent-obgp-01, March 2001

Wang, L.

L. Wang, H. Zhang, and X. Zheng, et al. “A Novel OBGP-based Mechanism for Lightpath Establishment in WDM Mesh Networks,” in Proceedings of European Conference on Optical Communication, (Academic, Rimini, Italy, 2003), We4.P.136, vol. 3, pp. 828–829

Wen, A.

H. Qin, Z. Liu, S. Zhang, and A. Wen, “Routing and wavelength assignment based on genetic algorithm,” IEEE Commun. Lett. 6, 455–457 (2002)
[Crossref]

Zhang, H.

L. Wang, H. Zhang, and X. Zheng, et al. “A Novel OBGP-based Mechanism for Lightpath Establishment in WDM Mesh Networks,” in Proceedings of European Conference on Optical Communication, (Academic, Rimini, Italy, 2003), We4.P.136, vol. 3, pp. 828–829

T. Qin, H. Zhang, and Y. Guo, “A modified simulated annealing algorithm for Joint configuration of the optical and electrical layer in intelligent optical networks,” in Proceedings of IEEE Global Communications Conference, (Institute of Electrical and Electronics Engineering, Taipei, China, 2002), OPNT-05-8

Zhang, S.

H. Qin, Z. Liu, S. Zhang, and A. Wen, “Routing and wavelength assignment based on genetic algorithm,” IEEE Commun. Lett. 6, 455–457 (2002)
[Crossref]

Zheng, X.

L. Wang, H. Zhang, and X. Zheng, et al. “A Novel OBGP-based Mechanism for Lightpath Establishment in WDM Mesh Networks,” in Proceedings of European Conference on Optical Communication, (Academic, Rimini, Italy, 2003), We4.P.136, vol. 3, pp. 828–829

IEEE Commun. Lett. (1)

H. Qin, Z. Liu, S. Zhang, and A. Wen, “Routing and wavelength assignment based on genetic algorithm,” IEEE Commun. Lett. 6, 455–457 (2002)
[Crossref]

Other (8)

C. Ersoy and S. S. Panwar, “Topological design of multihop lightwave networks,” in Proceedings of IEEE Global Communications Conference, (Institute of Electrical and Electronics Engineering, Houston, TX, 1993), pp.1803–1807

M. Ktao and Y. Oie, “Reconfiguration algorithms based on metaheuristics for multihop WDM lightwave networks,” in Proceedings of IEEE International Conference on Communications, (Institute of Electrical and Electronics Engineering, New Orleans, LA, 2000), pp.1638–1644

T. Qin, H. Zhang, and Y. Guo, “A modified simulated annealing algorithm for Joint configuration of the optical and electrical layer in intelligent optical networks,” in Proceedings of IEEE Global Communications Conference, (Institute of Electrical and Electronics Engineering, Taipei, China, 2002), OPNT-05-8

P. Datta, M. Sridharan, and A. K. Somani, “A simulated annealing approach for topology planning and evolution of mesh-restorable optical networks,” in Proceedings of IFIP Working Conference on Optical Network Design and Modeling, (Budapest, Hungary, 2003), vol. 1, pp. 23–40

M. Blanchet, F. Parent, and B. St-Arnaud, “Optical BGP (OBGP): InterAS Lightpath Provisioning,” ietf-draft-parent-obgp-01, March 2001

G. Bernstein, D. Cheng, and D. Pendarakis, et al. “Domain to Domain Routing using GMPLS, OSPF Extension V1.1 (Draft),” OIF2002.23.06, July 2002

L. Wang, H. Zhang, and X. Zheng, et al. “A Novel OBGP-based Mechanism for Lightpath Establishment in WDM Mesh Networks,” in Proceedings of European Conference on Optical Communication, (Academic, Rimini, Italy, 2003), We4.P.136, vol. 3, pp. 828–829

R. Bhandari, Survivable Networks: Algorithms for Diverse Routing (Kluwer, Boston, Mass., 1999)

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

Fig.1.
Fig.1.

An example for the comparison of MDP and SATORA

Fig. 2.
Fig. 2.

Flowchart of initialization routing algorithm

Fig. 3.
Fig. 3.

Simulation network environment: (a) and (b) NInter =9; (c) NInter =14.

Fig. 4.
Fig. 4.

Blocking probability vs. network traffic load for SATORA

Fig. 5.
Fig. 5.

Comparing SATORA and MDP for path protection in blocking probability

Fig. 6.
Fig. 6.

Comparing SATORA and MDP for path protection in network congestion degree

Tables (5)

Tables Icon

Table 1. The SA-based routing algorithm

Tables Icon

Table 3. The improved SA-based routing algorithm for diverse routing

Tables Icon

Table 4. Improvement of the network congestion degree between SATORA and MDP

Tables Icon

Table 5. Operation time in SATORA and MDP

Equations (3)

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

E ( P ) = α * E 1 ( P ) + β * E 2 ( P )
E ( P , G ) = Φ * E ( P Inter , G Inter ) + Ψ * k = 1 P Inter E ( P Intra , k , G Intra , k )
E ( P w ) = Φ * E Inter , w + Ψ * k = 1 P I nter E Intra , w , k

Metrics