Network Function Virtualization (NFV) is an emerging technology in which network functions are executed on generic-purpose servers instead of proprietary software appliances. Such replacement makes it easier for Internet Service Providers to employ various Virtual Network Functions (VNFs), including firewalls, load balancers, network address translators, content filtering, deep packet inspection, and so on. 

Also, with the advent of such evolution of networking, it is possible to employ the VNFs without installing new equipment and thus more environmentally friendly and cost-efficient. 

One of the most significant challenges in NFV technology is a so-called join placement and allocation of VNFs, which considers the balance between VNF instances investment in the network to provide specific service and the Quality of Services (QoS), one measure of which is the so-called packet loss probability. 

A research team led by Prof ZHANG Yong from the Shenzhen Institutes of Advanced Technology (SIAT) of the Chinese Academy of Sciences has addressed the challenge of VNFs by designing a series of efficient algorithms, the study was published as an Editors' suggestion in the IEEE Internet of Things Journal on 27 April 2020. 

In this study, researchers investigated an inclusive and provable well-defined Joint Placement and Allocation of VNFs with Heterogeneous Servers (OJPA-HS) model in the system firstly, and then they found that this model sufficiently general to extend several classical models for the Joint Placement and Allocation of VNFs.  

The researchers designed optimization strategies that extracted the properties of the network and of the requests. They were based on probabilistic decisions and also deterministic decisions.  

For the negative part, the OJPA-HS was proved at least NP-hard, and an adversary instance indicated that it was even not possible to get a bounded performance guarantee. For the positive part, a provably best-possible (w.r.t. performance) deterministic online algorithm was presented.  

Furthermore, researchers reduced the running time dramatically through Las Vegas randomized online algorithm (LV) with little loss of the performance. Moreover, if the ISPs were allowed to fail to serve some requirements, another randomized algorithm, the Monte Carlo randomized algorithm (MC), was proposed.  

More notably, MC outperformed LV in running time when the input data get large, and the fail rate was controllable by setting a particular parameter in MC. The space-complexity of both randomized algorithms was provably small.  

The team corroborated the efficiency of the proposed algorithms through extensive numerical experiments, the results demonstrated that it could handle generalized networks with heterogeneous servers, while previous work considered that all servers in the network were identical.

Media Contact: 
ZHANG Xiaomin 
Email: xm.zhang@siat.ac.cn