Network virtualization provides a promising tool to allow multiple heterogeneous virtual networks to run on a shared substrate network simultaneously. A longstanding challenge in network virtualization is the Virtual Network Embedding (VNE) problem: how to embed virtual networks onto specific physical nodes and links in the substrate network effectively. Recent research presents several heuristic algorithms that only consider single topological attribute of networks, which may lead to decreased utilization of resources. In this paper, we introduce six complementary characteristics that reflect different topological attributes, and propose three topologyaware VNE algorithms by leveraging the respective advantages of different characteristics. In addition, a new KScore decomposition algorithm based on two characteristics is devised to better disentangle the hierarchical topological structure of virtual networks. Due to the overall consideration of topological attributes of substrate and virtual networks by using multiple characteristics, our study better coordinates node and link embedding. Extensive simulations demonstrate that our proposed algorithms improve the longterm average revenue, acceptance ratio, and revenue/cost ratio compared to previous algorithms.
1. Introduction
A
s a powerful way to eradicate the ossifying forces of the Internet, network virtualization is an important technique for designing the future Internet architecture, and has obtained wide attention in recent years
[1

5]
. Network virtualization allows multiple heterogeneous virtual networks (VNs), each customized to a specific topology and purpose, to run on a shared substrate network simultaneously. It will benefit many new computing and networking paradigms, such as Cloud Computing platforms, Data Center networks, and Software Defined Networking (SDN).
In network virtualization environment, traditional Internet Service Providers (ISPs) nowadays are decoupled into two independent entities: Infrastructure Providers (InPs) who deploy and manage physical infrastructures, and Service Providers (SPs) who rent sliceable physical resources from InPs to build VNs and offer diverse services to end users. A VN has a customized logical topology that is composed of virtual nodes and links with various resource requirements. To serve as many different virtual network requests (VNRs) as possible and profit from them, InPs strive to make efficient use of physical resources by optimizing mapping algorithms that map/embed each VN onto specific physical nodes and links in the substrate network. (The words “embed” and “map” will not be differentiated in this paper.) This is known as the Virtual Network Embedding (VNE) problem. However, the VNE problem is NPhard whether the problem space is restricted or not. Computational intractability urges researchers to devise various heuristic algorithms to find practical solutions
[6

13]
.
The VNE problem can be divided into two subproblems: the node mapping where virtual nodes are allocated in physical nodes and the link mapping where virtual links connecting these virtual nodes are mapped to physical paths connecting the corresponding physical nodes. Most heuristic algorithms employ the “greedy” node mapping (e.g.,
[7
,
8
,
9
,
11
,
12
,
13]
), also called L2S2 mapping (which stands for “largetolarge and smalltosmall” mapping
[11]
). It maps the virtual nodes requiring more resources onto the physical nodes with more resources, so as to minimize the use of resources at bottleneck nodes and links. This greedy way helps to satisfy the resource requirements of current VNR and balance the loads of the substrate network. Furthermore, it is beneficial to future VNRs that require specific physical nodes and links with scarce resources.
The most important part in the “greedy” node mapping is the node ranking, i.e., how to measure every node in a substrate or virtual network, in order to correspondingly match and embed them one after another. Recent algorithms measure a node in the substrate network or a VN quantitatively by using its CPU and bandwidth (e.g.,
[9
,
12]
), or certain network topological attribute (e.g.,
[11
,
13]
). However, topological attributes could have significant effect on the performance of embedding algorithms. The existing algorithms, which typically ignore the topological structure or only consider single topological attribute in node ranking, barely coordinate node and link mapping, and may lead to decreased utilization of the substrate network resources, meaning low revenues or high costs for InPs. This calls for the design of new algorithms that synthetically measure a node’s resources and topological attributes at the same time.
Motivated by the disadvantages of traditional greedy node mapping, we present a new topologyaware approach in this paper, which utilizes different network topological attributes simultaneously. Topological attributes emerge in the form of diverse characteristics, which measure the relative influence or importance of nodes and links from different aspects. Six characteristics reflecting different topological attributes are introduced: “degree”, “strength”, “closeness (farness) centrality”, “betweenness centrality”, “eigenvector centrality” and “Katz centrality”. Three topologyaware heuristic algorithms with multiple characteristics are proposed accordingly, to leverage the respective advantages of different characteristics. Our algorithms consider not only the resource requirements of nodes but also their topological attributes, which should better coordinate node mapping and link mapping.
In most cases, nodes in a VN play different roles according to the services they provide, such as directories, file servers, terminals, etc. Even if all the nodes in some specific VNs are considered to be equivalent, they can be differentiated hierarchically according to their abilities or actual effects in the network. Therefore in the VNE problem, using topology decomposition to disentangle the hierarchical structure of a VN can make the mapping process easier. Inspired by the Kcore decomposition algorithm presented in
[12]
, we come up with a new KScore decomposition algorithm based on two characteristics, “degree” and “strength”, to better disentangle the hierarchical topological structure of a VN and divide it into a core network and multiple edge networks. The KScore decomposition algorithm is an example of utilizing topological characteristics from a different aspect in the VNE problem.
Due to the overall consideration of topological attributes of substrate and virtual networks by using multiple characteristics, our new topologyaware approaches can better coordinate node and link mapping. Extensive simulations demonstrate that our approaches improve the longterm average revenue, acceptance ratio, and revenue/cost ratio compared to previous algorithms.

In summary, this paper presents the following major contributions:

a) We introduce six topological characteristics, which represent different topological attributes, in the design of topologyaware VNE algorithms. To the best of our knowledge, most of these characteristics are first applied to the VNE problem.

b) We propose three topologyaware VNE algorithms based on multiple topological characteristics, and three correspondingly modified algorithms for the algorithm presented in[11]. Equations of node ranking are well designed to leverage the respective advantages of different characteristics.

c) The KScore decomposition algorithm based on the characteristic “degree” and “strength” is devised to better disentangle the hierarchical structure of each VN.

