2 * OSPF version 2 Interface State Machine
3 * From RFC2328 [OSPF Version 2]
4 * Copyright (C) 1999, 2000 Toshiaki Takada
6 * This file is part of GNU Zebra.
8 * GNU Zebra is free software; you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License as published by the
10 * Free Software Foundation; either version 2, or (at your option) any
13 * GNU Zebra is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * General Public License for more details.
18 * You should have received a copy of the GNU General Public License
19 * along with GNU Zebra; see the file COPYING. If not, write to the Free
20 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
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_network.h"
42 #include "ospfd/ospf_dump.h"
43 #include "ospfd/ospf_packet.h"
44 #include "ospfd/ospf_flood.h"
45 #include "ospfd/ospf_abr.h"
46 #include "ospfd/ospf_snmp.h"
48 /* elect DR and BDR. Refer to RFC2319 section 9.4 */
49 static struct ospf_neighbor
*
50 ospf_dr_election_sub (struct list
*routers
)
52 struct listnode
*node
;
53 struct ospf_neighbor
*nbr
, *max
= NULL
;
55 /* Choose highest router priority.
56 In case of tie, choose highest Router ID. */
57 for (ALL_LIST_ELEMENTS_RO (routers
, node
, nbr
))
63 if (max
->priority
< nbr
->priority
)
65 else if (max
->priority
== nbr
->priority
)
66 if (IPV4_ADDR_CMP (&max
->router_id
, &nbr
->router_id
) < 0)
74 static struct ospf_neighbor
*
75 ospf_elect_dr (struct ospf_interface
*oi
, struct list
*el_list
)
78 struct listnode
*node
;
79 struct ospf_neighbor
*nbr
, *dr
= NULL
, *bdr
= NULL
;
81 dr_list
= list_new ();
83 /* Add neighbors to the list. */
84 for (ALL_LIST_ELEMENTS_RO (el_list
, node
, nbr
))
86 /* neighbor declared to be DR. */
88 listnode_add (dr_list
, nbr
);
90 /* Preserve neighbor BDR. */
91 if (IPV4_ADDR_SAME (&BDR (oi
), &nbr
->address
.u
.prefix4
))
95 /* Elect Designated Router. */
96 if (listcount (dr_list
) > 0)
97 dr
= ospf_dr_election_sub (dr_list
);
101 /* Set DR to interface. */
103 DR (oi
) = dr
->address
.u
.prefix4
;
107 list_delete (dr_list
);
112 static struct ospf_neighbor
*
113 ospf_elect_bdr (struct ospf_interface
*oi
, struct list
*el_list
)
115 struct list
*bdr_list
, *no_dr_list
;
116 struct listnode
*node
;
117 struct ospf_neighbor
*nbr
, *bdr
= NULL
;
119 bdr_list
= list_new ();
120 no_dr_list
= list_new ();
122 /* Add neighbors to the list. */
123 for (ALL_LIST_ELEMENTS_RO (el_list
, node
, nbr
))
125 /* neighbor declared to be DR. */
129 /* neighbor declared to be BDR. */
130 if (NBR_IS_BDR (nbr
))
131 listnode_add (bdr_list
, nbr
);
133 listnode_add (no_dr_list
, nbr
);
136 /* Elect Backup Designated Router. */
137 if (listcount (bdr_list
) > 0)
138 bdr
= ospf_dr_election_sub (bdr_list
);
140 bdr
= ospf_dr_election_sub (no_dr_list
);
142 /* Set BDR to interface. */
144 BDR (oi
) = bdr
->address
.u
.prefix4
;
148 list_delete (bdr_list
);
149 list_delete (no_dr_list
);
155 ospf_ism_state (struct ospf_interface
*oi
)
157 if (IPV4_ADDR_SAME (&DR (oi
), &oi
->address
->u
.prefix4
))
159 else if (IPV4_ADDR_SAME (&BDR (oi
), &oi
->address
->u
.prefix4
))
166 ospf_dr_eligible_routers (struct route_table
*nbrs
, struct list
*el_list
)
168 struct route_node
*rn
;
169 struct ospf_neighbor
*nbr
;
171 for (rn
= route_top (nbrs
); rn
; rn
= route_next (rn
))
172 if ((nbr
= rn
->info
) != NULL
)
173 /* Ignore 0.0.0.0 node*/
174 if (nbr
->router_id
.s_addr
!= 0)
175 /* Is neighbor eligible? */
176 if (nbr
->priority
> 0)
177 /* Is neighbor upper 2-Way? */
178 if (nbr
->state
>= NSM_TwoWay
)
179 listnode_add (el_list
, nbr
);
182 /* Generate AdjOK? NSM event. */
184 ospf_dr_change (struct ospf
*ospf
, struct route_table
*nbrs
)
186 struct route_node
*rn
;
187 struct ospf_neighbor
*nbr
;
189 for (rn
= route_top (nbrs
); rn
; rn
= route_next (rn
))
190 if ((nbr
= rn
->info
) != NULL
)
191 /* Ignore 0.0.0.0 node*/
192 if (nbr
->router_id
.s_addr
!= 0)
193 /* Is neighbor upper 2-Way? */
194 if (nbr
->state
>= NSM_TwoWay
)
196 if (!IPV4_ADDR_SAME (&nbr
->router_id
, &ospf
->router_id
))
197 OSPF_NSM_EVENT_SCHEDULE (nbr
, NSM_AdjOK
);
201 ospf_dr_election (struct ospf_interface
*oi
)
203 struct in_addr old_dr
, old_bdr
;
204 int old_state
, new_state
;
205 struct list
*el_list
;
207 /* backup current values. */
210 old_state
= oi
->state
;
212 el_list
= list_new ();
214 /* List eligible routers. */
215 ospf_dr_eligible_routers (oi
->nbrs
, el_list
);
217 /* First election of DR and BDR. */
218 ospf_elect_bdr (oi
, el_list
);
219 ospf_elect_dr (oi
, el_list
);
221 new_state
= ospf_ism_state (oi
);
223 zlog_debug ("DR-Election[1st]: Backup %s", inet_ntoa (BDR (oi
)));
224 zlog_debug ("DR-Election[1st]: DR %s", inet_ntoa (DR (oi
)));
226 if (new_state
!= old_state
&&
227 !(new_state
== ISM_DROther
&& old_state
< ISM_DROther
))
229 ospf_elect_bdr (oi
, el_list
);
230 ospf_elect_dr (oi
, el_list
);
232 new_state
= ospf_ism_state (oi
);
234 zlog_debug ("DR-Election[2nd]: Backup %s", inet_ntoa (BDR (oi
)));
235 zlog_debug ("DR-Election[2nd]: DR %s", inet_ntoa (DR (oi
)));
238 list_delete (el_list
);
240 /* if DR or BDR changes, cause AdjOK? neighbor event. */
241 if (!IPV4_ADDR_SAME (&old_dr
, &DR (oi
)) ||
242 !IPV4_ADDR_SAME (&old_bdr
, &BDR (oi
)))
243 ospf_dr_change (oi
->ospf
, oi
->nbrs
);
250 ospf_hello_timer (struct thread
*thread
)
252 struct ospf_interface
*oi
;
254 oi
= THREAD_ARG (thread
);
257 if (IS_DEBUG_OSPF (ism
, ISM_TIMERS
))
258 zlog_debug("ISM[%s]: Timer (Hello timer expire)", IF_NAME(oi
));
260 /* Sending hello packet. */
261 ospf_hello_send (oi
);
263 /* Hello timer set. */
264 OSPF_HELLO_TIMER_ON (oi
);
270 ospf_wait_timer (struct thread
*thread
)
272 struct ospf_interface
*oi
;
274 oi
= THREAD_ARG (thread
);
277 if (IS_DEBUG_OSPF (ism
, ISM_TIMERS
))
278 zlog_debug("ISM[%s]: Timer (Wait timer expire)", IF_NAME(oi
));
280 OSPF_ISM_EVENT_SCHEDULE (oi
, ISM_WaitTimer
);
285 /* Hook function called after ospf ISM event is occured. And vty's
286 network command invoke this function after making interface
289 ism_timer_set (struct ospf_interface
*oi
)
294 /* First entry point of ospf interface state machine. In this state
295 interface parameters must be set to initial values, and timers are
297 OSPF_ISM_TIMER_OFF (oi
->t_hello
);
298 OSPF_ISM_TIMER_OFF (oi
->t_wait
);
299 OSPF_ISM_TIMER_OFF (oi
->t_ls_ack
);
302 /* In this state, the interface may be looped back and will be
303 unavailable for regular data traffic. */
304 OSPF_ISM_TIMER_OFF (oi
->t_hello
);
305 OSPF_ISM_TIMER_OFF (oi
->t_wait
);
306 OSPF_ISM_TIMER_OFF (oi
->t_ls_ack
);
309 /* The router is trying to determine the identity of DRouter and
310 BDRouter. The router begin to receive and send Hello Packets. */
311 /* send first hello immediately */
312 OSPF_ISM_TIMER_MSEC_ON (oi
->t_hello
, ospf_hello_timer
, 1);
313 OSPF_ISM_TIMER_ON (oi
->t_wait
, ospf_wait_timer
,
314 OSPF_IF_PARAM (oi
, v_wait
));
315 OSPF_ISM_TIMER_OFF (oi
->t_ls_ack
);
317 case ISM_PointToPoint
:
318 /* The interface connects to a physical Point-to-point network or
319 virtual link. The router attempts to form an adjacency with
320 neighboring router. Hello packets are also sent. */
321 /* send first hello immediately */
322 OSPF_ISM_TIMER_MSEC_ON (oi
->t_hello
, ospf_hello_timer
, 1);
323 OSPF_ISM_TIMER_OFF (oi
->t_wait
);
324 OSPF_ISM_TIMER_ON (oi
->t_ls_ack
, ospf_ls_ack_timer
, oi
->v_ls_ack
);
327 /* The network type of the interface is broadcast or NBMA network,
328 and the router itself is neither Designated Router nor
329 Backup Designated Router. */
330 OSPF_HELLO_TIMER_ON (oi
);
331 OSPF_ISM_TIMER_OFF (oi
->t_wait
);
332 OSPF_ISM_TIMER_ON (oi
->t_ls_ack
, ospf_ls_ack_timer
, oi
->v_ls_ack
);
335 /* The network type of the interface is broadcast os NBMA network,
336 and the router is Backup Designated Router. */
337 OSPF_HELLO_TIMER_ON (oi
);
338 OSPF_ISM_TIMER_OFF (oi
->t_wait
);
339 OSPF_ISM_TIMER_ON (oi
->t_ls_ack
, ospf_ls_ack_timer
, oi
->v_ls_ack
);
342 /* The network type of the interface is broadcast or NBMA network,
343 and the router is Designated Router. */
344 OSPF_HELLO_TIMER_ON (oi
);
345 OSPF_ISM_TIMER_OFF (oi
->t_wait
);
346 OSPF_ISM_TIMER_ON (oi
->t_ls_ack
, ospf_ls_ack_timer
, oi
->v_ls_ack
);
352 ism_interface_up (struct ospf_interface
*oi
)
356 /* if network type is point-to-point, Point-to-MultiPoint or virtual link,
357 the state transitions to Point-to-Point. */
358 if (oi
->type
== OSPF_IFTYPE_POINTOPOINT
||
359 oi
->type
== OSPF_IFTYPE_POINTOMULTIPOINT
||
360 oi
->type
== OSPF_IFTYPE_VIRTUALLINK
)
361 next_state
= ISM_PointToPoint
;
362 /* Else if the router is not eligible to DR, the state transitions to
364 else if (PRIORITY (oi
) == 0) /* router is eligible? */
365 next_state
= ISM_DROther
;
367 /* Otherwise, the state transitions to Waiting. */
368 next_state
= ISM_Waiting
;
370 if (oi
->type
== OSPF_IFTYPE_NBMA
)
371 ospf_nbr_nbma_if_update (oi
->ospf
, oi
);
373 /* ospf_ism_event (t); */
378 ism_loop_ind (struct ospf_interface
*oi
)
382 /* call ism_interface_down. */
383 /* ret = ism_interface_down (oi); */
388 /* Interface down event handler. */
390 ism_interface_down (struct ospf_interface
*oi
)
392 ospf_if_cleanup (oi
);
398 ism_backup_seen (struct ospf_interface
*oi
)
400 return ospf_dr_election (oi
);
404 ism_wait_timer (struct ospf_interface
*oi
)
406 return ospf_dr_election (oi
);
410 ism_neighbor_change (struct ospf_interface
*oi
)
412 return ospf_dr_election (oi
);
416 ism_ignore (struct ospf_interface
*oi
)
418 if (IS_DEBUG_OSPF (ism
, ISM_EVENTS
))
419 zlog_debug("ISM[%s]: ism_ignore called", IF_NAME(oi
));
424 /* Interface State Machine */
426 int (*func
) (struct ospf_interface
*);
428 } ISM
[OSPF_ISM_STATE_MAX
][OSPF_ISM_EVENT_MAX
] =
431 /* DependUpon: dummy state. */
432 { ism_ignore
, ISM_DependUpon
}, /* NoEvent */
433 { ism_ignore
, ISM_DependUpon
}, /* InterfaceUp */
434 { ism_ignore
, ISM_DependUpon
}, /* WaitTimer */
435 { ism_ignore
, ISM_DependUpon
}, /* BackupSeen */
436 { ism_ignore
, ISM_DependUpon
}, /* NeighborChange */
437 { ism_ignore
, ISM_DependUpon
}, /* LoopInd */
438 { ism_ignore
, ISM_DependUpon
}, /* UnloopInd */
439 { ism_ignore
, ISM_DependUpon
}, /* InterfaceDown */
443 { ism_ignore
, ISM_DependUpon
}, /* NoEvent */
444 { ism_interface_up
, ISM_DependUpon
}, /* InterfaceUp */
445 { ism_ignore
, ISM_Down
}, /* WaitTimer */
446 { ism_ignore
, ISM_Down
}, /* BackupSeen */
447 { ism_ignore
, ISM_Down
}, /* NeighborChange */
448 { ism_loop_ind
, ISM_Loopback
}, /* LoopInd */
449 { ism_ignore
, ISM_Down
}, /* UnloopInd */
450 { ism_interface_down
, ISM_Down
}, /* InterfaceDown */
454 { ism_ignore
, ISM_DependUpon
}, /* NoEvent */
455 { ism_ignore
, ISM_Loopback
}, /* InterfaceUp */
456 { ism_ignore
, ISM_Loopback
}, /* WaitTimer */
457 { ism_ignore
, ISM_Loopback
}, /* BackupSeen */
458 { ism_ignore
, ISM_Loopback
}, /* NeighborChange */
459 { ism_ignore
, ISM_Loopback
}, /* LoopInd */
460 { ism_ignore
, ISM_Down
}, /* UnloopInd */
461 { ism_interface_down
, ISM_Down
}, /* InterfaceDown */
465 { ism_ignore
, ISM_DependUpon
}, /* NoEvent */
466 { ism_ignore
, ISM_Waiting
}, /* InterfaceUp */
467 { ism_wait_timer
, ISM_DependUpon
}, /* WaitTimer */
468 { ism_backup_seen
, ISM_DependUpon
}, /* BackupSeen */
469 { ism_ignore
, ISM_Waiting
}, /* NeighborChange */
470 { ism_loop_ind
, ISM_Loopback
}, /* LoopInd */
471 { ism_ignore
, ISM_Waiting
}, /* UnloopInd */
472 { ism_interface_down
, ISM_Down
}, /* InterfaceDown */
475 /* Point-to-Point: */
476 { ism_ignore
, ISM_DependUpon
}, /* NoEvent */
477 { ism_ignore
, ISM_PointToPoint
}, /* InterfaceUp */
478 { ism_ignore
, ISM_PointToPoint
}, /* WaitTimer */
479 { ism_ignore
, ISM_PointToPoint
}, /* BackupSeen */
480 { ism_ignore
, ISM_PointToPoint
}, /* NeighborChange */
481 { ism_loop_ind
, ISM_Loopback
}, /* LoopInd */
482 { ism_ignore
, ISM_PointToPoint
}, /* UnloopInd */
483 { ism_interface_down
, ISM_Down
}, /* InterfaceDown */
487 { ism_ignore
, ISM_DependUpon
}, /* NoEvent */
488 { ism_ignore
, ISM_DROther
}, /* InterfaceUp */
489 { ism_ignore
, ISM_DROther
}, /* WaitTimer */
490 { ism_ignore
, ISM_DROther
}, /* BackupSeen */
491 { ism_neighbor_change
, ISM_DependUpon
}, /* NeighborChange */
492 { ism_loop_ind
, ISM_Loopback
}, /* LoopInd */
493 { ism_ignore
, ISM_DROther
}, /* UnloopInd */
494 { ism_interface_down
, ISM_Down
}, /* InterfaceDown */
498 { ism_ignore
, ISM_DependUpon
}, /* NoEvent */
499 { ism_ignore
, ISM_Backup
}, /* InterfaceUp */
500 { ism_ignore
, ISM_Backup
}, /* WaitTimer */
501 { ism_ignore
, ISM_Backup
}, /* BackupSeen */
502 { ism_neighbor_change
, ISM_DependUpon
}, /* NeighborChange */
503 { ism_loop_ind
, ISM_Loopback
}, /* LoopInd */
504 { ism_ignore
, ISM_Backup
}, /* UnloopInd */
505 { ism_interface_down
, ISM_Down
}, /* InterfaceDown */
509 { ism_ignore
, ISM_DependUpon
}, /* NoEvent */
510 { ism_ignore
, ISM_DR
}, /* InterfaceUp */
511 { ism_ignore
, ISM_DR
}, /* WaitTimer */
512 { ism_ignore
, ISM_DR
}, /* BackupSeen */
513 { ism_neighbor_change
, ISM_DependUpon
}, /* NeighborChange */
514 { ism_loop_ind
, ISM_Loopback
}, /* LoopInd */
515 { ism_ignore
, ISM_DR
}, /* UnloopInd */
516 { ism_interface_down
, ISM_Down
}, /* InterfaceDown */
520 static const char *ospf_ism_event_str
[] =
533 ism_change_state (struct ospf_interface
*oi
, int state
)
536 struct ospf_lsa
*lsa
;
538 /* Logging change of state. */
539 if (IS_DEBUG_OSPF (ism
, ISM_STATUS
))
540 zlog_debug("ISM[%s]: State change %s -> %s", IF_NAME(oi
),
541 LOOKUP(ospf_ism_state_msg
, oi
->state
),
542 LOOKUP(ospf_ism_state_msg
, state
));
544 old_state
= oi
->state
;
549 /* Terminal state or regression */
550 if ((state
== ISM_DR
) || (state
== ISM_Backup
) || (state
== ISM_DROther
) ||
551 (state
== ISM_PointToPoint
) || (state
< old_state
))
553 /* ospfVirtIfStateChange */
554 if (oi
->type
== OSPF_IFTYPE_VIRTUALLINK
)
555 ospfTrapVirtIfStateChange (oi
);
556 /* ospfIfStateChange */
558 ospfTrapIfStateChange (oi
);
562 /* Set multicast memberships appropriately for new state. */
563 ospf_if_set_multicast(oi
);
565 if (old_state
== ISM_Down
|| state
== ISM_Down
)
566 ospf_check_abr_status (oi
->ospf
);
568 /* Originate router-LSA. */
569 if (state
== ISM_Down
)
571 if (oi
->area
->act_ints
> 0)
572 oi
->area
->act_ints
--;
574 else if (old_state
== ISM_Down
)
575 oi
->area
->act_ints
++;
577 /* schedule router-LSA originate. */
578 ospf_router_lsa_update_area (oi
->area
);
580 /* Originate network-LSA. */
581 if (old_state
!= ISM_DR
&& state
== ISM_DR
)
582 ospf_network_lsa_update (oi
);
583 else if (old_state
== ISM_DR
&& state
!= ISM_DR
)
585 /* Free self originated network LSA. */
586 lsa
= oi
->network_lsa_self
;
588 ospf_lsa_flush_area (lsa
, oi
->area
);
590 ospf_lsa_unlock (&oi
->network_lsa_self
);
591 oi
->network_lsa_self
= NULL
;
594 ospf_opaque_ism_change (oi
, old_state
);
596 /* Check area border status. */
597 ospf_check_abr_status (oi
->ospf
);
600 /* Execute ISM event process. */
602 ospf_ism_event (struct thread
*thread
)
606 struct ospf_interface
*oi
;
608 oi
= THREAD_ARG (thread
);
609 event
= THREAD_VAL (thread
);
612 next_state
= (*(ISM
[oi
->state
][event
].func
))(oi
);
615 next_state
= ISM
[oi
->state
][event
].next_state
;
617 if (IS_DEBUG_OSPF (ism
, ISM_EVENTS
))
618 zlog_debug("ISM[%s]: %s (%s)", IF_NAME(oi
),
619 LOOKUP(ospf_ism_state_msg
, oi
->state
),
620 ospf_ism_event_str
[event
]);
622 /* If state is changed. */
623 if (next_state
!= oi
->state
)
624 ism_change_state (oi
, next_state
);
626 /* Make sure timer is set. */