ospf_flood.c

router source code for the ospdf.

/*
 * OSPF Flooding -- RFC2328 Section 13.
 * Copyright (C) 1999, 2000 Toshiaki Takada
 *
 * 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 "linklist.h"
#include "prefix.h"
#include "if.h"
#include "command.h"
#include "table.h"
#include "thread.h"
#include "memory.h"
#include "log.h"
#include "zclient.h"

#include "ospfd/ospfd.h"
#include "ospfd/ospf_interface.h"
#include "ospfd/ospf_ism.h"
#include "ospfd/ospf_asbr.h"
#include "ospfd/ospf_lsa.h"
#include "ospfd/ospf_lsdb.h"
#include "ospfd/ospf_neighbor.h"
#include "ospfd/ospf_nsm.h"
#include "ospfd/ospf_spf.h"
#include "ospfd/ospf_flood.h"
#include "ospfd/ospf_packet.h"
#include "ospfd/ospf_abr.h"
#include "ospfd/ospf_route.h"
#include "ospfd/ospf_zebra.h"
#include "ospfd/ospf_dump.h"

extern struct zclient *zclient;

/* Do the LSA acking specified in table 19, Section 13.5, row 2
 * This get called from ospf_flood_out_interface. Declared inline 
 * for speed. */
static void
ospf_flood_delayed_lsa_ack (struct ospf_neighbor *inbr, struct ospf_lsa *lsa)
{
  /* LSA is more recent than database copy, but was not
     flooded back out receiving interface.  Delayed
     acknowledgment sent. If interface is in Backup state
     delayed acknowledgment sent only if advertisement
     received from Designated Router, otherwise do nothing See
     RFC 2328 Section 13.5 */

  /* Whether LSA is more recent or not, and whether this is in
     response to the LSA being sent out recieving interface has been 
     worked out previously */

  /* Deal with router as BDR */
  if (inbr->oi->state == ISM_Backup && ! NBR_IS_DR (inbr))
    return;

  /* Schedule a delayed LSA Ack to be sent */ 
  listnode_add (inbr->oi->ls_ack, ospf_lsa_lock (lsa));
}

/* Check LSA is related to external info. */
struct external_info *
ospf_external_info_check (struct ospf_lsa *lsa)
{
  struct as_external_lsa *al;
  struct prefix_ipv4 p;
  struct route_node *rn;
  int type;

  al = (struct as_external_lsa *) lsa->data;

  p.family = AF_INET;
  p.prefix = lsa->data->id;
  p.prefixlen = ip_masklen (al->mask);

  for (type = 0; type <= ZEBRA_ROUTE_MAX; type++)
    {
      int redist_type = is_prefix_default (&p) ? DEFAULT_ROUTE : type;
      if (ospf_is_type_redistributed (redist_type))
	if (EXTERNAL_INFO (type))
	  {
	    rn = route_node_lookup (EXTERNAL_INFO (type),
				    (struct prefix *) &p);
	    if (rn)
	      {
		route_unlock_node (rn);
		if (rn->info != NULL)
		  return (struct external_info *) rn->info;
	      }
	  }
    }

  return NULL;
}

void
ospf_process_self_originated_lsa (struct ospf *ospf,
				  struct ospf_lsa *new, struct ospf_area *area)
{
  struct ospf_interface *oi;
  struct external_info *ei;
  listnode node;
  
  if (IS_DEBUG_OSPF_EVENT)
    zlog_info ("LSA[Type%d:%s]: Process self-originated LSA",
	       new->data->type, inet_ntoa (new->data->id));

