mpr.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: mpr.c,v 1.18 2007/10/05 08:06:12 bernd67 Exp $
 */

#include "defs.h"
#include "mpr.h"
#include "two_hop_neighbor_table.h"
#include "olsr.h"
#include "neighbor_table.h"
#include "scheduler.h"

/* Begin:
 * Prototypes for internal functions 
 */

static olsr_u16_t
add_will_always_nodes(void);

static void
olsr_optimize_mpr_set(void);

static void
olsr_clear_mprs(void);

static void
olsr_clear_two_hop_processed(void);

static struct neighbor_entry *
olsr_find_maximum_covered(int);

static olsr_u16_t
olsr_calculate_two_hop_neighbors(void);

static int
olsr_check_mpr_changes(void);

static int
olsr_chosen_mpr(struct neighbor_entry *, olsr_u16_t *);

static struct neighbor_2_list_entry *
olsr_find_2_hop_neighbors_with_1_link(int);


/* End:
 * Prototypes for internal functions 
 */



/**
 *Find all 2 hop neighbors with 1 link
 *connecting them to us trough neighbors
 *with a given willingness.
 *
 *@param willingness the willigness of the neighbors
 *
 *@return a linked list of allocated neighbor_2_list_entry structures
 */
static struct neighbor_2_list_entry *
olsr_find_2_hop_neighbors_with_1_link(int willingness)
{
  
 
  olsr_u8_t                    index;
  struct neighbor_2_list_entry *two_hop_list_tmp = NULL;
  struct neighbor_2_list_entry *two_hop_list = NULL;
  struct neighbor_entry        *dup_neighbor;
  struct neighbor_2_entry      *two_hop_neighbor = NULL;


  for(index=0;index<HASHSIZE;index++)
    {

      for(two_hop_neighbor = two_hop_neighbortable[index].next;
	  two_hop_neighbor != &two_hop_neighbortable[index];
	  two_hop_neighbor = two_hop_neighbor->next)
	{
	  
	  //two_hop_neighbor->neighbor_2_state=0;
	  //two_hop_neighbor->mpr_covered_count = 0;
	  
	  dup_neighbor = olsr_lookup_neighbor_table(&two_hop_neighbor->neighbor_2_addr);
	  
	  if((dup_neighbor != NULL) && (dup_neighbor->status != NOT_SYM))
	    {
	      
	      //OLSR_PRINTF(1, "(1)Skipping 2h neighbor %s - already 1hop\n", olsr_ip_to_string(&two_hop_neighbor->neighbor_2_addr));

	      continue;
	    }
	  
	  if(two_hop_neighbor->neighbor_2_pointer == 1)
	    {
	      if((two_hop_neighbor->neighbor_2_nblist.next->neighbor->willingness == willingness) &&
		 (two_hop_neighbor->neighbor_2_nblist.next->neighbor->status == SYM))
		{
		  two_hop_list_tmp = olsr_malloc(sizeof(struct neighbor_2_list_entry), "MPR two hop list");

		  //OLSR_PRINTF(1, "ONE LINK ADDING %s\n", olsr_ip_to_string(&two_hop_neighbor->neighbor_2_addr));

		  /* Only queue one way here */		  
		  two_hop_list_tmp->neighbor_2 = two_hop_neighbor;
		  
		  two_hop_list_tmp->next = two_hop_list;
		  
		  two_hop_list= two_hop_list_tmp;
		}
	    }
	  
	}
      
    }
  
  return(two_hop_list_tmp);
}
  





/**
 *This function processes the chosen MPRs and updates the counters
 *used in calculations
 */
