Network virtualization allows hosting applications with diverse computation and communication requirements on shared edge infrastructure. Given a set of requests for deploying virtualized applications, the edge provider has to deploy a maximum number of them to the underlying physical network, subject to capacity constraints. This challenge is known as the virtual network embedding (VNE) problem: it models applications as virtual networks, where virtual nodes represent functions and virtual links represent communication between the virtual nodes.All variants of VNE are known to be strongly NP-hard. Because of its centrality to network virtualization, VNE has been extensively studied. We focus on the online variant of VNE, in which deployment requests are not known in advance. This reflects the highly skewed and unpredictable demand intrinsic to the edge. Unfortunately, existing solutions to online VNE do not scale well with the number of requests per second and the physical topology size.We propose a novel approach in which our new online algorithm, Olive, leverages a nearly optimal embedding for an aggregated expected demand. This embedding is computed offline. It serves as a plan that Olive uses as a guide for handling actual individual requests while dynamically compensating for deviations from the plan. We demonstrate that our solution can handle a number of requests per second greater by two orders of magnitude than the best results reported in the literature. Thus, it is particularly suitable for realistic edge environments.

Mobile edge computing offers a myriad of opportunities to innovate and introduce novel applications, thereby enhancing user experiences considerably. A critical issue extensively investigated in this domain is efficient deployment of Service Function Chains (SFCs) across the physical network, spanning from the edge to the cloud. This problem is known to be NP-hard. As a result of its practical importance, there is significant interest in the development of high-quality sub-optimal solutions.In this paper, we consider this problem and propose a novel near-optimal heuristic that is extremely efficient and scalable. We compare our solution to the state-of-the-art heuristic and to the theoretical optimum. In our large scale evaluations, we use realistic topologies which were previously reported in the literature. We demonstrate that the execution time offered by our solution grows slowly as the number of Virtual Network Function (VNF) forwarding graph embedding requests grows, and it handles one million requests in slightly more than 20 seconds for 100 nodes and 150 edges physical topology.

Data scientists and platform engineers who maintain AI stacks are required to continuously run AI workloads. When executing any part of the AI pipeline, whether data preprocessing, training, fine-tuning or inference, a frequent question is how to optimally configure the environment to meet Service Level Objectives (SLOs), such as desired throughput, runtime deadlines, and avoid memory and CPU exhaustion. We present ARISE, a tool that enables making data-driven decisions about AI workload configuration questions. ARISE trains performance prediction machine-learning regression models on historical workloads and performance benchmark metadata, and then predicts the performance of future workloads based on their input metadata, using the best performing regression models. Initial evaluation of ARISE on real-world workloads shows high prediction accuracy.

Mobile edge computing offers ultra-low latency, high bandwidth, and high reliability. Thus, it can support a plethora of emerging services that can be placed in close proximity to the user. One of the fundamental problems in this context is maximizing the benefit from the placement of networked services, while meeting bandwidth and latency constraints. In this study, we propose an adaptive and predictive resource allocation strategy for virtual-network function placement comprising services at the mobile edge. Our study focuses on maximizing the service provider's benefit under user mobility, i.e., uncertainty. This problem is NP-hard, and thus we propose a heuristic solution: we exploit local knowledge about the likely movements of users to speculatively allocate service functions. We allow the service functions to be allocated at different edge nodes, as long as latency and bandwidth constraints are met. We evaluate our proposal against a theoretically optimal algorithm as well as against recent previous work, using widely used simulation tools. We demonstrate that under realistic scenarios, an adaptive and proactive strategy coupled with flexible placement can achieve close-to-optimal benefit.

Hash-based stateful load-balancers employ connection tracking to avoid per-connection-consistency (PCC) violations that lead to broken connections. In this paper, we propose Just Enough Tracking (JET), a new algorithmic framework that significantly reduces the size of the connection tracking tables for hash-based stateful load-balancers without increasing PCC violations.

