Improving Service Differentiation in IP Networks through Dual

University of Pennsylvania

ScholarlyCommons

Departmental Papers (ESE) Department of Electrical & Systems Engineering

10-23-2007

Improving Service Differentiation in IP Networks

through Dual Topology Routing

Kin-Wah (Eric) Kwong

University of Pennsylvania, [email protected]

Roch A. Guérin

University of Pennsylvania, [email protected]

Anees Shaikh

IBM Corporation

Shu Tao

IBM T.J. Watson Research Center

Postprint version. Paper to be presented at ACM CoNEXT 2007 Conference, December 2007, 12 pages.

This paper is posted at ScholarlyCommons. http://repository.upenn.edu/ese_papers/303

For more information, please contact [email protected].

Improving Service Differentiation in IP Networks through

Dual Topology Routing

∗

Kin-Wah Kwong, Roch Guérin

University of Pennsylvania

{kkw@seas, guerin@ee}.upenn.edu

Anees Shaikh, Shu Tao

IBM T.J. Watson Research Center

{aashaikh@watson, shutao@us}.ibm.com

ABSTRACT

The convergence on IP of a wide variety of trafﬁc types has

strengthened the need for service differentiation. Service

differentiation relies on two equally important components:

(i) resource allocation, i.e., what resources does a given ser-

vice class have access to; and (ii) contention resolution, i.e.,

how is access to shared resources arbitrated between ser-

vices classes. The latter has been well studied with numer-

ous mechanisms, e.g., scheduling and buffer management,

supporting it in modern routers. In contrast, relatively few

studies exist on the former, and in particular on the impact

of routing that determines the resources a given service class

is assigned to. This is the focus of the paper, which seeks to

investigate how routing inﬂuences a network’s ability to efﬁ-

ciently support different service classes. Of particular inter-

est is the extent to which the ability to route service classes

separately is beneﬁcial. This question is explored for a base

conﬁguration involving two classes with either similar or en-

tirely different service objectives (cost functions). The pa-

per’s contributions are in demonstrating and quantifying the

beneﬁts that the added ﬂexibility of different (dual) routing

affords, and in developing an efﬁcient heuristic for comput-

ing jointly optimal routing solutions. The former can mo-

tivate the deployment of newly standardized multi-topology

routing (MTR) functionality. The latter is a key enabler for

the effective use of such capability.

1. INTRODUCTION

IP networks today carry traﬃc of diﬀerent types,

characteristics, and performance requirements. For in-

stance, many ISP’s are using IP networks to deliver

∗

The work of Kin-Wah Kwong and Roch Gu´erin was sup-

p orted by NSF grant CNS-0627004.

Permission to make digital or hard copies of all or part of this work for

personal or classroom use is granted without fee provided that copies are

not made or distributed for proﬁt or commercial advantage and that copies

bear this notice and the full citation on the ﬁrst page. To copy otherwise, to

republish, to post on servers or to redistribute to lists, requires prior speciﬁc

permission and/or a fee.

CoNEXT’07, December 10-13, 2007, New York, NY, U.S.A.

bundled services that include performance-sensitive ap-

plications, such as voice and video, as well as the more

“elastic” data services. Large enterprises also rely heav-

ily on IP networks to transfer a mix of both critical (e.g.,

data center backup) and non-critical data for their busi-

ness needs. To better support such mixed traﬃc, service

diﬀerentiation is often necessary or at least desirable.

Service diﬀerentiation is widely available in modern

routers, e.g., in the form of scheduling and buﬀer man-

agement mechanisms that arbitrate between service classes

in the presence of resource contention. Although “con-

tention resolution” is a critical component in support

of service diﬀerentiation, it does little to ensure that a

network delivers the best possible services to the diﬀer-

ent service classes it supports, i.e., minimizes the onset

of contention whenever possible. In IP networks, this is

largely controlled by routing that determines how net-

work resources (link bandwidth) are assigned to carry

diﬀerent traﬃc ﬂows. In order to optimize routing for

the expected traﬃc demand, network operators often

employ traﬃc engineering (TE) algorithms to determine

the paths, which are then implemented using shortest-

path routing protocols, such as OSPF or IS-IS.

We investigate the performance beneﬁts of diﬀerent

routing schemes using this traditional TE framework,

but with two traﬃc classes (i.e., high and low priority).

We assume a simple contention resolution mechanism—

priority queueing (i.e., a separate queue is maintained

on each link for each service class, and higher priority

classes are always served ﬁrst). When using common

TE approaches in a priority queueing environment, it

is straightforward to optimize performance of the high-

priority traﬃc. However, as we show, such optimized

performance often comes at the expense of low-priority

traﬃc, whose performance may be severely degraded.

Ideally, we seek a routing scheme that ensures the best

performance for high-priority traﬃc, while still main-

taining reasonable performance for low-priority traﬃc.

In this paper, we develop a practical routing scheme

that achieves the goal of improving support for service

diﬀerentiation in IP networks. Our approach is based

on multi-topology routing (MTR), in which diﬀerent

routings are computed for diﬀerent service classes, al-

lowing greater ﬂexibility in exploiting available network

resources to meet their service goals. In traditional IP

networks, a single weight is assigned to each link, which

produces a single routing that is used to forward packets

of all traﬃc classes. We refer to this traditional routing

scheme as single-topology routing (STR). In contrast,

MTR allows multiple weights on each link, and hence

a corresponding number of diﬀerent routings that can

each be assigned to separate service classes. MTR is be-

ing standardized [1] and is becoming available on a num-

ber of router platforms. In our investigation, we limit

ourselves to two topologies, i.e., two distinct weights

on each link, and denote the resulting routing as dual-

topology routing (DTR). In DTR, high-priority traﬃc

is routed using one set of link weights, and low-priority

traﬃc routed using the other.

While the increased routing ﬂexibility of DTR is clearly

beneﬁcial when compared to STR, those beneﬁts come

at a cost. The ﬁrst is the higher complexity of identify-

ing good sets of link weights. This is because the solu-

tion space to explore is exponentially larger than with

STR (each assignment of link weights for one traﬃc

class needs to be evaluated for all possible combinations

of links weights for the other traﬃc class). Furthermore,

the objective functions that need to be optimized by

selecting link weights are often diﬀerent for each traf-

ﬁc class. For example, two commonly used objective

functions include one that is based on link utilization

and seeks to minimize the average overall network de-

lay, and a second that involves Service Level Agree-

ments (SLAs) in the form of delay bounds that need

to be met for each “user” (pairs of source and destina-

tion nodes). Computing weight settings that optimize

various combinations of such objective functions can be

challenging. As a result, realizing any of the beneﬁts of

DTR calls for developing computationally tractable ap-

proaches for ﬁnding good combinations of link weights

across these many diﬀerent scenarios. Another cost of

DTR over STR is in the added conﬁguration and com-

putational overhead it imposes on routers, because of

the need to conﬁgure and disseminate multiple weights

for each link and run multiple SPF algorithms in the

presence of network changes.

