ospf6_spf.c

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

  route->path.metric_type = 1;
  route->path.cost = v->cost;
  route->path.cost_e2 = v->hops;
  route->path.router_bits = v->capability;
  route->path.options[0] = v->options[0];
  route->path.options[1] = v->options[1];
  route->path.options[2] = v->options[2];

  for (i = 0; ospf6_nexthop_is_set (&v->nexthop[i]) &&
       i < OSPF6_MULTI_PATH_LIMIT; i++)
    ospf6_nexthop_copy (&route->nexthop[i], &v->nexthop[i]);

  if (v->parent)
    listnode_add_sort (v->parent->child_list, v);
  route->route_option = v;

  ospf6_route_add (route, result_table);
  return 0;
}

void
ospf6_spf_table_finish (struct ospf6_route_table *result_table)
{
  struct ospf6_route *route;
  struct ospf6_vertex *v;
  for (route = ospf6_route_head (result_table); route;
       route = ospf6_route_next (route))
    {
      v = (struct ospf6_vertex *) route->route_option;
      ospf6_vertex_delete (v);
      ospf6_route_remove (route, result_table);
    }
}

/* RFC2328 16.1.  Calculating the shortest-path tree for an area */
/* RFC2740 3.8.1.  Calculating the shortest path tree for an area */
void
ospf6_spf_calculation (u_int32_t router_id,
                       struct ospf6_route_table *result_table,
                       struct ospf6_area *oa)
{
  struct pqueue *candidate_list;
  struct ospf6_vertex *root, *v, *w;
  int i;
  int size;
  caddr_t lsdesc;
  struct ospf6_lsa *lsa;

  /* initialize */
  candidate_list = pqueue_create ();
  candidate_list->cmp = ospf6_vertex_cmp;

  ospf6_spf_table_finish (result_table);

  /* Install the calculating router itself as the root of the SPF tree */
  /* construct root vertex */
  lsa = ospf6_lsdb_lookup (htons (OSPF6_LSTYPE_ROUTER), htonl (0),
                           router_id, oa->lsdb);
  if (lsa == NULL)
    return;
  root = ospf6_vertex_create (lsa);
  root->area = oa;
  root->cost = 0;
  root->hops = 0;
  root->nexthop[0].ifindex = 0; /* loopbak I/F is better ... */
  inet_pton (AF_INET6, "::1", &root->nexthop[0].address);

  /* Actually insert root to the candidate-list as the only candidate */
  pqueue_enqueue (root, candidate_list);

  /* Iterate until candidate-list becomes empty */
  while (candidate_list->size)
    {
      /* get closest candidate from priority queue */
      v = pqueue_dequeue (candidate_list);

      /* installing may result in merging or rejecting of the vertex */
      if (ospf6_spf_install (v, result_table) < 0)
        continue;

      /* For each LS description in the just-added vertex V's LSA */
      size = (VERTEX_IS_TYPE (ROUTER, v) ?
              sizeof (struct ospf6_router_lsdesc) :
              sizeof (struct ospf6_network_lsdesc));
      for (lsdesc = OSPF6_LSA_HEADER_END (v->lsa->header) + 4;
           lsdesc + size <= OSPF6_LSA_END (v->lsa->header); lsdesc += size)
        {
          lsa = ospf6_lsdesc_lsa (lsdesc, v);
          if (lsa == NULL)
            continue;

          if (! ospf6_lsdesc_backlink (lsa, lsdesc, v))
            continue;

          w = ospf6_vertex_create (lsa);
          w->area = oa;
          w->parent = v;
          if (VERTEX_IS_TYPE (ROUTER, v))
            {
              w->cost = v->cost + ROUTER_LSDESC_GET_METRIC (lsdesc);
              w->hops = v->hops + (VERTEX_IS_TYPE (NETWORK, w) ? 0 : 1);
            }
          else /* NETWORK */
            {
              w->cost = v->cost;
              w->hops = v->hops + 1;
            }

          /* nexthop calculation */
          if (w->hops == 0)
            w->nexthop[0].ifindex = ROUTER_LSDESC_GET_IFID (lsdesc);
          else if (w->hops == 1 && v->hops == 0)
            ospf6_nexthop_calc (w, v, lsdesc);
          else
            {
              for (i = 0; ospf6_nexthop_is_set (&v->nexthop[i]) &&
                   i < OSPF6_MULTI_PATH_LIMIT; i++)
                ospf6_nexthop_copy (&w->nexthop[i], &v->nexthop[i]);
            }

          /* add new candidate to the candidate_list */
          if (IS_OSPF6_DEBUG_SPF (PROCESS))
            zlog_info ("  New candidate: %s hops %d cost %d",
                       w->name, w->hops, w->cost);
          pqueue_enqueue (w, candidate_list);
        }
    }

