From the perspective of user experience, when optimizing resource provisioning in networks, we have to maximize social utility, which is an abstraction of what users can obtain from the service provided by a network. In quantum networks, unlike their counterparts, circuit-switched classical networks, (i) the utility obtained by a demand is not always concave for the number of Entanglement Connections (ECs) we provision to it; and (ii) each demand requires a different amount of quantum resources over each link along the path to establish an EC. As a result, the Social Utility Maximization (SUM) problem is more challenging than in classic circuit-switched networks. In this paper, we propose an approach also called SUM to maximize social utility in quantum networks by provisioning an appropriate number of ECs (and corresponding resources) to demands. We first formulate the SUM problem and analyze it based on Lagrangian relaxation and duality techniques. Accordingly, we derive the optimal EC provisioning scheme for a given Lagrangian multiplier, depending on whether the utility function of each demand is convex, concave, or sigmoid-like. After that, a primal-dual iteration algorithm is proposed to determine the optimal EC provisioning scheme to maximize social utility. We conduct extensive simulations to demonstrate that SUM outperforms the state-of-the-art approach to maximizing quantum network throughput,i.e., EFiRAP, by up to 58.4%.

Conventional entanglement routing approaches decide the Entanglement Paths (EPs) to establish Entanglement Connections (ECs) before trying to create Entanglement Links (ELs). By doing so, very few EL failures will result in a low network throughput. In this paper, we study how to choose the EPs to establish ECs after knowing which ELs are successfully created. This is called the Deferred EP Selection (DEPS) problem. DEPS is a generalized integer multi-commodity flow problem and we cannot solve it quickly with conventional optimization methods. To address this issue, we propose a Deep Reinforcement Learning based EP Selection (DRLEPS) approach. The salient features of DRLEPS include (i) by controlling the number of candidate EPs, DRLEPS can achieve a trade-off between time complexity and the EC establishment rate; and (ii) using candidate EPs as input, DRLEPS is robust to request variation; and (iii) by training neural networks with different topologies, a model derived by DRLEPS can be applied to various networks (even with a different number of nodes) without fine-tune. Through extensive simulations, we show that even in a network with 200 nodes, DRLEPS can solve the DEPS problem in 0.39 seconds with a Nvidia GeForce 3090 GPU. It outperforms the approach always establishing ECs through the EP with the largest success probability by up to 23.4% in EC establishment rate. It also outperforms the Integer Linear Programming (ILP) based scheme, which can achieve the maximum EC establishment rate, by up to 184.2x in network throughput.

Quantum Key Distribution (QKD) is considered to be the ultimate solution to communication security. However, current QKD devices, especially quantum photon sources, are expensive, and they can generate secret keys only at a low rate. In this paper, we first consider homogeneous trusted-relay-based QKD networks where every request has the same amount of secret key requirement and every photon source has the same key distribution rate, and design an approach named RPSP to not only minimize the number of photon sources needed in a network to ensure at least one feasible relay path exists for any potential QKD requests but also save the time to complete a batch of QKD requests by jointly optimizing the routing of relay paths and the provisioning of photon sources to distribute secret keys. Then, we extend RPSP to RPSP-HN which can be applied to heterogeneous networks where requests have different secret key requirements and photon sources distribute keys at different rates. Furthermore, we also extend RPSP to RPSP-HY, which considers that some of the nodes in a network is untrusted. Compared with existing works, RPSP and its extensions focus on more practical scenarios where only some of the nodes are equipped with photon sources and they leverage optical switching to enable dynamic photon source provisioning such that we can utilize QKD devices more efficiently. Extensive simulations show that compared with baseline schemes, RPSP, RPSP-HN, and RPSP-HY can save up to 33%, 37%, and 25% of the time to complete a batch of QKD requests in homogeneous, heterogeneous, and hybrid QKD networks, respectively.

Entanglement routing plays a vital role in supporting various applications in quantum networks. Existing works on entanglement routing either ignored the Entangled Photon Source (EPS) placement issue or simply assumed a pool of EPSes at a centralized location that can provision entanglement over arbitrary quantum links. In this paper, we propose LIGHTER and fidelity-aware LIGHTER (named F-LIGHTER) to solve the joint EPS placement and entanglement routing problem based on the assumption that EPSes are co-located with quantum nodes and each EPS can send one entangled photon at a time to one of its adjacent nodes only. The salient features of LIGHTER and F-LIGHTER include (i) LIGHTER and F-LIGHTER use a demand-agnostic EPS placement scheme to maximize network throughput and fairness for all feasible Entanglement Connection EC) establishment demands, and (ii) most requested ECs can be established over Entanglement Paths (EPs) determined offline, and only a small percentage of them will be established over online calculated EPs, resulting in fast and efficient entanglement routing. Extensive simulations show that compared with schemes without proper EPS placement or entanglement routing, LIGHTER can improve the network throughput by up to 175.6% and 37.0%, respectively. When the fidelity is considered, the network throughput improvement achieved by F-LIGHTER will be up to 135.0% and 21.5%, respectively.

The advent of Federated Learning (FL) empowers IoT devices to collectively train a shared model without local data exposure. In order to address the issue of Non-IID that causes model performance degradation, the recently proposed federated codistillation framework has shown great potential. However, due to the system heterogeneity of devices, the federated codistillation framework still faces a synchronization barrier issue, resulting in a non-negligible waiting time with a fixed computation amount (epoch or batch size) assigned. In this paper, we propose Adaptive Computation Amount Allocation (ACAA) to accelerate federated codistillation. Specifically, we leverage a criterion, solution inexactness, to quantify the computation amount. We dynamically adjust the solution inexactness of devices based on their computing power and bandwidth to enable them nearly simultaneous completion of training, reducing synchronization waiting time without sacrificing the training performance. The minimum required computation amount is determined by the coefficient of the distillation term and the gradient dissimilarity bound of Non-IID. We theoretically analyze the convergence of ACAA. Extensive experiments show that, compared to benchmark algorithms, ACAA can accelerate training by up to 5×.

Quantum Networks (QNs) typically leverage teleportation to send quantum bits (called qubits) to their destinations. To teleport a data qubit from Alice to Bob, one Entanglement Connection (EC) between Alice and Bob needs to be established. Accordingly, we have to concurrently establish as many requested ECs as possible in order to maximize the network throughput. Conventional methods either assumed a known traffic matrix and calculated the Entanglement Paths (EPs) for all requests in one batch or maximized the number of ECs established between all Source-Destination (SD) pairs without considering the amount of data qubits to be teleported. These methods are not scalable in large scale QNs since it is time consuming to calculate the EPs for a batch of requests. In addition, there may be only very few data qubits to be teleported between some SD pairs. Accordingly, the latter method may establish many useless ECs. To address these issues, we propose a Dynamic Entanglement Routing (DER) scheme which determines the EPs based on stream processing. By introducing a method to derive an appropriate purification scheme along each EP, we further extend DER to Dynamic Entanglement Routing with Purification (DERP) that provides fidelity guarantee to the established ECs. Through extensive simulations, we demonstrate that DER outperforms two representative heuristics by up to 52.79% and 61.27%, respectively, in terms of average request completion time and when we have to ensure the fidelity of the established ECs, this performance improvement will become 21.05% and 48.67%, respectively, if DERP is adopted.

