Annotation of embedaddon/quagga/bgpd/bgp_damp.c, revision 1.1.1.1
1.1 misho 1: /* BGP flap dampening
2: Copyright (C) 2001 IP Infusion Inc.
3:
4: This file is part of GNU Zebra.
5:
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
9: later version.
10:
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.
15:
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
19: 02111-1307, USA. */
20:
21: #include <zebra.h>
22: #include <math.h>
23:
24: #include "prefix.h"
25: #include "memory.h"
26: #include "command.h"
27: #include "log.h"
28: #include "thread.h"
29:
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"
36:
37: /* Global variable to access damping configuration */
38: struct bgp_damp_config bgp_damp_cfg;
39: static struct bgp_damp_config *damp = &bgp_damp_cfg;
40:
41: /* Utility macro to add and delete BGP dampening information to no
42: used list. */
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)
45:
46: /* Calculate reuse list index by penalty value. */
47: static int
48: bgp_reuse_index (int penalty)
49: {
50: unsigned int i;
51: int index;
52:
53: i = (int)(((double) penalty / damp->reuse_limit - 1.0) * damp->scale_factor);
54:
55: if ( i >= damp->reuse_index_size )
56: i = damp->reuse_index_size - 1;
57:
58: index = damp->reuse_index[i] - damp->reuse_index[0];
59:
60: return (damp->reuse_offset + index) % damp->reuse_list_size;
61: }
62:
63: /* Add BGP dampening information to reuse list. */
64: static void
65: bgp_reuse_list_add (struct bgp_damp_info *bdi)
66: {
67: int index;
68:
69: index = bdi->index = bgp_reuse_index (bdi->penalty);
70:
71: bdi->prev = NULL;
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;
76: }
77:
78: /* Delete BGP dampening information from reuse list. */
79: static void
80: bgp_reuse_list_delete (struct bgp_damp_info *bdi)
81: {
82: if (bdi->next)
83: bdi->next->prev = bdi->prev;
84: if (bdi->prev)
85: bdi->prev->next = bdi->next;
86: else
87: damp->reuse_list[bdi->index] = bdi->next;
88: }
89:
90: /* Return decayed penalty value. */
91: int
92: bgp_damp_decay (time_t tdiff, int penalty)
93: {
94: unsigned int i;
95:
96: i = (int) ((double) tdiff / DELTA_T);
97:
98: if (i == 0)
99: return penalty;
100:
101: if (i >= damp->decay_array_size)
102: return 0;
103:
104: return (int) (penalty * damp->decay_array[i]);
105: }
106:
107: /* Handler of reuse timer event. Each route in the current reuse-list
108: is evaluated. RFC2439 Section 4.8.7. */
109: static int
110: bgp_reuse_timer (struct thread *t)
111: {
112: struct bgp_damp_info *bdi;
113: struct bgp_damp_info *next;
114: time_t t_now, t_diff;
115:
116: damp->t_reuse = NULL;
117: damp->t_reuse =
118: thread_add_timer (master, bgp_reuse_timer, NULL, DELTA_REUSE);
119:
120: t_now = bgp_clock ();
121:
122: /* 1. save a pointer to the current zeroth queue head and zero the
123: list head entry. */
124: bdi = damp->reuse_list[damp->reuse_offset];
125: damp->reuse_list[damp->reuse_offset] = NULL;
126:
127: /* 2. set offset = modulo reuse-list-size ( offset + 1 ), thereby
128: rotating the circular queue of list-heads. */
129: damp->reuse_offset = (damp->reuse_offset + 1) % damp->reuse_list_size;
130:
131: /* 3. if ( the saved list head pointer is non-empty ) */
132: for (; bdi; bdi = next)
133: {
134: struct bgp *bgp = bdi->binfo->peer->bgp;
135:
136: next = bdi->next;
137:
138: /* Set t-diff = t-now - t-updated. */
139: t_diff = t_now - bdi->t_updated;
140:
141: /* Set figure-of-merit = figure-of-merit * decay-array-ok [t-diff] */
142: bdi->penalty = bgp_damp_decay (t_diff, bdi->penalty);
143:
144: /* Set t-updated = t-now. */
145: bdi->t_updated = t_now;
146:
147: /* if (figure-of-merit < reuse). */
148: if (bdi->penalty < damp->reuse_limit)
149: {
150: /* Reuse the route. */
151: bgp_info_unset_flag (bdi->rn, bdi->binfo, BGP_INFO_DAMPED);
152: bdi->suppress_time = 0;
153:
154: if (bdi->lastrecord == BGP_RECORD_UPDATE)
155: {
156: bgp_info_unset_flag (bdi->rn, bdi->binfo, BGP_INFO_HISTORY);
157: bgp_aggregate_increment (bgp, &bdi->rn->p, bdi->binfo,
158: bdi->afi, bdi->safi);
159: bgp_process (bgp, bdi->rn, bdi->afi, bdi->safi);
160: }
161:
162: if (bdi->penalty <= damp->reuse_limit / 2.0)
163: bgp_damp_info_free (bdi, 1);
164: else
165: BGP_DAMP_LIST_ADD (damp, bdi);
166: }
167: else
168: /* Re-insert into another list (See RFC2439 Section 4.8.6). */
169: bgp_reuse_list_add (bdi);
170: }
171:
172: return 0;
173: }
174:
175: /* A route becomes unreachable (RFC2439 Section 4.8.2). */
176: int
177: bgp_damp_withdraw (struct bgp_info *binfo, struct bgp_node *rn,
178: afi_t afi, safi_t safi, int attr_change)
179: {
180: time_t t_now;
181: struct bgp_damp_info *bdi = NULL;
182: double last_penalty = 0;
183:
184: t_now = bgp_clock ();
185:
186: /* Processing Unreachable Messages. */
187: if (binfo->extra)
188: bdi = binfo->extra->damp_info;
189:
190: if (bdi == NULL)
191: {
192: /* If there is no previous stability history. */
193:
194: /* RFC2439 said:
195: 1. allocate a damping structure.
196: 2. set figure-of-merit = 1.
197: 3. withdraw the route. */
198:
199: bdi = XCALLOC (MTYPE_BGP_DAMP_INFO, sizeof (struct bgp_damp_info));
200: bdi->binfo = binfo;
201: bdi->rn = rn;
202: bdi->penalty = (attr_change ? DEFAULT_PENALTY / 2 : DEFAULT_PENALTY);
203: bdi->flap = 1;
204: bdi->start_time = t_now;
205: bdi->suppress_time = 0;
206: bdi->index = -1;
207: bdi->afi = afi;
208: bdi->safi = safi;
209: (bgp_info_extra_get (binfo))->damp_info = bdi;
210: BGP_DAMP_LIST_ADD (damp, bdi);
211: }
212: else
213: {
214: last_penalty = bdi->penalty;
215:
216: /* 1. Set t-diff = t-now - t-updated. */
217: bdi->penalty =
218: (bgp_damp_decay (t_now - bdi->t_updated, bdi->penalty)
219: + (attr_change ? DEFAULT_PENALTY / 2 : DEFAULT_PENALTY));
220:
221: if (bdi->penalty > damp->ceiling)
222: bdi->penalty = damp->ceiling;
223:
224: bdi->flap++;
225: }
226:
227: assert ((rn == bdi->rn) && (binfo == bdi->binfo));
228:
229: bdi->lastrecord = BGP_RECORD_WITHDRAW;
230: bdi->t_updated = t_now;
231:
232: /* Make this route as historical status. */
233: bgp_info_set_flag (rn, binfo, BGP_INFO_HISTORY);
234:
235: /* Remove the route from a reuse list if it is on one. */
236: if (CHECK_FLAG (bdi->binfo->flags, BGP_INFO_DAMPED))
237: {
238: /* If decay rate isn't equal to 0, reinsert brn. */
239: if (bdi->penalty != last_penalty)
240: {
241: bgp_reuse_list_delete (bdi);
242: bgp_reuse_list_add (bdi);
243: }
244: return BGP_DAMP_SUPPRESSED;
245: }
246:
247: /* If not suppressed before, do annonunce this withdraw and
248: insert into reuse_list. */
249: if (bdi->penalty >= damp->suppress_value)
250: {
251: bgp_info_set_flag (rn, binfo, BGP_INFO_DAMPED);
252: bdi->suppress_time = t_now;
253: BGP_DAMP_LIST_DEL (damp, bdi);
254: bgp_reuse_list_add (bdi);
255: }
256:
257: return BGP_DAMP_USED;
258: }
259:
260: int
261: bgp_damp_update (struct bgp_info *binfo, struct bgp_node *rn,
262: afi_t afi, safi_t safi)
263: {
264: time_t t_now;
265: struct bgp_damp_info *bdi;
266: int status;
267:
268: if (!binfo->extra || !((bdi = binfo->extra->damp_info)))
269: return BGP_DAMP_USED;
270:
271: t_now = bgp_clock ();
272: bgp_info_unset_flag (rn, binfo, BGP_INFO_HISTORY);
273:
274: bdi->lastrecord = BGP_RECORD_UPDATE;
275: bdi->penalty = bgp_damp_decay (t_now - bdi->t_updated, bdi->penalty);
276:
277: if (! CHECK_FLAG (bdi->binfo->flags, BGP_INFO_DAMPED)
278: && (bdi->penalty < damp->suppress_value))
279: status = BGP_DAMP_USED;
280: else if (CHECK_FLAG (bdi->binfo->flags, BGP_INFO_DAMPED)
281: && (bdi->penalty < damp->reuse_limit) )
282: {
283: bgp_info_unset_flag (rn, binfo, BGP_INFO_DAMPED);
284: bgp_reuse_list_delete (bdi);
285: BGP_DAMP_LIST_ADD (damp, bdi);
286: bdi->suppress_time = 0;
287: status = BGP_DAMP_USED;
288: }
289: else
290: status = BGP_DAMP_SUPPRESSED;
291:
292: if (bdi->penalty > damp->reuse_limit / 2.0)
293: bdi->t_updated = t_now;
294: else
295: bgp_damp_info_free (bdi, 0);
296:
297: return status;
298: }
299:
300: /* Remove dampening information and history route. */
301: int
302: bgp_damp_scan (struct bgp_info *binfo, afi_t afi, safi_t safi)
303: {
304: time_t t_now, t_diff;
305: struct bgp_damp_info *bdi;
306:
307: assert (binfo->extra && binfo->extra->damp_info);
308:
309: t_now = bgp_clock ();
310: bdi = binfo->extra->damp_info;
311:
312: if (CHECK_FLAG (binfo->flags, BGP_INFO_DAMPED))
313: {
314: t_diff = t_now - bdi->suppress_time;
315:
316: if (t_diff >= damp->max_suppress_time)
317: {
318: bgp_info_unset_flag (bdi->rn, binfo, 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;
324:
325: /* Need to announce UPDATE once this binfo is usable again. */
326: if (bdi->lastrecord == BGP_RECORD_UPDATE)
327: return 1;
328: else
329: return 0;
330: }
331: }
332: else
333: {
334: t_diff = t_now - bdi->t_updated;
335: bdi->penalty = bgp_damp_decay (t_diff, bdi->penalty);
336:
337: if (bdi->penalty <= damp->reuse_limit / 2.0)
338: {
339: /* release the bdi, bdi->binfo. */
340: bgp_damp_info_free (bdi, 1);
341: return 0;
342: }
343: else
344: bdi->t_updated = t_now;
345: }
346: return 0;
347: }
348:
349: void
350: bgp_damp_info_free (struct bgp_damp_info *bdi, int withdraw)
351: {
352: struct bgp_info *binfo;
353:
354: if (! bdi)
355: return;
356:
357: binfo = bdi->binfo;
358: binfo->extra->damp_info = NULL;
359:
360: if (CHECK_FLAG (binfo->flags, BGP_INFO_DAMPED))
361: bgp_reuse_list_delete (bdi);
362: else
363: BGP_DAMP_LIST_DEL (damp, bdi);
364:
365: bgp_info_unset_flag (bdi->rn, binfo, BGP_INFO_HISTORY|BGP_INFO_DAMPED);
366:
367: if (bdi->lastrecord == BGP_RECORD_WITHDRAW && withdraw)
368: bgp_info_delete (bdi->rn, binfo);
369:
370: XFREE (MTYPE_BGP_DAMP_INFO, bdi);
371: }
372:
373: static void
374: bgp_damp_parameter_set (int hlife, int reuse, int sup, int maxsup)
375: {
376: double reuse_max_ratio;
377: unsigned int i;
378: double j;
379:
380: damp->suppress_value = sup;
381: damp->half_life = hlife;
382: damp->reuse_limit = reuse;
383: damp->max_suppress_time = maxsup;
384:
385: /* Initialize params per bgp_damp_config. */
386: damp->reuse_index_size = REUSE_ARRAY_SIZE;
387:
388: damp->ceiling = (int)(damp->reuse_limit * (pow(2, (double)damp->max_suppress_time/damp->half_life)));
389:
390: /* Decay-array computations */
391: damp->decay_array_size = ceil ((double) damp->max_suppress_time / DELTA_T);
392: damp->decay_array = XMALLOC (MTYPE_BGP_DAMP_ARRAY,
393: sizeof(double) * (damp->decay_array_size));
394: damp->decay_array[0] = 1.0;
395: damp->decay_array[1] = exp ((1.0/((double)damp->half_life/DELTA_T)) * log(0.5));
396:
397: /* Calculate decay values for all possible times */
398: for (i = 2; i < damp->decay_array_size; i++)
399: damp->decay_array[i] = damp->decay_array[i-1] * damp->decay_array[1];
400:
401: /* Reuse-list computations */
402: i = ceil ((double)damp->max_suppress_time / DELTA_REUSE) + 1;
403: if (i > REUSE_LIST_SIZE || i == 0)
404: i = REUSE_LIST_SIZE;
405: damp->reuse_list_size = i;
406:
407: damp->reuse_list = XCALLOC (MTYPE_BGP_DAMP_ARRAY,
408: damp->reuse_list_size
409: * sizeof (struct bgp_reuse_node *));
410:
411: /* Reuse-array computations */
412: damp->reuse_index = XCALLOC (MTYPE_BGP_DAMP_ARRAY,
413: sizeof(int) * damp->reuse_index_size);
414:
415: reuse_max_ratio = (double)damp->ceiling/damp->reuse_limit;
416: j = (exp((double)damp->max_suppress_time/damp->half_life) * log10(2.0));
417: if ( reuse_max_ratio > j && j != 0 )
418: reuse_max_ratio = j;
419:
420: damp->scale_factor = (double)damp->reuse_index_size/(reuse_max_ratio - 1);
421:
422: for (i = 0; i < damp->reuse_index_size; i++)
423: {
424: damp->reuse_index[i] =
425: (int)(((double)damp->half_life / DELTA_REUSE)
426: * log10 (1.0 / (damp->reuse_limit * ( 1.0 + ((double)i/damp->scale_factor)))) / log10(0.5));
427: }
428: }
429:
430: int
431: bgp_damp_enable (struct bgp *bgp, afi_t afi, safi_t safi, time_t half,
432: unsigned int reuse, unsigned int suppress, time_t max)
433: {
434: if (CHECK_FLAG (bgp->af_flags[afi][safi], BGP_CONFIG_DAMPENING))
435: {
436: if (damp->half_life == half
437: && damp->reuse_limit == reuse
438: && damp->suppress_value == suppress
439: && damp->max_suppress_time == max)
440: return 0;
441: bgp_damp_disable (bgp, afi, safi);
442: }
443:
444: SET_FLAG (bgp->af_flags[afi][safi], BGP_CONFIG_DAMPENING);
445: bgp_damp_parameter_set (half, reuse, suppress, max);
446:
447: /* Register reuse timer. */
448: if (! damp->t_reuse)
449: damp->t_reuse =
450: thread_add_timer (master, bgp_reuse_timer, NULL, DELTA_REUSE);
451:
452: return 0;
453: }
454:
455: static void
456: bgp_damp_config_clean (struct bgp_damp_config *damp)
457: {
458: /* Free decay array */
459: XFREE (MTYPE_BGP_DAMP_ARRAY, damp->decay_array);
460:
461: /* Free reuse index array */
462: XFREE (MTYPE_BGP_DAMP_ARRAY, damp->reuse_index);
463:
464: /* Free reuse list array. */
465: XFREE (MTYPE_BGP_DAMP_ARRAY, damp->reuse_list);
466: }
467:
468: /* Clean all the bgp_damp_info stored in reuse_list. */
469: void
470: bgp_damp_info_clean (void)
471: {
472: unsigned int i;
473: struct bgp_damp_info *bdi, *next;
474:
475: damp->reuse_offset = 0;
476:
477: for (i = 0; i < damp->reuse_list_size; i++)
478: {
479: if (! damp->reuse_list[i])
480: continue;
481:
482: for (bdi = damp->reuse_list[i]; bdi; bdi = next)
483: {
484: next = bdi->next;
485: bgp_damp_info_free (bdi, 1);
486: }
487: damp->reuse_list[i] = NULL;
488: }
489:
490: for (bdi = damp->no_reuse_list; bdi; bdi = next)
491: {
492: next = bdi->next;
493: bgp_damp_info_free (bdi, 1);
494: }
495: damp->no_reuse_list = NULL;
496: }
497:
498: int
499: bgp_damp_disable (struct bgp *bgp, afi_t afi, safi_t safi)
500: {
501: /* Cancel reuse thread. */
502: if (damp->t_reuse )
503: thread_cancel (damp->t_reuse);
504: damp->t_reuse = NULL;
505:
506: /* Clean BGP dampening information. */
507: bgp_damp_info_clean ();
508:
509: /* Clear configuration */
510: bgp_damp_config_clean (&bgp_damp_cfg);
511:
512: UNSET_FLAG (bgp->af_flags[afi][safi], BGP_CONFIG_DAMPENING);
513: return 0;
514: }
515:
516: void
517: bgp_config_write_damp (struct vty *vty)
518: {
519: if (bgp_damp_cfg.half_life == DEFAULT_HALF_LIFE*60
520: && bgp_damp_cfg.reuse_limit == DEFAULT_REUSE
521: && bgp_damp_cfg.suppress_value == DEFAULT_SUPPRESS
522: && bgp_damp_cfg.max_suppress_time == bgp_damp_cfg.half_life*4)
523: vty_out (vty, " bgp dampening%s", VTY_NEWLINE);
524: else 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 %ld%s",
529: bgp_damp_cfg.half_life/60,
530: VTY_NEWLINE);
531: else
532: vty_out (vty, " bgp dampening %ld %d %d %ld%s",
533: bgp_damp_cfg.half_life/60,
534: bgp_damp_cfg.reuse_limit,
535: bgp_damp_cfg.suppress_value,
536: bgp_damp_cfg.max_suppress_time/60,
537: VTY_NEWLINE);
538: }
539:
540: static const char *
541: bgp_get_reuse_time (unsigned int penalty, char *buf, size_t len)
542: {
543: time_t reuse_time = 0;
544: struct tm *tm = NULL;
545:
546: if (penalty > damp->reuse_limit)
547: {
548: reuse_time = (int) (DELTA_T * ((log((double)damp->reuse_limit/penalty))/(log(damp->decay_array[1]))));
549:
550: if (reuse_time > damp->max_suppress_time)
551: reuse_time = damp->max_suppress_time;
552:
553: tm = gmtime (&reuse_time);
554: }
555: else
556: reuse_time = 0;
557:
558: /* Making formatted timer strings. */
559: #define ONE_DAY_SECOND 60*60*24
560: #define ONE_WEEK_SECOND 60*60*24*7
561: if (reuse_time == 0)
562: snprintf (buf, len, "00:00:00");
563: else if (reuse_time < ONE_DAY_SECOND)
564: snprintf (buf, len, "%02d:%02d:%02d",
565: tm->tm_hour, tm->tm_min, tm->tm_sec);
566: else if (reuse_time < ONE_WEEK_SECOND)
567: snprintf (buf, len, "%dd%02dh%02dm",
568: tm->tm_yday, tm->tm_hour, tm->tm_min);
569: else
570: snprintf (buf, len, "%02dw%dd%02dh",
571: tm->tm_yday/7, tm->tm_yday - ((tm->tm_yday/7) * 7), tm->tm_hour);
572:
573: return buf;
574: }
575:
576: void
577: bgp_damp_info_vty (struct vty *vty, struct bgp_info *binfo)
578: {
579: struct bgp_damp_info *bdi;
580: time_t t_now, t_diff;
581: char timebuf[BGP_UPTIME_LEN];
582: int penalty;
583:
584: if (!binfo->extra)
585: return;
586:
587: /* BGP dampening information. */
588: bdi = binfo->extra->damp_info;
589:
590: /* If dampening is not enabled or there is no dampening information,
591: return immediately. */
592: if (! damp || ! bdi)
593: return;
594:
595: /* Calculate new penalty. */
596: t_now = bgp_clock ();
597: t_diff = t_now - bdi->t_updated;
598: penalty = bgp_damp_decay (t_diff, bdi->penalty);
599:
600: vty_out (vty, " Dampinfo: penalty %d, flapped %d times in %s",
601: penalty, bdi->flap,
602: peer_uptime (bdi->start_time, timebuf, BGP_UPTIME_LEN));
603:
604: if (CHECK_FLAG (binfo->flags, BGP_INFO_DAMPED)
605: && ! CHECK_FLAG (binfo->flags, BGP_INFO_HISTORY))
606: vty_out (vty, ", reuse in %s",
607: bgp_get_reuse_time (penalty, timebuf, BGP_UPTIME_LEN));
608:
609: vty_out (vty, "%s", VTY_NEWLINE);
610: }
611:
612: const char *
613: bgp_damp_reuse_time_vty (struct vty *vty, struct bgp_info *binfo,
614: char *timebuf, size_t len)
615: {
616: struct bgp_damp_info *bdi;
617: time_t t_now, t_diff;
618: int penalty;
619:
620: if (!binfo->extra)
621: return NULL;
622:
623: /* BGP dampening information. */
624: bdi = binfo->extra->damp_info;
625:
626: /* If dampening is not enabled or there is no dampening information,
627: return immediately. */
628: if (! damp || ! bdi)
629: return NULL;
630:
631: /* Calculate new penalty. */
632: t_now = bgp_clock ();
633: t_diff = t_now - bdi->t_updated;
634: penalty = bgp_damp_decay (t_diff, bdi->penalty);
635:
636: return bgp_get_reuse_time (penalty, timebuf, len);
637: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to bgp_damp.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / quagga / bgpd