We study online task scheduling problems where tasks arrive sequentially and are processed by the platform or server. The service processes for tasks are multi-stage and are modeled as episodic Markov Decision Processes (MDPs). While processing a task, the system acquires rewards by consuming resources. The goal of the platform is to maximize the reward-to-cost ratio over a sequence of K tasks. Online scheduling with multi-stage tasks faces two major challenges: intra-dependence among the different stages within a task and inter-dependence among different tasks. These challenges are further exacerbated by the unknown rewards, costs, and task arrival distribution. To address these challenges, we propose the Robbins-Monro-based Value Iteration for Ratio Maximization (RM^2VI) algorithm. Specifically,RM^2VI addresses ``intra-dependence'' through optimistic value iteration and handles ``inter-dependence'' using the Robbins-Monro method. The algorithm has a greedy structure and achieves a sub-linear regret of O(K^(3/4)), establishing the no-regret property (per-task). We test RM^2VI in two synthetic experiments of sale promotion in E-commerce and machine learning job training in cloud computing. The results show RM^2VI achieves the best reward-to-cost ratio compared with the baselines.

Balancing helpfulness and safety (harmlessness) is a critical challenge in aligning large language models (LLMs). Current approaches often decouple these two objectives, training separate preference models for helpfulness and safety, while framing safety as a constraint within a constrained Markov Decision Process (CMDP) framework. This paper identifies a potential issue when using the widely adopted expected safety constraints for LLM safety alignment, termed "safety compensation'', where the constraints are satisfied on expectation, but individual prompts may trade off safety, resulting in some responses being overly restrictive while others remain unsafe. To address this issue, we propose **Rectified Policy Optimization (RePO)**, which replaces the expected safety constraint with critical safety constraints imposed on every prompt. At the core of RePO is a policy update mechanism driven by rectified policy gradients, which penalizes the strict safety violation of every prompt, thereby enhancing safety across nearly all prompts. Our experiments demonstrate that RePO outperforms strong baseline methods and significantly enhances LLM safety alignment.

As one of the most common ways for user authentication, Personal Identification Number (PIN), due to its simplicity and convenience, has suffered from plenty of side-channel attacks, which pose a severe threat to people’s privacy and property. The success of existing attacks is usually built upon the premise of no occlusion between the attacker and the victim’s hand gesture, but it increases the difficulty of launching the attack and the possibility of exposure. To overcome such limitation, we propose ArmSpy++, an improved video-assisted PIN inference attack built upon our previous research, ArmSpy. Specifically, ArmSpy++ employs new modules to leverage more features like the keystroke-induced elbow bending, wrist speed variation, and the spatial relationship between different arm joints, to correctly detect Keystrokes. ArmSpy++ delves into the perspective relationship and natural typing habits to ensure a high success rate of PIN inference. We also re-designed the inferred PIN pattern coordination mechanism to accurately deduce the PINs. By using a pre-trained HigherHRNet model for posture estimation ArmSpy++ eliminates the necessity of additional training. The extensive experiments demonstrate that ArmSpy++ can achieve over 83.1% average accuracy with 3 attempts and even 92.5% for some victims, indicating the severity of the threat posed by ArmSpy++.

Constrained combinatorial contextual bandits have emerged as trending tools in intelligent systems and networks to model reward and cost signals under combinatorial decision-making. On one hand, both signals are complex functions of the context, e.g., in federated learning, training loss (negative reward) and energy consumption (cost) are nonlinear functions of edge devices’ system conditions (context). On the other hand, there are cumulative constraints on costs, e.g., the accumulated energy consumption should be budgeted by energy resources. Besides, real-time systems often require such constraints to be guaranteed anytime or in each round, e.g., ensuring anytime fairness for task assignment to maintain the credibility of crowdsourcing platforms for workers. This bandit setting presents significant challenges, including modeling complex rewards/costs, satisfying anytime cumulative constraints, and balancing exploration and exploitation. Therefore, we propose a primal-dual algorithm (Neural-PD) with neural network-based estimations for rewards/costs and virtual queue-based optimization for constraints. Besides, we provide theoretical guarantees regarding the behavior of neural network training within the primal-dual framework and the dynamic neural tangent kernel (NTK) of the neural networks during online learning. By integrating NTK theory and Lyapunov-drift techniques, we prove Neural-PD achieves a sharp regret bound and a zero constraint violation. We also show Neural-PD outperforms existing algorithms with extensive experiments on both synthetic and real-world datasets.

Physical layer-based secret key generation has garnered significant attention due to its inherent advantages of lightweight implementation, information-theoretic security, and broad applicability for mobile devices. The reciprocal randomness of the wireless channel ensures the consistent generation of secret bits between two communicating parties. However, it also suffers from the degradation of the efficiency of key generation attributed to the adverse impact of ambient noise, despite sustained efforts to mitigate the inconsistency during quantization. We find that a slight perturbation of the pilot signal, without affecting the correct reception of data frames, induces a corresponding change in the channel response, making it possibly adaptable to the target quantization strategies, thereby reducing the probability of key mismatch. Therefore, we take a different viewpoint on proactive contamination of the pilot signals to obtain the desired channel measurements for accurate physical layer secret key generation. Specifically, we design an adaptive pilot manipulation to avoid the expected channel measurements being too close to the quantization thresholds, enabling high quantization consistency. Furthermore, we also develop a random cross-threshold mechanism to prevent attackers from inferring the quantization results by monitoring the trend of pilot signal variations. A reliable long training sequence (LTS) modification mechanism is incorporated into our method to ensure communication performance by adaptively adjusting the scale of the pilot signal. To validate the effectiveness of our proposed method, we implement a prototype by re-configuring software modules in GNU radio running on the USRP platform. Extensive experiments demonstrate that our scheme outperforms existing representative quantization schemes with better key generation performance.

Optical image stabilization (OIS), powered by a special micro-electromechanical structure in the camera lenses to compensate for the optical distortion caused by camera shakes, has become an indispensable feature in many smartphones. However, we discover that this seemingly benign component can be exploited to eavesdrop on nearby audio signals, posing a significant threat to people's privacy during conversations or phone calls. Specifically, the OIS component can be influenced by external acoustic stimuli leading to slight vibrations, and at the same time, the coil and magnetized components inside the OIS induce electromagnetic leakage as they vibrate, according to Faraday's Law of Electromagnetic Induction. This electro-magnetic leakage contains voice information that can be used to recover the audio signals if intercepted by individuals with malicious intent. Inspired by the above discovery, we propose OISMic, a new acoustic eavesdropping attack that takes advantage of sound-induced OIS vibrations on smartphones. Unlike other existing acoustic eavesdropping attacks, eavesdropping exploiting OIS vibrations not only overcomes the constraints imposed by system permissions for many sensor-based approaches but is also immune to ultrasonic jammer that hinders the methods relying on microwave or light reflections to sense sound-induced vibrations. To execute this non-trivial attack in practical scenarios, we developed a prototype circuit that has a compact design capable of capturing the electromagnetic leakage caused by OIS vibrations. After converting the collected leaked electromagnetic signals into audio signals, a software-based phase-locked loop (PLL) method is developed to enhance the representation of voice components. Meanwhile, to reconstruct the weak audio signals, we also designed a diffusion-based neural network to learn the distribution of electromagnetic noise within the audio spectrum. Extensive experiments indicate that OISMic can accurately reconstruct voice under various scenarios, achieving an average word correct rate of 90.57 % across different devices.

The proliferation of edge computing has facilitated the edge-based artificial intelligence-generated content (AIGC) for ubiquitous and distributed end devices. To exemplify, we focus on the distributed implementation of one established instance, generative adversarial network (GAN), yielding the distributed GAN task. Practically speaking, this task usually is impeded by concerns including the unknown latency (of processing and transmission), the fairness requirement induced by heterogeneous distributed data and the limited energy budget of end devices. Besides, an often neglected factor is how to exploit feedback from networked end devices among which social ties indicate the flow of shared information. In practice, such social ties are partially observable to lack of exact knowledge of users, e.g., resulted from scarce historical data and privacy issues. Under this setting, we propose an online algorithm via integration of 1) online learning aided by graph neural network (GNN), aiming to recover social ties with GNN-based edge prediction, for accelerated learning of uncertainty and 2) online control to adaptively guarantee the constraints. We theoretically show that it not only achieves a sub-linear regret with guaranteed energy consumption and fairness but also leads to a superior global GAN. We also conduct simulations to justify its outperformance over online baselines.

Advanced edge systems have brought intelligence to networked end devices at the network edge. In such systems, privacy preservation has been an integral role since users' privacy may be violated via edge-device interaction given unsafe decision-making on information sharing. Therefore, we in this paper study privacy preservation for decision-making under bandit models. Particularly, a canonical bandit model features an agent that aims to maximize attainable rewards based on feedback from arm selection. However, upon application in edge systems, such feedback becomes more complex given 1) privacy concern and 2) non-negligible cost feedback. Confronting such concerns during decision-making, we study a privacy-preserving constrained bandit variant where we face the challenge of guaranteeing privacy preservation and within-budget cost while striving for high rewards. In this paper, we address the challenge with an integration of local differential privacy mechanism, online control, and online learning. Theoretically, we prove that our algorithm maintains adjustable privacy, adheres to cost constraints, and achieves a sub-linear regret (i.e., loss of reward). Numerically, we conduct simulations to demonstrate the outperformance of our algorithm over baselines.

