]> git.proxmox.com Git - mirror_frr.git/blob - ospfd/ospf_spf.c
2005-04-07 Paul Jakma <paul.jakma@sun.com>
[mirror_frr.git] / ospfd / ospf_spf.c
1 /* OSPF SPF calculation.
2 Copyright (C) 1999, 2000 Kunihiro Ishiguro, Toshiaki Takada
3
4 This file is part of GNU Zebra.
5
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
9 later version.
10
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.
15
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
19 02111-1307, USA. */
20
21 #include <zebra.h>
22
23 #include "thread.h"
24 #include "memory.h"
25 #include "hash.h"
26 #include "linklist.h"
27 #include "prefix.h"
28 #include "if.h"
29 #include "table.h"
30 #include "log.h"
31 #include "sockunion.h" /* for inet_ntop () */
32 #include "pqueue.h"
33
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"
48
49 #define DEBUG
50
51 /* Heap related functions, for the managment of the candidates, to
52 * be used with pqueue. */
53 static int
54 cmp (void * node1 , void * node2)
55 {
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);
60 else
61 return 0;
62 }
63
64 static void
65 update_stat (void * node , int position)
66 {
67 struct vertex * v = (struct vertex *) node;
68 /* Set the status of the vertex, when its position changes. */
69 *(v->stat) = position;
70 }
71 /* End of the heap related functions. */
72
73 struct vertex_nexthop *
74 vertex_nexthop_new (struct vertex *parent)
75 {
76 struct vertex_nexthop *new;
77
78 new = XCALLOC (MTYPE_OSPF_NEXTHOP, sizeof (struct vertex_nexthop));
79 new->parent = parent;
80
81 return new;
82 }
83
84 void
85 vertex_nexthop_free (struct vertex_nexthop *nh)
86 {
87 XFREE (MTYPE_OSPF_NEXTHOP, nh);
88 }
89
90 struct vertex_nexthop *
91 vertex_nexthop_dup (struct vertex_nexthop *nh)
92 {
93 struct vertex_nexthop *new;
94
95 new = vertex_nexthop_new (nh->parent);
96
97 new->oi = nh->oi;
98 new->router = nh->router;
99
100 return new;
101 }
102 \f
103
104 struct vertex *
105 ospf_vertex_new (struct ospf_lsa *lsa)
106 {
107 struct vertex *new;
108
109 new = XMALLOC (MTYPE_OSPF_VERTEX, sizeof (struct vertex));
110 memset (new, 0, sizeof (struct vertex));
111
112 new->flags = 0;
113 new->stat = &(lsa->stat);
114 new->type = lsa->data->type;
115 new->id = lsa->data->id;
116 new->lsa = lsa->data;
117 new->distance = 0;
118 new->child = list_new ();
119 new->nexthop = list_new ();
120 new->backlink = -1;
121
122 return new;
123 }
124
125 void
126 ospf_vertex_free (struct vertex *v)
127 {
128 struct listnode *node, *nnode;
129 struct vertex_nexthop *nh;
130
131 list_delete (v->child);
132
133 if (listcount (v->nexthop) > 0)
134 for (ALL_LIST_ELEMENTS (v->nexthop, node, nnode, nh))
135 vertex_nexthop_free (nh);
136
137 list_delete (v->nexthop);
138
139 XFREE (MTYPE_OSPF_VERTEX, v);
140 }
141
142 void
143 ospf_vertex_dump(const char *msg, struct vertex *v,
144 int print_nexthops, int print_children)
145 {
146 if ( ! IS_DEBUG_OSPF_EVENT)
147 return;
148
149 zlog_debug("%s %s vertex %s distance %u backlink %d flags %u",
150 msg,
151 v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network",
152 inet_ntoa(v->lsa->id),
153 v->distance,
154 v->backlink,
155 (unsigned int)v->flags);
156
157 if (print_nexthops)
158 {
159 struct listnode *node;
160 struct vertex_nexthop *nexthop;
161
162 for (ALL_LIST_ELEMENTS_RO (v->nexthop, node, nexthop))
163 {
164 char buf1[BUFSIZ];
165 char buf2[BUFSIZ];
166
167 if (nexthop)
168 {
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,
174 buf2, BUFSIZ)
175 : "NULL");
176 }
177 }
178 }
179
180 if (print_children)
181 {
182 struct listnode *cnode;
183 struct vertex *cv;
184
185 for (ALL_LIST_ELEMENTS_RO (v->child, cnode, cv))
186 ospf_vertex_dump(" child:", cv, 0, 0);
187 }
188 }
189
190
191 /* Add a vertex to the list of children in each of its parents. */
192 void
193 ospf_vertex_add_parent (struct vertex *v)
194 {
195 struct vertex_nexthop *nh;
196 struct listnode *node;
197
198 for (ALL_LIST_ELEMENTS_RO (v->nexthop, node, nh))
199 {
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);
203 }
204 }
205 \f
206 void
207 ospf_spf_init (struct ospf_area *area)
208 {
209 struct vertex *v;
210
211 /* Create root node. */
212 v = ospf_vertex_new (area->router_lsa_self);
213
214 area->spf = v;
215
216 /* Reset ABR and ASBR router counts. */
217 area->abr_count = 0;
218 area->asbr_count = 0;
219 }
220
221 /* return index of link back to V from W, or -1 if no link found */
222 int
223 ospf_lsa_has_link (struct lsa_header *w, struct lsa_header *v)
224 {
225 unsigned int i, length;
226 struct router_lsa *rl;
227 struct network_lsa *nl;
228
229 /* In case of W is Network LSA. */
230 if (w->type == OSPF_NETWORK_LSA)
231 {
232 if (v->type == OSPF_NETWORK_LSA)
233 return -1;
234
235 nl = (struct network_lsa *) w;
236 length = (ntohs (w->length) - OSPF_LSA_HEADER_SIZE - 4) / 4;
237
238 for (i = 0; i < length; i++)
239 if (IPV4_ADDR_SAME (&nl->routers[i], &v->id))
240 return i;
241 return -1;
242 }
243
244 /* In case of W is Router LSA. */
245 if (w->type == OSPF_ROUTER_LSA)
246 {
247 rl = (struct router_lsa *) w;
248
249 length = ntohs (w->length);
250
251 for (i = 0;
252 i < ntohs (rl->links) && length >= sizeof (struct router_lsa);
253 i++, length -= 12)
254 {
255 switch (rl->link[i].type)
256 {
257 case LSA_LINK_TYPE_POINTOPOINT:
258 case LSA_LINK_TYPE_VIRTUALLINK:
259 /* Router LSA ID. */
260 if (v->type == OSPF_ROUTER_LSA &&
261 IPV4_ADDR_SAME (&rl->link[i].link_id, &v->id))
262 {
263 return i;
264 }
265 break;
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))
270 {
271 return i;
272 }
273 break;
274 case LSA_LINK_TYPE_STUB:
275 /* Not take into count? */
276 continue;
277 default:
278 break;
279 }
280 }
281 }
282 return -1;
283 }
284
285 /* Add the nexthop to the list, only if it is unique.
286 * If it's not unique, free the nexthop entry.
287 */
288 void
289 ospf_nexthop_add_unique (struct vertex_nexthop *new, struct list *nexthop)
290 {
291 struct vertex_nexthop *nh;
292 struct listnode *node;
293 int match;
294
295 match = 0;
296
297 for (ALL_LIST_ELEMENTS_RO (nexthop, node, nh))
298 {
299 /* Compare the two entries. */
300 /* XXX
301 * Comparing the parent preserves the shortest path tree
302 * structure even when the nexthops are identical.
303 */
304 if (nh->oi == new->oi &&
305 IPV4_ADDR_SAME (&nh->router, &new->router) &&
306 nh->parent == new->parent)
307 {
308 match = 1;
309 break;
310 }
311 }
312
313 if (!match)
314 listnode_add (nexthop, new);
315 else
316 vertex_nexthop_free (new);
317 }
318
319 /* Merge entries in list b into list a. */
320 void
321 ospf_nexthop_merge (struct list *a, struct list *b)
322 {
323 struct listnode *node, *nnode;
324 struct vertex_nexthop *nh;
325
326 for (ALL_LIST_ELEMENTS (b, node, nnode, nh))
327 ospf_nexthop_add_unique (nh, a);
328 }
329
330 #define ROUTER_LSA_MIN_SIZE 12
331 #define ROUTER_LSA_TOS_SIZE 4
332
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.
336 */
337 struct router_lsa_link *
338 ospf_get_next_link (struct vertex *v, struct vertex *w,
339 struct router_lsa_link *prev_link)
340 {
341 u_char *p;
342 u_char *lim;
343 struct router_lsa_link *l;
344
345 if (prev_link == NULL)
346 p = ((u_char *) v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
347 else
348 {
349 p = (u_char *) prev_link;
350 p += (ROUTER_LSA_MIN_SIZE +
351 (prev_link->m[0].tos_count * ROUTER_LSA_TOS_SIZE));
352 }
353
354 lim = ((u_char *) v->lsa) + ntohs (v->lsa->length);
355
356 while (p < lim)
357 {
358 l = (struct router_lsa_link *) p;
359
360 p += (ROUTER_LSA_MIN_SIZE + (l->m[0].tos_count * ROUTER_LSA_TOS_SIZE));
361
362 if (l->m[0].type == LSA_LINK_TYPE_STUB)
363 continue;
364
365 /* Defer NH calculation via VLs until summaries from
366 transit areas area confidered */
367
368 if (l->m[0].type == LSA_LINK_TYPE_VIRTUALLINK)
369 continue;
370
371 if (IPV4_ADDR_SAME (&l->link_id, &w->id))
372 return l;
373 }
374
375 return NULL;
376 }
377
378 /*
379 * Consider supplied next-hop for inclusion to the supplied list of
380 * equal-cost next-hops, adjust list as neccessary.
381 *
382 * (Discussed on GNU Zebra list 27 May 2003, [zebra 19184])
383 *
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.
387 *
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.
392 */
393 void
394 ospf_spf_consider_nexthop (struct list *nexthops,
395 struct vertex_nexthop *newhop)
396 {
397 struct vertex_nexthop *hop;
398 struct listnode *ln, *nn;
399
400 /* nexthop list should contain only the set of nexthops that have the lowest
401 * equal cost
402 */
403 if (nexthops->head != NULL)
404 {
405 hop = listgetdata (nexthops->head);
406
407 /* weed out hops with higher cost than the newhop */
408 if (hop->oi->output_cost > newhop->oi->output_cost)
409 {
410 /* delete the existing nexthops */
411 for (ALL_LIST_ELEMENTS (nexthops, ln, nn, hop))
412 {
413 listnode_delete (nexthops, hop);
414 vertex_nexthop_free (hop);
415 }
416 }
417 else if (hop->oi->output_cost < newhop->oi->output_cost)
418 return;
419 }
420
421 /* new hop is <= existing hops, add it */
422 listnode_add (nexthops, newhop);
423
424 return;
425 }
426
427 /* 16.1.1. Calculate nexthop from root through V (parent) to
428 * vertex W (destination).
429 */
430 void
431 ospf_nexthop_calculation (struct ospf_area *area,
432 struct vertex *v, struct vertex *w)
433 {
434 struct listnode *node, *nnode;
435 struct vertex_nexthop *nh, *x;
436 struct ospf_interface *oi = NULL;
437 struct router_lsa_link *l = NULL;
438
439
440 if (IS_DEBUG_OSPF_EVENT)
441 {
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);
445 }
446
447 if (v == area->spf)
448 {
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.
454 */
455
456 if (w->type == OSPF_VERTEX_ROUTER)
457 {
458 while ((l = ospf_get_next_link (v, w, l)))
459 {
460 /* l is a link from v to w
461 * l2 will be link from w to v
462 */
463 struct router_lsa_link *l2 = NULL;
464
465 if (IS_DEBUG_OSPF_EVENT)
466 {
467 char buf1[BUFSIZ];
468 char buf2[BUFSIZ];
469
470 zlog_debug("ospf_nexthop_calculation(): considering link "
471 "type %d link_id %s link_data %s",
472 l->m[0].type,
473 inet_ntop (AF_INET, &l->link_id, buf1, BUFSIZ),
474 inet_ntop (AF_INET, &l->link_data, buf2, BUFSIZ));
475 }
476
477 if (l->m[0].type == LSA_LINK_TYPE_POINTOPOINT)
478 {
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.
487
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.
497 */
498 oi = ospf_if_is_configured (area->ospf, &l->link_data);
499 if (oi && oi->type == OSPF_IFTYPE_POINTOMULTIPOINT)
500 {
501 struct prefix_ipv4 la;
502
503 la.family = AF_INET;
504 la.prefixlen = oi->address->prefixlen;
505
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)))
509 {
510 la.prefix = l2->link_data;
511
512 if (prefix_cmp ((struct prefix *) &la,
513 oi->address) == 0)
514 /* link_data is on our PtMP network */
515 break;
516 }
517 } /* end l is on point-to-multipoint link */
518 else
519 {
520 /* l is a regular point-to-point link.
521 Look for a link from W to V.
522 */
523 while ((l2 = ospf_get_next_link (w, v, l2)))
524 {
525 oi = ospf_if_is_configured (area->ospf,
526 &(l2->link_data));
527
528 if (oi == NULL)
529 continue;
530
531 if (!IPV4_ADDR_SAME (&oi->address->u.prefix4,
532 &l->link_data))
533 continue;
534
535 break;
536 }
537 }
538
539 if (oi && l2)
540 {
541 /* found all necessary info to build nexthop */
542 nh = vertex_nexthop_new (v);
543 nh->oi = oi;
544 nh->router = l2->link_data;
545 ospf_spf_consider_nexthop (w->nexthop, nh);
546 }
547 else
548 {
549 zlog_info("ospf_nexthop_calculation(): "
550 "could not determine nexthop for link");
551 }
552 } /* end point-to-point link from V to W */
553 } /* end iterate over links in W */
554 } /* end W is a Router vertex */
555 else
556 {
557 assert(w->type == OSPF_VERTEX_NETWORK);
558 while ((l = ospf_get_next_link (v, w, l)))
559 {
560 oi = ospf_if_is_configured (area->ospf, &(l->link_data));
561 if (oi)
562 {
563 nh = vertex_nexthop_new (v);
564 nh->oi = oi;
565 nh->router.s_addr = 0;
566 ospf_spf_consider_nexthop (w->nexthop, nh);
567 }
568 }
569 }
570 return;
571 } /* end V is the root */
572
573 /* Check if W's parent is a network connected to root. */
574 else if (v->type == OSPF_VERTEX_NETWORK)
575 {
576 /* See if any of V's parents are the root. */
577 for (ALL_LIST_ELEMENTS (v->nexthop, node, nnode, x))
578 {
579 if (x->parent == area->spf) /* connects to root? */
580 {
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...
585 */
586
587 assert(w->type == OSPF_VERTEX_ROUTER);
588 while ((l = ospf_get_next_link (w, v, l)))
589 {
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).
595 */
596 nh = vertex_nexthop_new (v);
597 nh->oi = x->oi;
598 nh->router = l->link_data;
599 ospf_spf_consider_nexthop (w->nexthop, nh);
600 }
601 return;
602 }
603 }
604 }
605
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
609 * parent.
610 */
611 for (ALL_LIST_ELEMENTS (v->nexthop, node, nnode, nh))
612 {
613 nh->parent = v;
614 ospf_nexthop_add_unique (nh, w->nexthop);
615 }
616 }
617
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.
622 */
623 void
624 ospf_spf_next (struct vertex *v, struct ospf_area *area,
625 struct pqueue * candidate)
626 {
627 struct ospf_lsa *w_lsa = NULL;
628 struct vertex *w, *cw;
629 u_char *p;
630 u_char *lim;
631 struct router_lsa_link *l = NULL;
632 struct in_addr *r;
633 int type = 0;
634
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)
638 {
639 if (IS_ROUTER_LSA_VIRTUAL ((struct router_lsa *) v->lsa))
640 area->transit = OSPF_TRANSIT_TRUE;
641 }
642
643 p = ((u_char *) v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
644 lim = ((u_char *) v->lsa) + ntohs (v->lsa->length);
645
646 while (p < lim)
647 {
648 int link = -1; /* link index for w's back link */
649
650 /* In case of V is Router-LSA. */
651 if (v->lsa->type == OSPF_ROUTER_LSA)
652 {
653 l = (struct router_lsa_link *) p;
654
655 p += (ROUTER_LSA_MIN_SIZE +
656 (l->m[0].tos_count * ROUTER_LSA_TOS_SIZE));
657
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
661 calculation. */
662 if ((type = l->m[0].type) == LSA_LINK_TYPE_STUB)
663 continue;
664
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. */
668 switch (type)
669 {
670 case LSA_LINK_TYPE_POINTOPOINT:
671 case LSA_LINK_TYPE_VIRTUALLINK:
672 if (type == LSA_LINK_TYPE_VIRTUALLINK)
673 {
674 if (IS_DEBUG_OSPF_EVENT)
675 zlog_debug ("looking up LSA through VL: %s",
676 inet_ntoa (l->link_id));
677 }
678
679 w_lsa = ospf_lsa_lookup (area, OSPF_ROUTER_LSA, l->link_id,
680 l->link_id);
681 if (w_lsa)
682 {
683 if (IS_DEBUG_OSPF_EVENT)
684 zlog_debug ("found Router LSA %s", inet_ntoa (l->link_id));
685 }
686 break;
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,
692 l->link_id);
693 if (w_lsa)
694 if (IS_DEBUG_OSPF_EVENT)
695 zlog_debug ("found the LSA");
696 break;
697 default:
698 zlog_warn ("Invalid LSA link type %d", type);
699 continue;
700 }
701 }
702 else
703 {
704 /* In case of V is Network-LSA. */
705 r = (struct in_addr *) p;
706 p += sizeof (struct in_addr);
707
708 /* Lookup the vertex W's LSA. */
709 w_lsa = ospf_lsa_lookup_by_id (area, OSPF_ROUTER_LSA, *r);
710 }
711
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] */
715 if (w_lsa == NULL)
716 continue;
717
718 if (IS_LSA_MAXAGE (w_lsa))
719 continue;
720
721 if ( (link = ospf_lsa_has_link (w_lsa->data, v->lsa)) < 0 )
722 {
723 if (IS_DEBUG_OSPF_EVENT)
724 zlog_debug ("The LSA doesn't have a link back");
725 continue;
726 }
727
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)
731 {
732 if (IS_DEBUG_OSPF_EVENT)
733 zlog_debug ("The LSA is already in SPF");
734 continue;
735 }
736
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
741 V and W. If D is: */
742
743 /* prepare vertex W. */
744 w = ospf_vertex_new (w_lsa);
745
746 /* Save W's back link index number, for use by virtual links */
747 w->backlink = link;
748
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;
754
755 /* Is there already vertex W in candidate list? */
756 if (w_lsa->stat == LSA_SPF_NOT_EXPLORED)
757 {
758 /* Calculate nexthop to W. */
759 ospf_nexthop_calculation (area, v, w);
760 pqueue_enqueue (w, candidate);
761 }
762 else if (w_lsa->stat >= 0)
763 {
764 /* Get the vertex from candidates. */
765 cw = (struct vertex *) candidate->array[w_lsa->stat];
766
767 /* if D is greater than. */
768 if (cw->distance < w->distance)
769 {
770 ospf_vertex_free (w);
771 continue;
772 }
773 /* equal to. */
774 else if (cw->distance == w->distance)
775 {
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);
781 }
782 /* less than. */
783 else
784 {
785 /* Found a lower-cost path to W. Calculate nexthop to W. */
786 ospf_nexthop_calculation (area, v, w);
787
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);
793 }
794 } /* end W is already on the candidate list */
795 } /* end loop over the links in V's LSA */
796 }
797
798 void
799 ospf_spf_route_free (struct route_table *table)
800 {
801 struct route_node *rn;
802 struct vertex *v;
803
804 for (rn = route_top (table); rn; rn = route_next (rn))
805 {
806 if ((v = rn->info))
807 {
808 ospf_vertex_free (v);
809 rn->info = NULL;
810 }
811
812 route_unlock_node (rn);
813 }
814
815 route_table_finish (table);
816 }
817
818 void
819 ospf_spf_dump (struct vertex *v, int i)
820 {
821 struct listnode *cnode;
822 struct listnode *nnode;
823 struct vertex_nexthop *nexthop;
824
825 if (v->type == OSPF_VERTEX_ROUTER)
826 {
827 if (IS_DEBUG_OSPF_EVENT)
828 zlog_debug ("SPF Result: %d [R] %s", i, inet_ntoa (v->lsa->id));
829 }
830 else
831 {
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));
836 }
837
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));
841
842 i++;
843
844 for (ALL_LIST_ELEMENTS_RO (v->child, cnode, v))
845 ospf_spf_dump (v, i);
846 }
847
848 /* Second stage of SPF calculation. */
849 void
850 ospf_spf_process_stubs (struct ospf_area *area, struct vertex *v,
851 struct route_table *rt)
852 {
853 struct listnode *cnode, *cnnode;
854 struct vertex *child;
855
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)
860 {
861 u_char *p;
862 u_char *lim;
863 struct router_lsa_link *l;
864 struct router_lsa *rlsa;
865
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;
870
871
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);
877
878 while (p < lim)
879 {
880 l = (struct router_lsa_link *) p;
881
882 p += (ROUTER_LSA_MIN_SIZE +
883 (l->m[0].tos_count * ROUTER_LSA_TOS_SIZE));
884
885 if (l->m[0].type == LSA_LINK_TYPE_STUB)
886 ospf_intra_add_stub (rt, l, v, area);
887 }
888 }
889
890 ospf_vertex_dump("ospf_process_stubs(): after examining links: ", v, 1, 1);
891
892 for (ALL_LIST_ELEMENTS (v->child, cnode, cnnode, child))
893 {
894 if (CHECK_FLAG (child->flags, OSPF_VERTEX_PROCESSED))
895 continue;
896
897 ospf_spf_process_stubs (area, child, rt);
898
899 SET_FLAG (child->flags, OSPF_VERTEX_PROCESSED);
900 }
901 }
902
903 void
904 ospf_rtrs_free (struct route_table *rtrs)
905 {
906 struct route_node *rn;
907 struct list *or_list;
908 struct ospf_route *or;
909 struct listnode *node, *nnode;
910
911 if (IS_DEBUG_OSPF_EVENT)
912 zlog_debug ("Route: Router Routing Table free");
913
914 for (rn = route_top (rtrs); rn; rn = route_next (rn))
915 if ((or_list = rn->info) != NULL)
916 {
917 for (ALL_LIST_ELEMENTS (or_list, node, nnode, or))
918 ospf_route_free (or);
919
920 list_delete (or_list);
921
922 /* Unlock the node. */
923 rn->info = NULL;
924 route_unlock_node (rn);
925 }
926 route_table_finish (rtrs);
927 }
928
929 void
930 ospf_rtrs_print (struct route_table *rtrs)
931 {
932 struct route_node *rn;
933 struct list *or_list;
934 struct listnode *ln;
935 struct listnode *pnode;
936 struct ospf_route *or;
937 struct ospf_path *path;
938 char buf1[BUFSIZ];
939 char buf2[BUFSIZ];
940
941 if (IS_DEBUG_OSPF_EVENT)
942 zlog_debug ("ospf_rtrs_print() start");
943
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))
947 {
948 switch (or->path_type)
949 {
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,
955 buf2, BUFSIZ));
956 break;
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,
962 buf2, BUFSIZ));
963 break;
964 default:
965 break;
966 }
967
968 for (ALL_LIST_ELEMENTS_RO (or->paths, pnode, path))
969 {
970 if (path->nexthop.s_addr == 0)
971 {
972 if (IS_DEBUG_OSPF_EVENT)
973 zlog_debug (" directly attached to %s\r\n",
974 IF_NAME (path->oi));
975 }
976 else
977 {
978 if (IS_DEBUG_OSPF_EVENT)
979 zlog_debug (" via %s, %s\r\n",
980 inet_ntoa (path->nexthop), IF_NAME (path->oi));
981 }
982 }
983 }
984
985 zlog_debug ("ospf_rtrs_print() end");
986 }
987
988 /* Calculating the shortest-path tree for an area. */
989 void
990 ospf_spf_calculate (struct ospf_area *area, struct route_table *new_table,
991 struct route_table *new_rtrs)
992 {
993 struct pqueue *candidate;
994 struct vertex *v;
995
996 if (IS_DEBUG_OSPF_EVENT)
997 {
998 zlog_debug ("ospf_spf_calculate: Start");
999 zlog_debug ("ospf_spf_calculate: running Dijkstra for area %s",
1000 inet_ntoa (area->area_id));
1001 }
1002
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)
1006 {
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));
1011 return;
1012 }
1013
1014 /* RFC2328 16.1. (1). */
1015 /* Initialize the algorithm's data structures. */
1016
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;
1024
1025 /* Initialize the shortest-path tree to only the root (which is the
1026 router doing the calculation). */
1027 ospf_spf_init (area);
1028 v = area->spf;
1029 /* Set LSA position to LSA_SPF_IN_SPFTREE. This vertex is the root of the
1030 * spanning tree. */
1031 *(v->stat) = LSA_SPF_IN_SPFTREE;
1032
1033 /* Set Area A's TransitCapability to FALSE. */
1034 area->transit = OSPF_TRANSIT_FALSE;
1035 area->shortcut_capability = 1;
1036
1037 for (;;)
1038 {
1039 /* RFC2328 16.1. (2). */
1040 ospf_spf_next (v, area, candidate);
1041
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)
1047 break;
1048
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
1052 process). */
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);
1058
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. */
1064
1065 /* RFC2328 16.1. (4). */
1066 if (v->type == OSPF_VERTEX_ROUTER)
1067 ospf_intra_add_router (new_rtrs, v, area);
1068 else
1069 ospf_intra_add_transit (new_table, v, area);
1070
1071 /* RFC2328 16.1. (5). */
1072 /* Iterate the algorithm by returning to Step 2. */
1073
1074 } /* end loop until no more candidate vertices */
1075
1076 if (IS_DEBUG_OSPF_EVENT)
1077 {
1078 ospf_spf_dump (area->spf, 0);
1079 ospf_route_table_dump (new_table);
1080 }
1081
1082 /* Second stage of SPF calculation procedure's */
1083 ospf_spf_process_stubs (area, area->spf, new_table);
1084
1085 /* Free candidates. */
1086 pqueue_delete (candidate);
1087
1088 /* Increment SPF Calculation Counter. */
1089 area->spf_calculation++;
1090
1091 area->ospf->ts_spf = time (NULL);
1092
1093 if (IS_DEBUG_OSPF_EVENT)
1094 zlog_debug ("ospf_spf_calculate: Stop");
1095 }
1096 \f
1097 /* Timer for SPF calculation. */
1098 int
1099 ospf_spf_calculate_timer (struct thread *thread)
1100 {
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;
1105
1106 if (IS_DEBUG_OSPF_EVENT)
1107 zlog_debug ("SPF: Timer (SPF calculation expire)");
1108
1109 ospf->t_spf_calc = NULL;
1110
1111 /* Allocate new table tree. */
1112 new_table = route_table_init ();
1113 new_rtrs = route_table_init ();
1114
1115 ospf_vl_unapprove (ospf);
1116
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);
1120
1121 ospf_vl_shut_unapproved (ospf);
1122
1123 ospf_ia_routing (ospf, new_table, new_rtrs);
1124
1125 ospf_prune_unreachable_networks (new_table);
1126 ospf_prune_unreachable_routers (new_rtrs);
1127
1128 /* AS-external-LSA calculation should not be performed here. */
1129
1130 /* If new Router Route is installed,
1131 then schedule re-calculate External routes. */
1132 if (1)
1133 ospf_ase_calculate_schedule (ospf);
1134
1135 ospf_ase_calculate_timer_add (ospf);
1136
1137 /* Update routing table. */
1138 ospf_route_install (ospf, new_table);
1139
1140 /* Update ABR/ASBR routing table */
1141 if (ospf->old_rtrs)
1142 {
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);
1146 }
1147
1148 ospf->old_rtrs = ospf->new_rtrs;
1149 ospf->new_rtrs = new_rtrs;
1150
1151 if (IS_OSPF_ABR (ospf))
1152 ospf_abr_task (ospf);
1153
1154 if (IS_DEBUG_OSPF_EVENT)
1155 zlog_debug ("SPF: calculation complete");
1156
1157 return 0;
1158 }
1159
1160 /* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
1161 set timer for SPF calc. */
1162 void
1163 ospf_spf_calculate_schedule (struct ospf *ospf)
1164 {
1165 time_t ht, delay;
1166
1167 if (IS_DEBUG_OSPF_EVENT)
1168 zlog_debug ("SPF: calculation timer scheduled");
1169
1170 /* OSPF instance does not exist. */
1171 if (ospf == NULL)
1172 return;
1173
1174 /* SPF calculation timer is already scheduled. */
1175 if (ospf->t_spf_calc)
1176 {
1177 if (IS_DEBUG_OSPF_EVENT)
1178 zlog_debug ("SPF: calculation timer is already scheduled: %p",
1179 ospf->t_spf_calc);
1180 return;
1181 }
1182
1183 ht = time (NULL) - ospf->ts_spf;
1184
1185 /* Get SPF calculation delay time. */
1186 if (ht < ospf->spf_holdtime)
1187 {
1188 if (ospf->spf_holdtime - ht < ospf->spf_delay)
1189 delay = ospf->spf_delay;
1190 else
1191 delay = ospf->spf_holdtime - ht;
1192 }
1193 else
1194 delay = ospf->spf_delay;
1195
1196 if (IS_DEBUG_OSPF_EVENT)
1197 zlog_debug ("SPF: calculation timer delay = %ld", (long)delay);
1198 ospf->t_spf_calc =
1199 thread_add_timer (master, ospf_spf_calculate_timer, ospf, delay);
1200 }