Given the costs associated with DTR, it is vital to

both provide techniques to mitigate them when pos-

sible, and equally important to quantify the magni-

tude of the improvements achievable with DTR. The

paper makes contributions toward both of these issues,

ﬁrst by developing an eﬃcient heuristic for computing

good weight settings for DTR in the presence of var-

ious objective functions, and second by performing a

comprehensive assessment of the performance beneﬁts

that DTR can aﬀord. Through extensive simulations,

we show that DTR is able to provide substantial perfor-

mance improvements, especially for low-priority traﬃc,

when compared with STR. These beneﬁts are consis-

tent across a number of topologies, network sizes, traf-

ﬁc patterns, and objective functions in the optimization

formulation.

The rest of this paper is structured as follows. Sec-

tion 2 provides some background on multi-topology rout-

ing and reviews a few related works. Section 3 formu-

lates the problem and introduces the two objective func-

tions considered in our problem setting. Section 4 de-

scribes the heuristic algorithm designed for link weight

computation in DTR. Section 5 applies this algorithm

to a wide set of network topologies and traﬃc patterns,

and provides an in-depth discussion of when and why

DTR can oﬀer substantial performance improvements

above and beyond STR-based solutions. Section 6 sum-

marizes our ﬁndings and concludes the paper.

2. RELATED WORK

The problem of ﬁnding optimal link weight settings in

IP networks that rely on destination-based, SPF routing

was ﬁrst studied in [2], where the problem was identiﬁed

as NP-hard and a local search heuristic was proposed.

Several other heuristics, e.g., [3, 4], were later developed

as extensions to this work. Nucci et al. [5] studied a

similar problem, and their goal was to compute a link

weight setting that both met SLA requirements and was

robust to link failures. All these works consider routing

of only a single traﬃc class, i.e., an STR setting.

The use of MTR for traﬃc engineering purposes was

proposed in [6] based on dividing traﬃc matrix into

smaller “slices”, each routed on a separate topology—

the greater the number of slices, the better the perfor-

mance as it increases the ability to approximate optimal

routing. Recently, the use of MTR has been proposed

to improve the resiliency of IP routing [7, 8, 9], with

diﬀerent topologies oﬀering backup routes for diﬀerent

failure scenarios. Our work diﬀers from these earlier

contributions in that we focus on assessing MTR’s ben-

eﬁts in a network that oﬀers service diﬀerentiation.

Also related to our work are studies on QoS routing

for optimizing multi-class traﬃc p erformance, e.g., [10,

11, 12, 13, 14, 15]. However, even though they con-

sider the problem of optimizing network p erformance

across multiple traﬃc classes and performance objec-

tives, these works focus on a ﬂow-oriented environment

where the goal is to minimize the blocking probabil-

ity of high-priority requests [14, 15]. In contrast, in

this paper we assume the standard destination/SPF

based routing/forwarding paradigm of traditional IP

networks. Similarly, works on multi-class TE in MPLS

[16, 17] have also tackled the problem of network op-

timization in the presence of diﬀerent traﬃc classes.

However, they again diﬀer from the work of this paper

because of the ﬂow-oriented nature of MPLS networks.

3. PROBLEM FORMULATION

We model the network as a directed graph G = (V, E)

with node set V and edge set E, and C

denotes the ca-

pacity of edge (i, j) ∈ E. The traﬃc from the high- and

low-priority classes are speciﬁed through two traﬃc ma-

trices, T

= [r

(s, t)]

|V |×|V |

and T

= [r

(s, t)]

|V |×|V |

respectively, where r

(s, t) and r

(s, t) represent the

volume of high- and low-priority traﬃc originating at

node s and destined for node t, with r

(s, s) = r

(s, s) =

0, ∀s ∈ V .

As mentioned earlier, the contention resolution mech-

anism used to diﬀerentiate b etween service classes is a

simple two-priority queueing scheme. The high-priority

queue is always served ﬁrst, hence the low-priority traf-

ﬁc only sees the residual capacity left by the high-priority

traﬃc. For example, if link l with capacity C

is carry-

ing H

units of high-priority traﬃc, the residual capacity

seen by the low-priority traﬃc is

= max(C

− H

, 0).

When computing “good” weight settings, we focus on

two cost/objective functions that are commonly used in

practice in IP networks.

3.1 Load-based cost function

We ﬁrst consider a load-based cost function that seeks

to minimize the overall queueing delay each traﬃc class

experiences in a network. Our model is a generalized

version of that of [2]. Speciﬁcally, we assume that the

performance of both traﬃc classes on a link can be mod-

eled by an M/M/1 model. Using the piecewise linear

approximation suggested in [2], we deﬁne the cost in-

curred by the high-priority traﬃc on link l as

H,l











(1a)

− 2/3C

(1b)

10H

− 16/3C

(1c)

70H

− 178/3C

6 1 (1d)

500H

− 1468/3C

, 1 6

(1e)

5000H

− 16318/3C

(1f)

where H

denotes the amount of high-priority traﬃc on

link l. Similarly, the cost incurred by the low-priority

traﬃc on link l, Φ

L,l

, can be deﬁned by replacing H

with the amount of low-priority traﬃc on link l, L

and C

with the residual capacity on link l seen by the

low-priority traﬃc,

Based on the above deﬁnitions, we deﬁne the overall

cost for the two traﬃc classes, denoted by Φ

and Φ

as the sum of all link costs, i.e., Φ

l∈E

H,l

and

l∈E

L,l

. Our goal is to minimize Φ

and Φ

while preserving the priority precedence between the

traﬃc classes. We, therefore, deﬁne a lexicographical

optimization function such that the high-priority traﬃc

is optimized ﬁrst. Speciﬁcally, our goal is to

minimize A = hΦ

, Φ

i (2)

Note that we use the notation h·, ·i to denote a lexico-

graphically ordered tuple. Namely, hx

, y

i > hx

, y

if and only if x

> x

, or x

= x

and y

> y

. In other

words, we optimize ﬁrst for the high-priority traﬃc and

then for the low-priority traﬃc.

3.2 SLA-based cost function

Another commonly used cost function is based on

Service Level Agreements (SLA’s) [5]. SLA’s are typ-

ically deﬁned in the form of end-to-end delay targets

for each source-destination (SD) pair. SLA-based cost

functions are particularly meaningful for high-priority

traﬃc, as customers of this service class pay a premium

for their service. Typically, whenever an SLA is vio-

lated, a provider pays a certain penalty back to its cus-

tomers. There is, therefore, a strong incentive on the

provider’s part to select a routing that minimizes the

chance of such occurrences.

The second cost function we consider reﬂects such an

objective. Speciﬁcally, its goal is to ensure that delay

performance targets are met for all the high-priority

traﬃc SD pairs. Delay consists of both queueing and

propagation delays contributed by all links on the path

used by a given SD pair. Speciﬁcally, the average de-

lay D

(seen by high-priority traﬃc) on link l can be

computed as

− H

+ 1

+ p

≈

H,l

+ 1

+ p

(3)

