Exact and heuristic graph-coloring for energy efficient advance cloud resource reservation

Chaima Ghribi; Djamal Zeghlache

doi:10.1109/CLOUD.2014.25

Exact and heuristic graph-coloring for energy efficient advance cloud resource reservation

Chaima Ghribi, Djamal Zeghlache

CNRS SAMOVAR UMR 5157

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

Abstract

This paper presents a new graph-coloring model for advance resource reservation with minimum energy consumption in heterogeneous IaaS cloud data centers. We start with an exact integer linear programming (ILP) formulation which generalizes the graph coloring problem and follow with a fast Energy Efficient Graph Pre-coloring (EEGP) heuristic to address the scalability and to reduce convergence times. The results of performance evaluation and comparisons of EEGP with our exact algorithm and the Haizea advance reservation (AR) algorithm demonstrate the efficiency of EEGP for the energy efficient advance resource reservation problem. Our proposed EEGP heuristic is shown to perform very close to optimal, to scale well with problem size and to achieve convergence times close to the simple and fast AR algorithm that is however suboptimal.

Original language	English
Title of host publication	Proceedings - 2014 IEEE 7th International Conference on Cloud Computing, CLOUD 2014
Editors	Carl Kesselman
Publisher	IEEE Computer Society
Pages	112-119
Number of pages	8
ISBN (Electronic)	9781479950638
DOIs	https://doi.org/10.1109/CLOUD.2014.25
Publication status	Published - 3 Dec 2014
Externally published	Yes
Event	7th IEEE International Conference on Cloud Computing, CLOUD 2014 - Anchorage, United States Duration: 27 Jun 2014 → 2 Jul 2014

Publication series

Name	IEEE International Conference on Cloud Computing, CLOUD
ISSN (Print)	2159-6182
ISSN (Electronic)	2159-6190

Conference

Conference	7th IEEE International Conference on Cloud Computing, CLOUD 2014
Country/Territory	United States
City	Anchorage
Period	27/06/14 → 2/07/14

Keywords

Advance Resource reservation
Energy efficiency
Graph-coloring
Heterogeneous Cloud Data Centers

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.1109/CLOUD.2014.25

Cite this

Ghribi, C., & Zeghlache, D. (2014). Exact and heuristic graph-coloring for energy efficient advance cloud resource reservation. In C. Kesselman (Ed.), Proceedings - 2014 IEEE 7th International Conference on Cloud Computing, CLOUD 2014 (pp. 112-119). Article 6973731 (IEEE International Conference on Cloud Computing, CLOUD). IEEE Computer Society. https://doi.org/10.1109/CLOUD.2014.25

@inproceedings{4c3f1a7b8c0c4028a5e44315795fec9b,

title = "Exact and heuristic graph-coloring for energy efficient advance cloud resource reservation",

abstract = "This paper presents a new graph-coloring model for advance resource reservation with minimum energy consumption in heterogeneous IaaS cloud data centers. We start with an exact integer linear programming (ILP) formulation which generalizes the graph coloring problem and follow with a fast Energy Efficient Graph Pre-coloring (EEGP) heuristic to address the scalability and to reduce convergence times. The results of performance evaluation and comparisons of EEGP with our exact algorithm and the Haizea advance reservation (AR) algorithm demonstrate the efficiency of EEGP for the energy efficient advance resource reservation problem. Our proposed EEGP heuristic is shown to perform very close to optimal, to scale well with problem size and to achieve convergence times close to the simple and fast AR algorithm that is however suboptimal.",

keywords = "Advance Resource reservation, Energy efficiency, Graph-coloring, Heterogeneous Cloud Data Centers",

author = "Chaima Ghribi and Djamal Zeghlache",

note = "Publisher Copyright: {\textcopyright} 2014 IEEE.; 7th IEEE International Conference on Cloud Computing, CLOUD 2014 ; Conference date: 27-06-2014 Through 02-07-2014",

year = "2014",

month = dec,

day = "3",

doi = "10.1109/CLOUD.2014.25",

language = "English",

series = "IEEE International Conference on Cloud Computing, CLOUD",

publisher = "IEEE Computer Society",

pages = "112--119",

editor = "Carl Kesselman",

booktitle = "Proceedings - 2014 IEEE 7th International Conference on Cloud Computing, CLOUD 2014",

}

