Glaucoma is a leading cause of irreversible blindness worldwide, with asymptomatic early stages often delaying diagnosis and treatment. Early and accurate diagnosis requires integrating complementary information from multiple ocular imaging modalities. However, most existing studies rely on single- or dual-modality imaging, such as fundus and optical coherence tomography (OCT), for coarse binary classification, thereby restricting the exploitation of complementary information and hindering both early diagnosis and stage-specific treatment. To address these limitations, we propose glaucoma lesion evaluation and analysis with multimodal imaging (GLEAM), the first publicly available tri-modal glaucoma dataset comprising scanning laser ophthalmoscopy fundus images, circumpapillary OCT images, and visual field pattern deviation maps, annotated with four disease stages, enabling effective exploitation of multimodal complementary information and facilitating accurate diagnosis and treatment across disease stages. To effectively integrate cross-modal information, we propose hierarchical attentive masked modeling (HAMM) for multimodal glaucoma classification. Our framework employs hierarchical attentive encoders and light decoders to focus cross-modal representation learning on the encoder. The attention module, named multimodal-channel graph attention (MCGA), boosts glaucoma classification performance by emulating two key clinical reasoning steps: first, it uses a multi-head modality gating mechanism to replicate ophthalmologists' confidence scoring of fundus, OCT, and VF modalities; then, MCGA leverages a relational graph attention network to cross-examine structural-functional consistencies of weighted modalities. The experiments on GLEAM demonstrate that tri-modal fusion significantly outperforms single-modal and dual-modal configurations. Moreover, our proposed HAMM achieves superior performance compared with state-of-the-art multimodal learning methods. The dataset and code are publicly available via https://github.com/microewing/HAMM.

In recent years, deep neural networks (DNNs) have been extensively utilized to provide vehicular intelligent services. Given the limited computing capabilities of vehicles, collaborative vehicle-edge DNN inference has emerged as a promising approach. This method partitions the DNN, then distributes parts to the vehicle or the edge,e.g.,roadside unit (RSU), for sequential inferences. However, determining the optimal DNN partition is challenging due to the uneven load distribution of DNN models and varying road traffic conditions. Moreover, vehicle movement can cause loss of inference results if vehicles leave the RSU signal coverage. To this end, we propose a novel online learning-based collaborative DNN Inference frameworkMCI.MCIutilizes multiple RSUs to assist vehicles with sequential inference and ensure reliable data transmission. To reduce learning cost,MCIdesigns a trajectory prediction to analyze vehicle context before making decisions. Then,MCIcombines the classical EXP4 and LinUCB algorithms to learn system dynamics and make effective scheduling decisions. We prove thatMCIachieves a sublinear regret bound of$O(T^{3/4} \sqrt {\log T})$. Extensive experimental results show thatMCIreduces latency by up to 68% and has a lower failure rate, compared to state-of-the-art algorithms.

Mobile edge computing (MEC) can pre-cache deep neural networks (DNNs) near end-users, providing low-latency services and improving users’ quality of experience (QoE). However, caching all DNN models at capacity-limited edge servers is difficult, and the impact of model loading time on QoE remains underexplored. We explore dynamic DNNs by disassembling a complete DNN model into interrelated submodels to enable fine-grained joint optimization of submodel caching and request routing to balance inference precision and loading latency. In this paper, we study the joint dynamic model caching and request routing problem in MEC networks, aiming to maximize user request inference precision under constraints of server resources, latency, and model loading time. We propose CoCaR, an offline algorithm based on linear programming and random rounding that optimizes joint decisions with a provable performance bound. Furthermore, we develop an online extension, CoCaROL, to adapt to dynamic and unpredictable request patterns. The simulation results demonstrate that CoCaR improves the average inference precision for user requests by 40.1% over state-of-the-art baselines. In addition, CoCaR-OL achieves an improvement of at least 32.3% in users’ QoE over competitive baselines.

Federated Learning (FL) enables potentially a large number of clients to collaboratively train a global model with the coordination of a central cloud server without exposing client raw data. However, the FL model convergence performance, often measured by the job completion time, is hindered by two critical factors: non independent and identically distributed (non-IID) data across clients and the straggler effect. In this work, we propose a clustered FL framework,MCFL, to minimize the job completion time by mitigating the influence of non-IID data and the straggler effect while guaranteeing the FL model convergence performance.MCFLbuilds upon a two-stage operation: i) a clustering algorithm constructs clusters, each containing clients with similar computing and communications capabilities to combat the straggler effect within a cluster; ii) a deep reinforcement learning (DRL) algorithm based on soft actor-critic with discrete actions intelligently selects a subset of clients from each cluster to mitigate the impact of non-IID data, and derives the number of intra-cluster aggregation iterations for each cluster to reduce the straggler effect among clusters. We next proposeA-MCFL, a semi-asynchronous clustered framework based on context-aware Multi-Armed Bandit (MAB) client selection algorithm to further reduce job completion time. Extensive testbed experiments are conducted under various configurations to verify the efficacy ofMCFLandA-MCFL. The results show thatMCFLcan reduce the job completion time by up to 70% compared with three state-of-the-art FL frameworks. In addition,A-MCFLhas a further performance improvement overMCFL, achieving an average 64% reduction in job completion time.

Multi-view inference (MVI), which accepts images from multiple viewpoints as input of deep neural networks, is proposed to improve the inference accuracy of conventional single-view models. However, existing mechanisms face challenges in feature fusion and computation efficiency: (1) features from inter-view and intra-view contribute differently to inference, and uniform feature fusion limits MVI accuracy; (2) the sophisticated process and tremendous computational workload of MVI cause a considerable increase in inference latency. This article addresses the above challenges and enables high-accuracy and low-latency MVI for edge intelligence by proposing an end-to-edge synergistic multi-view inference (SMVI) framework. SMVI integrates the f eature f u sion module based on pairwise m utual- a ttention (FUMA), which incorporates the differences between features, enhancing MVI accuracy. To optimize the computation of FUMA-based SMVI, we present a joint optimization algorithm of r esource a llocation and m odel p artition (RAMP) to reduce MVI latency, considering device heterogeneity, dynamic network connection, and resource limitation in heterogeneous edge environments. We developed an SMVI prototype system with heterogeneous embedded GPUs and evaluated its performance in real-world MVI scenarios. Extensive experiments demonstrate that the proposed mechanism achieves a notable MVI accuracy improvement of approximately 4% and accelerates the process by 4.08 × compared to state-of-the-art approaches.

In contrast to static Directed Acyclic Graphs (DAGs) with fixed execution paths, dynamic DAG applications in edge serverless platform have unpredicted function invocations along the paths, complicating the container deployment. Furthermore, the limited resources of edge servers and the cold start problem of containers must also be considered during the task scheduling and container deployment in serverless edge computing. To address these challenges, we propose the Synchronized Deployment and Scheduling for Expected Requests (Sdser) framework, which aims to minimize the total overhead, including the execution time, the transmission time, and the deployment cost. First, we decompose the dynamic DAG paths into individual function hops, modeling each hop as a request triple. We then introduce a real-time function prediction method based on Bayesian estimation to predict requests. Based on the prediction, we propose a Prediction-based Pre-deployment and Scheduling (PPS) algorithm to generate the preliminary solution and predeploy containers accordingly with theoretical guarantee. Finally, for real-time requests that deviate from the predictions, we present the Multi-priority Online Scheduling Adjustment (Mosa) algorithm to adjust the preliminary solution, executing the final task scheduling. Experimental results, using data from real applications, demonstrate that our approach reduces the total overhead by up to 27.05% and the cold start rate by 31.36% compared to existing methods.

Sparsely activated Mixture-of-Experts (MoE) has emerged as a key technique to expand the size of Transformer-based large language models (LLMs) while maintaining low computational costs. However, MoE layers require to route the input data to distributed devices, incurring significant communication latency. Existing studies have primarily focused on alleviating this problem by overlapping computation and communication tasks within a single MoE layer, which fails to achieve sufficient overlap and results in limited performance gains. In this work, we introduce an orthogonal partitioning dimension from existing task-parallel methods by leveraging the autoregressive nature of causal Transformer-based LLMs, i.e. partitioning tasks along the sequence dimension. This provides more flexible and efficient overlaps among tasks from both non-MoE and MoE layers. To this end, we propose an efficient MoE training approach, SP-MoE, with two innovative designs. 1) It incorporates non-MoE layers into the overlapping with not only the current MoE layer but also the preceding MoE layer, thereby facilitating more efficient training; 2) It identifies the optimal combination of pipeline degrees for non-MoE and MoE layers and devises the best scheduling plans for load-imbalanced non-MoE and uniform MoE layers to achieve the goal of minimizing the total training latency. Extensive experiments conducted on two GPU clusters demonstrate that SP-MoE can effectively identify the optimal combination of pipeline degrees and achieve 16.1% - 34.3% reduction in training latency compared to three state-of-the-art MoE systems.

