Non-emergency municipal services, e.g., city 311 systems, have been widely implemented across cities in Canada and the United States to enhance residents' quality of life. These systems enable residents to report issues, e.g., noise complaints, missed garbage collection, and potholes, via phone calls, mobile applications, or webpages. However, residents are often given limited information about when their service requests will be addressed, which can reduce transparency, lower resident satisfaction, and increase the number of follow-up inquiries. Predicting the service time for municipal service requests is challenging due to several complex factors: (i) dynamic spatial-temporal correlations, (ii) underlying interactions among heterogeneous service request types, and (iii) high variation in service duration even within the same request category. In this work, we propose MuST2-Learn: a Multi-view Spatial-Temporal-Type Learning framework designed to address the aforementioned challenges by jointly modeling spatial, temporal, and service type dimensions. In detail, it incorporates an inter-type encoder to capture relationships among heterogeneous service request types and an intra-type variation encoder to model service time variation within homogeneous types. In addition, a spatiotemporal encoder is integrated to capture spatial and temporal correlations in each request type. The proposed framework is evaluated with extensive experiments using two real-world datasets. The results show that MuST2-Learn reduces mean absolute error by at least 32.5%, which outperforms state-of-the-art methods.

In today's rapidly evolving technological landscape, accurate object characterization is crucial for a wide range of applications, from autonomous systems to smart environments and security. Simultaneously, the growing concern for privacy necessitates innovative approaches that can characterize objects without compromising sensitive visual information. In this paper, we introduce a novel approach for object characterization using Radio Frequency (RF) propagation map generation through ray-tracing within a Digital Twin (DT) framework. We outline a systematic pipeline for leveraging NVIDIA's Sionna RayTracing tool to generate DT propagation maps created in Blender for indoor environments. Using these propagation maps, we propose a machine learning-based approach to facilitate object characterization. Our results demonstrate the feasibility of object characterization through strategic scene configuration using a small dataset that leverages RF maps within DTs. This paper provides valuable insights into the potential of our framework as a reliable and more efficient method for object characterization, offering a promising alternative to traditional vision-based techniques in scenarios where privacy concerns or environmental constraints limit the use of conventional imaging methods.

Secure data sharing and storage are critical to realizing the ultra-high safety and efficiency promised by intelligent transportation systems (ITS). However, ensuring data integrity under stringent resource constraints of ITS remains an open challenge. Existing approaches either incur substantial computational and transmission overhead or demand resources beyond what ITS environments can provide. To address this dilemma, we propose a lightweight blockchain-based data sharing and storage framework tailored for ITS. The system features a distributed, asynchronous reputation mechanism that enables trustworthy data evaluation and dissemination without burdening critical computing and communication paths. Additionally, a resource-efficient blockchain storage layer ensures low-latency, tamper-resistant access to locally shared data. Extensive simulations demonstrate that our approach outperforms existing solutions in both integrity assurance and resource efficiency.

Heterogeneous devices in edge computing bring challenges as well as opportunities for edge computing to utilize powerful and heterogeneous hardware for a variety of complex tasks. In this paper, we propose a service function chain placement strategy considering the heterogeneity of devices in deviceless edge computing environments. The service function chain system utilizes lightweight virtualization technologies to manage resources, considering the heterogeneity of devices to support various complex tasks, and offer low latency services to user requests. We propose an optimal service function chain placement problem minimizing the service delay and formulate it into a quasi-convex problem. We implement different edge applications that can be served by function chains and conduct extensive experiments over real heterogeneous edge devices. Results from the experiments and simulations show that our proposed service function chain scheme is applicable in edge environments, and perform well over services latency, resource utilization as well as the power consumption of edge devices.

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.