Physical-layer key generation has emerged as a promising avenue for establishing secret keys using reciprocal channel measurements between wireless devices. However, channel reciprocity may suffer degradation from ambient noise and cause mismatched secret bits, while existing methods mitigating this issue may yet face limitations in key efficiency. The root cause behind such limitations is the heavy reliance on channel measurements, which can be naturally susceptible to channel non-reciprocity attributed to environmental factors. Instead of direct key extraction from channel measurements, we seek to share a pre-defined key and utilize channel measurements as a bearer to facilitate key transmission. We propose an accurate and efficient key generation method (KeyCome) to ensure secure key sharing by encapsulating it with channel state information (CSI) obfuscation matrices through circulant convolution. To this end, we develop a reliable key derivation through a quadratic programming method with matrix equilibration, ensuring stable and rapid solutions. Notably, the transmitter can control the key beforehand for enhanced communication efficiency and combine it with an error correction mechanism for accurate key derivation. Furthermore, a lightweight reconciliation scheme is designed to minimize mismatched bits caused by occasional non-reciprocity. Comprehensive experiments demonstrate KeyCome's high accuracy and efficiency in key generation.

Emoji prediction has been widely adopted in most mobile keyboards to improve the quality of user experience. Considering the resource constraints of smartphones, it is promising to deploy well-trained prediction models on edge servers, with which smartphones can carry out emoji prediction in an online fashion. However, a key issue in such a scenario lies in how the smartphone should select a subset of models to achieve high-accuracy and real-time emoji prediction with energy efficiency (a.k.a.themodel selectionproblem). Moreover, part of the system dynamics such as the prediction accuracy and the inference latency of each model are usually unknowna prioriin practice, further complicating the problem. In this paper, with an effective integration of history-aware online learning and online control, we propose the first green edge intelligence scheme to solve the model selection problem for mobile keyboard emoji prediction. Our theoretical analysis and simulation results verify the effectiveness of our proposed scheme in achieving a sub-linear round-averaged regret bound and energy efficiency with a high prediction accuracy and a low latency.

The pursuit of high-quality artificial intelligence generated contents (AIGC) with fast response has prompted the evolution of natural language processing (NLP) services, notably those enabled at the edge (i.e., edge NLP). For concreteness, we study distributed inference for next-word prediction which is a prevalent edge NLP service for mobile keyboards on user devices. Accordingly, we optimize coupled metrics,i.e., maximize prediction click-through rate (CTR) for improved quality-of-service (QoS), minimize user impatience for enhanced quality-of-experience (QoE), and keep energy consumption within budget for sustainability. Moreover, we consider the real-world setting where there is no prior knowledge of heterogeneous NLP models' prediction accuracy. Via an integration of online learning and online control, we propose a novel distributed inference algorithm for online next-word prediction with user impatience (DONUT) to estimate models' prediction accuracy and balance the trade-offs among coupled metrics. Our theoretical analysis reveals that DONUT achieves sub-linear regret (loss of CTR), ensures bounded user impatience, and maintains within-budget energy consumption. Through numerical simulations, we not only establish DONUT's superior performance over other baseline methods, but also demonstrate its adaptability to various settings.

Meta-learning has earned its wide popularity to handle a family of similar tasks (e.g., classification of pets and wildlife) with elaborately trained meta-knowledge (e.g., shared network architecture and neural network parameter initialization). In this paper, we focus on the distributed training of meta-knowledge via server-device collaboration at the edge (i.e., distributed meta-learning). Notably, its practical implementation often runs into concerns like 1) time-varying unknown wireless dynamics (e.g., transmission latency); 2) device-side fair device involvement in distributed training; 3) server-side resource efficiency. To address such concerns, 1) we employ online learning to estimate the unknown dynamics and further exploit social ties among device users to accelerate online learning; 2) we utilize online control techniques to handle long-term fairness and resource constraints. By characterizing inter-user social ties as a social graph, we study distributed meta-learning from the perspective of constrained graphical bandits. Therefore, we propose a SoCial-awarE meta-kNowledge dispaTch (SCENT) algorithm by effectively integrating graphical bandit learning and online control. Besides a sublinear regret (i.e., loss of performance), SCENT also guarantees a well-trained meta-knowledge under within-budget resource consumption and fair device involvement. We conduct simulations to justify the outperformance of SCENT compared with baselines.

The dueling bandit model has been acknowledged as an efficient analytic tool for sequential decision-making problems with qualitative pairwise comparison. For example, the comparison of workers' completion quality of assigned tasks in crowdsourcing systems; user's ranking of recommended items in recommender systems. In dueling bandits, an agent uses pairwise comparisons of selected arms to balance the exploitation-exploration trade-off during the online learning of uncertainties. Despite the wide application of dueling bandits, their green implementation should also consider the non-neglectable energy costs for selecting arms, implying the green dueling bandit model. Particularly, it requires online control to optimize energy costs adaptively in the long run for sustainable system deployment. Therefore, we 1) employ online learning methods to learn the uncertainties via qualitative pairwise comparisons; 2) utilize online control techniques to guarantee a within-budget energy cost for the green real-world deployment. Accordingly, we propose a Green Dueling Bandit Learning (GDBL) algorithm to effectively integrate dueling bandit learning for the exploration-exploitation trade-off and online control for the optimization of energy costs. We prove that GDBL achieves a sublinear round-averaged regret while keeping the energy cost under budget. We conduct simulations to demonstrate the outperformance of GDBL over baselines.

Rate-splitting multiple access (RSMA) has emerged as a potential non-orthogonal transmission strategy and powerful interference management scheme for 6G. Most of the existing works on RSMA beamforming design assume instantaneous or statistical channel state information (CSI) is available at the transmitter. Such an assumption however is impractical especially in massive multiple-input multiple-output (MIMO) due to the dynamic wireless environments and the challenges in channel estimation. In this work, we propose a novel beamforming design framework based on online learning and online control to adaptively learn the best precoding action for a RSMA-aided downlink massive MIMO without explicit CSI feedback. In particular, we first formulate the precoder selection problem that maximizes the ergodic sum-rate subject to a long-term transmit power constraint as a constrained combinatorial multi-armed bandit (CMAB) problem. Then we propose a precoder selection with bandit learning algorithm for RSMA (PBR). Our theoretical analysis shows that PBR achieves a sublinear regret bound with a long-term power constraint guarantee. Through experimental results, we not only verify our theoretical analysis but also demonstrate the outperformance of PBR in terms of sum-rate and power consumption compared with the conventional transmission schemes without using RSMA.

Constrained combinatorial contextual bandits have emerged as trending tools in intelligent systems and networks to model reward and cost signals under combinatorial decision-making. On one hand, both signals are complex functions of the context, e.g., in federated learning, training loss (negative reward) and energy consumption (cost) are nonlinear functions of edge devices’ system conditions (context). On the other hand, there are cumulative constraints on costs, e.g., the accumulated energy consumption should be budgeted by energy resources. Besides, real-time systems often require such constraints to be guaranteed anytime or in each round, e.g., ensuring anytime fairness for task assignment to maintain the credibility of crowdsourcing platforms for workers. This setting imposes a challenge on how to simultaneously achieve reward maximization while subjecting to anytime cumulative constraints. To address such challenge, we propose a primal-dual algorithm (Neural-PD) whose primal component adopts multi-layer perceptrons to estimate reward and cost functions, and its dual component estimates the Lagrange multiplier with the virtual queue. By integrating neural tangent kernel theory and Lyapunov-drift techniques, we prove Neural-PD achieves a sharp regret bound and a zero constraint violation. We also show Neural-PD outperforms existing algorithms with extensive experiments on both synthetic and real-world datasets.

In satellite-terrestrial integrated networks, it is a common practice to schedule real-time tasks from low Earth orbit (LEO) satellites to ground stations (GSs) for data processing. However, the joint task scheduling and resource allocation under unknown environment dynamics (e.g., transmission latency) remains to be a challenging problem. First, the tradeoff between task latencies and energy consumption should be carefully considered when making decisions to minimize task latencies under time-averaged energy consumption constraints. Second, to learn the environment uncertainties and minimize the system performance loss (i.e., regret) in terms of task latencies, both online feedback and offline history should be leveraged efficiently, and the accompanying exploration-exploitation tradeoff should be dealt with in a proper way. In this article, we formulate the joint task scheduling and resource allocation problem as a constrained combinatorial multi-armed bandit (CMAB) problem. To solve the problem, by integrating online learning, online control, and offline historical information, we propose aTask scheduling and Resource allocation scheme with Data-driven Bandit LearningcalledTRDBL. Our theoretical and numerical results show that TRDBL achieves a sublinear time-averaged regret while satisfying the time-averaged energy consumption constraints.