On-device continual learning (CL) enables lifelong and privacy-preserving learning for various edge intelligent applications. Increasing the number of model parameters as new learning tasks emerge is effective in ensuring learning quality but inefficient in memory cost, especially for resource-constrained devices. In this paper, we introduce InfiniCL, the first ondevice CL system that dynamically balances memory cost and learning quality. A key idea behind InfiniCL is elastic continual learning: selectively freezing layers in the expanding model and periodically distilling the model, preventing unbounded memory growth while preserving learning quality for new tasks. This novel CL paradigm opens a new challenging problem: how to decide the memory allocation of the model and data to achieve better learning Quality of Service (QoS) under the limited memory budget? To alleviate this challenge, we further propose a Bayesian Optimization-driven algorithm to jointly optimize layer freezing selection and data-model memory allocation. Evaluations show that InfiniCL outperforms state-of-the-art methods on diverse memory constraints, achieving 5.34-7.15% and 2.72-9.36% higher accuracy on CIFAR-100 and ImageNet-100, respectively.

Serverless computing converts services into multiple containerized functions, greatly enhancing the flexibility of edge applications. To guarantee Service Level Objectives (SLOs), it is common to pre-warm containers for all functions. However, we have observed that requests with a Directed Acyclic Graph (DAG) structure commonly involve only a subset of functions. Pre-warming all containers may lead to over-provisioning, and the fixed optimization strategy for pre-warming becomes ineffective in scenarios where the calling probabilities of functions dynamically change. To overcome the above challenges, we constructed a dynamic DAG model with the consideration of function calling probability, aiming to minimize the request execution time. Based on the model, we proposed an Expectation-based Rounding Optimization (EBRO) algorithm to progressively find the offline optimal container perwarm and deployment strategy with theoretical performance guarantee. Then, we implemented an Online Pre-warming and Tasks Scheduling (OPTS) algorithm to adjust pre-warming and deployment locations based on real-time edge resources and container states. Finally, extensive experiments on a edge cluster show that, compared with baselines, EBRO has the lowest average request execution time and cold start time, with reductions reaching 78.4% and 88.5% respectively. OPTS can potentially reduce the request execution time by up to 25.2%, and reduce the cold start time by a maximum of 80.1 %.

Recently, edge-assisted methods have been proposed as a promising technique to deliver fast and accurate on-device video analytics by partitioning frame data and dispatching them to edge servers for parallel execution. However, the data partition (DP) reduces the detection latency but decreases accuracy since objects may cross the boundaries of adjacent blocks. The effect of DP on the accuracy and latency depends on multiple vital parameters (e.g., target size, density, network, and computing resources) in an unknown and time-varying fashion. Moreover, these parameters are determined by the application scenarios and edge environment, which are uncertain and heterogeneous at the edge. Hence, how to partition frames to strike a balance between accuracy and latency is a nontrivial and intractable problem. To this end, we propose an online learning-based device-edge–cloud collaboration framework, ADPTD, to guide DP at the edge. We propose an optimal task dispatching algorithm (OTD) to minimize detection latency. Then, we propose a multiarmed bandit-based algorithm to pick a DP strategy and invoke OTD to dispatch tasks in each time slot. Theoretical analysis reveals that ADPTD achieves sublinear regret. Extensive experimental results show that ADPTD outperforms the state-of-the-art methods, achieving a latency reduction of up to$2.53\times $and improving accuracy by up to 49.4%.

Federated learning (FL) has emerged as an innovative paradigm designed to protect privacy by enabling collaborative machine learning (ML) model training across multiple data owners (also known as clients) without the need to access clients’ raw data. The majority of existing FL research concentrates on scenarios where a single job necessitates training. In practical applications, multiple FL jobs can simultaneously undergo training using a common pool of clients, a scenario known as multijob FL. However, the problem of FL training with multiple jobs remains open and presents significant challenges of the escalated heterogeneity of jobs and clients, complex tradeoffs between training latency and energy consumption, uncertainty of client quality, and potential linear switching cost associated with client selection. This work aims to jointly optimize training efficiency in terms of latency, energy consumption, and switching cost for multiple jobs in stochastic and dynamic environments. Specifically, we propose a novel multijob FL framework, namedEffI-FL, incorporating three innovative designs: 1) to reduce switching cost, we extend the client selection interval from every round to multiple rounds, called a block, within which client subset switching is prohibited; 2) we employ multiarmed bandit (MAB) methods to measure clients’ latency and energy cost under uncertainty. Additionally, we utilize the virtual queue technique to trace clients’ battery usage patterns. By integrating the above client-side knowledge, we propose an adaptive client selection policy aimed at balancing latency, energy consumption, and battery condition; and 3) given that multiple jobs may compete for the same client, we devise a greedy algorithm to assign each client to a single job. We rigorously prove that the regret of our client selection policy and the cost of our block-wise client subset switching algorithm are both sublinear. Finally, we implementEffI-FLusing PyTorch and conduct experiments demonstrating thatEffI-FLreduces the weighted sum of latency, energy consumption, and switching cost by up to 52.3% compared to four state-of-the-art FL frameworks.

Unmanned aerial vehicles (UAVs) have emerged as a new and flexible paradigm to offer low-latency and diverse mobile edge computing (MEC) services for user equipment (UE). To minimize the service delay, caching is introduced in UAV-assisted MEC networks to bring service contents closer to UEs. However, UAV-assisted MEC is challenged by the heavy communication overhead introduced by service caching and UAV’s limited energy capacity. In this article, we propose an online algorithm,OOA, that jointly optimizes caching and offloading decisions for UAV-assisted MEC networks, to minimize the overall service delay. Specifically, to improve the caching effectiveness and reduce the caching overhead,OOAemploys a greedy algorithm to dynamically make caching decisions based on UEs’ preferences on services and UAVs’ historical trajectories, with the goal of maximizing the probability of successful offloading. To realize the rational utilization of energy from a long-term perspective,OOAdecomposes the online problem into a series of single-slot problems by scaling the UAV’s energy constraint into the objective, and iteratively optimizes UAV trajectory and task offloading at each time slot. Theoretical analysis proves thatOOAconverges to a suboptimal solution with polynomial time complexity. Extensive simulations based on real world data further show thatOOAcan reduce the service delay by up to 33% while satisfying the UAV’s energy constraint, compared to three state-of-the-art algorithms.

DNS misconfiguration can result in severe social and financial consequences. Existing DNS configuration verification tools employ a centralized architecture, where all zone files are collected for verification. This architecture faces significant scalability issues (e.g., the verifier becoming the performance bottleneck and not supporting incremental verification). Inspired by the recent proposal of distributed data plane verification and the resemblance between the network data plane and DNS configuration, we propose to rearchitect DNS configuration verification with a distributed design. Our key insight is that by analyzing the query processing behavior of each DNS zone file in parallel and stitching the results in a symbolic way, we can substantially scale up the verification of DNS configuration. Evaluation shows that an up to 9.51× speed up on a dataset with over 410,000 resource records while having small overhead.

Recent years have witnessed a widespread use of deep neural networks (DNNs) in providing various intelligent services, and vehicular networks are no exception. Given the limited computing capabilities of vehicles, collaborative vehicle-edge DNN inference has emerged as a viable alternative. This approach employs DNN partitioning, where a part of DNN is computed on vehicles, and the other part on the edge, e.g., roadside unit (RSU), aiming to enhance the inference accuracy and reduce the inference latency. In this setting, deriving an optimal DNN partitioning scheme becomes critical, yet challenging given the constant movement of vehicles and the highly dynamic wireless connections. Furthermore, vehicles may move out of the signal coverage of an RSU, making it difficult to receive the inference results. To this end, we propose a two-stage intelligent scheduling framework named Soft Actor-critic for discrete actions (SAC-D) based collaborative DNN inference FramEwork (SAFE). SAFE engages multiple RSUs to assist vehicles in completing inference tasks sequentially and ensuring reliable data transmission. It can learn the dynamic vehicular network and make scheduling decisions to minimize the overall latency of vehicle inference tasks. Extensive experimental results show that SAFE can reduce up to 80% of the overall latency with a lower failure rate, compared to four baselines.

Serverless edge computing is an efficient way to execute event-driven, short-duration, and bursty IoT data processing tasks on resource-limited edge servers, using on-demand resource allocation and dynamic auto-scaling. In this paradigm, function requests are handled in virtualized environments, e.g., containers. When a function request arrives online, if there is no container in memory to execute it, the serverless platform will initialize such a container with non-negligible latency, known as cold start. Otherwise, it results in a warm start with no latency in previous studies. However, based on our experiments, we find there is a remarkable third case called Late-Warm, i.e., when a request arrives during the container initializing, its latency is less than a cold start but not zero. In this paper, we study online container caching in serverless edge computing to minimize the total latency with Late-Warm and other practical issues considered. We propose OnCoLa, a novel$O(T_{c}^{3}/2K)$-competitive algorithm supporting request relaying on multiple edge servers. Here, Tc and$K$are the maximum container cold start latency and the memory size, respectively. Experiments on Raspberry Pi and Jetson Nano with OpenFaaS and faasd using common IoT data processing tasks show that OnCoLa reduces latency by up to 21.38% compared with representative lightweight policies. Extensive simulations on two real-world traces demonstrate that OnCoLa consistently outperforms the state-of-the-art container caching algorithms and reduces the latency by 27.8%.

