Mobile Edge Computing (MEC) shifts the computing power to the edge of core networks and provides important impetus in the flourishment of delay sensitive services at the network edge. Digital Twin (DT) technique enables object behavior monitoring, analysis, and prediction through data analytics and artificial intelligence, which facilitates inference service provisioning based on machine learning models. In this paper, we deal with the Quality-of-Experience (QoE) issue of user satisfaction on inference services in DT-assisted MEC networks, through executing user tasks locally or offloaded to the MEC network. We formulate two novel optimization problems: the utility maximization problem, and the dynamic utility maximization problem, with the aim to maximize the total utility of user task executions in terms of QoEs and service delays of users with the services. We first provide an Integer Linear Programming solution for the utility maximization problem when the problem size is small or medium; otherwise we devise a randomized algorithm with high probability, at the expense of bounded resource violations. We then develop an efficient online heuristic for the dynamic utility maximization problem. We also devise an online algorithm with a provable competitive ratio for a special case of the dynamic utility maximization problem without the bandwidth constraint. We finally evaluate the performance of proposed algorithms through simulations. The simulation results show that the proposed algorithms are promising.

The integration of Artificial Itelligence (AI) and edge computing has sparked significant interest in edge inference services. In this paper, we consider delay-sensitive, differential accuracy inference services in a Mobile Edge Computing (MEC) network while meeting user stringent delay and accuracy requirements. We formulate two novel profit maximization problems under static and dynamic settings of service request arrivals, with the aim of maximizing the accumulative profit of admitted requests. We assign differential accuracy service requests to the corresponding resolution instances of their requested service models, assuming that each resolution instance can serve up to$L\geq 1$the same type of service requests. Since the profit maximization problem is NP-hard, we first formulate an Integer Linear Program (ILP) solution if the problem size is small or medium; otherwise, we devise a constant randomized algorithm with high probability. Then, we consider dynamic service request admissions without the knowledge of future request arrivals for a given finite time horizon, for which we develop a simple yet effective prediction mechanism to accurately predict the number of different resolution instances of each model needed, and pre-deploy the predicted number of resolution instances into cloudlets to reduce instantiating delays. We then devise an online algorithm with a provable competitive ratio for the dynamic profit maximization problem by leveraging the primal-dual dynamic updating technique. Finally, we evaluate the performance of the proposed algorithms by simulations. The simulation results demonstrate that the proposed algorithms are promising.

The Digital Twin (DT) technique enables seamless integrations between the physical and virtual worlds. By continuously synchronizing DTs with their physical counterparts, DTs can provide accurate reflections of physical objects and facilitate high-fidelity inference services based on service models. Orthogonal to the DT technology, Mobile Edge Computing (MEC) has been envisioning as a promising paradigm for providing intelligent services to users while meeting stringent delay and accuracy requirements. In this paper, we investigate fidelity-aware inference services in a DT-assisted MEC network where there are multiple source DTs providing new updated training data to service models often. We jointly schedule mobile devices to upload their update data to their DTs, and choose service models for retraining using their updated source DT data over a given time horizon. We further assume that the previous version of each service model can still serve its users during its retraining period, while a retrained service model can provide high-fidelity services to its users. To this end, we first formulate two novel optimization problems: the model instance placement problem that assigns model instances to cloudlets in an MEC network so that the total placement cost of all service models is minimized, and the cumulative utility maximization problem to maximize the cumulative fidelity of all service models over a given time horizon, by jointly scheduling mobile devices to upload their update data to their DTs and service models to be trained using their updated source DT data at each time slot. We then formulate an integer linear programming (ILP) solution for the model instance placement problem when the problem size is small; otherwise we develop an approximate solution to the problem, at the expense of moderate resource violations. We also devise an efficient online algorithm for the cumulative utility maximization problem. We finally evaluate the performance of the proposed algorithms via simulations, and the simulation results demonstrate that the proposed algorithms are promising.

The past decade witnessed an explosive growth on the number of IoT devices (objects/suppliers), including portable mobile devices, autonomous vehicles, sensors and intelligence appliances. To realize the digital representations of objects, Digital Twins (DTs) are key enablers to provide real-time monitoring, behavior simulations and predictive decisions for objects. On the other hand, Mobile Edge Computing (MEC) has been envisioned as a promising paradigm to provide delay-sensitive services for mobile users (consumers) at the network edge, e.g., real-time healthcare, AR/VR, online gaming, smart cities, and so on. In this paper, we study a novel DT migration problem for high quality service provisioning in an MEC network with the mobility of both suppliers and consumers for a finite time horizon, with the aim to minimize the sum of the accumulative DT synchronization cost of all suppliers and the total service cost of all consumers requesting for different DT services. To this end, we first show that the problem is NP-hard, and formulate an integer linear programming solution to the offline version of the problem. We then develop a Deep Reinforcement Learning (DRL) algorithm for the DT migration problem, by considering the system dynamics and heterogeneity of different resource consumptions, mobility traces of both suppliers and consumers, and workloads of cloudlets. We finally evaluate the performance of the proposed algorithms through experimental simulations. Simulation results demonstrate that the proposed algorithms are promising.

