Traffic processing on cloud-scale bandwidths has given rise to a new type of network structure, comprising a large number of highly-structured virtual entities working in close harmony. This structure, which we call a virtual sub-network, might be in need of migration, for reasons of load-balancing, maintenance, and disaster prevention. In this paper, we argue that the common migration schemes are not adequate for the complexity of this task. Therefore, we present Qanat, a migration system specifically optimized for the live migration of a virtual sub-network in its entirety to a different physical location. We show how Qanat employs widely-used techniques, such as traffic prioritization, buffering, and network tunnels, to overcome the main issues of live migration. In the paper, we categorize the main challenges of the migration task, provide an analytical study of Qanat’s algorithms, and measure its performance metrics through large-scale simulations. We conclude that Qanat can efficiently and transparently migrate virtual sub-networks and can provide a useful tool for system administrators.

Due to the dynamic nature of traffic, networks must rapidly adapt to changing conditions. This is especially true in the context of the control plane which must ensure continuous and seamless operation. Switch migration, the process of changing the controller associated with a switch, is an important tool in facilitating this goal. In this work, we study the problem of minimizing the overall time to migrate a set of switches. We examine the problem subject to constraints on controller resources and QoS groups. We show that the problem is NP-hard and provide heuristic algorithms for solving large instances in practice. Through extensive experiments, we demonstrate that the heuristics achieve performance close to optimal while reducing the running time by several orders of magnitude.

Semidefinite programming is a powerful tool in the design and analysis of approximation algorithms for combinatorial optimization problems. In particular, the random hyperplane rounding method of Goemans and Williamson [ 31 ] has been extensively studied for more than two decades, resulting in various extensions to the original technique and beautiful algorithms for a wide range of applications. Despite the fact that this approach yields tight approximation guarantees for some problems, e.g., Max-Cut , for many others, e.g., Max-SAT and Max-DiCut , the tight approximation ratio is still unknown. One of the main reasons for this is the fact that very few techniques for rounding semi-definite relaxations are known. In this work, we present a new general and simple method for rounding semi-definite programs, based on Brownian motion. Our approach is inspired by recent results in algorithmic discrepancy theory. We develop and present tools for analyzing our new rounding algorithms, utilizing mathematical machinery from the theory of Brownian motion, complex analysis, and partial differential equations. Focusing on constraint satisfaction problems, we apply our method to several classical problems, including Max-Cut , Max-2SAT , and Max-DiCut , and derive new algorithms that are competitive with the best known results. To illustrate the versatility and general applicability of our approach, we give new approximation algorithms for the Max-Cut problem with side constraints that crucially utilizes measure concentration results for the Sticky Brownian Motion, a feature missing from hyperplane rounding and its generalizations.

Load migration protocols have been used for load balancing in network controllers. In this poster, we argue that other network applications (e.g., power saving, network security, failure recovery, etc.) have properties that might require different load migration protocols. We introduce four new load migration protocols and show how they might match different application requirements better. We present preliminary experimental results for one of these protocols that show more than 20%-30% speedup in the total load migration time.

As network traffic and conditions change, the load on different instances of control plane changes. To ensure various control applications can operate continuously and efficiently, we need to migrate the load among controller instances. For this, we need a migration schedule that minimizes the overall migration time while ensuring the quality of service and controller resource constraints. In this poster, we show this problem is NP-hard, and show how a heuristic algorithm performs close to the best existing solution with orders of magnitude reduction in scheduling time.

Semi-definite programming is a powerful tool in the design and analysis of approximation algorithms for combinatorial optimization problems. In particular, the random hyperplane rounding method of Goemans and Williamson [23] has been extensively studied for more than two decades, resulting in various extensions to the original technique and beautiful algorithms for a wide range of applications. Despite the fact that this approach yields tight approximation guarantees for some problems, e.g., Max-Cut, for many others, e.g., Max-SAT and Max-DiCut, the tight approximation ratio is still unknown. One of the main reasons for this is the fact that very few techniques for rounding semi-definite relaxations are known. In this work, we present a new general and simple method for rounding semi-definite programs, based on Brownian motion. Our approach is inspired by recent results in algorithmic discrepancy theory. We develop and present tools for analyzing our new rounding algorithms, utilizing mathematical machinery from the theory of Brownian motion, complex analysis, and partial differential equations. Focusing on constraint satisfaction problems, we apply our method to several classical problems, including Max-Cut, Max-2SAT, and Max-DiCut, and derive new algorithms that are competitive with the best known results. To illustrate the versatility and general applicability of our approach, we give new approximation algorithms for the Max-Cut problem with side constraints that crucially utilizes measure concentration results for the Sticky Brownian Motion, a feature missing from hyperplane rounding and its generalizations.

Feature selection is a fundamental problem in machine learning and data mining. The majority of feature selection algorithms are designed for running on a single machine (centralized setting) and they are less applicable to very large datasets. Although there are some distributed methods to tackle this problem, most of them are distributing the data horizontally which are not suitable for datasets with a large number of features and few number of instances. Thus, in this paper, we introduce a novel vertically distributable feature selection method in order to speed up this process and be able to handle very large datasets in a scalable manner. In general, feature selection methods aim at selecting relevant and non-redundant features (Minimum Redundancy and Maximum Relevance). It is much harder to consider redundancy in a vertically distributed setting than a centralized setting since there is no global access to the whole data. To the best of our knowledge, this is the first attempt toward solving the feature selection problem with a vertically distributed filter method which handles the redundancy with consistently comparable results with centralized methods. In this paper, we formalize the feature selection problem as a diversity maximization problem by introducing a mutual-information-based metric distance on the features. We show the effectiveness of our method by performing an extensive empirical study. In particular, we show that our distributed method outperforms state-of-the-art centralized feature selection algorithms on a variety of datasets. From a theoretical point of view, we have proved that the used greedy algorithm in our method achieves an approximation factor of 1/4 for the diversity maximization problem in a distributed setting with high probability. Furthermore, we improve this to 8/25 expected approximation using multiplicity in our distribution.