Energy-efficient anycast scheduling and resource allocation in optical grids

Abstract

In recent years, optical grid networks has been used as an ideal infrastructure to support high-performance computing environment, data intensive applications and interconnection of data centers. Due to rapid increase in the high-bandwidth applications, the power consumption of communications equipment for such networks has been increasing steadily over the past decade. Therefore, energy efficient routing schemes and traffic models can be developed to reduce the energy consumption. In many applications it is possible to select the destination node from a set of possible destinations, which have the required computing/storage resources. This is known as anycasting compared to unicasting where there is only one destination for each communication. In this paper we adopt the sliding scheduled traffic model, where setup and tear down times may vary within larger window frame. We propose a novel problem that exploits knowledge of demand holding times using anycasting model. We show how the flexibility of anycast routing can lead to additional energy saving. The problem was formulated as an integer linear program to optimally schedule demands (in time) and route them in order to minimize overall network energy consumption. The problem of energy consumption is addressed by switching off idle network components in low utilization periods. We analyze the performance of the proposed approach for anycast and unicast routing models. Our simulation results demonstrate that the proposed approach can lead to significant reductions in energy consumption, compared to traditional routing schemes.

1 Introduction

Grid computing refers to high performance computing resource sharing using optical backbone networks to support data-intensive applications. Grid computing provides a solution to better utilize these resources, for applications where the physical location of the resource is not important. Grids provide a form of distributed computing (Tafani et al. 2012) whereby a super virtual computer is composed of many networked loosely coupled computers, acting together to perform large tasks (Mishra et al. 2017). For the grid computing the basic requirement is high speed with low delay time. Optical communications technology with wavelength division multiplexing (WDM) networks fulfills the requirements for optical grid computing as it can carry large amount of data with reliability. Recent studies have shown that the energy consumption can become the bottleneck for the high speed data communication (Shen and Tucker 2009; Gupta and Singh 2003; Kukreja et al. 2017) in today’s networks. Efficient routing schemes and resource allocation both in optical and electrical domain can be used to help mitigate this problem (Orgerie et al. 2014). A transparent IP-over-WDM network can be utilized to allow traffic to optically bypass the electronic components, e.g. IP routers and switches, which typically consumes more power than the corresponding optical equipment. WDM networks uses the technology of combining multiple optical signals on the same fiber in order to effectively utilize the tremendous bandwidth available in a single optical fiber (Bandyopadhyay 2007). We consider energy-aware routing and wavelength assignment (RWA) problem (Nafarieh et al. 2015). RWA involves finding a route and assigning a channel or wavelength for each request for communication.

In recent years various research works have been published in the field of energy efficient WDM networks. A number of different approaches have been proposed including switching off or slowing down unused network elements (Habib et al. 2013), reducing electrical–optical–electrical (E–O–E) conversions (Tafani et al. 2012), putting selected network components in sleep mode (Coiro et al. 2011), and using intelligent traffic grooming techniques (Chabarek et al. 2008; Yetginer and Rouskas 2009). In many applications the physical location of the server or other network resources remains hidden from the user as it is not important. In this scenario, it is possible to select the best destination from the set of possible destinations to execute a job. This is known as anycast routing (Develder et al. 2009). This allows the routing algorithms the flexibility of choosing a suitable processing (destination) node for a given task, such that network resources can be utilized as efficiently as possible. There are mainly three different demand allocations models exist for WDM optical networks. In static traffic model, the set of demands are fixed and known in advance. For dynamic traffic, the start time and the end time the demands are known in advance, they are generated based on certain distributions. Scheduled traffic model is predictable and periodic in nature. In scheduled traffic demands the set up time and the tear down time for the demand is known in advance. The scheduled traffic model is further divided into two different models, known as fixed window traffic model and sliding scheduled traffic model. A number of recent papers have shown how anycast routing can be used for minimizing the overall energy consumption in optical networks (Chen and Jaekel 2013; Buysse et al. 2013; Chen et al. 2014). However, these papers mostly deal with the static (Zhu and Mukherjee 2002; Kwangil and Shayman 2005) or dynamic (Zhu et al. 2002; Yao and Ramamurthy 2005) traffic models. Although energy aware routing for WDM networks has received significant attention in recent years, the idea of utilizing the anycast concept for energy minimization (Habib et al. 2013; Chen and Jaekel 2013) has been less well studied.