  /* If we're here, we installed a self-originated LSA that we received
     from a neighbor, i.e. it's more recent.  We must see whether we want
     to originate it.
     If yes, we should use this LSA's sequence number and reoriginate
     a new instance.
     if not --- we must flush this LSA from the domain. */
  switch (new->data->type)
    {
    case OSPF_ROUTER_LSA:
      /* Originate a new instance and schedule flooding */
      /* It shouldn't be necessary, but anyway */
      ospf_lsa_unlock (area->router_lsa_self);
      area->router_lsa_self = ospf_lsa_lock (new);

      ospf_router_lsa_timer_add (area);
      return;
    case OSPF_NETWORK_LSA:
#ifdef HAVE_OPAQUE_LSA
    case OSPF_OPAQUE_LINK_LSA:
#endif /* HAVE_OPAQUE_LSA */
      /* We must find the interface the LSA could belong to.
	 If the interface is no more a broadcast type or we are no more
	 the DR, we flush the LSA otherwise -- create the new instance and
	 schedule flooding. */

      /* Look through all interfaces, not just area, since interface
	 could be moved from one area to another. */
      for (node = listhead (ospf->oiflist); node; nextnode (node))
	/* These are sanity check. */
	if ((oi = getdata (node)) != NULL)
	  if (IPV4_ADDR_SAME (&oi->address->u.prefix4, &new->data->id))
	    {
	      if (oi->area != area ||
		  oi->type != OSPF_IFTYPE_BROADCAST ||
		  !IPV4_ADDR_SAME (&oi->address->u.prefix4, &DR (oi)))
		{
		  ospf_schedule_lsa_flush_area (area, new);
		  return;
		}
	      
#ifdef HAVE_OPAQUE_LSA
              if (new->data->type == OSPF_OPAQUE_LINK_LSA)
                {
                  ospf_opaque_lsa_refresh (new);
                  return;
                }
#endif /* HAVE_OPAQUE_LSA */

	      ospf_lsa_unlock (oi->network_lsa_self);
	      oi->network_lsa_self = ospf_lsa_lock (new);
	      
	      /* Schedule network-LSA origination. */
	      ospf_network_lsa_timer_add (oi);
	      return;
	    }
      break;
    case OSPF_SUMMARY_LSA:
    case OSPF_ASBR_SUMMARY_LSA:
      ospf_schedule_abr_task (ospf);
      break;
    case OSPF_AS_EXTERNAL_LSA :
#ifdef HAVE_NSSA
    case OSPF_AS_NSSA_LSA:
#endif /* HAVE_NSSA */
      ei = ospf_external_info_check (new);
      if (ei)
	ospf_external_lsa_refresh (ospf, new, ei, LSA_REFRESH_FORCE);
      else
	ospf_lsa_flush_as (ospf, new);
      break;
#ifdef HAVE_OPAQUE_LSA
    case OSPF_OPAQUE_AREA_LSA:
      ospf_opaque_lsa_refresh (new);
      break;
    case OSPF_OPAQUE_AS_LSA:
      ospf_opaque_lsa_refresh (new); /* Reconsideration may needed. *//* XXX */
      break;
#endif /* HAVE_OPAQUE_LSA */
    default:
      break;
    }
}

/* OSPF LSA flooding -- RFC2328 Section 13.(5). */

/* Now Updated for NSSA operation, as follows:


	Type-5's have no change.  Blocked to STUB or NSSA.

	Type-7's can be received, and if a DR
	they will also flood the local NSSA Area as Type-7's

	If a Self-Originated LSA (now an ASBR), 
	The LSDB will be updated as Type-5's, (for continual re-fresh)

	    If an NSSA-IR it is installed/flooded as Type-7, P-bit on.
	    if an NSSA-ABR it is installed/flooded as Type-7, P-bit off.

	Later, during the ABR TASK, if the ABR is the Elected NSSA
	translator, then All Type-7s (with P-bit ON) are Translated to
	Type-5's and flooded to all non-NSSA/STUB areas.

	During ASE Calculations, 
	    non-ABRs calculate external routes from Type-7's
	    ABRs calculate external routes from Type-5's and non-self Type-7s
*/
int
ospf_flood (struct ospf *ospf, struct ospf_neighbor *nbr,
	    struct ospf_lsa *current, struct ospf_lsa *new)
{
  struct ospf_interface *oi;
  struct timeval now;
  int lsa_ack_flag;

  /* Type-7 LSA's will be flooded throughout their native NSSA area,
     but will also be flooded as Type-5's into ABR capable links.  */