Recent neural rendering techniques have greatly benefited image-based modeling and relighting tasks. They provide a continuous, compact, and parallelable representation by modeling the plenoptic function as multilayer perceptrons (MLPs). However, vanilla MLPs suffer from spectral biases on multidimensional datasets. Recent rescues based on isotropic Fourier features mapping mitigate the problem but still fall short of handling heterogeneity across different dimensions, causing imbalanced regression and visual artifacts such as excessive blurs. We present an anisotropic random Fourier features (RFF) mapping scheme to tackle spectral biases. We first analyze the influence of bandwidth from a different perspective: we show that the optimal bandwidth exhibits strong correlations with the frequency spectrum of the training data across various dimensions. We then introduce an anisotropic feature mapping scheme with multiple bandwidths to model the multidimensional signal characteristics. We further propose an efficient bandwidth searching scheme through iterative golden-section search that can significantly reduce the training overload from polynomial time to logarithm. Our anisotropic scheme directly applies to neural surface light-field rendering and image-based relighting. Comprehensive experiments show that our scheme can more faithfully model lighting conditions and object features as well as preserve fine texture details and smooth view transitions even when angular and spatial samples are highly imbalanced.

The flourished edge intelligence has motivated the execution of machine learning tasks at the network edge. In this paper, we focus on distributing training, one of the core tasks, that is carried out by an edge server of limited communication capacity and multiple end devices. In distributed training, the key issue for the edge server is how to dynamically select a proper subset of end devices to periodically participate in the training. Such a dynamic end device selection problem is hindered by concerns like 1) unknown system dynamics, e.g., transmission latencies; 2) limited energy resources on end devices; and 3) unbalanced and non-IID data distribution over end devices. Therefore, the core challenge lies in the coordination of online learning and online control to fulfill both efficient learning of unknown statistics and guarantees of within-budget energy consumption and fairness selection. To address the above challenge, we first characterize the social ties among users of end devices as a social graph and then formulate the dynamic end device selection problem from the perspective of constrained graphical bandits. Under the formulation, we propose GRIND to effectively integrate graphical bandit learning methods with Lyapunov-drift techniques. The theoretical superiority of GRIND is not only 1) the achieved sub-linear round-averaged regret with satisfied long-term constraints but also 2) the characterization of graph structure with the independence number. Extensive simulations also verify the effectiveness of GRIND in terms of both latency reduction and long-term constraint satisfaction.

To cope with the high communication overhead caused by frequent aggregation of Federated Learning (FL) in Multi-access Edge Computing (MEC) scenarios, Hierarchical Federated Edge Learning (HFEL) is proposed as an evolving framework. HFEL offloads tasks to edge servers for partial model aggregation to reduce network traffic. However, most of the existing research focuses on resource optimization for HFEL without considering the impact of data characteristics and cannot guarantee the quality of FL training. To this end, we propose a task offloading approach based on data and resource heterogeneity under HFEL to improve training performance and reduce system cost. Specifically, we leverage information entropy to incorporate data statistical features into the cost function to reshape edge datasets. In addition, we applied Multi-Agent Deep Deterministic Policy Gradient (MADDPG) with a resource allocation module to generate distributed offloading policy more efficiently. Our algorithm not only adopts local observations to obtain the optimal action but also takes into account device heterogeneity, which can adapt to the unstable edge environment. Extensive experiments under multiple datasets and baselines are carried out, which demonstrate that our algorithm can effectively improve the accuracy of aggregated models while reducing system cost.

The scheme design of switch-controller association is an essential problem for software-defined networking (SDN) systems. A natural idea is to address the problem from the perspective of stable matching, since each switch (controller) often prefers to be associated with those controllers (switches) of lower communication costs and control traffic overhead. However, in practice, such system dynamics are usually unknown a priori, making it a challenging open problem. In this paper, we study such a problem of stable matching between switches and controllers with unknown communication costs from the perspective of multi-agent multi-armed bandit (MAMAB) learning. By integrating stable matching with online learning, we propose an effective Learning-aided Switch-controller Stable Matching (LS2M) scheme. Our theoretical analysis shows that LS2M effectively achieves a switch-optimal stable matching with a sublinear regret bound over time slots. Moreover, we conduct numerical simulations to verify the outperformance of LS2M over various baseline schemes.

In intelligent Internet of Things systems, data-hungry services are empowered by data collection, which is jointly accomplished by edge servers and data-collecting sensors. In this paper, we aim to achieve efficient data collection, i.e., maximize data rates from sensors to servers while mitigating the impact of data heterogeneity for data collected from sensors. Considering geographically distributed servers and sensors, we study the problem from the perspective of multi-agent multi-armed bandits. The key ideas of our approach are to 1) establish associations between servers and sensors under unknown wireless dynamics (i.e., channel state information) and selection fraction constraints; 2) utilize shared information via pairwise communication between servers to mitigate biased observations for data rates. To this end, we propose a scheme that leverages online learning to reduce uncertainties in wireless dynamics and online control to mitigate the impact of data heterogeneity. Based on an effective integration of bandit learning methods under pairwise communication and Lyapunov optimization techniques, we present a novel Decentralized sErver-Sensor association scheme with Multi-Agent learning under pairwise communication (DESMA). Our theoretical analysis demonstrates that DESMA achieves a tunable trade-off between maximizing data rate and mitigating the impact of data heterogeneity.

Most online service providers deploy their own data stream processing systems in the cloud to conduct large-scale and real-time data analytics. However, such systems, e.g., Apache Heron, often adopt naive scheduling schemes to distribute data streams (in the units of tuples) among processing instances, which may result in workload imbalance and system disruption. Hence, there still exists a mismatch between the temporal variations of data streams and such inflexible scheduling scheme designs. Besides, the fundamental limits of benefits of predictive scheduling to data stream processing systems remain unexplored. In this article, we focus on the problem of tuple scheduling with predictive service in Apache Heron. With a careful choice in the granularity of system modeling and decision making, we formulate the problem as a stochastic network optimization problem and proposePOTUS, an online predictive scheduling scheme that aims to minimize the response time of data stream processing by steering data streams in a distributed fashion. Theoretical analysis and simulation results show that POTUS achieves an ultra-low response time with a stability guarantee. Moreover, POTUS only requires mild-value of future information to effectively reduce the response time, even with mis-prediction.

For wireless caching networks, the scheme design for content delivery is non-trivial in the face of the following tradeoff. On one hand, to optimize overall throughput, users can associate their nearby APs with great channel capacities; however, this may lead to unstable queue backlogs on APs and prolong request delays. On the other hand, to ensure queue stability, some users may have to associate APs with inferior channel states, which would incur throughput loss. Moreover, for such systems, how to conduct predictive scheduling to reduce delays and the fundamental limits of its benefits remain unexplored. In this paper, we formulate the problem of online user-AP association and resource allocation for content delivery with predictive scheduling under a fixed content placement as a stochastic network optimization problem. By exploiting its unique structure, we transform the problem into a series of modular maximization sub-problems with matroid constraints. Then we devisePUARA, a Predictive User-AP Association and Resource Allocation scheme which achieves a provably near-optimal throughput with queue stability. Our theoretical analysis and simulation results show that PUARA can not only perform a tunable control between throughput maximization and queue stability, but also incur a notable delay reduction with predicted information.

Considering the contradiction between limited re-sources in small devices and the high complexity of deep neural networks (DNNs), DNNs can hardly run on small devices such as smartphones and wearable devices. Therefore, offloading DNNs to computing units (fog/edge servers), where each unit executes a part of a DNN collaboratively, has gained increasing popularity. Notably, DNNs are generally in chained structure, while streaming tasks are the central part of artificial-intelligent applications. Thus it is crucial to reduce chained DNNs' delay for streaming tasks. Although existing works have advanced DNN offloading largely, the discussion about chained DNNs and streaming tasks is negligible. To address this issue, in this paper, we propose a layer-level offloading model called OCDST based on the analysis about them. After chained DNNs are offloaded to computing units, the involved units will handle streaming tasks as a pipeline. Consequently, the model significantly reduces the average task delay by paralleling each step in the pipeline. Moreover, the global optimal model solution is drawn by an improved depth-first search (DFS) algorithm, which utilizes DFS to achieve path establishment, calculation and record stages. Based on multi-threading programming and producer-consumer pattern, a program parallelization scheme is also devised to ensure the feasibility of the obtained optimum. Experimental results show that OCDST significantly outperforms recent works with higher inferring speed and faster response.

Emoji prediction has been widely adopted in most mobile keyboards to improve the quality of user experience. Considering the energy limitations of smartphones, it is promising to consider deploying pre-trained prediction models on edge servers, with which smartphones can carry out emoji prediction in an online fashion. However, given a limited connection capacity, a key issue under such a scheme lies in how each smartphone should select a subset of models to achieve high-accuracy and real-time emoji prediction with energy efficiency (a.k.a. the model selection problem). Moreover, part of the system dynamics such as the accuracy and the latency of individual models are usually unknown a priori in practice, further complicating the problem. In this paper, with an effective integration of history-aware online learning and online control, we propose the first green edge intelligence scheme to solve the model selection problem for edge-assisted mobile keyboard emoji prediction. Our theoretical analysis and simulation results verify the effectiveness of our proposed scheme in achieving a sublinear regret bound and energy efficiency with high accuracy and low latency.