Digital twin (DT) has been emerging as an enabling technology to provide seamless interactions between the virtual cyber world and the real world. The explosion of IoT devices (objects) further fuels the development of the DT technology, and paves the way to real-time monitoring, behavior simulations and decisive predictions on objects through their digital counterparts. Meanwhile, mobile edge computing (MEC) has been envisioned as a promising computing paradigm for various IoT applications with stringent delay requirements. In this paper, we study mobility-aware, delay-sensitive service provisioning in a DT-empowered MEC network with the mobility of both users and objects through DT replica placements of mobile objects. To this end, we first formulate two novel optimization problems: the DT replica placement problem and the dynamic DT replica placement problem, respectively, and show NP-hardness of the two problems. We then formulate an Integer Linear Programming (ILP) solution to the DT replica placement problem when the problem size is small or medium; otherwise we devise a randomized algorithm with high probability, provided that the mobility profiles of each object and each user are given. Meanwhile, We also develop an online algorithm for the dynamic DT replica placement problem, where for a given time horizon, service requests arrive one by one without the knowledge of future arrivals, each arrived request must be responded immediately by accepting or rejecting it. However, the heterogeneity and dynamics of user requests on resource demands may lead to the removals and re-instantiations of DT instances frequently. To mitigate this, we propose an efficient prediction mechanism to reserve a certain number of DTs for future by introducing the timestamp concept. We finally evaluate the performance of the proposed algorithms by simulations. Simulation results show that the proposed algorithms are promising, and outperform the performance of other comparison counterparts.

In the past decades, explosive numbers of Internet of Things (IoT) devices (objects) have been connected to the Internet, which enable users to access, control, and monitor their surrounding phenomenons at anytime and anywhere. To provide seamless interactions between the cyber world and the real world, Digital twins (DTs) of objects (IoT devices) are key enablers for real time monitoring, behaviour simulations, and predictive decisions on objects. Compared to centralized cloud computing, mobile edge computing (MEC) has been envisioning as a promising paradigm for low latency IoT applications. Accelerating the usage of DTs in MEC networks will bring unprecedented benefits to diverse services, through the co-evolution between physical objects and their virtual DTs, and DT-assisted service provisioning has attracted increasing attention recently. In this article, we consider novel DT placement and migration problems in an MEC network with the mobility assumption of objects and users, by jointly considering the freshness of DT data and the service cost of users requesting for DT data. To this end, we first propose an algorithm for the DT placement problem with the aim to minimize the sum of the DT update cost of objects and the total service cost of users requesting for DT data, through efficient DT placements and resource allocation to process user requests. We then devise an approximation algorithm with a provable approximation ratio for a special case of the DT placement problem when each user requests the DT data of only one object. Meanwhile, considering the mobility of users and objects, we devise an online, two-layer scheduling algorithm for DT migrations to further reduce the total service cost of users within a given finite time horizon. We finally evaluate the performance of the proposed algorithms through experimental simulations. The simulation results show that the proposed algorithms are promising.

Mobile Edge Computing (MEC) has emerged as a promising platform to provide various services for mobile applications at the edge of core networks while meeting stringent service delay requirements of users. Digital twin (DT) that is a mirror of a physical object in cyberspace now becomes a key player in smart cities and the Metaverse, which can be used to simulate or predict the behaviours of the object in future. To enable such a simulation or predication to be more accurate and robust, the state of the digital twin needs to be synchronized (updated) with its object quite often. The quality of inference services in a DT-empowered MEC network usually is determined by the state freshness of service models, while a service model further is determined by the state freshness of its source DT data. It is vital to refresh the states of service models frequently in order to provide high quality inference services. In this paper, we study how to maximize the state freshness of both digital twins and a set of inference service models that are built upon digital twins in an MEC network, while the state freshness of a DT or a service model is achieved through frequent synchronizations between the DT and its physical object. Specifically, we first study a novel cost-aware average model freshness maximization problem with the aim to maximize the average freshness of the states of inference service models while minimizing the cost of achieving the model freshness, and show the NP-hardness of the problem. We then formulate an integer linear programming solution for the offline version of the problem, and devise a performance-guaranteed approximation algorithm for a special case of problem when the monitoring period consists of a single time slot only. Also, we develop an efficient online algorithm for the problem through scheduling objects to upload their update data to their digital twins in the network at each time slot efficiently. We finally evaluate the performance of the proposed algorithms through simulations. Simulation results demonstrate that the proposed algorithms are promising.

