Compression is an efficient way to relieve the tremendous communication overhead of federated learning (FL) systems. However, for the existing works, the information loss under compression will lead to unexpected model/gradient deviation for the FL training, significantly degrading the training performance, especially under the challenges of data heterogeneity and model obsolescence. To strike a delicate trade-off between model accuracy and traffic cost, we propose Caesar, a novel FL framework with a low-deviation compression approach. For the global model download, we design a greedy method to optimize the compression ratio for each device based on the staleness of the local model, ensuring a precise initial model for local training. Regarding the local gradient upload, we utilize the device's local data properties (i.e., sample volume and label distribution) to quantify its local gradient's importance, which then guides the determination of the gradient compression ratio. We have implemented Caesar, on two physical platforms with 40 smartphones and 80 NVIDIA Jetson devices. Extensive results show that Caesar, can reduce the traffic costs by about 25.54%þicksim37.88% when achieving the same target accuracy compared to the compression-based baselines, while incurring only a 0.68% degradation in final test accuracy relative to the full-precision communication.

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.

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

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.

Federated fine-tuning (FedFT) provides an effective paradigm for fine-tuning large language models (LLMs) in privacy-sensitive scenarios. However, practical deployment remains challenging due to the limited resources on end devices. Existing methods typically utilize parameter-efficient fine-tuning (PEFT) techniques, such as Low-Rank Adaptation (LoRA), to substantially reduce communication overhead. Nevertheless, significant memory usage for activation storage and computational demands from full backpropagation remain major barriers to efficient deployment on resource-constrained end devices. Moreover, substantial resource heterogeneity across devices results in severe synchronization bottlenecks, diminishing the overall fine-tuning efficiency. To address these issues, we propose FedQuad, a novel LoRA-based FedFT framework that adaptively adjusts the LoRA depth (the number of consecutive tunable LoRA layers from the output) according to devices' computational power, while employing activation quantization to reduce memory overhead, thereby enabling efficient deployment on resource-constrained devices. Specifically, FedQuad first identifies the feasible and efficient combinations of LoRA depth and the number of activation quantization layers based on device-specific resource constraints. Subsequently, FedQuad employs a greedy strategy to select the optimal configurations for each device, effectively accommodating system heterogeneity. Extensive experiments demonstrate that FedQuad achieves a 1.4–5.3× convergence acceleration compared to state-of-the-art baselines when reaching target accuracy, highlighting its efficiency and deployability in resource-constrained and heterogeneous end-device environments.

Federated Learning (FL) has emerged as a potential distributed learning paradigm that enables model training on edge devices (i.e., workers) while preserving data privacy. However, its reliance on a centralized server leads to limited scalability. Decentralized federated learning (DFL) eliminates the dependency on a centralized server by enabling peer-to peer model exchange. Existing DFL mechanisms mainly employ synchronous communication, which may result in training inefficiencies under heterogeneous and dynamic edge environments. Although a few recent asynchronous DFL (ADFL) mechanisms have been proposed to address these issues, they typically yield stale model aggregation and frequent model transmission, leading to degraded training performance on non-IID data and high communication overhead. To overcome these issues, we present DySTop, an innovative mechanism that jointly optimizes dynamic staleness control and topology construction in ADFL. In each round, multiple workers are activated, and a subset of their neighbors is selected to transmit models for aggregation, followed by local training. We provide a rigorous convergence analysis for DySTop, theoretically revealing the quantitative relationships between the convergence bound and key factors such as maximum staleness, activating frequency, and data distribution among workers. From the insights of the analysis, we propose a worker activation algorithm (WAA) for staleness control and a phase-aware topology construction algorithm (PTCA) to reduce communication overhead and handle data non-IID. Extensive evaluations through both large-scale simulations and real-world testbed experiments demonstrate that our DySTop reduces completion time by 46.7% and the communication resource consumption by 48.3% compared to state-of-the-art solutions, while maintaining the same model accuracy.

Decentralized Federated Graph Learning (DFGL) overcomes the potential bottlenecks of the parameter server in FGL. However, extensive cross-worker communication of graph node embeddings during DFGL training introduces substantial communication costs. To improve communication efficiency, constructing sparse network topologies or applying graph sampling are potential methods. In this paper, we first reveal the bidirectional coupling between network topology construction and graph sampling, underscoring the necessity of their joint optimization. Motivated by this insight, we proposeDuplex, a unified framework that co-optimizes these two components by explicitly modeling their interdependent relationship, thereby significantly reducing communication costs while enhancing training performance in DFGL.Duplexformulates the decision-making process as a coordinated configuration$\langle \mathbf {A}, \mathbf {R} \rangle$, where$\bf {A}$is the adjacency matrix of the network topology and$\bf {R}$denotes the set of graph sampling ratios for workers. However, determining proper coordinated configurations to achieve optimal communication efficiency and training performance (e.g., model accuracy and convergence rate) is challenging due to several practical issues,e.g., statistical heterogeneity and dynamic network conditions. To overcome these challenges,Duplexintroduces a novel learning-driven algorithm to adaptively determine optimal network topologies and graph sampling ratios for workers. Experimental results demonstrate thatDuplexreduces completion time by 20.1%–48.8% and communication costs by 16.7%–37.6% to achieve target accuracy, while improving accuracy by 3.3%–7.9% under identical resource budgets compared to baselines.

Considering the hardware-friendly characteristics, structured pruning has emerged as an effective solution to reduce the resource requirements of large language models (LLMs) on resource-constrained devices. Since pruning a certain number of parameters will often reduce the model accuracy, fine-tuning is usually required to recover performance loss. However, fine-tuning relies on high device power and substantial data, making it unsuitable for on-device applications. Recent approaches propose post-training structured pruning techniques that do not require fine-tuning, following three granularities,i.e., neurons, attention heads, and layers. Unfortunately, the previous solutions still suffer from the high memory overhead of substructures' importance evaluation at different granularities and the problem of only applying to models with specific structures, which limit their scope of applications. This paper proposes COMP, a lightweight and general post-training structured hybrid-granularity pruning method designed for on-device applications. COMP begins by assessing the importance of model layers and neurons individually using distributional distance and the matrix condition number. Subsequently, COMP performs fine-grained neuron pruning and simultaneously determines whether to apply coarse-grained layer pruning or not by comparing the outcomes of the two granularity strategies. Furthermore, COMP implements mask tuning to restore model accuracy without additional fine-tuning, minimizing dependency on external data resources and device power. Experimental results demonstrate that COMP performs well across models with various architectures. When pruning 20% of LLaMA-2-13B parameters, COMP requires less than 8 GB of memory, maintaining more than 90% model accuracy. Meanwhile, COMP improves performance by 3.54% compared to LLM-Pruner, while reducing memory overhead by 90%.

Federated learning (FL) enables multiple clients to collaboratively train models without exposing raw data. However, most FL research assumes that all clients have fully labeled data, which is impractical for many real-world applications. To this end, we focus on semi-supervised FL (SSFL), where data samples of each client are partially labeled. Existing SSFL methods often ignore three inherent characteristics of FL: limited communication resources, data heterogeneity and system heterogeneity, which severely hinder convergence stability and efficiency. This paper proposes E-FedAC, a novel SSFL framework that tackles these challenges through alternating client-to-client (C2C) collaboration. Specifically, E-FedAC employs a two-stage clustering strategy in each training round while concurrently considering differences in client computing/communication capabilities to mitigate the impact of intra-cluster stragglers. The first stage employs similarity clustering to group clients based on local data distribution, which allows similar clients to share knowledge and generate high-quality pseudo-labels for unlabeled data. In the second stage, clients are re-grouped using a dissimilarity clustering strategy to approximate the IID setting at the cluster level, thereby alleviating the bias induced by Non-IID data. E-FedAC utilizes a reinforcement learning algorithm to adaptively determine the average number of intra-cluster iterations across all clusters for both clustering stages, balancing between labeling assistance from similar clients and unbiased optimization from dissimilar clients. Additionally, E-FedAC dynamically optimizes local updating frequencies for each generated cluster based on this average and individual cluster capabilities, further reducing the waiting time across clusters. Extensive evaluations demonstrate that E-FedAC can provide up to 4.02× speedup and 61.74% savings in communication costs compared with existing benchmarks.

Recently, aided by edge computing (EC), federated meta-learning (FML) has been proposed to adequately utilize personalized data on different edge devices by incorporating meta-learning with federated learning (FL). Unlike conventional FL which conducts several stochastic gradient descent (SGD) steps to directly update the local model in each training round, FML first performs some SGDsteps to obtain a reference model and then performs a meta-step to update the local model along the direction towards the reference model. In this way, FML can identify common patterns and structures across different clients (i.e., edge devices) and quickly adapt to new data distributions, which exhibits its advantage in dealing with statistical heterogeneity inherent in FL. However, existing FML approaches struggle to effectively cope with two key challenges: i) the disparity in dataset informativeness among clients with statistically heterogeneous local data; and ii) the disparity in computing capacities among clients with heterogeneous hardware configurations. Herein, we propose a heterogeneity-aware FML framework, termed HFML, which explores adjusting the execution frequencies of SGD step and meta-step in each training round to address the above statistical and system heterogeneity challenges simultaneously. We introduce usable information (UI) as a new metric in HFML to quantify dataset informativeness, and theoretically analyze the influence of the execution frequencies of SGD steps and meta-steps on model performance and convergence speed. Based on the theoretical analysis, we develop an efficient optimization algorithm to jointly adjust the execution frequencies for different clients to handle the heterogeneity issues, which contributes to accelerating model training and enhancing personalization performance. Experimental results demonstrate that HFML can speed up training by up to 4.02× and improve model accuracy by an average of 11.5% compared to the baselines under heterogeneous settings.

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.

Decentralized federated learning (DFL) has gained popularity for training machine learning models on massive data in edge computing, as it avoids the potential bottleneck of conventional parameter server architectures. However, the existing DFL solutions typically use deterministic topologies that struggle with both system heterogeneity and non-IID local data, resulting in high bandwidth costs and slow convergence rates. In this paper, we propose a novel mechanism called Communication-efficient Decentralized Federated Learning (CedFL) to accelerate model training. InCedFL, each worker will communicate with each of its neighbors (i.e., model exchange) according to a certain probability at each epoch, so as to reduce bandwidth consumption. To this end, we then propose an efficient algorithm to adaptively determine the optimal probability for each worker pair according to real-time system situations (e.g., data distribution and bandwidth resource). Our proposed mechanism has been extensively tested on classical models and datasets, and the results demonstrate its high effectiveness.CedFLhas been shown to reduce completion time for model training by approximately 55% and improve test accuracy by 11% under the bandwidth constraint, compared to state-of-the-art solutions.

Federated learning (FL) enables training AI models across distributed edge devices (i.e., workers) using local data, while facing challenges including communication resource constraints, edge heterogeneity, and non-IID data. Over-the-air computation (AirComp) has emerged as a promising technique to improve communication efficiency by leveraging the superposition property of a wireless multiple access channel (MAC) for model aggregation. However, over-the-air aggregation requires strict synchronization among edge devices, which is essentially incompatible with the asynchronous FL mechanisms often used to handle edge heterogeneity. To overcome this incompatibility, we propose Air-FedGA, a grouping-based asynchronous FL mechanism via AirComp, where workers are organized into groups for synchronized over-the-air aggregation within each group, while groups asynchronously communicate with the parameter server to update the global model. This design retains the communication efficiency of AirComp while addressing training inefficiency caused by edge heterogeneity. We provide a rigorous convergence analysis for Air-FedGA, theoretically quantifying how the convergence bound depends on several key factors, such as the maximum staleness, the degree of non-IID data among groups, and the AirComp aggregation mean squared error (MSE). Guided by these theoretical insights, we propose power control and worker grouping algorithms to minimize the convergence bound by jointly optimizing the AirComp aggregation MSE and the grouping strategy. We conduct experiments on classical models and datasets, and the results demonstrate that our proposed mechanism and algorithms can accelerate the model training by 1.83-$2.22\times $compared with the state-of-the-art solutions.

Recently, Split Federated Learning (SFL) advances typical Federated Learning (FL) and offers a feasible solution by splitting a full model into a bottom model (for clients) and a top model (for the server), which alleviates the computation and/or communication burden on clients. However, existing SFL works often assume sufficient labeled data on clients, which is usually impractical. Besides, non-IID data poses another challenge to ensure efficient model training. To our best knowledge, the above two data-related issues have not been simultaneously addressed in SFL. Herein, we review the distinct properties of SFL and develop a novel Semi-supervised SFL system, called SemiSFL. In SemiSFL, a student bottom model and a teacher bottom model are assigned to each client, while the server maintains the top parts and full versions of both the global and teacher models. Cross-entity (i.e., clients and the server) semi-supervised training and server-side supervised training are alternately conducted. During semi-supervised training, we explore regularizing the student features (produced by student bottom models) from different clients with the teacher features (produced by teacher bottom models) before conducting semi-supervised training, so as to improve the generalization ability of student bottom models. Moreover, our theoretical and experimental investigations reveal that the inconsistent training processes on labeled and unlabeled data have an influence on the effectiveness of SemiSFL. To mitigate training inconsistency, we develop an algorithm for dynamically regulating the frequency of performing server-side supervised training. Extensive experiments on benchmark models and datasets show that SemiSFL provides a 3.8× speed-up in training time, reduces the communication cost by about 70.3% while reaching the target accuracy, and achieves up to 5.8% improvement in accuracy under different non-IID settings compared to the state-of-the-art baselines.

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.

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.

Large language models (LLMs) rely heavily on sampling methods to generate diverse and highquality text.While existing sampling methods like top-p and min-p have identified the detrimental effects of low-probability tails in LLMs' outputs, they still fail to effectively distinguish between diversity and noise.This limitation stems from their reliance on probability-based metrics that are inherently sensitive to temperature scaling.Through empirical and theoretical analysis, we make two key discoveries: (1) the pre-softmax logits exhibit a clear statistical separation between informative tokens and noise, and (2) we prove the mathematical equivalence of min-p and top-(1-p) under uniform distribution over logits.These findings motivate the design of top-nσ, a novel sampling method that identifies informative tokens by eliminating noise directly in logit space.Unlike existing methods that become unstable at high temperatures, top-nσ achieves temperature-invariant token selection while preserving output diversity.Extensive experiments across reasoning and creative writing tasks demonstrate that our method consistently outperforms existing approaches, with particularly significant improvements in high-temperature settings.

Edge inference is a technology that enables real-time data processing and analysis on clients near the data source. To ensure compliance with the Service-Level Objectives (SLOs), such as a 30% latency reduction target, caching is usually adopted to reduce redundant computations in inference tasks on stream data. Due to task and data correlations, sharing cache information among clients can improve the inference performance. However, the non-independent and identically distributed (non-IID) nature of data across different clients and the long-tail distributions, where some classes have significantly more samples than others, will reduce cache hit ratios and increase latency. To address the aforementioned challenges, we propose an efficient inference framework, CoCa, which leverages a multi-client collaborative caching mechanism to accelerate edge inference. On the client side, the model is pre-set with multiple cache layers to achieve a quick inference. During inference, the model performs sequential lookups at cache layers activated by the edge server. On the server side, CoCa uses a two-dimensional global cache to periodically aggregate information from clients, mitigating the effects of non-IID data. For client cache allocation, CoCa first evaluates the importance of classes based on how frequently and recently their samples have been accessed. CoCa then selects frequently recurring classes to address long-tail distribution challenges. Finally, CoCa dynamically activates cache layers to balance lookup overhead and accuracy. Extensive experiments demonstrate that CoCa reduces inference latency by 23.0% to 45.2% on the VGG, ResNet and AST models with a slight loss of accuracy.

Federated fine-tuning (FedFT) has become a decentralized approach for fine-tuning pre-trained large language models(LLMs). However, due to the immense size of LLMs, there are two critical challenges for efficient FedFT in practice, i.e., resource constraints and system heterogeneity. Though existing approaches employ low-rank adaptation (LoRA) method, to mitigate fine-tuning overhead, they still suffer from high memory consumption and large training latency. According to the characteristics of FedFT, we observe that appropriate quantization and LoRA configurations can reduce resource consumption while maintaining comparable model performance. Consequently, we propose an efficient FedFT framework, termed FedQLoRA, which dynamically adjusts the quantization level and LoRA depth during training. This design enables large models to be fine-tuned on resource-limited devices while reducing training latency and preserving model performance. Extensive experimental results demonstrate that FedQLoRA achieves up to 70.34% reduction in training time and$62.71 \%-77.50 \%$savings in memory consumption compared to baseline methods.

Federated learning (FL) is a new paradigm to train AI models over distributed edge devices (i.e., workers) using their local data, while confronting various challenges including communication resource constraints, edge heterogeneity and data Non-IID. Over-the-air computation (AirComp) is a promising technique to achieve efficient utilization of communication resource for model aggregation by leveraging the superposition property of a wireless multiple access channel (MAC). However, AirComp requires strict synchronization among edge devices, which is hard to achieve in heterogeneous scenarios. In this paper, we propose an AirComp-based grouping asynchronous federated learning mechanism (Air-FedGA), which combines the advantages of AirComp and asynchronous FL to address the communication and heterogeneity challenges. Specifically, AirFedGA organizes workers into groups and performs over-theair aggregation within each group, while groups asynchronously communicate with the parameter server to update the global model. In this way, Air-FedGA accelerates the FL model training by over-the-air aggregation, while relaxing the synchronization requirement of this aggregation technology. We theoretically prove the convergence of Air-FedGA. We formulate a training time minimization problem for Air-FedGA and propose the power control and worker grouping algorithm to solve it, which jointly optimizes the power scaling factors at edge devices, the denoising factors at the parameter server, as well as the worker grouping strategy. We conduct experiments on classical models and datasets, and the results demonstrate that our proposed mechanism and algorithm can speed up FL model training by$\mathbf{29.9\% - 71.6\%}$compared with 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.

Edge video analytics enables agile responses of machine-centric applications by streaming videos from end devices to edge servers (ESs) for resource-intensive deep neural network (DNN) inference. Quality of Inference (QoI), reflected by end-to-end analytics delay and inference accuracy, is crucial for the high-quality real-time decision-making. Due to the limited ES resources and dynamic network conditions, video configuration adaptation and fine-grained resource allocation are necessary to enhance the QoI of video streams, which involves a delicate balance between delay and accuracy. In this article, we propose an edge-enabled multivideo analytics framework, in which performing DNN inference relies on heterogeneous resources, including CPU, GPU, and memory. Considering the different impacts of heterogeneous resources on QoI and double-queue backlogs, we formulate the joint video configuration adaptation, CPU-GPU resource allocation, and batch size selection (JCCGB) problem based on semi-Markov decision process to maximize the long-term average QoI. Then, Lyapunov optimization is applied to transform the original problem into one that minimizes the Lyapunov drift-plus-penalty upper bound, thereby ensuring the stability of both the transmission and computation queues. To tackle the potential multimodality of the optimal configuration adaptation and resource allocation policy, we propose the diffusion-deep-reinforcement-learning-based JCCGB (DD-JCCGB) scheme. This approach effectively enhances the policy performance and accelerates the training process. Experiments driven by real-world network traces demonstrate that the DD-JCCGB algorithm improves the long-term average QoI and outperforms baseline schemes.

