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
30 #include "bgpd/bgpd.h"
31 #include "bgpd/bgp_damp.h"
32 #include "bgpd/bgp_table.h"
33 #include "bgpd/bgp_route.h"
34 #include "bgpd/bgp_attr.h"
35 #include "bgpd/bgp_advertise.h"
37 /* Global variable to access damping configuration */
38 struct bgp_damp_config bgp_damp_cfg;
39 struct bgp_damp_config *damp = &bgp_damp_cfg;
41 /* Utility macro to add and delete BGP dampening information to no
43 #define BGP_DAMP_LIST_ADD(N,A) BGP_INFO_ADD(N,A,no_reuse_list)
44 #define BGP_DAMP_LIST_DEL(N,A) BGP_INFO_DEL(N,A,no_reuse_list)
46 /* Calculate reuse list index by penalty value. */
48 bgp_reuse_index (int penalty)
53 i = (int)(((double) penalty / damp->reuse_limit - 1.0) * damp->scale_factor);
55 if ( i >= damp->reuse_index_size )
56 i = damp->reuse_index_size - 1;
58 index = damp->reuse_index[i] - damp->reuse_index[0];
60 return (damp->reuse_offset + index) % damp->reuse_list_size;
63 /* Add BGP dampening information to reuse list. */
65 bgp_reuse_list_add (struct bgp_damp_info *bdi)
69 index = bdi->index = bgp_reuse_index (bdi->penalty);
72 bdi->next = damp->reuse_list[index];
73 if (damp->reuse_list[index])
74 damp->reuse_list[index]->prev = bdi;
75 damp->reuse_list[index] = bdi;
78 /* Delete BGP dampening information from reuse list. */
80 bgp_reuse_list_delete (struct bgp_damp_info *bdi)
83 bdi->next->prev = bdi->prev;
85 bdi->prev->next = bdi->next;
87 damp->reuse_list[bdi->index] = bdi->next;
90 /* Return decayed penalty value. */
92 bgp_damp_decay (time_t tdiff, int penalty)
96 i = (int) ((double) tdiff / DELTA_T);
101 if (i >= damp->decay_array_size)
104 return (int) (penalty * damp->decay_array[i]);
107 /* Handler of reuse timer event. Each route in the current reuse-list
108 is evaluated. RFC2439 Section 4.8.7. */
110 bgp_reuse_timer (struct thread *t)
112 struct bgp_damp_info *bdi;
113 struct bgp_damp_info *next;
114 time_t t_now, t_diff;
116 int bgp_process (struct bgp *, struct bgp_node *, afi_t, safi_t);
118 damp->t_reuse = NULL;
120 thread_add_timer (master, bgp_reuse_timer, NULL, DELTA_REUSE);
122 bgp = bgp_get_default ();
128 /* 1. save a pointer to the current zeroth queue head and zero the
130 bdi = damp->reuse_list[damp->reuse_offset];
131 damp->reuse_list[damp->reuse_offset] = NULL;
133 /* 2. set offset = modulo reuse-list-size ( offset + 1 ), thereby
134 rotating the circular queue of list-heads. */
135 damp->reuse_offset = (damp->reuse_offset + 1) % damp->reuse_list_size;
137 /* 3. if ( the saved list head pointer is non-empty ) */
138 for (; bdi; bdi = next)
142 /* Set t-diff = t-now - t-updated. */
143 t_diff = t_now - bdi->t_updated;
145 /* Set figure-of-merit = figure-of-merit * decay-array-ok [t-diff] */
146 bdi->penalty = bgp_damp_decay (t_diff, bdi->penalty);
148 /* Set t-updated = t-now. */
149 bdi->t_updated = t_now;
151 /* if (figure-of-merit < reuse). */
152 if (bdi->penalty < damp->reuse_limit)
154 /* Reuse the route. */
155 UNSET_FLAG (bdi->binfo->flags, BGP_INFO_DAMPED);
156 bdi->suppress_time = 0;
158 if (bdi->lastrecord == BGP_RECORD_UPDATE)
160 UNSET_FLAG (bdi->binfo->flags, BGP_INFO_HISTORY);
161 bgp_aggregate_increment (bgp, &bdi->rn->p, bdi->binfo,
162 bdi->afi, bdi->safi);
163 bgp_process (bgp, bdi->rn, bdi->afi, bdi->safi);
166 if (bdi->penalty <= damp->reuse_limit / 2.0)
167 bgp_damp_info_free (bdi, 1);
169 BGP_DAMP_LIST_ADD (damp, bdi);
172 /* Re-insert into another list (See RFC2439 Section 4.8.6). */
173 bgp_reuse_list_add (bdi);
179 /* A route becomes unreachable (RFC2439 Section 4.8.2). */
181 bgp_damp_withdraw (struct bgp_info *binfo, struct bgp_node *rn,
182 afi_t afi, safi_t safi, int attr_change)
185 struct bgp_damp_info *bdi;
186 double last_penalty = 0;
190 /* Processing Unreachable Messages. */
191 bdi = binfo->damp_info;
195 /* If there is no previous stability history. */
198 1. allocate a damping structure.
199 2. set figure-of-merit = 1.
200 3. withdraw the route. */
202 bdi = XCALLOC (MTYPE_BGP_DAMP_INFO, sizeof (struct bgp_damp_info));
205 bdi->penalty = (attr_change ? DEFAULT_PENALTY / 2 : DEFAULT_PENALTY);
207 bdi->start_time = t_now;
208 bdi->suppress_time = 0;
212 binfo->damp_info = bdi;
213 BGP_DAMP_LIST_ADD (damp, bdi);
217 last_penalty = bdi->penalty;
219 /* 1. Set t-diff = t-now - t-updated. */
221 (bgp_damp_decay (t_now - bdi->t_updated, bdi->penalty)
222 + (attr_change ? DEFAULT_PENALTY / 2 : DEFAULT_PENALTY));
224 if (bdi->penalty > damp->ceiling)
225 bdi->penalty = damp->ceiling;
230 bdi->lastrecord = BGP_RECORD_WITHDRAW;
231 bdi->t_updated = t_now;
233 /* Make this route as historical status. */
234 SET_FLAG (binfo->flags, 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 SET_FLAG (bdi->binfo->flags, 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 bdi = binfo->damp_info;
271 return BGP_DAMP_USED;
274 UNSET_FLAG (binfo->flags, BGP_INFO_HISTORY);
276 bdi->lastrecord = BGP_RECORD_UPDATE;
277 bdi->penalty = bgp_damp_decay (t_now - bdi->t_updated, bdi->penalty);
279 if (! CHECK_FLAG (bdi->binfo->flags, BGP_INFO_DAMPED)
280 && (bdi->penalty < damp->suppress_value))
281 status = BGP_DAMP_USED;
282 else if (CHECK_FLAG (bdi->binfo->flags, BGP_INFO_DAMPED)
283 && (bdi->penalty < damp->reuse_limit) )
285 UNSET_FLAG (bdi->binfo->flags, BGP_INFO_DAMPED);
286 bgp_reuse_list_delete (bdi);
287 BGP_DAMP_LIST_ADD (damp, bdi);
288 bdi->suppress_time = 0;
289 status = BGP_DAMP_USED;
292 status = BGP_DAMP_SUPPRESSED;
294 if (bdi->penalty > damp->reuse_limit / 2.0)
295 bdi->t_updated = t_now;
297 bgp_damp_info_free (bdi, 0);
302 /* Remove dampening information and history route. */
304 bgp_damp_scan (struct bgp_info *binfo, afi_t afi, safi_t safi)
306 time_t t_now, t_diff;
307 struct bgp_damp_info *bdi;
310 bdi = binfo->damp_info;
312 if (CHECK_FLAG (binfo->flags, BGP_INFO_DAMPED))
314 t_diff = t_now - bdi->suppress_time;
316 if (t_diff >= damp->max_suppress_time)
318 UNSET_FLAG (binfo->flags, BGP_INFO_DAMPED);
319 bgp_reuse_list_delete (bdi);
320 BGP_DAMP_LIST_ADD (damp, bdi);
321 bdi->penalty = damp->reuse_limit;
322 bdi->suppress_time = 0;
323 bdi->t_updated = t_now;
325 /* Need to announce UPDATE once this binfo is usable again. */
326 if (bdi->lastrecord == BGP_RECORD_UPDATE)
334 t_diff = t_now - bdi->t_updated;
335 bdi->penalty = bgp_damp_decay (t_diff, bdi->penalty);
337 if (bdi->penalty <= damp->reuse_limit / 2.0)
339 /* release the bdi, bdi->binfo. */
340 bgp_damp_info_free (bdi, 1);
344 bdi->t_updated = t_now;
350 bgp_damp_info_free (struct bgp_damp_info *bdi, int withdraw)
352 struct bgp_info *binfo;
353 void bgp_info_delete (struct bgp_node *, struct bgp_info *);
354 void bgp_info_free (struct bgp_info *);
360 binfo->damp_info = NULL;
362 if (CHECK_FLAG (binfo->flags, BGP_INFO_DAMPED))
363 bgp_reuse_list_delete (bdi);
365 BGP_DAMP_LIST_DEL (damp, bdi);
367 UNSET_FLAG (binfo->flags, BGP_INFO_DAMPED);
368 UNSET_FLAG (binfo->flags, BGP_INFO_HISTORY);
370 if (bdi->lastrecord == BGP_RECORD_WITHDRAW && withdraw)
372 bgp_info_delete (bdi->rn, binfo);
373 bgp_info_free (binfo);
374 bgp_unlock_node (bdi->rn);
376 XFREE (MTYPE_BGP_DAMP_INFO, bdi);
380 bgp_damp_parameter_set (int hlife, int reuse, int sup, int maxsup)
382 double reuse_max_ratio;
386 damp->suppress_value = sup;
387 damp->half_life = hlife;
388 damp->reuse_limit = reuse;
389 damp->max_suppress_time = maxsup;
391 /* Initialize params per bgp_damp_config. */
392 damp->reuse_index_size = REUSE_ARRAY_SIZE;
394 damp->ceiling = (int)(damp->reuse_limit * (pow(2, (double)damp->max_suppress_time/damp->half_life)));
396 /* Decay-array computations */
397 damp->decay_array_size = ceil ((double) damp->max_suppress_time / DELTA_T);
398 damp->decay_array = XMALLOC (MTYPE_BGP_DAMP_ARRAY,
399 sizeof(double) * (damp->decay_array_size));
400 damp->decay_array[0] = 1.0;
401 damp->decay_array[1] = exp ((1.0/((double)damp->half_life/DELTA_T)) * log(0.5));
403 /* Calculate decay values for all possible times */
404 for (i = 2; i < damp->decay_array_size; i++)
405 damp->decay_array[i] = damp->decay_array[i-1] * damp->decay_array[1];
407 /* Reuse-list computations */
408 i = ceil ((double)damp->max_suppress_time / DELTA_REUSE) + 1;
409 if (i > REUSE_LIST_SIZE || i == 0)
411 damp->reuse_list_size = i;
413 damp->reuse_list = XCALLOC (MTYPE_BGP_DAMP_ARRAY,
414 damp->reuse_list_size
415 * sizeof (struct bgp_reuse_node *));
416 memset (damp->reuse_list, 0x00,
417 damp->reuse_list_size * sizeof (struct bgp_reuse_node *));
419 /* Reuse-array computations */
420 damp->reuse_index = XMALLOC (MTYPE_BGP_DAMP_ARRAY,
421 sizeof(int) * damp->reuse_index_size);
422 memset (damp->reuse_index, 0x00,
423 damp->reuse_list_size * sizeof (int));
425 reuse_max_ratio = (double)damp->ceiling/damp->reuse_limit;
426 j = (exp((double)damp->max_suppress_time/damp->half_life) * log10(2.0));
427 if ( reuse_max_ratio > j && j != 0 )
430 damp->scale_factor = (double)damp->reuse_index_size/(reuse_max_ratio - 1);
432 for (i = 0; i < damp->reuse_index_size; i++)
434 damp->reuse_index[i] =
435 (int)(((double)damp->half_life / DELTA_REUSE)
436 * log10 (1.0 / (damp->reuse_limit * ( 1.0 + ((double)i/damp->scale_factor)))) / log10(0.5));
441 bgp_damp_enable (struct bgp *bgp, afi_t afi, safi_t safi, int half,
442 int reuse, int suppress, int max)
444 if (CHECK_FLAG (bgp->af_flags[afi][safi], BGP_CONFIG_DAMPENING))
446 if (damp->half_life == half
447 && damp->reuse_limit == reuse
448 && damp->suppress_value == suppress
449 && damp->max_suppress_time == max)
451 bgp_damp_disable (bgp, afi, safi);
454 SET_FLAG (bgp->af_flags[afi][safi], BGP_CONFIG_DAMPENING);
455 bgp_damp_parameter_set (half, reuse, suppress, max);
457 /* Register reuse timer. */
460 thread_add_timer (master, bgp_reuse_timer, NULL, DELTA_REUSE);
466 bgp_damp_config_clean (struct bgp_damp_config *damp)
468 /* Free decay array */
469 XFREE (MTYPE_BGP_DAMP_ARRAY, damp->decay_array);
471 /* Free reuse index array */
472 XFREE (MTYPE_BGP_DAMP_ARRAY, damp->reuse_index);
474 /* Free reuse list array. */
475 XFREE (MTYPE_BGP_DAMP_ARRAY, damp->reuse_list);
478 /* Clean all the bgp_damp_info stored in reuse_list. */
480 bgp_damp_info_clean ()
483 struct bgp_damp_info *bdi, *next;
485 damp->reuse_offset = 0;
487 for (i = 0; i < damp->reuse_list_size; i++)
489 if (! damp->reuse_list[i])
492 for (bdi = damp->reuse_list[i]; bdi; bdi = next)
495 bgp_damp_info_free (bdi, 1);
497 damp->reuse_list[i] = NULL;
500 for (bdi = damp->no_reuse_list; bdi; bdi = next)
503 bgp_damp_info_free (bdi, 1);
505 damp->no_reuse_list = NULL;
509 bgp_damp_disable (struct bgp *bgp, afi_t afi, safi_t safi)
511 /* Cancel reuse thread. */
513 thread_cancel (damp->t_reuse);
514 damp->t_reuse = NULL;
516 /* Clean BGP dampening information. */
517 bgp_damp_info_clean ();
519 /* Clear configuration */
520 bgp_damp_config_clean (&bgp_damp_cfg);
522 UNSET_FLAG (bgp->af_flags[afi][safi], BGP_CONFIG_DAMPENING);
527 bgp_config_write_damp (struct vty *vty)
531 if (bgp_damp_cfg.half_life == DEFAULT_HALF_LIFE*60
532 && bgp_damp_cfg.reuse_limit == DEFAULT_REUSE
533 && bgp_damp_cfg.suppress_value == DEFAULT_SUPPRESS
534 && bgp_damp_cfg.max_suppress_time == bgp_damp_cfg.half_life*4)
535 vty_out (vty, " bgp dampening%s", VTY_NEWLINE);
536 else if (bgp_damp_cfg.half_life != DEFAULT_HALF_LIFE*60
537 && bgp_damp_cfg.reuse_limit == DEFAULT_REUSE
538 && bgp_damp_cfg.suppress_value == DEFAULT_SUPPRESS
539 && bgp_damp_cfg.max_suppress_time == bgp_damp_cfg.half_life*4)
540 vty_out (vty, " bgp dampening %d%s",
541 bgp_damp_cfg.half_life/60,
544 vty_out (vty, " bgp dampening %d %d %d %d%s",
545 bgp_damp_cfg.half_life/60,
546 bgp_damp_cfg.reuse_limit,
547 bgp_damp_cfg.suppress_value,
548 bgp_damp_cfg.max_suppress_time/60,
555 #define BGP_UPTIME_LEN 25
558 bgp_get_reuse_time (int penalty, char *buf, size_t len)
560 time_t reuse_time = 0;
561 struct tm *tm = NULL;
563 if (penalty > damp->reuse_limit)
565 reuse_time = (int) (DELTA_T * ((log((double)damp->reuse_limit/penalty))/(log(damp->decay_array[1]))));
567 if (reuse_time > damp->max_suppress_time)
568 reuse_time = damp->max_suppress_time;
570 tm = gmtime (&reuse_time);
575 /* Making formatted timer strings. */
576 #define ONE_DAY_SECOND 60*60*24
577 #define ONE_WEEK_SECOND 60*60*24*7
579 snprintf (buf, len, "00:00:00");
580 else if (reuse_time < ONE_DAY_SECOND)
581 snprintf (buf, len, "%02d:%02d:%02d",
582 tm->tm_hour, tm->tm_min, tm->tm_sec);
583 else if (reuse_time < ONE_WEEK_SECOND)
584 snprintf (buf, len, "%dd%02dh%02dm",
585 tm->tm_yday, tm->tm_hour, tm->tm_min);
587 snprintf (buf, len, "%02dw%dd%02dh",
588 tm->tm_yday/7, tm->tm_yday - ((tm->tm_yday/7) * 7), tm->tm_hour);
594 bgp_damp_info_vty (struct vty *vty, struct bgp_info *binfo)
596 struct bgp_damp_info *bdi;
597 time_t t_now, t_diff;
598 char timebuf[BGP_UPTIME_LEN];
601 /* BGP dampening information. */
602 bdi = binfo->damp_info;
604 /* If dampening is not enabled or there is no dampening information,
605 return immediately. */
609 /* Calculate new penalty. */
611 t_diff = t_now - bdi->t_updated;
612 penalty = bgp_damp_decay (t_diff, bdi->penalty);
614 vty_out (vty, " Dampinfo: penalty %d, flapped %d times in %s",
616 peer_uptime (bdi->start_time, timebuf, BGP_UPTIME_LEN));
618 if (CHECK_FLAG (binfo->flags, BGP_INFO_DAMPED)
619 && ! CHECK_FLAG (binfo->flags, BGP_INFO_HISTORY))
620 vty_out (vty, ", reuse in %s",
621 bgp_get_reuse_time (penalty, timebuf, BGP_UPTIME_LEN));
623 vty_out (vty, "%s", VTY_NEWLINE);
627 bgp_damp_reuse_time_vty (struct vty *vty, struct bgp_info *binfo)
629 struct bgp_damp_info *bdi;
630 time_t t_now, t_diff;
631 char timebuf[BGP_UPTIME_LEN];
634 /* BGP dampening information. */
635 bdi = binfo->damp_info;
637 /* If dampening is not enabled or there is no dampening information,
638 return immediately. */
642 /* Calculate new penalty. */
644 t_diff = t_now - bdi->t_updated;
645 penalty = bgp_damp_decay (t_diff, bdi->penalty);
647 return bgp_get_reuse_time (penalty, timebuf, BGP_UPTIME_LEN);