Modification of Load Calculation in The Dijkstra Algorithm to Achieve High Throughput and Low Latency on 5G Networks
DOI:
https://doi.org/10.37385/jaets.v5i2.4705Keywords:
5G, Bandwidth, Dijkstra, Latency, Software Defined NetworkAbstract
throughput for high-resolution remote video surveillance. 5G cellular network as today's most advanced wireless technology will be the perfect match for Agriculture 4.0 requirements. In its maturity process, the 5G network requires various optimizations, one of which is by making route algorithm calculation modifications in terms of determining the best route for a data packet from a data source to a data destination. To achieve this goal, it requires research in the form of experiments using network simulator. Software Define Network (SDN) as network programmability is used to modify route in Dijkstra algorithm calculation, and run several use case that simulate 5G network characteristic. By adding bandwidth utilization and latency parameters into the routing algorithm calculations, 5G requirements such as packet loss below 1% and latency below 5ms are successfully achieved. These positive results may be further tested on real 5G networks, if in the future this research also gets positive results in testing on a real 5G network, then cellular network customers will be able to experience an increase in service quality.
Downloads
References
Abdulaziz, A., Adedokun, E. A., & Man-Yahya, S. (2017). Improved extended Dijkstra’s algorithm for software defined networks. International Journal of Applied Information Systems (Online)/International Journal of Applied Information Systems, 12(8), 22–26. https://doi.org/10.5120/ijais2017451714
Albu-Salih, A. T. (2022). Performance evaluation of RYU Controller in software defined networks. Magalla? Al-q?disiyya? Li-?ul?m Al-??sib?t Wa-al-riy??iyy?t, 14(1). https://doi.org/10.29304/jqcm.2022.14.1.879
An, N., Kim, Y., Park, J., Kwon, D., & Lim, H. (2019). Slice management for quality of service differentiation in wireless network slicing. Sensors, 19(12), 2745. https://doi.org/10.3390/s19122745
Araújo, S. O., Peres, R. S., Barata, J., Lidon, F., & Ramalho, J. C. (2021). Characterising the Agriculture 4.0 Landscape—Emerging Trends, challenges and opportunities. Agronomy, 11(4), 667. https://doi.org/10.3390/agronomy11040667
Barakabitze, A. A., Ahmad, A., Mijumbi, R., & Hines, A. (2020). 5G network slicing using SDN and NFV: A survey of taxonomy, architectures and future challenges. Computer Networks, 167, 106984. https://doi.org/10.1016/j.comnet.2019.106984
Bojovi?, P. D., Malbaši?, T., Vujoševi?, D., Marti?, G., & Bojovi?, Ž. (2022). Dynamic QoS Management for a Flexible 5G/6G Network Core: A Step toward a Higher Programmability. Sensors, 22(8), 2849. https://doi.org/10.3390/s22082849
Chao, Y. (2010). A developed Dijkstra algorithm and simulation of urban path search. In 2010 International Conference on Crowd Science and Engineering. https://doi.org/10.1109/iccse.2010.5593700
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms, third edition. MIT Press.
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269–271. https://doi.org/10.1007/bf01386390
Fan, D., & Shi, P. (2010). Improvement of Dijkstra’s algorithm and its application in route planning. 2010 Seventh International Conference on Fuzzy Systems and Knowledge Discovery. https://doi.org/10.1109/fskd.2010.5569452
Fuhao, Z., & Jiping, L. (2009). An algorithm of shortest path based on Dijkstra for huge data. In 2009 Sixth International Conference on Fuzzy Systems and Knowledge Discov, 4, 244–247. https://doi.org/10.1109/fskd.2009.848
Goransson, P., Black, C., & Culver, T. (2016). Software defined networks: A Comprehensive Approach. Morgan Kaufmann.
Goyal, M., Soperi, M., Baccelli, E., Choudhury, G., Shaikh, A., Hosseini, H., & Trivedi, K. (2012). Improving convergence speed and scalability in OSPF: a survey. IEEE Communications Surveys and Tutorials/IEEE Communications Surveys and Tutorials, 14(2), 443–463. https://doi.org/10.1109/surv.2011.011411.00065
Hu, F., Hao, Q., & Bao, K. (2014). A survey on Software-Defined Network and OpenFlow: From Concept to implementation. IEEE Communications Surveys and Tutorials/IEEE Communications Surveys and Tutorials, 16(4), 2181–2206. https://doi.org/10.1109/comst.2014.2326417
Huang, Y., Yi, Q., & Shi, M. (2013). An improved Dijkstra Shortest Path algorithm. Proceedings of the 2nd International Conference on Computer Science and Electronics Engineering. https://doi.org/10.2991/iccsee.2013.59
Jiang, J., Huang, H., Liao, J., & Chen, S. (2014). Extending Dijkstra’s shortest path algorithm for software defined networking. In 2014 16th Asia-Pacific Network Operations and Management Symposium. https://doi.org/10.1109/apnoms.2014.6996609
Kadry, S., Abdallah, A., & Joumaa, C. (2011). On the Optimization of Dijkstra’s Algorithm. In Lecture notes in electrical engineering (pp. 393–397). https://doi.org/10.1007/978-3-642-25992-0_55
Karami, F., & Akhtarkavan, E. (2015). Improving OSPF Protocol based Latency?: A new algorithm based on Dijkstra by using OSPF existing Metrics in SDN networks. Ciência E Natura, 37, 344. https://doi.org/10.5902/2179460x20793
Khachiyan, L., Gurvich, V., & Zhao, J. (2006). Extending Dijkstra’s algorithm to maximize the shortest path by Node-Wise limited arc interdiction. In Lecture notes in computer science (pp. 221–234). https://doi.org/10.1007/11753728_24
Komite Percepatan Penyediaan Infr,astruktur Prioritas (KPPIP). (2019). Indonesia Digital for Future Economy and Inclusive Urban Transformation. Deputy Ministry for Coordination of Infrastructure and Regional Development Acceleration.
Kreutz, D., Ramos, F. M. V., Verissimo, P. E., Rothenberg, C. E., Azodolmolky, S., & Uhlig, S. (2015). Software-Defined Networking: A Comprehensive survey. Proceedings of the IEEE, 103(1), 14–76. https://doi.org/10.1109/jproc.2014.2371999
Lanning, D. R., Harrell, G. K., & Wang, J. (2014). Dijkstra’s algorithm and Google maps. In Proceedings of the 2014 ACM Southeast Regional Conference. https://doi.org/10.1145/2638404.2638494
Luo, M., Hou, X., & Yang, J. (2020). Surface optimal path planning using an extended Dijkstra algorithm. IEEE Access, 8, 147827–147838. https://doi.org/10.1109/access.2020.3015976
M Abdelghany, H., W Zaki, F., M Ashour, M. (2022). Modified Dijkstra Shortest Path Algorithm for SD Networks. International Journal of Electrical and Computer Engineering Systems, 13(3), 203-208. https://doi.org/10.32985/ijeces.13.3.5.
Mehlhorn, K., & Sanders, P. (2008). Algorithms and data structures: The Basic Toolbox. Springer Science & Business Media.
Noto, M., & Sato, H. (2000). A method for the shortest path search by extended Dijkstra algorithm. In 2000 International Conference on Systems, Man and Cybernetics, 3, 2316–2320. https://doi.org/10.1109/icsmc.2000.886462
Palmieri, F. (2020). A Reliability and latency-aware routing framework for 5G transport infrastructures. Computer Networks, 179, 107365.
https://doi.org/10.1016/j.comnet.2020.107365
Sanders, P., & Schultes, D. (2007). Engineering fast route planning algorithms. In Springer eBooks (pp. 23–36). https://doi.org/10.1007/978-3-540-72845-0_2
Sirika, N. S., & Mahajan, N. S. (2016). Survey on Dynamic Routing Protocols. International Journal of Engineering Research and Technology, V5(01).
https://doi.org/10.17577/ijertv5is010028
Shu-Xi, W. (2012). The improved Dijkstra’s Shortest Path algorithm and its application. Procedia Engineering, 29, 1186–1190.
https://doi.org/10.1016/j.proeng.2012.01.110
Sutton, A. (2018). 5G Network Architecture: Enabling the future delivery and consumption of digital media. The ITP (Institute of Telecommunications Professionals) Journal, 12, 9–15.
Szigeti, T., Hattingh, C., Barton, R., & Briley, K. (2013). End-to-end QOS network design. Pearson Education.
Tang, Y., Dananjayan, S., Hou, C., Guo, Q., Luo, S., & He, Y. (2021). A survey on the 5G network and its impact on agriculture: Challenges and opportunities. Computers and Electronics in Agriculture, 180, 105895. https://doi.org/10.1016/j.compag.2020.105895
Wang, R. (2017). A research on the weighted improvement of Dijkstra algorithm in optimal path calculation. In 2017 5th International Conference on Frontiers of Manufacturing Science and Measuring Technology. https://doi.org/10.2991/fmsmt-17.2017.33
Wei, K., Gao, Y., Zhang, W., & Lin, S. (2019). A modified Dijkstra’s algorithm for solving the problem of finding the maximum load path. In 2019 Proceedings of the International Conference on Information and Communication Technology. https://doi.org/10.1109/infoct.2019.8711024
Wenzheng, L., Junjun, L., & Shunli, Y. (2019). An improved Dijkstra’s algorithm for shortest path planning on 2D grid maps. In 2019 International Conference on Electronics Information and Emergency Communication, 438–441. https://doi.org/10.1109/iceiec.2019.8784487
Wu, Q., Qin, G., & Li, H. (2015). An improved Dijkstra’s algorithm application to multi-core processors. Metal Journal, 9, 76–81. https://www.metaljournal.com.ua/assets/Journal/ english-edition/MMI_2015_9/012_Qiong-Wu.pdf
Xiao, N. J., & Lu, N. F. (2010). An improvement of the shortest path algorithm based on Dijkstra algorithm. In International Conference on Computer and Automation Engineering, 383–385. https://doi.org/10.1109/iccae.2010.5451564
Xu, M., Liu, Y., Huang, Q., Zhang, Y., & Luan, G. (2007). An improved Dijkstra’s shortest path algorithm for sparse network. Applied Mathematics and Computation, 185(1), 247–254. https://doi.org/10.1016/j.amc.2006.06.094
Zhang, W., Jiang, C., & Ma, Y. (2012). An Improved Dijkstra Algorithm Based on Pairing Heap. In 2012 Fifth International Symposium on Computational Intelligence and Design, 2, 419–422. https://doi.org/10.1109/iscid.2012.260
CITEDNESS IN SCOPUS
CITEDNESS IN WOS