where s is the average packet size, p

is the propagation

delay of link l. Note that we use Φ

H,l

to approximate

/(C

− H

) [18].

Let ξ

(s,t)

be the average end-to-end delay for SD pair

(s, t). Suppose the SLA delay bound of any SD pair is

θ > 0. We deﬁne the cost function for the high-priority

traﬃc between SD pair (s, t) as

(s,t)

0, if ξ

(s,t)

6 θ (4a)

a + b(ξ

(s,t)

− θ), Otherwise (4b)

Here, a and b are two positive parameters that deter-

mine the SLA penalty; a is a constant penalty incurred

by any SLA violation, while b represents the penalty

ratio associated with delay in excess of the SLA bound.

Without loss of generality, we choose a = 100 and b = 1.

The overall cost function for the high-priority traﬃc is

then deﬁned as Λ :=

(s,t)∈V ×V

(s,t)

. In other words,

Λ can be considered as the total amount of penalty that

the provider pays back to customers because of SLA vi-

olations.

For the low priority traﬃc, we continue to use the

load-based cost function Φ

deﬁned in Section 3.1. In

keeping with the lexicographical ordering that gives prece-

dence to the high-priority traﬃc cost function, our goal

is now to

minimize S = hΛ, Φ

i (5)

3.3 Discussions

3.3.1 On the feasibility of a joint cost function

A natural question when considering an optimization

problem consisting of multiple cost functions, i.e., for

diﬀerent service classes, is to explore whether a unique,

joint cost function can be deﬁned to facilitate the se-

lection of a routing solution

that accurately captures

the goals of the original individual cost functions. One

such possibility is a joint cost function of the form J :=

αΦ

+ Φ

or J := αΛ + Φ

, where by varying α > 0 a

diﬀerent trade-oﬀ can be realized between the two ser-

vice classes. When setting α → ∞, J defaults back

to the earlier lexicographical cost function. A similar

joint cost function was proposed in [19], for a conﬁg-

uration where the two objectives being combined were

performance and reliability instead of the performance

of diﬀerent service classes as is the case here.

In spite of the attractiveness of such an approach,

especially in terms of computational simplicity

, iden-

tifying how to select α in order to realize a given per-

formance trade-oﬀ for high- and low-priority traﬃc is

challenging. Setting α to too low a value can result in a

“priority inversion” in the sense that some high-priority

traﬃc can see relatively poor performance compared to

what low-priority traﬃc sees overall. This violates the

concept of “high priority” and the associated ordering

among traﬃc classes. Conversely, choosing too large a

value for α yields little beneﬁts compared to a lexico-

graphical ordering solution, and in general identifying

a value of α that works well across all conﬁgurations is

a challenging task. This is especially so when dealing

with diﬀerent cost functions across service classes, as

identifying how to “add” quantities that are expressed

in diﬀerent units is at best un-intuitive. We brieﬂy illus-

trate these diﬃculties next through a simple example.

Consider a 3-node triangular network (A, B and C),

as shown in Fig. 1. The capacity of each link is 1 unit,

and 1/3 and 2/3 units of high- and low-priority traf-

ﬁc, respectively, originate at node A destined for node

C. Consider J := αΦ

+ Φ

, where α = 35. Under

STR, both traﬃc classes then use link A − C to min-

Note that the use of a joint cost function only makes sense

in a setting where STR is used. If DTR is available, because

each class can be routed independently, there is no beneﬁt

in coupling their routing through a joint cost function.

A purely lexicographical optimization calls for identifying

“all” routings that minimize the ﬁrst cost function, and then

select the one that yields the best value for the second. With

a joint cost function, a single optimization is instead per-

formed.

Figure 1: A simple 3-node network

imize J, which results in Φ

= 1/3 and Φ

= 64/9.

This solution is the same as lexicographically minimiz-

ing A = hΦ

, Φ

i and maintains the priority prece-

dence among the two traﬃc classes. However, the low-

priority traﬃc performance is very poor, so that one

may want to improve it by lowering α to, say, α = 30.

The solution that minimizes J then calls for evenly

splitting both high- and low-priority traﬃc over links

A−B and A−C, which yields Φ

= 1/2 and Φ

= 4/3.

This improves Φ

by 81%, but also degrades Φ

50%, which results in a “priority inversion” that vio-

lates the implicit precedence given to high priority traf-

ﬁc. This illustrates how diﬃcult it is to select a value

of α such that both traﬃc classes achieve good perfor-

mance, and matters are even worse when considering

more complex topologies and diﬀerent combinations of

traﬃc loads and patterns.

3.3.2 STR with trade-off between trafﬁc classes

Our performance goal is formulated as a lexicograph-

ical optimization, which gives strict precedence to the

performance of high-priority traﬃc. With DTR the im-

pact of this strict precedence is “softened” by giving

low-priority traﬃc control on its own routing once the

high-priority routing has been set. A natural question is

then whether similar beneﬁts are achievable with STR

by slightly relaxing the precedence rule.

For load-based cost functions, this can be realized as

follows: Denote the minimum cost for high-priority traf-

ﬁc as Φ

∗

; one may then allow STR solutions that satisfy

≤ (1 + ε)Φ

∗

, ε > 0. In other words, we allow all

routing solutions that do not degrade the performance

of high-priority traﬃc by more than ε. This increases

the number of routing solutions that can be considered,

hence improving the odds of ﬁnding one that yields bet-

ter performance for low-priority traﬃc. The parameter

ε, allows us to tune how much high-priority performance

we are willing to sacriﬁce to improve low-priority per-

formance. For an SLA-based cost function, a similar

trade-oﬀ can be realized simply by increasing the high-

priority delay bound to (1 + ε)θ. As ε grows, more STR

routing solutions satisfy the SLA; hence again increas-

ing the odds of ﬁnding one that yields b etter perfor-

mance for low-priority traﬃc.

As we shall see, while such relaxation can help im-

prove the overall performance of STR, it does not come

anywhere near what is achievable through DTR. We

expand on this in Section 5.3.

4. HEURISTIC SEARCH FOR DTR LINK

WEIGHT ASSIGNMENT

For most cost functions, including the two we se-

lected, ﬁnding an optimal link weight setting in STR

is an NP-hard problem [2]. As alluded to earlier, the

problem is even more complex with DTR since in each

possible weight conﬁguration for the high-priority traf-

ﬁc, there are exponentially many possible weight set-

tings for the low-priority traﬃc. To address the prob-

lem of computing good sets of link weights for DTR, we

develop the following heuristic algorithm.

Let W = {W

, W

} be the set of link weights for

DTR, where W

l∈E

and W

l∈E

denote the sets of link weights for the high- and low-

priority traﬃc, respectively. Our goal is to ﬁnd W

that minimizes our lexicographical objective function L,

where L = A (Eq. (2)) or L = S (Eq. (5)). The heuris-

tic is an iterative algorithm. As shown in Algorithm 1,

it consists of three routines: The ﬁrst minimizes the

high-priority traﬃc cost; the second minimizes the low-

