Energy-aware virtual network embedding in flexi-grid networks

Rongping Lin; Shan Luo; Haoran Wang; Sheng Wang

doi:10.1364/OE.25.029699

1. Introduction

Network virtualization technology has been proposed to hide the complex details of the substrate network, and provides virtualized resources (such as computation, storage, and networking) to users, and allow multiple heterogeneous virtual networks (VNs) to coexist on a shared substrate network, which increases the flexibility of the substrate network management and network resource utilizations [1]. A VN consists of virtual nodes and virtual links, and mapping a VN onto the substrate network is known as the virtual network embedding (VNE) problem. Therefore, the VNE problem consists of: the virtual node embedding which is to map the virtual nodes to physical nodes under node computation resource constraints, and the virtual link embedding which is to map the virtual links to physical paths under bandwidth resource constraints [2]. An example is shown in Fig. 1, where multiple VNs are embedded in a substrate network. Virtual nodes are mapped to physical nodes and computation resources are reserved, and virtual links are mapped to physical paths and bandwidth resources are reserved. It is clear that a physical node or a physical link can be shared by multiple VNs. For simplicity, we only show virtual links e₁ and e₂ of two different VNs are embedded into p₁ and p₂ respectively, where a substrate node and a substrate link are shared.

Fig. 1 VNE in network virtualization.

Download Full Size | PDF

Most of literatures on the VNE problem work on the objective of accommodating more VN requests with limited resources to increase the network revenue. There are some publications [3–5] focus on the scenario that all VNs are known already, including computation requirements at virtual nodes and bandwidth demands of virtual links, and the problem is to embed all VN requests with the minimal resources. Other work [6–8] focus on the scenario that VN requests arrive one-by-one, and the request leaves the network after receiving services, and the problem is to allocate resources for an arriving VN request based on the current network state. After the service, the VN request will leave the network and the occupied resources will be released.

In addition to the network virtualization technology, the flexi-grid technology is also proposed to increase the flexibility of optical networks [9]. In contrast, the traditional wavelength-division multiplexing (WDM) technology allocate spectrum with the fixed and coarse granularity, which leads to low bandwidth utilization problems. For example, a wavelength channel must be allocated to a connection request that requires less than the whole wavelength capacity. To overcome this, in flexi-grid optical networks, spectrum is uniformly slotted by a much finer granularity than that in WDM networks (e.g. 6.25 GHz v.s. 50 GHz), then network operators can efficiently allocate spectrum resources to connections. Specifically, just enough frequency slots (or spectrum slots) are allocated to connections achieving a finer sub-wavelength granularity than WDM [2, 10, 11]. There are some publications on the VNE problem in flexi-grid optical networks. An auxiliary graph with meta-nodes was proposed in [8, 11], and the meta-nodes are clustering nodes where virtual nodes can be embedded and the virtual link mapping becomes the commodity flow problem among meta-nodes. In [12, 13], an auxiliary graph was built based on the available spectrum resources, and in the graph, the number of spectrum resources adjacent to a physical node is taken into consideration in virtual node mapping, where the physical nodes with more adjacent spectrum resources have higher probabilities to find feasible lightpaths for virtual links.

Energy consumption has been significantly increased with the traffic explosion. It was reported that 1,500 TWh of electricity which was approximately 10% of global electricity generation was consumed by the information and communication technology (ICT) in 2013 and the usage was predicted to double in 2023 [14]. While in cloud networks, the annual energy bill was estimated to exceed the cost of equipments in the long term with current trends maintain [15]. Accordingly, efforts have been devoted to the energy-aware VNE problem. In [16], the energy efficient VNE problem for cloud networks was investigated. A set of VN requests were given, and a mixed integer linear programming (MILP) was proposed to minimize the overall power consumption of the network and data centers. However, this work was on IP over WDM networks, and wavelength continuity constraint was not considered because wavelength convertors were assumed at all network nodes. In [17], a mixed integer programming (MIP) was developed for the VNE problem with energy awareness, where the objective function was to minimize the number of physical links and nodes that will be activated for accommodating the arriving VN request. The authors assumed that the energy savings from switching off a node and from a link are equal. This work did not consider optical networks and cannot be applied in flexi-grid optical networks. In [18], a linear programming (LP) was proposed for the energy-aware VNE problem, and the objective function is to minimize the number of working nodes and intermediate nodes that need to be powered on from off state. A two-stage heuristic algorithm was also proposed where the node mapping and link mapping were coordinated by considering the connectivity constraint for the subsequent link mapping. In [19], a MIP was formulated for the VNE problem with the objective of minimizing energy consumption, a linear relaxation and heuristic methods for the virtual link mapping were applied to obtain integer solutions. In [20], cost and energy in the VNE problem based on the knowledge of the entire daily traffic profile and on the knowledge of the current traffic information were investigated.

To the best of our knowledge, all the publications on the energy-aware VNE problem above are based on the physical networks with computation resource and bandwidth resource limitations only, which cannot be directly applied in flexi-grid optical networks. In flexi-grid optical networks, the bandwidth resource is allocated in term of frequency slots and continuity and contiguity constraints must be satisfied, i.e. the same frequency slots should be used along the lightpath (continuity constraint), and the allocated frequency slots in a link should be contiguous (contiguity constraint). This paper works on the energy-aware VNE problem in flexi-grid optical networks.

The remainder of this paper is organized as follows. Section II gives the details of energy consumption in flexi-grid optical networks. Section III describes the ILP formulation of the problem. In Section IV, we propose a heuristic algorithm for large networks. Section V evaluates both ILP and the heuristic algorithm by simulations. Section VI concludes this paper.

