# Routing On Demand: Toward the Energy-Aware Traffic Engineering with OSPF

Meng Shen, Hongying Liu, Ke Xu, Ning Wang, Yifeng Zhong

► To cite this version:

Meng Shen, Hongying Liu, Ke Xu, Ning Wang, Yifeng Zhong. Routing On Demand: Toward the Energy-Aware Traffic Engineering with OSPF. 11th International Networking Conference (NET-WORKING), May 2012, Prague, Czech Republic. pp.232-246, 10.1007/978-3-642-30045-5_18 . hal-01531129

HAL Id: hal-01531129

https://inria.hal.science/hal-01531129

Submitted on 1 Jun 2017

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Routing On Demand: Toward the Energy-Aware Traffic Engineering with OSPF

Meng Shen<fnref n="1" />*, Hongying Liu<fnref n="2" />, Ke Xu<fnref n="1" />, Ning Wang<fnref n="3" />, and Yifeng Zhong<fnref n="1" />

**Abstract.** Energy consumption has already become a major challenge to the current Internet. Most researches aim at lowering energy consumption under certain fixed performance constraints. Since trade-offs exist between network performance and energy saving, Internet Service Providers (ISPs) may desire to achieve different Traffic Engineering (TE) goals corresponding to changeable requirements. The major contributions of this paper are twofold: 1) we present an OSPF-based routing mechanism, Routing On Demand (ROD), that considers both performance and energy saving, and 2) we theoretically prove that a set of link weights always exists for each trade-off variant of the TE objective, under which solutions (*i.e.*, routes) derived from ROD can be converted into shortest paths and realized through OSPF. Extensive evaluation results show that ROD can achieve various trade-offs between energy saving and performance in terms of Maximum Link Utilization, while maintaining better packet delay than that of the energy-agnostic TE.

**Keywords:** Traffic Engineering, OSPF, Energy Saving, Routing

## 1 Introduction

Since plenty of bandwidth-intensive applications (*e.g.*, video-on-demand and cloud computing) have come into service, the amount of data being carried on the Internet has dramatically grown [11]. Traditionally, Internet Service Providers

<footnote n="1">¹ Tsinghua National Laboratory for Information Science and Technology
Department of Computer Science, Tsinghua University,
Beijing, 100084, China
{shenmeng,ke.xu,zhongyifeng}@csnet1.cs.tsinghua.edu.cn</footnote>

<footnote n="2">² School of Mathematics and Systems Science, Beihang University,
Beijing, 100191, China
liuhongying@buaa.edu.cn</footnote>

<footnote n="3">³ Center for Communication Systems Research, University of Surrey,
Surrey, GU2 7XH, United Kingdom
N.Wang@surrey.ac.uk</footnote>

<footnote>* This work is supported by New Generation Broadband Wireless Mobile Communication Network of the National Science and Technology Major Projects (2012ZX03005001), NSFC Project (61170292, 60970104), 973 Project of China (2009CB320501), Program for New Century Excellent Talents in University and EVANS Project (PIRSES-GA-2010-269323).</footnote>
(ISPs) leverage Traffic Engineering (TE) to ensure acceptable network performance. Open Shortest Path First (OSPF) [18] is a commonly used intra-domain routing protocol that can be applied in TE through configuring appropriate link weights. In our previous work [5], we made a change on the traffic splitting scheme in OSPF and proposed an OSPF-based approach to achieve optimal TE.

As bandwidth requirements increase, ISPs need to deploy more and faster
network equipments (e.g., routers) to handle these demands, resulting in the
growth of energy consumption. Therefore, TE should take both energy effi-
ciency and network performance into consideration rather than merely focus-
ing on the latter. The common idea of the state-of-the-art energy-aware TE
approaches [7] [11] is to reduce energy consumption under certain performance
constraints. However, we argue that trade-offs exist between energy saving and
network performance. Intuitively, an ISP can achieve higher network energy ef-
ficiency at the cost of sacrificing partial performance without influencing user
experience. Thus, there is a set of solutions rather than a unique solution to
solve the energy-aware TE problem, where ISPs can make a flexible adjustment
among these solutions.

The main challenge to achieve this goal exists that the conventional TE prob-
lem is already difficult due to the elastic nature of network traffic. Therefore,
considering energy saving and network performance together will make the prob-
lem even harder. This problem should be carefully studied to ensure the network
free from frequent oscillations and extra long delays.

This paper presents Routing On Demand (ROD), an OSPF-based routing
mechanism that can achieve energy-aware traffic engineering solutions. ROD is
formulated based on the Multiple Commodity Flows (MCF) constrains with
a weighted objective considering both energy consumption and network per-
formance in terms of Maximum Link Utilization (MLU). In ROD, a specific
trade-off requirement can be derived from adjusting a green factor in the ob-
jective function, where corresponding solutions (i.e., routes) can be converted
into shortest paths with respect to a set of link weights. Then we develop al-
gorithms to achieve these link weights, as well as flow splitting ratios based on
minor extensions to the Equal-Cost Multiple Paths (ECMPs) function in OSPF
that has been proposed in [5], which can be directly configured through OSPF
protocol without introducing additional load to the network. The compatibility
with existing network protocols eases the deployment of ROD mechanism.

