An optimization problem in adaptive virtual environments

ABSTRACT

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.

REFERENCES

• 1: Renato J. Figueiredo , Peter A. Dinda , José A. B. Fortes, A Case For Grid Computing On Virtual Machines, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.550, May 19-22, 2003
• 2: A. Gupta and P. A. Dinda. Infering the topology and traffic load of parallel programs running in a virtual machine environment. In Proceedings of the 10th Workshop on Job Scheduling Strategies for Parallel Program Processing(JSSPP), June 2004.
• 3: A. Gupta, M. Zangrilli, A. I. Sundararaj, P. Dinda, and B. Lowekamp. Free network measurment for adaptive virtualized distributed computing. Technical Report NWU-CS-05-13, June 2005.
• 4: Xuxian Jiang , Dongyan Xu, SODA: A Service-On-Demand Architecture for Application Service Hosting Utility Platforms, Proceedings of the 12th IEEE International Symposium on High Performance Distributed Computing (HPDC'03), p.174, June 22-24, 2003
• 5: R. Karp. Compexity of Computer Computations, chapter Reducibility among combinatorial problems, pages 85--103. Plenum Press, New York, 1972.
• 6: J. R. Lange, A. I. Sundararaj, and P. A. Dinda. Automatic dynamic run-time optical network reservations. In Proceedings of the 14th International Symposium on High Performance Distributed Computing (HPDC), July 2005.
• 7: Bin Lin , Peter A. Dinda, VSched: Mixing Batch And Interactive Virtual Machines Using Periodic Real-time Scheduling, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.8, November 12-18, 2005 [doi>10.1109/SC.2005.80]
• 8: A. I. Sundararaj and P. A. Dinda. Towards virtual networks for virtual machine grid computing. In Proceedings of the 3rd USENIX Virtual Machine Research and Technology Symposium (VM), May 2004.
• 9: A. I. Sundararaj, A. Gupta, and P. A. Dinda. Increasing application performance in virtual environments through run-time inference and adaptation. In Proceedings of the 14th International Symposium on High Performance Distributed Computing (HPDC), July 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development

General Terms:
Design, Performance, Theory