static int
olsr_chosen_mpr(struct neighbor_entry *one_hop_neighbor, olsr_u16_t *two_hop_covered_count)
{
  struct neighbor_list_entry   *the_one_hop_list;
  struct neighbor_2_list_entry *second_hop_entries; 
  struct neighbor_entry        *dup_neighbor;
  olsr_u16_t                   count;
  
  count = *two_hop_covered_count;

  OLSR_PRINTF(1, "Setting %s as MPR\n", olsr_ip_to_string(&one_hop_neighbor->neighbor_main_addr));

  //printf("PRE COUNT: %d\n\n", count);

  one_hop_neighbor->is_mpr = OLSR_TRUE; //NBS_MPR;
  
  for(second_hop_entries = one_hop_neighbor->neighbor_2_list.next;
      second_hop_entries != &one_hop_neighbor->neighbor_2_list;
      second_hop_entries = second_hop_entries->next)
    {
      dup_neighbor = olsr_lookup_neighbor_table(&second_hop_entries->neighbor_2->neighbor_2_addr);

      if((dup_neighbor != NULL) && (dup_neighbor->status == SYM))
	{
	  //OLSR_PRINTF(7, "(2)Skipping 2h neighbor %s - already 1hop\n", olsr_ip_to_string(&second_hop_entries->neighbor_2->neighbor_2_addr));
	  continue;
	}

      //      if(!second_hop_entries->neighbor_2->neighbor_2_state)
      //if(second_hop_entries->neighbor_2->mpr_covered_count < olsr_cnf->mpr_coverage)
      //{
	  /*
	    Now the neighbor is covered by this mpr
	  */
	  second_hop_entries->neighbor_2->mpr_covered_count++;
	  the_one_hop_list = second_hop_entries->neighbor_2->neighbor_2_nblist.next;

	  //OLSR_PRINTF(1, "[%s](%x) has coverage %d\n", olsr_ip_to_string(&second_hop_entries->neighbor_2->neighbor_2_addr), second_hop_entries->neighbor_2, second_hop_entries->neighbor_2->mpr_covered_count);

	  if(second_hop_entries->neighbor_2->mpr_covered_count >= olsr_cnf->mpr_coverage)
	     count++;
		      
	  while(the_one_hop_list != &second_hop_entries->neighbor_2->neighbor_2_nblist)
	    {
	      
	      if((the_one_hop_list->neighbor->status == SYM))
		{
		  if(second_hop_entries->neighbor_2->mpr_covered_count >= olsr_cnf->mpr_coverage)
		    {
		      the_one_hop_list->neighbor->neighbor_2_nocov--;
		    }
		}
	      the_one_hop_list = the_one_hop_list->next;
	    }
	  
	  //}
    }

  //printf("POST COUNT %d\n\n", count);
  
  *two_hop_covered_count = count;
  return count;

}


/**
 *Find the neighbor that covers the most 2 hop neighbors
 *with a given willingness
 *
 *@param willingness the willingness of the neighbor
 *
 *@return a pointer to the neighbor_entry struct
 */
static struct neighbor_entry *
olsr_find_maximum_covered(int willingness)
{
  olsr_u16_t                  maximum;
  olsr_u8_t                   index;
  struct neighbor_entry       *a_neighbor;
  struct neighbor_entry       *mpr_candidate=NULL;
   
  maximum = 0;
  
  for (index=0;index<HASHSIZE;index++)
    {
      for(a_neighbor = neighbortable[index].next;
	  a_neighbor != &neighbortable[index];
	  a_neighbor = a_neighbor->next)
	{
	  /*	  
	  printf("[%s] nocov: %d mpr: %d will: %d max: %d\n\n", 
		 olsr_ip_to_string(&a_neighbor->neighbor_main_addr), 
		 a_neighbor->neighbor_2_nocov,
		 a_neighbor->is_mpr,
		 a_neighbor->willingness,
		 maximum);
	  */
	  if((!a_neighbor->is_mpr) &&
	     (a_neighbor->willingness == willingness) && 
	     (maximum < a_neighbor->neighbor_2_nocov))
	    {
	      //printf("ADDING\n");
	      maximum = a_neighbor->neighbor_2_nocov;
	      mpr_candidate = a_neighbor;
	    }
	}
    }
  return mpr_candidate;
}


/**
 *Remove all MPR registrations
 */
static void
olsr_clear_mprs(void)
{
  olsr_u32_t index;
  
  for (index=0;index<HASHSIZE;index++)
    {
      struct neighbor_entry   *a_neighbor;
      for(a_neighbor = neighbortable[index].next;
	  a_neighbor != &neighbortable[index];
	  a_neighbor = a_neighbor->next)
	{
          struct neighbor_2_list_entry *two_hop_list;
	  /* Clear MPR selection */
	  if(a_neighbor->is_mpr)
	    {
	      a_neighbor->was_mpr = OLSR_TRUE;
	      a_neighbor->is_mpr = OLSR_FALSE;
	    }

	  /* Clear two hop neighbors coverage count */
	  for(two_hop_list = a_neighbor->neighbor_2_list.next;
	      two_hop_list != &a_neighbor->neighbor_2_list;
	      two_hop_list = two_hop_list->next)
	    {
	      two_hop_list->neighbor_2->mpr_covered_count = 0;
	    }
	}
    }
}


/**