Distributed Quantum Computing (DQC) expands qubit capacity by interconnecting multiple Quantum Processing Units (QPUs), but remote gate execution introduces significant entanglement overhead. In this paper, we study the Remote Gate Scheduling problem in DQC (RGS-DQC) under a hybrid Telegate and Teledata model, provide a formal formulation, and establish its NP hardness. To address this challenge, we proposeLABUBU, a layer buffered bundled optimization framework that integrates coordinate wise pruned greedy refinement with bounded perturbation under QPU capacity constraints while maintaining linear complexity per iteration. Extensive simulations on both structured Quantum Fourier Transform circuits and unstructured random circuits show that Labubu consistently reduces entanglement cost compared with Telegate-SA, Telegate-RD, Teledata-ZS, and the competitive GateCover baseline. Experiments on QEC encoded circuits further confirm its potential for large scale fault tolerant distributed quantum computing.

Quantum computing has the potential to outperform classical computing in solving specific problems. However, the limited qubit capacity of existing Quantum Processing Units (QPUs) poses significant barriers to the practical implementation of quantum computing. Distributed quantum computing (DQC) offers a promising approach to scaling the qubit capacity of quantum systems by interconnecting multiple QPUs and enabling collaborative computation. Nevertheless, DQC necessitates implementing remote quantum gate operations that consume entangled qubit pairs, which poses a significant challenge for DQC. In this work, we formulate and investigate the remote gate scheduling (RGS) problem, considering two approaches for remote gate operations: Telegate and Teledata. We propose a hybrid heuristic algorithm that dynamically schedules quantum gate operations within a circuit, executed on distributed QPUs, while minimizing entanglement consumption. We conducted extensive simulations using real-world quantum circuits and processors to evaluate the proposed approach. The results show that our approach reduces entanglement consumption by up to 90% and 25% compared to the two baselines, Telegate-SA and Teledata-ZS, respectively. Furthermore, the execution time of our approach is significantly shorter than that of the baselines.

Quantum computing, utilizing the unique properties of quantum mechanics, has the potential to revolutionize various fields. However, current quantum processors face challenges in scaling the number of qubits, limiting their practical applications. In response, Distributed Quantum Computing (DQC) has emerged as a promising paradigm where multiple interconnected Quantum Processing Units (QPUs) collaborate to execute quantum circuits. In this paper, we focus on designing networks to interconnect QPUs for the implementation of DQC. We find that in real-world experiments and systems, the photon collection and coupling efficiency is low, leading to significant performance degradation in direct connection networks. To address this limitation, we propose a novel multistage switching network tailored for DQC, which has low system complexity and high entanglement generation rates. The proposed switching network comprises$\log _{2}(N)$stages and$N/2$binary switches at each stage, where N represents the number of QPUs. We prove that the proposed network is nonblocking and develop an efficient routing algorithm with a time complexity of$\mathcal {O}(N\log (N))$. Additionally, we show the success probability of entanglement generation in the proposed switching network. Extensive simulations demonstrate that our network significantly outperforms the highly efficient circuit-switching Beneš network and three direct connection networks.

Quantum computing has the potential to solve complicated problems that are impossible for classical servers. Nevertheless, the applications of current quantum processors are restricted by their limited qubit capacity. Distributed Quantum Computing (DQC) is promising to scale up the computing capability by interconnecting quantum processors and performing computing collectively. The network interconnecting quantum processors can impact the efficiency of DQC. In this paper, we analyze and compare the performance of various interconnection networks for DQC. First, we meticulously derive the success probabilities of entanglement generation and the fidelity of shared Bell states generated within three typical static networks: line, ring, and grid. In addition, we propose a switching network with a minimal number of switch stages and evaluate its performance in terms of probability and fidelity. Moreover, we conduct extensive simulations based on real-world parameters to compare the static and switching networks, and the results reveal that the switching network performs better and is more scalable.

