mpr.c

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

 *Check for changes in the MPR set
 *
 *@return 1 if changes occured 0 if not
 */
static int
olsr_check_mpr_changes(void)
{
  olsr_u32_t index;
  int retval;

  retval = 0;
  
  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)
	{
	  if(a_neighbor->was_mpr)
	    {
	      a_neighbor->was_mpr = OLSR_FALSE;
	      if(!a_neighbor->is_mpr)
		retval = 1;
	    }
	}
    }

  return retval;
}


/**
 *Clears out proccess registration
 *on two hop neighbors
 */
static void
olsr_clear_two_hop_processed(void)
{
  int index;
  
  for(index=0;index<HASHSIZE;index++)
    {
      struct neighbor_2_entry  *neighbor_2;
      for(neighbor_2 = two_hop_neighbortable[index].next;
	  neighbor_2 != &two_hop_neighbortable[index];
	  neighbor_2 = neighbor_2->next)
	{
	  /* Clear */
	  neighbor_2->processed = 0;
	}
    }

}


/**
 *This function calculates the number of two hop neighbors
 */
static olsr_u16_t
olsr_calculate_two_hop_neighbors(void)
{
  olsr_u8_t                    index;
  olsr_u16_t                   sum = 0;
  
  /* Clear 2 hop neighs */
  olsr_clear_two_hop_processed();

  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 *twohop_neighbors;
          olsr_u16_t                   count = 0;
          olsr_u16_t                   n_count = 0;
          if(a_neighbor->status == NOT_SYM)
	    {	    
	      a_neighbor->neighbor_2_nocov = count;
	      continue;
	    }

	  for(twohop_neighbors = a_neighbor->neighbor_2_list.next;
	      twohop_neighbors != &a_neighbor->neighbor_2_list;
	      twohop_neighbors = twohop_neighbors->next)
	    {
	      //printf("\tChecking %s....", olsr_ip_to_string(&twohop_neighbors->neighbor_2->neighbor_2_addr));
              struct neighbor_entry *dup_neighbor = olsr_lookup_neighbor_table(&twohop_neighbors->neighbor_2->neighbor_2_addr);
	      
	      if((dup_neighbor == NULL) || (dup_neighbor->status != SYM))
		{
		  n_count++;
		  if(!twohop_neighbors->neighbor_2->processed)
		    {
		      count++;
		      twohop_neighbors->neighbor_2->processed = 1;
		    }
		}
	    }
	  a_neighbor->neighbor_2_nocov = n_count;
	  
	  /* Add the two hop count */
	  sum += count;
	}
    }
  
  OLSR_PRINTF(3, "Two hop neighbors: %d\n", sum);
  return sum;
}




/**
 * Adds all nodes with willingness set to WILL_ALWAYS
 */
static olsr_u16_t
add_will_always_nodes(void)
{
  olsr_u16_t                   count = 0;
  olsr_u8_t                    index;

  //printf("\nAdding WILL ALWAYS nodes....\n");

  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)
	{ 
	  if((a_neighbor->status == NOT_SYM) || (a_neighbor->willingness != WILL_ALWAYS))
	    continue;

	  olsr_chosen_mpr(a_neighbor, &count); 

	  OLSR_PRINTF(3, "Adding WILL_ALWAYS: %s\n", olsr_ip_to_string(&a_neighbor->neighbor_main_addr));

	}
    }
  
  //OLSR_PRINTF(1, "Count: %d\n", count);
  return count;
}

/**
 *This function calculates the mpr neighbors
 *@return nada
 */
