Clustering-based energy-aware virtual network embedding

Abstract

Virtual network embedding has received a lot of attention from researchers. In this problem, it needs to map a sequence of virtual networks onto the physical network. Generally, the virtual networks have topology, node, and link constraints. Prior studies mainly focus on designing a solution to maximize the revenue by accepting more virtual networks while ignoring the energy cost for the physical network. In this article, to bridge this gap, we design a heuristic energy-aware virtual network embedding algorithm called EA-VNE-C, to coordinate the dynamic electricity price and energy consumption to further optimize the energy cost. Extensive simulations demonstrate that this algorithm significantly reduces the energy cost by up to 14% over the state-of-the-art algorithm while maintaining similar revenue.

Keywords

Network virtualization virtual network embedding energy cost clustering

Introduction

Network virtualization supports multiple virtual networks (VNs) to exist on one physical network (PN). It provides “Network as a service.” Each VN may have different topologies and different numbers of nodes and links, for deploying different applications. How to embed such VNs onto the PN while satisfying the topology, node, and link constraint is termed as VN embedding problem. This problem has been proved to be non-deterministic polynomial-time hard (NP-hard).¹

Since the VN embedding problem is one of the most significant challenges, it has been widely studied. However, most of these studies^1–3 are devoted to designing efficient approaches with the goal of embedding more VNs and generating more revenues with little attention to the energy-related cost generated by the PN. In fact, energy-related cost is becoming more and more important, which is about 50% of the operating cost.⁴ For example, in the United States, Akamai, one of the world’s leading providers of content delivery networking services, has an annual electricity cost of about US$10 million.⁵ In China, China Mobile Communications Corporation, the largest mobile service provider in the world, consumed over 13 TWH power consumption in 2011.⁶ To conserve more energy in VN embedding, we have studied energy-aware VN embedding problem in previous studies.^7–9 In such studies, we observe that the electricity price varies a lot for different locations and it also exhibits great time diversity for just a location. Thus, we proposed to leverage such diversities to save energy in VN embedding. However, it still awaits to be further optimized because it first selects the physical domain with the lowest price and then performs the intra-domain VN embedding. That means, it does not coordinate these two factors together, that is, the power and electricity price. Selecting the physical domain with lowest price may cause the problem of high energy consumption and thus suffers from high energy costs. In this article, we propose to coordinate the power and electricity price together to further optimize the energy cost. Specifically, we first use the topology of the VN to generate a weighted similarity graph for capturing the similarity between each two virtual nodes. We then employ local clustering technique to cluster the virtual nodes. We next perform the VN embedding based on such clusters. Through extensive simulations, we show that our algorithm can significantly reduce energy consumption by up to 14% over the state-of-the-art algorithm.

The key contributions of this article are listed as follows:

To the best of our knowledge, this is the first attempt to coordinate the electricity price and power consumption to save energy cost in VN embedding problem.

To address this problem, we proposed a clustering-based coordinated VN embedding approach to further optimize the energy cost.

We conducted extensive simulations for evaluating our algorithm. We show that our algorithm reduces energy consumption by up to 14% over the existing migration-oblivious algorithm.

Modeling and formulation

In this section, we define the network model and the electricity price model first. We then specify how to calculate the electricity cost in terms of a given mapping solution. In the end, we give the performance metrics.

Network model

A PN consists of a set of physical domains and a set of backbone links connecting between them. So, we use $G_{p} = (⋃_{u} D_{u}, L_{p})$ to denote the graph of PN, where $D_{u}$ is a physical domain on the graph $G_{p}$ and $L_{p}$ is a set of cross-domain links that link between domains. And we have $D_{u} = (N_{u}, L_{u})$ , where $N_{u}$ is the set of physical nodes inside the domain $D_{u}$ and $L_{u}$ is the set of local links between nodes of $N_{u}$ inside one $D_{u}$ . In our real world, a domain could be some data centers in which there are several computing nodes and local links, and there are backbone links connecting the data centers across different domains.

For a domain, there are two properties: location and electricity price. The electricity price we used is from the real-world power market. In our model, we denote $Pric e_{u, t}$ as the electricity price of domain $u$ at time point $t$ .

A physical node can be denoted as $i$ with the properties of CPU capacity and current load. A physical link, including local link and backbone link, between nodes $i$ and $j$ can be denoted as $l_{ij}$ , consisting of properties of bandwidth and current load.

We use $G_{v} = (N_{v}, L_{v})$ to denote a VN, where $N_{v}$ is the set of virtual nodes and $L_{v}$ is the set of virtual links. A virtual node could be denoted as $m$ with the properties of CPU requirement and domain constraint. Under the domain constraint, the virtual node could only be mapped to a set of given domains. Similar to physical link, a virtual link between virtual nodes $m$ and $n$ can be denoted as $l_{mn}$ , having the property of bandwidth requirement.