Several researches show that routing schemes can affect the overall energy consumption of a network (Habib et al. 2013; Chen et al. 2014). In this paper, we address the problem of energy efficient routing of traffic demands, under the sliding scheduled traffic model (STM) (Andrei et al. 2009). This paper extends our work in (Rami et al. 2016) which reported some preliminary findings for the sliding scheduled traffic using anycasting model. Rather than using the traditional unicast routing, our proposed approach uses the anycast routing principle to select the most suitable destination for a given demand. Furthermore, we present a novel approach that jointly routes and schedules demands in time. We have developed a new integer linear program (ILP) formulation to optimally solve this integrated routing and scheduling problem. We consider power consumption at both network nodes (e.g. in IP routers, optical switches) and along fiber links. In order to evaluate the performance of our ILP, we compare the solutions generated by the ILP with the solutions obtained using the unicast principle, as well as anycast routing with fixed start and end times for each demand. To the best of our knowledge, the proposed work is the first to consider energy-aware RWA for the sliding scheduled traffic model. Thus we consider not only routing but also scheduling of demands in time in an integrated manner. Previous work in this area typically focuses on the routing component, along with wavelength assignment. We have given a comprehensive mathematical formulation to solved the design problem. We have also performed simulations on well-known topologies to evaluate the performance of the proposed approach. Our experimental results show that the proposed formulation outperformed other routing schemes in terms of reduced energy consumption. We note that the solution times are higher for the proposed approach as the ILP formulation has to decide the best start time for each request and the destination nodes compared to the fixed window model and the unicast principle, respectively.

The rest of the paper is organized as follows: in Sect. 2 we present the related work in the literature. In Sect. 3 we formulate our energy-aware scheduling and routing problem. We discuss our simulation results in Sect. 4 and conclude this study in Sect. 5.

2 Related work

The tremendous growth in high-bandwidth applications in the past decade has led to a corresponding increase in power consumption in today’s core/transport networks. It has been predicted that “energy consumption rather than the cost of the component equipment may eventually become the barrier to continued growth” (Shen and Tucker 2009) for today’s core/transport networks. Consequently, energy efficiency of core wavelength division multiplexing (WDM) networks has received significant research attention in the last few years (Buysse et al. 2011; Coiro et al. 2011). Energy-aware RWA approaches in WDM networks has received considerable research attention in the last 10 years (Henriques et al. 2014). Both heuristics and optimal formulations using anycast routing has been considered in Buysse et al. (2011); Chen and Jaekel (2013); Chen et al. (2014). The goal is to reduce both the static and dynamic (load dependent) portions of power consumption as much as possible, although static power consumption typically dominates for most network components (Chen et al. 2014).

In Habib et al. (2013) the authors propose exploiting anycast principle to reduce energy in optical networks and server systems. Their proposed approach evaluates power consumption on networks with wavelength conversion and without conversion. The proposed approach intelligently select the destination through anycast routing by switching off unused network elements. The authors compare their proposed anycast routing scheme with unicast routing; further they compare the results for wavelength conversion and wavelength continuous networks. The authors state that the power consumption in fiber links accounts consumes 30%, while OXC and other network node consumes 70% of total power consumption. The results show 23% less power consumption for anycast and 28% less power consumption for unicast with energy aware routing compared to shortest path routing.

In Buysse et al. (2011), the authors propose ILP formulations and heuristic for their proposed scheme to reduce power consumption by selective switching off of optical links. The authors used network model of a transparent circuit switched optical network with WDM transmissions with no wavelength conversion. The results show that the proposed scheme saves between 28 and 33% energy on an average by mediating the results on daily traffic variability and also the power consumption reduces with the increase in number of wavelengths.

The study (Coiro et al. 2011) surveyed the schemes proposed in the literature like green routing, energy efficient packet forwarding, energy efficient design and selective turn off for access, metro and backbone networks. In this study, the connection requests follow the anycast paradigm and energy saving is done by switching off network nodes. The authors count the energy consumption on the basis of erbium doped fiber amplifiers (EDFAs), energy consumption due to wavelength utilization and due to ON state of a node. In this paper, the authors introduce a model where each node stores two predetermined thresholds that trigger the node switching between sleep and active modes, depending on traffic load. The authors claim that their proposed model reduces energy consumption of a network by 6% at all traffic loads. The results demonstrate that the average end to end network delay is maximum for sleep mode scheme compared to energy unaware and adaptive sleep mode scheme. One drawback of this model is it can drop lightpath requests due to isolated nodes.

In Tafani et al. (2012), the authors propose a new approach to energy aware resource allocation for optical grids with using anycast principle. They present an ILP formulations for minimizing the energy consumption of a set of lightpath demands using anycasting model and a fast two stage ILP capable of generating near optimal results for larger networks. In this paper the authors consider an IP-overWDM network architecture, where each node consists of OXC connected to an IP router. In the proposed model the traffic can be switched directly in optical domain if routing is not required in electrical domain, otherwise it is sent to associated router via transponders. The model considers traffic granularity at lightpath level and does not consider sub wavelength demands grooming. The authors take into account the power consumption at IP routers and optical switches. The authors claim that their proposed scheme performs 35% better with 40 lightpath demands and 15% better with 120 demands. The energy savings decrease with increase in number of demands because of less availability of nodes to switch off with higher number of demands. They also claim that the optical switch requires less energy compared to IP routers and optical amplifiers in NSFNET and COST-239 topology. All the above papers consider either the static traffic model, where the traffic demands are set up on a permanent or semi-permanent basis, or the dynamic traffic model, where connection requests arrive randomly and are allocated on-demand as they arrive.