Federated learning (FL) has emerged as a pivotal paradigm for distributed model training in edge computing (EC), enabling cooperation among numerous Internet of Things devices while safeguarding their data privacy. Despite its successes in machine learning, concerns regarding data security and model fidelity necessitate the efficient unlearning of target device, i.e., federated unlearning (FUN). However, due to resource constraints, device heterogeneity, and non-independent and identically distributed (Non-IID) data, securely eliminating a device’s impact without retraining the model from scratch presents a complex challenge. In response to these challenges, we propose a hierarchical FUN framework, called Hier-FUN. Hier-FUN organizes edge devices into K clusters, each managed by a head device responsible for aggregating local models within the cluster. To expedite both the learning and unlearning processes of Hier-FUN, we design a heuristic algorithm to determine an appropriate value for K based on devices’ data distributions and available resources. In addition, Hier-FUN denies the communication between the server and cluster heads during training, which can constrain the influence sphere of target device and accelerate the unlearning process. We conduct extensive experiments using real-world datasets, and the experimental results illustrate that Hier-FUN can improve test accuracy by 3.19% during the learning phase and achieve a$6.8\times $speedup during unlearning compared with the baseline methods.

Decentralized federated learning (DFL) is a promising technique to enable distributed machine learning over edge nodes without relying on a centralized parameter server. However, existing DFL network topologies, such as fully connected, partially connected, or lower-tier hierarchical topology often struggle to effectively address the unique challenges presented by edge networks, including edge heterogeneity, communication resource constraint, and data Non-IID. In order to tackle these challenges, we propose a data-aware clustering algorithm, called FRACTAL, to construct a multi-tier hierarchical topology in a bottomup manner taking into consideration both data distribution and communication efficiency for DFL. We theoretically explore the quantitative relationship between the convergence bound of multi-tier FL and the data distribution among each-tier servers. To further improve communication efficiency and address edge heterogeneity, we deploy a time-sharing communication scheduling algorithm within each fractal unit (the basic structure in FRACTAL consisting of multiple nodes and an aggregator), called magic mirror method (MMM), to determine the optimal order of model distributing and uploading for nodes. We conduct extensive experiments on the classical models and datasets to evaluate the performance of FRACTAL, and the results show that FRACTAL can significantly accelerate the DFL model training by 48.6%- 72.3% compared with the state-of-the-art solutions.

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.

Federated learning (FL) is an efficient distributed learning method that facilitates collaborative model training among multiple edge devices (or clients). However, current research always assumes that clients have access to ground-truth data for training, which is unrealistic in practice because of a lack of expertise. Semi-supervised federated learning (SSFL) has been proposed in many existing works to address this problem, which always adopts a fixed model architecture for training, bringing two main problems with varying amounts of pseudo-labeled data. First, the shallow model cannot have the capability to fit the increasing pseudo-labeled data, leading to poor training performance. Second, the large model suffers from an overfitting problem when exploiting a few labeled data samples in SSFL, and also requires tremendous resource (e.g., computation and communication) costs. To tackle these problems, we propose a novel framework, calledstar, which adopts progressive training to enhance model training in SSFL. Specifically,stargradually increases the model depth through adding the sub-module (e.g., one or several layers) from a shallow model, and performs pseudo-labeling for unlabeled data with a specialized confidence threshold simultaneously. Then, we propose an efficient algorithm to determine the appropriate model depth for each client with varied resource budgets and the proper confidence threshold for pseudo-labeling in SSFL. The experimental results demonstrate the high effectiveness of STAR. For instance,starcan reduce the bandwidth consumption by about 40%, and achieve an average accuracy improvement of around 9.8% compared with the baselines, on CIFAR10.

Federated fine-tuning (FedFT) has been proposed to fine-tune the pre-trained language models in a distributed manner. However, there are two critical challenges for efficient FedFT in practical applications,i.e., resource constraints and system heterogeneity. Existing works rely on parameter-efficient fine-tuning methods,e.g., low-rank adaptation (LoRA), but with major limitations. Herein, based on the inherent characteristics of FedFT, we observe that LoRA layers with higher ranks added close to the output help to save resource consumption while achieving comparable fine-tuning performance. Then we propose a novel LoRA-based FedFT framework, termed LEGEND, which faces the difficulty of determining the number of LoRA layers (called, LoRA depth) and the rank of each LoRA layer (called, rank distribution). We analyze the coupled relationship between LoRA depth and rank distribution, and design an efficient LoRA configuration algorithm for heterogeneous devices, thereby promoting fine-tuning efficiency. Extensive experiments are conducted on a physical platform with 80 commercial devices. The results show that LEGEND can achieve a speedup of 1.5-2.8× and save communication costs by about 42.3% when achieving the target accuracy, compared to the advanced solutions.

Federated graph learning (FGL) has been proposed to collaboratively train the increasing graph data with graph neural networks (GNNs) in a recommendation system. Nevertheless, implementing an efficient recommendation system with FGL still faces two primary challenges, i.e., limited communication bandwidth and non-IID local graph data. Existing works typically reduce communication frequency or transmission amount, which may suffer significant performance degradation under non-IID settings. Furthermore, some researchers propose to share the underlying structure among clients, which brings massive communication cost. To this end, we propose an efficient FGL framework, named FedACS, which adaptively selects a subset of clients for model training, to alleviate communication overhead and non-IID issues simultaneously. In FedACS, the global GNN model learns significant hidden edges and the structure of graph data among selected clients, enhancing recommendation efficiency. This capability distinguishes it from the traditional FL client selection methods. To optimize the client selection process, we introduce a multi-armed bandit (MAB) based algorithm to select participating clients according to the resource budgets and the training performance (i.e., RMSE). Experimental results indicate that FedACS improves RMSE by 5.4% over baselines with the same resource budget and reduces communication costs by up to 70.7% to achieve the same RMSE performance.

Service function chain (SFC) consists of multiple ordered network functions (e.g., firewall, load balancer) and plays an important role in improving network security and ensuring network performance. Offloading SFCs onto programmable switches can bring significant performance improvement, but it suffers from unbearable reconfiguration delays, making it hard to cope with network workload dynamics in a timely manner. To bridge the gap, this paper presents OptRec, an efficient SFC proactive reconfiguration optimization framework based on deep reinforcement learning (DRL). OptRec predicts future traffic and places SFCs on programmable switches in advance to ensure the timeliness of the SFC reconfiguration, which is a proactive approach. However, it is non-trivial to extract effective features from historical traffic information and global network states, while ensuring efficient and stable model training. To this end, OptRec introduces a multi-level feature extraction model for different types of features. Additionally, it combines reinforcement learning and autoregressive learning to enhance model efficiency and stability. Results of in-depth simulations based on real-world datasets show the average prediction error of OptRec is less than 3 can increase the system throughput by up to 69.6 compared with other alternatives.

To provide a flexible tradeoff between inference accuracy and resource requirement at runtime, the slimmable neural network (SNN), a single network executable at different widths with the same deploying and management cost as that of a single model, has been proposed. However, how to effectively train SNN among massive devices in edge computing without revealing their local data remains an open problem. To this end, we leverage a novel distributed machine learning paradigm, i.e., federated learning, to realize effective on-device SNN training. As current FL schemes often train only one model with fixed architecture, and the existing SNN training algorithm is resource-intensive, integrating FL and SNN is non-trivial. Furthermore, two intrinsic features in edge computing, i.e., data and system heterogeneity, exacerbate the difficulty. Motivated by this, we redesign the model distribution, local training, and model aggregation phases in traditional FL, and propose FedSNN, a framework that ensures all widths in SNN can obtain high accuracy with less resource consumption. Specifically, for devices with heterogeneous training capacities and data distributions, the parameter server will distribute each of them with one proper width for adaptive local training guided by their uploaded model features, and their trained models will be weighted-averaged using the proposed multi-width SNN aggregation to improve their statistical utility. Extensive experiments on a distributed testbed show that FedSNN improves the model accuracy by about 2.18%-8.1%, and accelerates training by about$1.31\times $-$6.84\times $, compared with existing solutions.

Federated Learning (FL) enables distributed clients to collaboratively train models without exposing their private data. However, it is difficult to implement efficient FL due to limited resources. Most existing works compress the transmitted gradients or prune the global model to reduce the resource cost, but leave the compressed or pruned parameters under-optimized, which degrades the training performance. To address this issue, the neural composition technique constructs size-adjustable models by composing low-rank tensors, allowing every parameter in the global model to learn the knowledge from all clients. Nevertheless, some tensors can only be optimized by a small fraction of clients, thus the global model may get insufficient training, leading to a long completion time, especially in heterogeneous edge scenarios. To this end, we enhance the neural composition technique, enabling all parameters to be fully trained. Further, we propose a lightweight FL framework, called Heroes, with enhanced neural composition and adaptive local update. A greedy-based algorithm is designed to adaptively assign the proper tensors and local update frequencies for participating clients according to their heterogeneous capabilities and resource budgets. On this basis, we further propose an extension of Heroes, termed AdaHeroes, which further improves the training performance under the statistical heterogeneity scenario based on an adaptive client selection strategy. Extensive experiments demonstrate that Heroes can reduce traffic consumption by about 72.46% and provide up to$2.76\times $speedup compared to the baselines. Furthermore, with the setting of statistical heterogeneity, AdaHeroes can improve the test accuracy by about 4.77% compared with Heroes and the baselines.

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.

Federated learning (FL) has recently gained tremendous attention in edge computing and the Internet of Things, due to its capability of enabling clients to perform model training at the network edge or end devices (i.e., clients). However, these end devices are usually resource-constrained without the ability to train large-scale models. In order to accelerate the training of large-scale models on these devices, we incorporate Split Learning (SL) into Federated Learning (FL), and propose a novel FL framework, termedPairingFL. Specifically, we split a full model into a bottom model and a top model, and arrange participating clients into pairs, each of which collaboratively trains the two partial models as one client does in typical FL. Driven by the advantages of SL and FL, PairingFL is able to relax the computation burden on clients and protect model privacy. However, considering the features of system and statistical heterogeneity in edge networks, it is challenging to pair the clients by carefully developing the strategies of client partitioning and matching for efficient model training. To this end, we first theoretically analyze the convergence property of PairingFL, and obtain a convergence upper bound. Guided by this, we then design a greedy and efficient algorithm, which makes the joint decision of client partitioning and matching, so as to well balance the trade-off between convergence rate and model accuracy. The performance of PairingFL is evaluated through extensive simulation experiments. The experimental results demonstrate that PairingFL can speed up the training process by$4.6\times $compared to baselines when achieving the corresponding convergence accuracy.

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.

Nowadays, federated learning (FL) has been widely adopted to train deep neural networks (DNNs) among massive devices without revealing their local data in edge computing (EC). To relieve the communication bottleneck of the central server in FL, hierarchical federated learning (HFL), which leverages edge servers as intermediaries to perform model aggregation among devices in proximity, comes into being. Nevertheless, the existing HFL systems may not perform training effectively due to bandwidth constraints and non-IID issues on devices. To conquer these challenges, we introduce anHFL system with device-edgeassignment andlayer selection, namely Heal. Specifically, Heal organizes all the devices into a hierarchical structure (i.e., device-edge assignment) and enables each device to forward only a sub-model with several valuable layers for aggregation (i.e., layer selection). This processing procedure is called layer-wise aggregation. To further save communication resource and improve the convergence performance, we then design an iteration-based algorithm to optimize the development of our layer-wise aggregation strategy by considering the data distribution as well as resource constraints among devices. Extensive experiments on both the physical platform and the simulated environment show that Heal accelerates DNN training by about 1.4–12.5×, and reduces the network traffic consumption by about 31.9–64.1%, compared with the existing HFL systems.

Federated learning (FL) has gained Important attention for training deep learning models across clients in edge computing. The scarcity of labeled data poses critical challenges in professional fields (e.g., medical diagnosis) for FL, motivating the development of federated semi-supervised learning (FSSL) to exploit unlabeled data. The existing works of FSSL always assign fixed values for global updating frequency and/or local updating frequency during training. Though the previous works can make full use of unlabeled data, they may still hinder the improvement of model performance on heterogeneous clients, due to that the two hyper-parameters are coupled and have a joint impact on training process. To this end, we propose a novel FSSL framework, named LOGO, to enhance training efficiency by jointly optimizing local and global updating frequencies. We analyze the coupled impact of these two hyper-parameters on model training. Then, we develop a multi-armed bandit (MAB) based online algorithm to adaptively determine diverse local updating frequencies for heterogeneous clients as well as appropriate global updating frequency, so as to address system heterogeneity and improve training efficiency. The performance of LOGO is evaluated through extensive simulation experiments. The experimental results demonstrate that LOGO achieves the model training speedup by 2.3 × and reduces communication cost by 44%, compared to the baselines.

Service function chain (SFC) consists of multiple ordered network functions (e.g., firewall, load balancer) and plays an important role in improving network security and ensuring network performance. Offloading SFCs onto programmable switches can bring significant performance improvement, but it suffers from unbearable reconfiguration delays, making it hard to cope with network workload dynamics in a timely manner. To bridge the gap, this paper presents OptRec, an efficient SFC reconfiguration optimization framework based on deep reinforcement learning (DRL). OptRec predicts future traffic and places SFCs on programmable switches in advance to ensure the timeliness of the SFC reconfiguration, which is a proactive approach. However, it is non-trivial to extract effective features from historical traffic information and ensure efficient and stable model training. To this end, OptRec introduces a multi-level feature extraction model for different types of features. Additionally, it combines reinforcement learning and autoregressive learning to enhance model efficiency and stability. Results of in-depth simulations based on real-world datasets show the average prediction error of OptRec is less than 3% and OptRec can increase the system throughput by up to 69.6%~72.6% compared with other alternatives.

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.

Federated learning (FL) provides a distributed framework for multiple clients to collaboratively train models without exposing raw data. Most FL research assumes that all clients have fully labeled data, which is impractical for many real-world applications. To this end, we focus on semi-supervised FL (SSFL), where data samples of each client are partially labeled. However, existing SSFL methods ignore two inherent characteristics of FL: limited communication resources and heterogeneous data distribution, which severely hinder convergence stability and efficiency. This paper proposes a novel SSFL mechanism, called FedAC, to address the above two challenges by alternating client-to-client (C2C) collaboration. Specifically, we group all clients using different clustering strategies at two different training stages. During each global round, FedAC first performs similarity clustering based on local data distribution, which gathers the knowledge from similar clients to generate high-quality pseudo-labels for unlabeled data. Then the clients are re-grouped using dissimilarity clustering strategy to approximate the IID setting at the cluster level, thereby alleviating the bias induced by Non-IID data. FedAC adopts a reinforcement learning algorithm to achieve a balance between labeling assistance from similar clients and unbiased optimization from dissimilar clients. Extensive evaluations demonstrate that FedAC can improve model accuracy and save up to 59.65% of communication costs compared with existing benchmarks.

Recently, federated learning (FL) has emerged as a popular technique for edge AI to mine valuable knowledge in edge computing (EC) systems. To boost the performance of AI applications, large-scale models have received increasing attention due to their excellent generalized abilities. However, training and transmitting large-scale models will incur significant computing and communication burden on the resource-constrained workers, and the exchange of entire models may violate model privacy. To relax the burden of workers and protect model privacy, split federated learning (SFL) has been released by integrating both data and model parallelism. Despite resource limitations, SFL also faces two other critical challenges in EC systems, i.e., statistical heterogeneity and system heterogeneity. In order to address these challenges, we propose a novel SFL framework, termed MergeSFL, by incorporating feature merging and batch size regulation in SFL. Concretely, feature merging aims to merge the features from workers into a mixed feature sequence, which is approximately equivalent to the features derived from IID data and is employed to promote model accuracy. While batch size regulation aims to assign diverse and suitable batch sizes for heterogeneous workers to improve training efficiency. Moreover, MergeSFL explores to jointly optimize these two strategies upon their coupled relationship to better enhance the performance of SFL. Extensive experiments are conducted on a physical platform with 80 NVIDIA Jetson edge devices, and the experimental results show that MergeSFL can improve the final model accuracy by 5.82% to 26.22%, with a speedup by about 1.39x to 4.14x, compared to the baselines.

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.

Recently, Hierarchical Federated Learning (HFL) stands out as a cutting-edge approach to efficiently learn knowledge from massive data on edge devices or clients. To alleviate the computation/communication burden of training large-scale models on resource-constrained clients, Hierarchical Split Federated Learning (HSFL), which splits an entire model into a top and bottom (sub-)model and offloads the training of the top model to the edge server, has been proposed. Nonetheless, there are two key issues, i.e., system heterogeneity and dynamic contexts, hindering the application of effective HSFL. In response, we present an efficient HSFL method, termed AdaHSFL, which introduces intra-cluster gradient feedback regulation and inter-cluster updating frequencies optimization to enhance training efficiency. Concretely, intra-cluster gradient feedback regulation enables edge servers to instantly process incoming smashed data and calculate gradients using top model copies on background threads, while inter-cluster updating frequencies optimization adjusts edge cluster updating frequencies to align the training duration across all clusters with that of the fastest cluster. Furthermore, AdaHSFL explores to jointly implement these two strategies to eliminate the idle waiting time both intra- and intercluster incurred by synchronization barriers. Rigorous performance evaluation demonstrates that AdaHSFL can improve the accuracy by $3.9 \%-25.5 \%$ within given time budgets, compared with the baselines.

Federated Learning (FL) enables distributed clients to collaboratively train models without exposing their private data. However, it is difficult to implement efficient FL due to limited resources. Most existing works compress the transmitted gradients or prune the global model to reduce the resource cost, but leave the compressed or pruned parameters under-optimized, which degrades the training performance. To address this issue, the neural composition technique constructs size-adjustable models by composing low-rank tensors, allowing every parameter in the global model to learn the knowledge from all clients. Nevertheless, some tensors can only be optimized by a small fraction of clients, thus the global model may get insufficient training, leading to a long completion time, especially in heterogeneous edge scenarios. To this end, we enhance the neural composition technique, enabling all parameters to be fully trained. Further, we propose a lightweight FL framework, called Heroes, with enhanced neural composition and adaptive local update. A greedy-based algorithm is designed to adaptively assign the proper tensors and local update frequencies for participating clients according to their heterogeneous capabilities and resource budgets. Extensive experiments demonstrate that Heroes can reduce traffic consumption by about 72.05% and provide up to 2.97× speedup compared to the baselines.

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.

