Virtual Network Embedding Algorithm for Location-Based Identifier Allocation

Abstract

Network virtualization allows multiple isolated virtual networks (VNs) to share the same substrate network (SN). VN embedding (VNE) algorithms can efficiently allocate the limited SN resources to VNs and assign a unique identifier to each VN. However, the fixed bit width of VN identifier in the packet header limits the number of VNs, and extending the bit width leads to the increase of the network traffic. In this paper, we consider the label-combination method to generate VN identifiers by combining the link-grained labels with location information. This method requires the efficient allocation of labels, but the existing VN embedding works only consider the CPU and bandwidth resources. To address this issue, we propose a novel embedding model that considers the label, CPU and bandwidth resource constraints. Furthermore, two window-based heuristic algorithms called VNE-LIA and VNE-iLIA using the greedy algorithm and the proximity principle are presented to solve the VNE problem. The simulation experiments show that our proposed algorithms increase the number of VN identifiers and the revenue to cost ratio under the different resource conditions of SN.

Keywords

• Virtual network embedding
• virtual network identifier
• resource allocation
• online algorithm
• network virtualization