Evolutionary optimization for energy efficient service provisioning in IT and optical network infrastructures

Markos P. Anastasopoulos; Anna Tzanakaki; Konstantinos Georgakilas

doi:10.1364/OE.19.00B496

1. Introduction

Over the past decade, Internet traffic has experienced tremendous growth, driven primarily by scientific and commercial applications generating a large amount of data. These data need to be transferred and processed by high-end computational resources such as computing clusters, storage servers and instruments. As high-performance applications require very high network capacities and specific IT resources, they cannot be intrinsically delivered by the current best effort Internet. In this context, optical networks offering high bandwidth, increased dynamicity, and flexibility through recent technology advancements are expected to play a key role in the Future Internet architecture. At the same time, it is estimated that Information and Communication Technology (ICT) accounts for 4% of the primary energy consumption worldwide [‎1]. The expansion of the Internet in size and complexity incurs increased energy consumption for both IT and network resources, thus attracting a lot of attention on energy efficient networking [‎2]. Designing, engineering and operating infrastructures comprising IT resources and optical networks in a power-aware manner seems to be instrumental for a more energy-efficient and hence sustainable ICT.

In addition, due to the increasing scalability and flexibility required by the dynamic service-oriented network and computing infrastructures and the need to implement online optimization mechanisms, conventional centralized service provisioning algorithms are unsuitable. This is because the requirement of these algorithms to allow a single entity to take decisions based on an overall network optimization criterion (e.g. minimize total power consumption for network and IT resources) is not possible to be satisfied. This imposes the requirement for an increased level of intelligence in the optical network, including the introduction of novel and disruptive approaches that support user-driven service provisioning of requests. This type of approach will allow users to provision their own services and optimize their performance selfishly, i.e. without considering their impact on the overall network. The suitable optimization tool to address this type of approach is game theory. In conventional game theory, the objective of a user (player) is to choose a strategy that maximizes its payoff, i.e. minimize the cost for the support of the requested service. The game is played by fully rational players that have complete and accurate knowledge of the details of the game. Rational players have knowledge of all possible strategies involved in the game and choose the one that maximizes their payoff. However, in modeling complex infrastructures including optical networks and IT resources, where the resulting network topology can also be highly dynamic, players most likely will not be fully rationale. Thus a suitable approach would be to let the users learn empirically how to select their own service provisioning strategies during the game according to the evolutionary game theory (EGT) [‎3].

This paper proposes for the first time to adaptively route information from an origin node to an IT server via the most energy efficient path employing EGT. Our EGT modeling results clearly indicate, that given sufficient time to learn the network status, the overall network optimization criterion reaches the optimum value achieved through traditional global optimization approaches such as integer linear programming (ILP). More specifically, the large information flows accommodated by the network consist of wavelengths –referred to as agents in EGT– each carrying a small portion of the load compared to the total network traffic load. The aim is to minimize the individual end-to-end energy consumption without considering the impact on the overall network performance. The service provisioning strategy of every agent is continuously updated by sampling all the alternative paths connecting origin nodes to potential IT servers, taking advantage of the information obtained by the infrastructure.

2. Power consumption model

The Energy model adopted in this paper assumes that the total power is consumed due to the operation of the infrastructure incorporating integrated optical network and IT resources. The overall network power consumption model is based on the power dissipating (active) elements of the network and the transmission line related elements [‎4]. These elements consume a certain amount of power, which consists of two parts, i.e., traffic independent and traffic dependent power that is proportional to the number of wavelengths per link [‎5]. Assuming that w wavelengths are assigned per fiber, the aggregate power consumption for optical link i is

E_{i}^{(N)} (w) = E_{i}^{A m p} + E_{i}^{T R, S W} w

where

E_{i}^{A m p}

is the power consumed due to amplification and

E_{i}^{T R, S W}

the power due to electrical to optical and optical to electrical conversion as well as switching across link i. Both parameters are increasing functions of the length of the optical link i.