Network Function Virtualization (NFV) has the potential for cost-efficiency, manage-convenience, and flexibility services but meanwhile poses challenges for the service function chain (SFC) deployment problem, which is NP-hard. It is so complicated that existing work conspicuously neglects the flow changes along the chains and only gives heuristic algorithms without a performance guarantee. In this paper, we fill this gap by formulating a traffic-sensitive online joint SFC placement and flow routing (TO-JPR) model, with the objective of jointly optimize the resource cost and network latency, and proposing a novel two-stage scheme to solve it. We design a dynamic segmental packing (DSP) algorithm for the first stage, which not only maintains the minimal traffic burden for the network but also achieves an approximation ratio of a small constant on the resource cost. Besides, we propose the greedy mapping (GM) algorithm for the second stage, which can guarantee a global approximation ratio of O(d) on the network latency. Here d is the diameter of the network graph and is typically smaller than O(log(M)), where M is the number of servers in the network. Finally, we perform extensive simulations to demonstrate the outstanding performance of our algorithms compared with the optimal solutions and benchmarks.

Open Radio Access Networks (O-RANs) are transforming the landscape of telecommunications to better performance and higher cost-efficiency by enabling network operators to integrate diverse vendor components. Nevertheless, the involvement of multiple Network Service Providers (NSPs) and Mobile Network Operators (MNOs) also brings new challenges in the management of computation and network resources. To resolve this challenge, we propose a blockchain-based framework to guarantee secure, transparent, and decentralized resource allocation in O-RAN systems. Our resource allocation mainly considers the tradeoff of cost and service quality. Our design facilitates real-time adjustments to resource distribution based on dynamic network conditions and incorporates user feedback to optimize service quality continuously. By integrating a Proof-of-Reputation (PoR) consensus mechanism, the framework enhances the reliability and integrity of transactions among competing vendors without central oversight. We evaluate the performance of our design through extensive simulations, which demonstrate significant improvements over the baselines in resource utilization and service delivery across various network scenarios.

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.

Quantum Internet has potential capabilities far beyond the traditional Internet and is thus a promising future platform for communication and computation. Entanglement is a cornerstone of quantum mechanics and forms the basis of numerous quantum applications in the quantum Internet. While existing studies primarily focus on two-user entanglement, a plethora of applications necessitates the leap to multi-user entanglement. This paper tackles the fundamental problem of multi-user entanglement routing in the quantum Internet, aiming to entangle multiple quantum users with a high entanglement rate. We abstract the problem as a novel graph routing problem, which is not readily addressed by existing graph problem solutions due to the unique characteristics of the quantum Internet. To address this problem, we first consider a sufficient condition ensuring a feasible solution's existence and design an algorithm with the optimal solution. Given the NP-Completeness and NP- Hardness of determining a feasible solution's existence and deriving an optimal solution in general cases, respectively, we propose two heuristic algorithms to offer efficient solutions, which are shown, via extensive simulations, to outperform the existing algorithms in terms of entanglement rates.

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.

Serverless Computing and Function-as-a-Service (FaaS) offer convenient and transparent services to developers and users. The deployment and resource allocation of services are managed by the cloud service providers. Meanwhile, the development of smart mobile devices and network technology enables the collection and transmission of a huge amount of data, which shifts tasks to the network edge for mobile users. In this paper, we propose a deviceless edge computing system targeting the mobility of end users using the data migration of virtual functions. We focus on the adjustment of migration among virtual functions to provide uninterrupted services to mobile users. We introduce the deviceless edge computing model and propose a seamless data migration scheme of virtual functions with limited involvement of function developers. We formulate the migration decision problem into integer linear programming and use receding horizon control (RHC) for online solutions. We implement the migration system to support delay-sensitive scenarios over real edge devices and develop a streaming game as the virtual function to test the performance. Extensive experiments in real scenarios exhibit the system has the ability to support high-mobility and delay-sensitive application scenarios. Extensive simulation results show the applicability of the proposed system over large-scale networks.

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.

Network Function Virtualization (NFV) emerges as a promising paradigm with the potential for cost-efficiency, manage-convenience, and flexibility, where the service function chain (SFC) deployment scheme is a crucial technology. In this paper, we propose an Ant Colony Optimization (ACO) meta-heuristic algorithm for the Online SFC Deployment, called ACO-OSD, with the objectives of jointly minimizing the server operation cost and network latency. As a meta-heuristic algorithm, ACO-OSD performs better than the state-of-art heuristic algorithms, specifically 42.88% lower total cost on average. To reduce the time cost of ACO-OSD, we design two acceleration mechanisms: the Next-Fit (NF) strategy and the many-to-one model between SFC deployment schemes and ant-tours. Besides, for the scenarios requiring real-time decisions, we propose a novel online learning framework based on the ACO-OSD algorithm, called prior-based learning real-time placement (PLRP). It realizes near real-time SFC deployment with the time complexity of O(n), where n is the total number of VNFs of all newly arrived SFCs. It meanwhile maintains a performance advantage with 36.53% lower average total cost than the state-of-art heuristic algorithms. Finally, we perform extensive simulations to demonstrate the outstanding performance of ACO-OSD and PLRP compared with the benchmarks.

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.

