link_set.c

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

/*
 * The olsr.org Optimized Link-State Routing daemon(olsrd)
 * Copyright (c) 2004, Andreas T鴑nesen([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: link_set.c,v 1.74 2007/10/05 20:10:24 bernd67 Exp $
 */


/*
 * Link sensing database for the OLSR routing daemon
 */

#include "defs.h"
#include "link_set.h"
#include "hysteresis.h"
#include "mid_set.h"
#include "mpr.h"
#include "neighbor_table.h"
#include "olsr.h"
#include "scheduler.h"
#include "lq_route.h"


static clock_t hold_time_neighbor;

struct link_entry *link_set;


static int
check_link_status(const struct hello_message *message, const struct interface *in_if);

static void
olsr_time_out_hysteresis(void);

static void olsr_time_out_packet_loss(void);

static struct link_entry *
add_link_entry(const union olsr_ip_addr *, const union olsr_ip_addr *, const union olsr_ip_addr *, double, double, const struct interface *);

static void
olsr_time_out_link_set(void);

static int
get_neighbor_status(const union olsr_ip_addr *);


clock_t 
get_hold_time_neighbor(void)
{
  return hold_time_neighbor;
}

struct link_entry *
get_link_set(void)
{
  return link_set;
}

void
olsr_init_link_set(void)
{

  /* Timers */
  hold_time_neighbor = (NEIGHB_HOLD_TIME*1000) / olsr_cnf->system_tick_divider;

  olsr_register_timeout_function(&olsr_time_out_link_set, OLSR_TRUE);
  if(olsr_cnf->use_hysteresis)
    {
      olsr_register_timeout_function(&olsr_time_out_hysteresis, OLSR_TRUE);
    }

  if (olsr_cnf->lq_level > 0)
    {
      olsr_register_timeout_function(&olsr_time_out_packet_loss, OLSR_TRUE);
    }
}



/**
 * Get the status of a link. The status is based upon different
 * timeouts in the link entry.
 *
 *@param remote address of the remote interface
 *
 *@return the link status of the link
 */
int
lookup_link_status(const struct link_entry *entry)
{

  if(entry == NULL || link_set == NULL)
    return UNSPEC_LINK;

  /*
   * Hysteresis
   */
  if(olsr_cnf->use_hysteresis)
    {
      /*
	if L_LOST_LINK_time is not expired, the link is advertised
	with a link type of LOST_LINK.
      */

      if(!TIMED_OUT(entry->L_LOST_LINK_time))
	return LOST_LINK;
      /*
	otherwise, if L_LOST_LINK_time is expired and L_link_pending
	is set to "true", the link SHOULD NOT be advertised at all;
      */
      if(entry->L_link_pending == 1)
	{
#ifdef DEBUG
	  OLSR_PRINTF(3, "HYST[%s]: Setting to HIDE\n", olsr_ip_to_string(&entry->neighbor_iface_addr));
#endif
	  return HIDE_LINK;
	}
      /*
	otherwise, if L_LOST_LINK_time is expired and L_link_pending
	is set to "false", the link is advertised as described
	previously in section 6.
      */
    }

  if(!TIMED_OUT(entry->SYM_time))
    return SYM_LINK;

  if(!TIMED_OUT(entry->ASYM_time))
    return ASYM_LINK;

  return LOST_LINK;


}






/**
 *Find the "best" link status to a
 *neighbor
 *
 *@param address the address to check for
 *
 *@return SYM_LINK if a symmetric link exists 0 if not
 */