Consistent hashing is a central building block in many networking applications, such as maintaining connection affinity of TCP flows. However, current consistent hashing solutions do not ensure full consistency under arbitrary changes or scale poorly in terms of memory footprint, update time and key lookup complexity. We present AnchorHash, a scalable and fully-consistent hashing algorithm. AnchorHash achieves high key lookup rate, low memory footprint and low update time. We formally establish its strong theoretical guarantees, and present an advanced implementation with a memory footprint of only a few bytes per resource. Moreover, evaluations indicate that AnchorHash scales on a single core to 100 million resources while still achieving a key lookup rate of more than 15 million keys per second.

This research is done in the context of the SliceNet project [4] that aims to extend 5G infrastructure with cognitive management of cross-domain, cross-layer network slices [1], with emphasis on Quality of Experience (QoE) for vertical industries. The provisioning of network slices with proper QoE guarantees is seen as one of the key enablers of future 5G-enabled networks. The challenge is to assess the QoE experienced by the vertical application and its users without requiring the applications or the users to measure and report QoE related metrics back to the provider. To address this challenge, we propose a method for deriving application-level QoE from network-level Quality of Service (QoS) measurements, easily accessible by the provider. In particular, we describe a PoC where QoE, perceived by application users, is estimated from low level network monitoring data, by applying cognitive methods. Our main goal is enabling the cloud provider to support the desired E2E QoE-based Service Level Agreements (SLAs), e.g. by monitoring QoS metrics within the provider's domain to optimize resource allocation through provider's actuators. Additional benefit can be achieved by applying the same technique to troubleshoot issues in the provider's infrastructure. In this work, we employed classical statistical methods to assess the relationship between the application-level QoE and the network-level QoS.

Given a large variety of resources and billing contracts offered by today’s cloud providers, customers face a nontrivial optimization challenge for their application workloads. A number of works are dealing with either billing contracts selection optimization or resource types selection. We argue that the largest cost savings to elastic workloads result from jointly optimizing heterogeneous resources and billing contracts selection. To this end, we introduce a novel cloud control and management framework and formulate a novel optimization problem called Heterogeneous Resource Reservation (HRR). We evaluate our solution through a thorough simulation study using publicly available cloud workload data as well as internal anonymous customer data. For these data our approach attain dramatic cost savings compared to the current state of the art.

No abstract available.

With a growing number of infrastructure cloud services becoming available there are many benefits to interconnecting several cloud services. However, seamless cloud interoperability is the complex issue, especially when different cloud platforms are interconnected. One of the major aspects of federating clouds resources is network federation. Federated networks must deal not only with heterogeneous cloud platforms, but also with different virtualization technologies and the added complexity of multi-layer virtualization. In order to allow monitoring and analysis of the complex heterogeneous environment, there is a need to present a user with the full aggregated view of the federated network including cloud interconnect and with the match between different layers and platforms. In this paper we present a framework that uses Skydive tool for network monitoring and analysis in BEACON federated network environment.

Operating a cloud-scale service is a huge challenge. There are millions of users worldwide and millions of requests per seconds. For example, Amazon's Simple Storage Service (S3) in 2013 contained two trillion objects and its logs contained 1.1 million log lines per second, which are approximately 10 PB of log records per year (see [1]). Cloud scale implies thousands of servers and network elements, and hundreds of services from multiple cross-regional data centers. Cloud service operation data is scattered over various types of semi-structured and unstructured logs (e.g., application, error, debug), telemetry and network data, as well as customer service records. It is therefore extremely difficult for the multiple owners and administrators in such systems, coming from different units of the organization, to follow the possible paths and system alternatives in order to detect problems, solve issues and understand the service operation.

Hybrid switching combines a high-bandwidth optical circuit switch in parallel with a low-bandwidth electronic packet switch. It presents an appealing solution for scaling datacenter architectures. Unfortunately, it does not fit many traffic patterns produced by typical datacenter applications, and in particular the skewed traffic patterns that involve highly intensive one-to-many and many-to-one communications.

