The Value of Simple Heuristics for Virtualized Network Function Placement

Zahra Jahedi and Thomas Kunz
Additional contact information
Zahra Jahedi: The Department of Systems and Computer Engineering, Carleton University, 1125 Colonel By Drive, Ottawa, ON K1S 5B6, Canada
Thomas Kunz: The Department of Systems and Computer Engineering, Carleton University, 1125 Colonel By Drive, Ottawa, ON K1S 5B6, Canada

Future Internet, 2020, vol. 12, issue 10, 1-16

Abstract: Network Function Virtualization (NFV) can lower the CAPEX and/or OPEX for service providers and allow for quick deployment of services. Along with the advantages come some challenges. The main challenge in the use of Virtualized Network Functions (VNF) is the VNFs’ placement in the network. There is a wide range of mathematical models proposed to place the Network Functions (NF) optimally. However, the critical problem of mathematical models is that they are NP-hard, and consequently not applicable to larger networks. In wireless networks, we are considering the scarcity of Bandwidth (BW) as another constraint that is due to the presence of interference. While there exist many efforts in designing a heuristic model that can provide solutions in a timely manner, the primary focus with such heuristics was almost always whether they provide results almost as good as optimal solution. Consequently, the heuristics themselves become quite non-trivial, and solving the placement problem for larger networks still takes a significant amount of time. In this paper, in contrast, we focus on designing a simple and scalable heuristic. We propose four heuristics, which are gradually becoming more complex. We compare their performance with each other, a related heuristic proposed in the literature, and a mathematical optimization model. Our results demonstrate that while more complex placement heuristics do not improve the performance of the algorithm in terms of the number of accepted placement requests, they take longer to solve and therefore are not applicable to larger networks.In contrast, a very simple heuristic can find near-optimal solutions much faster than the other more complicated heuristics while keeping the number of accepted requests close to the results achieved with an NP-hard optimization model.

Keywords: virtualized network function; wireless multi-hop networks; network function embedding problem; Service graph, linear programming; interference; simple; fast (search for similar items in EconPapers)
JEL-codes: O3 (search for similar items in EconPapers)
Date: 2020
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/1999-5903/12/10/161/pdf (application/pdf)
https://www.mdpi.com/1999-5903/12/10/161/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jftint:v:12:y:2020:i:10:p:161-:d:419202

Access Statistics for this article

Future Internet is currently edited by Ms. Grace You

More articles in Future Internet from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().