priority traﬃc cost, and the third reﬁnes the solution

obtained from the ﬁrst two. Details on each routine are

provided next.

In the ﬁrst routine (from lines 3 to 12), the high-

priority traﬃc performance is optimized by searching

for a good weight setting W

(see subroutine FindH)

given a set of initial link weights for the low-priority

traﬃc, i.e., W

remains unchanged as W

is optimized.

In the second routine (from lines 15 to 24), W

is set

to the best setting W

H∗

obtained in the ﬁrst routine,

and the low-priority link weights are optimized. After

completion of the ﬁrst two routines, a reasonably good

link weight setting W

∗

= {W

H∗

, W

L∗

} has been iden-

tiﬁed. However, additional improvements are possible,

and the third routine (from lines 27 to 38) is used as a

reﬁnement step that searches for better overall solutions

in a small neighborhood around W

∗

= {W

H∗

, W

L∗

In Algorithm 1, diversiﬁcation is also used to let the

search “escape” from a local optimum if there is no cost

improvement in M iterations. A small fraction (g

and

) of weights in W

and W

are randomly perturbed

in the ﬁrst and second routines respectively (in lines 9

and 21). In the third routine, the diversiﬁcation proce-

dure (from lines 33 to 36) randomly perturbs a smaller

fraction ( g

) of link weights in b oth W

and W

, so

that the search re-starts from a solution sightly diﬀerent

from W

∗

, while preventing it from jumping to a very

sub-optimal one.

The FindH subroutine is shown in Algorithm 2. The

subroutine ﬁrst deﬁnes a “neighborhood” for the cur-

rent solution W , and then evaluates solutions in this

neighborhood to ﬁnd the best one to replace W . A

neighborhood is deﬁned as follows. With the current

solution W , each link l is associated with a lexicograph-

ical cost L

, where L

:= hΦ

H,l

, Φ

L,l

i (resp. L

, Φ

L,l

i) if L = A (resp. L = S). Links are then

sorted in decreasing order of cost. Intuitively, we want

to increase the weight of links with high cost to route

traﬃc away from them, and decrease the weight of links

with low cost to attract more traﬃc onto them [5]. In

our heuristic, we select m high-cost links and m low-

cost links to form two sets, A and B. A neighbor of the

current solution W is identiﬁed by randomly selecting a

link from A (resp. B) and increasing (resp. decreasing)

its weight, both without replacement. As a result, m

such neighbors can be identiﬁed to form the neighbor-

hood of W . Note that it is not always good to change

the weights of the links with the highest or lowest cost,

because this may lead to situations where only a few

links are perturbed, so that only a small part of the

solution space is explored. To avoid this problem, we

introduce one more randomization for link selection in

FindH (as shown in lines 2 to 4 in Algorithm 2). We

deﬁne two integers k

and k

randomly drawn from a

heavy-tail probability distribution P (k ) ∝ k

−τ

, where

1 6 k 6 n − m + 1 and n is the total number of links in

the network [20]. Based on this distribution, if τ → 0,

links in A and B are selected independent of their costs,

while if τ → ∞, only those links with the highest or low-

est costs are included in A and B. In our study, we use

τ = 1.5 so that all links have a chance of being chosen,

while keeping some preference for selecting links with

very high or low costs.

The routine FindL is similar to FindH except that

we use Φ

L,l

for sorting links, because W

has no eﬀect

on the high-priority traﬃc. For brevity, we omit the

pseudo-code for FindL.

5. EVALUATION AND FINDINGS

In this section, we evaluate the performance bene-

ﬁts of DTR over STR solutions. Our evaluation spans

a broad range of network settings, including diﬀerent

topologies, traﬃc patterns and intensity levels. Our

goal is to investigate when DTR is worth deploying

(given its added complexity), and in particular whether

the use of diﬀerent performance objectives for the two

traﬃc classes plays a major role.

5.1 Evaluation settings

5.1.1 Network topology

We use three diﬀerent types of topologies:

• Random topology: generated by randomly adding

links between nodes in a network, all nodes have

similar link degrees.

• Power-law topology: generated using the preferen-

Algorithm 1: DTR Weight Search

Input: Network topology, traﬃc matrix, initial link weight

setting W

Result: Best link weight setting W

∗

W ← W

, W

∗

← W

∗

← L(W

); Iteration ← 02

while Iteration<N do3

W ← FindH()4

if L(W ) < L

∗

then5

∗

← L(W ), W

∗

← W6

end7

if No improvement in L

∗

after M iterations then8

Randomly perturb g

(%) of link weights in W

end10

Iteration++11

end12

Iteration ← 013

← W

H∗

while Iteration<N do15

W ← FindL()16

if Φ

(W ) < Φ

∗

then17

∗

← Φ

(W ), W

∗

← W18

end19

if No improvement in Φ

∗

after M iterations then20

Randomly perturb g

(%) of link weights in W

end22

Iteration++23

end24

W ← W

∗

Iteration ← 026

while Iteration<K do27

W ← FindH()28

W ← FindL()29

if L(W ) < L

∗

then30

∗

← L(W ), W

∗

← W31

end32

if No improvement in L

∗

after M iterations then33

W ← W

∗

Randomly perturb g

(%) of link weights in both35

and W

end36

Iteration++37

end38

tial attachment model [21] to emulate the power-

law degree distribution observed in the Internet

topology [21, 22].

• ISP top ology: emulating a North American back-

bone network consisting of 16 nodes and 70 links.

In our study, all link capacities are set equal to 500

Mbps. For the evaluation of the SLA-based cost func-

tion, we also need to assign propagation delays to links.

For synthesized (i.e., random and power-law) topolo-

gies, the propagation delay of each link is randomly

selected in the range of 1.2ms and 15ms. This ensures

that the simulated links range from very short links to

long-haul (coast-to-coast) links. For the ISP topology,

we assign a propagation delay between 8ms and 15ms

to each link, based on the geographical locations of the

corresponding nodes. Unless speciﬁed otherwise, the

SLA delay bound is set to θ = 25ms.

Algorithm 2: FindH()

Input: Current link weight setting W

Sort the links in the decreasing order of their lexicographical1

link costs, i.e. L

Π(1)

> L

Π(2)

> . . . > L

Π(n)

, where Π (·)

means p ermutation.

Draw two random integers, k

and k

, from the distribution2

P (k) where 1 6 k 6 n − m + 1.

Select m links with ranks3

Π (k

) , Π (k

+ 1) , . . . , Π (k

+ m − 1) to form a set A.

Select m links with ranks4

Π (n + 1 − k

) , Π (n − k

) , . . . , Π (n − k

− m + 2) to form

a set B.

A neighbor is deﬁned as randomly selecting a link l from A5

and a link l

from B, both without replacement. Then we

increase W

and decrease W

. Construct m neighbors as

the ab ove manner.

Find the best neighbor, denoted by W , from the6

neighborhood.

if L

< L (W ) then

return W .8

else9

return W .10

end11

5.1.2 Trafﬁc matrix

The traﬃc matrices T

= [r

(s, t)]

|V |×|V |

and T

(s, t)]

