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.

The traffic bandwidth costs, primarily driven by outbound traffic, comprise a significant amount of operating expenditure in CDNs, induced by the traffic from the end-users to edge servers (edge cost) and from the edge to the center servers (midgress cost). Traffic allocation is the main approach to minimizing the total bandwidth cost. The joint optimization of the total costs is challenging, specifically when the percentile charging mechanism as well as some other practical issues are considered, such as the dynamicity of midgress traffic and the granularity of traffic allocation. In this work, based on our novel miss ratio prediction mechanism, we propose the first online framework, namedIris, jointly optimizing the edge and midgress costs under the 95th percentile charging in commercial CDNs.Iriscan theoretically achieve a competitive ratio of$1+\frac {p_{e}}{\beta \cdot p_{c}}$, when the miss ratio of all domains is set as$\beta $. Here$p_{e}$and$p_{c}$are the unit bandwidth price of the edge and midgress cost, respectively.Irisis tolerant to prediction errors which can be deployed in practical CDN systems. Extensive experiments based on real data indicate thatIriscan dramatically reduce bandwidth costs by about 8.149% compared with the SOTA schemes, potentially saving millions of dollars per month for our large-scale commercial CDN collaborator.

With the rapid growth of data-intensive applications, such as artificial intelligence and the Internet of Things, CDNs, which use persistent storage (e.g., SSDs and HDDs) to cache data at the edge, have become crucial for enhancing network efficiency. Two metrics—hit ratio and processing la tency—are essential for evaluating CDN caching performance. However, CDN caching faces the challenge of write amplification, creating a trade-off between random access for higher hit ratios and sequential writes for reducing processing latency. Existing cache designs struggle to effectively balance these conflicting requirements across diverse workloads. In this paper, we present FOSS, a caching system specifically optimized for CDNs deployed on SSD-based storage and hybrid SSD–HDD storage, which features a streamlined, thin file system that operates independently of the kernel. At its heart, FOSS employs a multi-level FIFO queue to strike a balance between local sequential and global random access on SSDs. Then, FOSS incorporates a learning-based method to dynamically configure the multi-level structure configuration, making the system adaptive to various workload characteristics and caching algorithm requirements. Therefore, FOSS ensures better performance across different scenarios. Our extensive experiments show FOSS improves hit ratios significantly over existing systems, reduces end-to-end response latency by 16.5% and demonstrates a consistent performance improvement in various settings on large-scale commercial CDN traces.

The efficiency and profitability of cloud data centers are significantly influenced by virtual machine (VM) placement. However, the Non-Uniform Memory Access (NUMA), which has been practically applied to reduce the memory bandwidth competition, is often neglected in the existing research. Actually, the incorporation of NUMA may change the traditional resource allocation mechanism, and demands for a new VM placement model. Hence, considering the multi-NUMA architecture, this paper studies the NUMA-aware VM placement (NAVMP) problem in a cloud computing system, where the resource pool is composed of enormous number of heterogeneous servers with diverse multi-resource remains. The NAVMP problem is analytically formulated as an integer program (IP). Also, for the first time, the incarnations of VM types are introduced to simplify the VM deployment rules originated from complex NUMA architecture. We aim to maximize the VM provision ability (VPA) of the resource pool, and thus propose a novel Value Function to describe servers’ VPA. The resulting formulation, which is a new variant of the multiple-choice multiple multi-dimensional knapsack (MMMK) problem, is of significant computational challenges. So we customize a decomposition approach based on Column Generation (CG) to support the offline optimization. Numerical experiments on a practical dataset demonstrate the validity and scalability of the customized CG-based approach. Our approach outperforms a professional IP solver, i.e., Cbc, and a popular meta-heuristic algorithm, i.e., genetic algorithm (GA), and can efficiently address large-scale NAVMP instances with ten thousands of VM demands and servers.Note to Practitioners—This paper proposes a novel IP model for NAVMP. To cope with the complicated deployment logic associated with the complex multi-NUMA architecture of modern multi-core systems, we present an NAVMP formulation from the perspective of incarnations of VM types. Different from the traditional VM placement problem that aims to minimize the number of activated servers, i.e., the vector bin packing (VBP)-based model, we adopt the objective that maximizes the VPA of a resource pool for further improving the resource utilization. The resulting formulation is an MMMK problem, which is computational very challenging for a practical scale resource pool. Hence, to mitigate the computation burden, we design and implement a CG-based decomposition approach to support the offline optimization for NAVMP. Parallelization scheme and nontrivial heuristic strategies are applied to promote the computation efficiency. According to our numerical experiments, the proposed decomposition approach demonstrates a much superior solution capacity to the Cbc solver and GA. In particular, to achieve a comparable solution precision with Cbc, the computing time can be reduced by orders of magnitude. Also the CG-based approach outperforms GA in both the solution quality and computation time for large-scale instances. Besides, compared to the VBP model, our MMMK-based NAVMP model has improved the VPA up to 44.39%. Practically, the proposed offline approach can be leveraged to guide online VM allocation decisions, and perform efficient results evaluation.

In latency-sensitive file caching systems such as Content Delivery Networks (CDNs) and Mobile Edge Computing (MEC), the latency of fetching a missing file to the local cache can be significant. Recent studies have revealed that successive requests for the same missing file before the fetching process completes could still suffer latency (so-called delayed hits). Motivated by the practical scenarios, we study the online general file caching problem with delayed hits and bypassing,i.e., a request may be bypassed and processed directly at the remote data center. The objective is to minimize the total request latency. We present a general reduction that turns a traditional file caching algorithm into one that can handle delayed hits. Based on this reduction, we propose an efficient online file caching algorithm, calledCaLa, with an asymptotically tight competitive ratio as$O(Z \log K)$, whereZis the maximum fetching latency of any file andKis the cache size. Extensive simulations on the production data trace from Google and the Yahoo benchmark illustrate thatCaLacan reduce the latency by up to 8.48% compared with the state-of-the-art schemes dealing with delayed hits without bypassing, and this improvement increases to 26.00% if bypassing is allowed. Furthermore, by upgrading the method for estimating files’ weights inCaLa, we proposeCaLa+, which further reduces the total latency by more than 5%.

Deploying deep neural networks (DNNs) on IoT devices for model serving is a promising solution for intelligent applications with high real-time requirements and bandwidth sensitivity. To cope with the prohibitive computation and storage overheads of modern DNNs, great efforts have been devoted to the model compression technique. Most existing model compression approaches focus on minimizing the model size and maximizing the average accuracy on all the inference tasks. However, real-world IoT tasks have various service-level objectives (SLOs). Models compressed by existing methods struggle to simultaneously meet SLOs in multiple dimensions, such as latency and accuracy. In this work, we study model compression with a joint consideration of SLO awareness and task adaptation. Through our extensive experience with model compression across various IoT tasks, we observe that the importance of individual channels in contributing to accuracy is heavily influenced by task-specific data distribution. Therefore, we design a channel Shapley algorithm to estimate the importance of individual channels in DNNs and propose a deep reinforcement learning based controller to incorporate SLOs into the compression objective. Integrating these designs, we propose and prototype ChannelZip, the first SLO-aware channel compression framework. Extensive evaluations on real IoT model serving systems show the effectiveness in task adaptation of ChannelZip. ChannelZip outperforms strong model compression baselines by 3.77% accuracy and achieves a 69% average parameter compression ratio. Real-world deployment on different IoT devices shows that ChannelZip meets all task SLOs and achieves up to 2.32 × inference speedup.

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 proposeOnCoLa, a novel$O(T_{c}K)$-competitive algorithm supporting request relaying on multiple edge servers. Here,$T_{c}$and$K$are the maximum container cold start latency and the memory size, respectively. Extensive simulations on two real-world traces demonstrate thatOnCoLaconsistently outperforms the state-of-the-art container caching algorithms and reduces the latency by$23.33\%$. Experiments on Raspberry Pi and Jetson Nano show thatOnCoLareduces latency by up to$21.38\%$compared with the representative lightweight policy.

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.

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