static int
get_neighbor_status(const union olsr_ip_addr *address)
{
  const union olsr_ip_addr *main_addr;
  struct interface   *ifs;

  //printf("GET_NEIGHBOR_STATUS\n");

  /* Find main address */
  if(!(main_addr = mid_lookup_main_addr(address)))
    main_addr = address;

  //printf("\tmain: %s\n", olsr_ip_to_string(main_addr));

  /* Loop trough local interfaces to check all possebilities */
  for(ifs = ifnet; ifs != NULL; ifs = ifs->int_next)
    {
      struct mid_address   *aliases;
      struct link_entry  *lnk = lookup_link_entry(main_addr, NULL, ifs);

      //printf("\tChecking %s->", olsr_ip_to_string(&ifs->ip_addr));
      //printf("%s : ", olsr_ip_to_string(main_addr)); 
      if(lnk != NULL)
	{
	  //printf("%d\n", lookup_link_status(link));
	  if(lookup_link_status(lnk) == SYM_LINK)
	    return SYM_LINK;
	}
      /* Get aliases */
      for(aliases = mid_lookup_aliases(main_addr);
	  aliases != NULL;
	  aliases = aliases->next_alias)
	{
	  //printf("\tChecking %s->", olsr_ip_to_string(&ifs->ip_addr));
	  //printf("%s : ", olsr_ip_to_string(&aliases->address)); 
            lnk = lookup_link_entry(&aliases->alias, NULL, ifs);
            if(lnk != NULL)
	    {
	      //printf("%d\n", lookup_link_status(link));

	      if(lookup_link_status(lnk) == SYM_LINK)
		return SYM_LINK;
	    }
	}
    }
  
  return 0;
}

/**
 * Find best link to a neighbor
 */

struct link_entry *
get_best_link_to_neighbor(const union olsr_ip_addr *remote)
{
  const union olsr_ip_addr *main_addr;
  struct link_entry *walker, *good_link, *backup_link;
  int curr_metric = MAX_IF_METRIC;
  float curr_lq = -1.0;
  
  // main address lookup

  main_addr = mid_lookup_main_addr(remote);

  // "remote" *already is* the main address

  if (main_addr == NULL)
    main_addr = remote;

  // we haven't selected any links, yet

  good_link = NULL;
  backup_link = NULL;

  // loop through all links that we have

  for (walker = link_set; walker != NULL; walker = walker->next)
  {
    // if this is not a link to the neighour in question, skip

    if (!COMP_IP(&walker->neighbor->neighbor_main_addr, main_addr))
      continue;

    // handle the non-LQ, RFC-compliant case

    if (olsr_cnf->lq_level == 0)
    {
      struct interface *tmp_if;

      // find the interface for the link - we select the link with the
      // best local interface metric
      tmp_if = walker->if_name ? if_ifwithname(walker->if_name) :
              if_ifwithaddr(&walker->local_iface_addr);

      if(!tmp_if)
	continue;

      // is this interface better than anything we had before?

      if ((tmp_if->int_metric < curr_metric) ||
          // use the requested remote interface address as a tie-breaker
          ((tmp_if->int_metric == curr_metric) && 
           COMP_IP(&walker->local_iface_addr, remote)))
      {
        // memorize the interface's metric

        curr_metric = tmp_if->int_metric;

        // prefer symmetric links over asymmetric links

        if (lookup_link_status(walker) == SYM_LINK)
          good_link = walker;

        else
          backup_link = walker;
      }
    }

    // handle the LQ, non-RFC compliant case

    else
    {
      float tmp_lq;

      // calculate the bi-directional link quality - we select the link
      // with the best link quality

      tmp_lq = walker->loss_link_quality * walker->neigh_link_quality;

      // is this link better than anything we had before?
	      
      if((tmp_lq > curr_lq) ||
         // use the requested remote interface address as a tie-breaker
         ((tmp_lq == curr_lq) && COMP_IP(&walker->local_iface_addr, remote)))
      {
        // memorize the link quality

        curr_lq = tmp_lq;

        // prefer symmetric links over asymmetric links

        if(lookup_link_status(walker) == SYM_LINK)
          good_link = walker;

        else
          backup_link = walker;
      }
    }
  }

  // if we haven't found any symmetric links, try to return an
  // asymmetric link

  return good_link ? good_link : backup_link;
}

