1 /* OSPF SPF calculation.
2 Copyright (C) 1999, 2000 Kunihiro Ishiguro, Toshiaki Takada
4 This file is part of GNU Zebra.
6 GNU Zebra is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
11 GNU Zebra is distributed in the hope that it will be useful, but
12 WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU Zebra; see the file COPYING. If not, write to the Free
18 Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
31 #include "sockunion.h" /* for inet_ntop () */
34 #include "ospfd/ospfd.h"
35 #include "ospfd/ospf_interface.h"
36 #include "ospfd/ospf_ism.h"
37 #include "ospfd/ospf_asbr.h"
38 #include "ospfd/ospf_lsa.h"
39 #include "ospfd/ospf_lsdb.h"
40 #include "ospfd/ospf_neighbor.h"
41 #include "ospfd/ospf_nsm.h"
42 #include "ospfd/ospf_spf.h"
43 #include "ospfd/ospf_route.h"
44 #include "ospfd/ospf_ia.h"
45 #include "ospfd/ospf_ase.h"
46 #include "ospfd/ospf_abr.h"
47 #include "ospfd/ospf_dump.h"
51 /* Heap related functions, for the managment of the candidates, to
52 * be used with pqueue. */
54 cmp (void * node1
, void * node2
)
56 struct vertex
* v1
= (struct vertex
*) node1
;
57 struct vertex
* v2
= (struct vertex
*) node2
;
58 if (v1
!= NULL
&& v2
!= NULL
)
59 return (v1
->distance
- v2
->distance
);
65 update_stat (void * node
, int position
)
67 struct vertex
* v
= (struct vertex
*) node
;
68 /* Set the status of the vertex, when its position changes. */
69 *(v
->stat
) = position
;
71 /* End of the heap related functions. */
73 struct vertex_nexthop
*
74 vertex_nexthop_new (struct vertex
*parent
)
76 struct vertex_nexthop
*new;
78 new = XCALLOC (MTYPE_OSPF_NEXTHOP
, sizeof (struct vertex_nexthop
));
85 vertex_nexthop_free (struct vertex_nexthop
*nh
)
87 XFREE (MTYPE_OSPF_NEXTHOP
, nh
);
90 struct vertex_nexthop
*
91 vertex_nexthop_dup (struct vertex_nexthop
*nh
)
93 struct vertex_nexthop
*new;
95 new = vertex_nexthop_new (nh
->parent
);
98 new->router
= nh
->router
;
105 ospf_vertex_new (struct ospf_lsa
*lsa
)
109 new = XMALLOC (MTYPE_OSPF_VERTEX
, sizeof (struct vertex
));
110 memset (new, 0, sizeof (struct vertex
));
113 new->stat
= &(lsa
->stat
);
114 new->type
= lsa
->data
->type
;
115 new->id
= lsa
->data
->id
;
116 new->lsa
= lsa
->data
;
118 new->child
= list_new ();
119 new->nexthop
= list_new ();
126 ospf_vertex_free (struct vertex
*v
)
128 struct listnode
*node
, *nnode
;
129 struct vertex_nexthop
*nh
;
131 list_delete (v
->child
);
133 if (listcount (v
->nexthop
) > 0)
134 for (ALL_LIST_ELEMENTS (v
->nexthop
, node
, nnode
, nh
))
135 vertex_nexthop_free (nh
);
137 list_delete (v
->nexthop
);
139 XFREE (MTYPE_OSPF_VERTEX
, v
);
143 ospf_vertex_dump(const char *msg
, struct vertex
*v
,
144 int print_nexthops
, int print_children
)
146 if ( ! IS_DEBUG_OSPF_EVENT
)
149 zlog_debug("%s %s vertex %s distance %u backlink %d flags %u",
151 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
152 inet_ntoa(v
->lsa
->id
),
155 (unsigned int)v
->flags
);
159 struct listnode
*node
;
160 struct vertex_nexthop
*nexthop
;
162 for (ALL_LIST_ELEMENTS_RO (v
->nexthop
, node
, nexthop
))
169 zlog_debug (" nexthop %s interface %s parent %s",
170 inet_ntop(AF_INET
, &nexthop
->router
, buf1
, BUFSIZ
),
171 nexthop
->oi
? IF_NAME(nexthop
->oi
) : "NULL",
172 nexthop
->parent
? inet_ntop(AF_INET
,
173 &nexthop
->parent
->id
,
182 struct listnode
*cnode
;
185 for (ALL_LIST_ELEMENTS_RO (v
->child
, cnode
, cv
))
186 ospf_vertex_dump(" child:", cv
, 0, 0);
191 /* Add a vertex to the list of children in each of its parents. */
193 ospf_vertex_add_parent (struct vertex
*v
)
195 struct vertex_nexthop
*nh
;
196 struct listnode
*node
;
198 for (ALL_LIST_ELEMENTS_RO (v
->nexthop
, node
, nh
))
200 /* No need to add two links from the same parent. */
201 if (listnode_lookup (nh
->parent
->child
, v
) == NULL
)
202 listnode_add (nh
->parent
->child
, v
);
207 ospf_spf_init (struct ospf_area
*area
)
211 /* Create root node. */
212 v
= ospf_vertex_new (area
->router_lsa_self
);
216 /* Reset ABR and ASBR router counts. */
218 area
->asbr_count
= 0;
221 /* return index of link back to V from W, or -1 if no link found */
223 ospf_lsa_has_link (struct lsa_header
*w
, struct lsa_header
*v
)
225 unsigned int i
, length
;
226 struct router_lsa
*rl
;
227 struct network_lsa
*nl
;
229 /* In case of W is Network LSA. */
230 if (w
->type
== OSPF_NETWORK_LSA
)
232 if (v
->type
== OSPF_NETWORK_LSA
)
235 nl
= (struct network_lsa
*) w
;
236 length
= (ntohs (w
->length
) - OSPF_LSA_HEADER_SIZE
- 4) / 4;
238 for (i
= 0; i
< length
; i
++)
239 if (IPV4_ADDR_SAME (&nl
->routers
[i
], &v
->id
))
244 /* In case of W is Router LSA. */
245 if (w
->type
== OSPF_ROUTER_LSA
)
247 rl
= (struct router_lsa
*) w
;
249 length
= ntohs (w
->length
);
252 i
< ntohs (rl
->links
) && length
>= sizeof (struct router_lsa
);
255 switch (rl
->link
[i
].type
)
257 case LSA_LINK_TYPE_POINTOPOINT
:
258 case LSA_LINK_TYPE_VIRTUALLINK
:
260 if (v
->type
== OSPF_ROUTER_LSA
&&
261 IPV4_ADDR_SAME (&rl
->link
[i
].link_id
, &v
->id
))
266 case LSA_LINK_TYPE_TRANSIT
:
267 /* Network LSA ID. */
268 if (v
->type
== OSPF_NETWORK_LSA
&&
269 IPV4_ADDR_SAME (&rl
->link
[i
].link_id
, &v
->id
))
274 case LSA_LINK_TYPE_STUB
:
275 /* Not take into count? */
285 /* Add the nexthop to the list, only if it is unique.
286 * If it's not unique, free the nexthop entry.
289 ospf_nexthop_add_unique (struct vertex_nexthop
*new, struct list
*nexthop
)
291 struct vertex_nexthop
*nh
;
292 struct listnode
*node
;
297 for (ALL_LIST_ELEMENTS_RO (nexthop
, node
, nh
))
299 /* Compare the two entries. */
301 * Comparing the parent preserves the shortest path tree
302 * structure even when the nexthops are identical.
304 if (nh
->oi
== new->oi
&&
305 IPV4_ADDR_SAME (&nh
->router
, &new->router
) &&
306 nh
->parent
== new->parent
)
314 listnode_add (nexthop
, new);
316 vertex_nexthop_free (new);
319 /* Merge entries in list b into list a. */
321 ospf_nexthop_merge (struct list
*a
, struct list
*b
)
323 struct listnode
*node
, *nnode
;
324 struct vertex_nexthop
*nh
;
326 for (ALL_LIST_ELEMENTS (b
, node
, nnode
, nh
))
327 ospf_nexthop_add_unique (nh
, a
);
330 #define ROUTER_LSA_MIN_SIZE 12
331 #define ROUTER_LSA_TOS_SIZE 4
333 /* Find the next link after prev_link from v to w. If prev_link is
334 * NULL, return the first link from v to w. Ignore stub and virtual links;
335 * these link types will never be returned.
337 struct router_lsa_link
*
338 ospf_get_next_link (struct vertex
*v
, struct vertex
*w
,
339 struct router_lsa_link
*prev_link
)
343 struct router_lsa_link
*l
;
345 if (prev_link
== NULL
)
346 p
= ((u_char
*) v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
349 p
= (u_char
*) prev_link
;
350 p
+= (ROUTER_LSA_MIN_SIZE
+
351 (prev_link
->m
[0].tos_count
* ROUTER_LSA_TOS_SIZE
));
354 lim
= ((u_char
*) v
->lsa
) + ntohs (v
->lsa
->length
);
358 l
= (struct router_lsa_link
*) p
;
360 p
+= (ROUTER_LSA_MIN_SIZE
+ (l
->m
[0].tos_count
* ROUTER_LSA_TOS_SIZE
));
362 if (l
->m
[0].type
== LSA_LINK_TYPE_STUB
)
365 /* Defer NH calculation via VLs until summaries from
366 transit areas area confidered */
368 if (l
->m
[0].type
== LSA_LINK_TYPE_VIRTUALLINK
)
371 if (IPV4_ADDR_SAME (&l
->link_id
, &w
->id
))
379 * Consider supplied next-hop for inclusion to the supplied list of
380 * equal-cost next-hops, adjust list as neccessary.
382 * (Discussed on GNU Zebra list 27 May 2003, [zebra 19184])
384 * Note that below is a bit of a hack, and limits ECMP to paths that go to
385 * same nexthop. Where as paths via inequal output_cost interfaces could
386 * still quite easily be ECMP due to remote cost differences.
388 * TODO: It really should be done by way of recording currently valid
389 * backlinks and determining the appropriate nexthops from the list of
390 * backlinks, or even simpler, just flushing nexthop list if we find a lower
391 * cost path to a candidate vertex in SPF, maybe.
394 ospf_spf_consider_nexthop (struct list
*nexthops
,
395 struct vertex_nexthop
*newhop
)
397 struct vertex_nexthop
*hop
;
398 struct listnode
*ln
, *nn
;
400 /* nexthop list should contain only the set of nexthops that have the lowest
403 if (nexthops
->head
!= NULL
)
405 hop
= listgetdata (nexthops
->head
);
407 /* weed out hops with higher cost than the newhop */
408 if (hop
->oi
->output_cost
> newhop
->oi
->output_cost
)
410 /* delete the existing nexthops */
411 for (ALL_LIST_ELEMENTS (nexthops
, ln
, nn
, hop
))
413 listnode_delete (nexthops
, hop
);
414 vertex_nexthop_free (hop
);
417 else if (hop
->oi
->output_cost
< newhop
->oi
->output_cost
)
421 /* new hop is <= existing hops, add it */
422 listnode_add (nexthops
, newhop
);
427 /* 16.1.1. Calculate nexthop from root through V (parent) to
428 * vertex W (destination).
431 ospf_nexthop_calculation (struct ospf_area
*area
,
432 struct vertex
*v
, struct vertex
*w
)
434 struct listnode
*node
, *nnode
;
435 struct vertex_nexthop
*nh
, *x
;
436 struct ospf_interface
*oi
= NULL
;
437 struct router_lsa_link
*l
= NULL
;
440 if (IS_DEBUG_OSPF_EVENT
)
442 zlog_debug ("ospf_nexthop_calculation(): Start");
443 ospf_vertex_dump("V (parent):", v
, 1, 1);
444 ospf_vertex_dump("W (dest) :", w
, 1, 1);
449 /* 16.1.1 para 4. In the first case, the parent vertex (V) is the
450 root (the calculating router itself). This means that the
451 destination is either a directly connected network or directly
452 connected router. The outgoing interface in this case is simply
453 the OSPF interface connecting to the destination network/router.
456 if (w
->type
== OSPF_VERTEX_ROUTER
)
458 while ((l
= ospf_get_next_link (v
, w
, l
)))
460 /* l is a link from v to w
461 * l2 will be link from w to v
463 struct router_lsa_link
*l2
= NULL
;
465 if (IS_DEBUG_OSPF_EVENT
)
470 zlog_debug("ospf_nexthop_calculation(): considering link "
471 "type %d link_id %s link_data %s",
473 inet_ntop (AF_INET
, &l
->link_id
, buf1
, BUFSIZ
),
474 inet_ntop (AF_INET
, &l
->link_data
, buf2
, BUFSIZ
));
477 if (l
->m
[0].type
== LSA_LINK_TYPE_POINTOPOINT
)
479 /* If the destination is a router which connects to
480 the calculating router via a Point-to-MultiPoint
481 network, the destination's next hop IP address(es)
482 can be determined by examining the destination's
483 router-LSA: each link pointing back to the
484 calculating router and having a Link Data field
485 belonging to the Point-to-MultiPoint network
486 provides an IP address of the next hop router.
488 At this point l is a link from V to W, and V is the
489 root ("us"). Find the local interface associated
490 with l (its address is in l->link_data). If it
491 is a point-to-multipoint interface, then look through
492 the links in the opposite direction (W to V). If
493 any of them have an address that lands within the
494 subnet declared by the PtMP link, then that link
495 is a constituent of the PtMP link, and its address is
496 a nexthop address for V.
498 oi
= ospf_if_is_configured (area
->ospf
, &l
->link_data
);
499 if (oi
&& oi
->type
== OSPF_IFTYPE_POINTOMULTIPOINT
)
501 struct prefix_ipv4 la
;
504 la
.prefixlen
= oi
->address
->prefixlen
;
506 /* V links to W on PtMP interface
507 - find the interface address on W */
508 while ((l2
= ospf_get_next_link (w
, v
, l2
)))
510 la
.prefix
= l2
->link_data
;
512 if (prefix_cmp ((struct prefix
*) &la
,
514 /* link_data is on our PtMP network */
517 } /* end l is on point-to-multipoint link */
520 /* l is a regular point-to-point link.
521 Look for a link from W to V.
523 while ((l2
= ospf_get_next_link (w
, v
, l2
)))
525 oi
= ospf_if_is_configured (area
->ospf
,
531 if (!IPV4_ADDR_SAME (&oi
->address
->u
.prefix4
,
541 /* found all necessary info to build nexthop */
542 nh
= vertex_nexthop_new (v
);
544 nh
->router
= l2
->link_data
;
545 ospf_spf_consider_nexthop (w
->nexthop
, nh
);
549 zlog_info("ospf_nexthop_calculation(): "
550 "could not determine nexthop for link");
552 } /* end point-to-point link from V to W */
553 } /* end iterate over links in W */
554 } /* end W is a Router vertex */
557 assert(w
->type
== OSPF_VERTEX_NETWORK
);
558 while ((l
= ospf_get_next_link (v
, w
, l
)))
560 oi
= ospf_if_is_configured (area
->ospf
, &(l
->link_data
));
563 nh
= vertex_nexthop_new (v
);
565 nh
->router
.s_addr
= 0;
566 ospf_spf_consider_nexthop (w
->nexthop
, nh
);
571 } /* end V is the root */
573 /* Check if W's parent is a network connected to root. */
574 else if (v
->type
== OSPF_VERTEX_NETWORK
)
576 /* See if any of V's parents are the root. */
577 for (ALL_LIST_ELEMENTS (v
->nexthop
, node
, nnode
, x
))
579 if (x
->parent
== area
->spf
) /* connects to root? */
581 /* 16.1.1 para 5. ...the parent vertex is a network that
582 * directly connects the calculating router to the destination
583 * router. The list of next hops is then determined by
584 * examining the destination's router-LSA...
587 assert(w
->type
== OSPF_VERTEX_ROUTER
);
588 while ((l
= ospf_get_next_link (w
, v
, l
)))
590 /* ...For each link in the router-LSA that points back to the
591 * parent network, the link's Link Data field provides the IP
592 * address of a next hop router. The outgoing interface to
593 * use can then be derived from the next hop IP address (or
594 * it can be inherited from the parent network).
596 nh
= vertex_nexthop_new (v
);
598 nh
->router
= l
->link_data
;
599 ospf_spf_consider_nexthop (w
->nexthop
, nh
);
606 /* 16.1.1 para 4. If there is at least one intervening router in the
607 * current shortest path between the destination and the root, the
608 * destination simply inherits the set of next hops from the
611 for (ALL_LIST_ELEMENTS (v
->nexthop
, node
, nnode
, nh
))
614 ospf_nexthop_add_unique (nh
, w
->nexthop
);
618 /* RFC2328 Section 16.1 (2).
619 * v is on the SPF tree. Examine the links in v's LSA. Update the list
620 * of candidates with any vertices not already on the list. If a lower-cost
621 * path is found to a vertex already on the candidate list, store the new cost.
624 ospf_spf_next (struct vertex
*v
, struct ospf_area
*area
,
625 struct pqueue
* candidate
)
627 struct ospf_lsa
*w_lsa
= NULL
;
628 struct vertex
*w
, *cw
;
631 struct router_lsa_link
*l
= NULL
;
635 /* If this is a router-LSA, and bit V of the router-LSA (see Section
636 A.4.2:RFC2328) is set, set Area A's TransitCapability to TRUE. */
637 if (v
->type
== OSPF_VERTEX_ROUTER
)
639 if (IS_ROUTER_LSA_VIRTUAL ((struct router_lsa
*) v
->lsa
))
640 area
->transit
= OSPF_TRANSIT_TRUE
;
643 p
= ((u_char
*) v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
644 lim
= ((u_char
*) v
->lsa
) + ntohs (v
->lsa
->length
);
648 int link
= -1; /* link index for w's back link */
650 /* In case of V is Router-LSA. */
651 if (v
->lsa
->type
== OSPF_ROUTER_LSA
)
653 l
= (struct router_lsa_link
*) p
;
655 p
+= (ROUTER_LSA_MIN_SIZE
+
656 (l
->m
[0].tos_count
* ROUTER_LSA_TOS_SIZE
));
658 /* (a) If this is a link to a stub network, examine the next
659 link in V's LSA. Links to stub networks will be
660 considered in the second stage of the shortest path
662 if ((type
= l
->m
[0].type
) == LSA_LINK_TYPE_STUB
)
665 /* (b) Otherwise, W is a transit vertex (router or transit
666 network). Look up the vertex W's LSA (router-LSA or
667 network-LSA) in Area A's link state database. */
670 case LSA_LINK_TYPE_POINTOPOINT
:
671 case LSA_LINK_TYPE_VIRTUALLINK
:
672 if (type
== LSA_LINK_TYPE_VIRTUALLINK
)
674 if (IS_DEBUG_OSPF_EVENT
)
675 zlog_debug ("looking up LSA through VL: %s",
676 inet_ntoa (l
->link_id
));
679 w_lsa
= ospf_lsa_lookup (area
, OSPF_ROUTER_LSA
, l
->link_id
,
683 if (IS_DEBUG_OSPF_EVENT
)
684 zlog_debug ("found Router LSA %s", inet_ntoa (l
->link_id
));
687 case LSA_LINK_TYPE_TRANSIT
:
688 if (IS_DEBUG_OSPF_EVENT
)
689 zlog_debug ("Looking up Network LSA, ID: %s",
690 inet_ntoa (l
->link_id
));
691 w_lsa
= ospf_lsa_lookup_by_id (area
, OSPF_NETWORK_LSA
,
694 if (IS_DEBUG_OSPF_EVENT
)
695 zlog_debug ("found the LSA");
698 zlog_warn ("Invalid LSA link type %d", type
);
704 /* In case of V is Network-LSA. */
705 r
= (struct in_addr
*) p
;
706 p
+= sizeof (struct in_addr
);
708 /* Lookup the vertex W's LSA. */
709 w_lsa
= ospf_lsa_lookup_by_id (area
, OSPF_ROUTER_LSA
, *r
);
712 /* (b cont.) If the LSA does not exist, or its LS age is equal
713 to MaxAge, or it does not have a link back to vertex V,
714 examine the next link in V's LSA.[23] */
718 if (IS_LSA_MAXAGE (w_lsa
))
721 if ( (link
= ospf_lsa_has_link (w_lsa
->data
, v
->lsa
)) < 0 )
723 if (IS_DEBUG_OSPF_EVENT
)
724 zlog_debug ("The LSA doesn't have a link back");
728 /* (c) If vertex W is already on the shortest-path tree, examine
729 the next link in the LSA. */
730 if (w_lsa
->stat
== LSA_SPF_IN_SPFTREE
)
732 if (IS_DEBUG_OSPF_EVENT
)
733 zlog_debug ("The LSA is already in SPF");
737 /* (d) Calculate the link state cost D of the resulting path
738 from the root to vertex W. D is equal to the sum of the link
739 state cost of the (already calculated) shortest path to
740 vertex V and the advertised cost of the link between vertices
743 /* prepare vertex W. */
744 w
= ospf_vertex_new (w_lsa
);
746 /* Save W's back link index number, for use by virtual links */
749 /* calculate link cost D. */
750 if (v
->lsa
->type
== OSPF_ROUTER_LSA
)
751 w
->distance
= v
->distance
+ ntohs (l
->m
[0].metric
);
752 else /* v is not a Router-LSA */
753 w
->distance
= v
->distance
;
755 /* Is there already vertex W in candidate list? */
756 if (w_lsa
->stat
== LSA_SPF_NOT_EXPLORED
)
758 /* Calculate nexthop to W. */
759 ospf_nexthop_calculation (area
, v
, w
);
760 pqueue_enqueue (w
, candidate
);
762 else if (w_lsa
->stat
>= 0)
764 /* Get the vertex from candidates. */
765 cw
= (struct vertex
*) candidate
->array
[w_lsa
->stat
];
767 /* if D is greater than. */
768 if (cw
->distance
< w
->distance
)
770 ospf_vertex_free (w
);
774 else if (cw
->distance
== w
->distance
)
776 /* Found an equal-cost path to W. Calculate nexthop to W. */
777 ospf_nexthop_calculation (area
, v
, w
);
778 ospf_nexthop_merge (cw
->nexthop
, w
->nexthop
);
779 list_delete_all_node (w
->nexthop
);
780 ospf_vertex_free (w
);
785 /* Found a lower-cost path to W. Calculate nexthop to W. */
786 ospf_nexthop_calculation (area
, v
, w
);
788 /* Remove old vertex from candidate list. */
789 ospf_vertex_free (cw
);
790 candidate
->array
[w_lsa
->stat
] = w
;
791 /* Decrease the key of the node in the heap, re-sort the heap. */
792 trickle_down (w_lsa
->stat
, candidate
);
794 } /* end W is already on the candidate list */
795 } /* end loop over the links in V's LSA */
799 ospf_spf_route_free (struct route_table
*table
)
801 struct route_node
*rn
;
804 for (rn
= route_top (table
); rn
; rn
= route_next (rn
))
808 ospf_vertex_free (v
);
812 route_unlock_node (rn
);
815 route_table_finish (table
);
819 ospf_spf_dump (struct vertex
*v
, int i
)
821 struct listnode
*cnode
;
822 struct listnode
*nnode
;
823 struct vertex_nexthop
*nexthop
;
825 if (v
->type
== OSPF_VERTEX_ROUTER
)
827 if (IS_DEBUG_OSPF_EVENT
)
828 zlog_debug ("SPF Result: %d [R] %s", i
, inet_ntoa (v
->lsa
->id
));
832 struct network_lsa
*lsa
= (struct network_lsa
*) v
->lsa
;
833 if (IS_DEBUG_OSPF_EVENT
)
834 zlog_debug ("SPF Result: %d [N] %s/%d", i
, inet_ntoa (v
->lsa
->id
),
835 ip_masklen (lsa
->mask
));
838 if (IS_DEBUG_OSPF_EVENT
)
839 for (ALL_LIST_ELEMENTS_RO (v
->nexthop
, nnode
, nexthop
))
840 zlog_debug (" nexthop %s", inet_ntoa (nexthop
->router
));
844 for (ALL_LIST_ELEMENTS_RO (v
->child
, cnode
, v
))
845 ospf_spf_dump (v
, i
);
848 /* Second stage of SPF calculation. */
850 ospf_spf_process_stubs (struct ospf_area
*area
, struct vertex
*v
,
851 struct route_table
*rt
)
853 struct listnode
*cnode
, *cnnode
;
854 struct vertex
*child
;
856 if (IS_DEBUG_OSPF_EVENT
)
857 zlog_debug ("ospf_process_stub():processing stubs for area %s",
858 inet_ntoa (area
->area_id
));
859 if (v
->type
== OSPF_VERTEX_ROUTER
)
863 struct router_lsa_link
*l
;
864 struct router_lsa
*rlsa
;
866 if (IS_DEBUG_OSPF_EVENT
)
867 zlog_debug ("ospf_process_stubs():processing router LSA, id: %s",
868 inet_ntoa (v
->lsa
->id
));
869 rlsa
= (struct router_lsa
*) v
->lsa
;
872 if (IS_DEBUG_OSPF_EVENT
)
873 zlog_debug ("ospf_process_stubs(): we have %d links to process",
874 ntohs (rlsa
->links
));
875 p
= ((u_char
*) v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
876 lim
= ((u_char
*) v
->lsa
) + ntohs (v
->lsa
->length
);
880 l
= (struct router_lsa_link
*) p
;
882 p
+= (ROUTER_LSA_MIN_SIZE
+
883 (l
->m
[0].tos_count
* ROUTER_LSA_TOS_SIZE
));
885 if (l
->m
[0].type
== LSA_LINK_TYPE_STUB
)
886 ospf_intra_add_stub (rt
, l
, v
, area
);
890 ospf_vertex_dump("ospf_process_stubs(): after examining links: ", v
, 1, 1);
892 for (ALL_LIST_ELEMENTS (v
->child
, cnode
, cnnode
, child
))
894 if (CHECK_FLAG (child
->flags
, OSPF_VERTEX_PROCESSED
))
897 ospf_spf_process_stubs (area
, child
, rt
);
899 SET_FLAG (child
->flags
, OSPF_VERTEX_PROCESSED
);
904 ospf_rtrs_free (struct route_table
*rtrs
)
906 struct route_node
*rn
;
907 struct list
*or_list
;
908 struct ospf_route
*or;
909 struct listnode
*node
, *nnode
;
911 if (IS_DEBUG_OSPF_EVENT
)
912 zlog_debug ("Route: Router Routing Table free");
914 for (rn
= route_top (rtrs
); rn
; rn
= route_next (rn
))
915 if ((or_list
= rn
->info
) != NULL
)
917 for (ALL_LIST_ELEMENTS (or_list
, node
, nnode
, or))
918 ospf_route_free (or);
920 list_delete (or_list
);
922 /* Unlock the node. */
924 route_unlock_node (rn
);
926 route_table_finish (rtrs
);
930 ospf_rtrs_print (struct route_table
*rtrs
)
932 struct route_node
*rn
;
933 struct list
*or_list
;
935 struct listnode
*pnode
;
936 struct ospf_route
*or;
937 struct ospf_path
*path
;
941 if (IS_DEBUG_OSPF_EVENT
)
942 zlog_debug ("ospf_rtrs_print() start");
944 for (rn
= route_top (rtrs
); rn
; rn
= route_next (rn
))
945 if ((or_list
= rn
->info
) != NULL
)
946 for (ALL_LIST_ELEMENTS_RO (or_list
, ln
, or))
948 switch (or->path_type
)
950 case OSPF_PATH_INTRA_AREA
:
951 if (IS_DEBUG_OSPF_EVENT
)
952 zlog_debug ("%s [%d] area: %s",
953 inet_ntop (AF_INET
, &or->id
, buf1
, BUFSIZ
),
954 or->cost
, inet_ntop (AF_INET
, &or->u
.std
.area_id
,
957 case OSPF_PATH_INTER_AREA
:
958 if (IS_DEBUG_OSPF_EVENT
)
959 zlog_debug ("%s IA [%d] area: %s",
960 inet_ntop (AF_INET
, &or->id
, buf1
, BUFSIZ
),
961 or->cost
, inet_ntop (AF_INET
, &or->u
.std
.area_id
,
968 for (ALL_LIST_ELEMENTS_RO (or->paths
, pnode
, path
))
970 if (path
->nexthop
.s_addr
== 0)
972 if (IS_DEBUG_OSPF_EVENT
)
973 zlog_debug (" directly attached to %s\r\n",
978 if (IS_DEBUG_OSPF_EVENT
)
979 zlog_debug (" via %s, %s\r\n",
980 inet_ntoa (path
->nexthop
), IF_NAME (path
->oi
));
985 zlog_debug ("ospf_rtrs_print() end");
988 /* Calculating the shortest-path tree for an area. */
990 ospf_spf_calculate (struct ospf_area
*area
, struct route_table
*new_table
,
991 struct route_table
*new_rtrs
)
993 struct pqueue
*candidate
;
996 if (IS_DEBUG_OSPF_EVENT
)
998 zlog_debug ("ospf_spf_calculate: Start");
999 zlog_debug ("ospf_spf_calculate: running Dijkstra for area %s",
1000 inet_ntoa (area
->area_id
));
1003 /* Check router-lsa-self. If self-router-lsa is not yet allocated,
1004 return this area's calculation. */
1005 if (!area
->router_lsa_self
)
1007 if (IS_DEBUG_OSPF_EVENT
)
1008 zlog_debug ("ospf_spf_calculate: "
1009 "Skip area %s's calculation due to empty router_lsa_self",
1010 inet_ntoa (area
->area_id
));
1014 /* RFC2328 16.1. (1). */
1015 /* Initialize the algorithm's data structures. */
1017 /* This function scans all the LSA database and set the stat field to
1018 * LSA_SPF_NOT_EXPLORED. */
1019 ospf_lsdb_clean_stat (area
->lsdb
);
1020 /* Create a new heap for the candidates. */
1021 candidate
= pqueue_create();
1022 candidate
->cmp
= cmp
;
1023 candidate
->update
= update_stat
;
1025 /* Initialize the shortest-path tree to only the root (which is the
1026 router doing the calculation). */
1027 ospf_spf_init (area
);
1029 /* Set LSA position to LSA_SPF_IN_SPFTREE. This vertex is the root of the
1031 *(v
->stat
) = LSA_SPF_IN_SPFTREE
;
1033 /* Set Area A's TransitCapability to FALSE. */
1034 area
->transit
= OSPF_TRANSIT_FALSE
;
1035 area
->shortcut_capability
= 1;
1039 /* RFC2328 16.1. (2). */
1040 ospf_spf_next (v
, area
, candidate
);
1042 /* RFC2328 16.1. (3). */
1043 /* If at this step the candidate list is empty, the shortest-
1044 path tree (of transit vertices) has been completely built and
1045 this stage of the procedure terminates. */
1046 if (candidate
->size
== 0)
1049 /* Otherwise, choose the vertex belonging to the candidate list
1050 that is closest to the root, and add it to the shortest-path
1051 tree (removing it from the candidate list in the
1053 /* Extract from the candidates the node with the lower key. */
1054 v
= (struct vertex
*) pqueue_dequeue (candidate
);
1055 /* Update stat field in vertex. */
1056 *(v
->stat
) = LSA_SPF_IN_SPFTREE
;
1057 ospf_vertex_add_parent (v
);
1059 /* Note that when there is a choice of vertices closest to the
1060 root, network vertices must be chosen before router vertices
1061 in order to necessarily find all equal-cost paths. */
1062 /* We don't do this at this moment, we should add the treatment
1063 above codes. -- kunihiro. */
1065 /* RFC2328 16.1. (4). */
1066 if (v
->type
== OSPF_VERTEX_ROUTER
)
1067 ospf_intra_add_router (new_rtrs
, v
, area
);
1069 ospf_intra_add_transit (new_table
, v
, area
);
1071 /* RFC2328 16.1. (5). */
1072 /* Iterate the algorithm by returning to Step 2. */
1074 } /* end loop until no more candidate vertices */
1076 if (IS_DEBUG_OSPF_EVENT
)
1078 ospf_spf_dump (area
->spf
, 0);
1079 ospf_route_table_dump (new_table
);
1082 /* Second stage of SPF calculation procedure's */
1083 ospf_spf_process_stubs (area
, area
->spf
, new_table
);
1085 /* Free candidates. */
1086 pqueue_delete (candidate
);
1088 /* Increment SPF Calculation Counter. */
1089 area
->spf_calculation
++;
1091 area
->ospf
->ts_spf
= time (NULL
);
1093 if (IS_DEBUG_OSPF_EVENT
)
1094 zlog_debug ("ospf_spf_calculate: Stop");
1097 /* Timer for SPF calculation. */
1099 ospf_spf_calculate_timer (struct thread
*thread
)
1101 struct ospf
*ospf
= THREAD_ARG (thread
);
1102 struct route_table
*new_table
, *new_rtrs
;
1103 struct ospf_area
*area
;
1104 struct listnode
*node
, *nnode
;
1106 if (IS_DEBUG_OSPF_EVENT
)
1107 zlog_debug ("SPF: Timer (SPF calculation expire)");
1109 ospf
->t_spf_calc
= NULL
;
1111 /* Allocate new table tree. */
1112 new_table
= route_table_init ();
1113 new_rtrs
= route_table_init ();
1115 ospf_vl_unapprove (ospf
);
1117 /* Calculate SPF for each area. */
1118 for (ALL_LIST_ELEMENTS (ospf
->areas
, node
, nnode
, area
))
1119 ospf_spf_calculate (area
, new_table
, new_rtrs
);
1121 ospf_vl_shut_unapproved (ospf
);
1123 ospf_ia_routing (ospf
, new_table
, new_rtrs
);
1125 ospf_prune_unreachable_networks (new_table
);
1126 ospf_prune_unreachable_routers (new_rtrs
);
1128 /* AS-external-LSA calculation should not be performed here. */
1130 /* If new Router Route is installed,
1131 then schedule re-calculate External routes. */
1133 ospf_ase_calculate_schedule (ospf
);
1135 ospf_ase_calculate_timer_add (ospf
);
1137 /* Update routing table. */
1138 ospf_route_install (ospf
, new_table
);
1140 /* Update ABR/ASBR routing table */
1143 /* old_rtrs's node holds linked list of ospf_route. --kunihiro. */
1144 /* ospf_route_delete (ospf->old_rtrs); */
1145 ospf_rtrs_free (ospf
->old_rtrs
);
1148 ospf
->old_rtrs
= ospf
->new_rtrs
;
1149 ospf
->new_rtrs
= new_rtrs
;
1151 if (IS_OSPF_ABR (ospf
))
1152 ospf_abr_task (ospf
);
1154 if (IS_DEBUG_OSPF_EVENT
)
1155 zlog_debug ("SPF: calculation complete");
1160 /* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
1161 set timer for SPF calc. */
1163 ospf_spf_calculate_schedule (struct ospf
*ospf
)
1167 if (IS_DEBUG_OSPF_EVENT
)
1168 zlog_debug ("SPF: calculation timer scheduled");
1170 /* OSPF instance does not exist. */
1174 /* SPF calculation timer is already scheduled. */
1175 if (ospf
->t_spf_calc
)
1177 if (IS_DEBUG_OSPF_EVENT
)
1178 zlog_debug ("SPF: calculation timer is already scheduled: %p",
1183 ht
= time (NULL
) - ospf
->ts_spf
;
1185 /* Get SPF calculation delay time. */
1186 if (ht
< ospf
->spf_holdtime
)
1188 if (ospf
->spf_holdtime
- ht
< ospf
->spf_delay
)
1189 delay
= ospf
->spf_delay
;
1191 delay
= ospf
->spf_holdtime
- ht
;
1194 delay
= ospf
->spf_delay
;
1196 if (IS_DEBUG_OSPF_EVENT
)
1197 zlog_debug ("SPF: calculation timer delay = %ld", (long)delay
);
1199 thread_add_timer (master
, ospf_spf_calculate_timer
, ospf
, delay
);