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.

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.

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.

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

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

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.

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.