Federated graph learning (FGL) has been proposed to collaboratively train the increasing graph data with graph neural networks (GNNs) in a recommendation system, aggregating the features of graph nodes and edges among these nodes. Nevertheless, implementing an efficient recommendation system with FGL still faces two primary challenges, i.e., limited communication bandwidth and non-IID local graph data. Existing works typically reduce communication frequency or transmission amount, which may suffer significant performance degradation under non-IID settings. Furthermore, some researchers propose to share the underlying structure information among all clients, which brings massive communication cost. To this end, we propose an efficient FGL framework, named FedACS, which adaptively selects a subset of clients for model training, to alleviate communication overhead and non-IID issues simultaneously. In FedACS, the global GNN model can learn significant hidden edges and the structure of graph data among selected clients, enhancing recommendation efficiency. This capability distinguishes it from the traditional FL client selection methods. To optimize the client selection process, we introduce a multi-armed bandit (MAB) based algorithm to select participating clients according to the resource budgets and the training performance (i.e., RMSE) under different data distributions. Experimental results show that, given the same resource budget, FedACS achieves the RMSE improvement of 5.4% over the baselines. Besides, when achieving the same RMSE performance, FedACS saves up to approximately 70.7% communication cost, compared with the baselines.

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

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.

Mobile devices contribute more than half of the world's web traffic, providing massive and diverse data for powering various federated learning (FL) applications. In order to avoid the communication bottleneck on the parameter server (PS) and accelerate the training of large-scale models on resource-constraint workers in edge computing (EC) system, we propose a novel split federated learning (SFL) framework, termed ParallelSFL. Concretely, we split an entire model into a bottom submodel and a top submodel, and divide participating workers into multiple clusters, each of which collaboratively performs the SFL training procedure and exchanges entire models with the PS. However, considering the statistical and system heterogeneity in edge systems, it is challenging to arrange suitable workers to specific clusters for efficient model training. To address these challenges, we carefully develop an effective clustering strategy by optimizing a utility function related to training efficiency and model accuracy. Specifically, ParallelSFL partitions workers into different clusters under the heterogeneity restrictions, thereby promoting model accuracy as well as training efficiency. Meanwhile, ParallelSFL assigns diverse and appropriate local updating frequencies for each cluster to further address system heterogeneity. Extensive experiments are conducted on a physical platform with 80 NVIDIA Jetson devices, and the experimental results show that ParallelSFL can reduce the traffic consumption by at least 21%, speed up the model training by at least 1.36X, and improve model accuracy by at least 5% in heterogeneous scenarios, compared to the baselines.

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.

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

The emerging Federated Learning (FL) permits all workers (e.g., mobile devices) to cooperatively train a model using their local data at the network edge. In order to avoid the possible bottleneck of conventional parameter server architecture, the decentralized federated learning (DFL) is developed on the peer-to-peer (P2P) communication. In DFL, model exchanging among workers is usually regarded as an atomic operation, which largely affects the total bandwidth consumption during model training. Given the limited communication resource on workers, model exchanging will pose a great challenge when meeting with the large-scale models. Herein, we propose to let workers exchange theintermediate results, instead of the entire model, with each other. We provide theoretical analysis of DFL based on intermediate result exchanging, which reveals the relationship between the training performance and the exchanging interval (i.e., the number of local updating iterations) of intermediate results. According to the convergence bound, we propose an adaptive exchanging interval (or frequency) algorithm called Fed-IR, which optimizes the trade-off between communication cost and training performance. Extensive simulation results show that compared with the model exchanging methods, our proposed algorithms can save communication traffic of around 42%$\sim$81% while still achieving the similar accuracy.

The emerging Federated Learning (FL) permits all workers (e.g., mobile devices) to cooperatively train a model using their local data at the network edge. In order to avoid the possible bottleneck of conventional parameter server architecture, the decentralized federated learning (DFL) is developed on the peer-to-peer (P2P) communication. Non-IID issue is a key challenge in FL and will significantly degrade the model training performance. To this end, we propose a personalized solution called TOPFL, in which only parts of the local models (not the entire models) are shared and aggregated. Moreover, considering the limited communication bandwidth on workers, we propose a topology construction algorithm to accelerate the training process. To verify the convergence of the decentralized training framework, we theoretically analyze the impact of the data heterogeneity and topology on the convergence upper bound. Extensive simulation results show that TOPFL can achieve 2.2× speedup when reaching convergence and 5.8% higher test accuracy under the same resource consumption, compared with the baseline solutions.

The massive data from mobile and embedded devices have huge potential for training machine learning models. Decentralized machine learning (DML) can avoid the inherent bottleneck of the parameter server (PS) by collaboratively training models in a device-to-device (D2D) fashion. However, the previous DML works often assume that the local data are fully annotated with ground-truth labels, which is unrealistic for many Internet of Things (IoT) applications. This arises a new practical DML scenario, namely semi-supervised DML, where the local data of distributed workers are partially labeled in the D2D network. The existing semi-supervised learning techniques are proposed for standalone or the PS architecture, which ignore the impact of D2D topology on the performance of semi-supervised learning. Thus, they cannot adequately leverage the unlabeled data of decentralized workers, leading to performance degradation. Herein, we propose a novel framework, called SSD, to address the problem of semi-supervised DML by exploiting D2D cooperation. The key insight behind SSD is that neighbor selection has a crucial impact on pseudo-label quality and communication overhead. In SSD, each worker adaptively selects its neighbors with high-quality models and similar data distribution under communication resource constraints, which helps to generate high-confidence pseudo-labels for local unlabeled data and further boosts the DML performance. Extensive empirical evaluations on both testbed and simulated environments show that SSD significantly outperforms other baselines.

Federated learning (FL) has emerged as a promising distributed learning paradigm that enables a large number of mobile devices to cooperatively train a model without sharing their raw data. The iterative training process of FL incurs considerable computation and communication overhead. The workers participating in FL are usually heterogeneous and the workers with poor capabilities may become the bottleneck of model training. To address the challenges of resource overhead and system heterogeneity, this article proposes an efficient FL framework, called FedMP, that improves both computation and communication efficiency over heterogeneous workers through adaptive model pruning. We theoretically analyze the impact of pruning ratio on training performance, and employ a Multi-Armed Bandit based online learning algorithm to adaptively determine different pruning ratios for heterogeneous workers, even without any prior knowledge of their capabilities. As a result, each worker in FedMP can train and transmit the sub-model that fits its own capabilities, accelerating the training process without hurting model 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). Besides, our proposed framework can be extended to the peer-to-peer (P2P) setting. Extensive experiments on physical devices 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.

Data generated at the network edge can be processed locally by leveraging the paradigm of edge computing (EC). Aided by EC, decentralized federated learning (DFL), which overcomes the single-point-of-failure problem in the parameter server based federated learning, is becoming a practical and popular approach for machine learning over distributed data. However, DFL faces two critical challenges,i.e., system heterogeneity and statistical heterogeneity introduced by edge devices. To ensure fast convergence with the existence of slow edge devices, we present an efficient DFL method, termed FedHP, which integrates adaptive control of both local updating frequency and network topology to better support the heterogeneous participants. We establish a theoretical relationship between local updating frequency and network topology regarding model training performance and obtain a convergence upper bound. Upon the convergence bound, we propose an optimization algorithm that adaptively determines local updating frequencies and constructs the network topology, so as to speed up convergence and improve the model accuracy. We evaluate the performance of FedHP through extensive simulation and testbed experiments. Evaluation results show that the proposed FedHP can reduce the completion time by about 51% and improve model accuracy by at least 5% in heterogeneous scenarios, compared with the baselines.

Federated learning (FL) has been widely adopted to train machine learning models over massive data in edge computing. Most works of FL employ pre-defined model architectures on all participating clients for model training. However, these pre-defined architectures may not be the optimal choice for the FL setting since manually designing a high-performance neural architecture is complicated and burdensome with intense human expertise and effort, which easily makes the model training fall into the local suboptimal solution. To this end, Neural Architecture Search (NAS) has been applied to FL to address this critical issue. Unfortunately, the search space of existing federated NAS approaches is extraordinarily large, resulting in unacceptable completion time on the resource-constrained edge clients, especially under the non-independent and identically distributed (non-IID) setting. In order to remedy this, we propose a novel framework, calledFinch, which adopts hierarchical neural architecture search to enhance federated learning. InFinch, we first divide the clients into several clusters according to the data distribution. Then, some subnets are sampled from a pre-trained supernet and allocated to the specific client clusters for searching the optimal model architecture in parallel, so as to significantly accelerate the process of model searching and training. The extensive experimental results demonstrate the high effectiveness of our proposed framework. Specifically,Finchcan reduce the completion time by about 30.6%, and achieve an average accuracy improvement of around 9.8% compared with the baselines.

Federated learning (FL) is an effective approach to train models collaboratively among distributed edge nodes (i.e., workers) while facing three crucial challenges, edge heterogeneity, resource constraint, and Non-IID data. Under the parameter server (PS) architecture, a single parameter server may become the system bottleneck and cannot well deal with the edge heterogeneity, while the peer-to-peer (P2P) architecture causes significant communication consumption to achieve satisfactory training performance. To this end, hierarchical aggregation (HA) architecture is proposed to cluster workers to tackle the edge heterogeneity and reduce communication consumption for FL. However, the existing researches on HA architecture cannot provide a unified clustering approach for various inter-cluster aggregation patterns (e.g., centralized or decentralized structure, synchronous or asynchronous mode). In this paper, we explore the quantitative relationship between the convergence bounds of different inter-cluster patterns and several factors, e.g., data distribution, frequency of clusters participating in inter-cluster aggregation (for asynchronous modes), and inter-cluster topology (for decentralized structures). Based on the convergence bounds, we design a unified clustering algorithm FedUC to organize workers for different patterns. Experimental results on classical models and datasets show that FedUC can greatly accelerate the model training of different patterns by 1.79-7.39× compared with the state-of-the-art clustering methods.

The emerging Personalized Federated Learning (PFL) methods aim to produce personalized models for different users, so as to keep track of their individualized requirements in Edge Computing (EC). The centralized PFL methods may suffer from the communication bottleneck and single point of failure. As an alternative solution, the decentralized PFL (DPFL) methods are performed in a Peer-to-Peer (P2P) manner, and collaboratively train personalized models by model aggregation among congenial devices. However, these DPFL methods may incur high communication cost and low resource utilization induced by large-scale models. Herein, we take the communication constraint and heterogeneity into consideration and propose to realize communication-efficient DPFL with adaptive model pruning and neighbor selection. We theoretically analyze the convergence of the proposed DPFL method, and study the impacts of both model pruning and neighbor selection on training performance. Furthermore, we propose an efficient algorithm that combines model pruning and neighbor selection to achieve a trade-off between model quality and communication cost. Extensive simulation and testbed experiments on real-world datasets are conducted. The experimental results demonstrate that the proposed algorithm can improve the test accuracy by at most 13% and save the traffic consumption by 45.4% on average compared with the existing PFL methods.

Federated learning (FL) has recently gained tremendous attention in edge computing and Internet of Things, due to its capability of enabling distributed clients to cooperatively train models while keeping raw data locally. However, the existing works usually suffer from limited communication resources, dynamic network conditions and heterogeneous client properties, which hinder efficient FL. To simultaneously tackle the above challenges, we propose a heterogeneity-aware FL framework, called FedCG, with adaptive client selection and gradient compression. Specifically, FedCG introduces diversity to client selection and aims to select a representative client subset considering statistical heterogeneity. These selected clients are assigned different compression ratios based on heterogeneous and time-varying capabilities. After local training, they upload sparse model updates matching their capabilities for global aggregation, which can effectively reduce the communication cost and mitigate the straggler effect. More importantly, instead of naively combining client selection and gradient compression, we highlight that their decisions are tightly coupled and indicate the necessity of joint optimization. We theoretically analyze the impact of both client selection and gradient compression on convergence performance. Guided by the convergence rate, we develop an iteration-based algorithm to jointly optimize client selection and compression ratio decision using submodular maximization and linear programming. On this basis, we propose the quantized extension of FedCG, termed Q-FedCG, which further adjusts quantization levels based on gradient innovation. Extensive experiments on both real-world prototypes and simulations show that FedCG and its extension can provide up to 6.4× speedup.

Federated learning (FL) enables edge devices to cooperatively train models without exposing their raw data. However, implementing a practical FL system at the network edge mainly faces three challenges: label noise, data non-IIDness, and device heterogeneity, which seriously harm model performance and slow down convergence speed. Unfortunately, none of the existing works tackle all three challenges simultaneously. To this end, we develop a novel FL system, called Aorta, which features adaptive dataset construction and aggregation weightassignment. On each client, Aorta first calibrates potentially noisy labels and then constructs a training dataset with low noise, balanced distribution, and proper size. To fully utilize limited data on clients, we propose a global model guided method to select clean data and progressively correct noisy labels. To achieve balanced class distribution and proper dataset size, we propose a distribution-and-capability-aware data augmentation method to generate local training data. On the server, Aorta assigns aggregation weights based on the quality of local models to ensure that high-quality models have a greater influence on the global model. The model quality is measured through its cosine similarity with a benchmark model, which is trained on a clean and balanced dataset. We conduct extensive experiments on four datasets with various settings, including different noise types/ratios and non-IID types/levels. Compared to the baselines, Aorta improves model accuracy up to 9.8% on the datasets with moderate noise and non-IIDness, while providing a speedup of 4.2× on average when achieving the same target accuracy.

Federated Learning (FL) has been widely adopted to process the enormous data in the application scenarios like Edge Computing (EC). However, the commonly-used synchronous mechanism in FL may incur unacceptable waiting time for heterogeneous devices, leading to a great strain on the devices' constrained resources. In addition, the alternative asynchronous FL is known to suffer from the model staleness, which will lead to performance degradation of the trained model, especially onnon-i.i.d.data. In this paper, we design a novel asynchronous FL mechanism, named FedLC, to handle thenon-i.i.d.issue in EC by enabling the local collaboration among edge devices. Specifically, apart from uploading the local model directly to the server, each device will transmit its gradient to the other devices with different data distributions for local collaboration, which can improve the model generality. We theoretically analyze the convergence rate of FedLC and obtain the quantitative relationship between convergence bound and local collaboration. We design an efficient algorithm utilizing demand-list to determine the set of devices receiving gradients from each device. To handle the model staleness, we further assign different learning rates for various devices according to their participation frequency. The extensive experimental results demonstrate the effectiveness of our proposed mechanism.

Federated learning (FL) has been widely applied to collaboratively train deep learning (DL) models on massive end devices (i.e., clients). Due to the limited storage capacity and high labeling cost, the data on each client may be insufficient for model training. Conversely, in cloud datacenters, there exist large-scale unlabeled data, which are easy to collect from public access (e.g., social media). Herein, we propose theAda-FedSemisystem, which leverages both on-device labeled data and in-cloud unlabeled data to boost the performance of DL models. In each round, local models are aggregated to produce pseudo-labels for the unlabeled data, which are utilized to enhance the global model. Considering that the number of participating clients and the quality of pseudo-labels will have a significant impact on the training performance, we introduce a multi-armed bandit (MAB) based online algorithm to adaptively determine the participating fraction and confidence threshold. Besides, to alleviate the impact of stragglers, we assign local models of different depths for heterogeneous clients. Extensive experiments on benchmark models and datasets show that given the same resource budget, the model trained by Ada-FedSemi achieves 3%$\sim$14.8% higher test accuracy than that of the baseline methods. When achieving the same test accuracy, Ada-FedSemi saves up to 48% training cost, compared with the baselines. Under the scenario with heterogeneous clients, the proposed HeteroAda-FedSemi can further speed up the training process by$1.3\times \sim 1.5\times$.

In edge computing (EC), federated learning (FL) enables numerous distributed devices (or workers) to collaboratively train AI models without exposing their local data. Most works of FL adopt a predefined architecture on all participating workers for model training. However, since workers' local data distributions vary heavily in EC, the predefined architecture may not be the optimal choice for every worker. It is also unrealistic to manually design a high-performance architecture for each worker, which requires intense human expertise and effort. In order to tackle this challenge, neural architecture search (NAS) has been applied in FL to automate the architecture design process. Unfortunately, the existing federated NAS frameworks often suffer from the difficulties of system heterogeneity and resource limitation. To remedy this problem, we present a novel framework, termedPeaches, to achieve efficient searching and training in the resource-constrained EC system. Specifically, the local model of each worker is stacked by base cell and personal cell, where the base cell is shared by all workers to capture the common knowledge and the personal cell is customized for each worker to fit the local data. We determine the number of base cells, shared by all workers, according to the bandwidth budget on the parameters server. Besides, to relieve the data and system heterogeneity, we find the optimal number of personal cells for each worker based on its computing capability. In addition, we gradually prune the search space during training to mitigate the resource consumption. We evaluate the performance ofPeachesthrough extensive experiments, and the results show thatPeachescan achieve an average accuracy improvement of about 6.29% and up to 3.97× speed up compared with the baselines.

Federated semi-supervised learning (FSSL) has been proposed to address the insufficient labeled data problem by training models with pseudo-labeling. In previous FSSL systems, a single global model is always trained without an equivalent generalization ability for the clients under the non-IID setting. Accordingly, model personalization methods have been proposed to overcome this problem. Intuitively, seeking labeling assistance from other clients with similar data distribution,i.e., model migration, can effectively improve the personalization on the clients with scarce labeled data. However, previous works require to migrate a pre-fixed number of models among the clients, causing unnecessary resource waste and accuracy degradation due to resource heterogeneity. Considering that the number of model migrations and the quality of pseudo-labels have a significant impact on the training performance (e.g., efficiency and accuracy), we propose a novel personalized FSSL system, called Ferrari, to boost the efficiency of pseudo-labeling and training accuracy through adaptive model migrations among the clients. Specifically, Ferrari first generates the similarity-based ranking using a Gaussian KD-Tree, considering the varied data distributions among the clients. Combined with the ranking and clients' heterogeneous resource constraints, Ferrari then adaptively determines the proper model migration policy and confidence thresholds for high-quality pseudo-labeling and personalized training for clients. Extensive experiments on a physical platform show that Ferrari provides a 1.2$\sim 5.5\times$speedup without sacrificing model accuracy, compared to existing methods.

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.