Over the recent years we witness a massive growth of cloud usage, accelerated by new types of 'born-to-the-cloud' workloads. These new types of workloads are increasingly multi-component, dynamic and often present highly intensive communication patterns. Massive innovation of Data Center Network (DCN) technologies is required to support the demand, giving raise to new network topologies, new network control paradigms, and management models. One particularly promising technology candidate for improving the DCN efficiency is Optical Circuit Switching (OCS).

The placement of virtual machines (VMs) on a cluster of hosts under multiple constraints, including administrative (security, regulations) resource-oriented (capacity, energy), and QoS-oriented (performance) is a highly complex task. We define a new high-availability property for a VM; when a VM is marked as k-resilient, as long as there are up to k host failures, it should be guaranteed that it can be relocated to a non-failed host without relocating other VMs. Together with Hardware Predictive Failure Analysis and live migration, which enable VMs to be evacuated from a host before it fails, this property allows the continuous running of YMs on the cluster despite host failures. The complexity of the constraints associated with k-resiliency, which are naturally expressed by Second Order logic statements, prevented their integration into the placement computation until now. We present a novel algorithm which enables this integration by transforming the k-resiliency constraints to rules consumable by a generic Constraint Programming engine, prove that it guarantees the required resiliency and describe the implementation. We provide some preliminary results and compare our high availability support with naive solutions.

Cloud Computing in general and Virtualized Infrastructure Provisioning in particular, are significant trends with the potential to increase agility and lower costs of IT. An emerging cloud service is a virtual server shop, that allows cloud customers to order virtual appliances to be delivered virtually on the cloud. Like physical shops, customers want to customize the ordered products, e.g., have them pre-installed with their desired applications and pre-configured. Global cloud providers need to create customized virtual-server disk images and deliver them on time to meet the customer reservations and service level. This framework creates a new flavor of content distribution over the web, where large virtual server images need to be delivered to the target compute farms (either on the global cloud or on customer private clouds). In order to reduce provisioning time and meet reservation deadlines, one approach is to stage images on storage near the customer. This introduces an optimization problem of finding an optimal staging schedule, according to network bandwidth, pending reservations schedule, and customer value. This problem has some similarities to cache pre-filling and production-line scheduling. It combines scheduling, bandwidth considerations, and storage capacity constraints. In this paper we study the fundamental properties of this approach and formalize several flavors of the related optimization problem. We prove useful properties of the problem and then use those properties to provide exact efficient algorithms to solve it. We also derive efficient approximate solutions with proven error bounds.

User-transparent live migration is one of the most interesting features of Virtual Machine (VM) environments. Current live-migration technologies require that the VM retains its IP network address; therefore, are typically restricted to movement within an IP subnet. The growing number of portable computing devices has led to the development of IP mobility solutions that enable uninterrupted network connectivity while moving between different IP subnets. In this paper we study the application of current network mobility approaches to VM cross-subnet live-migration. We show that although the core problems are similar, there are significant differences between these domains, in terms of both assumptions and requirements. We present a specific solution for live migration of a VM across IP subnets, and introduce a new framework for synchronizing migration and network configuration, which allows better optimization for different scenarios of live migration.

The problems related to supporting multicast connections with quality of service (QoS) requirements are studied. We investigate the problem of optimal resource allocation in the context of performance dependent costs. In this context each network element can offer several QoS guarantees, each associated with a different cost. This is a natural extension to the commonly used bi-criteria model, where each link is associated with a single delay and a single cost. This framework is simple yet strong enough to model many practical interesting networking problems. The fundamental multicast resource allocation problem under this framework is how to optimally allocate QoS requirements on the links of the multicast tree. One needs to partition the end-to-end QoS requirement along the various paths in a tree. The goal is to satisfy the end-to-end QoS requirement with minimum cost. Previous studies under this framework considered single-source multicast connections, where the end-to-end QoS requirement is specified from the source to all other multicast group members. In this paper we extend these results to the more general, and considerably harder case of multicast sessions, where the end-to-end requirement hold for every path between any two multicast group members. Our aim is to provide rigorous solutions, with proven performance guarantees, by way of algorithmic analysis. The problem under investigation is NP hard for general cost functions, thus we first present a pseudopolynomial exact solution. From this solution we derive two efficient /spl epsi/-approximate solutions. One achieves optimal cost, but may violate the end-to-end delay requirement by a factor of (1 + /spl epsi/), and the other strictly obeys the bounds and achieves a cost within a factor of (1+/spl epsi/) of the optimum. Furthermore, we present improved results for discrete cost functions, and give a simple linear-time exact polynomial solution for a specific, and practically interesting, family of convex cost functions.

