Abstract

We present the generic Dijkstra shortest-path algorithm: an efficient algorithm for finding a shortest path in an optical network, in both a wavelength-division multiplexed network and an elastic optical network (EON). The proposed algorithm is an enabler of real-time softwarized control of large-scale networks and is not limited to optical networks. The Dijkstra algorithm is a generalization of the breadth-first search, and we generalize the Dijkstra algorithm further to resolve the continuity and contiguity constraints of the frequency slot units required in EONs. Specifically, we generalize the notion of a label, change what we iterate with, and reformulate the edge relaxation so that vertices are revisited, loops avoided, and worse labels discarded. We also use the typical constriction during edge relaxation to take care of the signal modulation constraints. The algorithm can be used with various spectrum allocation policies. We motivate and discuss the algorithm design, and provide our free, reliable, and generic implementation using the Boost Graph Library. We carried out 85,000 simulation runs for realistic and random networks (Gabriel graphs) of 75 vertices with about a billion shortest-path searches, and found that the proposed algorithm outperforms considerably three other competing optimal algorithms that are frequently used.

© 2019 Optical Society of America under the terms of the OSA Open Access Publishing Agreement

Full Article  |  PDF Article
OSA Recommended Articles
Dynamic Routing and Spectrum Allocation in Elastic Optical Networks With Mixed Line Rates

Xiong Wang, Kaixuan Kuang, Sheng Wang, Shizhong Xu, Hong Liu, and Gordon Ning Liu
J. Opt. Commun. Netw. 6(12) 1115-1127 (2014)

Graph-Model-Based Dynamic Routing and Spectrum Assignment in Elastic Optical Networks

Ching-Fang Hsu, Yuan-Chih Chang, and Siou-Ci Sie
J. Opt. Commun. Netw. 8(7) 507-520 (2016)

Load Balancing in Fixed-Routing Optical Networks with Weighted Ordering Heuristics

L. H. Bonani, J. C. F. Queiroz, M. L. F. Abbade, and F. Callegati
J. Opt. Commun. Netw. 11(3) 26-38 (2019)