Distributed Quantum Computing (DQC) has the potential to solve industrial large-scale problems by connecting multiple small quantum processors together to form a larger computing system. Concerning the emerging distributed paradigm, a pivotal challenge lies in crafting specialized network topologies to establish efficient connections among quantum processors while minimizing communication costs. In this paper, we propose a novel DQC topology generation algorithm (DQC-TG) to create optimal and near-optimal network topologies for homogeneous and heterogeneous quantum computers, respectively. Furthermore, for specific quantum circuits requiring diverse communication demands between each pair of qubits, we extend the original algorithm into DQC- TG- Plus to design network topologies tailored for these circuits to further enhance the performance. We perform extensive simulations to evaluate the superiority of the generated network topology designs by our algorithms to baselines.

Network Function Virtualization (NFV) is becoming one of the most popular paradigms for providing cost-efficient, flexible, and easily-managed network services by migrating network functions from dedicated hardware to commercial general-purpose servers. Despite the benefits of NFV, it remains a challenge to deploy Service Function Chains (SFCs), placing virtual network functions (VNFs) and routing the corresponding flow between VNFs, in the edge-cloud continuum with the objective of jointly optimizing resource and latency. In this paper, we formulate the SFC Deployment Problem (SFCD). To address this NP-hard problem, we first introduce a constant approximation algorithm for a simplified SFCD limited at the edge, followed by a promotional algorithm for SFCD in the edge-cloud continuum, which also maintains a provable constant approximation ratio. Furthermore, we provide an online algorithm for deploying sequentially-arriving SFCs in the edge-cloud continuum and prove the online algorithm achieves a constant competitive ratio. Extensive simulations demonstrate that on average, the total costs of our offline and online algorithms are around 1.79 and 1.80 times the optimal results, respectively, and significantly smaller than the theoretical bounds. In addition, our proposed algorithms consistently outperform the popular benchmarks, showing the superiority of our algorithms.

With the proliferation of smart devices in recent years, many applications requiring high computing capability and low latency have emerged. Edge computing is one of the promising paradigms to support such applications. Due to the high volatility of edge environments, e.g., frequent movements of mobile devices, varying task sizes, and time-variant channel conditions, we have to make the offloading and resource management decisions on the fly. This paper formulates and studies the problem of online task offloading and resource management in heterogeneous mobile edge environments. The goal of the problem is to minimize the overall system latency. We prove that the problem is NP-hard. Moreover, traditional algorithms needing long decision-making times are insufficient to support applications with high volatility. This paper proposes a deep learning-assisted online algorithm that can make fast decisions. In particular, we design an offline solver for the proposed problem and use a deep neural network to emulate the solver. We conduct extensive simulations to evaluate the proposed approach. Results show that the proposed approach is around$50,000\times$and$500\times$faster than the commercial Gurobi solver for the optimal solution and the proposed offline approximation solver, respectively. Moreover, the overall latency under the proposed approach is near-optimal.

Mobile edge computing has emerged as a prevalent computing paradigm to support applications that demand low latency and high computational capacity. Hardware reconfigurable accelerators exhibit high energy efficiency and low latency compared to general-purpose servers, making them ideal for integration into mobile edge computing systems. This paper investigates the problem of joint task offloading, access point selection, and resource allocation in heterogeneous edge environments for latency minimization. Given the heterogeneity of edge computing devices and the interdependence of the decisions required for offloading, access point selection, and resource allocation, it is challenging to optimize over them simultaneously. We decomposed the proposed problem into two disjoint subproblems and developed algorithms for each of them. The first subproblem is to jointly determine access point selection and communication resource allocation decisions, for which we have proposed an algorithm with a provable approximation ratio of$2.62/(1-8\lambda )$, where$\lambda$is a tunable parameter balancing the approximation ratio and time complexity. Additionally, we offer a faster variant of the algorithm with an approximation ratio of$(\sqrt{3}+1)^{2}$. The second subproblem is to determine offloading and computing resource allocation decisions jointly and is NP-hard, where we developed algorithms based on relaxation and rounding. We conducted comprehensive numerical simulations to evaluate the proposed algorithms, and the results demonstrated that our algorithms outperformed existing baselines and achieved near-optimal performance across various settings.

