ospf6_damp.c

router source code for the ipv6 ospdf ,it can use for wireless.

/*
 * OSPF flap dampening by Manav Bhatia
 * Copyright (C) 2002 
 * 
 * This file is part of GNU Zebra.
 * 
 * GNU Zebra is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the
 * Free Software Foundation; either version 2, or (at your option) any
 * later version.
 * 
 * GNU Zebra is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with GNU Zebra; see the file COPYING.  If not, write to the Free
 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
 * 02111-1307, USA.  
 */

#include <zebra.h>
#include <math.h>

#include "log.h"
#include "prefix.h"
#include "thread.h"
#include "table.h"
#include "command.h"
#include "vty.h"

extern struct thread_master *master;

#include "ospf6_damp.h"

#ifdef HAVE_OSPF6_DAMP

#define DELTA_REUSE         10 /* Time granularity for reuse lists */
#define DELTA_T              5 /* Time granularity for decay arrays */
#define DEFAULT_HALF_LIFE   60 /* (sec)     1 min */

#define DEFAULT_PENALTY   1000
#define DEFAULT_REUSE      750
#define DEFAULT_SUPPRESS  2000

#define REUSE_LIST_SIZE    256
#define REUSE_ARRAY_SIZE  1024

/* Global variable to access damping configuration */
struct ospf6_damp_config damp_config;
struct ospf6_damp_config *dc = &damp_config;
u_int reuse_array_offset = 0;
struct route_table *damp_info_table[OSPF6_DAMP_TYPE_MAX];
struct thread *ospf6_reuse_thread = NULL;

int ospf6_damp_debug = 0;
#define IS_OSPF6_DEBUG_DAMP (ospf6_damp_debug)

static struct ospf6_damp_info *
ospf6_damp_lookup (u_short type, struct prefix *name)
{
  struct route_node *node;

  node = route_node_lookup (damp_info_table[type], name);
  if (node && node->info)
    return (struct ospf6_damp_info *) node->info;
  return NULL;
}

static struct ospf6_damp_info *
ospf6_damp_create (u_short type, struct prefix *name)
{
  struct route_node *node;
  struct ospf6_damp_info *di;
  char namebuf[64];

  di = ospf6_damp_lookup (type, name);
  if (di)
    return di;

  if (IS_OSPF6_DEBUG_DAMP)
    {
      prefix2str (name, namebuf, sizeof (namebuf));
      zlog_info ("DAMP: create: type: %d, name: %s", type, namebuf);
    }

  di = (struct ospf6_damp_info *)
    malloc (sizeof (struct ospf6_damp_info));
  memset (di, 0, sizeof (struct ospf6_damp_info));
  di->type = type;
  prefix_copy (&di->name, name);

  node = route_node_get (damp_info_table[type], name);
  node->info = di;

  return di;
}

static void
ospf6_damp_delete (u_short type, struct prefix *name)
{
  struct route_node *node;
  struct ospf6_damp_info *di;
  char namebuf[64];

  node = route_node_lookup (damp_info_table[type], name);
  if (! node || ! node->info)
    return;

  di = node->info;

  if (IS_OSPF6_DEBUG_DAMP)
    {
      prefix2str (&di->name, namebuf, sizeof (namebuf));
      zlog_info ("DAMP: delete: type: %d, name: %s",
                 di->type, namebuf);
    }

  node->info = NULL;
  free (di);
}