Recent advancements in federated learning have shown promising results in resource-constrained edge environments. However, with mobile devices becoming more capable of collecting data, individual client models are unable to utilize the available data due to their devices’ limited support for complex model training. Conversely, non-portable devices possess substantial computational resources, but the data they autonomously collect is insufficient to support the training of complex models. In this paper, we introduce HASFL, a novel split federated learning (SFL) framework that supports model structure heterogeneity across devices and decouples computation from the model. Through circular group training, HASFL enables mobile devices to utilize complex models to train their own data while ensuring that non-portable devices harness the data collected by mobile users. HASFL effectively addresses the challenges of applying advanced machine learning models in resource-constrained environments, leveraging the collective power of distributed devices without compromising data security. We implemented a circular group allocation method using the online algorithm to ensure cooperative training among heterogeneous models within each group while minimizing training time. In addition, we have conducted experiments to evaluate the performance of HASFL on various datasets and model architectures and analyzed the communication overhead of HASFL. The experimental results demonstrate that HASFL supports the training of heterogeneous models and significantly enhances the model’s accuracy with a relatively small increase in communication overhead.

Compressed edge DNN models usually experience decreasing model accuracy when performing inference due to data drift. To maintain the inference accuracy, retraining models with continuous learning is usually employed in the edge. However, online edge DNN inference with continuous learning faces new challenges. First, introducing retraining jobs leads to resource competition with the existing edge inference tasks, which will affect the inference latency. Second, retraining jobs and inference tasks exhibit significant differences in workload and latency requirements. These two jobs cannot adopt the same scheduling policy. To overcome the challenges, we propose an Online scheduling algorithm for INference with Continuous learning (OINC). OINC minimizes the weighted sum of the latency of inference tasks and the completion time of retraining jobs with limited edge resources, while ensuring the satisfaction of the inference task’s service level objective (SLO) and meeting the deadlines of retraining jobs. OINC first reserves a portion of resources to complete all current inference tasks and allocates the remaining resources to retraining jobs. Subsequently, based on the reserved resource ratio, OINC invokes two sub-algorithms to select edges and allocate resources for each inference task and retraining job respectively. Compared with six state-of-the-art algorithms, OINC can reduce the weighted sum by up to 23.7%, and increase the success rate by up to 35.6%.

Erasure coding is a storage-efficient redundancy scheme for modern key–value (KV) stores, storing stripes of data and parity chunks in multiple nodes. To accommodate the highly skewed and time-varying nature of the workload, KV stores require erasure code that dynamically optimizes its parameters, known as redundancy converting. Stretched Reed–Solomon (SRS) and elastic Reed–Solomon (ERS) codes represent promising candidates for meeting such requirements. However, both SRS and ERS are limited to RS$(d,r)\to $RS$(d^{\prime },r^{\prime })$converting, where$d^{\prime }>d,r^{\prime }=r$, failing to fully meet actual needs. This work presents an advanced ERS code (AERS code), which builds upon flexible encoding matrices and placement strategies, serving different types of redundancy converting, and minimizing converting traffic. We further prove that the AERS code is an optimal redundancy converting solution that achieves the theoretical lower bound on data traffic during redundancy converting while guaranteeing node-level fault tolerance. We evaluate the AERS code through both mathematical analysis and experiments. In the mise-en-scène of its state-of-the-art alternatives, AERS stands out by reducing network traffic up to 50%–85.7% while accelerating redundancy converting.

Hierarchical federated learning (HFL) has recently emerged as a more practical machine learning (ML) paradigm, which enables edge servers (ESs) in close proximity to conduct partial model aggregation. Despite its utility, local training and model aggregation incur considerable computation and communication time. client selection (CS) has proven effective for minimizing latency. However, CS faces the following challenges in hierarchical federated learning (HFL). First, the accessible clients, computation resources and network bandwidth are time-varying and unpredictable. Second, certain dynamics can only be observed after the decisions are made. Third, multiple ESs face different unknown clients, increasing the difficulty of selecting clients in an online manner. Finally, resource usage may be excessively violated during the training process. Existing HFL researches are insufficient to tackle these challenges. This work proposes a multi- ESs CS framework (MCS), which is based on multiarmed bandit (MAB) technique. MCS aims to reduce the cumulative computation and communication time, using two algorithms: 1) an online learning-based CS algorithm (OCA) makes the CS decisions for each ES, based on empirical learning results; and 2) a randomized rounding algorithm (RRA) converts fractional decisions obtained by OCA into binary solutions. Theoretically, MCS can enjoy the sublinear regret and violation compared to the optimal strategy. Practically, extensive experiments on real-world data sets demonstrate the empirical superiority of MCS over multiple state-of-the-art algorithms in minimizing cumulative latency.

The emergence of edge intelligence has made smart IoT services (e.g.,video/audio surveillance, autonomous driving and smart city) a reality. To ensure the quality of service, edge service providers train unbiased models of distributed machine learning jobs over the local datasets collected by edge networks, and usually adopt the parameter server (PS) architecture. However, the training ofunbiased distributed learning(UDL) depends on geo-distributed data and edge resources, bringing a new challenge for service providers: how to effectively schedule and price UDL jobs such that the long-term system utility (i.e.,social welfare) can be maximized. In this paper, we propose an online auction-based scheduling algorithmEris, which determines the data workload, the number and the placement of concurrent workers and PSs for each arriving UDL job, and dynamically prices limited edge resources based on current resource consumption.Erisapplies a primal-dual framework which calls an efficient dual subroutine to schedule UDL jobs, achieving a good competitive ratio and pseudo-polynomial time complexity. To evaluate the effectiveness ofEris, we implement both a testbed and a large-scaled simulator. The results demonstrate thatErisoutperforms and achieves up to 44% more social welfare compared to state-of-the-art algorithms in today's cloud system.

To mitigate Distributed Denial-of-Service (DDoS) attacks towards enterprise networks, we study the problem of scheduling DDoS traffic through on-premises scrubbing at the local edge and on-demand scrubbing in the remote clouds. We model this problem as a nonlinear mixed- integer program, which is characterized by the inputs of arbitrary dynamics and the trade-offs between staying at suboptimal scrubbing locations and using different best locations with switching overhead. We first design a prediction-oblivious online algorithm which consists of a carefully-designed fractional algorithm to pursue the long-term total cost minimization but avoid excessive switching overhead over time, and a randomized rounding algorithm to derive the flow-based, integral decisions. We next design a prediction-aware online algorithm which leverages the predicted inputs and can make even better scheduling decisions through invoking our prediction-oblivious online algorithm and improving its solutions via re-solving the original problem slice over each prediction window. We further extend our study to prioritize local scrubbing, and adapt our algorithms to this case correspondingly. Then, we rigorously prove the worst-case, constant competitive performance guarantees of our online algorithms. Finally, we conduct extensive evaluations and validate the superiority of our approach over multiple existing alternatives approaches.

Unmanned aerial vehicles (UAVs) have emerged as a promising technology to provide low-latency mobile edge computing (MEC) services. To fully utilize the potential of UAV-assisted MEC in practice, both technical and economic challenges need to be addressed: how to optimize UAV trajectory for online task offloading and incentivize the participation of UAVs without compromising the privacy of user equipment (UE). In this work, we consider unique features of UAVs,i.e.,high mobility as well as limited energy and computing capacity, and propose privacy-preserving auction frameworks, Ptero, to schedule offloading tasks on the fly and incentivize UAVs’ participation. Specifically, Ptero first decomposes the online task offloading problem into a series of one-round problems by scaling the UAV’s energy constraint into the objective. To protect UE’s privacy, Ptero calculates UAV’s coverage based on subset-anonymity. At each round, Ptero schedules UAVs greedily, computes remuneration for working UAVs, and processes unserved tasks in the cloud to maximize the system’s utility ( i.e., minimize social cost). Theoretical analysis proves that Ptero achieves truthfulness, individual rationality, computational efficiency, privacy-preserving and a nontrivial competitive ratio. Trace-driven evaluations further verify that Ptero can reduce the social cost by up to$116\%$compared with four state-of-the-art algorithms.

As the applications of AI proliferate, it is critical to increase the throughput of online DNN inference services. Multi-process service (MPS) improves the utilization rate of GPU resources by spatial-sharing, but it also brings unique challenges. First, interference between co-located DNN models deployed on the same GPU must be accurately modeled. Second, inference tasks arrive dynamically online, and each task needs to be served within a bounded time to meet the service-level objective (SLO). Third, the problem of fragments has become more serious. To address the above three challenges, we propose anIntelligentScheduling orchestrator for multi-GPU inference servers with spatio-temporalSharing (InSS), aiming to maximize the system throughput.InSSexploits two key innovations: i) An interference-aware latency analytical model which estimates the task latency. ii) A two-stage intelligent scheduler is tailored to jointly optimize the model placement, GPU resource allocation and adaptively decides batch size by coupling the latency analytical model. Our prototype implementation on four NVIDIA A100 GPUs shows thatInSScan improve the throughput by up to 86% compared to the state-of-the-art GPU schedulers, while satisfying SLOs. We further show the scalability ofInSSon 64 GPUs.

