NDRA: An Efficient Multi-Objective Optimal Routing Algorithm Using Pareto Domination
Pages 19 - 24
Abstract
Rapid advancements in the Internet have presented new demands for next-generation communication networks. Despite promising techniques such as APN6 and SRV6 have been proposed, research on multi-objective optimal routing, which serves as the fundamental basis for differentiated service delivery, remains limited. Consequently, this paper aims to bridge this research gap by introducing an efficient routing algorithm, NDRA, for multi-objective optimization. The proposed algorithm utilizes the Dijkstra algorithm as the backbone. Besides, a pruning process referring to the term of Pareto domination is introduced to avoid unnecessary path exploration. Evaluations demonstrate that compared to existing methods, our algorithm guarantees that a set of optimal solutions will be found and the computational overhead is affordable across different network scenarios.
References
[1]
Hajar Hantouti, Nabil Benamar, Tarik Taleb, and Abdelquoddous Laghrissi. Traffic steering for service function chaining. IEEE Communications Surveys & Tutorials, 21(1): 487--507, 2018.
[2]
Gang Wu, Chenyang Yang, Shaoqian Li, and Geoffrey Ye Li. Recent advances in energy-efficient networks and their application in 5g systems. IEEE Wireless Communications, 22(2): 145--151, 2015.
[3]
David D Clark and Wenjia Fang. Explicit allocation of best-effort packet delivery service. IEEE/ACM Transactions on networking, 6(4): 362--373, 1998.
[4]
Fetia Bannour, Sami Souihi, and Abdelhamid Mellouk. Distributed sdn control: Survey, taxonomy, and challenges. IEEE Communications Surveys & Tutorials, 20(1): 333--354, 2018.
[5]
Rashid Amin, Martin Reisslein, and Nadir Shah. Hybrid sdn networks: A survey of existing approaches. IEEE Communications Surveys & Tutorials, 20(4): 3259--3306, 2018.
[6]
Thomas M Chen and Tae H Oh. Reliable services in mpls. IEEE Communications Magazine, 37(12): 58--62, 1999.
[7]
Xipeng Xiao, Alan Hannan, Brook Bailey, and Lionel M Ni. Traffic engineering with mpls in the internet. IEEE network, 14(2): 28--33, 2000.
[8]
Sandra Zajac and Sandra Huber. Objectives and methods in multi-objective routing problems: a survey and classification scheme. European Journal of Operational Research, 290(1): 1--25, 2021.
[9]
Jochen W Guck, Amaury Van Bemten, Martin Reisslein, and Wolfgang Kellerer. Unicast qos routing algorithms for sdn: A comprehensive survey and performance evaluation. IEEE Communications Surveys & Tutorials, 20(1): 388--415, 2017.
[10]
Gang Feng and Turgay Korkmaz. Finding multi-constrained multiple shortest paths. IEEE Transactions on Computers, 64(9): 2559--2572, 2014.
[11]
Aditya Pathak, Irfan Al-Anbagi, and Howard J Hamilton. An adaptive qos and trust-based lightweight secure routing algorithm for wsns. IEEE Internet of Things Journal, 9(23): 23826--23840, 2022.
[12]
R. Murugeswari, sridhar radhakrishnan, and D. Devaraj. A multi-objective evolutionary algorithm based qos routing in wireless mesh networks. Applied Soft Computing, 40: 517--525, 2016.
[13]
Gang Liu and K. G. Ramakrishnan. Aprune: an algorithm for finding k shortest paths subject to multiple constraints. IEEE International Conference on Computer Communications, 2: 743--749, 2001.
[14]
Turgay Korkmaz and Marwan Krunz. Multi-constrained optimal path selection. IEEE International Conference on Computer Communications, 2: 834--843, 2001.
[15]
Mahmoud Hashem Eiza, Thomas Owens, and Qiang Ni. Secure and robust multi-constrained qos aware routing algorithm for vanets. IEEE Transactions on Dependable and Secure Computing, 13(1): 32--45, 2015.
[16]
Shaoyong Guo, Yao Dai, Siya Xu, Xuesong Qiu, and Feng Qi. Trusted cloud-edge network resource management: Drl-driven service function chain orchestration for iot. IEEE Internet of Things Journal, 7(7): 6010--6022, 2019.
[17]
Yunyun Niu, Jie Shao, Jianhua Xiao, Wen Song, and Zhiguang Cao. Multi-objective evolutionary algorithm based on rbf network for solving the stochastic vehicle routing problem. Information Sciences, 609: 387--410, 2022.
[18]
Randeep Bhatia, Fang Hao, Murali Kodialam, and TV Lakshman. Optimized network traffic engineering using segment routing. In 2015 IEEE Conference on Computer Communications, 657--665, 2015.
Index Terms
- NDRA: An Efficient Multi-Objective Optimal Routing Algorithm Using Pareto Domination
Recommendations
Inverted PBI in MOEA/D and its impact on the search performance on multi and many-objective optimization
GECCO '14: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary ComputationMOEA/D decomposes a multi-objective optimization problem into a number of single objective optimization problems. Each single objective optimization problem is defined by a scalarizing function using a weight vector. In MOEA/D, there are several ...
A numerical method for constructing the Pareto front of multi-objective optimization problems
In this paper, a new numerical method is presented for constructing an approximation of the Pareto front of multi-objective optimization problems. This method is based on the well-known scalarization approach by Pascoletti and Serafini. The proposed ...
Multimodal scalarized preferences in multi-objective optimization
GECCO '17: Proceedings of the Genetic and Evolutionary Computation ConferenceScalarization functions represent preferences in multi-objective optimization by mapping the vector of objectives to a single real value. Optimization techniques using scalarized preferences mainly focus on obtaining only a single global preference ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
October 2023
41 pages
ISBN:9798400703416
DOI:10.1145/3615587
Copyright © 2023 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 02 October 2023
Check for updates
Author Tags
Qualifiers
- Short-paper
- Research
- Refereed limited
Conference
ACM MobiCom '23
Sponsor:
ACM MobiCom '23: The 29th Annual International Conference on Mobile Computing and Networking
October 6, 2023
Madrid, Spain
Acceptance Rates
Overall Acceptance Rate 47 of 92 submissions, 51%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 55Total Downloads
- Downloads (Last 12 months)27
- Downloads (Last 6 weeks)0
Reflects downloads up to 10 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in