summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorgdt <gdt>2004-08-31 17:28:41 +0000
committergdt <gdt>2004-08-31 17:28:41 +0000
commit630e48072a4a4685a7c04a7b73ae9170d2f0844a (patch)
tree1a343e551a0ce24d8c8c93aa62860742749355ee
parent94755ea13e9466fc4590994b551dc23a44571622 (diff)
Assorted changes from work at BBN. Most are minor, and several are in
support of more significant changes not in this commit. The last item in the ChangeLog below may be needed for p2mp to work correctly. 2004-08-31 David Wiggins <dwiggins@bbn.com> * hash.c (hash_iterate): Save next pointer before calling procedure, so that iteration works even if the called procedure deletes the hash backet. * linklist.h (listtail): new macro, not yet used. 2004-08-31 David Wiggins <dwiggins@bbn.com> * ospf_spf.c (ospf_spf_calculate): Many more comments and debug print statements. New function ospf_vertex_dump used in debugging. 2004-08-31 David Wiggins <dwiggins@bbn.com> * ospf_spf.h (struct vertex): Comments for flags and structure members. 2004-08-31 David Wiggins <dwiggins@bbn.com> * ospf_route.c: When finding an alternate route, log cost as well. 2004-08-31 David Wiggins <dwiggins@bbn.com> * ospf_interface.c (ospf_lookup_if_params): Initialize af in struct prefix allocated on stack. 2004-08-31 David Wiggins <dwiggins@bbn.com> * ospf_packet.c (ospf_ls_ack_send_delayed): In p2mp mode, send acks to AllSPFRouters, rather than All-DR.
-rw-r--r--lib/ChangeLog8
-rw-r--r--lib/hash.c11
-rw-r--r--lib/linklist.h1
-rw-r--r--ospfd/ChangeLog23
-rw-r--r--ospfd/ospf_interface.c3
-rw-r--r--ospfd/ospf_packet.c2
-rw-r--r--ospfd/ospf_route.c3
-rw-r--r--ospfd/ospf_spf.c258
-rw-r--r--ospfd/ospf_spf.h27
9 files changed, 270 insertions, 66 deletions
diff --git a/lib/ChangeLog b/lib/ChangeLog
index ea965eae..c72fa28a 100644
--- a/lib/ChangeLog
+++ b/lib/ChangeLog
@@ -1,3 +1,11 @@
+2004-08-31 David Wiggins <dwiggins@bbn.com>
+
+ * hash.c (hash_iterate): Save next pointer before calling
+ procedure, so that iteration works even if the called procedure
+ deletes the hash backet.
+
+ * linklist.h (listtail): new macro, not yet used.
+
2004-08-27 Hasso Tepper <hasso at quagga.net>
* command.c: Install "terminal length" commands only if vty is used.
diff --git a/lib/hash.c b/lib/hash.c
index 40975079..e89171b8 100644
--- a/lib/hash.c
+++ b/lib/hash.c
@@ -142,10 +142,17 @@ hash_iterate (struct hash *hash,
{
int i;
struct hash_backet *hb;
+ struct hash_backet *hbnext;
for (i = 0; i < hash->size; i++)
- for (hb = hash->index[i]; hb; hb = hb->next)
- (*func) (hb, arg);
+ for (hb = hash->index[i]; hb; hb = hbnext)
+ {
+ /* get pointer to next hash backet here, in case (*func)
+ * decides to delete hb by calling hash_release
+ */
+ hbnext = hb->next;
+ (*func) (hb, arg);
+ }
}
/* Clean up hash. */
diff --git a/lib/linklist.h b/lib/linklist.h
index 331135fe..303b0bce 100644
--- a/lib/linklist.h
+++ b/lib/linklist.h
@@ -48,6 +48,7 @@ struct list
#define nextnode(X) ((X) = (X)->next)
#define listhead(X) ((X)->head)
+#define listtail(X) ((X)->tail)
#define listcount(X) ((X)->count)
#define list_isempty(X) ((X)->head == NULL && (X)->tail == NULL)
#define getdata(X) ((X)->data)
diff --git a/ospfd/ChangeLog b/ospfd/ChangeLog
index 53a278de..3c5777b1 100644
--- a/ospfd/ChangeLog
+++ b/ospfd/ChangeLog
@@ -1,3 +1,26 @@
+2004-08-31 David Wiggins <dwiggins@bbn.com>
+
+ * ospf_spf.c (ospf_spf_calculate): Many more comments and debug
+ print statements. New function ospf_vertex_dump used in debugging.
+
+2004-08-31 David Wiggins <dwiggins@bbn.com>
+
+ * ospf_spf.h (struct vertex): Comments for flags and structure members.
+
+2004-08-31 David Wiggins <dwiggins@bbn.com>
+
+ * ospf_route.c: When finding an alternate route, log cost as well.
+
+2004-08-31 David Wiggins <dwiggins@bbn.com>
+
+ * ospf_interface.c (ospf_lookup_if_params): Initialize af in
+ struct prefix allocated on stack.
+
+2004-08-31 David Wiggins <dwiggins@bbn.com>
+
+ * ospf_packet.c (ospf_ls_ack_send_delayed): In p2mp mode, send
+ acks to AllSPFRouters, rather than All-DR.
+
2004-08-27 Hasso Tepper <hasso at quagga.net>
* ospf_vty.c: Don't print ospf network type under interface only
diff --git a/ospfd/ospf_interface.c b/ospfd/ospf_interface.c
index fcc70e3b..f7e200c3 100644
--- a/ospfd/ospf_interface.c
+++ b/ospfd/ospf_interface.c
@@ -545,6 +545,8 @@ ospf_free_if_params (struct interface *ifp, struct in_addr addr)
struct ospf_if_params *oip;
struct prefix_ipv4 p;
struct route_node *rn;
+
+ p.family = AF_INET;
p.prefixlen = IPV4_MAX_PREFIXLEN;
p.prefix = addr;
rn = route_node_lookup (IF_OIFS_PARAMS (ifp), (struct prefix*)&p);
@@ -578,6 +580,7 @@ ospf_lookup_if_params (struct interface *ifp, struct in_addr addr)
struct prefix_ipv4 p;
struct route_node *rn;
+ p.family = AF_INET;
p.prefixlen = IPV4_MAX_PREFIXLEN;
p.prefix = addr;
diff --git a/ospfd/ospf_packet.c b/ospfd/ospf_packet.c
index 4d158253..9afd929b 100644
--- a/ospfd/ospf_packet.c
+++ b/ospfd/ospf_packet.c
@@ -3295,6 +3295,8 @@ ospf_ls_ack_send_delayed (struct ospf_interface *oi)
dst.s_addr = htonl (OSPF_ALLSPFROUTERS);
else if (oi->type == OSPF_IFTYPE_POINTOPOINT)
dst.s_addr = htonl (OSPF_ALLSPFROUTERS);
+ else if (oi->type == OSPF_IFTYPE_POINTOMULTIPOINT)
+ dst.s_addr = htonl (OSPF_ALLSPFROUTERS);
else
dst.s_addr = htonl (OSPF_ALLDROUTERS);
diff --git a/ospfd/ospf_route.c b/ospfd/ospf_route.c
index a8ee232f..9f3efb14 100644
--- a/ospfd/ospf_route.c
+++ b/ospfd/ospf_route.c
@@ -528,7 +528,8 @@ ospf_intra_add_stub (struct route_table *rt, struct router_lsa_link *link,
if (IS_DEBUG_OSPF_EVENT)
zlog_info ("ospf_intra_add_stub(): "
- "another route to the same prefix found");
+ "another route to the same prefix found with cost %u",
+ cur_or->cost);
/* Compare this distance to the current best cost to the stub
network. This is done by looking up the stub network's
diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c
index bc12c366..5288531f 100644
--- a/ospfd/ospf_spf.c
+++ b/ospfd/ospf_spf.c
@@ -115,6 +115,58 @@ ospf_vertex_free (struct vertex *v)
}
void
+ospf_vertex_dump(char *msg, struct vertex *v,
+ int print_nexthops, int print_children)
+{
+ if ( ! IS_DEBUG_OSPF_EVENT)
+ return;
+
+ zlog_info("%s %s vertex %s distance %u backlink %d flags %u",
+ msg,
+ v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network",
+ inet_ntoa(v->lsa->id),
+ v->distance,
+ v->backlink,
+ (unsigned int)v->flags);
+
+ if (print_nexthops)
+ {
+ listnode nnode;
+ for (nnode = listhead (v->nexthop); nnode; nextnode (nnode))
+ {
+ char buf1[BUFSIZ];
+ char buf2[BUFSIZ];
+ struct vertex_nexthop *nexthop;
+
+ nexthop = getdata (nnode);
+ if (nexthop)
+ {
+ zlog_info (" nexthop %s interface %s parent %s",
+ inet_ntop(AF_INET, &nexthop->router, buf1, BUFSIZ),
+ nexthop->oi ? IF_NAME(nexthop->oi) : "NULL",
+ nexthop->parent ? inet_ntop(AF_INET,
+ &nexthop->parent->id,
+ buf2, BUFSIZ)
+ : "NULL");
+ }
+ }
+ }
+
+ if (print_children)
+ {
+ listnode cnode;
+ for (cnode = listhead (v->child); cnode; nextnode (cnode))
+ {
+ struct vertex *cv = getdata (cnode);
+ if (cv)
+ ospf_vertex_dump(" child:", cv, 0, 0);
+ }
+ }
+}
+
+
+/* Add a vertex to the list of children in each of its parents. */
+void
ospf_vertex_add_parent (struct vertex *v)
{
struct vertex_nexthop *nh;
@@ -145,6 +197,7 @@ 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)
@@ -169,6 +222,9 @@ ospf_spf_has_vertex (struct route_table *rv, struct route_table *nv,
return 0;
}
+/* Find the vertex specified by the given id and LSA type
+ * in vlist (the candidate list).
+ */
listnode
ospf_vertex_lookup (list vlist, struct in_addr id, int type)
{
@@ -300,6 +356,10 @@ ospf_nexthop_merge (list a, list b)
#define ROUTER_LSA_MIN_SIZE 12
#define ROUTER_LSA_TOS_SIZE 4
+/* Find the next link after prev_link from v to w. If prev_link is
+ * NULL, return the first link from v to w. Ignore stub and virtual links;
+ * these link types will never be returned.
+ */
struct router_lsa_link *
ospf_get_next_link (struct vertex *v, struct vertex *w,
struct router_lsa_link *prev_link)
@@ -309,7 +369,7 @@ ospf_get_next_link (struct vertex *v, struct vertex *w,
struct router_lsa_link *l;
if (prev_link == NULL)
- p = ((u_char *) v->lsa) + 24;
+ p = ((u_char *) v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
else
{
p = (u_char *) prev_link;
@@ -393,7 +453,9 @@ ospf_spf_consider_nexthop (struct list *nexthops,
return;
}
-/* Calculate nexthop from root to vertex W. */
+/* 16.1.1. Calculate nexthop from root through V (parent) to
+ * vertex W (destination).
+ */
void
ospf_nexthop_calculation (struct ospf_area *area,
struct vertex *v, struct vertex *w)
@@ -405,29 +467,72 @@ ospf_nexthop_calculation (struct ospf_area *area,
if (IS_DEBUG_OSPF_EVENT)
- zlog_info ("ospf_nexthop_calculation(): Start");
+ {
+ zlog_info ("ospf_nexthop_calculation(): Start");
+ ospf_vertex_dump("V (parent):", v, 1, 1);
+ ospf_vertex_dump("W (dest) :", w, 1, 1);
+ }
- /* W's parent is root. */
if (v == area->spf)
{
+ /* 16.1.1 para 4. In the first case, the parent vertex (V) is the
+ root (the calculating router itself). This means that the
+ destination is either a directly connected network or directly
+ connected router. The outgoing interface in this case is simply
+ the OSPF interface connecting to the destination network/router.
+ */
+
if (w->type == OSPF_VERTEX_ROUTER)
{
while ((l = ospf_get_next_link (v, w, l)))
{
+ /* l is a link from v to w
+ * l2 will be link from w to v
+ */
struct router_lsa_link *l2 = NULL;
+ if (IS_DEBUG_OSPF_EVENT)
+ {
+ char buf1[BUFSIZ];
+ char buf2[BUFSIZ];
+ zlog_info("ospf_nexthop_calculation(): considering link "
+ "type %d link_id %s link_data %s",
+ l->m[0].type,
+ inet_ntop (AF_INET, &l->link_id, buf1, BUFSIZ),
+ inet_ntop (AF_INET, &l->link_data, buf1, BUFSIZ));
+ }
+
if (l->m[0].type == LSA_LINK_TYPE_POINTOPOINT)
{
- /* Check for PtMP, signified by PtP link V->W
- with link_data our PtMP interface. */
+ /* If the destination is a router which connects to
+ the calculating router via a Point-to-MultiPoint
+ network, the destination's next hop IP address(es)
+ can be determined by examining the destination's
+ router-LSA: each link pointing back to the
+ calculating router and having a Link Data field
+ belonging to the Point-to-MultiPoint network
+ provides an IP address of the next hop router.
+
+ At this point l is a link from V to W, and V is the
+ root ("us"). Find the local interface associated
+ with l (its address is in l->link_data). If it
+ is a point-to-multipoint interface, then look through
+ the links in the opposite direction (W to V). If
+ any of them have an address that lands within the
+ subnet declared by the PtMP link, then that link
+ is a constituent of the PtMP link, and its address is
+ a nexthop address for V.
+ */
oi = ospf_if_is_configured (area->ospf, &l->link_data);
if (oi && oi->type == OSPF_IFTYPE_POINTOMULTIPOINT)
{
struct prefix_ipv4 la;
- la.family = AF_INET;
+
+ la.family = AF_INET;
la.prefixlen = oi->address->prefixlen;
- /* We link to them on PtMP interface
- - find the interface on w */
+
+ /* V links to W on PtMP interface
+ - find the interface address on W */
while ((l2 = ospf_get_next_link (w, v, l2)))
{
la.prefix = l2->link_data;
@@ -437,9 +542,12 @@ ospf_nexthop_calculation (struct ospf_area *area,
/* link_data is on our PtMP network */
break;
}
- }
+ } /* end l is on point-to-multipoint link */
else
{
+ /* l is a regular point-to-point link.
+ Look for a link from W to V.
+ */
while ((l2 = ospf_get_next_link (w, v, l2)))
{
oi = ospf_if_is_configured (area->ospf,
@@ -458,16 +566,23 @@ ospf_nexthop_calculation (struct ospf_area *area,
if (oi && l2)
{
+ /* found all necessary info to build nexthop */
nh = vertex_nexthop_new (v);
nh->oi = oi;
nh->router = l2->link_data;
ospf_spf_consider_nexthop (w->nexthop, nh);
}
- }
- }
- }
+ else
+ {
+ zlog_info("ospf_nexthop_calculation(): "
+ "could not determine nexthop for link");
+ }
+ } /* end point-to-point link from V to W */
+ } /* end iterate over links in W */
+ } /* end W is a Router vertex */
else
{
+ assert(w->type == OSPF_VERTEX_NETWORK);
while ((l = ospf_get_next_link (v, w, l)))
{
oi = ospf_if_is_configured (area->ospf, &(l->link_data));
@@ -481,17 +596,32 @@ ospf_nexthop_calculation (struct ospf_area *area,
}
}
return;
- }
- /* In case of W's parent is network connected to root. */
+ } /* end V is the root */
+
+ /* Check if W's parent is a network connected to root. */
else if (v->type == OSPF_VERTEX_NETWORK)
{
+ /* See if any of V's parents are the root. */
for (node = listhead (v->nexthop); node; nextnode (node))
{
- x = (struct vertex_nexthop *) getdata (node);
- if (x->parent == area->spf)
- {
+ x = (struct vertex_nexthop *) getdata (node);
+ if (x->parent == area->spf) /* connects to root? */
+ {
+ /* 16.1.1 para 5. ...the parent vertex is a network that
+ * directly connects the calculating router to the destination
+ * router. The list of next hops is then determined by
+ * examining the destination's router-LSA...
+ */
+
+ assert(w->type == OSPF_VERTEX_ROUTER);
while ((l = ospf_get_next_link (w, v, l)))
{
+ /* ...For each link in the router-LSA that points back to the
+ * parent network, the link's Link Data field provides the IP
+ * address of a next hop router. The outgoing interface to
+ * use can then be derived from the next hop IP address (or
+ * it can be inherited from the parent network).
+ */
nh = vertex_nexthop_new (v);
nh->oi = x->oi;
nh->router = l->link_data;
@@ -502,7 +632,11 @@ ospf_nexthop_calculation (struct ospf_area *area,
}
}
- /* Inherit V's nexthop. */
+ /* 16.1.1 para 4. If there is at least one intervening router in the
+ * current shortest path between the destination and the root, the
+ * destination simply inherits the set of next hops from the
+ * parent.
+ */
for (node = listhead (v->nexthop); node; nextnode (node))
{
nh = vertex_nexthop_dup (node->data);
@@ -511,12 +645,15 @@ ospf_nexthop_calculation (struct ospf_area *area,
}
}
+/* Add a vertex to the SPF candidate list. */
void
ospf_install_candidate (list candidate, struct vertex *w)
{
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);
@@ -538,9 +675,23 @@ ospf_install_candidate (list candidate, struct vertex *w)
break;
}
}
+
+ if (IS_DEBUG_OSPF_EVENT)
+ {
+ zlog_info("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). */
+/* 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
+ * path is found to a vertex already on the candidate list, store the new cost.
+ */
void
ospf_spf_next (struct vertex *v, struct ospf_area *area,
list candidate, struct route_table *rv, struct route_table *nv)
@@ -603,7 +754,7 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area,
if (w_lsa)
{
if (IS_DEBUG_OSPF_EVENT)
- zlog_info ("found the LSA");
+ zlog_info ("found Router LSA %s", inet_ntoa (l->link_id));
}
break;
case LSA_LINK_TYPE_TRANSIT:
@@ -671,53 +822,60 @@ ospf_spf_next (struct vertex *v, struct ospf_area *area,
/* calculate link cost D. */
if (v->lsa->type == OSPF_ROUTER_LSA)
- w->distance = v->distance + ntohs (l->m[0].metric);
- else
- w->distance = v->distance;
+ 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? */
node = ospf_vertex_lookup (candidate, w->id, w->type);
if (node == NULL)
{
- /* Calculate nexthop to W. */
+ /* W is a new candidate. Calculate nexthop to W and add W
+ * to the candidate list.
+ */
ospf_nexthop_calculation (area, v, w);
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 D is greater than. */
+ /* 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)
{
- /* Calculate nexthop to W. */
+ /* Found an equal-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
{
- /* Calculate nexthop. */
+ /* 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 to candidate. */
+ /* Install new W to candidate list. */
ospf_install_candidate (candidate, w);
}
- }
- }
+ } /* end W is already on the candidate list */
+ } /* end loop over the links in V's LSA */
}
/* Add vertex V to SPF tree. */
@@ -728,6 +886,8 @@ ospf_spf_register (struct vertex *v, struct route_table *rv,
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;
@@ -778,13 +938,13 @@ ospf_spf_dump (struct vertex *v, int i)
if (IS_DEBUG_OSPF_EVENT)
zlog_info ("SPF Result: %d [N] %s/%d", i, inet_ntoa (v->lsa->id),
ip_masklen (lsa->mask));
+ }
- for (nnode = listhead (v->nexthop); nnode; nextnode (nnode))
- {
- nexthop = getdata (nnode);
- if (IS_DEBUG_OSPF_EVENT)
- zlog_info (" nexthop %s", inet_ntoa (nexthop->router));
- }
+ for (nnode = listhead (v->nexthop); nnode; nextnode (nnode))
+ {
+ nexthop = getdata (nnode);
+ if (IS_DEBUG_OSPF_EVENT)
+ zlog_info (" nexthop %s", inet_ntoa (nexthop->router));
}
i++;
@@ -815,15 +975,15 @@ ospf_spf_process_stubs (struct ospf_area *area, struct vertex *v,
struct router_lsa *rlsa;
if (IS_DEBUG_OSPF_EVENT)
- zlog_info ("ospf_process_stub():processing router LSA, id: %s",
+ zlog_info ("ospf_process_stubs():processing router LSA, id: %s",
inet_ntoa (v->lsa->id));
rlsa = (struct router_lsa *) v->lsa;
if (IS_DEBUG_OSPF_EVENT)
- zlog_info ("ospf_process_stub(): we have %d links to process",
+ zlog_info ("ospf_process_stubs(): we have %d links to process",
ntohs (rlsa->links));
- p = ((u_char *) v->lsa) + 24;
+ p = ((u_char *) v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
lim = ((u_char *) v->lsa) + ntohs (v->lsa->length);
while (p < lim)
@@ -838,14 +998,7 @@ ospf_spf_process_stubs (struct ospf_area *area, struct vertex *v,
}
}
- if (IS_DEBUG_OSPF_EVENT)
- zlog_info ("children of V:");
- for (cnode = listhead (v->child); cnode; nextnode (cnode))
- {
- child = getdata (cnode);
- if (IS_DEBUG_OSPF_EVENT)
- zlog_info (" child : %s", inet_ntoa (child->id));
- }
+ ospf_vertex_dump("ospf_process_stubs(): after examining links: ", v, 1, 1);
for (cnode = listhead (v->child); cnode; nextnode (cnode))
{
@@ -1014,7 +1167,7 @@ ospf_spf_calculate (struct ospf_area *area, struct route_table *new_table,
v = getdata (node);
ospf_vertex_add_parent (v);
- /* Reveve from the candidate list. */
+ /* Remove from the candidate list. */
listnode_delete (candidate, v);
/* Add to SPF tree. */
@@ -1034,7 +1187,8 @@ ospf_spf_calculate (struct ospf_area *area, struct route_table *new_table,
/* RFC2328 16.1. (5). */
/* Iterate the algorithm by returning to Step 2. */
- }
+
+ } /* end loop until no more candidate vertices */
if (IS_DEBUG_OSPF_EVENT)
{
diff --git a/ospfd/ospf_spf.h b/ospfd/ospf_spf.h
index 73120000..928d98b7 100644
--- a/ospfd/ospf_spf.h
+++ b/ospfd/ospf_spf.h
@@ -20,29 +20,34 @@
* 02111-1307, USA.
*/
-#define OSPF_VERTEX_ROUTER 1
-#define OSPF_VERTEX_NETWORK 2
+/* values for vertex->type */
+#define OSPF_VERTEX_ROUTER 1 /* for a Router-LSA */
+#define OSPF_VERTEX_NETWORK 2 /* for a Network-LSA */
+/* values for vertex->flags */
#define OSPF_VERTEX_PROCESSED 0x01
+/* The "root" is the node running the SPF calculation */
+/* A router or network in an area */
struct vertex
{
u_char flags;
- u_char type;
- struct in_addr id;
- struct lsa_header *lsa;
- u_int32_t distance;
+ u_char type; /* copied from LSA header */
+ struct in_addr id; /* copied from LSA header */
+ struct lsa_header *lsa; /* Router or Network LSA */
+ u_int32_t distance; /* from root to this vertex */
int backlink; /* link index of back-link */
- list child;
- list nexthop;
+ list child; /* list of vertex: children in SPF tree*/
+ list nexthop; /* list of vertex_nexthop from root to this vertex */
};
+/* A nexthop taken on the root node to get to this (parent) vertex */
struct vertex_nexthop
{
- struct ospf_interface *oi;
- struct in_addr router;
- struct vertex *parent;
+ struct ospf_interface *oi; /* output intf on root node */
+ struct in_addr router; /* router address to send to */
+ struct vertex *parent; /* parent in SPF tree */
};
void ospf_spf_calculate_schedule (struct ospf *);