ospf_spf.c

router source code for the ospdf.

              zlog_info ("Looking up Network LSA, ID: %s",
                         inet_ntoa(l->link_id));
              w_lsa = ospf_lsa_lookup_by_id (area, OSPF_NETWORK_LSA,
					     l->link_id);
              if (w_lsa)
		  if (IS_DEBUG_OSPF_EVENT)
                zlog_info("found the LSA");
              break;
            default:
	      zlog_warn ("Invalid LSA link type %d", type);
              continue;
            }
        }
      else
        {
          /* In case of V is Network-LSA. */
          r = (struct in_addr *) p ;
          p += sizeof (struct in_addr);

          /* Lookup the vertex W's LSA. */
          w_lsa = ospf_lsa_lookup_by_id (area, OSPF_ROUTER_LSA, *r);
        }

      /* (b cont.) If the LSA does not exist, or its LS age is equal
         to MaxAge, or it does not have a link back to vertex V,
         examine the next link in V's LSA.[23] */
      if (w_lsa == NULL)
        continue;

      if (IS_LSA_MAXAGE (w_lsa))
        continue;

      if (! ospf_lsa_has_link (w_lsa->data, v->lsa))
        {
		  if (IS_DEBUG_OSPF_EVENT)
	  zlog_info ("The LSA doesn't have a link back");
          continue;
        }

      /* (c) If vertex W is already on the shortest-path tree, examine
         the next link in the LSA. */
      if (ospf_spf_has_vertex (rv, nv, w_lsa->data))
        {
		  if (IS_DEBUG_OSPF_EVENT)
          zlog_info ("The LSA is already in SPF");
          continue;
        }

      /* (d) Calculate the link state cost D of the resulting path
         from the root to vertex W.  D is equal to the sum of the link
         state cost of the (already calculated) shortest path to
         vertex V and the advertised cost of the link between vertices
         V and W.  If D is: */

      /* prepare vertex W. */
      w = ospf_vertex_new (w_lsa);

      /* calculate link cost D. */
      if (v->lsa->type == OSPF_ROUTER_LSA)
        w->distance = v->distance + ntohs (l->m[0].metric);
      else
        w->distance = v->distance;

      /* Is there already vertex W in candidate list? */
      node = ospf_vertex_lookup (candidate, w->id, w->type);
      if (node == NULL)
        {
          /* Calculate nexthop to W. */
          ospf_nexthop_calculation (area, v, w);

          ospf_install_candidate (candidate, w);
        }
      else
        {
          cw = (struct vertex *) getdata (node);

          /* if D is greater than. */
          if (cw->distance < w->distance)
            {
              ospf_vertex_free (w);
              continue;
            }
          /* equal to. */
          else if (cw->distance == w->distance)
            {
              /* Calculate nexthop to W. */
              ospf_nexthop_calculation (area, v, w);
              ospf_nexthop_merge (cw->nexthop, w->nexthop);
              list_delete_all_node (w->nexthop);
              ospf_vertex_free (w);
            }
          /* less than. */
          else
            {
              /* Calculate nexthop. */
              ospf_nexthop_calculation (area, v, w);

              /* Remove old vertex from candidate list. */
              ospf_vertex_free (cw);
              listnode_delete (candidate, cw);

              /* Install new to candidate. */
              ospf_install_candidate (candidate, w);
            }
        }
    }
}

/* Add vertex V to SPF tree. */
void
ospf_spf_register (struct vertex *v, struct route_table *rv,
		   struct route_table *nv)
{
  struct prefix p;
  struct route_node *rn;

  p.family = AF_INET;
  p.prefixlen = IPV4_MAX_BITLEN;
  p.u.prefix4 = v->id;

  if (v->type == OSPF_VERTEX_ROUTER)
    rn = route_node_get (rv, &p);
  else
    rn = route_node_get (nv, &p);

  rn->info = v;
}

void
ospf_spf_route_free (struct route_table *table)
{
  struct route_node *rn;
  struct vertex *v;

  for (rn = route_top (table); rn; rn = route_next (rn))
    {
      if ((v = rn->info))
	{
	  ospf_vertex_free (v);
	  rn->info = NULL;
	}

      route_unlock_node (rn);
    }

  route_table_finish (table);
}