|V |×|V |

, which correspond to the high- and low-

priority traﬃc classes, are speciﬁed as follows.

The low-priority traﬃc matrix T

is generated using a

gravity model [23, 24, 5]. Speciﬁcally, the traﬃc volume

from node s to node t is deﬁned as

(s, t) = d

i∈V \{s}

(6)

where d

is the total traﬃc originating at node s, given







Uniform(10, 50), with prob 0.6 (7a)

Uniform(80, 130), with prob 0.35 (7b)

Uniform(150, 200), with prob 0.05 (7c)

Here, Uniform(a,b) denotes a random variable uniformly

distributed in [a, b], V

is a random variable uniformly

distributed in [1, 1.5], and can be considered the “mass”

of node t. The larger a node’s mass, the more traﬃc it

attracts. Using d

, we generate a heterogeneous traﬃc

demand model with three diﬀerent levels: (1) low traﬃc

volume originating from 60% of the nodes, (2) medium

traﬃc volume originating from 35% of the nodes, and

(3) high traﬃc volume originating from 5% of the nodes

to emulate “hot spots” in the network.

We consider two diﬀerent models for high-priority

traﬃc. The ﬁrst is a random model, in which we ran-

domly select a fraction (k) of SD pairs to generate high-

priority traﬃc. In other words, k represents the density

of high-priority SD pairs. The second is a sink model

that emulates “popular” servers, e.g,. data centers that

are destinations for a large number of client nodes. In

our simulation, a small number of sinks were selected

among nodes with the highest degree. Then, a larger

number of client nodes are selected, and bi-directional

traﬃc is assumed between sinks and client nodes.

The volume of high-priority traﬃc is speciﬁed in pro-

portion to the total network traﬃc volume. Speciﬁcally,

0 < f < 1 denotes the fraction of the total traﬃc volume

that corresponds to high-priority traﬃc. In other words,

if the high- and low-priority traﬃc volumes are η

and

respectively, f = η

/(η

+ η

). The high-priority

traﬃc volume between nodes s and t is then generated

as follows. We ﬁrst assign a uniformly distributed ran-

dom variable, m

(s,t)

∈ [1, 4], to SD pair (s, t). Given

that the total volume of low-priority traﬃc is η

s,t∈V

(s, t), the volume of high-priority traﬃc be-

tween SD pair (s, t) is set as r

(s, t) = η

1−f

(s,t)

i,j∈V

(i,j)

This not only ensures that the total high-priority traﬃc

is a fraction f of the total network traﬃc, but also gen-

erates a heterogeneous traﬃc volume among diﬀerent

high-priority SD pairs.

5.1.3 Heuristic algorithm settings

In our heuristic algorithm, we deﬁne link weights to

be between 1 and 30. The relatively small maximum

link weight is selected as a trade-oﬀ between the eﬀec-

tiveness of the resulting routing solutions and compu-

tational complexity.

Algorithm 1 uses two variables N and K to control

the number of iterations of each routine. In this study,

we select N = 300000 and K = 800000. In each itera-

tion, the heuristic evaluates m = 5 neighbors. We also

choose g

= g

= 5% and g

= 3% for the diversiﬁ-

cation phases of the three routines of Algorithm 1; g

is smaller because this routine is computationally more

complex. The diversiﬁcation interval is set to M = 300.

Extensive investigations [25] have shown that these are

suﬃcient to generate good link weight settings for the

topologies considered in this paper.

To compare the performance of DTR with that of

STR, we adopt the “single weight change” heuristic pro-

posed in [2] to generate STR link weight settings to

minimize the objective functions of Eqs. (2) and (5).

5.2 Performance beneﬁt of DTR

In this section, we evaluate the performance beneﬁts

of DTR over STR. The focus is not only on quantifying

the beneﬁts of DTR, but also on identifying the scenar-

ios where the diﬀerence is more signiﬁcant. Because of

space limitations, we only include a representative set of

results. Results for many other conﬁgurations are avail-

able in [25], and are consistent with the subset reported

here.

A general and expected observation is that across

topologies, the performance of high-priority traﬃc un-

der DTR and STR is comparable, while the perfor-

mance of low-priority traﬃc is signiﬁcantly better un-

der DTR. This holds for both cost functions of Sec-

tion 3. This can be explained as follows: For either load-

based or SLA-based cost functions, the combination of

lexicographical optimization and priority queueing en-

sures that under both STR and DTR the performance

of high-priority traﬃc is optimized ﬁrst. Furthermore,

it also ensures that the high-priority traﬃc is imper-

vious to the behavior of low-priority traﬃc, whether

routed identically or diﬀerently. In contrast, because

STR routes the low-priority traﬃc over the same set

of links as the high-priority traﬃc, it tends to experi-

ence higher link loads, hence higher cost. DTR gives it

the ﬂexibility to be routed away from overloaded links,

hence lowering its cost. To illustrate this eﬀect, we plot

in Fig. 3 the distribution of link utilization (with both

high- and low-priority traﬃc) in a random topology for

the load- and SLA-based cost functions respectively

As shown in the ﬁgure, DTR yields signiﬁcantly fewer

overloaded links than STR does.

To further demonstrate the beneﬁts of DTR, Fig. 2

shows for three diﬀerent topologies the cost ratios R

and R

(computed as the cost under STR over the

cost under DTR) for high- and low-priority traﬃc, us-

ing load- and SLA-based cost functions, respectively.

For all three topologies, the total traﬃc demand (rep-

resented by the average link utilization

) is varied by

scaling the traﬃc matrix. As can be seen from the ﬁg-

ures, R

is approximately equal to 1, while R

can be

relatively large.

In our simulations, we also ﬁnd that the beneﬁts of

DTR can be aﬀected by several factors, including net-

work load and traﬃc patterns. Some of our major ﬁnd-

ings are summarized as follows

• DTR outperforms STR the most when the network

is moderately loaded. The diﬀerence decreases

when network load is either light or heavy;

• The performance beneﬁts of DTR are more signif-

icant when the network carries more high-priority

traﬃc;

• When the density of high-priority SD pairs in-

creases, we observe opposite behaviors for the cost

functions under consideration: the beneﬁts of DTR

decrease for load-based cost function, but increase

under SLA-based cost function;

• High-priority traﬃc patterns also aﬀect the perfor-

mance of DTR. When high-priority traﬃc is con-

centrated “locally” on a small set of nodes, the

performance beneﬁts of DTR are less pronounced.

Fig. 3 is a “stacked” bar chart so that the DTR bars are

drawn on top of the STR bars and do not overlap.

Because the average link utilization is roughly equal under

DTR and STR, we use it as a reference of network load.

Since we always have R

≈ 1, we focus only on R

0.5 0.6 0.7 0.8 0.9

Average link utilization

Ratio of STR cost to DTR cost

H−cost ratio

L−cost ratio

(a) Random topology

0.4 0.5 0.6 0.7 0.8

