Shadow-routing based dynamic algorithms for virtual machine placement in a network cloud

Yang Guo, Alexander L. Stolyar, Anwar Walid

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider a shadow routing based approach to the problem of real-time adaptive placement of virtual machines (VM) in large data centers (DC) within a network cloud. Such placement in particular has to respect vector packing constraints on the allocation of VMs to host physical machines (PM) within a DC, because each PM can potentially serve multiple VMs simultaneously. Shadow routing is attractive in that it allows a large variety of system objectives and/or constraints to be treated within a common framework (as long as the underlying optimization problem is convex). Perhaps even more attractive feature is that the corresponding algorithm is very simple to implement, it runs continuously, and adapts automatically to changes in the VM demand rates, changes in system parameters, etc., without the need to re-solve the underlying optimization problem 'from scratch'. In this paper we focus on the min-max-DC-load problem. Namely, we propose a combined VM-to-DC routing and VM-to-PM assignment algorithm, referred to as Shadow scheme, which minimizes the maximum of appropriately defined DC utilizations. We prove that the Shadow scheme is asymptotically optimal (as one of its parameters goes to 0). Simulation confirms good performance and high adaptivity of the algorithm. Favorable performance is also demonstrated in comparison with a baseline algorithm based on VMware implementation [7], [8]. We also propose a simplified-'more distributed'-version of the Shadow scheme, which performs almost as well in simulations.

Original languageEnglish (US)
Title of host publication2013 Proceedings IEEE INFOCOM 2013
Pages620-628
Number of pages9
DOIs
StatePublished - Sep 2 2013
Externally publishedYes
Event32nd IEEE Conference on Computer Communications, IEEE INFOCOM 2013 - Turin, Italy
Duration: Apr 14 2013Apr 19 2013

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X

Other

Other32nd IEEE Conference on Computer Communications, IEEE INFOCOM 2013
CountryItaly
CityTurin
Period4/14/134/19/13

Fingerprint

Virtual machine

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering

Cite this

Guo, Y., Stolyar, A. L., & Walid, A. (2013). Shadow-routing based dynamic algorithms for virtual machine placement in a network cloud. In 2013 Proceedings IEEE INFOCOM 2013 (pp. 620-628). [6566847] (Proceedings - IEEE INFOCOM). https://doi.org/10.1109/INFCOM.2013.6566847

Shadow-routing based dynamic algorithms for virtual machine placement in a network cloud. / Guo, Yang; Stolyar, Alexander L.; Walid, Anwar.

2013 Proceedings IEEE INFOCOM 2013. 2013. p. 620-628 6566847 (Proceedings - IEEE INFOCOM).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Guo, Y, Stolyar, AL & Walid, A 2013, Shadow-routing based dynamic algorithms for virtual machine placement in a network cloud. in 2013 Proceedings IEEE INFOCOM 2013., 6566847, Proceedings - IEEE INFOCOM, pp. 620-628, 32nd IEEE Conference on Computer Communications, IEEE INFOCOM 2013, Turin, Italy, 4/14/13. https://doi.org/10.1109/INFCOM.2013.6566847
Guo Y, Stolyar AL, Walid A. Shadow-routing based dynamic algorithms for virtual machine placement in a network cloud. In 2013 Proceedings IEEE INFOCOM 2013. 2013. p. 620-628. 6566847. (Proceedings - IEEE INFOCOM). https://doi.org/10.1109/INFCOM.2013.6566847
Guo, Yang ; Stolyar, Alexander L. ; Walid, Anwar. / Shadow-routing based dynamic algorithms for virtual machine placement in a network cloud. 2013 Proceedings IEEE INFOCOM 2013. 2013. pp. 620-628 (Proceedings - IEEE INFOCOM).
@inproceedings{4eca1d1c3cf94f6b8b1f8c31e54fe5dc,
title = "Shadow-routing based dynamic algorithms for virtual machine placement in a network cloud",
abstract = "We consider a shadow routing based approach to the problem of real-time adaptive placement of virtual machines (VM) in large data centers (DC) within a network cloud. Such placement in particular has to respect vector packing constraints on the allocation of VMs to host physical machines (PM) within a DC, because each PM can potentially serve multiple VMs simultaneously. Shadow routing is attractive in that it allows a large variety of system objectives and/or constraints to be treated within a common framework (as long as the underlying optimization problem is convex). Perhaps even more attractive feature is that the corresponding algorithm is very simple to implement, it runs continuously, and adapts automatically to changes in the VM demand rates, changes in system parameters, etc., without the need to re-solve the underlying optimization problem 'from scratch'. In this paper we focus on the min-max-DC-load problem. Namely, we propose a combined VM-to-DC routing and VM-to-PM assignment algorithm, referred to as Shadow scheme, which minimizes the maximum of appropriately defined DC utilizations. We prove that the Shadow scheme is asymptotically optimal (as one of its parameters goes to 0). Simulation confirms good performance and high adaptivity of the algorithm. Favorable performance is also demonstrated in comparison with a baseline algorithm based on VMware implementation [7], [8]. We also propose a simplified-'more distributed'-version of the Shadow scheme, which performs almost as well in simulations.",
author = "Yang Guo and Stolyar, {Alexander L.} and Anwar Walid",
year = "2013",
month = "9",
day = "2",
doi = "10.1109/INFCOM.2013.6566847",
language = "English (US)",
isbn = "9781467359467",
series = "Proceedings - IEEE INFOCOM",
pages = "620--628",
booktitle = "2013 Proceedings IEEE INFOCOM 2013",

}

