Cloud providers commonly employ oversubscription strategies to maximize profitability, leveraging the significant gap between the resources purchased by tenants and those actually consumed by their workloads. However, the temporal volatility of workloads may lead to overload on oversubscribed nodes. To address this issue, existing works typically focus on designing reactive rescheduling mechanisms triggered by overload events or adopt conservative oversubscription strategies to mitigate overload risks. Nonetheless, these solutions compromise either tenant experience or provider profitability. In fact, reducing the temporal volatility of workloads is key to addressing the above challenges. We observe that many workloads exhibit temporal complementarity. Aggregating such workloads can effectively mitigate temporal volatility, thereby improving overall resource utilization. Motivated by this insight, we first design a new metric, called Maximum-based Coefficient of Variation (MCV), to quantify the temporal volatility of workloads. We then propose Hestia, a framework that achieves long-term stable oversubscription through workload aggregation. Specifically, we propose a smoothing-based method to classify workloads suitable for aggregation according to their periodicity. Subsequently, we design an aggregation algorithm to minimize the overall MCV, and treat the aggregated workloads as the units for oversubscription. Experimental results show that, using CPU as a representative example, Hestia reduces MCV by 43.3% and increases oversubscription profit by 66.74%.

Virtual private clouds (VPCs) play a critical role in providing secure and isolated network environments for web services. However, with the growing number and size of VPCs, efficiently delivering control messages from the control plane to the data plane has become a major concern for cloud vendors. Existing end-to-end transmission solutions (e.g., RPC) will result in substantial overhead in the control plane, while message-oriented middleware-based solutions (e.g., message queue) will lead to high data plane overhead. To address this issue, we design Meteor, a high-performance control message delivery system for large-scale clouds. Specifically, Meteor combines an RPC path with a message queue (MQ) path and employs an auto dual-path switching mechanism to minimize the message delivery latency. Additionally, we propose a VPC-based message delivery and filtering scheme for the MQ path to reduce data plane overhead. We also design a delivery robustness guarantee mechanism to ensure the reachability and consistency of control messages. Meteor has been thoroughly tested with up to 100k container instances. Evaluation results show that Meteor decreases the message delivery latency by 48.8% and reduces the overhead by about 50% in real-world scenarios, compared with state-of-the-art solutions.

Ensuring reliable operation of cloud networks is critical for cloud service providers to guarantee quality of service for tenants. A promising solution is to design a high-fidelity cloud network validation platform that proactively validates the correctness of all operations before implementing changes to the production network. However, the tight coupling between physical and virtual networks in the cloud poses challenges to achieving high-fidelity cloud network validation. Existing network validation platforms focus primarily on traditional physical networks, while ignoring virtual network validation. Regrettably, neglecting the combined validation of physical and virtual networks will result in inaccurate evaluations. To bridge this gap, we present HifiCNet, a high-fidelity platform that concurrently validates both physical and virtual networks. HifiCNet designs an orchestrator to elegantly coordinate the interaction between physical and virtual networks in the cloud and innovatively adopts an emulator-simulator hybrid architecture to ensure high fidelity and scalability for cloud network validation. Through extensive evaluation based on real topologies and traffic traces, we show that HifiCNet enables high-fidelity validation of cloud network configurations, services, and exceptions. Notably, HifiCNet can leverage 38 servers to establish a physical network comprising 10k hosts, as well as a virtual network consisting of 200k virtual machines.

The increasing demands of tenants are driving the growth of single virtual private cloud (VPC), leading to a trend towards cross-cluster VPC deployments, which fuels an increasing demand for cross-cluster VPC communication. However, the rapid growth of cross-cluster traffic and its inherently dynamic nature have exposed critical limitations in existing network solutions, which now struggle to maintain required throughput levels and ensure reliable communication. This growing inadequacy has consequently created persistent network performance bottlenecks in cross-cluster communication systems. To address this issue, we present HiReC, a system designed to achieve high-throughput and reliable cross-cluster VPC communication. To optimize throughput performance, HiReC leverages multiple gateways with a rounding-based mapping algorithm that ensures effective load balancing to forward cross-cluster traffic. Furthermore, HiReC augments gateway forwarding efficiency through implementation of the eXpress Data Path (XDP) framework, leveraging kernel-bypass techniques to accelerate packet processing. For reliability enhancement, HiReC employs a low-overhead, eBPF-based monitoring module and adaptive load adjustment mechanism to dynamically adjust traffic distribution among gateways, effectively handling gateway node or link failures. We implement our system and evaluate its performance through testbed experiments and simulation experiments. The results show that HiReC can effectively improve the throughput of cross-cluster communication and deal with abnormal events. For example, HiReC improves the throughput by$3.8\times $and reduces the failure recovery latency by$19\times $compared with state-of-the-art solutions.

Distributed training (DT) has emerged as a solution to address the growing computational resource demands of training large-scale machine learning models. To meet this need, cloud providers typically build GPU clusters to accommodate DT jobs. For DT job requests, cloud providers need to determine in which GPUs place workers (i.e., job placement). Existing approaches usually place workers on as few idle machines as possible to minimize communication time. However, this scheme will lead to aresource fragmentation problem, which degrades the resource utilization rate of the GPU cluster and increases training costs for cloud providers. In this paper, we propose$\textsf {Titan}$, a novel job placement scheme that mitigates the influence of resource fragmentation by enhancing the utilization of non-idle machines. To further optimize resource allocation, we introduce a dynamic defragmentation algorithm that migrates fragmented jobs to consolidate GPU resources, enabling efficient placement of large-scale training jobs.$\textsf {Titan}$formulates a multi-objective non-linear optimization problem and proves its NP-hardness. To solve this problem,$\textsf {Titan}$presents an effective submodular-based greedy algorithm with a tight approximation ratio ($1-\frac {1}{e}$). We evaluate$\textsf {Titan}$with a large-scale simulation employing real-world job traces and a small-scale testbed consisting of 8 servers with 32 logical GPUs. Experimental results show that$\textsf {Titan}$can achieve near-optimal training throughput while improving the efficiency of the cluster by 74.9% compared to the state-of-the-art solutions.

Enterprise tenants access networks with committed bandwidth quotas shared among multiple departments and diverse services within each department. As a result, cloud vendors need to simultaneously fulfill two requirements, i.e., committed bandwidth guarantee and tenant-specified service bandwidth allocation. Hierarchical bandwidth allocation is a widely used technology that satisfies both requirements. In traditional schemes, each tenant's traffic is processed by a single node, potentially leading to single-node failures. Previous works have enhanced reliability by extending existing schemes to distributed systems with tenant-level bandwidth allocation, but fail to meet both requirements simultaneously. To bridge this gap, we propose S-DAL, which can achieve both requirements through servicelevel distributed hierarchical bandwidth allocation. We introduce an efficient fluid model-based algorithm for bandwidth allocation and employ a memory utilization based flow rate estimation mechanism to deliver accurate flow rate measurements. Additionally, we integrate a burst detection to mitigate excessive packet loss caused by burst traffic. Through testbeds and simulations, we demonstrate that S-DAL effectively ensures tenant-specified service bandwidth allocation while only reducing the shortfall in committed bandwidth to less than 0.23%.

The increasing demands of tenants are driving the growth of single virtual private cloud (VPC), leading to a trend towards cross-cluster VPC deployments, which fuels an increasing demand for cross-cluster VPC communication. However, with the rapid increase in cross-cluster traffic and its inherent dynamism, existing solutions fail to meet tenants' demands for throughput and reliability, thereby leading to network performance bottlenecks in cross-cluster communication. To address this issue, we present HiReC, a system designed to achieve high-throughput and reliable cross-cluster VPC communication. To improve throughput, HiReC leverages multiple gateways with a rounding-based mapping algorithm for load balancing to forward cross-cluster traffic. Moreover, we further enhance the forwarding capabilities of gateways with the eXpress Data Path (XDP) technology. To enhance reliability, HiReC employs a low-overhead, eBPF-based monitoring module and adaptive load adjustment mechanism to dynamically adjust traffic distribution among gateways, effectively handling gateway node or link failures. We implement our system and evaluate its performance through testbed experiments. The results show that HiReC can effectively improve the throughput of cross-cluster communication and deal with abnormal events. For example, HiReC improves the throughput by$3.88 \times$and reduces the failure recovery latency by$19 \times$compared with state-of-the-art solutions.

