This paper investigates the opportunities and limitations of adaptive virtual machine (VM) migration to reduce communication costs in a virtualized environment. We introduce a new formal model for the problem of online VM migration in two scenarios: (1) VMs can be migrated arbitrarily in the substrate network; e.g., a private cloud provider may have an incentive to reduce the overall communication cost in the network. (2) VMs can only be migrated within a given tenant; e.g., a user that was assigned a set of physical machines may exchange the functionality of the VMs on these machines. We propose a simple class of Destination-Swap algorithms which are based on an aggressive collocation strategy (inspired by splay datastructures) and which maintain a minimal and local amount of per-node (amortized cost) information to decide where to migrate a VM and how; thus, the algorithms react quickly to changes in the load. The algorithms come in two main flavors, an indirect and distributed variant which keeps existing VM placements local, and a direct variant which keeps the number of affected VMs small. We show that naturally, inter-tenant optimizations yield a larger potential for optimization, but generally also a tenant itself can improve its embedding. Moreover, there exists an interesting tradeoff between direct and indirect strategies: indirect variants are preferable under skewed and sparse communication patterns due to their locality properties.
Today's trend toward network virtualization and software-defined networking enables flexible new distributed systems where resources can be dynamically allocated and migrated to locations where they are most useful. This paper proposes a competitive analysis approach to design and reason about online algorithms that find a good tradeoff between the benefits and costs of a migratable service. A competitive online algorithm provides worst-case performance guarantees under any demand dynamics, and without any information or statistical assumptions on the demand in the future. This is attractive especially in scenarios where the demand is hard to predict and can be subject to unexpected events. As a case study, we describe a service (e.g., an SAP server or a gaming application) that uses network virtualization to improve the quality of service (QoS) experienced by thin client applications running on mobile devices. By decoupling the service from the underlying resource infrastructure, it can be migrated closer to the current client locations while taking into account migration costs. We identify the major cost factors in such a system and formalize the wide-area service migration problem. Our main contributions are a randomized and a deterministic online algorithm that achieve a competitive ratio of @math in a simplified scenario, where @math is the size of the substrate network. This is almost optimal. We complement our worst-case analysis with simulations in different specific scenarios and also sketch a migration demonstrator. Virtual machine technology and the ease with which VMs can be migrated within the LAN, has changed the scope of resource management from allocating resources on a single server to manipulating pools of resources within a data center. We expect WAN migration of virtual machines to likewise transform the scope of provisioning compute resources from a single data center to multiple data centers spread across the country or around the world. In this paper we present the CloudNet architecure as a cloud framework consisting of cloud computing platforms linked with a VPN based network infrastructure to provide seamless and secure connectivity between enterprise and cloud data center sites. To realize our vision of efficiently pooling geographically distributed data center resources, CloudNet provides optimized support for live WAN migration of virtual machines. Specifically, we present a set of optimizations that minimize the cost of transferring storage and virtual machine memory during migrations over low bandwidth and high latency Internet links. We evaluate our system on an operational cloud platform distributed across the continental US. During simultaneous migrations of four VMs between data centers in Texas and Illinois, CloudNet's optimizations reduce memory migration time by 65 and lower bandwidth consumption for the storage and memory transfer by 19GB, a 50 reduction. This paper attends to the problem of embedding flexibly specified virtual networks connecting cloud resources (e.g., storage or computation) on a given substrate (e.g., a data center, an ISP backbone, a router site, or a virtual provider network). We study a scenario where a substrate provider (or a potential intermediate broker or reseller) wants to optimize the embedding of these so-called by migrating them to more suitable locations. For instance, such re-embeddings can be useful if the were requested at short notice and initially placed heuristically. Subsequent optimizations can, e.g., reduce the peak resource loads in the network by spreading across the infrastructure or save energy by moving together and switching off unused components. We present the generic mathematical programming algorithm used in our prototype to compute optimal embeddings. For example, this algorithm supports different objective functions (such as load minimization or energy conservation), arbitrary resource combinations and the mapping of multiple virtual nodes of a to a single substrate node, cost-aware migrations, and it can deal with all link types that arise in practice (e.g., full-duplex or even wireless or wired broadcast links with multiple endpoints). Of course, such rigorous optimizations are time consuming, and we report on the time complexities obtained from our experiments with our network virtualization prototype architecture. It turns out that optimizing over moderate sized infrastructures is feasible, even for scenarios with high flexibility and without tuning the solver software to speed up computations further. It is envisaged that services and applications will migrate to a cloud-computing paradigm where thin-clients on user devices access, over the network, applications hosted in data centers by application service providers. Examples are cloud based gaming applications and cloud-supported virtual desktops. For good performance and efficiency, it is critical that these services are delivered from locations that are the best for the current (dynamically changing) set of users. To achieve this, we expect that services will be hosted on virtual machines in interconnected data centers and that these virtual machines will migrate dynamically to locations best suited for the current user population. A basic network infrastructure need then is the ability to migrate virtual machines across multiple networks without losing service continuity. In this paper, we develop mechanisms to accomplish this using a network-virtualization architecture that relies on a set of distributed forwarding elements with centralized control (borrowing on several recent proposals in a similar vein). We describe a preliminary prototype system, built using Openflow components, that demonstrates the feasibility of this architecture in enabling seamless migration of virtual machines and in enhancing delivery of cloud-based services.