void
ospf_spf_dump (struct vertex *v, int i)
{
  listnode cnode;
  listnode nnode;
  struct vertex_nexthop *nexthop;

  if (v->type == OSPF_VERTEX_ROUTER)
    {
      if (IS_DEBUG_OSPF_EVENT)
	zlog_info ("SPF Result: %d [R] %s", i, inet_ntoa (v->lsa->id));
    }
  else
    {
      struct network_lsa *lsa = (struct network_lsa *) v->lsa;
      if (IS_DEBUG_OSPF_EVENT)
	zlog_info ("SPF Result: %d [N] %s/%d", i, inet_ntoa (v->lsa->id),
		   ip_masklen (lsa->mask));

      for (nnode = listhead (v->nexthop); nnode; nextnode (nnode))
        {
          nexthop = getdata (nnode);
	  if (IS_DEBUG_OSPF_EVENT)
	    zlog_info (" nexthop %s", inet_ntoa (nexthop->router));
        }
    }

  i++;

  for (cnode = listhead (v->child); cnode; nextnode (cnode))
    {
      v = getdata (cnode);
      ospf_spf_dump (v, i);
    }
}

/* Second stage of SPF calculation. */
void
ospf_spf_process_stubs (struct ospf_area *area, struct vertex * v,
                        struct route_table *rt)
{
  listnode cnode;
  struct vertex *child;

  if (IS_DEBUG_OSPF_EVENT)
    zlog_info ("ospf_process_stub():processing stubs for area %s",
	       inet_ntoa (area->area_id));
  if (v->type == OSPF_VERTEX_ROUTER)
    {
      u_char *p;
      u_char *lim;
      struct router_lsa_link *l;
      struct router_lsa *rlsa;

  if (IS_DEBUG_OSPF_EVENT)
      zlog_info ("ospf_process_stub():processing router LSA, id: %s",
                 inet_ntoa (v->lsa->id));
      rlsa = (struct router_lsa *) v->lsa;


  if (IS_DEBUG_OSPF_EVENT)
      zlog_info ("ospf_process_stub(): we have %d links to process",
                 ntohs (rlsa->links));
      p = ((u_char *) v->lsa) + 24;
      lim = ((u_char *) v->lsa) + ntohs (v->lsa->length);

      while (p < lim)
        {
          l = (struct router_lsa_link *) p;

          p += (ROUTER_LSA_MIN_SIZE +
                (l->m[0].tos_count * ROUTER_LSA_TOS_SIZE));

          if (l->m[0].type == LSA_LINK_TYPE_STUB)
            ospf_intra_add_stub (rt, l, v, area);
        }
    }

  if (IS_DEBUG_OSPF_EVENT)
  zlog_info ("children of V:");
  for (cnode = listhead (v->child); cnode; nextnode (cnode))
    {
      child = getdata (cnode);
  if (IS_DEBUG_OSPF_EVENT)
      zlog_info (" child : %s", inet_ntoa (child->id));
    }

  for (cnode = listhead (v->child); cnode; nextnode (cnode))
    {
      child = getdata (cnode);

      if (CHECK_FLAG (child->flags, OSPF_VERTEX_PROCESSED))
	continue;

      ospf_spf_process_stubs (area, child, rt);

      SET_FLAG (child->flags, OSPF_VERTEX_PROCESSED);
    }
}

void
ospf_rtrs_free (struct route_table *rtrs)
{
  struct route_node *rn;
  list or_list;
  listnode node;

  if (IS_DEBUG_OSPF_EVENT)
  zlog_info ("Route: Router Routing Table free");

  for (rn = route_top (rtrs); rn; rn = route_next (rn))
    if ((or_list = rn->info) != NULL)
      {
	for (node = listhead (or_list); node; nextnode (node))
	  ospf_route_free (node->data);

	list_delete (or_list);

	/* Unlock the node. */
	rn->info = NULL;
	route_unlock_node (rn);
      }
  route_table_finish (rtrs);
}