Cloud vendors provide network services to tenants through shared service nodes, which may cause the abnormal traffic of one tenant to affect others. Deploying auxiliary systems such as firewalls will reduce the frequency of abnormal traffic occurrences but cannot eliminate them entirely. In practice, proper tenant deployment is a promising method to pursue anomaly isolation. Previous works have explored solutions along this line, such as controlling the impact scope of abnormal traffic to mitigate the influence of anomalies among tenants. However, these solutions cannot ensure full anomaly isolation among all tenants. That is, an anomaly in one tenant may cause complete service disruption for another tenant. To bridge the gap, we study the problem of multi-tenant Deployment with Anomaly Isolation (DAI), which is NP-hard. To address this problem, this paper introduces R-DAI, a rounding-based algorithm that can provide a tenant deployment solution in polynomial time, ensuring anomaly isolation among all tenants and load balancing. We implement our proposed algorithm on a large-scale simulation, and the results demonstrate its superior performance. For example, our algorithm eliminates tenant service disruptions caused by abnormal traffic and reduces the impact scope of a service node failure by 53% compared with other alternatives.

Deep learning (DL) has seen a growing dataset, an expanding model scale, and increasing applications in recent years. There is a notable trend of shifting DL training jobs from local computing units to powerful DL clusters built by cloud providers. These clusters allocate physical training nodes to DL jobs through a process referred to as multi-job placement. Existing multi-job placement strategies fail to achieve high efficiency in resource utilization, DL training, and robustness simultaneously, resulting in poor performance when resources are limited or when abnormalities occur in some devices. To tackle these challenges, we present CROP, an approach that performs efficient and robust multi-job placement in DL clusters. We formulate the efficient and robust multi-job placement problem as a non-linear program and prove its NP-hardness. To solve this problem, we present an effective submodular-based algorithm with a tight approximation factor of ($1-1/e$). We evaluate CROP on a small-scale testbed consisting of 8 physical GPUs and a large-scale simulation employing real-world job traces. Experimental results demonstrate that CROP achieves nearoptimal communication overhead while improving the training throughput of the DL cluster by up to$57.5\%$compared to state-of-the-art solutions.

The growing reliance on cloud services has made availability critical for global business continuity. To mitigate disruptions caused by cloud outages, many large-scale applications maintain core functionality through multi-instance deployments. To support this, cloud providers enable cross-AZ deployments to deliver high availability. However, pursuing high availability must be balanced against cost efficiency, which presents three key challenges: electricity price disparity, application affinity requirement, and disaster recovery demand. Existing research primarily focuses on single-region optimization, often overlooking the potential benefits of multi-region deployment in cost and availability. While some works explore multi-region deployment strategies, they fail to address application affinity or disaster recovery requirements, resulting in low application availability. To address this issue, we propose CARD, a cost-efficient and availability-aware application deployment scheme in geodistributed clouds. Specifically, we formulates this problem as a mixed-integer nonlinear program and designs an efficient approximation algorithm based on submodular function, achieving an approximation ratio of ($1-1 / e$). Large-scale simulations on realworld datasets demonstrate the algorithm's effectiveness, overall reducing costs by 20% – 50% and improving availability by 90% compared to existing solutions.

Kubernetes is widely adopted by enterprises to enhance service availability for applications such as web services and large-scale model training, due to its advantages in managing containerized applications. As service demands increase, a single Kubernetes cluster often becomes insufficient, leading to the trend of using multiple clusters to improve service scalability. However, achieving efficient cross-cluster communication poses significant challenges due to the need for low latency, high throughput, and strong robustness. Existing methods for cross-cluster communication either employ a centralized control plane, which becomes a communication bottleneck, or use numerous service-bound proxies, leading to increased management complexity and possibly compromised robustness in cross-cluster communication.

Motivated by the need to reduce vendor lock-in and address concerns regarding dedicated hardware availability, cloud applications have increasingly adopted a multi-cloud deployment strategy, in which cloud applications are deployed in different zones associated with various cloud service providers. When deploying cloud applications in multi-clouds, there are three crucial and coupled metrics:deployment cost,access delayandtraffic demand. Unfortunately, existing works overlook either the data transfer cost in deployment cost or the access delay and traffic demand requirements, resulting in high operating costs or low user QoS. To bridge this gap, this paper proposes theCost-EfficientApplicationDeployment Framework (CADER) with tenant requirement guarantee in multi-clouds environment. However, due to the challenges of service price heterogeneity, transfer cost diversity, and resource limitation, achieving cost-efficient cloud application deployment while satisfying all tenant requirements is not an easy task. To tackle this issue, we design an approximate algorithm based on the random rounding method and prove that its approximate ratio is$O(\log g)$, where$g$is the number of cloud zones. Results of in-depth simulations indicate that CADER can reduce the application deployment cost ranging from 16% to 38% compared to commonly used alternatives while ensuring the satisfaction of tenant requirements.

Distributed training (DT) has emerged as a solution to address the growing computational resource demands of training large-scale machine learning models. To meet this need, major cloud providers typically build GPU clusters to accommodate DT jobs. Specifically, for an incoming DT job request, cloud providers need to determine in which GPUs place workers (i.e., worker placement). Existing approaches usually place workers on as few idle machines as possible to minimize communication time. However, this scheme will lead to resource fragmentation problem, which degrades the efficiency of the GPU cluster and increases training costs for cloud providers. In this paper, we propose Titan, a novel worker placement scheme that mitigates the influence of resource fragmentation by enhancing the utilization of non-idle machines. Titan formulates a multi-objectives non-linear optimization problem that incorporates the collective communication constraint and proves its NP-hardness. To solve the problem, Titan presents an effective submodular-based greedy algorithm with a tight approximation ratio ($1-\frac{1}{e}$). We evaluate Titan with a large-scale simulation employing real-world job traces and a small-scale testbed consisting of 8 servers with 32 logical GPUs. Experimental results show that Titan can achieve near-optimal training throughput while improving the efficiency of the cluster by 74.9% compared to the state-of-the-art solutions.

Ensuring reliable operation of cloud networks is critical for cloud service providers to guarantee quality of service for tenants. A promising solution is to design a high-fidelity cloud network validation platform that proactively validates the correctness of all operations before implementing changes to the production network. However, the tight coupling between physical and virtual networks in the cloud poses challenges to achieving high-fidelity cloud network validation. Existing network validation platforms focus primarily on traditional physical networks, while ignoring virtual network validation. Regrettably, neglecting the combined validation of physical and virtual networks will result in inaccurate evaluations. To bridge this gap, we present HifiCNet, a high-fidelity platform that concurrently validates both physical and virtual networks. HifiCNet designs an orchestrator to elegantly coordinate the interaction between physical and virtual networks in the cloud and innovatively adopts an emulator-simulator hybrid architecture to ensure high fidelity and scalability for cloud network validation. Through extensive evaluation based on real topologies and traffic traces, we show that HifiCNet enables high-fidelity validation of cloud network configurations, services, and exceptions. Notably, HifiCNet can use 38 servers to establish a physical network comprising 10k hosts, and a virtual network consisting of 200 k virtual machines.

Distributed training has emerged as a critical application in clusters due to the widespread adoption of AI technology across various domains. However, as distributed training continues to advance, it has become increasingly time-consuming. To address this challenge, researchers have explored leveraging In-Network Aggregation (INA) to expedite distributed model training. Specifically, by harnessing programmable hardware, such as Intel Tofino switches, INA can aggregate gradients within the network, thereby reducing the amount of gradient transmission and accelerating distributed training. However, previous works assume fixed routing selection and batch size, ignoring their impact on model convergence and resulting in extended completion time. To bridge this gap, we propose InGo, a pioneering approach that considers both in-network aggregation routing and batch size adjustment, and provide the rigorous convergence analysis. Then, we formally define the problem of in-network aggregation routing with batch size adjustment, and present an efficient algorithm with bounded approximation factors to solve this problem. Through extensive experiments on both physical platforms and simulated environments, we demonstrate that InGo significantly reduces the completion time by 25.2%-74.7% compared to state-of-the-art solutions.

Driving southbound messages from a cloud control plane down to the distributed data plane on every compute node is one of the critical challenges in public clouds. Existing message delivery solutions solely based on remote procedure call (RPC) or message queue (MQ) tend to overlook strict resource constraints, e.g., network bandwidth and CPU capacity. This often results in extensive overhead in the control plane or message redundancy in the data plane, especially when a cloud receives highly concurrent user requests or experiences a rapid expansion. To this end, we design a dual-channel southbound message delivery framework, namely SMART, which combines an RPC channel with an MQ channel, to maximize the resource utilization in the cloud network. In the control plane, we implement a message parsing mechanism and propose a delivery channel selection algorithm based on the deep reinforcement learning (DRL) approach to support efficient dual-channel delivery under resource constraints. In the data plane, we design a message agent on each compute node to ensure the order preservation and state consistency of southbound messages. Both experimental and large-scale simulation results show that SMART demonstrates a reduction in control plane overhead by 64% compared to RPC and redundant messages by 45% compared to MQ, respectively.