In satellite-terrestrial integrated networks, it is a common practice to distribute real-time tasks from low Earth orbit (LEO) satellites to ground stations (GSs) for data processing. However, it remains an open problem how to match tasks with proper GSs in an online fashion with unknown dynamics, e.g., transmission latency. Moreover, such a problem is further complicated by the non-trivial interaction between the decision-making procedure and long-term constraints on time-averaged energy consumptions. In this paper, by formulating the energy-constrained online matching problem with unknown transmission latency as a constrained Combinatorial Multi-Armed Bandit (CMAB) problem, we adopt bandit learning methods and virtual queue techniques to deal with the exploration-exploitation tradeoff and long-term constraints, respectively. With an effective integration of online learning and online control, we propose a Task-matching and Resource-allocation with Data-driven Bandit Learning (TRDBL) scheme. Our theoretical analysis shows that TRDBL achieves a sublinear regret bound with a time-averaged energy constraints guarantee in the long run. Through simulation results we not only verify our theoretical analysis but also demonstrate the outperformance of TRDBL in terms of both task latency reduction and energy efficiency.

In fog-assisted Internet-of-Things systems, it is a common practice to cache popular content at the network edge to achieve high quality of service. Due to uncertainties, in practice, such as unknown file popularities, the cache placement scheme design is still an open problem with unresolved challenges: 1) how to maintain time-averaged storage costs under budgets; 2) how to incorporate online learning to aid cache placement to minimize performance loss [also known as (a.k.a.) regret]; and 3) how to exploit offline historical information to further reduce regret. In this article, we formulate the cache placement problem with unknown file popularities as a constrained combinatorial multiarmed bandit problem. To solve the problem, we employ virtual queue techniques to manage time-averaged storage cost constraints, and adopt history-aware bandit learning methods to integrate offline historical information into the online learning procedure to handle the exploration–exploitation tradeoff. With an effective combination of online control and history-aware online learning, we devise a cache placement scheme with history-aware bandit learning calledCPHBL. Our theoretical analysis and simulations show that CPHBL achieves a sublinear time-averaged regret bound. Moreover, the simulation results verify CPHBL’s advantage over the deep reinforcement learning-based approach.

In fog computing systems, each fog node often maintains multiple interfaces to achieve simultaneous communications with end devices. To maximize the utilization of network capacities and avoid interference, a critical mission for each fog node is to allocate distinct channels to its interfaces, also known as multi-interface channel allocation, to maximize the total throughput by successful transmissions. However, the effective allocation scheme design is challenging because the full knowledge of channel state dynamics is often hard to attain in practice. Faced with such uncertainties, online learning is needed to cooperate with online decision making. In this article, we devise an integrated design to conduct such multi-interface channel allocation in fog computing systems. Specifically, by formulating the channel allocation problem in the settings of multiarmed bandit with multiple plays and leveraging Thompson sampling techniques, we propose a multi-interface channel allocation with binary feedback (MICA-B) scheme, which makes online channel allocation decisions through effective learning from binary transmission feedback. Our theoretical analysis shows that MICA-B achieves a sublinear O(logT) regret bound on the performance loss (also known as regret) over a finite time horizon T. Based on MICA-B, we further exploit structure information of channel characteristics and design constrained MICA-B (CoMICA-B) to improve learning efficiency. Further, we propose multi-interface channel allocation with multilevel feedback (MICA-M) which extends MICA to handle more general cases with multilevel feedback information. Our simulation results verify the effectiveness and robustness of MICA-B, CoMICA-B, and MICA-M in terms of regret reduction.

For systems that are based on network function virtualization (NFV), it remains a key challenge to conduct effective service chain composition with the lowest request latency and the minimum network congestion. In such an NFV system, users are usually non-cooperative, i.e., they compete with each other to optimize their own benefits. However, existing solutions often ignore such non-cooperative behaviors of users. What is more, they may fall short in the face of unexpected resource failures such as breakdown of virtual machines and loss of connections to users. In this article, we formulate the service chain composition problem with resource failures in NFV systems as a non-cooperative game, and show that such a game is a weighted potential game, aiming to search for the optimal Nash equilibrium (NE). By adopting Markov approximation techniques, we devise a distributed scheme called MH-SCCA, which achieves a provably near-optimal NE and adapts to resource failures in a timely manner. For comparison, we also propose two baseline schemes (DRL-SCCA and MCTS-SCCA) for centralized service chain composition that are based on deep reinforcement learning (DRL) and Monte Carlo tree search (MCTS) techniques, respectively. Our simulation results demonstrate the effectiveness of the three proposed schemes in terms of both latency reduction and congestion mitigation, as well as the adaptivity of MH-SCCA when faced with resource failures.

In software-defined networking (SDN) systems, it is a common practice to adopt a multi-controller design and control devolution techniques to improve the performance of the control plane. However, in such systems the decision-making for joint switch-controller association and control devolution often involves various uncertainties, e.g., the temporal variations of controller accessibility, and computation and communication costs of switches. In practice, statistics of such uncertainties are unattainable and need to be learned in an online fashion, calling for an integrated design of learning and control. In this article, we formulate a stochastic network optimization problem that aims to minimize time-average system costs and ensure queue stability. By transforming the problem into a combinatorial multi-armed bandit problem with long-term stability constraints, we adopt bandit learning methods and optimal control techniques to handle the exploration-exploitation tradeoff and long-term stability constraints, respectively. Through an integrated design of online learning and online control, we propose an effective Learning-Aided Switch-Controller Association and Control Devolution (LASAC) scheme. Our theoretical analysis and simulation results show that LASAC achieves a tunable tradeoff between queue stability and system cost reduction with a sublinear time-averaged regret bound over a finite time horizon.

For NFV systems, the key design space includes the function chaining for network requests and the resource scheduling for servers. The problem is challenging since NFV systems usually require multiple (often conflicting) design objectives and the computational efficiency of real-time decision making with limited information. Furthermore, the benefits of predictive scheduling to NFV systems still remain unexplored. In this article, we propose POSCARS, an efficient predictive and online service chaining and resource scheduling scheme that achieves tunable trade-offs among various system metrics with stability guarantee. Through a careful choice of granularity in system modeling, we acquire a better understanding of the trade-offs in our design space. By a non-trivial transformation, we decouple the complex optimization problem into a series of online sub-problems to achieve the optimality with only limited information. By employing randomized load balancing techniques, we propose three variants of POSCARS to reduce the overheads of decision making. Theoretical analysis and simulations show that POSCARS and its variants require only mild-value of future information to achieve near-optimal system cost with an ultra-low request response time.

In this paper, we focus on the problem of online content placement with unknown content popularity in caching-enabled fog computing systems, i.e., how to decide and update cached content on resourcelimited edge fog nodes to maximize cache hit rate and minimize switching costs of content update. Faced with such uncertainties, the placement procedure must be well integrated with effective online learning while ensuring minimum performance loss (a.k.a. regret) due to improper content updates. To overcome such difficulties, we formulate the problem as a multi-play multi-armed bandit problem. By adopting Thompson sampling methods, we propose LACP, a learning-aided content placement scheme which continuously improves its online decision-making by proactively learning with hit-or-miss feedback information. Our theoretical and simulation results demonstrate the effectiveness of LACP against baseline schemes with an O(logT) regret over time horizon T.

In fog-assisted IoT systems, it is a common practice to offload tasks from IoT devices to their nearby fog nodes to reduce task processing latencies and energy consumptions. However, the design of online energy-efficient scheme is still an open problem because of various uncertainties in system dynamics such as processing capacities and transmission rates. Moreover, the decision-making process is constrained by resource limits on fog nodes and IoT devices, making the design even more complicated. In this paper, we formulate such a task offloading problem with unknown system dynamics as a combinatorial multi-armed bandit (CMAB) problem with long-term constraints on time-average energy consumptions. Through an effective integration of online learning and online control, we propose a Learning-Aided Green Offloading (LAGO) scheme. In LAGO, we employ bandit learning methods to handle the exploitation-exploration tradeoff and utilize virtual queue techniques to deal with the long-term constraints. Our theoretical analysis shows that LAGO can reduce the average task latency with an O(1/V + √(log T)/T) regret bound over time horizon T and satisfy the long-term time-average energy constraints, where V is a tunable positive parameter. We conduct extensive simulations to verify such theoretical results.

In fog-assisted IoT systems, it is a common practice to cache popular content at the network edge to achieve high quality of service. Due to various uncertainties such as unknown file popularities in practice, the design of effective cache placement scheme is still an open problem with two key challenges: 1) how to incorporate online learning into the cache placement process to minimize performance loss (a.k.a. regret), and 2) how to maintain caching costs under budgets in the long run. In this paper, we formulate the content cache placement problem with unknown file popularities as a combinatorial multi-armed bandit (CMAB) problem with long-term time-average constraints. We adopt bandit learning methods and virtual queue technique to deal with the exploration-exploitation tradeoff and long-term time-average constraints, respectively. With an effective integration of online learning and online control, we devise a learning-aided cache placement scheme called CPB (Cache Placement with Bandit Learning). Our theoretical analysis and simulation results show that CPB achieves a tunable sublinear regret over a finite time horizon and keeps caching costs within budgets in the long run.

