Increasing Internet Capacity Using Local Search.
Open Shortest Path First (OSPF) is one of the most commonly used intra-domain internet routing protocol. Traffic flow is routed along shortest paths, splitting flow evenly at nodes where several outgoing links are on shortest paths to the destination. The weights of the links, and thereby the shortest path routes, can be changed by the network operator. The weights could be set proportional to the physical lengths of the links, but often the main goal is to avoid congestion, i.e. overloading of links, and the standard heuristic recommended by Cisco (a major router vendor) is to make the weight of a link inversely proportional to its capacity.We study the problem of optimizing OSPF weights for a given a set of projected demands so as to avoid congestion. We show this problem is NP-hard, even for approximation, and propose a local search heuristic to solve it. We also provide worst-case results about the performance of OSPF routing vs. an optimal multi-commodity flow routing. Our numerical experiments compare the results obtained with our local search heuristic to the optimal multi-commodity flow routing, as well as simple and commonly used heuristics for setting the weights. Experiments were done with a proposed next-generation AT&T WorldNet backbone as well as synthetic internetworks.
Introduction
Provisioning an Internet Service Provider (ISP) backbone network for intra-domain IP
traffic is a big challenge, particularly due to rapid growth of the network and user demands.
At times, the network topology and capacity may seem insufficient to meet the current
demands. At the same time, there is mounting pressure for ISPs to provide Quality of
Service (QoS) in terms of Service Level Agreements (SLAs) with customers, with loose
guarantees on delay, loss, and throughput. All of these issues point to the importance
of traffic engineering, making more efficient use of existing network resources by tailoring
routes to the prevailing traffic.
1.1 The general routing problem
Optimizing the use of existing network resources can be seen as a general routing problem
defined as follows. We are given a capacitated directed graph
whose nodes and arcs represent routers and the capacitated links between them,
and a demand matrix D that, for each pair (s; t) of nodes, tells us how much traffic flow
we need to send from s to t. We refer to s and t as the source and the destination of the
demand. Many of the entries of D may be zero, and in particular, D(s; t) should be zero
if there is no path from s to t in G.
With each arc a 2 A, we associate a cost function \Phi a ('(a)) of the load '(a), depending
on how close the load is to the capacity c(a). More precisely, for each a 2 A, \Phi a is the
continuous function with \Phi a derivative
a
3 for 1=3 - x=c(a) ! 2=3;
5000 for 11=10 -
(1)
The function \Phi a is illustrated in Figure 1, and can be viewed as modeling retransmission
delays caused by packet losses. Generally it is cheap to send flow over an arc with a small
utilization '(a)=c(a). The cost increases progressively as the utilization approaches 100%,
and explodes when we go above 110%.
Our formal objective is to distribute the demanded flow so as to minimize the sum
a2A
\Phi a ('(a))
of the resulting costs over all arcs. Because of the explosive increase in cost as loads exceeds
capacities, our objective typically implies that we keep the max-utilization max a2A '(a)=c(a)
below 1, or at least below 1:1, if at all possible.
The exact definition of the objective function is not so important for our techniques,
as long as it is a piecewise linear increasing and convex function. In this general routing
cost
load

Figure

1: Arc cost \Phi a ('(a)) as a function of load '(a) for arc capacity c(a) = 1.
problem, there are no limitations to how we can distribute the flow between the paths,
and the problem can therefore be formulated and solved in polynomial time as a fractional
multi-commodity flow problem, as we show in Section 2.
The above definition of the general routing problem, except for the exact choice of
objective function, is equivalent to the one used e.g. in Awduche et al. (1999). Its most
controversial feature is the assumption that we have an estimate of a demand matrix.
This demand matrix could, as in our case for the proposed AT&T WorldNet backbone, be
based on concrete measures of the flow between source-destination pairs (Feldmann et al.
2000). The demand matrix could also be based on a concrete set of customer subscriptions
to virtual leased line services. Our demand matrix assumption does not accommodate
unpredicted bursts in traffic. However, we can deal with more predictable periodic changes,
say between morning and evening, simply by thinking of it as two independent routing
problems: one for the morning, and one for the evening.
1.2 OSPF versus MPLS routing protocols
Unfortunately, most intra-domain internet routing protocols today do not support a free
distribution of flow between source and destination as defined above in the general routing
problem. The most common protocol today is Open Shortest Path First (OSPF) (Moy
1999). In this protocol, the network operator assigns a weight to each link, and shortest
paths from each router to each destination are computed using these weights as lengths of
the links. In each router, the next link on all shortest paths to all possible destinations is
stored in a table, and a flow arriving at the router is sent to its destination by splitting the
flow between the links that are on the shortest paths to the destination. The definition
of the OSPF protocol specifies that the splitting is approximately even, and for simplicity
we will assume that the splitting is exactly even (for AT&T's WorldNet this simplification
leads to reasonable estimates).
The quality of OSPF routing depends highly on the choice of weights. Nevertheless, as
recommended by Cisco (a major router vendor) (1997), these are often just set inversely
proportional to the capacities of the links, without taking any knowledge of the demand
into account.
It is widely believed that the OSPF protocol is not flexible enough to provide good
load balancing for a given demand matrix (Awduche et al. 1999, x2.3), and this is one
of the reasons for introducing the more flexible Multi-Protocol Label Switching (MPLS)
technologies. With MPLS one can in principle decide the path for each individual packet.
Hence, we can simulate a solution to the general routing problem by distributing the
packets on the paths between a source-destination pair using the same distribution as we
used for the flow. The MPLS technology has some disadvantages. First of all, MPLS is
not yet widely deployed, let alone tested. Second OSPF routing is simpler in the sense
that the routing is completely determined by one weight for each arc. That is, we do not
need to make individual routing decisions for each source/destination pair. Also, if a link
fails, the weights on the remaining links immediately determine the new routing.
1.3 Our results
The general question studied in this paper is: Can a sufficiently clever weight setting make
OSPF routing perform nearly as well as optimal general/MPLS routing?
Our first answer is negative: for arbitrary n, we construct an instance of the routing
problem on - n 3 nodes where any OSPF routing has its average flow on arcs with utiliza-
tion
n) times higher than the max-utilization in an optimal general solution. With our
concrete objective function, this demonstrates a gap of a factor approaching 5000 between
the cost of the optimal general routing and the cost of the optimal OSPF routing. This is
worst possible, a gap of at most 5000 can be achieved by setting all weights to 1.
The next natural question is: how well does OSPF routing perform on real networks.
In particular we wanted to answer this question for a proposed AT&T WorldNet backbone.
In addition, we studied synthetic internetworks, generated as suggested by Calvert et al.
(1997) and Zegura et al. (1996). Finding a perfect answer is hard in the sense that it
is NP-hard to find even an approximately optimal setting of the OSPF weights for an
arbitrary network. Instead we resorted to a local search heuristic, not guaranteed to find
optimal solutions. Very surprisingly, it turned out that for the proposed AT&T WorldNet
backbone, as well as for the synthetic networks, the heuristic found weight settings making
OSPF routing perform within a few percent of the optimal general routing. Thus for the
proposed AT&T WorldNet backbone with our projected demands, and with our concrete
objective function, there would be no substantial traffic engineering gain in switching
from the existing well-tested and understood robust OSPF technology to the new MPLS
alternative.
We also compared our local search heuristic with standard heuristics, such as weights
inversely proportional to the capacities or proportional to the physical distances, and found
that, for the same network and capacities, we could support a 50%-115% increase in the
demands, both with respect to our concrete cost function and, simultaneously, with respect
to keeping the max-utilization below 100%.
1.4 Technical contributions
Our local search heuristic is original in its use of hash tables both to avoid cycling and for
search diversification. Using hashing tables to avoid cycling in local search was already
proposed by Woodruff and Zemel (1993), but our approach differs in the sense that we
eliminate completely all solutions already encountered, and we do not need the concept of
solution attributes. More precisely, our approach is closely related to strict tabu search
(Battiti and Tecchiolli 1994), where each solution is mapped to a hash value (that can be
seen as the unique solution attribute), and we do not allow the same value twice during the
complete search. Using the same mechanism to obtain diversification is, to our knowledge,
a new idea that has not been tested before.
Our local search heuristic is also original in its use of more advanced dynamic graph
algorithms. Computing the OSPF routing resulting from a given set of weights turned
out to be the computational bottleneck, as many different solutions are evaluated during
a neighborhood exploration. However, our neighborhood structure allows only a few local
changes in the weights. We therefore developed efficient algorithms to update the routing
and recompute the cost of a solution when a few weights are changed. These speed-ups
are critical for the local search to reach a good solution within reasonable time bounds, as
they typically reduce the computing time by a factor of 15.
Related work
To the best of our knowledge, there has not been any previous work dealing with the even
splitting in OSPF routing. In previous work on optimizing OSPF weights (Rodrigues and
Ramakrishnan 1992; Lin and Wang 1993; Bley, Gr-otchel, and Wess-aly 1998) they have
either chosen weights so as to avoid multiple shortest paths from source to destination,
or applied a protocol for breaking ties, thus selecting a unique shortest path for each
source-destination pair.
Besides the difference in model, where we deal with even splitting, our approach is
also technically different. First of all, we deal with much larger networks. In more detail,
(Rodrigues and Ramakrishnan 1992) presents a local search like ours, but using only a
single descent. In contrast, we consider non-improving moves and hence we have to deal
with the problem of avoiding cycles. The largest network considered in (Rodrigues and
Ramakrishnan 1992) has 16 nodes and links. Also (Bley, Gr-otchel, and Wess-aly 1998)
uses a single descent local search. The largest network they consider has 13 links, but
it should be mentioned that they simultaneously deal with the problem of designing the
network, whereas we only try to optimize the weights for a given network. Finally, (Lin and
Wang 1993) presents a completely different approach based on Lagrangian relaxation, and
consider networks with up to 26 nodes. In our experiments, the proposed AT&T WorldNet
backbone has 90 nodes and 274 links, and our synthetic networks have up to 100 nodes and
503 links. The scale of our experiments makes speed an issue, motivating our innovative
use of dynamic graph algorithms in local search.
In Section 2 we formalize our general routing model as a multi-commodity flow problem.
ferent sizes and topologies of networks. In Section 4, a family of networks is constructed,
demonstrating a large gap between OSPF and multi-commodity flow routing, and in Section
5, we show that the problem of optimizing OSPF weights is NP-hard. In Section 6
we present our local search algorithm, guiding the search with hash tables. In Section 7
we show how to speed-up the calculations using dynamic graph algorithms. In Section 8,
we report the numerical experiments, and we conclude in Section 9 with some comments
about the results obtained.
Mathematical formulations
2.1 Optimal routing
We are given a directed network with a capacity c(a) for each a 2 A, and a
demand matrix D that, for each pair (s; t) 2 N \Theta N , tells the demand D(s; t) in traffic flow
between s and t. We sometimes refer to the non-zero entries of D as the demands. With
each pair (s; t) and each arc a, we associate a variable f (s;t)
a telling how much of the traffic
flow from s to t goes over a. Variable '(a) represents the total load on arc a, i.e. the sum
of the flows going over a, and \Phi a is used to model the piecewise linear cost function of arc
a.
With this notation, the general routing problem can be formulated as the following
linear program, which is in fact an uncapacitated multi-commodity flow problem with
increasing piecewise linear costs.
a2A
\Phi a
subject to
u:(u;v)2A
u:(v;u)2A
\GammaD(s;t) if v=s;
a a 2 A; (3)
\Phi a - '(a) a 2 A; (4)
3 c(a) a 2 A; (5)
3 c(a) a 2 A; (6)
\Phi a - 70'(a) \Gamma 178
3 c(a) a 2 A; (7)
\Phi a - 500'(a) \Gamma 1468
3 c(a) a 2 A; (8)
\Phi a - 5000'(a) \Gamma 19468c(a) a 2 A;
Constraints (2) are flow conservation constraints that ensure the desired traffic flow is
routed from s to t, constraints (3) define the load on each arc and constraints (4) to
define the cost on each arc.
The above program is a complete linear programming formulation of the general routing
problem, and hence it can be solved optimally in polynomial time (Khachiyan 1979). In
our experiments, we solved the above problems by calling CPLEX version 6.5 via AMPL.
We denote by \Phi OPT the optimal solution of this general routing problem.
2.2 OSPF routing
In OSPF routing, we choose a positive integer weight w a for each arc. The length of a path
is then the sum of its arc weights, and we have the extra condition that all flow leaving a
node aimed at a given destination is evenly spread over the first arcs on shortest paths to
that destination. More precisely, for each source-destination pair (s; t) 2 N \Theta N and for
each node u, we have that f (s;t)
is not on a shortest path from s to t, and that
are on shortest paths from s to t. Note that the
routing of the demands is completely determined by the shortest paths which in turn are
determined by the weights we assign to the arcs.
We denote by \Phi OptOSPF the optimal cost with OSPF routing.
3 Normalizing cost
We now introduce a normalizing scaling factor for the cost function that allows us to
compare costs across different sizes and topologies of networks. To define the measure, we
introduce
(D(s;
Here dist 1 (\Delta) is distance measured with unit weights (hop count). Also, we let \Phi UnitOSPF
denote the cost of OSPF routing with unit weights. Below we present several nice properties
of \Phi Uncap and \Phi UnitOSPF . It is (ii) that has inspired the name "Uncapacitated".
(i) \Phi Uncap is the total load if all traffic flow goes along unit weight shortest paths.
have unlimited capacity.
(iii) \Phi Uncap is the minimal total load of the network.
(iv) \Phi Uncap - \Phi OPT .
Above, 5000 is the maximal value of \Phi 0
a .
Proof. Above (i) follows directly from the definition. Now (ii) follows from (i) since the
ratio of cost over load on an arc is 1 if the capacity is more than 3 times the load. Further
(iii) follows from (i) because sending flow along longer paths only increases the load. From
(iii) we get (iv) since 1 is the smallest possible ratio of cost over load. Finally we get (v)
from (ii) since decreasing the capacity of an arc with a given load increases the arc cost by
strictly less than a factor 5000 if the capacity stays positive. 2
Our scaled cost is now defined as:
From Lemma 1 (iv) and (v), we immediately get:
Note that if we get \Phi  means that we are routing along unit weight shortest paths
with all loads staying below 1/3 of the capacity. In this ideal situation for our mathematical
model, there is no point in increasing the capacities of the network.
packet cost
utilization

Figure

2: Arc packet cost as function of utilization
A packet level view
Perhaps the most instructive way of understanding our cost functions is on the packet
level. We can interpret the demand D(s; t) as measuring how many packets - of identical
sizes - we expect to send from s to t within a certain time frame. Each packet will follow
a single path from s to t, and it pays a cost for each arc it uses. With our original cost
function \Phi, the per packet cost for using an arc is \Phi a ('(a))='(a). This per packet cost
is closely related to the probability of a packet being lost. Now, \Phi can be obtained by
summing the path cost for each packet.
The per packet arc cost \Phi a ('(a))='(a) is a function OE of the utilization '(a)=c(a). The
function OE is depicted in Figure 2. First OE is 1 while the utilization is - 1=3. Then OE
increases to 70 2for a full arc, and after that it grows rapidly towards 5000. The
cost factor of a packet is the ratio of its current cost over the cost it would have paid if it
could follow the unit-weight shortest path without hitting any utilization above 1/3, hence
paying the minimal cost of 1 for each arc traversed. The latter ideal situation is what is
measured by \Phi Uncap , and therefore \Phi   measures the weighted average packet cost factor
where each packet is weighted proportionally to the unit-weight distance between its end
points.
If a packet follows a shortest path, and if all arcs are exactly full, the cost factor is
exactly
3 . The same cost factor can of course be obtained by some arcs going above
capacity and others going below, or by the packet following a longer detour using less
congested arcs. Nevertheless, it is natural to say that a routing congests a network if
From (13), it follows that the maximal gap between optimal general routing and optimal
OSPF routing is less than a factor 5000. In Lemma 2, we show that the gap can in fact
approach 5000.
Our proof is based on a construction where OSPF leads to very bad congestion for any
natural definition of congestion. In fact, the construction provides a negative example for
any type of routing where if the flow from a node to a given destination splits, it splits
evenly between the outgoing links that it uses.
More precisely, for arbitrary n, we construct an instance of the routing problem on - n 3
nodes with only one demand, and where all paths from the source to the destination are
shortest with respect to unit weights, or hop count. In this instance, any OSPF routing
has its average flow on arcs with
n) times higher than the max-utilization
in an optimal general solution. With our concrete objective function, this demonstrates a
gap of a factor approaching 5000 between the cost of the optimal general routing and the
cost of the optimal OSPF routing.
There is a family of networks G n so that the optimal general routing approaches
being 5000 times better than the optimal OSPF routing as n !1.
Proof. For be the graph defined by node set
ng [
and arc set
(v
The capacities of the arcs are
ae
3 otherwise.
Finally, we have a single demand of size n with source s and destination t.
The graph G n has O(n 3 ) nodes and arcs and is illustrated in Figure 3 for
high capacity arcs represented by thick lines.
By our construction, there are exactly n paths from s to t, each with n 2 links. These
paths are :
The optimal solution of the general routing model is obviously given by sending one
unit of flow along each path, meaning that no arc gets more flow than a third of its capacity.
Therefore, as each unit of flow from s to t has to follow a path of length n 2 , the optimal
cost \Phi n
OPT is equal to n 3 .
In the OSPF model, we can freely decide which paths we use, but because of the even
splitting, the first path used gets half the flow, i.e. n=2 units, the second gets n=4 units,
and so on. Asymptotically this means that almost all the flow goes along arcs with load
a factor
n) above their capacity, and since all paths use at least n
capacity, the optimal OSPF cost \Phi n
OptOSPF satisfies
s
Figure

3: G n for
We conclude that the ratio of the OSPF cost over the optimal cost is such that
OptOSPF
OPT
5 Complexity
In this section, we will formally present our hardness results, stating that it is NP-hard to
find even an approximately optimal setting of OSPF weights. All proofs are deferred to


Appendix

A. The hardness will be presented, not only for our concrete cost function \Phi
as defined in Section 1, but for much more general classes of cost functions. Also, we will
prove hardness of approximation with respect to max-utilization, which is another natural
measure for the quality of routing. In all cases, our inapproximability factors are much
worse than the results we will later obtain experimentally.
For our cost function from Section 1, we have
Theorem 3 It is NP-hard to optimize the OSPF weight setting with respect to the cost
function defined by (1) within a factor 3:1 from optimality.
Theorem 3 is derived from the following hardness result for a large class of cost functions:
Theorem 4 Let ff and fi be fixed constants. Suppose our total routing cost is
a2A \Psi a ('(a)) where
\Psi a (l) - ffl if l - c(a);
\Psi a (l) - ffc(a)
Then, if fi - 52ff, it is NP-hard to optimize the OSPF weight setting with respect to
a2A \Psi a (l(a)) within a factor 0:72 optimality.
The proof of Theorem 4 is deferred to Appendix A, but here we verify that Theorem 4
does generalize Theorem 3, as claimed.
Proof that Theorem 4 implies Theorem 3. In order to get into the hypothesis of
Theorem 4, it is sufficient to see that an equivalent problem is obtained by defining new
capacities by using the modified cost functions defined
by \Phi a
a
This new cost function satisfies the hypothesis of Theorem 4 with
and leading to an inapproximability factor greater than 3:1. 2
Finally, we state the hardness for max-utilization.
Theorem 5 It is NP-hard to optimize the max-utilization in OSPF routing within a factor
3=2.
6 OSPF Weight Setting using Local Search
In OSPF routing, for each arc a 2 A, we have to choose a weight w a . These weights
uniquely determine the shortest paths, the routing of traffic flow, the loads on the arcs,
and finally, the value of the cost function \Phi. In the rest of this section, we present a local
search heuristic to determine weights w a ; a 2 A, in order to minimize \Phi.
Suppose that we want to minimize a function f over a set X of feasible solutions. Local
search techniques are iterative procedures that for each iteration define a neighborhood
for the current solution x 2 X, and then choose the next solution x 0 from this
neighborhood. Often we want the neighbor x 0 2 N (x) to improve on f in the sense that
Differences between local search heuristics arise essentially from the definition of the
neighborhood, the way it is explored, and the choice of the next solution from the neigh-
borhood. Descent methods consider the entire neighborhood, select an improving neighbor
and stop when a local minimum is found. Meta-heuristics such as Tabu search or simulated
annealing allow non-improving moves while applying restrictions to the neighborhood to
avoid cycling. An extensive survey of local search and its application can be found in Aarts
and Lenstra (1997).
In the remainder of this section, we first describe the neighborhood structure we apply
to solve the weight setting problem. Second, using hashing tables, we address the problem
of avoiding cycling. These hashing tables are also used to avoid repetitions in the neighborhood
exploration. While the neighborhood search aims at intensifying the search in a
promising region, it is often of great practical importance to search a new region when the
neighborhood search fails to improve the best solution for a while. These techniques are
called search diversification and are addressed at the end of the section.
As a very first step, we choose a maximal weight w restrict our
attention to weights . The idea behind using small weights is that we increase
the chance of even splitting due to multiple shortest paths from a node to some destination.
6.1 Neighborhood structure
A solution of the weight setting problem is completely characterized by its vector
(w a ) a2A of weights. We define a neighbor w 0 2 N (w) of w by one of the two following
operations applied to w.
Single weight change. This simple modification consists in changing a single weight in
We define a neighbor w 0 of w for each arc a 2 A and for each possible weight
by setting w
Evenly balancing flows. Assuming that the cost function \Phi a for an arc a 2 A is increasing
and convex, meaning that we want to avoid highly congested arcs, we want
to split the flow as evenly as possible between different arcs.
More precisely, consider a demand node t such that
of the demand going to t goes through a given node u. Intuitively, we would like
OSPF routing to split the flow to t going through u evenly along arcs leaving u.
This is the case if all the arcs leaving u belong to a shortest path from u to t. More
precisely, if are the nodes adjacent from u, and if P i is one of the
shortest paths from u i to t, for as illustrated in Figure 4, then we want
to set w 0 such that
denotes the sum of the weights of the arcs belonging to P i . A simple
way of achieving this goal is to set
w a otherwise:
where w
A drawback of this approach is that an arc that does not belong to one of the shortest
paths from u to t may already be congested, and the modifications of weights we
propose will send more flow on this congested arc, an obviously undesirable feature.
We therefore decided to choose at random a threshold ratio ' between 0.25 and 1,
and we only modify weights for arcs in the maximal subset B of arcs leaving u such
that
l w (u;
where l w (a) denotes the load on a resulting from weight vector w. In this way, flow
leaving u towards t can only change for arcs in B, and choosing ' at random allows
to diversify the search.

Figure

4: The second type of move tries to make all paths form u to t of equal length.
Another drawback of this approach is that it does not ensure that weights remain
below w max . This can be done by adding the condition that max i2B w(P
choosing B.
As detailed in in the rest of this section, we will not explore the full neighborhood. Of
all neighbors explored, our next solution will be the best according to our cost function.
6.2 Guiding the search with hashing tables
The simplest local search heuristic is the descent method that, at each iteration, selects
the best element in the neighborhood and stops when this element does not improve the
objective function. This approach leads to a local minimum that is often far from the
optimal solution of the problem, and heuristics allowing non-improving moves have been
considered. Unfortunately, non-improving moves can lead to cycling, and one must provide
mechanisms to avoid it. Tabu search algorithms (Glover 1986, 1989, 1990; Glover
and Laguna 1997), for example, make use of a Tabu list that records some attributes of
solutions encountered during the recent iterations and forbids any solution having the same
attributes.
As our neighborhood structure for the weight setting problem is quite complex, efficiently
designing Tabu attributes and search parameters such as the length of the Tabu list
would have required a lot of work. We instead developed a search strategy that completely
avoids cycling without the need to store complex solution attributes. This approach, called
Strict Tabu Search was studied by Battiti and Tecchiolli (1994). They tested different techniques
for implementing it, namely the Reverse Elimination Method (Glover 1990), hashing
(Woodruff and Zemel 1993) and digital trees (Knuth 1973).
It turns out that the Reverse Elimination Method is much more expensive both in
memory and computing requirements. Furthermore, digital trees are best suited for binary
variables, and would be too expensive memory-wise for encoding our solutions as jAj-
dimensional 16-bit integer vectors. We therefore resorted to hashing. Hash functions
w a 0 1001
p a 0100101101110110 1101
a w a 00010
l-z -
h a (w a )
z -
Figure

5: Example of hash function for a single weight with w a (w a
42797.
compress solutions into single integer values, sending different solutions into the same
integer with small probability. To implement Strict Tabu Search, we use a boolean table T
to record if a value produced by the hash function has been encountered. At the beginning
of the algorithm, all entries in T are set to false. If w is the solution produced at a given
iteration, we set T (h(w)) to true, and, while searching the neighborhood, we reject any
solution w 0 such that T (h(w 0 )) is true. Checking that a solution has been encountered is
therefore performed in constant time.
As pointed out by Carlton and Barnes (1996), we risk collisions whenever w 0 6= w but
They show that collisions arise with a high probability after just a few
iterations. In our case, roughly 10 % of all solutions are eliminated because of collisions.
However, the eliminated solutions are essentially random, and since our approach is already
highly randomized, this is not critical. Moreover, for the weight setting problem, many
different solutions (i.e. weight vectors) lead to the same arc loads and total cost. Therefore,
even if a good solution is killed by a collision, there is a high chance that some other solution
leading to the same routing will survive.
The hash functions we use are based on developments from Carter and Wegman (1979),
Dietzfelbinger (1996), and Thorup (2000), and have the property that the probability that
any two different weight settings get the same hash value is the same as if the functions
were truly random, which is not the case for functions used by Woodruff and Zemel (1993).
Suppose the weights are represented as m-bit integers, where m - log 2 w max . and we want
to map them to l-bit integers. In our case, we had
With each arc a 2 A, we associate a random (l +m \Gamma 1)-bit integer p a . We then define
the hash function h a (w a ) of a single weight w a by considering p a w a , which is a (2m+ l \Gamma 1)-
bit integer, and taking the l-bit integer obtained by dropping the m highest bits and the
lowest bits of p a w a , as illustrated in Figure 5.
The hashing value of w is then defined by
a2A
h a (w a );
where \Phi denotes the bitwise XOR operation. A big advantage of using the XOR operation
is that it allows a fast update of the hashing value when a single weight is changed. More
precisely, if w 0 is equal to w except for a given a for which w 0
a 6= w a , then h(w 0 ) can be
computed as
a (w a ) \Phi h a (w 0
a
In our local search we performed 5000 iterations, recorded 5000 solutions, thus using a
fraction 5000=2 of the potential hash values.
6.3 Speeding up neighborhood evaluation
Due to our complex neighborhood structure for evenly balancing flows, it turned out that
several moves often lead to the same weight setting. A simple example is if we have a node
w with a single incoming arc (v; w). Then from any node u 6= v; w, we will do exactly the
same balancing with destination v as with destination w.
For efficiency, we would like to avoid evaluation of these equivalent moves. Again,
hashing tables are a useful tool to achieve this goal : inside a neighborhood exploration,
we define a secondary hashing table used to store the encountered weight settings as above,
and we do not evaluate moves leading to a hashing value already met.
The neighborhood structure we use has also the drawback that the number of neighbors
of a given solution is very large, and exploring the neighborhood completely may be too
time consuming. To avoid this drawback, we only evaluate a randomly selected set of
neighbors.
We start by evaluating 20 % of the neighborhood. Each time the current solution is
improved, we divide the size of the sampling by 3, while we multiply it by 2 each time
the current solution is not improved. Moreover, we enforce sampling at least 1 % of the
neighborhood.
6.4 Diversification
Another important ingredient for local search efficiency is diversification. The aim of
diversification is to escape from regions that have been explored for a while without any
improvement, and to search regions as yet unexplored.
In our particular case, many weight settings can lead to the same routing. Therefore,
we observed that when a local minimum is reached, it has many neighbors having the
same cost, leading to long series of iterations with the same cost value. To escape from
these "long valleys" of the search space, the secondary hashing table is again used. This
table is generally reset at the end of each iteration, since we want to avoid repetitions
inside a single iteration only. However, if the neighborhood exploration does not lead to
a solution better than the current one, we do not reset the table. If this happens for
several iterations, more and more collisions occur and more potentially good solutions are
excluded, forcing the algorithm to escape from the region currently explored. For these
collisions to appear at a reasonable rate, the size of the secondary hashing table must be
small compared to the primary one. In our experiments, its size is 20 times the number of
cost
iteration

Figure

Evolution of the local search over iterations, AT&T WorldNet backbone
arcs in the network. For AT&T WorldNet's proposed backbone with 274 links, this gives
a secondary size of 5; 480 whereas the primary size is 2 This approach for
diversification is useful to avoid regions with a lot of local minima with the same cost, but
is not sufficient to completely escape from one region and go to a possibly more attractive
one. Therefore, each time the best solution found is not improved for 300 iterations, we
randomly perturb the current solution in order to explore a new region from the search
space. The perturbation consists of adding a randomly selected perturbation, uniformly
chosen between -2 and +2, to 10 % of the weights.
We present in Figure 6 the evolution of the cost at each iteration of the search for one
run of an instance for AT&T WorldNet backbone. The impact of our diversification scheme
is the high variation in cost that can be observed in the figure, but as the algorithm only
allows a few diversifying moves, we can observe a quick descent to a good region after a
"bad move".
7 Cost Evaluation
In this section, we first show how to evaluate our cost function for the static case of a
network with a specified weight setting. Computing this cost function from scratch is
unfortunately too time consuming for our local search, so afterwards, we show how to
reuse computations, exploiting the fact that there are only few weight changes between a
current solution and any solution in its neighborhood.
7.1 The static case
We are given a directed graph capacities fc a g a2A , a demand matrix D,
and weights fw a g a2A . For the instances considered, the graph is sparse with
Moreover, in the weighted graph the maximal distance between any two nodes is O(jN j).
We want to compute our cost function \Phi. The basic problem is to compute the loads
resulting from the weight setting. We consider one destination t at a time, and compute
the total flow from all sources s 2 N to t. This gives rise to a certain partial load
l t
a for each arc. Having done the above computation for each destination t,
we can compute the load l a on arc a as
a .
To compute the flow to t, our first step is to use Dijkstra's algorithm to compute
all distances to t (normally Dijkstra's algorithm computes the distances away from some
source, but we can just apply such an implementation of Dijkstra's algorithm to the graph
obtained by reversing the orientation of all arcs in G). Having computed the distance d t
to t for each node u, we compute the set A t of arcs on shortest paths to t, that is,
For each node u, let ffi t
u denote its out degree in A t , i.e.
Observation 6 For all (v; w) 2 A t ,
l t
Proof. The even flow splitting on outgoing shortest path arcs gives the following straight-forward
calculation:
l t
(v;w)
):Using Observation 6, we can now compute all the loads l t
(v;w) as follows. The nodes v 2 N
are visited in order of decreasing distance d t
v to t. When visiting a node v, we first set
Second we set l t
l for each (v; w) 2 A t .
To see that the above algorithm works correctly, we assume, inductively, that we have
dealt correctly with all nodes visited before v. Since every arc (u; v) entering v in A t stems
from a node u strictly further from t, we know u has been visited previously. Hence, by
induction, the load l t
(u;v) is correct. Since all the incoming arcs loads are correct when v is
visited, the outgoing arc loads are computed correctly by Observation 6.
Using bucketing for the priority queue in Dijkstra's algorithm, the computation for each
destination takes time, and hence our total time bound is O(jN j 2 ).
7.2 The dynamic case
In our local search we want to evaluate the cost of many different weight settings, and
these evaluations are a bottleneck for our computation. To save time, we try to exploit the
fact that when we evaluate consecutive weight settings, typically only a few arc weights
change. Thus it makes sense to try to be lazy and not recompute everything from scratch,
but to reuse as much as possible. With respect to shortest paths, this idea is already well
studied (Ramalingam and Reps 1996), and we can apply their algorithm directly. Their
basic result is that, for the recomputation, we only spend time proportional to the number
of arcs incident to nodes u whose distance d t
u to t changes. In our experiments there were
typically only very few changes, so the gain was substantial - in the order of factor 15 for
a 100 node graph. Similar positive experiences with this laziness have been reported in
Frigioni et al. (1998).
The set of changed distances immediately gives us a set of "update" arcs to be added
to or deleted from A t . We now present a lazy method for finding the changes of loads.
We operate with a set M of "critical" nodes. Initially, M consists of all nodes with an
incoming or outgoing update arc. We repeat the following until M is empty: First, we
take the node v 2 M which maximizes the updated distance d t
v and remove v from M .
Finally, for each (v; w) in the updated A t , if
(v; w) is new or l 6= l t
(v;w) , set l t
l and add w to M .
To see that the above suffices, first note that the nodes visited are considered in order of
decreasing distances. This follows because we always take the node at the maximal distance
and because when we add a new node w to M , it is closer to t than the currently visited
node v. Consequently, our dynamic algorithm behaves exactly as our static algorithm
except that it does not treat nodes not in M . However, all nodes whose incoming or
outgoing arc set changes, or whose incoming arc loads change are put in M , so if a node
is skipped, we know that the loads around it would be exactly the same as in the previous
evaluation.
In order to measure the impact of the dynamic update of the cost on the performance of
our algorithm, we performed 500 iterations on various networks with different demand sets.
The results are presented in Table 1. From this table, we can see that dynamic updates
make the algorithm from 5 up to 25 times faster, with an average of 15 times faster. This
improvement was critical to us, as we typically ran the local search for a bit more than 1
hour in order to get good solutions.
8 Numerical Experiments
We present here our results obtained with a proposed AT&T WorldNet backbone as well
as synthetic internetworks.
Besides comparing our local search heuristic (HeurOSPF) with the general optimum
(OPT), we compared it with OSPF routing with "oblivious" weight settings based on
properties of the arc alone but ignoring the rest of the network. The oblivious heuristics
90 / 274 / 3814
90
90 / 274 / 19068 53 712 13.4
90
90 / 274 / 34323 52 443 8.5
90
Average: 144 2198 15.2

Table

1: Computing times for 500 iterations of local search (in seconds)
are
ffl InvCapOSPF, setting the weight of an arc inversely proportional to its capacity as
recommended by Cisco (1997). In each of our experiments, all capacities divided the
maximal capacity, so to get integer weights, for each link, we found the weight by
dividing the maximal capacity by the capacity of the link.
ffl UnitOSPF, setting all arc weights to 1,
ffl L2OSPF, setting the weight proportional to its physical Euclidean distance (L 2
norm), and
ffl RandomOSPF, just choosing the weights randomly.
Our local search heuristic starts with randomly generated weights and performs 5000 it-
erations, which for the largest graphs took approximately one hour. The random starting
point was weights chosen for RandomOSPF, so the initial cost of our local search is that
of RandomOSPF.
The results for the AT&T WorldNet backbone with different scalings of the projected
demand matrix are presented in Table 2. Here, by scaling a demand matrix, we mean that
we multiply all entries with a common number. Each algorithm was run once independently
for each scaling. Hence OPT, RandomOSPF, and HeurOSPF use different routings for
different scalings whereas UnitOSPF and InvCapOSPF always use the same routing. In
each entry we have the normalized cost \Phi   introduced in Section 3. The normalized cost
is followed by the max-utilization in parenthesis. The bold line in the table corresponds to
the original non-scaled demand.
For all the OSPF schemes, the normalized cost and max-utilization are calculated for
the same weight setting and routing. However, for OPT, the optimal normalized cost and
the optimal max-utilization are computed independently with different routing. We do
not expect any general routing to be able to get the optimal normalized cost and max-
utilization simultaneously. The results are also depicted graphically in Figure 7. The first
graph shows the normalized cost and the horizontal line shows our threshold of
3 for
regarding the network as congested. The second graph shows the max-utilization.
We also generated three flavors of synthetic graphs.
2-level hierarchical graphs: these graphs were produced using the generator GT-ITM
(Zegura 1996), based on a model of Calvert et al. (1997) and Zegura et al.
(1996). Arcs are divided in two classes: local access arcs and long distance arcs. Arc
capacities are equal to 200 for local access arcs and to 1000 for long distance arcs.
Purely random graphs: the probability of having an arc between two nodes is given by
a constant parameter used to control the density of the graph. All arc capacities are
set to 1000.
90 / 274 / 3709 1.00 (0.10) 1.00 (0.15) 1.01 (0.15) 1.13 (0.23) 1.12 (0.35) 1.00 (0.17)
90 / 274 / 7417 1.00 (0.19) 1.00 (0.31) 1.01 (0.30) 1.15 (0.46) 1.91 (1.05) 1.00 (0.30)
90 / 274 / 11126 1.01 (0.29) 1.03 (0.46) 1.05 (0.45) 1.21 (0.70) 1.36 (0.66) 1.01 (0.34)
90 / 274 / 14835 1.04 (0.39) 1.13 (0.62) 1.15 (0.60) 1.42 (0.93) 12.76 (1.15) 1.05 (0.47)
90
90
90
90
90
90
90
90

Table

2: Results for proposed AT&T WorldNet backbone
Waxman graphs: nodes are uniformly distributed points in a unit square and the probability
of having an arc between two nodes u and v is given by
where ff and fi are parameters used to control the density of the graph, ffi(u; v) is the
Euclidean distance between u and v and \Delta is the maximum distance between two
nodes (Waxman 1988). All arc capacities are set to 1000.
Above, the 2-level hierarchical graphs are the most realistic known models for internetworks
while the random graphs and Waxman graphs are cleaner from a mathematical perspective.
The demands are generated as follows. For each node u, we pick two random numbers
O . Further, for each pair (u; v) of nodes we pick a random number C (u;v) 2
[0; 1]. The demand between u and v is
ffO u D v C (u;v) e \Gammaffi(u;v)
Here ff is a parameter and \Delta is again the largest Euclidean distance between any pair of
nodes. Above, the O u and D v reflect the fact that different nodes can be more or less active
senders and receivers, thus modeling hot spots on the net. Because we are multiplying three
random variables, we have a quite large variation in the demands. The factor e \Gammaffi(u;v)=2\Delta
implies that we have relatively more demand between close pairs of nodes. The results for
the synthetic networks are presented in Figures 12-19. Note that for random and Waxman
graphs, all capacities are equal, so InvCapOSPF is represented via UnitOSPF.
9 Discussion
We presented in this paper a local search heuristic for optimizing OSPF weights used for
intra-domain internet routing. This heuristic was tested on a substantial set of instances,
cost
demand
InvCapOSPF
UnitOSPF
HeurOSPF
OPT0.20.611.4
max-utilization
demand
InvCapOSPF
UnitOSPF
HeurOSPF
OPT

Figure

7: AT&T's proposed backbone with 90 nodes and 274 arcs and scaled projected
cost
demand
InvCapOSPF
UnitOSPF
HeurOSPF
OPT0.20.611.4
max-utilization
demand
InvCapOSPF
UnitOSPF
HeurOSPF
OPT

Figure

8: 2-level graph with 50 nodes and 148 arcs2610140 1000 2000 3000 4000 5000 6000
cost
demand
InvCapOSPF
UnitOSPF
HeurOSPF
OPT0.20.611.4
max-utilization
demand
InvCapOSPF
UnitOSPF
HeurOSPF
OPT

Figure

9: 2-level graph with 50 nodes and 212 arcs
d
InvCapOSPF
UnitOSPF
HeurOSPF
OPT0.20.611.4
max-utilization
demand
InvCapOSPF
UnitOSPF
HeurOSPF
OPT

Figure

10: 2-level graph with 100 nodes and 280 arcs2610140 2000 4000 6000 8000 10000 12000 14000 16000 18000
cost
demand
InvCapOSPF
UnitOSPF
HeurOSPF
OPT0.20.611.4
max-utilization
demand
InvCapOSPF
UnitOSPF
HeurOSPF
OPT

Figure

11: 2-level graph with 100 nodes and 360 arcs
d
UnitOSPF
HeurOSPF
OPT0.20.611.4
max-utilization
demand
UnitOSPF
HeurOSPF
OPT

Figure

13: Random graph with 50 nodes and 245 arcs261014
cost
demand
UnitOSPF
HeurOSPF
OPT0.20.611.4
max-utilization
demand
UnitOSPF
HeurOSPF
OPT

Figure

14: Random graph with 100 nodes and 403 arcs
cost
demand
UnitOSPF
HeurOSPF
OPT0.20.611.4
max-utilization
demand
UnitOSPF
HeurOSPF
OPT

Figure

17: Waxman graph with 50 nodes and 230 arcs261014
cost
demand
UnitOSPF
HeurOSPF
OPT0.20.611.4
max-utilization
demand
UnitOSPF
HeurOSPF
OPT

Figure

18: Waxman graph with 100 nodes and 391 arcs
s
including a proposed AT&T WorldNet backbone with projected demands. It would have
been nice to run on more real world data, but such data are typically company secrets.
If we consider the results for the AT&T WorldNet backbone with projected (non-scaled)
demands, i.e. the bold line in Table 7, we observe that our heuristic, HeurOSPF, is within
1.8% from optimality. In contrast, the oblivious methods are all off by at least 15%.
Considering the general picture for the normalized costs in Figures 7-19, we see that
L2OSPF and RandomOSPF typically do worst. Then comes InvCapOSPF and UnitOSPF
closely together, with InvCapOSPF being generally slightly better (for the random and
Waxman graphs in Figures 12-19, InvCapOSPF coincides with UnitOSPF since all links
have the same capacity). Recall that InvCapOSPF is Cisco's recommendation, so it is
comforting to see that it is the best of the oblivious heuristics. The clear winner of the
OSPF schemes is our HeurOSPF, which is, in fact, much closer to the general optimum
than to the oblivious OSPF schemes.
To quantify the difference between the different schemes, note that all curves, but those
for RandomOSPF, start off pretty flat, and then, quite suddenly, start increasing rapidly.
This pattern is somewhat similar to that in Figure 1. This is not surprising since Figure 1
shows the curve for a network consisting of a single arc. The reason why RandomOSPF
does not follow this pattern is that the weight settings are generated randomly for each
entry. The jumps of the curve for RandomOSPF in Figure 10 nicely illustrate the luck
impact in the weight setting. One could, of course, have run RandomOSPF several times,
and used the best solution, but from the figures it is clear that even if it is erratic how badly
RandomOSPF performs, it is never the best. The purpose of including RandomOSPF is
to be able to compare the other weight settings with random choices. Interestingly, for
any particular demand, the value of RandomOSPF is the value of the initial solution for
our local search heuristic. However, the jumps of RandomOSPF are not transferred to
HeurOSPF which hence seems oblivious to the quality of the initial solution.
The most interesting comparison between the different schemes is the amount of demand
they can cope with before the network gets too congested. In Section 3, we defined
2as the threshold for congestion, but the exact threshold is inconsequential. Considering
the proposed AT&T WorldNet backbone in Figure 7 and for the 2-level graphs in

Figures

8-11, we see that HeurOSPF allows us to cope with 50%-115% more demand than
Cisco's recommended InvCapOSPF, with an average around 70%. The maximum of 115%
is achieved in Figure 9. In this particular figure, L2OSPF actually does quite well, but
generally InvCapOSPF is the better of the oblivious heuristics, and hence the most challenging
one to compete with. Moreover, in all but Figure 9, HeurOSPF is less than 2%
from being able to cope with the same demands as the optimal general routing OPT. In

Figure

9, HeurOSPF is about 20% from OPT. Recall from Theorem 3 that it is NP-hard to
approximate the optimal cost of an OSPF solution within a factor 3, and we have no idea
whether there exist OSPF solutions closer to OPT than the ones found by our heuristic.
The above picture is generally repeated for the random graphs in Figures 12-15, except
that our HeurOSPF tends to be a little further away from OPT, though still by less than
10%. For the Waxman graphs in Figures 16-19, the most significant difference relative to
the other models is that Unit/InvCapOSPF tends to get closer to OPT, with OPT only
allowing for in average 30% increase in demands, thus leaving less scope for improvement.
On the other hand, for the Waxman graphs, HeurOSPF nearly coincides with OPT. The
random and Waxman graphs are considered much less realistic than the 2-level graphs, but
we see them as supporting evidence for conjecturing that for typical internetworks, Heur-
OSPF will be able to supply large parts of the gain that OPT may have over InvCapOSPF,
or any other of the oblivious heuristics.
If we now turn our attention to max-utilization, we get the same ordering of the schemes,
with InvCapOSPF the winner among the oblivious schemes and HeurOSPF the overall best
OSPF scheme. The advantage of using HeurOSPF for max-utilization is interesting in that
our local search did not use max-utilization as its objective.
The step-like pattern of HeurOSPF show the impact of the changes in \Phi 0
a . For example,
in

Figure

7, we see how HeurOSPF fights to keep the max utilization below 1, in order to
avoid the high penalty for getting load above capacity. Following the pattern in our analysis
for the normalized cost, we can ask how much more demand we can deal with before getting
max-utilization above 1, and we see that HeurOSPF again beats the oblivious schemes by
at least 50% for the proposed AT&T WorldNet backbone and the 2-level graphs.
The fact that our HeurOSPF provides weight settings and routings that are simultaneously
good both for our best effort type average cost function, and for the performance
guarantee type measure of max-utilization indicates that the weights obtained are "univer-
sally good" and not just tuned for our particular cost function. Recall that the values for
OPT are not for the same routings, and there may be no general routing getting simultaneously
closer to the optimal cost and the optimal max-utilization than HeurOSPF. Anyhow,
our HeurOSPF is generally so close to OPT that there is little scope for improvement.
We have presented worst-case examples showing that there are cases where even the best
OSPF weight setting leads to very bad routing as compared with the the best general
routing. Also, we have shown that it is NP-hard to find even an approximately optimal
OSPF weight setting. These negative findings are contrasted by the positive findings in
our experimental work, where our weight setting heuristic produces OSPF routings that
are quite close in performance to that of the best possible general routings. This indicates
that the negative examples for OSPF routing are too contrived to dominate in practice.
For the proposed AT&T WorldNet backbone and for the 2-level graphs suggested in
(Zegura, Calvert, and Bhattacharjee 1996; Calvert, Doar, and Zegura 1997), our OSPF
weight setting heuristic further distinguished itself by producing weight settings allowing
for a 50-115% increase in demands over what is achieved with standard weight setting
heuristics, such as using inverse capacity as recommended by Cisco (1997). Thus we have
shown that in the context of known demands, a clever weight setting algorithm for OSPF
routing is a powerful tool for increasing a network's ability to honor increasing demands,
and that OSPF with clever weight setting can provide large parts of the potential gains of
traffic engineering for supporting demands, even when compared with the possibilities of
the much more flexible MPLS schemes.
In future work, we will study robustness issues such as link failures and appearance of
hot-spots on the internet.
A NP-hardness proofs
In this appendix, we prove the NP-hardness results claimed in Section 5. The proofs are
done partly in collaboration with David Johnson and Christos Papadimitriou. First we
prove the hardness of minimizing the max-utilization, and second we prove hardness with
respect to summation-based cost functions like \Phi. The proof for max-utilization is much
easier, and helps presenting some of the basic ideas needed for the summation based cost
functions.
Recall from Section 5:
Theorem 5 It is NP-hard to optimize the max-utilization in OSPF routing within a
Proof of Theorem 5. We prove this result by reducing 3SAT to the problem of optimizing
OSPF weight setting with respect to max-utilization. More precisely, let
an instance of 3SAT with variable set X and clause set C where each clause has 3 literals
(Cook 1971). We construct an instance of the OSPF weight setting problem such that
ffl there exists a satisfiable assignment for the 3SAT instance if and only if the max-
utilization in the OSPF instance is equal to 1;
ffl if there is no satisfiable assignment for the 3SAT instance, the max-utilization for
any weight setting is at least 3=2.
Fx
vx
tx
sx

Figure

20: Reduction from 3SAT to OSPF max-utilization
The construction of the graph G corresponding to the 3SAT instance is
illustrated in Figure 20. With each clause c 2 C, we associate a node c 2 N S . All these
nodes are connected by an arc of capacity 2 to a global node w.
For each variable x 2 X, let jxj denote the least power of 2 bounding both the number of
negative and the number of positive occurrences of x in S. With each x 2 X, we associate
a source s x and a destination t x , with demand 2jxj between them. Furthermore, for each
x, we have three nodes v x , F x , and T x , and arcs (s x
The arcs (v x
Balanced binary trees with jxj leaves are rooted at F x and T x . For each positive (negative)
occurrence of x in a clause c, we have an arc from a leaf under F x (T x ) to the node c.
Each leaf can only be used for one occurrence of x in the clauses. Each leaf which is not
connected to a clause is connected to a global node u, which in turn is connected to w.
The arcs inside the binary trees have capacity jxj while the arcs from the leaves to the
clauses or to u all have capacity 1. Arc (u; w) has capacity
x2X jxj, and for all x, there
is an arc from w to t x with capacity jxj.
A canonical flow in this network is defined as a flow corresponding to an assignment of
values to the variables in x. More precisely, in a canonical flow, we have jxj units of flow
going down (v x ; t x ) and jxj units going to either T x or F x depending on whether x is true or
false. If the flow comes to T x it spreads evenly so that we get 1 unit leaving each leaf going
either to a clause node c or to u, and then these jxj units of flow are sent to t x through w.
With this assignment of flows, for each clause c, there is 1 unit of flow through (c; w) for
each negative literal in c. Thus, if the clause c is satisfied, it has at most 2 negative literals
and then the load stays within the capacity of (c; w). Otherwise, the load on (c; w) is 3
and the utilization of (c; w) goes to 3=2. All other loads in a canonical flow stay within the
capacities.
Now suppose we are given a non-canonical flow satisfying the OSPF routing condition
that if the flow to a destination splits, it splits evenly. We will show that max-utilization for
this non-canonical flow is at least 3=2. It is easy to see that a non-canonical flow satisfies
at least one of the following conditions for some x:
(i) only one of (v
are all used;
exactly one of (s are used. However, there is at least
one internal node in one of the binary trees where the flow does not split down to
both children.
In case (i), the only arc which is used gets a flow of 2jxj, leading to max-utilization 2.
In case (ii) where (v x ; t x ) is not used, we get all the flow from s x through (w; t x ), leading
to max-utilization 2. In case (iii) where all of (v are used, even
splitting implies that 1=2 of the flow goes down (s x ; T x ) while 1=4 goes down each of (v x
and (v x ; F x ). As a result, we must get 3=4 \Delta leading to
a max-utilization of 3=2. In case (iv) we have jxj units of flow arriving at T x (or F x ).
Consider a node a of the binary tree below T x (or F x ) where the flow does not split and
which is closest possible to T x (or F x ). Then the flow splits evenly above a, so a receives
exactly one unit of flow for each leaf descending from a. However, all the flow to a is sent
down to one child with only half as many descending leaves, so one of these leaves must
receive 2 units of flow, which is twice the capacity of its outgoing arc.
We have now shown that an evenly splitting flow leads to a max-utilization equal to 1
if and only if the flow is canonical and corresponds to a satisfiable assignment; any other
evenly splitting flow leads to a max-utilization greater than or equal to 3/2.
It remains to show that any satisfiable canonical flow can be achieved by a suitable
set of weights for OSPF routing. This is done as follows. All paths from s x to t x going
through T x use 4+ log 2 jxj arcs, those going through F x use 5+ log 2 jxj arcs, and the direct
path arcs. If the canonical flow leads to a true value for x, then flow splits
equally at s x and does not split at v x , which is achieved if the paths going through T x
and the direct path have the same weight, while the paths going through F x have a larger
weight. Giving a weight equal to 3 weight equal to 1 to all the
other arcs leads to such a weight setting. If the canonical flow leads to a false value for x,
then flow does not split at s x and splits equally at v x , which is achieved if the paths going
through F x and the direct path have the same weight, while the paths going through T x
have a larger weight. Giving a weight equal to 4 to (v x ; t x ), a weight equal to 3
to weight equal to 1 to all the other arcs leads to such a weight setting.
In conclusion, there exists a satisfiable assignment if and only if there exists an OSPF
weight setting leading to a max-utilization of 1. Conversely, we have shown that any evenly
splitting flow that does not correspond to a satisfying truth assignment has max-utilization
greater than or equal to 3/2. Hence, approximating the max-utilization within a factor
implies a solution to 3SAT. 2
We will now prove the other result from Section 5, stating the inapproximability of the
OSPF weight setting problem with respect to a large class of cost functions, including our
cost function \Phi.
Theorem 4 Let ff and fi be fixed constants. Suppose our total routing cost is
a2A \Psi a ('(a)) where
\Psi a (l) - ffl if l - c(a);
\Psi a (l) - ffc(a)
Then, if fi - 52ff, it is NP-hard to optimize the OSPF weight setting with respect to
a2A \Psi a (l(a)) within a factor 0:72 optimality.
Recall from Section 5 that Theorem 4 implies an inapproximability factor of 3.1 for our
cost function \Phi. The proof follows the same pattern as we used for max-utilization, but
is more complex because we are dealing with a sum rather than a maximum. It is based
on the following deep inapproximability result implicit in H-astad (1997) (H-astad, personal
Lemma 7 (H-astad) Given a satisfiable instance of Max-SAT where each clause has 3
literals and each variable has the same number of positive and negative occurrences, it is
NP-hard to satisfy a fraction 701=800 of the clauses.
Proof of Theorem 4. We prove this result by reducing a satisfiable instance of Max-SAT
where each clause has 3 literals and each variable has the same number of positive and
negative occurrences to the OSPF weight setting problem, such that we can use Lemma 7.
Our reduction is similar to that for max-utilization, and is illustrated in Figure 21. The
main differences relative to construction for max-utilization are that we have subdivided
some arcs into paths so as to give them higher weight in the cost function, and that we
have contracted the binary trees rooted in T x and F x .
Formally, let C) be a satisfiable instance of Max-SAT with variable set X and
clause set C where each clause has 3 literals and each variable has the same number of
positive and negative occurrences. Let jxj denote this number of occurrences for a clause
x in C.
As for max-utilization, there is a node c associated to each clause c 2 C, connected to
a node w through a path P c - instead of a single arc - where P c has jP c
capacity 2. With each variable x 2 X, we associate a source s x and a destination t x , and
a demand of 2jxj between them. From s x , there are outgoing arcs to two nodes v x and T x
and there is an arc from v x to a node F x . Instead of the arc (v x ; t x ), there is now a path
sx
Fx
Pc
Rx
Fx
Qx
tx
vx

Figure

21: Reduction from 3SAT to our OSPF cost function
Q x from v x to t x . The arcs
has jQ x arcs, each of capacity jxj.
From T x , there is a path P c
to c for each clause c in which x occurs negatively. Similarly,
from F x there is a path P c
Fx to c for each clause c in which x occurs positively. Path P c
Fx
have jP c
have jP c
arcs, each of capacity 1. Finally, for
each x 2 X, we have a path R x from w to t x with 3 arcs, each with capacity jxj.
As in Theorem 5, we define a canonical flow in this network as a flow corresponding to
an assignment of values to the variables in x. In a canonical flow, we have jxj units of flow
going down Q x and jxj units going to either T x or F x depending on whether x is true or
false. If the flow comes to T x , it spreads evenly so that each P c
gets 1 unit of flow going
to c. Similarly, if the flow is sent to F x , each P c
Fx gets 1 unit of flow going to c. All flow
arriving a clause c is then sent to w via P c , and finally to t x via R x . With this assignment
of flows, for every clause c, there is 1 unit of flow through P c for each negative literal in c.
Thus, if the clause c is satisfied, it has at most 2 negative literals and then the load stays
within the capacity on P c . Otherwise, the load on P c is one unit above capacity. All flows
outside the clause paths P c stay within the capacities.
Our hardness result is based on showing that it is hard to get a flow of cost close to
that of the canonical flow corresponding to a satisfying truth assignment. Since, such a
satisfying flow has all loads within capacity, we only make the approximation easier if we
reduce the costs of loads above the capacity. Hence, for proving the hardness, we may
assume
a
The remainder of the proof is organized as follows: first we show that we can transform
in polynomial time a non-canonical even splitting flow to a canonical flow of smaller cost.
Next we show that any canonical flow can be achieved with a suitable weight setting.
Finally, we apply Lemma 7 to show that a canonical flows of low cost is hard to find.
Lemma 8 A non-canonical even splitting flow can be transformed in polynomial time to
a canonical flow of smaller cost.
Proof. Suppose we have a non-canonical flow. We show we can always find a flow of
lower cost. It is easy to see that a non-canonical flow satisfies at least one of the following
conditions for some x:
(i) only one of Q
(ii) Q x is not used;
are all used;
(iv) (a) if there is flow through F x , not all P c
Fx paths are used;
(b) if there is flow through T x , not all P c
paths are used.
In case (i), if Q x is the only included one, it receives 2jxj units of flow, i.e. jxj units
above capacity. If we move this extra flow - by splitting equally in v x - to F x and then
send one unit through each P c
Fx , we decrease the cost on Q x by fijQ x jjxj, while none of
Fx and R x get above capacity. As they were not used before, each unit of flow
transferred to these paths cost at most ff per arc. Only P c could get an increase of jxj
units above capacity, so the total increase in cost due to the new routing is bounded by
j)jxj. The net decrease in cost is thus
as fi - 52ff. Similarly, if only (s x ; T x ) or only (v x ; F x ) is used, moving half the flow to Q x
(which was empty) leads to a decrease in cost of at least
Above we did not count gain from moving flow from clause paths P c . The point is that
these paths may have had load strictly below capacity, and then we have no lower bound
on what they cost.
In case (ii), we can suppose both are used; for otherwise we come
back to the previous case. Then R x has jxj units of flow above capacity. Moving the jxj
units of flow going through F x to the empty jQ x j leads to a decrease in cost of at least
In case (iii), the even splitting implies that we get jxj=2 units of flow to Q x and F x
while we get jxj units of flow to T x . We then move the flow from F x to Q x . By doing so,
we reduce the flow trough R x from 3jxj=2 to jxj. The only place where the flow and hence
the cost increases is in Q x , from jxj=2 to jxj. However, the flow in Q x remains within the
capacity, and the total cost on this path is bounded by ffjQ x jjxj, leading to a decrease in
cost of
Thus we can now assume that Q x and exactly one of F x and T x are used, as in (iv).
To deal with case (iv)(a), it remains to show that if F x is included, then it is beneficial to
include all paths P c
Fx . Suppose q of them were not included, and now we include them.
Afterwards, each path P c
Fx has exactly 1 unit of flow corresponding to its capacity. This
means that the q units of flow that we moved to the empty paths were previously above
capacity. However, now q units of flow are sent differently through P c , each at cost at most
fijP c j, leading to a cost decrease of at least
In case (iv)(b) the cost decrease becomes
canonical flow can be achieved with a suitable OSPF weight setting.
Proof. All paths form s x to t x going through T x or F x use 207 arcs, while path s x
uses 104 arcs. If the canonical flow leads to a true value for x, then flow splits equally in s x
and do not split in v x , which is achieved if the paths going through T x and path s x
have the same weight, while the paths going through F x have a larger weight. Giving a
weight equal to 2 to arcs in Q x and to (v x ; F x ) and a weight equal to 1 to all the other arcs
leads to such a weight setting. In the case a false value is assigned to x, similar arguments
lead to a weight equal to 2 for arcs in Q x and for (s x ; T x ) and a weight equal to 1 for all
the other arcs. 2
We are now ready for finishing the proof of Theorem 4. By Lemma 8, we know that
only canonical flows are of interest, and Lemma 9 ensures these flows can be obtained using
OSPF routing.
A canonical flow corresponding to a satisfiable assignment of values to variables in X
is such that all loads remain within capacities. Moreover, for each variable x, jxj units
of flow are sent through T x or F x on paths using 207 arcs, and jxj units of flow are sent
through Q x on paths using 104 arcs, leading to a total cost of at most 311ff
x2X jxj.
On the other hand, consider the canonical flow corresponding to an assignment satisfying
at most 701=800 of the clauses. The routing down Q x , the P c
or P c
Fx , and R x costs ff
per unit of flow and per arcs, since all the used paths are exactly loaded to their capacity.
Moreover, for each unsatisfied clause c, P c has a load of 3 while the capacity is 2, thus
contributing (2ff to the total cost. As the total number of clauses is
the total cost of at least
where we ignore any load that may be below capacity for some P c .
By Lemma 7, it is NP-hard to get an assignment satisfying more than a fraction 701=800
of the clauses, so we can conclude that it is NP-hard to approximate the optimal OSPF
weight setting within a factor of
which concludes the proof of Theorem 4. 2

Acknowledgment

We would like to thank David Johnson and Jennifer Rexford for some very useful comments.
The first author was sponsored by the AT&T Research Prize 1997.



--R

Local Search in Combinatorial Optimization.
Discrete Mathematics and Optimization.

The reactive tabu search.
Design of broadband virtual private networks: Model and heuristics for the B-WiN

A note on hashing functions and tabu search algo- rithms
Universal classes of hash functions.

The complexity of theorem proving procedures.
Universal hashing and k-wise independent random variables via integer arithmetic without primes

Netscope: Traffic engineering for ip networks.
Experimental analysis of dynamic algorithms for the single-source shortest path problem
Future paths for integer programming and links to artificial intelli- gence
Tabu search-Part I
Tabu search-Part II
Some optimal inapproximability results.
on Theory of Computing (STOC)
A polynomial time algorithm for linear programming.

The Art of Computer Programming III: Sorting and Searching.

Minimax open shortest path first routing algorithms in networks supporing the smds services.
OSPF: Anatomy of an Internet Routing Protocal.
An incremental algorithm for a generalization of the shortest-path problem
Optimal routing in data networks.

Routing of multipoint connections.
Hashing vectors for tabu search.

http://www.
How to model an internet- work
--TR
Future paths for integer programming and links to artificial intelligence
Hashing vectors for tabu search
An incremental algorithm for a generalization of the shortest-path problem
The art of computer programming, volume 3
Experimental analysis of dynamic algorithms for the single
Even strongly universal hashing is pretty fast
Detection of combined occurrences
Some optimal inapproximability results
OSPF
Local Search in Combinatorial Optimization
Tabu Search
Universal Hashing and k-Wise Independent Random Variables via Integer Arithmetic without Primes
The complexity of theorem-proving procedures

--CTR
Hakan mit, A column generation approach for IGP weight setting problem, Proceedings of the 2005 ACM conference on Emerging network experiment and technology, October 24-27, 2005, Toulouse, France
Makarem Bamatraf , Mohamed Othman, Improved balancing heuristics for optimizing shortest path routing, Computer Communications, v.30 n.7, p.1513-1526, May, 2007
Renata Teixeira , Timothy G. Griffin , Mauricio G. C. Resende , Jennifer Rexford, TIE breaking: tunable interdomain egress selection, IEEE/ACM Transactions on Networking (TON), v.15 n.4, p.761-774, August 2007
shortest path routing;local search;traffic engineering