Data generated at the network edge can be processed locally by leveraging the emerging technology of Federated Learning (FL). However, non-IID local data will lead to degradation of model accuracy and the heterogeneity of edge nodes inevitably slows down model training efficiency. Moreover, to avoid the potential communication bottleneck in the parameter-server-based FL, we concentrate on the Decentralized Federated Learning (DFL) that performs distributed model training in Peer-to-Peer (P2P) manner. To address these challenges, we propose an asynchronous DFL system by incorporating neighbor selection and gradient push, termed AsyDFL. Specifically, we require each edge node to push gradients only to a subset of neighbors for resource efficiency. Herein, we first give a theoretical convergence analysis of AsyDFL under the complicated non-IID and heterogeneous scenario, and further design a priority-based algorithm to dynamically select neighbors for each edge node so as to achieve the trade-off between communication cost and model performance. We evaluate the performance of AsyDFL through extensive experiments on a physical platform with 30 NVIDIA Jetson edge devices. Evaluation results show that AsyDFL can reduce the communication cost by 57% and the completion time by about 35% for achieving the same test accuracy, and improve model accuracy by at least 6% under the non-IID scenario, compared to the baselines.

Recently, edge AI has been launched to mine and discover valuable knowledge at network edge. Federated Learning, as an emerging technique for edge AI, has been widely deployed to collaboratively train models on many end devices in data-parallel fashion. To alleviate the computation/communication burden on the resource-constrained workers (e.g., end devices) and protect user privacy, Spilt Federated Learning (SFL), which integrates both data parallelism and model parallelism in Edge Computing (EC), is becoming a practical and popular approach for model training over distributed data. However, apart from the resource limitation, SFL still faces two other critical challenges in EC, i.e., system heterogeneity and context dynamics. To overcome these challenges, we present an efficient SFL method, named AdaSFL, which controls both local updating frequency and batch size to better accelerate model training. We theoretically analyze the model convergence rate and obtain a convergence upper bound regarding local updating frequency given a fixed batch size. Upon this, we develop a control algorithm to determine adaptive local updating frequency and diverse batch sizes for heterogeneous workers to enhance the training efficiency. The experimental results show that AdaSFL can reduce the completion time by about 43% and the network traffic consumption by about 31% for achieving the similar test accuracy, compared to the baselines.

Traditional Federated Learning (FL) is a promising paradigm that enables massive edge clients to collaboratively train deep neural network (DNN) models without exposing raw data to the parameter server (PS). To avoid the bottleneck on the PS, Decentralized Federated Learning (DFL), which utilizes peer-to-peer (P2P) communication without maintaining a global model, has been proposed. Nevertheless, DFL still faces two critical challenges, i.e., limited communication bandwidth and not independent and identically distributed (non-IID) local data, thus hindering efficient model training. Existing works commonly assume full model aggregation at periodic intervals, i.e., clients periodically collect models from peers. To reduce the communication cost, these methods allow clients to collect model(s) from selected peers, but often result in a significant degradation of model accuracy when dealing with non-IID data. Alternatively, the layer-wise aggregation mechanism has been proposed to alleviate communication overhead under the PS architecture, but its potential in DFL remains rarely explored yet. To this end, we propose an efficient DFL framework YOGA that adaptively performs layer-wise model aggregation and training. Specifically, YOGA first generates the ranking of layers in the model according to the learning speed and layer-wise divergence. Combining with the layer ranking and peers’ status information (i.e., data distribution and communication capability), we propose the max-match (MM) algorithm to generate the proper layer-wise model aggregation policy for the clients. Extensive experiments on DNN models and datasets show that YOGA saves communication cost by about 45% without sacrificing the model performance compared with the baselines, and provides 1.53-$3.5\times $speedup on the physical platform.

To approach the challenges of non-IID data and limited communication resource raised by the emerging federated learning (FL) in mobile edge computing (MEC), we propose an efficient framework, calledFedMigr, which integrates a deep reinforcement learning (DRL) based model migration strategy into the pioneer FL algorithmFedAvg. According to the data distribution and resource budgets, ourFedMigrwill intelligently guide one client to forward its local model to another client after local updating, before directly sending the local models to the server for global aggregation as inFedAvg. Intuitively, migrating a local model from one client to another is equivalent to training the model over more data from different clients, alleviating the influence of non-IID issue. To this end, we propose an experience-driven method to make proper decisions for model migrations while satisfying the resource constraints. We also prove thatFedMigrcan help to reduce the parameter divergences between different local models and the global model from a theoretical perspective under the non-IID setting. Extensive experiments on three popular benchmark datasets demonstrate thatFedMigrcan achieve an average accuracy improvement of around 13%, and reduce bandwidth consumption for global communication by 42% on average, compared with the baselines.

Federated Learning (FL) is a distributed model training framework that allows multiple clients to collaborate on training a global model without disclosing their local data in edge computing (EC) environments. 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 pioneering FL algorithm FedAvg, for resource-constrained edge computing. Specifically, we first divide the model into multiple blocks according to the layer order of deep neural network (DNN). The server only sends some consecutive model blocks instead of an entire model to clients for communication efficiency. Then, the clients make use of knowledge distillation to absorb the knowledge of global model blocks to alleviate statistical heterogeneity during local training. We provide a theoretical convergence guarantee for FedBR and show that the convergence bound will decrease as the increasing number of model blocks sent by the server. Besides, since the increasing number of model blocks brings more computing and communication costs, 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 bandwidth consumption by about 31%, and achieve an average accuracy improvement of around 5.6% compared with the baselines under heterogeneous settings.

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.

At the network edge, federated learning (FL) has gained attention as a promising approach for training deep learning (DL) models collaboratively across a large number of devices while preserving user privacy. However, FL still faces specific challenges related to the limited, heterogeneous and dynamic resources of devices. In most FL systems, all devices train the same model, while the devices with constrained resources, referred to as stragglers, will significantly slow down overall training process. It is intuitive to alleviate computation and communication load on the stragglers by training and transmitting a part of the model. Inspired by multi-exit models, we divide an original DL model into several non-overlapping blocks, which can be trained separately on the low-capability devices. Furthermore, we propose BOSE, a novel FL system that performs adaptiveblock-wisemodel training under resource constraints. Considering the diverse impacts of different blocks on model convergence and the varying training loads they incur, a naive block assignment strategy, e.g., uniformly random assignment, may not yield optimal model performance and fail to fully utilize available resources. To this end, we introduce two metrics, includinglearning speedanddevice-wise divergence, to measure the potential of blocks in promoting model convergence. Given resource budget, BOSE initially identifies a set of candidate blocks for each device and subsequently selects specific training blocks based on their potential for promoting model convergence. In general, blocks with higher potential are more likely to be chosen for training. Extensive experiments on a physical platform show that BOSE provides a 1.4$\times$$\sim$3.8$\times$speedup without sacrificing model accuracy, compared to the baselines.

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

The emerging paradigm of federated learning (FL) strives to enable devices to cooperatively train models without exposing their raw data. In most cases, the data across devices are non-independently and identically distributed in FL. Thus, the local models trained over different data distributions will inevitably deviate from the global optima, which induces optimization inconsistency and even hurts global convergence. Moreover, the resource-constrained devices with heterogeneous training capacities (e.g., computing and communication) further slow down the convergence rate. To this end, we introduce anFL framework withadaptive datasampling and localtraining, namely FAST. Specifically, even without devices’ private data distributions, FAST enables each device to sample different rates of data points from each of its local classes to rebuild a dataset for training, thus adjusting the convergence direction of the aggregated global model to be closer to the global optima. The theoretical analysis shows that the convergence bound depends on the sampling rates as well as the number of local iterations executed on the sampled data. To achieve resource-effective and convergence-guaranteed FL, we then design an online learning algorithm that jointly optimizes the data sampling and local training strategies so as to encourage the decrease of global loss under the given time budget. Extensive experiments on physical and simulated environments show that, FAST improves the model accuracy by about 1.55%-6.78% given the same time budget, and accelerates training by about 1.39-5.89× with the same target accuracy, compared with the baselines.

Data generated at the network edge can be processed locally by leveraging the emerging technology of Federated Learning (FL). However, non-IID local data will lead to degradation of model accuracy and the heterogeneity of edge nodes inevitably slows down model training efficiency. Moreover, to avoid the potential communication bottleneck in the parameter-server-based FL, we concentrate on the Decentralized Federated Learning (DFL) that performs distributed model training in Peer-to-Peer (P2P) manner. To address these challenges, we propose an asynchronous DFL system by incorporating neighbor selection and gradient push, termed AsyNG. Specifically, we require each edge node to push gradients only to a subset of neighbors for resource efficiency. Herein, we first give a theoretical convergence analysis of AsyNG under the complicated non-IID and heterogeneous scenario, and further design a priority-based algorithm to dynamically select neighbors for each edge node so as to achieve the trade-off between communication cost and model performance. We evaluate the performance of AsyNG through extensive experiments on a physical platform. Evaluation results show that AsyNG can reduce the communication cost by 60% and the completion time by about 30% for achieving the same test accuracy, compared to the baselines.

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.

Federated learning (FL) allows multiple clients cooperatively train models without disclosing local data. However, the existing works fail to address all these practical concerns in FL: limited communication resources, dynamic network conditions and heterogeneous client properties, which slow down the convergence of FL. To tackle the above challenges, we propose a heterogeneity-aware FL framework, called FedCG, with adaptive client selection and gradient compression. Specifically, the parameter server (PS) selects a representative client subset considering statistical heterogeneity and sends the global model to them. After local training, these selected clients upload compressed model updates matching their capabilities to the PS for aggregation, which significantly alleviates the communication load and mitigates the straggler effect. We theoretically analyze the impact of both client selection and gradient compression on convergence performance. Guided by the derived convergence rate, we develop an iteration-based algorithm to jointly optimize client selection and compression ratio decision using submodular maximization and linear programming. Extensive experiments on both real-world prototypes and simulations show that FedCG can provide up to 5.3× speedup compared to other methods.

Data generated at the network edge can be processed locally by leveraging the paradigm of edge computing (EC). Aided by EC, decentralized federated learning (DFL), which overcomes the single-point-of-failure problem in the parameter server (PS) based federated learning, is becoming a practical and popular approach for machine learning over distributed data. However, DFL faces two critical challenges, i.e., system heterogeneity and statistical heterogeneity introduced by edge devices. To ensure fast convergence with the existence of slow edge devices, we present an efficient DFL method, termed FedHP, which integrates adaptive control of both local updating frequency and network topology to better support the heterogeneous participants. We establish a theoretical relationship between local updating frequency and network topology regarding model training performance and obtain a convergence upper bound. Upon this, we propose an optimization algorithm, that adaptively determines local updating frequencies and constructs the network topology, so as to speed up convergence and improve the model accuracy. Evaluation results show that the proposed FedHP can reduce the completion time by about 51% and improve model accuracy by at least 5% in heterogeneous scenarios, compared with the baselines.

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.

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.

Federated learning (FL) has been widely adopted to train machine learning models over massive data in edge computing. However, machine learning faces critical challenges, e.g., data imbalance, edge dynamics, and resource constraints, in edge computing. The existing FL solutions cannot well cope with data imbalance or edge dynamics, and may cause high resource cost. In this paper, we propose an adaptive asynchronous federated learning (AAFL) mechanism. To deal with edge dynamics, a certain fraction$\alpha$of all local updates will be aggregated by their arrival order at the parameter server in each epoch. Moreover, the system can intelligently vary the number of local updated models for global model aggregation in different epochs with network situations. We then propose experience-driven algorithms based on deep reinforcement learning (DRL) to adaptively determine the optimal value of$\alpha$in each epoch for two cases of AAFL, single learning task and multiple learning tasks, so as to achieve less completion time of training under resource constraints. Extensive experiments on the classical models and datasets show high effectiveness of the proposed algorithms. Specifically, AAFL can reduce the completion time by about 70 percent and improve the learning accuracy by about 28 percent under resource constraints, compared with the state-of-the-art solutions.

The emerging Federated Learning (FL) enables IoT devices to collaboratively learn a shared model based on their local datasets. However, due to end devices’ heterogeneity, it will magnify the inherent synchronization barrier issue of FL and result in non-negligible waiting time when local models are trained with the identical batch size. Moreover, the useless waiting time will further lead to a great strain on devices’ limited battery life. Herein, we aim to alleviate the negative impact of synchronization barrier through adaptive batch size during model training. When using different batch sizes, stability and convergence of the global model should be enforced by assigning appropriate learning rates on different devices. Therefore, we first study the relationship between batch size and learning rate, and formulate a scaling rule to guide the setting of learning rate in terms of batch size. Then we theoretically analyze the convergence rate of global model and obtain a convergence upper bound. On these bases, we propose an efficient algorithm that adaptively adjusts batch size with scaled learning rate for heterogeneous devices to reduce the waiting time and save battery life. We conduct extensive simulations and testbed experiments, and the experimental results demonstrate the effectiveness of our method.

Multi-access edge computing achieves better application responsiveness by offloading tasks from end devices to edge servers installed at the vicinity. Practical scenarios, such as post-disaster rescuing and battlefield monitoring, make it attractive to use end devices themselves as edge servers. This, however, introduces a new challenge: Due to mobility and power limitation, the set of edge servers becomes dynamic. As some servers fail, the tasks that run on them will also fail. This paper introduces a new dynamic edge computing model and conducts the first study on robust task offloading which is tolerant to$h$server failures. We propose online primal-dual algorithms that offload tasks as they arrive. We evaluate the performance of our robust task offloading solutions through extensive simulations based on real task sets. The results show that our proposed solutions can well handle edge dynamics and achieve near optimal throughput (above 95 percent) compared to the optimal offline benchmark algorithm.

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.

In edge computing (EC), federated learning (FL) enables massive devices to collaboratively train AI models without exposing local data. In order to avoid the possible bottleneck of the parameter server (PS) architecture, we concentrate on the decentralized federated learning (DFL), which adopts peer-to-peer (P2P) communication without maintaining a global model. However, due to the intrinsic features of EC, e.g., resource limitation and heterogeneity, network dynamics and non-IID data, DFL with a fixed P2P topology and/or an identical model compression ratio for all workers results in a slow convergence rate. In this paper, we propose an efficient algorithm (termed CoCo) to accelerate DFL by integrating optimization of topology Construction and model Compression. Concretely, we adaptively construct P2P topology and determine specific compression ratios for each worker to conquer the system dynamics and heterogeneity under bandwidth constraints. To reflect how the non-IID data influence the consistency of local models in DFL, we introduce the consensus distance, i.e., the discrepancy between local models, as the quantitative metric to guide the fine-grained operations of the joint optimization. Extensive simulation results show that CoCo achieves 10× speedup, and reduces the communication cost by about 50% on average, compared with the existing DFL baselines.

Data generated at the network edge can be processed locally by leveraging the paradigm of Edge Computing (EC). Aided by EC, Federated Learning (FL) has been becoming a practical and popular approach for distributed machine learning over locally distributed data. However, FL faces three critical challenges, i.e., resource constraint, system heterogeneity and context dynamics in EC. To address these challenges, we present a training-efficient FL method, termedFedLamp, by optimizing both theLocal updating frequency andmodel compression ratio in the resource-constrained EC systems. We theoretically analyze the model convergence rate and obtain a convergence upper bound related to the local updating frequency and model compression ratio. Upon the convergence bound, we propose a control algorithm, that adaptively determines diverse and appropriate local updating frequencies and model compression ratios for different edge nodes, so as to reduce the waiting time and enhance the training efficiency. We evaluate the performance ofFedLampthrough extensive simulation and testbed experiments. Evaluation results show thatFedLampcan reduce the traffic consumption by 63% and the completion time by about 52% for achieving the similar test accuracy, compared to the baselines.

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.

Recently, mobile and embedded devices worldwide generate a massive amount of data at the network edge. To efficiently exploit the data from distributed devices, we concentrate on decentralized machine learning (DML), where the workers collaboratively train models under the peer-to-peer (P2P) setting. DML avoids the bottleneck of the parameter server (PS) by enabling the workers to exchange local models with their neighbors rather than the PS. However, DML still faces some key challenges, i.e., resource limitation, system heterogeneity, network dynamics and non-IID data. In this article, we design and implement MOTOR, an efficient DML mechanism that simultaneously addresses these challenges by applying model pruning and topology construction, thus accelerating DML. Specifically, MOTOR assigns different pruning ratios to heterogeneous workers. After model pruning, each worker will train and transmit a sub-model that fits its capabilities, reducing both computation and communication overhead. Besides, MOTOR dynamically constructs the network topology considering the time-varying network conditions and non-IID data distributions. We theoretically analyze the impact of pruning ratio and network topology on model training performance. Guided by the theoretical analysis, we develop a joint optimization algorithm for pruning ratio decision and topology construction to achieve the trade-off between resource overhead and training performance. We implement MOTOR on commercial devices and evaluate the performance with different DML tasks. Extensive experiments show that MOTOR achieves up to 4.2× speedup compared to the existing DML approaches.

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.

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.

To approach the challenges of non-IID data and limited communication resource raised by the emerging federated learning (FL) in mobile edge computing (MEC), we propose an efficient framework, called FedMigr, which integrates a deep reinforcement learning (DRL) based model migration strategy into the pioneer FL algorithm FedAvg. According to the data distribution and resource constraints, our FedMigr will intelligently guide one client to forward its local model to another client after local updating, rather than directly sending the local models to the server for global aggregation as in FedAvg. Intuitively, migrating a local model from one client to another is equivalent to training it over more data from different clients, contributing to alleviating the influence of non-IID issue. We prove that FedMigr can help to reduce the parameter divergences between different local models and the global model from a theoretical perspective, even over local datasets with non-IID settings. Extensive experiments on three popular benchmark datasets demonstrate that FedMigr can achieve an average accuracy improvement of around 13%, and reduce bandwidth consumption for global communication by 42% on average, compared with the baselines.

Federated learning (FL) has been widely applied to collaboratively train deep learning (DL) models on massive end devices (i.e., clients). Due to the limited storage capacity and high labeling cost, there are always insufficient data stored and annotated on each client. Conversely, in cloud datacenters, there exist large-scale unlabeled data, which are easy to collect from public access (e.g., social media). Herein, upon the federated semi-supervised learning (FSSL) technology, we propose the Ada-FedSemi system, which leverages both on-device labeled data and in-cloud unlabeled data to boost the performance of DL models. Given the limited communication and massive quantity of the clients, in each training round, we decide to select partial clients to participate in FL, and their local models are aggregated by the parameter server (PS) to produce pseudo-labels for the unlabeled data, which are utilized to enhance the global model. Considering that the number of participating clients and the quality of pseudo-labels will have a significant impact on the training performance (e.g., efficiency and accuracy), we introduce a multi-armed bandit (MAB) based online algorithm to adaptively determine the participating fraction and confidence threshold during federated model training. Extensive experiments on benchmark models and datasets show that, given the same resource budget, the model trained by Ada-FedSemi achieves 3%-14.8 % higher test accuracy than that of the baseline methods. Besides, when achieving the same test accuracy, Ada-FedSemi saves up to 48% training cost, compared with the baselines.