Entanglement routing plays a vital role in distributed quantum computing and quantum networks. Previous works on entanglement routing have addressed several design challenges due to limited quantum resources, failures to establish entanglement, and decoherence of established entanglement, but considered neither the limitations imposed by having a limited number of entangled photon sources (EPSes), nor the benefits of using all-optical (or quantum) switching to distribute entangled photons. In this paper, we first explore the problem of jointly optimizing entanglement routing and EPS assignment, assuming no all-optical switching capability. In other words, a pair of entangled photons generated by one EPS can be distributed to two neighboring quantum nodes. We then relax the above assumption so as to allow a pair of entangled photons generated by one EPS to be distributed to non-adjacent nodes using all-optical switching. We propose two corresponding solutions, namely, entanglement routing and EPS assignment (or ERSA), and ERSA with all-optical switching-based distribution (or ERSA+D) that aim to maximize the number of entanglement connections between the given set of source-destination (SD) pairs while avoiding starvation and achieving fairness among the SD pairs. In order to obtain efficient solutions in a large discrete solution space in a timely manner, we first formulate each optimization problem as an Integer Linear Programming (ILP), and then propose efficient algorithms to derive near-optimal solutions based on relaxation, Lagrangian decomposition, duality iteration, and rounding techniques. Extensive simulations show that ERSA+D can increase network throughput by up to 1652% and 113%, respectively, thanks to EPS assignment optimization, and all-optical switching based entanglement distribution.

Entanglement routing in quantum data networks plays a vital role to support various quantum applications. Existing works on entanglement routing either ignored the Entangled Photon Source (EPS) placement issue or simply assumed a pool of EPSes at a centralized location that can provision entanglement over arbitrary quantum links. In this paper, we propose LightER to solve the joint EPS placement and entanglement routing problem based on the assumption that EPSes are distributed over a quantum network, where an EPS, which is co-located with a quantum node, can send one entangled photon at a time to one of the adjacent nodes only. The salient features of LightER include (i) LightER uses a demand-agnostic EPS placement scheme to maximize network throughput and fairness for all feasible entanglement connection (EC) establishment demands, and (ii) most of the requested ECs can be established over their corresponding Entanglement Paths (EPs) determined offline, and only a small percentage of the ECs will be established over EPs that need to be calculated online, resulting in fast and efficient entanglement routing. Extensive simulations show that compared with schemes without proper EPS placement or entanglement routing, LightER can improve the network throughput by up to 215% and 56.2%, respectively.

Efficient entanglement routing in Quantum Data Networks (QDNs) is essential in order to concurrently establish as many Entanglement Connections (ECs) as possible, which in turn maximizes the network throughput. In this work, we consider a new class of QDNs with wavelength division multiplexed (WDM) quantum links where each quantum repeater will perform entanglement swapping by measuring two photonic qubits coming from some entangled photon sources directly on the same wavelength. To address unique challenges in achieving a high network throughput in such QDNs, we propose QuRWA to jointly optimize the entanglement routing and wavelength assignment. To this end, we introduce a key concept named Co-Path to improve fault-tolerance: all ELs in a Co-Path set will be assigned the same wavelength and this may serve as backup for some other ELs in the same Co-Path when establishing ECs. We design efficient algorithms to optimize the Co-Path selection and wavelength assignment to maximize resource utilization and fault tolerance. Extensive simulations demonstrate that compared with the methods without introducing Co-Path, QuRWA improves the network throughput by up to 122%.

Quantum Key Distribution (QKD) is considered to be an ultimate solution to communication security. However, current QKD devices, especially quantum photon sources, are expensive, and they can generate secret keys only at a low rate. In this paper, we design a system named RPSP for trusted relay-based QKD networks to not only minimize the number of photon sources needed in a network to ensure at least one feasible relay path exists for any potential QKD requests but also save the time to complete a batch of end-to-end QKD requests by jointly optimizing the routing of relay paths and the provisioning of photon sources along each relay path. Compared with existing works, RPSP focuses on a more practical scenario where only some of the nodes are equipped with photon sources and it leverages optical switching to enable dynamic photon source provisioning such that we can utilize such QKD devices in a more efficient way. Extensive simulations show that compared with baseline schemes, RPSP can save up to 87% of the photon sources needed in a trusted relay based QKD network, and 36% of the time to complete a batch of QKD requests.

Congestion Control (CC) plays a vital role in deploying lossless datacenter networks based on Remote Direct Memory Access (RDMA). A high-performance CC scheme should provide low-latency and precise feedback to congestion events. However, no existing CC schemes achieved both features simultaneously. In this paper, we propose LHCC, a Low-latency and Hi-precision Congestion Control scheme for RDMA datacenter networks. LHCC uses out-band signaling to notify the network status and hence a packet sender can detect congestion events within an RTT. In addition, LHCC adjusts packet sending rate by taking into consideration all queues along the entire path that a packet has gone through. Accordingly, it provides a more precise CC compared with existing schemes especially when there are multiple bottlenecks in the networks. We build the LHCC prototype on a real testbed carrying NVIDIA BlueField-3 NICs and AGM39D FPGAs. Both testbed experiments and extensive simulations show that LHCC can reduce the Flow Completion Time (FCT) slow down and reduce the buffer usage (i.e., reduce the queue lengths) by up to 62.5% and 58%, respectively, compared with the state-of-the-art high-precision CC scheme, HPCC.

In Distributed Quantum Computing (DQC), quantum bits (qubits) used in a task may be distributed on multiple Quantum Computers (QCs) connected by a Quantum Data Network (QDN). When we have to perform a quantum gate operation involving two qubits on different QCs, an Entanglement Connection (EC) has to be established between these two QCs. Since quantum gate operations can be performed at the data speed, the completion time of a DQC task is dominated by the time to establish ECs.To minimize the DQC task completion time, we propose QuPEP to jointly optimize data qubit (i.e., dbit) placement (that determines the number of ECs we have to establish between each pair of QCs) and entangled qubit (i.e., ebit) provisioning (that minimizes the time to establish each EC). QuPEP has an offline algorithm to optimize the dbit placement based on Genetic Simulated Annealing (GSA) and an online algorithm to optimize ebit provisioning based on Lagrange’s relaxation and the stochastic gradient descent method. By setting the fitness of each chromosome in GSA as the minimum DQC task completion time that can be achieved by the proposed online ebit provisioning scheme, QuPEP joints dbit placement and ebit provisioning. Extensive simulations show that compared with only optimizing dbit placement or ebit provisioning, QuPEP can reduce the DQC task completion time by up to 38% and 95%, respectively.

