Network virtualization allows logically separated Virtual Networks (VNs) to coexist on a shared Physical Network (PN) and provides network operators with flexibility, diversity, security, and manageability. Virtual Network Embedding (VNE) is an optimization problem in which a network provider attempts to find the minimum cost of embedding between the requested VN and its PN with respect to the constraints of physical resources (nodes and links).

Conventional VNE methods have time complexity roughly proportional to the cube of the number of nodes and links. Since VNs have no physical restrictions on link deployments, VNs designed on the estimated traffic matrix between virtual nodes will have virtual links between all virtual node pairs. In this case, the number of links is roughly the square of the number of nodes, and the VNE time grows from the cube to the 6th power of the number of nodes; e.g., if the number of nodes is one hundred, then the time gap is a factor of one million.

This paper proposes network reduction, a scheme that converts a dense VN into a sparse one to reduce the embedding time. The scheme converts the computed embedding of the sparse VN back to that of the dense one. However, the network reduction combines several virtual links into a broader link, which makes the embedding cost (solution quality) worse. This paper analytically and empirically investigates the trade-off between the embedding time and cost for network reduction. The analysis indicates that an exponential drop in embedding time can be achieved with a linear increase in embedding cost. A rigorous numerical evaluation justifies the desirability of the trade-off.

Public networks are an essential part of the social information infrastructure, and traffic demands and connected devices are rapidly increasing. To meet these increases, network service providers have started to leverage network virtualization. This paper supports these movements by proposing a scheme that aids the effective deployment of virtualized infrastructures on the physical network.