Device authentication plays a crucial role in preventing illegal access and ensuring smooth usage of magnetic wireless charging. However, current authentication techniques suffer from security vulnerabilities and are incompatible with low-cost receiver devices, thus severely limiting their applications. In this paper, we propose FreAuth, a novel Frequency feature-based device Authentication technology for magnetic wireless power transfer systems. Technically, we begin by conducting circuit measurements at the transmitter side to subtly retrieve impedance information related to the receiver without the need for its corporation. Then, we employ a dual-frequency interleaved-based subtraction technique to remove the ideal receiver impedance and capture the fairly weak frequency features. Furthermore, we normalize the captured frequency features to account for environment variations. These steps allow us to generate and store a hardware fingerprint for the receiver based on its frequency features. During device authentication, we use a discrete Frechet distance-based algorithm for fingerprint matching. We devise and implement a prototype of FreAuth and conduct extensive experiments to evaluate the proposed scheme. The experimental results validate the reliability (95.74% authentication accuracy among 60+ devices) and robustness (anti-interference with device location variations) of our FreAuth.

In this paper, we focus on the privacy preserving mechanism design for crowdsourced Federated Learning (FL), where a requester can outsource its model training task to some workers via an FL platform. A potential way to preserve the privacy of workers' local data is to leverage Differential Privacy (DP) mechanisms on local models. However, most of these studies cannot allow workers to dominate their own privacy protection levels by themselves. Thus, we propose a Personalized Privacy Preserving Mechanism, called P3M, to satisfy the heterogeneous privacy needs of workers, which consists of two parts. The first part includes a personalized privacy budget determination problem. We model it as a two-stage Stackelberg game, derive the personalized privacy budget for each worker and the optimal payment for the requester, and prove that they form a unique Stackelberg equilibrium. Second, we design a dynamic perturbation scheme to perturb model parameters. Through the theoretical analysis, we prove that P3M satisfies the desired DP property, and derive the bounds of the variance of average perturbed parameters and the convergence upper bound. This demonstrates that the global model accuracy can be controllable and P3M is endowed with the satisfactory convergence performance. In addition, we extend our problem to the scenario where the total privacy budget of all workers is limited, so as to prevent some workers from setting exorbitant privacy budgets. Under the privacy constraint, we re-determine the personalized privacy budget for each worker. Finally, exhaustive simulations of P3M are conducted based on real-world datasets, and the experimental results corroborate its effectiveness and practicability.

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.

In Mobile Edge Computing, edge servers have limited storage and computing resources that can only support a small number of functions. Meanwhile, mobile applications are becoming more complex, consisting of multiple dependent tasks, modeled as a Directed Acyclic Graph (DAG). When a request arrives, typically in an online manner with a deadline specified, we need to configure the servers and assign the dependent tasks for efficient processing. This work jointly considers the problem of dependent task placement and scheduling with on-demand function configuration on edge servers, aiming to meet as many deadlines as possible. For a single request, when the configuration on each edge server is fixed, we derive FixDoc to find the optimal task placement and scheduling. When the on-demand function configuration is allowed, we propose GenDoc , a novel approximation algorithm, and analyze its additive error from the optimal theoretically. For multiple requests, we derive OnDoc , an online algorithm easy to deploy in practice. Our extensive experiments show that GenDoc outperforms state-of-the-art baselines in processing 86.14% of these unique applications, and reduces their average completion time by at least 24%. The number of deadlines that OnDoc can satisfy is at least 1.9× that of the baselines.

Wireless sensor networks (WSNs) leveraging millimeter wave (mmWave) communication for bandwidth-demanding applications is considered in this article. Despite the large bandwidth, the delivery of delay-sensitive information collected by sensors may still face significant latency due to the vulnerability to intermittent link blockage. Hence, the guarantee of low age of information (AoI) in mmWave WSNs is not straightforward. In this article, the wireless sensing and dynamic programming techniques are jointly exploited to relieve the above issue. The former tracks the human blockers and predicts the chance of link blockage; the latter optimizes the transmission of multiple sensors based on the prediction. Particularly, the long-term optimization of sampling, uplink time and power allocation policies in a sensor network can be formulated as an infinite-horizon Markov decision process (MDP) with discounted cost, where the state transition probabilities can be predicted via wireless sensing. A novel low-complexity solution framework, namely COSMO, with a guaranteed performance in the worst case, is proposed. Simulations show that compared with heuristic benchmarks, benefiting from the prediction of the link blockage, COSMO can significantly suppress the average system cost, which consists of both AoI and energy consumption.

In this paper, the joint downlink delay-aware scheduling in a large time span, where the rotation of User Equipments (UEs) may lead to significant channel variation, is investigated via a novel approximate Markov Decision Process (MDP) method. Specifically, we consider the joint downlink power allocation and receiving UE selection of a number of successive frames in a millimeter Wave (mmWave) system with quasi-static scattering clusters in the channel and rotating UEs. The propagation statistics of scattering clusters can be tracked via a learning method. Since the rotation of UEs can be detected, future channel statistics can be forecast via embedded motion sensors. Hence, the overall scheduling is formulated as a finite-horizon MDP with non-stationary predictable state transition probabilities, where the average queuing delay and probability of transmission buffer overflow are considered in the objective of scheduling optimization. A novel low-complexity solution framework with an analytical performance bound is proposed to save the efforts of value iteration. Benefiting from the forecast of system statistics, superior performance to the benchmarks is shown by numerical simulations, particularly in the suppression of buffer overflow rate. Preliminary experiments via an mmWave testbed are conducted to demonstrate the feasibility of the sensor-assisted mmWave beam alignment.

User impression forecasting underpins various commercial activities, from long-term strategic decisions to short-term automated operations. As a representative that involves both kinds, the highly profitable Guaranteed Delivery (GD) advertising focuses mainly on promoting brand effect by allowing advertisers to order target impressions weeksin advance and get allocatedonline at the scheduled time. Such a business mode naturally incurs three issues making existing solutions inferior: 1) Timescale-granularity dilemma of coherently supporting the sales of day-level impressions of the distant future and the corresponding fine-grained allocation in real-time. 2) High dimensionality due to the Cartesian product of user attribute combinations. 3) Stability-plasticity dilemma of instant adaptation to emerging patterns of temporal dependency withoutcatastrophic forgetting of repeated ones facing the non-stationary traffic.

Today's trend of building ever larger language models (LLMs), while pushing the performance of natural language processing, adds significant latency to the inference stage. We observe that due to the diminishing returns of adding parameters to LLMs, a smaller model could make the same prediction as a costly LLM for a majority of queries. Based on this observation, we design Tabi, an inference system with a multi-level inference engine that serves queries using small models and optional LLMs for demanding applications. Tabi is optimized for discriminative models (i.e., not generative LLMs) in a serving framework. Tabi uses the calibrated confidence score to decide whether to return the accurate results of small models extremely fast or re-route them to LLMs. For re-routed queries, it uses attention-based word pruning and weighted ensemble techniques to offset the system overhead and accuracy loss. We implement and evaluate Tabi with multiple tasks and models. Our result shows that Tabi achieves 21%-40% average latency reduction (with comparable tail latency) over the state-of-the-art while meeting LLM-grade high accuracy targets.

Millimeter wave (MmWave) has been regarded as a promising technology to support high-capacity communications in 5G era. However, its high-layer performance such as latency and packet drop rate in the long term highly depends on resource allocation because mmWave channel suffers significant fluctuation with rotating users due to mmWave sparse channel property and limited field-of-view (FoV) of antenna arrays. In this paper, downlink transmission scheduling considering rotation of user equipments (UE) and limited antenna FoV in an mmWave system is optimized via a novel approximate Markov decision process (MDP) method. Specifically, we consider the joint downlink UE selection and power allocation in a number of frames where future orientations of rotating UEs can be predicted via embedded motion sensors. The problem is formulated as a finite-horizon MDP with non-stationary state transition probabilities. A novel low-complexity solution framework is proposed via one iteration step over a base policy whose average future cost can be predicted with analytical expressions. It is demonstrated by simulations that compared with existing benchmarks, the proposed scheme can schedule the downlink transmission and suppress the packet drop rate efficiently in non-stationary mmWave links.