In edge computing (EC), federated learning (FL) has been widely used to cooperatively train machine learning models and protect privacy over the traditional approaches. In order to avoid the possible communication bottleneck and single point failure in parameter server (PS) framework, we mainly focus on decentralized federated learning (DFL) in which each worker disseminates information through peer-to-peer (P2P) communication network. However, the high communication cost and the non-IID local data hinder the efficient training of DFL. In this paper, we propose a mechanism (termed DFL-DF) to achieve efficient communication and improve the performance on non-IID data. Specifically, each worker will exchange data features with neighbors rather than models (or gradients). Different from the traditional fixed topology methods, each worker will communicate with its neighbors selected at each round. Extensive experiment results show the high effectiveness of DFL-DF. Specifically, DFL-DF can reduce communication cost by 29.4%-82.06% and improve test accuracy 2.5%-9.1% under communication cost constraints, compared with the traditional model exchanging methods.

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.

Detecting heavy hitters that constitute the majority of network traffic is a critical task in network measurement. However, the highly skewed network traffic and the size-limited on-chip memory pose great challenges for heavy-hitter detection. The prior arts either use sketches to track all flows or maintain a fix-sized tracking list for recording elephant flows, resulting in limited detection precision or time-consuming tracking list exchanges. This paper presents HeavyTracker, an efficient algorithm that detects heavy hitters based on a count-with-threshold strategy. A two-dimensional tracker unit array is employed in our design to capture the heavy hitters, where each flow is randomly mapped to one unit in all rows. The tracker unit is designed to accept many flows and precisely report the largest two with frequencies that reach a predefined threshold. This design eliminates the frequent and time-consuming exchanges for maintaining the tracking list, allowing us to use a hash table to track the reported elephant flows. Experimental results based on real Internet traces show that HeavyTracker achieves a high $\mathbf{F}_{\beta}$-Score of threshold-t detection (0.97) and over 99% precision of top-k detection under a tight memory size. Besides, it reduces the frequency estimation error by 97.4% compared to the state-of-the-art.

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.

Per-flow size measurement is a fundamental problem in network engineering and plays a pivotal role in many practical applications. Constrained by on-chip memory resources and packet processing speed, most existing solutions use compact data structures (i.e., sketches) to perform the line-speed measurement. However, sketches share the record units (bits/counters) among flows, inevitably introducing noises to each flow’s measurement result. Although they adopt an average denoising strategy to remove noises from the raw estimations, the accuracy for medium flows is still lacking. This paper complements the prior art and presents a novel per-flow size measurement method, Adaptive Denoising (ADN), which can provide more accurate estimates for online and offline queries. For an online query, we use the collected flow records for real-time estimation. For an offline query, we model the propagation of noises based on the optimization algorithm to produce flow size estimation with much better accuracy. Experimental results based on real Internet traffic traces show that our measurement solutions outperform the state-of-the-art approaches and reduce the mean absolute error by around one order of magnitude under the same on-chip memory usage.

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

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 devices) and time-varying network connectivity due to device mobility or wireless channel dynamics, which receives less attention in recent years. To address these two challenges, this paper studies the impact of topology construction on the P2P training performance. Specifically, we dynamically construct an efficient P2P topology, where model aggregation occurs at the edge. 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 evaluate the performance of our proposed algorithm through extensive simulations and physical platform. Evaluation results show that our method can improve the model training efficiency by about 11% with resource constraints, reduce the communication cost by 30% and the network traffic consumption by about 60% under the same accuracy requirement compared to the benchmarks.

Under the paradigm of edge computing, the enormous data generated at the network edge can be processed locally. To make full utilization of these widely distributed data, we focus on an edge computing system that conducts distributed machine learning using gradient-descent based approaches. To ensure the system’s performance, there are two major challenges: how to collect data from multiple data source nodes for training jobs and how to allocate the limited resources on each edge server among these jobs. In this paper, we jointly consider the two challenges for distributed training (without service requirement), aiming to maximize the system throughput while ensuring the system’s quality of service (QoS). Specifically, we formulate the joint problem as a mixed-integer non-linear program, which is NP-hard, and propose an efficient approximation algorithm. Furthermore, we take service placement into consideration for diverse training jobs and propose an approximation algorithm. We also analyze that our proposed algorithm can achieve the constant bipartite approximation under many practical situations. We build a test-bed to evaluate the effectiveness of our proposed algorithm in a practical scenario. Extensive simulation results and testing results show that the proposed algorithms can improve the system throughput 56-69 percent compared with the conventional algorithms.

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.

As some delay-sensitive mobile services such as augmented reality and autonomous driving proliferate, users' demand for low latency access to computation resources increases dramatically, and existing centralized cloud computing paradigm is difficult to solve the current dilemma. As a emerging computing paradigm in which computational capabilities are pushed from the central cloud to the network edges, Mobile Edge Computing (MEC) is expected to be an effective solution. However, due to the limited capacity (e.g. computation and bandwidth) of MEC nodes, it is not easy to maintain satisfactory quality of service for user applications. Most of the previous work is limited to reducing the processing delay by dynamically adjusting the task offloading strategy, while ignoring the key impact of access network selection on network congestion. To fill this gap, we study the joint optimization of network selection and task offloading in MEC networks with multidimensional resources constraints. To address a number of key challenges in MEC systems, including spatial demand coupling and decentralized coordination, we propose an efficient online algorithm and achieve provable close-to-optimal performance. Extensive simulation results are presented to verify the performance of our algorithm.

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.

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.

Federated learning (FL) involves training machine learning models over distributed edge nodes (i.e., workers) while facing three critical challenges, edge heterogeneity, Non-IID data and communication resource constraint. In the synchronous FL, the parameter server has to wait for the slowest workers, leading to significant waiting time due to edge heterogeneity. Though asynchronous FL can well tackle the edge heterogeneity, it requires frequent model transfers, resulting in massive communication resource consumption. Moreover, the different relative frequency of workers participating in asynchronous updating may seriously hurt training accuracy, especially on Non-IID data. In this paper, we propose a semi-asynchronous federated learning mechanism (FedSA), where the parameter server aggregates a certain number of local models by their arrival order in each round. We theoretically analyze the quantitative relationship between the convergence bound of FedSA and different factors,e.g., the number of participating workers in each round, the degree of data Non-IID and edge heterogeneity. Based on the convergence bound, we present an efficient algorithm to determine the number of participating workers to minimize the training completion time. To further improve the training accuracy on Non-IID data, FedSA deploys adaptive learning rates for workers by their relative participation frequency. We extend our proposed mechanism to the dynamic and multiple learning tasks scenarios. Experimental results on the testbed show that our proposed mechanism and algorithms address the three challenges more effectively than the state-of-the-art solutions.

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.

To meet the ever-increasing demands for high-quality network services, a software defined network (SDN) can support various virtual network functions (VNFs) using virtualization technology. Due to network dynamics, an SDN needs to be updated frequently to optimize various performance objectives, such as load balancing. Most previous solutions first determine a new network configuration (e.g., target VNF placement and flow routing) based on the current workload, and then update the VNF placement and routing paths of the existing flows. However, due to massive VNF’s state migration and slow update of the flow table, unacceptable update delay may occur, especially in large or frequently changed networks. In this paper, we address the real-time network update, which jointly considers the optimization of the service function chain (SFC) update and the routing update. We propose the delay-satisfied NFV-enabled network update (DSNU) problem, and prove its NP-Hardness. We design an algorithm with bounded approximation factor to solve this problem. To further reduce the delay, we also design an efficient algorithm for the update scheduling. The experimental results show that our method can reduce the network update delay by about 86% compared with the previous network update methods while preserving a similar network performance,i.e., the VNF instance load ratio increases by less than 5%.

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.

Large software defined networks use a cluster of distributed controllers to process flow requests from a massive number of switches. To cope with traffic dynamics, this paper studies a new problem of how to improve the residual capacity available at the controllers to handle request bursts experienced at the switches. While the total residual capacity is a constant under a given total capacity of all controllers and a given total workload from all switches, this paper considers the residual capacity available to each individual switch, which depends on how the switches are mapped to the controllers for management. We focus on how tomaximize the minimum residual capacity available to any switch. The prior work either provides poor residual capacity or incurs heavy synchronization overhead by simulation results. This paper proposes a new method calledindirect multi-mappingthat achieves both high residual capacity and low synchronization cost. We formally define a non-linear integer optimization problem for max-min residual capacity under indirect multi-mapping. We then approximate the problem as two sub-problems: switch-controller mapping selection and weight assignment for each switch-controller mapping. We solve these sub-problems and formally analyze their approximate factor. We implement the proposed solution on an SDN testbed for experimental studies and use simulations for large-scale investigation. Our evaluation shows that indirect multi-mapping improves the minimum residual capacity by 49.8% on average and reduces the synchronization cost by 41.9-60.3% on average when compared with the alternatives.

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.

Mobile edge computing(MEC), as an emerging computing paradigm, pushes services away from centralized remote cloud to distributed edge servers deployed by multiple service providers(SPs), improving user experience and reducing the communication burden on core network. However, this distributed computing architecture also brings some new challenges to the network. In multi-SP MEC system, a SP prefers to use edge servers deployed by itself instead of others, which not only improves service quality but also reduces processing cost. The service placement and request scheduling strategies directly affect the revenue of SPs. Since the service popularity changes over time and the resources of edge servers are limited, the network system needs to make decisions about service placement and request scheduling dynamically to provide better service for users. Owing to the lack of long-term prior knowledge and involving binary decision variables, how to place services and schedule requests to boost the profit of SPs is a challenging problem. We formally formalize this joint optimization problem and propose an efficient online algorithm. First, we invoke Lyapunov optimization technology to convert the long-term optimization problem into a series of subproblems, then a dual-decomposition algorithm is utilized to solve the subproblem. Experimental results show that the algorithm proposed in this paper achieves nearly optimal performance, and it raises 25% and 70% profit compared to greedy and Top-K algorithms, respectively.

Attributed graph data is powerful to describe relational information in various areas, such as social links through numerous web services and citation/reference relations in the collaboration network. Taking advantage of attributed graph data, service providers can model complex systems and capture diversified interactions to achieve better business performance. However, privacy concern is a huge obstacle to collect and analyze user's attributed graph data. Existing studies on protecting private graph data mainly focus on edge local differential privacy(LDP), which might be insufficient in some highly sensitive scenarios. In this paper, we present a novel privacy notion that is stronger than edge LDP, and investigate approaches to analyze attributed graphs under this notion. To neutralize the effect of excessively introduced noise, we propose PrivAG, a privacy-preserving framework that protects attributed graph data in the local setting while providing representative graph statistics. The effectiveness and efficiency of PrivAG framework is validated through extensive experiments.

An SDN overlay network is a legacy network improved through SDN and overlay technology. It has some traits including the cheap upgrade cost, flexible network management and the sharing of physical network resources which has brought huge benefits to the multi-tenant cloud platform. Link failure is an important issue that shoulde be solved in any large network. In SDN overlay networks, link failure recovery brings new challenges different from the legacy network, such as how to maintain the performance of overlay networks in the post-recovery network. Thus, in the case of single link failure, we devise a recovery approach to guarantee the performance of overlay networks by the coordination between SDN switches and traditional switches. We formulate the link failure recovery (LFR) problem as an integer linear program and prove its NP-hardness. A rounding-based algorithm with bounded approximation factors is devised to solve the LFR problem. The simulation results show that the devised scheme can guarantee the performance of the overlay network after restoration. The results also show that, compared with SPR and IPFRR, the designed method can reduce the maximum link load rate by approximately 41.5% and 51.6%.

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.

Most user-generated data in online services are presented as set-valued data, e.g., visited website URLs, recently used Apps by a person, and etc. These data are of great value to service providers, but also bring privacy concerns if collected and analyzed directly. To tackle potential privacy threatens, local differential privacy (LDP) attracts increasing attention nowadays. However, existing approaches only provide sub-optimal error bound for set-valued data distribution estimation with LDP. Besides, it is computational expensive and communication expensive to use for high dimensional set-valued data, considering large domains in real scenarios. Thus, existing approaches are unpractical to use on resource-constrained user-side devices (e.g., smartphones and wearable devices). In this paper, we propose a utility-optimal and efficient set-valued data publication method (i.e., wheel mechanism ). On the user side, each user contributes only one numerical value to represent their privatized data. The computational complexity is O (min{ m log m , me ɛ }) and communication cost is O (log( me ɛ )) bits, while existing approaches usually depend on O ( d ) or O (log d ), where m is the number of items in the set-valued data ( m ≡ 1 for categorical data), d is the domain size (usually d ≫ m ) and ɛ is the privacy budget. On the server side, the estimator takes numerical values from users as input and derives an unbiased distribution estimation. Theoretical results show that estimation error bounds are improved from previously known [EQUATION] to the optimal rate [EQUATION]. Results on extensive experiments demonstrate that our proposed wheel mechanism is 3-100× faster than existing approaches, meanwhile has optimal statistical efficiency.

In the cloud environment, it brings better reliability and robustness with geographically distributed datacenters. As the growth of large-scale applications in geo-distributed cloud systems, the resource demand from different areas increases violently, and researchers pay more attention to meet as many cloud users' VM demands as possible by using limited cloud resources. However, there exist many issues for cloud users in existing works, such as the VM demands being refused and high response latency. In this paper, we present a cloud system model for the cloud provider to dynamically expand the scale of geo-distributed date centers. In our model, the cloud provider rents hardware resources from other resource owners (ROs), who have redundant resources and are willing to lease them. Since the ROs possess vast resources and spread all over the global, our system model can deploy more cloud users' VMs and effectively reduce the bandwidth cost. We propose an optimization problem for the cloud provider to maximize the profit, and carefully solve it in different conditions. Our simulation results show that our system model and algorithms can effectively improve the user satisfaction and the total revenue and reduce the average latency of users' requests.

With the proliferation of mobile devices, mobile crowd sensing (MCS) has emerged as a new data collection paradigm, which allows the crowd to act as sensors and contribute their observations about entities. Unfortunately, users with varied skills and motivations may provide conflicting information for the same entity. Existing work solves this problem by estimating user reliability and inferring the correct observations (i.e., truths). However, these methods assume that users' expertise degrees are dependent on the truths, but ignore the finer clusters that exist even in the entities with the same truths. To capture users' fine-grained reliability on different entity clusters, we propose a novel Bayesian co-clustering truth discovery model for the task of observation aggregation. This model enables us to produce a more precise estimation while taking into account the entity clusters and the user clusters. Experiments on four real-world datasets reveal that our method outperforms the state-of-the-art approaches in terms of accuracy and F1-score.

Traffic measurement in high-speed networks has many important functions in improving network performance, assisting resource allocation, and detecting anomalies. In this paper, we study a generalized problem called k-persistent spread estimation, which measures the volume of persist traffic elements in each flow that appear during at least k out of t measurement periods, where k and t are two positive integers that can be arbitrarily set in user queries, with k ≤ t. Solutions to this problem have interesting applications in network attack detection, popular content identification, user access profiling, etc. There is very limited prior art for this problem, only addressing the special case of k = t under a flawed assumption. Removing this assumption, we propose an efficient and accurate estimator for generalized k-persistent traffic measurement, with k ≤ t. Our method relies on bitwise SUM, instead of bitwise AND in the prior art, to combine the information collected from different periods. This change has fundamental impact on the probabilistic analysis that derives the estimator, particular over space-saving virtual bitmaps. Based on real network traces, we demonstrate experimentally the effectiveness of our new method in estimating the k-persistent spreads of all network flows. Our estimator performs much better than the prior art on its case of k = t. We also incorporate a sampling module to the estimator for improved flexibility, and give a use study on how to detect and find DDoS attackers using the proposed estimator.

Traffic measurement is very important for various applications, such as traffic engineering and attack detection, in software-defined networks. Due to limited resources (e.g., computing, memory) on SDN switches, sketches have been widely used for efficient traffic measurement. Meanwhile, multiple independent sketches are required for different application requirements, such as heavy hitter detection and flow size distribution estimation. To avoid the measurement redundancy, we configure which sketch(es) will measure flow on each switch. If traffic measurement is performed on each switch without considering network routing, due to traffic dynamics, it will cause massive measurement overhead on a switch, which may exceed the switch's computing capacity. In this paper, we study the joint optimization of flow routing and sketch configuration in SDNs. We formulate this problem as an integer linear programming and prove its NP-hardness. To solve this problem, we propose a rounding-based offline algorithm and a primal-dual-based online algorithm for different application scenarios. To deal with bursty traffic, we also design an adaptive sampling mechanism for high-fidelity traffic measurement. We formally analyze the approximation performance or competitive ratio of the proposed algorithms. The extensive simulation results show the high efficiency of our proposed algorithms. For example, the online algorithm can improve the network throughput 30% compared with the state-of-the-art.

Sketches have been widely used to record traffic statistics using sub-linear space data structure. Most sketches focus on the traffic estimation of elephant flows (i.e., heavy hitters) due to their importance to many network optimization tasks, e.g., traffic engineering and load balancing. In fact, the information of aggregate mice flows (e.g., all the mice flows with the same source IP) is also crucial to many security-associated tasks, e.g., DDoS detection and network scan detection. However, the previous solutions, e.g., measuring each individual flow or using multiple sketches for independent measurement tasks, will result in worse estimation error or higher computational overhead. To conquer the above disadvantages, we propose an accurate traffic measurement framework with multiple filters, called Sketchtree, to efficiently measure both elephant flows and aggregate mice flows. These filters in Sketchtree are organized in a hierarchical manner, and help to alleviate the hash collision and improve the measurement accuracy, as the number of flows through hierarchical filters in turn will be decreased gradually. We also design some mechanisms to improve the resource utilization efficiency. To validate our proposal, we have implemented Sketchtree and conducted experimental evaluation using real campus traffic traces. The experimental results show that Sketchtree can increase the processing speed by 100 percent, and reduce the measurement error by over 30 percent compared with state-of-the-art sketches.

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.

Many important functions in software defined networks can benefit from fine-grained traffic measurement at flow level. Because TCAM-based flow entries only provide aggregate traffic statistics, prior research has suggested to perform flow-level measurement in SRAM and balance the measurement load across the network through collaborative traffic measurement. The key problem of collaborative measurement is to provide a mechanism to distribute flows to switches such that each switch can identify its subset of flows to measure. We observe that the prior work has focused on optimizing flow distribution among switches, but overlooked their high space and per-packet processing overhead introduced to the data plane, which becomes a serious issue in large SDN systems. In this paper, we propose a new lightweight solution to the flow distribution problem. It follows the design principle of alleviating complexity of the data plane by minimizing the data-plane space and processing overhead. At the control plane, we formulate flow distribution as optimization problems under two scenarios that implement collaborative measurement by edge switches only and by edge/core switches together, respectively. Our extensive simulations demonstrate that, comparing with the best existing work, the proposed lightweight solution achieves a comparable performance in terms of load balancing, while drastically reducing both space overhead and per-packet processing overhead, making it more practical in real-world systems that are sensitive to the additional overhead introduced by flow distribution.