Edge intelligence is an emerging paradigm that leverages edge computing to pave the last mile delivery of artificial intelligence. While pilot efforts on edge intelligence have mostly focused on the performance and power issues, the sustainability dilemma along with the upcoming carbon peaking and neutrality era has largely been overlooked. To green edge intelligence, we propose a carbon-aware online control framework (CARE) in this paper. CARE colocates learning and inference tasks within an edge node and dynamically adapts their configurations based on the temporal variation of carbon intensity and renewable energy availability. With such a colocation setup, CARE aims to minimize the long-term inference accuracy loss under the long-term carbon emission cap. The underlying long-term optimization problem is nontrivial since it involves uncertain information (e.g., renewable energy availability) and is NP-hard. To address these dual challenges, CARE first designs an online learning module to make fractional decisions by learning from previous system dynamics and configuration adaptation results. Then, CARE further designs a randomized rounding module, which converts the fractional decision into integer without violating the long-term carbon emission cap. The effectiveness of CARE is verified by rigorous theoretical analysis and extensive trace-driven simulations.

Federated learning (FL) is a new paradigm for privacy-preserving learning. This is particularly appealing in the mobile edge network (MEN), in which devices collectively train a global model with their own set of data. It is, however, routinely difficult for FL algorithms to satisfy different training task preferences in terms of the total latency and model accuracy due to a number of factors including the straggler effect, data heterogeneity, communication bottleneck and device mobility. To this end, we propose an Adaptive Semi-asynchronous Federated Learning (ASFL) framework, which adaptively balances the total latency and model accuracy according to the task preferences in MEN. Specifically, ASFL conducts a two-stage operation: i) Device selection stage. Each global round selects a set of devices that can maximize the model accuracy to eliminate data heterogeneity and communication bottlenecks; ii) Training stage. We first define a latency-accuracy objective value to model the balance between the latency and accuracy. Then in each global round, we use a deep reinforcement learning (DRL) algorithm based on soft actor-critic with discrete actions to intelligently derive the number of picked devices (i.e., participants in the current global aggregation) and the lag tolerance at each global round to maximize the latency-accuracy objective value. Extensive experiments show that ASFL can improve the latency-accuracy objective value by up to 94% compared with three state-of-the-art FL frameworks.

The separation of compute and storage in modern cloud services eases the deployment of general applications. However, with the development of accelerators such as GPU/TPU, Deep Learning (DL) training is suffering from potential IO bottlenecks when loading data from storage clusters. Therefore, DL training jobs need to either create local cache in the compute cluster to reduce the bandwidth demands or scale up the IO capacity with higher bandwidth cost. It is full of challenges to choose the best strategy due to the heterogeneous cache/IO preference of DL models, shared dataset among multiple jobs and dynamic GPU scaling of DL training. In this work, we exploit the job characteristics based on their training throughput, dataset size and scalability. For fixed GPU allocation of jobs, we propose CBA to minimize the training cost with a closed-form approach. For clusters that can automatically scale the GPU allocations of jobs, we extend CBA to AutoCBA to support diverse job utility functions and improve social welfare within a limited budget. Extensive experiments with production traces validate that CBA and AutoCBA can reduce IO cost and improve total social welfare by up to 20.5% and 2.27×, respectively, over the state-of-the-art schedulers for DL training.

Federated Learning (FL) enables potentially a large number of clients to collaboratively train a global model with the coordination of a central cloud server without exposing client raw data. However, the FL model convergence performance, often measured by the job completion time, is hindered by two critical factors: non independent and identically distributed (non-IID) data across clients and the straggler effect. In this work, we propose a clustered FL framework, MCFL, to minimize the job completion time by mitigating the influence of non-IID data and the straggler effect while guaranteeing the FL model convergence performance. MCFL builds upon a two-stage operation: i) a clustering algorithm constructs clusters, each containing clients with similar computing and communications capabilities to combat the straggler effect within a cluster; ii) a deep reinforcement learning (DRL) algorithm based on soft actor-critic with discrete actions intelligently selects a subset of clients from each cluster to mitigate the impact of non-IID data, and derives the number of intra-cluster aggregation iterations for each cluster to reduce the straggler effect among clusters. Extensive testbed experiments are conducted under various configurations to verify the efficacy of MCFL. The results show that MCFL can reduce the job completion time by up to 70% compared with three state-of-the-art FL frameworks.

Live video streaming is increasingly popular for its rich content and real-time interactions, but its demand for bandwidth has put a heavy burden on backbone networks. To save bandwidth, recent studies have proposed neural-enhanced live video streaming that deploys deep neural networks (DNNs) for video super-resolution (VSR) on end devices or nearby edge devices to enhance video quality by taking low-resolution frames as input and producing high-resolution output frames. In this solution, the high computational demands of high-quality VSR DNNs make them difficult to support on single end or edge device, necessitating the use of distributed resources in edge facilities. However, the distributed deployment of high-quality VSR DNNs for low-latency inference remains challenging due to the inherent data dependencies of VSR DNNs and the heterogeneity and dynamics of edge facilities. In this paper, we present WAEVSR, a novel collaborative neural-enhanced live video super-resolution system that enables effective leverage of distributed resources to maximize the latency-bounded quality in wide-area MEC environments. WAEVSR consists of two key components: 1) It deploys a parallel-friendly video super-resolution DNN among edge devices, 2) with an inference controller based on the variable-size sliding window to balance the latency and quality of distributed inference in the heterogeneous and dynamics MEC environment. Prototype-based evaluation shows that WAEVSR can achieve 2.5 × lower end-to-end latency than traditional super-resolution serving with a 0.01 drop in SSIM score. The case study also demonstrates its higher stability on latency than vanilla distributed MEC deployment.

Unmanned Aerial Vehicles (UAV)-assisted Mobile Edge Computing (MEC) has recently emerged as a novel and adaptable approach to delivering low-latency services to User Equipments (UEs). Many smart applications, e.g., recognizing illegal buildings based on image processing, involve dependent subtasks where the output from some subtasks serves as input for others and require to respond to UEs in real-time. In UAV-assisted MEC, the latency in task completion can be significantly impacted by the trajectory of the UAV and the offloading order of dependent tasks. How to plan the trajectories of UAVs and offload tasks with dependencies to UAVs is a challenging problem. In this paper, we introduce an online framework, JTDO, that Jointly considers UAV Trajectory and Dependent task Offloading to minimize the response latency. Specifically, to maximize the number of tasks offloaded to UAVs, JTDO adopts an efficient deployment algorithm to dynamically update UAV trajectory. For dependent task offloading, JTDO first models dependent tasks as directed acyclic graphs and then reformulates the dependent task offloading problem as a Markov decision process. Finally, JTDO proposes a proximal policy optimization based deep reinforcement learning algorithm to learn the optimal offloading strategy. Simulation results show that JTDO quickly converges under various scenarios and reduces the latency by up to 37% compared with five state-of-the-art algorithms.

Decentralized federated learning across edge networks can leverage blockchain with consensus mechanisms for training information exchange among participants over costly and distrustful wide-area networks. However, it is non-trivial to optimally operate the blockchain to support decentralized federated learning due to the complex cost structure of blockchain operations, the balance between blockchain overhead and model convergence, and the dynamics and uncertainties of edge network environments. To overcome these challenges, we formulate a non-linear time-varying integer program that jointly places blockchain nodes and determines the number of training iterations to minimize the long-term blockchain computation and communication cost. We then design an online polynomial-time approximation algorithm that decomposes the problem and solves the subproblems alternately on the fly using only estimated inputs. We rigorously prove the sublinear regret of our approach. We further implement our approach with a prototype system, and conduct extensive trace-driven experiments to validate the superiority of our approach over other alternatives.

Nowadays distributed machine learning (ML) jobs usually adopt a parameter server (PS) framework to train models over large-scale datasets. Such ML job deploys hundreds of concurrent workers, and model parameter updates are exchanged frequently between workers and PSs. Current practice is that workers and PSs may be placed on different physical servers, bringing uncertainty in jobs’ runtime. Existing cloud pricing policy often charges a fixed price according to the job’s runtime. Although this pricing strategy is simple to implement, such pricing mechanism is not suitable for distributed ML jobs whose runtime is stochastic and can only be estimated according to its placement after job admission. To supplement existing cloud pricing schemes, we design a dynamic pricing and placement algorithm, DPS, for distributed ML jobs. DPS aims to maximize the cloud service provider’s profit, which dynamically calculates unit resource price upon a job’s arrival, and determines job’s placement to minimize its runtime if offered price is accepted to users. Our design exploits the multi-armed bandit (MAB) technique to learn unknown information based on past sales. DPS balances the exploration and exploitation stage, and selects the best price based on the reward which is related to job runtime. Our learning-based algorithm can increase the provider’s profit by 200%, and achieves a sub-linear regret with both the time horizon and the total job number, compared to benchmark pricing schemes. Extensive evaluations using real-world data also validates the efficacy of DPS.

To save cost, companies usually train machine learning (ML) models on a shared multi-tenant system. In this cooperative environment, one of the fundamental challenges is how to distribute resources fairly among tenants such that each tenant is satisfied. A satisfactory allocation policy needs to meet the following properties. First, the performance of each tenant in the shared cluster is at least the same as that in its exclusive cluster partition. Second, no tenant can get more benefits by lying about its demands. Third, tenants cannot use the idle resources of others for free. Moreover, the resource allocation for ML workloads should avoid costly migration overhead. To this end, we propose a three-layer scheduling framework Astraea: i) a batch scheduling framework groups unprocessed jobs into multiple batches; ii) a round-by-round algorithm enables tenants to reserve their share of resources and schedule jobs in a non-preemptive manner; iii) one-round algorithm based on primal-dual approach and posted pricing framework, which encourages tenants to report truthful demands. Astraea is proven to achieve performance guarantee and some desirable properties of sharing, including sharing incentive, strategy-proofness and gain-as-you-contribute fairness. Extensive trace-driven simulations show Astraea advances in both fairness and cluster efficiency compared to three state-of-the-art baselines.