Using real and synthetic network topologies, we evaluate the effectiveness of
the ROD mechanism in multiple metrics, including trade-offs between energy
saving and performance, link utilization and packet delay. Results show that,
through adjusting the green factor, ROD can achieve diverse trade-offs between
energy saving and MLU without bias on topology types. Moreover, a promising
result for Abilene lies in that a 1% growth of MLU threshold will roughly lead
to a 15% decrease in energy consumption. Similar results also hold for other
topologies.

The rest of the paper is organized as follows. Section 2 gives an overview of
our basic idea. In Section 3, we present the ROD model and the proof of the
<figure><img src="image_2.png" /><figcaption>**Figure 1.** Optimal Routing in Various Cases</figcaption></figure>

existence of optimal link weights. The implementation issues are discussed in Section 4, which is followed by the evaluation of ROD mechanism in Section 5. We summarize the related work in Section 6 and then conclude the paper in Section 7.

## 2 Overview of the Basic Idea

In this section, we illustrate through case studying that trade-offs exist between energy saving and network performance.

As shown in Figure 1, each link has a capacity of 5 units. Traffic demands consist of 2 Original-Destination (OD) pairs, namely A→B and A→E, with a bandwidth requirement of 2 and 4 units respectively. For simplicity, we assume that each unused link can be put into sleep mode [8] without any power consumption, while each loaded link consumes the same amount of power. Given traffic demands and network topology, we need to configure the OSPF link weights under which the optimal routes for these demands according to certain constrains and objectives are exactly the OSPF shortest paths.

Through the following three cases with the OSPF link weights beside links, we illustrate the existence of trade-offs between energy saving and network performance in terms of Maximum Link Utilization (MLU) based on OSPF.

**Case 1: Minimizing MLU.** The most widely used objective function of the conventional TE is simply to minimize MLU [14], which aims at reducing the risk of network congestion. The optimal routes are shown in Figure 1 (a), where each path is marked with the same line type and its traffic load. In this case, the optimal routes altogether leverage 7 links with a 2-unit load on each link. Thus the MLU is 40%.

**Case 2: Minimizing energy consumption without MLU constraint.** Based on the energy assumption, this goal is equivalent to minimize the number of loaded links. The optimal routes are presented in Figure 1 (b), where altogether 4 links are involved and the MLU is 80%. Comparing to Case 1, energy consumption of the entire network is reduced approximately by $(7-4)/7 = 42.9\%$.

**Case 3: Minimizing energy consumption with certain MLU upper bound.** TE with only energy consideration might increase the risk of network congestion on
heavy loaded links when facing traffic bursts. Therefore, an ISP may desire to minimize energy consumption while keeping MLU within certain safety threshold, say 60%. The optimal routes are shown in Figure 1 (c), where the energy saving rate compared with Case 1 is about 14.3% and the MLU is exactly 60%.

We notice that the traffic is not equally split over two ECMPs serving the same OD pair A→E in Case 3. This can be realized by modifying hardware components, which will be discussed in Section 4.

# 3 ROD Model

In this section, we first present the Routing On Demand (ROD) model to formulate energy-aware TE problem, which extracts the trade-off between energy saving and network performance. Then we prove that the optimal link weights always exist under each considered TE objective function.

## 3.1 Network Model

We consider a directed network $G = (\mathcal{N}, \mathcal{E})$, where $\mathcal{N}$ is the set of nodes (i.e., routers) and $\mathcal{E}$ is the set of edges (i.e., links). We assume that all links are directional and each link $(i, j) \in \mathcal{E}$ is attached with its own capacity $c_{ij}$ which is the maximum amount of traffic it can take. Let $\mathcal{M}$ denote the set of source-destination pairs. For each $m \in \mathcal{M}$, a traffic demand of $(s_m, t_m)$ is $d_m$, which represents the average intensity of traffic volume entering the network at node $s_m$ and leaving from node $t_m$. Hereafter we use notations $\mathcal{N}, \mathcal{E}$ and $\mathcal{M}$ to denote the cardinalities of sets $\mathcal{N}, \mathcal{E}$ and $\mathcal{M}$, respectively.

A customary way to treat the TE problem is to formulate it based on MCF constraints. We denote the destination node set with $\mathcal{D} = \{t \in \mathcal{N} : \exists m \in \mathcal{M} \text{ s.t. } t_m = t\}$. The traffic volume of commodity flow $t$ along edge $(i, j)$ is denoted by $f_{ij}^t$. The MCF constraints can be formulated as

$$f_{ij} = \sum_{t \in \mathcal{D}} f_{ij}^t \le c_{ij}, \forall (i, j) \in \mathcal{E} \qquad (1a)$$

$$\sum_{i:(s,i) \in \mathcal{E}} f_{si}^t - \sum_{j:(j,s) \in \mathcal{E}} f_{js}^t = d_s^t, \forall t \in \mathcal{D}, s \in \mathcal{N} \qquad (1b)$$

$$f_{ij}^t \ge 0, \forall t \in \mathcal{D}, (i, j) \in \mathcal{E}, \qquad (1c)$$

