diff options
| -rw-r--r-- | ospfd/ChangeLog | 11 | ||||
| -rw-r--r-- | ospfd/ospf_lsa.h | 6 | ||||
| -rw-r--r-- | ospfd/ospf_lsdb.c | 17 | ||||
| -rw-r--r-- | ospfd/ospf_lsdb.h | 2 | ||||
| -rw-r--r-- | ospfd/ospf_spf.c | 241 | ||||
| -rw-r--r-- | ospfd/ospf_spf.h | 1 |
6 files changed, 107 insertions, 171 deletions
diff --git a/ospfd/ChangeLog b/ospfd/ChangeLog index 396ac71a..ee30e55c 100644 --- a/ospfd/ChangeLog +++ b/ospfd/ChangeLog @@ -1,3 +1,14 @@ +2005-02-23 Vincenzo Eramo <eramo at infocom.ing.uniroma1.it> + + * ospf_lsa.h: New flag to the LSA structure for the SPF calculation. + * ospf_lsdb.h: Export ospf_lsdb_clean_stat() function. + * ospf_spf.h: Add link to the LSA stat structure into vertex. + * ospf_spf.c: New functions cmp() and update_stat() to manage + candidates. Remove ospf_spf_has_vertex(), ospf_vertex_lookup(), + ospf_install_candidate() and ospf_spf_register() functions not needed + any more. Update ospf_vertex_new(), ospf_spf_next() and + ospf_spf_calculate() functions to use pqueue instead of linked list. + 2005-02-21 Hasso Tepper <hasso at quagga.net> * ospf_ase.c: Don't show messages related to the ase calculations if diff --git a/ospfd/ospf_lsa.h b/ospfd/ospf_lsa.h index 6d10e645..952ca774 100644 --- a/ospfd/ospf_lsa.h +++ b/ospfd/ospf_lsa.h @@ -90,6 +90,12 @@ struct ospf_lsa /* All of reference count, also lock to remove. */ int lock; + /* Flags for the SPF calculation. */ + int stat; + #define LSA_SPF_NOT_EXPLORED -1 + #define LSA_SPF_IN_SPFTREE -2 + /* If stat >= 0, stat is LSA position in candidates heap. */ + /* References to this LSA in neighbor retransmission lists*/ int retransmit_counter; diff --git a/ospfd/ospf_lsdb.c b/ospfd/ospf_lsdb.c index 94d839f2..56ab9e2a 100644 --- a/ospfd/ospf_lsdb.c +++ b/ospfd/ospf_lsdb.c @@ -180,6 +180,23 @@ ospf_lsdb_delete_all (struct ospf_lsdb *lsdb) } } +void +ospf_lsdb_clean_stat (struct ospf_lsdb *lsdb) +{ + struct route_table *table; + struct route_node *rn; + struct ospf_lsa *lsa; + int i; + + for (i = OSPF_MIN_LSA; i < OSPF_MAX_LSA; i++) + { + table = lsdb->type[i].db; + for (rn = route_top (table); rn; rn = route_next (rn)) + if ((lsa = (rn->info)) != NULL) + lsa->stat = LSA_SPF_NOT_EXPLORED; + } +} + struct ospf_lsa * ospf_lsdb_lookup (struct ospf_lsdb *lsdb, struct ospf_lsa *lsa) { diff --git a/ospfd/ospf_lsdb.h b/ospfd/ospf_lsdb.h index 8ae66a15..e192308c 100644 --- a/ospfd/ospf_lsdb.h +++ b/ospfd/ospf_lsdb.h @@ -69,6 +69,8 @@ void ospf_lsdb_cleanup (struct ospf_lsdb *); void ospf_lsdb_add (struct ospf_lsdb *, struct ospf_lsa *); void ospf_lsdb_delete (struct ospf_lsdb *, struct ospf_lsa *); void ospf_lsdb_delete_all (struct ospf_lsdb *); +/* Set all stats to -1 (LSA_SPF_NOT_EXPLORED). */ +void ospf_lsdb_clean_stat (struct ospf_lsdb *lsdb); struct ospf_lsa *ospf_lsdb_lookup (struct ospf_lsdb *, struct ospf_lsa *); struct ospf_lsa *ospf_lsdb_lookup_by_id (struct ospf_lsdb *, u_char, struct in_addr, struct in_addr); diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c index 1298ebe8..9a4e8ffa 100644 --- a/ospfd/ospf_spf.c +++ b/ospfd/ospf_spf.c @@ -29,6 +29,7 @@ Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA #include "table.h" #include "log.h" #include "sockunion.h" /* for inet_ntop () */ +#include "pqueue.h" #include "ospfd/ospfd.h" #include "ospfd/ospf_interface.h" @@ -47,6 +48,28 @@ Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA #define DEBUG +/* Heap related functions, for the managment of the candidates, to + * be used with pqueue. */ +static int +cmp (void * node1 , void * node2) +{ + struct vertex * v1 = (struct vertex *) node1; + struct vertex * v2 = (struct vertex *) node2; + if (v1 != NULL && v2 != NULL ) + return (v1->distance - v2->distance); + else + return 0; +} + +static void +update_stat (void * node , int position) +{ + struct vertex * v = (struct vertex *) node; + /* Set the status of the vertex, when its position changes. */ + *(v->stat) = position; +} +/* End of the heap related functions. */ + struct vertex_nexthop * vertex_nexthop_new (struct vertex *parent) { @@ -87,6 +110,7 @@ ospf_vertex_new (struct ospf_lsa *lsa) memset (new, 0, sizeof (struct vertex)); new->flags = 0; + new->stat = &(lsa->stat); new->type = lsa->data->type; new->id = lsa->data->id; new->lsa = lsa->data; @@ -197,50 +221,6 @@ ospf_spf_init (struct ospf_area *area) area->asbr_count = 0; } -/* Check if the vertex represented by lsa is on the SPF tree. */ -int -ospf_spf_has_vertex (struct route_table *rv, struct route_table *nv, - struct lsa_header *lsa) -{ - struct prefix p; - struct route_node *rn; - - p.family = AF_INET; - p.prefixlen = IPV4_MAX_BITLEN; - p.u.prefix4 = lsa->id; - - if (lsa->type == OSPF_ROUTER_LSA) - rn = route_node_get (rv, &p); - else - rn = route_node_get (nv, &p); - - if (rn->info != NULL) - { - route_unlock_node (rn); - return 1; - } - return 0; -} - -/* Find the vertex specified by the given id and LSA type - * in vlist (the candidate list). - */ -struct listnode * -ospf_vertex_lookup (struct list *vlist, struct in_addr id, int type) -{ - struct listnode *node; - struct vertex *v; - - for (node = listhead (vlist); node; nextnode (node)) - { - v = (struct vertex *) getdata (node); - if (IPV4_ADDR_SAME (&id, &v->id) && type == v->type) - return node; - } - - return NULL; -} - /* return index of link back to V from W, or -1 if no link found */ int ospf_lsa_has_link (struct lsa_header *w, struct lsa_header *v) @@ -643,48 +623,6 @@ ospf_nexthop_calculation (struct ospf_area *area, } } -/* Add a vertex to the SPF candidate list. */ -void -ospf_install_candidate (struct list *candidate, struct vertex *w) -{ - struct listnode *node; - struct vertex *cw; - - ospf_vertex_dump("ospf_install_candidate(): add to candidate list", w, 1, 1); - - if (list_isempty (candidate)) - { - listnode_add (candidate, w); - return; - } - - /* Install vertex with sorting by distance. */ - for (node = listhead (candidate); node; nextnode (node)) - { - cw = (struct vertex *) getdata (node); - if (cw->distance > w->distance) - { - list_add_node_prev (candidate, node, w); - break; - } - else if (node->next == NULL) - { - list_add_node_next (candidate, node, w); - break; - } - } - - if (IS_DEBUG_OSPF_EVENT) - { - zlog_debug("ospf_install_candidate(): candidate list now contains:"); - for (node = listhead (candidate); node; nextnode (node)) - { - cw = (struct vertex *) getdata (node); - ospf_vertex_dump(" candidate:", cw, 0, 0); - } - } -} - /* RFC2328 Section 16.1 (2). * v is on the SPF tree. Examine the links in v's LSA. Update the list * of candidates with any vertices not already on the list. If a lower-cost @@ -692,8 +630,7 @@ ospf_install_candidate (struct list *candidate, struct vertex *w) */ void ospf_spf_next (struct vertex *v, struct ospf_area *area, - struct list *candidate, struct route_table *rv, - struct route_table *nv) + struct pqueue * candidate) { struct ospf_lsa *w_lsa = NULL; struct vertex *w, *cw; @@ -701,7 +638,6 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area, u_char *lim; struct router_lsa_link *l = NULL; struct in_addr *r; - struct listnode *node; int type = 0; /* If this is a router-LSA, and bit V of the router-LSA (see Section @@ -799,12 +735,12 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area, /* (c) If vertex W is already on the shortest-path tree, examine the next link in the LSA. */ - if (ospf_spf_has_vertex (rv, nv, w_lsa->data)) - { - if (IS_DEBUG_OSPF_EVENT) - zlog_debug ("The LSA is already in SPF"); - continue; - } + if (w_lsa->stat == LSA_SPF_IN_SPFTREE) + { + if (IS_DEBUG_OSPF_EVENT) + zlog_debug ("The LSA is already in SPF"); + continue; + } /* (d) Calculate the link state cost D of the resulting path from the root to vertex W. D is equal to the sum of the link @@ -825,34 +761,25 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area, w->distance = v->distance; /* Is there already vertex W in candidate list? */ - node = ospf_vertex_lookup (candidate, w->id, w->type); - if (node == NULL) - { - /* W is a new candidate. Calculate nexthop to W and add W - * to the candidate list. - */ - ospf_nexthop_calculation (area, v, w); + if (w_lsa->stat == LSA_SPF_NOT_EXPLORED) + { + /* Calculate nexthop to W. */ + ospf_nexthop_calculation (area, v, w); + pqueue_enqueue (w, candidate); + } + else if (w_lsa->stat >= 0) + { + /* Get the vertex from candidates. */ + cw = (struct vertex *) candidate->array[w_lsa->stat]; - ospf_install_candidate (candidate, w); - } - else - { - /* W is already on the candidate list; call it cw. - * Compare the previously calculated cost (cw->distance) - * with the cost we just determined (w->distance) to see - * if we've found a shorter path. - */ - cw = (struct vertex *) getdata (node); - - /* If the previous cost was lower, we didn't find a - * shorter path, so we're done with w. - */ - if (cw->distance < w->distance) + /* if D is greater than. */ + if (cw->distance < w->distance) { ospf_vertex_free (w); continue; } - else if (cw->distance == w->distance) + /* equal to. */ + else if (cw->distance == w->distance) { /* Found an equal-cost path to W. Calculate nexthop to W. */ ospf_nexthop_calculation (area, v, w); @@ -860,44 +787,22 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area, list_delete_all_node (w->nexthop); ospf_vertex_free (w); } - else + /* less than. */ + else { /* Found a lower-cost path to W. Calculate nexthop to W. */ ospf_nexthop_calculation (area, v, w); /* Remove old vertex from candidate list. */ ospf_vertex_free (cw); - listnode_delete (candidate, cw); - - /* Install new W to candidate list. */ - ospf_install_candidate (candidate, w); + candidate->array[w_lsa->stat] = w; + /* Decrease the key of the node in the heap, re-sort the heap. */ + trickle_down (w_lsa->stat, candidate); } } /* end W is already on the candidate list */ } /* end loop over the links in V's LSA */ } -/* Add vertex V to SPF tree. */ -void -ospf_spf_register (struct vertex *v, struct route_table *rv, - struct route_table *nv) -{ - struct prefix p; - struct route_node *rn; - - ospf_vertex_dump("ospf_spf_register(): adding to SPF tree:", v, 1, 1); - - p.family = AF_INET; - p.prefixlen = IPV4_MAX_BITLEN; - p.u.prefix4 = v->id; - - if (v->type == OSPF_VERTEX_ROUTER) - rn = route_node_get (rv, &p); - else - rn = route_node_get (nv, &p); - - rn->info = v; -} - void ospf_spf_route_free (struct route_table *table) { @@ -1103,11 +1008,8 @@ void ospf_spf_calculate (struct ospf_area *area, struct route_table *new_table, struct route_table *new_rtrs) { - struct list *candidate; - struct listnode *node; + struct pqueue *candidate; struct vertex *v; - struct route_table *rv; - struct route_table *nv; if (IS_DEBUG_OSPF_EVENT) { @@ -1129,17 +1031,22 @@ ospf_spf_calculate (struct ospf_area *area, struct route_table *new_table, /* RFC2328 16.1. (1). */ /* Initialize the algorithm's data structures. */ - rv = route_table_init (); - nv = route_table_init (); - - /* Clear the list of candidate vertices. */ - candidate = list_new (); + + /* This function scans all the LSA database and set the stat field to + * LSA_SPF_NOT_EXPLORED. */ + ospf_lsdb_clean_stat (area->lsdb); + /* Create a new heap for the candidates. */ + candidate = pqueue_create(); + candidate->cmp = cmp; + candidate->update = update_stat; /* Initialize the shortest-path tree to only the root (which is the router doing the calculation). */ ospf_spf_init (area); v = area->spf; - ospf_spf_register (v, rv, nv); + /* Set LSA position to LSA_SPF_IN_SPFTREE. This vertex is the root of the + * spanning tree. */ + *(v->stat) = LSA_SPF_IN_SPFTREE; /* Set Area A's TransitCapability to FALSE. */ area->transit = OSPF_TRANSIT_FALSE; @@ -1148,29 +1055,25 @@ ospf_spf_calculate (struct ospf_area *area, struct route_table *new_table, for (;;) { /* RFC2328 16.1. (2). */ - ospf_spf_next (v, area, candidate, rv, nv); + ospf_spf_next (v, area, candidate); /* RFC2328 16.1. (3). */ /* If at this step the candidate list is empty, the shortest- path tree (of transit vertices) has been completely built and this stage of the procedure terminates. */ - if (listcount (candidate) == 0) + if (candidate->size == 0) break; /* Otherwise, choose the vertex belonging to the candidate list that is closest to the root, and add it to the shortest-path tree (removing it from the candidate list in the process). */ - node = listhead (candidate); - v = getdata (node); + /* Extract from the candidates the node with the lower key. */ + v = (struct vertex *) pqueue_dequeue (candidate); + /* Update stat field in vertex. */ + *(v->stat) = LSA_SPF_IN_SPFTREE; ospf_vertex_add_parent (v); - /* Remove from the candidate list. */ - listnode_delete (candidate, v); - - /* Add to SPF tree. */ - ospf_spf_register (v, rv, nv); - /* Note that when there is a choice of vertices closest to the root, network vertices must be chosen before router vertices in order to necessarily find all equal-cost paths. */ @@ -1197,12 +1100,8 @@ ospf_spf_calculate (struct ospf_area *area, struct route_table *new_table, /* Second stage of SPF calculation procedure's */ ospf_spf_process_stubs (area, area->spf, new_table); - /* Free all vertices which allocated for SPF calculation */ - ospf_spf_route_free (rv); - ospf_spf_route_free (nv); - - /* Free candidate list */ - list_free (candidate); + /* Free candidates. */ + pqueue_delete (candidate); /* Increment SPF Calculation Counter. */ area->spf_calculation++; diff --git a/ospfd/ospf_spf.h b/ospfd/ospf_spf.h index 25b1d79b..57f9d28b 100644 --- a/ospfd/ospf_spf.h +++ b/ospfd/ospf_spf.h @@ -36,6 +36,7 @@ struct vertex u_char type; /* copied from LSA header */ struct in_addr id; /* copied from LSA header */ struct lsa_header *lsa; /* Router or Network LSA */ + int * stat; /* Link to LSA status. */ u_int32_t distance; /* from root to this vertex */ int backlink; /* link index of back-link */ struct list *child; /* list of vertex: children in SPF tree*/ |