Quantum Data Networks (QDNs) are vital to building Distributed Quantum Computing (DQC) systems. Though several communication protocols have been proposed for QDNs, most of them are at the network layer or below. The only transport layer protocol [1] used batch processing of requests for End-to-End (E2E) quantum data transmission. It not only limits the quantum resource utilization, more importantly, it cannot guarantee reliable E2E quantum data transmission. In this paper, we propose the first asynchronous transportation layer protocol, called AQTP, for QDNs to achieve high-speed and reliable E2E quantum data transmission. AQTP has several distinct features: (i) each quantum node locally allocates quantum resources in order to improve scalability; (ii) requests are processed in an asynchronous manner, which results in a higher quantum resource utilization; and (iii) it ensures reliable data transmission even if the teleportation operations fail. Extensive simulations show that compared with a batch processed transport layer protocol, AQTP can increase the network throughput by up to 82.97%, and reduce the Average Task Completion Time (ATCT) of DQC tasks by up to 94.69%.

Network Function Virtualization (NFV) introduces a new network architecture that offers different network services flexibly and dynamically in the form of Service Function Chains (SFCs), which refer to a set of Virtualization Network Functions (VNFs) chained in a specific order. However, the service latency often increases linearly with the length of SFCs due to the sequential execution of VNFs, resulting in sub-optimal performance for most delay-sensitive applications. In this paper, a novel Parallel VNF Placement (PVFP) approach is proposed for real-world networks via Federated Deep Reinforcement Learning (FDRL). PVFP has three remarkable characteristics distinguishing from previous work: 1) PVFP designs a specific parallel principle, with three parallelism identification rules, to reasonably decide partial VNF parallelism; 2) PVFP considers SFC partition in multi-domains built on their remaining resources and potential parallel VNFs to ensure that VNFs can be reasonably distributed for resource balancing among domains; 3) FDRL-based framework of parallel VNF placement is designed to train a global intelligent model, with time-variant local autonomy explorations, for cross-domain SFC deployment, avoiding data sharing among domains. Simulation results in different scenarios demonstrate that PVFP can significantly reduce the end-to-end latency of SFCs at the medium resource expenditures to place VNFs in multiple administrative domains, compared with the state-of-the-art mechanisms.

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).

We envision a wide deployment of battery-operated edge devices such as data kiosk, to provide pervasive data collection and dissemination services. Although these data kiosks can be powered by green energy sources, their batteries may deplete overtime, and have to recharged frequently to prevent power outages and potential loss of critical data. In this paper, we propose an edge device recharging system using autonomous electric vehicles as Mobile Chargers (MCs). First, we determine the numbers and locations of Dispatching Centers (DCs) for these MCs, each of which will be responsible for recharging some edge devices in a surrounding area. Then, we plan optimal routes of the MCs in order to minimize the number of MCs needed to recharge all edge devices before a deadline. To reduce the time complexity involved in optimizing the routes, we cluster the edge devices and propose efficient algorithms to plan the route of MCs for each cluster based on the relaxation and rounding of a Mixed Integer Linear Programming (MILP) model. Extensive simulations show that our approach can reduce the number of MCs required to recharge all edge devices before a deadline by up to 71.93% compared with greedy-based heuristic algorithms.

In Federated Learning (FL), to improve the training efficiency, we don’t need to let all of the clients join in the training process. Instead, we can select some specific clients to join in the training. In particular, if some of these selected clients become problematic due to various reasons (e.g. shortage of power, poor internet connection, or being vulnerable to attacks) and thus could not successfully complete the training process, then we can discard those clients during training, in order to improve the efficiency. However, discarding those clients could increase the data source’s bias, because the data categories that contain those clients’ data would be underrepresented during the training process. To solve this problem, in this paper, we propose a robust client selection and replacement approach called RCSR. Using RCSR, we first cluster all clients according to their data distribution, and then use normal clients in the same cluster (with similar data distributions) to replace those problematic clients during training. We apply our methods to a couple of application scenarios in edge computing, and our results show that our methods can save training costs without affecting the accuracy.

Federated Learning (FL) has emerged as an efficient distributed model training framework that enables multiple clients cooperatively to train a global model without exposing their local data in edge computing (EC). However, FL usually faces statistical heterogeneity (e.g., non-IID data) and system heterogeneity (e.g., computing and communication capabilities), resulting in poor model training performance. To deal with the above two challenges, we propose an efficient FL framework, named FedBR, which integrates the idea of block-wise regularization and knowledge distillation (KD) into the pioneer FL algorithm FedAvg, for resource-constrained edge computing. Besides, we design a heuristic algorithm (GMBS) to determine the appropriate number of model blocks for clients according to their varied data distributions, computing, and communication capabilities. Extensive experimental results show that FedBR can reduce the time cost by 19.5% and the communication cost by 27% on average compared with the other three baselines when achieving the target testing accuracy under heterogeneous settings.

Entanglement routing plays a vital role in quantum networks. Previous works on entanglement routing did not note that all-optical switching capacity can be used to improve the network throughput or ignored that the placement of Entangled Photon Sources (EPS), another type of precious (and costly) quantum source, which also limits the network throughput. In this paper, we propose OptEPS to jointly optimize all-optical switching and EPS placement in entanglement routing to maximize the quantum network throughput. The main challenge of OptEPS lies in two folds: i). an entanglement may fail to be created; ii). the joint optimization problem suffers from a large time complexity. To overcome these challenges, we first formulate the joint optimization problem as a link-path based model and prune out some candidate paths in order to reduce the time complexity. Then, efficient algorithms are proposed to derive a near-optimal solution in a timely manner. Extensive simulations show that compared with the solutions ignoring EPS placement or without introducing all-optical switching, OptEPS will increase the network throughput by 1557% and 109%, respectively.

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.

Geo-Distributed Machine Learning (Geo-DML) has been proposed to collaborate geographically dispersed data centers (DCs) and train large scale machine learning (ML) models for various applications. While Geo-DML can achieve excellent performance, it also injects massive data traffic into the Wide Area Networks (WANs) in order to exchange gradients during model training process. Such a huge amount of traffic will not only incur network congestion and prolong the training procedure, but also result in straggler problem when DCs are working in heterogeneous network environments. To alleviate these problems, we propose Self-Adaptive Gradient Quantization (SAGQ) for Geo-DML in this work. In SAGQ, each worker DC adopts specific quantization method based on the heterogeneous and dynamic link bandwidth in order to reduce the communication overhead and balance the communication time among worker DCs. By doing so, SAGQ will speed up the Geo-DML training process without sacrificing the ML model performance. Extensive experiments show that compared with the state-of-the-art techniques, SAGQ reduces the Wall-clock time spent to train an ML model by 1.13×–21.31×. In addition, SAGQ can also improve the model accuracy by 0.11%–2.27% over baselines.

Federated learning (FL) has emerged in edge computing to address the limited bandwidth and privacy concerns of traditional cloud-based training. However, the existing FL mechanisms may lead to a long training time and consume massive communication resources. In this paper, we propose an efficient FL mechanism, namely FedCH, to accelerate FL in heterogeneous edge computing. Different from existing works which adopt the pre-defined system architecture and train models in a synchronous or asynchronous manner, FedCH will construct a special cluster topology and perform hierarchical aggregation for training. Specifically, FedCH arranges all clients into multiple clusters based on their heterogeneous training capacities. The clients in one cluster synchronously forward their local updates to the cluster header for aggregation, while all cluster headers take the asynchronous method for global aggregation. Our analysis shows that the convergence bound depends on the number of clusters and the training epochs. We propose efficient algorithms to determine the optimal number of clusters with resource budgets and then construct the cluster topology to address the client heterogeneity. Extensive experiments on both physical platform and simulated environment show that FedCH reduces the completion time by 49.5-79.5% and the network traffic by 57.4-80.8%, compared with the existing FL mechanisms.

