|
/* RFC2328
Section 16.1 (2) */
void
ospf_spf_next (struct vertex *v, struct ospf_area *area,
struct
pqueue *candidate,
struct route_table *rv, struct route_table *nv)
{
[ ... ]
/* (c) If vertex W is already on the shortest-path
tree, examine
the next link in the
LSA. */
if (w_lsa->stat == inSPFtree) /* instead of searching
inside the rv and nv
we
simply check the status of this vertex
inSPFtree
is defined in ospf_lsa.h */
{
if (IS_DEBUG_OSPF_EVENT)
zlog_info
("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
state cost of the
(already calculated) shortest path to
vertex V and the
advertised cost of the link between vertices
V and W. If D is:
*/
/* prepare vertex W. */
w = ospf_vertex_new (w_lsa);
/* Save W's back
link index number, for use by virtual links */
w->backlink = link;
/* calculate link cost D. */
if (v->lsa->type == OSPF_ROUTER_LSA)
w->distance =
v->distance + ntohs (l->m[0].metric);
else
/* v is not a Router-LSA */
w->distance =
v->distance;
/* Is there already vertex W in candidate list?
*/
if (w_lsa->stat == notEXPLORED )
{
/* Calculate nexthop
to W. */
ospf_nexthop_calculation (area, v, w);
pqueue_enqueue
(w,candidate);
}
else if (w_lsa->stat >= 0)
{
cw = (struct vertex *)
candidate->array[w_lsa->stat];
/*
If the previous cost was lower, we didn't find a
* shorter path, so we're done with w.
*/
if
(cw->distance < w->distance)
{
ospf_vertex_free (w);
continue;
}
/* equal to. */
else if (cw->distance
== w->distance)
{
/*
Found a equal-cost-cost path to W. Calculate nexthop to W. */
ospf_nexthop_calculation (area, v, w);
ospf_nexthop_merge (cw->nexthop, w->nexthop);
list_delete_all_node (w->nexthop);
ospf_vertex_free (w);
}
/* less than. */
else
{
/* Found a
lower-cost path to W. Calculate nexthop. */
ospf_nexthop_calculation (area, v, w);
/*
Remove old vertex from candidate list. */
ospf_vertex_free (cw);
candidate->array[w_lsa->stat]
= w;
/* Decrease the key of the
node in 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 */
}
|