The physical IT infrastructures in this paper are considered to be data centers i.e. facilities used to house computer systems and associated components. Data centers are primarily used to process or store data. A large part of the energy consumption of a data center resides in the IT equipment and the cooling [2], making infrastructure equipment (especially cooling) an important factor when trying to reduce the energy consumption in data centers. The power consumption model adopted in this paper mainly concentrates on the power consumption associated with the CPU load of IT resources and is described via the following equation

E_{s}^{(I T)} (w) = P_{s}^{I d l e} + P_{s}^{b u s y} w

where

E_{s}^{(I T)}

denotes the energy consumption for processing w wavelengths in IT server s and

P_{s}^{i d l e}

,

P_{s}^{b u s y}

are parameters describing the energy consumption of IT server s at idle state and per wavelength, respectively [2].

3. Problem formulation

In the problem under consideration, there is a set of demands d (d = 1,2,…,D) to be served by a set of IT servers s (s = 1, 2, … S). The granularity of demands is the wavelength and is formed by aggregating traffic generated by several users. It is also assumed that each demand can be assigned to one server only. The IT locations (demand destinations) at which the services will be handled, are not specified and are of no importance to the services themselves. Therefore, the demand destinations will be identified through the optimization performed by two different algorithmic approaches: a centralized and a distributed. The analysis is based on the NSFNET topology depicted in Fig. 1 comprising of a set of origin nodes generating demands destined to three IT servers. Furthermore, we assume a single fiber per link, 80 wavelengths per fiber, and wavelength channels of 10Gb/s each. It is also assumed that each IT server can process up to 2Tb/s and its power consumption ranges from 6.6 to 13.2KW, under idle and full load, respectively.

Fig. 1 NSFNET topology with integrated IT elements.

Download Full Size | PDF

3.1 Centralized algorithm

In centralized algorithms, decisions are taken by a single controller based on an overall optimization criterion. Usually, these types of algorithms are formulated using ILP, Mixed ILP and Non-Linear Programming techniques. For example, considering the reference topology presented in Fig. 1, the energy-minimized service provisioning problem may be written using ILP formulation as follows:

\min \sum_{s} E_{s}^{(I T)} + \sum_{ℓ} E_{ℓ}^{(N)}

subject to

\sum_{s} \sum_{c} a_{d s} w_{d p} = h_{d}, d = 1, 2, ..., D

\sum_{d} \sum_{s} \sum_{p} δ_{ℓ d p s} w_{d p} \leq y_{ℓ}, ℓ = 1, 2, ..., L

\sum_{d} \sum_{p} a_{d s} c_{d s} (w_{d p}) \leq ω_{s}, s = 1, 2, ..., S

where

p, p = 1, 2, ..., P_{d s}

is the candidate path list required to support demand d at server s and

w_{d p s}

the non-negative number of wavelengths allocated to path p. Furthermore,

a_{d s}

is a binary variable indicating whether demand d is assigned to server s or not and it equals 1, if and only if demand d is processed on server s, and

δ_{ℓ d p s}

binary variable taking value equal to 1 if link

ℓ

(

ℓ

= 1,2,...,L) of the NSFNET belongs to path p realizing demand d at server s. Finally,

c_{d s} (w_{d p})

and

ω_{s}

are parameters specifying computational requirements for demand d on server s and processing capabilities of server s, respectively. Note that Eqs. (3.2), (3.3) and (3.4) are known as demand, link and processing capacity constraints, respectively.

3.2. Dynamic and distributed adaptive algorithm

Let us consider again the scenario where traffic demands at origin nodes have to be served by IT servers. In contrast to the previously described model where routing decisions are taken by a centralized authority, in this approach users try to optimize their own performance selfishly. Since the available bandwidth in optical networks is extremely large, each user’s traffic demands correspond to a small portion of the total volume of traffic that is transferred over the network. In this context, it can be assumed that traffic (measured in wavelengths) is transferred by a large number of users with bounded rationality who learn about the network status empirically. To address this scenario, a suitable optimization framework that can be used to support energy-minimized service provisioning and the integration of Network and IT resources in a common infrastructure can be found in EGT [3].