Measuring traffic volume in a road system has important applications in transportation engineering. The connected vehicle technologies integrate wireless communications and computers into transportation systems, allowing wireless data exchanges between vehicles and road-side equipment, and enabling large-scale, sophisticated traffic measurement. This paper investigates the problem of persistent traffic measurement, which was not adequately studied in the prior art, particularly in the context of intelligent vehicular networks. We propose three estimators for privacy-preserving persistent traffic measurement: one for point traffic, one for point-to-point traffic, and another for three-point traffic. After that, we present a general framework to measure persistent traffic that go through more than three locations. The estimators are mathematically derived from the join result of traffic records, which are produced by the electronic roadside units with privacy-preserving data structures. We evaluate our estimation methods using simulations based on both real transportation traffic data and synthetic data. The numerical results demonstrate the effectiveness of the proposed methods in producing high measurement accuracy and allowing accuracy-privacy tradeoff through parameter setting.

For the purpose of improving the quality of services, softwares or online services are collecting various of user data, such as personal information and locations. Such data facilitates mining statistical knowledge of users, but threatens users' privacy as it may reveal sensitive information (e.g., identities and activities) about individuals. This work considers distribution estimation over user-contributed data meanwhile providing rigid protection of their data with local ε-differential privacy (ε-LDP), which sanitizes each user's data on the client's side (e.g, on the user's mobile device). Our privacy protection covers both qualitative data (e.g., categorical data) and discrete quantitative data (e.g., location data). Specifically, for categorical data, we derive an optimal ε-LDP mechanism (termed as k-subset mechanism) from mutual information perspective, and further show its optimality over existing approaches within the context of discrete distribution estimation; for discrete quantitative data that have arbitrary distance metric, we provide an efficient extension of k-subset mechanism by proposing a variant of the popular Exponential Mechanism (EM) to tackle the asymmetry issue on the data domain. Experiments on real-world datasets and simulated scenarios show that our mechanism is highly efficient and reduces nearly a fraction of exp(- ε/2) error for distribution estimation when compared to existing approaches.

There are more and more structured traffic flows (a.k.a coflow) in today's data center networks. Completing a coflow is extremely important for various applications, e.g., MapReduce. To reduce the coflow completion time or CCT, one may increase the link capacity by applying advanced optical circuit switches in data center networks. Due to special features of optical circuit switches, both traffic scheduling and circuit scheduling will influence the CCT. However, previous solutions have some significant limitations: they consider either coflow scheduling, or circuit scheduling for only one optical circuit switch, which are both insufficient. In this paper, we study the integrated coflow and circuit scheduling (GCCS) problem with the objective to minimize the CCT, and prove its NP-hardness. We present an integrated algorithm which includes two steps, coflow scheduling and circuit scheduling, respectively. We also analyze that the proposed algorithm can achieve the approximation ratio O(h) in most practical situations, where h is the maximum number of ports among all lightpaths. Through large-scale simulations, we demonstrate that the integrated solution can significantly reduce the CCT by about 43-70 percent compared with the state-of-the-art coflow scheduler for optical networks.

Set-valued data is useful for representing a rich family of information in numerous areas, such as market basket data of online shopping, apps on mobile phones and web browsing history. By analyzing set-valued data that are collected from users, service providers could learn the demographics of the users, the patterns of their usages, and finally, improve the quality of services for them. However, privacy has been an increasing concern in collecting and analyzing users' set-valued data, since these data may reveal sensitive information (e.g., identities, preferences and diseases) about individuals. In this work, we propose a privacy preserving aggregation mechanism for set-valued data: PrivSet. It provides rigorous data privacy protection locally (e.g., on mobile phones or wearable devices) and efficiently (its computational overhead is linear to the item domain size) for each user, and meanwhile allowing effective statistical analyses (e.g., distribution estimation of items, distribution estimation of set cardinality) on set-valued data for service providers. More specifically, in PrivSet, within the constraints of local e-differential privacy, each user independently responses with a subset of the set-valued data domain with calibrated probabilities, hence the true positive/false positive rate of each item is balanced and the performance of distribution estimation is optimized. Besides presenting theoretical error bounds of PrivSet and proving its optimality over existing approaches, we experimentally validate the mechanism, the experimental results illustrate that the estimation error in PrivSet has been reduced by half when compared to state-of-the-art approaches.

The combination of Network Function Virtualization (NFV) and Software Defined Networking (SDN) possesses a great potential in accommodating dynamic network control via cloning/migration of virtualized NFs and steering of traffic flows. A great challenge is the lack of the proprietary internal NF state information to the control system (including SDN controller and NFV orchestrator), which may lead to incorrect packet/flow processing at the newly created NF instances. In this work, we design a light-weight approach which can function either independently or as a plug-in to the network control system to reveal the internal NF states. Unlike the previous work, we propose to learn the internal NF states through normal network functions instead of designing extra APIs for certain NFs. Moreover, we propose a feasible way to detect state violations and even correct them automatically. Our approach is tested by experiments, and the results confirm its efficiency and practicability.

There is a fundamental and critical problem in modern mobile applications, in which the battery life of mobile devices is usually limited. Recently, some researchers prolong the life of batteries by offloading computation tasks to edge-servers which are deployed near the mobile devices. However, computing offloading causes extra delay, which may severely downgrade the user experience especially for the delay-sensitive applications. Moreover, the dynamic nature of mobile devices and the limited computation capacity of edge-servers also bring another challenges for tradeoff optimization between energy consumption and task completion latency. In this paper, we propose a dynamic computing offloading (DCL) problem, which aims to minimize the maximum energy consumption of the mobile devices with constraints on computation tasks latency in a Mobile Edge-Computing (MEC) network. To solve the problem, we consider two complementary cases: offline case (we sacrifice response time to achieve better service results) and online case (where we have to make immediate offloading decision for each computation task arrived online). For the offline case, we propose an efficient RMCL algorithm, and prove that our RMCL method achieves at least O((log m)/α + 1) of the optimum with high probability, where m is the number of computation tasks in a time slot, and α is a value depending on the minimum edge-server capacity and the maximum computation task demand, with α ≥ 1 under most practical situations. For the online case, we propose an algorithm, named OMCL, which considers a trade off between the latency and energy consumption. The performance of our proposed algorithms is evaluated by formal analysis and simulation on a small-scale system. The simulation results show that the algorithm can reduce the maximum energy consumption in a set of mobile devices by 40% compared with executing computation tasks locally.

In[1], reference [16] should be replaced as follows: [16] P. Chao, Y. Tan, and L. T. Yang, “New algorithms for the minimum-cost single-source unsplittable flow problem,” inProc. 21st Int. Conf. Adv. Inf. Netw. Appl. Workshops (AINAW), Niagara Falls, ON, Canada, May 2007.

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.

Software defined networking (SDN) is becoming increasingly prevalent for its programmability that enables centralized network configuration and management. With the growth of SDNs, a cluster of controllers cooperatively manages more and more switches/flows in a network to avoid the single-controller congestion/failure and improve the control-plane robustness. Under the architecture with multiple controllers, it is expected to minimize the maximum response time on these controllers to provide better QoS for users. To achieve this target, two previous methods are mainly used, the static scheme and the dynamic scheme. However, these methods may lead to an increase of the control-plane communication overhead/delay. In this paper, we propose to minimize the maximum response time on controllers through flow redirecting, which is implemented by installing wildcard rules on switches. We formulate the minimum controller response time problem, which takes the flow-table size and link capacity constraints into account, as an integer linear program, and prove its NP-Hardness. Two algorithms with bounded approximation factors are designed to solve this problem. We implement the proposed methods on our SDN testbed. The testing results and extensive simulation results show that our proposed algorithm can reduce the maximum controller response time by about 50%-80% compared with the static/dynamic methods under the same controller cost, or reduce the number of controllers by 30% compared with the dynamic method while preserving almost the same controller response time.

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.

In a software-defined network (SDN), statistics information is of vital importance for different applications, such as traffic engineering, flow rerouting, and attack detection. Since some resources, e.g., ternary content addressable memory, SRAM, and computing capacity, are often limited on SDN switches, traffic measurements based on flow tables or sampling become infeasible. In fact, sketches provide a promising building block for filling this void by monitoring every packet with fixed-size memory. Although many efficient sketches have been designed, our analysis shows that existing sketch-based measurement solutions may suffer from severe computing overhead on switches especially under high traffic load that significantly interferes with switch's basic functions, such as flow rule setup and modification. In this paper, we present CountMax, a lightweight and cooperative sketch for traffic measurement, which can achieve low-amortized processing overhead and tight estimation bounds, to track large flows in SDNs. We also discuss how to apply CountMax to support a variety of applications. We have implemented the proposed algorithm on our open switches. Testbed experiments and extensive simulation results show that CountMax consumes only 1/3-1/2 computing overhead and reduces the average estimation error by 20%-30%, compared with the existing solutions under the same memory size.

Cooperative communication (CC) is shown to be a promising technology to improve the spatial diversity without additional equipments and antennas. The choice of relay nodes can significantly affect the performance of wireless cooperative networks, e.g. energy- efficiency. Most of existing works focused on dedicating one relay node to a transmission pair in the network. However, the energy-efficiency can be improved by sharing each relay node among more than one transmission pair. In this paper, we first introduce the feasibility of shared relay assignment to improve the energy-efficiency while achieving the required bandwidth for each transmission pair. Then, the Minimum Energy Consumption (MEC) problem of CC with shared relay is defined, and we formulate it as a mixed integer optimization program and prove it is NP-hard. A Simulated Annealing (SA) algorithm is designed to solve this problem. We conduct abundant simulation experiments to evaluate the performance of our proposed algorithm. The simulation results show that the SA algorithm can save about 15 energy consumption on average than the previous work in wireless networks.

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.

Measuring point traffic volume and point-to-point traffic volume in a road system has important applications in transportation engineering. The connected vehicle technologies integrate wireless communications and computers into transportation systems, allowing wireless data exchanges between vehicles and road-side equipment, and enabling large-scale, sophisticated traffic measurement. This paper investigates the problems of persistent point traffic measurement and persistent point-to-point traffic measurement, which were not adequately studied in the prior art, particularly in the context of intelligent vehicular networks. We propose two novel estimators for privacy-preserving persistent traffic measurement: one for point traffic and the other for point-to-point traffic. The estimators are mathematically derived from the join result of traffic records, which are produced by the electronic roadside units with privacy-preserving data structures. We evaluate our estimation methods using simulations based on both real transportation traffic data and synthetic data. The numerical results demonstrate the effectiveness of the proposed methods in producing high measurement accuracy and allowing accuracy-privacy tradeoff through parameter setting.

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.

The categorical data that have natural ordering between categories are termed ordinal data, which are pervasive in numerous areas, including discrete sensor readings, metering data or preference options. Though aggregating such ordinal data from the population is facilitating plenty of crowdsourcing applications, contributing such data is privacy risky and may reveal sensitive information (e.g. locations, identities) about individuals. This work studies ordinal data aggregation for distribution estimation meanwhile locally preserving individuals' data privacy (such as on their mobile devices). Under ε-geo-indistinguishable constraints, which capture intrinsic dissimilarity between ordinal categories in the framework of differential privacy, we provide an efficient and effective locally private mechanism: Subset Exponential Mechanism (SEM) for ordinal data distribution estimation. The mechanism randomly responds with a fixed-size subset of the categories with calibrated probability assignment. Specially for uniform ordinal data, we propose a circling technique to symmetrically randomizing categories and estimating frequencies of categories, hence the computational/space costs and estimation performance of SEM are further optimized. Besides contributing theoretical error bounds of SEM, we also evaluate the mechanism on extensive scenarios, the evaluation results show that SEM reduces distribution estimation error on average by exp(ϵ/2) factor over existing private mechanisms.

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.

In a software defined network (SDN), the control plane needs to frequently collect flow statistics measured at the data plane switches for different applications, such as traffic engineering, flow re-routing, and attack detection. However, existing solutions for flow statistics collection may result in large bandwidth cost in the control channel and long processing delay on switches, which significantly interfere with the basic functions such as packet forwarding and route update. To address this challenge, we propose a Cost-Optimized Flow Statistics Collection (CO-FSC) scheme using wildcard-based requests. We prove that the CO-FSC problem is NP-Hard and present a rounding-based algorithm with an approximation factor f, where f is the maximum number of switches visited by each flow. Moreover, our CO-FSC problem is extended to the general case, in which only a part of flows in a network need to be collected. The extensive simulation results show that the proposed algorithms can reduce the bandwidth overhead by over 41% and switch processing delay by over 45% compared with the existing solutions.

To take advantage of software defined networking (SDN) within a limited budget constraint, a natural strategy is to incrementally deploy a few SDN switches (and a limited amount of additional link bandwidth) into the legacy optical network. In such a hybrid optical network, operators can only change the routes of flows that traverse SDN switches. Therefore, to optimize SDN deployment, it is essential to decide the best places to deploy SDN resources (including SDN switches and link bandwidth) while taking the network traffic into consideration. In this paper, we propose a new SDN deployment scheme, called duplicated deployment, to provide a simple and efficient way for a hybrid network. Based on the proposed deployment scheme, we for the first time define the joint duplicated deployment and routing (DDR) problem for throughput maximization (or optimal deployment) with a given budget constraint on the additional SDN resource cost. Due to the NP-Hardness of the DDR problem, we then present an approximation algorithm based on the traffic mapping and randomized rounding methods, and prove that the approximation factor is (O(log n);O(log n)) in the worst case and (O(1);O(1)) under most practical situations for link capacity and flow-table size constraints, where n is the number of devices (including SDN switches and legacy routers) in the hybrid network. Through extensive simulations, we demonstrate high efficiency of our joint deployment and routing algorithm. For example, our proposed algorithm can improve the network throughput by about 26% compared with existing routing mechanisms with the same amount of extra resources.

Cooperative communication has great potential to enhance the performance of wireless networks by exploiting relay nodes' spatial diversity. Relay assignment plays a vital role in making the most of this potential. However, most previous studies investigate relay assignment in a rather static manner which may lead to the under‐utilisation of relay nodes, especially in the scenarios where source nodes' demands are time varying. Hence, in this study, the authors consider the relay assignment problem for cooperative networks using auction model with access flexibility, i.e. providing sufficient flexibility for source nodes to access relay nodes in time domain. They divide relay nodes' access time into multiple smaller access units and permit each source node to bid for a bundle of desired access units in the auction. This model is formulated as a combinational auction whose winner determination problem is NP hard. They thus present an auction mechanism with an elaborated greed strategy which not only achieves adorable properties such as truthfulness, individual rationality and computational efficiency, but also guarantees near‐optimal social welfare. Finally, they conduct extensive evaluations to verify the performance of their mechanism.

Software defined networking (SDN) separates the data plane and control plane on independent devices. Since the data plane, consisting of switches, is responsible for packets forwarding, previous work often considers the different constraints (e.g., data link capacity and flow-table size) only in the data plane to provide better QoS for users. However, due to limited CPU processing power and low speed of flow-table updating on each switch, the control channels/links between switches and the controller often have very limited capacity, which will cause QoS performance (e.g., response time and throughput) degradation when the switch should handle a high traffic load. The goal of our paper is to achieve better QoS by jointly considering the control link constraint and other different constraints of the data plane in SDNs. We formally define the control link load balancing and low delay route deployment problems, and prove the NP-Hardness. We present two algorithms with bounded approximation factors for each problem and implement the proposed methods on our SDN testbed. Extensive simulation results and experimental results show that our algorithms can reduce control link load by about 50% and response time by about 60%, and increase the network throughput by 65% compared with previous methods.

To explore the advantages of software defined network (SDN), while preserving the legacy networking systems, a natural deployment strategy is to deploy a hybrid SDN incrementally to improve the network performance. In this paper, we address two technical challenges: an incremental deployment strategy and a throughput-maximization routing, for deploying a hybrid network incrementally. For incremental deployment, we propose a heuristic algorithm for deploying a hybrid SDN under the budget constraint, and prove the approximate factor of 1- 1/e. For throughput-maximization routing, we apply a depth-first-search method and a randomized rounding mechanism to solve the multi-commodity h-splittable flow routing problem in a hybrid SDN, where h ≥ 1. We also prove that our method has approximation ratio O(1/log N), where N is the number of links in a hybrid SDN. We then show, by both analysis and simulations, that our algorithms can obtain significant performance gains and perform better than the theoretical worst-case bound. For example, our incremental deployment scheme helps to enhance the throughout about 40% compared with the previous deployment scheme by deploying a small number of SDN devices, and the proposed routing algorithm can improve the throughput about 31% compared with ECMP in hybrid networks.

Due to flow dynamics, a software defined network (SDN) may need to frequently update its data plane so as to optimize various performance objectives, such as load balancing. Most previous solutions first determine a new route configuration based on the current flow status, and then update the forwarding paths of existing flows. However, due to slow update operations of Ternary Content Addressable Memory-based flow tables, unacceptable update delays may occur, especially in a large or frequently changed network. According to recent studies, most flows have short duration and the workload of the entire network will vary significantly after a long duration. As a result, the new route configuration may be no longer efficient for the workload after the update, if the update duration takes too long. In this paper, we address the real-time route update, which jointly considers the optimization of flow route selection in the control plane and update scheduling in the data plane. We formulate the delay-satisfied route update problem, and prove its NP-hardness. Two algorithms with bounded approximation factors are designed to solve this problem. We implement the proposed methods on our SDN test bed. The experimental results and extensive simulation results show that our method can reduce the route update delay by about 60% compared with previous route update methods while preserving a similar routing performance (with link load ratio increased less than 3%).

In a software-defined network (SDN), the control plane needs to frequently collect flow statistics measured at the data plane switches for different applications, such as traffic engineering, QoS routing, and attack detection. However, existing solutions for flow statistics collection may result in large bandwidth cost in the control channel and long processing delay on switches, which significantly interfere with the basic functions, such as packet forwarding and route update. To address this challenge, we propose a cost-optimized flow statistics collection (CO-FSC) scheme and a cost-optimized partial flow statistics collection (CO-PFSC) scheme using wildcard-based requests, and prove that both the CO-FSC and CO-PFSC problems are NP-hard. For CO-FSC, we present a rounding-based algorithm with an approximation factor f, where f is the maximum number of switches visited by each flow. For CO-PFSC, we present an approximation algorithm based on randomized rounding for collecting statistics information of a part of flows in a network. Some practical issues are discussed to enhance our algorithms, for example, the applicability of our algorithms. Moreover, we extend CO-FSC to achieve the control link cost optimization FSC problem, and also design an algorithm with an approximation factor f for this problem. We implement our designed flow statistics collection algorithms on the open virtual switch-based SDN platform. The testing and extensive simulation results show that the proposed algorithms can reduce the bandwidth overhead by over 39% and switch processing delay by over 45% compared with the existing solutions.