where $d_s^t \ge 0$ in (1b) is the expected traffic entering the network at node $s$ and destined to node $t$. For $s \ne t$, set $d_s^t = d_m$ if there exists $m \in \mathcal{M}$ such that $s_m = s$ and $t_m = t$, or set $d_s^t = 0$ otherwise. For $s = t$, according to the previous definition of commodity, we set $d_t^t = - \sum_{m:t_m=t} d_m$. Constraint sets (1a) and (1b) represent the capacity and flow conservation constraints, respectively. We say a traffic distribution $\mathbf{f} = (f_{ij}, (i, j) \in \mathcal{E})$ is feasible if there exists $(\mathbf{f}^t, t \in \mathcal{D})$ such that $(\mathbf{f}, \mathbf{f}^t, t \in \mathcal{D})$ satisfies the MCF constraints.

**Remark:** Here, to formulate the problem in a more compact way, we regard all traffic flows to the same destination as a commodity, i.e., we use the constraints (1b) associated with those traffic flows with their sum for $s = t$, so that
we can obtain a formulation with less constraints and variables. It can be easily checked that this formulation is equivalent to the one where each traffic flow is treated as a separate commodity.

**Minimizing MLU.** If $\mathbf{f}$ is feasible, the total load and the utilization of link $(i, j) \in \mathcal{E}$ are $f_{ij}$ and $f_{ij}/c_{ij}$, respectively. The conventional TE problem prefers to minimize MLU to balance traffic distribution over all links, i.e.,

$$ \underset{(i,j) \in \mathcal{E}}{\text{minimize}} \quad \max \quad \frac{f_{ij}}{c_{ij}} \qquad (2a) $$

$$ \text{subject to} \quad (1a) - (1c). \qquad (2b) $$

**Minimizing Energy Consumption.** If we only consider minimizing energy consumption of the entire network, then the TE problem turns into optimizing traffic distribution under the same MCF constraints in (2) to use as few links as possible, i.e., to minimize $\|\mathbf{f}\|_0$, where $\|\mathbf{f}\|_0$ represents the number of non-zero elements of $\mathbf{f}$.

The above formulation, which seeks the vector whose support has the smallest cardinality, is commonly referred to as cardinality minimization and known to be NP-hard. Since the computation time for medium and large-scale networks is a great concern, the cardinality minimization problem is thus usually heuristically solved by minimizing the $\ell_1$ norm [6]. Then the TE problem of minimizing energy consumption with the relaxed objective function is

$$ \underset{(i,j) \in \mathcal{E}}{\text{minimize}} \quad \sum_{(i,j) \in \mathcal{E}} f_{ij} \qquad (3) $$
$$ \text{subject to} \quad (1a) - (1c). $$

**Routing On Demand.** We introduce a green factor $\theta$ to combine the above two models together and propose an integrated ROD model as follows

$$ \underset{(i,j) \in \mathcal{E}}{\text{minimize}} \quad \theta \max_{(i,j) \in \mathcal{E}} \frac{f_{ij}}{c_{ij}} + \sum_{(i,j) \in \mathcal{E}} f_{ij} \qquad (4) $$

$$ \text{subject to} \quad (1a) - (1c). $$

## 3.2 Universal Existence of Optimal Link Weights

We associate the network with an operator, and assume that if the load held by link $(i, j)$ is $f_{ij}$, then the cost is $\phi(\mathbf{f})$. We also assume that the cost $\phi(\mathbf{f})$ is an continuous convex function of $\mathbf{f}$ ($\mathbf{f} \ge 0$). Without loss of generality, we can apply $\phi(\mathbf{f})$ to represent various objective functions of previous models. The goal of TE thus turns into minimizing $\phi(\mathbf{f})$ over MCF constraints.

For simplicity of presentation, we write the MCF constrains in matrix form. Then the general TE problem is given as TE($\phi, \mathcal{G}, \mathbf{c}, \mathbf{D}$)

$$ \underset{\phi(\mathbf{f})}{\text{minimize}} \qquad (5a) $$

$$ \text{subject to} \quad \mathbf{f} - \sum_{t \in \mathcal{D}} \mathbf{f}^t = \mathbf{0} \qquad (5b) $$

$$ \mathbf{f} \le \mathbf{c} \qquad (5c) $$

$$ \mathbf{A}\mathbf{f}^t = \mathbf{d}^t, \mathbf{f}^t \ge \mathbf{0}, \forall t \in \mathcal{D}, \qquad (5d) $$
where **A**, an $N \times E$ node-arc incidence matrix for network $\mathcal{G}$, is introduced to represent the multi-commodity flow constraints (1b). The column corresponding to link $(i, j)$ has a +1 entries in row $i$ and a -1 entries in row $j$.

The partial Lagrangian of TE($\phi, \mathcal{G}, \mathbf{c}, \mathbf{D}$) is

$$ \mathcal{L}(\mathbf{f}, \mathbf{f}^t, t \in \mathcal{D}; \mathbf{w}) = \phi(\mathbf{f}) - \sum_{(i,j) \in \mathcal{E}} w_{ij} f_{ij} + \sum_{t \in \mathcal{D}} \mathbf{w}^T \mathbf{f}^t $$