2. Energy consumption in flexi-grid optical networks

In this paper, the devices in flexi-grid optical networks that have energy consumptions include servers and network devices. The servers are attached to physical nodes of the network, which provide computation resources to the virtual nodes hosted. The network devices in the flexi-grid optical network include bandwidth variable transceiver (BVT), bandwidth variable OXC (BV-OXC), erbium doped fiber amplifier (EDFA) in this work.

To illustrate the details of energy consumptions, an end-to-end transmission (a→b→c) in the flexi-grid optical network is shown in Fig. 2. This transmission is a lightpath that provides an optical end-to-end connection, where at the source a and destination c, a transmitter module and a receiver module are used for emitting and receiving the optical signal, respectively. In the intermediate nodes b, BV-OXC bypasses the optical signal in the optical domain without optical-electronic-optical conversions. The optical signal is transmitted in optical fibers that attenuates the signal power, so optical amplifiers, i.e. EDFA, are applied. In the figure, the node architecture of physical node consists of BV-OXC, BVT and server. The BVT contains transmitter module and receiver module. It is noted that a transmitter and a receiver are usually built together in a transceiver. Accordingly, in Fig. 2, the devices along the lightpath that consume energy are listed as follows: the server at node a, the BVT at node a, the BV-OXC at node a, the EDFA between node a and node b, the BV-OXC at node b, the EDFA between node b and node c, the BV-OXC at node c, the BVT at node c, finally the server at node c.

Fig. 2 An end-to-end transmission in flexi-grid networks.

Download Full Size | PDF

According to [21, 22], the power of physical link (m, n) caused by EDFA is calculated in Eq. (1), where L_mn is the distance of link (m, n), and each EDFA has the power of 13W. The power of a BV-OXC is calculated by Eq. (2), where deg(t) denotes the degree of the physical node t.

P_{m n}^{E D F A} = [⌈ L_{m n} / 80 - 1 ⌉ + 2] \cdot 13

P_{t}^{B V O X C} = 85 d e g (t) + 150

Usually, a server has power consumption variations according to the CPU utilization, and a comparable idle power (may be more than 50% of the maximal power usage) is consumed even the CPU utilization is zero [23]. It is clear that the energy consumption of a network becomes high even most of servers work on low utilization leaves, and it is necessary to merge work loads to increase utilizations and reduce the overhead from idle powers. A BVT has the similar power consumption behavior to a server, where idle power is considered regardless of the device utilization. However, the power consumptions of BV-OXC and EDFA are not sensitive to the traffic load, and the power consumptions do not change accordingly.

3. ILP based resource allocation

In general, the VNE problem has been based on two phases: virtual node embedding and virtual link embedding. Our goal is to embed the arriving VN request considering the electricity cost, in particular we provide: 1) virtual node embedding information, each virtual node is mapped to a specific physical node and computation resources are reserved, which decides the ends of physical paths that provide connections for virtual links; 2) virtual link embedding information, each virtual link is mapped to a set of physical links that forms a lightpath connecting two physical nodes hosting the ends nodes of the virtual link, and spectrum slots along the lightpath are reserved which meet the constraints of continuity and contiguity; 3) electricity cost information, the occupations of devices are updated, so does the the energy consumption of the network.

Usually, an ILP is used to solve a static (deterministic) optimization problem, but our ILP-based method applies to a dynamic set-up. When a VN request arrives, the ILP formulation is used to derive an embedding solution for the request. After service is complete, the VN request leaves the network and the occupied resources are released. The available network resources are changed according to request arrivals and departures. If a VN request cannot be accommodated because of lack of resources, the ILP cannot find a feasible solution, and this request is blocked. In the following, we provide the ILP formulation that minimizes the electricity cost of the VN request.

3.1. ILP formulation

Given

G^s(N^s, L^s): a directed graph represents the substrate network, where N^s is the set of physical nodes and L^s is the set of physical links.
G^v(N^v, L^v): a directed graph represents an arriving VN request, where N^v is the set of virtual nodes and L^v is the set of virtual links.
r_i: the computation resource requirement of virtual node i, i ∈ N^v.
r_ij: the bandwidth requirement of virtual link (i, j), (i, j) ∈ L^v in terms of number of spectrum slots.
F: the set that contains slot indexes of a physical link in the network.
U_k: the number of residual computation resources at node k, k ∈ N^s.
U_mn_,f : indicates the status of fth slot in physical link (m, n), where (m, n) ∈ L^s, f ∈ F. It takes the value of 1 when fth slot of link (m, n) is available, otherwise 0.
$P_{s e r v e r}^{i d l e}$ , $P_{B V T}^{i d l e}$ : the idle powers of server and BVT.
P_server, P_slot: the power consumption of one unit utilization increment of server and power consumption of a spectrum slot at BVT.
$P_{m n}^{E D F A}$ : the power consumption of link (m, n) caused by EDFAs, which is calculated by Eq. (1), where (m, n) ∈ L^s.
$P_{k}^{B V O X C}$ : the power consumption of BV-OXC at node k, which is calculated by Eq. (2)k ∈ N^s.
α_k, β_k, γ_k and δ_mn: indicates the existing status of server, BVT, BV-OXC of physical node k and EDFA (physical link) mn before embedding, respectively. They take the value of 1 when the according device is already on, otherwise 0. For example, if BV-OXC of node k is already turned on, (1 − γ_k) is equal to 0 that means the arriving VN request can use this device without the need to switch it on and there is no power consumption increment.
Δu_k(r_i): the utilization increment of server at physical node k if virtual node i is embedded at node k.
c_k: the unit electricity cost at node k, where k ∈ N^s.
c_mn: the unit electricity cost at link (m, n), where (m, n) ∈ L^s.
V: a large enough integer.