In fog computing systems, each fog node often maintains multiple interfaces to achieve simultaneous communication with end devices. To maximize the utilization of network capacities and avoid interference, a critical mission for each fog node is to allocate distinct channels to its interfaces, a.k.a. multi-interface channel allocation, to maximize the total throughput by successful transmissions over time. However, the effective allocation scheme design is challenging because the full knowledge of channel state dynamics is often hard to attain in practice. Faced with such uncertainties, online learning is needed to cooperate with online decision making. In this paper, we devise an integrated design to conduct such multi-interface channel allocation in fog computing systems. Specifically, by formulating the channel allocation problem in the settings of multi-armed bandit with multiple plays and leveraging Thompson sampling techniques, we propose a Multi-Interface Channel Allocation with Binary feedback (MICAB) scheme, which makes online channel allocation decisions through effective learning from binary transmission feedback. Our theoretical analysis shows that MICA-B achieves a sublinear $O(\log T)$ regret bound over the performance loss (a.k.a regret) over a finite time horizon T. Further, we propose MICA-M which extends MICA to handle more general multi-level feedback information. Our simulation results verify the effectiveness and robustness of both MICA-B and MICA-M in terms of regret reduction.

For modern large-scale networked systems, ranging from cloud to edge computing systems, the topology design has a significant impact on the system performance in terms of scalability, cost, latency, throughput, and fault-tolerance. These performance metrics may conflict with each other and design criteria often vary across different networks. To date, there has been little theoretic foundation on topology designs from a prescriptive perspective, indicating that the current status quo of the design process is more of an art than a science. In this paper, we advocate a novel unified framework to describe, generate, and analyze topology design in a systematic fashion. By reverse-engineering existing topology designs and developing a fine-grained decomposition method for topology design, we propose a general procedure that serves as a common language to describe topology design. By proposing general criteria for the procedure, we devise a top-down approach to generate topology models, based on which we can systematically construct and analyze new topologies. To validate our approach, we leverage concrete tools based on combinatorial design theory and propose a novel layered topology model. With quantitative performance analysis, we reveal the trade-offs among performance metrics and generate new topologies with various advantages for different large-scale networks.

In software-defined networking (SDN) systems, it is a common practice to adopt a multi-controller design and control devolution techniques to improve the performance of the control plane. However, in such systems the decision making for joint switch-controller association and control devolution often involves various uncertainties, e.g., the temporal variations of controller accessibility, and computation and communication costs of switches. In practice, statistics of such uncertainties are unattainable and need to be learned in an online fashion, calling for an integrated design of learning and control. In this paper, we formulate a stochastic network optimization problem that aims to minimize time-average system costs and ensure queue stability. By transforming the problem into a combinatorial multi-armed bandit problem with long-term stability constraints, we adopt bandit learning methods and optimal control techniques to handle the exploration-exploitation tradeoff and long-term stability constraints, respectively. Through an integrated design of online learning and online control, we propose an effective Learning-Aided Switch-Controller Association and Control Devolution (LASAC) scheme. Our theoretical analysis and simulation results show that LASAC achieves a tunable tradeoff between queue stability and system cost reduction with a sublinear regret bound over a finite time horizon.

In multitiered fog computing systems, to accelerate the processing of computation-intensive tasks for real-time Internet of Things (IoT) applications, resource-limited IoT devices can offload part of their workloads to nearby fog nodes, whereafter such workloads may be offloaded to upper-tier fog nodes with greater computation capacities. Such hierarchical offloading, though promising to shorten processing latencies, may also induce excessive power consumptions and latencies for wireless transmissions. With the temporal variation of various system dynamics, such a tradeoff makes it rather challenging to conduct effective and online offloading decision making. Meanwhile, the fundamental benefits of predictive offloading to fog computing systems still remain unexplored. In this article, we focus on the problem of dynamic offloading and resource allocation with traffic prediction in multitiered fog computing systems. By formulating the problem as a stochastic network optimization problem, we aim to minimize the time-average power consumptions with stability guarantee for all queues in the system. We exploit unique problem structures and propose predictive offloading and resource allocation (PORA), an efficient and distributed PORA scheme for multitiered fog computing systems. Our theoretical analysis and simulation results show that PORA incurs near-optimal power consumptions with queue stability guarantee. Furthermore, PORA requires only mild value of predictive information to achieve a notable latency reduction, even with the prediction errors.

Fog computing has been promoted to support delay-sensitive applications in future Internet of Things (IoT). For a general heterogeneous fog network consisting of many dispersive fog nodes (FNs), it may well happen that some of them have delay-sensitive tasks to process, i.e., task nodes (TNs), and some have spare resources to help the TNs to process tasks, i.e., helper nodes (HNs). It remains a fundamental challenge to effectively map multiple tasks or TNs into multiple HNs to minimize every task's service delay in a distributed manner, i.e., the multitask multihelper (MTMH) problem. The problem becomes more challenging as tasks are splittable, i.e., tasks can be divided into multiple subtasks and offloaded to multiple HNs to further reduce the service delay via the scheme similar to distributed computing, because it introduces the more complicated task division problem which results in a much larger and more complex solution space. To tackle this challenge, in this article, a generalized Nash equilibrium problem (GNEP), called parallel offloading of splittable tasks (POST), is formulated and studied thoroughly. The structural properties of the problem are characterized and thus the existence of generalized Nash equilibrium (GNE) is proven via the fixed-point theorem. Furthermore, the corresponding distributed task offloading algorithm is developed via the Gauss-Seidel-type method. The simulation results show that the proposed POST algorithm can offer much better performance in terms of the system average delay, individual delay, delay reduction ratio (DRR), and number of beneficial TNs, compared with the existing solution to the counterpart problem for nonsplittable tasks.

Fog computing (FC) has the potential to process computation-intensive tasks in Industrial Internet of Things (IIoT) systems. In parallel with the development of FC, non-orthogonal multiple access (NOMA) has been recognized as a promising technique to significantly improve the spectrum efficiency. In this paper, a NOMA-based FC framework for IIoT systems is considered, where multiple task nodes offload their tasks via NOMA to multiple nearby helper nodes for execution. We formulate a joint task scheduling and subcarrier allocation problem, with an objective to minimize the total cost in terms of the delay and energy consumption, while taking into account the practical communication and computation constraints. Note that the task scheduling includes task, computation resource, and power allocations. Since the task and subcarrier allocations involve binary variables, it is challenging to obtain an optimal solution for such a combinatorial problem. To this end, we solve the task scheduling and subcarrier allocation problem in an online learning fashion. During the online learning process, we propose an iterative algorithm to jointly optimize the subcarrier allocation and task scheduling in each time episode. Simulation results show that the proposed scheme can significantly reduce the sum cost compared to the baseline schemes.

For software-defined networking (SDN) systems, to enhance the scalability and reliability of control plane, existing solutions adopt either multi-controller design with static switch-controller association, or static control devolution by delegating certain request processing back to switches. Such solutions can fall short in face of temporal variations of request traffics, incurring considerable local computation costs on switches and their communication costs to controllers. So far, it still remains an open problem to develop a joint online scheme that conducts dynamic switch-controller association and dynamic control devolution. In addition, the fundamental benefits of predictive scheduling to SDN systems still remain unexplored. In this paper, we identify the non-trivial trade-off in such a joint design and formulate a stochastic network optimization problem which aims to minimize time-averaged total system costs and ensure long-term queue stability. By exploiting the unique problem structure, we devise a predictive online switch-controller association and control devolution (POSCAD) scheme, which solves the problem through a series of online distributed decision making. Theoretical analysis shows that without prediction, POSCAD can achieve near-optimal total system costs a tunable trade-off for queue stability. With prediction, POSCAD can achieve even better performance with shorter latencies. We conduct extensive simulations to evaluate POSCAD. Notably, with mild-value of future information, POSCAD incurs a significant reduction in request latencies, even when faced with prediction errors.

A key challenge in the design space of fog computing systems is online task scheduling, i.e., to allocate multiple types of resources to pending tasks that are constantly generated from end devices. It is challenging because of the online, intensive, and time-varying nature of task arrival, the varieties in the amounts and durations of task resource demands, as well as the unattainability of such priori information due to the online nature of task arrivals. To handle such uncertainties, an online task scheduler design with flexibility to process sequences of task arrivals with variable lengths is highly demanded. Existing works have adopted deep reinforcement learning (DRL) techniques to develop online task schedulers in a data-driven fashion by constructing them as neural networks and training using empirical data. However, hindered by the intrinsic restriction of the underlying neural network design, such schedulers often suffer from poor flexibility that may induce resource under- utilization, or overly fine-grained control that induces considerable overheads. In this paper, we address the above challenges by integrating pointer network architecture with the scheduler design, and proposing Neural Task Scheduling (NTS), an online flexible task scheduling scheme which effectively reduces average task slowdown to facilitate best quality-of-service. Simulation results show that NTS consistently outperforms state-of-the-art schemes under different settings.