Distributed machine learning (ML) has played a key role in today's proliferation of AI services. A typical model of distributed ML is to partition training datasets over multiple worker nodes to update model parameters in parallel, adopting aparameter serverorAllReducearchitecture. ML training jobs are typically resource elastic, completed using various time lengths with different resource configurations. A fundamental problem in a distributed ML cluster is how to explore the demand elasticity of ML jobs and schedule them with different resource configurations, such that the utilization of resources is maximized and average job completion time is minimized. To address it, we propose an online scheduling algorithm to decide the execution time window, the number and the type of concurrent workers and parameter servers for each job upon its arrival, with a goal of minimizing the weighted average completion time. Our online algorithm consists of (i) an online scheduling framework that groups unprocessed ML training jobs into a batch iteratively, and (ii) a batch scheduling algorithm that configures each ML job to maximize the total weight of scheduled jobs in the current iteration. Our online algorithm guarantees a good parameterized competitive ratio with polynomial time complexity. Extensive evaluations using real-world data demonstrate that it outperforms state-of-the-art schedulers in today's AI cloud systems.

Federated Learning (FL) is a new distributed machine learning (ML) approach which enables thousands of mobile devices to collaboratively train artificial intelligence (AI) models using local data without compromising user privacy. Although FL represents a promising computing paradigm, such training process can not be fully realized without an appropriate economic mechanism that incentivizes the participation of heterogeneous clients. This work targets social cost minimization, and studies the incentive mechanism design in FL through a procurement auction. Different from existing literature, we consider a practical scenario of FL where clients are selected and scheduled at different global iterations to guarantee the completion of the FL job, and capture the distinct feature of FL that the number of global iterations is determined by the local accuracy of all participants to balance between computation and communication. Our auction framework$A_{FL}$first decomposes the social cost minimization problem into a series of winner determination problems (WDPs) based on the number of global iterations. To solve each WDP,$A_{FL}$invokes a greedy algorithm to determine the winners, and a payment algorithm for computing remuneration to winners. Finally,$A_{FL}$returns the best solution among all WDPs. We carried out theoretical analysis to prove that$A_{FL}$is truthful, individual rational, computationally efficient, and achieves a near-optimal social cost. We further extend our model to consider multiple FL jobs with corresponding budgets and propose another efficient algorithm$A_{FL-M}$to solve the extended problem. We conduct large-scale simulations based on the real-world data and testbed experiments by adopting FL frameworks FAVOR and CoCoA. Simulation and experiment results show that both$A_{FL}$and$A_{FL-M}$can reduce the social cost by up to 55% compared with state-of-the-art algorithms.

The accelerating convergence of artificial intelligence and edge computing has sparked a recent wave of interest in edge intelligence. While pilot efforts focused on edge DNN inference serving for a single user or DNN application, scaling edge DNN inference serving to multiple users and applications is however nontrivial. In this paper, we propose an online optimization framework EdgeAdaptor for multi-user and multi-application edge DNN inference serving at scale, which aims to navigate the three-way trade-off between inference accuracy, latency, and resource cost via jointly optimizing the application configuration adaption, DNN model selection and edge resource provisioning on-the-fly. The underlying long-term optimization problem is difficult since it is NP-hard and involves future uncertain information. To address these dual challenges, we fuse the power of online optimization and approximate optimization into a joint optimization framework, via i) decomposing the long-term problem into a series of single-shot fractional problems with a regularization technique, and ii) rounding the fractional solution to a near-optimal integral solution with a randomized dependent scheme. Rigorous theoretical analysis derives a parameterized competition ratio of our online algorithms, and extensive trace-driven simulations verify that its empirical value is no larger than 1.4 in typical scenarios.

5G and Internet of Things stimulate smart applications of edge computing, such as autonomous driving and smart city. As edge computing power increases, more and more machine learning (ML) jobs will be trained in the edge-cloud network, adopting the parameter server (PS) architecture. Due to the distinct features of the edge (low-latency and the scarcity of resources), the cloud (high delay and rich computing capacity) and ML jobs (frequent communication between workers and PSs and unfixed runtime), existing cloud job pricing and scheduling algorithms are not applicable. Therefore, how to price, deploy and schedule ML jobs in the edge-cloud network becomes a challenging problem. To solve it, we propose an auction-based online framework DPS. DPS consists of three major parts: job admission control, price function design and scheduling orchestrator. DPS dynamically prices workers and PSs based on historical job information and real-time system status, and decides whether to accept the job according to the deployment cost. DPS then deploys and schedules accepted ML jobs to pursue the maximum social welfare. Through theoretical analysis, we prove that DPS can achieve a good competition ratio and truthfulness in polynomial time. Large-scale simulations and testbed experiments show that DPS can improve social welfare by at least$95\%$, compared with benchmark algorithms in today's cloud system.

Due to vehicle mobility, the topology of Vehicle Ad-hoc Networks (VANETs) may change dynamically. High mobility, limited bandwidth, and dynamic network topology pose challenges for communication in the Internet of Vehicles (IoVs). Literature works have attempted to promote efficient (e.g., lower end-to-end latency) message forwarding. However, due to the uncertain direction of message forwarding and vehicle mobility, they suffer from unreachable destinations and unstable connections. This paper explores the efficient method of message forwarding to alleviate network congestion in IoVs. We propose a Spatio-Temporal domain Autonomous Load Balancing (STALB) routing protocol. Specifically, STALB is a trajectory-based method for controlling the direction of message forwarding. STALB can significantly reduce the end-to-end latency and overload ratio, since it considers the local status of network relay devices (i.e., buffer score, congestion status) from the spatio-temporal domain. Then, we present a path reconstruction mechanism, which ensures that messages are forwarded to destinations within limited Time-To-live (TTL). Extensive simulation results show that STALB significantly outperforms other baseline methods (BSaW, TDOR, and TBHGR) regarding overhead ratio, average delivery latency, and average buffer time. Especially, the delivery rate of STALB can reach 99.9% under the sparse network scenario (4,500 messages), at least 0.7% higher than other baseline methods. Similarly, the average delivery delay of STALB is at least 84.31% lower than that of other baseline methods under the dense network scenario (18,000 messages).

Federated Learning (FL) is a secure distributed learning paradigm, which enables potentially a large number of devices to collaboratively train a global model based on their local dataset. FL exhibits two distinctive features in job requirement and client participation, where FL jobs may have different training criteria, and clients possess diverse device capabilities and data characteristics. In order to capture such heterogeneities, this paper proposes a new FL framework, Hca, which aims to strike a balance between the job completion time and model accuracy. Specifically, Hca builds upon a number of innovations in the following three phases: i) pre-estimation: we first derive the optimal set of parameters used in training in terms of the number of training rounds, the number of iterations and the number of participating clients in each round; ii) client selection: we design a novel device selection algorithm, which selects the most effective clients for participation based on both client historical contributions and data effectiveness; iii) model aggregation: we improve the classic FedAvg algorithm by integrating the model loss reduction in consecutive rounds as a weighted factor into aggregation computation. To evaluate the performance and effectiveness of Hca, we conduct theoretical analysis and testbed experiments over an FL platform FAVOR. Extensive results show that Hca can improve the job completion time by up to 34% and the model accuracy by up to 9.1%, and can reduce the number of communication rounds required in FL by up to 75% compared with two state-of-the-art FL frameworks.

Federated learning (FL) has emerged as a new paradigm that enables distributed mobile devices to learn a global model collaboratively. Since mobile devices (a.k.a, clients) exhibit diversity in model training quality, client selection (CS) becomes critical for efficient FL. CS faces the following challenges: First, the client’s availability, the training data volumes, and the network connection status are time-varying and cannot be easily predicted. Second, clients for training and the number of local iterations would seriously affect the model accuracy. Thus, selecting a subset of available clients and controlling local iterations should guarantee model quality. Third, renting clients for model training needs cost. It is necessary to dynamically administrate the use of the long-term budget without knowledge of future inputs. To this end, we propose a federated edge learning (FedL) framework, which can select appropriate clients and control the number of training iterations in real-time. FedL aims to reduce the completion time while reaching the desired model convergence and satisfying the long-term budget for renting clients. FedL consists of two algorithms: i) the online learning algorithm makes CS and iteration decisions according to historic learning results; ii) the online rounding algorithm translates fractional decisions derived by the online learning algorithm into integers to satisfy feasibility constraints. Rigorous mathematical proof reveals that dynamic regret and dynamic fit have sub-linear upper-bounds with time for a given budget. Extensive experiments based on realistic datasets suggest that FedL outperforms multiple state-of-the-art algorithms. In particular, FedL reduces at least 38% completion time compared with others.