With the rapid advancement of edge computing and network function virtualization, it is promising to provide flexible and low-latency network services at the edge. However, due to the vulnerability of edge services and the volatility of edge computing system states, i.e., service request rates, failure rates, and resource prices, it is challenging to minimize the online service cost while providing the availability guarantee. This paper considers the problem of online virtual network function backup under availability constraints (OVBAC) for cost minimization in edge environments. We formulate the problem based on the characteristics of the volatility system states derived from real-world data and show the hardness of the formulated problem. We use an online backup deployment scheme named Drift-Plus-Penalty (DPP) with provable near-optimal performance for the AVBAC problem. In particular, DPP needs to solve an integer programming problem at the beginning of each time slot. We propose a dynamic programming-based algorithm that can optimally solve the problem in pseudo-polynomial time. Extensive real-world data-driven simulations demonstrate that DPP significantly outperforms popular baselines used in practice.

Mobile edge computing with the near-data processing paradigm can support applications requiring low latency and high computing capability, where energy cost is a significant part of the expenditure. This paper formulates and studies the problem of online joint task offloading and resource allocation for latency minimization subjecting to a time average energy cost constraint in mobile edge computing systems. The formulated problem has four time-variant system states, i.e., data lengths, task sizes, channel conditions, and electricity prices, which are modeled based on real-world data. At the beginning of each time slot, the system has to make five online decisions jointly: base station selection, server selection for task offloading, communication bandwidth allocation, computing resource allocation, and frequency scaling. We prove the offline version of the formulated problem is NP-hard. We design an online algorithm with a provable approximation ratio and low computational complexity for the proposed problem. In particular, it balances energy cost and latency based on the drift-plus-penalty algorithm and makes server and base station selection decisions using a game theoretic-based algorithm. We conduct extensive real-world data-driven simulations to evaluate the proposed algorithm. Simulation results show that the proposed approach outperforms popular baselines.

Mobile edge computing is becoming one of the ubiquitous computing paradigms to support applications requiring low latency and high computing capability. FPGA-based reconfigurable accelerators have high energy efficiency and low latency compared to general-purpose servers. Therefore, it is natural to incorporate reconfigurable accelerators in mobile edge computing systems. This paper formulates and studies the problem of joint task offloading, access point selection, and resource allocation in heterogeneous edge environments for latency minimization. Due to the heterogeneity in edge computing devices and the coupling between offloading, access point selection, and resource allocation decisions, it is challenging to optimize over them simultaneously. We decomposed the proposed problem into two disjoint subproblems and developed algorithms for them. The first subproblem is to jointly determine offloading and computing resource allocation decisions and is NP-hard, where we developed an algorithm based on semidefinite relaxation. The second subproblem is to jointly determine access point selection and communication resource allocation decisions, where we proposed an algorithm with a provable approximation ratio of 2.62. We conducted extensive numerical simulations to evaluate the proposed algorithms. Results highlighted that the proposed algorithms outperformed baselines and were near-optimal over a wide range of settings.

Introducing the emerging serverless paradigm into edge computing could avoid over- and under-provisioning of limited edge resources and make complex edge resource management transparent to application developers, which largely facilitates the cost-effectiveness, portability, and short time-to-market of edge applications. However, the computation/data dispersion and device/network heterogeneity of edge environments prevent current serverless computing platforms from acclimating to the network edge. In this paper, we address such challenges by formulating a container placement and data flow routing problem, which fully considers the heterogeneity of edge networks and the overhead of operating serverless platforms on resource-limited edge servers. We design an online algorithm to solve the problem. We further show its local optimum for each arriving container and prove its theoretical guarantee to the optimal offline solution. We also conduct extensive simulations based on practical experiment results to show the advantages of the proposed algorithm over existing baselines.

Caching popular contents at the network edge is promising to reduce the retrieval latency, the network congestion, and the number of requests to the remote content provider during peak hours. In general, edge caching resource is costly and highly limited. Nevertheless, it is possible to provide cost-effective caching services using unreliable resources, which are resources reserved for other applications but have not been fully used or resources on vulnerable servers. In this paper, we consider the problem of caching popular contents over unreliable resources as a less expensive solution to limited edge caching capacity. In particular, to address the unreliability of edge resources, erasure coding is leveraged to increase the availability of cached contents. We formulate the problem as a discrete optimization problem and prove it is NP-hard. We start with two special cases of the problem and provide optimal algorithms for them. We then design an algorithm for the general version of the proposed problem and provide a provable performance guarantee. Real-world data-driven simulations demonstrate that the proposed algorithms significantly outperform popular baselines, and the rewards for the general version of the problem are near-optimal.

