umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Algorithms and Systems for Virtual Machine Scheduling in Cloud Infrastructures
Umeå University, Faculty of Science and Technology, Department of Computing Science. (UMIT)
2014 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

With the emergence of cloud computing, computing resources (i.e., networks, servers, storage, applications, etc.) are provisioned as metered on-demand services over net- works, and can be rapidly allocated and released with minimal management effort. In the cloud computing paradigm, the virtual machine (VM) is one of the most com- monly used resource units in which business services are encapsulated. VM schedul- ing optimization, i.e., finding optimal placement schemes for VMs and reconfigu- rations according to the changing conditions, becomes challenging issues for cloud infrastructure providers and their customers.

The thesis investigates the VM scheduling problem in two scenarios: (i) single- cloud environments where VMs are scheduled within a cloud aiming at improving criteria such as load balancing, carbon footprint, utilization, and revenue, and (ii) multi-cloud scenarios where a cloud user (which could be the owner of the VMs or a cloud infrastructure provider) schedules VMs across multiple cloud providers, target- ing optimization for investment cost, service availability, etc. For single-cloud scenar- ios, taking load balancing as the objective, an approach to optimal VM placement for predictable and time-constrained peak loads is presented. In addition, we also present a set of heuristic methods based on fundamental management actions (namely, sus- pend and resume physical machines, VM migration, and suspend and resume VMs), continuously optimizing the profit for the cloud infrastructure provider regardless of the predictability of the workload. For multi-cloud scenarios, we identify key re- quirements for service deployment in a range of common cloud scenarios (including private clouds, bursted clouds, federated clouds, multi-clouds, and cloud brokering), and present a general architecture to meet these requirements. Based on this architec- ture, a set of placement algorithms tuned for cost optimization under dynamic pricing schemes are evaluated. By explicitly specifying service structure, component relation- ships, and placement constraints, a mechanism is introduced to enable service owners the ability to influence placement. In addition, we also study how dynamic cloud scheduling using VM migration can be modeled using a linear integer programming approach.

The primary contribution of this thesis is the development and evaluation of al- gorithms (ranging from combinatorial optimization formulations to simple heuristic algorithms) for VM scheduling in cloud infrastructures. In addition to scientific pub- lications, this work also contributes software tools (in the OPTIMIS project funded by the European Commissions Seventh Framework Programme) that demonstrate the feasibility and characteristics of the approaches presented. 

Abstract [sv]

I datormoln tillhandahålls datorresurser (dvs., nätverk, servrar, lagring, applikationer,

etc.) som tjänster åtkomliga via Internet. Resurserna, som t.ex. virtuella maskiner (VMs), kan snabbt och enkelt allokeras och frigöras alltefter behov. De potentiellt snabba förändringarna i hur många och hur stora VMs som behövs leder till utmanade schedulerings- och konfigureringsproblem. Scheduleringsproblemen uppstår både för infrastrukturleverantörer som behöver välja vilka servrar olika VMs ska placeras på inom ett moln och deras kunder som behöver välja vilka moln VMs ska placeras på.

Avhandlingen fokuserar på VM-scheduleringsproblem i dessa två scenarier, dvs (i) enskilda moln där VMs ska scheduleras för att optimera lastbalans, energiåtgång, resursnyttjande och ekonomi och (ii) situationer där en molnanvändare ska välja ett eller flera moln för att placera VMs för att optimera t.ex. kostnad, prestanda och tillgänglighet för den applikation som nyttjar resurserna. För det förstnämnda scenar- iot presenterar avhandlingen en scheduleringsmetod som utifrån förutsägbara belast- ningsvariationer optimerar lastbalansen mellan de fysiska datorresurserna. Därtill pre- senteras en uppsättning heuristiska metoder, baserade på fundamentala resurshanter- ingsåtgärder, fö att kontinuerligt optimera den ekonomiska vinsten för en molnlever- antör, utan krav på lastvariationernas förutsägbarhet.

För fallet med flera moln identifierar vi viktiga krav för hur resurshanteringstjänster ska konstrueras för att fungera väl i en rad konceptuellt olika fler-moln-scenarier. Utifrån dessa krav definierar vi också en generell arkitektur som kan anpassas till dessa scenarier. Baserat pp vår arkitektur utvecklar och utvärderar vi en uppsättning algoritmer för VM-schedulering avsedda att minimera kostnader för användning av molninfrastruktur med dynamisk prissättning. Användaren ges genom ny funktionalitet möjlighet att explicit specificera relationer mellan de VMs som allokeras och andra bivillkor för hur de ska placeras. Vi demonstrerar också hur linjär heltals- programmering kan användas för att optimera detta scheduleringsproblem.