The advance of Digital Twin (DT) technology sheds light on seamless cyber-physical integration with the Industry 4.0 initiative. Through continuous synchronization with their physical objects, DTs can power inference service models for analysis, emulation, optimization, and prediction on physical objects. With the proliferation of DTs, Digital Twin Network (DTN) slicing is emerging as a new paradigm of service providers for differential quality of service provisioning, where each DTN is a virtual network that consists of a set of inference service models with source data from a group of DTs, and the inference service models provide users with differential quality of services. Mobile Edge Computing (MEC) as a new computing paradigm shifts the computing power towards the edge of core networks, which is appropriate for delay-sensitive inference services. In this paper we consider Age of Information (AoI)-aware inference service provisioning in an MEC network through DTN slicing requests, where the accuracy of inference services provided by each DTN slice is determined by the Expected Age of Information (EAoI) of its inference model. Specifically, we first introduce a novel AoI-aware inference service framework of DTN slicing requests. We then formulate the expected cost minimization problem by jointly placing DT and inference service model instances, and develop efficient algorithms for the problem, based on the proposed framework. We also consider dynamic DTN slicing request admissions where requests arrive one by one without the knowledge of future arrivals, for which we devise an online algorithm with a provable competitive ratio for dynamic request admissions, assuming that DTs of all objects have been placed already. Finally, we evaluate the performance of the proposed algorithms through simulations. Simulation results demonstrate that the proposed algorithms are promising, and the proposed online algorithm improves the number of admitted requests by more than 6% than its counterpart.

This article proposes an optimization model for the network service (NS) mapping and scheduling problem with uncertain processing time in network function virtualization. We model processing time uncertainty through the$\Gamma$-robustness approach, which provides different degrees of robustness against processing time uncertainty. We formulate the problem with the objective to minimize the worst-case makespan over the given uncertainty set. We show the NP-hardness of considered problem. A heuristic that divides the problem into subproblems is presented to tackle it. For the subproblem in which mapping and scheduling decisions are given, we develop an algorithm with polynomial time complexity to calculate the worst-case makespan over the uncertainty set, which has a better scalability than the corresponding mixed integer linear programming (MILP) problem and obtains the same worst-case makespan with the MILP problem. The numerical results show that the proposed model outperforms the conventional model with deterministic parameters in terms of worst-case makespan.

This paper proposes an availability-aware service provisioning model with backup sub-chain-enabled sharing in network function virtualization to minimize the deployment cost. A sub-chain consists of a set of ordered VNFs that corresponds to a part of or the whole function chain of a service. Different from a conventional model in which a backup sub-chain is dedicated to protecting a primary sub-chain of one service, the proposed model allows the backup sub-chain sharing among services to reduce the deployment cost. Due to the complexity of the investigated problem, a heuristic is designed to tackle it. The numerical results show that the proposed model achieves lower deployment cost with satisfying the availability requirement than the conventional one.

This paper proposes a sub-chain-enabled coordinated protection model for the availability-guaranteed service function chain (SFC) provisioning, which considers the availability of each component to constitute an SFC, including links and VNFs. Unlike conventional protection models providing certain protection for the whole chain, the proposed model configures sub-chains for each SFC and provides proper protection for each sub-chain to achieve the required availability in a cost efficient way. We formulate the proposed model as an optimization problem to minimize the deployment cost. A game approach is presented to tackle the problem. The numerical results show that the proposed model outperforms the conventional ones in terms of deployment cost; the game approach has scalability of tackling the proposed model as the problem size increases.

This paper proposes an optimization model for the network service mapping and scheduling problem with uncertain processing time. We model processing time uncertainty through Γ-robustness approach, which provides different degrees of robustness against processing time uncertainty. We formulate the problem with the objective to minimize the worst-case makespan over the given uncertainty set. A heuristic is presented to tackle the problem. The numerical results show that the proposed model outperforms the conventional model with deterministic parameters in terms of worst-case makespan.

Network function virtualization enables network operators to implement network functions in a software-oriented manner and makes network services (NSes) provisioning much simpler. This paper proposes an optimization model to schedule delay sensitive NSes with deadlines allowing resource sharing and preemption. Unlike conventional NS scheduling models with static resource allocation for virtualized network function (VNF) instances, the proposed model ensures that VNF instances deployed on the same node share computation resources of the node and are able to scale up/down to change their process rate at runtime. NSes mapped to the same VNF instance of the same node share computation resources of the VNF instance and are able to be processed in parallel by the VNF instance. Preemption is allowed, which means that rescheduling the order of NS processing at runtime is possible and the process duration of each function of an NS is allowed to be discrete. We formulate the proposed model as an integer linear programming problem to maximize the number of admissible NSes. Due to the complexity of the problem, we develop a genetic algorithm to solve it efficiently. We evaluate the proposed model with conventional models in the static and dynamic scenarios. The numerical results show that the proposed model outperforms conventional models in terms of acceptance ratio in both static and dynamic scenarios.

This paper proposes an optimization model to schedule network services (NSes) in virtual networks with resource sharing and preemption. Inefficient NS scheduling can severely degrade the acceptance ratio of arriving NSes of the network. Conventional NS scheduling models do not consider sharing computational resources of a node among different virtual network function (VNF) instances deployed on this node. In the proposed model, NSes mapped to the same VNF instance on the same node share computational resources of the VNF instance, and VNF instances deployed on the same node share computational resources of the node. The proposed model allows preemption, which means that rescheduling the process order of NSes in runtime is possible and the process duration of each function of an NS is allowed to be discrete. We formulate the proposed model as an integer linear programming problem to maximize the number of admissible NSes. The numerical results show that the proposed model outperforms conventional models in terms of the acceptance ratio of arriving NSes.