In this way, we can use $R_{v} = (G_{v}, t_{a}, t_{d})$ to denote a VN request, where $G_{v}$ is the requested VN and $t_{a}$ , $t_{d}$ are the arrival time and duration, respectively. Finally, we define the VN embedding problem as finding a node mapping solution and link mapping solution to satisfy all the nodes’ and links’ requirements of a request.

The notations used are given in Table 1.

Table 1.

Notations.

Notation	Description
$x_{j}^{u}$	A binary variable. $x_{j}^{u} = 1$ if virtual node $u$ is mapped to the substrate node $j$ and 0 otherwise
$f_{jk}^{uv}$	A binary variable. $f_{jk}^{uv} = 1$ if virtual link $l_{uv}$ is routed on physical link $l_{jk}$ and 0 otherwise
$D_{u}$	The location of node $u$ , which can be represented by $(x_{u}, y_{u})$
$Dis (u, j)$	The Euclidean distance between $u$ and $j$ , which can be calculated by $\sqrt{{(x_{u} - x_{j})}^{2} + {(y_{u} - y_{j})}^{2}}$
$W_{u}$	Indicating how far $u$ can be placed from its own location to the location of substrate nodes
$N_{i}^{H}$	The number of hosting nodes needing to be powered on from off state in ith domain
$N_{i}^{F}$	The number of forwarding nodes needing to be powered on from off state in ith domain
$P_{b}$	The baseline power for a server
$P_{l}$	The power proportional factor for CPU utilization
$S_{j}$	The power state of substrate node $j$ . $S_{j} = 1$ if j is in on state and 0 otherwise
$Δ PN$	The additional node power consumption
$Δ PL$	The additional link power consumption
$Δ E_{s}$	One-time power consumption for powering up
$Δ EN$	The additional node energy cost
$Δ EL$	The additional link energy cost
$Δ ES$	The additional switching energy cost

Power cost modeling

To calculate the power consumption of the VN embedding, we classify the power consumption into three categories: node power cost, link power cost, and switching power cost.

Node power cost

For embedding a VN, there are two kinds of roles for each node involved: hosting node and forwarding node. Hosting nodes are responsible for providing the CPU capacity and doing computation as required, and forwarding nodes are used to forward the traffic between hosting nodes if two of the hosting nodes are not connected directly.

As we can see in previous studies, the power consumption of normal server is a linear growth with the utilization of CPU.¹⁰

So, we use the following equation to evaluate the power consumption of an active node

PN = P_{b} + P_{l} \cdot util

(1)

where $P_{b}$ is the basic power consumption of an active node, $P_{l}$ is the additional power consumption of full CPU utilization, and $util$ is the current load of this node. Thus, the additional power consumption for mapping a virtual hosting node $h$ to $j$ is