From the general theory of constrained convex optimization [1], it follows that $(\mathbf{f}, \mathbf{f}^t, t \in \mathcal{D})$ solves Problem (5) if and only if there exists a Lagrangian multiplier vector $\mathbf{w}$ such that $(\mathbf{f}, \mathbf{f}^t, t \in \mathcal{D})$ solves

$$ \begin{array}{ll} \text{minimize} & \phi(\mathbf{f}) - \sum_{(i,j) \in \mathcal{E}} w_{ij} f_{ij} + \sum_{t \in \mathcal{D}} \mathbf{w}^T \mathbf{f}^t \\ \text{subject to} & \mathbf{f} \le \mathbf{c}; \quad \mathbf{A}\mathbf{f}^t = \mathbf{d}^t, \mathbf{f}^t \ge 0, \forall t \in \mathcal{D}. \end{array} \qquad (6) $$

Problem (6) is a separable optimization, since there is no coupling between variable $\mathbf{f}$ and $\mathbf{f}^t$ for all $t \in \mathcal{D}$. Then Problem (5) can be solved through the following distributed method, i.e., $(\mathbf{f}, \mathbf{f}^t, t \in \mathcal{D})$ solves problem (5) if and only if there exists the Lagrangian multiplier vector $\mathbf{w}$ such that $\mathbf{f}$ solves the capacity planning problem ISP($\mathbf{w}, \phi, \mathbf{c}$), i.e.,

$$ \begin{array}{ll} \text{minimize} & \phi(\mathbf{f}) - \sum_{(i,j) \in \mathcal{E}} w_{ij} f_{ij} \\ \text{subject to} & \mathbf{f} \le \mathbf{c} \end{array} \qquad (7) $$

and for each $t \in \mathcal{D}$, $\mathbf{f}^t$ solves the minimum cost flow problem MCF($\mathbf{w}, \mathbf{d}^t$)

$$ \begin{array}{ll} \text{minimize} & \mathbf{w}^T \mathbf{f}^t \\ \text{subject to} & \mathbf{A}\mathbf{f}^t = \mathbf{d}^t; \quad \mathbf{f}^t \ge 0. \end{array} \qquad (8) $$

Here we give some engineering interpretations to the separated Problems (7) and (8) for all $t \in \mathcal{D}$. First, the ISP's problem (7) can be interpreted as a capacity planning problem where ISP determines the possible virtual link capacity with each link cost $w_{ij}$, the total cost $\phi(\mathbf{f})$ generated for flow distribution $\mathbf{f}_{ij}$, and the maximal permission capacity for each link $c_{ij}$ and the objective as the net cost. Then the flows of the t-th class with the same destination $t$ finds a solution that minimizes the total cost under the given link cost $w_{ij}$ without considering the link capacity.

An promising property of the optimal routes is that they can be converted into shortest paths, i.e., the routes for the t-th class flow is the shortest path under the link weights $w_{ij}$. Let $\nu^t$ denote the optimal solution of the dual of Problem (8). By applying the complementary slackness theorem, we have

$$ \nu_i^t - \nu_j^t = w_{ij}, \quad \text{if} \quad f_{ij}^t > 0 \qquad (9a) $$

$$ \le w_{ij}, \quad \text{if} \quad f_{ij}^t = 0. \qquad (9b) $$

Let $p: i_0 i_1 \cdots i_n$ be a possible path of OD pair $(s, t)$, where $i_0 = s$ and $i_n = t$. For example, if $y_p = \min_{k=1,2,\cdots,n} f_{i_{k-1}i_k}^t > 0$, we have $\sum_{(i,j) \in p} w_{ij} = \nu_s^t - \nu_t^t \le$
$\sum_{(i,j) \in \bar{\mathcal{P}}} w_{ij}$ for any other path $\bar{\mathcal{P}}$ that connects the same source-destination pair $(s, t)$ under conditions (9a) and (9b).

Hereafter we refer to these as the optimal link weights and the optimal link loads, which are denoted by $\mathbf{w}^*$ and $\mathbf{f}^*$, respectively. The similar results have been shown by Wang et al. [3]. The major difference existing in our approach is that we present a close form of the link weights which are explicitly determined by the objective and the optimal traffic distribution. The main results are shown by Theorem 1 and that in Section 3.3.

Let $\mathbf{p}$ be a subgradient of a convex function $f$ at $\mathbf{x} \in \text{dom} f$ if

$$f(\mathbf{y}) \geq f(\mathbf{x}) + \mathbf{p}^T(\mathbf{y} - \mathbf{x}), \quad \forall \mathbf{y} \in \text{dom} f.$$

Subdifferential of $f$ at $\mathbf{x} \in \text{dom} f$ is the set of all subgradients of $f$ at $\mathbf{x}$ and is denoted by $\partial f(\mathbf{x})$. If $f$ is convex and differentiable at $\mathbf{x}$, then $\partial f(\mathbf{x}) = \{\nabla f(\mathbf{x})\}$.

**Theorem 1.** There exists one subgradient $\mathbf{p}$ of $\phi$ at $\mathbf{f}^*$ such that $w_{ij}^* = p_{ij}$ if $f_{ij}^* < c_{ij}$ and $w_{ij}^* \geq p_{ij}$ if $f_{ij}^* = c_{ij}$.