  if (IS_DEBUG_OSPF_EVENT)
    zlog_info ("LSA[Flooding]: start, NBR %s (%s), cur(%p), New-LSA[%s]",
               inet_ntoa (nbr->router_id),
               LOOKUP (ospf_nsm_state_msg, nbr->state),
               current,
               dump_lsa_key (new));

  lsa_ack_flag = 0;
  oi = nbr->oi;

  /* Get current time. */
  gettimeofday (&now, NULL);

  /* If there is already a database copy, and if the
     database copy was received via flooding and installed less
     than MinLSArrival seconds ago, discard the new LSA
     (without acknowledging it). */
  if (current != NULL)		/* -- endo. */
    {
      if (IS_LSA_SELF (current)
      && (ntohs (current->data->ls_age)    == 0
      &&  ntohl (current->data->ls_seqnum) == OSPF_INITIAL_SEQUENCE_NUMBER))
        {
          if (IS_DEBUG_OSPF_EVENT)
	    zlog_info ("LSA[Flooding]: Got a self-originated LSA, "
		       "while local one is initial instance.");
          ; /* Accept this LSA for quick LSDB resynchronization. */
        }
      else if (tv_cmp (tv_sub (now, current->tv_recv),
	               int2tv (OSPF_MIN_LS_ARRIVAL)) < 0)
        {
          if (IS_DEBUG_OSPF_EVENT)
	    zlog_info ("LSA[Flooding]: LSA is received recently.");
          return -1;
        }
    }

  /* Flood the new LSA out some subset of the router's interfaces.
     In some cases (e.g., the state of the receiving interface is
     DR and the LSA was received from a router other than the
     Backup DR) the LSA will be flooded back out the receiving
     interface. */
  lsa_ack_flag = ospf_flood_through (ospf, nbr, new);

#ifdef HAVE_OPAQUE_LSA
  /* Remove the current database copy from all neighbors' Link state
     retransmission lists.  AS_EXTERNAL and AS_EXTERNAL_OPAQUE does
                                        ^^^^^^^^^^^^^^^^^^^^^^^
     not have area ID.
     All other (even NSSA's) do have area ID.  */
#else /* HAVE_OPAQUE_LSA */
  /* Remove the current database copy from all neighbors' Link state
     retransmission lists.  Only AS_EXTERNAL does not have area ID.
     All other (even NSSA's) do have area ID.  */
#endif /* HAVE_OPAQUE_LSA */
  if (current)
    {
      switch (current->data->type)
        {
        case OSPF_AS_EXTERNAL_LSA:
#ifdef HAVE_OPAQUE_LSA
        case OSPF_OPAQUE_AS_LSA:
#endif /* HAVE_OPAQUE_LSA */
          ospf_ls_retransmit_delete_nbr_as (ospf, current);
          break;
        default:
          ospf_ls_retransmit_delete_nbr_area (nbr->oi->area, current);
          break;
        }
    }

  /* Do some internal house keeping that is needed here */
  SET_FLAG (new->flags, OSPF_LSA_RECEIVED);
  ospf_lsa_is_self_originated (ospf, new); /* Let it set the flag */

  /* Install the new LSA in the link state database
     (replacing the current database copy).  This may cause the
     routing table calculation to be scheduled.  In addition,
     timestamp the new LSA with the current time.  The flooding
     procedure cannot overwrite the newly installed LSA until
     MinLSArrival seconds have elapsed. */  

  new = ospf_lsa_install (ospf, nbr->oi, new);

  /* Acknowledge the receipt of the LSA by sending a Link State
     Acknowledgment packet back out the receiving interface. */
  if (lsa_ack_flag)
    ospf_flood_delayed_lsa_ack (nbr, new);     

  /* If this new LSA indicates that it was originated by the
     receiving router itself, the router must take special action,
     either updating the LSA or in some cases flushing it from
     the routing domain. */
  if (ospf_lsa_is_self_originated (ospf, new))
    ospf_process_self_originated_lsa (ospf, new, oi->area);
  else
    /* Update statistics value for OSPF-MIB. */
    ospf->rx_lsa_count++;