]>
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
*ospf_find_abr_route(struct route_table
*rtrs
,
49 struct prefix_ipv4
*abr
,
50 struct ospf_area
*area
)
52 struct route_node
*rn
;
53 struct ospf_route
* or ;
54 struct listnode
*node
;
56 if ((rn
= route_node_lookup(rtrs
, (struct prefix
*)abr
)) == NULL
)
59 route_unlock_node(rn
);
61 for (ALL_LIST_ELEMENTS_RO((struct list
*)rn
->info
, node
, or))
62 if (IPV4_ADDR_SAME(& or->u
.std
.area_id
, &area
->area_id
)
63 && (or->u
.std
.flags
& ROUTER_LSA_BORDER
))
69 static void ospf_ia_network_route(struct ospf
*ospf
, struct route_table
*rt
,
70 struct prefix_ipv4
*p
,
71 struct ospf_route
*new_or
,
72 struct ospf_route
*abr_or
)
74 struct route_node
*rn1
;
75 struct ospf_route
* or ;
77 if (IS_DEBUG_OSPF_EVENT
)
78 zlog_debug("%s: processing summary route to %pFX", __func__
, p
);
80 /* Find a route to the same dest */
81 if ((rn1
= route_node_lookup(rt
, (struct prefix
*)p
))) {
84 route_unlock_node(rn1
);
86 if ((or = rn1
->info
)) {
87 if (IS_DEBUG_OSPF_EVENT
)
89 "%s: Found a route to the same network",
91 /* Check the existing route. */
92 if ((res
= ospf_route_cmp(ospf
, new_or
, or)) < 0) {
93 /* New route is better, so replace old one. */
94 ospf_route_subst(rn1
, new_or
, abr_or
);
95 } else if (res
== 0) {
96 /* New and old route are equal, so next hops can
99 ospf_route_copy_nexthops(or, abr_or
->paths
);
100 route_unlock_node(rn1
);
102 /* new route can be deleted, because existing
103 * route has been updated. */
104 ospf_route_free(new_or
);
106 /* New route is worse, so free it. */
107 ospf_route_free(new_or
);
112 else { /* no route */
113 if (IS_DEBUG_OSPF_EVENT
)
114 zlog_debug("%s: add new route to %pFX", __func__
, p
);
115 ospf_route_add(rt
, p
, new_or
, abr_or
);
119 static void ospf_ia_router_route(struct ospf
*ospf
, struct route_table
*rtrs
,
120 struct prefix_ipv4
*p
,
121 struct ospf_route
*new_or
,
122 struct ospf_route
*abr_or
)
124 struct ospf_route
* or = NULL
;
125 struct route_node
*rn
;
128 if (IS_DEBUG_OSPF_EVENT
)
129 zlog_debug("%s: considering %pFX", __func__
, p
);
131 /* Find a route to the same dest */
132 rn
= route_node_get(rtrs
, (struct prefix
*)p
);
134 if (rn
->info
== NULL
)
135 /* This is a new route */
136 rn
->info
= list_new();
138 struct ospf_area
*or_area
;
139 or_area
= ospf_area_lookup_by_area_id(ospf
,
140 new_or
->u
.std
.area_id
);
142 /* This is an additional route */
143 route_unlock_node(rn
);
144 or = ospf_find_asbr_route_through_area(rtrs
, p
, or_area
);
148 if (IS_DEBUG_OSPF_EVENT
)
150 "%s: a route to the same ABR through the same area exists",
152 /* New route is better */
153 if ((ret
= ospf_route_cmp(ospf
, new_or
, or)) < 0) {
154 listnode_delete(rn
->info
, or);
158 /* Routes are the same */
160 if (IS_DEBUG_OSPF_EVENT
)
161 zlog_debug("%s: merging the new route",
164 ospf_route_copy_nexthops(or, abr_or
->paths
);
165 ospf_route_free(new_or
);
168 /* New route is worse */
170 if (IS_DEBUG_OSPF_EVENT
)
171 zlog_debug("%s: skipping the new route",
173 ospf_route_free(new_or
);
178 ospf_route_copy_nexthops(new_or
, abr_or
->paths
);
180 if (IS_DEBUG_OSPF_EVENT
)
181 zlog_debug("%s: adding the new route", __func__
);
183 listnode_add(rn
->info
, new_or
);
187 static int process_summary_lsa(struct ospf_area
*area
, struct route_table
*rt
,
188 struct route_table
*rtrs
, struct ospf_lsa
*lsa
)
190 struct ospf
*ospf
= area
->ospf
;
191 struct ospf_area_range
*range
;
192 struct ospf_route
*abr_or
, *new_or
;
193 struct summary_lsa
*sl
;
194 struct prefix_ipv4 p
, abr
;
200 sl
= (struct summary_lsa
*)lsa
->data
;
202 if (IS_DEBUG_OSPF_EVENT
)
203 zlog_debug("%s: LS ID: %pI4", __func__
, &sl
->header
.id
);
205 metric
= GET_METRIC(sl
->metric
);
207 if (metric
== OSPF_LS_INFINITY
)
210 if (IS_LSA_MAXAGE(lsa
))
213 if (ospf_lsa_is_self_originated(area
->ospf
, lsa
))
217 p
.prefix
= sl
->header
.id
;
219 if (sl
->header
.type
== OSPF_SUMMARY_LSA
)
220 p
.prefixlen
= ip_masklen(sl
->mask
);
222 p
.prefixlen
= IPV4_MAX_BITLEN
;
226 if (sl
->header
.type
== OSPF_SUMMARY_LSA
227 && (range
= ospf_area_range_match_any(ospf
, &p
))
228 && ospf_area_range_active(range
))
231 /* XXX: This check seems dubious to me. If an ABR has already decided
232 * to consider summaries received in this area, then why would one wish
233 * to exclude default?
235 if (IS_OSPF_ABR(ospf
) && ospf
->abr_type
!= OSPF_ABR_STAND
236 && area
->external_routing
!= OSPF_AREA_DEFAULT
237 && p
.prefix
.s_addr
== OSPF_DEFAULT_DESTINATION
&& p
.prefixlen
== 0)
238 return 0; /* Ignore summary default from a stub area */
240 abr
.family
= AF_INET
;
241 abr
.prefix
= sl
->header
.adv_router
;
242 abr
.prefixlen
= IPV4_MAX_BITLEN
;
243 apply_mask_ipv4(&abr
);
245 abr_or
= ospf_find_abr_route(rtrs
, &abr
, area
);
250 new_or
= ospf_route_new();
251 new_or
->type
= OSPF_DESTINATION_NETWORK
;
252 new_or
->id
= sl
->header
.id
;
253 new_or
->mask
= sl
->mask
;
254 new_or
->u
.std
.options
= sl
->header
.options
;
255 new_or
->u
.std
.origin
= (struct lsa_header
*)sl
;
256 new_or
->cost
= abr_or
->cost
+ metric
;
257 new_or
->u
.std
.area_id
= area
->area_id
;
258 new_or
->u
.std
.external_routing
= area
->external_routing
;
259 new_or
->path_type
= OSPF_PATH_INTER_AREA
;
261 if (sl
->header
.type
== OSPF_SUMMARY_LSA
)
262 ospf_ia_network_route(ospf
, rt
, &p
, new_or
, abr_or
);
264 new_or
->type
= OSPF_DESTINATION_ROUTER
;
265 new_or
->u
.std
.flags
= ROUTER_LSA_EXTERNAL
;
266 ospf_ia_router_route(ospf
, rtrs
, &p
, new_or
, abr_or
);
272 static void ospf_examine_summaries(struct ospf_area
*area
,
273 struct route_table
*lsdb_rt
,
274 struct route_table
*rt
,
275 struct route_table
*rtrs
)
277 struct ospf_lsa
*lsa
;
278 struct route_node
*rn
;
280 LSDB_LOOP (lsdb_rt
, rn
, lsa
)
281 process_summary_lsa(area
, rt
, rtrs
, lsa
);
284 int ospf_area_is_transit(struct ospf_area
*area
)
286 return (area
->transit
== OSPF_TRANSIT_TRUE
)
287 || ospf_full_virtual_nbrs(
288 area
); /* Cisco forgets to set the V-bit :( */
291 static void ospf_update_network_route(struct ospf
*ospf
, struct route_table
*rt
,
292 struct route_table
*rtrs
,
293 struct summary_lsa
*lsa
,
294 struct prefix_ipv4
*p
,
295 struct ospf_area
*area
)
297 struct route_node
*rn
;
298 struct ospf_route
* or, *abr_or
, *new_or
;
299 struct prefix_ipv4 abr
;
302 abr
.family
= AF_INET
;
303 abr
.prefix
= lsa
->header
.adv_router
;
304 abr
.prefixlen
= IPV4_MAX_BITLEN
;
305 apply_mask_ipv4(&abr
);
307 abr_or
= ospf_find_abr_route(rtrs
, &abr
, area
);
309 if (abr_or
== NULL
) {
310 if (IS_DEBUG_OSPF_EVENT
)
311 zlog_debug("%s: can't find a route to the ABR",
316 cost
= abr_or
->cost
+ GET_METRIC(lsa
->metric
);
318 rn
= route_node_lookup(rt
, (struct prefix
*)p
);
321 if (ospf
->abr_type
!= OSPF_ABR_SHORTCUT
)
322 return; /* Standard ABR can update only already
325 if (IS_DEBUG_OSPF_EVENT
)
326 zlog_debug("%s: Allowing Shortcut ABR to add new route",
328 new_or
= ospf_route_new();
329 new_or
->type
= OSPF_DESTINATION_NETWORK
;
330 new_or
->id
= lsa
->header
.id
;
331 new_or
->mask
= lsa
->mask
;
332 new_or
->u
.std
.options
= lsa
->header
.options
;
333 new_or
->u
.std
.origin
= (struct lsa_header
*)lsa
;
335 new_or
->u
.std
.area_id
= area
->area_id
;
336 new_or
->u
.std
.external_routing
= area
->external_routing
;
337 new_or
->path_type
= OSPF_PATH_INTER_AREA
;
338 ospf_route_add(rt
, p
, new_or
, abr_or
);
342 route_unlock_node(rn
);
343 if (rn
->info
== NULL
)
349 if (or->path_type
!= OSPF_PATH_INTRA_AREA
&&
350 or->path_type
!= OSPF_PATH_INTER_AREA
) {
351 if (IS_DEBUG_OSPF_EVENT
)
352 zlog_debug("%s: ERR: path type is wrong", __func__
);
356 if (ospf
->abr_type
== OSPF_ABR_SHORTCUT
) {
358 or->path_type
== OSPF_PATH_INTRA_AREA
359 && !OSPF_IS_AREA_ID_BACKBONE(
360 or->u
.std
.area_id
)) {
361 if (IS_DEBUG_OSPF_EVENT
)
363 "%s: Shortcut: this intra-area path is not backbone",
367 } else /* Not Shortcut ABR */
369 if (!OSPF_IS_AREA_ID_BACKBONE(or->u
.std
.area_id
)) {
370 if (IS_DEBUG_OSPF_EVENT
)
371 zlog_debug("%s: route is not BB-associated",
373 return; /* We can update only BB routes */
377 if (or->cost
< cost
) {
378 if (IS_DEBUG_OSPF_EVENT
)
379 zlog_debug("%s: new route is worse", __func__
);
383 if (or->cost
== cost
) {
384 if (IS_DEBUG_OSPF_EVENT
)
386 "%s: new route is same distance, adding nexthops",
388 ospf_route_copy_nexthops(or, abr_or
->paths
);
391 if (or->cost
> cost
) {
392 if (IS_DEBUG_OSPF_EVENT
)
394 "%s: new route is better, overriding nexthops",
396 ospf_route_subst_nexthops(or, abr_or
->paths
);
399 if ((ospf
->abr_type
== OSPF_ABR_SHORTCUT
)
400 && !OSPF_IS_AREA_ID_BACKBONE(or->u
.std
.area_id
)) {
401 or->path_type
= OSPF_PATH_INTER_AREA
;
402 or->u
.std
.area_id
= area
->area_id
;
403 or->u
.std
.external_routing
= area
->external_routing
;
404 /* Note that we can do this only in Shortcut ABR mode,
405 because standard ABR must leave the route type and
413 static void ospf_update_router_route(struct ospf
*ospf
,
414 struct route_table
*rtrs
,
415 struct summary_lsa
*lsa
,
416 struct prefix_ipv4
*p
,
417 struct ospf_area
*area
)
419 struct ospf_route
* or, *abr_or
, *new_or
;
420 struct prefix_ipv4 abr
;
423 abr
.family
= AF_INET
;
424 abr
.prefix
= lsa
->header
.adv_router
;
425 abr
.prefixlen
= IPV4_MAX_BITLEN
;
426 apply_mask_ipv4(&abr
);
428 abr_or
= ospf_find_abr_route(rtrs
, &abr
, area
);
430 if (abr_or
== NULL
) {
431 if (IS_DEBUG_OSPF_EVENT
)
432 zlog_debug("%s: can't find a route to the ABR",
437 cost
= abr_or
->cost
+ GET_METRIC(lsa
->metric
);
439 /* First try to find a backbone path,
440 because standard ABR can update only BB-associated paths */
442 if ((ospf
->backbone
== NULL
) && (ospf
->abr_type
!= OSPF_ABR_SHORTCUT
))
443 return; /* no BB area, not Shortcut ABR, exiting */
445 /* find the backbone route, if possible */
446 if ((ospf
->backbone
== NULL
)
447 || !(or = ospf_find_asbr_route_through_area(rtrs
, p
,
449 if (ospf
->abr_type
!= OSPF_ABR_SHORTCUT
)
451 /* route to ASBR through the BB not found
452 the router is not Shortcut ABR, exiting */
456 /* We're a Shortcut ABR*/
458 /* Let it either add a new router or update the route
459 through the same (non-BB) area. */
461 new_or
= ospf_route_new();
462 new_or
->type
= OSPF_DESTINATION_ROUTER
;
463 new_or
->id
= lsa
->header
.id
;
464 new_or
->mask
= lsa
->mask
;
465 new_or
->u
.std
.options
= lsa
->header
.options
;
466 new_or
->u
.std
.origin
= (struct lsa_header
*)lsa
;
468 new_or
->u
.std
.area_id
= area
->area_id
;
469 new_or
->u
.std
.external_routing
= area
->external_routing
;
470 new_or
->path_type
= OSPF_PATH_INTER_AREA
;
471 new_or
->u
.std
.flags
= ROUTER_LSA_EXTERNAL
;
472 ospf_ia_router_route(ospf
, rtrs
, p
, new_or
, abr_or
);
478 /* At this point the "or" is always bb-associated */
480 if (!(or->u
.std
.flags
& ROUTER_LSA_EXTERNAL
)) {
481 if (IS_DEBUG_OSPF_EVENT
)
482 zlog_debug("%s: the remote router is not an ASBR",
487 if (or->path_type
!= OSPF_PATH_INTRA_AREA
&&
488 or->path_type
!= OSPF_PATH_INTER_AREA
)
494 else if (or->cost
== cost
)
495 ospf_route_copy_nexthops(or, abr_or
->paths
);
497 else if (or->cost
> cost
) {
498 ospf_route_subst_nexthops(or, abr_or
->paths
);
501 /* Even if the ABR runs in Shortcut mode, we can't change
502 the path type and area, because the "or" is always
504 at this point and even Shortcut ABR can't change these
509 static int process_transit_summary_lsa(struct ospf_area
*area
,
510 struct route_table
*rt
,
511 struct route_table
*rtrs
,
512 struct ospf_lsa
*lsa
)
514 struct ospf
*ospf
= area
->ospf
;
515 struct summary_lsa
*sl
;
516 struct prefix_ipv4 p
;
522 sl
= (struct summary_lsa
*)lsa
->data
;
524 if (IS_DEBUG_OSPF_EVENT
)
525 zlog_debug("%s: LS ID: %pI4", __func__
, &lsa
->data
->id
);
526 metric
= GET_METRIC(sl
->metric
);
528 if (metric
== OSPF_LS_INFINITY
) {
529 if (IS_DEBUG_OSPF_EVENT
)
530 zlog_debug("%s: metric is infinity, skip", __func__
);
534 if (IS_LSA_MAXAGE(lsa
)) {
535 if (IS_DEBUG_OSPF_EVENT
)
536 zlog_debug("%s: This LSA is too old", __func__
);
540 if (ospf_lsa_is_self_originated(area
->ospf
, lsa
)) {
541 if (IS_DEBUG_OSPF_EVENT
)
542 zlog_debug("%s: This LSA is mine, skip", __func__
);
547 p
.prefix
= sl
->header
.id
;
549 if (sl
->header
.type
== OSPF_SUMMARY_LSA
)
550 p
.prefixlen
= ip_masklen(sl
->mask
);
552 p
.prefixlen
= IPV4_MAX_BITLEN
;
556 if (sl
->header
.type
== OSPF_SUMMARY_LSA
)
557 ospf_update_network_route(ospf
, rt
, rtrs
, sl
, &p
, area
);
559 ospf_update_router_route(ospf
, rtrs
, sl
, &p
, area
);
564 static void ospf_examine_transit_summaries(struct ospf_area
*area
,
565 struct route_table
*lsdb_rt
,
566 struct route_table
*rt
,
567 struct route_table
*rtrs
)
569 struct ospf_lsa
*lsa
;
570 struct route_node
*rn
;
572 LSDB_LOOP (lsdb_rt
, rn
, lsa
)
573 process_transit_summary_lsa(area
, rt
, rtrs
, lsa
);
576 void ospf_ia_routing(struct ospf
*ospf
, struct route_table
*rt
,
577 struct route_table
*rtrs
)
579 struct listnode
*node
;
580 struct ospf_area
*area
;
582 if (IS_DEBUG_OSPF_EVENT
)
583 zlog_debug("%s:start", __func__
);
585 if (IS_OSPF_ABR(ospf
)) {
586 switch (ospf
->abr_type
) {
588 if (IS_DEBUG_OSPF_EVENT
)
589 zlog_debug("%s:Standard ABR", __func__
);
591 if ((area
= ospf
->backbone
)) {
592 if (IS_DEBUG_OSPF_EVENT
) {
594 "%s:backbone area found, examining summaries",
598 OSPF_EXAMINE_SUMMARIES_ALL(area
, rt
, rtrs
);
600 for (ALL_LIST_ELEMENTS_RO(ospf
->areas
, node
,
602 if (area
!= ospf
->backbone
)
603 if (ospf_area_is_transit(area
))
604 OSPF_EXAMINE_TRANSIT_SUMMARIES_ALL(
606 } else if (IS_DEBUG_OSPF_EVENT
)
607 zlog_debug("%s:backbone area NOT found",
612 if (IS_DEBUG_OSPF_EVENT
)
613 zlog_debug("%s:Alternative Cisco/IBM ABR",
615 area
= ospf
->backbone
; /* Find the BB */
617 /* If we have an active BB connection */
618 if (area
&& ospf_act_bb_connection(ospf
)) {
619 if (IS_DEBUG_OSPF_EVENT
) {
621 "%s: backbone area found, examining BB summaries",
625 OSPF_EXAMINE_SUMMARIES_ALL(area
, rt
, rtrs
);
627 for (ALL_LIST_ELEMENTS_RO(ospf
->areas
, node
,
629 if (area
!= ospf
->backbone
)
630 if (ospf_area_is_transit(area
))
631 OSPF_EXAMINE_TRANSIT_SUMMARIES_ALL(
633 } else { /* No active BB connection--consider all areas
635 if (IS_DEBUG_OSPF_EVENT
)
637 "%s: Active BB connection not found",
639 for (ALL_LIST_ELEMENTS_RO(ospf
->areas
, node
,
641 OSPF_EXAMINE_SUMMARIES_ALL(area
, rt
,
645 case OSPF_ABR_SHORTCUT
:
646 if (IS_DEBUG_OSPF_EVENT
)
647 zlog_debug("%s:Alternative Shortcut", __func__
);
648 area
= ospf
->backbone
; /* Find the BB */
650 /* If we have an active BB connection */
651 if (area
&& ospf_act_bb_connection(ospf
)) {
652 if (IS_DEBUG_OSPF_EVENT
) {
654 "%s: backbone area found, examining BB summaries",
657 OSPF_EXAMINE_SUMMARIES_ALL(area
, rt
, rtrs
);
660 for (ALL_LIST_ELEMENTS_RO(ospf
->areas
, node
, area
))
661 if (area
!= ospf
->backbone
)
662 if (ospf_area_is_transit(area
)
663 || ((area
->shortcut_configured
664 != OSPF_SHORTCUT_DISABLE
)
665 && ((ospf
->backbone
== NULL
)
666 || ((area
->shortcut_configured
667 == OSPF_SHORTCUT_ENABLE
)
668 && area
->shortcut_capability
))))
669 OSPF_EXAMINE_TRANSIT_SUMMARIES_ALL(
676 if (IS_DEBUG_OSPF_EVENT
)
677 zlog_debug("%s:not ABR, considering all areas",
680 for (ALL_LIST_ELEMENTS_RO(ospf
->areas
, node
, area
))
681 OSPF_EXAMINE_SUMMARIES_ALL(area
, rt
, rtrs
);