Home // AFIN 2019, The Eleventh International Conference on Advances in Future Internet // View article

Optimization of Service Function Assignment and Shortest Path for Network Function Virtualization

Authors:
Arvind Kalyan

Keywords: Network Function Virtualization, Integer Linear Programming, Dijkstra’s Shortest Path Algorithm, Greedy Heuristic

Abstract:
This paper focuses on the concept of Network Function Virtualization (NFV): the implementation of requests consisting of various service functions on servers located in data centers. This paper attempts to minimize both the cost of routing and service function assignment of requests from source to destination node on a network. This problem falls under the class of Integer Linear Programming (ILP), which is NP-Hard and cannot be solved in polynomial time. Towards developing a solution, it is proposed to split the problem into two separate optimization subproblems: shortest path routing and service function assignment. We utilize Dijkstra’s Shortest Path algorithm and a Greedy method for service function assignment to propose a new heuristic algorithm that minimizes the total cost of routing and service functions assignment. The experimental results suggest that the proposed algorithm matches the optimal ILP solution within acceptable limits.

Pages: 10 to 16

Copyright: Copyright (c) IARIA, 2019

Publication date: October 27, 2019

Published in: conference

ISSN: 2308-4340

ISBN: 978-1-61208-747-4

Location: Nice, France

Dates: from October 27, 2019 to October 31, 2019