An optimization problem in adaptive virtual environments

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. Along with resource monitoring and inference and application-independent adaptation mechanisms, efficient adaptation algorithms are key to the success of such an effort. In previous work we have described our measurement and inference framework, explained our adaptation mechanisms, and proposed simple heuristics as adaptation algorithms. Though we were successful in improving performance as compared to the case with no adaptation, none of our algorithms were characterized by theoretically proven bounds. In this paper, we formalize the adaptation problem, show that it is NP-hard and propose research directions for coming up with an efficient solution.