TY - GEN

T1 - Two-Stage Algorithm for Bi-objective Black-Box Traffic Engineering

AU - Yuskov, Alexander

AU - Kulachenko, Igor

AU - Melnikov, Andrey

AU - Kochetov, Yury

N1 - The study was carried out within the framework of the state contract of the Sobolev Institute of Mathematics (project FWNF-2022-0019).

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

UR - https://www.mendeley.com/catalogue/095e07f3-ec65-3e15-a859-51a4884d454d/

U2 - 10.1007/978-3-031-47859-8_9

DO - 10.1007/978-3-031-47859-8_9

M3 - Conference contribution

SN - 978-303147858-1

VL - 14395

SP - 110

EP - 125

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

PB - Springer Science and Business Media Deutschland GmbH

ER -