In the proposed service provisioning scheme, initially, all users select randomly one of the possible IT servers. As every user wishes to minimize its own overall energy consumption, it reconsiders periodically its routing strategy by randomly sampling different IT servers and comparing the corresponding energy consumption with its own. When a lower value is found, the user switches to a new IT server; otherwise, the current routing strategy remains unchanged. The corresponding evolution of population shares adopting a specific routing strategy follows the well known replicator dynamics model [6,7]. One of the basic elements of replicator dynamics is the rate at which users revise their strategy. This rate depends on several factors including the performance of the subscribers’ current strategy, population state, network configuration etc.

For the reference topology presented in Fig. 1, it is assumed that the information generated at the source nodes must be transmitted to one of the available IT servers. The set of all available paths (strategies) connecting the source nodes and the IT servers is denoted by $P = \times_{d \in D} P_{d}$ where $P_{d}$ is the set of paths realizing demand d at one of the IT servers in the network. The network traffic is accommodated by $h_{d} = \sum_{p} w_{d p}$ wavelengths. The normalized number of wavelengths $x_{d p} = w_{d p} / h_{d}$ programmed to use each path is collected for each demand d in the vector $x_{d} = [x_{d 1}, x_{d 2}, ..., x_{d p}, ..., x_{d P}]$ . The associated population state is defined as the vector $x = [x_{1}, x_{2}, ..., x_{d}, ..., x_{D}]$ . Then, the expected payoff for demand d of using pure strategy $p_{d} \in P_{d}$ given that the population is in state $x$ is $u_{d} (p_{d}, x)$ and the population average payoff, that is the payoff of an agent drawn randomly from the population is $u_{d} (x, x) = \sum_{d} x_{d p} u_{d} (p_{d}, x)$ .The objective is for each demand to find vectors $x_{d}$ that route information via the paths $p_{d} \in P_{d}$ to the IT servers with the minimum end-to-end energy consumption under the traffic conservation, network capacity and IT server processing constraints. Since in the current problem formulation energy efficiency is the main objective, $u_{d}$ is related to the energy cost for using network or IT resources. Note that, $u_{d}$ is readily obtained from Eqs. (1) and (2) and, therefore, it is a linear function of x. The evolution of population shares is described via the multi-population replicator equations [6]

{\dot{x}}_{d p} = [u_{d} (p_{d}, x) - \sum_{d} x_{d p} u_{d} (p_{d}, x)] x_{d p}, p = 1, 2, ..., P_{d}, d = 1, 2, ..., D

under the following constraints

\sum_{p} x_{d p} = 1 a n d x_{d p} \geq 0, d = 1, 2, ..., D

In the simple case that two demands $i, j \in D$ are realized through the set of paths $p_{i}, p_{j} \in P_{d}$ Eq. (4) is downsized to the standard two-population replicator equations

{\dot{x}}_{i p_{i}} = [\sum_{p_{j}} u_{i} (p_{i}, p_{j}) x_{j p_{j}} - \sum_{p_{i}} \sum_{p_{j}} x_{i p_{i}} u_{i} (p_{i}, p_{j}) x_{j p_{j}}] x_{i p_{i}}, i, j \in D, p_{i} \in P_{i}, p_{j} \in P_{j},

u_{i} (p_{i}, p_{j})

is the energy cost for the population

x_{i p_{i}}

derived when population

x_{j p_{j}}

is transferred to an IT server using path

p_{j}

. Parameters

u_{i} (p_{i}, p_{j})