Due to flow dynamics, a software defined network (SDN) may need to frequently update its data plane so as to optimize various performance objectives, such as load balancing. Most previous solutions first determine a new route configuration based on the current flow status, and then update the forwarding paths of existing flows. However, due to slow update operations of Ternary Content Addressable Memory (TCAM) based flow tables, unacceptable update delays may occur, especially in a large or frequently changed network. According to recent studies, most flows have short duration and the workload of the entire network may vary after a long duration. As a result, the new route configuration may be no longer efficient for the workload after the update, if the update duration takes too long. In this paper, we address the real-time route update, which jointly considers the optimization of flow route selection in the control plane and update scheduling in the data plane. We formulate the delay-satisfied route update (DSRU) problem, and prove its NP-Hardness. Two algorithms with bounded approximation factors are designed to solve this problem. We implement the proposed methods on our SDN testbed. The experimental results and extensive simulation results show that our method can reduce the route update delay by about 60% compared with previous route update methods while preserving a similar routing performance (with link load ratio increased less than 3%).

It is a common view in Software Defined Network (SDN) that the flow table plays the most significant role in SDN architecture, but suffers from the limited TCAM chips. The shortage of flow table storage strongly impacts the quality of service (QoS) provided by SDN, but requires rational solutions. In this paper, we present a practical on-line approach based on the decision tree structure to solve this problem. Our performance is evaluated by the comparison with other existing technologies.

In this work, we focus on designing high-throughput anycast mechanisms in a software Defined Network (SDN), as anycast routing serves as a fundamental building block for many services. Specifically, we investigate two main challenges for efficient implementation of a SDN-based anycast system: high throughput anycast routing (HTAR) and congestion-free anycast reconfiguration (CFAR). For the first challenge, we design an anycast routing (ARFU) algorithm, based on the fully polynomial time approximation scheme and the single-source unsplittable flow routing method. We prove that ARFU produces a route that can achieve a throughput at least 1/2(1+ξ) of the optimum, where ξ > 0 is an arbitrarily small constant. We then propose an anycast reconfiguration algorithm with transitive configurations, called ARTC, for congestion-free. This algorithm tries to find a routing reconfiguration procedure consisting of at most T ≥ 1 transitive configurations while meeting all the flow demands. When traffic demands can not be satisfied, ARTC maximizes the minimum throughput using one transitive configuration. Our simulations demonstrate high-efficiency of our algorithms.

Visible light communication (VLC) has been shown to have several advantages over traditional wireless communication. We envision a LED-to-smartphone VLC protocol for delivering messages to a group of unsynchronized mobile device receivers. We carefully design and implement our protocol, Martian, which allows smooth communication from the LED lights to a group of camera-enabled mobile devices. Across several phone models, Martian can achieve data rate of about 1.6kbps even with NLOS-light. Our intensive evaluations indicate that, the data rate reaches 4.2kbps on iPhone 6. This is a significant improvement compared with the 88bps data rate claimed by state-of-art design.

Surface transportation is of a great importance in urban life. Fueled by the promise of Smart City, it is becoming more and more common to provide WiFi services in urban Public Transportation System (PTS). In this paper, we present a practical method to make use of the WiFi service provided on buses to estimate real-time urban traffic condition. We validate the proposed method in a city district and show that it is an excellent alternative or supplement of the existing traffic condition estimation services.

Dynamic secondary spectrum markets have gained tremendous attentions recently, which can provide significant flexibility for trading spectrum by conducting auctions periodically. The high price of spectrum necessitates a thorough consideration on secondary users' budget constraint, i.e. the total money they could pay. However, previous studies rarely deal with the practical issue of budget constraint, and concentrate on maximizing social welfare greedily in a single round auction, which may not guarantee their performance after multiple rounds of auctions. In this paper, we investigate the techniques for budget constrained periodic spectrum auction, which ensures approximate social welfare maximization from a long- term perspective. With the celebrated primal-dual method, we present a Periodic Spectrum Auction framework (PSA) that runs a tailored One Round Spectrum Auction (ORSA) in each round. In the ORSA, we achieve critical properties such as truthfulness, individual rationality and computational efficiency. Due to the dual fitting technique, ORSA not only achieves approximate social welfare maximization in one round, but also guarantees only a small loss of approximation ratio when runs in multiple rounds under the PSA framework. Finally, we conduct extensive simulations to demonstrate the performance of our schemes.

Relay assignment significantly affects the performance of the cooperative communication, which is an emerging technology for the future mobile system. Previous studies in this area have mostly focused on assigning a dedicated relay to each source-destination pair for one-to-one (121) traffic. However, many-to-one (M21) traffic, which is also common in many situations (for example, several users associate with one access point in a wireless access network such as a WLAN), hasn't been well studied. This paper addresses the shared relay assignment (SRA) problem for M21 traffic. We formulate two new optimization problems: one is to maximize the minimum throughput among all the sources (hereafter called M21-SRA-MMT), and the other is to maximize the total throughput over all the sources while maintaining some degree of fairness (hereafter called M21-SRA-MTT). As the optimal solutions to the two problems are hard to find, we propose two approximation algorithms whose performance factors are 5.828 and 3, respectively, based on the rounding mechanism. Extensive simulation results show that our algorithms for M21-SRA-MMTcan significantly improve the minimum throughput compared with existing algorithms, while our algorithm for M21-SRA-MTTcan achieve the close-to-optimal performance.

Virtual multi-input-multi-output vMIMO technology is becoming a promising way to improve the energy efficiency of wireless networks. Previous research always builds up the vMIMO-based routing on the fixed structure such as clusters, and the MIMO mode is omitted in most cases. So, they cannot fully explore the advantage of vMIMO in routing. In this paper, we study a general routing scheme in which no fixed structure is required, and any communication mode of vMIMO is allowed for sake of the energy efficiency. We define two vMIMO-based routing problems aiming to energy-minimization and lifetime-optimization. The first problem can be solved by our distributed energy-minimum vMIMO-based algorithm. The algorithm constructs the virtual cooperative graph, and applies the shortest path method on the virtual cooperative graph to solve this problem. The second problem is non-deterministic polynomial-time hard, and we design the distributed lifetime-oriented vMIMO-based algorithm, which is based on the modified Bellman-Ford method. It can reach approximation ratio of four. The simulations show that our algorithms can work well in many situations. For example, distributed lifetime-oriented vMIMO-based algorithm can prolong the lifetime about 20.2% in dense topologies compared with the cooperative routing algorithm on average. Copyright © 2015 John Wiley & Sons, Ltd.

Histogram estimation is one of the fundamental tasks in crowdsourcing data aggregation. Since contributing data reveal more or less information about individuals' identifications and activities, participants need to preserve privacy of data according to their own levels of privacy concern. However, most of the existing work only aggregates data with an identical privacy level. In this paper, we propose an aggregation scheme for histogram estimation, wherein participants can publish their data at personalized differential-privacy levels. The aggregator also benefits from potential wider engagement or more honest data. Specially, since privacy levels under personalized privacy policy are sensitive information for participants, our scheme permits participants to keep their privacy levels secret even from the aggregator. We also show how to further optimize the estimation accuracy under given privacy levels by choosing specific randomization strategies.

Software Defined Network (SDN) is facilitating rapid innovation of network by providing a programmable network infrastructure. However, managing SDN flow rules, especially among multiple modules and administrators, has become complex and error-prone. Different controller modules with diverse objectives may be installed on the SDN controller, which can lead to anomalies among policies and rules. In this paper, we propose ADRS(Anomaly Detecting and Resolving for SDN) to solve this problem. Firstly, we analyse the rule-level anomalies that may occur in SDN based on OpenFlow protocol. Then we present an interval tree model for rapid rule scanning and a share model for network privilege allocating. By applying these models, we provide an automatic algorithm to detect and resolve the anomalies among SDN modules. Moreover, a rule-recovery mechanism is presented to avoid modification faults. We also implement and evaluate our system in the OpenDayLight controller.

The software defined network (SDN) has been developing tremendously in recent years. Numerous studies are proposed on the performance of SDN in academia. The idea of programmable network which is the foundation of SDN ensures dynamic network management by separating the control plane away from the network switches. The focus of this paper is the flow table's size in OpenFlow switches which is a significant bottleneck in SDN's practical application. We propose a mechanism named “Flow Table Reduction Scheme”(FTRS) for reducing the flow table size and maintaining the omnipotent controller's functions at the same time. We test the performance of FTRS both in simulation and experiment and the results show that FTRS is able to reduce 98% at most of the size of flow table with no impact on network's normal functions.

To tackle the challenging secrecy communication problem in energy harvesting cognitive radio networks, this paper considers an overlay system with one energy harvesting secondary user (SU) to assist primary transmission under the assumption that the primary channel at primary receiver is worse than the eavesdropper. Under such scenario, we optimize the secrecy rate of the PU transmitter by jointly investigating energy harvesting slot, cooperative transmission slot and so on. Given the transmission rate requirement between SUs, the optimization problem is formulated as a mixed integer non-linear (MINLP) program. Due to the special features, we design a polynomial time algorithm SRMA to optimally solve this problem. The algorithm computes the lower bound and upper bound of the transmission power in a secondary transmitter, which are relative with the QoS requirement and energy harvesting parameters. Then SRMA determines its optimal transmission power by iteratively searching between two bounds. Numerical results demonstrate that the primary secrecy rate grows with the increasing energy save ratio and optimal energy save ratio is inversely proportional to the energy harvesting rate.

Cooperative cognitive radio network (CCRN) is a promising paradigm to increase spectrum utilization and exploit spatial diversity. The allocation of two related resources, i.e. spectrum and relay nodes, plays a fundamental role in the performance of CCRNs. However, previous works either lack of incentives for both primary users (PUs) and relay nodes to participate in or consider spectrum auction and relay auction separately. In this paper, we consider a static cooperative cognitive radio network scenario with several PUs and multiple secondary user coteries, each of which consists of a set of secondary users who are interested in sharing the same secondary relay node. We model the problem of joint spectrum allocation and relay allocation as a hierarchical auction and propose TERA, which is the first Truthful auction mechanism for Efficient Resource Allocation in CCRNs. We show that TERA satisfies critical economic properties such as truthful, individual rationality, budget balance, supply limits and computational efficiency. Furthermore, we theoretically prove TERA can achieve near-optimal revenue with high probability. Finally, extensive simulation results show that TERA is efficient and able to improve the utility of PUs and relay nodes significantly up to 125% and 151% respectively.

As more and more applications migrate into clouds, the placement of virtual machines for these applications has much impact on the performance of cloud systems. A number of virtual machine (VM) placement techniques have been proposed over recent years. However, most of the existing works on VM placement ignore the response latency of the requests from tenants. In this paper, we investigate the techniques of VM placement with stochastic requests from the tenants to minimize the total (average) response latency. We first model the requests for each application from the corresponding tenant as independent Poisson stream. Moreover, the VMs are modeled as simple M/M/1 queueing systems. Then, we define the problem of VM placement for minimizing the total response delay (VMMD) and show it is NP-hard. We propose three heuristic algorithms, namely, Greedy, Local Adjustment (LA) and Simulated Annealing (SA). We conduct abundant simulation experiments to evaluate the performance of our proposed algorithms. The simulation results show that the proposed algorithms are efficient in decreasing the total response latency of the requests from tenants. Especially, the SA heuristic, which decreases the total response latency about 68% at most, shows the best performance on minimizing the total response latency in cloud systems.

The popularity of mobile devices has far expanded the application scenarios of spatial crowdsensing, due to its ability to provide fine-grained multi dimensional sensor readings associated with location information. Privacy is one of the fundamental issues in crowdsensing, as these location-based sensor readings may reveal identities or activities of participants. In this paper, we adopts the state-of-art location privacy definition geo-indistinguishability, provide an efficient and effective privacy preserving histogram aggregation mechanism BFMM (Bit Flipping Matrix Mechanism) for fine-grained multi dimensional location-based data. Theoretical analyses and experimental results demonstrate the efficiency and effectiveness of our approach for fine-grained multidimensional location-based data. Specifically, the aggregation accuracy of our approach averagely outperforms existing methods by a factor of number of buckets in the histogram.

Wireless mesh networks (WMNs) are being used and deployed widely all around the world for various reasons such as public safety, environmental monitoring and city-wide wireless Internet services [4], [12]. Although faced with some difficulties, wireless mesh network is thought to be a preferred municipal Internet service provider [5] with huge potential due to its automatic connection, ease of installation, dynamic route discovery, flexibility and other advantages. Since plenty of cities such as Singapore and the city of Cambridge have put providing ubiquitous Internet access on the agenda [3], the research on providing QoS-guaranteed municipal WMNs is in urgent need.

As the size of smartphone touchscreens becomes larger and larger in recent years, operability with single hand is getting worse especially for female users. We envision that user experience can be significantly improved if smartphones are able to detect the current operating hand and adjust the UI subsequently. In this paper, we propose a novel scheme that leverages user-generated touchscreen traces to recognize current operating hand accurately, with the help of a supervised classifier constructed from twelve different kinds of touchscreen trace features. As opposed to existing solutions that all require users to select the current operating hand or dominant hand manually, our scheme follows a more convenient and practical manner, and allows users to change operating hand frequently without any harm to user experience. We conduct a series of real-world experiments on Samsung Galaxy S4 smartphones, and evaluation results demonstrate that our proposed approach achieves 94.1% accuracy when deciding with a single trace only, and the false positive rate is as low as 2.6%.

Spectrum auction is an emerging economic scheme to stimulate both primary spectrum operators (POs) and secondary users (SUs) to be involved in spectrum sharing. Previous spectrum auction works mostly assume each PO can only have one type spectrum or each SU can only buy homogeneous spectrum bands from the same PO. However, in a ubiquitous network scenario, each PO possesses heterogeneous spectrum resources such as WiFi, 3G and each SU may request different types of spectrum bands from the same PO. Existing auction schemes cannot be used to effectively solve the problem. Therefore, the authors come out with a lightweight combinatorial double auction to tackle this challenge. Since spectrum combinatorial double auction problem is NP‐hard, the authors develop a general greedy algorithm G‐Greedy to solve the problem. Inspired by the recent group‐buying discounts, they also invent an enhanced scheme E‐Greedy to further optimise total utility. They theoretically prove the economy properties of the proposed schemes such as individual rationality, budget balance and truthfulness. Simulation results show that both of the two algorithms can yield higher utilities and are effective.

Many spectrum auction mechanisms have been proposed for spectrum allocation problem, and unfortunately, few of them protect the bid privacy of bidders and achieve good social efficiency. In this paper, we propose PPS, a Privacy Preserving Strategyproof spectrum auction framework. We design two schemes based on PPS separately for 1) the single-unit auction model (SUA), where only single channel will be sold in the spectrum market; and 2) the multi-unit auction model (MUA), where the primary user subleases multi-unit channels to the secondary users and each of the secondary users wants to access multi-unit channels either. Since the social efficiency maximization problem is NP-hard in both auction models, we present allocation mechanisms with approximation factors of (1 + ε) and 32 separately for SUA and MUA, and further judiciously design strategyproof auction mechanisms with privacy preserving based on them. Our extensive evaluations show that our mechanisms achieve good social efficiency and with low computation and communication overhead.

Virtual multi-input multi-output (MIMO) or vMIMO is becoming an attractive technology to achieve spatial diversity in wireless networks without using additional antennas, and to reduce power consumption by cooperation among multiple nodes. As data gathering is one of the most important operations in many sensor network applications, this paper studies energy-efficient data gathering in wireless sensor networks using vMIMO. We define the joint vMIMO and data gathering (vMDG) problem, which is NP-hard. We also propose a distributed method called D-vMDG as an approximation algorithm. This algorithm first constructs a tree-like topology by taking the unique features of vMIMO into account. Then, an energy-efficient routing protocol based on dynamic programming is proposed for each node on the constructed topology. Our theoretical analysis shows that D-vMDG can achieve an approximation ratio of O(1). Our simulations show that D-vMDG decreases the energy consumption by 81 and 36 percent compared to the well-known MDT [26] and MIMO-LEACH [19] algorithms respectively.

The choice of relay nodes significantly affects the performance of wireless cooperative networks. Previous research mostly focused on dedicating one relay node to a source node in the network. However, fairness can be improved by sharing each relay node among more than one source node. This paper first defines the shared relay assignment for (max-min) fairness (SRAF) problem, and formalizes it using a mixed integer program. We then propose a heuristic algorithm (RRA) to solve this problem. The algorithm mainly uses the binary search and rounding mechanisms to implement the shared relay assignment, so that the minimum throughput of all source nodes is improved. The theoretical analysis proves that the proposed algorithm can reach the approximate performance of 2+ε, where ε is an arbitrarily small positive number. An improved version of RRA, called IRRA, can improve the minimum throughput while still preserving the worst-case performance. Our simulations show that the IRRA algorithm can achieve about 18% improvement over the best existing approach in the minimum throughout among the source nodes.

With the development of cloud computing, there is an increasing number of market-based mechanisms for cloud resource allocation. Inspired by the emerging group-buying Web sites, we advocate that group-buying can be applied to cloud resource allocation, and thus cloud providers can benefit from demand aggregation due to the advantage of group-buying in attracting customers, while cloud users can enjoy lower price. However, none of the existing allocation mechanisms is specifically designed for the scenario with group-buying, and it is a challenge for mechanism design to take full advantage of group-buying to maximize the total utility. In this paper, we fill this gap by proposing an innovative auction mechanism. The mechanism is designed based on a combinatorial double auction, in which the allocation algorithm and payment scheme are specifically designed to efficiently generate allocation and compute prices considering group-buying. We theoretically prove that the necessary economic properties in auction design, such as individual rationality, budget balance and truthfulness, are satisfied in our work. The experiments show that the proposed mechanism yields higher total utility, and has good scalability.

Content Delivery Network (CDN) is proposed for replicating data objects at multiple locations in the network and encounters vast potential for future development, as a result of which, a number of replica placement techniques have been proposed over the last decade. However, most of the existing works on replica placement (RP) ignore the statistical property of the demands and the restricted service rate of the servers. In this paper, we investigate the techniques of replica placement in CDNs with stochastic demands and M/M/1 servers to optimize the overall performance in the network. We first model the demands and the servers as independent Poisson streams and simple M/M/1 queueing systems, respectively. Then, a formal definition and formalization of RP problem will be given. We show that RP problem is NP-complete and propose two heuristic algorithms: Greedy Dropping (GD) and Tabu Search (TS). We conduct abundant simulation experiments to evaluate the performance of our proposed algorithms. According to our simulation results, both of the two algorithms are efficient in finding a feasible solution with high probability. Especially, the TS decreases the average delay of the demands about 50% on average.