References

  • View by:
  • |
  • |
  • |

  1. I. Szcześniak, “The implementation of the generic Dijkstra,” 2018, http://www.irkos.org/gd .
  2. I. Szcześniak, “The SDI software,” 2013, http://www.irkos.org/sdi .
  3. R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications (Prentice Hall, 1993).
  4. I. Szcześniak and B. Woźna-Szcześniak, “Adapted and constrained Dijkstra for elastic optical networks,” in International Conference on Optical Network Design and Modeling (ONDM), May 2016, pp. 1–6.
  5. A. A. Stepanov and D. E. Rose, From Mathematics to Generic Programming (Addison-Wesley, 2014).
  6. H. Zang, J. P. Jue, and B. Mukherjee, “A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks,” Opt. Netw. Mag. 1(1), 47–60 (2000).
  7. S. Talebi, F. Alam, I. Katib, M. Khamis, R. Salama, and G. N. Rouskas, “Spectrum management techniques for elastic optical networks: a survey,” Opt. Switching Netw. 13, 34–48 (2014).
    [Crossref]
  8. Y. Wang, X. Cao, and Y. Pan, “A study of the routing and spectrum allocation in spectrum-sliced elastic optical path networks,” in IEEE INFOCOM, April 2011, pp. 1503–1511.
  9. B. C. Chatterjee, N. Sarma, and E. Oki, “Routing and spectrum allocation in elastic optical networks: a tutorial,” IEEE Commun. Surv. Tutorials 17, 1776–1800 (2015).
    [Crossref]
  10. F. S. Abkenar and A. G. Rahbar, “Study and analysis of routing and spectrum allocation (RSA) and routing, modulation and spectrum allocation (RMSA) algorithms in elastic optical networks (EONs),” Opt. Switching Netw. 23, 5–39 (2017).
    [Crossref]
  11. I. Olszewski, “Improved dynamic routing algorithms in elastic optical networks,” Photon. Netw. Commun. 34, 323–333 (2017).
    [Crossref]
  12. L. Velasco, M. Klinkowski, M. Ruiz, and J. Comellas, “Modeling the routing and spectrum allocation problem for flexgrid optical networks,” Photon. Netw. Commun. 24, 177–186 (2012).
    [Crossref]
  13. X. Wang, K. Kuang, S. Wang, S. Xu, H. Liu, and G. N. Liu, “Dynamic routing and spectrum allocation in elastic optical networks with mixed line rates,” J. Opt. Commun. Netw. 6, 1115–1127 (2014).
    [Crossref]
  14. X. Wan, N. Hua, and X. Zheng, “Dynamic routing and spectrum assignment in spectrum-flexible transparent optical networks,” J. Opt. Commun. Netw. 4, 603–613 (2012).
    [Crossref]
  15. K. Christodoulopoulos, P. Kokkinos, and E. M. Varvarigos, “Indirect and direct multicost algorithms for online impairment-aware RWA,” IEEE/ACM Trans. Netw. 19, 1759–1772 (2011).
    [Crossref]
  16. E. M. Varvarigos, V. Sourlas, and K. Christodoulopoulos, “Routing and scheduling connections in networks that support advance reservations,” Comput. Netw. 52, 2988–3006 (2008).
    [Crossref]
  17. F. Gutierrez, E. Varvarigos, and S. Vassiliadis, “Multi-cost routing in max-min fair share networks,” in 38th Annual Allerton Conference on Communications, Control, and Computing, Monticello, Virginia, October 2000, pp. 1294–1304.
  18. L. Velasco, A. Castro, M. Ruiz, and G. Junyent, “Solving routing and spectrum allocation related optimization problems: from off-line to in-operation flexgrid network planning,” J. Lightwave Technol. 32, 2780–2795 (2014).
    [Crossref]
  19. A. A. Stepanov and P. McJones, Elements of Programming (Addison-Wesley, 2009).
  20. E. Cetinkaya, M. Alenazi, Y. Cheng, A. Peck, and J. Sterbenz, “On the fitness of geographic graph generators for modelling physical level topologies,” in 5th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), September 2013, pp. 38–45.
  21. M. Jinno, B. Kozicki, H. Takara, A. Watanabe, Y. Sone, T. Tanaka, and A. Hirano, “Distance-adaptive spectrum resource allocation in spectrum-sliced elastic optical path network,” IEEE Commun. Mag. 48(8), 138–145 (2010).
    [Crossref]

2017 (2)

F. S. Abkenar and A. G. Rahbar, “Study and analysis of routing and spectrum allocation (RSA) and routing, modulation and spectrum allocation (RMSA) algorithms in elastic optical networks (EONs),” Opt. Switching Netw. 23, 5–39 (2017).
[Crossref]

I. Olszewski, “Improved dynamic routing algorithms in elastic optical networks,” Photon. Netw. Commun. 34, 323–333 (2017).
[Crossref]

2015 (1)

B. C. Chatterjee, N. Sarma, and E. Oki, “Routing and spectrum allocation in elastic optical networks: a tutorial,” IEEE Commun. Surv. Tutorials 17, 1776–1800 (2015).
[Crossref]

2014 (3)

2012 (2)

X. Wan, N. Hua, and X. Zheng, “Dynamic routing and spectrum assignment in spectrum-flexible transparent optical networks,” J. Opt. Commun. Netw. 4, 603–613 (2012).
[Crossref]

L. Velasco, M. Klinkowski, M. Ruiz, and J. Comellas, “Modeling the routing and spectrum allocation problem for flexgrid optical networks,” Photon. Netw. Commun. 24, 177–186 (2012).
[Crossref]

2011 (1)