Finally, in Chen and Jaekel (2013) the authors address the energy-aware anycast routing problem for the fixed window scheduled traffic model (Kuri et al. 2003), using anycast principle. Each scheduled lightpath demand has a specified source node, bandwidth requirement (number of required lightpaths), starting time and ending time. The authors consider power consumption at IP routers, optical switches and pre, post and inline amplifiers. The authors compared their results with energy aware unicast, energy unaware anycast and energy aware but holding time unaware anycast routing approaches. The proposed approach shows reduction in energy of 21–27% compared to next best technique, which was energy aware unicast routing. Their approach considers applications with periodic bandwidth demands and demand holding time to reduce energy consumption.

Our approach differs from the existing works in that we consider the sliding scheduled traffic model (Andrei et al. 2009; Jaekel and Chen 2009) and investigate if adding some flexibility in terms of the demand start and end times can help to further reduce the overall network energy consumption.

3 Energy-efficient routing and scheduling of SLDs

3.1 Network model

Our formulation takes as input a physical topology G[N, E]; here N is the set of nodes and E is the set of fiber links, where each fiber can accommodate a set of K WDM channels. We are also given a set P of scheduled lightpath demands (SLDs) and the entire time duration is divided into $m_{max}$ intervals, numbered $m = 1,2,3..m_{max}$. Each demand $p \in P$ is specified as a tuple ($s_p$, $D_p$, $\alpha _p$, $\omega _p,$ $\tau _p$). A demand p has a specified duration $\tau _p$, and can be scheduled any time within a larger window ($\alpha _p$, $\omega _p$), such that the demand can only start after $\alpha _p$, and must be completed before $\omega _p$. Clearly $(\omega _p - \alpha _p + 1) \ge \tau _p$. Here $s_p$ is the source node for the SLD and $D_p$ is a set of potential destination nodes, from which the routing algorithm will choose the most suitable one. We note that our ILP formulation is solved offline and the duration of the intervals as well as each lightpath demand is quite long (of the order on minutes) and lightpaths are used for high-bandwidth bulk data transfer. This means that network updates will be relatively infrequent. Also, the amount of information needed to represent the network state at a given time is quite small compared to the data carried on a single lightpath. We assume separate control channels are available for exchanging this information and therefore bandwidth and power costs for such infrequent internal communication are not considered in the problem formulation.

The total power consumption of an active IP router ($P_{IP}$) and an optical switch ($P_{SW}$) are shown in (1) and (2) respectively.

$$\begin{aligned} P_{IP} = C^s_{IP} + C^d_{IP} \cdot t_{IP} \end{aligned}$$

(1)

$$\begin{aligned} P_{SW} = C^s_{SW} + C^d_{SW} \cdot t_{\lambda } \end{aligned}$$

(2)

In both cases, the first term denotes the static component of the power consumption for simply turning the device ON or making it active. The second term is the load dependent portion of the power consumption and increases with the amount of traffic $t_{IP}$ ($t_{\lambda }$) flowing through the IP router (optical switch). Finally, $C_{link}^e$, the power consumption of an active fiber link e is shown in (3). The value of $C_{link}^e$ is determined by the number of inline amplifiers plus the pre and post amplifiers for each link, and can be calculated beforehand. Table 1 shows the power consumption of different network devices considered in this paper, based on Musumeci et al. (2012).

$$\begin{aligned} C_{link}^e = C_{pre} + n_e\cdot C_{ILA} + C_{post} \end{aligned}$$

(3)

Table 1 Power consumption of different network devices

Our approach to addresses the energy minimization problem by developing energy efficient routing schemes. We consider a set of sliding scheduled lightpath demands or SLDs (P) originating from different sources, and select the route and destination for each demand in such a way that the overall energy consumption is minimized. It has been shown that the power requirement of adding extra traffic on a node or link is significantly lower compared to turning on additional network components (Tafani et al. 2012). Therefore, out objective is to select a destination node, routing path and start time for each demand, such that the components required establishing the lightpath can be shared by other lightpaths as much as possible. We present integer linear program (ILP) formulation that takes into consideration the energy at network nodes (including electronic routing and optical switching) and along the fibers to achieve this objective. Existing work on energy efficient RWA schemes focused on static, dynamic or fixed window demand allocation (Chen and Jaekel 2013; Chen et al. 2014). Unlike the previous work, we address the problem of sliding scheduled demand allocation based on anycast principle for WDM optical networks.

3.2 ILP formulation

The following variables are defined for our ILP:

Binary variables

• $r_{i,m} = 1$, if IP router at node i is being used during interval m.

• $s_{i,m} = 1$, if optical switch at node i is being used during interval m.

• $t_{e,m} = 1$, if link e is being used during interval m.