Facing the huge volume of traffic and intensive traffic dynamics, the traditional datacenter architectures are behind the curve due to the fixed topology and the demand-oblivious nature. Driven by the traffic pattern, the reconfigurable technologies, like optical circuit switches (OCSes), are a promising alternative to further improve throughput when facing traffic dynamics, thanks to the high bandwidth and low reconfiguration time. However, existing works on OCSes are relatively elementary. Some of previous works only deploy single OCS which cannot adapt to large-scale datacenters, while others either cannot guarantee near-optimality or overlook practical issues like limited fiber capacity. These solutions may cause low throughput and long reconfiguration time, resulting in poor QoS. In this paper, we present Leaf to maximize throughput thus to further improve QoS, by deploying multiple OCSes to carry traffic in a cooperation manner. Furthermore, we also show its efficient reconfiguration ability and near-optimality. The formulated problem is a new k-weight limited matching problem and is proven to be N P-hard, which can be solved by a new proposed approximation algorithm with bounded approximation ratio. To evaluate our proposed solution, simulation experiments are conducted with both real-world and synthetic datasets. Compared with state-of-the-arts works, Leaf can improve throughput by 42.16%−68.92%, and reduce runnning time by 68.87%−78.72%.

Deep learning has brought about a revolutionary transformation in network applications, particularly in domains like e-commerce and online advertising. Distributed training (DT), as a critical means to expedite model training, has progressively emerged as a key foundational infrastructure for such applications. However, with the rapid advancement of hardware accelerators, the performance bottleneck in DT has shifted from computation to communication. In-network aggregation (INA) solutions have shown promise in alleviating the communication bottleneck. Regrettably, current INA solutions primarily focus on improving efficiency under the traditional parameter server (PS) architecture and do not fully address the communication bottleneck caused by limited PS ingress bandwidth. To bridge this gap, we propose InArt, the first work to introduce INA with routing selection in a multi-PS architecture. InArt employs a multi-PS architecture to split DT tasks among multiple PSs, and selects appropriate routing schemes to fully harness INA capabilities. To accommodate traffic dynamics, InArt adopts a two-phase approach: splitting the training model among multiple parameter servers and selecting routing paths for INA. We propose Lagrange multiplier and randomized rounding algorithms for these phases, respectively. We implement InArt and evaluate its performance through experiments on physical platforms (Tofino switches) and Mininet emulation (P4 Software Switches). Experimental results show that InArt can reduce communication time by 48%\!\sim57\!% compared with state-of-the-art solutions.

The surging scale of distributed training (DT) incurs significant communication overhead in datacenters, while a promising solution is in-network aggregation (INA). It leverages programmable switches (e.g., Intel Tofino switches) for gradient aggregation to accelerate DT tasks. Due to switches’ limited on-chip memory size, existing solutions try to design the memory sharing mechanism for INA. This mechanism requires gradients to arrive at switches synchronously, while network dynamics make it common for the asynchronous arrival of gradients, resulting in existing solutions being inefficient (e.g., massive communication overhead). To address this issue, we propose GOAT, the first-of-its-kind work on gradient scheduling with collaborative in-network aggregation, so that switches can efficiently aggregate asynchronously arriving gradients. Specifically, GOAT first partitions the model into a set of sub-models, then decides which sub-model gradients each switch is responsible for aggregating exclusively and to which switch each worker should send its sub-model gradients. To this end, we design an efficient knapsack-based randomized rounding algorithm and formally analyze the approximation performance. We implement GOAT and evaluate its performance on a testbed consisting of 3 Intel Tofino switches and 9 servers. Experimental results show that GOAT can speed up the DT by$1.5 \times $compared to the state-of-the-art solutions.

In a multi-tenant cloud, the cloud service provider (CSP) leases physical resources to tenants in the form of virtual machines (VMs) with an agreed service level agreement (SLA). As the most important indicator of SLA, we should guarantee the service availability of tenants when placing the VMs. However, previous works about VM placement mainly concentrate on optimizing the cloud resource utilization, but only a few works consider the service availability by measuring the hardware availability. In fact, abnormal tenants can make the corresponding service unavailable by launching network attacks. That is, both the hardware availability and the tenant uncertainty will affect the service availability of VMs on physical machines (PMs). Without considering this factor, the CSP may fail to meet the tenant’s SLA requirements, leading to a reduction in revenue. To solve such a problem, this paper considers the service availability in terms of both the hardware availability and the tenant uncertainty, and studies the service availability-guaranteed VM placement in multi-tenant clouds (SAG-VMP) problem. This problem is very challenging since the service availability actually changes with the tenants served on the PM. To address this issue, we propose a two-phase approach: PM assignment and VM placement. The first phase determines the availability of each PM through a long-term tenant-PM mapping algorithm and the second phase places each VM on a PM that meets the service availability requirement based on a primal-dual online algorithm. Two algorithms with bounded approximation factors are proposed for these two phases, respectively. Both small-scale experiment results and large-scale simulation results show the superior performance of our proposed algorithms compared with other alternatives.

Cloud infrastructure has gradually displayed a tendency of geographical distribution in order to provide anywhere, anytime connectivity to tenants all over the world. The tenant task placement in geo-distributed clouds comes with three critical and coupled factors:regional diversity in electricity prices,access delay for tenants, andtraffic demand among tasks. However, existing works disregard either the regional difference in electricity prices or the tenant requirements in geo-distributed clouds, resulting in increased operating costs or low user QoS. To bridge the gap, we design a cost optimization framework for tenant task placement in geo-distributed clouds, called TanGo. However, it is non-trivial to achieve an optimization framework while meeting all the tenant requirements. To this end, we first formulate the electricity cost minimization for task placement problem as a constrained mixed-integer non-linear programming problem. We then propose a near-optimal algorithm with a tight approximation ratio$(1-1/e)$using an effective submodular-based method. Results of in-depth simulations based on real-world datasets show the effectiveness of our algorithm as well as the overall 10%-30% reduction in electricity expenses compared to commonly-adopted alternatives.

With the increase in both the model size and dataset size of distributed training (DT) tasks, communication between the workers and parameter servers (PSs) in a cluster has become a bottleneck. In-network aggregation (INA) enabled by programmable switches has been proposed as a promising solution to alleviate the communication bottleneck. However, existing works focused on in-network aggregation implementation based on simple DT placement and fixed routing policies, which may lead to a large communication overhead and inefficient use of resources (e.g., storage, computing power and bandwidth). In this paper, we propose PARING, the first-of-its-kind INA approach that jointly optimizes DT task placement and routing in order to reduce traffic volume and minimize communication time. We formulate the problem as a nonlinear multi-objective mixed-integer programming problem, and prove its NP-Hardness. Based on the concept of Steiner trees, an algorithm with bounded approximation factors is proposed for this problem. Large-scale simulations show that our algorithm can reduce communication time by up to 81.0% and traffic volume by up to 19.1% compared to the state-of-the-art algorithms.

Distributed training includes two important operations: gradient transmission and gradient aggregation, which will consume massive bandwidth and computing resources. To achieve efficient distributed training, one must overcome two critical challenges: heterogeneity of bandwidth resources and limitation of computing resources among compute nodes. Existing architectures based on Parameter Server (PS) and All-Reduce (AR) fail to cope with these challenges because the PS will aggregate gradients from all workers and suffers from bandwidth bottlenecks, while AR intends to alleviate bandwidth bottlenecks at the PS, but the workers need to process many gradient packets thus can be overloaded. To address these shortcomings, we design a new distributed training system called ALEPH. In the control plane, ALEPH uses an efficient algorithm to group workers into clusters with different sizes so as to fully utilize heterogeneous bandwidth. We show that the proposed algorithm can achieve a good approximation performance. In the data plane, ALEPH leverages, for the first time, extended Berkeley Packet Filter (eBPF) programs to aggregate and forward gradient packets to reduce computation overhead. We show how to overcome several hurdles in using eBPF for distributed training. We implement ALEPH and evaluate its performance on a small-scale testbed and large-scale simulations. Experimental results show that ALEPH reduces training time by 20%-31% and increases bandwidth utilization by 88% compared with state-of-the-art frameworks.