Various middleboxes are ubiquitously deployed in networks to perform packet processing functions, such as firewalling, proxy, scheduling, etc., for the flows passing through them. With the explosion of network traffic and the demand for multiple types of network resources, it has never been more challenging on a middlebox to provide Quality-of-Service (QoS) guarantees to grouped flows. Unfortunately, all currently existing fair queueing algorithms fail in supporting hierarchical scheduling, which is necessary to provide QoS guarantee to the grouped flows of multiple service classes. In this paper, we present two new multi-resource fair queueing algorithms to support hierarchical scheduling, collapsed Hierarchical Dominant Resource Fair Queueing (collapsed H-DRFQ) and dove-tailing H-DRFQ. Particularly, collapsed H-DRFQ transforms the hierarchy of grouped flows into a flat structure for flat scheduling while dove-tailing H-DRFQ iteratively performs flat scheduling to sibling nodes on the original hierarchy. Through rigorous theoretical analysis, we find that both algorithms can provide hierarchical share guarantees to individual flows, while the upper bound of packet delay in dove-tailing H-DRFQ is smaller than that of collapsed H-DRFQ. We implement the proposed algorithms on Click modular router and the experimental results verify our analytical results.

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.

Quantum computing holds great promise and this work proposes to use new quantum data networks (QDNs) to connect multiple small quantum computers to form a cluster. Such a QDN differs from existing quantum key distribution (QKD) networks in that the former must deliver data quantum bits (i.e., qubits) reliably between different quantum computers. Two families of QDNs are studied, one using teleportation, named Tele-QDN, and the other using tell-and-go (TAG), named TAG-QDN. In order to provide reliable delivery of data qubits, while addressing QDN-specific constraints imposed by quantum physics laws such as the no-cloning theorem, and limited availability of quantum memory, two corresponding transport layer protocols suitable for distributed implementation are designed and evaluated. Such distributed quantum transport protocols (DTPs), named Tele-DTP and TAG-DTP, are the first-of-its-kind and are complementary to existing works on the protocol stack for QDNs which are at the network layer and below. Both analysis and extensive simulations show that the proposed DTPs can achieve high throughput and fairness. This study also offers new insights into potential tradeoffs involved in using different types of QDNs.

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.

Federated learning (FL) has been widely adopted to train machine learning models over massive distributed data sources in edge computing. However, the existing FL frameworks usually suffer from the difficulties of resource limitation and edge heterogeneity. Herein, we design and implement FedMP, an efficient FL framework through adaptive model pruning. We theoretically analyze the impact of pruning ratio on model training performance, and propose to employ a Multi-Armed Bandit based online learning algorithm to adaptively determine different pruning ratios for heterogeneous edge nodes, even without any prior knowledge of their computation and communication capabilities. With adaptive model pruning, FedMP can not only reduce resource consumption but also achieve promising accuracy. To prevent the diverse structures of pruned models from affecting the training convergence, we further present a new parameter synchronization scheme, called Residual Recovery Synchronous Parallel (R2SP), and provide a theoretical convergence guarantee. Extensive experiments on the classical models and datasets demonstrate that FedMP is effective for different heterogeneous scenarios and data distributions, and can provide up to 4.1× speedup compared to the existing FL methods.

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.

Quantum Data Networks (QDNs) typically leverage teleportation to reliably send data quantum bits (called qubits) to their destinations. To teleport a data qubit from Alice to Bob, one entanglement connection between Alice and Bob needs to be established. Accordingly, we have to establish as many entanglement connections as possible with limited quantum resources in order to maximize the network throughput. Conventional methods assume a known traffic matrix and calculate the paths to establish entanglement connections in one batch using a centralized algorithm. However, these methods are not scalable in large scale QDNs since it is time consuming to optimize the entanglement paths for a batch of requests, which may result in a long time slot duration and significantly reduce the network throughput. To address this issue, we propose an Online Entanglement Routing (OER) scheme which determines the entanglement paths for each request when it arrives. In addition, OER pursues work conservation and fairness among all requests in the QDNs. Through extensive simulations, we demonstrate that OER not only outperforms two representative heuristics by up to 61.27% and 52.79%, respectively, in terms of average request completion time, but also achieves a better fairness performance than these two counterparts.

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.

The knowledge of network distances, in the form of delay or latency, for example, is beneficial to a number of distributed applications. Notice that it is difficult and expensive to implement global network measurements to obtain network distance, a feasible idea is to predict unknown distances by introducing network coordinates with limited network measurements. The existing solutions always represent the unknown network distances in a rather unique number. However, research and applications indicate that the real network distances are hard to be accurately figured out and changes subtly in an interval over time with the dynamic network environments. Accordingly, this article proposes a tensor-based network distance prediction (TNDP) approach to represent network distance with confidence intervals, by exploiting the random distance tensor and distributed matrix factorization. With a small set of network measurements among the nodes selected randomly, a distance matrix tensor has been established and factorized into the product of two location matrixes with the adaptive SGD-based learning solution. By introducing the important training determinants, including weight matrix, regularization coefficient, and minibatch gradient descent with the exponential decay rates, the unknown distances among nodes can be accurately inferred in the forms of confidence intervals, with quick convergence and less overfitting. Extensive experimental simulations on a wide variety of available data sets demonstrate that TNDP is superior to other approaches in terms of accuracy for network distance prediction.

In this paper, we propose EdgePS, an advanced parameter server approach for distributed machine learning in edge computing scenarios. Different from the Conventional Parameter Server (CPS) approach, which performs parameter aggregation after every local training epoch, EdgePS synchronizes the parameters of all workers only when the local training cannot improve the global model performance. We first analyze how the local training will impact the performance of the global model, and then design algorithms to determine when the best time is to perform the parameter aggregation. Both real testbed experiments and extensive large scale simulations demonstrate that EdgePS can train a practical machine learning model, e.g., VGG-16, with up to 59.28% less time compared with the CPS approach. With the same training time, EdgePS can improve model accuracy by up to 30.19 % compared with the state-of-the-art distributed machine learning algorithm designed for edge computing scenarios.

Data generated at the network edge can be processed locally by leveraging the paradigm of edge computing. To fully utilize the widely distributed data, we concentrate on a wireless edge computing system that conducts model training using decentralized peer-to-peer (P2P) methods. However, there are two major challenges on the way towards efficient P2P model training: limited resources (e.g., network bandwidth and battery life of mobile edge devices) and time-varying network connectivity due to device mobility or wireless channel dynamics, which have received less attention in recent years. To address these two challenges, this paper adaptively constructs a dynamic and efficient P2P topology, where model aggregation occurs at the edge devices. In a nutshell, we first formulate the topology construction for P2P learning (TCPL) problem with resource constraints as an integer programming problem. Then a learning-driven method is proposed to adaptively construct a topology at each training epoch. We further give the convergence analysis on training machine learning models even with non-convex loss functions. Extensive simulation results show that our proposed method can improve the model training efficiency by about 11% with resource constraints and reduce the communication cost by about 30% under the same accuracy requirement compared to the benchmarks.