Average link utilization

Ratio of STR cost to DTR cost

H−cost ratio

L−cost ratio

(b) Power-law topology

0.4 0.5 0.6 0.7 0.8

Average link utilization

Ratio of STR cost to DTR cost

H−cost ratio

L−cost ratio

0.5 0.55 0.6 0.65 0.7 0.75

Average link utilization

Ratio of STR cost to DTR cost

H−cost ratio

L−cost ratio

(d) Random topology

0.4 0.45 0.5 0.55 0.6 0.65

Average link utilization

Ratio of STR cost to DTR cost

H−cost ratio

L−cost ratio

(e) Power-law topology

0.4 0.5 0.6 0.7 0.8

Average link utilization

Ratio of STR cost to DTR cost

H−cost ratio

L−cost ratio

(f) ISP topology

Figure 2: Cost ratios between STR and DTR when the load-based cost function (a-c) or the SLA-

based cost function (d-f) is used: R

(denoted as “L-cost ratio”) and R

(denoted as “H-cost ratio”).

30% of the traﬃc is of high-priority (f = 30%); 10% high-priority SD-pair density (k = 10%). A

30-node, 150 link random topology is studied in (a) and (d), a 30-node, 162-link power-law topology

is used in (b) and (e), and the ISP topology is used in (c) and (f ).

We expand on these observations in the following sec-

tions.

5.2.1 Impact of network load

We ﬁrst study how R

changes with network load.

From Fig. 2, we observe that for both load- and SLA-

based cost functions, R

follows an “increasing-and-

decreasing” pattern when network load (represented by

the average link utilization) increases. This observation

can be explained as follows.

When the overall network load is low, the volume

of high-priority traﬃc is proportionally low (note that

f = 30% and k = 10% throughout the simulations in

Fig. 2). Therefore, although STR routes high- and low-

priority traﬃc on the same set of paths, the residual

capacity seen by the low-priority traﬃc on these paths

is relatively large. Hence, the cost for low-priority traf-

ﬁc (Φ

), which is determined by the residual capacity

(see Eq. (1)), is low. In such cases, the diﬀerence be-

tween STR and DTR is marginal. When network load

increases, the volume of high-priority traﬃc proportion-

ally increases. With STR, the residual capacity seen by

the low-priority traﬃc decreases, hence Φ

increases.

But with DTR, the low-priority traﬃc can be routed

away from the links with low residual capacity, hence al-

lowing Φ

not to increase as much. As the network load

keeps increasing, most links become eventually heavily

loaded, so no matter how low-priority traﬃc is routed,

it experiences a high cost, which limits the potential

for improvement of DTR and eventually results in a

decrease of R

Next, we investigate the eﬀect on R

of varying the

fraction of network load contributed by the high-priority

traﬃc. Speciﬁcally, we conduct simulations similar to

those discussed above, but change f from 20% to 40%,

while keeping k = 10%. Fig. 4 shows the results for

a 30-node, 150-link random topology, when the load-

based cost function is used. As the ﬁgure shows, the

cost ratio R

becomes higher when f increases from

20% to 40%. This can be understood as follows. As f

increases, the links on the shortest paths (for both STR

and DTR) become more loaded with high-priority traf-

ﬁc. Since under STR the low-priority traﬃc is routed

over the same links, its performance degrades. In con-

trast, DTR allows low-priority traﬃc to be routed away

from those highly loaded links, hence avoiding most of

the performance degradations associated with the in-

crease of f. As a result, the beneﬁts of DTR are more

pronounced (R

becomes larger) for f = 40% than for

f = 20%. For the same reasons, the above observation

also holds for the SLA-based cost function.

5.2.2 Impact of high-priority SD-pair density

We investigate next how R

varies when the density

0 0.5 1 1.5

Link utilization

Link count

Single routing

Dual routing

(a)

0 0.5 1

Link utilization

Link count

Single routing

Dual routing

(b)

0 0.5 1 1.5 2 2.5

Link utilization

Link count

Single routing

Dual routing

(c)

Figure 3: Link utilization comparison between STR and DTR in a 30-node, 150-link random topology.

30% of the traﬃc is of high-priority (f = 30%). (a) 10% high-priority SD pairs ( k = 10% ), load-based

cost function. (b) 10% high-priority SD pairs (k = 10%), SLA-based cost function. (c) 30% high-

priority SD pairs (k = 30%), SLA-based cost function.

0.4 0.5 0.6 0.7 0.8

Average link utilization

Ratio of STR L−cost to DTR L−cost

f=20%

f=40%

Figure 4: The impact of high-priority traﬃc vol-

ume on cost ratio R

in a 30-node, 150-link ran-

dom topology for the load-based cost function,

k = 10%.

of high-priority SD pairs (i.e., k) changes. Speciﬁcally,

we conduct a series of simulations in which k is increased

from 10% to 30%, with the fraction of high-priority traf-

ﬁc ﬁxed at f = 30%. We observe opposite behaviors

under the load- and SLA-based cost functions.

We consider ﬁrst the load-based cost function. As

shown in Fig. 5(a), when k changes from 10% to 30%,

decreases. This is because for a ﬁxed fraction f of

the high-priority traﬃc volume, as the number of SD

pairs sending high-priority traﬃc increases, the high-

priority traﬃc is spread on more links. For instance,

Fig. 6 shows the high-priority link utilization (sorted

in descending order) in a random topology, when STR

is used. As shown in the ﬁgure, when k is increased

from 10% to 30%, the curve “ﬂattens”, indicating more

evenly distributed high-priority load across the links,

and hence lowering the utilization on those once-highly-

loaded links. Consequently, the residual capacity on

those links is increased, which helps make the perfor-

mance of low-priority traﬃc under STR closer to that

of DTR, hence reducing R

In contrast, when the SLA-based cost function is used,

increases when k changes from 10% to 30%, e.g., see

0.5 0.6 0.7 0.8 0.9

Average link utilization

Ratio of STR L−cost to DTR L−cost

k=10%

k=30%

(a)

0.5 0.6 0.7 0.8

Average link utilization

Ratio of STR L−cost to DTR L−cost

k=10%

k=30%

(b)

Figure 5: The impact of high-priority SD-pair

density (k) on R

in a 30-node, 150-link ran-

dom topology. (a) Load-based cost function. (b)

SLA-based cost function.

Fig. 5(b). This can be explained as follows: Given that

the high-priority traﬃc is only a small portion of the

total traﬃc (f = 30%), its queueing delay is nearly in-

signiﬁcant compared to the propagation delay; hence it

plays little or no role in the optimization of the objective

function Λ in Eq. (4). As the density of high-priority SD

pairs initially increases, more high-priority ﬂows con-

centrate on links with small propagation delays. In

STR, because nodes originating high-priority traﬃc also

generate low-priority traﬃc to the same destination(s),

when k increases to 30%, at least 30% of low-priority

SD pairs are “forced” onto a small set of links with low

0 50 100 150

0.2

0.4

0.6

0.8

Sorted links

Link H−utilization

