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_INFO_ADD(N,A,no_reuse_list)
46 #define BGP_DAMP_LIST_DEL(N,A) BGP_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
->binfo
->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_info_unset_flag(bdi
->rn
, bdi
->binfo
,
150 bdi
->suppress_time
= 0;
152 if (bdi
->lastrecord
== BGP_RECORD_UPDATE
) {
153 bgp_info_unset_flag(bdi
->rn
, bdi
->binfo
,
155 bgp_aggregate_increment(bgp
, &bdi
->rn
->p
,
156 bdi
->binfo
, bdi
->afi
,
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_info
*binfo
, struct bgp_node
*rn
, afi_t afi
,
176 safi_t safi
, int attr_change
)
179 struct bgp_damp_info
*bdi
= NULL
;
180 double last_penalty
= 0;
184 /* Processing Unreachable Messages. */
186 bdi
= binfo
->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_info_extra_get(binfo
))->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
) && (binfo
== bdi
->binfo
));
227 bdi
->lastrecord
= BGP_RECORD_WITHDRAW
;
228 bdi
->t_updated
= t_now
;
230 /* Make this route as historical status. */
231 bgp_info_set_flag(rn
, binfo
, BGP_INFO_HISTORY
);
233 /* Remove the route from a reuse list if it is on one. */
234 if (CHECK_FLAG(bdi
->binfo
->flags
, BGP_INFO_DAMPED
)) {
235 /* If decay rate isn't equal to 0, reinsert brn. */
236 if (bdi
->penalty
!= last_penalty
) {
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_info_set_flag(rn
, binfo
, BGP_INFO_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_info
*binfo
, struct bgp_node
*rn
, afi_t afi
,
259 struct bgp_damp_info
*bdi
;
262 if (!binfo
->extra
|| !((bdi
= binfo
->extra
->damp_info
)))
263 return BGP_DAMP_USED
;
266 bgp_info_unset_flag(rn
, binfo
, BGP_INFO_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
->binfo
->flags
, BGP_INFO_DAMPED
)
272 && (bdi
->penalty
< damp
->suppress_value
))
273 status
= BGP_DAMP_USED
;
274 else if (CHECK_FLAG(bdi
->binfo
->flags
, BGP_INFO_DAMPED
)
275 && (bdi
->penalty
< damp
->reuse_limit
)) {
276 bgp_info_unset_flag(rn
, binfo
, BGP_INFO_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_info
*binfo
, afi_t afi
, safi_t safi
)
295 time_t t_now
, t_diff
;
296 struct bgp_damp_info
*bdi
;
298 assert(binfo
->extra
&& binfo
->extra
->damp_info
);
301 bdi
= binfo
->extra
->damp_info
;
303 if (CHECK_FLAG(binfo
->flags
, BGP_INFO_DAMPED
)) {
304 t_diff
= t_now
- bdi
->suppress_time
;
306 if (t_diff
>= damp
->max_suppress_time
) {
307 bgp_info_unset_flag(bdi
->rn
, binfo
, BGP_INFO_DAMPED
);
308 bgp_reuse_list_delete(bdi
);
309 BGP_DAMP_LIST_ADD(damp
, bdi
);
310 bdi
->penalty
= damp
->reuse_limit
;
311 bdi
->suppress_time
= 0;
312 bdi
->t_updated
= t_now
;
314 /* Need to announce UPDATE once this binfo is usable
316 if (bdi
->lastrecord
== BGP_RECORD_UPDATE
)
322 t_diff
= t_now
- bdi
->t_updated
;
323 bdi
->penalty
= bgp_damp_decay(t_diff
, bdi
->penalty
);
325 if (bdi
->penalty
<= damp
->reuse_limit
/ 2.0) {
326 /* release the bdi, bdi->binfo. */
327 bgp_damp_info_free(bdi
, 1);
330 bdi
->t_updated
= t_now
;
335 void bgp_damp_info_free(struct bgp_damp_info
*bdi
, int withdraw
)
337 struct bgp_info
*binfo
;
343 binfo
->extra
->damp_info
= NULL
;
345 if (CHECK_FLAG(binfo
->flags
, BGP_INFO_DAMPED
))
346 bgp_reuse_list_delete(bdi
);
348 BGP_DAMP_LIST_DEL(damp
, bdi
);
350 bgp_info_unset_flag(bdi
->rn
, binfo
, BGP_INFO_HISTORY
| BGP_INFO_DAMPED
);
352 if (bdi
->lastrecord
== BGP_RECORD_WITHDRAW
&& withdraw
)
353 bgp_info_delete(bdi
->rn
, binfo
);
355 XFREE(MTYPE_BGP_DAMP_INFO
, bdi
);
358 static void bgp_damp_parameter_set(int hlife
, int reuse
, int sup
, int maxsup
)
360 double reuse_max_ratio
;
364 damp
->suppress_value
= sup
;
365 damp
->half_life
= hlife
;
366 damp
->reuse_limit
= reuse
;
367 damp
->max_suppress_time
= maxsup
;
369 /* Initialize params per bgp_damp_config. */
370 damp
->reuse_index_size
= REUSE_ARRAY_SIZE
;
373 (int)(damp
->reuse_limit
* (pow(2,
374 (double)damp
->max_suppress_time
375 / damp
->half_life
)));
377 /* Decay-array computations */
378 damp
->decay_array_size
=
379 ceil((double)damp
->max_suppress_time
/ DELTA_T
);
380 damp
->decay_array
= XMALLOC(MTYPE_BGP_DAMP_ARRAY
,
381 sizeof(double) * (damp
->decay_array_size
));
382 damp
->decay_array
[0] = 1.0;
383 damp
->decay_array
[1] =
384 exp((1.0 / ((double)damp
->half_life
/ DELTA_T
)) * log(0.5));
386 /* Calculate decay values for all possible times */
387 for (i
= 2; i
< damp
->decay_array_size
; i
++)
388 damp
->decay_array
[i
] =
389 damp
->decay_array
[i
- 1] * damp
->decay_array
[1];
391 /* Reuse-list computations */
392 i
= ceil((double)damp
->max_suppress_time
/ DELTA_REUSE
) + 1;
393 if (i
> REUSE_LIST_SIZE
|| i
== 0)
395 damp
->reuse_list_size
= i
;
397 damp
->reuse_list
= XCALLOC(MTYPE_BGP_DAMP_ARRAY
,
398 damp
->reuse_list_size
399 * sizeof(struct bgp_reuse_node
*));
401 /* Reuse-array computations */
402 damp
->reuse_index
= XCALLOC(MTYPE_BGP_DAMP_ARRAY
,
403 sizeof(int) * damp
->reuse_index_size
);
405 reuse_max_ratio
= (double)damp
->ceiling
/ damp
->reuse_limit
;
406 j
= (exp((double)damp
->max_suppress_time
/ damp
->half_life
)
408 if (reuse_max_ratio
> j
&& j
!= 0)
412 (double)damp
->reuse_index_size
/ (reuse_max_ratio
- 1);
414 for (i
= 0; i
< damp
->reuse_index_size
; i
++) {
415 damp
->reuse_index
[i
] =
416 (int)(((double)damp
->half_life
/ DELTA_REUSE
)
417 * log10(1.0 / (damp
->reuse_limit
419 / damp
->scale_factor
))))
424 int bgp_damp_enable(struct bgp
*bgp
, afi_t afi
, safi_t safi
, time_t half
,
425 unsigned int reuse
, unsigned int suppress
, time_t max
)
427 if (CHECK_FLAG(bgp
->af_flags
[afi
][safi
], BGP_CONFIG_DAMPENING
)) {
428 if (damp
->half_life
== half
&& damp
->reuse_limit
== reuse
429 && damp
->suppress_value
== suppress
430 && damp
->max_suppress_time
== max
)
432 bgp_damp_disable(bgp
, afi
, safi
);
435 SET_FLAG(bgp
->af_flags
[afi
][safi
], BGP_CONFIG_DAMPENING
);
436 bgp_damp_parameter_set(half
, reuse
, suppress
, max
);
438 /* Register reuse timer. */
439 thread_add_timer(bm
->master
, bgp_reuse_timer
, NULL
, DELTA_REUSE
,
445 static void bgp_damp_config_clean(struct bgp_damp_config
*damp
)
447 /* Free decay array */
448 XFREE(MTYPE_BGP_DAMP_ARRAY
, damp
->decay_array
);
450 /* Free reuse index array */
451 XFREE(MTYPE_BGP_DAMP_ARRAY
, damp
->reuse_index
);
453 /* Free reuse list array. */
454 XFREE(MTYPE_BGP_DAMP_ARRAY
, damp
->reuse_list
);
457 /* Clean all the bgp_damp_info stored in reuse_list. */
458 void bgp_damp_info_clean(void)
461 struct bgp_damp_info
*bdi
, *next
;
463 damp
->reuse_offset
= 0;
465 for (i
= 0; i
< damp
->reuse_list_size
; i
++) {
466 if (!damp
->reuse_list
[i
])
469 for (bdi
= damp
->reuse_list
[i
]; bdi
; bdi
= next
) {
471 bgp_damp_info_free(bdi
, 1);
473 damp
->reuse_list
[i
] = NULL
;
476 for (bdi
= damp
->no_reuse_list
; bdi
; bdi
= next
) {
478 bgp_damp_info_free(bdi
, 1);
480 damp
->no_reuse_list
= NULL
;
483 int bgp_damp_disable(struct bgp
*bgp
, afi_t afi
, safi_t safi
)
485 /* If it wasn't enabled, there's nothing to do. */
486 if (!CHECK_FLAG(bgp
->af_flags
[afi
][safi
], BGP_CONFIG_DAMPENING
))
489 /* Cancel reuse thread. */
491 thread_cancel(damp
->t_reuse
);
492 damp
->t_reuse
= NULL
;
494 /* Clean BGP dampening information. */
495 bgp_damp_info_clean();
497 /* Clear configuration */
498 bgp_damp_config_clean(&bgp_damp_cfg
);
500 UNSET_FLAG(bgp
->af_flags
[afi
][safi
], BGP_CONFIG_DAMPENING
);
504 void bgp_config_write_damp(struct vty
*vty
)
506 if (bgp_damp_cfg
.half_life
== DEFAULT_HALF_LIFE
* 60
507 && bgp_damp_cfg
.reuse_limit
== DEFAULT_REUSE
508 && bgp_damp_cfg
.suppress_value
== DEFAULT_SUPPRESS
509 && bgp_damp_cfg
.max_suppress_time
== bgp_damp_cfg
.half_life
* 4)
510 vty_out(vty
, " bgp dampening\n");
511 else 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
515 == bgp_damp_cfg
.half_life
* 4)
516 vty_out(vty
, " bgp dampening %lld\n",
517 bgp_damp_cfg
.half_life
/ 60LL);
519 vty_out(vty
, " bgp dampening %lld %d %d %lld\n",
520 bgp_damp_cfg
.half_life
/ 60LL, bgp_damp_cfg
.reuse_limit
,
521 bgp_damp_cfg
.suppress_value
,
522 bgp_damp_cfg
.max_suppress_time
/ 60LL);
525 static const char *bgp_get_reuse_time(unsigned int penalty
, char *buf
,
526 size_t len
, u_char use_json
,
529 time_t reuse_time
= 0;
530 struct tm
*tm
= NULL
;
533 if (penalty
> damp
->reuse_limit
) {
534 reuse_time
= (int)(DELTA_T
535 * ((log((double)damp
->reuse_limit
/ penalty
))
536 / (log(damp
->decay_array
[1]))));
538 if (reuse_time
> damp
->max_suppress_time
)
539 reuse_time
= damp
->max_suppress_time
;
541 tm
= gmtime(&reuse_time
);
545 /* Making formatted timer strings. */
546 #define ONE_DAY_SECOND 60*60*24
547 #define ONE_WEEK_SECOND 60*60*24*7
548 if (reuse_time
== 0) {
550 json_object_int_add(json
, "reuseTimerMsecs", 0);
552 snprintf(buf
, len
, "00:00:00");
553 } else if (reuse_time
< ONE_DAY_SECOND
) {
555 time_store
= (3600000 * tm
->tm_hour
)
556 + (60000 * tm
->tm_min
)
557 + (1000 * tm
->tm_sec
);
558 json_object_int_add(json
, "reuseTimerMsecs",
561 snprintf(buf
, len
, "%02d:%02d:%02d", tm
->tm_hour
,
562 tm
->tm_min
, tm
->tm_sec
);
563 } else if (reuse_time
< ONE_WEEK_SECOND
) {
565 time_store
= (86400000 * tm
->tm_yday
)
566 + (3600000 * tm
->tm_hour
)
567 + (60000 * tm
->tm_min
)
568 + (1000 * tm
->tm_sec
);
569 json_object_int_add(json
, "reuseTimerMsecs",
572 snprintf(buf
, len
, "%dd%02dh%02dm", tm
->tm_yday
,
573 tm
->tm_hour
, tm
->tm_min
);
577 (604800000 * tm
->tm_yday
/ 7)
579 * (tm
->tm_yday
- ((tm
->tm_yday
/ 7) * 7)))
580 + (3600000 * tm
->tm_hour
) + (60000 * tm
->tm_min
)
581 + (1000 * tm
->tm_sec
);
582 json_object_int_add(json
, "reuseTimerMsecs",
585 snprintf(buf
, len
, "%02dw%dd%02dh", tm
->tm_yday
/ 7,
586 tm
->tm_yday
- ((tm
->tm_yday
/ 7) * 7),
593 void bgp_damp_info_vty(struct vty
*vty
, struct bgp_info
*binfo
,
594 json_object
*json_path
)
596 struct bgp_damp_info
*bdi
;
597 time_t t_now
, t_diff
;
598 char timebuf
[BGP_UPTIME_LEN
];
604 /* BGP dampening information. */
605 bdi
= binfo
->extra
->damp_info
;
607 /* If dampening is not enabled or there is no dampening information,
608 return immediately. */
612 /* Calculate new penalty. */
614 t_diff
= t_now
- bdi
->t_updated
;
615 penalty
= bgp_damp_decay(t_diff
, bdi
->penalty
);
618 json_object_int_add(json_path
, "dampeningPenalty", penalty
);
619 json_object_int_add(json_path
, "dampeningFlapCount", bdi
->flap
);
620 peer_uptime(bdi
->start_time
, timebuf
, BGP_UPTIME_LEN
, 1,
623 if (CHECK_FLAG(binfo
->flags
, BGP_INFO_DAMPED
)
624 && !CHECK_FLAG(binfo
->flags
, BGP_INFO_HISTORY
))
625 bgp_get_reuse_time(penalty
, timebuf
, BGP_UPTIME_LEN
, 1,
629 " Dampinfo: penalty %d, flapped %d times in %s",
631 peer_uptime(bdi
->start_time
, timebuf
, BGP_UPTIME_LEN
, 0,
634 if (CHECK_FLAG(binfo
->flags
, BGP_INFO_DAMPED
)
635 && !CHECK_FLAG(binfo
->flags
, BGP_INFO_HISTORY
))
636 vty_out(vty
, ", reuse in %s",
637 bgp_get_reuse_time(penalty
, timebuf
,
645 const char *bgp_damp_reuse_time_vty(struct vty
*vty
, struct bgp_info
*binfo
,
646 char *timebuf
, size_t len
, u_char use_json
,
649 struct bgp_damp_info
*bdi
;
650 time_t t_now
, t_diff
;
656 /* BGP dampening information. */
657 bdi
= binfo
->extra
->damp_info
;
659 /* If dampening is not enabled or there is no dampening information,
660 return immediately. */
664 /* Calculate new penalty. */
666 t_diff
= t_now
- bdi
->t_updated
;
667 penalty
= bgp_damp_decay(t_diff
, bdi
->penalty
);
669 return bgp_get_reuse_time(penalty
, timebuf
, len
, use_json
, json
);
672 int bgp_show_dampening_parameters(struct vty
*vty
, afi_t afi
, safi_t safi
)
675 bgp
= bgp_get_default();
678 vty_out(vty
, "No BGP process is configured\n");
682 if (CHECK_FLAG(bgp
->af_flags
[afi
][safi
], BGP_CONFIG_DAMPENING
)) {
683 vty_out(vty
, "Half-life time: %lld min\n",
684 (long long)damp
->half_life
/ 60);
685 vty_out(vty
, "Reuse penalty: %d\n", damp
->reuse_limit
);
686 vty_out(vty
, "Suppress penalty: %d\n", damp
->suppress_value
);
687 vty_out(vty
, "Max suppress time: %lld min\n",
688 (long long)damp
->max_suppress_time
/ 60);
689 vty_out(vty
, "Max supress penalty: %u\n", damp
->ceiling
);
692 vty_out(vty
, "dampening not enabled for %s\n",
693 afi
== AFI_IP
? "IPv4" : "IPv6");