Federated learning (FL) has emerged in edge computing to address limited bandwidth and privacy concerns of traditional cloud-based centralized training. However, the existing FL mechanisms may lead to long training time and consume a tremendous amount of communication resources. In this paper, we propose an efficient FL mechanism, which divides the edge nodes into K clusters by balanced clustering. The edge nodes in one cluster forward their local updates to cluster header for aggregation by synchronous method, called cluster aggregation, while all cluster headers perform the asynchronous method for global aggregation. This processing procedure is called hierarchical aggregation. Our analysis shows that the convergence bound depends on the number of clusters and the training epochs. We formally define the resource-efficient federated learning with hierarchical aggregation (RFL-HA) problem. We propose an efficient algorithm to determine the optimal cluster structure (i.e., the optimal value of K) with resource constraints and extend it to deal with the dynamic network conditions. Extensive simulation results obtained from our study for different models and datasets show that the proposed algorithms can reduce completion time by 34.8%-70% and the communication resource by 33.8%-56.5% while achieving a similar accuracy, compared with the well-known FL mechanisms.

Quantum communication using qubits based on the principle of entangled photons is a promising solution to improve network security. However, it is difficult to successfully create an entanglement link or connection between two nodes, especially when they are far apart from each other. In addition, only one qubit can be exchanged over an established entanglement connection, resulting in a low throughput.In this paper, we propose Redundant Entanglement Pro-visioning and Selection (REPS) to maximize the throughput for multiple source-destination (SD) pairs in a circuit-switched, multi-hop quantum network. REPS has two distinct features: (i). It provisions backup resources for extra entanglement links between adjacent nodes for failure-tolerance; and (ii). It provides flexibility in selecting successfully created entanglement links to establish entanglement connections for the SD pairs to achieve network-wide optimization. Extensive analysis and simulations show that REPS can achieve optimal routing with a high probability, and improves the throughput by up to 68.35% over the highest-performing algorithms in existence. In addition, it also improves the fairness among the SD pairs in the networks.

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.

Network function virtualization (NFV) is critical to the scalability and flexibility of various network services in the form of service function chains (SFCs), which refer to a set of Virtual Network Functions (VNFs) chained in a specific order. However, the NFV performance is hard to fulfill the ever-increasing requirements of network services mainly due to the static orchestrations of SFCs. To tackle this issue, a novel Scalable SFC Orchestration (SSCO) scheme is proposed in this paper for NFV-enabled networks via federated reinforcement learning. SSCO has three remarkable characteristics distinguishing from the previous work: (1) A federated-learning-based framework is designed to train a global learning model, with time-variant local model explorations, for scalable SFC orchestration, while avoiding data sharing among stakeholders; (2) SSCO allows for parameter update among local clients and the cloud server just at the first and last epochs of each episode to ensure that distributed clients can make model optimization at a low communication cost; (3) SSCO introduces an efficient deep reinforcement learning (DRL) approach, with the local learning knowledge of available resources and instantiation cost, to map VNFs into networks flexibly. Furthermore, a loss-weight-based mechanism is proposed to generate and exploit reference samples in replay buffers for future training, avoiding the strong relevance of samples. Simulation results obtained from different working scenarios demonstrate that SSCO can significantly reduce placement errors and improve resource utilization ratio to place time-variant VNFs compared with the state-of-the-art mechanisms. Furthermore, the results show that the proposed approach can achieve desirable scalability.

With the development of applications on end devices, such as cell phones and tablets, more and more passengers would like to have entertainment on these end devices when they are cruising on vehicles. Due to the limited computation ability of the end devices, some of these applications have back-end components on the edge clouds, which are realized by Service Entities (SEs). In this work, we propose a system named DSEP to Dynamically determine the SEPlacement, such that the maximum latency experienced by the passengers can be minimized. To this end, we first train two sequential neural networks to predict the position of each individual vehicle, and propose an efficient algorithm based on optimization relaxation and Lagrange decomposition to determine the SE placement. Through extensive real-data driven simulations, we find that with the two sequential neural networks proposed in this paper, there are less than 1 percent errors on estimating where the passengers will access the edge cloud system. When the computation resources in the edge cloud are limited, DSEP can reduce the response latency by up to 43 percent compared with the nearest placement scheme. Even averaging the performance improvement over all simulation settings, DSEP can reduce the response latency by 16 percent.

Reducing Coflow Completion Time (CCT) has a significant impact on application performance in data-parallel frameworks. Most existing works assume that the endpoints of constituent flows in each coflow are predetermined. We argue that CCT can be further optimized by treating flows' destinations as an additional optimization dimension via reducer placement. In this article, we propose and implement RPC, a joint online Reducer Placement and Coflow bandwidth scheduling framework, to minimize the average CCT in cloud clusters. We first develop a 2-approximation algorithm to minimize the CCT of a single coflow, and then schedule all the coflows following the Shortest Remaining Time First (SRTF) principle. We use real testbed experiments and extensive large-scale simulations to demonstrate that RPC can reduce the average CCT by 64.98% compared with the state-of-the-art technologies.

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.

More and more applications learn from the data collected by the edge devices. Conventional learning methods, such as gathering all the raw data to train an ultimate model in a centralized way, or training a target model in a distributed manner under the parameter server framework, suffer a high communication cost. In this paper, we design Select Neighbors and Parameters (SNAP), a communication efficient distributed machine learning framework, to mitigate the communication cost. A distinct feature of SNAP is that the edge servers act as peers to each other. Specifically, in SNAP, every edge server hosts a copy of the global model, trains it with the local data, and periodically updates the local parameters based on the weighted sum of the parameters from its neighbors (i.e., peers) only (i.e., without pulling the parameters from all other edge servers). Different from most of the previous works on consensus optimization in which the weight matrix to update parameter values is predefined, we propose a scheme to optimize the weight matrix based on the network topology, and hence the convergence rate can be improved. Another key idea in SNAP is that only the parameters which have been changed significantly since the last iteration will be sent to the neighbors. Both theoretical analysis and simulations show that SNAP can achieve the same accuracy performance as the centralized training method. Compared to the state-of-the-art communication-aware distributed learning scheme TernGrad, SNAP incurs a significantly lower (99.6% lower) communication cost.

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 rapid development of Autonomous Vehicle (AV) technologies provides a new opportunity to evacuate vulnerable persons from their residences to shelters when some emergency event happens. One of the most important objectives is to minimize the evacuation time, which depends on the order to evacuate persons and which shelter each person is delivered to. We first formulate this AV dispatching problem as an Integer Linear Programming (ILP) model and prove this problem is NP-hard. Due to the problem hardness, an efficient algorithm based on Dynamical Programming (DP) is proposed. Through extensive simulations, we find that our algorithm can reduce the evacuation time by 58\% compared with a greedy based algorithm, which is the common method to solve the Traveling Salesman Problem (TSP), a special case of our AV dispatching problem.