As a new paradigm, edge caching is deemed an effective alternative by fetching contents at the network edge. However, designing an efficient caching mechanism is challenging. First, the content library is a dynamic set rather than a static set. Second, the content may be prevalent in different small base stations (SBSs), resulting in different rewards. Thus, the above reasons require each SBS could learn its caching decisions in a multi-SBSs network. Existing reinforcement learning algorithms either fail to consider the non-stationary environment or do not provide any performance guarantee. Thus, previous algorithms work well no longer. This work proposes a multi-agent multi-armed bandit caching framework, MAMAB-C, which navigates SBSs to cache contents in a distributed manner. Specifically, we formulate the multi-SBSs caching optimization problem as an online integer linear program (ILP) and convert it into a multi-agent multi-armed bandit (MAMAB) problem with resource constraints. MAMAB-C can realize the sub-linear metric property and significantly outperform multiple state-of-the-art algorithms.

Mobile Edge Computing (MEC) is a new paradigm where mobile users can offload computation tasks to the nearby MEC server to reduce their resource consumption. Some works have pointed out that the true amount of offloaded tasks may reveal the sensitive information (e.g., device usage pattern and location information) of users, and proposed several privacy-preserving offloading mechanisms. However, to the best of our knowledge, none of them can provide strict and provable privacy guarantee. In this paper, we focus on the privacy leakage issue in computation offloading in MEC with a honest-but-curious server, and propose a novel online privacy-preserving computation offloading mechanism, called OffloadingGuard, to generate efficient offloading strategies for users in real time, which provide strict user privacy guarantee while minimizing the total cost of task computation. To this end, we design a deep reinforcement learning-based offloading model which allows each user to adaptively determine the satisfactory perturbed offloading ratio according to the time-varying channel state at each time slot to achieve trade-off between user privacy and computation cost. In particular, to strictly protect the true amount of offloaded tasks and prevent the untrusted MEC server from revealing mobile users’ privacy, a range-constrained Laplace distribution is designed to obfuscate the original offloading ratio of each user and restrict the perturbed offloading ratio in a rational range. OffloadingGuard is proved to satisfy ϵ-differential privacy, and extensive experiments demonstrate its effectiveness.

The emergence of unmanned aerial vehicles (UAVs) extends the mobile edge computing (MEC) services in broader coverage to offer new flexible and low-latency computing services for user equipment (UE) in the era of 5G and beyond. One of the fundamental requirements in UAV-assisted mobile wireless systems is the low latency, which can be jointly optimized with service caching and task offloading. However, this is challenged by the communication overhead involved with service caching and constrained by limited energy capacity. In this work, we present a comprehensive optimization framework with the objective of minimizing the service latency while incorporating the unique features of UAVs. Specifically, to reduce the caching overhead, we make caching placement decision every T slots (specified by service providers), and adjust UAV trajectory, user equipment or UE-UAV association, and task offloading decisions at each time slot under the constraints of UAV’s energy and resource capacity. By leveraging Lyapunov optimization approach and dependent rounding technique, we design an alternating optimization-based algorithm, named TJSO, which iteratively optimizes caching and offloading decisions. Theoretical analysis proves that TJSO converges to the near-optimal solution in polynomial time. Extensive simulations further verify that our proposed solution can significantly reduce the service delay for UEs while maintaining low energy consumption when compared to the three state-of-the-art baselines.

Clustered Federated Learning (FL) addresses heterogeneous objectives from different client groups, by capturing the intrinsic relationship between data distributions of clients. This work aims to minimize the completion time of clustered FL training while guaranteeing convergence, given the following challenges. First, clients’ data distributions are not static since their interests are usually time-varying. Obsolete data may incur training failures, requiring detection of distribution changes at runtime. Second, even with the same distribution, client datasets may have different contributions to model accuracy. Besides, the training data typically arrive at clients dynamically, which brings uncertainties to assessing the quality of client data. Third, the execution environments of clients and networks are often unstable and stochastic, leading to uncertainties in calculating computation and communication time. Given the above challenges, we propose Acct with two innovations: i) change detection: we first model the time-varying interests of clients as piecewise stationary based on practical observations, then apply generalized likelihood ratio detectors to FL for detecting changes in client distributions; ii) client selection: we adopt the multi-armed bandit (MAB) technique to account for the uncertainties in measuring data quality, computation and communication time. Based on the upper confidence bound (UCB) method, we construct a novel “double UCB” policy to adaptively select clients with high data quality and low computation and communication overhead. We rigorously prove the convergence of Acct and sub-linear regret regarding the proposed client selection policy. Finally, we implement Acct using PyTorch and conduct experiments showing that Acct reduces the completion time by almost 18.2% compared with three state-of-the-art FL frameworks.

Unmanned aerial vehicles (UAVs) have emerged as a promising technology to provide low-latency mobile edge computing (MEC) services. To fully utilize the potential of UAV-assisted MEC in practice, both technical and economic challenges need to be addressed: how to optimize UAV trajectory for online task offloading and incentivize the participation of UAVs without compromising the privacy of user equipment (UE). In this work, we consider unique features of UAVs, i.e., high mobility as well as limited energy and computing capacity, and propose a privacy-preserving auction framework, Ptero, to schedule offloading tasks on the fly and incentivize UAVs' participation. Specifically, Ptero first decomposes the online task offloading problem into a series of one-round problems by scaling the UAV's energy constraint into the objective. To protect UE's privacy, Ptero calculates UAV's coverage based on subset-anonymity. At each round, Ptero schedules UAVs greedily, computes remuneration for working UAVs, and processes unserved tasks in the cloud to maximize the system's utility (i.e., minimize social cost). Theoretical analysis proves that Ptero achieves truthfulness, individual rationality, computational efficiency, privacy preserving and a non-trivial competitive ratio. Trace-driven evaluations further verify that Ptero can reduce the social cost by up to 116% compared with four state-of-the-art algorithms.

To mitigate Distributed Denial-of-Service (DDoS) attacks towards enterprise networks, we study the problem of scheduling DDoS traffic through on-premises scrubbing at the local edge and on-demand scrubbing in the remote clouds. We model this problem as a nonlinear mixed-integer program, which is characterized by the inputs of arbitrary dynamics and the trade-offs between staying at suboptimal scrubbing locations and using different best locations with switching overhead. We first design a prediction-oblivious online algorithm which consists of a carefully-designed fractional algorithm to pursue the long-term total cost minimization but avoid excessive switching overhead over time, and a randomized rounding algorithm to derive the flow-based, integral decisions. We next design a prediction-aware online algorithm which leverages the predicted inputs and can make even better scheduling decisions through invoking our prediction-oblivious online algorithm and improving its solutions via re-solving the original problem slice over each prediction window. We further rigorously prove the worst-case, constant competitive performance guarantees of our online algorithms. We finally conduct extensive evaluations and validate the superiority of our approach over multiple existing alternatives.

Recent advances in 5G and edge computing enable rapid development and deployment of edge-cloud systems, which are ideal for delay-sensitive machine learning (ML) applications such as autonomous driving and smart city. Distributed ML jobs often need to train a large model with enormous datasets, which can only be handled by deploying a distributed set of workers in an edge-cloud system. One common approach is to employ a parameter server (PS) architecture, in which training is carried out at multiple workers, while PSs are used for aggregation and model updates. In this architecture, one of the fundamental challenges is how to dispatch ML jobs to workers and PSs such that the average job completion time (JCT) can be minimized. In this work, we propose a novel online preemptive scheduling framework to decide the location and the execution time window of concurrent workers and PSs upon each job arrival. Specifically, our proposed scheduling framework consists of: i) a job dispatching and scheduling algorithm that assigns each ML job to workers and decides the schedule to train each data chunk; ii) a PS assignment algorithm that determines the placement of PS. We prove theoretically that our proposed algorithm is$D_{max}(1+1/\epsilon)$-competitive with$(1 + \epsilon)$-speed augmentation, where$D_{max}$is the maximal number of data chunks in any job. Extensive testbed experiments and trace-driven simulations show that our algorithm can reduce the average JCT by up to 30% compared with state-of-the-art baselines.

Small cells are deployed in 5G networks to complement the macro cells for improving coverage and capacity. Small cells and edge computing are natural partners which can improve users’ experience. Small cell nodes (SCNs) equipped with edge servers can support emerging computing services, such as virtual reality which impose low-latency and precise contextual requirements. With the proliferation of wireless devices, there is an increasing demand for offloading tasks to SCNs. Given limited computation and communication resources, the fundamental problem for a small cell network is how to select computing tasks to maximize effective rewards in an uncertain and stochastic environment. To this end, we propose an online learning framework, LFSC, which has the performance guarantee to guide task offloading in a small cell network. LFSC balances between reward and constraint violations, and it consists of three subroutines: i) a randomized algorithm which calculates selection probability of each task based on task weights; ii) a greedy assignment algorithm which cooperatively allocates tasks among different SCNs based on the selection probability; iii) an update algorithm which exploits the multi-armed bandit (MAB) technique to update task weights according to the feedback. Our theoretical analysis shows that both the regret and violations metrics of LFSC have the sub-linear property. Extensive simulation studies based on real world data confirm that LFSC achieves a close-to-optimal reward with low violations, and outperforms many state-of-the-art algorithms.

