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.

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.

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.

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.

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.

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.

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.

Motivated by the demand for energy efficiency improvement in mobile communication industry, we explore an idea of optimizing energy efficiency for MIMO-OFDM wireless communication systems while maintaining users' quality of service (QoS) requirement. Based on the binary power control scheme,a power allocation criterion for energy efficiency optimization is derived under the total power constraint. From a bit error rate (BER) point of view, a protection constraint is configured to guarantee the system QoS. With the aim of energy efficiency optimization under QoS guarantee in MIMO-OFDM wireless communication systems, an energy-efficient binary power control with BER constraint (EBPCB) algorithm is proposed based on the power allocation criterion and QoS constraint. Simulations results demonstrate the energy efficiency improvement of EBPCB.