With the growth of model/dataset/system size for distributed model training in datacenters, the widely used Parameter Server (PS) architecture suffers from communication bottleneck of gradient transmission. Recent works attempt to utilize programmable switches to implement in-network gradient aggregation and alleviate communication bottlenecks on PSs. Due to the limited on-chip memory of programmable switches, gradient transmission requires strict synchronization to achieve ideal aggregation performance. However, the distributed training system is usually heterogeneous in datacenters (e.g., computation and bandwidth heterogeneity), and the gradient will reach the aggregation nodes asynchronously, thereby seriously affecting the aggregation performance. To solve the above issue, we propose XAgg, which accelerates heterogeneous gradient aggregation by deploying the eXpress Data Path (XDP) based aggregator on servers. Specifically, the abundant idle memory on servers can cache the entire gradient, so as to effectively deal with asynchronous gradient transmission in heterogeneous scenarios. Moreover, XDP can provide high-performance and low-latency gradient aggregation. We conduct microbenchmark and testbed with real-world DNN models and datasets. Experimental results show that XAgg improves the gradient aggregation throughput by 3.3$\times$compared with TCP-based aggregation, reaching 100 Gbps with 10 CPU cores. In addition, XAgg reduces communication time by 49%-82% compared with state-of-the-art solutions.

In a commercial cloud, service providers (e.g., video streaming service provider) rent resources from cloud vendors (e.g., Google Cloud Platform) and provide services to cloud users, making a profit from the price gap. Cloud users acquire services by forwarding their requests to corresponding servers. In practice, as a common scenario, traffic dynamics will cause server overload or load-unbalancing. Existing works mainly deal with the problem by two methods: elastic resource provisioning and request updating. Elastic resource provisioning is a fast and agile solution but may cost too much since service providers need to buy extra resources from cloud vendors. Though request updating is a free solution, it will cause a significant delay, resulting in a bad users’ QoS. In this paper, we present a new scheme, called real-time request updating with elastic resource provisioning (TRUST), to help service providers pay less cost with users’ QoS guarantee in clouds. In addition, we propose an efficient algorithm for TRUST with a bounded approximation factor based on progressive-rounding. Both small-scale experiment results and large-scale simulation results show the superior performance of our proposed algorithm compared with state-of-the-art benchmarks.

There are two conventional methods to establish an entanglement connection in a Quantum Data Networks (QDN). One is to create single-hop entanglement links first and then connect them with quantum swapping, and the other is forwarding one of the entangled photons from one end to the other via all-optical switching at intermediate nodes to directly establish an entanglement connection. The two methods both have pros and cons. Respectively, the former method has a higher success probability of constructing entanglement link, but it would consume more quantum resources. The latter method, however, has a lower success probability to deliver a photon across multiple quantum links with fewer quantum resources. Accordingly, we are expecting to establish significantly more entanglement connections with limited quantum resources by first creating entanglement segments, each spanning multiple quantum link, using all-optical switching, and then connecting them with quantum swapping. In this paper, we design SEE, a Segmented Entanglement Establishment approach that seamlessly integrates quantum swapping and all-optical switching to maximize quantum network throughput. SEE first creates entanglement segments over one or multiple quantum links with all-optical switching, and then connect them with quantum swapping. Accordingly, SEE can theoretically outperform conventional entanglement link-based approaches. Large scale simulations show that SEE can achieve up to 100.00% larger throughput compared with the state-of-the-art entanglement link-based approaches, e.g., Redundant Entanglement Provisioning and Selection (REPS).

As the parameter scale of large-scale models continues to increase, distributed model training imposes significant communication overhead in data centers, resulting in reduced training efficiency. To address this challenge, a promising solution, called in-network aggregation, is proposed to mitigate the bandwidth bottleneck in data centers by aggregating gradients within network. However, existing works mainly rely on programmable switches to implement in-network aggregation, while programmable switches have limited memory resources, which makes it hard to storage parameter with large size. Moreover, programmable switches are not yet widely deployed in current data centers, resulting in poor availability. To overcome this limitation, we leverage servers with idle resources in data centers for in-network aggregation, since servers have more powerful storage capabilities compared with programmable switches. Specifically, we formally formulate the problem of server-based in-network aggregation. An efficient approximate algorithm with bounded approximation factor is proposed to select servers with idle resources and paths for model aggregation. Our extensive simulations show that our proposed method can reduce communication time by 38.4%-60.1% compared to state-of-the-art solutions.

Cloud computing plays an increasingly vital role in both commercial and personal services. In multi-tenant clouds, cloud providers encounter challenges such as physical machine failures and malicious tenant attacks. Ensuring the reliability and robustness of cloud remain significant and complex challenges for cloud providers to improve quality of service and profitability. Previous works either fail to strike a balance between these aspects or result in resource waste and increased costs. In this paper, we propose an innovative virtual machine placement solution without additional resource overhead. Specifically, we place tenants’ virtual machines (VMs) on physical machines (PMs) that meet the reliability requirements specified in the service level agreement, while also limiting the number of PMs to mitigate the impact of malicious attacks, thereby enhancing the robustness of the cloud. However, the dynamic nature of tenant traffic exacerbates the complexity of the problem. To tackle this challenge, we present KR-OPD, a two-stage algorithm with superior competitive ratios. Through large-scale simulations and small-scale testbed, KR-OPD outperforms existing state-of-the-art solutions. For example, our algorithm reduces the affected range of tenants by 47%-64% and the packet loss rate of PM nodes by over 70% compared with other alternatives.

Cloud infrastructure has gradually displayed a tendency of geographical distribution in order to provide anywhere, anytime connectivity to tenants all over the world. The tenant task placement in geo-distributed clouds comes with three critical and coupled factors: regional diversity in electricity prices, access delay for tenants, and traffic demand among tasks. However, existing works disregard either the regional difference in electricity prices or the tenant requirements in geo-distributed clouds, resulting in increased operating costs or low user QoS. To bridge the gap, we design a cost optimization framework for tenant task placement in geo-distributed clouds, called TanGo. However, it is non-trivial to achieve an optimization framework while meeting all the tenant requirements. To this end, we first formulate the electricity cost minimization for task placement problem as a constrained mixed-integer non-linear programming problem. We then propose a near-optimal algorithm with a tight approximation ratio (1 − 1/e) using an effective submodular-based method. Results of in-depth simulations based on real-world datasets show the effectiveness of our algorithm as well as the overall 10%-30% reduction in electricity expenses compared to commonly-adopted alternatives.

The rapid growth of cloud services has brought a significant increase in inter-datacenter traffic. To transfer data among geographically distributed datacenters, cloud providers need to purchase bandwidth from ISPs. The data transferring cost has become one of the major expenses for cloud providers. Therefore, it is essential for a cloud provider to carefully allocate inter-datacenter traffic among the ISPs' links to minimize the costs. Exiting solutions mainly focus on the situations where all links adopt the same pricing scheme. However, in practice, ISPs usually provide multiple pricing schemes for their links due to market competition, which makes the existing solutions nonoptimal. Thus, a new traffic engineering approach that considers various pricing schemes is needed. This paper presents COIN, a new framework for cost-efficient traffic engineering with various pricing schemes. We propose a partition rounding traffic engineering algorithm based on linear independence analysis. The approximation factors and time complexity are formally analyzed. We further conduct large-scale simulations with real- world topologies and datasets. Extensive simulation results show that COIN can save the data transferring cost by up to 54.54% compared with the state-of-the-art solutions.

The surging scale of distributed training (DT) incurs significant communication overhead in datacenters, while a promising solution is in-network aggregation (INA). It leverages programmable switches (e.g., Intel Tofino switches) for gradient aggregation to accelerate the DT. Due to switches' limited on-chip memory size, existing solutions try to design the memory sharing mechanism for INA. This mechanism requires gradients to arrive at switches synchronously, while network dynamics make it common for the asynchronous arrival of gradients, resulting in existing solutions being inefficient (e.g., massive communication overhead). To address this issue, we propose GOAT, the first-of-its-kind work on gradient scheduling with collaborative in-network aggregation, so that switches can efficiently aggregate asynchronously arriving gradients. Specifically, GOAT first partitions the model into a set of sub-models, then decides which sub-model gradients each switch is responsible for aggregating exclusively and to which switch each worker should send its sub-model gradients. To this end, we design an efficient knapsack-based randomized rounding algorithm and formally analyze the approximation performance. We implement GOAT and evaluate its performance on a testbed consisting of 3 Intel Tofino switches and 9 servers. Experimental results show that GOAT can speed up the DT by 1.5× compared to the state-of-the-art solutions.

