"Optimal Configuration of OSPF Aggregates"
Abstract
Open Shortest Path First (OSPF) is a popular protocol for routing
within an Autonomous System (AS) domain.
In order to scale for large networks containing hundreds and thousands
of subnets, OSPF supports a two-level hierarchical routing scheme through
the use of OSPF areas.
Subnet addresses within an area are aggregated, and this aggregation
is a crucial requirement for scaling OSPF
to large AS domains, as it results in significant reductions in routing table
sizes, smaller link-state databases, and less network traffic to synchronize
the router link-state databases.
On the other hand, address aggregation also implies loss of information
about the length of the shortest path to each subnet,
which in turn, can lead to suboptimal routing.
In this paper, we address the important practical problem of configuring
OSPF aggregates to minimize the error in OSPF shortest path computations
due to subnet aggregation.
We first develop an optimal dynamic programming algorithm that,
given an upper bound k on the number of aggregates to be advertised
and a weight-assignment function for the aggregates, computes the
k aggregates that result in the minimum cumulative error in the
shortest path computations for all source-destination subnet pairs.
Subsequently, we tackle the problem of assigning weights to OSPF
aggregates such that the cumulative error in the computed shortest
paths is minimized.
We demonstrate that, while for certain special cases (e.g., unweighted cumulative
error) efficient optimal algorithms for the weight-assignment problem can be devised,
the general problem itself is NP-hard.
Consequently, we have to rely on search heuristics to solve the weight-assignment
problem.
To the best of our knowledge, our work is the first to address the algorithmic
issues underlying the configuration of OSPF aggregates and to propose efficient
configuration algorithms that are provably optimal for many practical
scenarios.
[
camera-ready paper
(pdf)
(ps.gz)
|
journal version
(pdf)
(in IEEE/ACM Transactions on Networking)
|
Rajeev's talk slides
(ppt.gz)
]
Copyright © 2002, IEEE.
Personal use of this material is permitted. However, permission to
reprint/republish this material for advertising or promotional purposes or for
creating new collective works for resale or redistribution to servers or lists,
or to reuse any copyrighted component of this work in other works must be
obtained from the IEEE.