Federated Learning (FL) is a new distributed machine learning (ML) approach which enables thousands of mobile devices to collaboratively train artificial intelligence (AI) models using local data without compromising user privacy. Although FL represents a promising computing paradigm, such training process can not be fully realized without an appropriate economic mechanism that incentivizes the participation of heterogeneous clients. This work targets social cost minimization, and studies the incentive mechanism design in FL through a procurement auction. Different from existing literature, we consider a practical scenario of FL where clients are selected and scheduled at different global iterations to guarantee the completion of the FL job, and capture the distinct feature of FL that the number of global iterations is determined by the local accuracy of all participants to balance between computation and communication. Our auction framework$A_{FL}$first decomposes the social cost minimization problem into a series of winner determination problems (WDPs) based on the number of global iterations. Then to solve each WDP,$A_{FL}$invokes a greedy algorithm to determine the winners, and a payment algorithm for computing remuneration to winners. Finally,$A_{FL}$returns the best solution among all WDPs. Theoretical analysis proves that$A_{FL}$is truthful, individual rational, computationally efficient, and achieves a near-optimal social cost. We further conduct large-scale simulation studies based on the real-world data. Simulation results show that$A_{FL}$can reduce the social cost by up to 75% compared with state-of-the-art algorithms.

To realize high quality smart IoT services, such as intelligent video surveillance in Auto Driving and Smart City, tremendous amount of distributed machine learning jobs train unbiased models in wireless edge networks, adopting the parameter server (PS) architecture. Due to the large datasets collected geo-distributedly, the training of unbiased distributed learning (UDL) brings high response latency and bandwidth consumption. In this paper, we propose an online scheduling algorithm, Okita, to minimize both the latency cost and bandwidth cost in UDL. Okita schedules UDL jobs at each time slot to jointly decide the execution time window, the amount of training data, the number and the location of concurrent workers and PSs in each site. To evaluate the practical performance of Okita, we implement a testbed based on Kubernetes. Extensive experiments and simulations show that Okita can reduce up to 60% of total cost, compared with the state-of-the-art schedulers in cloud systems.

Metric learning aims to project original data into a new space, where data points can be classified more accurately using kNN or similar types of classification algorithms. To avoid trivial learning results such as indistinguishably projecting the data onto a line, many existing approaches formulate metric learning as a constrained optimization problem, like finding a metric that minimizes the distance between data points from the same class, with a constraint of ensuring a certain separation for data points from different classes, and then they approximate the optimal solution to the constrained optimization in an iterative way. In order to improve the classification accuracy as much as possible, we try to find a metric that is able to minimize the intra-class distance and maximize the inter-class distance simultaneously. Towards this, we formulate metric learning as a penalized optimization problem, and provide design guideline, paradigms with a general formula, as well as two representative instantiations for the penalty term. In addition, we provide an analytical solution for the penalized optimization, with which costly computation can be avoid, and more importantly, there is no need to worry about the convergence rates or approximation ratios any more. Extensive experiments on real-world data sets are conducted, and the results verify the effectiveness and efficiency of our approach.

Small cells are deployed in 5G networks to complement the macro cells for improving coverage and capacity. Small cells and edge computing are natural partners which can improve users’ experience. Small cell nodes (SCNs) equipped with edge servers can support emerging computing services such as virtual reality which impose low-latency and precise contextual requirements. With the proliferation of wireless devices, there is an increasing demand for offloading tasks to SCNs. Given limited computation and communication resources, the fundamental problem for a small cell network is how to select computing tasks to maximize effective rewards in an uncertain and stochastic environment. To this end, we propose an online learning framework, LFSC, which has the performance guarantee to guide task offloading in a small cell network. LFSC balances between reward and constraint violations, and it consists of three subroutines: i) a randomized algorithm which calculates selection probability of each task based on task weights; ii) a greedy assignment algorithm which cooperatively allocates tasks among different SCNs based on the selection probability; iii) an update algorithm which exploits the multi-armed bandit (MAB) technique to update task weights according to the feedback. Our theoretical analysis shows that both the regret and violations metrics of LFSC have the sub-linear property. Extensive simulation studies based on real world data confirm that LFSC achieves a close-to-optimal reward with low violations, and outperforms many state-of-the-art algorithms.

While both Internet Service Providers (ISPs) and third-party Security Service Providers (SSPs) offer Distributed Denial-of-Service (DDoS) mitigation services through cloud-based scrubbing centers, it is often beneficial for ISPs to outsource part of the traffic scrubbing to SSPs to achieve less economic cost and better network performance. To explore this potential, we design an online auction mechanism, featured by the challenge of the switching cost of using different winning bids over time. Formulating the social cost minimization as a nonconvex integer program, we firstly relax it and design an online algorithm that breaks it into a series of modified single-shot problems and solves each of them in polynomial time, without requiring knowledge of future inputs; then, we design a randomized rounding algorithm to convert the fractional decisions into integers without violating any constraints; and finally, we design the payment for each bid based on its winning probability. We rigorously prove that our mechanism achieves a parameterized-constant competitive ratio for the long-term social cost, with truthfulness and individual rationality in expectation. We also exhibit its superior practical performance via evaluations driven by real-world data traces.

Distributed machine learning (ML) has played a key role in today's proliferation of AI services. A typical model of distributed ML is to partition training datasets over multiple worker nodes to update model parameters in parallel, adopting a parameter server architecture. ML training jobs are typically resource elastic, completed using various time lengths with different resource configurations. A fundamental problem in a distributed ML cluster is how to explore the demand elasticity of ML jobs and schedule them with different resource configurations, such that the utilization of resources is maximized and average job completion time is minimized. To address it, we propose an online scheduling algorithm to decide the execution time window, the number and the type of concurrent workers and parameter servers for each job upon its arrival, with a goal of minimizing the weighted average completion time. Our online algorithm consists of (i) an online scheduling framework that groups unprocessed ML training jobs into a batch iteratively, and (ii) a batch scheduling algorithm that configures each ML job to maximize the total weight of scheduled jobs in the current iteration. Our online algorithm guarantees a good parameterized competitive ratio with polynomial time complexity. Extensive evaluations using real-world data demonstrate that it outperforms state-of-the-art schedulers in today's AI cloud systems.

Geo-distributed machine learning (ML) often uses large geo-dispersed data collections produced over time to train global models, without consolidating the data to a central site. In the parameter server architecture, “workers” and “parameter servers” for a geo-distributed ML job should be strategically deployed and adjusted on the fly, to allow easy access to the datasets and fast exchange of the model parameters at anytime. Despite many cloud platforms now provide volume discounts to encourage the usage of their ML resources, different geo-distributed ML jobs that run in the clouds often rent cloud resources separately and respectively, thus rarely enjoying the benefit of discounts. We study an ML broker service that aggregates geo-distributed ML jobs into cloud data centers for volume discounts via dynamic online placement and scaling of workers and parameter servers in individual jobs for long-term cost minimization. To decide the number and the placement of workers and parameter servers, we propose an efficient online algorithm which first decomposes the online problem into a series of one-shot optimization problems solvable at each individual time slot by the technique of regularization, and afterwards round the fractional decisions to the integer ones via a carefully-designed dependent rounding method. We prove a parameterized-constant competitive ratio for our online algorithm as the theoretical performance analysis, and also conduct extensive simulation studies to exhibit its close-to-offline-optimum practical performance in realistic settings.

Operating distributed Scrubbing Centers (SCs) to mitigate massive Distributed Denial of Service (DDoS) traffic in large-scale networks faces critical challenges. The operator needs to determine the diversion rule installation and elimination in the networks, as well as the scrubbing resource activation and revocation in the SCs, while minimizing the long-term cost and the cumulative decision-switching penalty without knowing the exact amount of the malicious traffic. We model and formulate this problem as an online nonlinear integer program. In contrast to many other online problems where future inputs are unknown but at least current inputs are known, a key new challenge here is that even part of the current inputs are unknown when decisions are made. To "learn" the best decisions online, we transform our problem via a gap-preserving approximation into an online optimization problem with only the known inputs, which is further relaxed and decoupled into a series of one-shot convex programs solvable in individual time slots. To overcome the intractability, we design a progressive rounding algorithm to convert fractional decisions into integral ones without violating the constraints. We characterize the competitive ratio of our approach as a function of the key parameters of our problem. We conduct evaluations using real-world data and confirm our algorithms' superiority over de facto practices and state-of-the-art methods.

Containers represent an agile alternative to virtual machines (VMs), for providing cloud computing services. Containers are more flexible and lightweight, and can be easily instrumented. Enterprise users often create clusters of inter-connected containers to provision complex services. Compared to traditional cloud services, key challenges in container cluster (CC) provisioning lie in the optimal placement of containers while considering inter-container traffic in a CC. The challenge further escalates, when CCs are provisioned in an online fashion. We propose an online algorithm to address the above challenges, aiming to maximize the aggregate value of all served clusters. We first study a one-shot CC placement problem. Leveraging techniques of exhaustive sampling and ST rounding, we design an efficient one-shot algorithm to determine the placement scheme of a given CC. We then propose a primal-dual online placement scheme that employs the one-shot algorithm as a building block to make decisions upon the arrival of each CC request. Through both theoretical analysis and trace-driven simulations, we verify that the online placement algorithm is computationally efficient and achieves a good competitive ratio.