TY - GEN

T1 - Shadow-routing based dynamic algorithms for virtual machine placement in a network cloud

AU - Guo, Yang

AU - Stolyar, Alexander L.

AU - Walid, Anwar

PY - 2013/9/2

Y1 - 2013/9/2

N2 - We consider a shadow routing based approach to the problem of real-time adaptive placement of virtual machines (VM) in large data centers (DC) within a network cloud. Such placement in particular has to respect vector packing constraints on the allocation of VMs to host physical machines (PM) within a DC, because each PM can potentially serve multiple VMs simultaneously. Shadow routing is attractive in that it allows a large variety of system objectives and/or constraints to be treated within a common framework (as long as the underlying optimization problem is convex). Perhaps even more attractive feature is that the corresponding algorithm is very simple to implement, it runs continuously, and adapts automatically to changes in the VM demand rates, changes in system parameters, etc., without the need to re-solve the underlying optimization problem 'from scratch'. In this paper we focus on the min-max-DC-load problem. Namely, we propose a combined VM-to-DC routing and VM-to-PM assignment algorithm, referred to as Shadow scheme, which minimizes the maximum of appropriately defined DC utilizations. We prove that the Shadow scheme is asymptotically optimal (as one of its parameters goes to 0). Simulation confirms good performance and high adaptivity of the algorithm. Favorable performance is also demonstrated in comparison with a baseline algorithm based on VMware implementation [7], [8]. We also propose a simplified-'more distributed'-version of the Shadow scheme, which performs almost as well in simulations.

AB - We consider a shadow routing based approach to the problem of real-time adaptive placement of virtual machines (VM) in large data centers (DC) within a network cloud. Such placement in particular has to respect vector packing constraints on the allocation of VMs to host physical machines (PM) within a DC, because each PM can potentially serve multiple VMs simultaneously. Shadow routing is attractive in that it allows a large variety of system objectives and/or constraints to be treated within a common framework (as long as the underlying optimization problem is convex). Perhaps even more attractive feature is that the corresponding algorithm is very simple to implement, it runs continuously, and adapts automatically to changes in the VM demand rates, changes in system parameters, etc., without the need to re-solve the underlying optimization problem 'from scratch'. In this paper we focus on the min-max-DC-load problem. Namely, we propose a combined VM-to-DC routing and VM-to-PM assignment algorithm, referred to as Shadow scheme, which minimizes the maximum of appropriately defined DC utilizations. We prove that the Shadow scheme is asymptotically optimal (as one of its parameters goes to 0). Simulation confirms good performance and high adaptivity of the algorithm. Favorable performance is also demonstrated in comparison with a baseline algorithm based on VMware implementation [7], [8]. We also propose a simplified-'more distributed'-version of the Shadow scheme, which performs almost as well in simulations.

UR - http://www.scopus.com/inward/record.url?scp=84883111226&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84883111226&partnerID=8YFLogxK

U2 - 10.1109/INFCOM.2013.6566847

DO - 10.1109/INFCOM.2013.6566847

M3 - Conference contribution

AN - SCOPUS:84883111226

SN - 9781467359467

T3 - Proceedings - IEEE INFOCOM

SP - 620

EP - 628

BT - 2013 Proceedings IEEE INFOCOM 2013

ER -