arXiv:2106.10707 · IEEE International Conference on Mobile Ad-Hoc and Sensor Systems (MASS)

Minimizing Delay in Network Function Visualization with Quantum Computing

Wenlu Xuan, Zhongqi Zhao, Lei Fan, Zhu Han

Published Oct 1, 2021• 18 citations

Abstract

Network function virtualization (NFV) is a crucial technology for the 5G network development because it can improve the flexibility of employing hardware and reduce the construction of base stations. There are vast service chains in NFV to meet users’ requests, which are composed of a sequence of network functions. These virtual network functions (VNFs) are implemented in virtual machines by software and virtual environment. How to deploy VMs to process VNFs of the service chains as soon as possible when users’ requests are received is very challenging to solve by traditional algorithms on a large scale. Compared with traditional algorithms, quantum computing has better computational performance because of quantum parallelism. We build an integer linear programming model of the VNF scheduling problem with the objective of minimizing delays, and transfer it into the quadratic unconstrained binary optimization (QUBO) model. Our proposed heuristic algorithm employs a quantum annealer to solve the model. Finally, we evaluate the computational results and explore the feasibility of leveraging quantum computing to solve the VNF scheduling problem.

DOI: 10.1109/mass52906.2021.00022

Related papers

Virtual Network Function Embedding with Quantum Annealing

Pietro Chiavassa, Andrea Marchesin, Ignazio Pedone +2 more

In recent years, the growing number of devices connected to the internet led network operators to continuously expand their own infrastructures. In order to simplify this scaling process, the research community is currently investigating the opportunity to move the complexity from a hardware to a software domain, through the introduction of a new paradigm, called Network Functions Virtualisation (NFV). It considers standard hardware platforms where many virtual instances are allocated to implement specific network services. However, despite the theoretical benefits, the mapping of the different virtual instances to the available physical resources represents a complex problem, difficult to be solved classically. The present work proposes a Quadratic Unconstrained Binary Optimisation (QUBO) formulation of this embedding process, exploring the implementation possibilities on D-Wave’s Quantum Annealers. Many test cases, with realistic constraints, have been considered to validate and characterise the potential of the model, and the promising results achieved are discussed throughout the document. The technical discussion is enriched with comparisons of the results obtained through heuristic algorithms, highlighting the strengths and the limitations in the resolution of the QUBO formulation proposed on current quantum machines.

IEEE International Conference on Quantum Computing and Engineering (QCE)Sep 1, 20223 citations

Quantum Evolutionary Algorithm for Scheduling Resources in Virtualized 5G RAN Environment

M. Saravanan, Rana Pratap Sircar

Radio is the most important part of any wireless network. Radio Access Network (RAN) has been virtualized and disaggregated into different functions whose location is best defined by the requirements and economics of the use case. This Virtualized RAN (vRAN) architecture separates network functions from the underlying hardware and so 5G can leverage virtualization of the RAN to implement these functions. The easy expandability and manageability of the vRAN support the expansion of the network capacity and deployment of new features and algorithms for streamlining resource usage. In this paper, we try to address the problem of scheduling 5G vRAN with mid-haul network capacity constraints as a combinatorial optimization problem. We transformed it to a Quadratic Unconstrained Binary Optimization (QUBO) problem by using a newly proposed quantum-based algorithm and compared our implementation with existing classical algorithms. This work has demonstrated the advantage of quantum computers in solving a particular optimization problem in the Telecommunication domain and paves the way for solving critical real-world problems using quantum computers faster and better.

IEEE 5G World Forum (5GWF)Oct 1, 20211 citation

Entanglement-assisted decision making for VNF migration in 6G Communication Networks

Shivam Maheshwari, Vignesh Raman, Riccardo Bassoli +1 more

