Hardness of Approximation and Greedy Algorithms for the Adaptation Problem in Virtual Environments
- 8 August 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Over the past decade, wide-area distributed computing has emerged as a powerful computing paradigm. Virtual machines greatly simplify wide-area distributed computing by lowering the abstraction to benefit both resource users and providers. A virtual execution environment consisting of virtual machines (VMs) interconnected with virtual networks provides opportunities to dynamically optimize, at run-time, the performance of existing, unmodified distributed applications without any user or programmer intervention. We have formalized the adaptation problem in virtual execution environments and shown that it is NP-hard to both, solve and approximate within a factor of m1/2-δfor any δ > 0, where m is the number of edges in the virtual overlay graph. We also designed and evaluated greedy adaptation algorithms and found them to work well in practice.Keywords
This publication has 2 references indexed in Scilit:
- Free network measurement for adaptive virtualized distributed computingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Increasing application performance in virtual environments through run-time inference and adaptationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005