static void set_loss_link_multiplier(struct link_entry *entry)
{
  struct interface *inter;
  struct olsr_if *cfg_inter;
  struct olsr_lq_mult *mult;
  float val = -1.0;
  union olsr_ip_addr null_addr;

  // find the interface for the link

  inter = if_ifwithaddr(&entry->local_iface_addr);

  // find the interface configuration for the interface

  for (cfg_inter = olsr_cnf->interfaces; cfg_inter != NULL;
       cfg_inter = cfg_inter->next)
    if (cfg_inter->interf == inter)
      break;

  // create a null address for comparison

  memset(&null_addr, 0, sizeof (union olsr_ip_addr));

  // loop through the multiplier entries

  for (mult = cfg_inter->cnf->lq_mult; mult != NULL; mult = mult->next)
  {
    // use the default multiplier only if there isn't any entry that
    // has a matching IP address

    if ((COMP_IP(&mult->addr, &null_addr) && val < 0.0) ||
        COMP_IP(&mult->addr, &entry->neighbor_iface_addr))
      val = mult->val;
  }

  // if we have not found an entry, then use the default multiplier

  if (val < 0)
    val = 1.0;

  // store the multiplier

  entry->loss_link_multiplier = val;
}

/**
 *Delete all interface link entries
 *
 *@param interface ip address
 */

void
del_if_link_entries(const union olsr_ip_addr *int_addr)
{
  struct link_entry *tmp_link_set, *last_link_entry;

  if(link_set == NULL)
    return;

  tmp_link_set = link_set;
  last_link_entry = NULL;

  while(tmp_link_set)
    {

      if(COMP_IP(int_addr, &tmp_link_set->local_iface_addr))
        {
          if(last_link_entry != NULL)
            {
              last_link_entry->next = tmp_link_set->next;

              /* Delete neighbor entry */
              if(tmp_link_set->neighbor->linkcount == 1)
                olsr_delete_neighbor_table(&tmp_link_set->neighbor->neighbor_main_addr);
              else
                tmp_link_set->neighbor->linkcount--;

              //olsr_delete_neighbor_if_no_link(&tmp_link_set->neighbor->neighbor_main_addr);
              changes_neighborhood = OLSR_TRUE;

              free(tmp_link_set);
              tmp_link_set = last_link_entry;
            }
          else
            {
              link_set = tmp_link_set->next; /* CHANGED */

              /* Delete neighbor entry */
              if(tmp_link_set->neighbor->linkcount == 1)
                olsr_delete_neighbor_table(&tmp_link_set->neighbor->neighbor_main_addr);
              else
                tmp_link_set->neighbor->linkcount--;

              changes_neighborhood = OLSR_TRUE;

              free(tmp_link_set);
              tmp_link_set = link_set;
              continue;
            }
        }

      last_link_entry = tmp_link_set;
      tmp_link_set = tmp_link_set->next;
    }

  return;
}

/**
 *Nothing mysterious here.
 *Adding a new link entry to the link set.
 *
 *@param local the local IP address
 *@param remote the remote IP address
 *@param remote_main the remote nodes main address
 *@param vtime the validity time of the entry
 *@param htime the HELLO interval of the remote node
 *@param local_if the local interface
 */