K. Christodoulopoulos, P. Kokkinos, and E. M. Varvarigos, “Indirect and direct multicost algorithms for online impairment-aware RWA,” IEEE/ACM Trans. Netw. 19, 1759–1772 (2011).
[Crossref]

2010 (1)

M. Jinno, B. Kozicki, H. Takara, A. Watanabe, Y. Sone, T. Tanaka, and A. Hirano, “Distance-adaptive spectrum resource allocation in spectrum-sliced elastic optical path network,” IEEE Commun. Mag. 48(8), 138–145 (2010).
[Crossref]

2008 (1)

E. M. Varvarigos, V. Sourlas, and K. Christodoulopoulos, “Routing and scheduling connections in networks that support advance reservations,” Comput. Netw. 52, 2988–3006 (2008).
[Crossref]

2000 (1)

H. Zang, J. P. Jue, and B. Mukherjee, “A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks,” Opt. Netw. Mag. 1(1), 47–60 (2000).

Abkenar, F. S.

F. S. Abkenar and A. G. Rahbar, “Study and analysis of routing and spectrum allocation (RSA) and routing, modulation and spectrum allocation (RMSA) algorithms in elastic optical networks (EONs),” Opt. Switching Netw. 23, 5–39 (2017).
[Crossref]

Ahuja, R. K.

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications (Prentice Hall, 1993).

Alam, F.

S. Talebi, F. Alam, I. Katib, M. Khamis, R. Salama, and G. N. Rouskas, “Spectrum management techniques for elastic optical networks: a survey,” Opt. Switching Netw. 13, 34–48 (2014).
[Crossref]

Alenazi, M.

E. Cetinkaya, M. Alenazi, Y. Cheng, A. Peck, and J. Sterbenz, “On the fitness of geographic graph generators for modelling physical level topologies,” in 5th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), September 2013, pp. 38–45.

Cao, X.

Y. Wang, X. Cao, and Y. Pan, “A study of the routing and spectrum allocation in spectrum-sliced elastic optical path networks,” in IEEE INFOCOM, April 2011, pp. 1503–1511.

Castro, A.

Cetinkaya, E.

E. Cetinkaya, M. Alenazi, Y. Cheng, A. Peck, and J. Sterbenz, “On the fitness of geographic graph generators for modelling physical level topologies,” in 5th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), September 2013, pp. 38–45.

Chatterjee, B. C.

B. C. Chatterjee, N. Sarma, and E. Oki, “Routing and spectrum allocation in elastic optical networks: a tutorial,” IEEE Commun. Surv. Tutorials 17, 1776–1800 (2015).
[Crossref]

Cheng, Y.

E. Cetinkaya, M. Alenazi, Y. Cheng, A. Peck, and J. Sterbenz, “On the fitness of geographic graph generators for modelling physical level topologies,” in 5th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), September 2013, pp. 38–45.

Christodoulopoulos, K.

K. Christodoulopoulos, P. Kokkinos, and E. M. Varvarigos, “Indirect and direct multicost algorithms for online impairment-aware RWA,” IEEE/ACM Trans. Netw. 19, 1759–1772 (2011).
[Crossref]

E. M. Varvarigos, V. Sourlas, and K. Christodoulopoulos, “Routing and scheduling connections in networks that support advance reservations,” Comput. Netw. 52, 2988–3006 (2008).
[Crossref]

Comellas, J.

L. Velasco, M. Klinkowski, M. Ruiz, and J. Comellas, “Modeling the routing and spectrum allocation problem for flexgrid optical networks,” Photon. Netw. Commun. 24, 177–186 (2012).
[Crossref]

Gutierrez, F.

F. Gutierrez, E. Varvarigos, and S. Vassiliadis, “Multi-cost routing in max-min fair share networks,” in 38th Annual Allerton Conference on Communications, Control, and Computing, Monticello, Virginia, October 2000, pp. 1294–1304.

Hirano, A.