Network Function Virtualization (NFV) has enabled scalable deployment of novel user service requests in current and future communication networks (sixth generation (6G)). However, virtualization also introduces down functioning of certain Key Performance Indicator (KPI)s such as latency. Novel technology like quantum computing has potential to surpass these limitations. One of the problems to tackle in NFV based systems, is decision making for Virtual Network Function (VNF) migration. Classical and quantum solutions are proposed for this problem. It is observed that both solutions ensure anonymity; however lesser overhead is required in the quantum solution. Further, future research directions are discussed as well to inculcate quantum technology into broader class of problems in 6G communication networks.

IEEE Conference on Network Function Virtualization and Software Defined Networks (NFV-SDN)Nov 5, 20242 citations

Lagrangian Relaxation Based Parallelized Quantum Annealing and Its Application in Network Function Virtualization

Wenlu Xuan, Zhongqi Zhao, Lei Fan +1 more

Quantum computing is commonly considered one highly efficient computing method with the potential to revolutionize computation technology and solve problems that are currently unsolvable. However, due to the limitation of hardware equipment and an immature experimental base, quantum technology is still in its early stages and is far from achieving the expected performance, especially in solving large-scale complex problems. To break through these barriers, we propose a parallelized quantum annealing algorithm based on Lagrangian relaxation. The proposed algorithm divides the large-scale problem into several small problems and then employs multiple quantum computers to solve them. Our proposed approach overcomes the limited number of qubits and allows quantum computing to solve largescale optimization problems. Additionally, we incorporate a local search method to ensure this Lagrangian relaxation based quantum algorithm achieves an optimal solution. We use the proposed parallelized quantum annealing algorithm to solve optimal scheduling problems in network function virtualization networks. The problem is expressed in a linear optimization model that is NP-hard. Our proposed algorithm presents excellent time performance in solving this virtualized network functions scheduling problem, compared with the Lagrangian relaxation based classical algorithm.

IEEE Open Journal of the Communications SocietyJan 1, 20241 citation

Resource Optimization of SFC Embedding for IoT Networks Using Quantum Computing

Mahzabeen Emu, Salimur Choudhury, Kai Salomaa

Embedding Service Function Chain (SFC) into the massive and resource-hungry Internet of Things (IoT) substrate graph is a critical optimization research problem. Unfortunately, the classical Integer Linear Programming (ILP) formulation for such problems is usually NP-hard. Thus, this research study presses on the need to go beyond the realms and employ Quantum Annealing (QA) to speed up the computation. To comply, we reformulate the SFC embedding problem into IoT graphs as Quadratic Unconstrained Binary Optimization (QUBO) format and propose a hybrid warm start quantum annealing (WSQA) optimization technique. Simulation results show that our proposed WSQA can improve resource utilization, accelerate computing time, and achieve a better scalability success rate at solving large-scale SFC deployment compared to standalone QA. Further along the line, this research inspires the application of quantum optimization for resource allocation in next-generation networks even with the limited availability of qubits.

IEEE International Workshop on Computer Aided Modeling and Design of Communication Links and Networks (CAMAD)Nov 2, 20225 citations

Classical and Quantum Solvers for Joint Network/Servers Power Optimization

Michele Amoretti, Ferrari, Davide, Antonio Manzalini

The digital transformation that Telecommunications and ICT domains are crossing today, is posing several new challenges to Telecom Operators. These challenges require solving complex problems such as: dimensioning and scheduling of virtual/real resources in data centers; automating real-time management/control and orchestration of networks processes; optimizing energy consumption; and overall, ensuring networks and services stability. These problems are usually tackled with methods and algorithms that find suboptimal solutions, for computational efficiency reasons. In this work, we consider a Virtual Data Center scenario where virtual machine consolidation must be performed with joint minimization of network/servers power consumption. For this scenario, we provide an ILP model, the equivalent binary model and the steps towards the equivalent Quadratic Unconstrained Binary Optimization (QUBO) model that is suitable for being solved by means of quantum optimization algorithms. Finally, we compare the computational complexity of classical and quantum solvers from a theoretical perspective.

arXiv:2205.01165May 2, 20220 citations