Variables

$M_{m n, f}^{i j}$ : a Boolean variable. It takes the value of 1 when virtual link (i, j) traverses physical link (m, n) with the spectrum allocation starting from fth slot, otherwise 0.
$A_{k}^{i}$ : a Boolean variable. It takes the value of 1 if virtual node i is mapped to physical node k, otherwise 0. In this paper, the virtual node embedding is considered without any geographical or location constraints. We assume that a virtual node can be embedded to any physical node in the substrate network which is a general situation in a datacenter network that provides virtual network as services.
$T_{f}^{i j}$ : a Boolean variable. It takes the value of 1 if virtual link (i, j) is mapped with the spectrum allocation starting from fth slot, otherwise 0.
Z_k: a Boolean variable. It takes the value of 1 if physical node k has been traversed in the embedding solution, otherwise 0.
Y_mn: a Boolean variable. It takes the value of 1 if physical link (m, n) has been traversed in the embedding solution, otherwise 0.

Objective

\begin{array}{l} M i n i m i z e : \sum_{i \in N^{v}} \sum_{k \in N^{s}} c_{k} A_{k}^{i} [Δ u_{k} (r_{i}) P_{s e r v e r} + (1 - α_{k}) P_{s e r v e r}^{i d l e}] \\ + \sum_{i \in N^{v}} \sum_{k \in N^{s}} c_{k} A_{k}^{i} [(\sum_{t \in N^{v}} r_{i t} + \sum_{t \in N^{v}} r_{t i}) P_{s l o t} + (1 - β_{k}) P_{B V T}^{i d l e}] \\ + \sum_{k \in N^{s}} c_{k} Z_{k} (1 - γ_{k}) P_{k}^{B V O X C} + \sum_{m n \in L^{s}} c_{m n} Y_{m n} (1 - δ_{m n}) P_{m n}^{E D F A} \end{array}

The objective is to minimize the electricity cost (unit time) to accommodate the arriving VN request. Power consumptions of computational devices and network devices are considered, which contain: servers, BVTs, BV-OXCs at nodes and EDFAs at links. Specifically, the first term of (3) is the electricity cost of servers, the second term is for BVT, the third is for BV-OXC, and the last is for EDFA.

Constraints

\sum_{k \in N^{s}} A_{k}^{i} = 1; \forall i \in N^{v}

\sum_{i \in N^{v}} A_{k}^{i} \leq 1; \forall k \in N^{s}

Equation (4) ensures that each virtual node is embedded to a physical node, and Eq. (5) ensures that a physical node can host at most one virtual node of the VN request.

\sum_{f \in F} \sum_{m \in N^{s}} M_{m k, f}^{i j} - \sum_{f \in F} \sum_{n \in N^{s}} M_{k n, f}^{i j} = A_{k}^{j} - A_{k}^{i}; \forall i j \in L^{v}, k \in N^{s}

Equation (6) derives the route of virtual link (i, j), where Eq. (6) has three cases according to the value of the right-hand side of the equation: 1) the right-hand side of equation equals to 0 (values of $A_{k}^{j}$ and $A_{k}^{i}$ are the same). According to Eq. (5), $A_{k}^{j}$ and $A_{k}^{i}$ only can be zero if they have the same value. Neither of end nodes of virtual link (i, j) is mapped to physical node k, then Eq. (6) ensures that for substrate node k, the number of incoming physical links traversed equals to the number of outgoing physical links traversed; 2) the right-hand side of equation equals to 1 ( $A_{k}^{j}$ equals to 1 and $A_{k}^{i}$ equals to 0). This means the end node j of virtual link (i, j) is mapped to physical node k, then at node k the number of incoming physical links traversed is larger than the number of outgoing physical links traversed by 1; 3) the right-hand side of equation equals to −1 ( $A_{k}^{j}$ equals to 0 and $A_{k}^{i}$ equals to 1), means the source node i of virtual link (i, j) is mapped to physical node k. Accordingly, at node k, the number of outgoing physical links traversed is larger than that of incoming physical links traversed by 1.

\sum_{i j \in L^{v}} \sum_{f \in F} (\sum_{m \in N^{s}} M_{m k, f}^{i j} + \sum_{n \in N^{s}} M_{k n, f}^{i j}) \leq V \cdot Z_{k}; \forall k \in N^{s}

\sum_{i j \in L^{v}} \sum_{f \in F} M_{m n, f}^{i j} \leq V \cdot Y_{m n}; \forall m n \in L^{s}

A physical node may be traversed multiple times in a VNE solution, but the BV-OXC energy consumption in a node should be count only once. Equation (7) derives the value of Z_k to indicate physical node k been traversed or not as ends or intermediate node. Equation (8) does similarly to assign values to Y_mn that to indicate a physical link been traversed or not.

\sum_{f \in F} T_{f}^{i j} = 1; \forall i j \in L^{v}

\sum_{m n \in L^{s}} M_{m n, f}^{i j} \geq T_{f}^{i j}; \forall i j \in L^{v}, f \in F

\sum_{m n \in L^{s}} M_{m n, f}^{i j} \leq V \cdot T_{f}^{i j}; \forall i j \in L^{v}, f \in F

Equation (9) ensures that only one spectrum allocation is applied by each virtual link mapping. Equations (10) and (11) ensure that $T_{f}^{i j}$ has values only when virtual link (i, j) is mapped to physical link(s) with spectrum allocation stating from fth slot.

\sum_{i \in N^{v}} r_{i} A_{k}^{i} \leq U_{k}; \forall k \in N^{s}