Ghribi, C & Zeghlache, D 2014, Exact and heuristic graph-coloring for energy efficient advance cloud resource reservation. in C Kesselman (ed.), Proceedings - 2014 IEEE 7th International Conference on Cloud Computing, CLOUD 2014., 6973731, IEEE International Conference on Cloud Computing, CLOUD, IEEE Computer Society, pp. 112-119, 7th IEEE International Conference on Cloud Computing, CLOUD 2014, Anchorage, United States, 27/06/14. https://doi.org/10.1109/CLOUD.2014.25

Exact and heuristic graph-coloring for energy efficient advance cloud resource reservation. / Ghribi, Chaima; Zeghlache, Djamal.
Proceedings - 2014 IEEE 7th International Conference on Cloud Computing, CLOUD 2014. ed. / Carl Kesselman. IEEE Computer Society, 2014. p. 112-119 6973731 (IEEE International Conference on Cloud Computing, CLOUD).

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

TY - GEN

T1 - Exact and heuristic graph-coloring for energy efficient advance cloud resource reservation

AU - Ghribi, Chaima

AU - Zeghlache, Djamal

PY - 2014/12/3

Y1 - 2014/12/3

N2 - This paper presents a new graph-coloring model for advance resource reservation with minimum energy consumption in heterogeneous IaaS cloud data centers. We start with an exact integer linear programming (ILP) formulation which generalizes the graph coloring problem and follow with a fast Energy Efficient Graph Pre-coloring (EEGP) heuristic to address the scalability and to reduce convergence times. The results of performance evaluation and comparisons of EEGP with our exact algorithm and the Haizea advance reservation (AR) algorithm demonstrate the efficiency of EEGP for the energy efficient advance resource reservation problem. Our proposed EEGP heuristic is shown to perform very close to optimal, to scale well with problem size and to achieve convergence times close to the simple and fast AR algorithm that is however suboptimal.

AB - This paper presents a new graph-coloring model for advance resource reservation with minimum energy consumption in heterogeneous IaaS cloud data centers. We start with an exact integer linear programming (ILP) formulation which generalizes the graph coloring problem and follow with a fast Energy Efficient Graph Pre-coloring (EEGP) heuristic to address the scalability and to reduce convergence times. The results of performance evaluation and comparisons of EEGP with our exact algorithm and the Haizea advance reservation (AR) algorithm demonstrate the efficiency of EEGP for the energy efficient advance resource reservation problem. Our proposed EEGP heuristic is shown to perform very close to optimal, to scale well with problem size and to achieve convergence times close to the simple and fast AR algorithm that is however suboptimal.

KW - Advance Resource reservation

KW - Energy efficiency

KW - Graph-coloring

KW - Heterogeneous Cloud Data Centers

U2 - 10.1109/CLOUD.2014.25

DO - 10.1109/CLOUD.2014.25

M3 - Conference contribution

AN - SCOPUS:84919819920

T3 - IEEE International Conference on Cloud Computing, CLOUD

SP - 112

EP - 119

BT - Proceedings - 2014 IEEE 7th International Conference on Cloud Computing, CLOUD 2014

A2 - Kesselman, Carl

PB - IEEE Computer Society

T2 - 7th IEEE International Conference on Cloud Computing, CLOUD 2014

Y2 - 27 June 2014 through 2 July 2014

ER -

Exact and heuristic graph-coloring for energy efficient advance cloud resource reservation

Abstract

Publication series

Conference

Keywords

UN SDGs

Access to Document

Fingerprint

Cite this