d) Extensive simulations are conducted to compare 7 proposed algorithms with 4 previous algorithms accordingly. The results demonstrate that our algorithms significantly increase the longterm average revenue, acceptance ratio, and revenue/cost ratio.
The remainder of this paper is organized as follows. Section 2 discusses some previous VNE algorithms related to our work, and Section 3 presents the general model of the VNE problem, along with three objectives used in the evaluation. Six topological characteristics are introduced in Section 4, which are used to design three new algorithms and three modified algorithms in Section 5. We devise the KScore decomposition algorithm in Section 6. Section 7 presents the simulation results and the paper is concluded in Section 8.
2. Related Work
Previous research presents some heuristic algorithms that consider the network topologies more or less. Szeto et al.
[6]
propose a link mapping scheme based on MultiCommodity Flow (MCF) problem. In their scheme, nodes in the substrate network are classified as “the access nodes” and “the transit nodes”, thus each pair of access nodes is treated as a commodity and a set of resources are preallocated to them.
To utilize the flexibility provided by small topologies, Zhu and Ammar
[7]
split VNRs into many star subnetworks. During the node mapping process, the center node with highest degree in a star subnetwork is mapped to the physical node with lowest CPU and bandwidth occupancy rate. Once the center node has been determined, other nodes in the same subnetwork with higher degrees are embedded onto physical nodes with lower resource occupancy rates and shorter distances to the center, one by one. However, their algorithm assumes that substrate resources are unlimited, and focuses on load balance in the substrate network without the need of admission control. Besides, not all the topologies can be appropriately divided into star subnetworks. Houidi et al.
[8]
adopt similar idea of topology splitting in
[7]
. Every center node is mapped onto the physical node with maximum resources, while every edge node is mapped onto the physical node with shortest path to the center one. As the centralized VNE algorithms suffer from the scalability limitation and high latency, they present a distributed VNE algorithm by using a multiagent system. The distributed algorithm can improve the system’s robustness, reduce the communication costs and support the highspeed parallel computing. Nevertheless, it has relatively poor performance although unlimited resources are assumed to accept all the VNRs.
Yu et al.
[9]
assume that the substrate network supports path splitting and path migration, rather than restricting the problem space as many previous algorithms did. Flexible splitting of virtual links over multiple physical paths and periodically reoptimizing the embedding of existing virtual links allow the substrate network to accept more VNRs, and thus increase the average revenue of InPs. A “greedy” node mapping algorithm similar to
[7]
is proposed, in which the product of CPU and adjacent bandwidth is newly defined for node ranking. However, a virtual node may choose a physical node with more than adequate CPU resource but not enough bandwidth resource, leading to the failure of subsequent link mapping process.
Chowdhury et al.
[10]
introduce the correlation between node mapping and link mapping. They formulate the VNE problem as a Mixed Integer Programming problem by constructing an augmented substrate network based on the location constraints of virtual nodes. To decide which physical nodes should be chosen, they relax the integer constraints and use deterministic or randomized rounding techniques. After the node mapping process, MCF algorithm or the shortest path algorithm is used to map the virtual links. However, the results from the node mapping process may result in an infeasible link mapping.
Cheng et al.
[11]
use Google’s successful PageRank algorithm in the web search domain for reference, by applying Markov’s Random Walk model in node ranking. Every node in the substrate network and VNs is ranked based on its resources (CPU and bandwidth, similar to
[9]
), as well as the ranks of its connected nodes. The nodes are mapped in a greedy way according to their ranking values.
Qing et al.
[12]
advocate a hybrid VNE algorithm by pruning the topologies of VNs with the Kcore decomposition. A VN is differentiated as a core network and multiple edge networks, which are respectively applied with certain twostage algorithm and onestage algorithm to leverage the respective advantages of these two kinds of algorithms simultaneously. In the core network and edge networks, node mapping employs the same “greedy” algorithm as previous algorithms did. Nevertheless, the Kcore decomposition is not adequate to the weighted networks and some specific topologies.
Wang et al.
[13]
exploit the “closeness centrality” (which will be discussed in details in Section 4) and propose two VNE algorithms. The node mapping process also works in a greedy way, where node ranking is based on each node’s closeness centrality. However, the closeness centrality is one network topological attribute and only measures how close a node is to other nodes. Their classical closeness algorithm has high acceptance ratio but low revenue/cost ratio. Thus, more topological attributes should be taken into consideration in order to achieve the optimal performance of VNE.
3. Virtual Network Embedding Problem
In this section, we describe the general model and objectives of the VNE problem.
Substrate Network
The topology of the substrate network is not always clear, especially when multiple InPs are involved in the multidomain VNE problem. By applying the topology discovery tool in
[14]
, the topology of the substrate network can be well revealed. Similar to previous work in
[9
,
11]
, a substrate network is denoted by a weighted undirected graph
where
N^{s}
refers to the set of physical nodes and
L^{s}
refers to the set of physical links.
denote the attributes of the physical nodes and links respectively. The attributes of a node include computation capacity, memory, disk capacity, buffer size, geographical location, and so on
[15]
. And the attributes of a link include bandwidth, propagation delay, bit error rate, and so on. In this paper we consider the typical CPU capacity as the node attribute and the typical bandwidth as the link attribute, just the same as most previous algorithms did. Therefore, each physical node
n^{s}
∈
N^{s}
is associated with an available CPU capacity
while each physical link
l^{s}
∈
L^{s}
is associated with an available bandwidth capacity
In addition, we use
P^{s}
to denote the set of all loopfree physical paths in the substrate network.
The right side of
Fig. 1
demonstrates a substrate network, where the numbers next to nodes are their available CPU resources and the numbers in parentheses over links represent their available bandwidths. The links thicker are the links with more bandwidth resources.
An example of virtual network embedding
Virtual Network Request
We use another weighted undirected graph
to denote a VN.
N^{v}
represents the set of virtual nodes and
L^{v}
represents the set of virtual links. Virtual nodes and links have CPU and bandwidth constraints, which are respectively denoted by
We also denote the
i^{th}
VNR by
VNR_{i}
(
G^{v}
,
t
,
d
,
t_{d}
).
t
is the arrival time of the VNR,
d
is its duration, i.e., for how long the VN plans to rent the resources in the substrate network, and
t_{d}
is its delay, i.e., for how long the VN is willing to wait before it is successfully embedded. Once
VNR_{i}
arrives, the substrate network tries to assign resources to this VNR to meet the resource requirements of its virtual nodes and links. If there are not sufficient substrate resources available,
VNR_{i}
will be postponed. If a VNR could not be embedded after time
t_{d}
, it will be rejected.
The left side of
Fig. 1
depicts two VNRs:
VNR_{1}
requires 10 units of CPU resources each at node
a
,
b
, and 30 at node
c
, and requires 15 units of bandwidth resources each over link (
a
,
c
), (
b
,
c
), and 10 over link (
a
,
b
).
VNR_{2}
needs a link of 20 units of bandwidth to connect node
d
and
e
, whose CPU constraints are 40 units and 15 units respectively.
VNE Problem
The embedding of a VNR onto the substrate network is defined by the mapping
M
from
G^{v}
to a subset of
G^{s}
:
where
Nʹ
⊂
N^{s}
,
Pʹ
⊂
P^{S}
, and
Aʹ_{N}
,
Aʹ_{L}
are the node and link resources assigned to the VNR, with all its constraints satisfied.
Fig. 1
also shows the VNE solutions for
VNR_{1}
and
VNR_{2}
. For
VNR_{1}
, the virtual node
a
,
b
, and
c
are mapped to the physical node
B
,
E
, and
A
, and the virtual link (
a
,
b
), (
a
,
c
), and (
b
,
c
) are mapped to the physical path (
B
,
C
,
E
), (
B
,
A
), and (
E
,
A
).
VNR_{2}
is mapped likewise. Note that the virtual nodes from different VNRs can be mapped onto the same physical node, but different virtual nodes from the same VNR cannot.
If a VNR has been successfully embedded, the assigned physical resources will be dedicated to it during its duration. When the time of the VN is over, the assigned resources will be released, and get ready to be reassigned for other VNRs.
Objectives
VNE is a multiobjective optimization problem. From InPs' perspective, the VNE problem has three main objectives: maximum revenue, maximum acceptance ratio, and maximum revenue/cost (RC) ratio. Revenue always comes first in business, and acceptance ratio ensures it. High revenue and acceptance ratio mean not only high market share but also a good reputation. Once the revenue is guaranteed, the efficiency of the resource utilization of the substrate network becomes important, which is measured by RC ratio.
Similar to previous work in
[7
,
9]
, the revenue of maintaining an embedded VNR at time
t
is defined as the weighted sum of total resources it demands:
where
CPU
(
n^{v}
) and
BW
(
l^{v}
) are CPU constraint of virtual node
n^{v}
and bandwidth constraint of virtual link
l^{v}
, respectively.
α
is a coefficient used to balance the relative revenues from CPU and bandwidth. So our first objective, the longterm average revenue, can be formulated as follows:
Let
VNR^{s}
denote the total VNRs and
VNR^{m}
denote the number of successfully mapped VNRs. Our second objective, the longterm acceptance ratio is defined as:
A little different from the revenue, the cost of mapping a VNR at time
t
is defined as the total consumption of resources:
where
Pʹ
is the set of physical paths assigned to the virtual links,
hop
(
Pʹ
) is the number of hops in physical path
Pʹ
, and
BW
(
Pʹ
) is the dedicated bandwidth over
Pʹ
. Note that the revenue of a VNR is not affected by the mapped physical paths. But when calculating the cost, InPs have to count the number of hops in each mapped physical path. This is reasonable, because obviously SPs do not want to pay for more number of hops assigned to the same virtual links.
With the revenue and cost of a VNR, we present the longterm RC ratio, in which we can see that to maximize the RC ratio, the number of hops of each mapped physical path should be minimized:
4. Topological Characteristics
Network topological attributes have a critical effect on the performance of VNE algorithms, and they emerge in the form of diverse characteristics, every one of which measures the relative influence or importance of nodes and links from different aspects. Degree is one basic topological characteristic of a node. So is the total bandwidth of all adjacent links of a node, named “strength”. Other topological characteristics can be obtained through centrality measures in the network analysis, which is widely used in disciplines like sociology
[16]
. In the scope of network analysis, nodes are characterized from multidimensional measures, including closeness centrality, betweenness centrality, eigenvector centrality, and Katz centrality
[17
,
18]
.
The degree of a node is the number of immediate links to its neighbors. Degree can be interpreted as the immediate possibility that a node contacts with others. The degree of a node
n_{i}
can be denoted as:
In a weighted network, links can be treated more than binary interactions. So the strength comes, which takes into account the total bandwidth of the same adjacent links contributing to the degree. The strength of node
n_{i}
is defined as follows, where
L
(
n_{i}
) is the set of adjacent links of
n_{i}
:
The closeness centrality is a natural distance metric between all pairs of nodes, based on the length of their shortest paths. It can be regarded as a measure of how close a node is to the network center. The farness of a node is defined as the sum of its shortest distances to all the other nodes, and its closeness is defined as the reciprocal of farness. So the lower the farness of a node is, the higher its closeness is, and the more central it is. The farness of node
n_{i}
is defines as:
where
d(
n_{i}
,
n_{j}
) is the length of shortest path between node
n_{i}
and
n_{j}
, and
N
is the sum of nodes. Note that
d(
n_{i}
,
n_{j}
) = 0 when
i
=
j
. Similar to
[13]
, the closeness of
n_{i}
is defined as:
The betweenness centrality quantifies the number of times a node acts as a bridge along the shortest path between any other two nodes. It reflects the switching capacity of a node in the network and has been applied to control the traffic flow in congestion. The betweenness of node
n_{i}
is denoted by:
where
P_{nj,nk}
is the number of shortest paths between node
n_{j}
and
n_{k}
, and
P_{nj,nk}
(
n_{i}
) is the number of those passing through
n_{i}
.
The eigenvector centrality uses eigenvectors of the adjacency matrix corresponding to a network, to determine the nodes that tend to be frequently visited. It assigns a relative score to every node based on the concept that connections to highscore nodes contribute more to the score of the node in question. The eigenvector centrality is mainly used to measure the directed networks. For a given graph
G
= (
N
,
L
), the adjacency matrix is defined to be
A
= (
a_{ni,nj}
) .
a_{ni,nj}
= 1 if node
n_{i}
links to
n_{j}
, and
a_{ni,nj}
= 0 otherwise. Let
γ
denote the eigenvalue, the eigenvector centrality of node
n_{i}
is formulated by:
The Katz centrality can be viewed as an extension of the eigenvector centrality. The relative influence of a node within a network is measured by summing the weighted paths between this node and all reachable nodes in the network. Paths connecting the node with its immediate neighbors carry higher weights than those connecting it with other nodes far away. Similar to the eigenvector centrality, the Katz centrality is also mainly used in directed networks, and is more suitable in directed acyclic graphs where the eigenvector centrality is rendered useless
[16]
. Similar to the eigenvector centrality, the Katz centrality is formulated as follows:
where
μ
is an attenuation factor by which the contribution of a distant node is penalized.
To summarize, a node with high degree has many connections while a node with high strength has strong connections. A node with high closeness centrality is, on average, at a short distance from other nodes in the network. A node with high betweenness centrality lies on many of the shortest paths between any other two nodes in the network
[19]
. A node with high eigenvector centrality or Katz centrality has a high probability of connecting to other nodes with high eigenvector centrality or Katz centrality. All these characteristics measure a node’s relative influence or importance within the network from different aspects.
5. Topologyaware Mapping Algorithms With Multiple Characteristics
Since Yu et al.
[9]
use the product of a node’s CPU and adjacent bandwidth in node ranking, many greedy node mapping algorithms later adopt the similar method. However, these node mapping algorithms could not give every node a comprehensive rank. A virtual node may choose a physical node with more than adequate CPU resource but not enough bandwidth resource, leading to the failure of subsequent link mapping process. Even if the bandwidth resource is adequate, adjacent virtual nodes may be mapped onto physical nodes far away from each other, which will cause higher costs and increase the network fragmentation that gradually prevents the substrate network from accepting more VNRs.
We argue that the disadvantages of traditional greedy node mapping can be eliminated by utilizing more topological attributes. Therefore, we propose a topologyaware approach that integrates multiple topological characteristics into the node mapping process and leverages their respective advantages. In addition, our approach aims to better coordinate node and link mapping, and thus improve the success rate and efficiency of the link mapping process and the performance of VNE.
A motivational example of using the characteristic “degree” in node ranking is illustrated in
Fig. 2
, where the numbers next to nodes are their CPU capacities and the numbers in parentheses over links represent their bandwidth capacities. The links thicker are the links with more bandwidths. Node N and M have equal CPU capacities (i.e., 75) and strengths (i.e., 340), and are considered equivalent in traditional node ranking. However, Node N should have higher priority than Node M, especially when path splitting is supported by the substrate network. This is because the degree of Node N is 5, higher than the degree of Node M (i.e., 4), which means that Node N has not only strong connections but also more connections. Therefore, mapping a virtual node to Node N may have a higher chance to achieve a successful and lowcost link mapping.
A motivational example
Similar to “degree”, other characteristics, “closeness (farness) centrality”, “betweenness centrality”, “eigenvector centrality”, and “Katz centrality”, can also help to improve the performance of VNE. When the characteristics used in node ranking fail to tell the proper differences between nodes, other topological characteristics can be used to rank the nodes more accurately, and thus the success rate and efficiency of subsequent link mapping are improved. Our node ranking reflects not only nodes’ CPU resources but also topological attributes. Obviously, using such a node ranking method to construct VNE solutions can increase the possibility of satisfying the resource requirements of VNRs and reduce the costs of embedding and network fragmentation.
Because the effects of these topological characteristics on the performance of VNE are not well understood, we attempt to integrate them into node ranking step by step, so as to better reveal and compare their influence over the practical VNE algorithms. In the remainder of this section, we propose three heuristic algorithms based on “degree”, “strength”, “closeness (farness) centrality”, and “betweenness centrality” in
5.1
,
5.2
and
5.3
from simple to complex. As for
5.4
, we adopt the algorithm in
[11]
, which includes the implementation of “eigenvector centrality” and “Katz centrality”, and improve it by applying our three new node ranking methods.
 5.1. Mapping Algorithm with Degree