With the increase of various of applications, CPU is no longer adequate for the computation tasks. Accordingly, some providers deploy accelerators in their cloud. Since not all the servers in the cloud can carry accelerators, how to schedule jobs onto accelerators and improve the system performance is an important issue. Due to the distributed computing frameworks in cloud computing systems, the jobs usually arrive in batches, and hence we try to minimize the make-span of a batch of jobs in this paper. To this end, we first formulate this problem as a mathematic programming model, and prove the NP-hardness of this problem. To solve this problem efficiently, we propose a 4- approximation algorithm. Through extensive simulations, we find that our algorithm can reduce the make-span of a batch of jobs by about 32%, and enhance the system throughput by up to 29% compared with our comparison baseline.

Reducing Coflow Completion Time (CCT) has a significant impact on application performance in data-parallel frameworks. Most existing works assume that the endpoints of constituent flows in each coflow are predetermined. We argue that CCT can be further optimized by treating flows' destinations as an additional optimization dimension via reducer placement. In this paper, we propose and implement RPC, a joint online Reducer Placement and Coflow bandwidth scheduling framework, to minimize the average CCT in cloud clusters. We first develop a 2-approximation algorithm to minimize the CCT of a single coflow, then schedule all the coflows following the Shortest Remaining Time First (SRTF) principle. We use a real testbed implementation and extensive large-scale simulations to demonstrate that RPC can reduce the average CCT by 64.98% compared with state-of-the-art technologies.

Combining Virtual Network Functions (VNF) and Software Defined Networking (SDN) enables fine-grained traffic steering to provide required network services to flows. However, online routing calculation and flow table enforcement incurs an non-negligible overhead. In this work, we propose to design a nonblocking network with fixed routing and VNF provisioning schemes to improve the network performance (e.g. the flow completion time). We first formulate this problem as a linear programming (LP) problem with infinite number of constraints, and leverage primal-dual technology to reformulate the problem as a polynomial size LP. The LP formulation is also extended to reconfigure the network when some components become unavailable, in order to keep the network nonblocking. Since solving the LP formulation is time consuming or even impossible in large scale networks, an efficient algorithm based on optimization decomposition and column generation is proposed to find a near optimal solution quickly. Simulation results show that nonblocking networks can speed up 60% of the flows by 2x, with a small increase in the required network capacity, compared with approaches that do not use the nonblocking networks.

Network function virtualization is a promising technique to greatly improve the effectiveness and flexibility of network services through a process named service function chain (SFC) mapping, with which network functions are deployed over virtualized and shared platforms in data centers. However, failures are quite common in data centers. Therefore, a practical and yet theoretically challenging issue in SFC mapping in such an environment is to manage the availability of the requests. In this paper, we present a framework to provision availability of SFC requests in a data center with multiple layers of connected devices, and the devices follow heterogeneous failure processes with the objective of minimizing resource usage. To expedite the process, we further propose an optimization problem of request mapping and backup estimation and solve it efficiently with an approximation algorithm. With simulations, we demonstrate the effectiveness of our proposed framework.

Using FPGA as accelerators is gaining popularity in Cloud computing. Usually, FPGA accelerators in a datacenter are managed as a single resource pool. By issuing a request to this pool, a tenant can transparently access FPGA resources. FPGA requests usually arrive in batches. The objective of scheduling is to minimize the make-span of a given batch of requests, which is the completion time of the entire batch of jobs. As a result, either the responsiveness is improved, or the system throughput is maximized. The key technical challenge is the existence of multiple resource bottlenecks. An FPGA job can be bottlenecked by either computation (i.e., computation-intensive) or network (i.e., network-intensive), and sometimes by both. To the best of our knowledge, this is the first work that minimizes the make-span of batched requests for an FPGA accelerator pool in Cloud computing that considers multiple resource bottlenecks. In this paper, we design several scheduling algorithms to address the challenge. We implement our scheduling algorithms in an IBM Cloud system. We conduct extensive evaluations on both a small scale testbed and a large-scale simulator. Compared with the Shortest-Job-First scheduling, our algorithms can reduce the make-span by 36.25 percent, and improve the system throughput by 36.05 percent.

This paper studies how to consolidate Virtual Machines (VMs) on physical severs in order to minimize the energy consumption in Cloud data centers. In Cloud data centers, a major energy consumption component is the physical servers, and it is a way to save the energy by consolidating VMs onto fewer VMs and shut down the idle physical servers. However, executing more VMs on fewer physical servers should degrade the VM performance. Accordingly, how to consolidate VMs but guarantee the VM performance is an important issue to study. To this end, we first formulate the VM consolidation problem as a mathematic model and then prove that it is equivalent to a generalized constrained minimumk-cut problem, which is the hardest NP-hard problem. Due to the problem complexity, an efficient heuristic named PEVMP (Performance-aware Energy-efficient Virtual Machine Placement) is proposed to solve it. In addition, we extend the PEVMP to be an online version to handle service dynamics. Extensive simulation results show that PEVMP can save up to 36.78% energy, and the performance of online algorithm is close to the offline result.

This paper studies how to optimize the interdependencies among the components in the interdependent Cyber-Physical Systems (CPS), in order to enhance the system robustness. In the interdependent CPS, some components may require the resources (or work conditions) provided by other components. Accordingly, small scale initial failure may incur large scale cascading failure as some of the working components may loss the resources (or work conditions) provided by the failed components. Due to this fact, we can optimize the resource allocation and change the interdependencies among components, so as to minimize the impact of cascading failure incurred by single component failure. To this end, we formulate the problem as an Integer Linear Programming (ILP) problem, and design an efficient algorithm based on progressive relaxation and rounding method to solve it. We also propose a greedy algorithm to quickly solve the problems in extreme large scale systems. In addition, we study how to allocate the redundant resources for the backup purpose and further enhance the system robustness. Simulation results show that if 1.3 times of the resources required by all the components are provided, we can eliminate the cascading failure incurred by single component failure.

Computing frameworks have been widely deployed to support global-scale services. A job typically has multiple sequential stages, where each stage is further divided into multiple parallel tasks. We call the set of all the tasks in a stage of a job a cotask. In this paper, we aim to minimize the average Cotask Completion Time (CCT) in cotask scheduling. To the best of our knowledge, there is no prior work on cotask scheduling for cloud computing. We propose the Cotask Scheduling Scheme (CSS), and take MapReduce as a representative of computing frameworks. CSS schedules cotasks following the Minimum Completion Time First (MCTF) policy, and we prove this problem is NP-hard. We formulate the model using the Integer Linear Programming (ILP), and solve it through an efficient heuristics based on ILP relaxation. Through real trace based simulations, we show that CSS is able to reduce the average CCT by up to 62.20% and 69.93% with traces from our testbed and from a large production cluster respectively.

