Improved Heuristics for Online Node and Link Mapping Problem in Network Virtualization

Network virtualization is considered a promising way to improve flexibility and manageability for Internet. A major challenge in network virtualization is how to effectively allocate the underlying resources satisfying virtual network requests. Since the general network embedding problem is computationally unsolvable, past researches have followed various approaches to reduce the computational cost. For example, Minlan Yu et al. have introduced a greedy algorithm for online virtual network requests with low complexity. In this work, we further improve the performance of this algorithm by proposing three improvements: (1) sorting virtual nodes according to the amount of required resources, (2) using an adaptive function to evaluate available resources and (3) pre-checking invalid substrate links before link-mapping phase. Extensive simulation shows that our proposed algorithm gives better results in terms of acceptance ratio, revenue-to-cost ratio as well as computational cost.