Wireless data collection requires a sequence of resource provisioning decisions due to the limited battery capacity of wireless sensors. The corresponding online resource provisioning problem is challenging. Recently, many prediction methods have been proposed that can be used to benefit the performance of various systems through their incorporation. Therefore, in this article, we focus on online resource provisioning problems with short-term predictions motivated by the wireless data collection problem. Specifically, we design separate online algorithms for systems in which the state evolves in either a stationary manner or an arbitrarily determined manner and prove their performance bounds where their bounds improve as the amount of available predictions increases. Additionally, we design a meta-algorithm that can choose which online algorithm to implement at each point in time, depending on the recent behavior of the system environment. The practical performances of the proposed algorithms are corroborated in trace-driven numerical simulations of data collection of shared bikes. Additionally, we show that the performance of our meta-algorithm in various system environments can be better than that of the single best algorithm chosen in hindsight.

Cloud computing is becoming one of the ubiquitous computing paradigms for enterprises and organizations in recent years. Due to the volatility of system states such as cloud resource price and workload demand, it is challenging to provision cloud resources efficiently. This paper studies online cloud resource provisioning problems under cost budget where no accurate or distributional future information is available. We develop an algorithmic framework and design online algorithms based on the framework. We prove the competitive ratio of the proposed algorithms. We further show the proposed algorithms have better performance than a prominent existing algorithm named CR-Pursuit. While prior works on the problem require the objective functions to be concave, the proposed algorithms work for non-convex and non-concave objective functions. We conduct real-world trace-driven simulations. Results highlight the proposed algorithms outperform baselines significantly over a wide range of settings.

With the advancement of edge computing and network function virtualization, it is promising to provide flexible and low-latency network services at the network edge. However, due to resource limitation and heterogeneity of servers at the edge, it is unlikely to achieve an efficient service function chain deployment without considering the resource management of edge servers jointly. In this article, we consider the Joint Service function chain Deployment and Resource Management problem (JSDRM) in heterogeneous edge environments with the goal of minimizing the total system latency. We prove the NP-hardness of JSDRM and propose a scheme called JOint service function chain deployment and resource management Scheme (JOS) based on a game-theoretic approach to deploy service function chains and manage resources. We prove that JOS has a constant approximation ratio of 2.62 Extensive simulation results show that our scheme performs comparably to the optimal solution and much better than the baselines. The simulation results also show that the proposed scheme is time-efficient.

The fast development of virtual network functions (VNFs) brings new challenges to providing reliability. The widely adopted approach of deploying backups incurs financial costs and environmental impacts. On the other hand, the recent trend of incorporating renewable energy into computing systems provides great potentials, yet the volatility of renewable energy generation presents significant operational challenges. In this paper, we optimize availability of VNFs under a limited backup budget and renewable energy using a dynamic strategy GVB. GVB applies a novel online algorithm to solve the VNF reliability optimization problem with non-stationary energy generation and VNF failures. Both theoretical bound and extensive simulation results highlight that GVB provides higher reliability compared with existing baselines.

We investigate the problem of stochastic network optimization in presence of non-stationarity and estimations of average states in the future. Specifically, we first prove that the widely-used Drift and Penalty Algorithm in the Lyapunov optimization framework works well for non-stationary systems with periodical states. However, when the system is not periodical, non-stationarity may lead to severe performance degradation, which motivates the design of a novel, online algorithm named DPNP that incorporates the estimations of average future states into the stochastic optimization framework for decision making. DPNP is an online algorithm that requires zero a-prior distributional information about estimation errors. DPNP not only has near-optimal theoretical performance guarantees, but also outperforms existing Drift and Penalty Algorithm in numerical simulations. The improvement of DPNP highlights the importance of combining historic and future state estimations in non-stationary stochastic network optimization.