The proof of Theorem 1 can be conducted based on the convex analysis theory with the ISP's problem (7) and the calculation rule of subdifferential, which is omitted here due to space limitation.

## 3.3 Optimal Link Weights for Various Cost Functions

In this subsection, we will illustrate that the optimal link weights can be achieved for those cost functions in Section 3.1.

**Lemma 1.** Let $f(\mathbf{x}) = \max\{f_1(\mathbf{x}), \dots, f_m(\mathbf{x})\}$. Define $\mathcal{I}(\mathbf{x}) = \{i : f_i(\mathbf{x}) = f(\mathbf{x})\}$, and the active functions is at $\mathbf{x}$. Then it holds that

$$\partial f(\mathbf{x}) = \text{conv} \{\cup_{i \in \mathcal{I}(\mathbf{x})} \partial f_i(\mathbf{x})\},$$

For minimizing MLU, i.e., (2), we have $\phi(\mathbf{f}) = \max_{(i,j) \in \mathcal{E}} \frac{f_{ij}}{c_{ij}}$. Let $\mathcal{I}(\mathbf{f}^*) = \{(i,j) \in \mathcal{E} : f_{ij}^*/c_{ij} = \max_{(i,j) \in \mathcal{E}} f_{ij}/c_{ij}\}$, i.e., the set of the link with MLU. By Lemma 1, we have $\mathbf{p} \in \partial \phi(\mathbf{f}^*)$ if and only if $p_{ij} = a_{ij}/c_{ij}$ for $(i,j) \in \mathcal{I}(\mathbf{f}^*)$ and $a_{ij} \geq 0, \sum_{(i,j) \in \mathcal{I}(\mathbf{f}^*)} a_{ij} = 1$, and $p_{ij} = 0$ otherwise.

The results show that the routing minimizing MLU is the shortest path routing for each source-destination pair, where the link weights for the non-bottleneck links are all zeros, and only the link weights of the bottleneck links are possibly positive and scale with the inverse of their link capacities.

For minimizing energy consumption, by Theorem 1, routes derived from Model (3) are the shortest paths, where link weights are 1s for unsaturated links (i.e., $f_{ij}^* < c_{ij}$) and greater than 1 for the rest links. Furthermore, any path without including saturated links must be the lowest hop-count path.

For Routing On Demand, in (4), assume the green factor such that the optimal link load $f_{ij}^* < c_{ij}$ for all $(i,j) \in \mathcal{E}$, i.e., all links are unsaturated. By Theorem 1, the routes minimizing Problem (4) are the shortest paths, where the link weight is $\theta a_{ij}/c_{ij} + 1$ for $(i,j) \in \mathcal{I}(\mathbf{f}^*)$ and $a_{ij} \geq 0, \sum_{(i,j) \in \mathcal{I}(\mathbf{f}^*)} a_{ij} = 1$, and is 1 otherwise. Furthermore, the path of a source-destination pair must be the shortest hop-count path if it does not cross bottleneck links.
# 4 Implementation Issues

In this section, we will briefly discuss the implementation issues of ROD mechanism based on the theoretical formulation in Section 3. Similar to the conventional traffic engineering, ROD relies on a centralized controller that is responsible for centrally computing link weights and periodically configuring all routers.

## 4.1 Collecting and Disseminating Information for ROD

The input information for ROD (e.g., network topology and traffic matrix) can be collected from routers. In OSPF, each router will periodically flood its Link State Advertisements (LSAs) that contain all link state information. In particular, the Traffic Engineering Link State Advertisement (TE-LSA) defined in RFC3630 [17] records link load information. Thus, the latest topology and traffic matrix could be computed based on this information.

**Algorithm 1** Computing the optimal link weights

Given optimal tolerance $\epsilon$ and initial weight $\mathbf{w}(0)$ (such as $w_{ij}(0) = 1$), $k = 0$; 
**for** the given weight $\mathbf{w}(k)$ **do**

Solve ISP($\mathbf{w}, \phi, \mathbf{c}$) in (7) to achieve the traffic load $f_{ij}(k)$ for link $(i, j)$;

Solve MCF($\mathbf{w}, \mathbf{d}^t$) in (8) to achieve the routing variable $\mathbf{f}^t(k)$ for destination $t$;

Each link $(i, j) \in \mathcal{E}$ updates its link weight

$$w_{ij}(k+1) = (w_{ij}(k) - \gamma_k(\sum_{t \in \mathcal{D}} f_{ij}^t(k) - f_{ij}(k)))_+;$$

$k \leftarrow k + 1$;

**Until** gap($\mathbf{w}(k), f(k), \mathbf{f}(k)$) < $\epsilon$.

**end for**

The optimal link weights can be computed through Algorithm 1, which is derived from the dual decomposition of TE($\phi, \mathcal{G}, \mathbf{c}, \mathbf{D}$) defined in (5). Given the link weight $\mathbf{w}$ in each iteration, the ISP's problem in (7) and the MCF problem in (8) will be solved to get their own optimal traffic distribution. Then the dual gap

$$\text{gap}(\mathbf{w}(k), f(k), \mathbf{f}(k)) = \sum_{(i,j) \in \mathcal{E}} w_{ij}(k) \left( \sum_{t \in \mathcal{D}} f_{ij}^t(k) - f_{ij}(k) \right)$$