M. Jinno, B. Kozicki, H. Takara, A. Watanabe, Y. Sone, T. Tanaka, and A. Hirano, “Distance-adaptive spectrum resource allocation in spectrum-sliced elastic optical path network,” IEEE Commun. Mag. 48(8), 138–145 (2010).
[Crossref]

Hua, N.

Jinno, M.

M. Jinno, B. Kozicki, H. Takara, A. Watanabe, Y. Sone, T. Tanaka, and A. Hirano, “Distance-adaptive spectrum resource allocation in spectrum-sliced elastic optical path network,” IEEE Commun. Mag. 48(8), 138–145 (2010).
[Crossref]

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. Netw. Mag. 1(1), 47–60 (2000).

Junyent, G.

Katib, I.

S. Talebi, F. Alam, I. Katib, M. Khamis, R. Salama, and G. N. Rouskas, “Spectrum management techniques for elastic optical networks: a survey,” Opt. Switching Netw. 13, 34–48 (2014).
[Crossref]

Khamis, M.

S. Talebi, F. Alam, I. Katib, M. Khamis, R. Salama, and G. N. Rouskas, “Spectrum management techniques for elastic optical networks: a survey,” Opt. Switching Netw. 13, 34–48 (2014).
[Crossref]

Klinkowski, M.

L. Velasco, M. Klinkowski, M. Ruiz, and J. Comellas, “Modeling the routing and spectrum allocation problem for flexgrid optical networks,” Photon. Netw. Commun. 24, 177–186 (2012).
[Crossref]

Kokkinos, P.

K. Christodoulopoulos, P. Kokkinos, and E. M. Varvarigos, “Indirect and direct multicost algorithms for online impairment-aware RWA,” IEEE/ACM Trans. Netw. 19, 1759–1772 (2011).
[Crossref]

Kozicki, B.

M. Jinno, B. Kozicki, H. Takara, A. Watanabe, Y. Sone, T. Tanaka, and A. Hirano, “Distance-adaptive spectrum resource allocation in spectrum-sliced elastic optical path network,” IEEE Commun. Mag. 48(8), 138–145 (2010).
[Crossref]

Kuang, K.

Liu, G. N.

Liu, H.

Magnanti, T. L.

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications (Prentice Hall, 1993).

McJones, P.

A. A. Stepanov and P. McJones, Elements of Programming (Addison-Wesley, 2009).

Mukherjee, B.

H. Zang, J. P. Jue, and B. Mukherjee, “A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks,” Opt. Netw. Mag. 1(1), 47–60 (2000).

Oki, E.

B. C. Chatterjee, N. Sarma, and E. Oki, “Routing and spectrum allocation in elastic optical networks: a tutorial,” IEEE Commun. Surv. Tutorials 17, 1776–1800 (2015).
[Crossref]

Olszewski, I.

I. Olszewski, “Improved dynamic routing algorithms in elastic optical networks,” Photon. Netw. Commun. 34, 323–333 (2017).
[Crossref]

Orlin, J. B.

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications (Prentice Hall, 1993).

Pan, Y.

Y. Wang, X. Cao, and Y. Pan, “A study of the routing and spectrum allocation in spectrum-sliced elastic optical path networks,” in IEEE INFOCOM, April 2011, pp. 1503–1511.

Peck, A.

E. Cetinkaya, M. Alenazi, Y. Cheng, A. Peck, and J. Sterbenz, “On the fitness of geographic graph generators for modelling physical level topologies,” in 5th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), September 2013, pp. 38–45.

Rahbar, A. G.

F. S. Abkenar and A. G. Rahbar, “Study and analysis of routing and spectrum allocation (RSA) and routing, modulation and spectrum allocation (RMSA) algorithms in elastic optical networks (EONs),” Opt. Switching Netw. 23, 5–39 (2017).
[Crossref]

Rose, D. E.

A. A. Stepanov and D. E. Rose, From Mathematics to Generic Programming (Addison-Wesley, 2014).

Rouskas, G. N.

