A topology-cognitive algorithm framework for virtual network embedding problem

The virtual network embedding/mapping problem is an important issue in network virtualization in Software-Defined Networking (SDN). It is mainly concerned with mapping virtual network requests, which could be a set of SDN flows, onto a shared substrate network automatically and efficiently. Previous researches mainly focus on developing heuristic algorithms for general topology virtual network. In practice however, the virtual network is usually generated with specific topology for specific purpose. Thus, it is a challenge to optimize the heuristic algorithms with these topology information. In order to deal with this problem, we propose a topology-cognitive algorithm framework, which is composed of a guiding principle for topology algorithm developing and a compound algorithm. The compound algorithm is composed of several sub-algorithms, which are optimized for specific topologies. We develop star, tree, and ring topology algorithms as examples, other sub-algorithms can be easily achieved following the same framework. The simulation results show that the topology-cognitive algorithm framework is effective in developing new topology algorithms, and the developed compound algorithm greatly enhances the performance of the Revenue/Cost (R/C) ratio and the Runtime than traditional heuristic algorithms for multi-topology virtual network embedding problem.