is applied as an optimality measure. Here $\gamma_k$ is the step size and $(z)_+ = \max(0, z)$. If the dual gap is smaller than tolerance $\epsilon$, the iteration will terminate with optimal link weights $\mathbf{w}^*$ and traffic distribution $\mathbf{f}^*$.

These link weights can be directly configured in routes as OSPF link weights. Algorithm 1 is converged because we apply the classic sub-gradient projection method [1] to the dual of TE($\phi, \mathcal{G}, \mathbf{c}, \mathbf{D}$) in (5). Since the traffic matrix changes over time, the frequency of periodically computation and configuration may have
an impact on network overhead and ROD performance. This is a major issue for
our further investigation.

## 4.2 Data Forwarding under ROD

The packet under ROD mechanism is forwarded hop-by-hop along the destination-
based shortest paths, which is the same as in OSPF. The shortest paths are
constructed from the optimal link weights derived from Algorithm 1. In case
that there are multiple equal-cost shortest paths between the same OD pairs,
the flow splitting ratios over these paths can be computed from Algorithm 2.
Taking the optimal traffic distribution $f^*$ derived from Algorithm 1 as input
information, Algorithm 2 first topologically sorts all nodes that are involved in
data forwarding to a certain destination $t$, and then calculates the traffic split-
ting ratio $\tau(s, p, t)$ for each candidate next-hop denoted by $p$. The computational
complexity of Algorithm 2 is $O(N * (N + E))$.

We mentioned the unequal traffic splitting ratios over ECMPs in Section 2.
In hardware level, such traffic splitting scheme is usually realized through a hash-
based mechanism [9]. Therefore, we can configure the hash table with different
weights corresponding to the desired traffic splitting ratios.

<caption>**Algorithm 2 Achieving the splitting ratios**</caption>

Input the optimal traffic distribution $f^*$
**for** each $t \in \mathcal{D}$ **do**
    Define an empty node set $\mathcal{V}$ and an empty link set $\mathcal{L}$
    $\mathcal{V} \leftarrow \mathcal{V} \cup \{t\}$
    **for** each link $(i, j) \in \mathcal{E}$ **do**
        if $i \notin \mathcal{V}$ and $f_{ij}^* > 0$ **then**
            $\mathcal{V} \leftarrow \mathcal{V} \cup \{i\}$ and $\mathcal{L} \leftarrow \mathcal{L} \cup \{(i, j)\}$
        **end if**
    **end for**
    Do topological sorting on $\mathcal{V}$ to get the sorted node set $\mathcal{V}'$
    **for** each node $s \in \mathcal{V}'$ ($s \neq t$) **do**
        $\tau(s, p, t) = f_{sp}^{st} / \sum_{(s,p) \in \mathcal{L}} f_{sp}^{st}$
        $\mathcal{V}' \leftarrow \mathcal{V}' \setminus \{s\}$
    **end for**
    **end for**

# 5 Evaluation

In this section, we evaluate ROD with real and synthetic networks to show its
effectiveness on achieving trade-offs between energy saving and performance.
<table><caption>**Table 1.** Topologies for evaluation</caption><thead><tr><th>Network</th><th>Category</th><th>Nodes</th><th>Links</th><th>Flows</th></tr></thead><tbody><tr><td>Abilene</td><td>Backbone</td><td>11</td><td>28</td><td>110</td></tr><tr><td>Cernet2</td><td>Backbone</td><td>20</td><td>44</td><td>380</td></tr><tr><td>Random</td><td>Random</td><td>50</td><td>230</td><td>50</td></tr></tbody></table>

<table><caption>**Table 2.** Power consumption of line-cards</caption><thead><tr><th>Line-card</th><th>Rate/Mbps</th><th>Energy/W</th></tr></thead><tbody><tr><td>1-Port OC3</td><td>155.52</td><td>60</td></tr><tr><td>8-Port OC3</td><td>1244.16</td><td>100</td></tr><tr><td>1-Port OC48</td><td>2488.32</td><td>140</td></tr><tr><td>1-Port OC192</td><td>9953.28</td><td>174</td></tr></tbody></table>

<figure><img src="image_3.png" /><figcaption>(a) Abilene Network</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>(b) Cernet2 Network</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>(c) Random Network</figcaption></figure>

<caption>**Figure 2.** Trade-offs between MLU and Energy Consumption for Different Topologies</caption>

## 5.1 Experimental Setup

We resort to ns2 simulator [21] to explore the effectiveness of ROD on small- and large-scale topologies. For comparison, hereafter we refer to mechanisms minimizing MLU and energy consumption as MMLU and MEC, respectively.

**Topologies.** The topologies used are summarized in Table 1. The router-level topology of Abilene is available at [16]. For simplicity, we consider the two routers at Atlanta as a single node, the entire network thus has 11 nodes altogether. The Cernet2 is the worldwide largest pure IPv6 research network, which has 44 links with 10 Gbps for 8 core links and 2.5 Gbps for the rest. The Random topology is generated by GT-ITM [20], whose capacity is set to 1 Gbps for each link.

