/*
* The olsr.org Optimized Link-State Routing daemon(olsrd)
* Copyright (c) 2004, Andreas Tønnesen(andreto@olsr.org)
* 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;
}
}
}
}
/**
*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");
}
syntax highlighted by Code2HTML, v. 0.9.1