Firstly, we extend the traditional node mapping with “degree”. The degree and strength of a node both measure the extent to which it is connected to the rest of the network, from two complementary aspects. By adding degree, we wish to enhance the influence of local resources in node mapping. We define the amount of resources for node
n_{i}
by:
Our algorithm is a twostage VNE algorithm. We describe the node mapping algorithm with degree in Algorithm 1. Time is discretized into consecutive time windows and the VNR queue is applied to store a group of unmapped and incoming VNRs with irregular arrival times during a time window. During the node mapping process, we collect in the queue all the VNRs that just arrive or should be mapped during the current time window at first, and then sort them according to their revenues. The unchecked VNR with largest revenue has priority. When a VNR is to be embedded, the
R_{d}
in (13) for each virtual node and physical node will be calculated and act as their ranking values. Note that the CPU, degree and strength of a physical node in
R_{d}
are all calculated using its realtime residual resources. Thus the amount of available resources
R_{d}
of a physical node can reflect the dynamic state of the substrate network. Our algorithm maps the virtual node with the highest rank to the physical node with the highest rank that satisfies every constraint and is unmapped with any other nodes from the same VNR. Other virtual nodes of the VNR will be mapped in the same greedy way according to the order of their ranks. Some VNRs may be postponed due to the lack of resources in the substrate network, and have to wait for next time window to be mapped. A VNR is rejected once it cannot be served within its tolerant delay. The algorithm will go back to the queue to find the next unchecked VNR with the largest revenue until every VNR is mapped, postponed or rejected.
The link mapping process follows the node mapping process. Virtual links are embedded by the kshortest path algorithm
[20]
if path splitting is not supported by the substrate network or the MultiCommodity Flow (MCF) algorithm
[21]
if path splitting is supported. The kshortest path algorithm is shown in Algorithm 2. The MCF algorithm is implemented by the PPRN package
[22]
, which is generally appropriate to solve a high variety of MCF problems with linear/nonlinear objective functions and with/without linear side constraints.
Once all the virtual nodes and links have been mapped, the embedding of a VNR succeeds. The dedicated resources of a VNR will be released when its duration is over and get ready to be reassigned for other VNRs.
 5.2. Mapping Algorithm with Degree and Closeness