  pqueue_delete (candidate_list);
}

void
ospf6_spf_log_database (struct ospf6_area *oa)
{
  char *p, *end, buffer[256];
  listnode node;
  struct ospf6_interface *oi;

  p = buffer;
  end = buffer + sizeof (buffer);

  snprintf (p, end - p, "SPF on DB (#LSAs):");
  p = (buffer + strlen (buffer) < end ? buffer + strlen (buffer) : end);
  snprintf (p, end - p, " Area %s: %d", oa->name, oa->lsdb->count);
  p = (buffer + strlen (buffer) < end ? buffer + strlen (buffer) : end);

  for (node = listhead (oa->if_list); node; nextnode (node))
    {
      oi = (struct ospf6_interface *) getdata (node);
      snprintf (p, end - p, " I/F %s: %d",
                oi->interface->name, oi->lsdb->count);
      p = (buffer + strlen (buffer) < end ? buffer + strlen (buffer) : end);
    }

  zlog_info ("%s", buffer);
}

int
ospf6_spf_calculation_thread (struct thread *t)
{
  struct ospf6_area *oa;
  struct timeval start, end, runtime;

  oa = (struct ospf6_area *) THREAD_ARG (t);
  oa->thread_spf_calculation = NULL;

  if (IS_OSPF6_DEBUG_SPF (PROCESS))
    zlog_info ("SPF calculation for Area %s", oa->name);
  if (IS_OSPF6_DEBUG_SPF (DATABASE))
    ospf6_spf_log_database (oa);

  /* execute SPF calculation */
  gettimeofday (&start, (struct timezone *) NULL);
  ospf6_spf_calculation (oa->ospf6->router_id, oa->spf_table, oa);
  gettimeofday (&end, (struct timezone *) NULL);
  timersub (&end, &start, &runtime);

  if (IS_OSPF6_DEBUG_SPF (PROCESS) || IS_OSPF6_DEBUG_SPF (TIME))
    zlog_info ("SPF runtime: %ld sec %ld usec",
               runtime.tv_sec, runtime.tv_usec);

  ospf6_intra_route_calculation (oa);
  ospf6_intra_brouter_calculation (oa);

  return 0;
}

void
ospf6_spf_schedule (struct ospf6_area *oa)
{
  if (oa->thread_spf_calculation)
    return;
  oa->thread_spf_calculation =
    thread_add_event (master, ospf6_spf_calculation_thread, oa, 0);
}

void
ospf6_spf_display_subtree (struct vty *vty, char *prefix, int rest,
                           struct ospf6_vertex *v)
{
  listnode node;
  struct ospf6_vertex *c;
  char *next_prefix;
  int len;
  int restnum;

  /* "prefix" is the space prefix of the display line */
  vty_out (vty, "%s+-%s [%d]%s", prefix, v->name, v->cost, VNL);

  len = strlen (prefix) + 4;
  next_prefix = (char *) malloc (len);
  if (next_prefix == NULL)
    {
      vty_out (vty, "malloc failed%s", VNL);
      return;
    }
  snprintf (next_prefix, len, "%s%s", prefix, (rest ? "|  " : "   "));

  restnum = listcount (v->child_list);
  LIST_LOOP (v->child_list, c, node)
    {
      restnum--;
      ospf6_spf_display_subtree (vty, next_prefix, restnum, c);
    }

  free (next_prefix);
}

DEFUN (debug_ospf6_spf_process,
       debug_ospf6_spf_process_cmd,
       "debug ospf6 spf process",
       DEBUG_STR
       OSPF6_STR
       "Debug SPF Calculation\n"
       "Debug Detailed SPF Process\n"
      )
{
  unsigned char level = 0;
  level = OSPF6_DEBUG_SPF_PROCESS;
  OSPF6_DEBUG_SPF_ON (level);
  return CMD_SUCCESS;
}