k=10%

k=30%

Figure 6: Link load contributed by the high-

priority traﬃc under STR using the load-based

cost function. The results for two diﬀerent high-

priority SD-pair densities, k = 10% and k = 30%,

are plotted.

5 10 15

0.5

1.5

2.5

Link propagation delay (ms)

Link utilization

Single routing

Dual routing

Figure 7: Link load as a function of propagation

delay when SLA-based cost function is used.

propagation delay. Therefore, the low-priority traﬃc

performance is poorer than when k = 10%. To better

illustrate this eﬀect, we plot the link utilization distri-

butions for k = 10% and k = 30% in Figs. 3(b) and 3(c)

respectively in which a random topology is used. We see

that when k = 30%, the tail of distribution is spread to

the right under STR, indicating more low-priority traf-

ﬁc has been “dragged” onto congested links. In Fig. 7,

we also plot the load of a link as a function of its prop-

agation delay, which shows how links with lower prop-

agation delay tend to have a higher load. This further

conﬁrms the role of link propagation delays.

5.2.3 Impact of high-priority trafﬁc patterns

The above discussions focus on the random model

for the high-priority traﬃc. We consider next the sink

model of Section 5.1. We ﬁnd that in most cases DTR

still outperforms STR, and essentially the same obser-

vations hold as with random traﬃc patterns (details

can be found in [25]). Nevertheless, there exists one

noticeable diﬀerence, namely, that the distribution of

high-priority SD pairs together with topology, may sig-

niﬁcantly aﬀect the eﬀectiveness of DTR.

To illustrate this eﬀect, we consider a power-law topol-

ogy and two diﬀerent distributions of high-priority node.

Speciﬁcally, we ﬁrst select 3 nodes with the highest de-

grees as sink nodes and then select high-priority client

0.4 0.5 0.6 0.7 0.8

Average link utilization

Ratio of STR L−cost to DTR L−cost

Local

Uniform

(a)

0.5 0.6 0.7 0.8

Average link utilization

Ratio of STR L−cost to DTR L−cost

Local

Uniform

(b)

Figure 8: Performance beneﬁts of DTR for the

sink communication pattern (Uniform vs. Lo-

cal) in a 30-node, 162-link power-law topology.

f = 20% and k = 10%. (a) Load-based cost func-

tion. (b) SLA-based cost function.

nodes either uniformly distributed in the network or

among nodes located close to the sinks. Fig. 8 shows

the performance of DTR and STR under the load-based

and the SLA-based cost functions for the two scenarios

(“Uniform” and “Local” denote the ﬁrst and second

scenarios, respectively). We see that DTR and STR

achieve similar performance (R

≈ 1) in the “Local”

scenario, while DTR performs much better than STR

in the “Uniform” scenario. There are several reasons

for this behavior. When client nodes are close to the

sink nodes, high-priority paths remain “local” to the

sink nodes, and hence aﬀect fewer low-priority SD pairs

overall. In addition, the proximity between client and

sink nodes also means that their SLA is easier to meet,

which allow more routing solutions, some of which can

yield better low-priority performance. Neither of these

factors is present when clients are randomly distributed

in the network, so that the beneﬁts of DTR remain more

pronounced in this case.

5.3 Comparing DTR and STR with tradeoff

between trafﬁc classes

Following the discussion of Section 3.3, we study whether

and how much low-priority performance can be improved

under STR if we are willing to sacriﬁce some high-

priority performance.

Table 1: Low-priority traﬃc performance in

STR with a relaxation. f = 30%, k = 10%.

30-node, 150-link random topology

1.03 1.29 1.38 4.04 31.16 58.17 7.51

L,5%

1.02 1.07 1.14 2.34 19.89 21.84 5.74

L,30%

1.02 1.04 1.14 2.07 6.91 19.56 5.52

0.43 0.5 0.58 0.65 0.73 0.8 0.88

30-node, 162-link power-law topology

1.03 1.15 5.20 34.32 21.06 8.3 4.07

L,5%

1.03 1.09 1.3 5.86 15.62 4.69 3.28

L,30%

1.03 1.09 1.25 3.24 15.45 4.58 3.06

0.41 0.48 0.55 0.63 0.71 0.78 0.85

ISP topology

1 1.07 1.11 3.91 9.28 2.3 2.1

L,5%

1 1.04 1.09 2.06 7.72 1.58 1.36

L,30%

1 1.04 1.06 1.42 5.94 1.45 1.35

0.33 0.42 0.5 0.59 0.67 0.78 0.86

5.3.1 The case of load-based cost function

We ﬁrst consider the load-based cost function. Relax-

ing the constraint of strict lexicographical optimization

can be easily incorporated into the heuristic used to

search for STR solutions. Speciﬁcally, denote the link

weight setting at iteration n as W (n), and the costs

of high- and low-priority traﬃc associated with it as

(n) and Φ

(n), respectively. Φ

∗

(n) and Φ

∗

(n) are

the best costs for high- and low-priority traﬃc up to it-

eration n. Assume next that we allow a degradation of ε

of the high-priority traﬃc performance. Then, for every

iteration n, if W (n) results in Φ

(n) ≤ (1 + ε)Φ

∗

(n)

and Φ

(n) < Φ

∗

(n), we record W (n) as a “relaxed”

best solution

. We study the impact on the low-priority

traﬃc performance of this relaxation for ε = 5% and

30%. The results are shown in Table 1 for three diﬀer-

ent topologies, where A

is the average link utilization.

We observe that the performance of low-priority traﬃc

improves as ε increases in STR, but even for ε = 30%, a

large gap remains between the performance of STR and

DTR. Furthermore, this improvement causes signiﬁcant

performance degradation to the high-priority traﬃc. In

contrast, DTR provides both greater improvement for

low-priority traﬃc and no degradation in the perfor-

mance of high-priority traﬃc.

5.3.2 The case of SLA-based cost function

In the case of an SLA-based cost function, relaxation

takes the form of a looser SLA delay bound. To investi-

gate its impact, we study the performance of STR and

DTR when varying the SLA requirement from 25ms to

35ms. In Fig. 9, we report a set of results collected from

a random topology, with a random traﬃc pattern.

Fig. 9(a) shows that independent of the SLA delay

bound, the number of high-priority SD pairs that vi-

olate the SLA requirement is the same for STR and

DTR. We also observe that when the SLA delay bound

If there are multiple such W (n)’s, we pick the one achieving

the lowest Φ

(n).

is above 30ms, STR and DTR result in similar perfor-

mance for the low-priority traﬃc and similar maximum

link utilizations as shown in Figs. 9(b) and 9(c) respec-

tively. In other words, a loosening of the delay bound

by 20% allows STR to provide similar performance as

DTR for the low priority traﬃc. The main reason for

this improvement is that the looser SLA enables STR

to explore more routing solutions, including some that

oﬀer good performance to the low-priority traﬃc while

still meeting the (looser) high-priority SLA. Neverthe-

less, DTR oﬀers these beneﬁts without penalizing high-