We investigate the problem of optimal resource allocation for end-to-end QoS requirements on unicast paths and multicast trees. Specifically, we consider a framework in which resource allocation is based on local QoS requirements at each network link, and associated with each link is a cost function that increases with the severity of the QoS requirement. Accordingly, the problem that we address is how to partition an end-to-end QoS requirement into local requirements, such that the overall cost is minimized. We establish efficient (polynomial) solutions for both unicast and multicast connections. These results provide the required foundations for the corresponding QoS routing schemes, which identify either paths or trees that lead to minimal overall cost. In addition, we show that our framework provides better tools for coping with other fundamental multicast problems, such as dynamic tree maintenance.

We investigate the problem of optimal resource allocation for end to-end QoS requirements on unicast paths and multicast trees. Specifically, we consider a framework in which resource allocation is based on local QoS requirements at each network link, and associated with each link is a cost function that increases with the severity of the QoS requirement. Accordingly, the problem that we address is how to partition an end-to-end QoS requirement into local requirements, such that the overall cost is minimized. We establish efficient (polynomial) solutions for both unicast and multicast connections. These results provide the required foundations for the corresponding QoS routing schemes, which identify either paths or trees that lead to minimal overall cost. In addition, we show that our framework provides better tools for coping with other fundamental multicast problems, such as dynamic tree maintenance.

This article considers the problem of routing connections with QoS requirements across networks, when the information available for making routing decisions is inaccurate. This uncertainty about the actual state of a network component arises naturally in a number of different environments, which are reviewed in the paper. The goal of the route selection process is then to identify a path that is most likely to satisfy the QoS requirements. For end to end delay guarantees, this problem is intractable. However we show that by decomposing the end-to-end constraint into local delay constraints, efficient and tractable solutions can be established. We first consider the simpler problem of decomposing the end-to-end constraint into local constraints, for a given path. We show that, for general distributions, this problem is also intractable. Nonetheless, by defining a certain class of probability distributions, which posses a certain convexity property, and restricting ourselves to that class, we are able to establish efficient and exact solutions. Moreover, we show that typical distributions would belong to that class. We then consider the general problem, of combined path optimization and delay decomposition. We present an efficient solution scheme for the above class of probability distributions. Our solution is similar to that of the restricted shortest-path problem, which renders itself to near-optimal approximations of polynomial complexity. We also show that yet simpler solutions exist in the special case of uniform distributions.

We consider the problem of routing connections with quality of service (QoS) requirements across networks when the information available for making routing decisions is inaccurate. Such uncertainty about the actual state of a network component arises naturally in a number of different environments. The goal of the route selection process is then to identify a path that is most likely to satisfy the QoS requirements. For end-to-end delay guarantees, this problem is intractable. However, we show that by decomposing the end-to-end constraint into local delay constraints, efficient and tractable solutions can be established. Moreover, we argue that such decomposition better reflects the interoperability between the routing and reservation phases. We first consider the simpler problem of decomposing the end-to-end constraint into local constraints for a given path. We show that, for general distributions, this problem is also intractable. Nonetheless, by defining a certain class of probability distributions, which includes typical distributions, and restricting ourselves to that class, we are able to establish efficient and exact solutions. We then consider the general problem of combined path optimization and delay decomposition and present efficient solutions. Our findings are applicable also to a broader problem of finding a path that meets QoS requirements at minimal cost, where the cost of each link is some general increasing function of the QoS requirements from the link.