Network Function Virtualization (NFV) is a promising technique to greatly improve the effectiveness and flexibility of network services through a process named Service Function Chain (SFC) mapping, with which different network services are deployed over virtualized and shared platforms in data centers. However, such an evolution towards software-defined network functions introduces new challenges to network services which require high availability. One effective way of protecting the network services is to use sufficient redundancy. By doing so, however, the efficiency of physical resources may be greatly decreased. To address such an issue, this paper defines an optimal availability-aware SFC mapping problem and presents a novel online algorithm that can minimize the physical resources consumption while guaranteeing the required high availability within a polynomial time. Simulation results show that our proposed algorithm can significantly improve SFC mapping request acceptance ratio and reduce resource consumption.

This paper studies how to determine an optimal order of recovering interdependent Cyber Physical Systems (CPS) after a large scale failure. In such a CPS, some failed devices must be repaired first before others can. In addition, such failed devices require a certain amount of repair resources and may take multiple stages to repair. We consider two scenarios: 1) reserved model where all the required repair resources should be prepared at the beginning of repairing a device; and 2) opportunistic model where we can partially repair a device with only part of the required resources. For each scenario, we model it using an Integer Linear Programming (ILP) and use a relaxation and rounding method to design an ILP based algorithm. In addition, we also design a Dynamic Programming (DP) based algorithm. Simulation results show that ILP based algorithm outperforms DP based algorithm by 10%-20% in systems with less than 200 failed devices, but DP based algorithm can support extreme large size systems with more than 5000 failed devices.

As Network Function Virtualization (NFV) becomes reality and cloud computing offers a scalable pay-as-you-go charging model, more network operators would like to outsource their Service Function Chains (SFC) to the public clouds in order to reduce the operational cost. However, how to minimize the operational cost with Quality of Service (QoS) guarantee when outsourcing SFC is still an open problem. In this paper, we are to study this problem when there are large number of candidate cloud providers with diverse pricing schemes of network functions. In addition, extra delay is introduced as the result of outsourcing SFCs. Firstly, we formulate this problem as an Integer Linear Programming (ILP) model. Then we design an efficient heuristic algorithm named QoS-Guaranteed SFC Outsourcing algorithm (QGSO) based on Hidden Markov Model (HMM). The extensive simulations show that QGSO saves up to 75.8% cost compared with that of deploying network functions in local network. QGSO also achieves up to 42.6% cost savings compared with the result of first-fit based optimization algorithm.

In this paper, we present our effort towards comprehensive traffic forecasting for big data applications using external, light-weighted file system monitoring. Our idea is motivated by the key observations that rich traffic demand information already exists in the log and meta-data files of many big data applications, and that such information can be readily extracted through run-time file system monitoring. As the first step, we use Hadoop as a concrete example to explore our methodology and develop a system called HadoopWatch to predict traffic demands of Hadoop applications. We further implement HadoopWatch in a small-scale testbed with 10 physical servers and 30 virtual machines. Our experiments over a series of MapReduce applications demonstrate that HadoopWatch can forecast the traffic demand with almost 100% accuracy and time advance. Furthermore, it makes no modification on the Hadoop framework, and introduces little overhead to the application performance. Finally, to showcase the utility of accurate traffic prediction made by HadoopWatch, we design and implement a simple HadoopWatch-enabled network optimization module into the HadoopWatch controller, and with realistic Hadoop job benchmarks we find that even a simple algorithm can leverage the forecasting results provided by HadoopWatch to significantly improve the Hadoop job completion time by up to 14.72%.

In current data centers, an application (e.g., MapReduce, Dryad, search platform, etc.) usually generates a group of parallel flows to complete a job. These flows compose a coflow and only completing them all is meaningful to the application. Accordingly, minimizing the average Coflow Completion Time (CCT) becomes a critical objective of flow scheduling. However, achieving this goal in today's Data Center Networks (DCNs) is quite challenging, not only because the schedule problem is theoretically NP-hard, but also because it is tough to perform practical flow scheduling in large-scale DCNs. In this paper, we find that minimizing the average CCT of a set of coflows is equivalent to the well-known problem of minimizing the sum of completion times in a concurrent open shop. As there are abundant existing solutions for concurrent open shop, we open up a variety of techniques for coflow scheduling. Inspired by the best known result, we derive a 2-approximation algorithm for coflow scheduling, and further develop a decentralized coflow scheduling system, D-CAS, which avoids the system problems associated with current centralized proposals while addressing the performance challenges of decentralized suggestions. Trace-driven simulations indicate that D-CAS achieves a performance close to Varys, the state-of-the-art centralized method, and outperforms Baraat, the only existing decentralized method, significantly.

Network Function Virtualization (NFV) provides an effective way to reduce the network provider's cost by allowing multiple Virtual Networks (VNs) to share the underlying physical infrastructure. In the NFV environment, especially when supporting multicast service over the VNs, reliability is a critical requirement in the process of VN mapping since the failure of one virtual node can cause the malfunction of all the subsequent nodes that receive multicasting data from it. In this paper, for the first time, we study how to efficiently map VNs for reliable multicast services, while taking into consideration the max-min fairness of the reliability among distinct VNs. We propose a Mixed Integer Linear Programming (MILP) model to determine the upper bound on the max-min fairness reliability. In addition, an efficient heuristic, namely Uniform Reliability Mutation based Genetic (URMG) algorithm, is developed to address reliable multicast VN mapping with a low computational complexity. By encoding multicast tree construction and link mapping into path selection, taking into consideration the max-min reliability fairness goal, and the networking reliability factors during mutation, URMG can globally optimize the reliability and its fairness of all the multicast VN requests. Through extensive simulations, we demonstrate that URMG achieves close to the optimal reliability fairness with a much lower time complexity than the MILP and yields a significant performance improvement in terms of reliability fairness, bandwidth consumption and transmission delay comparing with other heuristic solutions.

In current data centers, an application (e.g. MapReduce) usually generates a collection of parallel flows sharing a common goal. These flows compose a coflow and only completing them all is meaningful. Accordingly, minimizing the average coflow completion time (CCT) becomes a critical objective for flow scheduling. In this topic, the state-of-the-art centralized method, Varys, achieves a good average CCT; but it has the scalability problem. Alternatively, the only existing decentralized method, Baraat, suffers from the head-of-line blocking problem. To solve these problems, we propose D-CAS, a preemptive, decentralized, coflow-aware scheduling system in this paper. D-CAS pursues coflow-level remaining-time-first (MRTF) principle by leveraging a simple negotiation mechanism between each coflow's data senders and receivers. As the MRTF principle is inherently preemptive and proven to be a near-optimal guideline to minimize average CCT, D-CAS avoids the head-of-line blocking problem and gets good performances. Through extensive simulations, we find that D-CAS achieves a performance close to Varys (gap <; 15%) and outperforms Baraat significantly (about 1.4-4×).

In the data flow models of today's data center applications such as MapReduce, Spark and Dryad, multiple flows can comprise a coflow group semantically. Only completing all flows in a coflow is meaningful to an application. To optimize application performance, routing and scheduling must be jointly considered at the level of a coflow rather than individual flows. However, prior solutions have significant limitation: they only consider scheduling, which is insufficient. To this end, we present Rapier, a coflow-aware network optimization framework that seamlessly integrates routing and scheduling for better application performance. Using a small-scale testbed implementation and large-scale simulations, we demonstrate that Rapier significantly reduces the average coflow completion time (CCT) by up to 79.30% compared to the state-of-the-art scheduling-only solution, and it is readily implementable with existing commodity switches.

