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"
47 /* elect DR and BDR. Refer to RFC2319 section 9.4 */
48 struct ospf_neighbor
*
49 ospf_dr_election_sub (list routers
)
52 struct ospf_neighbor
*nbr
, *max
= NULL
;
54 /* Choose highest router priority.
55 In case of tie, choose highest Router ID. */
56 for (node
= listhead (routers
); node
; nextnode (node
))
64 if (max
->priority
< nbr
->priority
)
66 else if (max
->priority
== nbr
->priority
)
67 if (IPV4_ADDR_CMP (&max
->router_id
, &nbr
->router_id
) < 0)
75 struct ospf_neighbor
*
76 ospf_elect_dr (struct ospf_interface
*oi
, list el_list
)
80 struct ospf_neighbor
*nbr
, *dr
= NULL
, *bdr
= NULL
;
82 dr_list
= list_new ();
84 /* Add neighbors to the list. */
85 for (node
= listhead (el_list
); node
; nextnode (node
))
89 /* neighbor declared to be DR. */
91 listnode_add (dr_list
, nbr
);
93 /* Preserve neighbor BDR. */
94 if (IPV4_ADDR_SAME (&BDR (oi
), &nbr
->address
.u
.prefix4
))
98 /* Elect Designated Router. */
99 if (listcount (dr_list
) > 0)
100 dr
= ospf_dr_election_sub (dr_list
);
104 /* Set DR to interface. */
107 DR (oi
) = dr
->address
.u
.prefix4
;
108 dr
->d_router
= dr
->address
.u
.prefix4
;
113 list_delete (dr_list
);
118 struct ospf_neighbor
*
119 ospf_elect_bdr (struct ospf_interface
*oi
, list el_list
)
121 list bdr_list
, no_dr_list
;
123 struct ospf_neighbor
*nbr
, *bdr
= NULL
;
125 bdr_list
= list_new ();
126 no_dr_list
= list_new ();
128 /* Add neighbors to the list. */
129 for (node
= listhead (el_list
); node
; nextnode (node
))
131 nbr
= getdata (node
);
133 /* neighbor declared to be DR. */
137 /* neighbor declared to be BDR. */
138 if (NBR_IS_BDR (nbr
))
139 listnode_add (bdr_list
, nbr
);
141 listnode_add (no_dr_list
, nbr
);
144 /* Elect Backup Designated Router. */
145 if (listcount (bdr_list
) > 0)
146 bdr
= ospf_dr_election_sub (bdr_list
);
148 bdr
= ospf_dr_election_sub (no_dr_list
);
150 /* Set BDR to interface. */
153 BDR (oi
) = bdr
->address
.u
.prefix4
;
154 bdr
->bd_router
= bdr
->address
.u
.prefix4
;
159 list_delete (bdr_list
);
160 list_delete (no_dr_list
);
166 ospf_ism_state (struct ospf_interface
*oi
)
168 if (IPV4_ADDR_SAME (&DR (oi
), &oi
->address
->u
.prefix4
))
170 else if (IPV4_ADDR_SAME (&BDR (oi
), &oi
->address
->u
.prefix4
))
177 ospf_dr_eligible_routers (struct route_table
*nbrs
, list el_list
)
179 struct route_node
*rn
;
180 struct ospf_neighbor
*nbr
;
182 for (rn
= route_top (nbrs
); rn
; rn
= route_next (rn
))
183 if ((nbr
= rn
->info
) != NULL
)
184 /* Ignore 0.0.0.0 node*/
185 if (nbr
->router_id
.s_addr
!= 0)
186 /* Is neighbor eligible? */
187 if (nbr
->priority
!= 0)
188 /* Is neighbor upper 2-Way? */
189 if (nbr
->state
>= NSM_TwoWay
)
190 listnode_add (el_list
, nbr
);
193 /* Generate AdjOK? NSM event. */
195 ospf_dr_change (struct ospf
*ospf
, struct route_table
*nbrs
)
197 struct route_node
*rn
;
198 struct ospf_neighbor
*nbr
;
200 for (rn
= route_top (nbrs
); rn
; rn
= route_next (rn
))
201 if ((nbr
= rn
->info
) != NULL
)
202 /* Ignore 0.0.0.0 node*/
203 if (nbr
->router_id
.s_addr
!= 0)
204 /* Is neighbor upper 2-Way? */
205 if (nbr
->state
>= NSM_TwoWay
)
207 if (!IPV4_ADDR_SAME (&nbr
->router_id
, &ospf
->router_id
))
208 OSPF_NSM_EVENT_SCHEDULE (nbr
, NSM_AdjOK
);
212 ospf_dr_election (struct ospf_interface
*oi
)
214 struct in_addr old_dr
, old_bdr
;
215 int old_state
, new_state
;
217 struct ospf_neighbor
*dr
, *bdr
;
219 /* backup current values. */
222 old_state
= oi
->state
;
224 el_list
= list_new ();
226 /* List eligible routers. */
227 ospf_dr_eligible_routers (oi
->nbrs
, el_list
);
229 /* First election of DR and BDR. */
230 bdr
= ospf_elect_bdr (oi
, el_list
);
231 dr
= ospf_elect_dr (oi
, el_list
);
233 new_state
= ospf_ism_state (oi
);
235 zlog_info ("DR-Election[1st]: Backup %s", inet_ntoa (BDR (oi
)));
236 zlog_info ("DR-Election[1st]: DR %s", inet_ntoa (DR (oi
)));
238 if (new_state
!= old_state
&&
239 !(new_state
== ISM_DROther
&& old_state
< ISM_DROther
))
241 ospf_elect_bdr (oi
, el_list
);
242 ospf_elect_dr (oi
, el_list
);
244 new_state
= ospf_ism_state (oi
);
246 zlog_info ("DR-Election[2nd]: Backup %s", inet_ntoa (BDR (oi
)));
247 zlog_info ("DR-Election[2nd]: DR %s", inet_ntoa (DR (oi
)));
250 list_delete (el_list
);
252 /* if DR or BDR changes, cause AdjOK? neighbor event. */
253 if (!IPV4_ADDR_SAME (&old_dr
, &DR (oi
)) ||
254 !IPV4_ADDR_SAME (&old_bdr
, &BDR (oi
)))
255 ospf_dr_change (oi
->ospf
, oi
->nbrs
);
257 if (oi
->type
== OSPF_IFTYPE_BROADCAST
|| oi
->type
== OSPF_IFTYPE_POINTOPOINT
)
259 /* Multicast group change. */
260 if ((old_state
!= ISM_DR
&& old_state
!= ISM_Backup
) &&
261 (new_state
== ISM_DR
|| new_state
== ISM_Backup
))
262 ospf_if_add_alldrouters (oi
->ospf
, oi
->address
, oi
->ifp
->ifindex
);
263 else if ((old_state
== ISM_DR
|| old_state
== ISM_Backup
) &&
264 (new_state
!= ISM_DR
&& new_state
!= ISM_Backup
))
265 ospf_if_drop_alldrouters (oi
->ospf
, oi
->address
, oi
->ifp
->ifindex
);
273 ospf_hello_timer (struct thread
*thread
)
275 struct ospf_interface
*oi
;
277 oi
= THREAD_ARG (thread
);
280 if (IS_DEBUG_OSPF (ism
, ISM_TIMERS
))
281 zlog (NULL
, LOG_DEBUG
, "ISM[%s]: Timer (Hello timer expire)",
284 /* Sending hello packet. */
285 ospf_hello_send (oi
);
287 /* Hello timer set. */
288 OSPF_ISM_TIMER_ON (oi
->t_hello
, ospf_hello_timer
,
289 OSPF_IF_PARAM (oi
, v_hello
));
295 ospf_wait_timer (struct thread
*thread
)
297 struct ospf_interface
*oi
;
299 oi
= THREAD_ARG (thread
);
302 if (IS_DEBUG_OSPF (ism
, ISM_TIMERS
))
303 zlog (NULL
, LOG_DEBUG
, "ISM[%s]: Timer (Wait timer expire)",
306 OSPF_ISM_EVENT_SCHEDULE (oi
, ISM_WaitTimer
);
311 /* Hook function called after ospf ISM event is occured. And vty's
312 network command invoke this function after making interface
315 ism_timer_set (struct ospf_interface
*oi
)
320 /* First entry point of ospf interface state machine. In this state
321 interface parameters must be set to initial values, and timers are
323 OSPF_ISM_TIMER_OFF (oi
->t_hello
);
324 OSPF_ISM_TIMER_OFF (oi
->t_wait
);
325 OSPF_ISM_TIMER_OFF (oi
->t_ls_ack
);
328 /* In this state, the interface may be looped back and will be
329 unavailable for regular data traffic. */
330 OSPF_ISM_TIMER_OFF (oi
->t_hello
);
331 OSPF_ISM_TIMER_OFF (oi
->t_wait
);
332 OSPF_ISM_TIMER_OFF (oi
->t_ls_ack
);
335 /* The router is trying to determine the identity of DRouter and
336 BDRouter. The router begin to receive and send Hello Packets. */
337 /* send first hello immediately */
338 OSPF_ISM_TIMER_ON (oi
->t_hello
, ospf_hello_timer
, 1);
339 OSPF_ISM_TIMER_ON (oi
->t_wait
, ospf_wait_timer
,
340 OSPF_IF_PARAM (oi
, v_wait
));
341 OSPF_ISM_TIMER_OFF (oi
->t_ls_ack
);
343 case ISM_PointToPoint
:
344 /* The interface connects to a physical Point-to-point network or
345 virtual link. The router attempts to form an adjacency with
346 neighboring router. Hello packets are also sent. */
347 /* send first hello immediately */
348 OSPF_ISM_TIMER_ON (oi
->t_hello
, ospf_hello_timer
, 1);
350 OSPF_ISM_TIMER_OFF (oi
->t_wait
);
351 OSPF_ISM_TIMER_ON (oi
->t_ls_ack
, ospf_ls_ack_timer
, oi
->v_ls_ack
);
354 /* The network type of the interface is broadcast or NBMA network,
355 and the router itself is neither Designated Router nor
356 Backup Designated Router. */
357 OSPF_ISM_TIMER_ON (oi
->t_hello
, ospf_hello_timer
,
358 OSPF_IF_PARAM (oi
, v_hello
));
359 OSPF_ISM_TIMER_OFF (oi
->t_wait
);
360 OSPF_ISM_TIMER_ON (oi
->t_ls_ack
, ospf_ls_ack_timer
, oi
->v_ls_ack
);
363 /* The network type of the interface is broadcast os NBMA network,
364 and the router is Backup Designated Router. */
365 OSPF_ISM_TIMER_ON (oi
->t_hello
, ospf_hello_timer
,
366 OSPF_IF_PARAM (oi
, v_hello
));
367 OSPF_ISM_TIMER_OFF (oi
->t_wait
);
368 OSPF_ISM_TIMER_ON (oi
->t_ls_ack
, ospf_ls_ack_timer
, oi
->v_ls_ack
);
371 /* The network type of the interface is broadcast or NBMA network,
372 and the router is Designated Router. */
373 OSPF_ISM_TIMER_ON (oi
->t_hello
, ospf_hello_timer
,
374 OSPF_IF_PARAM (oi
, v_hello
));
375 OSPF_ISM_TIMER_OFF (oi
->t_wait
);
376 OSPF_ISM_TIMER_ON (oi
->t_ls_ack
, ospf_ls_ack_timer
, oi
->v_ls_ack
);
382 ism_stop (struct ospf_interface
*oi
)
388 ism_interface_up (struct ospf_interface
*oi
)
392 /* if network type is point-to-point, Point-to-MultiPoint or virtual link,
393 the state transitions to Point-to-Point. */
394 if (oi
->type
== OSPF_IFTYPE_POINTOPOINT
||
395 oi
->type
== OSPF_IFTYPE_POINTOMULTIPOINT
||
396 oi
->type
== OSPF_IFTYPE_VIRTUALLINK
)
397 next_state
= ISM_PointToPoint
;
398 /* Else if the router is not eligible to DR, the state transitions to
400 else if (PRIORITY (oi
) == 0) /* router is eligible? */
401 next_state
= ISM_DROther
;
403 /* Otherwise, the state transitions to Waiting. */
404 next_state
= ISM_Waiting
;
406 if (oi
->type
== OSPF_IFTYPE_NBMA
)
407 ospf_nbr_nbma_if_update (oi
->ospf
, oi
);
409 /* ospf_ism_event (t); */
414 ism_loop_ind (struct ospf_interface
*oi
)
418 /* call ism_interface_down. */
419 /* ret = ism_interface_down (oi); */
424 /* Interface down event handler. */
426 ism_interface_down (struct ospf_interface
*oi
)
428 ospf_if_cleanup (oi
);
434 ism_backup_seen (struct ospf_interface
*oi
)
436 return ospf_dr_election (oi
);
440 ism_wait_timer (struct ospf_interface
*oi
)
442 return ospf_dr_election (oi
);
446 ism_neighbor_change (struct ospf_interface
*oi
)
448 return ospf_dr_election (oi
);
452 ism_ignore (struct ospf_interface
*oi
)
454 if (IS_DEBUG_OSPF (ism
, ISM_EVENTS
))
455 zlog (NULL
, LOG_INFO
, "ISM[%s]: ism_ignore called", IF_NAME (oi
));
460 /* Interface State Machine */
464 } ISM
[OSPF_ISM_STATE_MAX
][OSPF_ISM_EVENT_MAX
] =
467 /* DependUpon: dummy state. */
468 { ism_ignore
, ISM_DependUpon
}, /* NoEvent */
469 { ism_ignore
, ISM_DependUpon
}, /* InterfaceUp */
470 { ism_ignore
, ISM_DependUpon
}, /* WaitTimer */
471 { ism_ignore
, ISM_DependUpon
}, /* BackupSeen */
472 { ism_ignore
, ISM_DependUpon
}, /* NeighborChange */
473 { ism_ignore
, ISM_DependUpon
}, /* LoopInd */
474 { ism_ignore
, ISM_DependUpon
}, /* UnloopInd */
475 { ism_ignore
, ISM_DependUpon
}, /* InterfaceDown */
479 { ism_ignore
, ISM_DependUpon
}, /* NoEvent */
480 { ism_interface_up
, ISM_DependUpon
}, /* InterfaceUp */
481 { ism_ignore
, ISM_Down
}, /* WaitTimer */
482 { ism_ignore
, ISM_Down
}, /* BackupSeen */
483 { ism_ignore
, ISM_Down
}, /* NeighborChange */
484 { ism_loop_ind
, ISM_Loopback
}, /* LoopInd */
485 { ism_ignore
, ISM_Down
}, /* UnloopInd */
486 { ism_interface_down
, ISM_Down
}, /* InterfaceDown */
490 { ism_ignore
, ISM_DependUpon
}, /* NoEvent */
491 { ism_ignore
, ISM_Loopback
}, /* InterfaceUp */
492 { ism_ignore
, ISM_Loopback
}, /* WaitTimer */
493 { ism_ignore
, ISM_Loopback
}, /* BackupSeen */
494 { ism_ignore
, ISM_Loopback
}, /* NeighborChange */
495 { ism_ignore
, ISM_Loopback
}, /* LoopInd */
496 { ism_ignore
, ISM_Down
}, /* UnloopInd */
497 { ism_interface_down
, ISM_Down
}, /* InterfaceDown */
501 { ism_ignore
, ISM_DependUpon
}, /* NoEvent */
502 { ism_ignore
, ISM_Waiting
}, /* InterfaceUp */
503 { ism_wait_timer
, ISM_DependUpon
}, /* WaitTimer */
504 { ism_backup_seen
, ISM_DependUpon
}, /* BackupSeen */
505 { ism_ignore
, ISM_Waiting
}, /* NeighborChange */
506 { ism_loop_ind
, ISM_Loopback
}, /* LoopInd */
507 { ism_ignore
, ISM_Waiting
}, /* UnloopInd */
508 { ism_interface_down
, ISM_Down
}, /* InterfaceDown */
511 /* Point-to-Point: */
512 { ism_ignore
, ISM_DependUpon
}, /* NoEvent */
513 { ism_ignore
, ISM_PointToPoint
}, /* InterfaceUp */
514 { ism_ignore
, ISM_PointToPoint
}, /* WaitTimer */
515 { ism_ignore
, ISM_PointToPoint
}, /* BackupSeen */
516 { ism_ignore
, ISM_PointToPoint
}, /* NeighborChange */
517 { ism_loop_ind
, ISM_Loopback
}, /* LoopInd */
518 { ism_ignore
, ISM_PointToPoint
}, /* UnloopInd */
519 { ism_interface_down
, ISM_Down
}, /* InterfaceDown */
523 { ism_ignore
, ISM_DependUpon
}, /* NoEvent */
524 { ism_ignore
, ISM_DROther
}, /* InterfaceUp */
525 { ism_ignore
, ISM_DROther
}, /* WaitTimer */
526 { ism_ignore
, ISM_DROther
}, /* BackupSeen */
527 { ism_neighbor_change
, ISM_DependUpon
}, /* NeighborChange */
528 { ism_loop_ind
, ISM_Loopback
}, /* LoopInd */
529 { ism_ignore
, ISM_DROther
}, /* UnloopInd */
530 { ism_interface_down
, ISM_Down
}, /* InterfaceDown */
534 { ism_ignore
, ISM_DependUpon
}, /* NoEvent */
535 { ism_ignore
, ISM_Backup
}, /* InterfaceUp */
536 { ism_ignore
, ISM_Backup
}, /* WaitTimer */
537 { ism_ignore
, ISM_Backup
}, /* BackupSeen */
538 { ism_neighbor_change
, ISM_DependUpon
}, /* NeighborChange */
539 { ism_loop_ind
, ISM_Loopback
}, /* LoopInd */
540 { ism_ignore
, ISM_Backup
}, /* UnloopInd */
541 { ism_interface_down
, ISM_Down
}, /* InterfaceDown */
545 { ism_ignore
, ISM_DependUpon
}, /* NoEvent */
546 { ism_ignore
, ISM_DR
}, /* InterfaceUp */
547 { ism_ignore
, ISM_DR
}, /* WaitTimer */
548 { ism_ignore
, ISM_DR
}, /* BackupSeen */
549 { ism_neighbor_change
, ISM_DependUpon
}, /* NeighborChange */
550 { ism_loop_ind
, ISM_Loopback
}, /* LoopInd */
551 { ism_ignore
, ISM_DR
}, /* UnloopInd */
552 { ism_interface_down
, ISM_Down
}, /* InterfaceDown */
556 static char *ospf_ism_event_str
[] =
569 ism_change_state (struct ospf_interface
*oi
, int state
)
572 struct ospf_lsa
*lsa
;
574 /* Logging change of state. */
575 if (IS_DEBUG_OSPF (ism
, ISM_STATUS
))
576 zlog (NULL
, LOG_INFO
, "ISM[%s]: State change %s -> %s", IF_NAME (oi
),
577 LOOKUP (ospf_ism_state_msg
, oi
->state
),
578 LOOKUP (ospf_ism_state_msg
, state
));
580 old_state
= oi
->state
;
584 if (old_state
== ISM_Down
|| state
== ISM_Down
)
585 ospf_check_abr_status (oi
->ospf
);
587 /* Originate router-LSA. */
590 if (state
== ISM_Down
)
592 if (oi
->area
->act_ints
> 0)
593 oi
->area
->act_ints
--;
595 else if (old_state
== ISM_Down
)
596 oi
->area
->act_ints
++;
598 /* schedule router-LSA originate. */
599 ospf_router_lsa_timer_add (oi
->area
);
602 /* Originate network-LSA. */
603 if (old_state
!= ISM_DR
&& state
== ISM_DR
)
604 ospf_network_lsa_timer_add (oi
);
605 else if (old_state
== ISM_DR
&& state
!= ISM_DR
)
607 /* Free self originated network LSA. */
608 lsa
= oi
->network_lsa_self
;
611 ospf_lsa_flush_area (lsa
, oi
->area
);
612 OSPF_TIMER_OFF (oi
->t_network_lsa_self
);
615 ospf_lsa_unlock (oi
->network_lsa_self
);
616 oi
->network_lsa_self
= NULL
;
619 #ifdef HAVE_OPAQUE_LSA
620 ospf_opaque_ism_change (oi
, old_state
);
621 #endif /* HAVE_OPAQUE_LSA */
623 /* Check area border status. */
624 ospf_check_abr_status (oi
->ospf
);
627 /* Execute ISM event process. */
629 ospf_ism_event (struct thread
*thread
)
633 struct ospf_interface
*oi
;
635 oi
= THREAD_ARG (thread
);
636 event
= THREAD_VAL (thread
);
639 next_state
= (*(ISM
[oi
->state
][event
].func
))(oi
);
642 next_state
= ISM
[oi
->state
][event
].next_state
;
644 if (IS_DEBUG_OSPF (ism
, ISM_EVENTS
))
645 zlog (NULL
, LOG_INFO
, "ISM[%s]: %s (%s)", IF_NAME (oi
),
646 LOOKUP (ospf_ism_state_msg
, oi
->state
),
647 ospf_ism_event_str
[event
]);
649 /* If state is changed. */
650 if (next_state
!= oi
->state
)
651 ism_change_state (oi
, next_state
);
653 /* Make sure timer is set. */