An Optimised Shortest Path Algorithm for Network Rotuting & SDN Improvement on Bellman-Ford Algorithm

Article Sidebar

PDF
Published: Aug 18, 2023
DOI: https://doi.org/10.17762/ijritcc.v11i8s.7172
Keywords:
Network Routing, Routing Algorithms, SDN Routing, Algorithm optimization, Bellman Ford, SPFA

Main Article Content

Mohit Chandra Saxena
Author, SCSE Galgotias University, Greater Noida, India
Munish Sabharwal
Dean, SCSE Galgotias University, Greater Noida, India
Preeti Bajaj
Vice Chancellor, Lovely Professional University, Punjab, India

Abstract

Network routing algorithms form the backbone of data transmission in modern network architectures, with implications for efficiency, speed, and reliability. This research aims to critically investigate and compare three prominent routing algorithms: Bellman-Ford, Shortest Path Faster Algorithm (SPFA), and our novel improved variant of Bellman-Ford, the Space-efficient Cost-Balancing Bellman-Ford (SCBF). We evaluate the performance of these algorithms in terms of time and space complexity, memory utilization, and routing efficacy, within a simulated network environment. Our results indicate that while Bellman-Ford provides consistent performance, both SPFA and SCBF present improvements in specific scenarios with the SCBF showing notable enhancements in space efficiency. The innovative SCBF algorithm provides competitive performance and greater space efficiency, potentially making it a valuable contribution to the development of network routing protocols. Further research is encouraged to optimize and evaluate these algorithms in real-world network conditions. This study underscores the continuous need for algorithmic innovation in response to evolving network demands.

Article Details

How to Cite
Saxena, M. C. ., Sabharwal, M. ., & Bajaj, P. . (2023). An Optimised Shortest Path Algorithm for Network Rotuting & SDN: Improvement on Bellman-Ford Algorithm. International Journal on Recent and Innovation Trends in Computing and Communication, 11(8s), 20–31. https://doi.org/10.17762/ijritcc.v11i8s.7172
Issue
Vol. 11 No. 8s (2023)
Section
Articles

References

Medhi, D., & Ramasamy, K. (2017). Network routing: algorithms, protocols, and architectures. Morgan Kaufmann.

Gu, Y., & Grossman, R. L. (2007). UDT: UDP-based data transfer for high-speed wide area networks. Computer Networks, 51(7), 1777-1799.

Ahuja, R. K., Mehlhorn, K., Orlin, J., & Tarjan, R. E. (1990). Faster algorithms for the shortest path problem. Journal of the ACM (JACM), 37(2), 213-223.

Brandes, Ulrik. "A faster algorithm for betweenness centrality." Journal of mathematical sociology 25.2 (2001): 163-177.

J. Clerk Maxwell, A Treatise on Electricity and Magnetism, 3rd ed., vol. 2. Oxford: Clarendon, 1892, pp.68–73.

Sungwon Jung and S. Pramanik, "An efficient path computation model for hierarchically structured topographical road maps," in IEEE Transactions on Knowledge and Data Engineering, vol. 14, no. 5, pp. 1029-1046, Sept.-Oct. 2002, doi: 10.1109/TKDE.2002.1033772.I.