• $\omega _{k,p} = 1$, if lightpath p uses channel k.

• $y_{p,i} = 1$, if lightpath p uses node i.

• $x_{e,p} = 1$, if lightpath p uses link e.

• $d_{p,i} = 1$, if node i is selected as destination node for lightpath p.

• $a_{p,m} = 1$, if lightpath p is active during interval m.

• $st_{p,m} = 1$, if m is the starting interval for lightpath p.

Continuous variables

• $r_{i,m}^p = 1$, if lightpath p uses IP router at node i during interval m.

• $s_{i,m}^p = 1$, if lightpath p uses optical switch at node i during interval m.

• $t_{e,m}^p = 1$, if link e is being used by lightpath p during interval m.

• $a_{k,e}^p= 1$, if lightpath p uses channel k on link e.

Objective

$$\begin{aligned} Min \sum _m \left[\sum _{i \in N}\left(C_{ip}^s \cdot r_{i,m} + \sum _{p \in P}C_{ip}^d \cdot r_{i,m}^p \right) + \sum _{i \in N}\left(C_{sw}^s \cdot s_{i,m} + \sum _{p \in P} C_{sw}^d \cdot s_{i,m}^p\right) + \sum _{e \in E} C_{link}^e \cdot t_{e,m}\right] \end{aligned}$$

(4)

subject to:

• (a) Destination node selection constraints:

  $$\begin{aligned} \sum _{i \in D_p} d_{p,i}=1\quad \forall p \in P \end{aligned}$$

  (5a)
  $$\begin{aligned} d_{p,i}=0, \forall i \notin D_p, \forall p \in P \end{aligned}$$

  (5b)