Deep neural networks (DNNs) are the key techniques to enable edge/fog intelligence. By far, it remains challenging to conduct distributed deployment of DNN models onto resource-constrained fog nodes with low latency. Existing solutions adopt either model compression techniques to reduce the computation loads on fog nodes, or horizontal model partition techniques, which exploit particular communication and computation patterns to partition different layers of DNNs onto fog nodes. Nonetheless, sometimes even resource demands of particular layers can be unaffordable to fog nodes, which makes horizontal partition inadequate and calls for the joint design of vertical and horizontal model partition. Besides, model partition and compression may lead to degraded inference accuracy, but approaches to compensate such accuracy loss remain unexplored.In this paper, we propose an integrated efficient distributed deep learning (EDDL) framework to address the above challenges. Particularly, we adopt balanced incomplete block design (BIBD) methods to reduce computation loads on fog nodes by removing some data flows in DNNs in a systematic and structured manner. By leveraging grouped convolution techniques, we propose a practical scheme to conduct horizontal and vertical model partition jointly. Moreover, we integrate multi-task learning and ensemble learning techniques to further improve the inference accuracy. Simulation results verify the effectiveness of EDDL framework in achieving notable reduction in computation load and memory footprint with mild loss of inference accuracy.

For NFV systems, the key design space includes the function chaining for network requests and resource scheduling for servers. The problem is challenging since NFV systems usually require multiple (often conflicting) design objectives and the computational efficiency of decision making with limited information. Besides, the limits and benefits of predictive scheduling to NFV systems still remain unexplored. In this paper, we propose POSCARS, an efficient, distributed, and online algorithm that achieves a tunable trade-off between various system metrics with stability guarantee, while exploiting the power of predictive scheduling. Using randomized load balancing techniques, we propose three variants of POSCARS to further reduce sampling overheads. Theoretical analysis and trace-driven simulations show that POSCARS and its variants require only mild-value of future information to achieve a near- optimal average system cost while effectively shortening the average request response time.

For data stream processing systems such as Apache Heron, workload imbalance across processing instances often causes significant system performance degradation. To mitigate such issues, Apache Heron leverages a naive throttling-based back-pressure scheme, which may lead to unexpected system disruption. This calls for a finer-grained control to distribute data stream units (tuples) between successive instances, a.k.a. tuple scheduling, which well adapts to data stream variations and workload discrepancy. Besides, the benefits of predictive scheduling to data stream processing systems still remain unexplored. In this paper, we formulate tuple scheduling problem as a stochastic network optimization problem, with careful choices in the granularity of system modeling and decision making. With non-trivial transformation, we decouple the problem into a series of online subproblems. By exploiting unique subproblem structure, we propose POTUS, an efficient, online, and distributed scheduling scheme that employs the power of predictive scheduling but requires only limited system dynamics to achieve a tunable trade-off between communication cost reduction and system queue stability. Theoretical analysis and simulations show that POTUS effectively shortens response time with mild-value of future information, even in the face of misprediction. Our solution is also applicable to other data stream processing systems.

Fog computing has risen as an evolving architecture to support delay-sensitive applications in Internet of Things (IoT) and next generation mobile networks. For a typical heterogeneous fog network consisting of many fog nodes, some of them have different computation tasks while some have spare computation resources, which forms a multi-task multi-helper (MTMH) network. How to effectively map multiple tasks into multiple helper nodes to reduce the service delay is a key issue to be resolved. To tackle this issue, a computation offloading problem minimizing every task's delay is considered, from the perspective of individuals. This problem is further formulated into a non-cooperative game, i.e., MTMH computation offloading (MTMHCO) game, to model the competition among tasks for helpers. The existence of Nash equilibrium (NE) is guaranteed and an efficient distributed algorithm is developed to achieve an NE for the MTMHCO game. Theoretical analysis and simulation results show that the proposed algorithm can offer the nearoptimal performance in system average delay and achieve more number of beneficial task nodes, at two orders of magnitude lower complexity than a centralized optimal algorithm.

Network functions virtualization (NFV) initiates a revolution of network service (NS) delivery by forming each NS as a chain of virtual network functions across commodity servers. However, it still remains a key challenge in NFV to decide the chains that induce short latency and low congestion, a.k.a. service chain composition problem. Existing works mainly resort to centralized solutions that require full knowledge of the network state to coordinate different users' traffic and NSs, overlooking privacy issues and the non-cooperative interactions among users. Moreover, handling the possible failures due to user/resource unavailability makes the problem even more challenging. By modeling the service chain composition problem with respect to both user and resource failures as a noncooperative game, we formulate the problem as searching the Nash Equilibrium (NE) with the optimal system performances. By exploiting the unique problem structure, we show that the game is a weighted potential game. We propose DISCCA, a distributed and low-complexity algorithm that guides the system towards the NE with short latency and low congestion, through decision making by individual users with local information. Results from extensive simulations show that DISCCA effectively achieves near-optimal system performances within mild-value of iterations, even in the presence of failures.

Fog computing is a promising paradigm that enables Internet-of-Things (IoT) applications with ultra-low latency and intensive computation. However, it is challenging to make efficient online decisions under varying system dynamics and intertwined power-latency tradeoffs. Moreover, the fundamental limits and benefits of predictive offloading in fog computing systems still remain unknown. In this paper, we study the problem of dynamic workload offloading and resource allocation in multi-tiered fog computing systems. By developing a fine-grained queue model and formulate a stochastic network optimization problem, we propose PORA, an efficient scheme that exploits predictive information to solve the problem. Results from our theoretical analysis and simulations show that PORA achieves a near-optimal power consumption with low latencies. Furthermore, PORA effectively reduces latencies with only mild-value of predictive information and it's robust against prediction errors.

For up-to-date data stream processing systems, e.g., Apache Heron, the distribution of processing units, a.k.a. instance placement, is determined in two stages, i.e., first mapping instances to containers and then mapping containers to servers. The placement, if improperly decided, can induce considerable traffic across servers and inefficient resource allocation. However, it is an open problem to decide the placement effectively, due to the complex interaction among instances, dependency between the decision making in two stages, and the trade-off between traffic reduction and resource utilization improvement. In this paper, we formulate such a problem as two sequential decision making problems. By adopting Monte Carlo Tree Search (MCTS) methods, we propose MIPS, i.e., a MCTS-based Instance Placement Scheme that decides the two-stage placement in a unified manner, achieving a well balance between computational efficiency and optimality. Results from simulations show that, with mild-value of samples, MIPS surpasses baseline schemes with significant improvement in both traffic reduction and utilization. To our best knowledge, this paper is the first to study and solve the two-staged mapping problem in such systems based on Heron.

In software-defined networking (SDN) systems, the scalability and reliability of the control plane still remain as major concerns. Existing solutions adopt either multi-controller designs or control devolution back to the data plane. The former requires a flexible yet efficient switch-controller association mechanism to adapt to workload changes and potential failures, while the latter demands timely decision making with low overheads. The integrate design for both is even more challenging. Meanwhile, the dramatic advancement in machine learning techniques has boosted the practice of predictive scheduling to improve the responsiveness in various systems. Nonetheless, so far little work has been conducted for SDN systems. In this paper, we study the joint problem of dynamic switch-controller association and control devolution, while investigating the benefits of predictive scheduling in SDN systems. We propose POSCAD, an efficient, online, and distributed scheme that exploits predictive future information to minimize the total system cost and the average request response time with queueing stability guarantee. Theoretical analysis and trace-driven simulation results show that POSCAD requires only mild-value of future information to achieve a near-optimal system cost and near-zero average request response time. Further, POSCAD is robust against mis-prediction to reduce the average request response time.

In fog computing systems, one key challenge is online task scheduling, i.e., to decide the resource allocation for tasks that are continuously generated from end devices. The design is challenging because of various uncertainties manifested in fog computing systems; e.g., tasks' resource demands remain unknown before their actual arrivals. Recent works have applied deep reinforcement learning (DRL) techniques to conduct online task scheduling and improve various objectives. However, they overlook the multi-resource fairness for different tasks, which is key to achieving fair resource sharing among tasks but in general non-trivial to achieve. Thus it is still an open problem to design an online task scheduling scheme with multi-resource fairness. In this paper, we address the above challenges. Particularly, by leveraging DRL techniques and adopting the idea of dominant resource fairness (DRF), we propose FairTS, an online task scheduling scheme that learns directly from experience to effectively shorten average task slowdown while ensuring multi-resource fairness among tasks. Simulation results show that FairTS outperforms state- of-the-art schemes with an ultra-low task slowdown and better resource fairness.

In fog-assisted IoT systems, to achieve best quality of service with ultra-low latency, resource-limited IoT user nodes may offload some tasks to nearby fog nodes, a.k.a. task offloading, to accelerate their processing. However, it remains non-trivial and challenging to decide when and which fog node to offload to. If offloaded, user tasks may experience unexpectedly long latency in face of system uncertainties, such as wireless channel dynamics, variety in task processing time, and resource contention on fog nodes. Moreover, feedback signals such as processing latency can be delayed and even go outdated due to non- stationarity, thereby degrading the effectiveness of system statistic learning and decision making. In this paper, we study task offloading problem for fog-assisted IoT systems in a non-stationary environment with delayed feedback. By leveraging a drift detector and queue methods, we propose TOS-BB and TOS-BS, two online task offloading schemes with bandit learning that endeavor to achieve ultra-low task latency. Simulation results show that both schemes outperform the benchmark while achieving close- to-optimal performance with short task latency.

