ospf6_flood.c

linux 路由软件 可支持RIP OSPF BGP等

/*
 * Copyright (C) 2003 Yasuhiro Ohara
 *
 * 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 "log.h"
#include "thread.h"
#include "linklist.h"
#include "vty.h"
#include "command.h"

#include "ospf6d.h"
#include "ospf6_proto.h"
#include "ospf6_lsa.h"
#include "ospf6_lsdb.h"
#include "ospf6_message.h"
#include "ospf6_route.h"
#include "ospf6_spf.h"

#include "ospf6_top.h"
#include "ospf6_area.h"
#include "ospf6_interface.h"
#include "ospf6_neighbor.h"

#include "ospf6_flood.h"

unsigned char conf_debug_ospf6_flooding;

struct ospf6_lsdb *
ospf6_get_scoped_lsdb (struct ospf6_lsa *lsa)
{
  struct ospf6_lsdb *lsdb = NULL;
  switch (OSPF6_LSA_SCOPE (lsa->header->type))
    {
    case OSPF6_SCOPE_LINKLOCAL:
      lsdb = OSPF6_INTERFACE (lsa->lsdb->data)->lsdb;
      break;
    case OSPF6_SCOPE_AREA:
      lsdb = OSPF6_AREA (lsa->lsdb->data)->lsdb;
      break;
    case OSPF6_SCOPE_AS:
      lsdb = OSPF6_PROCESS (lsa->lsdb->data)->lsdb;
      break;
    default:
      assert (0);
      break;
    }
  return lsdb;
}

struct ospf6_lsdb *
ospf6_get_scoped_lsdb_self (struct ospf6_lsa *lsa)
{
  struct ospf6_lsdb *lsdb_self = NULL;
  switch (OSPF6_LSA_SCOPE (lsa->header->type))
    {
    case OSPF6_SCOPE_LINKLOCAL:
      lsdb_self = OSPF6_INTERFACE (lsa->lsdb->data)->lsdb_self;
      break;
    case OSPF6_SCOPE_AREA:
      lsdb_self = OSPF6_AREA (lsa->lsdb->data)->lsdb_self;
      break;
    case OSPF6_SCOPE_AS:
      lsdb_self = OSPF6_PROCESS (lsa->lsdb->data)->lsdb_self;
      break;
    default:
      assert (0);
      break;
    }
  return lsdb_self;
}

void
ospf6_lsa_originate (struct ospf6_lsa *lsa)
{
  struct ospf6_lsa *old;
  struct ospf6_lsdb *lsdb_self;

  /* find previous LSA */
  old = ospf6_lsdb_lookup (lsa->header->type, lsa->header->id,
                           lsa->header->adv_router, lsa->lsdb);

  /* if the new LSA does not differ from previous,
     suppress this update of the LSA */
  if (old && ! OSPF6_LSA_IS_DIFFER (lsa, old))
    {
      if (IS_OSPF6_DEBUG_ORIGINATE_TYPE (lsa->header->type))
        zlog_info ("Suppress updating LSA: %s", lsa->name);
      ospf6_lsa_delete (lsa);
      return;
    }

  /* store it in the LSDB for self-originated LSAs */
  lsdb_self = ospf6_get_scoped_lsdb_self (lsa);
  ospf6_lsdb_add (ospf6_lsa_copy (lsa), lsdb_self);

  lsa->refresh = thread_add_timer (master, ospf6_lsa_refresh, lsa,
                                   LS_REFRESH_TIME);

  if (IS_OSPF6_DEBUG_LSA_TYPE (lsa->header->type) ||
      IS_OSPF6_DEBUG_ORIGINATE_TYPE (lsa->header->type))
    {
      zlog_info ("LSA Originate:");
      ospf6_lsa_header_print (lsa);
    }

  if (old)
    ospf6_flood_clear (old);
  ospf6_flood (NULL, lsa);
  ospf6_install_lsa (lsa);
}

void
ospf6_lsa_originate_process (struct ospf6_lsa *lsa,
                             struct ospf6 *process)
{
  lsa->lsdb = process->lsdb;
  ospf6_lsa_originate (lsa);
}

void
ospf6_lsa_originate_area (struct ospf6_lsa *lsa,
                          struct ospf6_area *oa)
{
  lsa->lsdb = oa->lsdb;
  ospf6_lsa_originate (lsa);
}

void
ospf6_lsa_originate_interface (struct ospf6_lsa *lsa,
                               struct ospf6_interface *oi)
{
  lsa->lsdb = oi->lsdb;
  ospf6_lsa_originate (lsa);
}

void
ospf6_lsa_purge (struct ospf6_lsa *lsa)
{
  struct ospf6_lsa *self;
  struct ospf6_lsdb *lsdb_self;

  /* remove it from the LSDB for self-originated LSAs */
  lsdb_self = ospf6_get_scoped_lsdb_self (lsa);
  self = ospf6_lsdb_lookup (lsa->header->type, lsa->header->id,
                            lsa->header->adv_router, lsdb_self);
  if (self)
    {
      THREAD_OFF (self->expire);
      THREAD_OFF (self->refresh);
      ospf6_lsdb_remove (self, lsdb_self);
    }

  ospf6_lsa_premature_aging (lsa);
}


void
ospf6_increment_retrans_count (struct ospf6_lsa *lsa)
{
  /* The LSA must be the original one (see the description
     in ospf6_decrement_retrans_count () below) */
  lsa->retrans_count++;
}

