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
18 * along with GNU Zebra; see the file COPYING. If not, write to the Free
19 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
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_ase.h"
45 #include "ospfd/ospf_abr.h"
46 #include "ospfd/ospf_ia.h"
47 #include "ospfd/ospf_dump.h"
52 ospf_find_abr_route (struct route_table
*rtrs
,
53 struct prefix_ipv4
*abr
,
54 struct ospf_area
*area
)
56 struct route_node
*rn
;
57 struct ospf_route
*or;
60 if ((rn
= route_node_lookup (rtrs
, (struct prefix
*) abr
)) == NULL
)
63 route_unlock_node (rn
);
65 for (node
= listhead ((list
) rn
->info
); node
; nextnode (node
))
66 if ((or = getdata (node
)) != NULL
)
67 if (IPV4_ADDR_SAME (&or->u
.std
.area_id
, &area
->area_id
) && (or->u
.std
.flags
& ROUTER_LSA_BORDER
))
74 ospf_ia_network_route (struct route_table
*rt
, struct prefix_ipv4
*p
,
75 struct ospf_route
*new_or
, struct ospf_route
*abr_or
)
77 struct route_node
*rn1
;
78 struct ospf_route
*or;
80 if (IS_DEBUG_OSPF_EVENT
)
81 zlog_info ("ospf_ia_network_route(): processing summary route to %s/%d",
82 inet_ntoa (p
->prefix
), p
->prefixlen
);
84 /* Find a route to the same dest */
85 if ((rn1
= route_node_lookup (rt
, (struct prefix
*) p
)))
89 route_unlock_node (rn1
);
93 if (IS_DEBUG_OSPF_EVENT
)
94 zlog_info ("ospf_ia_network_route(): "
95 "Found a route to the same network");
96 /* Check the existing route. */
97 if ((res
= ospf_route_cmp (new_or
, or)) < 0)
99 /* New route is better, so replace old one. */
100 ospf_route_subst (rn1
, new_or
, abr_or
);
104 /* New and old route are equal, so next hops can be added. */
105 route_lock_node (rn1
);
106 ospf_route_copy_nexthops (or, abr_or
->path
);
107 route_unlock_node (rn1
);
109 /* new route can be deleted, because existing route has been updated. */
110 ospf_route_free (new_or
);
114 /* New route is worse, so free it. */
115 ospf_route_free (new_or
);
122 if (IS_DEBUG_OSPF_EVENT
)
123 zlog_info ("ospf_ia_network_route(): add new route to %s/%d",
124 inet_ntoa (p
->prefix
), p
->prefixlen
);
125 ospf_route_add (rt
, p
, new_or
, abr_or
);
130 ospf_ia_router_route (struct route_table
*rt
, struct prefix_ipv4
*p
,
131 struct ospf_route
*new_or
, struct ospf_route
*abr_or
)
133 struct route_node
*rn
;
134 struct ospf_route
*or = NULL
;
137 if (IS_DEBUG_OSPF_EVENT
)
138 zlog_info ("ospf_ia_router_route(): considering %s/%d",
139 inet_ntoa (p
->prefix
), p
->prefixlen
);
140 /* Find a route to the same dest */
141 rn
= route_node_get (rt
,(struct prefix
*) p
);
143 if (rn
->info
== NULL
)
144 /* This is a new route */
145 rn
->info
= list_new ();
148 struct ospf_area
*or_area
;
149 or_area
= ospf_area_lookup_by_area_id (new_or
->u
.std
.area_id
);
151 /* This is an additional route */
152 route_unlock_node (rn
);
153 or = ospf_find_asbr_route_through_area (rt
, p
, or_area
);
158 if (IS_DEBUG_OSPF_EVENT
)
159 zlog_info ("ospf_ia_router_route(): "
160 "a route to the same ABR through the same area exists");
161 /* New route is better */
162 if ((ret
= ospf_route_cmp (new_or
, or)) < 0)
164 listnode_delete (rn
->info
, or);
165 ospf_route_free (or);
168 /* Routes are the same */
171 if (IS_DEBUG_OSPF_EVENT
)
172 zlog_info ("ospf_ia_router_route(): merging the new route");
174 ospf_route_copy_nexthops (or, abr_or
->path
);
175 ospf_route_free (new_or
);
178 /* New route is worse */
181 if (IS_DEBUG_OSPF_EVENT
)
182 zlog_info ("ospf_ia_router_route(): skipping the new route");
183 ospf_route_free (new_or
);
188 ospf_route_copy_nexthops (new_or
, abr_or
->path
);
190 if (IS_DEBUG_OSPF_EVENT
)
191 zlog_info ("ospf_ia_router_route(): adding the new route");
193 listnode_add (rn
->info
, new_or
);
199 struct route_table
*rt
;
200 struct route_table
*rtrs
;
201 struct ospf_area
*area
;
205 process_summary_lsa (struct ospf_lsa
*l
, void *v
, int i
)
207 struct ospf_area_range
*range
;
208 struct ospf_route
*abr_or
, *new_or
;
209 struct summary_lsa
*sl
;
210 struct prefix_ipv4 p
, abr
;
212 struct ia_args
*args
;
217 args
= (struct ia_args
*) v
;
218 sl
= (struct summary_lsa
*) l
->data
;
220 if (IS_DEBUG_OSPF_EVENT
)
221 zlog_info ("process_summary_lsa(): LS ID: %s", inet_ntoa (sl
->header
.id
));
223 metric
= GET_METRIC (sl
->metric
);
225 if (metric
== OSPF_LS_INFINITY
)
228 if (IS_LSA_MAXAGE (l
))
231 if (ospf_lsa_is_self_originated (l
))
235 p
.prefix
= sl
->header
.id
;
237 if (sl
->header
.type
== OSPF_SUMMARY_LSA
)
238 p
.prefixlen
= ip_masklen (sl
->mask
);
240 p
.prefixlen
= IPV4_MAX_BITLEN
;
242 apply_mask_ipv4 (&p
);
244 if (sl
->header
.type
== OSPF_SUMMARY_LSA
&&
245 (range
= ospf_area_range_match_any (ospf_top
, &p
)) &&
246 ospf_area_range_active (range
))
249 if (ospf_top
->abr_type
!= OSPF_ABR_STAND
&&
250 args
->area
->external_routing
!= OSPF_AREA_DEFAULT
&&
251 p
.prefix
.s_addr
== OSPF_DEFAULT_DESTINATION
&&
253 return 0; /* Ignore summary default from a stub area */
255 abr
.family
= AF_INET
;
256 abr
.prefix
= sl
->header
.adv_router
;
257 abr
.prefixlen
= IPV4_MAX_BITLEN
;
258 apply_mask_ipv4 (&abr
);
260 abr_or
= ospf_find_abr_route (args
->rtrs
, &abr
, args
->area
);
265 new_or
= ospf_route_new ();
266 new_or
->type
= OSPF_DESTINATION_NETWORK
;
267 new_or
->id
= sl
->header
.id
;
268 new_or
->mask
= sl
->mask
;
269 new_or
->u
.std
.options
= sl
->header
.options
;
270 new_or
->u
.std
.origin
= (struct lsa_header
*) sl
;
271 new_or
->cost
= abr_or
->cost
+ metric
;
272 new_or
->u
.std
.area_id
= args
->area
->area_id
;
274 new_or
->u
.std
.external_routing
= args
->area
->external_routing
;
275 #endif /* HAVE_NSSA */
276 new_or
->path_type
= OSPF_PATH_INTER_AREA
;
278 if (sl
->header
.type
== OSPF_SUMMARY_LSA
)
279 ospf_ia_network_route (args
->rt
, &p
, new_or
, abr_or
);
282 new_or
->type
= OSPF_DESTINATION_ROUTER
;
283 new_or
->u
.std
.flags
= ROUTER_LSA_EXTERNAL
;
284 ospf_ia_router_route (args
->rtrs
, &p
, new_or
, abr_or
);
291 ospf_examine_summaries (struct ospf_area
* area
,
292 struct route_table
*lsdb_rt
,
293 struct route_table
*rt
,
294 struct route_table
*rtrs
)
296 struct ia_args args
= {rt
, rtrs
, area
};
297 foreach_lsa (lsdb_rt
, &args
, 0, process_summary_lsa
);
301 ospf_area_is_transit (struct ospf_area
*area
)
303 return (area
->transit
== OSPF_TRANSIT_TRUE
) ||
304 ospf_full_virtual_nbrs(area
); /* Cisco forgets to set the V-bit :( */
308 ospf_update_network_route (struct route_table
*rt
,
309 struct route_table
*rtrs
,
310 struct summary_lsa
*lsa
,
311 struct prefix_ipv4
*p
,
312 struct ospf_area
*area
)
314 struct route_node
*rn
;
315 struct ospf_route
*or, *abr_or
, *new_or
;
316 struct prefix_ipv4 abr
;
319 abr
.family
= AF_INET
;
320 abr
.prefix
=lsa
->header
.adv_router
;
321 abr
.prefixlen
= IPV4_MAX_BITLEN
;
322 apply_mask_ipv4 (&abr
);
324 abr_or
= ospf_find_abr_route (rtrs
, &abr
, area
);
328 if (IS_DEBUG_OSPF_EVENT
)
329 zlog_info ("ospf_update_network_route(): can't find a route to the ABR");
333 cost
= abr_or
->cost
+ GET_METRIC (lsa
->metric
);
335 rn
= route_node_lookup (rt
, (struct prefix
*) p
);
339 if (ospf_top
->abr_type
!= OSPF_ABR_SHORTCUT
)
340 return; /* Standard ABR can update only already installed
342 if (IS_DEBUG_OSPF_EVENT
)
343 zlog_info ("ospf_update_network_route(): "
344 "Allowing Shortcut ABR to add new route");
345 new_or
= ospf_route_new ();
346 new_or
->type
= OSPF_DESTINATION_NETWORK
;
347 new_or
->id
= lsa
->header
.id
;
348 new_or
->mask
= lsa
->mask
;
349 new_or
->u
.std
.options
= lsa
->header
.options
;
350 new_or
->u
.std
.origin
= (struct lsa_header
*) lsa
;
352 new_or
->u
.std
.area_id
= area
->area_id
;
354 new_or
->u
.std
.external_routing
= area
->external_routing
;
355 #endif /* HAVE_NSSA */
356 new_or
->path_type
= OSPF_PATH_INTER_AREA
;
357 ospf_route_add (rt
, p
, new_or
, abr_or
);
363 route_unlock_node (rn
);
364 if (rn
->info
== NULL
)
370 if (or->path_type
!= OSPF_PATH_INTRA_AREA
&&
371 or->path_type
!= OSPF_PATH_INTER_AREA
)
373 if (IS_DEBUG_OSPF_EVENT
)
374 zlog_info ("ospf_update_network_route(): ERR: path type is wrong");
378 if (ospf_top
->abr_type
== OSPF_ABR_SHORTCUT
)
380 if (or->path_type
== OSPF_PATH_INTRA_AREA
&&
381 !OSPF_IS_AREA_ID_BACKBONE (or->u
.std
.area_id
))
383 if (IS_DEBUG_OSPF_EVENT
)
384 zlog_info ("ospf_update_network_route(): Shortcut: "
385 "this intra-area path is not backbone");
389 else /* Not Shortcut ABR */
391 if (!OSPF_IS_AREA_ID_BACKBONE (or->u
.std
.area_id
))
393 if (IS_DEBUG_OSPF_EVENT
)
394 zlog_info ("ospf_update_network_route(): "
395 "route is not BB-associated");
396 return; /* We can update only BB routes */
402 if (IS_DEBUG_OSPF_EVENT
)
403 zlog_info ("ospf_update_network_route(): new route is worse");
407 if (or->cost
== cost
)
409 if (IS_DEBUG_OSPF_EVENT
)
410 zlog_info ("ospf_update_network_route(): "
411 "new route is same distance, adding nexthops");
412 ospf_route_copy_nexthops (or, abr_or
->path
);
417 if (IS_DEBUG_OSPF_EVENT
)
418 zlog_info ("ospf_update_network_route(): "
419 "new route is better, overriding nexthops");
420 ospf_route_subst_nexthops (or, abr_or
->path
);
423 if ((ospf_top
->abr_type
== OSPF_ABR_SHORTCUT
) &&
424 !OSPF_IS_AREA_ID_BACKBONE (or->u
.std
.area_id
))
426 or->path_type
= OSPF_PATH_INTER_AREA
;
427 or->u
.std
.area_id
= area
->area_id
;
429 or->u
.std
.external_routing
= area
->external_routing
;
430 #endif /* HAVE_NSSA */
431 /* Note that we can do this only in Shortcut ABR mode,
432 because standard ABR must leave the route type and area
440 ospf_update_router_route (struct route_table
*rtrs
,
441 struct summary_lsa
*lsa
,
442 struct prefix_ipv4
*p
,
443 struct ospf_area
*area
)
445 struct ospf_route
*or, *abr_or
, *new_or
;
446 struct prefix_ipv4 abr
;
449 abr
.family
= AF_INET
;
450 abr
.prefix
= lsa
->header
.adv_router
;
451 abr
.prefixlen
= IPV4_MAX_BITLEN
;
452 apply_mask_ipv4 (&abr
);
454 abr_or
= ospf_find_abr_route (rtrs
, &abr
, area
);
458 if (IS_DEBUG_OSPF_EVENT
)
459 zlog_info ("ospf_update_router_route(): can't find a route to the ABR");
463 cost
= abr_or
->cost
+ GET_METRIC (lsa
->metric
);
465 /* First try to find a backbone path,
466 because standard ABR can update only BB-associated paths */
468 if ((ospf_top
->backbone
== NULL
) &&
469 (ospf_top
->abr_type
!= OSPF_ABR_SHORTCUT
))
471 /* no BB area, not Shortcut ABR, exiting */
474 or = ospf_find_asbr_route_through_area (rtrs
, p
, ospf_top
->backbone
);
478 if (ospf_top
->abr_type
!= OSPF_ABR_SHORTCUT
)
480 /* route to ASBR through the BB not found
481 the router is not Shortcut ABR, exiting */
485 /* We're a Shortcut ABR*/
487 /* Let it either add a new router or update the route
488 through the same (non-BB) area. */
490 new_or
= ospf_route_new ();
491 new_or
->type
= OSPF_DESTINATION_ROUTER
;
492 new_or
->id
= lsa
->header
.id
;
493 new_or
->mask
= lsa
->mask
;
494 new_or
->u
.std
.options
= lsa
->header
.options
;
495 new_or
->u
.std
.origin
= (struct lsa_header
*)lsa
;
497 new_or
->u
.std
.area_id
= area
->area_id
;
499 new_or
->u
.std
.external_routing
= area
->external_routing
;
500 #endif /* HAVE_NSSA */
501 new_or
->path_type
= OSPF_PATH_INTER_AREA
;
502 new_or
->u
.std
.flags
= ROUTER_LSA_EXTERNAL
;
503 ospf_ia_router_route (rtrs
, p
, new_or
, abr_or
);
509 /* At this point the "or" is always bb-associated */
511 if (!(or->u
.std
.flags
& ROUTER_LSA_EXTERNAL
))
513 if (IS_DEBUG_OSPF_EVENT
)
514 zlog_info ("ospf_upd_router_route(): the remote router is not an ASBR");
518 if (or->path_type
!= OSPF_PATH_INTRA_AREA
&&
519 or->path_type
!= OSPF_PATH_INTER_AREA
)
525 else if (or->cost
== cost
)
526 ospf_route_copy_nexthops (or, abr_or
->path
);
528 else if (or->cost
> cost
)
530 ospf_route_subst_nexthops (or, abr_or
->path
);
533 /* Even if the ABR runs in Shortcut mode, we can't change
534 the path type and area, because the "or" is always bb-associated
535 at this point and even Shortcut ABR can't change these attributes */
540 process_transit_summary_lsa (struct ospf_lsa
*l
, void *v
, int i
)
542 struct summary_lsa
*sl
;
543 struct prefix_ipv4 p
;
545 struct ia_args
*args
;
550 args
= (struct ia_args
*) v
;
551 sl
= (struct summary_lsa
*) l
->data
;
553 if (IS_DEBUG_OSPF_EVENT
)
554 zlog_info ("process_transit_summaries(): LS ID: %s",
555 inet_ntoa (l
->data
->id
));
556 metric
= GET_METRIC (sl
->metric
);
558 if (metric
== OSPF_LS_INFINITY
)
560 if (IS_DEBUG_OSPF_EVENT
)
561 zlog_info ("process_transit_summaries(): metric is infinity, skip");
565 if (IS_LSA_MAXAGE (l
))
567 if (IS_DEBUG_OSPF_EVENT
)
568 zlog_info ("process_transit_summaries(): This LSA is too old");
572 if (ospf_lsa_is_self_originated (l
))
574 if (IS_DEBUG_OSPF_EVENT
)
575 zlog_info ("process_transit_summaries(): This LSA is mine, skip");
580 p
.prefix
= sl
->header
.id
;
582 if (sl
->header
.type
== OSPF_SUMMARY_LSA
)
583 p
.prefixlen
= ip_masklen (sl
->mask
);
585 p
.prefixlen
= IPV4_MAX_BITLEN
;
587 apply_mask_ipv4 (&p
);
589 if (sl
->header
.type
== OSPF_SUMMARY_LSA
)
590 ospf_update_network_route (args
->rt
, args
->rtrs
, sl
, &p
, args
->area
);
592 ospf_update_router_route (args
->rtrs
, sl
, &p
, args
->area
);
598 ospf_examine_transit_summaries (struct ospf_area
*area
,
599 /* struct ospf_lsdb *lsdb, */
600 struct route_table
*lsdb_rt
,
601 struct route_table
*rt
,
602 struct route_table
*rtrs
)
604 struct ia_args args
= {rt
, rtrs
, area
};
606 /* ospf_lsdb_iterator (lsdb, &args, 0, process_transit_summary_lsa); */
607 foreach_lsa (lsdb_rt
, &args
, 0, process_transit_summary_lsa
);
611 ospf_ia_routing (struct route_table
*rt
,
612 struct route_table
*rtrs
)
614 struct ospf_area
* area
;
616 if (IS_DEBUG_OSPF_EVENT
)
617 zlog_info ("ospf_ia_routing():start");
622 struct ospf_area
*area
;
624 switch (ospf_top
->abr_type
)
627 if (IS_DEBUG_OSPF_EVENT
)
628 zlog_info ("ospf_ia_routing():Standard ABR");
630 if ((area
= ospf_top
->backbone
))
634 if (IS_DEBUG_OSPF_EVENT
)
636 zlog_info ("ospf_ia_routing():backbone area found");
637 zlog_info ("ospf_ia_routing():examining summaries");
640 OSPF_EXAMINE_SUMMARIES_ALL (area
, rt
, rtrs
);
642 for (node
= listhead (ospf_top
->areas
); node
; nextnode (node
))
643 if ((area
= getdata (node
)) != NULL
)
644 if (area
!= ospf_top
->backbone
)
645 if (ospf_area_is_transit (area
))
646 OSPF_EXAMINE_TRANSIT_SUMMARIES_ALL (area
, rt
, rtrs
);
649 if (IS_DEBUG_OSPF_EVENT
)
650 zlog_info ("ospf_ia_routing():backbone area NOT found");
654 if (IS_DEBUG_OSPF_EVENT
)
655 zlog_info ("ospf_ia_routing():Alternative Cisco/IBM ABR");
656 area
= ospf_top
->backbone
; /* Find the BB */
658 /* If we have an active BB connection */
659 if (area
&& ospf_act_bb_connection ())
661 if (IS_DEBUG_OSPF_EVENT
)
663 zlog_info ("ospf_ia_routing(): backbone area found");
664 zlog_info ("ospf_ia_routing(): examining BB summaries");
667 OSPF_EXAMINE_SUMMARIES_ALL (area
, rt
, rtrs
);
669 for (node
= listhead (ospf_top
->areas
); node
; nextnode (node
))
670 if ((area
= getdata (node
)) != NULL
)
671 if (area
!= ospf_top
->backbone
)
672 if (ospf_area_is_transit (area
))
673 OSPF_EXAMINE_TRANSIT_SUMMARIES_ALL (area
, rt
, rtrs
);
676 { /* No active BB connection--consider all areas */
677 if (IS_DEBUG_OSPF_EVENT
)
678 zlog_info ("ospf_ia_routing(): "
679 "Active BB connection not found");
680 for (node
= listhead (ospf_top
->areas
); node
; nextnode (node
))
681 if ((area
= getdata (node
)) != NULL
)
682 OSPF_EXAMINE_SUMMARIES_ALL (area
, rt
, rtrs
);
685 case OSPF_ABR_SHORTCUT
:
686 if (IS_DEBUG_OSPF_EVENT
)
687 zlog_info ("ospf_ia_routing():Alternative Shortcut");
688 area
= ospf_top
->backbone
; /* Find the BB */
690 /* If we have an active BB connection */
691 if (area
&& ospf_act_bb_connection ())
693 if (IS_DEBUG_OSPF_EVENT
)
695 zlog_info ("ospf_ia_routing(): backbone area found");
696 zlog_info ("ospf_ia_routing(): examining BB summaries");
698 OSPF_EXAMINE_SUMMARIES_ALL (area
, rt
, rtrs
);
701 for (node
= listhead (ospf_top
->areas
); node
; nextnode (node
))
702 if ((area
= getdata (node
)) != NULL
)
703 if (area
!= ospf_top
->backbone
)
704 if (ospf_area_is_transit (area
) ||
705 ((area
->shortcut_configured
!= OSPF_SHORTCUT_DISABLE
) &&
706 ((ospf_top
->backbone
== NULL
) ||
707 ((area
->shortcut_configured
== OSPF_SHORTCUT_ENABLE
) &&
708 area
->shortcut_capability
))))
709 OSPF_EXAMINE_TRANSIT_SUMMARIES_ALL (area
, rt
, rtrs
);
719 if (IS_DEBUG_OSPF_EVENT
)
720 zlog_info ("ospf_ia_routing():not ABR, considering all areas");
722 for (node
= listhead (ospf_top
->areas
); node
; nextnode (node
))
723 if ((area
= getdata (node
)) != NULL
)
724 OSPF_EXAMINE_SUMMARIES_ALL (area
, rt
, rtrs
);