Equipped with specific IoT on-board devices, un- manned aerial vehicles (UAVs) can be orchestrated to assist in particular value-added service delivery with improved quality-of- service. Typically, services are delegated in the unit of tasks to a designated leader UAV, while the leader UAV splits each task into sub- tasks and offloads them to part of its nearby UAVs, a.k.a. helper UAVs, for timely processing. Such a decision making pro- cess, often referred to as UAV task offloading, still remains open and challenging to design, due to various uncertainties therein, such as the resource availability and instant workloads on helper UAVs. However, existing solutions often assume the knowledge of system dynamics is fully available and conduct decision making in an offline manner, resulting in excessive control overheads and scalability issues. In this paper, we study the UAV task offloading problem in an online setting and formulate it as a multi-armed bandits (MAB) problem with time-varying resource constraints. Then we propose VR-LATOS, a learning- aided offloading scheme that learns the unknown statistics from feedback signals while making effective offloading decisions in an online fashion. Results from both theoretical analysis and simulations demonstrate that VR-LATOS outperforms state-of-the-art schemes.

Fog computing has recently emerged as a promising technique in content delivery wireless networks to alleviate the heavy bursty traffic burdens on backhaul connections. In order to improve the overall system performance, in terms of network throughput, service delay and fairness, it is very crucial and challenging to jointly optimize node assignments at control tier and resource allocation at access tier under dynamic user requirements and wireless network conditions. To solve this problem, in this paper, a fog-enabled multitier network architecture is proposed to model a typical content delivery wireless network with heterogeneous node capabilities in computing, communication, and storage. Further, based on Lyapunov optimization techniques, a new online low-complexity algorithm, namely fogenabled multitier operations scheduling (FEMOS), is developed to decompose the original complicated problem into two operations across different tiers. Rigorous performance analysis derives the tradeoff relationship between average network throughput and service delay, i.e., [O(1/V), O(V)] with a control parameter V, under FEMOS algorithm in dynamic wireless networks. For different network sizes and traffic loads, extensive simulation results show that FEMOS is a fair and efficient algorithm for all user terminals and, more importantly, it can offer much better performance, in terms of network throughput, service delay, and queue backlog, than traditional node assignment and resource allocation algorithms.

Caching is a promising technique to alleviate the capacity bottleneck of content-centric wireless networks (CCWNs). Most existing work of wireless caching networks focuses on the content placement policy, while some other interesting problems including dynamic user-AP association and predictive scheduling were rarely investigated. In this paper, we make the first attempt to investigate the benefit of such new degrees of freedom in wireless caching networks. Based on predictive service model, we formulate an average network throughput maximization problem with request queue stability constraints. We design the predictive user-AP association and resource allocation (P-UARA) algorithm, which is an online algorithm with theoretically guaranteed performance and does not require any statistical information of the system dynamics. Given the NP-hard user-AP association and bandwidth allocation optimization problem in P-UARA, we reformulate it and show the equivalence to the problem of modular function maximization subject to two matroid constraints. We propose an efficient greedy algorithm that guarantees a low bound 1/2 of the optimal value. Simulation results validate the theoretical analysis of our proposed algorithm and demonstrate the benefit of dynamic user-AP association and the predictive scheduling.

In software-defined networking (SDN), as data plane scale expands, scalability and reliability of the control plane have become major concerns. To mitigate such concerns, two kinds of solutions have been proposed separately. One is multi-controller architecture, i.e., a logically centralized control plane with physically distributed controllers. The other is control devolution, i.e., delegating control of some flows back to switches. Most of existing solutions adopt either static switch-controller association or static devolution, which may not adapt well to the traffic variation, leading to high communication costs between switches and controller, and high computation costs of switches. In this paper, we propose a novel scheme to jointly consider both solutions, i.e., we dynamically associate switches with controllers and dynamically devolve control of flows to switches. Our scheme is an efficient online algorithm that does not need the statistics of traffic flows. By adjusting some parameter V, we can make a trade-off between costs and queue backlogs. Theoretical analysis and extensive simulations show that our scheme yields much lower costs and latency compared to static schemes, and balanced loads among controllers.

Upload and download traffic often coexist in mobile networks. However, TCP download throughput could be substantially degraded by upload traffic even if the downlink is not the bottleneck. Previous works such as RSFC and TCP-RRE can substantially improve TCP download throughput in the presence of concurrent TCP upload flows, albeit at the expense of significantly degraded upload throughput performance. This work addresses this limitation by developing a novel Aggregate Transmission Rate Controller with Upload and Download flows aggregations (ATRC-UD) to jointly accelerate concurrent TCP upload and download flows from/to the same mobile device. The insight is that existing TCP as well as other flow-based approaches all suffer from ACK packets delayed by data packets from TCP flows in the opposite direction, resulting in significant errors in bandwidth estimation. By contrast, ATRC-UD exploits data packets of the opposite direction to enable continuously estimation of the downlink bandwidth and queueing delay even when ACK packets are significantly delayed. This allows ATRC-UD to track the bandwidth and delay variations more closely to maintain a shorter queue length at the downlink, thus jointly improve the download-upload throughput. Extensive emulated and real-world experiments showed that ATRC-UD enables TCP to achieve 96% downlink bandwidth utilization while improving uplink bandwidth utilization by over 115% compared to existing approaches, such as TCP-RRE and RSFC.

Wireless interference management through continuous power control has been extensively studied in the literature. However, practical systems often adopt discrete power control with a limited number of power levels and MCSs (Modulation Coding Schemes). In general, discrete power control is NP-hard due to its combinatorial nature. To tackle this challenge, we propose an innovative approach of interference management: ARM (Anonymous Rating Mechanism). Inspired by the successes of the simple anonymous rating mechanism in E-commerce, we develop ARM as distributed near-optimal algorithm for solving the discrete power control problem (i.e., the joint scheduling, power allocation, and modulation coding adaption problem) under the physical interference model. We show that ARM achieves a close-to-optimal network throughput with a low control overhead. We also characterize the performance gap of ARM with the theoretical optimal solution due to the loss of rating information, and study the trade-off between such gap and the convergence time of ARM. We present numerical results with practical parameter choices to validate the theoretical findings, and highlight the impacts of approximation factor, the number of power levels, and the incomplete rating information.

Wireless interference management through continuous power control has been extensively studied in the literature. However, practical systems often adopt discrete power control with a limited number of power levels and MCSs (Modulation Coding Schemes). In general, discrete power control is NP-hard due to its combinatorial nature. To tackle this challenge, we propose an innovative approach of interference management: ARM (Anonymous Rating Mechanism). Inspired by the successes of the simple Anonymous Rating Mechanism in Internet and E-commerce, we develop ARM as distributed near-optimal algorithm for solving the discrete power control problem (i.e., the joint scheduling, power allocation, and modulation coding adaption problem) under the physical interference model. We show that ARM achieves a close-to-optimal network throughput with a very low control overhead. We also characterize the performance gap of ARM due to the loss of rating information, and study the trade-off between such gap and the convergence time of ARM. Through comprehensive simulations under various network scenarios, we find that the optimality gap of ARM is small and such a small gap can be achievable with only a small number of power levels. Furthermore, the performance degradation is marginal if only limited local network information is available.

We study the problem of maximizing the broadcast rate in peer-to-peer (P2P) systems under node degree bounds, i.e., the number of neighbors a node can simultaneously connect to is upper-bounded. The problem is critical for supporting high-quality video streaming in P2P systems and is challenging due to its combinatorial nature. In this paper, we address this problem by providing the first distributed solution that achieves near-optimal broadcast rate under arbitrary node degree bounds and over arbitrary overlay graph. It runs on individual nodes and utilizes only the measurement from their one-hop neighbors, making the solution easy to implement and adaptable to peer churn and network dynamics. Our solution consists of two distributed algorithms proposed in this paper that can be of independent interests: a network-coding-based broadcasting algorithm that optimizes the broadcast rate given a topology, and a Markov-chain guided topology hopping algorithm that optimizes the topology. Our distributed broadcasting algorithm achieves the optimal broadcast rate over arbitrary P2P topology, while previously proposed distributed algorithms obtain optimality only for P2P complete graphs. We prove the optimality of our solution and its convergence to a neighborhood around the optimal equilibrium under noisy measurements or without time-scale separation assumptions. We demonstrate the effectiveness of our solution in simulations using uplink bandwidth statistics of Internet hosts.

Today's data centers are shared among multiple tenants running a wide range of applications. These applications require a network with a scalable and robust layer-2 network management solution that enables load-balancing and QoS provisioning. Ensemble routing was proposed to achieve management scalability and robustness by using Virtual Local Area Networks (VLANs) and operating on the granularity of flow ensembles, i.e. group of flows. The key challenge of intra-data-center traffic engineering with ensemble routing is the combinatorial optimization of VLAN assignment, i.e., optimally assigning flow ensembles to VLANs to achieve load balancing and low network costs. Based on the Markov approximation framework, we solve the VLAN assignment problem with a general objective function and arbitrary network topologies by designing approximation algorithms with close-to-optimal performance guarantees. We study several properties of our algorithms, including performance optimality, perturbation bound, convergence of algorithms and impacts of algorithmic parameter choices. Then we extend these results to variants of VLAN assignment problem, including interaction with TCP congestion and QoS considerations. We validate our analytical results by conducting extensive numerical experiments. The results show that our algorithms can be tuned to meet different temporal constraints, incorporate fine-grained traffic management, overcome traffic measurement limitations, and tolerate imprecise and incomplete traffic matrices.

