Improved monte carlo tree search for virtual network embedding

Maxime Elkael; Hind Castel-Taleb; Badii Jouaber; Andrea Araldo; Massinissa Ait Aba

doi:10.1109/LCN52139.2021.9524975

Improved monte carlo tree search for virtual network embedding

Maxime Elkael
, Hind Castel-Taleb
, Badii Jouaber
, Andrea Araldo
, Massinissa Ait Aba

CNRS UMR 5157 SAMOVAR
Davidson Consulting

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

In this paper, we consider the Virtual Network Embedding (VNE) problem for 5G networks slicing. This consists in optimally allocating multiple Virtual Networks (VN) on a substrate virtualized physical network while maximizing among others, resource utilization, maximum number of placed VNs and network operator's benefit. We solve the online version of the problem where slices arrive over time. We propose the use of the Nested Rollout Policy Adaptation (NRPA) algorithm, a variant of the well known Monte Carlo Tree Search (MCTS). Both algorithms learn by randomly simulating the embedding, but NRPA also learns how to perform better simulations over time. Performance analysis with different scenarios, show that NRPA improves acceptance and reward ratios (by up to 69% and 65%). We also show how a smart initialization of the learning process can help improve the results furthermore (up to a 12.5% increase of acceptance ratio).

Original language	English
Title of host publication	Proceedings of the IEEE 46th Conference on Local Computer Networks, LCN 2021
Editors	Lyes Khoukhi, Sharief Oteafy, Eyuphan Bulut
Publisher	IEEE Computer Society
Pages	605-612
Number of pages	8
ISBN (Electronic)	9780738124766
DOIs	https://doi.org/10.1109/LCN52139.2021.9524975
Publication status	Published - 4 Oct 2021
Event	46th IEEE Conference on Local Computer Networks, LCN 2021 - Edmonton, Canada Duration: 4 Oct 2021 → 7 Oct 2021

Publication series

Name	Proceedings - Conference on Local Computer Networks, LCN
Volume	2021-October

Conference

Conference	46th IEEE Conference on Local Computer Networks, LCN 2021
Country/Territory	Canada
City	Edmonton
Period	4/10/21 → 7/10/21

Keywords

5G slicing
AI-enabled networking
Cloud Computing and Networking
Quality of Service
Reinforcement Learning
Virtual Network Embedding

Access to Document

10.1109/LCN52139.2021.9524975

Cite this

Elkael, M., Castel-Taleb, H., Jouaber, B., Araldo, A., & Aba, M. A. (2021). Improved monte carlo tree search for virtual network embedding. In L. Khoukhi, S. Oteafy, & E. Bulut (Eds.), Proceedings of the IEEE 46th Conference on Local Computer Networks, LCN 2021 (pp. 605-612). (Proceedings - Conference on Local Computer Networks, LCN; Vol. 2021-October). IEEE Computer Society. https://doi.org/10.1109/LCN52139.2021.9524975

@inproceedings{66cfd38d4398434ca5227a3dcdeaf656,

title = "Improved monte carlo tree search for virtual network embedding",

abstract = "In this paper, we consider the Virtual Network Embedding (VNE) problem for 5G networks slicing. This consists in optimally allocating multiple Virtual Networks (VN) on a substrate virtualized physical network while maximizing among others, resource utilization, maximum number of placed VNs and network operator's benefit. We solve the online version of the problem where slices arrive over time. We propose the use of the Nested Rollout Policy Adaptation (NRPA) algorithm, a variant of the well known Monte Carlo Tree Search (MCTS). Both algorithms learn by randomly simulating the embedding, but NRPA also learns how to perform better simulations over time. Performance analysis with different scenarios, show that NRPA improves acceptance and reward ratios (by up to 69\% and 65\%). We also show how a smart initialization of the learning process can help improve the results furthermore (up to a 12.5\% increase of acceptance ratio).",

keywords = "5G slicing, AI-enabled networking, Cloud Computing and Networking, Quality of Service, Reinforcement Learning, Virtual Network Embedding",

author = "Maxime Elkael and Hind Castel-Taleb and Badii Jouaber and Andrea Araldo and Aba, \{Massinissa Ait\}",

note = "Publisher Copyright: {\textcopyright} 2021 IEEE.; 46th IEEE Conference on Local Computer Networks, LCN 2021 ; Conference date: 04-10-2021 Through 07-10-2021",

year = "2021",

month = oct,

day = "4",

doi = "10.1109/LCN52139.2021.9524975",

language = "English",

series = "Proceedings - Conference on Local Computer Networks, LCN",

publisher = "IEEE Computer Society",

pages = "605--612",

editor = "Lyes Khoukhi and Sharief Oteafy and Eyuphan Bulut",

booktitle = "Proceedings of the IEEE 46th Conference on Local Computer Networks, LCN 2021",

}