void
olsr_calculate_mpr(void)     
{  
  olsr_u16_t                   two_hop_covered_count;
  olsr_u16_t                   two_hop_count;
  int i;

  OLSR_PRINTF(3, "\n**RECALCULATING MPR**\n\n");

  olsr_clear_mprs();
  two_hop_count = olsr_calculate_two_hop_neighbors();
  two_hop_covered_count = add_will_always_nodes();

  /*
   *Calculate MPRs based on WILLINGNESS
   */

  for(i = WILL_ALWAYS - 1; i > WILL_NEVER; i--)
    {
      struct neighbor_entry        *mprs; 
      struct neighbor_2_list_entry *two_hop_list = olsr_find_2_hop_neighbors_with_1_link(i);

      while(two_hop_list != NULL)
	{
          struct neighbor_2_list_entry *tmp;
	  //printf("CHOSEN FROM 1 LINK\n");
	  if(!two_hop_list->neighbor_2->neighbor_2_nblist.next->neighbor->is_mpr)
	    olsr_chosen_mpr(two_hop_list->neighbor_2->neighbor_2_nblist.next->neighbor, &two_hop_covered_count); 
	  tmp = two_hop_list;
	  two_hop_list = two_hop_list->next;;
	  free(tmp);
	}
      
      if(two_hop_covered_count >= two_hop_count)
	{
	  i = WILL_NEVER;
	  break;
	}

      //printf("two hop covered count: %d\n", two_hop_covered_count);
   
      while((mprs = olsr_find_maximum_covered(i)) != NULL)
	{
	  //printf("CHOSEN FROM MAXCOV\n");
	  olsr_chosen_mpr(mprs,&two_hop_covered_count);

	  if(two_hop_covered_count >= two_hop_count)
	    {
	      i = WILL_NEVER;
	      break;
	    }

	}
    }
  
  /*
    increment the mpr sequence number
  */
  //neighbortable.neighbor_mpr_seq++;

  /* Optimize selection */
  olsr_optimize_mpr_set();

  if(olsr_check_mpr_changes())
    {
      OLSR_PRINTF(3, "CHANGES IN MPR SET\n");
      if(olsr_cnf->tc_redundancy > 0)
	signal_link_changes(OLSR_TRUE);
    }

}

/**
 *Optimize MPR set by removing all entries
 *where all 2 hop neighbors actually is
 *covered by enough MPRs already
 *Described in RFC3626 section 8.3.1
 *point 5
 *
 *@return nada
 */
static void
olsr_optimize_mpr_set(void)
{
  int i, remove;

  //printf("\n**MPR OPTIMIZING**\n\n");

  for(i = WILL_NEVER + 1; i < WILL_ALWAYS; i++)
    {
      int 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)
	    {
	      
	      if(a_neighbor->willingness != i)
		continue;
	      
	      if(a_neighbor->is_mpr)
		{
                  struct neighbor_2_list_entry *two_hop_list;
		  //printf("\tChecking %s\n", olsr_ip_to_string(&a_neighbor->neighbor_main_addr));
		  remove = 1;

		  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)
		    {
		      
                      const struct neighbor_entry * const dup_neighbor = olsr_lookup_neighbor_table(&two_hop_list->neighbor_2->neighbor_2_addr);
		      
		      if((dup_neighbor != NULL) && (dup_neighbor->status != NOT_SYM))
			continue;
		      
		      //printf("\t[%s] coverage %d\n", olsr_ip_to_string(&two_hop_list->neighbor_2->neighbor_2_addr), two_hop_list->neighbor_2->mpr_covered_count);
		      /* Do not remove if we find a entry which need this MPR */
		      if(two_hop_list->neighbor_2->mpr_covered_count <= olsr_cnf->mpr_coverage)
			remove = 0;
		      
		    }
		  if(remove)
		    {
		      OLSR_PRINTF(3, "MPR OPTIMIZE: removiong mpr %s\n\n", olsr_ip_to_string(&a_neighbor->neighbor_main_addr));
		      a_neighbor->is_mpr = OLSR_FALSE;
		    }
		}
	    }
	}
    }
}



void
olsr_print_mpr_set(void)
{
  int index;

  OLSR_PRINTF(1, "MPR SET: ");

  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)
	{ 
	  /* 
	   * Remove MPR settings
	   */
	  if(a_neighbor->is_mpr)
	    OLSR_PRINTF(1, "[%s] ", olsr_ip_to_string(&a_neighbor->neighbor_main_addr));
	}
    }
  OLSR_PRINTF(1, "\n");
}