S. Talebi, F. Alam, I. Katib, M. Khamis, R. Salama, and G. N. Rouskas, “Spectrum management techniques for elastic optical networks: a survey,” Opt. Switching Netw. 13, 34–48 (2014).
[Crossref]

Ruiz, M.

L. Velasco, A. Castro, M. Ruiz, and G. Junyent, “Solving routing and spectrum allocation related optimization problems: from off-line to in-operation flexgrid network planning,” J. Lightwave Technol. 32, 2780–2795 (2014).
[Crossref]

L. Velasco, M. Klinkowski, M. Ruiz, and J. Comellas, “Modeling the routing and spectrum allocation problem for flexgrid optical networks,” Photon. Netw. Commun. 24, 177–186 (2012).
[Crossref]

Salama, R.

S. Talebi, F. Alam, I. Katib, M. Khamis, R. Salama, and G. N. Rouskas, “Spectrum management techniques for elastic optical networks: a survey,” Opt. Switching Netw. 13, 34–48 (2014).
[Crossref]

Sarma, N.

B. C. Chatterjee, N. Sarma, and E. Oki, “Routing and spectrum allocation in elastic optical networks: a tutorial,” IEEE Commun. Surv. Tutorials 17, 1776–1800 (2015).
[Crossref]

Sone, Y.

M. Jinno, B. Kozicki, H. Takara, A. Watanabe, Y. Sone, T. Tanaka, and A. Hirano, “Distance-adaptive spectrum resource allocation in spectrum-sliced elastic optical path network,” IEEE Commun. Mag. 48(8), 138–145 (2010).
[Crossref]

Sourlas, V.

E. M. Varvarigos, V. Sourlas, and K. Christodoulopoulos, “Routing and scheduling connections in networks that support advance reservations,” Comput. Netw. 52, 2988–3006 (2008).
[Crossref]

Stepanov, A. A.

A. A. Stepanov and D. E. Rose, From Mathematics to Generic Programming (Addison-Wesley, 2014).

A. A. Stepanov and P. McJones, Elements of Programming (Addison-Wesley, 2009).

Sterbenz, J.

E. Cetinkaya, M. Alenazi, Y. Cheng, A. Peck, and J. Sterbenz, “On the fitness of geographic graph generators for modelling physical level topologies,” in 5th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), September 2013, pp. 38–45.

Szczesniak, I.

I. Szcześniak and B. Woźna-Szcześniak, “Adapted and constrained Dijkstra for elastic optical networks,” in International Conference on Optical Network Design and Modeling (ONDM), May 2016, pp. 1–6.

Takara, H.

M. Jinno, B. Kozicki, H. Takara, A. Watanabe, Y. Sone, T. Tanaka, and A. Hirano, “Distance-adaptive spectrum resource allocation in spectrum-sliced elastic optical path network,” IEEE Commun. Mag. 48(8), 138–145 (2010).
[Crossref]

Talebi, S.

S. Talebi, F. Alam, I. Katib, M. Khamis, R. Salama, and G. N. Rouskas, “Spectrum management techniques for elastic optical networks: a survey,” Opt. Switching Netw. 13, 34–48 (2014).
[Crossref]

Tanaka, T.

M. Jinno, B. Kozicki, H. Takara, A. Watanabe, Y. Sone, T. Tanaka, and A. Hirano, “Distance-adaptive spectrum resource allocation in spectrum-sliced elastic optical path network,” IEEE Commun. Mag. 48(8), 138–145 (2010).
[Crossref]

Varvarigos, E.

F. Gutierrez, E. Varvarigos, and S. Vassiliadis, “Multi-cost routing in max-min fair share networks,” in 38th Annual Allerton Conference on Communications, Control, and Computing, Monticello, Virginia, October 2000, pp. 1294–1304.

Varvarigos, E. M.

K. Christodoulopoulos, P. Kokkinos, and E. M. Varvarigos, “Indirect and direct multicost algorithms for online impairment-aware RWA,” IEEE/ACM Trans. Netw. 19, 1759–1772 (2011).
[Crossref]