Secondly, we take into consideration the closeness (farness) centrality. The closeness and farness is a pair of interesting distance metrics. They are analogous to the distance in physics. Let us consider two classical equations in physics: Newton's law of universal gravitation in gravitational field is
and Coulomb's law in electromagnetism is
Just like these two equations in physics describing the interactions between discrete particles, the distances between them have an inversesquare effect on their interactions. This is because the interactions in universe usually decrease over distances in an inversesquare way, rather than an isometric way. The closer one has a much stronger effect on the one in question than the farther one. We argue that the above principle applies to the node’s farness in the context of node ranking as well, i.e., the farness of a node has an inversesquare effect on its importance in the network. Therefore we formulate the amount of resources for node
n_{i}
by:
Steps of the algorithm with degree and closeness (farness) are similar to those of the algorithm with degree in
5.1.
The main difference is the calculating method of node ranking, in which
R_{d}
(
n_{i}
) is replaced by
R_{dc}
(
n_{i}
). And we employ the Floyd–Warshall algorithm to obtain the closeness (farness) by calculating shortest paths between all pairs of nodes.
 5.3. Mapping Algorithm with Degree, Closeness and Betweenness
Thirdly, we further extend the node mapping with betweenness centrality, which captures the switching capacity of a node. A node with higher switching capacity should have higher priority than the one with lower switching capacity. Therefore, we integrate it into node ranking and define the amount of resources for
n_{i}
by:
The algorithm with degree, closeness and betweenness is similar to the algorithm with degree and closeness in
5.2.
However, the calculating method of node ranking changes to
R_{dcb}
(
n_{i}
). In addition, calculating both the closeness (farness) and the betweenness of each node involves calculating shortest paths between all pairs of nodes. So we modify the Floyd–Warshall algorithm in order to find and locate all the shortest paths between any two nodes.
 5.4. Mapping Algorithm with Eigenvector Centrality and Katz Centrality