priority traﬃc. Furthermore, as with any relaxation

technique, identifying the “right” level of relaxation re-

quired to allow STR to provide reasonable performance

to low-priority traﬃc is in itself a challenging task. This

issue is altogether absent when using DTR.

6. CONCLUSION

This paper investigates how routing can help service

diﬀerentiation in IP networks. We study the beneﬁts

of DTR, which allows separate routing of high- and

low-priority traﬃc classes. Compared to the traditional

STR scheme, DTR provides greater ﬂexibility in con-

trolling resource allocation across traﬃc classes, hence

achieving more eﬃcient service diﬀerentiation.

To realize the beneﬁts of DTR, we developed a heuris-

tic that overcomes the computational complexity of iden-

tifying good link weight settings for each traﬃc class.

The heuristic was tested under a lexicographical op-

timization model that gives strict precedence to high

priority performance, but as shown in the paper, can

be easily adapted to other conﬁgurations. The heuris-

tic was used to investigate the eﬀectiveness of DTR

with two common performance objectives, embodied by

load-based and SLA-based cost functions, respectively.

The results showed that irrespective of which cost func-

tion was used, DTR can substantially improve the per-

formance of low-priority service class without sacriﬁc-

ing that of high-priority class. This was demonstrated

through extensive simulations for a broad range of net-

work topologies and traﬃc patterns.

7. REFERENCES

[1] P. Psenak, S. Mirtorabi, A. Roy, L. Nguyen, and

P. Pillay-Esnault, “Multi-topology (MT) routing

in OSPF,” IETF RFC 4915, June 2007.

[2] B. Fortz and M. Thorup, “Internet traﬃc

engineering by optimizing OSPF weights,” in

Proc. IEEE INFOCOM, 2000.

[3] M. Ericsson, M. Resende, and P. Pardalos, “A

genetic algorithm for the weight setting problem

in OSPF routing,” J. of Combinatorial

Optimization, vol. 6, pp. 299–333, 2002.

[4] L. Buriol, M. Resende, C. Ribeiro, and

M. Thorup, “A memetic algorithm for OSPF

25 30 35

SLA requirement (ms)

Number of SLA violations

Single routing

Dual routing

(a)

25 30 35

SLA requirement (ms)

Low−priority traffic cost

Single routing

Dual routing

(b)

25 30 35

0.8

1.2

1.4

1.6

1.8

SLA requirement (ms)

Max link utilization

Single routing

Dual routing

(c)

Figure 9: The impact of changing the SLA requirement on STR and DTR in a 30-node, 150-link

random topology. f = 30% and k = 30%. The average link utilization is roughly 0.5 in each SLA

requirement setting.

routing,” in Proc. 6th INFORMS Telecom, 2002.

[5] A. Nucci, S. Bhattacharyya, N. Taft, and C. Diot,

“IGP link weight assignment for operational

Tier-1 backbones,” IEEE/ACM Transactions on

Networking, vol. 15, no. 4, pp. 789–802, August

2007.

[6] S. Balon and G. Leduc, “Dividing the traﬃc

matrix to approach optimal traﬃc engineering,”

in Proc. IEEE ICON, 2006.

[7] G. Apostolopoulos, “Using multiple topologies for

IP-only protection against network failures: A

routing performance perspective,” ICS-FORTH,

Greece, Tech. Rep., 2006.

[8] S. Gjessing and O. Norway, “Implementation of

two resilience mechanisms using multi topology

routing and stub routers,” in Proc. AICT-ICIW,

2006.

[9] A. Kvalbein, A. F. Hansen, T. Cicic, S. Gjessing,

and O. Lysne, “Fast IP network recovery using

multiple routing conﬁgurations,” in Proc. IEEE

INFOCOM, 2006.

[10] W. C. Lee, M. G. Hluchyj, and P. A. Humblet,

“Routing subject to quality of service constraints

in integrated communication networks,” IEEE

Network, vol. 9, no. 4, pp. 46–55, Jul/Aug 1995.

[11] E. Crawley, B. R. R. Nair, and H. Sandick, “A

framework for QoS-based routing in integrated

service networks,” IETF RFC 2386 , 1998.

[12] J. Wang and K. Nahrstedt, “Hop-by-hop routing

algorithms for premium traﬃc,” ACM SIGCOMM

Computer Communications Review

, vol. 32, no. 5,

pp. 73–88, November 2002.

[13] R. Gu´erin and A. Orda, “QoS-based routing in

networks with inaccurate information: Theory

and algorithms,” in Proc. IEEE INFOCOM, 1997.

[14] Q. Ma and P. Steenkiste, “Supporting dynamic

inter-class resource sharing: A multi-class QoS

routing algorithm,” in Proc. IEEE INFOCOM,

1999.

[15] S. Chen and K. Nahrstedt, “An overview of

quality of service routing for next-generation

high-speed networks: Problems and solutions,”

IEEE Network, vol. 12, no. 6, pp. 64–79, Nov/Dec

1998.

[16] D. Mitra and K. G. Ramakrishnan, “Techniques

for traﬃc engineering of multiservice,

multi-priority networks,” Bell Labs Technical

Journal, vol. 6, no. 1, pp. 139–151, 2001.

[17] S. L. Spitler and D. C. Lee, “Integrating

eﬀective-bandwidth-based QoS routing and best

eﬀort routing,” in Proc. IEEE INFOCOM, 2003.

[18] S. Balon, F. Skiv´ee, and G. Leduc, “How well do

traﬃc engineering objective functions meet TE

requirements,” in Proc. IFIP Networking, 2006.

[19] B. Fortz and M. Thorup, “Optimizing

OSPF/IS-IS weights in a changing world,” IEEE

Journal on Selected Areas in Communications,

vol. 20, no. 4, pp. 756–767, May 2002.

[20] S. Boettcher and A. G. Percus, “Nature’s way of

optimizing,” Artiﬁcial Intelligence, vol. 119, pp.

275–286, May 2000.

[21] A.-L. Barab´asi and R. Albert, “Emergence of

scaling in random networks,” Science, vol. 286,

no. 5439, pp. 509–512, October 1999.

[22] M. Faloutsos, P. Faloutsos, and C. Faloutsos, “On

power-law relationships of the Internet topology,”

in Proc. ACM SIGCOMM, 1999.

[23] A. Medina, N. Taft, K. Salamatian,

S. Bhattacharyya, and C. Diot, “Traﬃc matrix

estimation: Existing techniques compared and

new directions,” in

Proc. ACM SIGCOMM

, 2002.

[24] S. Bhattacharyya, N. Taft, J. Jetcheva, and

C. Diot, “POP-level and access-link-level traﬃc

dynamics in a Tier-1 POP,” in Proc. ACM IMW,

2001.

[25] K.-W. Kwong, R. Gu´erin, A. Shaikh, and S. Tao,

“Improving service diﬀerentiation in IP networks

through dual topology routing,” University of

Pennsylvania, Tech. Rep., June 2007. [Online].

Available: http://einstein.seas.upenn.edu/mnlab