A novel virtual network embedding scheme based on Gomory-Hu tree within cloud's backbone

Oussama Soualah; Ilhem Fajjari; Makhlouf Hadji; Nadjib Aitsaadi; Djamal Zeghlache

doi:10.1109/NOMS.2016.7502855

A novel virtual network embedding scheme based on Gomory-Hu tree within cloud's backbone

Oussama Soualah
, Ilhem Fajjari
, Makhlouf Hadji
, Nadjib Aitsaadi
, Djamal Zeghlache

CNRS SAMOVAR UMR 5157
Orange Labs
IRT SystemX
Université de PARIS XII

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

11 Citations (Scopus)

Abstract

We address the online virtual network embedding problem within the Cloud's backbone to optimally map the virtual routers and links in the substrate network in order to maximize the Cloud's provider revenue. Since the problem is NP-hard, we propose a novel approach, named VNE-GH, to significantly reduce the problem size using the Gomory-Hu transformation without losing useful information on the virtual network embedding problem. Starting from the Gomory-Hu compact tree structure, we formulate the virtual network embedding as an Integer Linear Program and resolve the reduced size problem using the branch- and-cut algorithm. Results obtained via extensive simulations show that VNE-GH outperforms the most prominent related work strategies in terms of i) acceptance rate of virtual network requests and ii) Cloud provider's revenue.

Original language	English
Title of host publication	Proceedings of the NOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium
Editors	Sema Oktug Badonnel, Mehmet Ulema, Cicek Cavdar, Lisandro Zambenedetti Granville, Carlos Raniery P. dos Santos
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	536-542
Number of pages	7
ISBN (Electronic)	9781509002238
DOIs	https://doi.org/10.1109/NOMS.2016.7502855
Publication status	Published - 30 Jun 2016
Externally published	Yes
Event	2016 IEEE/IFIP Network Operations and Management Symposium, NOMS 2016 - Istanbul, Turkey Duration: 25 Apr 2016 → 29 Apr 2016

Publication series

Name	Proceedings of the NOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium

Conference

Conference	2016 IEEE/IFIP Network Operations and Management Symposium, NOMS 2016
Country/Territory	Turkey
City	Istanbul
Period	25/04/16 → 29/04/16

Keywords

Cloud networking
Gomory-Hu tree
Integer linear programming
NaaS
Virtual network embedding

Access to Document

10.1109/NOMS.2016.7502855

Cite this

Soualah, O., Fajjari, I., Hadji, M., Aitsaadi, N., & Zeghlache, D. (2016). A novel virtual network embedding scheme based on Gomory-Hu tree within cloud's backbone. In S. O. Badonnel, M. Ulema, C. Cavdar, L. Z. Granville, & C. R. P. dos Santos (Eds.), Proceedings of the NOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium (pp. 536-542). Article 7502855 (Proceedings of the NOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/NOMS.2016.7502855

Soualah, Oussama ; Fajjari, Ilhem ; Hadji, Makhlouf et al. / A novel virtual network embedding scheme based on Gomory-Hu tree within cloud's backbone. Proceedings of the NOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium. editor / Sema Oktug Badonnel ; Mehmet Ulema ; Cicek Cavdar ; Lisandro Zambenedetti Granville ; Carlos Raniery P. dos Santos. Institute of Electrical and Electronics Engineers Inc., 2016. pp. 536-542 (Proceedings of the NOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium).

@inproceedings{7e73fe57ec7c4d598bdc8f41c0bb09dd,

title = "A novel virtual network embedding scheme based on Gomory-Hu tree within cloud's backbone",

abstract = "We address the online virtual network embedding problem within the Cloud's backbone to optimally map the virtual routers and links in the substrate network in order to maximize the Cloud's provider revenue. Since the problem is NP-hard, we propose a novel approach, named VNE-GH, to significantly reduce the problem size using the Gomory-Hu transformation without losing useful information on the virtual network embedding problem. Starting from the Gomory-Hu compact tree structure, we formulate the virtual network embedding as an Integer Linear Program and resolve the reduced size problem using the branch- and-cut algorithm. Results obtained via extensive simulations show that VNE-GH outperforms the most prominent related work strategies in terms of i) acceptance rate of virtual network requests and ii) Cloud provider's revenue.",

keywords = "Cloud networking, Gomory-Hu tree, Integer linear programming, NaaS, Virtual network embedding",

author = "Oussama Soualah and Ilhem Fajjari and Makhlouf Hadji and Nadjib Aitsaadi and Djamal Zeghlache",

note = "Publisher Copyright: {\textcopyright} 2016 IEEE.; 2016 IEEE/IFIP Network Operations and Management Symposium, NOMS 2016 ; Conference date: 25-04-2016 Through 29-04-2016",

year = "2016",

month = jun,

day = "30",

doi = "10.1109/NOMS.2016.7502855",

language = "English",

series = "Proceedings of the NOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "536--542",

editor = "Badonnel, \{Sema Oktug\} and Mehmet Ulema and Cicek Cavdar and Granville, \{Lisandro Zambenedetti\} and \{dos Santos\}, \{Carlos Raniery P.\}",

booktitle = "Proceedings of the NOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium",

}