static struct link_entry *
add_link_entry(const union olsr_ip_addr *local,
               const union olsr_ip_addr *remote,
               const union olsr_ip_addr *remote_main,
               double vtime,
               double htime,
               const struct interface *local_if)
{
  struct link_entry *new_link;
  struct neighbor_entry *neighbor;
  struct link_entry *tmp_link_set = lookup_link_entry(remote, remote_main, local_if);
  if (tmp_link_set) {
    return tmp_link_set;
  }
  /*
   * if there exists no link tuple with
   * L_neighbor_iface_addr == Source Address
   */

#ifdef DEBUG
  OLSR_PRINTF(1, "Adding %s=>%s to link set\n", olsr_ip_to_string(local), olsr_ip_to_string(remote));
#endif

  /* a new tuple is created with... */

  new_link = olsr_malloc(sizeof(struct link_entry), "new link entry");

  memset(new_link, 0 , sizeof(struct link_entry));
  
  /* copy if_name, if it is defined */
  if (local_if->int_name)
    {
      new_link->if_name = olsr_malloc(strlen(local_if->int_name)+1, "target of if_name in new link entry");
      strcpy(new_link->if_name, local_if->int_name);
    } else 
      new_link->if_name = NULL;

  /*
   * L_local_iface_addr = Address of the interface
   * which received the HELLO message
   */
  //printf("\tLocal IF: %s\n", olsr_ip_to_string(local));
  COPY_IP(&new_link->local_iface_addr, local);
  /* L_neighbor_iface_addr = Source Address */
  COPY_IP(&new_link->neighbor_iface_addr, remote);

  /* L_SYM_time            = current time - 1 (expired) */
  new_link->SYM_time = now_times - 1;

  /* L_time = current time + validity time */
  new_link->time = GET_TIMESTAMP(vtime*1000);

  new_link->prev_status = ASYM_LINK;

  /* HYSTERESIS */
  if(olsr_cnf->use_hysteresis)
    {
      new_link->L_link_pending = 1;
      new_link->L_LOST_LINK_time = GET_TIMESTAMP(vtime*1000);
      new_link->hello_timeout = GET_TIMESTAMP(htime*1500);
      new_link->last_htime = htime;
      new_link->olsr_seqno = 0;
      new_link->olsr_seqno_valid = OLSR_FALSE;
    }

  new_link->L_link_quality = 0.0;

  if (olsr_cnf->lq_level > 0)
    {
      new_link->loss_hello_int = htime;

      new_link->loss_timeout = GET_TIMESTAMP(htime * 1500.0);

      new_link->loss_seqno = 0;
      new_link->loss_seqno_valid = 0;
      new_link->loss_missed_hellos = 0;

      new_link->lost_packets = 0;
      new_link->total_packets = 0;

      new_link->loss_index = 0;

      memset(new_link->loss_bitmap, 0, sizeof (new_link->loss_bitmap));

      set_loss_link_multiplier(new_link);
    }

  new_link->loss_link_quality = 0.0;
  new_link->neigh_link_quality = 0.0;

  new_link->loss_link_quality2 = 0.0;
  new_link->neigh_link_quality2 = 0.0;

  new_link->saved_loss_link_quality = 0.0;
  new_link->saved_neigh_link_quality = 0.0;

  /* Add to queue */
  new_link->next = link_set;
  link_set = new_link;


  /*
   * Create the neighbor entry
   */

  /* Neighbor MUST exist! */
  if(NULL == (neighbor = olsr_lookup_neighbor_table(remote_main)))
    {
      neighbor = olsr_insert_neighbor_table(remote_main);
#ifdef DEBUG
      OLSR_PRINTF(3, "ADDING NEW NEIGHBOR ENTRY %s FROM LINK SET\n", olsr_ip_to_string(remote_main));
#endif
    }

  /* Copy the main address - make sure this is done every time
   * as neighbors might change main address */
  /* Erik Tromp - OOPS! Don't do this! Neighbor entries are hashed through their
   * neighbor_main_addr field, and when that field is changed, their position
   * in the hash table is no longer correct, so that the function
   * olsr_lookup_neighbor_table() can no longer find the neighbor
   * entry. */
  /*COPY_IP(&neighbor->neighbor_main_addr, remote_main);*/

  neighbor->linkcount++;


  new_link->neighbor = neighbor;

  if(!COMP_IP(remote, remote_main))
    {
      /* Add MID alias if not already registered */
      /* This is kind of sketchy... and not specified
       * in the RFC. We can only guess a vtime.