2 Copyright (C) 2001 IP Infusion Inc.
4 This file is part of GNU Zebra.
6 GNU Zebra is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
11 GNU Zebra is distributed in the hope that it will be useful, but
12 WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU Zebra; see the file COPYING. If not, write to the Free
18 Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
31 #include "bgpd/bgpd.h"
32 #include "bgpd/bgp_damp.h"
33 #include "bgpd/bgp_table.h"
34 #include "bgpd/bgp_route.h"
35 #include "bgpd/bgp_attr.h"
36 #include "bgpd/bgp_advertise.h"
38 /* Global variable to access damping configuration */
39 struct bgp_damp_config bgp_damp_cfg
;
40 static struct bgp_damp_config
*damp
= &bgp_damp_cfg
;
42 /* Utility macro to add and delete BGP dampening information to no
44 #define BGP_DAMP_LIST_ADD(N,A) BGP_INFO_ADD(N,A,no_reuse_list)
45 #define BGP_DAMP_LIST_DEL(N,A) BGP_INFO_DEL(N,A,no_reuse_list)
47 /* Calculate reuse list index by penalty value. */
49 bgp_reuse_index (int penalty
)
54 i
= (int)(((double) penalty
/ damp
->reuse_limit
- 1.0) * damp
->scale_factor
);
56 if ( i
>= damp
->reuse_index_size
)
57 i
= damp
->reuse_index_size
- 1;
59 index
= damp
->reuse_index
[i
] - damp
->reuse_index
[0];
61 return (damp
->reuse_offset
+ index
) % damp
->reuse_list_size
;
64 /* Add BGP dampening information to reuse list. */
66 bgp_reuse_list_add (struct bgp_damp_info
*bdi
)
70 index
= bdi
->index
= bgp_reuse_index (bdi
->penalty
);
73 bdi
->next
= damp
->reuse_list
[index
];
74 if (damp
->reuse_list
[index
])
75 damp
->reuse_list
[index
]->prev
= bdi
;
76 damp
->reuse_list
[index
] = bdi
;
79 /* Delete BGP dampening information from reuse list. */
81 bgp_reuse_list_delete (struct bgp_damp_info
*bdi
)
84 bdi
->next
->prev
= bdi
->prev
;
86 bdi
->prev
->next
= bdi
->next
;
88 damp
->reuse_list
[bdi
->index
] = bdi
->next
;
91 /* Return decayed penalty value. */
93 bgp_damp_decay (time_t tdiff
, int penalty
)
97 i
= (int) ((double) tdiff
/ DELTA_T
);
102 if (i
>= damp
->decay_array_size
)
105 return (int) (penalty
* damp
->decay_array
[i
]);
108 /* Handler of reuse timer event. Each route in the current reuse-list
109 is evaluated. RFC2439 Section 4.8.7. */
111 bgp_reuse_timer (struct thread
*t
)
113 struct bgp_damp_info
*bdi
;
114 struct bgp_damp_info
*next
;
115 time_t t_now
, t_diff
;
117 damp
->t_reuse
= NULL
;
119 thread_add_timer (master
, bgp_reuse_timer
, NULL
, DELTA_REUSE
);
121 t_now
= bgp_clock ();
123 /* 1. save a pointer to the current zeroth queue head and zero the
125 bdi
= damp
->reuse_list
[damp
->reuse_offset
];
126 damp
->reuse_list
[damp
->reuse_offset
] = NULL
;
128 /* 2. set offset = modulo reuse-list-size ( offset + 1 ), thereby
129 rotating the circular queue of list-heads. */
130 damp
->reuse_offset
= (damp
->reuse_offset
+ 1) % damp
->reuse_list_size
;
132 /* 3. if ( the saved list head pointer is non-empty ) */
133 for (; bdi
; bdi
= next
)
135 struct bgp
*bgp
= bdi
->binfo
->peer
->bgp
;
139 /* Set t-diff = t-now - t-updated. */
140 t_diff
= t_now
- bdi
->t_updated
;
142 /* Set figure-of-merit = figure-of-merit * decay-array-ok [t-diff] */
143 bdi
->penalty
= bgp_damp_decay (t_diff
, bdi
->penalty
);
145 /* Set t-updated = t-now. */
146 bdi
->t_updated
= t_now
;
148 /* if (figure-of-merit < reuse). */
149 if (bdi
->penalty
< damp
->reuse_limit
)
151 /* Reuse the route. */
152 bgp_info_unset_flag (bdi
->rn
, bdi
->binfo
, BGP_INFO_DAMPED
);
153 bdi
->suppress_time
= 0;
155 if (bdi
->lastrecord
== BGP_RECORD_UPDATE
)
157 bgp_info_unset_flag (bdi
->rn
, bdi
->binfo
, BGP_INFO_HISTORY
);
158 bgp_aggregate_increment (bgp
, &bdi
->rn
->p
, bdi
->binfo
,
159 bdi
->afi
, bdi
->safi
);
160 bgp_process (bgp
, bdi
->rn
, bdi
->afi
, bdi
->safi
);
163 if (bdi
->penalty
<= damp
->reuse_limit
/ 2.0)
164 bgp_damp_info_free (bdi
, 1);
166 BGP_DAMP_LIST_ADD (damp
, bdi
);
169 /* Re-insert into another list (See RFC2439 Section 4.8.6). */
170 bgp_reuse_list_add (bdi
);
176 /* A route becomes unreachable (RFC2439 Section 4.8.2). */
178 bgp_damp_withdraw (struct bgp_info
*binfo
, struct bgp_node
*rn
,
179 afi_t afi
, safi_t safi
, int attr_change
)
182 struct bgp_damp_info
*bdi
= NULL
;
183 double last_penalty
= 0;
185 t_now
= bgp_clock ();
187 /* Processing Unreachable Messages. */
189 bdi
= binfo
->extra
->damp_info
;
193 /* If there is no previous stability history. */
196 1. allocate a damping structure.
197 2. set figure-of-merit = 1.
198 3. withdraw the route. */
200 bdi
= XCALLOC (MTYPE_BGP_DAMP_INFO
, sizeof (struct bgp_damp_info
));
203 bdi
->penalty
= (attr_change
? DEFAULT_PENALTY
/ 2 : DEFAULT_PENALTY
);
205 bdi
->start_time
= t_now
;
206 bdi
->suppress_time
= 0;
210 (bgp_info_extra_get (binfo
))->damp_info
= bdi
;
211 BGP_DAMP_LIST_ADD (damp
, bdi
);
215 last_penalty
= bdi
->penalty
;
217 /* 1. Set t-diff = t-now - t-updated. */
219 (bgp_damp_decay (t_now
- bdi
->t_updated
, bdi
->penalty
)
220 + (attr_change
? DEFAULT_PENALTY
/ 2 : DEFAULT_PENALTY
));
222 if (bdi
->penalty
> damp
->ceiling
)
223 bdi
->penalty
= damp
->ceiling
;
228 assert ((rn
== bdi
->rn
) && (binfo
== bdi
->binfo
));
230 bdi
->lastrecord
= BGP_RECORD_WITHDRAW
;
231 bdi
->t_updated
= t_now
;
233 /* Make this route as historical status. */
234 bgp_info_set_flag (rn
, binfo
, BGP_INFO_HISTORY
);
236 /* Remove the route from a reuse list if it is on one. */
237 if (CHECK_FLAG (bdi
->binfo
->flags
, BGP_INFO_DAMPED
))
239 /* If decay rate isn't equal to 0, reinsert brn. */
240 if (bdi
->penalty
!= last_penalty
)
242 bgp_reuse_list_delete (bdi
);
243 bgp_reuse_list_add (bdi
);
245 return BGP_DAMP_SUPPRESSED
;
248 /* If not suppressed before, do annonunce this withdraw and
249 insert into reuse_list. */
250 if (bdi
->penalty
>= damp
->suppress_value
)
252 bgp_info_set_flag (rn
, binfo
, BGP_INFO_DAMPED
);
253 bdi
->suppress_time
= t_now
;
254 BGP_DAMP_LIST_DEL (damp
, bdi
);
255 bgp_reuse_list_add (bdi
);
258 return BGP_DAMP_USED
;
262 bgp_damp_update (struct bgp_info
*binfo
, struct bgp_node
*rn
,
263 afi_t afi
, safi_t safi
)
266 struct bgp_damp_info
*bdi
;
269 if (!binfo
->extra
|| !((bdi
= binfo
->extra
->damp_info
)))
270 return BGP_DAMP_USED
;
272 t_now
= bgp_clock ();
273 bgp_info_unset_flag (rn
, binfo
, BGP_INFO_HISTORY
);
275 bdi
->lastrecord
= BGP_RECORD_UPDATE
;
276 bdi
->penalty
= bgp_damp_decay (t_now
- bdi
->t_updated
, bdi
->penalty
);
278 if (! CHECK_FLAG (bdi
->binfo
->flags
, BGP_INFO_DAMPED
)
279 && (bdi
->penalty
< damp
->suppress_value
))
280 status
= BGP_DAMP_USED
;
281 else if (CHECK_FLAG (bdi
->binfo
->flags
, BGP_INFO_DAMPED
)
282 && (bdi
->penalty
< damp
->reuse_limit
) )
284 bgp_info_unset_flag (rn
, binfo
, BGP_INFO_DAMPED
);
285 bgp_reuse_list_delete (bdi
);
286 BGP_DAMP_LIST_ADD (damp
, bdi
);
287 bdi
->suppress_time
= 0;
288 status
= BGP_DAMP_USED
;
291 status
= BGP_DAMP_SUPPRESSED
;
293 if (bdi
->penalty
> damp
->reuse_limit
/ 2.0)
294 bdi
->t_updated
= t_now
;
296 bgp_damp_info_free (bdi
, 0);
301 /* Remove dampening information and history route. */
303 bgp_damp_scan (struct bgp_info
*binfo
, afi_t afi
, safi_t safi
)
305 time_t t_now
, t_diff
;
306 struct bgp_damp_info
*bdi
;
308 assert (binfo
->extra
&& binfo
->extra
->damp_info
);
310 t_now
= bgp_clock ();
311 bdi
= binfo
->extra
->damp_info
;
313 if (CHECK_FLAG (binfo
->flags
, BGP_INFO_DAMPED
))
315 t_diff
= t_now
- bdi
->suppress_time
;
317 if (t_diff
>= damp
->max_suppress_time
)
319 bgp_info_unset_flag (bdi
->rn
, binfo
, BGP_INFO_DAMPED
);
320 bgp_reuse_list_delete (bdi
);
321 BGP_DAMP_LIST_ADD (damp
, bdi
);
322 bdi
->penalty
= damp
->reuse_limit
;
323 bdi
->suppress_time
= 0;
324 bdi
->t_updated
= t_now
;
326 /* Need to announce UPDATE once this binfo is usable again. */
327 if (bdi
->lastrecord
== BGP_RECORD_UPDATE
)
335 t_diff
= t_now
- bdi
->t_updated
;
336 bdi
->penalty
= bgp_damp_decay (t_diff
, bdi
->penalty
);
338 if (bdi
->penalty
<= damp
->reuse_limit
/ 2.0)
340 /* release the bdi, bdi->binfo. */
341 bgp_damp_info_free (bdi
, 1);
345 bdi
->t_updated
= t_now
;
351 bgp_damp_info_free (struct bgp_damp_info
*bdi
, int withdraw
)
353 struct bgp_info
*binfo
;
359 binfo
->extra
->damp_info
= NULL
;
361 if (CHECK_FLAG (binfo
->flags
, BGP_INFO_DAMPED
))
362 bgp_reuse_list_delete (bdi
);
364 BGP_DAMP_LIST_DEL (damp
, bdi
);
366 bgp_info_unset_flag (bdi
->rn
, binfo
, BGP_INFO_HISTORY
|BGP_INFO_DAMPED
);
368 if (bdi
->lastrecord
== BGP_RECORD_WITHDRAW
&& withdraw
)
369 bgp_info_delete (bdi
->rn
, binfo
);
371 XFREE (MTYPE_BGP_DAMP_INFO
, bdi
);
375 bgp_damp_parameter_set (int hlife
, int reuse
, int sup
, int maxsup
)
377 double reuse_max_ratio
;
381 damp
->suppress_value
= sup
;
382 damp
->half_life
= hlife
;
383 damp
->reuse_limit
= reuse
;
384 damp
->max_suppress_time
= maxsup
;
386 /* Initialize params per bgp_damp_config. */
387 damp
->reuse_index_size
= REUSE_ARRAY_SIZE
;
389 damp
->ceiling
= (int)(damp
->reuse_limit
* (pow(2, (double)damp
->max_suppress_time
/damp
->half_life
)));
391 /* Decay-array computations */
392 damp
->decay_array_size
= ceil ((double) damp
->max_suppress_time
/ DELTA_T
);
393 damp
->decay_array
= XMALLOC (MTYPE_BGP_DAMP_ARRAY
,
394 sizeof(double) * (damp
->decay_array_size
));
395 damp
->decay_array
[0] = 1.0;
396 damp
->decay_array
[1] = exp ((1.0/((double)damp
->half_life
/DELTA_T
)) * log(0.5));
398 /* Calculate decay values for all possible times */
399 for (i
= 2; i
< damp
->decay_array_size
; i
++)
400 damp
->decay_array
[i
] = damp
->decay_array
[i
-1] * damp
->decay_array
[1];
402 /* Reuse-list computations */
403 i
= ceil ((double)damp
->max_suppress_time
/ DELTA_REUSE
) + 1;
404 if (i
> REUSE_LIST_SIZE
|| i
== 0)
406 damp
->reuse_list_size
= i
;
408 damp
->reuse_list
= XCALLOC (MTYPE_BGP_DAMP_ARRAY
,
409 damp
->reuse_list_size
410 * sizeof (struct bgp_reuse_node
*));
412 /* Reuse-array computations */
413 damp
->reuse_index
= XCALLOC (MTYPE_BGP_DAMP_ARRAY
,
414 sizeof(int) * damp
->reuse_index_size
);
416 reuse_max_ratio
= (double)damp
->ceiling
/damp
->reuse_limit
;
417 j
= (exp((double)damp
->max_suppress_time
/damp
->half_life
) * log10(2.0));
418 if ( reuse_max_ratio
> j
&& j
!= 0 )
421 damp
->scale_factor
= (double)damp
->reuse_index_size
/(reuse_max_ratio
- 1);
423 for (i
= 0; i
< damp
->reuse_index_size
; i
++)
425 damp
->reuse_index
[i
] =
426 (int)(((double)damp
->half_life
/ DELTA_REUSE
)
427 * log10 (1.0 / (damp
->reuse_limit
* ( 1.0 + ((double)i
/damp
->scale_factor
)))) / log10(0.5));
432 bgp_damp_enable (struct bgp
*bgp
, afi_t afi
, safi_t safi
, time_t half
,
433 unsigned int reuse
, unsigned int suppress
, time_t max
)
435 if (CHECK_FLAG (bgp
->af_flags
[afi
][safi
], BGP_CONFIG_DAMPENING
))
437 if (damp
->half_life
== half
438 && damp
->reuse_limit
== reuse
439 && damp
->suppress_value
== suppress
440 && damp
->max_suppress_time
== max
)
442 bgp_damp_disable (bgp
, afi
, safi
);
445 SET_FLAG (bgp
->af_flags
[afi
][safi
], BGP_CONFIG_DAMPENING
);
446 bgp_damp_parameter_set (half
, reuse
, suppress
, max
);
448 /* Register reuse timer. */
451 thread_add_timer (master
, bgp_reuse_timer
, NULL
, DELTA_REUSE
);
457 bgp_damp_config_clean (struct bgp_damp_config
*damp
)
459 /* Free decay array */
460 XFREE (MTYPE_BGP_DAMP_ARRAY
, damp
->decay_array
);
462 /* Free reuse index array */
463 XFREE (MTYPE_BGP_DAMP_ARRAY
, damp
->reuse_index
);
465 /* Free reuse list array. */
466 XFREE (MTYPE_BGP_DAMP_ARRAY
, damp
->reuse_list
);
469 /* Clean all the bgp_damp_info stored in reuse_list. */
471 bgp_damp_info_clean (void)
474 struct bgp_damp_info
*bdi
, *next
;
476 damp
->reuse_offset
= 0;
478 for (i
= 0; i
< damp
->reuse_list_size
; i
++)
480 if (! damp
->reuse_list
[i
])
483 for (bdi
= damp
->reuse_list
[i
]; bdi
; bdi
= next
)
486 bgp_damp_info_free (bdi
, 1);
488 damp
->reuse_list
[i
] = NULL
;
491 for (bdi
= damp
->no_reuse_list
; bdi
; bdi
= next
)
494 bgp_damp_info_free (bdi
, 1);
496 damp
->no_reuse_list
= NULL
;
500 bgp_damp_disable (struct bgp
*bgp
, afi_t afi
, safi_t safi
)
502 /* If it wasn't enabled, there's nothing to do. */
503 if (! CHECK_FLAG (bgp
->af_flags
[afi
][safi
], BGP_CONFIG_DAMPENING
))
506 /* Cancel reuse thread. */
508 thread_cancel (damp
->t_reuse
);
509 damp
->t_reuse
= NULL
;
511 /* Clean BGP dampening information. */
512 bgp_damp_info_clean ();
514 /* Clear configuration */
515 bgp_damp_config_clean (&bgp_damp_cfg
);
517 UNSET_FLAG (bgp
->af_flags
[afi
][safi
], BGP_CONFIG_DAMPENING
);
522 bgp_config_write_damp (struct vty
*vty
)
524 if (bgp_damp_cfg
.half_life
== DEFAULT_HALF_LIFE
*60
525 && bgp_damp_cfg
.reuse_limit
== DEFAULT_REUSE
526 && bgp_damp_cfg
.suppress_value
== DEFAULT_SUPPRESS
527 && bgp_damp_cfg
.max_suppress_time
== bgp_damp_cfg
.half_life
*4)
528 vty_out (vty
, " bgp dampening%s", VTY_NEWLINE
);
529 else if (bgp_damp_cfg
.half_life
!= DEFAULT_HALF_LIFE
*60
530 && bgp_damp_cfg
.reuse_limit
== DEFAULT_REUSE
531 && bgp_damp_cfg
.suppress_value
== DEFAULT_SUPPRESS
532 && bgp_damp_cfg
.max_suppress_time
== bgp_damp_cfg
.half_life
*4)
533 vty_out (vty
, " bgp dampening %ld%s",
534 bgp_damp_cfg
.half_life
/60,
537 vty_out (vty
, " bgp dampening %ld %d %d %ld%s",
538 bgp_damp_cfg
.half_life
/60,
539 bgp_damp_cfg
.reuse_limit
,
540 bgp_damp_cfg
.suppress_value
,
541 bgp_damp_cfg
.max_suppress_time
/60,
546 bgp_get_reuse_time (unsigned int penalty
, char *buf
, size_t len
)
548 time_t reuse_time
= 0;
549 struct tm
*tm
= NULL
;
551 if (penalty
> damp
->reuse_limit
)
553 reuse_time
= (int) (DELTA_T
* ((log((double)damp
->reuse_limit
/penalty
))/(log(damp
->decay_array
[1]))));
555 if (reuse_time
> damp
->max_suppress_time
)
556 reuse_time
= damp
->max_suppress_time
;
558 tm
= gmtime (&reuse_time
);
563 /* Making formatted timer strings. */
564 #define ONE_DAY_SECOND 60*60*24
565 #define ONE_WEEK_SECOND 60*60*24*7
567 snprintf (buf
, len
, "00:00:00");
568 else if (reuse_time
< ONE_DAY_SECOND
)
569 snprintf (buf
, len
, "%02d:%02d:%02d",
570 tm
->tm_hour
, tm
->tm_min
, tm
->tm_sec
);
571 else if (reuse_time
< ONE_WEEK_SECOND
)
572 snprintf (buf
, len
, "%dd%02dh%02dm",
573 tm
->tm_yday
, tm
->tm_hour
, tm
->tm_min
);
575 snprintf (buf
, len
, "%02dw%dd%02dh",
576 tm
->tm_yday
/7, tm
->tm_yday
- ((tm
->tm_yday
/7) * 7), tm
->tm_hour
);
582 bgp_damp_info_vty (struct vty
*vty
, struct bgp_info
*binfo
)
584 struct bgp_damp_info
*bdi
;
585 time_t t_now
, t_diff
;
586 char timebuf
[BGP_UPTIME_LEN
];
592 /* BGP dampening information. */
593 bdi
= binfo
->extra
->damp_info
;
595 /* If dampening is not enabled or there is no dampening information,
596 return immediately. */
600 /* Calculate new penalty. */
601 t_now
= bgp_clock ();
602 t_diff
= t_now
- bdi
->t_updated
;
603 penalty
= bgp_damp_decay (t_diff
, bdi
->penalty
);
605 vty_out (vty
, " Dampinfo: penalty %d, flapped %d times in %s",
607 peer_uptime (bdi
->start_time
, timebuf
, BGP_UPTIME_LEN
));
609 if (CHECK_FLAG (binfo
->flags
, BGP_INFO_DAMPED
)
610 && ! CHECK_FLAG (binfo
->flags
, BGP_INFO_HISTORY
))
611 vty_out (vty
, ", reuse in %s",
612 bgp_get_reuse_time (penalty
, timebuf
, BGP_UPTIME_LEN
));
614 vty_out (vty
, "%s", VTY_NEWLINE
);
618 bgp_damp_reuse_time_vty (struct vty
*vty
, struct bgp_info
*binfo
,
619 char *timebuf
, size_t len
)
621 struct bgp_damp_info
*bdi
;
622 time_t t_now
, t_diff
;
628 /* BGP dampening information. */
629 bdi
= binfo
->extra
->damp_info
;
631 /* If dampening is not enabled or there is no dampening information,
632 return immediately. */
636 /* Calculate new penalty. */
637 t_now
= bgp_clock ();
638 t_diff
= t_now
- bdi
->t_updated
;
639 penalty
= bgp_damp_decay (t_diff
, bdi
->penalty
);
641 return bgp_get_reuse_time (penalty
, timebuf
, len
);