void
ospf6_decrement_retrans_count (struct ospf6_lsa *lsa)
{
  struct ospf6_lsdb *lsdb;
  struct ospf6_lsa *orig;

  /* The LSA must be on the retrans-list of a neighbor. It means
     the "lsa" is a copied one, and we have to decrement the
     retransmission count of the original one (instead of this "lsa"'s).
     In order to find the original LSA, first we have to find
     appropriate LSDB that have the original LSA. */
  lsdb = ospf6_get_scoped_lsdb (lsa);

  /* Find the original LSA of which the retrans_count should be decremented */
  orig = ospf6_lsdb_lookup (lsa->header->type, lsa->header->id,
                            lsa->header->adv_router, lsdb);
  if (orig)
    {
      orig->retrans_count--;
      assert (orig->retrans_count >= 0);
    }
}

/* RFC2328 section 13.2 Installing LSAs in the database */
void
ospf6_install_lsa (struct ospf6_lsa *lsa)
{
  struct ospf6_lsa *old;
  struct timeval now;

  if (IS_OSPF6_DEBUG_LSA_TYPE (lsa->header->type) ||
      IS_OSPF6_DEBUG_EXAMIN_TYPE (lsa->header->type))
    zlog_info ("Install LSA: %s", lsa->name);

  /* Remove the old instance from all neighbors' Link state
     retransmission list (RFC2328 13.2 last paragraph) */
  old = ospf6_lsdb_lookup (lsa->header->type, lsa->header->id,
                           lsa->header->adv_router, lsa->lsdb);
  if (old)
    {
      THREAD_OFF (old->expire);
      ospf6_flood_clear (old);
    }

  gettimeofday (&now, (struct timezone *) NULL);
  if (! OSPF6_LSA_IS_MAXAGE (lsa))
    lsa->expire = thread_add_timer (master, ospf6_lsa_expire, lsa,
                                    MAXAGE + lsa->birth.tv_sec - now.tv_sec);
  else
    lsa->expire = NULL;

  /* actually install */
  lsa->installed = now;
  ospf6_lsdb_add (lsa, lsa->lsdb);

  return;
}

/* RFC2740 section 3.5.2. Sending Link State Update packets */
/* RFC2328 section 13.3 Next step in the flooding procedure */
void
ospf6_flood_interface (struct ospf6_neighbor *from,
                       struct ospf6_lsa *lsa, struct ospf6_interface *oi)
{
  listnode node;
  struct ospf6_neighbor *on;
  struct ospf6_lsa *req;
  int retrans_added = 0;
  int is_debug = 0;

  if (IS_OSPF6_DEBUG_FLOODING ||
      IS_OSPF6_DEBUG_FLOOD_TYPE (lsa->header->type))
    {
      is_debug++;
      zlog_info ("Flooding on %s: %s", oi->interface->name, lsa->name);
    }

  /* (1) For each neighbor */
  for (node = listhead (oi->neighbor_list); node; nextnode (node))
    {
      on = (struct ospf6_neighbor *) getdata (node);

      if (is_debug)
        zlog_info ("To neighbor %s", on->name);

      /* (a) if neighbor state < Exchange, examin next */
      if (on->state < OSPF6_NEIGHBOR_EXCHANGE)
        {
          if (is_debug)
            zlog_info ("Neighbor state less than ExChange, next neighbor");
          continue;
        }

      /* (b) if neighbor not yet Full, check request-list */
      if (on->state != OSPF6_NEIGHBOR_FULL)
        {
          if (is_debug)
            zlog_info ("Neighbor not yet Full");

          req = ospf6_lsdb_lookup (lsa->header->type, lsa->header->id,
                                   lsa->header->adv_router, on->request_list);
          if (req == NULL)
            {
              if (is_debug)
                zlog_info ("Not on request-list for this neighbor");
              /* fall through */
            }
          else
            {
              /* If new LSA less recent, examin next neighbor */
              if (ospf6_lsa_compare (lsa, req) > 0)
                {
                  if (is_debug)
                    zlog_info ("Requesting is newer, next neighbor");
                  continue;
                }

              /* If the same instance, delete from request-list and
                 examin next neighbor */
              if (ospf6_lsa_compare (lsa, req) == 0)
                {
                  if (is_debug)
                    zlog_info ("Requesting the same, remove it, next neighbor");
                  ospf6_lsdb_remove (req, on->request_list);
                  continue;
                }

              /* If the new LSA is more recent, delete from request-list */
              if (ospf6_lsa_compare (lsa, req) < 0)
                {
                  if (is_debug)
                    zlog_info ("Received is newer, remove requesting");
                  ospf6_lsdb_remove (req, on->request_list);
                  /* fall through */
                }
            }
        }

      /* (c) If the new LSA was received from this neighbor,
         examin next neighbor */
      if (from == on)
        {
          if (is_debug)
            zlog_info ("Received is from the neighbor, next neighbor");
          continue;
        }

      /* (d) add retrans-list, schedule retransmission */
      if (is_debug)
        zlog_info ("Add retrans-list of this neighbor");
      ospf6_increment_retrans_count (lsa);
      ospf6_lsdb_add (ospf6_lsa_copy (lsa), on->retrans_list);
      if (on->thread_send_lsupdate == NULL)
        on->thread_send_lsupdate =
          thread_add_event (master, ospf6_lsupdate_send_neighbor,
                            on, on->ospf6_if->rxmt_interval);
      retrans_added++;
    }

  /* (2) examin next interface if not added to retrans-list */
  if (retrans_added == 0)
    {
      if (is_debug)
        zlog_info ("No retransmission scheduled, next interface");
      return;
    }