标题：An enhanced algorithm based on paths algebra strategy to solve the VNE problem
作者：Wang, Canhui; Zhu, Fangjin; Zhang, Qijia
作者机构：[Wang, Canhui; Zhu, Fangjin; Zhang, Qijia] Shandong Univ, Sch Comp Sci & Software Engineer, Jinan 250100, Peoples R China.
会议名称：34th IEEE International Perfonnance, Computing, and Communications Conference (lPCCC)
会议日期：DEC 14-16, 2015
来源：2015 IEEE 34TH INTERNATIONAL PERFORMANCE COMPUTING AND COMMUNICATIONS CONFERENCE (IPCCC)
关键词：network virtualization; virtual network embedding; sufficient capacity;; multi-constraint routing; paths algebra framework
摘要：Network virtualization is widely considered to be one of the main paradigms to solve the Internet ossification problem. One of the most challenging works in this paradigm will be the efficient use of the substrate resources, which is known as virtual network embedding (VNE) problem. The VNE problem is known to be an NP-hard problem which needs some heuristic and approximate algorithms to be solved. In this paper, the VNE is decomposed into two stages: virtual node and virtual link mapping. In the node mapping stage, the breadth first search algorithm is employed to construct loop-free tree for each substrate node, then we explored different hops sufficient capacity of each SN node via the loop-free tree, and analyze the best value of hops that contributes to gain better performance for the algorithm. And the link mapping stage, it can be seen as multi-constraint routing, which is known to be an NP-hard problem. The paths algebra framework was adopted to address this problem, for its convergence for multi-constraint routing problem and a large solution space that the algorithm can gain an enhanced optimization performance.