are defined on the basis that the fixed operational costs (

E_{i}^{A m p}

,

P_{s}^{I d l e}

) of the integrated network and IT infrastructures are shared equally among populations that exploit the same resources, while variable operating costs (energy consumption of network and IT resources per wavelength) are charged on a pay as you go basis. For example, the energy cost

u_{1} (p_{1}, p_{2})

for a scenario where paths

p_{1} = {1, 4}

,

p_{2} = {2, 4}

are solely used by the population shares

x_{1 p_{1}}

,

x_{2 p_{2}}

originating from sources S1, S2 and destined to IT server 1 is given by

u_{1} (p_{1}, p_{2}) = - (E_{1}^{A m p} + E_{2}^{A m p} + (E_{4}^{A m p} + P_{1}^{Ι d l e}) \frac{x_{1 p_{1}}}{x_{1 p_{1}} + x_{2 p_{2}}} + E_{1}^{T R, S W} + E_{2}^{T R, S W} + P_{1}^{b u s y})

Finally, the stability of the proposed adaptive energy-minimized service provisioning algorithm is examined. To achieve this, initially the critical points of the system are determined by setting Eq. (4) equal to zero and then solving the resulting system of algebraic equations. The stability of the critical points is then examined using the Lyapunov’s indirect method. The set of critical points of the system are $x^{0} = [x_{1}^{0}, x_{2}^{0}, ..., x_{D}^{0}]$ with $x_{d}^{0} = [(1, 0, ..., 0), (0, 1, ..., 0), ...., (0, 0, ..., 1), (x_{d 1}^{*}, x_{d 2}^{*}, ..., x_{d p}^{*})]$ where $(x_{d 1}^{*}, x_{d 2}^{*}, ..., x_{d p}^{*})$ is given by the solution of the following equation

u_{d} (p_{d}, x^{*}) = \sum_{d} x_{d p}^{*} u_{d} (p_{d}, x^{*}) .

The stability of the nonlinear system at $x_{}^{0}$ is studied after linearizing it at zero employing the transformation $x' = x - x_{}^{0}$ and then analyzing the corresponding eigenvalues, $λ_{i}$ , of the matrix $F$ with its (i,j) element, namely $F_{i j}$ , given by $F_{i j} = \partial x_{i p}^{'} / \partial x_{j p}$ at $x' = 0$ . It is proved that if the total demands do not exceed the capacity of an IT server, then the routing strategy that forwards all demands through the shortest paths to a single IT server is evolutionary stable. Otherwise, if the capacity of the closest to the sources IT server cannot accommodate all the traffic, a part of the demands will be served by the closest to the sources IT server, while the rest will be served by the second, third, etc next closer IT server.

4. Numerical results

To investigate the energy efficiency of the proposed algorithm, the topology presented in Fig. 1 is considered. Figure 2 illustrates the total power consumption under two traffic scenarios of the infrastructure (optical network and IT resources) when applying the conventional centralized ILP approach optimizing for energy or distance between sources and IT servers and the proposed evolutionary approach. In the traffic scenario 1, it is assumed that source nodes S1-S5 generate traffic demands equal to 40 wavelengths, while in scenario 2 the demand of S5 is increased to 60 wavelengths. Due to the global knowledge in the centralized approach, the decisions are made instantly at time 0 and exhibit globally optimum performance. On the other hand, distributed adaptive algorithms learn from the environment and eventually achieve convergence to the optimal solution. In scenario 1, it is observed that the problem has a unique stability point that is all information to be routed to the IT server 1 (1 IT), while IT servers 2,3 are switched off. In the scenario 2, traffic is routed to IT servers 1, 2 (2 IT).

Fig. 2 Total power consumption for two traffic scenarios.

Download Full Size | PDF

Figure 3a depicts the evolution of population shares in IT servers and the speed of convergence for traffic scenario 1. It is observed that after 35 sampling periods all traffic is served by a single IT server. In Fig. 3b, it is also observed that the population share in IT 2 originating from S3 tends to increase its share during the first few path samplings, since its payoff is higher than average. However, in the long term it reduces to zero. Hence, given that sufficient time is spent on learning the network status, distributed algorithms provide efficient solutions for service provisioning in integrated optical network and IT infrastructures.

