]>
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
)
79 "ospf_ia_network_route(): processing summary route to %pFX",
82 /* Find a route to the same dest */
83 if ((rn1
= route_node_lookup(rt
, (struct prefix
*)p
))) {
86 route_unlock_node(rn1
);
88 if ((or = rn1
->info
)) {
89 if (IS_DEBUG_OSPF_EVENT
)
91 "ospf_ia_network_route(): Found a route to the same network");
92 /* Check the existing route. */
93 if ((res
= ospf_route_cmp(ospf
, new_or
, or)) < 0) {
94 /* New route is better, so replace old one. */
95 ospf_route_subst(rn1
, new_or
, abr_or
);
96 } else if (res
== 0) {
97 /* New and old route are equal, so next hops can
100 ospf_route_copy_nexthops(or, abr_or
->paths
);
101 route_unlock_node(rn1
);
103 /* new route can be deleted, because existing
104 * route has been updated. */
105 ospf_route_free(new_or
);
107 /* New route is worse, so free it. */
108 ospf_route_free(new_or
);
113 else { /* no route */
114 if (IS_DEBUG_OSPF_EVENT
)
116 "ospf_ia_network_route(): add new route to %pFX",
118 ospf_route_add(rt
, p
, new_or
, abr_or
);
122 static void ospf_ia_router_route(struct ospf
*ospf
, struct route_table
*rtrs
,
123 struct prefix_ipv4
*p
,
124 struct ospf_route
*new_or
,
125 struct ospf_route
*abr_or
)
127 struct ospf_route
* or = NULL
;
128 struct route_node
*rn
;
131 if (IS_DEBUG_OSPF_EVENT
)
132 zlog_debug("ospf_ia_router_route(): considering %pFX", p
);
134 /* Find a route to the same dest */
135 rn
= route_node_get(rtrs
, (struct prefix
*)p
);
137 if (rn
->info
== NULL
)
138 /* This is a new route */
139 rn
->info
= list_new();
141 struct ospf_area
*or_area
;
142 or_area
= ospf_area_lookup_by_area_id(ospf
,
143 new_or
->u
.std
.area_id
);
145 /* This is an additional route */
146 route_unlock_node(rn
);
147 or = ospf_find_asbr_route_through_area(rtrs
, p
, or_area
);
151 if (IS_DEBUG_OSPF_EVENT
)
153 "ospf_ia_router_route(): a route to the same ABR through the same area exists");
154 /* New route is better */
155 if ((ret
= ospf_route_cmp(ospf
, new_or
, or)) < 0) {
156 listnode_delete(rn
->info
, or);
160 /* Routes are the same */
162 if (IS_DEBUG_OSPF_EVENT
)
164 "ospf_ia_router_route(): merging the new route");
166 ospf_route_copy_nexthops(or, abr_or
->paths
);
167 ospf_route_free(new_or
);
170 /* New route is worse */
172 if (IS_DEBUG_OSPF_EVENT
)
174 "ospf_ia_router_route(): skipping the new route");
175 ospf_route_free(new_or
);
180 ospf_route_copy_nexthops(new_or
, abr_or
->paths
);
182 if (IS_DEBUG_OSPF_EVENT
)
183 zlog_debug("ospf_ia_router_route(): adding the new route");
185 listnode_add(rn
->info
, new_or
);
189 static int process_summary_lsa(struct ospf_area
*area
, struct route_table
*rt
,
190 struct route_table
*rtrs
, struct ospf_lsa
*lsa
)
192 struct ospf
*ospf
= area
->ospf
;
193 struct ospf_area_range
*range
;
194 struct ospf_route
*abr_or
, *new_or
;
195 struct summary_lsa
*sl
;
196 struct prefix_ipv4 p
, abr
;
202 sl
= (struct summary_lsa
*)lsa
->data
;
204 if (IS_DEBUG_OSPF_EVENT
)
205 zlog_debug("process_summary_lsa(): LS ID: %pI4",
208 metric
= GET_METRIC(sl
->metric
);
210 if (metric
== OSPF_LS_INFINITY
)
213 if (IS_LSA_MAXAGE(lsa
))
216 if (ospf_lsa_is_self_originated(area
->ospf
, lsa
))
220 p
.prefix
= sl
->header
.id
;
222 if (sl
->header
.type
== OSPF_SUMMARY_LSA
)
223 p
.prefixlen
= ip_masklen(sl
->mask
);
225 p
.prefixlen
= IPV4_MAX_BITLEN
;
229 if (sl
->header
.type
== OSPF_SUMMARY_LSA
230 && (range
= ospf_area_range_match_any(ospf
, &p
))
231 && ospf_area_range_active(range
))
234 /* XXX: This check seems dubious to me. If an ABR has already decided
235 * to consider summaries received in this area, then why would one wish
236 * to exclude default?
238 if (IS_OSPF_ABR(ospf
) && ospf
->abr_type
!= OSPF_ABR_STAND
239 && area
->external_routing
!= OSPF_AREA_DEFAULT
240 && p
.prefix
.s_addr
== OSPF_DEFAULT_DESTINATION
&& p
.prefixlen
== 0)
241 return 0; /* Ignore summary default from a stub area */
243 abr
.family
= AF_INET
;
244 abr
.prefix
= sl
->header
.adv_router
;
245 abr
.prefixlen
= IPV4_MAX_BITLEN
;
246 apply_mask_ipv4(&abr
);
248 abr_or
= ospf_find_abr_route(rtrs
, &abr
, area
);
253 new_or
= ospf_route_new();
254 new_or
->type
= OSPF_DESTINATION_NETWORK
;
255 new_or
->id
= sl
->header
.id
;
256 new_or
->mask
= sl
->mask
;
257 new_or
->u
.std
.options
= sl
->header
.options
;
258 new_or
->u
.std
.origin
= (struct lsa_header
*)sl
;
259 new_or
->cost
= abr_or
->cost
+ metric
;
260 new_or
->u
.std
.area_id
= area
->area_id
;
261 new_or
->u
.std
.external_routing
= area
->external_routing
;
262 new_or
->path_type
= OSPF_PATH_INTER_AREA
;
264 if (sl
->header
.type
== OSPF_SUMMARY_LSA
)
265 ospf_ia_network_route(ospf
, rt
, &p
, new_or
, abr_or
);
267 new_or
->type
= OSPF_DESTINATION_ROUTER
;
268 new_or
->u
.std
.flags
= ROUTER_LSA_EXTERNAL
;
269 ospf_ia_router_route(ospf
, rtrs
, &p
, new_or
, abr_or
);
275 static void ospf_examine_summaries(struct ospf_area
*area
,
276 struct route_table
*lsdb_rt
,
277 struct route_table
*rt
,
278 struct route_table
*rtrs
)
280 struct ospf_lsa
*lsa
;
281 struct route_node
*rn
;
283 LSDB_LOOP (lsdb_rt
, rn
, lsa
)
284 process_summary_lsa(area
, rt
, rtrs
, lsa
);
287 int ospf_area_is_transit(struct ospf_area
*area
)
289 return (area
->transit
== OSPF_TRANSIT_TRUE
)
290 || ospf_full_virtual_nbrs(
291 area
); /* Cisco forgets to set the V-bit :( */
294 static void ospf_update_network_route(struct ospf
*ospf
, struct route_table
*rt
,
295 struct route_table
*rtrs
,
296 struct summary_lsa
*lsa
,
297 struct prefix_ipv4
*p
,
298 struct ospf_area
*area
)
300 struct route_node
*rn
;
301 struct ospf_route
* or, *abr_or
, *new_or
;
302 struct prefix_ipv4 abr
;
305 abr
.family
= AF_INET
;
306 abr
.prefix
= lsa
->header
.adv_router
;
307 abr
.prefixlen
= IPV4_MAX_BITLEN
;
308 apply_mask_ipv4(&abr
);
310 abr_or
= ospf_find_abr_route(rtrs
, &abr
, area
);
312 if (abr_or
== NULL
) {
313 if (IS_DEBUG_OSPF_EVENT
)
315 "ospf_update_network_route(): can't find a route to the ABR");
319 cost
= abr_or
->cost
+ GET_METRIC(lsa
->metric
);
321 rn
= route_node_lookup(rt
, (struct prefix
*)p
);
324 if (ospf
->abr_type
!= OSPF_ABR_SHORTCUT
)
325 return; /* Standard ABR can update only already
328 if (IS_DEBUG_OSPF_EVENT
)
330 "ospf_update_network_route(): Allowing Shortcut ABR to add new route");
331 new_or
= ospf_route_new();
332 new_or
->type
= OSPF_DESTINATION_NETWORK
;
333 new_or
->id
= lsa
->header
.id
;
334 new_or
->mask
= lsa
->mask
;
335 new_or
->u
.std
.options
= lsa
->header
.options
;
336 new_or
->u
.std
.origin
= (struct lsa_header
*)lsa
;
338 new_or
->u
.std
.area_id
= area
->area_id
;
339 new_or
->u
.std
.external_routing
= area
->external_routing
;
340 new_or
->path_type
= OSPF_PATH_INTER_AREA
;
341 ospf_route_add(rt
, p
, new_or
, abr_or
);
345 route_unlock_node(rn
);
346 if (rn
->info
== NULL
)
352 if (or->path_type
!= OSPF_PATH_INTRA_AREA
&&
353 or->path_type
!= OSPF_PATH_INTER_AREA
) {
354 if (IS_DEBUG_OSPF_EVENT
)
356 "ospf_update_network_route(): ERR: path type is wrong");
360 if (ospf
->abr_type
== OSPF_ABR_SHORTCUT
) {
362 or->path_type
== OSPF_PATH_INTRA_AREA
363 && !OSPF_IS_AREA_ID_BACKBONE(
364 or->u
.std
.area_id
)) {
365 if (IS_DEBUG_OSPF_EVENT
)
367 "ospf_update_network_route(): Shortcut: this intra-area path is not backbone");
370 } else /* Not Shortcut ABR */
372 if (!OSPF_IS_AREA_ID_BACKBONE(or->u
.std
.area_id
)) {
373 if (IS_DEBUG_OSPF_EVENT
)
375 "ospf_update_network_route(): route is not BB-associated");
376 return; /* We can update only BB routes */
380 if (or->cost
< cost
) {
381 if (IS_DEBUG_OSPF_EVENT
)
383 "ospf_update_network_route(): new route is worse");
387 if (or->cost
== cost
) {
388 if (IS_DEBUG_OSPF_EVENT
)
390 "ospf_update_network_route(): new route is same distance, adding nexthops");
391 ospf_route_copy_nexthops(or, abr_or
->paths
);
394 if (or->cost
> cost
) {
395 if (IS_DEBUG_OSPF_EVENT
)
397 "ospf_update_network_route(): new route is better, overriding nexthops");
398 ospf_route_subst_nexthops(or, abr_or
->paths
);
401 if ((ospf
->abr_type
== OSPF_ABR_SHORTCUT
)
402 && !OSPF_IS_AREA_ID_BACKBONE(or->u
.std
.area_id
)) {
403 or->path_type
= OSPF_PATH_INTER_AREA
;
404 or->u
.std
.area_id
= area
->area_id
;
405 or->u
.std
.external_routing
= area
->external_routing
;
406 /* Note that we can do this only in Shortcut ABR mode,
407 because standard ABR must leave the route type and
415 static void ospf_update_router_route(struct ospf
*ospf
,
416 struct route_table
*rtrs
,
417 struct summary_lsa
*lsa
,
418 struct prefix_ipv4
*p
,
419 struct ospf_area
*area
)
421 struct ospf_route
* or, *abr_or
, *new_or
;
422 struct prefix_ipv4 abr
;
425 abr
.family
= AF_INET
;
426 abr
.prefix
= lsa
->header
.adv_router
;
427 abr
.prefixlen
= IPV4_MAX_BITLEN
;
428 apply_mask_ipv4(&abr
);
430 abr_or
= ospf_find_abr_route(rtrs
, &abr
, area
);
432 if (abr_or
== NULL
) {
433 if (IS_DEBUG_OSPF_EVENT
)
435 "ospf_update_router_route(): can't find a route to the ABR");
439 cost
= abr_or
->cost
+ GET_METRIC(lsa
->metric
);
441 /* First try to find a backbone path,
442 because standard ABR can update only BB-associated paths */
444 if ((ospf
->backbone
== NULL
) && (ospf
->abr_type
!= OSPF_ABR_SHORTCUT
))
445 return; /* no BB area, not Shortcut ABR, exiting */
447 /* find the backbone route, if possible */
448 if ((ospf
->backbone
== NULL
)
449 || !(or = ospf_find_asbr_route_through_area(rtrs
, p
,
451 if (ospf
->abr_type
!= OSPF_ABR_SHORTCUT
)
453 /* route to ASBR through the BB not found
454 the router is not Shortcut ABR, exiting */
458 /* We're a Shortcut ABR*/
460 /* Let it either add a new router or update the route
461 through the same (non-BB) area. */
463 new_or
= ospf_route_new();
464 new_or
->type
= OSPF_DESTINATION_ROUTER
;
465 new_or
->id
= lsa
->header
.id
;
466 new_or
->mask
= lsa
->mask
;
467 new_or
->u
.std
.options
= lsa
->header
.options
;
468 new_or
->u
.std
.origin
= (struct lsa_header
*)lsa
;
470 new_or
->u
.std
.area_id
= area
->area_id
;
471 new_or
->u
.std
.external_routing
= area
->external_routing
;
472 new_or
->path_type
= OSPF_PATH_INTER_AREA
;
473 new_or
->u
.std
.flags
= ROUTER_LSA_EXTERNAL
;
474 ospf_ia_router_route(ospf
, rtrs
, p
, new_or
, abr_or
);
480 /* At this point the "or" is always bb-associated */
482 if (!(or->u
.std
.flags
& ROUTER_LSA_EXTERNAL
)) {
483 if (IS_DEBUG_OSPF_EVENT
)
485 "ospf_upd_router_route(): the remote router is not an ASBR");
489 if (or->path_type
!= OSPF_PATH_INTRA_AREA
&&
490 or->path_type
!= OSPF_PATH_INTER_AREA
)
496 else if (or->cost
== cost
)
497 ospf_route_copy_nexthops(or, abr_or
->paths
);
499 else if (or->cost
> cost
) {
500 ospf_route_subst_nexthops(or, abr_or
->paths
);
503 /* Even if the ABR runs in Shortcut mode, we can't change
504 the path type and area, because the "or" is always
506 at this point and even Shortcut ABR can't change these
511 static int process_transit_summary_lsa(struct ospf_area
*area
,
512 struct route_table
*rt
,
513 struct route_table
*rtrs
,
514 struct ospf_lsa
*lsa
)
516 struct ospf
*ospf
= area
->ospf
;
517 struct summary_lsa
*sl
;
518 struct prefix_ipv4 p
;
524 sl
= (struct summary_lsa
*)lsa
->data
;
526 if (IS_DEBUG_OSPF_EVENT
)
527 zlog_debug("process_transit_summaries(): LS ID: %pI4",
529 metric
= GET_METRIC(sl
->metric
);
531 if (metric
== OSPF_LS_INFINITY
) {
532 if (IS_DEBUG_OSPF_EVENT
)
534 "process_transit_summaries(): metric is infinity, skip");
538 if (IS_LSA_MAXAGE(lsa
)) {
539 if (IS_DEBUG_OSPF_EVENT
)
541 "process_transit_summaries(): This LSA is too old");
545 if (ospf_lsa_is_self_originated(area
->ospf
, lsa
)) {
546 if (IS_DEBUG_OSPF_EVENT
)
548 "process_transit_summaries(): This LSA is mine, skip");
553 p
.prefix
= sl
->header
.id
;
555 if (sl
->header
.type
== OSPF_SUMMARY_LSA
)
556 p
.prefixlen
= ip_masklen(sl
->mask
);
558 p
.prefixlen
= IPV4_MAX_BITLEN
;
562 if (sl
->header
.type
== OSPF_SUMMARY_LSA
)
563 ospf_update_network_route(ospf
, rt
, rtrs
, sl
, &p
, area
);
565 ospf_update_router_route(ospf
, rtrs
, sl
, &p
, area
);
570 static void ospf_examine_transit_summaries(struct ospf_area
*area
,
571 struct route_table
*lsdb_rt
,
572 struct route_table
*rt
,
573 struct route_table
*rtrs
)
575 struct ospf_lsa
*lsa
;
576 struct route_node
*rn
;
578 LSDB_LOOP (lsdb_rt
, rn
, lsa
)
579 process_transit_summary_lsa(area
, rt
, rtrs
, lsa
);
582 void ospf_ia_routing(struct ospf
*ospf
, struct route_table
*rt
,
583 struct route_table
*rtrs
)
585 struct listnode
*node
;
586 struct ospf_area
*area
;
588 if (IS_DEBUG_OSPF_EVENT
)
589 zlog_debug("ospf_ia_routing():start");
591 if (IS_OSPF_ABR(ospf
)) {
592 switch (ospf
->abr_type
) {
594 if (IS_DEBUG_OSPF_EVENT
)
595 zlog_debug("ospf_ia_routing():Standard ABR");
597 if ((area
= ospf
->backbone
)) {
598 if (IS_DEBUG_OSPF_EVENT
) {
600 "ospf_ia_routing():backbone area found");
602 "ospf_ia_routing():examining summaries");
605 OSPF_EXAMINE_SUMMARIES_ALL(area
, rt
, rtrs
);
607 for (ALL_LIST_ELEMENTS_RO(ospf
->areas
, node
,
609 if (area
!= ospf
->backbone
)
610 if (ospf_area_is_transit(area
))
611 OSPF_EXAMINE_TRANSIT_SUMMARIES_ALL(
613 } else if (IS_DEBUG_OSPF_EVENT
)
615 "ospf_ia_routing():backbone area NOT found");
619 if (IS_DEBUG_OSPF_EVENT
)
621 "ospf_ia_routing():Alternative Cisco/IBM ABR");
622 area
= ospf
->backbone
; /* Find the BB */
624 /* If we have an active BB connection */
625 if (area
&& ospf_act_bb_connection(ospf
)) {
626 if (IS_DEBUG_OSPF_EVENT
) {
628 "ospf_ia_routing(): backbone area found");
630 "ospf_ia_routing(): examining BB summaries");
633 OSPF_EXAMINE_SUMMARIES_ALL(area
, rt
, rtrs
);
635 for (ALL_LIST_ELEMENTS_RO(ospf
->areas
, node
,
637 if (area
!= ospf
->backbone
)
638 if (ospf_area_is_transit(area
))
639 OSPF_EXAMINE_TRANSIT_SUMMARIES_ALL(
641 } else { /* No active BB connection--consider all areas
643 if (IS_DEBUG_OSPF_EVENT
)
645 "ospf_ia_routing(): Active BB connection not found");
646 for (ALL_LIST_ELEMENTS_RO(ospf
->areas
, node
,
648 OSPF_EXAMINE_SUMMARIES_ALL(area
, rt
,
652 case OSPF_ABR_SHORTCUT
:
653 if (IS_DEBUG_OSPF_EVENT
)
655 "ospf_ia_routing():Alternative Shortcut");
656 area
= ospf
->backbone
; /* Find the BB */
658 /* If we have an active BB connection */
659 if (area
&& ospf_act_bb_connection(ospf
)) {
660 if (IS_DEBUG_OSPF_EVENT
) {
662 "ospf_ia_routing(): backbone area found");
664 "ospf_ia_routing(): examining BB summaries");
666 OSPF_EXAMINE_SUMMARIES_ALL(area
, rt
, rtrs
);
669 for (ALL_LIST_ELEMENTS_RO(ospf
->areas
, node
, area
))
670 if (area
!= ospf
->backbone
)
671 if (ospf_area_is_transit(area
)
672 || ((area
->shortcut_configured
673 != OSPF_SHORTCUT_DISABLE
)
674 && ((ospf
->backbone
== NULL
)
675 || ((area
->shortcut_configured
676 == OSPF_SHORTCUT_ENABLE
)
677 && area
->shortcut_capability
))))
678 OSPF_EXAMINE_TRANSIT_SUMMARIES_ALL(
685 if (IS_DEBUG_OSPF_EVENT
)
687 "ospf_ia_routing():not ABR, considering all areas");
689 for (ALL_LIST_ELEMENTS_RO(ospf
->areas
, node
, area
))
690 OSPF_EXAMINE_SUMMARIES_ALL(area
, rt
, rtrs
);