Relay assignment significantly affects the performance of cooperative communications. Previous studies in this area have mostly focused on assigning a dedicated relay to each source-destination pair for one-to-one (121) traffic. On the other hand, many-to-one (M21) traffic, which is also common in many situations (for example, several users associate with one access point in a wireless access network such as a WLAN), hasn't been well studied. This paper addresses the shared relay assignment (SRA) problem for M21 traffic. We formulate two new optimization problems: one is to maximize the minimum throughput among all the sources (hereafter called M21-SRA-MMT), and the other is to maximize the total throughput over all the sources while maintaining some degree of fairness (hereafter called M21-SRA-MTT). As both of these problems are NP-hard, we propose two approximation algorithms whose performance factors are 5.828 and 3, respectively, based on the rounding mechanism. Extensive simulation results show that our algorithm for M21-SRA-MMT can significantly improve the minimum throughput compared with existing algorithms, while our algorithm for M21-SRA-MTT can achieve the close-to-optimal performance.

We consider a promising application in Vehicular Cyber-Physical Systems (VCPS) called On-road Ad Delivery (OAD), where targeted advertisements are delivered via roadside APs to attract commuters to nearby shops. Different from most existing works on VANETs which only focused on a single technical area, this work on OAD involves technical elements from human factors, cyber systems and transportation systems since a commuter's shopping decision depends on e.g. the attractiveness of the ads, the induced detour, and traffic conditions on different routes. In this paper, we address a new optimization problem in OAD whose goal is to schedule ad messages and allocate a limited amount of AP bandwidth so as to maximize the system-wide performance in terms of total realized utilities (TRU) of the delivered ads. A number of efficient heuristics are proposed to deal with ad message scheduling and AP bandwidth allocation. Besides largescale simulations, we also present a case study in a more realistic scenario utilizing real traces collected from taxis in the city of Shanghai. In addition, we use a commercial traffic simulator (PARAMICS) to show that our proposed solutions are also useful for traffic management in terms of balancing vehicular traffic and alleviating congestion.

Opportunistic routing (OR) takes advantage of the broadcast nature and spatial diversity of wireless transmission to improve the performance of wireless ad-hoc networks. Instead of using a predetermined path to send packets, OR postpones the choice of the next-hop to the receiver side, and lets the multiple receivers of a packet to coordinate and decide which one will be the forwarder. Existing OR protocols choose the next-hop forwarder based on a predefined candidate list, which is calculated using single network metrics. In this paper, we propose TLG - Topology and Link quality-aware Geographical opportunistic routing protocol. TLG uses multiple network metrics such as network topology, link quality, and geographic location to implement the coordination mechanism of OR. We compare TLG with well-known existing solutions and simulation results show that TLG outperforms others in terms of both QoS and QoE metrics.

In this work, we study spectrum auction problem where each spectrum usage request has spatial, temporal, and spectral features. After receiving bid requests from secondary users, and possibly reserve price from primary users, our goal is to design truthful mechanisms that will either optimize the social efficiency or optimize the revenue of the primary user. As computing an optimal conflict-free spectrum allocation is an NP-hard problem, in this work, we design near optimal spectrum allocation mechanisms separately based on the techniques: derandomized allocation from integer programming formulation, and its linear programming (LP) relaxation. We theoretically prove that 1) our derandomized allocation methods are monotone, thus, implying truthful auction mechanisms; 2) our derandomized allocation methods can achieve a social efficiency or a revenue that is at least $1-\frac{1}{e}$ times of the optimal respectively; Our extensive simulation results corroborate our theoretical analysis.

As users drive through the vehicular networks with high speed, they frequently associate with different access points in succession to maintain connectivity. Without careful designed association control policy, it may lead to large number of handoffs and inefficient connections, which can potentially incur unacceptable delays and poor throughput. In this paper, we propose a new association control scheme with the goal of reducing the frequency of handoffs and improving throughput for all vehicular users. The defined problem HMTE (Handoff Minimization and Throughput Efficiency) is mathematically described as a min-max programming. Since the HMTE problem is NP-hard, we propose an alpha-approximation(alpha >= 2) algorithm CHMTE to resolve it. CHMTE employs a novel method to simplify the original problem to the Minimum cost Maximum flow problem, which is solved in polynomial time. Extensive evaluations show that the proposed algorithm outperforms the existing schemes in terms of the handoff frequency and network throughput.

Virtual multi-input-multi-output (or vMIMO) communication is a promising technology to improve the spatial diversity of wireless networks. Using this mechanism, multiple single-antenna nodes can coordinate their transmissions and receptions so as to reduce power consumption. This paper studies the problem of constructing an energy-efficient topology in wireless sensor networks using vMIMO communication. We first define the problem involving joint optimization of vMIMO, partner selection and topology control. As this problem is NP-Complete, a distributed and heuristic algorithm, called vMIMO topology control (VMTC), is proposed to solve this problem. The algorithm uses an improved binary searching method to obtain an initial power assignment. A local competition method is then adopted to implement the partner selection. At last, we reduce the power consumption of each node by using efficient vMIMO modes. Our theoretical analysis show that this algorithm can achieve an approximate performance of O(1). Our simulations show that VMTC helps to decrease the power consumptions by about 32% compared to the existing algorithms.

In order to save energy of sensors in the process of gathering data and transmitting information, Compressive Sensing (CS), as a novel and effective signal transform technology, has been used gradually in Wireless Sensor Networks (WSNs). In traditional usages of CS techniques in the previous literatures, the sparsities of the signals has to be known beforehand, which is much more importance for their recover results. However, it is difficult to realize precisely the structures of the signals actually in WSNs. Therefore, it is important to further exploit reasonable practicality availability in actual applications. In order to reduce energy of gathering and transmitting of sensors, this paper presents a model of optimized CS based on local regional data and design two corresponding algorithms, which could reconstruct the signals accurately and stably even if their sparsities could not be known in advance. Most important, our algorithms just need once extra transmission by sensors In the paper, we present two reasonable assumptions and then propose spatial-temporal correlation model for optimizing measure matrix of CS. Furthermore, two algorithms are designed in two kinds of situations that data satisfy random distribution or Gauss distribution, which is common in actual applications. According to experiments in the cases of both real data based on actual environments and two kinds of signals above based on simulation environments, our algorithm has been proved to be valuable for actual applications. Especially, when the amount of the sampling is only 15 with the dimension of the data is 256 and the sparsity is unknown, the relative error rate could be less than 6% in actual environments and 3.5% in simulation environments.

Cooperative communication is becoming an attractive technology as it can greatly improve the spatial diversity without additional antennas. This novel communication paradigm can effectively reduce power consumption via multi-node cooperation and resource allocation. This paper studies the energy-efficient node-disjoint multi-path routing for a given source-destination pair by joint route construction, relay assignment and power allocation methods. We first define a new bandwidth-power aware cooperative multi-path routing (BP-CMPR) problem, and formally prove its NP-hardness. The paper then presents a polynomial-time heuristic algorithm CMPR to solve the above problem. The algorithm adopts the Suurballe's method to find k minimal-weight node-disjoint paths from source to destination on a weighted graph. Then, dynamic programming is used to implement relay assignment and power allocation. The theoretical analysis shows that CMPR can reach approximation factors of 2 and \frac{4}{3} for BP-CMPR under the amplify-and-forward and decode-and-forward schemes respectively. The distributed version of the algorithm DCMPR is also presented for this problem. We also prove that both CMPR and DCMPR construct the same cooperative multi-path routing, and show via simulations that the performance of the proposed scheme is more than 15% better than that of a traditional multi-path routing scheme, and close to the optimal result for BP-CMPR in variety of situations.

As Radio Access Technology (RAT) being greatly developed nowadays, Call Admission Control (CAC) is also evolving to provide inter-network connectivity since mobile terminals are able to access multiple networks. In this paper, we propose a pricing-based resource allocation scheme in a heterogeneous wireless environment consisting of several different Radio Access Networks (RANs). We suppose that each RAN caters two kinds of customers, primary and secondary users. Secondary users (SUs) are charged once based on current system state by service provider to join a RAN. We integrate stochastic call admission control (SCAC) with dynamic pricing and formulate them as an infinite horizon average reward problem to maximize the expectation of system revenue in the long run. The optimal pricing policy characteristics are analyzed based on series of computation results under various system conditions. Assessments carried out for a small network model show that a system with relatively small PU blocking punishment gains more profit and the income could be improved by nearly 60% in particular cases.

In CRAHNs (Cognitive Radio Ad Hoc Networks), cognitive users coexist with primary users who have priority in accessing a set of licensed bands. Cognitive users can use those bands only when the primary users don't occupied them. And also, these occupied bands should be vacated immediately as soon as corresponding primary users wake up. Therefore, the more frequently primary user changes its activities, the less stable spectrum availability the cognitive user has. This makes route stability become one of the most concerned problems in CRAHNs. Some works have considered such kind of stability, but the overall performance of the network hasn't been taken into account when multiple cognitive user pairs (also called multi-sessions in the following) have routing requirements. Thus, in this paper, we investigate a joint routing and spectrum scheduling problem, in which multi-sessions exist, and the route stability is required. To solve this problem, a greedy strategy named Distributed Stability Algorithm (DSA) is proposed, which aims to maximize the route stability of the session, whose route stability is the minimal. The message complexity of our algorithm DSA is O((L+2)·Tmax·κ). Here, κ represents the number of transmission pairs, L and Tmaxare both two constants. Numerical results have shown that in a 100-node networks, compared with SAMER, our scheme can increase the route stability by 48.5% on average.

Recently, cooperative communication is shown to be a promising technology to achieve spatial diversity by keeping each node with only one antenna and having a node exploit a relay node's antenna. Most previous works assume that there are multiple source-destination pairs and multiple relay nodes in a network where each node only serves as one role: either transmission node or relay node. However, this assumption will not always hold in practice where each node has its own information to transmit. This paper studies the maximal lifetime scheduling problem for cooperative communication with guaranteed throughput service in a network environment where there are multiple source-destination pairs and each node can serve as both two roles: transmission node and "relay" node. We first analyze the power allocation of optimal lifetime for a single source-destination pair with a bounded throughput in different communication modes, and then design an optimal polynomial-time algorithm to maximize the network lifetime. This algorithm is based on iteration and tries to find a better solution than that before in each iteration. After that, the optimality of this algorithm has been proved formally. The simulation results show that the algorithm can prolong about 199% lifetime than that of direct transmission.

Cooperative communication is shown to be a promising technology to enhance the capacity of wireless transmission without additional equipments. Under this communication paradigm, both relay selection and power allocation significantly affect the overall system performance. Thus, this paper studies the joint power allocation and relay assignment problem to optimize the Max-Min fairness of cooperative network. We first analyze the trade-off between the bandwidth provision and power consumption for different communication schemes. According to the analytic results, a heuristic algorithm PRF is designed to determine the fairness factor with the binary searching. The analyses show that PRF algorithm can obtain the approximate ratio 1- ξ, where ξ is an arbitrarily small positive constant. Meanwhile, this paper also presents another heuristic algorithm JFAP, which uses the offer-and-gain mechanism to reach the Max-Min fairness. The simulation results show that PRF and JFAP algorithms can improve the fairness factor at least 36% and 32% compared with the direct transmission scheme in many situations.

This demonstration presents a mobile surveillance system that is developed at the University of Science and Technology of China and undergoing a technology transition. The goal of this project is to develop a low-cost, promptly-deployable, mobility manageable, location traceable, self-organizing wireless communication and mobile surveillance system, for real-time video surveillance and on-site guard for public security purposes, e.g., public security against terrorism in large-scale gatherings and events.

Recent years, researchers have proposed numerous positioning algorithms for wireless sensor networks, in which range-free schemes are more attractive because of their low-cost advantage. However, in practical circumstance, the raw range-free information (neighboring set and hop-counts et al.) is usually unreliable due to combined factors such as irregular signal patterns, environment noise and so on. To make matters worse, the unreliable localization information will lead to the reduction of localization accuracy. In order to tackle this problem, we propose a Reputation-based Revising Scheme (RRS) to preprocess the raw localization information before applying any positioning algorithm. In RRS, we reevaluate the reliability of raw information by utilizing the neighboring relationship. After being processed through RRS, the raw information is close to the information collected in ideal environment. According to our detailed simulations, we demonstrate that the revised localization information has 27% lower average error rate than the raw one. Based on the revised information, the traditional range-free localization algorithms are capable to achieve higher accuracy.

Because of rapid channel attenuation in lossy environment, there is a severe packet drop loss problem in wireless ad hoc networks. Though MIMO (Multi-Input Multi-Output) technology can alleviate this effect greatly, it will result in higher transmission energy depletion as using more transmit antennas. Lots of schemes have been proposed to reduce such energy cost by transmit antenna selection. However, most of those only consider QoS requirements between neighbor nodes while ignoring QoS requirements for entire network. In this paper, we investigate an energy-efficient transmit antenna selection problem for many-to-one communications, while guaranteeing a certain packet drop loss ratio from any node to the sink. We prove that this problem (Transmit Antenna Selection Problem, TASP) is NP-hard. Thus, a greedy algorithm TASA (Transmit Antenna Selection Algorithm) is proposed to solve this problem. This paper also prove the correctness of the proposed algorithm and the time complexity of TASA algorithm is O(|E|+|V|-MT), where |V| represents the number of nodes, |E| indicates the number of links and MTis the number of transmit antennas on each node, respectively. Our numerical results show that in a 100 node network, TASA can reduce transmission energy cost by 44.3% on average.

Wireless sensor and actor networks (WSANs) have attracted much attention in the recent years. In WSANs, sensor nodes are in charge of the sensing task, while the actor nodes take actions in response to the sensed phenomena or the detected event. In order to execute the correct operations, the applications typically have to process the data or messages from the different sensors in the same order. This paper presents a Consistent Message Ordering (CMO) algorithm, which ensures that messages from the different sensors arrive at the different actors in a consistent order. The significance of the algorithm is fully localized, asynchronous and energy-efficient. We prove the correctness of the algorithm, and analyze the theoretical message complexity. And the experimental results show that CMO algorithm improves the performance at least 60% over TMOS algorithm in many situations.

Relay node placement is an important issue because it greatly affects the performance of wireless ad hoc sensor networks. The pervious works mainly pay attention on placing the minimum number of relay nodes to connect all the sensor nodes. But we find that this placement scheme may result in QoS reduction of the network, such as transmission delay, energy cost, etc. Therefore, this work studies the minimum relay node placement problem to guarantee both the connectivity and geometric spanner properties. We first show that there is no algorithm with the performance O(opt) for this problem, where opt is the minimum number of relay nodes to connect the sensor nodes. Thus, this paper presents an efficient placement algorithm MSGP with O(max{opt, n}) relay nodes, where n is the number of sensor nodes. Specially, if any two sensor nodes cannot communicate directly, the algorithm obtains O(1)-approximation bound. Then, as data gathering is one of the most important operations in sensor networks, we also study the spanner-aware placement problem for this communication scheme. The simulation results show the efficiency of the proposed algorithm. For example, MSGP algorithm can reach the spanner factor 3 with the additional 30% relay nodes compared with MST-based placement algorithm.

In recent years, many localization algorithms have been proposed for wireless sensor networks, in which the hop-count based localization schemes are attractive due to the advantage of low cost. However, these approaches usually utilize discrete integers to calculate the hop-counts between nodes. Such coarse-grained hop-counts make no distinction among one-hop nodes. More seriously, as the hop-counts between nodes increase, the cumulative deviation of hop-counts would become unacceptable. In order to solve this problem, we propose the concept of fine-grained hop-count. It is a kind of float-type hop-count, which refines the coarse-grained one close to the actual distance between nodes. Based on this idea, we propose a fine-grained localization algorithm (AFLA). In AFLA, we first refine the hop-count information to obtain fine-grained hop-counts, then use the Apollonius circle method to achieve initial position estimations, and finally further improve the localization precision through confidence spring model (CSM). We conduct the comprehensive simulations to demonstrate that AFLA can achieve 30% higher average accuracy than the existing hop-count based algorithm in most scenarios and converge much faster than the traditional mass-spring model based scheme. Furthermore, AFLA is robust to achieve an approximate 35% accuracy even in noisy environment with a DOI of 0.4.

Topology control problem has been deeply studied in wireless sensor networks. Some methods try to minimize the maximal or average link interference, which may result in larger accumulative interference than the optimum for some node pairs. In this paper, we define the concept of path interference formally. And the path interference of the topology constructed by LIFE (Low Interference Forest Establisher) algorithm is even about O(D) factor of the optimum, where D is the network diameter. Thus, a localized algorithm, called LDPA, is presented to construct an efficient topology which guarantees the minimal path interference among any node pair. Moreover, we study the trade-off between the path interference and energy cost, thus define the problem of ε -interference. And an efficient algorithm, called ε -PI, is presented to solve it. The paper also theoretically proves that the proposed algorithms can satisfy the certain properties, such as minimal path interference or approximate path interference as well. And the experimental results show that the average path interference of LDPA is less than 1/2 of that of LIFE algorithm.

Mobile wireless sensor network (M-WSN) is wireless sensor network without infrastructure, and includes mobile nodes. According to certain mobility models, mobile nodes move around in the network, and change their locations continually. Because the paths between nodes are not fixed any more, it normally takes nodes longer time to communicate each other. To solve this problem in the M-WSN, this paper presents a new ant-colony routing protocol. The new protocol uses the tracking range of mobile nodes to split the path between source node and destination node into two parts: indefinite path and definite path. The indefinite path is almost the same as the path of probabilistic search in the traditional ant-colony routing protocols. The definite path is the path in the tracking range of mobile nodes. The message from source node is first sent through indefinite path until the tracking range of mobile destination node is reached. Then the message is sent through definite path to reach the destination node. Simulation results showed that our protocol speeded the procedure of message delivery.

This paper studies delay-constraint topology control (DTC) in wireless sensor networks. That is, the delay of transmission is guaranteed through topology control. This problem has been proved to be NP-Completeness, and the previous works are in-adequate and lack of the theoretical analysis. In this

The recent years, achievements in micro-sensor technology and low-power electronics make wireless sensor networks become into realities in applications.In this paper, we basically describe the implementation of the intensive irrigated agriculture monitoring system based on wireless sensor networks.we give some key technologies of wireless sensor networks according as the system performance requirements for this application, longevity and latency.

Wireless sensor networks have posed a number of challenging problems such as localization, deployment and tracking, etc. One of the interesting problems is the calculation of the coverage path for sensor networks. In this paper, we design a localized algorithm to solve the worst coverage problem first introduced by Meguerdichian et al. All nodes cooperate to construct the worst coverage path with their one-hop neighbors’ information. Also, the correctness of the algorithm is proved under the diminishing model formally.