In this paper, we study the multiobjective optimization problem for green network routing. Although traditional commonly used multiobjective optimization methods can yield a Pareto efficient solution, they need to construct an aggregate objective function (AOF) or model one objective as a constraint in the optimization problem formulation. As a result, it is difficult to achieve a fair tradeoff among all objectives. Accordingly, we induce a Nash bargaining framework, which treats the two objectives as two virtual players in a game theoretic model, who negotiate how traffic should be routed to optimize both objectives. During the negotiation, each of them announces its performance threat value to reduce its cost, so the model is regarded as a threat value game. Our analysis shows that no agreement can be achieved if each player sets its threat value selfishly. To avoid such a negotiation break-down, we modify the threat value game to have a repeated process and design a mechanism to not only guarantee an agreement, but also generate a fair solution. Finally, to evaluate the efficiency of our proposed framework, we implement it into two multiobjective optimization cases for network green routing. The first case is load balancing and energy efficiency optimization for intradomain routing, and the second one is the energy efficiency optimization of two domains for interdomain routing.

In this paper, we study how to manage the topology reconfiguration in OSA-based datacenter networks (DCNs). Though an OSA-based DCN can change its topology to adapt to the traffic matrix and improve the network scalability, it requires too much time (10ms) to reconfigure the topology, which may not only incur a great amount of traffic loss in high throughput low latency DCNs, but also bring much performance degradation to the delay sensitive flows. Therefore, a progressive topology reconfiguration scheme is required to reduce the traffic loss and guarantee the performance of delay sensitive flows. To this end, we first formulate the problem as a mathematical model, and then analyze its feasibility and complexity. Based on these analyses, topology management algorithm (TMA) is proposed to calculate the topology reconfiguration scheme that can maintain the topology connectivity during reconfiguration. By simulation, we find that TMA can reduce the traffic loss during topology reconfiguration by up to 50% in most of the cases and reconfigure topology without traffic loss in some cases.

This paper aims at systematically analyzing the pricing schemes in data center network. The interaction between a monopolistic operator and customers in the network is modeled as Stackelberg game. In this model, both homogeneous- and heterogeneous-customer scenarios are analyzed. In homogeneous customer case, a special scenario is that only a single customer exists in the network. In this scenario, we observe that the Stackelberg equilibrium will lead to a Pareto-inefficient outcome. To address this problem, a two-part pricing scheme is proposed to derive a Pareto efficient outcome and benefit both the operator and customers. When there are an infinite number of homogeneous customers in the network, our analysis shows that customers' selfish action may incur zero utility to them and operator can achieve all the utility by announcing an appropriate price. As to the heterogeneous customer case, we not only analyse how the operator should price the network resources, but also introduce Paris Metro Pricing (PMP) scheme to further increase operator's profit. Since the operator's profit is not a concave function of the resource price, these studies are conducted by simulation.

TCP in cast congestion which can introduce hundreds of milliseconds delay and up to 90% throughput degradation, severely affecting application performance, has been a practical issue in high-bandwidth low-latency data enter networks. Despite continuous efforts, prior solutions have significant drawbacks. They either only support quite a limited number of senders (e.g., 40-60), which is not sufficient, or require non-trivial system modifications, which is impractical and not incrementally deployable. We present PAC, a simple yet very effective design to tame TCP in cast congestion via Proactive ACK Control at the receiver. The key design principle behind PAC is that we treat ACK not only as the acknowledgement of received packets but also as the trigger for new packets. Leveraging data center network characteristics, PAC enforces a novel ACK control to release ACKs in such a way that the ACK-triggered in-flight data can fully utilize the bottleneck link without causing in cast collapse even when faced with over a thousand senders. We implement PAC on both Windows and Linux platforms, and extensively evaluate PAC using small-scale test bed experiments and large-scale ns-2 simulations. Our results show that PAC significantly outperforms the previous representative designs such as ICTCP and DCTCP by supporting 40X (i.e., 40?1600) more senders, further, it does not introduce spurious timeout and retransmission even when the measured 99th percentile RTT is only 3.6ms. Our implementation experiences show that PAC is readily deployable in production data enters, while requiring minimal system modification compared to prior designs.

In this paper, we study the tradeoff between two important traffic engineering objectives: load balance and energy efficiency. Although traditional commonly used multi-objective optimization methods can yield a Pareto efficient solution, they need to construct an aggregate objective function (AOF) or model one of the two objectives as a constraint in the optimization problem formulation. As a result, it is difficult to achieve a fair tradeoff between these two objectives. Accordingly, we induce a Nash bargaining framework which treats the two objectives as two virtual players in a game theoretic model, who negotiate how traffic should be routed in order to optimize both objectives. During the negotiation, each of them announces its performance threat value to reduce its cost, so the model is regarded as a threat value game. Our analysis shows that no agreement can be achieved if each player sets its threat value selfishly. To avoid such a negotiation break-down, we modify the threat value game to have a repeated process and design a mechanism to not only guarantee an agreement, but also generate a fair solution. In addition, the insights from this work are also useful for achieving a fair tradeoff in other multi-objective optimization problems.

The concept of monitoring trail (m-trail) provides a striking mechanism for fast and unambiguous link failure localization in all-optical networks. To achieve fast m-trail design in large-size networks, two efficient heuristics RCA+RCS and MTA are proposed against the optimal ILP (Integer Linear Program) model. However, RCA+RCS suffers from the disjoint trail problem which increases the required number of m-trails, and MTA always finds a deterministic solution which may not be good enough due to the limited solution space. In this paper, we propose a new heuristic RNH-MTA (Monitoring Trail Allocation with the Random Next Hop policy) to solve those issues. Similar to MTA, RNH-MTA ensures a valid optical structure of each m-trail and sequentially adds necessary m-trails to the solution, and thus is free of the disjoint trail problem. By replacing the deterministic searching in MTA using the Random Next Hop policy, RNH-MTA sets up a probabilistic model in extending each m-trail. This not only enlarges the solution space and increases the solution diversity, but also enables a controllable tradeoff between the solution quality and the running time of the algorithm. Our numerical results show the advantages of RNH-MTA over both RCA+RCS and MTA.

We study the m-trail (monitoring trail) allocation problem in all-optical WDM mesh networks for achieving fast and unambiguous link failure localization. The existing ILP is not feasible for solving the problem in large-size networks. A heuristic RCA+RCS can find feasible solutions in a shorter running time, but it is a randomized algorithm. More importantly, RCA+RCS suffers from the disjoint trail problem which dramatically increases the number of required monitors in large-size networks. In this paper, we propose a new heuristic MTA (Monitoring Trail Allocation) to solve the problem. MTA avoids those issues in RCA+RCS, and achieves an efficient tradeoff between monitor cost and bandwidth cost. Compared with RCA+RCS, MTA greatly shortens the running time and achieves a much higher solution quality. We also show that MTA provides a flexible framework to enable multiple possible variations for future study.