Finally, we try to implement the eigenvector centrality and the Katz centrality. Google's PageRank is a variant of eigenvector centrality and Katz centrality
[23]
that assign relative scores to all nodes in the network, and the major difference is the scaling factors. So is the Random Walk (RW) algorithm in
[11]
. The RW algorithm transplants Google’s PageRank algorithm into the VNE problem, along with a Markov Random Walk model.
PageRank considers a link from web page A to web page B as a vote. A web page is considered more important if more important web pages (either in quantity or quality) vote for it. In doing so, the topology of the web can influence the PageRank of a web page. In the context of VNE, the RW algorithm considers a node to be more important if a node links to more nodes with more resources
[11]
. Treating the connectivity between any two nodes as a Markov chain transition with certain probability, the RW algorithm iteratively calculates the relative resource quality of a node based on the product of its CPU and adjacent bandwidth, and the qualities of its neighbors.
We adopt the RW algorithm, which includes the implementation of eigenvector centrality and Katz centrality. Steps of the RW algorithm will not be repeatedly described here. To further integrate other topological characteristics, we improve it by applying three new node ranking methods proposed in
5.1
,
5.2
, and
5.3
. Three modified RW algorithms are proposed respectively, in which the iterative computation of the relative resource quality of a node is based on (13), (14), or (15), along with the qualities of its neighbors.
6. Topology Decomposition
In Section 5 we use six topological characteristics to design three new algorithms and three modified algorithms based on our new node ranking methods. In this section we further explore the use of topological characteristics in the VNE problem from another aspect.
Just like the productivity of modern economy is based on the division of labor, division has been proved to play a vital role in solving many difficult problems in all kinds of disciplines. Some previous heuristic VNE algorithms have applied the theory of division in different ways. Most of the VNE algorithms can be divided into two stages, firstly the node mapping stage and secondly the link mapping stage. Some VNE algorithms (e.g.,
[6]
) differentiate nodes as different types, while some others (e.g.,
[7
,
8]
) divide the VNs into many subgraphs.
Qing et al.
[12]
prune the topology of a VN by using the Kcore decomposition algorithm to divide it into a core network and multiple edge networks, and try to leverage the respective advantages of different VNE algorithms at the same time. Intuitively, a network core is a set of nodes that are highly and mutually interconnected. For a binary network, the Kcore of a graph is the maximal connected subgraph comprising nodes with degree at least k, and is derived by recursively deleting the nodes with degree less than k. Kcore decomposition is an important tool for the visualization of complex networks
[24
,
25]
.
However, Kcore decomposition is not adequate to the weighted networks and some specific topologies (e.g., star topology or tree topology), as a result of only considering the number of connections, i.e., the characteristic “degree”. We demonstrate it in
Fig. 3
(a), where there is a VNR with 9 nodes. A thick line denotes a strong link with high bandwidth while a thin one denotes the opposite. As we can see, node
a
,
b
,
c
,
e
, and
h
all have a strong link to each other, which implies some structural or functional importance in the network. After applying the Kcore decomposition to this topology, node
d
,
e
,
f
,
g
,
h
, and
i
are all peeled off as nodes of edge networks, and only node
a
,
b
, and
c
are included in the core network. Obviously this is not a satisfactory division where node
e
and node
h
are excluded from the core network.
An example of KScore decomposition and mapping of a virtual network request
Here, we advocate utilizing multiple topological characteristics to devise new algorithms of topology decomposition, in order to better disentangle the hierarchical structure of a VN.
The strength, which is complementary to the degree, naturally becomes our first choice. A node with high degree has many connections while a node with high strength has strong connections. Therefore, the strength can be treated as a more sophisticated version of the degree, where a node does not depend on the number of links incident to it but on the qualities of those links. By taking into consideration both the number of connections and their qualities, we propose a new KScore decomposition algorithm, in which the “S” stands for the “Strength”.
We implement the KScore decomposition by recursively removing the nodes whose degree equals to 1 and strength is less than the Strength Threshold, and pruning the corresponding links as well. The Strength Threshold is a parameter predefined according to the topologies of VNRs and the substrate network (such as the average bandwidth of links, the sum of nodes, and the linking probability of nodes), so as to properly differentiate the core network and the edge networks. The decomposition process will stop once no further removal is possible or the number of residual nodes in the VNR reaches the Minimum value, which should also be predefined to achieve the relative balance of nodes in core network and in edge networks. The remaining KScore contains only nodes with strength greater than the Strength Threshold and degree at least 2, and the pruned parts are multiple edge networks. We describe the KScore decomposition algorithm in Algorithm 3.
In
Fig. 3
(b), we show the result of the same VNR in
Fig. 3
(a) after applying the KScore decomposition algorithm. Five nodes incident to strong links, represented by red solid lines, are included in the core network. The residual parts, represented by blue dashed lines, are three independent edge networks.
Fig. 3
(c) and
Fig. 3
(d) depict the mapping of the core network and edge networks respectively.
To compare KScore decomposition algorithm with Kcore decomposition algorithm in the evaluation, we employ the same node mapping algorithms and link mapping algorithms as that in
[12]
. The evaluation results will be presented in the next section.
7. Performance Evaluation
In this section, we first describe the performance evaluation environment that is configured similar to previous work
[9
,
11
,
12]
, and then present our main evaluation results. Our evaluation focuses primarily on quantifying the benefits of our different algorithms.
 7.1. Evaluation Environment