Avhandlingens främsta bidrag är utveckling och utvärdering av nya metoder för VM-schedulering i datormoln, med lösningar som inkluderar såväl kombinatorisk op- timering som heuristiska metoder. Utöver vetenskapliga publikationer bidrar arbetet även med programvaror för VM-schedulering, utvecklade inom ramen för projektet OPTIMIS som finansierats av EU-kommissionens sjunde ramprogram.

metoder för VM-schedulering i datormoln, med lösningar som inkluderar såväl kombinatorisk op- timering som heuristiska metoder. Utöver vetenskapliga publikationer bidrar arbetet även med programvaror för VM-schedulering, utvecklade inom ramen för projektet OPTIMIS som finansierats av EU-kommissionens sjunde ramprogram.

Place, publisher, year, edition, pages
Umeå: Umeå̊ Universitet , 2014. , 33 p.
Series
Report / UMINF, ISSN 0348-0542 ; 2014:06
Keyword [en]
cloud computing, virtual machine, scheduling, systems, algorithms
National Category
Computer Science
Identifiers
URN: urn:nbn:se:umu:diva-87310ISBN: 978-91-7601-019-8 (print)OAI: oai:DiVA.org:umu-87310DiVA: diva2:708798
Public defence
2014-04-25, MIT-Huset, MA121, Umeå Universitet, Umeå, 10:00 (English)
Opponent
Supervisors
Available from: 2014-04-04 Created: 2014-03-29 Last updated: 2014-04-17Bibliographically approved
List of papers
1. Modeling for Dynamic Cloud Scheduling via Migration of Virtual Machines
Open this publication in new window or tab >>Modeling for Dynamic Cloud Scheduling via Migration of Virtual Machines
2011 (English)In: Cloud Computing Technology and Science (CloudCom), IEEE Computer Society, 2011, 163-171 p.Conference paper, Published paper (Refereed)
Abstract [en]

Cloud brokerage mechanisms are fundamental to reduce the complexity of using multiple cloud infrastructures to achieve optimal placement of virtual machines and avoid the potential vendor lock-in problems. However, current approaches are restricted to static scenarios, where changes in characteristics such as pricing schemes, virtual machine types, and service performance throughout the service life-cycle are ignored. In this paper, we investigate dynamic cloud scheduling use cases where these parameters are continuously changed, and propose a linear integer programming model for dynamic cloud scheduling. Our model can be applied in various scenarios through selections of corresponding objectives and constraints, and offers the flexibility to express different levels of migration overhead when restructuring an existing infrastructure. Finally, our approach is evaluated using commercial clouds parameters in selected simulations for the studied scenarios. Experimental results demonstrate that, with proper parametrizations, our approach is feasible.

Place, publisher, year, edition, pages
IEEE Computer Society, 2011
Keyword
cloud computing, dynamic scheduling, virtual machine placement, migration overhead, linear integer programming
National Category
Computer Science
Research subject
Computer Science
Identifiers
urn:nbn:se:umu:diva-50836 (URN)10.1109/CloudCom.2011.31 (DOI)978-1-4673-0090-2 (ISBN)
Conference
The 3rd IEEE International Conference on Cloud Computing Technology and Science (CloudCom 2011) November 29 - December 1, Athens, Greece
Available from: 2011-12-27 Created: 2011-12-27 Last updated: 2014-03-31Bibliographically approved
2. Virtual machine placement for predictable and time-constrained peak loads
Open this publication in new window or tab >>Virtual machine placement for predictable and time-constrained peak loads
2012 (English)In: Economics of Grids, Clouds, Systems, and Services: 8th International Workshop, GECON 2011, Paphos, Cyprus, December 5, 2011, Revised Selected Papers / [ed] Kurt Vanmechelen, Jörn Altmann, Omer F. Rana, Springer Berlin/Heidelberg, 2012, 120-134 p.Conference paper, Published paper (Refereed)
Abstract [en]

