Transcript Document

Optimizing OSPF


Bernard Fortz (Université Libre de Bruxelles)
Mikkel Thorup (AT&T Labs-Research)
Presented by : Lei Tian
OSPF
•Open Shortest Path First
•Link State SPF technology
•Variable-length subnet
masks
•Discontinuous subnets
•Developed by OSPF
working group of IETF (RFC •No periodic updates
1247)
•Route authentication
•Designed for TCP/IP
•OSPF standard described in
Internet environment
RFC 2328
•Fast convergence
The Metrics in OSPF
56 Kbps serial link
64 Kbps serial link
T1 (1.544 Mbps serial link)
E1 (2.048 Mbps serial link)
4 Mbps token ring
Ethernet
16 Mbps token ring
FDDI
1758
1562
65
48
25
10
6
1
Change the weight

Administrator can change the weight manually.





ip ospf cost
Use to configure the cost of sending a packet on the
network.
Cost is a metric value in the range 0-65535; the default
value is 1.
The router LSA advertises the link-state metric as the link
cost.
Example
host1(config)#interface fastethernet 0/0
host1(config-if)#ip ospf cost 50

Use the no version to reset the path cost to the default
value, 1.
How well does OSPF perform on
real network

We define the cost of an arc as
 1
 3

 10
 a '( x)   70

 500

5000
for
0  x / c(a )  1/ 3
for
1/ 3  x / c( a)  2 / 3
for
2 / 3  x / c( a)  9 /10
for
9 /10  x / c(a)  1
for
1  x / c(a)  11/10
for
11/10  x / c(a)
Cont.

For a given network topology, we can get the optimal
solution in term of link cost.
Minimize  a
aA
s.t.
y, s, t  N
 f
( s ,t )
( x, y )
( x , y )A
a  A, l a  
f
( s ,t )

 f
( y , z )A
( s ,t )
a
a  A,  a  l a
a  A,  a  3l a  (2 / 3)c(a)
a  A,  a  10l a  (16 / 3)c(a)
...
f
( s ,t )
a
, l a,  a  0
if
  D ( s, t )

  D ( s, t )
if
( y,z)
 0
otherwise

( s ,t )
ys
y t
OSPF vs general routing

Can OSPF perform as well as optimal
routing?


No
How close is OSPF compare with
general routing

Not even close
OSPF vs general routing cont.
For instance
3n
3n
3n
s
1
2
3
3
3
3
n
3
n2-2
3
n2-3
n2-4
n2-n-1
3
3
 n x  s, y  t
D( x, y)  
0 otherwise
3
t
OSPF vs general routing cont.
1
a, l (a)  c(a)
3
In general routing
3n
3n
3n
s
1
2
3
3
3
3
n
3
n2-2
n2-3
1
a
Each path has length n2
 OPT  R  n
1
1
n2-4
n2-n-1
 (l (a))  l (a)
1
t
3
OSPF vs general routing cont.
i,
n
s
1
n
i
2
3
n/2
3
2
n/4 3
3
n
3
 3.3   a(l (a))  5000l (a) 
n/2
n/4
n/8
19468
c(a)  5000l (a)  O(1)
3
3
  (n  i)(5000  O(1))  5000 n
2
2
2
i
n2-2
n2-3
n2-4
n2-n-1
n
i
i
 O(n 2 )
lim  OSPF
 5000
3
n 
t
n
Improve OSPF

Can we improve OSPF performance?


Yes, by changing the weight of each link.
Since it is NP-hard to find the optimal
solution of OSPF, so a Local Search
Heuristic to approximate optimal OSPF
is needed.
A Local Search Heuristic(HEUR)

W={1,2,…,wmax} is the set of all
possible weights.
The search is on all possible functions
(vectors) w : A W (W )
Start with a random vector x  w W
Do {

} Until x meets some optimality criteria


A
A

RAND
x  SEARCH ( N ( x )  W )
A
The Neighborhood Structure

x '  N ( x) if x’ can be obtained from x
by one of the following two:

Single weight change:



Choose an arc and change its weight
There are |A|x(|W|-1) such neighbors
Evenly balance flows:


Choose a node x and a destination t and
balance
There are |N|x(|N|-1) such neighbors
Evenly Balancing Flows
x1
P1
x2
x
P2
x3
t
P3
xp
Pp
*
w
 1  max{w( P i ) |1  i  p}
w 'i  w  w( P i)
*
Every xi is on a shortest path to t.
Local Search

Do {
x  SEARCH ( N ( x))




} Until x is a local minimum
SEARCH returns x’ s.t. cost(x’)<cost(x)
Problem: A local minimum may be far
from global minimum
Solution: Allow non-improving moves
Local Search (cont’d)




Problem: We may encounter cycles.
Solution: Tabu Search (maintain a tabu
list of the attributes of visited points)
HEUR uses a hash function h and a
table T with 1 bit for each possible
value of h.
If T(h(x’))=true, SEARCH does not
return x’.
Local Search (cont’d)



Problem: Duplicate neighbors due to
the complex neighborhood structure.
Solution: SEARCH maintains an internal
hash table T’.
If T’(h(x’))=true, SEARCH does not
evaluate the cost of x’.
Local Search (cont’d)


Problem: Too much neighbors.
Solution:




r=0.2
At each iteration evaluate only a subset of
the neighbors such that | N '( x) | r | N ( x) |
If (the cost is improved) {r=max(0.01,r/3)}
Else {r=min(1,10c)}
Diversification


In order to avoid “long valley”.
If cost is not improved for 300
iterations, perturb x by adding a
random perturbation, selected at
random from [-2,2] to %10 of the
weights.
Numerical Results

Two Additional routings are measured,
along the others:


L2OSPF : weights proportional to the
Euclidean distance between nodes.
RANDOMOSPF : Weight are assigned
randomly (The first step of HEUR).
Costs on a real network
14
12
OPT
RANDOM
HEUR
UNITOSPF
L2OSPF
INVCAP
THRESHOLD
10
8
6
4
2
0
Demand
Conclusion

HEUR is the best algorithm.


In fact it is the only algorithm “knowing”
the demands
It achieves performance close to %2 of
OPT.