**Traffic Matrices.** For Abilene, we select a subclass of the online available matrices [16], which are measured on March 1st, 2004. The traffic matrix for Cernet2 is generated by the gravity model [15] based on aggregated link load collected from January 10th to 16th, 2010. We generate a sparse traffic matrix for Random through gravity model to achieve a light traffic load scheme.

**Energy Saving Assumptions.** Since line-cards are considered to account for more than 40% of a router's total budget [19], we thus focus on line-cards for energy saving, whose consumption in our evaluation is summarized in TABLE 2. We assume that unloaded line-cards can be automatically put into sleep mode and the time required to enter or wake up from sleep mode is negligible [10].

## 5.2 Performance versus Energy Saving

In this subsection, we explore trade-offs that exist between performance and energy saving potential in ROD. MLU is usually a major concern for ISPs in
<figure><img src="image_6.png" /><figcaption>**Figure 3.** Simulation Results for Abilene on March 1st, 2004</figcaption></figure>

TE and thus employed here as an indicator of network performance. For energy saving indicator, we compute the amount of power consumption of line-cards in each simulation.

For each topology, we vary the green factor $\theta$ to investigate trade-offs between MLU and power consumption, which are plotted in Figure 2. The x-axis represents power consumption of the entire network and the y-axis represents the MLU. For ease of illustration, we use MEC as a benchmark and normalize the value of energy consumption of ROD. We first asterisk discrete points for a set of selected values of $\theta$ and then fit these points to achieve smooth curves.

The result for Abilene in Fig. 2(a) reveals that power consumption varies consistently with $\theta$, whereas MLU decreases as $\theta$ increases. We also notice that, if the MLU threshold of Abilene network is relaxed a bit (e.g., from 16.8% to 17.5%), the power consumption will considerably lower down (e.g., from 1.25 to 1.05). Similar results also hold for Cernet2 and Random.

From the three sub-figures, we also notice two stages, 1) keeping $\theta$ increasing when it is larger than 10 can slightly bring down MLU but dramatically raises up the energy consumption, which we refer to as **power-sensitive** stage; 2) continuing to turn $\theta$ down when it is smaller than 0.1 will make a small contribution to energy saving at the cost of a sharp increase of MLU, which we regard as **performance-sensitive** stage. As both power- and performance-sensitive stages are undesirable for ISPs, we choose three typical values of $\theta$ between these two stages for the following evaluation, namely 0.1, 1 and 10.

In Figure 3 (a), we show how the green factor $\theta$ affects the energy saving potential of Abilene on March 1st, 2004. For each time interval, the power saving ratio is computed with the total power consumption of MMLU as a benchmark. The average energy saving ratio of ROD with $\theta = 0.1$ is about 15%, which is very close to that of MEC and higher than the other two cases with larger $\theta$. The curve with $\theta = 1$ experiences severe oscillation since it can be easily affected by the changes in traffic matrix when equally considering minimizing MLU and power consumption.
<figure><img src="image_7.png" /><figcaption>Figure 4. Sorted Link Utilization for Different Topologies</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Figure 5. CDF of Packet Delay for Different Topologies</figcaption></figure>

## 5.3 Link Utilization

In this subsection, we evaluate the impact of ROD on link utilization that is denoted by *f* in Section 3. Using the Abilene traffic matrices collected for 24 hours, we first explore changes of MLU under each routing mechanism. We present the CDF of MLU of Abilene for a whole day in Figure 3 (b). Since the traffic is light, MLU is always under 40% for all cases. The curves for MMLU and MEC mechanisms act as a lower and higher bound, respectively. The three variations of ROD mechanism with different $\theta$ have slight difference in terms of MLU over temporal scale.

In Figure 4, we explore the utilization of all links for a single traffic matrix, where the x-axis represents the link indices. For Abilene, the traffic of MMLU is more evenly distributed over all links, since nearly 64.3% of the total 28 links achieve the largest utilization. However, MEC goes to the opposite side and concentrates the traffic on fewer links, leaving the minority of the links with much higher utilization. The curves under ROD mechanism with $\theta = 10$ is similar to that of MMLU, whereas the one with $\theta = 0.1$ is close to MEC, leaving the curve with $\theta = 1$ taking the middle place. The cases for Cernet2 and Random are similar, therefore, we do not present Random result due to space limitation.
## 5.4 Packet Delay

In this subsection, we evaluate the propagation delay under ROD. Figure 5 shows CDF of packet delay in different routing mechanisms for Abilene and Cernet2 topologies. For Abilene, MMLU exhibits the higher bound of packet delay, whereas MEC acts as the lower bound. The reason lies in that MMLU may result in undesirable overlong paths in terms of hop counts in order to avoid the highly utilized links. For this reason, the reciprocal of green factor in ROD could be considered as a penalty on the unnecessarily long paths. Therefore, the variation of ROD with a smaller $\theta$ should have a lower packet delay, which is confirmed through the curves in Figure 5(a). Due to space limitation, we omit the discussion on Cernet2 and the similar results to Random topology.

# 6 Related Work

Gupta et al. [8] firstly propose an energy saving approach by shifting network interfaces or devices (e.g., routers) into sleep mode during idle periods. Nedevschi et al. [10] investigate two approaches via sleep and rate adaption. The former approach enables line-cards to sleep between packet bursts while the latter can adjust devices to operate at low frequency when traffic load is light. Vasić et al. [11] consider the above two approaches and present EAte to reduce energy consumption at the expense of increasing massage overhead of routers. In contrast, ROD mechanism is compatible with the current OSPF protocol and thus do not introduce unnecessary message cost.