Network Function Virtualization (NFV) provides virtualized network services through service chains of virtual network functions (VNFs). VNFs typically execute on virtual machines in a cloud infrastructure, which consists of geo-distributed cloud data centers. Compared to traditional cloud services, key challenges in virtual network service provisioning lie in the optimal placement of VNF instances while considering inter-VNF traffic and end-to-end delay in a service chain. The challenge further escalates when a service chain requires online processing upon the its arrival. We propose an online algorithm to address the above challenges, while aim to maximize the aggregate chain valuation. We first study a one-time VNF chain placement problem. Leveraging techniques of exhaustive sampling and ST rounding, we propose an efficient one-time algorithm to determine the placement scheme of a given service chain. We then propose a primal-dual online placement scheme that employs the one-time algorithm as a building block to make decisions upon the arrival of each chain. Through both theoretical analysis and trace-driven simulations, we verify that the online placement algorithm is computationally efficient and achieves a good competitive ratio.

This work studies the emerging C-RAN market in a 5G wireless network where mobile operators lease computation and communication resources from the tower company to serve wireless users. We propose an online C-RAN auction where each mobile operator bids for three types of resources in a future time window: wireless spectrum at base stations (BSs), front-haul link capacities, and mobile BS instances at the mobile cloud. We target an online C-RAN auction that executes in polynomial time, elicits truthful bids from mobile operators, and maximizes the social welfare of the C-RAN eco-system with both spectrum cost at BSs and server cost at the mobile cloud considered. We show how the marriage of (i) a new Fenchel dual approach to convex optimization with (ii) the posted pricing framework for online auction design can help achieve the three goals simultaneously, and evaluate the efficiency of our online C-RAN auction through both theoretical analysis and empirical studies.

Effective incentive mechanisms are invaluable in mobile crowd sensing, for stimulating participation of smartphone users. Online auction mechanisms represent a natural solution for such sensing task allocation. Departing from existing studies that focus on an isolated system round, we optimize social cost across the system lifespan, while considering location constraints and capacity constraints when assigning sensing tasks to users. The winner determination problem (WDP) at each round is NP-hard even without inter-round coupling imposed by user capacity constraints. We first propose a truthful one-round auction, comprising of an approximation algorithm for solving the one-round WDP and a payment scheme for computing remuneration to winners. We then propose an online algorithm framework that employs the one-round auction as a building block towards a flexible mechanism that makes on-spot decisions upon dynamically arriving bids. Through both theoretical analysis and trace-driven simulations, we demonstrate that our online auction is truthful, individually rational, computationally efficient, and achieves a good competitive ratio.

Compared with traditional virtual machines, cloud containers are more flexible and lightweight, emerging as the new norm of cloud resource provisioning. We exploit this new algorithm design space, and propose scheduling frameworks for cloud container services. Our offline and online schedulers permit partial execution, and allow a job to specify its job deadline, desired cloud containers, and inter-container dependence relations. We leverage the following classic and new techniques in our scheduling algorithm design. First, we apply the compact-exponential technique to express and handle nonconventional scheduling constraints. Second, we adopt the primal-dual framework that determines the primal solution based on its dual constraints in both the offline and online algorithms. The offline scheduling algorithm includes a new separation oracle to separate violated dual constraints, and works in concert with the randomized rounding technique to provide a near-optimal solution. The online scheduling algorithm leverages the online primal-dual framework with a learning-based scheme for obtaining dual solutions. Both theoretical analysis and trace-driven simulations validate that our scheduling frameworks are computationally efficient and achieve close-to-optimal aggregate job valuation.

This paper studies the cloud market for computing jobs with completion deadlines, and designs efficient online auctions for cloud resource provisioning. A cloud user bids for future cloud resources to execute its job. Each bid includes: 1) a utility, reflecting the amount that the user is willing to pay for executing its job and 2) a soft deadline, specifying the preferred finish time of the job, as well as a penalty function that characterizes the cost of violating the deadline. We target cloud job auctions that executes in an online fashion, runs in polynomial time, provides truthfulness guarantee, and achieves optimal social welfare for the cloud ecosystem. Towards these goals, we leverage the following classic and new auction design techniques. First, we adapt the posted pricing auction framework for eliciting truthful online bids. Second, we address the challenge posed by soft deadline constraints through a new technique of compact exponential-size LPs coupled with dual separation oracles. Third, we develop efficient social welfare approximation algorithms using the classic primal-dual framework based on both LP duals and Fenchel duals. Empirical studies driven by real-world traces verify the efficacy of our online auction design.

The quintessential problem in a smart grid is the matching between power supply and demand - a perfect balance across the temporal domain, for the stable operation of the power network. Recent studies have revealed the critical role of electricity storage devices, as exemplified by rechargeable batteries and plug-in electric vehicles (PEVs), in helping achieve the balance through power arbitrage. Such potential from batteries and PEVs can not be fully realized without an appropriate economic mechanism that incentivizes energy discharging at times when supply is tight. This work aims at a systematic study of such demand response problem in storage-assisted smart grids through a well-designed online procurement auction mechanism. The long-term social welfare maximization problem is naturally formulated into a linear integer program. We first apply a primal-dual optimization algorithm to decompose the online auction design problem into a series of one-round auction design problems, achieving a small loss in competitive ratio. For the one round auction, we show that social welfare maximization is still NP-hard, and design a primal-dual approximation algorithm that works in concert with the decomposition algorithm. The end result is a truthful power procurement auction that is online, truthful, and 2-competitive in typical scenarios.

The smart grid is a modern power grid that achieves high efficiency and robustness through sophisticated information and communications technology. Demand response has great potential in helping balance demand and supply in a smart grid, cutting generation cost and carbon footprint, and improving system stability. Auctions represent a natural and efficient approach for carrying out demand response between the power grid and large electricity users, microgrids, and electricity storage devices. This work explores the modeling and design space of demand response auctions, targeting expressive power, truthful information revelation, computational efficiency, and economic efficiency. We present a randomized auction that explores the underlying problem structure of demand response, and prove that it is truthful, runs in polynomial time, and achieves (1 + ϵ)-optimal social cost for an arbitrarily small constant ϵ. The key technique lies in the marriage of smoothed analysis and randomized reduction, which makes its debut in this work among literature on mechanism design, and can be applied to problems where social welfare optimization is NP-hard but admits a smoothed polynomial-time algorithm.

We apply signal alignment (SA), a wireless communication technique that enables physical layer network coding (PNC) in multi-input multi-output (MIMO) wireless networks. Through calculated precoding, SA contracts the perceived signal space at a node to match its receive capability, and hence facilitates the demodulation of linearly combined data packets. PNC coupled with SA (PNC-SA) has the potential of fully exploiting the precoding space at the senders, and can better utilize the spatial diversity of a MIMO network for higher system degrees-of-freedom (DoF). PNC-SA adopts the idea of `demodulating a linear combination' from PNC. The design of PNC-SA is also inspired by recent advances in IA, though SA aligns signals not interferences. We study the optimal precoding and power allocation problem of PNC-SA, for SNR (singal-to-noise-ratio) maximization at the receiver. The mapping from SNR to BER is then analyzed, revealing that the DoF gain of PNC-SA does not come with a sacrifice in BER. We then design a general PNC-SA algorithm in larger systems, and demonstrate general applications of PNC-SA, and show via network level simulations that it can substantially increase the throughput of unicast and multicast sessions, by opening previously unexplored solution spaces in multi-hop MIMO routing.

NanoNets are networks of nanomachines at extremely small dimensions, on the order of nanometers or micrometers. Recent advances in physics and engineering have made basic computing and communication feasible on nanomachines, and NanoNets are envisioned as an important emerging technology with broad future applications. Traditional networking solutions require significant modifications for application in NanoNets. In this paper, we focus on routing algorithm design in NanoNets. Based on the salient features of a NanoNet, including low node cost and very low available power, we propose a new routing paradigm for multi-hop data transmission in NanoNets. Our design, termed {\em Buddy Routing (BR)}, is enabled by latest advancements in physical layer network coding, and argues for pair-to-pair data forwarding in place of traditional node-to-node data forwarding. Through both analysis and simulations, we compare BR with point-to-point routing, in terms of raw throughput, error rate, energy efficiency, and protocol overhead, and show the advantages of BR in NanoNets.

We propose signal alignment (SA), a new wireless communication technique that enables physical layer network coding (PNC) in multi-input multi-output (MIMO) wireless networks. Through calculated preceding, SA contracts the perceived signal space at a node to match its receive diversity, and hence facilitates the demodulation of linearly combined data packets. PNC coupled with SA (PNC-SA) has the potential of fully exploiting the preceding space at the senders, and can better utilize the spatial diversity of a MIMO network for higher transmission rates, outperforming existing techniques including MIMO or PNC alone, interference alignment (IA) and interference alignment and cancellation (IAC). PNC-SA adopts the seminal idea of 'demodulate a linear combination' from PNC. The design of PNC-SA is also inspired by recent advances in IA, though SA aligns signals not interferences. We study the optimal preceding and power allocation problem of PNC-SA, for SNR maximization at the receiver. The mapping from SNR to BER is then analyzed, revealing that the throughput gain of PNC-SA does not come with a sacrifice in BER. We finally demonstrate general applications of PNC-SA, and show via network level simulations that it can substantially increase the throughput of unicast and multicast sessions, by opening previously unexplored solution spaces in multi-hop MIMO routing.