|
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
1. THE SHORTEST PATH FIRST ALGORITHM
The main changes we have carried
out in SPF computation are the following: i) the Candidate List has been replaced by a
Binary Heap data structure; ii) the lsa
(link state advertisement)
structure and the vertex structure have been provided with a new field
which stores the status of a vertex during the execution of the Dijkstra
algorithm; iii) some functions and some data structures have been
consequentially modified.
Let us start with the lsa
structure in “ospf_lsa.h”.
A part of the declaration of “struct
ospf_lsa” is reported in Figure 1.
The new “stat” field is an integer and
stores the status of the lsa
during the SPF algorithm. It can assume two negative values or positive
values. The value -1 means that the node has not been reached by the SPF
algorithm yet. The value -2, instead, means that the node has already been
extracted from the Candidates and inserted into the Spanning Tree. Note
that there is not a Spanning Tree in OSPF, because we only need the
next-hop list of a node, but what is important is avoiding to process a
node twice or more. If a node has already been reached by the algorithm,
but it is not in the Spanning Tree yet, then it must be in the Candidate
List. In this case the “stat”
field is a positive value, and records the position of the node inside the
Candidate List. In fact the Candidate List is implemented by means of an
array and the array component, in which the node is stored, is reported in “stat” field. This way once you
have an lsa of a node with a
positive “stat”, you
can directly access to its node in the Candidates List. The introduction of
the “stat” field is
necessary because the Binary Heap does not support the search operation of
an element in an effective way.
Even the vertex
structure in “ospf_spf.h”
has been modified. As you can notice in Figure 2,
we have added a new field, called (again) “stat”, that is a pointer linked to the “stat” field of the associated lsa.
Now let us take a look at the SPF algorithm in “ospf_spf.c”. Two functions
have been modified: “ospf_spf_calculate()”
and “ospf_spf_next()”.
Start with “ospf_spf_calculate()”
illustrated in Figure 3. The Candidate List data
structure now is an Binary Heap. Moreover thanks to the new “stat” field, the two databases
“rv” and “nv” that stored the vertexes
already extracted from the Candidate List, are no longer needed and they
can be removed, together with the “ospf_spf_register()” and “ospf_spf_has_vertex()” functions. The initialization of
the data structures only consists in setting the status of all the lsas to the value -1 (notEXPLORED). This operation is
performed by the “ospf_lsdb_clean_stat
()” function implemented in “ospf_lsdb.c”. Moreover the Candidate List data structure
is initialised according to the “pqueue_create”
function defined in “pqueue.c”.
Other initialisations, that we will discuss in Section 2, are performed on
the candidate variable. After the
initialisation phase, the root
node is inserted in the Spanning Tree and the “stat” field of the lsa
associated to the root node is
updated to the value -2 (inSPFtree).
Hence the “ospf_spf_next()”
function is accomplished and the end of the Dijkstra algorithm is tested by
analysing if the Candidate List is empty, that is if the “size” fields (see “struct pqueue” in “pqueue.h” file) is equal to 0.
If the condition is true the “ospf_spf_calculate()”
function finishes, otherwise the vertex of the Candidate List with lowest
key is extracted by means of the “pqueue_dequeue”
function and the “stat”
field of the lsa associated to
the vertex is updated to the value -2 (inSPFtree).
At the end of the “ospf_spf_calculate”
function the Binary Heap data structure is destroyed.
Now we look at the other
important function, “ospf_spf_next()”.The
first part of the function reported in Figure 4
has not been modified. It takes one of the links of the given vertex and
finds the lsa of the vertex at the
other side of the link. This function has been deeply modified in order to
use the Binary Heap data structure, and the “stat” field in “struct
ospf_lsa”. The two databases “rv” and “nv”
have been removed.
Notice that in point (c) the “ospf_spf_has_vertex()” function has been deleted because
it is not necessary. In fact it checks if an lsa has been inserted in the Spanning Tree. It is not necessary
because this information is contained in the “stat” field defined in “struct ospf_lsa”; if “stat” assumes the value -2 (inSPFtree) means that the lsa
has been already inserted in the Spanning Tree. In point (d) the condition,
verifying if an lsa has been
already explored by the Dijkstra algorithm, has been changed. It is
sufficient to analyze the “stat”
field and the “ospf_vertex_lookup()”
function is not more necessary. In the case in which the lsa “w_lsa” is not in the Candidate List, it is it is inserted
by the “pqueue_enqueue()”
function defined in “pqueue.c”
file. On the contrary if the lsa
“w_lsa” is already in
the Candidate List, the associated vertex
“cw” is got by
extracting the component of index “w_lsa->stat” of the array “candidate->array”. In the following two different
cases must be considered. If the lsa
“w_lsa” can be
reached from the root trough a
path with lower distance, the vertex
associated to lsa “w_lsa” is changed to “w” by means of the instruction
“candidate->array[w_lsa->stat]=w”
and the Binary Heap is re-sorted by means of the “trickle_down()” function
defined in “pqueue.c”
file. On the contrary not operation have to be performed if the lsa “w_lsa” cannot reached from the root through a path with lower distance.
|