To distill more information from training data, more parameters are introduced into machine learning models. As a result, communication becomes the bottleneck of Distributed Machine Learning (DML) systems. To alleviate the communication resource contention among DML jobs, which prolongs the time to train machine learning models, in machine learning clusters, JointPS is proposed in this paper. JointPS first minimizes the completion time of a single training epoch for each DML job via jointly optimizing the parameter server placement and flow scheduling, and predicts the number of remaining training epochs for each DML job by leveraging a dynamic model fitting method. Then, JointPS can estimate the remaining time to complete each DML job. According to such estimation, JointPS schedules DML jobs following the Minimum Remaining Time First (MRTF) principle to minimize the average job completion time. To the best of our knowledge, JointPS should be the first work that minimizes the average completion time of network-intensive DML training jobs by jointly optimizing the parameter server placement and flow scheduling without modifying the DML models and training procedures. Through both testbed experiments and extensive simulations, we demonstrate that JointPS can reduce the average completion time of DML jobs by up to 88% compared with state-of-the-art technology.

As the scale of distributed training increases, it brings huge communication overhead in clusters. Some works try to reduce the communication cost through gradient compression or communication scheduling. However, these methods either downgrade the training accuracy or do not reduce the total transmission amount. One promising approach, called in-network aggregation, is proposed to mitigate the bandwidth bottleneck in clusters by aggregating gradients in programmable hardware (e.g., Intel Tofino switches). However, existing solutions mainly implement in-network aggregation through fixed (or default) routing paths, resulting in load imbalancing and long communication time. To deal with this issue, we propose GRID, the first-of-its-kind work on Gradient Routing with In-network Aggregation for Distributed Training. In the control plane, we present an efficient gradient routing algorithm based on randomized rounding and formally analyze the approximation performance. In the data plane, we realize in-network aggregation by carefully designing the logic of workers and programmable switches. We implement GRID and evaluate its performance on a small-scale testbed consisting of 3 Intel Tofino switches and 9 commodity servers. With a combination of testbed experiments and large-scale simulations, we show that GRID can reduce the communication time by 38.4%–60.1% and speed up distributed training by 17.4%–52.7% compared with state-of-the-art solutions.

With the broad deployment of distributed applications on clouds, east-west traffic is now dominating the majority of cloud networks. The existing communication solutions are tightly coupled with either the control plane (e.g., preprogrammed model) or the location of compute nodes (e.g., conventional gateway model). As a result, it is difficult to flexibly respond to the rapidly expanding networks and frequent abnormal events (e.g., burst traffic and device failures). Accordingly, they may not provide high-performance east-west forwarding while ensuring scalability and robustness. To address this issue, we design Zeta, a scalable and robust east-west forwarding framework with gateway clusters for hyperscale clouds. Zeta abstracts the traffic forwarding capability as a Gateway Cluster Layer, decoupled from the logic of control plane and the location of compute nodes. Specifically, Zeta adopts gateway clusters to support large-scale networks and cope with burst traffic. Moreover, a transparent Multi IPs Migration is proposed for fast recovery from unpredictable failures. We implement Zeta based on eXpress Data Path (XDP) and evaluate its scalability and robustness through comprehensive experiments with up to 100k container instances. Our evaluation shows that Zeta reduces the 99% RTT by$5.1 {\times }$in burst video traffic, and reduces the gateway pure recovery delay by$10.8 {\times }$compared with the state-of-the-art solutions.

Southbound message delivery from the control plane to the data plane is one of the essential issues in multi-tenant clouds. A natural method of southbound message delivery is that the control plane directly communicates with compute nodes in the data plane. However, due to the large number of compute nodes, this method may result in massive control overhead. The Message Queue (MQ) model can solve this challenge by aggregating and distributing messages to queues. Existing MQ-based solutions often perform message aggregation based on the physical network topology, which do not align with the fundamental requirements of southbound message delivery, leading to high message redundancy on compute nodes. To address this issue, we design and implement VITA, the first-of-its-kind work on virtual network topology-aware southbound message delivery. However, it is intractable to optimally deliver southbound messages according to the virtual attributes of messages. Thus, we design two algorithms, submodular-based approximation algorithm and simulated annealing-based algorithm, to solve different scenarios of the problem. Both experiment and simulation results show that VITA can reduce the total traffic amount of redundant messages by 45%-75% and reduce the control overhead by 33%-80% compared with state-of-the-art solutions.

As a simple and low-cost way to obtain enough computing resources, more and more tenants migrate their tasks to the cloud. However, the frequent occurrence of abnormal events (e.g., malicious tenants and node failures) in the cloud will seriously affect the tenants’ QoS. Conventionally, the cloud vendors reduce the frequency of abnormal events by deploying auxiliary systems, which requires additional costs and increases network complexity. Considering that it is an unrealistic expectation to eliminate the occurrence of abnormal events in clouds, this paper proposes a complementary scheme to alleviate the negative impact scope when an abnormal event occurs through multi-constrained VM placement without consuming additional resources. Specifically, when deploying VMs, we limit the number of pods (or service nodes) each tenant can access and the number of tenants hosted by each pod (or service node). However, the multi-dimensional interaction among numerous system parameters and performance/resource considerations makes the problem of multi-constrained VM placement for alleviating the impact of abnormal events very challenging. To solve this problem, we formulate an integer linear programming and propose a rounding-based algorithm with a logarithmic approximation ratio. We implement our proposed algorithm on a physical testbed. The experimental and simulation results show the high efficiency of the proposed algorithm. For example, our algorithm reduces the impact scope of service node failure by 60%, the impact scope of malicious tenants by 40%, and the tenant task makespan by 25% compared with other alternatives.

There are two conventional methods to establish an entanglement connection in a Quantum Data Network (QDN). One is to create single-hop entanglement links first and then connect them with quantum swapping, and the other is for-warding one of the entangled photons from one end to the other via all-optical switching at intermediate nodes to directly establish an entanglement connection. Since a photon is easy to be lost during a long distance transmission, all existing works are adopting the former method. However, in a room size network, the success probability of delivering a photon across multiple links via all-optical switching is not that low. In addition, with an all-optical switching technique, we can save quantum memory at the intermediate nodes. Accordingly, we are expecting to establish significantly more entanglement connections with limited quantum resources by first creating entanglement segments, each spanning multiple quantum links, using all-optical switching, and then connecting them with quantum swapping.In this paper, we design SEE, a Segmented Entanglement Establishment approach that seamlessly integrates quantum swapping and all-optical switching to maximize quantum network throughput. SEE first creates entanglement segments over one or multiple quantum links with all-optical switching, and then connect them with quantum swapping. It is clear that an entanglement link is only a special entanglement segment. Accordingly, SEE can theoretically outperform conventional entanglement link based approaches. Large scale simulations show that SEE can achieve up to 100.00% larger throughput compared with the state-of-the-art entanglement link based approach, i.e., REPS.

Traditional kernel network processing suffers from high delay and overhead, which has become the bottleneck of high-speed networks. A natural method to accelerate packet processing is to bypass the kernel network stack and process packets in user space directly, $e.g$., DPDK. However, due to many network functions are implemented in the kernel network stack, bypassing the stack means that we need to redesign the required functions elsewhere, leading to poor compatibility. One promising technology to address this problem is called eXpress Data Path (XDP), which can support high-performance packet processing while preserving the kernel stack. However, existing solutions mainly run XDP in software mode, resulting in relatively poor packet processing performance. Fortunately, with the development of programmable hardware, running XDP in hardware mode is a more promising approach. Thus, in this paper, we design and implement OXDP, the first-of-its-kind work on accelerating packet processing by offloading XDP to SmartNICs. Since today’s SmartNICs are still subject to some limitations regarding the rigid runtime environment, it is nontrivial to offload XDP to SmartNICs. To address this issue, OXDP performs best-effort offloading based on the primitive packet operations, thus maximizing the use of SmartNIC’s resources. Specifically, OXDP splits the forwarding function into two parts, one part offloading on SmartNIC with hardware XDP and the other part deploying on host. We evaluate the efficiency of OXDP with comprehensive experiments. Evaluation results show that the forwarding rate of OXDP can reach 18.7 Mpps, which improves $30 \times$ compared with the single-core performance of software XDP.

