Scientist propose new virtual network functions algorithms

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).

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

One challenge in NFV technology is the 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).

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 IEEE Internet of Things Journal on April 27.

In this study, the researchers investigated an inclusive and provable well-defined online joint placement and allocation of VNFs with heterogeneous servers (OJPA-HS) model in the system. They found that this model was 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 the requests. These strategies were based on probabilistic decisions and deterministic decisions as well.

"On the one hand, 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. On the other hand, a provably best-possible deterministic online algorithm was presented," said Prof. Zhang.

Furthermore, the researchers reduced the running time dramatically through Las Vegas randomized online algorithm (LV) with little loss of the performance. Moreover, if the ISPs failed 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.