Network coding has been applied widely in wireless networks. In this paper, we focus on the cross-layer optimization of wireless networks with multiple unicast sessions and network coding. By exploiting broadcast advantage and one hop opportunistic listening, we develop a fully distributed solution including primal-dual flow control, Markov chain based hyperlink scheduling, session-decomposition coding scheme and session scheduling. We further study the convergence property of the distributed solution without time-scale separation assumption. We show the convergence to optimum with some time-dependent step sizes and update intervals. We also show the convergence to the bounded neighborhood of optimum with constant step sizes and constant update intervals. Our numerical evaluations validate the analytical results. We emphasis that though the analysis for both cases is quite involved, the resulting distributed solutions are actually simple to implement.

Many important network design problems are fundamentally combinatorial optimization problems. A large number of such problems, however, cannot readily be tackled by distributed algorithms. The Markov approximation framework studied in this paper is a general technique for synthesizing distributed algorithms. We show that when using the log-sum-exp function to approximate the optimal value of any combinatorial problem, we end up with a solution that can be interpreted as the stationary probability distribution of a class of time-reversible Markov chains. Selected Markov chains among this class yield distributed algorithms that solve the log-sum-exp approximated combinatorial network optimization problem. By examining three applications, we illustrate that the Markov approximation technique not only provides fresh perspectives to existing distributed solutions, but also provides clues leading to the construction of new distributed algorithms in various domains with provable performance. We believe the Markov approximation techniques will find applications in many other network optimization problems.

In this paper we understand BitTorrent protocol from a Markov approximation perspective. We show that together with the underlying rate control algorithm, the rarest first algorithm and choking algorithm in BitTorrent protocol implicitly solve a cooperative combinatorial network utility maximization problem in a distributed manner. This understanding allows us to access properties of BitTorrent from a fresh perspective, including performance optimality, convergence and impacts of design parameters. Our numerical evaluations validate the analytical results.

We study the problem of neighbor selection in BitTorrent-like peer-to-peer (P2P) systems, and propose a "soft-worst-neighbor-choking" algorithm that is provably optimal. In practical P2P systems, peers often keep a large set of potential neighbors, but only simultaneously upload/download to/from a small subset of them, which we call active neighbors, to avoid excessive connection overhead. A natural question to ask is: which active neighbor set should each peer choose to maximize the global system performance? The combinatorial nature of the problem makes it especially challenging. In this paper, we formulate an optimization problem and derive a distributed algorithm. We remark that our solution has a similar favor compared to the worst neighbor choking and optimistic unchoking neighbor selection algorithms that are implemented by BitTorrent. However, it encourages peers to stick to better performing neighbors for longer time and is provably globally optimal. Our proposed solution is easy to implement: each peer periodically waits for a constant period of time that depends on the size of the potential neighbor set and the aggregated utility of the active neighbors, chokes (drops) one of its current active neighbors with probability proportional to an exponential weight on the utility of the corresponding link, and randomly unchokes (adds) a new neighbor from its potential neighbor set. Our theoretical findings provide insightful guidelines to designing practical P2P systems. Simulation results corroborate our proposed solution.

Network coding is a new paradigm in data transport that combines coding with data propagation over a network. Theory of linear network coding (LNC) adopts a linear coding scheme at every node of the network and promises the optimal data transmission rate from the source to all receivers. Linearity enhances the theoretic elegance and engineering simplicity, which leads to wide applicability. This paper reviews the basic theory of LNC and construction algorithms for optimal linear network codes. Exemplifying applications are presented, including random LNC. The fundamental theorem of LNC applies to only acyclic networks, but practical applications actually ignore the acyclic restriction. The theoretic justification for this involves convolutional network coding (CNC), which, however, incurs the difficulty of precise synchronization. The problem can be alleviated when CNC is generalized by selecting an appropriate structure in commutative algebra for data units. This paper tries to present the necessary algebraic concepts as much as possible in engineering language.

Peer-to-peer (P2P) systems have provided a scalable and cost effective way for file sharing and multimedia streaming in the past decade. The implementation of P2P systems usually involves two transmission schemes: routing (store-and-forward), and network coding. In this paper, we make a theoretical investigation of the rate that can be achieved by routing vs. network coding. We model P2P networks as node-capacitated networks with constraints on both node upload capacity and node download capacity. We compare routing and network coding for unicast, multicast and broadcast transmissions with both single-source scenario and multi-source scenario. Our results present not only a unification of existing results, but also extensions to new scenarios for node-capacitated networks.

Cross-layer optimization is a key step in wireless network design that coordinates the resources allocated to different layers in order to achieve globally optimal network performance. Existing work on cross-layer optimization for wireless networks often adopts simplistic physical-layer models for wireless channels, such as treating interference as noise or interference avoidance. This crude modeling of physical layer often leads to inefficient utilization of resources. In this paper, we adopt a deterministic channel model proposed in,, a simple abstraction of the physical layer that effectively captures the effect of channel strength, broadcast and superposition in wireless channels. This model allows us to go beyond “treating interference as noise” and as a consequence are able to achieve higher throughput and utility. Within the network utility maximization (NUM) framework, we study the cross-layer optimization for wireless networks based on this deterministic channel model. First, we extend the well-studied conflict graph model to capture the flow interactions over the deterministic channels and characterize the feasible rate region. Then we study distributed algorithms for general wireless multi-hop networks with both link-centric formulation and node-centric formulation. The convergence of algorithms is proved by applying Lyapunov stability theorem and stochastic approximation method. Further, we show the convergence to the bounded neighborhood of optimal solutions with probability one under constant step sizes and constant update intervals. Our numerical evaluations validate the analytical results and show the advantage of deterministic channel model over simple physical layer models such as treating interference as noise.

We study the problem of maximizing the broadcast rate in peer-to-peer (P2P) systems under node degree bounds, i.e., the number of neighbors a node can simultaneously connect to is upper-bounded. The problem is critical for supporting high-quality video streaming in P2P systems, and is challenging due to its combinatorial nature. In this paper, we address this problem by providing the first distributed solution that achieves near-optimal broadcast rate under arbitrary node degree bounds, and over arbitrary overlay graph. It runs on individual nodes and utilizes only the measurement from their one-hop neighbors, making the solution easy to implement and adaptable to peer churn and network dynamics. Our solution consists of two distributed algorithms proposed in this paper that can be of independent interests: a network-coding based broadcasting algorithm that optimizes the broadcast rate given a topology, and a Markov-chain guided topology hopping algorithm that optimizes the topology. Our distributed broadcasting algorithm achieves the optimal broadcast rate over arbitrary P2P topology, while previously proposed distributed algorithms obtain optimality only for P2P complete graphs. We prove the optimality of our solution and its convergence to a neighborhood around the optimal equilibrium under noisy measurements or without timescale separation assumptions. We demonstrate the effectiveness of our solution in simulations using uplink bandwidth statistics of Internet hosts.

Many important network design problems can be formulated as a combinatorial optimization problem. A large number of such problems, however, cannot readily be tackled by distributed algorithms. The Markov approximation framework studied in this paper is a general technique for synthesizing distributed algorithms. We show that when using the log-sum-exp function to approximate the optimal value of any combinatorial problem, we end up with a solution that can be interpreted as the stationary probability distribution of a class of time- reversible Markov chains. Certain carefully designed Markov chains among this class yield distributed algorithms that solve the log-sum-exp approximated combinatorial network optimization problem. By three case studies, we illustrate that Markov approximation technique not only can provide fresh perspective to existing distributed solutions, but also can help us generate new distributed algorithms in various domains with provable performance. We believe the Markov approximation framework will find applications in many network optimization problems, and this paper serves as a call for participation.

Existing work on cross-layer optimization for wireless networks adopts simple physical-layer models, i.e., treating interference as noise. In this paper, we adopt a deterministic channel model proposed in, a simple abstraction of the physical layer that effectively captures the effect of channel strength, broadcast and superposition in wireless channels. Within the Network Utility Maximization (NUM) framework, we study the cross-layer optimization for wireless networks based on this deterministic channel model. First, we extend the well-applied conflict graph model to capture the flow interactions over the deterministic channels and characterize the feasible rate region. Then we study distributed algorithms for general wireless multi-hop networks. The convergence of algorithms is proved by Lyapunov stability theorem and stochastic approximation method. Further, we show the convergence to the bounded neighborhood of optimal solutions with probability one under constant steps and constant update intervals. Our numerical evaluation validates the analytical results.

Node-capacitated networks are networks in which the capacity constraint is put on every node. They have recently attract attention as a good model for Peer-to-Peer (P2P) overlay networks. Existing work gives results on networks with constraints of node upload capacities. In this paper, we consider networks with constraints on both node upload and node download capacity. For such networks, we investigate the rate optimality of routing versus network coding. In general, network coding achieves a larger rate region than routing. However, for some important communication scenarios, routing achieves the same rate region as network coding.