Serverless Computing and Function-as-a-Service (FaaS) offer convenient and transparent services to developers and users. The deployment and resource allocation of services are managed by the cloud service providers. Meanwhile, the development of smart mobile devices and network technology enables the collection and transmission of a huge amount of data, which creates the mobile edge computing shifting tasks to the network edge for mobile users. In this paper, we propose a deviceless edge computing system targeting the mobility of end users. We focus on the migration of virtual functions to provide uninterrupted services to mobile users. We introduce the deviceless edge computing model and propose a seamless migration scheme of virtual functions with limited involvement of function developers. We formulate the migration decision problem into integer linear programming and use receding horizon control (RHC) for online solutions. We implement the migration system and algorithm to support delay-sensitive scenarios over real edge devices and develop a streaming game as the virtual function to test the performance. Extensive experiments in real scenarios exhibit the system has the ability to support high-mobility and delay-sensitive application scenarios. Extensive simulation results also show its applicability over large-scale networks.

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.

Network Function Virtualization (NFV) migrates network functions from proprietary hardware to commercial servers on the edge or cloud, making network services more cost-efficient, manage-convenient, and flexible. To facilitate these advantages, it is critical to find an optimal deployment of the chained virtual network functions, i.e. service function chains (SFCs), in hybrid edge-and-cloud environment, considering both resource and latency. It is an NP-hard problem. In this paper, we first limit the problem at the edge and design a constant approximation algorithm named chained next fit (CNF), where a sub-algorithm called double spanning tree (DST) is designed to deal with virtual network embedding. Then we take both cloud and edge resources into consideration and create a promotional algorithm called decreasing sorted, chained next fit (DCNF), which also has a provable constant approximation ratio. The simulation results demonstrate that the ratio between DCNF and the optimal solution is much smaller than the theoretical bound, approaching an average of 1.25. Moreover, DCNF always has a better performance than the benchmarks, which implies that it is a good candidate for joint resource and latency optimization in hybrid edge-and-cloud networks.

Network Function Virtualization (NFV) has the potential of cost-efficiency, manage-convenience, and flexibility but meanwhile poses challenges for the service function chain (SFC) deployment problem, which is NP-hard. It is so complicated that existing work conspicuously neglects the flow changes along the chains and only gives heuristic algorithms without a performance guarantee. In this paper, we fill this gap by formulating a traffic-sensitive online joint SFC placement and flow routing (TO-JPR) model and proposing a novel two-stage scheme to solve it. Moreover, we design a dynamic segmental packing (DSP) algorithm for the first stage, which not only maintains the minimal traffic burden for the network but also achieves an approximation ratio of 2 on the resource cost. Such a two-stage scheme and DSP can pave the way for efficiently solving TO-JPR. For example, simply applying the nearest neighbor (NN) algorithm for the second stage can guarantee a global approximation ratio of O(log(M)) on the network latency, where M is the number of servers. More future work can be done based on our scheme to get better performance on the network latency. Finally, we perform extensive simulations to demonstrate the outstanding performance of DSP+NN compared with the optimal solutions and benchmarks.

The fast development of mobile edge computing (MEC) and service virtualization brings new opportunities to the deployment of interactive applications, e.g., VR education, stream gaming, autopilot assistance, at the network edge for better performance. Ensuring quality of experience (QoE) for such services often requires the satisfaction of multiple quality of service (QoS) factors, e.g., short delay, high throughput rate, low packet loss. Nevertheless, existing mobile edge networks often fail to meet these requirements due to the mobility of end users and the volatility of network conditions. In this paper, we propose a novel scheme that both reduces delay and adjusts data throughput rate for QoE enhancement. We design an online service placement and throughput rate adjustment (SPTA) algorithm which coordinately migrates virtual services while tuning their data throughput rates based on real-time bandwidth fluctuation. By implementing a small-scale prototype supporting stream gaming at the edge, we show the necessity and feasibility of our work. Based on data from the experiments, we conduct real-world trace driven simulations to further demonstrate the advantages of our scheme over existing baselines.

