tc_set.c

wifi 无线网络路由协议OLSR linux下C代码

/*
 * The olsr.org Optimized Link-State Routing daemon(olsrd)
 * Copyright (c) 2004, Andreas Tønnesen([e-mail])
 * LSDB rewrite (c) 2007, Hannes Gredler ([e-mail])
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without 
 * modification, are permitted provided that the following conditions 
 * are met:
 *
 * * Redistributions of source code must retain the above copyright 
 *   notice, this list of conditions and the following disclaimer.
 * * Redistributions in binary form must reproduce the above copyright 
 *   notice, this list of conditions and the following disclaimer in 
 *   the documentation and/or other materials provided with the 
 *   distribution.
 * * Neither the name of olsr.org, olsrd nor the names of its 
 *   contributors may be used to endorse or promote products derived 
 *   from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 
 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 
 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 
 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 
 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 
 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
 * POSSIBILITY OF SUCH DAMAGE.
 *
 * Visit http://www.olsr.org for more information.
 *
 * If you find this software useful feel free to make a donation
 * to the project. For more information see the website or contact
 * the copyright holders.
 *
 * $Id: tc_set.c,v 1.32 2007/10/17 07:30:34 bernd67 Exp $
 */

#include "tc_set.h"
#include "olsr.h"
#include "scheduler.h"
#include "lq_route.h"
#include "lq_avl.h"
#include "assert.h"

/* Root of the link state database */
struct avl_tree tc_tree;
struct tc_entry *tc_myself; /* Shortcut to ourselves */

/**
 * Initialize the topology set
 *
 */
int
olsr_init_tc(void)
{
  OLSR_PRINTF(5, "TC: init topo\n");

  olsr_register_timeout_function(&olsr_time_out_tc_set, OLSR_TRUE);

  avl_init(&tc_tree, avl_comp_default);

  /*
   * Add a TC entry for ourselves.
   */
  tc_myself = olsr_add_tc_entry(&olsr_cnf->main_addr);
  return 1;
}

/**
 * The main ip address has changed.
 * Do the needful.
 */
void
olsr_change_myself_tc(void)
{
  struct tc_edge_entry *tc_edge;

  if (tc_myself) {

    /*
     * Check if there was a change.
     */
    if (COMP_IP(&tc_myself->addr, &olsr_cnf->main_addr)) {
      return;
    }

    /*
     * Flush all edges. This causes our own tc_entry to vanish.
     */
    OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc_myself, tc_edge) {
      olsr_delete_tc_edge_entry(tc_edge);
    } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc_myself, tc_edge);
  }

  /*
   * The old entry for ourselves is gone, generate a new one and trigger SPF.
   */
  tc_myself = olsr_add_tc_entry(&olsr_cnf->main_addr);
  changes_topology = OLSR_TRUE;
}

/**
 * Delete a TC entry.
 *
 * @param entry the TC entry to delete
 *
 */
static void
olsr_delete_tc_entry(struct tc_entry *tc)
{

#if 0
  OLSR_PRINTF(1, "TC: del entry %s\n", olsr_ip_to_string(&tc->addr));
#endif

  /* The edgetree must be empty before */
  assert(!tc->edge_tree.count);

  avl_delete(&tc_tree, &tc->vertex_node);
  free(tc);
}

/**
 * Look up a entry from the TC tree based on address
 *
 * @param adr the address to look for
 * @return the entry found or NULL
 */
struct tc_entry *
olsr_lookup_tc_entry(union olsr_ip_addr *adr)
{
  struct avl_node *node;

#if 0
  OLSR_PRINTF(1, "TC: lookup entry\n");
#endif

  node = avl_find(&tc_tree, adr);

  if (node) {
    return node->data;
  }

  return NULL;
}

/**
 * Grab the next topology entry.
 *
 * @param adr the address to look for
 * @return the entry found or NULL
 */
struct tc_entry *
olsr_getnext_tc_entry(struct tc_entry *tc)
{
  struct avl_node *node;

  node = avl_walk_next(&tc->vertex_node);

  if (node) {
    return node->data;
  }

  return NULL;
}

/**
 * Add a new tc_entry to the tc tree
 *
 * @param (last)adr address of the entry
 * @return a pointer to the created entry
 */