Because the actual substrate networks and VNs are not well understood yet, we use GTITM tool
[26]
to generate substrate networks and VNRs in our evaluation as most previous work did. Each substrate network is configured to have 100 nodes with over 500 links, which is about the scale of a mediumsized ISP. And the corresponding CPU and bandwidth resources are real numbers uniformly distributed from 50 to 100. The arrival of VNRs is modeled following a Poisson process with an average arrival rate of 5 VNs per 100 time units. We assume that each VN has an exponentially distributed duration with an average of 500 time units, while the delay is 200 time units. The number of nodes in a VNR is configured as a uniform distribution between 5 and 20. Pairs of virtual nodes are randomly connected by links with the probability of 0.5, which means a
n
node VN has
n
(
n
– 1)/4 links on average. CPU and bandwidth requirements of virtual nodes and virtual links are real number uniformly distributed between 1 and 50. Each experiment runs ten different instances, and each instance lasts for more than 56000 time units, corresponding to about 2800 VNRs. The arithmetic mean of ten instances is recorded as the final result.
ALGORITHMS IN COMPARISON
We implement three VNE simulators to respectively compare our 7 proposed topologyaware algorithms with 4 corresponding existing algorithms. The notations we refer to different algorithms are enumerated in
Table 1
, along with the simulators used. The ND
^{#}
simulator is a modified version of the VNE simulator
[27]
designed in
[9]
, the RW
^{#}
simulator is a modified version of the simulator in
[11]
, and the KS
^{#}
simulator is a modified version of the simulator in
[12]
. Performance metrics in comparison are three objectives presented in Section 3, i.e., the longterm average revenue, acceptance ratio, and RC ratio.
 7.2. Evaluation Results
The evaluation consists of three parts with three simulators respectively: (1) using the ND
^{#}
simulator to compare two baseline algorithms BL in
[9]
and CL in
[13]
with our three algorithms ND, NDC, and NDCB; (2) using the RW
^{#}
simulator to compare the baseline algorithm RW in
[11]
with three modified algorithms RWND, RWNDC, and RWNDCB; (3) using the KS
^{#}
simulator to compare the baseline algorithm Kcore in
[12]
with KScore decomposition algorithm. In all the following figures, the performance metrics are plotted against the time.
 7.2.1. Mapping Algorithms with Multiple Characteristics
Fig. 4
shows the longterm average revenue, acceptance ratio, and RC ratio of two baseline algorithms BL, CL, and three topologyaware algorithms ND, NDC, and NDCB. All the curves reach a relatively steady state after about 10000 time units.
average revenue, acceptance ratio, and revenue/cost ratio of 5 algorithms in comparison
In the left part of
Fig. 4
, the average revenue of algorithm ND is remarkably higher than that of the baseline algorithm BL, and algorithm NDC further improves it. The baseline algorithm CL shows impressively high average revenue as well, while algorithm NDCB has the relatively highest average revenue, which is about 8% higher than BL. We can see that a more comprehensive algorithm that considers multiple topological characteristics does improve the longterm average revenue.
The middle part of
Fig. 4
shows the results of the longterm acceptance ratio, which reveal a similar relationship to these of the longterm average revenue, and also confirm that high acceptance ratio usually guarantees high revenue. However, there is an exception. The baseline algorithm CL has almost the same high acceptance ratio as NDCB, which is about 8% higher than BL. Compared with the average revenue in the left, CL accepts as many VNRs as NDCB does, but obtains relatively lower average revenue. It indicates that the use of closeness centrality can increase the acceptance ratio, but has a tendency of accepting relatively smaller VNRs in the long term. This is because CL only chooses the nodes closer to the center of topology, and does not consider the load balance of the substrate network, which may easily lead to the fragmentation of substrate network resources. Thus, CL can accept the VNRs with smaller sizes, but has to reject those VNRs with large sizes. NDCB accepts more VNRs and achieves higher average revenue than others at the same time.
The right part of
Fig. 4
shows the results of the longterm RC ratio, which demonstrate a little different relationship of 5 algorithms in comparison. The curves of RC ratios all have a slow downward trend because of the gradual fragmentation of the substrate network over time. As a result, virtual links of VNRs have to be embedded into longer physical paths. The RC ratios of ND and NDC are remarkably higher than that of BL. However, CL has impressively low RC ratio, and NDCB has relatively higher RC ratio that is still lower than BL. NDC is about 5% higher than CL. We can see that ND and NDC improve the efficiency of embedding, but CL and NDCB achieve higher average revenues and acceptance ratios by sacrificing the efficiency more or less.
To summarize, our algorithm NDCB has relatively highest longterm average revenue and acceptance ratio, but these gains come at a penalty in the longterm RC ratio. Our algorithm ND improves the longterm average revenue, acceptance ratio, and RC ratio at the same time, while NDC further improves them. The baseline algorithm CL performs well in the longterm average revenue and acceptance ratio, but has a rather poor RC ratio.
 7.2.2. Modified Algorithms with Multiple Characteristics
Fig. 5
shows the longterm average revenue，acceptance ratio, and RC ratio of the baseline algorithm RW and three modified algorithms RWND, RWNDC, and RWNDCB.
average revenue, acceptance ratio, and revenue/cost ratio of 4 algorithms in comparison
The left part and middle part of
Fig. 5
reveal similar relationship of these algorithms with respect to the longterm average revenue and acceptance ratio. The RW* algorithms all have higher average revenues and acceptance ratios than the original RW algorithm, while RWNDC has similar average revenue and acceptance ratio as RWND. However, RWNDCB does not achieve the highest average revenue and acceptance ratio as expected. The iterative computation of obtaining the ranking of nodes in the RW and RW* algorithms does not reveal the advantages of using certain topological characteristics, such as betweenness centrality. Nevertheless, the use of multiple topological characteristics can still effectively improve the longterm average revenue and acceptance ratio of the RW algorithm.
The right part of
Fig. 5
shows the longterm RC ratio of 4 algorithms in comparison. The curves of RC ratio of RW* algorithms, especially the algorithm RWNDCB, are lower than that of the original RW algorithm. This indicates that RW* algorithms sacrifice the efficiency more or less, and the use of degree, strength, and closeness centrality performs better with the RW algorithm than the use of betweenness centrality.
To summarize, the modified RW algorithms using our node ranking methods all achieve higher average revenue and acceptance ratio than the original RW algorithm, but these gains come at a penalty in the longterm RC ratio.
 7.2.3. KScore Decomposition Algorithm
Fig. 6
shows the longterm average revenues, acceptance ratio, and RC ratio of the Kcore decomposition algorithm in
[12]
and our KScore decomposition algorithm predefined with different Strength Thresholds.
average revenue, acceptance ratio, and revenue/cost ratio of 2 Algorithms in comparison
The KScore decomposition algorithm has a very slight effect on the acceptance ratio compared to the Kcore decomposition algorithm, but an obvious effect on the average revenue and especially the RC ratio. When the Strength Threshold is set to be 60 or higher, the KScore decomposition algorithm has relatively the best performance in terms of the longterm average revenue and RC ratio (about 7% improvement). The performance cannot be further improved with higher Strength Threshold, because the number of edge nodes with their strengths below the Strength Threshold will not increase any more. When the Strength Threshold is 50, the KScore decomposition algorithm also has a relatively better performance in terms of the longterm average revenue and RC ratio than the Kcore decomposition algorithm. However, when the Strength Threshold is 40, the longterm average revenue is hardly improved, and the RC ratio is lower than the Kcore decomposition algorithm. This effect is more distinct when the Strength Threshold is 30. To achieve the best performance of our KScore decomposition algorithm, the Strength Threshold should be properly configured according to the topologies of VNRs and the substrate network.
8. Conclusion
The VNE problem is an open issue in network virtualization. We introduce six topological characteristics complementary to each other, which measure the relative influence or importance of nodes in the substrate network and VNs from different aspects. Based on the introduced topological characteristics, we propose three topologyaware VNE algorithms and three corresponding modified algorithms for the RW algorithm, by leveraging the respective advantages of different characteristics. On the other hand, KScore decomposition algorithm is devised to utilize the topological characteristics from the aspect of topology decomposition in the VNE problem. Extensive simulations between our 7 proposed algorithms and 4 baseline algorithms demonstrate that our algorithms better coordinate node and link mapping, and substantially increase the longterm average revenue, acceptance ratio, and RC ratio compared to the previous algorithms.
In our future work, the six characteristics proposed should be further analyzed in order to understand their relationships and their exact influence over the practical VNE algorithms, and avoid mutual interferences. Furthermore, topology decomposition with multiple topological characteristics will be further studied.
BIO
Jianxin Liao obtained his PhD degree from University of Electronics Science and Technology of China in 1996. He is currently the dean of Network Intelligence Research Center and the full professor of State Key laboratory of Networking and Switching Technology in Beijing University of Posts and Telecommunications. He has published hundreds of research papers and several books, and has been granted dozens of patents for inventions. His prizes include the Premier's Award of Distinguished Young Scientists from National Natural Science Foundation of China in 2005, and the Speciallyinvited Professor of the “Yangtse River Scholar Award Program” by Ministry of Education of China in 2009. His main creative contributions include mobile intelligent network, service network intelligent, networking architectures and protocols, and multimedia communication. These achievements were conferred the “National Prize for Progress in Science and Technology” twice, respectively in 2004 and 2009.
Min Feng is a PhD candidate in Communication and Information System, from the State Key Lab of Networking and Switching Technology in Beijing University of Posts and Telecommunications. His research interests include network virtualization, cloud computing, and data center network.
Tonghong Li obtained his PhD degree from Beijing University of Posts and Telecommunications in 1999. He is currently an assistant professor with the department of computer science, Technical University of Madrid, Spain. His main research interests include resource management, distributed system, middleware, wireless networks, and sensor networks.
Jingyu Wang obtained his PhD degree from Beijing University of Posts and Telecommunications in 2008. He is currently an associate professor in Beijing University of Posts and Telecommunications. His research interests span broad aspects of performance evaluation for Internet and overlay network, consumer electronic, traffic engineering, image/video coding, and multimedia communication over wireless network.
Sude Qing received his PhD degree in Computer Science from Beijing University of Posts and Telecommunications in 2013. His research interests include cloud computing and network virtualization.
Anderson T.
,
Peterson L.
,
Shenker S.
,
Turner J.
2005
“Overcoming the Internet impasse through virtualization”
IEEE Computer Magazine
Article(CrossRef Link)
38
(4)
34 
41
DOI : 10.1109/MC.2005.136
Turner J.
,
Taylor D.
“Diversifying the Internet”
in Proc. of IEEE GLOBECOM
vol. 2, pp.755760, 2005. Article(CrossRef Link)
Feamster N.
,
Gao L.
,
Rexford J.
2007
“How to lease the Internet in your spare time”
ACM SIGCOMM Computer Communication Review
Article(CrossRef Link)
37
(1)
61 
64
DOI : 10.1145/1198255.1198265
Bavier A.
,
Feamster N.
,
Huang M.
,
Peterson L.
,
Rexford J.
2006
“In VINI veritas: Realistic and controlled network experimentation”
ACM SIGCOMM Computer Communication Review
Article(CrossRef Link)
36
(4)
3 
14
DOI : 10.1145/1151659.1159916
Szeto W.
,
Iraqi Y.
,
Boutaba R.
“A multicommodity flow based approach to virtual network resource allocation”
in Proc. of IEEE GLOBECOM
vol. 6, pp. 30043008, 2003. Article(CrossRef Link)
Zhu Y.
,
Ammar M.
2006
“Algorithms for assigning substrate network resources to virtual network components”
in Proc. of IEEE INFOCOM
Article(CrossRef Link)
Houidi I.
,
Louati W.
,
Zeghlache D.
2008
“A distributed virtual network mapping algorithm”
in Proc. of IEEE ICC
Article(CrossRef Link)
5634 
5640
Yu M.
,
Yi Y.
,
Rexford J.
,
Chiang M.
2008
“Rethinking virtual network embedding: substrate support for path splitting and migration”
ACM SIGCOMM Computer Communication Review
Article(CrossRef Link)
38
(2)
17 
29
DOI : 10.1145/1355734.1355737
Chowdhury N.
,
Rahman M.
,
Boutaba R.
2009
“Virtual network embedding with coordinated node and link mapping”
in Proc. of IEEE INFOCOM
Article(CrossRef Link)
783 
791
Cheng X.
,
Su S.
,
Yang F.
2011
“Virtual network embedding through topologyAware node ranking”
ACM SIGCOMM Computer Communication Review
Article(CrossRef Link)
41
(2)
38 
47
DOI : 10.1145/1971162.1971168
Qing S.
,
Liao J.
,
Wang J.
,
Zhu X.
,
Qi Q.
2012
“Hybrid virtual network embedding with Kcore decomposition and timeoriented priority”
in Proc. of IEEE ICC
Article(CrossRef Link)
2695 
2699
Wang Z.
,
Han Y.
,
Lin T.
,
Tang H.
,
Ci S.
2012
“Virtual network embedding by exploiting topological information”
in Proc. of IEEE GLOBECOM
Article(CrossRef Link)
Marchetta P.
,
Mérindol P.
,
Donnet B.
,
Pescapé A.
,
Pansiot J.
2011
“Topology discovery at the router level: a new hybrid tool targeting ISP networks”
IEEE Journal on Selected Areas in Communications
Article(CrossRef Link)
29
(9)
1776 
1787
DOI : 10.1109/JSAC.2011.111003
Stezenbach D.
,
Hartmann M.
,
Tutschku K.
2012
“Parameters and challenges for virtual network embedding in the future internet”
in Proc. of IEEE NOMS
Article(CrossRef Link)
1272 
1278
Newman M.
2010
Networks: An Introduction
Oxford University Press
Oxford, UK
Article(CrossRef Link)
Opsahl T.
,
Agneessens F.
,
Skvoretz J.
2010
“Node centrality in weighted networks: generalizing degree and shortest paths”
Social Networks
Article(CrossRef Link)
32
(3)
245 
251
Freeman L.
2004
The development of social network analysis
Empirical Press
Vancouver, Canada
Hagmann P.
,
Cammoun L.
,
Gigandet X.
2008
“Mapping the structural core of human cerebral cortex”
PLoS biology
Article(CrossRef Link)
6
(7)
e159 
DOI : 10.1371/journal.pbio.0060159
Ahuja R. K.
,
Magnanti T. L.
,
Orlin J. B.
,
Weihe K.
1993
Network flows: theory, algorithms, and applications
Prentice Hall
Castro J.
,
Nabona N.
1996
“An implementation of linear and nonlinear multicommodity network flows”
European Journal of Operational Research
Article(CrossRef Link)
92
(1)
37 
53
DOI : 10.1016/03772217(95)001379
Austin D.
2006
“How Google finds your needle in the web’s haystack”
American Mathematical Society Feature Column
10 
12
Dorogovtsev S. N.
,
Goltsev A. V.
,
Mendes J. F. F.
2006
“Kcore organization of complex networks”
Physical review letters
Article(CrossRef Link)
96
(4)
DOI : 10.1103/PhysRevLett.96.040601
AlvarezHamelin J. I.
,
Dall’Asta L.
,
Barrat A.
,
Vespignani A.
2005
“Large scale networks fingerprinting and visualization using the kcore decomposition”
Advances in neural information processing systems
41 
50
Zegura E.
,
Calvert K.
,
Bhattacharjee S.
1996
“How to model an Internetwork”
in Proc. of IEEE INFOCOM
Article(CrossRef Link)
Virtual Network Embedding Simulator.
https://github.com/minlanyu/embed