/* compute and fill the configuration parameter */
void
ospf6_damp_init_config (u_int half_life, u_int reuse,
                        u_int suppress, u_int t_hold)
{
  int i;
  double max_ratio, max_ratio1, max_ratio2;

  dc->half_life = half_life ? half_life : DEFAULT_HALF_LIFE;
  dc->reuse     = reuse     ? reuse     : DEFAULT_REUSE;
  dc->suppress  = suppress  ? suppress  : DEFAULT_SUPPRESS;
  dc->t_hold    = t_hold    ? t_hold    : 4 * dc->half_life;

  /* Initialize system-wide params */
  dc->delta_t = DELTA_T;
  dc->delta_reuse = DELTA_REUSE;
  dc->default_penalty = DEFAULT_PENALTY;
  dc->reuse_index_array_size = REUSE_ARRAY_SIZE;

  /* ceiling is the maximum penalty a route may attain */
  /* ceiling = reuse * 2^(T-hold/half-life) */
  dc->ceiling = (int)
    (dc->reuse * (pow (2, (double) dc->t_hold / dc->half_life)));

  /* Decay-array computations */
  /* decay_array_size = decay memory/time granularity */
  dc->decay_array_size = ceil ((double) dc->t_hold / dc->delta_t);
  dc->decay_array = malloc (sizeof (double) * (dc->decay_array_size));

  /* Each i-th element is per tick delay raised to the i-th power */
  dc->decay_array[0] = 1.0;
  dc->decay_array[1] = exp ((1.0 / (dc->half_life / dc->delta_t)) * log (0.5));
  for (i = 2; i < dc->decay_array_size; i++)
    dc->decay_array[i] = dc->decay_array[i - 1] * dc->decay_array[1];

  /* Reuse-list computations (reuse queue head array ?) */
  dc->reuse_list_size = ceil ((double) dc->t_hold / dc->delta_reuse) + 1;
  if (dc->reuse_list_size == 0 || dc->reuse_list_size > REUSE_LIST_SIZE)
    dc->reuse_list_size = REUSE_LIST_SIZE;
  dc->reuse_list_array = (struct ospf6_damp_info **)
    malloc (dc->reuse_list_size * sizeof (struct ospf6_reuse_list *));
  memset (dc->reuse_list_array, 0x00,
          dc->reuse_list_size * sizeof (struct ospf6_reuse_list *));

  /* Reuse-array computations */
  dc->reuse_index_array = malloc (sizeof (int) * dc->reuse_index_array_size);

  /*
   * This is the maximum ratio between the current value of the penalty and
   * the reuse value which can be indexed by the reuse array. It will be 
   * limited by the ceiling or by the amount of time that the reuse list 
   * covers 
   */
  max_ratio1 = (double) dc->ceiling / dc->reuse;
  max_ratio2 = exp ((double) dc->t_hold / dc->half_life) * log10 (2.0);
  max_ratio = (max_ratio2 != 0 && max_ratio2 < max_ratio1 ?
               max_ratio2 : max_ratio1);

  /*
   * reuse array is just an estimator and we need something
   * to use the full array 
   */
  dc->scale_factor = (double) dc->reuse_index_array_size / (max_ratio - 1);

  for (i = 0; i < dc->reuse_index_array_size; i++)
    {
      dc->reuse_index_array[i] = (int)
        (((double) dc->half_life / dc->delta_reuse) *
         log10 (1.0 / (dc->reuse * (1.0 + ((double) i / dc->scale_factor))))
         / log10 (0.5));
    }

  dc->enabled = ON;
}

static double
ospf6_damp_decay (time_t tdiff)
{
  int index = tdiff / dc->delta_t;

  if (index >= dc->decay_array_size)
    return 0;

  return dc->decay_array[index];
}

static int
ospf6_damp_reuse_index (int penalty)
{
  int index;

  index = (int) (((double) penalty / dc->reuse - 1.0) * dc->scale_factor);

  if (index >= dc->reuse_index_array_size)
    index = dc->reuse_index_array_size - 1;

  return (dc->reuse_index_array[index] - dc->reuse_index_array[0]);
}

static int
ospf6_reuse_list_lookup (struct ospf6_damp_info *di)
{
  struct ospf6_damp_info *info;

  for (info = dc->reuse_list_array[di->index]; info; info = info->next)
    {
      if (info == di)
        return 1;
    }
  return 0;
}

static void
ospf6_reuse_list_remove (struct ospf6_damp_info *di)
{
  if (di->prev)
    di->prev->next = di->next;
  else
    dc->reuse_list_array[di->index] = di->next;
  if (di->next)
    di->next->prev = di->prev;

  di->index = -1;
  di->prev = NULL;
  di->next = NULL;
}