Fig. 3 a) Evolution of population share in the IT server 1 from all sources b) Evolution of population share from S3 to the three IT servers.

Download Full Size | PDF

5. Conclusion

The paper studied the problem of energy efficient service provisioning in converged network and IT infrastructures. A novel adaptive routing scheme was proposed based on evolutionary game theory and compared with typical ILP based centralized approaches. Due to the global knowledge in the centralized algorithms, the decisions are made instantly at time 0 and exhibit globally optimum performance. On the other hand, distributed adaptive algorithms learn from the environment and eventually achieve convergence to the optimal solution. We proved that given that sufficient time is spent on learning the network status, distributed evolutionary optimization algorithms can provide efficient and stable solutions to this problem.

Acknowledgments

This work was carried out with the support of the GEYSERS (FP7-ICT-248657) project funded by the European Commission through the 7th ICT Framework Program.

References and links

1. M. Pickavet, W. Vereecken, S. Demeyer, P. Audenaert, B. Vermeulen, C. Develder, D. Colle, B. Dhoedt and P. Demeester, “Worldwide energy needs for ICT: The rise of power-aware networking,” in IEEE ANTS2008 (2008), 1–3.

2. A. Tzanakaki, M. Anastasopoulos, K. Georgakilas, J. Buysse, M. De Leenheer, C. Develder, S. Peng, R. Nejabati, E. Escalona, D. Simeonidou, N. Ciulli, G. Landi, M. Brogle, A. Manfredi, E. Lopez, J. F. Riera, J. A. Garcia-Espin, P. Donadio, G. Parladori, and J. Jimenez, “Energy Efficiency in integrated IT and Optical Network Infrastructures: The GEYSERS approach,” in IEEE INFOCOM2011, Workshop Green Commun. and Networking(2011),343–348.

3. M. Anastasopoulos, P. Arapoglou, R. Kannan, and P. Cottis, “Adaptive Routing Strategies in IEEE 802.16 Multi-Hop Wireless Backhaul Networks Based On Evolutionary Game Theory,” IEEE J. Sel. Areas Comm. 26(7), 1218–1225 (2008). [CrossRef]

4. A. Tzanakaki, K. Katrinis, T. Politi, A. Stavdas, M. Pickavet, P. Van Daele, D. Simeonidou, M. O'Mahony, S. Aleksić, L. Wosinska, and P. Monti, “Dimensioning the future Pan-European optical network with energy efficiency considerations,” J. Opt. Commun. Netw. 3(4), 272–280 (2011). [CrossRef]

5. A. Jirattigalachote, C. Cavdar, P. Monti, L. Wosinska, and A. Tzanakaki, “Dynamic provisioning strategies for energy efficient WDM networks with dedicated path protection,” Opt. Switching Networking 8(3), 201–213 (2011). [CrossRef]

6. M. Anastasopoulos, D. Petraki, R. Kannan, and A. Vasilakos, “TCP Throughput Adaptation in WiMax Networks Using Replicator Dynamics,” IEEE Trans. Syst. Man Cybern. B Cybern. 40(3), 647–655 (2010). [CrossRef]

7. A. Pantoja and N. Quijano, “A Population Dynamics Approach for the Dispatch of Distributed Generators,” IEEE Trans. Ind. Electron. 58(10), 4559–4567 (2011). [CrossRef]

Evolutionary optimization for energy efficient service provisioning in IT and optical network infrastructures

Abstract

1. Introduction

2. Power consumption model

3. Problem formulation

3.1 Centralized algorithm

3.2. Dynamic and distributed adaptive algorithm

4. Numerical results

5. Conclusion

Acknowledgments

References and links

Cited By

Figures (3)

Equations (11)

Optics Express