]>
git.proxmox.com Git - mirror_frr.git/blob - ospfd/ospf_ia.c
2 * OSPF inter-area routing.
3 * Copyright (C) 1999, 2000 Alex Zinin, Toshiaki Takada
5 * This file is part of GNU Zebra.
7 * GNU Zebra is free software; you can redistribute it and/or modify it
8 * under the terms of the GNU General Public License as published by the
9 * Free Software Foundation; either version 2, or (at your option) any
12 * GNU Zebra is distributed in the hope that it will be useful, but
13 * WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * General Public License for more details.
17 * You should have received a copy of the GNU General Public License along
18 * with this program; see the file COPYING; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
33 #include "ospfd/ospfd.h"
34 #include "ospfd/ospf_interface.h"
35 #include "ospfd/ospf_ism.h"
36 #include "ospfd/ospf_asbr.h"
37 #include "ospfd/ospf_lsa.h"
38 #include "ospfd/ospf_lsdb.h"
39 #include "ospfd/ospf_neighbor.h"
40 #include "ospfd/ospf_nsm.h"
41 #include "ospfd/ospf_spf.h"
42 #include "ospfd/ospf_route.h"
43 #include "ospfd/ospf_ase.h"
44 #include "ospfd/ospf_abr.h"
45 #include "ospfd/ospf_ia.h"
46 #include "ospfd/ospf_dump.h"
48 static struct ospf_route
*
49 ospf_find_abr_route (struct route_table
*rtrs
,
50 struct prefix_ipv4
*abr
,
51 struct ospf_area
*area
)
53 struct route_node
*rn
;
54 struct ospf_route
*or;
55 struct listnode
*node
;
57 if ((rn
= route_node_lookup (rtrs
, (struct prefix
*) abr
)) == NULL
)
60 route_unlock_node (rn
);
62 for (ALL_LIST_ELEMENTS_RO ((struct list
*) rn
->info
, node
, or))
63 if (IPV4_ADDR_SAME (&or->u
.std
.area_id
, &area
->area_id
)
64 && (or->u
.std
.flags
& ROUTER_LSA_BORDER
))
71 ospf_ia_network_route (struct ospf
*ospf
, struct route_table
*rt
,
72 struct prefix_ipv4
*p
, struct ospf_route
*new_or
,
73 struct ospf_route
*abr_or
)
75 struct route_node
*rn1
;
76 struct ospf_route
*or;
78 if (IS_DEBUG_OSPF_EVENT
)
79 zlog_debug ("ospf_ia_network_route(): processing summary route to %s/%d",
80 inet_ntoa (p
->prefix
), p
->prefixlen
);
82 /* Find a route to the same dest */
83 if ((rn1
= route_node_lookup (rt
, (struct prefix
*) p
)))
87 route_unlock_node (rn1
);
91 if (IS_DEBUG_OSPF_EVENT
)
92 zlog_debug ("ospf_ia_network_route(): "
93 "Found a route to the same network");
94 /* Check the existing route. */
95 if ((res
= ospf_route_cmp (ospf
, new_or
, or)) < 0)
97 /* New route is better, so replace old one. */
98 ospf_route_subst (rn1
, new_or
, abr_or
);
102 /* New and old route are equal, so next hops can be added. */
103 route_lock_node (rn1
);
104 ospf_route_copy_nexthops (or, abr_or
->paths
);
105 route_unlock_node (rn1
);
107 /* new route can be deleted, because existing route has been updated. */
108 ospf_route_free (new_or
);
112 /* New route is worse, so free it. */
113 ospf_route_free (new_or
);
120 if (IS_DEBUG_OSPF_EVENT
)
121 zlog_debug ("ospf_ia_network_route(): add new route to %s/%d",
122 inet_ntoa (p
->prefix
), p
->prefixlen
);
123 ospf_route_add (rt
, p
, new_or
, abr_or
);
128 ospf_ia_router_route (struct ospf
*ospf
, struct route_table
*rtrs
,
129 struct prefix_ipv4
*p
,
130 struct ospf_route
*new_or
, struct ospf_route
*abr_or
)
132 struct ospf_route
*or = NULL
;
133 struct route_node
*rn
;
136 if (IS_DEBUG_OSPF_EVENT
)
137 zlog_debug ("ospf_ia_router_route(): considering %s/%d",
138 inet_ntoa (p
->prefix
), p
->prefixlen
);
139 /* Find a route to the same dest */
140 rn
= route_node_get (rtrs
, (struct prefix
*) p
);
142 if (rn
->info
== NULL
)
143 /* This is a new route */
144 rn
->info
= list_new ();
147 struct ospf_area
*or_area
;
148 or_area
= ospf_area_lookup_by_area_id (ospf
, new_or
->u
.std
.area_id
);
150 /* This is an additional route */
151 route_unlock_node (rn
);
152 or = ospf_find_asbr_route_through_area (rtrs
, p
, or_area
);
157 if (IS_DEBUG_OSPF_EVENT
)
158 zlog_debug ("ospf_ia_router_route(): "
159 "a route to the same ABR through the same area exists");
160 /* New route is better */
161 if ((ret
= ospf_route_cmp (ospf
, new_or
, or)) < 0)
163 listnode_delete (rn
->info
, or);
164 ospf_route_free (or);
167 /* Routes are the same */
170 if (IS_DEBUG_OSPF_EVENT
)
171 zlog_debug ("ospf_ia_router_route(): merging the new route");
173 ospf_route_copy_nexthops (or, abr_or
->paths
);
174 ospf_route_free (new_or
);
177 /* New route is worse */
180 if (IS_DEBUG_OSPF_EVENT
)
181 zlog_debug ("ospf_ia_router_route(): skipping the new route");
182 ospf_route_free (new_or
);
187 ospf_route_copy_nexthops (new_or
, abr_or
->paths
);
189 if (IS_DEBUG_OSPF_EVENT
)
190 zlog_debug ("ospf_ia_router_route(): adding the new route");
192 listnode_add (rn
->info
, new_or
);
197 process_summary_lsa (struct ospf_area
*area
, struct route_table
*rt
,
198 struct route_table
*rtrs
, struct ospf_lsa
*lsa
)
200 struct ospf
*ospf
= area
->ospf
;
201 struct ospf_area_range
*range
;
202 struct ospf_route
*abr_or
, *new_or
;
203 struct summary_lsa
*sl
;
204 struct prefix_ipv4 p
, abr
;
210 sl
= (struct summary_lsa
*) lsa
->data
;
212 if (IS_DEBUG_OSPF_EVENT
)
213 zlog_debug ("process_summary_lsa(): LS ID: %s", inet_ntoa (sl
->header
.id
));
215 metric
= GET_METRIC (sl
->metric
);
217 if (metric
== OSPF_LS_INFINITY
)
220 if (IS_LSA_MAXAGE (lsa
))
223 if (ospf_lsa_is_self_originated (area
->ospf
, lsa
))
227 p
.prefix
= sl
->header
.id
;
229 if (sl
->header
.type
== OSPF_SUMMARY_LSA
)
230 p
.prefixlen
= ip_masklen (sl
->mask
);
232 p
.prefixlen
= IPV4_MAX_BITLEN
;
234 apply_mask_ipv4 (&p
);
236 if (sl
->header
.type
== OSPF_SUMMARY_LSA
&&
237 (range
= ospf_area_range_match_any (ospf
, &p
)) &&
238 ospf_area_range_active (range
))
241 /* XXX: This check seems dubious to me. If an ABR has already decided
242 * to consider summaries received in this area, then why would one wish
243 * to exclude default?
245 if (IS_OSPF_ABR(ospf
) &&
246 ospf
->abr_type
!= OSPF_ABR_STAND
&&
247 area
->external_routing
!= OSPF_AREA_DEFAULT
&&
248 p
.prefix
.s_addr
== OSPF_DEFAULT_DESTINATION
&&
250 return 0; /* Ignore summary default from a stub area */
252 abr
.family
= AF_INET
;
253 abr
.prefix
= sl
->header
.adv_router
;
254 abr
.prefixlen
= IPV4_MAX_BITLEN
;
255 apply_mask_ipv4 (&abr
);
257 abr_or
= ospf_find_abr_route (rtrs
, &abr
, area
);
262 new_or
= ospf_route_new ();
263 new_or
->type
= OSPF_DESTINATION_NETWORK
;
264 new_or
->id
= sl
->header
.id
;
265 new_or
->mask
= sl
->mask
;
266 new_or
->u
.std
.options
= sl
->header
.options
;
267 new_or
->u
.std
.origin
= (struct lsa_header
*) sl
;
268 new_or
->cost
= abr_or
->cost
+ metric
;
269 new_or
->u
.std
.area_id
= area
->area_id
;
270 new_or
->u
.std
.external_routing
= area
->external_routing
;
271 new_or
->path_type
= OSPF_PATH_INTER_AREA
;
273 if (sl
->header
.type
== OSPF_SUMMARY_LSA
)
274 ospf_ia_network_route (ospf
, rt
, &p
, new_or
, abr_or
);
277 new_or
->type
= OSPF_DESTINATION_ROUTER
;
278 new_or
->u
.std
.flags
= ROUTER_LSA_EXTERNAL
;
279 ospf_ia_router_route (ospf
, rtrs
, &p
, new_or
, abr_or
);
286 ospf_examine_summaries (struct ospf_area
*area
,
287 struct route_table
*lsdb_rt
,
288 struct route_table
*rt
,
289 struct route_table
*rtrs
)
291 struct ospf_lsa
*lsa
;
292 struct route_node
*rn
;
294 LSDB_LOOP (lsdb_rt
, rn
, lsa
)
295 process_summary_lsa (area
, rt
, rtrs
, lsa
);
299 ospf_area_is_transit (struct ospf_area
*area
)
301 return (area
->transit
== OSPF_TRANSIT_TRUE
) ||
302 ospf_full_virtual_nbrs(area
); /* Cisco forgets to set the V-bit :( */
306 ospf_update_network_route (struct ospf
*ospf
,
307 struct route_table
*rt
,
308 struct route_table
*rtrs
,
309 struct summary_lsa
*lsa
,
310 struct prefix_ipv4
*p
,
311 struct ospf_area
*area
)
313 struct route_node
*rn
;
314 struct ospf_route
*or, *abr_or
, *new_or
;
315 struct prefix_ipv4 abr
;
318 abr
.family
= AF_INET
;
319 abr
.prefix
=lsa
->header
.adv_router
;
320 abr
.prefixlen
= IPV4_MAX_BITLEN
;
321 apply_mask_ipv4 (&abr
);
323 abr_or
= ospf_find_abr_route (rtrs
, &abr
, area
);
327 if (IS_DEBUG_OSPF_EVENT
)
328 zlog_debug ("ospf_update_network_route(): can't find a route to the ABR");
332 cost
= abr_or
->cost
+ GET_METRIC (lsa
->metric
);
334 rn
= route_node_lookup (rt
, (struct prefix
*) p
);
338 if (ospf
->abr_type
!= OSPF_ABR_SHORTCUT
)
339 return; /* Standard ABR can update only already installed
341 if (IS_DEBUG_OSPF_EVENT
)
342 zlog_debug ("ospf_update_network_route(): "
343 "Allowing Shortcut ABR to add new route");
344 new_or
= ospf_route_new ();
345 new_or
->type
= OSPF_DESTINATION_NETWORK
;
346 new_or
->id
= lsa
->header
.id
;
347 new_or
->mask
= lsa
->mask
;
348 new_or
->u
.std
.options
= lsa
->header
.options
;
349 new_or
->u
.std
.origin
= (struct lsa_header
*) lsa
;
351 new_or
->u
.std
.area_id
= area
->area_id
;
352 new_or
->u
.std
.external_routing
= area
->external_routing
;
353 new_or
->path_type
= OSPF_PATH_INTER_AREA
;
354 ospf_route_add (rt
, p
, new_or
, abr_or
);
360 route_unlock_node (rn
);
361 if (rn
->info
== NULL
)
367 if (or->path_type
!= OSPF_PATH_INTRA_AREA
&&
368 or->path_type
!= OSPF_PATH_INTER_AREA
)
370 if (IS_DEBUG_OSPF_EVENT
)
371 zlog_debug ("ospf_update_network_route(): ERR: path type is wrong");
375 if (ospf
->abr_type
== OSPF_ABR_SHORTCUT
)
377 if (or->path_type
== OSPF_PATH_INTRA_AREA
&&
378 !OSPF_IS_AREA_ID_BACKBONE (or->u
.std
.area_id
))
380 if (IS_DEBUG_OSPF_EVENT
)
381 zlog_debug ("ospf_update_network_route(): Shortcut: "
382 "this intra-area path is not backbone");
386 else /* Not Shortcut ABR */
388 if (!OSPF_IS_AREA_ID_BACKBONE (or->u
.std
.area_id
))
390 if (IS_DEBUG_OSPF_EVENT
)
391 zlog_debug ("ospf_update_network_route(): "
392 "route is not BB-associated");
393 return; /* We can update only BB routes */
399 if (IS_DEBUG_OSPF_EVENT
)
400 zlog_debug ("ospf_update_network_route(): new route is worse");
404 if (or->cost
== cost
)
406 if (IS_DEBUG_OSPF_EVENT
)
407 zlog_debug ("ospf_update_network_route(): "
408 "new route is same distance, adding nexthops");
409 ospf_route_copy_nexthops (or, abr_or
->paths
);
414 if (IS_DEBUG_OSPF_EVENT
)
415 zlog_debug ("ospf_update_network_route(): "
416 "new route is better, overriding nexthops");
417 ospf_route_subst_nexthops (or, abr_or
->paths
);
420 if ((ospf
->abr_type
== OSPF_ABR_SHORTCUT
) &&
421 !OSPF_IS_AREA_ID_BACKBONE (or->u
.std
.area_id
))
423 or->path_type
= OSPF_PATH_INTER_AREA
;
424 or->u
.std
.area_id
= area
->area_id
;
425 or->u
.std
.external_routing
= area
->external_routing
;
426 /* Note that we can do this only in Shortcut ABR mode,
427 because standard ABR must leave the route type and area
435 ospf_update_router_route (struct ospf
*ospf
,
436 struct route_table
*rtrs
,
437 struct summary_lsa
*lsa
,
438 struct prefix_ipv4
*p
,
439 struct ospf_area
*area
)
441 struct ospf_route
*or, *abr_or
, *new_or
;
442 struct prefix_ipv4 abr
;
445 abr
.family
= AF_INET
;
446 abr
.prefix
= lsa
->header
.adv_router
;
447 abr
.prefixlen
= IPV4_MAX_BITLEN
;
448 apply_mask_ipv4 (&abr
);
450 abr_or
= ospf_find_abr_route (rtrs
, &abr
, area
);
454 if (IS_DEBUG_OSPF_EVENT
)
455 zlog_debug ("ospf_update_router_route(): can't find a route to the ABR");
459 cost
= abr_or
->cost
+ GET_METRIC (lsa
->metric
);
461 /* First try to find a backbone path,
462 because standard ABR can update only BB-associated paths */
464 if ((ospf
->backbone
== NULL
) &&
465 (ospf
->abr_type
!= OSPF_ABR_SHORTCUT
))
466 return; /* no BB area, not Shortcut ABR, exiting */
468 /* find the backbone route, if possible */
469 if ((ospf
->backbone
== NULL
)
470 || !(or = ospf_find_asbr_route_through_area (rtrs
, p
, ospf
->backbone
)))
472 if (ospf
->abr_type
!= OSPF_ABR_SHORTCUT
)
474 /* route to ASBR through the BB not found
475 the router is not Shortcut ABR, exiting */
479 /* We're a Shortcut ABR*/
481 /* Let it either add a new router or update the route
482 through the same (non-BB) area. */
484 new_or
= ospf_route_new ();
485 new_or
->type
= OSPF_DESTINATION_ROUTER
;
486 new_or
->id
= lsa
->header
.id
;
487 new_or
->mask
= lsa
->mask
;
488 new_or
->u
.std
.options
= lsa
->header
.options
;
489 new_or
->u
.std
.origin
= (struct lsa_header
*)lsa
;
491 new_or
->u
.std
.area_id
= area
->area_id
;
492 new_or
->u
.std
.external_routing
= area
->external_routing
;
493 new_or
->path_type
= OSPF_PATH_INTER_AREA
;
494 new_or
->u
.std
.flags
= ROUTER_LSA_EXTERNAL
;
495 ospf_ia_router_route (ospf
, rtrs
, p
, new_or
, abr_or
);
501 /* At this point the "or" is always bb-associated */
503 if (!(or->u
.std
.flags
& ROUTER_LSA_EXTERNAL
))
505 if (IS_DEBUG_OSPF_EVENT
)
506 zlog_debug ("ospf_upd_router_route(): the remote router is not an ASBR");
510 if (or->path_type
!= OSPF_PATH_INTRA_AREA
&&
511 or->path_type
!= OSPF_PATH_INTER_AREA
)
517 else if (or->cost
== cost
)
518 ospf_route_copy_nexthops (or, abr_or
->paths
);
520 else if (or->cost
> cost
)
522 ospf_route_subst_nexthops (or, abr_or
->paths
);
525 /* Even if the ABR runs in Shortcut mode, we can't change
526 the path type and area, because the "or" is always bb-associated
527 at this point and even Shortcut ABR can't change these attributes */
532 process_transit_summary_lsa (struct ospf_area
*area
, struct route_table
*rt
,
533 struct route_table
*rtrs
, struct ospf_lsa
*lsa
)
535 struct ospf
*ospf
= area
->ospf
;
536 struct summary_lsa
*sl
;
537 struct prefix_ipv4 p
;
543 sl
= (struct summary_lsa
*) lsa
->data
;
545 if (IS_DEBUG_OSPF_EVENT
)
546 zlog_debug ("process_transit_summaries(): LS ID: %s",
547 inet_ntoa (lsa
->data
->id
));
548 metric
= GET_METRIC (sl
->metric
);
550 if (metric
== OSPF_LS_INFINITY
)
552 if (IS_DEBUG_OSPF_EVENT
)
553 zlog_debug ("process_transit_summaries(): metric is infinity, skip");
557 if (IS_LSA_MAXAGE (lsa
))
559 if (IS_DEBUG_OSPF_EVENT
)
560 zlog_debug ("process_transit_summaries(): This LSA is too old");
564 if (ospf_lsa_is_self_originated (area
->ospf
, lsa
))
566 if (IS_DEBUG_OSPF_EVENT
)
567 zlog_debug ("process_transit_summaries(): This LSA is mine, skip");
572 p
.prefix
= sl
->header
.id
;
574 if (sl
->header
.type
== OSPF_SUMMARY_LSA
)
575 p
.prefixlen
= ip_masklen (sl
->mask
);
577 p
.prefixlen
= IPV4_MAX_BITLEN
;
579 apply_mask_ipv4 (&p
);
581 if (sl
->header
.type
== OSPF_SUMMARY_LSA
)
582 ospf_update_network_route (ospf
, rt
, rtrs
, sl
, &p
, area
);
584 ospf_update_router_route (ospf
, rtrs
, sl
, &p
, area
);
590 ospf_examine_transit_summaries (struct ospf_area
*area
,
591 struct route_table
*lsdb_rt
,
592 struct route_table
*rt
,
593 struct route_table
*rtrs
)
595 struct ospf_lsa
*lsa
;
596 struct route_node
*rn
;
598 LSDB_LOOP (lsdb_rt
, rn
, lsa
)
599 process_transit_summary_lsa (area
, rt
, rtrs
, lsa
);
603 ospf_ia_routing (struct ospf
*ospf
,
604 struct route_table
*rt
,
605 struct route_table
*rtrs
)
607 struct ospf_area
* area
;
609 if (IS_DEBUG_OSPF_EVENT
)
610 zlog_debug ("ospf_ia_routing():start");
612 if (IS_OSPF_ABR (ospf
))
614 struct listnode
*node
;
615 struct ospf_area
*area
;
617 switch (ospf
->abr_type
)
620 if (IS_DEBUG_OSPF_EVENT
)
621 zlog_debug ("ospf_ia_routing():Standard ABR");
623 if ((area
= ospf
->backbone
))
625 struct listnode
*node
;
627 if (IS_DEBUG_OSPF_EVENT
)
629 zlog_debug ("ospf_ia_routing():backbone area found");
630 zlog_debug ("ospf_ia_routing():examining summaries");
633 OSPF_EXAMINE_SUMMARIES_ALL (area
, rt
, rtrs
);
635 for (ALL_LIST_ELEMENTS_RO (ospf
->areas
, node
, area
))
636 if (area
!= ospf
->backbone
)
637 if (ospf_area_is_transit (area
))
638 OSPF_EXAMINE_TRANSIT_SUMMARIES_ALL (area
, rt
, rtrs
);
641 if (IS_DEBUG_OSPF_EVENT
)
642 zlog_debug ("ospf_ia_routing():backbone area NOT found");
646 if (IS_DEBUG_OSPF_EVENT
)
647 zlog_debug ("ospf_ia_routing():Alternative Cisco/IBM ABR");
648 area
= ospf
->backbone
; /* Find the BB */
650 /* If we have an active BB connection */
651 if (area
&& ospf_act_bb_connection (ospf
))
653 if (IS_DEBUG_OSPF_EVENT
)
655 zlog_debug ("ospf_ia_routing(): backbone area found");
656 zlog_debug ("ospf_ia_routing(): examining BB summaries");
659 OSPF_EXAMINE_SUMMARIES_ALL (area
, rt
, rtrs
);
661 for (ALL_LIST_ELEMENTS_RO (ospf
->areas
, node
, area
))
662 if (area
!= ospf
->backbone
)
663 if (ospf_area_is_transit (area
))
664 OSPF_EXAMINE_TRANSIT_SUMMARIES_ALL (area
, rt
, rtrs
);
667 { /* No active BB connection--consider all areas */
668 if (IS_DEBUG_OSPF_EVENT
)
669 zlog_debug ("ospf_ia_routing(): "
670 "Active BB connection not found");
671 for (ALL_LIST_ELEMENTS_RO (ospf
->areas
, node
, area
))
672 OSPF_EXAMINE_SUMMARIES_ALL (area
, rt
, rtrs
);
675 case OSPF_ABR_SHORTCUT
:
676 if (IS_DEBUG_OSPF_EVENT
)
677 zlog_debug ("ospf_ia_routing():Alternative Shortcut");
678 area
= ospf
->backbone
; /* Find the BB */
680 /* If we have an active BB connection */
681 if (area
&& ospf_act_bb_connection (ospf
))
683 if (IS_DEBUG_OSPF_EVENT
)
685 zlog_debug ("ospf_ia_routing(): backbone area found");
686 zlog_debug ("ospf_ia_routing(): examining BB summaries");
688 OSPF_EXAMINE_SUMMARIES_ALL (area
, rt
, rtrs
);
691 for (ALL_LIST_ELEMENTS_RO (ospf
->areas
, node
, area
))
692 if (area
!= ospf
->backbone
)
693 if (ospf_area_is_transit (area
) ||
694 ((area
->shortcut_configured
!= OSPF_SHORTCUT_DISABLE
) &&
695 ((ospf
->backbone
== NULL
) ||
696 ((area
->shortcut_configured
== OSPF_SHORTCUT_ENABLE
) &&
697 area
->shortcut_capability
))))
698 OSPF_EXAMINE_TRANSIT_SUMMARIES_ALL (area
, rt
, rtrs
);
706 struct listnode
*node
;
708 if (IS_DEBUG_OSPF_EVENT
)
709 zlog_debug ("ospf_ia_routing():not ABR, considering all areas");
711 for (ALL_LIST_ELEMENTS_RO (ospf
->areas
, node
, area
))
712 OSPF_EXAMINE_SUMMARIES_ALL (area
, rt
, rtrs
);