• (b) Route selection constraints:

  $$\begin{aligned} \sum _{e:(i, j)\in E} x_{e,p} - \sum _{e:(j, i)\in E} x_{e,p} = \left\{ \begin{array}{l l} 1 &{} \quad \text{ if }\, i = s_p,\\ -d_{p,i} &{}\quad \text{ otherwise. } \quad \forall i \in N, p \in P \end{array} \right. \end{aligned}$$

  (6a)
  $$\begin{aligned} y_{p,i} = \sum _{j:(i \rightarrow j \in E)} x_{e,p} \quad \forall p \in P, i \in N \end{aligned}$$

  (6b)

• (c) IP router usage constraints:

  $$\begin{aligned} d_{p,i} + a_{p,m} - r_{i,m}^p \le 1 \quad \forall p \in P, i \in D_p, \alpha _p \le m \le \omega _p \end{aligned}$$

  (7a)
  $$\begin{aligned} d_{p,i}\ge r_{i,m}^p \quad \forall p \in P, i \in D_p, \alpha _p \le m \le \omega _p \end{aligned}$$

  (7b)
  $$\begin{aligned} a_{p,m} \ge r_{i,m}^p \quad \forall p \in P, i \in D_p, \alpha _p \le m \le \omega _p \end{aligned}$$

  (7c)
  $$\begin{aligned} \dfrac{\sum _p r_{i,m}^p}{M} \le r_{i,m} \quad \forall i \in D_{p}, \alpha _p \le m \le \omega _p \end{aligned}$$

  (7d)
  $$\begin{aligned} r_{i,m} \le \sum _p r_{i,m}^p \quad \forall i \in D_{p}, \alpha _p \le m \le \omega _p \end{aligned}$$

  (7e)

• (d) Optical switch usage constraints:

  $$\begin{aligned} a_{p,m} + (y_{p,i} + d_{p,i}) - s_{i,m}^p \le 1 \quad \forall p \in P,i \in D_{p}, \alpha _p \le m \le \omega _p \end{aligned}$$

  (8a)
  $$\begin{aligned} a_{p,m} \ge s_{i,m}^p \quad \forall p \in P,i \in D_{p}, \alpha _p \le m \le \omega _p \end{aligned}$$

  (8b)
  $$\begin{aligned} (d_{p,i} + y_{p,i}) \ge s_{i,m}^p \quad \forall p \in P,i \in D_{p}, \alpha _p \le m \le \omega _p \end{aligned}$$

  (8c)
  $$\begin{aligned} \dfrac{\sum _p s_{i,m}^p}{M} \le s_{i,m} \quad \forall i \in D_{p}, \alpha _p \le m \le \omega _p \end{aligned}$$

  (8d)
  $$\begin{aligned} s_{i,m} \le \sum _p s_{i,m}^p \quad \forall i \in D_{p}, \alpha _p \le m \le \omega _p \end{aligned}$$

  (8e)

• (e) Fiber link and node usage constraints:

  $$\begin{aligned} x_{e,p} + a_{p,m} - t_{e,m}^p \le 1 \quad \forall p \in P,i \in D_{p}, \alpha _p \le m \le \omega _p \end{aligned}$$

  (9a)
  $$\begin{aligned} a_{p,m} \ge t_{e,m}^p \quad \forall p \in P, i \in D_{p}, \alpha _p \le m \le \omega _p \end{aligned}$$

  (9b)
  $$\begin{aligned} x_{e,p} \ge t_{e,m}^p \quad \forall p \in P, i \in D_{p}, \alpha _p \le m \le \omega _p \end{aligned}$$

  (9c)
  $$\begin{aligned} \dfrac{\sum _p t_{e,m}^p}{M} \le t_{e,m} \quad \forall i \in D_{p}, \alpha _p \le m \le \omega _p \end{aligned}$$

  (9d)
  $$\begin{aligned} t_{e,m} \le \sum _p t_{e,m}^p \quad \forall i \in D_{p}, \alpha _p \le m \le \omega _p \end{aligned}$$

  (9e)

• (f) RWA constraints:

  $$\begin{aligned} \sum _{k \in K} \omega _{k,p}=1, \quad \forall p \in P \end{aligned}$$

  (10a)
  $$\begin{aligned} \omega _{k,p} + x_{e,p} - a_{k,e}^p \le 1; \quad \forall k \in K, e \in E, p \in P \end{aligned}$$

  (10b)
  $$\begin{aligned} \omega _{k,p} \ge a_{k,e}^p; \quad \forall k \in K, e \in E, p \in P \end{aligned}$$

  (10c)
  $$\begin{aligned} x_{e,p} \ge a_{k,e}^p; \quad \forall k \in K, e \in E, p \in P \end{aligned}$$

  (10d)
  $$\begin{aligned} a_{k,e}^p + a_{p,m} + a_{k,e}^q + a_{q,m} \le 3 \quad \forall k \in K, e \in E, p,q \in P, \alpha _p \le m \le \omega _p \end{aligned}$$

  (10e)

• (g) Demand scheduling constraints:

  $$\begin{aligned} \sum _m st_{p,m} = 1 , \quad \forall p \in P, \alpha _p \le m \le \omega _p - \tau _p \end{aligned}$$

  (12a)
  $$\begin{aligned} \sum _m a_{p,m} = \tau _p , \quad \forall p \in P, \alpha _p \le m \le \omega _p \end{aligned}$$

  (12b)
  $$\begin{aligned} a_{p,m+j} \ge st_{p,m}, \quad \forall p \in P, 0 \le j < \tau _p, \alpha _p \le m \le \omega _p \end{aligned}$$

  (12c)

The objective function in (4) tries to minimize the total number of active network components. $C_{IP}^s$ and $C_{SW}^s$ are the static components of power consumption in IP routers and optical switches respectively. The variables $r_{i,m}$ and ($s_{i,m}$) will be set 1 if the IP router (optical switch) at node i is being used during interval m. $C_{IP}^d$ and $C_{SW}^d$ represent the dynamic component of power consumption of an IP router and optical switch respectively. In other words, $C_{IP}^d$ ($C_{SW}^d$) represents the incremental power consumption per lightpath routed through the router (optical switch). Therefore, $\sum _{p \in P}C_{IP}^d \cdot r_{i,m}^p$ ($\sum _{p \in P} C_{SW}^d \cdot s_{i,m}^p$) represents the total dynamic power consumption for all lightpaths p that are using the router (optical switch) at node i during interval m. $C_{link}^e$ is the power consumption of an active link e which has at least one lightpath using that link. This value does not depend on the number of lightpaths using the link. The variable $t_{e,m}$ is set to 1 if link e is active during interval m. So, $\sum _{e \in E} C_{link}^e \cdot t_{e,m}$ represents the total power consumption for all links, during interval m. Similarly, $\sum _{i \in N}(C_{IP}^s \cdot r_{i,m} + \sum _{p \in P}C_{IP}^d \cdot r_{i,m}^p)$ ($\sum _{i \in N}(C_{SW}^s \cdot s_{i,m} + \sum _{p \in P} C_{SW}^d \cdot s_{i,m}^p)$) represents the total power consumption for all IP routers (optical switches) during interval m. Finally, the outer summation ($\sum _m[\sum _{i \in N}(C_{IP}^s \cdot r_{i,m} + \sum _{p \in P}C_{IP}^d \cdot r_{i,m}^p) + \sum _{i \in N}(C_{SW}^s \cdot s_{i,m} + \sum _{p \in P} C_{SW}^d \cdot s_{i,m}^p) + \sum _{e \in E} C_{link}^e \cdot t_{e,m}]$) in the objective function gives the total power consumption over all intervals.

Constraint (5a) selects exactly one destination for demand p. Constraint (5b) sets the value of $d_{p,i} = 0$, if $i \notin D_p$. This ensures that destination nodes are selected only from the set of candidate destinations for each demand p. Constraint (6a) is the standard flow conservation constraint and is used to find a feasible path from the from source node $s_p$ to the selected destination $d_{p,i}$ for each demand p. Constraint (6b) identifies the nodes that are used along the selected path of a demand p. The optical switches at all these nodes will be used by demand p, during the intervals in which it is active. Constraints (7a)–(7c) are used to set the value of $r_{i,m}^p=1$, if router at node i is being used by demand p during interval m. Constraint (7a) states that if $d_{p,i}=1$, (i.e. node i is the selected destination node for demand p) and $a_{p,m}=1$, (i.e. node demand p is active during interval m) then $r_{i,m}^p=1.$ Constraints (7b) and (7c) state that if either $d_{p,i}=0$ or $a_{p,m}=0$ , then $r_{i,m}^p$ must be set to 0. In constraint (7d) if there is at least one demand p which uses the IP router at node i during interval m (i.e. $r_{i,m}^p=1$), then this forces $r_{i,m}$ to be 1. On the other hand constraint (7e) states that if $\sum _{p} r_{i,m} = 0$ , (i.e. $r_{i,m}^p=0 ,\forall p \in P$), then $r_{i,m}=0$. In other words, constraints (7d) and (7e) together set the value of $r_{i,m}=1$, if the IP router at node i is being used by at least one demand (possibly more than 1) during interval m, and set $r_{i,m}=0$ otherwise. Similarly, Constraints (8a)–(8e) determine if optical switch at node i is being used during interval m. Constraints (9a)–(9e) state that fiber link e is in use during time interval m, if there is at least one SLD $p \in P$ such that p uses link e and is active during interval m.

Constraint (10a) enforces the wavelength continuity constraint, so that each demand p is allocated the same channel on each fiber it traverses. Constraints (10b)–(10d) set the value of $a_{k,e}^p=1$, if lightpath p uses channel k on link e. Expressing the constraints in this form allows $a_{k,e}^p=1$ to be defined as a continuous variable, while still restricting its values to 0 or 1 only. This lowers the number of integer variables, which leads to less complexity of the ILP. Constraint (10e) enforces the wavelength clash constraint and ensures that two lightpaths p and q cannot use the same channel k on the same link e if they are both active during the same interval m. If two demands p and q both use the same channel k on a link e, then we will have $a_{k,e}^p=1$ and $a_{k,e}^q=1$. This will be a valid assignment if and only if demands p and q are time disjoint, i.e. they are never active during the same time interval. In sliding window model the ILP itself determines the most suitable start time for each demand, based on other demands start times and durations. Constraints (12a)–(12c) are used to select the best starting interval for each SLD. Constraint (12a) sets the actual starting time for demand p during intervalm, and states that there can be exactly one starting interval for each demand. Constraint (12b) sets the number of active intervals for each demand p to its demand holding time $\tau _p$. Finally, constraint (12c) states that demand p will be active for $\tau _p$ consecutive time intervals, beginning with its selected starting interval of $st_{p,m}$.

3.3 Modification for fixed window model

For fixed window model, the actual start time for the demand is same as the starting time of its window. This means $\tau _p = \omega _p - \alpha _p +1$ and $st_p = \alpha _p, \forall p$. So in fixed window model, the starting time is known in advance. This can be easily handled by the proposed ILP, by simply adding an extra constraint as follows:

$$\begin{aligned} st_{p,\alpha _p} = 1 \quad \forall p \in P \end{aligned}$$

(13)

Constraint (13) states that $\alpha _p$ will be automatically selected as the starting interval for demand p, i.e. the ILP does not have the option of selecting any other time interval as the starting interval for p. Once the starting interval is set, all other constraints function in a similar manner as for sliding window model.

3.4 An illustrative example

To illustrate the effectiveness of the proposed approach, we consider a very simple example where three demands are to be scheduled and routed over a 4-node topology. The demands p1, p2 and p3 are specified as shown below:

• $p1=(2, \{1\}, 2, 4, 2)$: The source node $s1=2$; the set of potential destinations $D1=\{1\}$; the demand must be scheduled between intervals $\alpha 1 =2$, $\omega 1 =4$ and the demand holding time $\tau 1 =2$ intervals.

• $p2=(1, \{3\}, 1,4,3)$: The source node $s2=1$; the set of potential destinations $D2=\{3\}$; the demand must be scheduled between intervals $\alpha 2 =1$, $\omega 2 =4$ and the demand holding time $\tau 2 =3$ intervals.

• $p3=(2, \{3,4\},3,5,2)$: The source node $s2=2$; the set of potential destinations $D3=\{3,4\}$; the demand must be scheduled between intervals $\alpha 3 =3$, $\omega 3 =5$ and the demand holding time $\tau 3 =2$ intervals.

In order to simplify the explanation, we assume that demands p1 and p2 have already been routed along the routes $2 \rightarrow 1$ and $1 \rightarrow 3$ respectively, using channel $\lambda 1$, as shown in Fig. 1a. Furthermore, we assume that demands p1 and p2 have been scheduled to start at time interval $m=3$ and $m=2$ respectively. Demand p3 must start either during m=3 or m=4, since $\tau _3 = 2$ and the demand must be completed by the end of interval $m=5$. Figure 1b, c show the valid time scheduling options for the demand p3, assuming p1 and p2 have already been scheduled as specified above. Figure 1b represents the fixed window STM where demand p3 is scheduled at its earliest interval where as in Fig. 1c, demand p3 was scheduled using the sliding window STM.

For each scheduling option mentioned above, demand p3 has two possible choices for the destination, node 3 or node 4. Finally, for each destination node, there are several different ways the demand can be routed. So, we see that even for this simple example, and considering the choices for just one demand, the number of potential solutions can grow very quickly. Table 2 shows six different options for routing and scheduling demand p3. We note that this is not an exhaustive list, and there are other options that can be used. We are simply listing the following options to illustrate that there are many different ways a single demand may be accommodated.

Fig. 1

a Routing of demands p1 and p2, b and c the possible start time for demand p3 assuming p1 and p2 have already been scheduled

Table 2 Options for routing and scheduling demand p3 with two different destination nodes and starting intervals

Table 3 shows the number of active links and nodes during each time interval, and the total over all intervals, for each option shown in Table 2. We see that Option 2 has the lowest overall value of active nodes and links, which indicates the maximum sharing of resources and consequently reduces the energy consumption. For example, since node 3 is selected as destination node for p3, this allows node 4 to remain in a low-power (inactive) state. Also, route $2\rightarrow 1 \rightarrow 3$ is selected, rather than the shorter route $2 \rightarrow 3,$ because both links $2 \rightarrow 1$ and $1 \rightarrow 3$ are already in use by other demands. This means the optical amplifiers on link $2 \rightarrow 3$ can remain in low-power state. Finally, scheduling p1(p2) to start during interval $m=3(m=2)$ rather than the earliest possible times for those demands, allows p1 and p2 to remain active for the entire duration of p3, so that network components are active for a minimum amount of time.

Table 3 Number of active nodes and links for routing and scheduling demand p3

3.5 Complexity analysis of the proposed ILP

To get an insight into the size of the proposed ILP formulation, we calculate the number of variables and constraints generated by the ILP. The complexity of an ILP has been proven to be exponential in the number of integer variables (Schrijver, 1998), when the integer variables increase the ILP becomes computationally intractable. Hence, by declaring some variables (eg., $r^p_{i,m}, s^p_{i,m}, t^p_{e,m}, a^p_{k,e}$) as continuous variables and restricting their values to be 0 and 1 we can further reduce the ILP complexity. Clearly, Reducing the number of binary variables at the expense of more continuous variables reduces the complexity of the ILP, but this technique cannot be applied to all binary variables. Table 4 gives the number of integer variables, continuous variables and constraints in our proposed formulation presented in Sect. 3.2. In the table, we used $D_p$ and $A_p$ to indicate the number of possible destinations and the total number of intervals over the entire time period during which the demands may be active, respectively.

Table 4 Number of variables and constraints in the ILP

4 Experimental results

In this Section, we present simulation results, obtained using our proposed ILP formulations. We show the results for two well known topologies, NSFNET (14 nodes, 21 links) (Sridharan et al. 2002) and USANET (24 nodes, 32 links) (Ye et al. 2004). The proposed ILP is able to generate optimal results for practical sized problems. The simulations were carried out with IBM ILOG CPLEX 12.6.2. We have performed experiments considering 10, 20, 40 and 80 lightpaths and considering 16 channels (wavelengths) per fiber. The results reported below correspond to average values (rounded to the nearest integer) over 5 different runs. The power consumption was normalized with respect to the fixed window scheduled traffic model with unicast routing. For each given network topology, we have tested our proposed approach with different sized demand sets and different demand time correlations $\delta$ as defined in (Kuri et al. 2003). The demand time correlation $\delta$ determines the overlapping between different demands. If $\delta =0$, it means that the demands do not overlap in time, so RWA can be done for each demand separately. For the simulations we have considered four distinct scenarios:

• Energy aware anycast sliding scheduled traffic model (EA_Anycast_SSLD): This is our proposed approach, where the ILP selects the best possible destination node and start time for each demand, and then performs RWA.

• Energy aware anycast fixed window traffic model (EA_Anycast_FW): In this case the ILP is free to choose a suitable destination node, but the start time of each demand is fixed.

• Energy aware unicast sliding scheduled traffic model (EA_Unicast_SSLD): In this case the destination node is specified beforehand, but the ILP can select suitable start time for each demand and also perform RWA.

• Energy aware unicast fixed window traffic model (EA_Unicast_FW): This is the baseline scenario without any flexibility since both the destination node and start time of demand are fixed and the ILP only performs the RWA for each demand.

In the following paragraphs we will present the simulation results of all the four approaches mentioned above. Figure 2a shows the normalized energy consumption for routing a set of SLDs over the 14-node topology with 16 channels per fiber. We have normalized the energy consumption values with respect to the energy consumption for EA_Unicast_FW for 40 lightpath demands. It is clearly seen that the proposed approach (EA_Anycast_SSLD) performs the best irrespective of the number of demands. The EA_Unicast_SSLD performs better compared to EA_Unicast_FW, and EA_Unicast_FW has the worst performance. EA_Anycast_SSLD shows, on average, improvement about 13, 32, and 47% over EA_Anycast_FW, EA_Unicast_SSLD, EA_Unicast_FW, respectively. As we see in Fig. 2a, the gap between anycast approach and unicast approach is large compared to the gap between fixed window models and sliding scheduled models, which indicates that selection of the destination node is a more important factor in determining overall energy consumption compared to the start time. As expected, the overall trend shows an increase in energy consumption with increase in number of demands, since more network components such as switches, routers and amplifiers will be required to turn on.

In Fig. 2b the comparison of energy consumption for 24-node topology is illustrated. The results follow the same trend as in Fig. 2a, the proposed sliding scheduled demands allocation model outperforms the other approaches. The energy consumption also increases as the number of demands increase for both the topologies. The average improvement over the next best approach (EA_Anycast_FW) is 13, 11 and 7% for with 10, 20 and 40 demands respectively. Also we note that the improvement of EA_Anycast_SSLD is about 8, 41 and 44% over EA_Anycast_FW, EA_Unicast_SSLD, EA_Unicast_FW, respectively.

We next consider the performance of the different approaches but for different networks with the same number of demands as illustrated in Fig. 3a. We can see that the energy consumption is more in the case of 14-node topology compared to 11-node topology for all the approaches, but the energy consumption for 24-node topology is less compared to 14-node topology although 24-node topology includes more nodes and links compared to 14-node topology. This can be due to a number of factors, such as the length of the links, the number of available destination nodes, and the distribution of the demands.

In Fig. 3b we show the relative improvement obtained using our proposed scheme over other schemes. EA_Anycast_SSLD shows 12% improvement on 11-node topology, 11% improvement on 14-node topology and 7% improvement on 24-node topology comparing to next best technique EA_Anycast_FW. The simulation results show a big improvement by EA_Anycast_SSLD over EA_Unicast_SSLD and EA_Unicast_FW. EA_Anycast_SSLD performs 30% better on 11-node topology, 38% better on 14-node topology and 40% better on 24-node topology compared to EA_Unicast_SSLD. EA_Anycast_SSLD performs 38% better on 11-node topology and 46% better on 14-node and 24-node topologies compared to EA_Unicast_FW.

Finally, we consider the comparison of execution times of our proposed approach with the other approaches. The simulation results show that fixed window traffic allocation requires significantly less time compared to sliding scheduled demand allocation. The reason is that the additional flexibility in demand start time leads to an increase in the number of integer variables, which results in a much larger search space.

Figure 4 shows that the execution time increases with number of nodes, increases as expected. The The EA_Anycast_SSLD shows linear steady growth in execution time with increase in number of nodes. EA_Unicast_SSLD performs slightly faster compared to EA_Anycast_SSLD. The two fixed window approaches, EA_Anycast_FW and EA_Unicast_FW perform the best and are significantly faster than the other approaches.

Fig. 2

Comparison of energy consumption for sliding and fixed schedule traffic with different demand set sizes a 14-node network (NSFNET) and b 24-node network

Fig. 3

a Comparison of energy consumption for different network topologies and b improvement of EA_Anycast_SSLD over other approaches

Fig. 4

Comparison of execution time for different approaches

5 Conclusions

In this paper, we have presented a new approach for energy aware RWA, which jointly schedules demands (in time) and performs routing of sliding scheduled lightpath demands in optical grid networks by exploiting the flexibility of anycast principle. Our approach implements a comprehensive energy-aware resource allocation for optical grid networks, which is able to consider power consumption over a wide variety of network components. The objective of our formulation was to minimize the overall energy consumption of the network, by minimizing number of active network components during any given time interval. To the best of our knowledge, this is the first optimal ILP formulation for energy-aware RWA of sliding scheduled lightpath demands. We have compared our results with existing energy-aware routing techniques for WDM networks, using both unicast and anycast routing. The results demonstrate that not only does the proposed approach outperform energy unaware RWA, it significantly reduces energy consumption, even compared to previous energy-aware techniques. In applications where continuous data transmission is not required, it may be possible to divide the total data into small chunks, which are sent separately. The full amount of data transfer should still be completed within the specified time range. This type of traffic model is known as non-continuous sliding scheduled traffic model (Chen et al. 2011), and adds more flexibility to our proposed sliding scheduled approach. One possible direction for future work is to develop an energy-aware RWA for the non-continuous sliding scheduled traffic model. Since the proposed ILP can become computationally intractable as the number of demands increases, we are currently exploring the possibility of using meta-heuristics such as genetic algorithm, tabu search or simulated annealing in order to get faster results.