Abraham, C. Gavoille, A. V. Goldberg and D. Malkhi, "Routing in Networks with Low Doubling Dimension," 26th IEEE International Conference on Distributed Computing Systems (ICDCS'06), Lisboa, Portugal, 2006, pp. 75-75, doi: 10.1109/ICDCS.2006.72.

N. Futamura, R. Sangireddy, S. Aluru and A. K. Somani, "Scalable, memory efficient, high-speed lookup and update algorithms for IP routing," Proceedings. 12th International Conference on Computer Communications and Networks (IEEE Cat. No.03EX712), Dallas, TX, USA, 2003, pp. 257-263, doi: 10.1109/ICCCN.2003.1284179.

Zheng Wang and Jon Crowcroft. 1992. Analysis of shortest-path routing algorithms in a dynamic network environment. SIGCOMM Comput. Commun. Rev. 22, 2 (April 1992), 63–71. https://doi.org/10.1145/141800.141805

Madduri, K., Bader, D. A., Berry, J. W., & Crobak, J. R. (2007, January). An experimental study of a parallel shortest path algorithm for solving large-scale graph instances. In 2007 Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments (ALENEX) (pp. 23-35). Society for Industrial and Applied Mathematics.

Matti Virtanen, Jan de Vries, Thomas Müller, Daniel Müller, Giovanni Rossi. Machine Learning for Intelligent Feedback Generation in Online Courses . Kuwait Journal of Machine Learning, 2(2). Retrieved from http://kuwaitjournals.com/index.php/kjml/article/view/188

Pettie, S. (2004). A new approach to all-pairs shortest paths on real-weighted graphs. Theoretical Computer Science, 312(1), 47-74.

Dijkstra, E. W. (2022). A note on two problems in connexion with graphs. In Edsger Wybe Dijkstra: His Life, Work, and Legacy (pp. 287-290).

Fredman, M. L., & Tarjan, R. E. (1987). Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM (JACM), 34(3), 596-615.

Dinitz, Y., & Itzhak, R. (2017). Hybrid Bellman–Ford–Dijkstra algorithm. Journal of DiscreteAlgorithms, 42, 35–44. doi:10.1016/j.jda.2017.01.001.

Lacorte, A. M., & Chavez, E. P. (2018). Analysis on the Use of A* and Dijkstra’s Algorithms for Intelligent School Transport Route Optimization System. Proceedings of the 4th International Conference on Human-Computer Interaction and User Experience in Indonesia, CHIuXiD ’18 -CHIuXiD ’18. doi:10.1145/3205946.3205948

Ahammad, D. S. H. ., & Yathiraju, D. . (2021). Maternity Risk Prediction Using IOT Module with Wearable Sensor and Deep Learning Based Feature Extraction and Classification Technique. Research Journal of Computer Systems and Engineering, 2(1), 40:45. Retrieved from https://technicaljournals.org/RJCSE/index.php/journal/article/view/19

Luca Ferrari, Deep Learning Techniques for Natural Language Translation , Machine Learning Applications Conference Proceedings, Vol 2 2022.

Abbas, Q., Hussain, Q., Zia, T. & Mansoor, A. (2018). Reduced Solution Set Shortest Path Problem: Capton Algoritm With Special Reference To Dijkstra’s Algorithm. Malaysian Journal of Computer Science, [S.l.], v. 31, n. 3, p. 175-187, july 2018. ISSN 0127-9084

Sapundzhi, F. I., Popstoilov, M. S. (2018). Optimization algorithms for finding the shortest paths. Bulgarian Chemical Communications, Volume 50, Special Issue B, (pp. 115 – 120)

Geetha M., Karegowda, A. G. ., Nandeesha, & Nagaraj B. V. (2023). Classification of Sentinel 2 Images using Customized Convolution Neural Networks. International Journal of Intelligent Systems and Applications in Engineering, 11(1s), 136–142. Retrieved from https://ijisae.org/index.php/IJISAE/article/view/2485

Oyola, A., Romero, D. G., & Vintimilla, B. X. (2017). A Dijkstra-Based Algorithm for Selecting the Shortest-Safe Evacuation Routes in Dynamic Environments (SSER). Lecture Notes in Computer Science, 131–135. doi:10.1007/978-3-319-60042-0_15.

Singh, J.B., Tripathi, R.C. (2018). Investigation of Bellman–Ford Algorithm, Dijkstra's Algorithm for suitability of SPP. IJEDR | Volume 6, Issue 1 | ISSN: 2321-9939

Lacorte, A. M., & Chavez, E. P. (2018). Analysis on the Use of A* and Dijkstra’s Algorithms for Intelligent School Transport Route Optimization System. Proceedings of the 4th International Conference on Human-Computer Interaction and User Experience in Indonesia, CHIuXiD ’18 - CHIuXiD ’18. doi:10.1145/3205946.3205948

] Chan, S., Adnan, N., Sukri, S.S., & Zainon, W.M. (2016). An experiment on the performance of shortest path algorithm.Knowledge Management International Conference (KMICe) 2016, 29 – 30 August 2016, Chiang Mai, Thailand

M. C. Saxena and P. Bajaj, "Evolution of Wide Area network from Circuit Switched to Digital Software defined Network," 2021 International Conference on Technological Advancements and Innovations (ICTAI), Tashkent, Uzbekistan, 2021, pp. 351-357, doi: 10.1109/ICTAI53825.2021.9673201.

Samah W.G. AbuSalim et al 2020 IOP Conf. Ser.: Mater. Sci. Eng. 917 012077

Wang, X. Z. (2018, September). The comparison of three algorithms in shortest path issue. In Journal of Physics: Conference Series (Vol. 1087, No. 2, p. 022011). IOP Publishing.

Zhu, Z., Zhang, Z., Xhonneux, L. P., & Tang, J. (2021). Neural bellman-ford networks: A general graph neural network framework for link prediction. Advances in Neural Information Processing Systems, 34, 29476-29490.

Cherkassky, B. V., Goldberg, A. V., & Radzik, T. (1996). Shortest paths algorithms: Theory and experimental evaluation. Mathematical programming, 73(2), 129-174.

Duan, F. (1994). A faster algorithm for shortest-path—SPFA. Journal of Southwest Jiaotong University, 29(2), 207-212.

Marina, M. K., & Das, S. R. (2002). Ad hoc on-demand multipath distance vector routing. ACM SIGMOBILE Mobile Computing and Communications Review, 6(3), 92-93.

Hedrick, C. L. (1988). Routing information protocol (No. rfc1058).

Yen, J. Y. (1971). Finding the k shortest loopless paths in a network. management Science, 17(11), 712-716.

Zhang, W., Chen, H., Jiang, C., & Zhu, L. (2013, August). Improvement and experimental evaluation bellman-ford algorithm. In 2013 International Conference on Advanced ICT and Education (ICAICTE-13) (pp. 138-141). Atlantis Press.

Zhang, H., Liu, X., & Xiang, L. (2019, August). Improved SPFA algorithm based on Cell-like P system. In 2019 10th International Conference on Information Technology in Medicine and Education (ITME) (pp. 679-683). IEEE.

Mohit Saxena. (2023). Bellman_Ford-Enhanced-SCBF-SPFA-Comparison [Source code]. GitHub. https://github.com/m22aie240/Bellman_Ford-Enhanced-SCBF-SPFA-Comparison

Short-Circuiting Bellman-Ford (SCBF) Zhou, X. (2014). An Improved SPFA Algorithm for Single-Source Shortest Path Problem Using Forward Star Data Structure. International Journal of Managing Information Technology (IJMIT) Vol, 6.

Chivers, I., Sleightholme, J., Chivers, I., & Sleightholme, J. (2015). An introduction to Algorithms and the Big O Notation. Introduction to Programming with Fortran: With Coverage of Fortran 90, 95, 2003, 2008 and 77, 359-364.