struct tc_entry *
olsr_add_tc_entry(union olsr_ip_addr *adr)
{
  struct tc_entry *tc;

#if 0
  OLSR_PRINTF(1, "TC: add entry %s\n", olsr_ip_to_string(adr));
#endif

  tc = olsr_malloc(sizeof(struct tc_entry), "add TC entry");
  if (!tc) {
    return NULL;
  }
  memset(tc, 0, sizeof(struct tc_entry));

  /* Fill entry */
  COPY_IP(&tc->addr, adr);
  tc->vertex_node.data = tc;
  tc->vertex_node.key = &tc->addr;

  /*
   * Insert into the global tc tree.
   */
  avl_insert(&tc_tree, &tc->vertex_node, AVL_DUP_NO);

  /*
   * Initialize subtree for further edges to come.
   */
  avl_init(&tc->edge_tree, avl_comp_default);

  return tc;
}

/**
 * format a tc_edge contents into a buffer
 */
char *
olsr_tc_edge_to_string(struct tc_edge_entry *tc_edge)
{
  struct tc_entry *tc;
  static char buff[128];

  tc = tc_edge->tc;

  snprintf(buff, sizeof(buff),
           "%s > %s, lq %.3f, inv-lq %.3f, etx %.3f",
           olsr_ip_to_string(&tc->addr),
           olsr_ip_to_string(&tc_edge->T_dest_addr),
           tc_edge->link_quality,
           tc_edge->inverse_link_quality,
           tc_edge->etx);

  return buff;
}

/**
 * Set the TC edge expiration timer.
 *
 * all timer setting shall be done using this function since
 * it does also the correct insertion and sorting in the timer tree.
 * The timer param is a relative timer expressed in milliseconds.
 */
static void
olsr_set_tc_edge_timer(struct tc_edge_entry *tc_edge, unsigned int timer)
{
  tc_edge->T_time = GET_TIMESTAMP(timer);
}

/*
 * If the edge does not have a minimum acceptable link quality
 * set the etx cost to infinity such that it gets ignored during
 * SPF calculation.
 */
void
olsr_calc_tc_edge_entry_etx(struct tc_edge_entry *tc_edge)
{
  if (tc_edge->link_quality >= MIN_LINK_QUALITY &&
      tc_edge->inverse_link_quality >= MIN_LINK_QUALITY) {
        
    tc_edge->etx = 1.0 / (tc_edge->link_quality * tc_edge->inverse_link_quality);
  } else {
    tc_edge->etx = INFINITE_ETX;
  }
}

/**
 * Add a new tc_edge_entry to the tc_edge_tree
 *
 * @param (last)adr address of the entry
 * @return a pointer to the created entry
 */
struct tc_edge_entry *
olsr_add_tc_edge_entry(struct tc_entry *tc, union olsr_ip_addr *addr,
                       olsr_u16_t ansn, unsigned int vtime,
                       float link_quality, float neigh_link_quality)
{
  struct tc_entry *tc_neighbor;
  struct tc_edge_entry *tc_edge, *tc_edge_inv;

  tc_edge = olsr_malloc(sizeof(struct tc_edge_entry), "add TC edge");
  if (!tc_edge) {
    return NULL;
  }
  memset(tc_edge, 0, sizeof(struct tc_edge_entry));

  /* Fill entry */
  COPY_IP(&tc_edge->T_dest_addr, addr);
  olsr_set_tc_edge_timer(tc_edge, vtime*1000);
  tc_edge->T_seq = ansn;
  tc_edge->edge_node.data = tc_edge;
  tc_edge->edge_node.key = &tc_edge->T_dest_addr;

  if (olsr_cnf->lq_level > 0) {

    tc_edge->link_quality = neigh_link_quality;
    tc_edge->inverse_link_quality = link_quality;

  } else {

    /*
     * Set the link quality to 1.0 to mimikry a hopcount alike
     * behaviour for nodes not supporting the LQ extensions.
     */
    tc_edge->link_quality = 1.0;
    tc_edge->inverse_link_quality = 1.0;
  }

  /*
   * Insert into the edge tree.
   */
  avl_insert(&tc->edge_tree, &tc_edge->edge_node, AVL_DUP_NO);

  /*
   * Connect backpointer.
   */
  tc_edge->tc = tc;

#if 0
  OLSR_PRINTF(1, "TC: add edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
#endif

  /*
   * Check if the neighboring router and the inverse edge is in the lsdb.
   * Create short cuts to the inverse edge for faster SPF execution.
   */
  tc_neighbor = olsr_lookup_tc_entry(&tc_edge->T_dest_addr);
  if (tc_neighbor) {

#if 0
    OLSR_PRINTF(1, "TC:   found neighbor tc_entry %s\n",
                olsr_ip_to_string(&tc_neighbor->addr));
#endif

    tc_edge_inv = olsr_lookup_tc_edge(tc_neighbor, &tc->addr);