In a hyper-scale cloud data center, a large number of control messages are distributed to hundreds of thousands of compute nodes from a logically centralized control plane. The delivery of these control messages, a.k.a. southbound messages, is critical to cloud infrastructure management, as it greatly affects customer experience. Existing works mainly deal with southbound message delivery by two methods: point-to-point transmission and Message Queue (MQ)-based solutions. With the point-to-point transmission method, each message is sent from the control plane to compute nodes directly, which may cause high control complexity and overhead in hyper-scale clouds. The MQ-based method can address the challenge of high complexity through message aggregation and subscribe/publish model. However, it usually brings in redundant messages, and further causes extra load on compute nodes. To solve the problem above, we design SNIP, which exploits the ability of programmable switches to perform in-network message pruning and to reduce message redundancy. Specffically, forwarding and processing information computed by the control plane is attached to the package header of every control message. Redundant messages can be identified and processed by programmable switches. In addition, we propose a rounding-based algorithm to prune messages with minimal redundancy. The simulation results show that SNIP can reduce the control overhead by 80%-85% and the total traffic of redundant messages by 35% compared with existing solutions.

Southbound message delivery from the control plane to the data plane is one of the essential issues in multi-tenant clouds. A natural method of southbound message delivery is that the control plane directly communicates with compute nodes in the data plane. However, due to the large number of compute nodes, this method may result in massive control overhead. The Message Queue (MQ) model can solve this challenge by aggregating and distributing messages to queues. Existing MQ-based solutions often perform message aggregation based on the physical network topology, which do not align with the fundamental requirements of southbound message delivery, leading to high message redundancy on compute nodes. To address this issue, we design and implement VITA, the first-of-its-kind work on virtual network topology-aware southbound message delivery. However, it is intractable to optimally deliver southbound messages according to the virtual attributes of messages. Thus, we design two algorithms, submodular-based approximation algorithm and simulated annealing-based algorithm, to solve different scenarios of the problem. Both experiment and simulation results show that VITA can reduce the total traffic amount of redundant messages by 45%-75% and reduce the control overhead by 33%-80% compared with state-of-the-art solutions.

In a commercial cloud, service providers (e.g., video streaming service provider) rent resources from cloud vendors (e.g., Google Cloud Platform) and provide services to cloud users, making a profit from the price gap. Cloud users acquire services by forwarding their requests to corresponding servers. In practice, as a common scenario, traffic dynamics will cause server overload or load-unbalancing. Existing works mainly deal with the problem by two methods: elastic resource provisioning and request updating. Elastic resource provisioning is a fast and agile solution but may cost too much since service providers need to buy extra resources from cloud vendors. Though request updating is a free solution, it will cause a significant delay, resulting in a bad users’ QoS. In this paper, we present a new scheme, called real-time request updating with elastic resource provisioning (TRUST), to help service providers pay less cost with users’ QoS guarantee in clouds. In addition, we propose an efficient algorithm for TRUST with a bounded approximation factor based on randomized rounding. Both small-scale experiment results and large-scale simulation results show the superior performance of our proposed algorithm compared with state-of-the-art benchmarks.

This paper studies reliable teleportation of quantum bits (called qubits) in a quantum data network with multiple sources (S) and destinations (D) as well as repeaters. To teleport qubits for a SD pair reliably, not only an entanglement path for the SD pair, but also appropriate purification of the links along the path is required to ensure that the end-to-end (E2E) fidelity of the established entanglement connections is high enough.This is the first work on quantifying the E2E fidelity, and also using this E2E fidelity to determine critical links to achieve the most resource efficient purification. A novel approach called E2E Fidelity aware Routing and Purification (EFiRAP) is proposed to maximize network throughput, i.e., the number of entanglement connections among multiple SD pairs, with each connection having an E2E fidelity above a given required threshold. EFiRAP accomplishes this goal by first preparing multiple candidate entanglement paths and determining optimal purification schemes, and then selecting the final set of entanglement paths that can maximize network throughput under the given quantum resource constraints. Existing works only ensured the fidelity of individual links, rather than the E2E fidelity is above a given threshold. Extensive simulations show that the proposed EFiRAP can enhance network throughput by about 50% when compared with the state-of-the-art approach.

In Mobile Edge Computing (MEC), users' traffic needs to traverse a set of service functions in a specific order, referred to as a service function chain (SFC), to complete service requests. Thus, SFC routing is an essential issue in MEC. In practice, user mobility and resource limitation are two critical challenges of SFC routing in MEC. However, the previous works either ignore the user mobility or resource limitation, especially the flow-table resources, leading to high transmission latency and resource overhead. In this paper, we study the mobility-aware service function chain routing in MEC. We design an SFC routing scheme called MASCOT to address the above challenges. MASCOT implements SFC routing through three steps: user location prediction, routing path decision, and packet forwarding. For user location prediction, we adopt the order-K Markov prediction method to predict users' next accessed base station. For routing path decision, we formulate the SFC routing selection (SRS) problem, which respects the resource constraints. We propose a primal-dual online SFC routing algorithm (POSR) for the SRS problem and prove that POSR can achieve good competitiveness. For packet forwarding, we propose a forwarding scheme based on segment routing to address the resource limitation challenge further. Extensive simulation results show that our scheme can improve the system throughput by about 40% compared with the state-of-the-art approaches.

In multi-tenant clouds, requests need to traverse a set of network functions (NFs) in a specific order, referred to as a service function chain (SFC), for security and business logic issues. Due to workload dynamics, the central controller of a multi-tenant cloud needs to frequently update the SFC routing, so as to optimize various network performance, such as load balancing. To achieve effective SFC routing update, we should consider two critical requirements:system robustnessandreal-time update. Without considering these two requirements, prior works either result in fragile clouds or suffer from large update delay. In this paper, we propose a robustness-aware real-time SFC routing update (R3-UA) scheme which takes both requirements into consideration. R3-UA pursues robustness-aware real-time routing update through two phases: robust NF instance assignment update and real-time SFC routing update. Two algorithms with bounded approximation ratios are proposed for these two phases, respectively. We implement R3-UA on a real testbed. Both small-scale experimental results and large-scale simulation results show the superior performance of R3-UA compared with other alternatives.

In a multi-tenant cloud, cloud vendors provide services (e.g., elastic load-balancing, virtual private networks) on service nodes for tenants. Thus, the mapping of tenants’ traffic and service nodes is an important issue in multi-tenant clouds. In practice, unreliability of service nodes and uncertainty/dynamics of tenants’ traffic are two critical challenges that affect the tenants’ QoS. However, previous works often ignore the impact of these two challenges, leading to poor system robustness when encountering system accidents. To bridge the gap, this paper studies the problem of robust service mapping in multi-tenant clouds (RSMP). Due to traffic dynamics, we take a two-step approach:service node assignmentandtenant traffic scheduling. For service node assignment, we prove its NP-Hardness and analyze its problem difficulty. Then, we propose an efficient algorithm with bounded approximation factors based on randomized rounding and knapsack. For tenant traffic scheduling, we design an approximation algorithm based on fully polynomial time approximation scheme (FPTAS). The proposed algorithm achieves the approximation factor of 2+$\epsilon $, where$\epsilon $is an arbitrarily small value. Both small-scale experimental results and large-scale simulation results show the superior performance of our proposed algorithms compared with other alternatives.

The past decades have seen a proliferation of middlebox deployment in various scenarios, including backbone networks and cloud networks. Since flows have to traverse specific service function chains (SFCs) for security and performance enhancement, it becomes much complex for SFC routing due to routing loops, traffic dynamics and scalability requirement. The existing SFC routing solutions may consume many resources (e.g., TCAM) on the data plane and lead to massive overhead on the control plane, which decrease the scalability of middlebox networks. Due to SFC requirement and potential routing loops, solutions like traditional default paths (e.g., using ECMP) that are widely used in non-middlebox networks will no longer be feasible. In this paper, we present and implement a scalable and flexible middlebox policy enforcement (SAFE-ME) system to minimize the TCAM usage and control overhead. To this end, we design the smart tag operations for construction of default SFC paths with less TCAM rules in the data plane, and present lightweight SFC routing update with less control overhead for dealing with traffic dynamics in the control plane. We implement our solution and evaluate its performance with experiments on both physical platform (Pica8) and Programming Protocol-independent Packet Processors (P4) based data plane, as well as large-scale simulations. Both experimental and simulation results show that SAFE-ME can greatly improve scalability (e.g., TCAM cost, update delay, and control overhead) in middlebox networks, especially for large-scale clouds. For example, our system can reduce the control traffic overhead by about 85% while achieving almost the similar middlebox load, compared with state-of-the-art solutions.

