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.
In the theory community, many migration problem variants have been studied in the context of online page migration, and more generally, online metrical task systems @cite_11 . There exist several interesting results by on how to embed and migrate services to reduce load, e.g., @cite_0 @cite_16 . Indeed, given a fixed communication pattern between pairs of VMs, our work is related to classic graph embedding problems such as the (e.g., @cite_7 ) of a graph. Recently, such embedding problems have also been studied from the perspective of self-adjusting networks, in the context of distributed splay datastructures and peer-to-peer networks @cite_19 . Indeed, our algorithms are inspired by the classic splaying techniques introduced in the seminal work by Sleator and Tarjan @cite_14 on self-adjusting search trees, in the sense that we also aggressively migrate VMs closer together.
@cite_14 @cite_7 @cite_0 @cite_19 @cite_16 @cite_11
2092340542 1552771324 2315437335 2769159728
This paper is concerned with the page migration (or file migration) problem (Black and Sleator, Technical Report CMU-CS-89-201, Department of Computer Science, Carnegie-Mellon University, 1989) as part of a large class of on-line problems. The page migration problem deals with the management of pages residing in a network of processors. In the classical problem there is only one copy of each page which is accessed by different processors over time. The page is allowed to be migrated between processors. However a migration incurs higher communication cost than an access (proportionally to the page size). The problem is that of deciding when and where to migrate the page in order to lower access costs. A more general setting is the k-page migration problem where we wish to maintain k copies of the page. The page migration problems are concerned with a dilemma common to many on-line problems: determining when it is beneficial to make configuration changes. We deal with the relaxed task systems model which captures a large class of problems of this type, that can be described as the generalization of some original task system problem (, J. ACM 39(4) (1992) 745-763). Given a c-competitive algorithm for a task system we show how to obtain a deterministic O(c2) and randomized O(c) competitive algorithms for the corresponding relaxed task system. The result implies deterministic algorithms for k-page migration by using k-server (, J. Algorithms 11(2) (1990) 208-230) algorithms, and for network leasing by using generalized Steiner tree algorithms (, Proc 7th Ann. ACM-SIAM Symp. on Discrete Algorithms, January 1996, pp. 68-74), as well as providing solutions for natural generalizations of other problems (e.g. storage rearrangement (, Proc. 36th Ann. IEEE Symp. on Foundations of Computer Science, October 1995, pp. 392-403)). We further study some special cases of the k-page migration problem and get optimal deterministic algorithms. For the classical page migration problem we present a deterministic algorithm that achieves a competitive ratio of 4:086, improving upon the previously best competitive ratio of 7 (, Proc. 25th ACM Symp. on Theory of Computing, May 1993, pp. 164-173). (The current lower bound on the problem is 3:148 (, J. Algorithms 24(1) (1997) 124-157). Copyright 2001 Elsevier Science B.V. Virtualization can deliver significant benefits for cloud computing by enabling VM migration to improve utilization, balance load and alleviate hotspots. While several mechanisms exist to migrate VMs, few efforts have focused on optimizing migration policies in a multi-rooted tree datacenter network. The general problem has multiple facets, two of which map to generalizations of well-studied problems: (1) Migration of VMs in a bandwidth-oversubscribed tree network generalizes the maximum multicommodity flow problem in a tree, and (2) Migrations must meet load constraints at the servers, mapping to variants of the matching problem --- generalized assignment and demand matching. While these problems have been individually studied, a new fundamental challenge is to simultaneously handle the packing constraints of server load and tree edge capacities. We give approximation algorithms for several versions of this problem, where the objective is to alleviate a maximal number of hot servers. In the full version of this work [5], we empirically demonstrate the effectiveness of these algorithms through large scale simulations on real data. This paper initiates the study of locally self-adjusting networks: networks whose topology adapts dynamically and in a decentralized manner, to the communication pattern @math . Our vision can be seen as a distributed generalization of the self-adjusting datastructures introduced by Sleator and Tarjan, 1985: In contrast to their splay trees which dynamically optimize the lookup costs from a single node (namely the tree root), we seek to minimize the routing cost between arbitrary communication pairs in the network. As a first step, we study distributed binary search trees (BSTs), which are attractive for their support of greedy routing. We introduce a simple model which captures the fundamental tradeoff between the benefits and costs of self-adjusting networks. We present the SplayNet algorithm and formally analyze its performance, and prove its optimality in specific case studies. We also introduce lower bound techniques based on interval cuts and edge expansion, to study the limitations of any demand-optimized network. Finally, we extend our study to multi-tree networks, and highlight an intriguing difference between classic and distributed splay trees. This paper introduces a novel method to perform transfer learning across domains and tasks, formulating it as a problem of learning to cluster. The key insight is that, in addition to features, we can transfer similarity information and this is sufficient to learn a similarity function and clustering network to perform both domain adaptation and cross-task transfer learning. We begin by reducing categorical information to pairwise constraints, which only considers whether two instances belong to the same class or not. This similarity is category-agnostic and can be learned from data in the source domain using a similarity network. We then present two novel approaches for performing transfer learning using this similarity function. First, for unsupervised domain adaptation, we design a new loss function to regularize classification with a constrained clustering loss, hence learning a clustering network with the transferred similarity metric generating the training inputs. Second, for cross-task learning (i.e., unsupervised clustering with unseen categories), we propose a framework to reconstruct and estimate the number of semantic clusters, again using the clustering network. Since the similarity network is noisy, the key is to use a robust clustering algorithm, and we show that our formulation is more robust than the alternative constrained and unconstrained clustering approaches. Using this method, we first show state of the art results for the challenging cross-task problem, applied on Omniglot and ImageNet. Our results show that we can reconstruct semantic clusters with high accuracy. We then evaluate the performance of cross-domain transfer using images from the Office-31 and SVHN-MNIST tasks and present top accuracy on both datasets. Our approach doesn't explicitly deal with domain discrepancy. If we combine with a domain adaptation loss, it shows further improvement.