The freshness of information, measured as Age of Information (AoI), is critical for many applications in next-generation wireless sensor networks (WSNs). Due to its high bandwidth, millimeter wave (mmWave) communication is seen to be frequently exploited in WSNs to facilitate the deployment of bandwidth-demanding applications. However, the vulnerability of mmWave to user mobility typically results in link blockage and thus postponed real-time communications. In this paper, joint sampling and uploading scheduling in an AoI-oriented WSN working in mmWave band is considered, where a single human blocker is moving randomly and signal propagation paths may be blocked. The locations of signal reflectors and the real-time position of the blocker can be detected via wireless sensing technologies. With the knowledge of blocker motion pattern, the statistics of future wireless channels can be predicted. As a result, the AoI degradation arising from link blockage can be forecast and mitigated. Specifically, we formulate the long-term sampling, uplink transmission time and power allocation as an infinite-horizon Markov decision process (MDP) with discounted cost. Due to the curse of dimensionality, the optimal solution is infeasible. A novel low-complexity solution framework with guaranteed performance in the worst case is proposed where the forecast of link blockage is exploited in a value function approximation. Simulations show that compared with several heuristic benchmarks, our proposed policy, benefiting from the awareness of link blockage, can reduce average cost up to 49.6%.

Serverless edge computing has emerged as a new paradigm for running short-lived computations on edge devices. Considering the challenges posed by multiple edge servers and non-negligible cold start latency in serverless edge computing, we investigate the problem of function caching on multiple edge servers with relaying and bypassing. Our objective is to minimize the total latency of serving all function requests, which may either be processed by an idle container on the local server, initiate a new container on the local server, relayed to other edge servers, or bypassed to the cloud server. We propose FunCa, a greedy-based algorithm, and FunCa+, an extension version that supports bypassing. Large-scale simulation experiments using Azure trace and Alibaba trace demonstrate that compared to Camul, the state-of-the-art algorithm for handling requests on multiple edge servers, FunCa can reduce latency by 52.2% and 73.27% in the two traces, respectively.

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.

The traffic bandwidth costs comprise a significant amount of operating expenditure in CDNs, induced by the traffic from the end-users to edge servers (edge cost) and from the edge to the center servers (midgress cost). Traffic allocation is the main approach to minimizing the total bandwidth cost. The joint optimization of the total costs is challenging, specifically when the percentile charging mechanism as well as some other practical issues are considered, such as the dynamicity of midgress traffic and the granularity of traffic allocation. In this work, based on our novel miss ratio prediction mechanism, we propose the first online framework, named Iris, jointly optimizing the edge and midgress costs under the 95th percentile charging in commercial CDNs. Iris can theoretically achieve a competitive ratio of$1+\frac{p_{e}}{\beta\cdot p_{c}}$, when the miss ratio of all domains is set as$\beta$. Here$p_{e}$and$p_{c}$are the unit bandwidth price of the edge and midgress cost, respectively. Iris is tolerant to prediction errors which can be deployed in practical CDN systems. Extensive experiments based on real data indicate that Iris can dramatically reduce bandwidth costs by about 8.149% compared with the SOTA schemes, potentially saving millions of dollars per month for our large-scale commercial CDN collaborator.

We study the problem of resilient service provisioning for edge computing (RSPE), i.e., how to determine a service placement strategy to maximize the expected overall utility by service provisioning, in the presence of uncertain service failures. RSPE is extremely challenging to tackle, because the explicit expression of its objective function is difficult to obtain, and it is a resilient max–min problem subject to knapsack constraints, which is unexplored so far and cannot be addressed by existing resilient optimization techniques. We first explore the potential properties of the implicit objective function, and reveal that it is monotone submodular under certain conditions. We further prove that the knapsack constraints form a$q$-independence system constraint, where$q>0$is a constant related to the constraints. We propose two novel solutions for the general RSPE and homogeneous case, respectively. First, for the general problem, we propose a “two-step greedy” algorithm achieving a constant approximation ratio within polynomial time. Second, for the homogeneous case where one of the knapsack constraints reduces to a matroid constraint, we propose an improved “first-greedy-then-local search” polynomial time algorithm achieving better approximation ratio than the previous one. Both extensive simulations and field experiments validate the effectiveness of our proposed algorithms.

With the rapid advance of wireless sensing techniques, it becomes possible to provide a fine-grained user activity tracking service at home and office. Such a technique is of broad applications in various domains such as personal activity diary, elderly care, and customized services. For example, several radio frequency (RF) based sensing systems were recently proposed for human activity recognition. However, most of them focused on specific scenarios and suffered from interference caused by other users and wireless devices. In this work, we propose Back-Guard, a backscattering-based sensing system that achieves accurate and non-intrusive user activity recognition and further user identification/authentication. Back-Guard carefully examines the backscatter spectrogram data and extracts high-level features from both spatial and temporal domains. Leveraging the parallel attention based deep learning model, our system can discriminate different motions and users accurately and robustly in various situations. We implemented a prototype system and collected data from 25 users for more than 2 months. Extensive experiments demonstrate that Back-Guard achieves 93.4$\%$activity recognition accuracy and 91.5$\%$user identification accuracy, respectively. In particular, Back-Guard can also tackle multiple user scenarios, which has little accuracy reduction when the users are separated, e.g., by around 2 meters.

Edge computing systems typically handle a wide variety of applications that exhibit diverse degrees of sensitivity to job latency. Therefore, a multitude of utility functions of the job response time need to be considered by the underlying job dispatching and scheduling mechanism. Nonetheless, previous studies in edge computing mainly focused on optimizing a single utility function across all jobs, e.g., linear, sigmoid, or the hard deadline. In this paper, we design online job dispatching and scheduling strategies in which different jobs can be categorized by different non-increasing utility functions. Our goal is to maximize the total utility of all scheduled jobs. We first prove that no online deterministic algorithm could achieve a competitive ratio better than the lower bound$\Omega \left({\frac {1}{\sqrt {\epsilon }}}\right)$under the$(1+\epsilon)$-speed augmentation model. We proceed to propose an online algorithm, named asO4A, for handling jobs with heterogeneous utilities. We prove thatO4Ais$O\left({\frac {1}{\epsilon ^{2}}}\right)$-competitive. We also design its distributed version, i.e.,DO4A. We implementO4AandDO4Aon an edge computing testbed running deep learning inference jobs. With the production trace from Google Cluster, our experimental and large-scale simulation results indicate thatO4Acan increase the total utility by up to 50% compared with state-of-the-art methods. Besides, the performance loss ofDO4Ais only 2% compared withO4Awith a small communication overhead involved. Moreover, both of our algorithms are robust to estimation errors in job processing time and transmission delay.

Recently, multiple-input multiple-output (MIMO) technology has been introduced into magnetic resonant coupling (MRC) enabled wireless power transfer (WPT) systems for concurrent charging of multiple devices. However, impedance mismatching phenomena caused by strong TX-RX, TX-TX, or RX-RX coupling greatly affect the power delivered to load (PDL) in practical charging systems. To solve this issue, we propose an effective scheduling algorithm for Impedance Matching–enhanced PDL optimization in MIMO MRC-WPT systems (called IMeP ), which integrates the transmitter scheduling together with the impedance matching techniques, i.e., adjusting TX coils for tuning TX-RX/TX-TX coupling and grouping RXs to separate strongly coupled RX pairs. We formulate this as a joint optimization problem and decouple it into three sub-problems, i.e., current scheduling, coil adjustment, and RX grouping. We then solve them through alternating direction method of multipliers–based, randomized beamforming–based, and graph clique cover–based algorithms, respectively. Extensive experiments are performed on a prototype testbed, and the results demonstrate the effectiveness of our solution. Compared with the state-of-the-art power transfer efficiency maximization solution, the proposed algorithm IMeP achieves a 74.7× performance improvement of PDL on average.

Wireless power transfer (e.g., based on RF or magnetic) enables convenient device charging, and triggers innovative applications that typically call for faster, smarter, economic, and even simultaneous adaptive charging for multiple smart devices. Designing such a wireless charging system meeting these multi-requirements faces critical challenges, mainly including the better understanding of real-time energy receivers’ status and the power-transferring channels, the limited capability and the smart coordination of the transmitters and receivers. In this work, we devise Camel , a context-aware MIMO MRC-WPT (magnetic resonant coupling based wireless power transfer) system, which enables adaptive charging of multiple devices simultaneously with a novel context sensing scheme. In Camel , we craft an innovative MIMO MRC-WPT channels’ state estimation and collision-aware parallel in-band communication among multiple transmitters and receivers. We design and implement the Camel prototype and conduct extensive experimental studies. The results validate our design and demonstrate that Camel can support simultaneous charging of as many as 10 devices, high-speed context sensing within 50 ms, and efficient parallel communication among transceivers within proximity of ∼0.5 m.

