|
OPTIMIZATION IN THE SHORTEST PATH FIRST COMPUTATION
FOR THE QUAGGA SOFTWARE
ROUTING
V. Eramo, M. Listanti,
G. Gasparro, A. Cianfrani
University of Roma “La
Sapienza”, INFOCOM Dept.
Via Eudossiana, 18 – 00184 Roma, Italy
Tel: +39 6 44585458; Fax: +39 6 4744481
E-mail: eramo@infocom.uniroma1.it
3. THE SEARCH FUNCTION OF A NETWORK_LSA IN THE DATABASE
We have found a
problem with one of the search functions exploited during the SPF
calculation. The lsa database is
structured as a binary tree, ordered with binary prefixes of increasing
length. Each node of the database has a prefix shorter than the one of its
children. If a node has a prefix with h
bits, then its children have a prefix with k+1>h bits and
with the first h bits equal to
the ones of the father. In particular the (k+1)-th bit is equal
to 0 or 1 for the left and right child respectively.
The prefix of a
node representing an lsa consists
of the Link State ID and the Advertising Router ID of the lsa itself for a total of 64 bits.
If you need to search a particular lsa,
you can construct its prefix merging the Link State ID and the Advertising
Router ID of the lsa, and go down
along the database, reaching the node with the given prefix.
Now the problem is
that each lsa records, for each outgoing link, the Link State ID of the
linked vertex. So, when you want to find the lsa of a linked vertex, you do not know the entire prefix of
the node, but only half of it because you miss the Advertising Router ID.
Is that a problem ? No. There would never be two different LSAs with the
same Link State ID, so it should be sufficient to find an lsa in the database.
If a Router_lsa must be
searched, there are not any problem because the Advertising Router ID is
equal to the Link State ID and hence the entire prefix can be constructed
using the Link State ID twice. That is how the “ospf_lsa_lookup_by_id()” function, defined in “ospf_lsa.c” file, works when a
Router_lsa is searched. In
particular the “ospf_lsdb_by_id()”
function, defined in “ospf_lsdb.c”
file, is called and the search of a Router_lsa is performed by taking into account that data structure of
the database is a binary tree. On the contrary what is the solution when
looking for a Network_lsa that
have an Advertising Router ID different from the Link State ID ? The
“ospf_lsa_lookup_by_id()”
function perfoms the search in a not effective way because it scans
sequentially the entire Network_lsa
database and finds the lsa with
the given Link State ID. This is shown in Figure 8
where we report the “ospf_lsa_lookup_by_id()”
function, defined in “ospf_spf.c”
file.
To optimize the
search of a Network_lsa in the
database we introduce the “route_node_lookup_partial”
function, defined in “table.c”
file and reported in Figure 9. This function
exploits the sorting of the Network_lsa
database. In particular the “route_node_lookup_partial”
function looks for a node in the in the database with a prefix longer (64
bit) than and matching the prefix of a Network_lsa (32 bit).
The new version of the “ospf_lsa_lookup_by_id”
function is reported in Figure 10.
|