We present an approach to optimal virtual machine placement within datacenters for predicable and time-constrained load peaks. A method for optimal load balancing is developed, based on binary integer programming. For tradeoffs between quality of solution and computation time, we also introduce methods to pre-process the optimization problem before solving it. Upper bound based optimizations are used to reduce the time required to compute a final solution, enabling larger problems to be solved. For further scalability, we also present three approximation algorithms, based on heuristics and/or greedy formulations. The proposed algorithms are evaluated through simulations based on synthetic data sets. The evaluation suggests that our algorithms are feasible, and that these can be combined to achieve desired tradeoffs between quality of solution and execution time.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2012
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 7150
National Category
Computer Science
Identifiers
urn:nbn:se:umu:diva-51034 (URN)10.1007/978-3-642-28675-9_9 (DOI)3642286747 (ISBN)9783642286742 (ISBN)9783642286759 E-ISBN (ISBN)
Conference
GECON 2011 : 8th International Workshop on Economics of Grids, Clouds, Systems, and Services, December 5th, 2011 , Paphos, Cyprus
Available from: 2012-01-09 Created: 2012-01-09 Last updated: 2014-03-31Bibliographically approved
3. A General Approach to Service Deployment in Cloud Environments
Open this publication in new window or tab >>A General Approach to Service Deployment in Cloud Environments
2012 (English)In: Cloud and Green Computing (CGC 2012): 2012 Second International Conference on, IEEE Computer Society, 2012, 17-24 p.Conference paper, Published paper (Refereed)
Abstract [en]

The cloud computing landscape has recently developed into a spectrum of cloud architectures, leading to a broad range of management tools for similar operations but specialized for certain deployment scenarios. This both hinders the efficient reuse of algorithmic innovations within cloud management operations and increases the heterogeneity between different management systems. Our overarching goal is to overcome these problems by developing tools general enough to support the full range of popular architectures. In this contribution, we analyze commonalities in recently proposed cloud models (private clouds, multi-clouds, bursted clouds, federated clouds, etc.), and demonstrate how a key management functionality - service deployment - can be uniformly performed in all of these by a carefully designed system. The design of our service deployment framework is validated through a demonstration of how it can be used to deploy services, perform bursting and brokering, as well as mediate a cloud federation in the context of the OPTIMIS Toolkit.

Place, publisher, year, edition, pages
IEEE Computer Society, 2012
Keyword
Cloud Computing, Cloud Architecture, Service Deployment
National Category
Computer Science
Identifiers
urn:nbn:se:umu:diva-79784 (URN)10.1109/CGC.2012.90 (DOI)978-0-7695-4864-7 (ISBN)978-1-4673-3027-5 Print (ISBN)
Conference
the 2nd International Conference on Cloud and Green Computing, Xiangtan, 1-3 November 2012
Available from: 2013-09-02 Created: 2013-09-02 Last updated: 2014-04-14Bibliographically approved
4. Cost-Optimal Cloud Service Placement under Dynamic Pricing Schemes
Open this publication in new window or tab >>Cost-Optimal Cloud Service Placement under Dynamic Pricing Schemes
2013 (English)In: 6th IEEE/ACM International Conference on Utility and Cloud Computing, IEEE Computer Society, 2013, 187-194 p.Conference paper, Published paper (Refereed)
Abstract [en]

Until now, most research on cloud service placement has focused on static pricing scenarios, where cloud providers offer fixed prices for their resources. However, with the recent trend of dynamic pricing of cloud resources, where the price of a compute resource can vary depending on the free capacity and load of the provider, new placement algorithms are needed. In this paper, we investigate service placement in dynamic pricing scenarios by evaluating a set of placement algorithms, tuned for dynamic pricing. The algorithms range from simple heuristics to combinatorial optimization solutions. The studied algorithms are evaluated by deploying a set of services across multiple providers. Finally, we analyse the strengths and weaknesses of the algorithms considered. The evaluation suggests that exhaustive search based approach is good at finding optimal solutions for service placement under dynamic pricing schemes, but the execution times are usually long. In contrast, greedy approaches perform surprisingly well with fast execution times and acceptable solutions, and thus can be a suitable compromise considering the tradeoffs between quality of solution and execution time.

Place, publisher, year, edition, pages
IEEE Computer Society, 2013
Keyword
Cloud Computing, Dynamic Pricing, Service Placement, Deployment Optimization
National Category
Computer Science
Identifiers
urn:nbn:se:umu:diva-80478 (URN)
Conference
the 6th IEEE/ACM International Conference on Utility and Cloud Computing
Funder
eSSENCE - An eScience CollaborationEU, FP7, Seventh Framework Programme, 257115
Available from: 2013-09-18 Created: 2013-09-18 Last updated: 2014-04-14Bibliographically approved
5. Modeling and Placement of Cloud Services with Internal Structure
Open this publication in new window or tab >>Modeling and Placement of Cloud Services with Internal Structure
Show others...
2016 (English)In: IEEE Transactions on Cloud Computing, ISSN 2168-7161, Vol. 4, no 4, 429-439 p.Article in journal (Refereed) Published
Abstract [en]