r_{i j} M_{m n, f}^{i j} \leq \sum_{t = f, f + 1, .., f + r_{i j} - 1} U_{m n, t}; \forall i j \in L^{v}, m n \in L^{s}, f \in F

\sum_{i j \in L^{v}} \sum_{t = f - r_{i j} + 1, f - r_{i j} + 2, .., f} M_{m n, t}^{i j} \leq U_{m n, f}; \forall m n \in L^{s}, f \in F

Equation (12) ensures that virtual nodes are mapped to physical nodes with enough available computation resource. Equation (13) ensures that enough frequency slots are allocated for each virtual link mapping. Specifically, if a physical link (m, n) with spectrum allocation starting from fth slot is occupied by virtual link (i, j) with bandwidth requirement r_ij, then the slots from f to f + r_ij − 1 must be available. This ensures the contiguity constraint of spectrum allocation. Equation (14) ensures that a slot can be occupied by at most one virtual link. Specifically, at most one spectrum allocation containing the fth slot of physical link (m, n) is valid. For example, if virtual link (i, j) with bandwidth requirement r_ij is mapped to physical link (m, n), the spectrum allocations containing fth slot may range from f − r_ij + 1 to f as the starting slot, so Eq. (14) ensures that at most one spectrum allocation takes fth slot if this slot is available.

3.2. ILP problem size

We calculate the numbers of variables and constraints to gain insights into the ILP problem. The number of variables is O(|L^v||L^s||F|) and the number of constraints is O(|L^v||L^s||F|). As network size grows, solving the ILP problem becomes prohibitively time-consuming.

3.3. An example for the ILP formulation

An example of an eight-node network (shown in Fig. 3(a)) that uses the ILP formulation to find an optimal solution is given below. The number on a line is the distance of link in kilometer, and the number in bracket near a node or a link is the electricity price at the node or the link. Six randomly generated VN requests are given as the input to the ILP. We used a commercial ILP solver, CPLEX [24], to solve the ILP problem.

Fig. 3 Network topologies.

Download Full Size | PDF

The embedding solution, power, energy and electricity cost are list in the Table 1 for the six sequentially arriving and leaving VN requests. The VN1 is embedded to nodes 5, 0, 3, 4 that are the first four low electricity price nodes, and it is noted that all six VN requests in the table will be embedded to these low electricity price nodes to cut electricity bill. We also find that virtual nodes and virtual links are embedded on the low electricity price devices that have been turned on already to reduce electricity cost of an arriving VN request. To achieve this, long paths may be used for virtual link embedding. For example, each of requests from VN1 to VN5 has a path that is more than two hops for a virtual link embedding to reduce electricity cost by reusing the turned-on servers. In addition to using low electricity price devices that have been turned on already, the optimal solution prefers to select the physical node that has more available spectrum resources on its adjacent physical links that have been turned on already, which can reduce electricity cost furthermore. For example, VN6 has physical nodes 0, 3 instead of physical nodes 4, 5 (all are turned on already) to host virtual nodes, because physical node 0 have two physical links turned on and physical node 5 has only one, and the former has more spectrum resources adjacent. If a virtual node is embedded to physical node 5, link (4→5) will be turned on.

Table 1. VNE solutions of six VN requests

View Table | View all tables in this article

In this example, it took tens of minutes for a PC with a 2.8 GHz CPU and 1024 MB RAM to solve the ILP problem. As this approach cannot scale to large networks, a scalable heuristic algorithm will be proposed. The following observations based on the above example will be considered in the development of the heuristic algorithm: 1) prefer devices with low electricity prices; 2) prefer the low electricity price devices that have been turned on already even with the cost of long paths; 3) embed virtual nodes to the physical nodes that have more spectrum resources in the adjacent physical links that are turned on already.

4. Heuristic algorithm

It is noted that the acceptance of request has been guaranteed in the above ILP formulation if there is a feasible solution. In our heuristic algorithm design, in addition to the energy consumption of the network, the blocking ratio of request is also considered because it is critical for network performance in dynamic traffic scenarios. To coordinate virtual link mapping and virtual node mapping, we embed a virtual link and two associated virtual end nodes simultaneously, and the VN request is embedded link-by-link. The details of the algorithm is shown in Algorithm 1.

Algorithm 1. Virtual network embedding

View Table | View all tables in this article

In Algorithm 1, before virtual links are embedded one-by-one, they are sorted to let the links associated with high-degree nodes embed first. This increases the acceptance possibility of VN request because the high degree virtual nodes are embedded to physical nodes adjacent more bandwidth resources (this will be detailed next). To embed a virtual link and two associated virtual end nodes, an auxiliary graph is built to convert the problem into a shortest path routing. After all the virtual links are embedded, the network resources of G^s is finally updated by G, where G accommodates the new VN request.

