Skip to Main content Skip to Navigation
Conference papers

Monte Carlo Search Algorithms for Network Traffic Engineering

Abstract : The aim of Traffic Engineering is to provide routing configurations in networks such that the used resources are minimized while maintaining a high level of quality of service (QoS). Among the optimization problems arising in this domain, we address in this paper the one related to setting weights in networks that are based on shortest path routing protocols (OSPF, IS-IS). Finding weights that induce efficient routing paths (e.g that minimize the maximum congested link) is a computationally hard problem. We propose to use Monte Carlo Search for the first time for this problem. More specifically we apply Nested Rollout Policy Adaptation (NRPA). We also extend NRPA with the force_exploration algorithm to improve the results. In comparison to other algorithms NRPA scales better with the size of the instance and can be easily extended to take into account additional constraints (cost utilization, delay,. . .) or linear/non-linear optimization criteria. For difficult instances the optimum is not known but a lower bound can be computed. NRPA gives results close to the lower bound on a standard dataset of telecommunication networks.
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03346329
Contributor : Pierre-Henri Wuillemin Connect in order to contact the contributor
Submitted on : Friday, September 17, 2021 - 2:17:40 PM
Last modification on : Wednesday, September 22, 2021 - 3:36:08 AM

File

2021-ECML-Monte_Carlo_Search_A...
Files produced by the author(s)

Identifiers

`

Citation

Chen Dang, Cristina Bazgan, Tristan Cazenave, Morgan Chopin, Pierre-Henri Wuillemin. Monte Carlo Search Algorithms for Network Traffic Engineering. ECML-PKDD 2021, Sep 2021, Bilbao, Spain. pp.486-501, ⟨10.1007/978-3-030-86514-6_30⟩. ⟨hal-03346329v2⟩

Share

Metrics

Record views

33

Files downloads

60