|
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
4. CHANGES ROW BY ROW IN QUAGGA 0.97.3 CVS
In this section we describe the
changes row by row we have carried out in quagga 0.97.3 CVS. In the
following subsections we illustrate the changes in each file of quagga
0.97.3 we have modified. In particular we report the number of row in
quagga 0.97.3 CVS where the change has been carried out.
4.1 File
ospf_spf.c in /zebra/ospfd
row 32:
The file “pqueue.h”
has been included. This file defines the data structures of the Candidate
List.
row 50: Two related functions have been
introduced. The function “cmp”
evaluates the difference of the distance fields of the vertices pointed by node1 and node2. The function “update_stat” updates the
“stat” field in
“struct ospf_lsa”
when the position of a node changes inside the Candidate List due to a
distance change. The “struct
ospf_lsa” has been re-defined in file “ospf_lsa.h” and the integer “stat” field has been introduced. If the “stat” field assumes value -1 (notEXPLORED) means that the lsa (link state advertisement) has
not been explored by the Dijkstra algorithm yet. If the “stat” field assumes value -2 (inSPFtree) means that the lsa has been already inserted in the
Spanning Tree. Finally If the “stat”
field assumes integer value greater than or equal to 0, the lsa is in the Candidate List and the
value contained in “stat”
field denotes the position inside the Candidate List of the vertex associated to the lsa. The Candidate List data
structure we have used is a Binary Heap implemented by an array. In
particular when an lsa has been
inserted in the Candidate List, the component of the array in which is the vertex associated to the lsa, is stored in
“stat”.
In “struct vertex”, defined in
“ospf_spf.h” file,
the “stat” field has
been introduced. This “stat”
field is a pointer to an integer variable containing the “stat” field in “struct ospf_lsa” and allows
the “stat” field of
an lsa to be modified when its
associated vertex changes
position inside the Candidate List. This position change is due to a
variation of the distance of the vertex
from the root node during the
execution of the Dijkstra algorithm. Notice that the “stat” field in “struct ospf_lsa” and in
“struct vertex” have
a different meaning.
row 90: The “stat” field of the “struct vertex” is set to the reference of the “stat” field of the lsa associated to the vertex.
row 200: The function “ospf_spf_has_vertex” has been deleted. In fact it checked
if an lsa has been already
inserted in the Spanning Tree. It is not necessary because this information
is contained in the “stat”
field defined in “struct
ospf_lsa”; if the “stat”
field assumes the values -2 (in
SPFtree) means that the lsa
has already inserted in the Spanning Tree.
row 225: The function “ospf_vertex_lookup” has been deleted. The function
allowed a vertex to be found in the Candidate List if it was there. This
function is not necessary because we have introduced a new data structure (Binary Heap) to implement the
Candidate List. Further the “stat”
field in “struct ospf_lsa”
allows the presence and the position of a vertex in the Candidate List to be found immediately.
row 646: The function “ospf_instal_candidate” has been deleted because a new
data structure (Binary Heap) has been introduced to implement the Candidate
List. With the new implementation the insertion of a new vertex in the Candidate List is
accomplished by means of the function “pqueue_enqueue” defined in file “pqueue.c”.
row 695: Due to the new implementation of the
Candidate List, we change the declaration of the variable “candidate” in the function
“ospf_spf_next”.
Further the variables “rv”
and “nv” have been
deleted because, according to the introduction of the “stat” field defined in “struct ospf_lsa”, they are no
longer necessary.
row 704: The declaration “struct listnode *node” has
been deleted because it is no longer necessary.
row 803: The condition, verifying if an lsa is the Spanning Tree, has been
changed. Now it is sufficient to analyse the “stat” field in “struct
ospf_lsa” and the function “ospf_spf_has_vertex” is no longer necessary.
row 829: The condition, verifying if an lsa has been already taken into
account by the Dijkstra algorithm, has been changed. It is sufficient to
analyse the “stat”
field in “struct ospf_lsa”
and the function “ospf_vertex_lookup”
is no longer necessary.
row 837: The insertion of a vertex in the Candidate List is accomplished by means of the
function “pqueue_enqueue”
defined in file “pqueue.c”.
row 839: The condition w_lsa->stat>=0 denotes if the lsa is in the Candidate List.
row 841: The instruction, allowing the vertex associated to the lsa “w_lsa” and stored in the Candidate List to be found, has
been changed.
row 871: The distance of a vertex is updated and the Binary Heap is re-sorted by means of
the function “trickle_down”
defined in file “pqueue.c”.
row 880: Due to the introduction of the “stat” field in “struct ospf_lsa”, the
variables “rv”,
“nv” and the “ospf_spf_register” function
are no longer necessary.
row 1107: Due to the new implementation of the
Candidate List, both the definition of the variable “candidate” has been changed
and the definition of the variable “node” has been deleted.
row 1110: The declaration of the variables “rv” and “nv” are no longer necessary
because the information about the lsas
inserted in the Spanning Tree is contained in the “stat” field in “struct ospf_lsa” of the lsa stored in the database.
row1132: The initialisation of the variables
“rv” and “nv” is no longer necessary.
The initialisation of the Candidate List has been changed due to the new
implementation.
row 1143: When the vertex v is inserted in the Spanning Tree the “stat” field in “struct ospf_lsa” is updated.
The function “ospf_spf_register”
is no longer necessary.
row 1152: The variables “rv” and “nv”
have been deleted because they are no longer necessary.
row 1158: According to the new implementation of
the Candidate List, the condition verifying if the Candidate List is empty,
has been changed.
row 1165: The extraction of the minimum distance
vertex from the Candidate List is accomplished by means of the function
“pqueue_dequeue”
defined in file “pqueue.c”.
row 1172: The updating of the vertexes inserted in
the Spanning Tree is accomplished by changing the “stat” field in “struct ospf_lsa”. The
variables “rv”,
“nv” and the “ospf_spf_register” function
are no longer necessary.
row 1201: The Candidate List is removed by means of
the function “pqueue_delete”
defined in the file “pqueue.c”.
The memory de-allocation of the variables “rv” and “nv”
has been removed because they are no longer necessary.
4.2 File
ospf_spf.h in /zebra/ospfd
row 39: The “stat” field has been introduced in “struct vertex”. This “stat” field is a pointer to an
integer variable containing the “stat”
field in “struct ospf_lsa”
and allows the “stat”
field of an lsa to be modified
when its associated vertex
changes position inside the Candidate List. This position change is due to
a variation of the distance of the vertex
from the root node during the
execution of the Dijkstra algorithm. Notice that the “stat” field in “struct ospf_lsa” and in
“struct vertex” have
a different meaning.
4.3 File
pqueue.c in /zebra/lib
row 59: An instruction has been added in order to
update the “stat”
field in “struct ospf_lsa”.
In fact when a “trickle_up”
operation is applied, the position of the vertex in the Binary Heap is changed and hence it is necessary
to update the “stat”
field in “struct ospf_lsa”.
row 64: An instruction has been added for the
same reason illustrated in row 59.
row 93: An instruction has been added in order to
update the “stat”
field in “struct ospf_lsa”.
In fact when a “trickle_down”
operation is applied, the position of the vertex in the Binary Heap is changed and hence it is necessary
to update the “stat”
field in “struct ospf_lsa”.
row 98: An instruction has been added for the
same reason illustrated in row 93.
row 113: An initialisation instruction has been
added
row 149: When a vertex is added as leaf, its position in the “stat” field in “struct ospf_lsa” is set.
row 157: When a vertex is extracted from the Candidate List, it will be
inserted in the Spanning Tree and the value of the “stat” field in “struct ospf_lsa” will be
updated to -2.
4.4 File pqueue.h in /zebra/lib
row 31: The function “update” has been introduced. It will allow the “stat” field 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 function
“update” is
initialised in row 1137 in file “ospf_spf.c”
by means of the initialisation “candidate->update=update_stat”,
where the function “update_stat”
is defined in row 50 in file “ospf_spf.c”.
row 42: The file “pqueue.h” is included in file “ospf_spf.c” and hence the function “trickle_down” can be used in
file “ospf_spf.c” to
update the Binary Heap.
4.5 File
ospf_lsa.c in /zebra/ospfd
row 3080: The two variables “table” and “lp” are initialised. These variables
are needed for the implementation of an effective search of a Network_lsa in the database as
described in row 3087.
row 3087: In the old version of Quagga 0.97.3 the
search of a Network_lsa in the
database is accomplished in a sequential way. In the new implementation the
search is accomplished by taking into account that the Network_lsa database is sorted according to a binary tree. In
our patch, to implement the new search the function “route_node_lookup_partial”,
defined in file “table.c”,
is introduced. The function allows an lsa
to be found without scanning the database in a sequential way when the Link
State ID composed by 32 bit is known only as occurs for a Network_lsa.
4.6 File
ospf_lsa.h in /zebra/ospfd
row 93: The “struct ospf_lsa” has been re-defined and the integer
“stat” field has been
introduced. If the “stat”
field assumes value -1 (notEXPLORED)
means that the lsa (link state
advertisement) has not been explored by the Dijkstra algorithm yet. If
the “stat” field
assumes value -2 (inSPFtree)
means that the lsa has been
already inserted in the Spanning Tree. Finally If the “stat” field assumes integer
value greater than or equal to 0, the lsa
is in the Candidate List and the value contained in “stat” field denotes the
position inside the Candidate List of the vertex associated to the lsa.
4.7 File
ospf_lsdb.c in /zebra/ospfd
row 176: The function “ospf_lsdb_clean_stat” has been introduced. The function
is called in the initialisation phase (see row 1137 in file “ospf_spf.c”) in order to set
to -1 (notEXPLORED) the “stat” field in “struct ospf_lsa” of all of the
lsa stored in the database. In
fact when the SPF calculation starts all of the lsas are not explored. That is they are neither in the Spanning
Tree nor in the Candidate List.
4.8 File
ospf_lsdb.h in /zebra/ospfd
row 71: The function “ospf_lsdb_clean_stat” has been declared.
4.9 File table.c in /zebra/lib
row 34: The function “route_node_lookup_partial” has been introduced. Given a
prefix p having length l1 bit, the function
allows a node having a prefix of length l2
(with l2> l1) and matching the l1 bit of p to be lookup. The function is
important to effectively find a Network_lsa
in the database. It is called in the file “ospf_lsa.c” when the search of a Network_lsa is performed.
4.9 File table.h in /zebra/lib
row 65: The function “route_node_lookup_partial” is
declared.
|