An auxiliary graph is built by Algorithm 2 to convert the problem of a virtual link embedding plus two associated virtual node embeddings to be a routing problem. A small example is shown in Fig. 4, where Fig. 4(a) is the substrate network and Fig. 4(b) is the auxiliary graph. From the original network to the auxiliary graph, physical nodes are duplicated, and physical links are also duplicated where an original link from V_m to V_n becomes a link from V_m to $V_{n}^{'}$ and a link from $V_{m}^{'}$ to $V_{n}^{'}$ . Then a shortest path routing algorithm is applied to find a path from i to j at line 6 in Algorithm 1 to accomplish both virtual node embedding and virtual link embedding. At line 8, if the path traverses the same physical node to embed both virtual nodes i and j (violate constraint Eq. (5)), a dummy link with higher cost between a virtual node and the common physical node is deleted from the auxiliary graph, and the shortest path routing algorithm executes again.

Algorithm 2. Auxiliary graph

View Table | View all tables in this article

Fig. 4 (a) The substrate network. (b) The proposed auxiliary graph with continue available slots from f to f + r_ij − 1.

Download Full Size | PDF

Link cost in the auxiliary graph decides the solutions of virtual node embedding and virtual link embedding. Equation (15) assigns virtual node embedding cost and virtual link embedding cost (same as the objective function of ILP formulation) to dummy link cost and physical link cost, respectively, and we modify it to be Eq. (16), where $α_{k}^{'}$ , $β_{k}^{'}$ , $γ_{k}^{'}$ , and $δ_{m n}^{'}$ indicate the ongoing status of server, BVT, BV-OXC and physical link during the embedding procedure, respectively. If a device is just turned on (the variable value is changed from 0 to 1) by a virtual link embedding of a VN request, no power consumption increment will be incurred if other virtual link embeddings of the same VN request also use this device (the variable value maintains 1).

P_{m n} = {\begin{matrix} (1 - δ_{m n}^{'}) c_{m n} P_{m n}^{E D F A} + (1 - γ_{n}^{'}) c_{n} P_{n}^{B V O X C}, & m \neq i, n \neq j \\ \begin{array}{l} Δ u_{n} (r_{i}) c_{n} P_{s e r v e r} + (\sum_{t \in N^{v}} r_{i t} + \sum_{t \in N^{v}} r_{t i}) c_{n} P_{s l o t} + (1 - α_{n}^{'}) c_{n} P_{s e r v e r}^{i d l e} \\ + (1 - β_{n}^{'}) c_{n} P_{B V T}^{i d l e} + (1 - γ_{n}^{'}) c_{n} P_{n}^{B V O X C}, \end{array} & m = i \\ \begin{array}{l} Δ u_{m} (r_{j}) c_{m} P_{s e r v e r} + (\sum_{t \in N^{v}} r_{j t} + \sum_{t \in N^{v}} r_{t j}) c_{m} P_{s l o t} + (1 - α_{m}^{'}) c_{m} P_{s e r v e r}^{i d l e} \\ + (1 - β_{m}^{'}) c_{m} P_{B V T}^{i d l e}, \end{array} & n = j \end{matrix}

c_{m n} = {\begin{matrix} P_{m n} + θ, & m \neq i, n \neq j \\ V (P_{i n} + R_{n}^{- 1}), & m = i \\ V (P_{m j} + R_{m}^{- 1}), & n = j \end{matrix}

In Eq. (16), the physical link cost is the electricity cost P_mn plus a small enough value θ, where θ is used to select a shortest path when there is no electricity cost. The dummy link cost is a summation of weighted electricity cost and a measurement of bandwidth resource. The bandwidth resources adjacent to node t is given as

R_{t} = \frac{Σ_{e \in E (t)} Σ_{f \in F} U_{s (e) d (e), f}}{| E (t) |}, t \in N^{s},

where E(t) is the set of adjacent on-status links of node t, and s(e) and d(e) are the source and destination of e respectively.

This strategy of link cost setting helps the embedding with the minimal electricity cost and reduces request blocking probability. Because a virtual node is hosted on a physical node that may be a source or destination of multiple lightpaths in the substrate network, virtual node embedding is treated preferentially over virtual link embedding. To achieve this, the dummy link cost is deliberately multiplied by the large number V, then the dummy link cost is significantly larger than the physical link cost, where shortest path algorithms prefer virtual node embedding first. Accordingly, a path with the minimal electricity cost is derived and a properly physical node that is with enough bandwidth resources is selected for virtual links that have the same virtual node, which increases the possibility of finding paths for virtual links. This design follows the observations from Table 1.

It is noted that because the virtual node embedding and virtual link embedding have been converted to be a shortest path routing problem, the link cost setting (Eq. (16)) of the auxiliary graph decides the solutions of the virtual node embedding and virtual link embedding. We can vary the link cost setting to achieve different performances of the algorithm. In Eq. (16), the dummy link cost consists of the electricity cost term (P_in or P_mj) and the resource term ( $R_{n}^{- 1}$ or $R_{m}^{- 1}$ ). We propose three different algorithms based on three different dummy link cost settings: 1) the Resource-power algorithm, where the dummy link cost is equal to $V (P_{i n} + R_{n}^{- 1})$ or $V (P_{m j} + R_{m}^{- 1})$ , 2) the Power algorithm, where the dummy link cost is equal to V · P_in or V · P_mj, and 3) the Resource algorithm, where the dummy link cost is equal to $V \cdot R_{n}^{- 1}$ or $V \cdot R_{m}^{- 1}$ . The complexity of Algorithm 2 is O(|N^s| + |L^s|), then the Algorithm 1 complexity is O(F|L^v||L^s||N^s|²), so the complexities of the three algorithms are polynomial-time.

5. Numerical results

VN request arrival is assumed to follow a Poisson process with rate λ and the holding time has a negative exponential distribution with a mean 1/μ. The traffic load of network is calculated as λ/μ (Erlang). VN requests are assumed to be connected directed graphs without loss of generality. The numbers of virtual nodes and virtual links of a VN request are uniformly distributed, and the computation and bandwidth requirements are also uniformly distributed. The average values of ten experiments are shown in the figures. Table 2 gives the simulation parameters used in the eight-node network and the Usnet network.

Table 2. Simulation parameter setting

View Table | View all tables in this article

Figure 5 is numerical result that has been obtained for the eight-node network shown in Fig. 3(a). In Fig. 5(a), acceptance ratios are compared. The ILP has the highest value, followed by the resource algorithm, the resource-power algorithm and the power algorithm. The best performance of the ILP is at the cost of a high computation complexity. It is noted that the resource-power algorithm has a very close acceptance ratio (0.41% lower averagely) to the resource algorithm, where the latter tries to improve the embedding success probability using devices either turn on or turn off. However, this marginal acceptance ratio gain is at the cost of a higher electricity cost (2.56% higher averagely) which is shown in Fig. 5(b). The power algorithm has the lowest electricity cost in Fig. 5(b), this is because the algorithm has the lowest acceptance ratio (5.5% lower than the resource-power algorithm averagely) and a small number of devices are turned on. Figures 5(c) and 5(d) compare the numbers of turned on devices (named on-link and on-server afterwards), where the ILP has both the lowest on-link number and the lowest on-server number that reduce electricity cost, and the resource-power algorithm obtains a trade-off between the resource algorithm and the power algorithm. It is noted that the resource algorithm has both the highest on-link value and the highest on-server value. In addition, Figs. 5(e) and 5(f) show the on-link utilizations and on-server utilizations. Usually, a high utilization means more work load on the device, which increases the resource sharing and decreases the overhead of the idle power. The ILP has the highest value both in on-link utilization and on-server utilization, then followed by the power algorithm, the resource-power algorithm and the resource algorithm. Although the power algorithm has a higher utilization than the resource-power algorithm, but its acceptance ratio is the lowest among all.

Fig. 5 Eight-node network with variable network loads.

Download Full Size | PDF

We also verify the proposed heuristic algorithms in USnet network that is with 24 nodes and 43 links shown in Fig. 3(b), and distances of links in kilometer are shown on the lines. A similar performance can be found and the resource-power algorithm obtains a trade-off between the resource algorithm and the power algorithm. In Fig. 6(a), the resource-power algorithm obtains an acceptance ratio lower than the resource algorithm by 2.5%, and higher than the power algorithm by 6.45%. In Fig. 6(b), the resource algorithm has a higher electricity cost than the resource-power algorithm by 25.12% for the acceptance ratio gain. The power algorithm has the lowest electricity cost, this is because a large portion of requests has been blocked, then much less network devices are needed. Figures 6(c)–6(f) also show this trade-off of the resource-power algorithm to the resource algorithm and the power algorithm, which is similar to the results of the eight-node network in Fig. 5.

Fig. 6 USnet network with variable network loads.

Download Full Size | PDF

6. Conclusion

We have considered the energy-aware VNE problem with dynamic traffic in flexi-grid networks. An ILP formulation has been provided to minimize the electricity cost of each arriving VN request, and a polynomial-time heuristic algorithm that keeps a reasonable acceptance ratio and maintains a low electricity cost has been proposed. Numerical results show that the heuristic algorithm performs closely to the ILP for a eight-node network, and obtain a good acceptance ratio and reasonable electricity cost in USnet network.

Funding

National Natural Science Foundation of China (NSFC) (61401070, 61303250, 61671130, 61701079); National Basic Research Program (China’s 973 Program) (2013CB329103).

References and links

1. N. M. K. Chowdhury and R. Boutaba, “Network virtualization: state of the art and research challenges,” IEEE Commun. Mag. 47(7), 20–26 (2009). [CrossRef]

2. A. Fischer, J. Botero, M. Beck, H. De Meer, and X. Hesselbach, “Virtual network embedding: a survey,” IEEE Commun. Surv. Tutorials 15(4), 1888–1906 (2013). [CrossRef]

3. J. Lu and J. Turner, “Efficient mapping of virtual networks onto a shared substrate,” Washington University, Technical Report WUCSE-2006-35 (2006).

4. I. Houidi, W. Louati, and D. Zeghlache, “A distributed virtual network mapping algorithm,” in Proc. IEEE International Conference on Communications, 5634–5640 (2008).

5. A. Jarray and A. Karmouch, “Decomposition approaches for virtual network embedding with one-shot node and link mapping,” IEEE/ACM Trans. Netw. 23(3), 1012–1025 (2015). [CrossRef]

6. M. Yu, Y. Yi, J. Rexford, and M. Chiang, “Rethinking virtual network embedding substrate support for path splitting and migration,” SIGCOMM Comput. Commun. Rev. 38(2), 17–29 (2008). [CrossRef]

7. J. Lischka and H. Karl, “A virtual network mapping algorithm based on subgraph isomorphism detection,” in Proc. SIGCOMM Workshop on Virtualized Infrastruct Systems & Architectures, 81–88 (2009).

8. M. Chowdhury, M. R. Rahman, and R. Boutaba, “Vineyard: Virtual network embedding algorithms with coordinated node and link mapping,” IEEE/ACM Trans. Netw. 20(1), 206–219 (2012). [CrossRef]

9. M. Jinno, B. Kozicki, H. Takara, A. Watanabe, Y. Sone, T. Tanaka, and A. Hirano, “Distance-adaptive spectrum resource allocation in spectrumsliced elastic optical path network,” IEEE Commun. Mag. 48(8), 138–145 (2010). [CrossRef]

10. G. Shen and M. Zukerman, “Spectrum-efficient and agile co-ofdm optical transport networks: architecture, design, and operation,” IEEE Commun. Mag. 50(5), 82–89 (2012). [CrossRef]

11. G. Zhang, M. D. Leenheer, A. Morea, and B. Mukherjee, “A survey on ofdm-based elastic core optical networking,” IEEE Commun. Surv. Tutorials 15(1), 65–87 (2013). [CrossRef]

12. L. Gong, W. Zhao, Y. Wen, and Z. Zhu, “Dynamic transparent virtual network embedding over elastic optical infrastructures,” in Proc. IEEE International Conference on Communications, 3466–3470 (2013).

13. L. Gong and Z. Zhu, “Virtual optical network embedding (VONE) over elastic optical networks,” J. Lightwave Technol. 32(3), 450–460 (2014). [CrossRef]

14. M. Mills, “The cloud begins with coal: Big data, big networks, big infrastructure, and big power - An Overview of the Electricity Used By the Global Digital Ecosystem,” National Mining Association and American Coalition for Clean Coal Electricity (2013).

15. United States Environmental Protection Agency, “Report to congress on server and data center energy efficiency public law,” 109–431 (2007). Available: http://www.energystar.gov/ia/partners/.

16. L. Nonde, T. E. H. El-Gorashi, and J. M. H. Elmirghani, “Energy efficient virtual network embedding for cloud networks,” J. Lightwave Technol. 33(9), 1828–1849 (2015). [CrossRef]

17. J. F. Botero, X. Hesselbach, M. Duelli, D. Schlosser, A. Fischer, and H. de Meer, “Energy efficient virtual network embedding,” IEEE Commun. Lett. 16(5), 756–759 (2012). [CrossRef]

18. S. Su, Z. Zhang, X. Cheng, Y. Wang, Y. Luo, and J. Wang, “Energy-aware virtual network embedding through consolidation,” in Proc. IEEE International Conference on Computer Communications Workshops, 127–132 (2012).

19. B. Wang, X. Chang, J. Liu, and J. K. Muppala, “Reducing power consumption in embedding virtual infrastructures,” in Proc. IEEE Global Communications Conference Workshops, 714–718 (2012).

20. V. Eramo, E. Miucci, and M. Ammar, “Study of reconfiguration cost and energy aware vne policies in cycle-stationary traffic scenarios,” IEEE J. Sel. Areas Commun. 34(5), 1281–1297 (2016). [CrossRef]

21. G. Shen and R. S. Tucker, “Energy-minimized design for IP over WDM networks,” IEEE/OSA J. Opt. Commun. Netw. 1(1), 176–186 (2009). [CrossRef]

22. J. L. Vizcano, Y. Ye, and I. T. Monroy, “Energy efficiency analysis for flexible-grid OFDM-based optical networks,” Computer Networks 56(10), 2400–2419 (2012). [CrossRef]

23. X. Fan, W. D. Weber, and L. A. Barroso, “Power provisioning for a warehouse-sized computer,” In Proc. ACM International Symposium on Computer Architecture, 13–23 (2007).

24. ILOG CPLEX, ILOG, Inc., Mountain View, CA[Online], Available: http://www.ilog.com/products/cplex/.

25. A. Deylamsalehi, Y. Cui, P. Afsharlar, and V. M. Vokkarane, “Minimizing electricity cost and emissions in optical data center networks,” IEEE/OSA J. Opt. Commun. Netw. 9(4), 257–274 (2017) [CrossRef]

26. Federal Energy Regulatory Commission, “OE energy markey snapshot - national data through May 2017,” Available: https://www.ferc.gov/market-oversight/mkt-snp-sht/2017/06-2017-snapshot-national.pdf

Event	VN: i→j(r_i,r_j,r_ij)	Solution: m→n[a]	Status	Power (W)	Energy (kWh)	Cost ($) × 10⁻2
VN1 Arrive	(0→1)(3,1,4) (0→3)(3,4,6) (1→0)(1,3,2) (2→1)(2,1,2) (3→0)(4,3,3) (3→1)(4,1,2)	(3→4)[0] (3→0)[0] (4→3)[0] (5→4)[0] (0→3)[0] (0→3→4)[4]	Server&BVT on: 0,3,4,5 BVOXC on: 0,3,4,5 Link on: 3→4 3→0 4→3 5→4, 0→3	4782	0	0
VN2 Arrive	(0→2)(2,1,2) (1→0)(2,2,4) (2→1)(1,2,3)	(4→3)[2] (0→3→4)[6] (3→0)[6]		5382	2.657	5.512
VN1 Leave			Server&BVT off: 5 BVOXC off:5 Link off: 5→4	3342	3.404	7.102
VN3 Arrive	(0→1)(4,4,3) (1→0)(4,4,3) (2→0)(3,4,5) (2→1)(3,4,5)	(3→0)[0] (0→3)[0] (4→3)[4] (4→3→0)[9]		4472	3.868	8.275
VN4 Arrive	(0→2)(3,4,6) → (1→0)(4,3,5) (2→0)(3,4,2) (3→0)(4,3,2)	(3→0)[9] (5→4→3)[14] (0→3)[](4→3)[0]	Server&BVT on: 5 BVOXC on:5 Link on:5→4	6252	5.111	11.452
VN3 Leave				5122	5.632	12.520
VN2 Leave			Link off: 3→4	4394	5.916	13.065
VN5 Arrive	(1→0)(1,3,4) (1→2)(1,4,6) (2→1)(4,1,3)	(5→4→3)[6] (5→4)[0] (4→5)[0]	Link on:4→5	5424	6.526	14.167
VN5 Leave			Link off:4→5	4394	7.581	16.195
VN6 Arrive	(0→1)(2,1,3) (1→0)(1,2,6)	(0→3)[0] (3→0)[0]		3854	7.947	16.857
VN4 Leave			Server&BVT off: 4,5 BVOXC off: 4,5 Link off: 4→3, 5→4	3237	8.627	17.996
VN6 Leave			Server&BVT off: 0,3 BVOXC off: 0,3 Link off: 3→0,0→3	0	8.759	19.878

	Input: An arriving VN request G^v(N^v, L^v), and current network G^s N^s, L^s.
	Output: An embedding solution S in the current network, and updated network resources.
	BEGIN:
1	E ← L^v, G ← G^s.
2	Descending sort E by the degree of virtual end node with the higher degree of a link.
	//Embed each virtual link
3	for e ∈ E do
	//s(e) and d(e) are the source and destination of e, respectively.
4	for f = 1 to F − r_s₍ _e ₎ _d ₍ _e ₎ + 1 do
5	Call Algorithm 2 to build an auxiliary graph G^e with available slots from f to f + r_s₍ _e ₎ _d ₍ _e ₎ – 1.
6	Find the shortest path P from s(e) to d(e) in G^e.
7	If a path cannot be found, Continue.
8	If s(e) and d(e) are embedded in a common physical node v in P, delete the higher cost dummy link of G^e between the two: link from s(e) to v and link from v′ to d(e), go to line 6.
9	S ← S + P, allocate network resources of G to P, Break.
	end
10	If a path for e cannot be found, Return.
	end
11	G^s ← G.
	END

	Input: A virtual link e, a spectrum band from a₁ to a₂, a modulation md and a partial embedding solution S.
	Output: An auxiliary graph G^e.
	BEGIN:
1	Add virtual nodes s(e), d(e) and all physical nodes into the empty graph G^e (each physical node n has a duplicated node n′).
	//Physical link constructions
2	for l ∈ L^s do
3	If slots from a₁ to a₂ are available, add a link from s(l) to d(l)′ and a link from s(l) ′ to d(l)′in G^e.
	end
	//Dummy link constructions
4	Check s(e) in S. If s(e) has been embedded already, connect s(e) and the physical node in G^e. Otherwise, connect s(e) to all physical nodes that are with enough computation resources and have not embedded any virtual node of this VN yet.
5	Check d(e) in S. If d(e) has been embedded already, connect the physical node and d(e) in G^e. Otherwise, connect all physical nodes that are with enough computation resources and have not embedded any virtual node of this VN yet to d(e).
6	Assign link costs according to Eq. (16).
	END

Parameter	Eight-node	Usnet
Arrival rate (λ)	5.5 – 8.5	8.0 – 12.0
Service rate (μ)	1	1
Node computation capacity	20	200
Link spectrum slots	20	100
Electricity price at node	unif(20,40)	According to references [25, 26]
Electricity price at link	unif(20,40)	According to references [25, 26]
Virtual nodes of a VN	unif(2,4)	unif(2,8)
Virtual links of a VN	unif(1,6)	unif(1,10)
Computation requirement	unif(1,4)	unif(10,40)
Spectrum requirement	unif(2,6)	unif(2,10)
VN requests in an experiment	10000	100000
Number of experiments	10	10
CPU	2.8 GHz	2.8 GHz
RAM	1024 MB	1024 MB

Event	VN: i→j(r_i,r_j,r_ij)	Solution: m→n[a]	Status	Power (W)	Energy (kWh)	Cost ($) × 10⁻2
VN1 Arrive	(0→1)(3,1,4) (0→3)(3,4,6) (1→0)(1,3,2) (2→1)(2,1,2) (3→0)(4,3,3) (3→1)(4,1,2)	(3→4)[0] (3→0)[0] (4→3)[0] (5→4)[0] (0→3)[0] (0→3→4)[4]	Server&BVT on: 0,3,4,5 BVOXC on: 0,3,4,5 Link on: 3→4 3→0 4→3 5→4, 0→3	4782	0	0
VN2 Arrive	(0→2)(2,1,2) (1→0)(2,2,4) (2→1)(1,2,3)	(4→3)[2] (0→3→4)[6] (3→0)[6]		5382	2.657	5.512
VN1 Leave			Server&BVT off: 5 BVOXC off:5 Link off: 5→4	3342	3.404	7.102
VN3 Arrive	(0→1)(4,4,3) (1→0)(4,4,3) (2→0)(3,4,5) (2→1)(3,4,5)	(3→0)[0] (0→3)[0] (4→3)[4] (4→3→0)[9]		4472	3.868	8.275
VN4 Arrive	(0→2)(3,4,6) → (1→0)(4,3,5) (2→0)(3,4,2) (3→0)(4,3,2)	(3→0)[9] (5→4→3)[14] (0→3)[](4→3)[0]	Server&BVT on: 5 BVOXC on:5 Link on:5→4	6252	5.111	11.452
VN3 Leave				5122	5.632	12.520
VN2 Leave			Link off: 3→4	4394	5.916	13.065
VN5 Arrive	(1→0)(1,3,4) (1→2)(1,4,6) (2→1)(4,1,3)	(5→4→3)[6] (5→4)[0] (4→5)[0]	Link on:4→5	5424	6.526	14.167
VN5 Leave			Link off:4→5	4394	7.581	16.195
VN6 Arrive	(0→1)(2,1,3) (1→0)(1,2,6)	(0→3)[0] (3→0)[0]		3854	7.947	16.857
VN4 Leave			Server&BVT off: 4,5 BVOXC off: 4,5 Link off: 4→3, 5→4	3237	8.627	17.996
VN6 Leave			Server&BVT off: 0,3 BVOXC off: 0,3 Link off: 3→0,0→3	0	8.759	19.878

Energy-aware virtual network embedding in flexi-grid networks

Abstract

1. Introduction

2. Energy consumption in flexi-grid optical networks

3. ILP based resource allocation

3.1. ILP formulation

Given

Variables

Objective

Constraints

3.2. ILP problem size

3.3. An example for the ILP formulation

4. Heuristic algorithm

5. Numerical results

6. Conclusion

Funding

References and links

Cited By

Figures (6)

Tables (4)

Equations (17)

Optics Express