A forwarding graph embedding algorithm exploiting regional topology information

• Published in: Frontiers of information technology & electronic engineering 2017-11, Vol.18 (11), p.1854-1866
• Main Authors: Hu, Hong-chao, Zhang, Fan, Mao, Yu-xing, Wang, Zhen-peng
• Format: Article
• Language: English
• Subjects: Algorithms; Clustering; Communication; Communications Engineering; Computer Hardware; Computer Science; Computer Systems Organization and Communication Networks; Digital switching; Electrical Engineering; Electronics and Microelectronics; Embedding; Energy consumption; Instrumentation; Integer programming; Load; Network function virtualization; Networks; Revenue; Substrates; Topology; Virtual networks
• ISSN: 2095-9184; 2095-9230
• DOI: 10.1631/FITEE.1601404

Network function virtualization (NFV) is a newly proposed technique designed to construct and manage network functions dynamically and efficiently. Allocating physical resources to the virtual network function forwarding graph is a critical issue in NFV. We formulate the forwarding graph embedding (FGE) problem as a binary integer programming problem, which aims to increase the revenue and decrease the cost to a service provider (SP) while considering limited network resources and the requirements of virtual functions. We then design a novel regional resource clustering metric to quantify the embedding potential of each substrate node and propose a topology-aware FGE algorithm called ‘regional resource clustering FGE’ (RRC-FGE). After implementing our algorithms in C++, simulation results showed that the total revenue was increased by more than 50 units and the acceptance ratio by more than 15%, and the cost of the service provider was decreased by more than 60 units.