void
ospf_rtrs_print (struct route_table *rtrs)
{
  struct route_node *rn;
  list or_list;
  listnode ln;
  listnode pnode;
  struct ospf_route *or;
  struct ospf_path *path;
  char buf1[BUFSIZ];
  char buf2[BUFSIZ];

  if (IS_DEBUG_OSPF_EVENT)
    zlog_info ("ospf_rtrs_print() start");

  for (rn = route_top (rtrs); rn; rn = route_next (rn))
    if ((or_list = rn->info) != NULL)
      for (ln = listhead (or_list); ln; nextnode (ln))
        {
          or = getdata (ln);

          switch (or->path_type)
            {
            case OSPF_PATH_INTRA_AREA:
	      if (IS_DEBUG_OSPF_EVENT)
		zlog_info ("%s   [%d] area: %s", 
			   inet_ntop (AF_INET, &or->id, buf1, BUFSIZ), or->cost,
			   inet_ntop (AF_INET, &or->u.std.area_id,
				      buf2, BUFSIZ));
              break;
            case OSPF_PATH_INTER_AREA:
	      if (IS_DEBUG_OSPF_EVENT)
		zlog_info ("%s IA [%d] area: %s", 
			   inet_ntop (AF_INET, &or->id, buf1, BUFSIZ), or->cost,
			   inet_ntop (AF_INET, &or->u.std.area_id,
				      buf2, BUFSIZ));
              break;
            default:
              break;
            }

          for (pnode = listhead (or->path); pnode; nextnode (pnode))
            {
              path = getdata (pnode);
              if (path->nexthop.s_addr == 0)
		{
		  if (IS_DEBUG_OSPF_EVENT)
		    zlog_info ("   directly attached to %s\r\n",
			       IF_NAME (path->oi));
		}
              else 
		{
		  if (IS_DEBUG_OSPF_EVENT)
		    zlog_info ("   via %s, %s\r\n",
			       inet_ntoa (path->nexthop), IF_NAME (path->oi));
		}
            }
        }

  zlog_info ("ospf_rtrs_print() end");
}

/* Calculating the shortest-path tree for an area. */
void
ospf_spf_calculate (struct ospf_area *area, struct route_table *new_table, 
                    struct route_table *new_rtrs)
{
  list candidate;
  listnode node;
  struct vertex *v;
  struct route_table *rv;
  struct route_table *nv;

  if (IS_DEBUG_OSPF_EVENT)
    {
      zlog_info ("ospf_spf_calculate: Start");
      zlog_info ("ospf_spf_calculate: running Dijkstra for area %s", 
		 inet_ntoa (area->area_id));
    }

  /* Check router-lsa-self.  If self-router-lsa is not yet allocated,
     return this area's calculation. */
  if (! area->router_lsa_self)
    {
      if (IS_DEBUG_OSPF_EVENT)
	zlog_info ("ospf_spf_calculate: "
		   "Skip area %s's calculation due to empty router_lsa_self",
		   inet_ntoa (area->area_id));
      return;
    }

  /* RFC2328 16.1. (1). */
  /* Initialize the algorithm's data structures. */ 
  rv = route_table_init ();
  nv = route_table_init ();

  /* Clear the list of candidate vertices. */ 
  candidate = list_new ();

  /* Initialize the shortest-path tree to only the root (which is the
     router doing the calculation). */
  ospf_spf_init (area);
  v = area->spf;
  ospf_spf_register (v, rv, nv);

  /* Set Area A's TransitCapability to FALSE. */
  area->transit = OSPF_TRANSIT_FALSE;
  area->shortcut_capability = 1;

  for (;;)
    {
      /* RFC2328 16.1. (2). */
      ospf_spf_next (v, area, candidate, rv, nv);

      /* RFC2328 16.1. (3). */
      /* If at this step the candidate list is empty, the shortest-
         path tree (of transit vertices) has been completely built and
         this stage of the procedure terminates. */
      if (listcount (candidate) == 0)
        break;

      /* Otherwise, choose the vertex belonging to the candidate list
         that is closest to the root, and add it to the shortest-path
         tree (removing it from the candidate list in the
         process). */ 
      node = listhead (candidate);
      v = getdata (node);
      ospf_vertex_add_parent (v);

      /* Reveve from the candidate list. */
      listnode_delete (candidate, v);

      /* Add to SPF tree. */
      ospf_spf_register (v, rv, nv);

      /* Note that when there is a choice of vertices closest to the
         root, network vertices must be chosen before router vertices
         in order to necessarily find all equal-cost paths. */
      /* We don't do this at this moment, we should add the treatment
         above codes. -- kunihiro. */

      /* RFC2328 16.1. (4). */
      if (v->type == OSPF_VERTEX_ROUTER)
        ospf_intra_add_router (new_rtrs, v, area);
      else 
        ospf_intra_add_transit (new_table, v, area);

      /* RFC2328 16.1. (5). */
      /* Iterate the algorithm by returning to Step 2. */
    }