In latency-sensitive file caching systems such as Content Delivery Networks (CDNs) and Mobile Edge Computing (MEC), the latency of fetching a missing file to the local cache can be significant. Recent studies have revealed that successive requests of the same missing file before the fetching completes could still suffer latency (so-called delayed hits).Motivated by the practical scenarios, we study the online general file caching problem with delayed hits and bypassing, i.e., a request may be bypassed and processed directly at the remote data center. The objective is to minimize the total request latency. We show a general reduction that turns a traditional file caching algorithm to one that can handle delayed hits. We give an O(Z3/2logK)-competitive algorithm called CaLa with this reduction, where Z is the maximum fetching latency of any file and K is the cache size, and we show a nearly-tight lower bound Ω(Z logK) for our ratio. Extensive simulations based on the production data trace from Google and the Yahoo benchmark illustrate that CaLa can reduce the latency by up to 9.42% compared with the state-of-the-art scheme dealing with delayed hits without bypassing, and this improvement increases to 32.01% if bypassing is allowed.

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.

Recently, the developed techniques such as magnetic resonant coupling (MRC) and multiple-input multiple-output (MIMO) transmission have significantly improved the charging efficiency and distance for wireless power transfer (WPT) systems. However, the electromagnetic radiation (EMR) safety of wireless charging is critical in practice while mostly ignored. In this work, we take the EMR safety into account in MIMO MRC-WPT systems. We propose a safety ensured high-efficient scheduling algorithm for magnetic MIMO wireless power transfer system (called Shield). Technically, we firstly devise a simple but accurate Z-axis rotational symmetrical EMR model along with a magnetic-field-line-based meshing scheme. Further, we express the EMR safety requirement in the continuous physical space with a limited number of constraints via random sampling and rule-based filtering. Finally, we build up a system prototype for Shield and conduct extensive experiments. With the given power budget and resonant frequency, the results reveal that the EMR safety requirement only influences the charging performance of an MRC-WPT system within a certain range. Furthermore, Shield can dramatically improve the payload power transfer efficiency (PTE) by up to 66.60% compared with state-of-the-art baselines while guaranteeing the EMR safety.

With the explosion of data transmitted over the Internet, Content Delivery Networks (CDNs) carry massive network traffic globally and suffer an increasingly higher bandwidth cost. A critical issue for CDN service providers is how to allocate network traffic among CDN facilities to reduce the total bandwidth cost without violating the quality of service. This work studies online traffic allocation in CDNs to minimize the bandwidth cost under the 95th percentile charging model. Specifically, we here take into account practical deployment issues in large-scale CDN systems, e.g., allocation granularity and deviation. We first theoretically prove the approximation hardness of the traffic allocation problem. We then propose a novel prediction-based algorithm named OnTPC, which effectively addresses constraints raised in practical deployment. Extensive experiments demonstrate that OnTPC outperforms state-of-the-art baselines and is expected to save over a million dollars per month for our large-scale commercial CDN collaborator. Moreover, the performance of OnTPC is consistently outstanding under various settings, and specifically robust to large allocation deviation.

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.

Job dispatching is a fundamental problem in edge computing for load balancing among multiple edge servers. When implementing an edge computing system with distributed job dispatchers in a sizable network, such as a metropolitan area network (MAN), the highly dynamic transmission latency is nonnegligible, which could lead to outdated information being shared. Moreover, the fully observed system state is beyond reach as the reception of any broadcast is time consuming. In this article, we investigate the online distributed job dispatching problem in edge computing, where multiple access points (APs) collect jobs and then dispatch each job to an edge server. The distributed dispatcher on each AP would receive partially and outdated information exchanged via periodic broadcast. Hence, we formulate the distributed job dispatching problem by leveraging the partially observable Markov decision process (POMDP) and propose a novel approximate Markov decision process (MDP) solution framework, calledDecMDP, that bypasses the huge time complexity of conventional POMDP solutions. Both analytical and semi-analytical performance lower bounds are derived for the approximate MDP solution. Furthermore, we extendDecMDPto handle a more general scenario wherea prioriknowledge of the system is absent. Finally, extensive simulations based on the Google Cluster traces show that our policy can achieve the best performance when compared with heuristic baselines, e.g., achieving 20.67% reduction in average job response time, and consistently performs well under various parameter settings.

Federated learning (FL) is a newly emerging distributed machine learning paradigm, whereby a server can coordinate multiple clients to jointly train a learning model by using their private datasets. Many researches focus on designing incentive mechanisms in FL, but most of them cannot allow that clients flexibly determine privacy budgets by themselves. In this article, we propose a privacy-preserving incentive mechanism (NICE) based on differential privacy (DP) and Stackelberg game for FL systems in industrial Internet of Things. First, we design a flexible privacy-preserving mechanism for NICE, in which clients can add a Laplace noise into the loss function according to a customized privacy budget. Under this mechanism, we design two incentive utility functions for the server and clients. Next, we model the utility optimization problems as a two-stage Stackelberg game by seeing the server as a leader and the clients as followers. Finally, we derive an optimal Stackelberg equilibrium solution for both the stages of the whole game. Based on this solution, NICE can make the server and all clients achieve their maximum utilities simultaneously. In addition, we conduct extensive simulations on real-world datasets to demonstrate the significant performance of the proposed mechanism.

Heterogeneous cellular networks (HetNets), where low-power low-complexity base stations (Pico-BSs) are deployed inside the coverage of macro base stations (Macro-BSs), can significantly improve the spectrum efficiency by Pico- and Macro base station collaboration. Due to cross-tier interference, joint detection of uplink signals is widely adopted so that Pico-BS can either detect the uplink signals locally or forward them to Macro-BS for processing. The latter can achieve increased throughput at the cost of additional backhaul transmission. In this paper, we study the delay-optimal uplink scheduling problem in HetNets with limited backhaul capacity. Local signal detection or joint signal detection is scheduled in a unified delay-optimal framework. Specifically, we first prove that the problem is NP-hard and then formulate it as a Markov Decision Process. We propose an efficient algorithm, calledOLIUS, that can deal with the exponentially growing state and action space. Furthermore,OLIUSis online learning-based which does not require any prior knowledge on user behavior or channel characteristics. We prove the convergence ofOLIUSand derive an upper bound on its approximation error. Extensive experiments in various scenarios show our algorithm outperforms existing methods in reducing delay and power consumption.

Traffic signal control is essential to efficient transportation networks since it can mitigate traffic congestion significantly. Trial-and-error approach in reinforcement learning will lead to traffic jams, even traffic accidents in the real scene, which is in violation of safety for traffic signal control. Besides, most signal control systems still rely on oversimplified information, which makes item challenging to adapt to dynamic traffic. In this paper, we focus on the edge coordinated optimization of large-scale traffic signal control, and propose a two-layeR edge-assisted pressUre balaNce (RUN) approach based on cooperative game. The external layer utilizes cooperative game to divide the traffic network into multiple coalitions. The internal layer uses pressure control and weighted queue to coordinate actions within each coalition and handle dynamic traffic situations over time. We derive a Pareto stable solution for the multi-intersection signal cooperative game with pressure control, and prove that it is non-superadditive. Moreover, we conduct extensive simulations to verify the significant performances of RUN based on both real data and synthetic data.

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.

Wireless power transfer (e.g., based on RF or magnetic) enables convenient device-charging, and triggers innovative applications that typically call for faster, smarter, economic, and even simultaneous adaptive charging for multiple smart-devices. Designing such a wireless charging system meeting these multi-requirements faces critical challenges, mainly including the better understanding of real-time energy receivers' status and the power-transferring channels, the limited capability and the smart coordination of the transmitters and receivers. In this work, we devise Camel, a context-aware MIMO MRC-WPT (magnetic resonant coupling-based wireless power transfer) system, which enables adaptive charging of multiple devices simultaneously with a novel context sensing scheme. In Camel, we craft an innovative MIMO WPT channels' state estimation and collision-aware in-band parallel communication among multiple transmitters and receivers. We design and implement the Camel prototype and conduct extensive experimental studies. The results validate our design and demonstrate that Camel can support simultaneous charging of as many as 10 devices, high-speed context sensing within 50 milliseconds, and efficient parallel communication among transceivers within proximity of ~0.5m.

