Cited By
View all- Yuskov AKulachenko IMelnikov AKochetov Y(2024)Stadium Antennas Deployment OptimizationMathematical Optimization Theory and Operations Research10.1007/978-3-031-62792-7_30(449-461)Online publication date: 30-Jun-2024
Two-Stage Algorithm for Bi-objective Black-Box Traffic Engineering
Pages 110 - 125
Abstract
We have a directed graph describing a network and an origin-destination matrix for customer internet traffic demands. Our aim is to optimize the routing of the traffic by adjusting the weights of the graph links. Though the internal design of the routing protocol is unavailable, we have access to the simulator to model it. Given the link weights, the simulator provides the values for traffic flow on each link. If the flow on a link exceeds its capacity, this link is considered overloaded. The objectives of the problem are to minimize the total number of overloaded links and the distance from the initial weight vector. We have developed a scheme based on a novel integer linear programming model. It uses values of the traffic flow changes depending on the link weights modifications. In the two-stage approach, this scheme is used to provide the initial Pareto set approximation. The approach outperforms the state-of-the-art multi-objective evolutionary algorithms.
References
[1]
Abbasi M, Guleria A, and Devi M Traffic engineering in software defined networks: a survey J. Telecommun. Inf. Technol. 2016 4 3-14
[2]
Altın A, Fortz B, Thorup M, and Ümit H Intra-domain traffic engineering with shortest path routing protocols Ann. Oper. Res. 2013 204 1 65-95
[3]
Athanasiou G, Tsagkaris K, Vlacheas P, Karvounas D, and Demestichas P Multi-objective traffic engineering for future networks IEEE Commun. Lett. 2012 16 1 101-103
[4]
Audet C, Bigeon J, Cartier D, Le Digabel S, and Salomon L Performance indicators in multiobjective optimization Eur. J. Oper. Res. 2021 292 2 397-422
[5]
Audet C and Hare W Derivative-Free and Blackbox Optimization 2017 Cham Springer
[6]
Balon S, Skivée F, and Leduc G Boavida F, Plagemann T, Stiller B, Westphal C, and Monteiro E How well do traffic engineering objective functions meet TE requirements? NETWORKING 2006. Networking Technologies, Services, and Protocols; Performance of Computer and Communication Networks; Mobile and Wireless Communications Systems 2006 Heidelberg Springer 75-86
[7]
Bhatia, R., Hao, F., Kodialam, M., Lakshman, T.: Optimized network traffic engineering using segment routing. In: Proceedings IEEE INFOCOM 2015, pp. 657–665 (2015).
[8]
Blanchy, F., Melon, L., Leduc, G.: Routing in a MPLS network featuring preemption mechanisms. In: ICT 2003: 10th International Conference on Telecommunications, vol. 1, pp. 253–260 (2003).
[9]
Cisco Systems, I.: Internetworking Technologies Handbook, 3rd edn. Cisco Press (2000)
[10]
Corne, D.W., Jerram, N.R., Knowles, J.D., Oates, M.J.: PESA-II: region-based selection in evolutionary multiobjective optimization. In: Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation (GECCO 2001), pp. 283–290 (2001)
[11]
Deb K, Pratap A, Agarwal S, and Meyarivan T A fast and elitist multiobjective genetic algorithm: NSGA-II IEEE Trans. Evol. Comput. 2002 6 2 182-197
[12]
El-Alfy, E.S.: Flow-based path selection for internet traffic engineering with NSGA-II. In: ICT 2010: 17th International Conference on Telecommunications (2010).
[13]
Elwalid, A., Jin, C., Low, S., Widjaja, I.: MATE: MPLS adaptive traffic engineering. In: Proceedings IEEE INFOCOM 2001, vol. 3, pp. 1300–1309 (2001).
[14]
Ericsson M, Resende M, and Pardalos P A genetic algorithm for the weight setting problem in OSPF routing J. Comb. Optim. 2002 6 299-333
[15]
Fortz B, Rexford J, and Thorup M Traffic engineering with traditional IP routing protocols IEEE Commun. Mag. 2002 40 118-124
[16]
Fortz, B., Thorup, M.: Internet traffic engineering by optimizing OSPF weights. In: Proceedings IEEE INFOCOM 2000, vol. 2, pp. 519–528 (2000).
[17]
Fortz B and Thorup M Optimizing OSPF/IS-IS weights in a changing world IEEE J. Sel. Areas Commun. 2002 20 756-767
[18]
Hadka, D.: MOEA framework (2023). https://moeaframework.org
[19]
Hansen P, Mladenović N, Todosijević R, and Hanafi S Variable neighborhood search: basics and variants EURO J. Comput. Optim. 2016 5 3 423-454
[20]
Knowles JD and Corne DW Approximating the nondominated front using the pareto archived evolution strategy Evol. Comput. 2000 8 2 149-172
[21]
Konak A, Coit DW, and Smith AE Multi-objective optimization using genetic algorithms: a tutorial Reliab. Eng. Syst. Saf. 2006 91 9 992-1007
[22]
Lindauer M et al. SMAC3: a versatile Bayesian optimization package for hyperparameter optimization J. Mach. Learn. Res. 2022 23 54 1-9
[23]
Mann HB and Whitney DR On a test of whether one of two random variables is stochastically larger than the other Ann. Math. Stat. 1947 18 1 50-60
[24]
Pereira V, Sousa P, and Rocha M A comparison of multi-objective optimization algorithms for weight setting problems in traffic engineering Nat. Comput. 2022 21 507-522
[25]
Piòro M, Szentesi Á, Harmatos J, Jüttner A, Gajowniczek P, and Kozdrowski S On open shortest path first related network optimisation problems Perform. Eval. 2002 48 1 201-223
[26]
Sousa P, Cortez P, Rio M, and Rocha M Masip-Bruin X, Verchere D, Tsaoussidis V, and Yannuzzi M Traffic engineering approaches using multicriteria optimization techniques Wired/Wireless Internet Communications 2011 Heidelberg Springer 104-115
[27]
Wilcoxon F Individual comparisons by ranking methods Biometrics Bull. 1945 1 6 80-83
[28]
Zitzler, E., Laumanns, M., Thiele, L.: SPEA2: improving the strength pareto evolutionary algorithm. Tech. rep., Inst. f. Technische Informatik und Komm./Computer Eng. and Networks Lab. (2001)
Recommendations
An improved indicator-based two-archive algorithm for many-objective optimization problems
AbstractThe large number of objectives in many-objective optimization problems (MaOPs) has posed significant challenges to the performance of multi-objective evolutionary algorithms (MOEAs) in terms of convergence and diversity. To design a more balanced ...
A two-stage evolutionary algorithm based on three indicators for constrained multi-objective optimization
AbstractOne of the key issues in solving constrained multi-objective optimization problems (CMOPs) is balancing the three indicators of convergence, diversity, and feasibility. We believe at different stages of the evolution, different ...
Highlights- A TSTI method is proposed for the CMOPs.
- Two stages are used in TSTI with ...
A two-stage evolutionary algorithm assisted by multi-archives for constrained multi-objective optimization
AbstractDue to the widespread existence of constrained multi-objective optimization problems (CMOPs) in real life, many researchers start to research the constrained multi-objective evolutionary algorithms (CMOEAs). Therefore, a variety of CMOEAs have ...
Highlights- A MA-TSEA method is develop for CMOPs.
- Two stages are used in MA-TSEA with different purposes.
- Multiple archives assist the MA-TSEA find the complete constraint Pareto front.
- MA-TSEA can achieve better results compared with its ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sep 2023
400 pages
ISBN:978-3-031-47858-1
DOI:10.1007/978-3-031-47859-8
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2023.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 10 November 2023
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 03 Jan 2025
Other Metrics
Citations
Cited By
View all- Yuskov AKulachenko IMelnikov AKochetov Y(2024)Stadium Antennas Deployment OptimizationMathematical Optimization Theory and Operations Research10.1007/978-3-031-62792-7_30(449-461)Online publication date: 30-Jun-2024