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

References

  • View by:
  • |

  1. M. Blanchet, F. Parent, B. St-Arnaud, ???Optical BGP (OBGP): InterAS Lightpath Provisioning,??? ietf-draft-parent-obgp-01, March 2001
  2. G. Bernstein, D. Cheng, 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, 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

European Conf on Optical Comm.

L. Wang, H. Zhang, 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.

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]

IEEE Global Communications Conference

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

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

IEEE Intl. Conference on Comm.

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

IFIP Working Conference 2003

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

Other

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

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

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

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