The Bulk Synchronous Parallel (BSP) paradigm is gaining tremendous importance recently due to the popularity of computations as distributed machine learning and graph computation. In a typical BSP job, multiple workers concurrently conduct iterative computations, where frequent synchronization is required. Therefore, the workers should be scheduled simultaneously and their placement on different computing devices could significantly affect the performance. Simply retrofitting a traditional scheduling discipline will likely not yield the desired performance due to the unique characteristics of BSP jobs. In this work, we deriveSPIN, a novel scheduling designed for BSP jobs with placement-sensitive execution to minimize the makespan of all jobs. We first prove the problem approximation hardness and then present howSPINsolves it with a rounding-based randomized approximation approach. Our analysis indicatesSPINachieves a good performance guarantee efficiently. Moreover,SPINis robust against misestimation of job execution time by theoretically bounding its negative impact. We implementSPINon a production-trace driven testbed with 40 GPUs. Our extensive experiments show thatSPINcan reduce the job makespan and the average job completion time by up to$3\times $and$4.68\times $, respectively.SPINalso demonstrates better robustness to execution time misestimation compared with state-of-the-art heuristic baselines.

Motivated by practical scenarios in areas such as Mobile Edge Computing (MEC) and Content Delivery Networks (CDNs), we study online file caching on multiple caches, where a file request might be relayed to other caches or bypassed directly to the memory when a cache miss happens. We can also choose to fetch files from the memory to caches and conduct file replacement if necessary. We take the relaying, bypassing and fetching costs altogether into consideration. We first show the inherent difficulty of the problem even when the online requests are of uniform costs. We propose an O(logK)-competitive randomized online multiple caching algorithm (named Camul) and an O(K)-competitive deterministic algorithm (named Camul-Det), where K is the total number of slots in all caches. Both of them achieve asymptotically optimal competitive ratios. Moreover, our algorithms can be implemented efficiently such that each request is processed in amortized constant time. We conduct extensive simulations on production data traces from Google and a benchmark workload from Yahoo. It shows that our algorithms dramatically outperform state-of-the-art schemes, i.e., reducing the total cost by 85% and 43% respectively compared with important baselines and their strengthened versions with request relaying. More importantly, Camul achieves such a good total cost without sacrificing other performance measures, e.g., the hit ratio, and performs consistently well on various settings of experiment parameters.

To improve the application-level data efficiency, the scheduling of coflows, defined as a collection of parallel flows sharing the same objective, is prevailing in recent data centers. Meanwhile, optical circuit switches (OCS) are gradually applied to provide high data rate with low power consumption. However, so far few research outputs have covered the flow, let alone the coflow, scheduling in the context of OCS. In this work, we investigate coflow scheduling in OCS-based data centers. We first derive a novel operation called regularization processed respectively on the flow traffic demands and the flow start times, which can be efficiently implemented and reduce the circuit reconfiguration frequency dramatically. We then propose a 2-approximation algorithm, called Reco-Sin, for single coflow scheduling to minimize the coflow completion time (CCT). For multiple coflows, we derive Reco-Mul to minimize the total weighted CCT, which can transform any non-preemptive multi-coflow scheduling in packet switches to a scheduling scheme in OCS. Reco-Mul can achieve a constant approximation under the assumption that no tiny flows will be transmitted in OCS. To get rid of this assumption, we present another multiple coflow scheduling scheme, named Reco-Mul+, which has an approximation ratio of O(K). Here, K is the total number of coflows. Extensive simulations based on Facebook data traces show that our approaches outperform state-of-the-art schemes significantly, i.e., one single coflow can be finished up to 1.97× faster with Reco-Sin, and multiple coflows can be completed up to more than 2× faster with Reco-Mul and Reco-Mul+.

The Bulk Synchronous Parallel (BSP) paradigm is gaining tremendous importance recently because of the pop-ularity of computations such as distributed machine learning and graph computation. In a typical BSP job, multiple workers concurrently conduct iterative computations, where frequent synchronization is required. Therefore, the workers should be scheduled simultaneously and their placement on different computing devices could significantly affect the performance. Simply retrofitting a traditional scheduling discipline will likely not yield the desired performance due to the unique characteristics of BSP jobs. In this work, we derive SPIN, a novel scheduling designed for BSP jobs with placement-sensitive execution to minimize the makespan of all jobs. We first prove the problem approximation hardness and then present how SPIN solves it with a rounding-based randomized approximation approach. Our analysis indicates SPIN achieves a good performance guarantee efficiently. Moreover, SPIN is robust against misestimation of job execution time by theoretically bounding its negative impact. We implement SPIN on a production-trace driven testbed with 40 GPUs. Our extensive experiments show that SPIN can reduce the job makespan and the average job completion time by up to 3× and 4.68×, respectively. Our approach also demonstrates better robustness to execution time misestimation compared with heuristic baselines.

Real-time online services using pre-trained deep neural network (DNN) models, e.g., Siri and Instagram, require low-latency and cost-efficiency for quality-of-service and commercial competitiveness. When deployed in a cloud environment, such services call for an appropriate selection of cloud configurations (i.e., specific types of VM instances), as well as a considerate device placement plan that places the operations of a DNN model to multiple computation devices like GPUs and CPUs. Currently, the deployment mainly relies on service providers' manual efforts, which is not only onerous but also far from satisfactory oftentimes (for a same service, a poor deployment can incur significantly more costs by tens of times). In this paper, we attempt to automate the cloud deployment for real-time online DNN inference with minimum costs under the constraint of acceptably low latency. This attempt is enabled by jointly leveraging the Bayesian Optimization and Deep Reinforcement Learning to adaptively unearth the (nearly) optimal cloud configuration and device placement with limited search time. We implement a prototype system of our solution based on TensorFlow and conduct extensive experiments on top of Microsoft Azure. The results show that our solution essentially outperforms the nontrivial baselines in terms of inference speed and cost-efficiency.

Edge computing systems typically handle a wide variety of applications that exhibit diverse degrees of sensitivity to job latency. Therefore, a multitude of utility functions of the job response time need to be considered by the underlying job dispatching and scheduling mechanism. Nonetheless, previous works in edge computing mainly focused on either one kind of utility function (e.g., linear, sigmoid, or the hard deadline) or different kinds of utilities separately. In this paper, we investigate online job dispatching and scheduling strategies under the setting of coexistence of heterogeneous utilities, i.e., various coexisting jobs can employ different non-increasing utility functions. The goal is to maximize the total utility over all jobs in an edge system. Besides heterogeneous utilities, we here adopt a practical online model where the unrelated machine model and the upload and download delay are considered. We proceed to propose an online algorithm, O4A, to dispatch and schedule jobs with heterogeneous utilities. Our theoretical analysis shows that O4A is O(1/ɛ2)-competitive under the (1 + ɛ)-speed augmentation model, where ɛ is a small positive constant. We implement O4A on an edge computing testbed running deep learning inference jobs. With the production trace from Google Cluster, our experimental and large-scale simulation results indicate that O4A can increase the total utility by up to 39.42% compared with state-of-the-art utility-agnostic methods. Moreover, O4A is robust to estimation errors in job processing time and transmission delay.

In this paper, we investigate online distributed job dispatching in an edge computing system residing in a Metropolitan Area Network (MAN). Specifically, job dispatchers are implemented on access points (APs) which collect jobs from mobile users and distribute each job to a server at the edge or the cloud. A signaling mechanism with periodic broadcast is introduced to facilitate cooperation among APs. The transmission latency is non-negligible in MAN, which leads to outdated information sharing among APs. Moreover, the fully-observed system state is discouraged as reception of all broadcast is time consuming. Therefore, we formulate the distributed optimization of job dispatching strategies among the APs as a Markov decision process with partial and outdated system state, i.e., partially observable Markov Decision Process (POMDP). The conventional solution for POMDP is impractical due to huge time complexity. We propose a novel low-complexity solution framework for distributed job dispatching, based on which the optimization of job dispatching policy can be decoupled via an alternative policy iteration algorithm, so that the distributed policy iteration of each AP can be made according to partial and outdated observation. A theoretical performance lower bound is proved for our approximate MDP solution. Furthermore, we conduct extensive simulations based on the Google Cluster trace. The evaluation results show that our policy can achieve as high as 20.67% reduction in average job response time compared with heuristic baselines, and our algorithm consistently performs well under various parameter settings.

