|
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
2. THE HEAP BINARY DATA STRUCTURE
To optimize the SPF calculation,
the Candidate List data structure has been implemented with a Binary Heap.
The data structure definition and the management operations of the Binary
Heap are contained in “pqueue.h”
and “pqueue.c” files respectively.
The “struct pqueue”
in “pqueue.h” file
has been slightly modified as illustrated in Figure 5.
In particular the
“update” function has
been introduced. It will allow the “stat” field defined in “struct ospf_lsa” to be updated when: i) a vertex is inserted into the
Candidate List; ii) the distance of a vertex
have to be modified; iii) a vertex
is extracted from the Candidate List.
The “update”
function is initialised to “update_stat()”
in the “ospf_spf_calculate()”
function of the “ospf_spf.c”
as illustrated in Figure 3. In particular the
“update_stat” function
is defined at the beginning of the “ospf_spf.c” file as illustrated in Figure
6. It updates the “stat”
field in “struct ospf_lsa”
when the position of a node changes into the Candidate List due to a distance
variation. Notice also that in the initialisation phase in “ospf_spf_calculate()” of Figure 3 the “cmp” function is set to “cmp”. “cmp”
is also defined at the beginning of the “ospf_spf.c” in Figure 6. It
evaluates the difference of the distance fields of the vertexes pointed by
“node1” and “node2”.
Finally notice that the management operations of the Candidate List,
defined in “pqueue.c”
file, have been changed in order to update the “stat” field of the lsa
associated to a vertex stored and
moved inside the Candidate List. That is illustrated in Figure 7.
|