Zhang et al. [7] have recently proposed an MPLS-based intra-domain traffic engineering mechanism, GreenTE, to maximize the number of links that can be put into sleep mode under given performance constraints. However, GreenTE requires excessive management control to achieve its goal because MPLS tunnels should be frequently set up and adjusted according to the elastic traffic. Panarello et al. [12] put forward a trade-off approach for performance and energy saving in access network. However, since devices in backbone networks consume the large majority of energy [13], we thus focus on exploring trade-off that exists in backbone networks.

# 7 Conclusion

This paper presents Routing On Demand (ROD), which is an OSPF-based routing mechanism that can achieve trade-off solutions to energy-aware TE problem. We theoretically prove that a set of link weights always exists for each trade-off in energy-aware TE objective, under which solutions (i.e., routes) derived from ROD can be converted into shortest paths and realized through OSPF. Evaluation results show that ROD can achieve different trade-offs between energy saving and performance in terms of Maximum Link Utilization (MLU) while maintaining better packet delay than that of energy-ignore TE. The compatibility of ROD with OSPF eases its deployment. Our future work includes
investigating the overhead to realize ROD mechanism as well as the impact of
link failures and traffic bursts.

References

1. Bertsekas, D.P.: Nonlinear Programming, 2nd ed. Athena Scientific, Belmont, MA, USA (1999)

2. Awduche, D.: MPLS and Traffic Engineering in IP Networks. IEEE Communication Magazine 37(12), pp. 42-47 (1999)

3. Wang, Z., Wang, Y., Zhang, L.: Internet Traffic Engineering Without Full Mesh Overlaying. In: IEEE INFOCOM, pp. 565-571 (2001)

4. Sridharan, A., Guérin, R., Diot, C.: Achieving Near-Optimal Traffic Engineering Solutions for Current OSPF/IS-IS Networks. IEEE/ACM Transaction on Networking 13(2), pp. 234-247 (2005)

5. Xu, K., Liu, H., Liu, J., Shen, M.: One More Weight is Enough: Toward the Optimal Traffic Engineering with OSPF. In: IEEE ICDCS, pp. 836-846 (2011)

6. Candès, E.J., Tao, T.: Decoding by Linear Programming. IEEE Transactions on Information Theory 51(12), pp. 4203-4215 (2005)

7. Zhang, M., Yi, C., Liu, B., Zhang, B.: GreenTE: Power-Aware Traffic Engineering. In: IEEE ICNP, pp. 21-30 (2010)

8. Gupta, M., Singh, S.: Greening of the Internet. In: ACM SIGCOMM, pp. 19-26 (2003)

9. Cao, Z., Wang, Z., Zegura, E.: Performance of Hashing-Based Schemes for Internet Load Balancing. In: IEEE INFOCOM, pp. 332-341 (2000)

10. Nedevschi, S., Popa, L., Iannaccone, G., Ratnasamy, S., Wetherall, D.: Reducing Network Energy Consumption via Sleeping and Rate-Adaptation. In: USENIX NSDI, pp. 323-336 (2008)

11. Vasić, N., Kostić, D.: Energy-Aware Traffic Engineering. In: The 1st International Conference on Energy-Efficient Computing and Networking, pp. 169-178 (2010)

12. Panarello, C., Lombardo, A., Schembra, G., Chiaraviglio, L., Mellia, M.: Energy Saving and Network Performance: a Trade-off Approach. In: The 1st International Conference on Energy-Efficient Computing and Networking, pp. 41-50 (2010)

13. Tucker, R., Baliga, J., Ayre, R., Hinton, K., Sorin, W.: Energy Consumption in IP Networks. In: ECOC Symposium on Green ICT, pp. 1-1 (2008)

14. Applegate, D., Cohen, E.: Making Intra-domain Routing Robust to Changing and Uncertain Traffic Demands: Understanding Fundamental Tradeoffs. In: ACM SIGCOMM, pp. 313-324 (2003)

15. Roughan, M., Greenberg, A., Kalmanek, C., Rumsewicz, M., Yates, J., Zhang, Y.: Experience in Measuring Backbone Traffic Variability: Models, Metrics, Measurements and Meaning. In: ACM SIGCOMM Internet Measurement Workshop, pp. 91-92 (2002)

16. Yin Zhang's Abilene TM, http://www.cs.utexas.edu/~yzhang/research/AbileneTM/

17. Katz, D., Kompella, K., Yeung, D.: RFC 3630: Traffic Engineering (TE) Extensions to OSPF Version 2, http://www.ietf.org/rfc/rfc3630.txt

18. Moy, J.: RFC 2328 OSPF Version 2, http://tools.ietf.org/html/rfc2328.txt

19. Power Management for the Cisco 12000 Series Router, http://www.cisco.com/en/US/docs/ios/12_0s/feature/guide/12spower.html

20. GT-ITM, http://www.cc.gatech.edu/projects/gtitm/

21. Network Simulator 2, http://www.isi.edu/nsnam/ns/