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 along
17 * with this program; see the file COPYING; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
32 #include "bgpd/bgpd.h"
33 #include "bgpd/bgp_damp.h"
34 #include "bgpd/bgp_table.h"
35 #include "bgpd/bgp_route.h"
36 #include "bgpd/bgp_attr.h"
37 #include "bgpd/bgp_advertise.h"
39 /* Global variable to access damping configuration */
40 struct bgp_damp_config bgp_damp_cfg
;
41 static struct bgp_damp_config
*damp
= &bgp_damp_cfg
;
43 /* Utility macro to add and delete BGP dampening information to no
45 #define BGP_DAMP_LIST_ADD(N, A) BGP_PATH_INFO_ADD(N, A, no_reuse_list)
46 #define BGP_DAMP_LIST_DEL(N, A) BGP_PATH_INFO_DEL(N, A, no_reuse_list)
48 /* Calculate reuse list index by penalty value. */
49 static int bgp_reuse_index(int penalty
)
54 i
= (int)(((double)penalty
/ damp
->reuse_limit
- 1.0)
55 * damp
->scale_factor
);
57 if (i
>= damp
->reuse_index_size
)
58 i
= damp
->reuse_index_size
- 1;
60 index
= damp
->reuse_index
[i
] - damp
->reuse_index
[0];
62 return (damp
->reuse_offset
+ index
) % damp
->reuse_list_size
;
65 /* Add BGP dampening information to reuse list. */
66 static void 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. */
80 static void 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. */
91 int bgp_damp_decay(time_t tdiff
, int penalty
)
95 i
= (int)((double)tdiff
/ DELTA_T
);
100 if (i
>= damp
->decay_array_size
)
103 return (int)(penalty
* damp
->decay_array
[i
]);
106 /* Handler of reuse timer event. Each route in the current reuse-list
107 is evaluated. RFC2439 Section 4.8.7. */
108 static int bgp_reuse_timer(struct thread
*t
)
110 struct bgp_damp_info
*bdi
;
111 struct bgp_damp_info
*next
;
112 time_t t_now
, t_diff
;
114 damp
->t_reuse
= NULL
;
115 thread_add_timer(bm
->master
, bgp_reuse_timer
, NULL
, DELTA_REUSE
,
120 /* 1. save a pointer to the current zeroth queue head and zero the
122 bdi
= damp
->reuse_list
[damp
->reuse_offset
];
123 damp
->reuse_list
[damp
->reuse_offset
] = NULL
;
125 /* 2. set offset = modulo reuse-list-size ( offset + 1 ), thereby
126 rotating the circular queue of list-heads. */
127 damp
->reuse_offset
= (damp
->reuse_offset
+ 1) % damp
->reuse_list_size
;
129 /* 3. if ( the saved list head pointer is non-empty ) */
130 for (; bdi
; bdi
= next
) {
131 struct bgp
*bgp
= bdi
->path
->peer
->bgp
;
135 /* Set t-diff = t-now - t-updated. */
136 t_diff
= t_now
- bdi
->t_updated
;
138 /* Set figure-of-merit = figure-of-merit * decay-array-ok
140 bdi
->penalty
= bgp_damp_decay(t_diff
, bdi
->penalty
);
142 /* Set t-updated = t-now. */
143 bdi
->t_updated
= t_now
;
145 /* if (figure-of-merit < reuse). */
146 if (bdi
->penalty
< damp
->reuse_limit
) {
147 /* Reuse the route. */
148 bgp_path_info_unset_flag(bdi
->rn
, bdi
->path
,
150 bdi
->suppress_time
= 0;
152 if (bdi
->lastrecord
== BGP_RECORD_UPDATE
) {
153 bgp_path_info_unset_flag(bdi
->rn
, bdi
->path
,
155 bgp_aggregate_increment(bgp
, &bdi
->rn
->p
,
158 bgp_process(bgp
, bdi
->rn
, bdi
->afi
, bdi
->safi
);
161 if (bdi
->penalty
<= damp
->reuse_limit
/ 2.0)
162 bgp_damp_info_free(bdi
, 1);
164 BGP_DAMP_LIST_ADD(damp
, bdi
);
166 /* Re-insert into another list (See RFC2439 Section
168 bgp_reuse_list_add(bdi
);
174 /* A route becomes unreachable (RFC2439 Section 4.8.2). */
175 int bgp_damp_withdraw(struct bgp_path_info
*path
, struct bgp_node
*rn
,
176 afi_t afi
, safi_t safi
, int attr_change
)
179 struct bgp_damp_info
*bdi
= NULL
;
180 unsigned int last_penalty
= 0;
184 /* Processing Unreachable Messages. */
186 bdi
= path
->extra
->damp_info
;
189 /* If there is no previous stability history. */
192 1. allocate a damping structure.
193 2. set figure-of-merit = 1.
194 3. withdraw the route. */
196 bdi
= XCALLOC(MTYPE_BGP_DAMP_INFO
,
197 sizeof(struct bgp_damp_info
));
201 (attr_change
? DEFAULT_PENALTY
/ 2 : DEFAULT_PENALTY
);
203 bdi
->start_time
= t_now
;
204 bdi
->suppress_time
= 0;
208 (bgp_path_info_extra_get(path
))->damp_info
= bdi
;
209 BGP_DAMP_LIST_ADD(damp
, bdi
);
211 last_penalty
= bdi
->penalty
;
213 /* 1. Set t-diff = t-now - t-updated. */
215 (bgp_damp_decay(t_now
- bdi
->t_updated
, bdi
->penalty
)
216 + (attr_change
? DEFAULT_PENALTY
/ 2
219 if (bdi
->penalty
> damp
->ceiling
)
220 bdi
->penalty
= damp
->ceiling
;
225 assert((rn
== bdi
->rn
) && (path
== bdi
->path
));
227 bdi
->lastrecord
= BGP_RECORD_WITHDRAW
;
228 bdi
->t_updated
= t_now
;
230 /* Make this route as historical status. */
231 bgp_path_info_set_flag(rn
, path
, BGP_PATH_HISTORY
);
233 /* Remove the route from a reuse list if it is on one. */
234 if (CHECK_FLAG(bdi
->path
->flags
, BGP_PATH_DAMPED
)) {
235 /* If decay rate isn't equal to 0, reinsert brn. */
236 if (bdi
->penalty
!= last_penalty
&& bdi
->index
>= 0) {
237 bgp_reuse_list_delete(bdi
);
238 bgp_reuse_list_add(bdi
);
240 return BGP_DAMP_SUPPRESSED
;
243 /* If not suppressed before, do annonunce this withdraw and
244 insert into reuse_list. */
245 if (bdi
->penalty
>= damp
->suppress_value
) {
246 bgp_path_info_set_flag(rn
, path
, BGP_PATH_DAMPED
);
247 bdi
->suppress_time
= t_now
;
248 BGP_DAMP_LIST_DEL(damp
, bdi
);
249 bgp_reuse_list_add(bdi
);
252 return BGP_DAMP_USED
;
255 int bgp_damp_update(struct bgp_path_info
*path
, struct bgp_node
*rn
, afi_t afi
,
259 struct bgp_damp_info
*bdi
;
262 if (!path
->extra
|| !((bdi
= path
->extra
->damp_info
)))
263 return BGP_DAMP_USED
;
266 bgp_path_info_unset_flag(rn
, path
, BGP_PATH_HISTORY
);
268 bdi
->lastrecord
= BGP_RECORD_UPDATE
;
269 bdi
->penalty
= bgp_damp_decay(t_now
- bdi
->t_updated
, bdi
->penalty
);
271 if (!CHECK_FLAG(bdi
->path
->flags
, BGP_PATH_DAMPED
)
272 && (bdi
->penalty
< damp
->suppress_value
))
273 status
= BGP_DAMP_USED
;
274 else if (CHECK_FLAG(bdi
->path
->flags
, BGP_PATH_DAMPED
)
275 && (bdi
->penalty
< damp
->reuse_limit
)) {
276 bgp_path_info_unset_flag(rn
, path
, BGP_PATH_DAMPED
);
277 bgp_reuse_list_delete(bdi
);
278 BGP_DAMP_LIST_ADD(damp
, bdi
);
279 bdi
->suppress_time
= 0;
280 status
= BGP_DAMP_USED
;
282 status
= BGP_DAMP_SUPPRESSED
;
284 if (bdi
->penalty
> damp
->reuse_limit
/ 2.0)
285 bdi
->t_updated
= t_now
;
287 bgp_damp_info_free(bdi
, 0);
292 /* Remove dampening information and history route. */
293 int bgp_damp_scan(struct bgp_path_info
*path
, afi_t afi
, safi_t safi
)
295 time_t t_now
, t_diff
;
296 struct bgp_damp_info
*bdi
;
298 assert(path
->extra
&& path
->extra
->damp_info
);
301 bdi
= path
->extra
->damp_info
;
303 if (CHECK_FLAG(path
->flags
, BGP_PATH_DAMPED
)) {
304 t_diff
= t_now
- bdi
->suppress_time
;
306 if (t_diff
>= damp
->max_suppress_time
) {
307 bgp_path_info_unset_flag(bdi
->rn
, path
,
309 bgp_reuse_list_delete(bdi
);
310 BGP_DAMP_LIST_ADD(damp
, bdi
);
311 bdi
->penalty
= damp
->reuse_limit
;
312 bdi
->suppress_time
= 0;
313 bdi
->t_updated
= t_now
;
315 /* Need to announce UPDATE once this path is usable
317 if (bdi
->lastrecord
== BGP_RECORD_UPDATE
)
323 t_diff
= t_now
- bdi
->t_updated
;
324 bdi
->penalty
= bgp_damp_decay(t_diff
, bdi
->penalty
);
326 if (bdi
->penalty
<= damp
->reuse_limit
/ 2.0) {
327 /* release the bdi, bdi->path. */
328 bgp_damp_info_free(bdi
, 1);
331 bdi
->t_updated
= t_now
;
336 void bgp_damp_info_free(struct bgp_damp_info
*bdi
, int withdraw
)
338 struct bgp_path_info
*path
;
344 path
->extra
->damp_info
= NULL
;
346 if (CHECK_FLAG(path
->flags
, BGP_PATH_DAMPED
))
347 bgp_reuse_list_delete(bdi
);
349 BGP_DAMP_LIST_DEL(damp
, bdi
);
351 bgp_path_info_unset_flag(bdi
->rn
, path
,
352 BGP_PATH_HISTORY
| BGP_PATH_DAMPED
);
354 if (bdi
->lastrecord
== BGP_RECORD_WITHDRAW
&& withdraw
)
355 bgp_path_info_delete(bdi
->rn
, path
);
357 XFREE(MTYPE_BGP_DAMP_INFO
, bdi
);
360 static void bgp_damp_parameter_set(int hlife
, int reuse
, int sup
, int maxsup
)
362 double reuse_max_ratio
;
366 damp
->suppress_value
= sup
;
367 damp
->half_life
= hlife
;
368 damp
->reuse_limit
= reuse
;
369 damp
->max_suppress_time
= maxsup
;
371 /* Initialize params per bgp_damp_config. */
372 damp
->reuse_index_size
= REUSE_ARRAY_SIZE
;
375 (int)(damp
->reuse_limit
* (pow(2,
376 (double)damp
->max_suppress_time
377 / damp
->half_life
)));
379 /* Decay-array computations */
380 damp
->decay_array_size
=
381 ceil((double)damp
->max_suppress_time
/ DELTA_T
);
382 damp
->decay_array
= XMALLOC(MTYPE_BGP_DAMP_ARRAY
,
383 sizeof(double) * (damp
->decay_array_size
));
384 damp
->decay_array
[0] = 1.0;
385 damp
->decay_array
[1] =
386 exp((1.0 / ((double)damp
->half_life
/ DELTA_T
)) * log(0.5));
388 /* Calculate decay values for all possible times */
389 for (i
= 2; i
< damp
->decay_array_size
; i
++)
390 damp
->decay_array
[i
] =
391 damp
->decay_array
[i
- 1] * damp
->decay_array
[1];
393 /* Reuse-list computations */
394 i
= ceil((double)damp
->max_suppress_time
/ DELTA_REUSE
) + 1;
395 if (i
> REUSE_LIST_SIZE
|| i
== 0)
397 damp
->reuse_list_size
= i
;
399 damp
->reuse_list
= XCALLOC(MTYPE_BGP_DAMP_ARRAY
,
400 damp
->reuse_list_size
401 * sizeof(struct bgp_reuse_node
*));
403 /* Reuse-array computations */
404 damp
->reuse_index
= XCALLOC(MTYPE_BGP_DAMP_ARRAY
,
405 sizeof(int) * damp
->reuse_index_size
);
407 reuse_max_ratio
= (double)damp
->ceiling
/ damp
->reuse_limit
;
408 j
= (exp((double)damp
->max_suppress_time
/ damp
->half_life
)
410 if (reuse_max_ratio
> j
&& j
!= 0)
414 (double)damp
->reuse_index_size
/ (reuse_max_ratio
- 1);
416 for (i
= 0; i
< damp
->reuse_index_size
; i
++) {
417 damp
->reuse_index
[i
] =
418 (int)(((double)damp
->half_life
/ DELTA_REUSE
)
419 * log10(1.0 / (damp
->reuse_limit
421 / damp
->scale_factor
))))
426 int bgp_damp_enable(struct bgp
*bgp
, afi_t afi
, safi_t safi
, time_t half
,
427 unsigned int reuse
, unsigned int suppress
, time_t max
)
429 if (CHECK_FLAG(bgp
->af_flags
[afi
][safi
], BGP_CONFIG_DAMPENING
)) {
430 if (damp
->half_life
== half
&& damp
->reuse_limit
== reuse
431 && damp
->suppress_value
== suppress
432 && damp
->max_suppress_time
== max
)
434 bgp_damp_disable(bgp
, afi
, safi
);
437 SET_FLAG(bgp
->af_flags
[afi
][safi
], BGP_CONFIG_DAMPENING
);
438 bgp_damp_parameter_set(half
, reuse
, suppress
, max
);
440 /* Register reuse timer. */
441 thread_add_timer(bm
->master
, bgp_reuse_timer
, NULL
, DELTA_REUSE
,
447 static void bgp_damp_config_clean(struct bgp_damp_config
*damp
)
449 /* Free decay array */
450 XFREE(MTYPE_BGP_DAMP_ARRAY
, damp
->decay_array
);
451 damp
->decay_array_size
= 0;
453 /* Free reuse index array */
454 XFREE(MTYPE_BGP_DAMP_ARRAY
, damp
->reuse_index
);
455 damp
->reuse_index_size
= 0;
457 /* Free reuse list array. */
458 XFREE(MTYPE_BGP_DAMP_ARRAY
, damp
->reuse_list
);
459 damp
->reuse_list_size
= 0;
462 /* Clean all the bgp_damp_info stored in reuse_list. */
463 void bgp_damp_info_clean(void)
466 struct bgp_damp_info
*bdi
, *next
;
468 damp
->reuse_offset
= 0;
470 for (i
= 0; i
< damp
->reuse_list_size
; i
++) {
471 if (!damp
->reuse_list
[i
])
474 for (bdi
= damp
->reuse_list
[i
]; bdi
; bdi
= next
) {
476 bgp_damp_info_free(bdi
, 1);
478 damp
->reuse_list
[i
] = NULL
;
481 for (bdi
= damp
->no_reuse_list
; bdi
; bdi
= next
) {
483 bgp_damp_info_free(bdi
, 1);
485 damp
->no_reuse_list
= NULL
;
488 int bgp_damp_disable(struct bgp
*bgp
, afi_t afi
, safi_t safi
)
490 /* If it wasn't enabled, there's nothing to do. */
491 if (!CHECK_FLAG(bgp
->af_flags
[afi
][safi
], BGP_CONFIG_DAMPENING
))
494 /* Cancel reuse thread. */
496 thread_cancel(damp
->t_reuse
);
497 damp
->t_reuse
= NULL
;
499 /* Clean BGP dampening information. */
500 bgp_damp_info_clean();
502 /* Clear configuration */
503 bgp_damp_config_clean(&bgp_damp_cfg
);
505 UNSET_FLAG(bgp
->af_flags
[afi
][safi
], BGP_CONFIG_DAMPENING
);
509 void bgp_config_write_damp(struct vty
*vty
)
511 if (bgp_damp_cfg
.half_life
== DEFAULT_HALF_LIFE
* 60
512 && bgp_damp_cfg
.reuse_limit
== DEFAULT_REUSE
513 && bgp_damp_cfg
.suppress_value
== DEFAULT_SUPPRESS
514 && bgp_damp_cfg
.max_suppress_time
== bgp_damp_cfg
.half_life
* 4)
515 vty_out(vty
, " bgp dampening\n");
516 else if (bgp_damp_cfg
.half_life
!= DEFAULT_HALF_LIFE
* 60
517 && bgp_damp_cfg
.reuse_limit
== DEFAULT_REUSE
518 && bgp_damp_cfg
.suppress_value
== DEFAULT_SUPPRESS
519 && bgp_damp_cfg
.max_suppress_time
520 == bgp_damp_cfg
.half_life
* 4)
521 vty_out(vty
, " bgp dampening %lld\n",
522 bgp_damp_cfg
.half_life
/ 60LL);
524 vty_out(vty
, " bgp dampening %lld %d %d %lld\n",
525 bgp_damp_cfg
.half_life
/ 60LL, bgp_damp_cfg
.reuse_limit
,
526 bgp_damp_cfg
.suppress_value
,
527 bgp_damp_cfg
.max_suppress_time
/ 60LL);
530 static const char *bgp_get_reuse_time(unsigned int penalty
, char *buf
,
531 size_t len
, bool use_json
,
534 time_t reuse_time
= 0;
535 struct tm
*tm
= NULL
;
538 if (penalty
> damp
->reuse_limit
) {
539 reuse_time
= (int)(DELTA_T
540 * ((log((double)damp
->reuse_limit
/ penalty
))
541 / (log(damp
->decay_array
[1]))));
543 if (reuse_time
> damp
->max_suppress_time
)
544 reuse_time
= damp
->max_suppress_time
;
546 tm
= gmtime(&reuse_time
);
550 /* Making formatted timer strings. */
551 if (reuse_time
== 0) {
553 json_object_int_add(json
, "reuseTimerMsecs", 0);
555 snprintf(buf
, len
, "00:00:00");
556 } else if (reuse_time
< ONE_DAY_SECOND
) {
558 time_store
= (3600000 * tm
->tm_hour
)
559 + (60000 * tm
->tm_min
)
560 + (1000 * tm
->tm_sec
);
561 json_object_int_add(json
, "reuseTimerMsecs",
564 snprintf(buf
, len
, "%02d:%02d:%02d", tm
->tm_hour
,
565 tm
->tm_min
, tm
->tm_sec
);
566 } else if (reuse_time
< ONE_WEEK_SECOND
) {
568 time_store
= (86400000 * tm
->tm_yday
)
569 + (3600000 * tm
->tm_hour
)
570 + (60000 * tm
->tm_min
)
571 + (1000 * tm
->tm_sec
);
572 json_object_int_add(json
, "reuseTimerMsecs",
575 snprintf(buf
, len
, "%dd%02dh%02dm", tm
->tm_yday
,
576 tm
->tm_hour
, tm
->tm_min
);
580 (604800000 * tm
->tm_yday
/ 7)
582 * (tm
->tm_yday
- ((tm
->tm_yday
/ 7) * 7)))
583 + (3600000 * tm
->tm_hour
) + (60000 * tm
->tm_min
)
584 + (1000 * tm
->tm_sec
);
585 json_object_int_add(json
, "reuseTimerMsecs",
588 snprintf(buf
, len
, "%02dw%dd%02dh", tm
->tm_yday
/ 7,
589 tm
->tm_yday
- ((tm
->tm_yday
/ 7) * 7),
596 void bgp_damp_info_vty(struct vty
*vty
, struct bgp_path_info
*path
,
597 json_object
*json_path
)
599 struct bgp_damp_info
*bdi
;
600 time_t t_now
, t_diff
;
601 char timebuf
[BGP_UPTIME_LEN
];
607 /* BGP dampening information. */
608 bdi
= path
->extra
->damp_info
;
610 /* If dampening is not enabled or there is no dampening information,
611 return immediately. */
615 /* Calculate new penalty. */
617 t_diff
= t_now
- bdi
->t_updated
;
618 penalty
= bgp_damp_decay(t_diff
, bdi
->penalty
);
621 json_object_int_add(json_path
, "dampeningPenalty", penalty
);
622 json_object_int_add(json_path
, "dampeningFlapCount", bdi
->flap
);
623 peer_uptime(bdi
->start_time
, timebuf
, BGP_UPTIME_LEN
, 1,
626 if (CHECK_FLAG(path
->flags
, BGP_PATH_DAMPED
)
627 && !CHECK_FLAG(path
->flags
, BGP_PATH_HISTORY
))
628 bgp_get_reuse_time(penalty
, timebuf
, BGP_UPTIME_LEN
, 1,
632 " Dampinfo: penalty %d, flapped %d times in %s",
634 peer_uptime(bdi
->start_time
, timebuf
, BGP_UPTIME_LEN
, 0,
637 if (CHECK_FLAG(path
->flags
, BGP_PATH_DAMPED
)
638 && !CHECK_FLAG(path
->flags
, BGP_PATH_HISTORY
))
639 vty_out(vty
, ", reuse in %s",
640 bgp_get_reuse_time(penalty
, timebuf
,
648 const char *bgp_damp_reuse_time_vty(struct vty
*vty
, struct bgp_path_info
*path
,
649 char *timebuf
, size_t len
, bool use_json
,
652 struct bgp_damp_info
*bdi
;
653 time_t t_now
, t_diff
;
659 /* BGP dampening information. */
660 bdi
= path
->extra
->damp_info
;
662 /* If dampening is not enabled or there is no dampening information,
663 return immediately. */
667 /* Calculate new penalty. */
669 t_diff
= t_now
- bdi
->t_updated
;
670 penalty
= bgp_damp_decay(t_diff
, bdi
->penalty
);
672 return bgp_get_reuse_time(penalty
, timebuf
, len
, use_json
, json
);
675 int bgp_show_dampening_parameters(struct vty
*vty
, afi_t afi
, safi_t safi
)
678 bgp
= bgp_get_default();
681 vty_out(vty
, "No BGP process is configured\n");
685 if (CHECK_FLAG(bgp
->af_flags
[afi
][safi
], BGP_CONFIG_DAMPENING
)) {
686 vty_out(vty
, "Half-life time: %lld min\n",
687 (long long)damp
->half_life
/ 60);
688 vty_out(vty
, "Reuse penalty: %d\n", damp
->reuse_limit
);
689 vty_out(vty
, "Suppress penalty: %d\n", damp
->suppress_value
);
690 vty_out(vty
, "Max suppress time: %lld min\n",
691 (long long)damp
->max_suppress_time
/ 60);
692 vty_out(vty
, "Max suppress penalty: %u\n", damp
->ceiling
);
695 vty_out(vty
, "dampening not enabled for %s\n",
696 afi
== AFI_IP
? "IPv4" : "IPv6");