Elkael, M, Castel-Taleb, H, Jouaber, B , Araldo, A & Aba, MA 2021, Improved monte carlo tree search for virtual network embedding. in L Khoukhi, S Oteafy & E Bulut (eds), Proceedings of the IEEE 46th Conference on Local Computer Networks, LCN 2021. Proceedings - Conference on Local Computer Networks, LCN, vol. 2021-October, IEEE Computer Society, pp. 605-612, 46th IEEE Conference on Local Computer Networks, LCN 2021, Edmonton, Canada, 4/10/21. https://doi.org/10.1109/LCN52139.2021.9524975

Improved monte carlo tree search for virtual network embedding. / Elkael, Maxime; Castel-Taleb, Hind; Jouaber, Badii et al.
Proceedings of the IEEE 46th Conference on Local Computer Networks, LCN 2021. ed. / Lyes Khoukhi; Sharief Oteafy; Eyuphan Bulut. IEEE Computer Society, 2021. p. 605-612 (Proceedings - Conference on Local Computer Networks, LCN; Vol. 2021-October).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Improved monte carlo tree search for virtual network embedding

AU - Elkael, Maxime

AU - Castel-Taleb, Hind

AU - Jouaber, Badii

AU - Araldo, Andrea

AU - Aba, Massinissa Ait

PY - 2021/10/4

Y1 - 2021/10/4

N2 - In this paper, we consider the Virtual Network Embedding (VNE) problem for 5G networks slicing. This consists in optimally allocating multiple Virtual Networks (VN) on a substrate virtualized physical network while maximizing among others, resource utilization, maximum number of placed VNs and network operator's benefit. We solve the online version of the problem where slices arrive over time. We propose the use of the Nested Rollout Policy Adaptation (NRPA) algorithm, a variant of the well known Monte Carlo Tree Search (MCTS). Both algorithms learn by randomly simulating the embedding, but NRPA also learns how to perform better simulations over time. Performance analysis with different scenarios, show that NRPA improves acceptance and reward ratios (by up to 69% and 65%). We also show how a smart initialization of the learning process can help improve the results furthermore (up to a 12.5% increase of acceptance ratio).

AB - In this paper, we consider the Virtual Network Embedding (VNE) problem for 5G networks slicing. This consists in optimally allocating multiple Virtual Networks (VN) on a substrate virtualized physical network while maximizing among others, resource utilization, maximum number of placed VNs and network operator's benefit. We solve the online version of the problem where slices arrive over time. We propose the use of the Nested Rollout Policy Adaptation (NRPA) algorithm, a variant of the well known Monte Carlo Tree Search (MCTS). Both algorithms learn by randomly simulating the embedding, but NRPA also learns how to perform better simulations over time. Performance analysis with different scenarios, show that NRPA improves acceptance and reward ratios (by up to 69% and 65%). We also show how a smart initialization of the learning process can help improve the results furthermore (up to a 12.5% increase of acceptance ratio).

KW - 5G slicing

KW - AI-enabled networking

KW - Cloud Computing and Networking

KW - Quality of Service

KW - Reinforcement Learning

KW - Virtual Network Embedding

U2 - 10.1109/LCN52139.2021.9524975

DO - 10.1109/LCN52139.2021.9524975

M3 - Conference contribution

AN - SCOPUS:85118440780

T3 - Proceedings - Conference on Local Computer Networks, LCN

SP - 605

EP - 612

BT - Proceedings of the IEEE 46th Conference on Local Computer Networks, LCN 2021

A2 - Khoukhi, Lyes

A2 - Oteafy, Sharief

A2 - Bulut, Eyuphan

PB - IEEE Computer Society

T2 - 46th IEEE Conference on Local Computer Networks, LCN 2021

Y2 - 4 October 2021 through 7 October 2021

ER -

Elkael M, Castel-Taleb H, Jouaber B , Araldo A, Aba MA. Improved monte carlo tree search for virtual network embedding. In Khoukhi L, Oteafy S, Bulut E, editors, Proceedings of the IEEE 46th Conference on Local Computer Networks, LCN 2021. IEEE Computer Society. 2021. p. 605-612. (Proceedings - Conference on Local Computer Networks, LCN). doi: 10.1109/LCN52139.2021.9524975

Improved monte carlo tree search for virtual network embedding

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this