DEFUN (debug_ospf6_spf_time,
       debug_ospf6_spf_time_cmd,
       "debug ospf6 spf time",
       DEBUG_STR
       OSPF6_STR
       "Debug SPF Calculation\n"
       "Measure time taken by SPF Calculation\n"
      )
{
  unsigned char level = 0;
  level = OSPF6_DEBUG_SPF_TIME;
  OSPF6_DEBUG_SPF_ON (level);
  return CMD_SUCCESS;
}

DEFUN (debug_ospf6_spf_database,
       debug_ospf6_spf_database_cmd,
       "debug ospf6 spf database",
       DEBUG_STR
       OSPF6_STR
       "Debug SPF Calculation\n"
       "Log number of LSAs at SPF Calculation time\n"
      )
{
  unsigned char level = 0;
  level = OSPF6_DEBUG_SPF_DATABASE;
  OSPF6_DEBUG_SPF_ON (level);
  return CMD_SUCCESS;
}

DEFUN (no_debug_ospf6_spf_process,
       no_debug_ospf6_spf_process_cmd,
       "no debug ospf6 spf process",
       NO_STR
       DEBUG_STR
       OSPF6_STR
       "Quit Debugging SPF Calculation\n"
       "Quit Debugging Detailed SPF Process\n"
      )
{
  unsigned char level = 0;
  level = OSPF6_DEBUG_SPF_PROCESS;
  OSPF6_DEBUG_SPF_OFF (level);
  return CMD_SUCCESS;
}

DEFUN (no_debug_ospf6_spf_time,
       no_debug_ospf6_spf_time_cmd,
       "no debug ospf6 spf time",
       NO_STR
       DEBUG_STR
       OSPF6_STR
       "Quit Debugging SPF Calculation\n"
       "Quit Measuring time taken by SPF Calculation\n"
      )
{
  unsigned char level = 0;
  level = OSPF6_DEBUG_SPF_TIME;
  OSPF6_DEBUG_SPF_OFF (level);
  return CMD_SUCCESS;
}

DEFUN (no_debug_ospf6_spf_database,
       no_debug_ospf6_spf_database_cmd,
       "no debug ospf6 spf database",
       NO_STR
       DEBUG_STR
       OSPF6_STR
       "Debug SPF Calculation\n"
       "Quit Logging number of LSAs at SPF Calculation time\n"
      )
{
  unsigned char level = 0;
  level = OSPF6_DEBUG_SPF_DATABASE;
  OSPF6_DEBUG_SPF_OFF (level);
  return CMD_SUCCESS;
}

int
config_write_ospf6_debug_spf (struct vty *vty)
{
  if (IS_OSPF6_DEBUG_SPF (PROCESS))
    vty_out (vty, "debug ospf6 spf process%s", VNL);
  if (IS_OSPF6_DEBUG_SPF (TIME))
    vty_out (vty, "debug ospf6 spf time%s", VNL);
  if (IS_OSPF6_DEBUG_SPF (DATABASE))
    vty_out (vty, "debug ospf6 spf database%s", VNL);
  return 0;
}

void
install_element_ospf6_debug_spf ()
{
  install_element (ENABLE_NODE, &debug_ospf6_spf_process_cmd);
  install_element (ENABLE_NODE, &debug_ospf6_spf_time_cmd);
  install_element (ENABLE_NODE, &debug_ospf6_spf_database_cmd);
  install_element (ENABLE_NODE, &no_debug_ospf6_spf_process_cmd);
  install_element (ENABLE_NODE, &no_debug_ospf6_spf_time_cmd);
  install_element (ENABLE_NODE, &no_debug_ospf6_spf_database_cmd);
  install_element (CONFIG_NODE, &debug_ospf6_spf_process_cmd);
  install_element (CONFIG_NODE, &debug_ospf6_spf_time_cmd);
  install_element (CONFIG_NODE, &debug_ospf6_spf_database_cmd);
  install_element (CONFIG_NODE, &no_debug_ospf6_spf_process_cmd);
  install_element (CONFIG_NODE, &no_debug_ospf6_spf_time_cmd);
  install_element (CONFIG_NODE, &no_debug_ospf6_spf_database_cmd);
}

void
ospf6_spf_init ()
{
}