In this paper, the scheduling of downlink file transmission in one cell with the assistance of cache nodes with finite cache space is studied. Specifically, requesting users arrive randomly and the base station (BS) reactively multicasts files to the requesting users and selected cache nodes. The latter can offload the traffic in their coverage areas from the BS. We consider the joint optimization of the abovementioned file placement and delivery within a finite lifetime subject to the cache space constraint. Within the lifetime, the allocation of multicast power and symbol number for each file transmission at the BS is formulated as a dynamic programming problem with a random stage number. Note that there are no existing solutions to this problem. We develop an asymptotically optimal solution framework by transforming the original problem to an equivalent finite-horizon Markov decision process (MDP) with a fixed stage number. A novel approximation approach is then proposed to address the curse of dimensionality, where the analytical expressions of approximate value functions are provided. We also derive analytical bounds on the exact value function and approximation error. The approximate value functions depend on some system statistics, e.g., requesting users’ distribution. One reinforcement learning algorithm is proposed for the scenario where these statistics are unknown.

In this article, we study online deadline-aware task dispatching and scheduling in edge computing. We jointly considerthe management of the networking and computing resources to meet the maximum number of deadlines. We propose an online algorithm, named Dedas, which greedily schedules newly arriving tasks and considers whether to replace some existing tasks in order to make the new deadlines satisfied. We derive a non-trivial competitive ratio of Dedas theoretically, and our analysis is asymptotically tight. Besides, we implement a distributed approximation D - Dedas with a better scalability and less than 10 percent performance loss compared with the centralized algorithm Dedas. We then build DeEdge, an edge computing testbed installed with typical latency-sensitive applications such as IoT sensor monitoring and face matching. We adopt a real-world data trace from the Google cluster for large-scale emulations. Extensive testbed experiments and simulations demonstrate that the deadline miss ratio of Dedas is stable for online tasks, which is reduced by up to 60 percent compared with state-of-the-art methods. Moreover, Dedas performs well in minimizing the average task completion time.

To improve the application-level data efficiency, the scheduling of coflows, defined as a collection of parallel flows sharing the same objective, is prevailing in recent data centers. Meanwhile, optical circuit switches (OCS) are gradually applied to provide high data rate with low power consumption. However, so far few research outputs have covered the flow scheduling in the context of OCS, let alone the coflow scheduling problems. In this paper, we investigate coflow scheduling in the OCS-based data centers. We first derive a novel operation called regularization processed respectively on the flow traffic demands and the flow start times. Regularization can be efficiently implemented and reduce the circuit reconfiguration frequency dramatically. We then propose a 2-approximation algorithm, called Reco-Sin, for single coflow scheduling to minimize the coflow completion time (CCT). For multiple coflows, we derive another approximation algorithm, called Reco-Mul, to minimize the total weighted CCT, which can transform any non-preemptive multi-coflow scheduling in packet switches to that in OCS. Extensive simulations based on Facebook data traces show that Reco-Sin and Reco-Mul outperform state-of-the-art schemes significantly, i.e., one single coflow can be finished up to 2.72× faster with Reco-Sin, and multiple coflows can be completed up to 3.44× faster with Reco-Mul.

Desktop is a reliable and amicable object carrier that accompanies us in our daily life, while working, eating and even entertaining. In this work, we devise a contactless but accurate object tracking system on desktop with commercial RFIDs. Comparing with conventional vision or acoustic based solutions, our system needs less computational resources and could be mucheasier for deployment. Moreover, ours could record the true positions for each device instead of the relative positions delivered in most of the previous studies. To this end, recording the user's access to the object on the desktop allows the user to interact with the smart device with simple actions. We present RFdesk, a contactless object location system that accurately locates every objects on the desktop. However, compare to tracking object withcontacted tag, several challenges are tackled before we make the system work. First of all, the signal employed for contactless tracking gets reflected twice which is thus much weaker, making the signal more susceptible to environmental noise and multipath. Another well-known challenge for contactless tracking is multi-target tracking as the signals reflected from multiple targets get mixed and interact. Extensive experiments show that RFdesk canflexibly deploy devices and tags, antennas, and localization itemscan be deployed on different planes. A median error of 3cm can be achieved for target tracking without attaching tags to the targets, even if there are 4 positioning objects on the desktop. Moreover, the average localization error can still be kept within 5.6cm outperforming the state-of-the-art systems by 100%.

The rapid development of the Internet of Things (IoT) has brought profound changes in the cloud computing paradigm. One promising computing model in IoT-related applications is edge computing, which can decrease the request response time by deploying edge servers close to IoT devices. Two fundamental problems in edge computing include how to place a limited number of edge servers on the candidate locations (e.g., the Access Points) and how to configure the applications on each server. In this paper, we jointly study the edge server placement and the application configuration to minimize the weighted sum of the service cost and edge server opening cost. We propose a local-search based algorithm, named SPAC, to solve the problem efficiently with its approximation ratio analyzed. Extensive simulations on Google data traces demonstrate SPAC reduces the total cost by up to 60% compared with state-of-the-art methods, and outperforms the baselines consistently in different parameter settings.

In this paper, we study online deadline-aware task dispatching and scheduling in edge computing. We jointly consider management of the networking bandwidth and computing resources to meet the maximum number of deadlines. We propose an online algorithm Dedas, which greedily schedules newly arriving tasks and considers whether to replace some existing tasks in order to make the new deadlines satisfied. We derive a non-trivial competitive ratio theoretically, and our analysis is asymptotically tight. We then build DeEdge, an edge computing testbed installed with typical latency-sensitive applications such as IoT sensor monitoring and face matching. Besides, we adopt a real-world data trace from the Google cluster for large-scale emulations. Extensive testbed experiments and simulations demonstrate that the deadline miss ratio of Dedas is stable for online tasks, which is reduced by up to 60% compared with state-of-the-art methods. Moreover, Dedas performs well in minimizing the average task completion time.

Motivated by practical scenarios in areas such as Mobile Edge Computing (MEC) and Content Delivery Networks (CDNs), we study online file caching on multiple caches, where a file request might be relayed to other caches or bypassed directly to the memory when a cache miss happens. We take the relaying, bypassing and fetching costs altogether into consideration. We first show the inherent difficulty of the problem even when the online requests are of uniform cost. We propose an O(log K)-competitive randomized algorithm Camul and an O(K)-competitive deterministic algorithm Camul-Det, where K is the total number of slots in all caches. Both online algorithms achieve asymptotically optimal competitive ratios, and can be implemented efficiently such that each request is processed in amortized constant time. We conduct extensive simulations on production data traces from Google and a benchmark workload from Yahoo. It shows that our algorithms dramatically outperform existing schemes, i.e., reducing the total cost by 85% and 43% respectively compared with important baselines and their strengthened versions with request relaying. More importantly, Camul achieves such a good total cost without sacrificing other performance measures, e.g., the hit ratio, and can perform consistently well on various settings of experiment parameters.

In Mobile Edge Computing (MEC), each edge server can be configured with only a small number of functions due to the limited capacity of various resources. Meanwhile, mobile applications become more complicated, consisting of multiple dependent tasks which are typically modeled as a Directed Acyclic Graph (DAG). In edge computing, when an application arrives, we need to place and schedule its tasks onto edge servers and/or the remote cloud, where the functions to execute the tasks are configured. In this work, we jointly consider the problem of dependent task placement and scheduling with on-demand function configuration on servers. Our objective is to minimize the application completion time. Specifically, for the special case when the configuration on each edge server is fixed, we derive an algorithm to find the optimal task placement and scheduling efficiently. When the on-demand function configuration is allowed, we propose a novel approximation algorithm, named GenDoc, and analyze theoretically its additive error from the optimal solution. Our extensive experiments on the cluster trace from Alibaba (including 20365 unique applications with DAG information) show that GenDoc outperforms state-of-the-art baselines in processing 86.14% of these unique applications, and reduces their average completion time by at least 24% (and up to 54%). Moreover, GenDoc consistently performs well on various settings of key parameters.