The emerging network function virtualization is migrating traditional middleboxes, e.g., firewalls, load balancers, proxies, from dedicated hardware to virtual network functions (VNFs) running on commercial servers defined as network points of presence (N-PoPs). VNFs further chain up for more complex network services called service function chains (SFCs). SFCs introduce new flexibility and scalability which greatly reduce expenses and rolling out time of network services. However, chasing the lowest cost may lead to congestion on popular N-PoPs and links, thus resulting in performance degradation or violation of service-level agreements. To address this problem, we propose a novel scheme that reduces the operating cost and controls network congestion at the same time. It does so by placing VNFs and routing flows among them jointly. Given the problem is NP-hard, we design an approximation algorithm named candidate path selection (CPS) with a theoretical performance guarantee. We then consider cases when SFC demands fluctuate frequently. We propose an online candidate path selection (OCPS) algorithm to handle such cases considering the VNF migration cost. OCPS is designed to preserve good performance under various migration costs and prediction errors. Extensive simulation results highlight that CPS and OCPS algorithms perform better than baselines and comparably to the optimal solution.

Emerging virtual network functions (VNFs) bring new opportunities to network services on the edge within customers’ premises. Network services are realized by chained up VNFs, which are called service function chains (SFCs). These services are deployed on commercial edge servers for higher flexibility and scalability. Despite such promises, it is still unclear how to provide highly available and cost-effective SFCs under edge resource limitations and time-varying VNF failures. In this paper, we propose a novel Reliability-aware Adaptive Deployment scheme named RAD to efficiently place and back up SFCs over both the edge and the cloud. Specifically, RAD first deploys SFCs to fully utilize edge resources. It then uses both static backups and dynamic ones created on the fly to guarantee the availability under the resource limitation of edge networks. RAD does not assume failure rates of VNFs but instead strives to find the sweet spot between the desired availability of SFCs and the backup cost. Theoretical performance bounds, extensive simulations, and small-scale experiments highlight that RAD provides significantly higher availability with lower backup costs compared with existing baselines.

Network Functions Virtualisation (NFV) has a magnificent prospect due to its cost-efficiency, manage-convenience, and flexibility. To promote these advantages, the placement of virtual network functions (VNFs) is a key technology. In this paper, we focus on minimizing the total resources of used commercial servers to provide an optimal VNF placement scheme in edge networks. As for the NP-hard problem, we first design a Largest Fit Decreasing algorithm (LFD) with a provable constant approximation ratio of 2 and the computational complexity of$O(N^{2})$, where N is the number of VNFs. Besides, we improve it and further produce the Judge and Repeated Largest Fit Decreasing algorithm (JR-LFD), which has a bit larger computational complexity$O(kN^{2})$, but a smaller asymptotic approximation ratio of$\frac{3}{2}$, where k is the number of different server sizes. The simulation results demonstrate that the used resources derived by JR-LFD are always smaller than those by LFD. They both are extremely close to the optimal results and much smaller than the benchmark, which implies they improve the network resource utilization dramatically.