E. M. Varvarigos, V. Sourlas, and K. Christodoulopoulos, “Routing and scheduling connections in networks that support advance reservations,” Comput. Netw. 52, 2988–3006 (2008).
[Crossref]

Vassiliadis, S.

F. Gutierrez, E. Varvarigos, and S. Vassiliadis, “Multi-cost routing in max-min fair share networks,” in 38th Annual Allerton Conference on Communications, Control, and Computing, Monticello, Virginia, October 2000, pp. 1294–1304.

Velasco, L.

L. Velasco, A. Castro, M. Ruiz, and G. Junyent, “Solving routing and spectrum allocation related optimization problems: from off-line to in-operation flexgrid network planning,” J. Lightwave Technol. 32, 2780–2795 (2014).
[Crossref]

L. Velasco, M. Klinkowski, M. Ruiz, and J. Comellas, “Modeling the routing and spectrum allocation problem for flexgrid optical networks,” Photon. Netw. Commun. 24, 177–186 (2012).
[Crossref]

Wan, X.

Wang, S.

Wang, X.

Wang, Y.

Y. Wang, X. Cao, and Y. Pan, “A study of the routing and spectrum allocation in spectrum-sliced elastic optical path networks,” in IEEE INFOCOM, April 2011, pp. 1503–1511.

Watanabe, A.

M. Jinno, B. Kozicki, H. Takara, A. Watanabe, Y. Sone, T. Tanaka, and A. Hirano, “Distance-adaptive spectrum resource allocation in spectrum-sliced elastic optical path network,” IEEE Commun. Mag. 48(8), 138–145 (2010).
[Crossref]

Wozna-Szczesniak, B.

I. Szcześniak and B. Woźna-Szcześniak, “Adapted and constrained Dijkstra for elastic optical networks,” in International Conference on Optical Network Design and Modeling (ONDM), May 2016, pp. 1–6.

Xu, S.

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. Netw. Mag. 1(1), 47–60 (2000).

Zheng, X.

Comput. Netw. (1)

E. M. Varvarigos, V. Sourlas, and K. Christodoulopoulos, “Routing and scheduling connections in networks that support advance reservations,” Comput. Netw. 52, 2988–3006 (2008).
[Crossref]

IEEE Commun. Mag. (1)

M. Jinno, B. Kozicki, H. Takara, A. Watanabe, Y. Sone, T. Tanaka, and A. Hirano, “Distance-adaptive spectrum resource allocation in spectrum-sliced elastic optical path network,” IEEE Commun. Mag. 48(8), 138–145 (2010).
[Crossref]

IEEE Commun. Surv. Tutorials (1)

B. C. Chatterjee, N. Sarma, and E. Oki, “Routing and spectrum allocation in elastic optical networks: a tutorial,” IEEE Commun. Surv. Tutorials 17, 1776–1800 (2015).
[Crossref]

IEEE/ACM Trans. Netw. (1)

K. Christodoulopoulos, P. Kokkinos, and E. M. Varvarigos, “Indirect and direct multicost algorithms for online impairment-aware RWA,” IEEE/ACM Trans. Netw. 19, 1759–1772 (2011).
[Crossref]

J. Lightwave Technol. (1)

J. Opt. Commun. Netw. (2)

Opt. Netw. Mag. (1)

H. Zang, J. P. Jue, and B. Mukherjee, “A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks,” Opt. Netw. Mag. 1(1), 47–60 (2000).

Opt. Switching Netw. (2)

S. Talebi, F. Alam, I. Katib, M. Khamis, R. Salama, and G. N. Rouskas, “Spectrum management techniques for elastic optical networks: a survey,” Opt. Switching Netw. 13, 34–48 (2014).
[Crossref]