Δ PN = {\begin{matrix} P_{b} + P_{l} \cdot C_{h} (if S_{j} = 0) \\ P_{l} \cdot C_{h} (otherwise) \end{matrix}

(2)

Let $N_{i}^{H}$ and $N_{i}^{F}$ denote the additional number of hosting nodes and forwarding nodes in the ith domain, respectively. There will be two part of power consumption: the first is the baseline part and the second is the linear increasing part. For the first part, there will be $N_{i}^{H} + N_{i}^{F}$ new nodes. These nodes will consume baseline power at the amount of $(N_{i}^{H} + N_{i}^{F}) \cdot P_{b}$ . For the second part, it is $\sum_{u \in N_{v}} \sum_{i \in G} \sum_{j = 1}^{| N_{p_{i}} |} x_{j}^{u} P_{l} CPU (u)$ . Thus, the node energy cost can be calculated as

\begin{matrix} Δ EN = \int_{T_{a}}^{T_{a} + T_{d}} PN \cdot P r_{i} (t) dt \\ = \sum_{u \in N_{v}} \sum_{i \in G} \sum_{j = 1}^{| N_{p_{i}} |} x_{j}^{u} P_{l} CPU (u) \int_{T_{a}}^{T_{a} + T_{d}} P r_{i} (t) dt \\ + \sum_{i \in G} (N_{i}^{H} + N_{i}^{F}) P_{b} \int_{T_{a}}^{T_{a} + T_{d}} P r_{i} (t) dt \end{matrix}

Link power cost

We consider both long physical links, which span over a large geographical region and therefore require repeaters that consume power, and short physical links that span a small geographical region and require no repeaters. We use ${PL}_{st}^{uv}$ to denote the power consumption of the repeaters on a long link $l_{st} \in L_{sr}$ when mapping a virtual link $l_{uv} \in L_{vr}$ . The overall link cost can be calculated as

Δ EL = \sum_{l_{uv} \in L_{vr}} \sum_{l_{st} \in L_{sr}} f_{st}^{uv} Δ {PL}_{st}^{uv} P r_{s} (t) dt

(4)

We set $Δ {PL}_{st}^{uv}$ to be linear with the traffic volume of $l_{uv}$ and the distance between $s$ and $t$ based on the findings in Chiaraviglio et al.¹¹

Δ {PL}_{st}^{uv} = Dis (s, t) \cdot P_{r} \cdot \frac{B_{uv}}{O B_{st}}

(5)

where $P_{r}$ denotes the power density of the repeaters over distance and $O B_{st}$ denotes the overall bandwidth capacity of substrate backbone link $l_{st}$ .

Switching power cost

Powering up a server incurs one-time energy consumption for transiting from the power-saving state into the active state, which is called the switching cost. We use $N_{s}$ to denote how many nodes are powering up and $Δ E_{s}$ to denote the cost for one time of powering up. The overall switching cost can be calculated as

Δ ES = \sum_{r \in N_{v}} \sum_{i \in N_{p}} N_{s} E_{s} \cdot \int_{t_{a}}^{t_{e}} P r_{i} (t) dt

(6)

Performance metrics

Revenue

We define the long-term average revenue for mapping VN requests as follows

lim_{T \to \infty} \frac{\sum_{i = 1}^{N} R^{i} (G_{v})}{T}

(7)

where $R^{i} (G_{v}) = (\sum_{h \in N_{v}} C_{h} + \sum_{l_{v} \in L_{v}} B (l_{v})) \cdot t_{d}$ represents the revenue for mapping the ith VN request.

Energy cost

Based on equations (3), (4), and (6), for embedding a VN, the energy cost can be calculated as

Min Δ E = Δ EN + Δ EL + Δ ES

(8)

To calculate energy cost in the long run, we define the long-term average energy cost as follows

lim_{T \to \infty} \frac{\sum_{i = 1}^{N} E^{i} (G_{v})}{T}

(9)

where $N$ is the number of VN requests accepted by the PN successfully in time $T$ and $E^{i} (G_{v})$ denotes the energy cost for the ith VN request.

Proposed solution

Motivation

Electricity cost is a large overhead in VN embedding, and thus there are a handful of studies focusing on energy-aware approaches to cut down the cost. However, they have not coordinated both electricity price and energy consumption into consideration. Some of them only consider the energy consumption,^7,12 which will lead to a huge cost of electricity. Some of them only consider the electricity price,⁹ which will lead to high energy consumption. To achieve the goal of minimizing energy cost, the ideal algorithm should take the following factors into account: (1) mapping virtual nodes into the physical domain with lower electricity price, (2) consolidating virtual nodes into less number of physical nodes for energy saving, and (3) shortening the length of inter-domain physical links for energy saving. In order to achieve the goals above, we design an efficient algorithm called EA-VNE-C, to coordinate the electricity price and energy consumption together. Specifically, we first use the topology of the VN to generate a weighted similarity graph for capturing the similarity between each two virtual nodes. We then employ local clustering technique to cluster the virtual nodes and next perform the VN embedding based on such clusters.

Evaluating clustering coefficient

Before we get started, we define the cluster as a group of virtual nodes in which virtual nodes can be mapped into the same physical domain. We use $a$ and $b$ to denote them later.

For each cluster $a$ , we denote $D_{a}$ as the set of physical domains that all of the virtual modes inside $a$ can be mapped into.

For each pair of clusters $a$ and $b$ , we can denote $b w_{ab}$ as the cross-domain bandwidth between clusters $a$ and $b$ . It can be evaluated as the sum of request required bandwidth between each pair of virtual nodes inside the clusters $a$ and $b$ .

Unlike the classical local clustering schemes in social network, we evaluate the affinity as the clustering coefficient to measure the degree to which virtual nodes in a graph tend to cluster together. And we denote $w_{ab}$ as the affinity between the clusters $a$ and $b$ .

We use $Pric e_{i} = \int_{t_{a}}^{t_{e}} Pric e_{i, t} dt$ to denote the integral of electricity price in the time $[t_{a}, t_{e}]$ . We use $Pric e_{\max} = \max {Pric e_{i}}, \forall i \in D,$ to denote the maximum electricity price in all domains and use $Pric e_{\min} = \min {Pric e_{i}}, \forall i \in D,$ to denote the minimum electricity price in all domains.

So, we have

w_{ab} = {\begin{matrix} w_{ab}^{*} & D_{a} ⋂ D_{b} \neq \emptyset \\ 0 & D_{a} ⋂ D_{b} = \emptyset \end{matrix}

(10)

\begin{array}{l} w_{a b}^{*} = α \cdot \frac{P r i c e_{m a x} - \bar{P r i c e_{a b}}}{P r i c e_{m a x} - P r i c e_{m i n}} + (1 - α) \cdot \frac{b w_{a b}}{b w_{m a x}}, \\ α \in (0, 1) \end{array}

where

\bar{Pric e_{ab}} = \sum_{i \in D_{a} \cap D_{b}} {(\frac{Pric e_{\max} - Pric e_{i}}{Pric e_{\max} - Pric e_{\min}})}^{1 / r}, r \in Z^{+}

and

b w_{\max} = \max {b w_{ab}}, \forall a, b \in N_{v}

Here, $α$ is a bias for the weight of electricity price against link bandwidth and $r$ is a factor to enlarge the weight of sharing in physical domains between virtual node clusters.

Clustering

Our algorithm is based on a local clustering scheme, aiming to group virtual nodes into clusters and mapping each cluster into the best physical domain.

Our algorithm aims to coordinate the following aspects at the same time: (1) how much is the electricity price of a physical domain during the request, (2) how many physical domains could each pair of virtual nodes both mapped into, and (3) how much bandwidth does each pair of virtual nodes need. In this way, we can map virtual nodes into less physical domains with the lowest electricity price.

In this step, we apply local clustering technique to virtual nodes to group them into clusters. The input of this algorithm is the VN graph, and the output is the set of clusters. First, we produce a set of clusters and make it empty set initially. Second, we make each virtual node as a cluster and add this cluster to the result set. Third, we calculate the affinity between each pair of clusters and find the pair with the maximum affinity. If the maximum affinity is 0, that is, there is no pair of clusters which could be joined together, we end up the algorithm. Otherwise, we join the pair of clusters of the maximum affinity into one cluster. And then, we repeat this step until the maximum affinity meets 0. Finally, we return the set of remaining clusters.

VN embedding

In the second step, we apply energy-aware VN node and link embedding strategies in our previous studies.^8,9 The core idea of the VN node mapping strategy lies in that we use the best-fit scheme to consolidate the virtual nodes to the minimum number of substrate nodes while meeting the CPU requirements of these virtual nodes. Specifically, (1) we first use $N_{cpu}$ to denote the difference in CPU capacities between the physical node $n_{s}$ and the virtual node $n_{v}$ , that is, $N_{cpu} = CPU (n_{s}) - CPU (n_{v})$ . Note that only the substrate nodes which can satisfy the CPU constraint of $n_{v}$ are considered as candidate nodes. (2) We then rank the candidate physical nodes according to the values of $N_{cpu}$ in non-decreasing order. (3) We finally embed each virtual node to the physical node with the highest ranking.

The core idea of the VN link mapping strategy lies in that we consider the power state of physical nodes and design active-preferred shortest algorithm. It means that, we calculate several shortest paths for each pair of corresponding physical nodes and select the physical path with maximum number of active physical nodes.

Time complexity

In Algorithm 1, for a given VN of size $n$ , there are $n$ virtual nodes in this network, and it costs $O (n^{2})$ time to calculate $w_{ab}$ for each pair of virtual nodes $a$ and $b$ . It is $O (n)$ to have $w_{\max} = 0$ and converge in the worst case. Therefore, Algorithm 1 is a polynomial-time algorithm. In Algorithm 2, as we know,⁹ previous VN embedding scheme can be computed in polynomial-time. Hence, our algorithm is also a polynomial-time algorithm.

Algorithm 1. The clustering algorithm
Input: $G_{v}$ , $G_{p}$ Output: $C$ (the set of clustered virtual nodes) 1. $Clusters = {\emptyset}$ 2. for each virtual node $i$ in $G_{v}$ do 3. Add Cluster ${i}$ to $C$ . 4. while $true$ do 5. forfor each pair of cluster $a$ and $b$ in $C$ do 6. Calculate $w_{ab}$ according to equation (10); 7. Find the pair of $a$ and $b$ with $w_{\max} = w_{ab}$ . 8. if $w_{\max} = 0$ then 9. break; 10. else 11. Add $a ⋃ b$ to $C$ . 12. Remove $a$ and $b$ from $C$ . 13. return $C$ ;

Algorithm 1. The clustering algorithm

Input:

G_{v}

G_{p}

Output:

C

(the set of clustered virtual nodes)
1.

Clusters = {\emptyset}

2. for each virtual node

i

G_{v}

do
3. Add Cluster

{i}

C

.
4. while

true

do
5. forfor each pair of cluster

a

and

b

C

do
6. Calculate

w_{ab}

according to equation (10);
7. Find the pair of

a

and

b

with

w_{\max} = w_{ab}

.
8. if

w_{\max} = 0

then
9. break;
10. else
11. Add

a ⋃ b

C

.
12. Remove

a

and

b

from

C

.
13. return

C

;

Algorithm 2. The VN embedding algorithm
Input: $G_{v}$ , $G_{p}$ , $C$ (obtained from Algorithm 1) Output: mapping solutions for nodes and links 1. foreach Cluster $C_{a}$ in $C$ do 2. Find physical domain $p$ in $D_{a}$ with the lowest electricity price. 3. foreach virtual node $u \in C_{a}$ do 4. Map $n_{v}$ to the physical node using the best-fit scheme in the selected PN. 5. ifCPU constraint not satisfiedthen 6. $return$ $NM_FAILED$ 7. for each link $l_{v}$ do 8. Remove the substrate links that do not satisfy the bandwidth constraint. 9. Find the shortest paths in the residual underlay. 10. Search a path $P$ on these paths with least number of inactive substrate nodes. 11. iflink constraint not satisfiedthen 12. $return$ $LM_FAILED$ 13. Output the node and link mapping solutions.

Algorithm 2. The VN embedding algorithm

Input:

G_{v}

G_{p}

C

(obtained from Algorithm 1)
Output: mapping solutions for nodes and links
1. foreach Cluster

C_{a}

C

do
2. Find physical domain

p

D_{a}

with the lowest electricity price.
3. foreach virtual node

u \in C_{a}

do
4. Map

n_{v}

to the physical node using the best-fit scheme in the selected PN.
5. ifCPU constraint not satisfiedthen
6.

return

NM_FAILED

7. for each link

l_{v}

do
8. Remove the substrate links that do not satisfy the bandwidth constraint.
9. Find the shortest paths in the residual underlay.
10. Search a path

P

on these paths with least number of inactive substrate nodes.
11. iflink constraint not satisfiedthen
12.

return

LM_FAILED

13. Output the node and link mapping solutions.

Performance evaluation

Experimental setup

Like most previous works, we generate the PN and VN graphs by Georgia Tech Internetwork Topology Models. We use the similar configuration to the one in previous papers.⁹ The PN used consists of five domains which are located in a $100 \times 100$ grid randomly. In each of the domains, the number of uniform physical nodes is from $50$ to $90$ . The CPU capacity of a node varies from $50$ to $100$ . There is $50 %$ link connectivity between the nodes, that is, each pair of nodes inside a domain is connected with probability of $50 %$ . The bandwidth of each intra-domain links varies from $50$ to $100$ , and the bandwidth of inter-domain links is $10$ times of intra-domain. We use three different VN scales in this experiment: small size, regular size, and large size. Like each domain in PN, the virtual nodes in each VN are also located randomly in a $100 \times 100$ grid. The number of virtual nodes of a single request is 2–5, 2–10, and 2–15 for each VN size, respectively. The link connectivity is of $50 %$ . The range of CPU capacity and link bandwidth is $0 - 50$ . To simulate the request over the VNs, we assume that the arrival of requests is a Poisson process with average arrival rate of three requests per 60 time units. The request’s duration is an exponential distribution with an average of 500 time units. Our simulation starts from time point $0$ to $40, 000$ , consisting of about 2000 requests. The electricity prices for the domain we used are the real-world electricity price records of five regional transmission organization in September 2011 in the United States (available at: www.ferc.gov).¹³

We set $P_{r}$ to 1 W per distance unit so that the electricity cost of links is about $10 %$ of the nodes’ cost. By default, we set the bias factor $α$ to $0.3$ and exponent $r$ to $3$ .

We implement the algorithms in C++ and perform them side-by-side on Ubuntu 14.04 with 2.6 GHz CPU and 8 GB RAM.

In the first step, we compare our algorithm (denoted as EA-VNE-C) with the one (EA-VNE) that maps every virtual node into its corresponding lowest priced domain. We track down the long-term revenue, long-term electricity cost, active nodes’ count, mapping success rate, and running time for each 4000 time unit. In the second step, we compare between the above two algorithms on the variations of regular-sized VN. We evaluate the same performance as described in the first step under different request arrival densities and request duration densities. To facilitate such comparisons, we multiply 0.25, 0.5, 2, and 4 to request arrival time and duration, respectively. We use the result at the time point of 40,000 time unit for these comparisons. In the third step, we compare the performance of our algorithm with different bias factors, that is, $α$ value. We take $α$ as 0.1, 0.3, 0.5, 0.7, and 0.9. We use the regular-sized VN as the input, and also use the same performance as described in the first step above and the results at the time point of 40,000 time unit in this step.

Evaluation results

Comparison with EA-VNE under various VN scales

We first compare our algorithm to the state-of-the-art algorithm under different VN scales. We report the comparison results in Figures 1 –3. We also summarize the results in Figure 4. The results show that, compared to EA-VNE, the long-term revenue–cost ratios (long-term revenue divided by long-term cost) of EA-VNE-C increase by $5.9 %$ , $10.8 %$ , and $14.3 %$ , on small, regular, and large VNs respectively.

Figure 1.

Comparisons between our algorithm and the state-of-the-art algorithm (small-sized VNs): (a) revenue, (b) mapping ratio, (c) energy cost, and (d) revenue/cost (RC) ratio.

Figure 2.

Comparisons between our algorithm and the state-of-the-art algorithm (regular-sized VNs): (a) revenue, (b) mapping ratio, (c) energy cost, and (d) revenue/cost (RC) ratio.

Figure 3.

Comparisons between our algorithm and the state-of-the-art algorithm (large-sized VNs): (a) revenue, (b) mapping ratio, (c) energy cost, and (d) revenue/cost (RC) ratio.

Figure 4.

Comparisons between our algorithm and the state-of-the-art algorithm (different scales): (a) revenue, (b) mapping ratio, (c) energy cost, and (d) revenue/cost (RC) ratio.

On one hand, EA-VNE-C has the same mapping success rate as EA-VNE or even slightly better in some cases, which leads to a tie on the aspect of the long-term revenue. On the other hand, EA-VNE-C successfully cuts down the electricity cost on all VN scales. And as we can see, EA-VNE-C has a better long-term revenue–cost ratio. Thus, EA-VNE-C is more profitable on the same cost of electricity.

The reason that EA-VNE-C gets more long-term profit than EA-VNE is obvious. EA-VNE always chooses the domain with the lowest electricity price to map, while EA-VNE-C considers both the electricity price and the topology of VN. In this way, EA-VNE-C can manage to cut down the electricity price by mapping to lowest priced domain, and it also minimizes the electricity energy by clustering virtual nodes together.

Regarding running time comparison, as shown in Figure 5, EA-VNE-C finishes all computation in a slightly more time than EA-VNE. The reason is that it produces a better domain selection by clustering (Algorithm 1), which is helpful to find out the best node–link mapping solution in the fastest way (Algorithm 2).

Figure 5.

Time comparisons between our algorithm and the state-of-the-art algorithm (different scales).

However, on the small scaling network, virtual nodes are very sparse. Clustering before node mapping, in a way, could lead to the same result as direct selection by electricity price sometimes. Thereby, EA-VNE-C is not much better than EA-VNE in this case.

Impact of request density

We next evaluate the impact of the request density on the performance on our algorithm. We multiply 0.25, 0.5, 2, and 4 for the arrival time and duration of VN requests, respectively. We also use the result at the time point of 40,000 time unit for these comparisons. We report the comparison results in Figures 6 and 7. As the request gets denser, the mapping success rate for both EA-VNE and EA-VNE-C drops (as shown in Figures 6(b) and 7(b)), while the long-term revenue and long-term electricity cost rise (as shown in Figures 6(a), 6(c), 7(a), and 7(c)). Compared to EA-VNE, EA-VNE-C has a better mapping success rate and gets more long-term revenue while getting a little more on electricity cost. After all, EA-VNE-C improves the average long-term revenue–cost ratio by $12.4 %$ and $11.7 %$ than EA-VNE, under all request arrival density and duration density, respectively. As the requests arrive more frequently or keep longer, the available resource becomes more less. Thus, it is more difficult to find a mapping method with low electricity price and bandwidth utilization. However, EA-VNE-C still performs better in this case by clustering virtual nodes.

Figure 6.

Comparisons between our algorithm and the state-of-the-art algorithm (different arrival density): (a) revenue, (b) mapping ratio, (c) energy cost, and (d) revenue/cost (RC) ratio.

Figure 7.

Comparisons between our algorithm and the state-of-the-art algorithm (different duration density): (a) revenue, (b) mapping ratio, (c) energy cost, and (d) revenue/cost (RC) ratio.

Impact of bias factor

We next evaluate the impact of the parameter $α$ on the performance of our algorithm. We compare the performance of our algorithm with different bias factors, that is, $α$ value. We report such comparison results in Figure 8. We take $α$ as 0.1, 0.3, 0.5, 0.7, and 0.9. We use the regular-sized VN as the input, and also use the same performance as described in the first step above and the results at the time point of 40,000 time unit in this step.

Figure 8.

Comparisons between our algorithm and the state-of-the-art algorithm (different alpha values): (a) revenue, (b) mapping ratio, (c) energy cost, and (d) revenue/cost (RC) ratio.

In this case, we can find that the best $α$ value is $0.3$ for the requests on the regular-sized VN. Along with the $α$ value going lesser or greater than $0.3$ , as shown in Figure 8(a), the long-term revenue gets slightly less, while the long-term electricity cost is greater, and the long-term revenue–electricity ratio decreased.

Recall that $α$ value denotes the weight of electricity price against the weight of bandwidth in the affinity formulation. A smaller value of $α$ will enlarge the weight of topology aspect, while a larger value of $α$ will enlarge the weight of electricity price aspect. To coordinate two of the aspects, we should take a medium-sized $α$ value.

Related work

Since Yu et al.¹ propose the VN embedding framework formally, it has attracted increasing number of researchers’ attentions. There are two lines for addressing this problem: one is revenue-aware VN embedding and the other one is energy-aware VN embedding.

Revenue-aware VN embedding

Yu et al.¹ propose to leverage the path splitting and migration technique to increase the acceptance ratio of embedding a VN. Chowdhury et al.² formulate this problem to be a mixed integer programming model and employ the relax and rounding technique to solve this model. Zhang et al.³ present an opportunistic resource sharing–based mapping framework and propose two first-fit-based algorithms to maximize the utilization of the PN for VNs with dynamic demands. Some other techniques have also been applied in this branches, such as subgraph isomorphism algorithm¹⁴ and ant colony metaheuristic algorithm.¹⁵ Our work differs from these existing studies in the following way: we try to address the energy-cost-aware VN embedding problem, which can save energy cost and increase the net profit for the infrastructure provider.

Energy-aware VN embedding

To save energy consumption for carrying out VN embedding, Su and colleagues^7–9 propose the corresponding solution. Its core idea is that it leverages the location and time-varing diversities of electricity price to save the energy cost for multi-domain VN embedding. Our article proposes to further optimize the cost by coordinating electricity price and power consumption.

Recently, Zhang et al.¹² propose to save energy for VNs with dynamic demands. They first model the dynamics of VN demands as a combination of a Gaussian distribution. They then leverage this model and propose two efficient algorithms to minimize the energy consumption while keeping a high revenue for the PN. One algorithm processes the VN requests one by one, while the other one processes them group by group. We will also consider this factor to extend this article in the future.

Virtualized systems

There are also some other virtualized platforms^16,17 to achieve high performance for the system. The authors can read the surveys^18,19 of network virtualization and VN embedding for further reference.

Security and privacy issues

Besides the VN embedding allocation problem in cloud computing, there are also some hot topics, for example, security issues^20–30 and privacy issues^31,32 in cloud computing, which have attracted a lot of attention. Due to the page limits, we do not introduce them one by one.

Conclusion

In this article, we take a further step and coordinate the dynamic electricity price and energy consumption to optimize the energy cost. We first use the topology of the VN to generate a weighted graph for capturing the affinity between each two virtual nodes on the aspects of the electricity price and topology. We then employ local clustering algorithm to cluster the virtual nodes based on the affinity graph and finally perform the VN embedding based on such clusters. Through extensive simulations, we demonstrate that our algorithm saves up to 14% energy cost for the PN than the existing algorithm while obtaining attractive revenues.

Footnotes

Academic Editor: Hyungshin Kim

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported in part by the following funding agencies of China: National Natural Science Foundation under grants 61602050, 61170274, and U1534201.

References

Rexford

et al . Rethinking virtual network embedding: substrate support for path splitting and migration. ACM SIGCOMM Comp Com 2008; 38(2): 17–29.

Chowdhury

Rahman

Boutaba

. ViNEYard: virtual network embedding algorithms with coordinated node and link mapping. IEEE/ACM Trans Netw 2012; 20(1): 206–219.

Zhang

Qian

et al . Virtual network embedding with opportunistic resource sharing. IEEE T Parall Distr 2014; 25(3): 816–827.

Chun

Iannaccone

et al . An energy case for hybrid datacenters. ACM SIGOPS Oper Syst Rev 2010; 44(1): 76–80.

Qureshi

Weber

Balakrishnan

et al . Cutting the electric bill for internet-scale systems. In: Proceedings of the ACM SIGCOMM 2009 conference on data communication, Barcelona, 16–21 August 2009, pp.123–134. New York: ACM.

China Mobile Research Institute, https://s3-us-west-2.amazonaws.com/belllabs-microsite-greentouch/uploads/documents/Chih-Lin_I%20-%20TIA%20Green%20from%20a%20Service%20Provider%20Perspective.pdf

Zhang

Cheng

et al . Energy-aware virtual network embedding through consolidation. In: Proceedings IEEE INFOCOM workshops-CCSES: green networking and smart grids, Orlando, FL, 25–30 March 2012, pp.2708–2713. New York: IEEE.

Zhang

Liu

et al . Energy-aware virtual network embedding. IEEE/ACM Trans Netw 2014; 22(5): 1607–1620.

Zhang

Niu

et al . Minimizing electricity cost in geographical virtual network embedding. In: Proceedings IEEE global communication conference, Anaheim, CA, 3–7 December 2012, pp.2609–2614. New York: IEEE.

10.

Fan

Weber

Barroso

. Power provisioning for a warehouse-sized computer. In: Proceedings of the 34th annual international symposium on computer architecture, San Diego, CA, 9–13 June 2007, pp.13–23. New York: ACM.

11.

Chiaraviglio

Mellia

Neri

. Minimizing ISP network energy cost: formulation and solutions. IEEE/ACM Trans Netw 2012; 20(2): 463–476.

12.

Zhang

et al . Energy aware virtual network embedding with dynamic demands: online and offline. Comput Netw 2015; 93: 448–459.

13.

United States Federal Energy Regulatory Commission, www.ferc.gov

14.

Lischka

Karl

. A virtual network mapping algorithm based on subgraph isomorphism detection. In: Proceedings of the 1st ACM workshop on virtualized infrastructure systems and architectures, Barcelona, 17 August 2009, pp.81–88. New York: ACM.

15.

Fajjari

Aitsaadi

Pujolle

et al . VNE-AC: virtual network embedding algorithm based on ant colony metaheuristic. In: Proceedings of the 2011 IEEE international conference on communications, Kyoto, Japan, 5–9 June 2011. New York: IEEE.

16.

Lin

Dong

. Providing virtual memory support for sensor networks with mass data processing. Int J Distrib Sens Netw 2013; 9(3): 1–20.

17.

Shi

Chung

. A traffic-aware quality-of-service control mechanism for software-defined networking-based virtualized networks. Int J Distrib Sens Netw 2017; 13(3): 1–13.

18.

Chowdhury

Boutaba

. A survey of network virtualization. Comput Netw 2010; 54(5): 862–876.

19.

Fischer

Botero

Beck

et al . Virtual network embedding: a survey. IEEE Commun Surv Tut 2013; 15(4): 1888–1906.

20.

Guan

et al . Toward efficient multi-keyword fuzzy search over encrypted outsourced data with accuracy improvement. IEEE T Inf Foren Sec 2016; 11(12): 2706–2716.

21.

Zhou

Wang

et al . Effective and efficient global context verification for image copy detection. IEEE T Inf Foren Sec 2016; 12(1): 48–63.

22.

Xia

Wang

Sun

et al . A secure and dynamic multi-keyword ranked search scheme over encrypted cloud data. IEEE T Parall Distr 2016; 27(2): 340–352.

23.

Zhu

Guo

Yin

et al . Scalable link prediction in dynamic networks via non-negative matrix factorization. Technical report, 2014, https://arxiv.org/abs/1411.3675

24.

Yang

et al . Segmentation-based image copy-move forgery detection scheme. IEEE T Inf Foren Sec 2015; 10(3): 507–518.

25.

Yuan

Sun

. Fingerprint liveness detection based on multi-scale LPQ and PCA. China Commun 2016; 13(7): 60–65.

26.

Zhang

Sun

Wang

. Efficient algorithm for k-barrier coverage based on integer linear programming. China Commun 2016; 13(7): 16–23.

27.

Zhangjie

Xingming

et al . Achieving efficient cloud search services: multi-keyword ranked search over encrypted cloud data supporting parallel computing. IEICE T Commun 2015; 98(1): 190–200.

28.

Ren

Shen

Wang

et al . Mutual verifiable provable data auditing in public cloud storage. J Internet Technology 2015; 16(2): 317–323.

29.

Xia

Wang

Sun

et al . Steganalysis of least significant bit matching using multi-order differences. Secur Commun Netw 2014; 7(8): 1283–1291.

30.

Pan

Zhang

Kwong

. Efficient motion and disparity estimation optimization for low complexity multiview video coding. IEEE T Broadcast 2015; 61(2): 166–176.

31.

Xia

Wang

Zhang

et al . A privacy-preserving and copy-deterrence content-based image retrieval scheme in cloud computing. IEEE T Inf Foren Sec 2016; 11(11): 2594–2608.

32.

Ren

Shu

et al . Enabling personalized search over encrypted outsourced data with efficiency improvement. IEEE T Parall Distr 2016; 27(9): 2546–2559.