Cloud providers host various services for tenants’ requests (e.g., software-as-a-service) and seek to serve as many requests as possible for revenue maximization. Considering a large number of requests, the previous works on fine-grained request scheduling may lead to poor system scalability (or high schedule overhead) and break tenant isolation. In this article, we design a tenant-grained request scheduling framework to conquer the above two disadvantages. We formulate the tenant-grained request scheduling problem as an integer linear programming and prove its NP-hardness. We consider two complementary cases: the offline case (where we know all request demands in advance), and the online case (where we have to make immediate scheduling decisions for requests arriving online). A normalization-based algorithm with an approximation factor of$ {O}(1)$is proposed to solve the offline problem and a primal-dual-based algorithm with a competitive ratio of$[(1-\epsilon), {O}(\log 3\cdot n+\log (1/\epsilon))]$is designed for the online scenario, where$\epsilon \in (0,1)$and$n$is the number of racks in the cloud. We also discuss how to integrate our proposed algorithms with the previous (fine-grained) request scheduling mechanism. Extensive simulation and experiment results show that our algorithms can obtain significant performance gains, e.g., the online algorithm reduces the scheduler's overhead more than$90\%$and achieves tenant isolation, while obtaining similar network performance (e.g., throughput) compared with the fine-grained request scheduling methods.

In a multi-tenant cloud, cloud vendors provide services (e.g., elastic load-balancing, virtual private networks) on service nodes for tenants. Thus, the mapping of tenants' traffic and service nodes is an important issue in multi-tenant clouds. In practice, unreliability of service nodes and uncertainty/dynamics of tenants' traffic are two critical challenges that affect the tenants' QoS. However, previous works often ignore the impact of these two challenges, leading to poor system robustness when encountering system accidents. To bridge the gap, this paper studies the problem of robust service mapping in multi-tenant clouds (RSMP). Due to traffic dynamics, we take a two-step approach: service node assignment and tenant traffic scheduling. For service node assignment, we prove its NP-Hardness and analyze its problem difficulty. Then, we propose an efficient algorithm with bounded approximation factors based on randomized rounding and knapsack. For tenant traffic scheduling, we design an approximation algorithm based on fully polynomial time approximation scheme (FPTAS). The proposed algorithm achieves the approximation factor of 2+ ε , where ε is an arbitrarily small value. Both small-scale experimental results and large-scale simulation results show the superior performance of our proposed algorithms compared with other alternatives.

In multi-tenant clouds, requests need to traverse a set of network functions (NFs) in a specific order, referred to as a service function chain (SFC), for security and business logic issues. Due to workload dynamics, the central controller of a multi-tenant cloud needs to frequently update the SFC routing, so as to optimize various network performance, such as load balancing. To achieve effective SFC routing update, we should consider two critical requirements: system robustness and real-time update. Without considering these two requirements, prior works either result in fragile clouds or suffer from large update delay. In this paper, we propose a robustness-aware real-time SFC routing update (R3-UA) scheme which takes both requirements into consideration. R3-UA pursues robustness-aware real-time routing update through two phases: robust NF instance assignment and real-time SFC routing update. Two algorithms with bounded approximation ratios are proposed for these two phases, respectively. The large-scale simulation results show the superior performance of R3-UA compared with other alternatives.

More and more tenants (enterprises and personal users) migrate their tasks to clouds since it is a simple and low-cost way to obtain enough computing resources. However, due to potential node failures and malicious tenants, the modern cloud encounters one critical challenge, i.e., robustness. Conventionally, the cloud vendors deploy auxiliary systems to protect the cloud, which requires additional resource cost and increases the network complexity. To enhance the system robustness, this paper proposes a complementary scheme to improve the cloud robustness through efficient VM placement. Specifically, to alleviate the impact of malicious tenants and node failures on the cloud, when deploying VMs, we limit the number of pods (or service nodes) that each tenant can access, and the number of tenants hosted by each pod (or service node). Though there are a lot of works on VM placement, it is very challenging when the robustness issue is taken into consideration. To solve this problem, we formulate an integer linear programming and propose a rounding-based algorithm with a logarithmic approximation ratio. The simulation results show the high efficiency of the proposed algorithm. For example, our algorithm can improve the network throughput by 150% with other alternatives.

In a software defined network, the controller needs to obtain/collect traffic measurement information (i.e., flow statistics) from switches for different applications, such as traffic engineering. Existing solutions seldom consider the per-switch cost, which may lead to heavy statistics collection cost (e.g., high CPU overhead) on some switches. Due to limited computing power on most commodity switches, heavy statistics collection cost on those switches may seriously interfere with the basic rule operations, especially when some switches need to deal with many new-arrival flows or update routes of existing flows. To address this challenge, we design and implement efficient flow statistics collection (FSC) with limited interference on the basic rule operations. We formally propose a cooperative flow statistics collection with per-switch cost constraint (CP-FSC) problem. We prove that the CP-FSC problem is NP-hard and present an efficient algorithm with approximation ratio 1/2, based on dynamic programming. To reduce the time complexity, a greedy-based algorithm with approximation ratio 1/3 is also presented. We implement the proposed FSC algorithms on our SDN platform. The experimental results and the extensive simulation results show 36%-59% performance improvement compared with the existing solutions.