In edge-cloud computing, a set of servers (called edge servers) are deployed near the mobile devices to allow these devices to offload their jobs to and subsequently obtain their results from the edge servers with low latency. One fundamental problem in edge-cloud systems is how to dispatch and schedule the jobs so that the job response time (defined as the interval between the release of the job and the arrival of the computation result at the device) is minimized. In this paper, we propose a general model for this problem, where the jobs are generated in arbitrary order and at arbitrary times at the mobile devices and then offloaded to servers with both upload and download delays. Our goal is to minimize the total weighted response time of all the jobs. The weight is set based on how latency-sensitive the job is. We derive the first online job dispatching and scheduling algorithm in edge-clouds, called OnDisc, which is scalable in the speed augmentation model; that is, OnDisc is (1 + ε)-speed O(1/ε)-competitive for any small constant ε > 0. Moreover, OnDisc can be easily implemented in distributed systems. We also extend OnDisc with a fairness knob to incorporate the trade-off between the average job response time and the degree of fairness among jobs. Extensive simulations based on a real-world data-trace from Google show that OnDisc can reduce the total weighted response time dramatically compared with heuristic algorithms.

Efficient virtual machine (VM) management can dramatically reduce energy consumption in data centers. Existing VM management algorithms fall into two categories based on whether the VMs’ resource demands are assumed to be static or dynamic. The former category fails to maximize the resource utilization as they cannot adapt to the dynamic nature of VMs’ resource demands. Most approaches in the latter category are heuristic and lack theoretical performance guarantees. In this paper, we formulate the dynamic VM management as a large-scale Markov decision process (MDP) problem and derive an optimal solution. Our analysis of real-world data traces supports our choice of the modeling approach. However, solving the large-scale MDP problem suffers from the curse of dimensionality. Therefore, we further exploit the special structure of the problem and propose an approximate MDP-based dynamic VM management method, called MadVM. We prove the convergence of MadVM and analyze the bound of its approximation error. Moreover, we show that MadVM can be implemented in a distributed system with at most two times of the optimal migration cost. Extensive simulations based on two real-world workload traces show that MadVM achieves significant performance gains over two existing baseline approaches in power consumption, resource shortage, and the number of VM migrations. Specifically, the more intensely the resource demands fluctuate, the more MadVM outperforms.

A coflow is a collection of related parallel flows that occur typically between two stages of a multi-stage computing task in a network, such as shuffle flows in MapReduce. The coflow abstraction allows applications to convey their semantics to the network so that application-level requirements can be better satisfied. In this paper, we study the routing and scheduling of multiple coflows to minimize the total weighted coflow completion time (CCT). We first propose a rounding-based randomized approximation algorithm, called OneCoflow, for single coflow routing and scheduling. The multiple coflow problem is more challenging as coexisting coflows will compete for the same network resources, such as link bandwidth. To minimize the total weighted CCT, we derive an online multiple coflow routing and scheduling algorithm, called OMCoflow. We then derive a competitive ratio bound of our problem and prove that the competitive ratio of OMCoflow is nearly tight. To the best of our knowledge, this is the first online algorithm with theoretical performance guarantees which considers routing and scheduling simultaneously for multi-coflows. Compared with existing methods, OMCoflow runs more efficiently and avoids frequently rerouting the flows. Extensive simulations on a Facebook data trace show that OMCoflow outperforms the state-of-the-art heuristic schemes significantly (e.g., reducing the total weighted CCT by up to 41.8% and the execution time by up to 99.2% against RAPIER).

In this paper, the downlink file transmission in one cell with the assistance of cache nodes is studied. Specifically, the base station (BS) reactively delivers files to cache nodes and a requesting user in a multicast manner. Therefore, one file transmission may lead to the cache status update, which further affects the future file transmissions. We consider the joint optimization of file placement and delivery. In particular, we first formulate the optimization of transmission power and time in one finite file lifetime as a Markov Decision Process (MDP) with a random number of stages, where the objective is to minimize the transmission resource at the BS. It is shown that the optimal solution can be obtained via a revised Bellman's equation. Due to the curse of dimensionality, a novel approximation approach is proposed, where the value functions of the Bellman's equation can be calculated from analytical expressions. Hence, iterative algorithms, which appear in the general approximate MDP solutions, can be avoided. Moreover, an bound on the approximation error is also provided.

Coflow is gradually prevalent as a new traffic structure in data centers, which allows applications to convey their application-level semantics into the network. Meanwhile, optical circuit switches (OCS) are increasingly deployed in data centers due to the superiority in hardware, such as high bandwidth and low energy consumption. However, few works in the literature considered both coflow scheduling with OCS. In this paper, we study the coflow scheduling problem in an OCS-based data center network, with an aim to minimize the coflow completion time (CCT). We derive an online algorithm called OMCO to solve this problem. OMCO can not only optimize the circuit utilization but also minimize the number of circuit reconfigurations. Extensive simulations with real-world data traces show that OMCO outperforms other existing solutions dramatically. Compared with a FIFO-based scheme and the shortest-coflow-first heuristic, OMCO reduces the average coflow completion time by up to 61% and 62%, respectively.

Heterogeneous cellular networks (HetNets) can significantly improve the spectrum efficiency, where low-power low-complexity base stations (Pico-BSs) are deployed inside the coverage of macro base stations (Macro-BSs). Due to cross-tier interference, joint detection of the uplink signals is widely adopted so that a Pico-BS can either detect the uplink signals locally or forward them to the Macro-BS for processing. The latter can achieve increased throughput at the cost of additional backhaul transmission. However, in existing literature the delay of the backhaul links was often neglected. In this paper, we study the delay-optimal uplink scheduling problem in HetNets with limited backhaul capacity. Local signal detection or joint signal detection is scheduled in a unified delay-optimal framework. Specifically, we first prove that the problem is NP-hard and then formulate it as a Markov Decision Process problem. We propose an efficient and effective algorithm, called OLIUS, that can deal with the exponentially growing state and action spaces. Furthermore, OLIUS is online learning based which does not require any prior statistical knowledge on user behavior or channel characteristics. We prove the convergence of OLIUS and derive an upper bound on its approximation error. Extensive experiments in various scenarios show that our algorithm outperforms existing methods in reducing delay and power consumption.

In edge-cloud computing, a set of edge servers are deployed near the mobile devices such that these devices can offload jobs to the servers with low latency. One fundamental and critical problem in edge-cloud systems is how to dispatch and schedule the jobs so that the job response time (defined as the interval between the release of a job and the arrival of the computation result at its device) is minimized. In this paper, we propose a general model for this problem, where the jobs are generated in arbitrary order and times at the mobile devices and offloaded to servers with both upload and download delays. Our goal is to minimize the total weighted response time over all the jobs. The weight is set based on how latency sensitive the job is. We derive the first online job dispatching and scheduling algorithm in edge-clouds, called OnDisc, which is scalable in the speed augmentation model; that is, OnDisc is (1 + ε)-speed O(1/ε)-competitive for any constant ε ϵ (0,1). Moreover, OnDisc can be easily implemented in distributed systems. Extensive simulations on a real-world data-trace from Google show that OnDisc can reduce the total weighted response time dramatically compared with heuristic algorithms.

Mobile crowdsourcing has been proposed as a promising approach for urban data collection, but it has also brought the critical problem of designing proper mechanisms to incentivize user participation. Most previous work on crowdsourcing incentivization has assumed that each user holds a single private cost for participation or behaves in a "win all or nothing" (a.k.a. "single-minded") manner. However, in some crowdsourcing applications such as Amazon's Mechanical Turk, the users are usually "multi-minded" in the sense that each of them holds heterogeneous private costs for different tasks and only performs a portion of her/his interested tasks according to the announced payments. To address this problem, we propose LIME, an onLine prIcing mechanism to incentivize Multi-minded usErs under the scenario where the users arrive sequentially in an arbitrary order. We show that the design of LIME involves solving a "dummy semi-bandits with multiple knapsacks and random costs" problem, which has not been investigated before, and we also prove that LIME achieves several desirable properties including computational efficiency, budget feasibility, truthfulness, individual rationality and low regret on the utility. Finally, the effectiveness of LIME as well as its superiorities over prior related work are demonstrated through extensive simulations.