The development of Virtual Network Functions (VNFs) migrates network functions from dedicated hardware to groups of commodity servers called network points of presence (N-PoPs). In this way, network services are redefined as interconnected VNFs called Service Function Chains (SFCs). The emerging of SFCs significantly reduces the cost of network services and improves scalability. However, the availability of SFCs brings new challenges since a failure of any N-PoP along an SFC affects its availability. In this paper, we propose two rerouting strategies to improve the availability of SFCs. First, we propose a local rerouting strategy to bypass the failed N-PoPs on SFCs using locally rerouted paths (LRPs). In the strategy, we formulate an optimization model to minimize the maximum load on links while deploying SFCs and LRPs to reduce the risk of congested links caused by local rerouting. We then propose an approximation algorithm to solve the optimization problem, preserving an approximation ratio of$\mathcal {O}(\log (|V|))$, where$|V|$is the number of N-PoPs in the network. We also propose an alternative heuristic algorithm to improve efficiency. Second, we propose a supplementary rerouting strategy with an online algorithm to provide supplementary rerouted paths when original SFCs and corresponding LRPs fail at the same time in the local rerouting strategy. The online algorithm is proved to have an$\mathcal {O}(\log (|V|))$competitive ratio to the offline optimum. Finally, our extensive simulation results show that the proposed algorithms can provide highly available SFCs with less congested links.

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 opportunities to network service deployment on edge networks. For complicated services, VNFs can chain up to form service function chains (SFCs). Despite the promises, it is still not clear how to backup VNFs to minimize the cost while meeting the SFC availability requirements in an online manner. In this paper, we propose a novel self-adapting scheme named SAB to efficiently backup VNFs over both the edge and the cloud. Specifically, SAB uses both static backups and dynamic ones created on the fly to accommodate the resource limitation of edge networks. For each VNF backup, SAB determines whether to place it on the edge or the cloud, and if on the edge, which edge server to use for load balancing. SAB does not assume failure rates of VNFs but instead strives to find the sweet point between the desired availability of SFCs and the backup cost. Both theoretical performance bounds and extensive simulation results highlight that SAB provides significantly higher availability with lower backup cost compared with existing baselines.

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.

Emerging virtual network functions (VNFs) introduce new flexibility and scalability into traditional middlebox. Specifically, middleboxes are virtualized as software-based platforms running on commodity servers known as network points of presence (N-PoPs). Traditional network services are therefore realized by chained VNFs, i.e., service function chains (SFCs), running on potentially multiple N-PoPs. SFCs can be flexibly placed and routed to reduce operating cost. However, excessively pursuing low cost may incur congestion on some popular N-PoPs and links, which results in performance degradation or even violation of the service level of agreements.

The development of Virtual Network Functions (VNFs) migrates network functions from dedicated hardware to groups of commodity servers called network points of presence (N-PoPs). Thus, network services are redefined as interconnected VNFs called Service Function Chains (SFCs). SFC has the potential to reduce costs of network services and improve scalability. However, the availability of SFC brings new challenges since a failure of any N-PoP along the SFC affects its availability. Deploying backup SFCs is a practical method to improve the availability of SFCs, but inappropriate deployments of backups may trigger the unnecessary capacity expansion of N-PoPs and thus waste VNF resources. In this paper, we solve this problem by proposing an optimization model called partial service function chain mapping. The model adopts partial SFC rerouting strategy for smaller rerouting delay and minimizes the maximum load on N- PoPs to reduce unnecessary capacity expansion of N- PoPs. We then propose a randomized rounding algorithm to solve the optimization problem, preserving the competitive ratio of O(log n), where n is the number of NPoPs in the network. Our extensive simulation results show that the proposed algorithm can significantly improve the availability of SFCs and limit the capacity expansion of N-PoPs.

The recent development of network function virtualization decouples network functions from dedicated hardware. Thus, virtual network functions (VNFs) can be distributed onto shared and virtualized platforms held by multiple data centers in various network locations. The architecture of the distributed VNFs interconnected by virtual links is denoted as the Service Function Chain (SFC). SFC has the potential to significantly reduce the opening and operating cost of the network services while improving the flexibility. However, the availability of SFC on chained up data centers is always inferior to that of network functions running on a single data center because the failure in any data center on the chain may affect its availability. To improve the availabilities of SFCs, in this paper we propose a local rerouting strategy to bypass the failed data centers on SFCs using locally rerouted paths (LRPs). Furthermore, we formulate an optimization model to minimize the maximum load on links while deploying SFCs and LRPs into the network. Thus, we reduce the potential risk of congested links caused by the local rerouting strategy. We then propose a randomized rounding approximation algorithm to solve the optimization problem, preserving the competitive ratio of O(logn) for the model. We also propose a fast heuristic algorithm to improve the efficiency. Our extensive simulation results show that the proposed algorithms can provide highly available SFCs with more balanced link load.