Network Function Virtualization (NFV) is a new paradigm to enable service innovation through virtualizing traditional network functions. To construct a new NFV-enabled network, there are two critical requirements: minimizing server deployment cost and satisfying switch resource constraints. However, prior work mostly focuses on the server deployment cost, while ignoring the switch resource constraints (e.g., switch's flow-table size). It thus results in a large number of rules on switches and leads to massive control overhead. To address this challenge, we propose an incremental server deployment (INSD) problem for construction of scalable NFV-enabled networks. We prove that the INSD problem is NP-Hard, and there is no polynomial-time algorithm with approximation ratio of (1- ϵ)· ln m, where ϵ is an arbitrarily small value and m is the number of requests in the network. We then present an efficient algorithm with an approximation ratio of 2 · H(q · p), where q is the number of VNF's categories and p is the maximum number of requests through a switch. We evaluate the performance of our algorithm with experiments on physical platform (Pica8), Open vSwitches, and large-scale simulations. Both experimental results and simulation results show high scalability of the proposed algorithm. For example, our solution can reduce the control and rule overhead by about 88% with about 5% additional server deployment, compared with the existing solutions.

Fine-grained flow management is useful in many practical applications, e.g., resource allocation, anomaly detection and traffic engineering. However, it is difficult to provide fine-grained management for a large number of flows in SDNs due to switches' limited flow table capacity. While using wildcard rules can reduce the number of flow entries needed, it cannot fully ensure fine-grained management for all the flows without degrading application performance. In this article, we design and implement hybrid rule placement for fine-grained flow management (to be referred to as HiFi here after). HiFi achieves fine-grained management with a minimal number of flow entries through taking a two-step approach: wildcard entry installment and application-specific exact-match entry installment. How to optimally install wildcard and exact-match flow entries, however, is intractable. Therefore, we design approximation algorithms with bounded factors to solve these problems. We consider how to achieve network-wide load balancing via fine-grained flow management as a case study. Both experiment on a testbed built with open virtual switches and extensive simulation show that HiFi can reduce the number of required flow entries by about 45-69 percent and reduce the control overhead by about 28-50 percent compared with the state-of-the-art approaches for achieving fine-grained flow management.

In Mobile Edge Computing (MEC), many tasks require specific service support for execution and in addition, have a dependent order of execution among the tasks. However, previous works often ignore the impact of having limited services cached at the edge nodes on (dependent) task offloading, thus may lead to an infeasible offloading decision or a longer completion time. To bridge the gap, this article studies how to efficiently offload dependent tasks to edge nodes with limited (and predetermined) service caching. We formally define the problem of offloading dependent tasks with service caching (ODT-SC), and prove that there exists no algorithm with constant approximation for this hard problem. Then, we design an efficient convex programming based algorithm (CP) to solve this problem. Moreover, we study a special case with a homogeneous MEC and propose a favorite successor based algorithm (FS) to solve this special case with a competitive ratio of O(1)O(1). Extensive simulation results using Google data traces show that our proposed algorithms can significantly reduce applications' completion time by about 21-47 percent compared with other alternatives.

Network Function Virtualization (NFV) is a new paradigm to enable service innovation through virtualizing traditional network functions. To construct a new NFV-enabled network, there are two critical requirements: minimizing server deployment cost and satisfying switch resource constraints. However, prior work mostly focuses on the server deployment cost, while ignoring the switch resource constraints (e.g., switch's flow-table size). It thus results in a large number of rules on switches and leads to massive control overhead. To address this challenge, we propose an incremental server deployment (INSD) problem for construction of scalable NFV-enabled networks. We prove that the INSD problem is NP-Hard, and there is no polynomial-time algorithm with approximation ratio of (1- ε) ·ln m, where ε is an arbitrarily small value and m is the number of requests in the network. We then present an efficient algorithm with an approximation ratio of 2 · H(q · p)1, where q is the number of VNF's categories and p is the maximum number of requests through a switch. We evaluate the performance of our algorithm with experiments on physical platform (Pica8), Open vSwitches, and large-scale simulations. Both experiment and simulation results show high scalability of the proposed algorithm. For example, our solution can reduce the control and rule overhead by about 88% with about 5% additional server deployment, compared with the existing solutions.

Fine-grained flow management is useful in many practical applications, e.g., resource allocation, anomaly detection and traffic engineering. However, it is difficult to provide fine-grained management for a large number of flows in SDNs due to switches' limited flow table capacity. While using wildcard rules can reduce the number of flow entries needed, it cannot fully ensure fine-grained management for all the flows without degrading application performance. In this paper, we design and implement HiFi, a system that achieves fine-grained management with a minimal number of flow entries. To this end, HiFi takes a two-step approach: wildcard entry installment and application-specific exact-match entry installment. How to optimally install wildcard and exact-match flow entries, however, is intractable. Therefore, we design approximation algorithms with bounded factors to solve these problems. We consider how to achieve network-wide load balancing via fine-grained flow management as a case study. Both experimental and simulation results show that HiFi can reduce the number of required flow entries by about 45%-69% and reduce the control overhead by 28%-50% compared with the state-of-the-art approaches for achieving fine-grained flow management.

In Mobile Edge Computing (MEC), many tasks require specific service support for execution and in addition, have a dependent order of execution among the tasks. However, previous works often ignore the impact of having limited services cached at the edge nodes on (dependent) task offloading, thus may lead to an infeasible offloading decision or a longer completion time. To bridge the gap, this paper studies how to efficiently offload dependent tasks to edge nodes with limited (and predetermined) service caching. We formally define the problem of offloading dependent tasks with service caching (ODT-SC), and prove that there exists no algorithm with constant approximation for this hard problem. Then, we design an efficient convex programming based algorithm (CP) to solve this problem. Moreover, we study a special case with a homogeneous MEC and propose a favorite successor based algorithm (FS) to solve this special case with a competitive ratio of O(1). Extensive simulation results using Google data traces show that our proposed algorithms can significantly reduce applications' completion time by about 27-51% compared with other alternatives.

The past decades have seen a proliferation of middlebox deployment in various networks, including backbone networks and datacenters. Since network flows have to traverse specific service function chains (SFCs) for security and performance enhancement, it becomes much complex for SFC routing due to routing loops, traffic dynamics and scalability requirement. The existing SFC routing solutions may consume many resources (e.g., TCAM) on the data plane and lead to massive overhead on the control plane, which decrease the scalability of middlebox networks. Due to SFC requirement and potential routing loops, solutions like traditional default paths (e.g., using ECMP) that are widely used in non-middlebox networks will no longer be feasible. In this paper, we present and implement a scalable and flexible middlebox policy enforcement (SAFE-ME) system to minimize the TCAM usage and control overhead. To this end, we design the smart tag operations for construction of default SFC paths with less TCAM rules in the data plane, and present lightweight SFC routing update with less control overhead for dealing with traffic dynamics in the control plane. We implement our solution and evaluate its performance with experiments on both physical platform (Pica8) and Open vSwitch (OVS), as well as large-scale simulations. Both experimental and simulation results show that SAFE-ME can greatly improve scalability (e.g., TCAM cost, update delay, and control overhead) in middlebox networks. For example, our system can reduce the control traffic overhead by about 83% while achieving almost the similar middlebox load, compared with state-of-the-art solutions.

To better serve a diversity of flows, load balancing is crucial to ensure operational efficiency. However, previous works for load balancing have several disadvantages: 1) limited applicability with sub-flow scheduling (e.g., LetFlow); 2) hash collision (e.g., ECMP); or 3) transient network congestion due to reactive scheduling for traffic dynamics (e.g., Hedera and DevoFlow). An important reason for the above disadvantages is that it is difficult to provide fully fine-grained flow control for load balancing in an SDN as the flow table size of each SDN switch is usually limited. Inspired by the fact that a virtual switch (vswitch) has more powerful processing capacity and more flow entries compared with a physical switch, the previous work (e.g., Presto) deploys one vswitch for each ingress switch, and achieves the load balancing through efficient flow routing. However, this mechanism may lead to high cost and not well deal with topology asymmetry. Thus, this paper proposes to achieve the load balancing by incrementally deploying a certain number of vswitches in an SDN. We formulate the joint optimization of vswitch deployment and routing (JVR) problem as an integer linear program, and prove its NP-hardness. A rounding-based algorithm with bounded approximation factors is proposed to solve the JVR problem. We implement the proposed algorithm on an SDN testbed for experimental studies and use simulations for large-scale investigation. The experimental results and simulation results show high efficiency of our algorithm. For example, our proposed algorithm can reduce the link load ratio by about 41.5% compared with ECMP by deploying a small number of virtual switches.

Traditional networks rely on aggregate routing and decentralized control to achieve scalability. On the contrary, software-defined networks achieve near optimal network performance and policy-based management through per-flow routing and centralized control, which, however, face scalability challenge due to: 1) limited ternary content addressable memory and on-die memory for storing the forwarding table and 2) per-flow communication/computation overhead at the controller. This paper presents a novel hybrid switching (HS) design, which integrates traditional switching and software-defined networking (SDN) switching for the purpose of achieving both scalability and optimal performance. We show that the integration also leads to unexpected benefits of making both types of switching more efficient under the hybrid design. We also design the general optimization framework via HS and propose an approximation algorithm for load-balancing optimization as a case study. Testing and numerical evaluation demonstrate the superior performance of HS when comparing with the state-of-the-art SDN design.

Software Defined Network (SDN) is an architectural trend in networking towards the use of the centralized controller to get better performance. However, due to limited resources (especially limited flow table size and controller processing capacity), it may result in low-throughput and long-delay for a set of bursty flows. In this paper, we first combine the flow table size constraint and the controller processing capacity constraint to define the Throughput Maximization with Limited Resources (TMLR) problem. Then we prove TMLR is NP-Hard and design an approximation algorithm to solve the TMLR problem. The approximation factor of the proposed algorithm is also analyzed. The simulation results on the SDN platform (Mininet [1]) show that our algorithm can improve the network throughput about 39% on average compared with the existing algorithms.

Software Defined Networking (SDN) separates the control plane from the data plane to ease network management and provide flexibility in packet routing. The control plane interacts with the data plane through the forwarding tables, usually including a flow table and a group table, at each switch. Due to high cost and power consumption of Ternary Content Addressable Memory (TCAM), commodity switches can only support flow/group tables of limited size, which presents serious challenge for SDN to scale to large networks. One promising approach to address the scalability problem is to deploy aggregate default paths specified by wildcard forwarding rules. However, the multi-dimensional interaction among numerous system parameters and performance/scalability considerations makes the problem of setting up the flow/group tables at all switches for optimal overall layout of default paths very challenging. This paper studies the joint optimization of flow/group tables in the complex setting of large-scale SDNs. We formulate this problem as an integer linear program, and prove its NP-Hardness. An efficient algorithm with bounded approximation factors is proposed to solve the problem. The properties of our algorithm are formally analyzed. We implement the proposed algorithm on an SDN testbed for experimental studies and use simulations for large-scale investigation. The experimental results and simulation results demonstrate high efficiency of our proposed algorithm.

Traditional networks rely on aggregate routing and decentralized control to achieve scalability. On the contrary, software-defined networks achieve near optimal network performance and policy-based management through per-flow routing and centralized control, which however face scalability challenge due to (1) limited TCAM and on-die memory for storing the forwarding table and (2) per-flow communication/computation overhead at the controller. This paper presents a novel hybrid switching design, which integrates traditional switching and SDN switching for the purpose of achieving both scalability and optimal performance. We show that the integration also leads to unexpected benefits of making both types of switching more efficient under the hybrid design. Numerical evaluation demonstrates the superior performance of hybrid switching when comparing with the state-of-the-art SDN design.