Soualah, O, Fajjari, I, Hadji, M, Aitsaadi, N & Zeghlache, D 2016, A novel virtual network embedding scheme based on Gomory-Hu tree within cloud's backbone. in SO Badonnel, M Ulema, C Cavdar, LZ Granville & CRP dos Santos (eds), Proceedings of the NOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium., 7502855, Proceedings of the NOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium, Institute of Electrical and Electronics Engineers Inc., pp. 536-542, 2016 IEEE/IFIP Network Operations and Management Symposium, NOMS 2016, Istanbul, Turkey, 25/04/16. https://doi.org/10.1109/NOMS.2016.7502855

A novel virtual network embedding scheme based on Gomory-Hu tree within cloud's backbone. / Soualah, Oussama; Fajjari, Ilhem; Hadji, Makhlouf et al.
Proceedings of the NOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium. ed. / Sema Oktug Badonnel; Mehmet Ulema; Cicek Cavdar; Lisandro Zambenedetti Granville; Carlos Raniery P. dos Santos. Institute of Electrical and Electronics Engineers Inc., 2016. p. 536-542 7502855 (Proceedings of the NOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium).

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

TY - GEN

T1 - A novel virtual network embedding scheme based on Gomory-Hu tree within cloud's backbone

AU - Soualah, Oussama

AU - Fajjari, Ilhem

AU - Hadji, Makhlouf

AU - Aitsaadi, Nadjib

AU - Zeghlache, Djamal

PY - 2016/6/30

Y1 - 2016/6/30

N2 - We address the online virtual network embedding problem within the Cloud's backbone to optimally map the virtual routers and links in the substrate network in order to maximize the Cloud's provider revenue. Since the problem is NP-hard, we propose a novel approach, named VNE-GH, to significantly reduce the problem size using the Gomory-Hu transformation without losing useful information on the virtual network embedding problem. Starting from the Gomory-Hu compact tree structure, we formulate the virtual network embedding as an Integer Linear Program and resolve the reduced size problem using the branch- and-cut algorithm. Results obtained via extensive simulations show that VNE-GH outperforms the most prominent related work strategies in terms of i) acceptance rate of virtual network requests and ii) Cloud provider's revenue.

AB - We address the online virtual network embedding problem within the Cloud's backbone to optimally map the virtual routers and links in the substrate network in order to maximize the Cloud's provider revenue. Since the problem is NP-hard, we propose a novel approach, named VNE-GH, to significantly reduce the problem size using the Gomory-Hu transformation without losing useful information on the virtual network embedding problem. Starting from the Gomory-Hu compact tree structure, we formulate the virtual network embedding as an Integer Linear Program and resolve the reduced size problem using the branch- and-cut algorithm. Results obtained via extensive simulations show that VNE-GH outperforms the most prominent related work strategies in terms of i) acceptance rate of virtual network requests and ii) Cloud provider's revenue.

KW - Cloud networking

KW - Gomory-Hu tree

KW - Integer linear programming

KW - NaaS

KW - Virtual network embedding

U2 - 10.1109/NOMS.2016.7502855

DO - 10.1109/NOMS.2016.7502855

M3 - Conference contribution

AN - SCOPUS:84979769168

T3 - Proceedings of the NOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium

SP - 536

EP - 542

BT - Proceedings of the NOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium

A2 - Badonnel, Sema Oktug

A2 - Ulema, Mehmet

A2 - Cavdar, Cicek

A2 - Granville, Lisandro Zambenedetti

A2 - dos Santos, Carlos Raniery P.

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2016 IEEE/IFIP Network Operations and Management Symposium, NOMS 2016

Y2 - 25 April 2016 through 29 April 2016

ER -

Soualah O, Fajjari I, Hadji M, Aitsaadi N, Zeghlache D. A novel virtual network embedding scheme based on Gomory-Hu tree within cloud's backbone. In Badonnel SO, Ulema M, Cavdar C, Granville LZ, dos Santos CRP, editors, Proceedings of the NOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium. Institute of Electrical and Electronics Engineers Inc. 2016. p. 536-542. 7502855. (Proceedings of the NOMS 2016 - 2016 IEEE/IFIP Network Operations and Management Symposium). doi: 10.1109/NOMS.2016.7502855

A novel virtual network embedding scheme based on Gomory-Hu tree within cloud's backbone

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this