]>
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 %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
))) {
86 route_unlock_node(rn1
);
88 if ((or = rn1
->info
)) {
89 if (IS_DEBUG_OSPF_EVENT
)
91 "ospf_ia_network_route(): "
92 "Found a route to the same network");
93 /* Check the existing route. */
94 if ((res
= ospf_route_cmp(ospf
, new_or
, or)) < 0) {
95 /* New route is better, so replace old one. */
96 ospf_route_subst(rn1
, new_or
, abr_or
);
97 } else if (res
== 0) {
98 /* New and old route are equal, so next hops can
100 route_lock_node(rn1
);
101 ospf_route_copy_nexthops(or, abr_or
->paths
);
102 route_unlock_node(rn1
);
104 /* new route can be deleted, because existing
105 * route has been updated. */
106 ospf_route_free(new_or
);
108 /* New route is worse, so free it. */
109 ospf_route_free(new_or
);
114 else { /* no route */
115 if (IS_DEBUG_OSPF_EVENT
)
117 "ospf_ia_network_route(): add new route to %s/%d",
118 inet_ntoa(p
->prefix
), p
->prefixlen
);
119 ospf_route_add(rt
, p
, new_or
, abr_or
);
123 static void ospf_ia_router_route(struct ospf
*ospf
, struct route_table
*rtrs
,
124 struct prefix_ipv4
*p
,
125 struct ospf_route
*new_or
,
126 struct ospf_route
*abr_or
)
128 struct ospf_route
* or = NULL
;
129 struct route_node
*rn
;
132 if (IS_DEBUG_OSPF_EVENT
)
133 zlog_debug("ospf_ia_router_route(): considering %s/%d",
134 inet_ntoa(p
->prefix
), p
->prefixlen
);
135 /* Find a route to the same dest */
136 rn
= route_node_get(rtrs
, (struct prefix
*)p
);
138 if (rn
->info
== NULL
)
139 /* This is a new route */
140 rn
->info
= list_new();
142 struct ospf_area
*or_area
;
143 or_area
= ospf_area_lookup_by_area_id(ospf
,
144 new_or
->u
.std
.area_id
);
146 /* This is an additional route */
147 route_unlock_node(rn
);
148 or = ospf_find_asbr_route_through_area(rtrs
, p
, or_area
);
152 if (IS_DEBUG_OSPF_EVENT
)
154 "ospf_ia_router_route(): "
155 "a route to the same ABR through the same area exists");
156 /* New route is better */
157 if ((ret
= ospf_route_cmp(ospf
, new_or
, or)) < 0) {
158 listnode_delete(rn
->info
, or);
162 /* Routes are the same */
164 if (IS_DEBUG_OSPF_EVENT
)
166 "ospf_ia_router_route(): merging the new route");
168 ospf_route_copy_nexthops(or, abr_or
->paths
);
169 ospf_route_free(new_or
);
172 /* New route is worse */
174 if (IS_DEBUG_OSPF_EVENT
)
176 "ospf_ia_router_route(): skipping the new route");
177 ospf_route_free(new_or
);
182 ospf_route_copy_nexthops(new_or
, abr_or
->paths
);
184 if (IS_DEBUG_OSPF_EVENT
)
185 zlog_debug("ospf_ia_router_route(): adding the new route");
187 listnode_add(rn
->info
, new_or
);
191 static int process_summary_lsa(struct ospf_area
*area
, struct route_table
*rt
,
192 struct route_table
*rtrs
, struct ospf_lsa
*lsa
)
194 struct ospf
*ospf
= area
->ospf
;
195 struct ospf_area_range
*range
;
196 struct ospf_route
*abr_or
, *new_or
;
197 struct summary_lsa
*sl
;
198 struct prefix_ipv4 p
, abr
;
204 sl
= (struct summary_lsa
*)lsa
->data
;
206 if (IS_DEBUG_OSPF_EVENT
)
207 zlog_debug("process_summary_lsa(): LS ID: %s",
208 inet_ntoa(sl
->header
.id
));
210 metric
= GET_METRIC(sl
->metric
);
212 if (metric
== OSPF_LS_INFINITY
)
215 if (IS_LSA_MAXAGE(lsa
))
218 if (ospf_lsa_is_self_originated(area
->ospf
, lsa
))
222 p
.prefix
= sl
->header
.id
;
224 if (sl
->header
.type
== OSPF_SUMMARY_LSA
)
225 p
.prefixlen
= ip_masklen(sl
->mask
);
227 p
.prefixlen
= IPV4_MAX_BITLEN
;
231 if (sl
->header
.type
== OSPF_SUMMARY_LSA
232 && (range
= ospf_area_range_match_any(ospf
, &p
))
233 && ospf_area_range_active(range
))
236 /* XXX: This check seems dubious to me. If an ABR has already decided
237 * to consider summaries received in this area, then why would one wish
238 * to exclude default?
240 if (IS_OSPF_ABR(ospf
) && ospf
->abr_type
!= OSPF_ABR_STAND
241 && area
->external_routing
!= OSPF_AREA_DEFAULT
242 && p
.prefix
.s_addr
== OSPF_DEFAULT_DESTINATION
&& p
.prefixlen
== 0)
243 return 0; /* Ignore summary default from a stub area */
245 abr
.family
= AF_INET
;
246 abr
.prefix
= sl
->header
.adv_router
;
247 abr
.prefixlen
= IPV4_MAX_BITLEN
;
248 apply_mask_ipv4(&abr
);
250 abr_or
= ospf_find_abr_route(rtrs
, &abr
, area
);
255 new_or
= ospf_route_new();
256 new_or
->type
= OSPF_DESTINATION_NETWORK
;
257 new_or
->id
= sl
->header
.id
;
258 new_or
->mask
= sl
->mask
;
259 new_or
->u
.std
.options
= sl
->header
.options
;
260 new_or
->u
.std
.origin
= (struct lsa_header
*)sl
;
261 new_or
->cost
= abr_or
->cost
+ metric
;
262 new_or
->u
.std
.area_id
= area
->area_id
;
263 new_or
->u
.std
.external_routing
= area
->external_routing
;
264 new_or
->path_type
= OSPF_PATH_INTER_AREA
;
266 if (sl
->header
.type
== OSPF_SUMMARY_LSA
)
267 ospf_ia_network_route(ospf
, rt
, &p
, new_or
, abr_or
);
269 new_or
->type
= OSPF_DESTINATION_ROUTER
;
270 new_or
->u
.std
.flags
= ROUTER_LSA_EXTERNAL
;
271 ospf_ia_router_route(ospf
, rtrs
, &p
, new_or
, abr_or
);
277 static void ospf_examine_summaries(struct ospf_area
*area
,
278 struct route_table
*lsdb_rt
,
279 struct route_table
*rt
,
280 struct route_table
*rtrs
)
282 struct ospf_lsa
*lsa
;
283 struct route_node
*rn
;
285 LSDB_LOOP (lsdb_rt
, rn
, lsa
)
286 process_summary_lsa(area
, rt
, rtrs
, lsa
);
289 int ospf_area_is_transit(struct ospf_area
*area
)
291 return (area
->transit
== OSPF_TRANSIT_TRUE
)
292 || ospf_full_virtual_nbrs(
293 area
); /* Cisco forgets to set the V-bit :( */
296 static void ospf_update_network_route(struct ospf
*ospf
, struct route_table
*rt
,
297 struct route_table
*rtrs
,
298 struct summary_lsa
*lsa
,
299 struct prefix_ipv4
*p
,
300 struct ospf_area
*area
)
302 struct route_node
*rn
;
303 struct ospf_route
* or, *abr_or
, *new_or
;
304 struct prefix_ipv4 abr
;
307 abr
.family
= AF_INET
;
308 abr
.prefix
= lsa
->header
.adv_router
;
309 abr
.prefixlen
= IPV4_MAX_BITLEN
;
310 apply_mask_ipv4(&abr
);
312 abr_or
= ospf_find_abr_route(rtrs
, &abr
, area
);
314 if (abr_or
== NULL
) {
315 if (IS_DEBUG_OSPF_EVENT
)
317 "ospf_update_network_route(): can't find a route to the ABR");
321 cost
= abr_or
->cost
+ GET_METRIC(lsa
->metric
);
323 rn
= route_node_lookup(rt
, (struct prefix
*)p
);
326 if (ospf
->abr_type
!= OSPF_ABR_SHORTCUT
)
327 return; /* Standard ABR can update only already
330 if (IS_DEBUG_OSPF_EVENT
)
332 "ospf_update_network_route(): "
333 "Allowing Shortcut ABR to add new route");
334 new_or
= ospf_route_new();
335 new_or
->type
= OSPF_DESTINATION_NETWORK
;
336 new_or
->id
= lsa
->header
.id
;
337 new_or
->mask
= lsa
->mask
;
338 new_or
->u
.std
.options
= lsa
->header
.options
;
339 new_or
->u
.std
.origin
= (struct lsa_header
*)lsa
;
341 new_or
->u
.std
.area_id
= area
->area_id
;
342 new_or
->u
.std
.external_routing
= area
->external_routing
;
343 new_or
->path_type
= OSPF_PATH_INTER_AREA
;
344 ospf_route_add(rt
, p
, new_or
, abr_or
);
348 route_unlock_node(rn
);
349 if (rn
->info
== NULL
)
355 if (or->path_type
!= OSPF_PATH_INTRA_AREA
&&
356 or->path_type
!= OSPF_PATH_INTER_AREA
) {
357 if (IS_DEBUG_OSPF_EVENT
)
359 "ospf_update_network_route(): ERR: path type is wrong");
363 if (ospf
->abr_type
== OSPF_ABR_SHORTCUT
) {
365 or->path_type
== OSPF_PATH_INTRA_AREA
366 && !OSPF_IS_AREA_ID_BACKBONE(
367 or->u
.std
.area_id
)) {
368 if (IS_DEBUG_OSPF_EVENT
)
370 "ospf_update_network_route(): Shortcut: "
371 "this intra-area path is not backbone");
374 } else /* Not Shortcut ABR */
376 if (!OSPF_IS_AREA_ID_BACKBONE(or->u
.std
.area_id
)) {
377 if (IS_DEBUG_OSPF_EVENT
)
379 "ospf_update_network_route(): "
380 "route is not BB-associated");
381 return; /* We can update only BB routes */
385 if (or->cost
< cost
) {
386 if (IS_DEBUG_OSPF_EVENT
)
388 "ospf_update_network_route(): new route is worse");
392 if (or->cost
== cost
) {
393 if (IS_DEBUG_OSPF_EVENT
)
395 "ospf_update_network_route(): "
396 "new route is same distance, adding nexthops");
397 ospf_route_copy_nexthops(or, abr_or
->paths
);
400 if (or->cost
> cost
) {
401 if (IS_DEBUG_OSPF_EVENT
)
403 "ospf_update_network_route(): "
404 "new route is better, overriding nexthops");
405 ospf_route_subst_nexthops(or, abr_or
->paths
);
408 if ((ospf
->abr_type
== OSPF_ABR_SHORTCUT
)
409 && !OSPF_IS_AREA_ID_BACKBONE(or->u
.std
.area_id
)) {
410 or->path_type
= OSPF_PATH_INTER_AREA
;
411 or->u
.std
.area_id
= area
->area_id
;
412 or->u
.std
.external_routing
= area
->external_routing
;
413 /* Note that we can do this only in Shortcut ABR mode,
414 because standard ABR must leave the route type and
422 static void ospf_update_router_route(struct ospf
*ospf
,
423 struct route_table
*rtrs
,
424 struct summary_lsa
*lsa
,
425 struct prefix_ipv4
*p
,
426 struct ospf_area
*area
)
428 struct ospf_route
* or, *abr_or
, *new_or
;
429 struct prefix_ipv4 abr
;
432 abr
.family
= AF_INET
;
433 abr
.prefix
= lsa
->header
.adv_router
;
434 abr
.prefixlen
= IPV4_MAX_BITLEN
;
435 apply_mask_ipv4(&abr
);
437 abr_or
= ospf_find_abr_route(rtrs
, &abr
, area
);
439 if (abr_or
== NULL
) {
440 if (IS_DEBUG_OSPF_EVENT
)
442 "ospf_update_router_route(): can't find a route to the ABR");
446 cost
= abr_or
->cost
+ GET_METRIC(lsa
->metric
);
448 /* First try to find a backbone path,
449 because standard ABR can update only BB-associated paths */
451 if ((ospf
->backbone
== NULL
) && (ospf
->abr_type
!= OSPF_ABR_SHORTCUT
))
452 return; /* no BB area, not Shortcut ABR, exiting */
454 /* find the backbone route, if possible */
455 if ((ospf
->backbone
== NULL
)
456 || !(or = ospf_find_asbr_route_through_area(rtrs
, p
,
458 if (ospf
->abr_type
!= OSPF_ABR_SHORTCUT
)
460 /* route to ASBR through the BB not found
461 the router is not Shortcut ABR, exiting */
465 /* We're a Shortcut ABR*/
467 /* Let it either add a new router or update the route
468 through the same (non-BB) area. */
470 new_or
= ospf_route_new();
471 new_or
->type
= OSPF_DESTINATION_ROUTER
;
472 new_or
->id
= lsa
->header
.id
;
473 new_or
->mask
= lsa
->mask
;
474 new_or
->u
.std
.options
= lsa
->header
.options
;
475 new_or
->u
.std
.origin
= (struct lsa_header
*)lsa
;
477 new_or
->u
.std
.area_id
= area
->area_id
;
478 new_or
->u
.std
.external_routing
= area
->external_routing
;
479 new_or
->path_type
= OSPF_PATH_INTER_AREA
;
480 new_or
->u
.std
.flags
= ROUTER_LSA_EXTERNAL
;
481 ospf_ia_router_route(ospf
, rtrs
, p
, new_or
, abr_or
);
487 /* At this point the "or" is always bb-associated */
489 if (!(or->u
.std
.flags
& ROUTER_LSA_EXTERNAL
)) {
490 if (IS_DEBUG_OSPF_EVENT
)
492 "ospf_upd_router_route(): the remote router is not an ASBR");
496 if (or->path_type
!= OSPF_PATH_INTRA_AREA
&&
497 or->path_type
!= OSPF_PATH_INTER_AREA
)
503 else if (or->cost
== cost
)
504 ospf_route_copy_nexthops(or, abr_or
->paths
);
506 else if (or->cost
> cost
) {
507 ospf_route_subst_nexthops(or, abr_or
->paths
);
510 /* Even if the ABR runs in Shortcut mode, we can't change
511 the path type and area, because the "or" is always
513 at this point and even Shortcut ABR can't change these
518 static int process_transit_summary_lsa(struct ospf_area
*area
,
519 struct route_table
*rt
,
520 struct route_table
*rtrs
,
521 struct ospf_lsa
*lsa
)
523 struct ospf
*ospf
= area
->ospf
;
524 struct summary_lsa
*sl
;
525 struct prefix_ipv4 p
;
531 sl
= (struct summary_lsa
*)lsa
->data
;
533 if (IS_DEBUG_OSPF_EVENT
)
534 zlog_debug("process_transit_summaries(): LS ID: %s",
535 inet_ntoa(lsa
->data
->id
));
536 metric
= GET_METRIC(sl
->metric
);
538 if (metric
== OSPF_LS_INFINITY
) {
539 if (IS_DEBUG_OSPF_EVENT
)
541 "process_transit_summaries(): metric is infinity, skip");
545 if (IS_LSA_MAXAGE(lsa
)) {
546 if (IS_DEBUG_OSPF_EVENT
)
548 "process_transit_summaries(): This LSA is too old");
552 if (ospf_lsa_is_self_originated(area
->ospf
, lsa
)) {
553 if (IS_DEBUG_OSPF_EVENT
)
555 "process_transit_summaries(): This LSA is mine, skip");
560 p
.prefix
= sl
->header
.id
;
562 if (sl
->header
.type
== OSPF_SUMMARY_LSA
)
563 p
.prefixlen
= ip_masklen(sl
->mask
);
565 p
.prefixlen
= IPV4_MAX_BITLEN
;
569 if (sl
->header
.type
== OSPF_SUMMARY_LSA
)
570 ospf_update_network_route(ospf
, rt
, rtrs
, sl
, &p
, area
);
572 ospf_update_router_route(ospf
, rtrs
, sl
, &p
, area
);
577 static void ospf_examine_transit_summaries(struct ospf_area
*area
,
578 struct route_table
*lsdb_rt
,
579 struct route_table
*rt
,
580 struct route_table
*rtrs
)
582 struct ospf_lsa
*lsa
;
583 struct route_node
*rn
;
585 LSDB_LOOP (lsdb_rt
, rn
, lsa
)
586 process_transit_summary_lsa(area
, rt
, rtrs
, lsa
);
589 void ospf_ia_routing(struct ospf
*ospf
, struct route_table
*rt
,
590 struct route_table
*rtrs
)
592 struct ospf_area
*area
;
594 if (IS_DEBUG_OSPF_EVENT
)
595 zlog_debug("ospf_ia_routing():start");
597 if (IS_OSPF_ABR(ospf
)) {
598 struct listnode
*node
;
599 struct ospf_area
*area
;
601 switch (ospf
->abr_type
) {
603 if (IS_DEBUG_OSPF_EVENT
)
604 zlog_debug("ospf_ia_routing():Standard ABR");
606 if ((area
= ospf
->backbone
)) {
607 struct listnode
*node
;
609 if (IS_DEBUG_OSPF_EVENT
) {
611 "ospf_ia_routing():backbone area found");
613 "ospf_ia_routing():examining summaries");
616 OSPF_EXAMINE_SUMMARIES_ALL(area
, rt
, rtrs
);
618 for (ALL_LIST_ELEMENTS_RO(ospf
->areas
, node
,
620 if (area
!= ospf
->backbone
)
621 if (ospf_area_is_transit(area
))
622 OSPF_EXAMINE_TRANSIT_SUMMARIES_ALL(
624 } else if (IS_DEBUG_OSPF_EVENT
)
626 "ospf_ia_routing():backbone area NOT found");
630 if (IS_DEBUG_OSPF_EVENT
)
632 "ospf_ia_routing():Alternative Cisco/IBM ABR");
633 area
= ospf
->backbone
; /* Find the BB */
635 /* If we have an active BB connection */
636 if (area
&& ospf_act_bb_connection(ospf
)) {
637 if (IS_DEBUG_OSPF_EVENT
) {
639 "ospf_ia_routing(): backbone area found");
641 "ospf_ia_routing(): examining BB summaries");
644 OSPF_EXAMINE_SUMMARIES_ALL(area
, rt
, rtrs
);
646 for (ALL_LIST_ELEMENTS_RO(ospf
->areas
, node
,
648 if (area
!= ospf
->backbone
)
649 if (ospf_area_is_transit(area
))
650 OSPF_EXAMINE_TRANSIT_SUMMARIES_ALL(
652 } else { /* No active BB connection--consider all areas
654 if (IS_DEBUG_OSPF_EVENT
)
656 "ospf_ia_routing(): "
657 "Active BB connection not found");
658 for (ALL_LIST_ELEMENTS_RO(ospf
->areas
, node
,
660 OSPF_EXAMINE_SUMMARIES_ALL(area
, rt
,
664 case OSPF_ABR_SHORTCUT
:
665 if (IS_DEBUG_OSPF_EVENT
)
667 "ospf_ia_routing():Alternative Shortcut");
668 area
= ospf
->backbone
; /* Find the BB */
670 /* If we have an active BB connection */
671 if (area
&& ospf_act_bb_connection(ospf
)) {
672 if (IS_DEBUG_OSPF_EVENT
) {
674 "ospf_ia_routing(): backbone area found");
676 "ospf_ia_routing(): examining BB summaries");
678 OSPF_EXAMINE_SUMMARIES_ALL(area
, rt
, rtrs
);
681 for (ALL_LIST_ELEMENTS_RO(ospf
->areas
, node
, area
))
682 if (area
!= ospf
->backbone
)
683 if (ospf_area_is_transit(area
)
684 || ((area
->shortcut_configured
685 != OSPF_SHORTCUT_DISABLE
)
686 && ((ospf
->backbone
== NULL
)
687 || ((area
->shortcut_configured
688 == OSPF_SHORTCUT_ENABLE
)
689 && area
->shortcut_capability
))))
690 OSPF_EXAMINE_TRANSIT_SUMMARIES_ALL(
697 struct listnode
*node
;
699 if (IS_DEBUG_OSPF_EVENT
)
701 "ospf_ia_routing():not ABR, considering all areas");
703 for (ALL_LIST_ELEMENTS_RO(ospf
->areas
, node
, area
))
704 OSPF_EXAMINE_SUMMARIES_ALL(area
, rt
, rtrs
);