  if (IS_DEBUG_OSPF_EVENT)
    {
      ospf_spf_dump (area->spf, 0);
      ospf_route_table_dump (new_table);
    }

  /* Second stage of SPF calculation procedure's  */
  ospf_spf_process_stubs (area, area->spf, new_table);

  /* Free all vertices which allocated for SPF calculation */
  ospf_spf_route_free (rv);
  ospf_spf_route_free (nv);

  /* Free candidate list */
  list_free (candidate);

  /* Increment SPF Calculation Counter. */
  area->spf_calculation++;

  area->ospf->ts_spf = time (NULL);

  if (IS_DEBUG_OSPF_EVENT)
    zlog_info ("ospf_spf_calculate: Stop");
}

/* Timer for SPF calculation. */
int
ospf_spf_calculate_timer (struct thread *thread)
{
  struct ospf *ospf = THREAD_ARG (thread);
  struct route_table *new_table, *new_rtrs;
  listnode node;

  if (IS_DEBUG_OSPF_EVENT)
    zlog_info ("SPF: Timer (SPF calculation expire)");
  
  ospf->t_spf_calc = NULL;

  /* Allocate new table tree. */
  new_table = route_table_init ();
  new_rtrs  = route_table_init ();

  ospf_vl_unapprove (ospf);

  /* Calculate SPF for each area. */
  for (node = listhead (ospf->areas); node; node = nextnode (node))
    ospf_spf_calculate (node->data, new_table, new_rtrs);

  ospf_vl_shut_unapproved (ospf);

  ospf_ia_routing (ospf, new_table, new_rtrs);

  ospf_prune_unreachable_networks (new_table);
  ospf_prune_unreachable_routers (new_rtrs);

  /* AS-external-LSA calculation should not be performed here. */

  /* If new Router Route is installed,
     then schedule re-calculate External routes. */
  if (1)
    ospf_ase_calculate_schedule (ospf);

  ospf_ase_calculate_timer_add (ospf);

  /* Update routing table. */
  ospf_route_install (ospf, new_table);

  /* Update ABR/ASBR routing table */
  if (ospf->old_rtrs)
    {
      /* old_rtrs's node holds linked list of ospf_route. --kunihiro. */
      /* ospf_route_delete (ospf->old_rtrs); */
      ospf_rtrs_free (ospf->old_rtrs);
    }

  ospf->old_rtrs = ospf->new_rtrs;
  ospf->new_rtrs = new_rtrs;

  if (IS_OSPF_ABR (ospf)) 
    ospf_abr_task (ospf);

  if (IS_DEBUG_OSPF_EVENT)
    zlog_info ("SPF: calculation complete");

  return 0;
}

/* Add schedule for SPF calculation.  To avoid frequenst SPF calc, we
   set timer for SPF calc. */
void
ospf_spf_calculate_schedule (struct ospf *ospf)
{
  time_t ht, delay;

  if (IS_DEBUG_OSPF_EVENT)
    zlog_info ("SPF: calculation timer scheduled");

  /* OSPF instance does not exist. */
  if (ospf == NULL)
    return;

  /* SPF calculation timer is already scheduled. */
  if (ospf->t_spf_calc)
    {
      if (IS_DEBUG_OSPF_EVENT)
	zlog_info ("SPF: calculation timer is already scheduled: %p",
		   ospf->t_spf_calc);
      return;
    }

  ht = time (NULL) - ospf->ts_spf;

  /* Get SPF calculation delay time. */
  if (ht < ospf->spf_holdtime)
    {
      if (ospf->spf_holdtime - ht < ospf->spf_delay)
	delay = ospf->spf_delay;
      else
	delay = ospf->spf_holdtime - ht;
    }
  else
    delay = ospf->spf_delay;

  if (IS_DEBUG_OSPF_EVENT)
    zlog_info ("SPF: calculation timer delay = %ld", delay);
  ospf->t_spf_calc =
    thread_add_timer (master, ospf_spf_calculate_timer, ospf, delay);
}