F. S. Abkenar and A. G. Rahbar, “Study and analysis of routing and spectrum allocation (RSA) and routing, modulation and spectrum allocation (RMSA) algorithms in elastic optical networks (EONs),” Opt. Switching Netw. 23, 5–39 (2017).
[Crossref]

Photon. Netw. Commun. (2)

I. Olszewski, “Improved dynamic routing algorithms in elastic optical networks,” Photon. Netw. Commun. 34, 323–333 (2017).
[Crossref]

L. Velasco, M. Klinkowski, M. Ruiz, and J. Comellas, “Modeling the routing and spectrum allocation problem for flexgrid optical networks,” Photon. Netw. Commun. 24, 177–186 (2012).
[Crossref]

Other (9)

I. Szcześniak, “The implementation of the generic Dijkstra,” 2018, http://www.irkos.org/gd .

I. Szcześniak, “The SDI software,” 2013, http://www.irkos.org/sdi .

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications (Prentice Hall, 1993).

I. Szcześniak and B. Woźna-Szcześniak, “Adapted and constrained Dijkstra for elastic optical networks,” in International Conference on Optical Network Design and Modeling (ONDM), May 2016, pp. 1–6.

A. A. Stepanov and D. E. Rose, From Mathematics to Generic Programming (Addison-Wesley, 2014).

Y. Wang, X. Cao, and Y. Pan, “A study of the routing and spectrum allocation in spectrum-sliced elastic optical path networks,” in IEEE INFOCOM, April 2011, pp. 1503–1511.

A. A. Stepanov and P. McJones, Elements of Programming (Addison-Wesley, 2009).

E. Cetinkaya, M. Alenazi, Y. Cheng, A. Peck, and J. Sterbenz, “On the fitness of geographic graph generators for modelling physical level topologies,” in 5th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), September 2013, pp. 38–45.

F. Gutierrez, E. Varvarigos, and S. Vassiliadis, “Multi-cost routing in max-min fair share networks,” in 38th Annual Allerton Conference on Communications, Control, and Computing, Monticello, Virginia, October 2000, pp. 1294–1304.

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

Fig. 1.
Fig. 1. Example for vertex revisiting and looping.
Fig. 2.
Fig. 2. Example for discarding worse labels.
Fig. 3.
Fig. 3. Simulation results: sample means and maxima of the time taken and memory used by the evaluated algorithms. (a) Time taken for $\gamma = 1$ , and 160 units; (b) time taken for $\gamma = 1$ , and 320 units; (c) time taken for $\gamma = 1$ , and 640 units; (d) time taken for $\gamma = 10$ , and 160 units; (e) time taken for $\gamma = 10$ , and 320 units; (f) time taken for $\gamma = 10$ , and 640 units; (g) memory used for $\gamma = 1$ , and 160 units; (h) memory used for $\gamma = 1$ , and 320 units; (i) memory used for $\gamma = 1$ , and 640 units; (j) memory used for $\gamma = 10$ , and 160 units; (k) memory used for $\gamma = 10$ , and 320 units; (l) memory used for $\gamma = 10$ , and 640 units.
Fig. 4.
Fig. 4. Simulation results: maximum number of required words by the evaluated algorithms. (a) Proposed algorithm; (b) filtered-graphs algorithm; (c) brute-force algorithm.

Tables (6)

Tables Icon

Table 1. Relations between Labels $ {l_i} $ and $ {l_j} $ Depending on their Costs and CUs

Tables Icon

Algorithm 1. Generic Dijkstra

Tables Icon

Table 2. Statistics of the Generated Gabriel Networks

Tables Icon

Table 3. Summary of Algorithm Comparison

Equations (4)

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

λ ( μ ) = μ | E | | Ω | δ α γ .
r m = r M 2 M m .
m ( d ) = M + 1 l o g 2 ( 2 d / r M ) .
n ( b , d ) = { n M ( b ) i f d r M i f r 1 < d n M ( b ) log 2 ( 2 d / r M ) o t h e r w i s e .