static void
ospf6_reuse_list_add (struct ospf6_damp_info *di)
{
  /* set the index of reuse-array */
  di->index = (reuse_array_offset + (ospf6_damp_reuse_index (di->penalty)))
              % dc->reuse_list_size;

  /* insert to the head of the reuse list */
  di->next = dc->reuse_list_array[di->index];
  if (di->next)
    di->next->prev = di;
  di->prev = NULL;
  dc->reuse_list_array[di->index] = di;
}

/* When we quit damping for a target, we should execute proper event
   which have been postponed during damping */
static void
ospf6_damp_stop (struct ospf6_damp_info *di)
{
  time_t t_now;
  char namebuf[64];
  struct timeval now;

  if (IS_OSPF6_DEBUG_DAMP)
    {
      t_now = time (NULL);
      prefix2str (&di->name, namebuf, sizeof (namebuf));
      gettimeofday (&now, NULL);
      zlog_info ("DAMP: %lu.%06lu stop damping: %ld: type: %d, name: %s",
                 now.tv_sec, now.tv_usec,
                 t_now, di->type, namebuf);
    }

  /* set flag indicates that we're damping this target */
  di->damping = OFF;

  /* if the target's current status differ from that it should be,
     execute the proper event to repair his status */
  if (di->target_status != di->event_type)
    {
      (*(di->event)) (di->target);
      di->target_status = di->event_type;

      di->event = NULL;
      di->event_type = event_none;
    }
}

/* ospf6_reuse_timer is called every DELTA_REUSE seconds.
   Each route in the current reuse-list is evaluated
   and is used or requeued */
int
ospf6_damp_reuse_timer (struct thread *t)
{
  struct ospf6_damp_info *di, *next;
  time_t t_now, t_diff;
  char namebuf[64];
  struct timeval now;

  /* Restart the reuse timer */
  ospf6_reuse_thread =
    thread_add_timer (master, ospf6_damp_reuse_timer, NULL, dc->delta_reuse);

  t_now = time (NULL);

  /* get the damp info list head */
  di = dc->reuse_list_array[reuse_array_offset];
  dc->reuse_list_array[reuse_array_offset] = NULL;

  /* rotate the circular reuse list head array */
  reuse_array_offset = (reuse_array_offset + 1) % dc->reuse_list_size;

  /* for each damp info */
  while (di)
    {
      next = di->next;
      di->next = NULL;

      /* Update penalty */
      t_diff = t_now - di->t_updated;
      di->t_updated = t_now;
      di->penalty = (int)
        ((double) di->penalty * ospf6_damp_decay (t_diff));
      /* configration of ceiling may be just changed */
      if (di->penalty > dc->ceiling)
        di->penalty = dc->ceiling;

      if (IS_OSPF6_DEBUG_DAMP)
        {
          prefix2str (&di->name, namebuf, sizeof (namebuf));
          gettimeofday (&now, NULL);
          zlog_info ("DAMP: %lu.%06lu update penalty: type: %d, name: %s, penalty: %d",
                     now.tv_sec, now.tv_usec,
                     di->type, namebuf, di->penalty);
        }

      /* If the penalty becomes under reuse,
         call real event that we have been postponed. */
      if (di->penalty < dc->reuse && di->damping == ON)
        ospf6_damp_stop (di);

      /* If the penalty becomes less than the half of the
         reuse value, this damp info will be freed from reuse-list,
         by assuming that it is considered to be stable enough already,
         and there's no need to maintain flapping history for this. */
      if (di->penalty <= dc->reuse / 2)
        {
          ospf6_damp_delete (di->type, &di->name);
          di = next;
          continue;
        }

      /* re-insert to the reuse-list */
      ospf6_reuse_list_add (di);

      di = next;
    }

  return 0;
}

static void
ospf6_damp_event (damp_event_t event_type,
                  u_short type, struct prefix *name,