Motivated by practical scenarios, we study congestion games with failures. We investigate two models. The first model is congestion games with both resource and agent failures, where each agent chooses the same number of resources with the minimum expected cost. We prove that the game is potential and hence admits at least one pure-strategy Nash equilibrium (pure-NE). We also show that the Price of Anarchy and the Price of Stability are bounded (equal to 1 in some cases). The second model is congestion games with only resource failures (CG-CRF), where resources are provided in packages, and their failures can be correlated with each other. Each agent can choose multiple packages for reliability’s sake and utilize the survived one having the minimum cost. CG-CRF is shown to be not potential. We prove that it admits at least one pure-NE by constructing one efficiently. Finally, we discuss various applications of these two games in the networking field. To the best of our knowledge, this is the first paper studying congestion games with the coexistence of resource and agent failures, and we give also the first proof of the existence of a pure-NE in congestion games with correlated package failures.

Efficient virtual machine (VM) management can dramatically reduce energy consumption in data centers. Existing VM management algorithms fall into two categories based on whether the VMs' resource demands are assumed to be static or dynamic. The former category fails to maximize the resource utilization as they cannot adapt to the dynamic nature of VMs' resource demands. Most approaches in the latter category are heuristical and lack theoretical performance guarantees. In this work, we formulate dynamic VM management as a large-scale Markov Decision Process (MDP) problem and derive an optimal solution. Our analysis of real-world data traces supports our choice of the modeling approach. However, solving the large-scale MDP problem suffers from the curse of dimensionality. Therefore, we further exploit the special structure of the problem and propose an approximate MDP-based dynamic VM management method, called MadVM. We prove the convergence of MadVM and analyze the bound of its approximation error. Moreover, MadVM can be implemented in a distributed system, which should suit the needs of real data centers. Extensive simulations based on two real-world workload traces show that MadVM achieves significant performance gains over two existing baseline approaches in power consumption, resource shortage and the number of VM migrations. Specifically, the more intensely the resource demands fluctuate, the more MadVM outperforms.

A coflow is a collection of related parallel flows that occur typically between two stages of a multi-stage compute task in a network, such as shuffle flows in MapReduce. The coflow abstraction allows applications to convey their semantics to the network so that application-level requirements (e.g., minimizing the completion time of the slowest flow) can be better satisfied. In this paper, we study the routing and scheduling of multiple coflows to minimize the average coflow completion time (CCT). We first propose a rounding-based randomized approximation algorithm, called OneCoflow, for single coflow routing and scheduling. The multiple coflow problem is more challenging as coexisting coflows will compete for the same network resources such as link bandwidths. To minimize the average CCT, we derive an online multiple coflow routing and scheduling algorithm, called OMCoflow, and prove that it has a reasonably good competitive ratio. To the best of our knowledge, this is the first online algorithm with theoretical performance guarantees which considers routing and scheduling simultaneously for multi-coflows. Compared with existing methods, OMCoflow runs more efficiently, and it avoids the problem of frequently rerouting the flows. Extensive simulations on a Facebook data trace show that OMCoflow outperforms the state-of-the-art heuristic schemes significantly (e.g., reducing the average CCT by up to 41.8% and the execution time by up to 99.2% against RAPIER [28]).

Current large-scale computing services, such as online social networking and web searching, make the wired links in the data centers with an Ethernet infrastructure oversubscribed. Therefore, researchers consider to augment the data centers with wireless communication, called a hybrid data center network (HDCN), to improve the communication flexibility and network capacity. In this paper, we investigate how to use the wireless communication in hybrid DCNs from a cross-layer view. In the network layer, we propose a routing protocol to minimize the number of hops for data flows, and a congestion control protocol to reduce the congestion and deal with sporadic link failure. In the physical layer, we study the channel and power allocation problem with the SINR and QoS constraints in hybrid DCNs. In single channel scenarios, we prove the problem to be a geometric programming problem. In multi-channel scenarios, we prove the problem to be NP-hard and propose a Greedy based Online Channel and Power Allocation (GOCPA) algorithm. Our proposed protocols in network and physical layers collaborate to manage the wireless communication in hybrid DCNs. Extensive simulations show that our protocols can significantly increase the network throughput, decrease the latency, and moreover increase the robustness of the networks.

It has been shown in the existing literature that data symbols could help to relieve the pilot contamination issue of massive multiple-input multiple-output systems. In this paper, we show that pilot information of interference users could be exploited jointly with the data-assisted transmission mechanism. Specifically, we consider the uplink transmission of a massive multiple-input multiple-output network where there are backhauls with significant delay between base stations. Although real-time inter-base station cooperation is infeasible; pilot information, whose update frequency is very low, of closest interference users can be notified to the serving base station. Conventionally, estimating the interference channel will lead to larger pilot overhead. In our proposed scheme, however, the detected uplink data could provide sufficient degree- of-freedom to estimate the channels of the closest interference users without increasing pilot overhead. Hence, the inter-cell interference can be suppressed efficiently. In order to obtain useful insights on system-level performance, a stochastic geometry based framework is established to analyze the distribution of the signal-to-interference ratio of the proposed scheme. The closed-from expression of the asymptotic bound is thereby derived. It is shown that the analytical expression fits the numerical simulations very well, and the proposed scheme has significant gain over the data-assisted uplink scheme without backhaul.

In Cognitive Radio Networks (CRNs), a fundamental operation for the secondary users (SUs) is to establish communication through choosing a common available channel at the same time slot, which is referred to as rendezvous. In this paper, we study fast rendezvous for two SUs.

In Hybrid networks, which synergistically mix together wired and wireless links to achieve flexible and reliable communication, it is particularly challenging to routing selfish tasks since each task wish to finish transmission as early as possible and its decision could have impacts on the others. In this paper, we investigate the problem to route a given set of selfish tasks in hybrid networks. Under a unified cost model, the competitive behaviors of selfish players are modeled as a noncooperative game. We show the game is ordinal potential, and the existence of a pure-Nash Equilibrium (pure-NE) is therefore guaranteed. We also design a routing scheme, called Selfish Task-Driven Routing (STaR), to achieve a pure-NE. Extensive simulations show that our scheme can not only efficiently converge to an equilibrium but also outperform other source routing protocols regarding the completion time and load balancing.

A novel data-assisted channel estimation scheme is proposed for uplink massive multiple-input multiple-output (MIMO) systems to alleviate the performance bottleneck due to pilot contamination. Specifically, the uplink resource within a fading block is first divided into a number of data blocks, which are encoded respectively; then the detected data blocks are utilized iteratively to refine the channel estimation, improving the signal-to-interference-plus-noise ratio (SINR) of the following data blocks. In the existing literature, the system performance can not scale up with the number of base station's antenna due to the effect of pilot contamination. The proposed scheme provides a promising approach to improve the uplink SINR by the order θ(LM/L+M) without increasing the length of pilot sequence, where L and M are the number of transmission symbols within a fading block and the number of base station's antennas respectively. It is shown by simulations that the uplink performance of massive MIMO systems is significantly increased by the proposed scheme.

Abstract We propose a generic pigment model suitable for digital painting in a wide range of genres including traditional Chinese painting and water‐based painting. The model embodies a simulation of the pigment‐water solution and its interaction with the brush and the paper at the level of pigment particles; such a level of detail is needed for achieving highly intricate effects by the artist. The simulation covers pigment diffusion and sorption processes at the paper surface, and aspects of pigment particle deposition on the paper. We follow rules and formulations from quantitative studies of adsorption and diffusion processes in surface chemistry and the textile industry. The result is a pigment model that spans a continuum from the very wet to the very dry brush stroke effects. We also propose a new pigment mixing method based on machine learning techniques to emulate pigment mixing in real life as well as to support the creation of new artificial pigments. To experiment with the proposed model, we embedded the model in a sophisticated digital brush system. The combined system exhibits interactive speed on a modest PC platform. http://www.cs.hku.hk/~songhua/pigment provides supplementary materials for this paper.