Virtual machine placement is the process of mapping virtual machines to available physical hosts within a datacenter or on a remote datacenter in a cloud federation. Normally, service owners cannot influence the placement of service components beyond choosing datacenter provider and deployment zone at that provider. For some services, however, this lack of influence is a hindrance to cloud adoption. For example, services that require specific geographical deployment (due e.g. to legislation), or require redundancy by avoiding co-location placement of critical components. We present an approach for service owners to influence placement of their service components by explicitly specifying service structure, component relationships, and placement constraints between components. We show how the structure and constraints can be expressed and subsequently formulated as constraints that can be used in placement of virtual machines in the cloud. We use an integer linear programming scheduling approach to illustrate the approach, show the corresponding mathematical formulation of the model, and evaluate it using a large set of simulated input. Our experimental evaluation confirms the feasibility of the model and shows how varying amounts of placement constraints and data center background load affects the possibility for a solver to find a solution satisfying all constraints within a certain time-frame. Our experiments indicate that the number of constraints affects the ability of finding a solution to a higher degree than background load, and that for a high number of hosts with low capacity, component affinity is the dominating factor affecting the possibility to find a solution.

Place, publisher, year, edition, pages
IEEE Computer Society, 2016
Keyword
service management, service structure, placement, affinity, collocation, scheduling, integer linear programming, cloud computing
National Category
Computer Science
Research subject
Computer Science
Identifiers
urn:nbn:se:umu:diva-80125 (URN)10.1109/TCC.2014.2362120 (DOI)000390560200005 ()
Funder
eSSENCE - An eScience Collaboration
Available from: 2013-09-10 Created: 2013-09-10 Last updated: 2017-01-23Bibliographically approved
6. Continuous Datacenter Consolidation
Open this publication in new window or tab >>Continuous Datacenter Consolidation
Show others...
2014 (English)Report (Refereed)
Abstract [en]

Efficient mapping of Virtual Machines (VMs) onto physical servers is a key problem for cloud infrastructure providers as hardware utilization directly im- pacts revenue. Today, this mapping is commonly only performed when new VMs are created, but as VM workloads fluctuate and server availability varies, any ini- tial mapping is bound to become suboptimal over time. We introduce a set of heuristic methods for continuous optimization of the VM-to-server mapping based on combina- tions of fundamental management actions, namely suspending and resuming physical machines, migrating VMs, and suspending and resuming VMs. Using these methods cloud infrastructure providers can continuously optimize their server resources regard- less of the predictability of the workload. To verify that our approach is applicable in real-world scenarios, we build a proof-of-concept datacenter management system that implements the proposed algorithms. The feasibility of our approach is evaluated through a combination of simulations and real experiments where our system provi- sions a workload of benchmark applications. Our results indicate that the proposed algorithms are feasible, that the combined management approach achieves the best results, and that the VM suspend and resume mechanism has the largest impact. 

Place, publisher, year, edition, pages
Umeå: Umeå universitet, 2014. 12 p.
Series
Report / UMINF, ISSN 0348-0542 ; 2014:08
National Category
Computer Science
Identifiers
urn:nbn:se:umu:diva-87385 (URN)
Available from: 2014-03-31 Created: 2014-03-31 Last updated: 2014-04-14Bibliographically approved

Open Access in DiVA

Algorithms and Systems for Virtual Machine Scheduling in Cloud Infrastructures(1170 kB)3150 downloads
File information
File name FULLTEXT02.pdfFile size 1170 kBChecksum SHA-512
ba9ed698d31e8d502e38a3cc30945657806cab4a3ea9bc0c565b79cfd12df3da540fd85a7b004e5c2e6ec67ca255f75956d2a09b1b58b2326fcdaeb58633c033
Type fulltextMimetype application/pdf
errata(32 kB)34 downloads
File information
File name ERRATA01.pdfFile size 32 kBChecksum SHA-512
7a26a292a12787536b7e83a0bf99db39da2007cec759c5ed09f7dda0bcec90a816ccedd82be382a1bc21cf2d75b3c6b48a2e8f64d806193462b40f0ce731882e
Type errataMimetype application/pdf

Search in DiVA

By author/editor
Li, Wubin
By organisation
Department of Computing Science
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 3150 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 780 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf