olsr.c

OLSR Implementation for XORP

/*
 * Copyright (c) 2004 Ying Ge, Communication Research Center Canada.
 *
 * Copyright (c) 2002, 2003 Maoyu Wang, Communication Research Center Canada.
 *
 * By Ying Ge:
 * 1. Change the OLSR packet format and message processing procedure based 
 *    on the OLSR RFC.
 * 2. Add support of multiple interfaces to OLSR, including MID message 
 *    creating and processing procedure as specified in the OLSR RFC.
 * 3. Add QoS Support to OLSR
 *
 * By Maoyu Wang:
 * 1. Ported OLSR from IPv4 to IPv6.
 * 2. Added the Host and Network Association (HNA) functionality into OLSR.
 * 3. Added the default gateway functionality into OLSR by extending the HNA 
 *    message usage. The default gateway functionality supported the mobility
 *	  by cooperating with Mobile IPv6 for a mobile node as well as supported 
 * 	  Internet access for MANET nodes. 
 *
 * DISTRIBUTED WITH NO WARRANTY, EXPRESS OR IMPLIED.
 * See the GNU Library General Public License (file COPYING in the distribution)
 * for conditions of use and redistribution
 */
/* Code Modified by Joe Macker and Ron Lee July (NRL) 2001 
 * the following was added
 * (1) hysteresis code for hellos
 *   - added pending state and filter parameters
 * (2) parameterization of other setting
 * - hello intervals,
 * - hold timeouts based upon interval settings
 * (3) added jitter functionality
 * (4) still don't like the polling routing used as an event handler
 * but deal with it by adding -T option which allows polling time to 
 * be decreased to have more effective jitter processing
 * (5) added debug levels and some fixed some compiler warnings
 * (6) added functions for default gateway settings
 * (7) added some function for adding associated subnets and addresses
 * to routing table of OLSR node (see README)
 * ces tres bon... bon chance
 */
 
/*
 * This Copyright notice is in French. An English summary is given
 * but the referee text is the French one.
 *
 * Copyright (c) 2000, 2001 [e-mail], INRIA Rocquencourt,
 *                          [e-mail], INRIA Rocquencourt.
 *
 * Ce logiciel informatique est disponible aux conditions
 * usuelles dans la recherche, c'est-à-dire qu'il peut
 * être utilisé, copié, modifié, distribué à l'unique
 * condition que ce texte soit conservé afin que
 * l'origine de ce logiciel soit reconnue.
 * Le nom de l'Institut National de Recherche en Informatique
 * et en Automatique (INRIA), ou d'une personne morale
 * ou physique ayant participé à l'élaboration de ce logiciel ne peut
 * être utilisé sans son accord préalable explicite.
 * 
 * Ce logiciel est fourni tel quel sans aucune garantie,
 * support ou responsabilité d'aucune sorte.
 * Certaines parties de ce logiciel sont dérivées de sources developpees par
 * University of California, Berkeley et ses contributeurs couvertes 
 * par des copyrights.
 * This software is available with usual "research" terms
 * with the aim of retain credits of the software. 
 * Permission to use, copy, modify and distribute this software for any
 * purpose and without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies,
 * and the name of INRIA, or any contributor not be used in advertising
 * or publicity pertaining to this material without the prior explicit
 * permission. The software is provided "as is" without any
 * warranties, support or liabilities of any kind.
 * This product includes software developed by the University of
 * California, Berkeley and its contributors protected by copyrights.
 */

/*
 * Routing table management daemon.
 */

char olsr_rcsid[] = 
  "$Id: olsr.c,v 1.2 2000/12/06 10:36:11 prima Exp $";


#include "defs.h"
#include "math.h"

/* --------------------------------------------------------------------
    OLSR protocol
   -------------------------------------------------------------------- */

/* --------------------------------------------------------------------
    Forward declarations
   -------------------------------------------------------------------- */


/* --------------------------------------------------------------------
    Global variables and arrays
   -------------------------------------------------------------------- */


/* --------------------------------------------------------------------
    Functions
   -------------------------------------------------------------------- */


/*-------------------------------------------------------------------------*/

struct timeval  hold_time_neighbor ;
struct timeval  hold_time_topology;
struct timeval  hold_time_duplicate_tc;
struct timeval  hold_time_expired; //added by Y.Ge
struct timeval  hold_time_duplicate; //added by Y.Ge

//CRC HNA add
/*-------------------------------------------------------------------------*/
struct timeval  hold_time_hna;
struct timeval	hold_time_duplicate_hna;
/*-------------------------------------------------------------------------*/

//CRC HNA add
/*-------------------------------------------------------------------------*/
olsr_8_t changes_net;
/*-------------------------------------------------------------------------*/

olsr_8_t changes_topology;
olsr_8_t changes_neighborhood;

//CRC HNA add
olsr_8_t changes_gateway; 

FILE *f_r_id;
/* hysteresis trackig now included in debug 1 level neighbor message */
/*FILE *hys_id;*/

/* CRC v4->v6 add
 * copy from /usr/src/linux/include/net/addrconf.h:
 * ipv6_addr_hash(struct in6_addr) 
 */
/*-------------------------------------------------------------------------*/
void
olsr_hashing(struct olsr_ip_addr *address,olsr_u32_t *h)
{
	olsr_u32_t hash;
	hash = address->s6_addr[2]^address->s6_addr32[3];
	hash ^=(hash>>16);
	hash ^=(hash>>8);
	*h=((hash^(hash>>4))&0xff);
}
/*-------------------------------------------------------------------------*/

struct neighbor_2_list_entry 
*olsr_find_2_hop_neighbors_with_1_link()
{
	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_2_entry      *two_hop_neighbor=NULL;
	struct neighbor2_hash        *hash_2_neighbor;

	for(index=0;index<HASHSIZE;index++)
	{
		hash_2_neighbor=&neighbor2table[index];

		for(two_hop_neighbor=hash_2_neighbor->neighbor2_forw;two_hop_neighbor!=(struct neighbor_2_entry  *)hash_2_neighbor;two_hop_neighbor=two_hop_neighbor->neighbor_2_forw)
		{
			two_hop_neighbor->neighbor_2_state=0;
			if(two_hop_neighbor->neighbor_2_pointer==1)
			{
				//if(two_hop_neighbor->neighbor_2_nblist->neighbor->neighbor_status==NBS_SYM)//commented by Y.Ge
				if(two_hop_neighbor->neighbor_2_nblist->neighbor->neighbor_status==SYM_LINK)//added by Y.Ge
				{
					two_hop_list_tmp =(struct neighbor_2_list_entry *)malloc(sizeof(struct neighbor_2_list_entry));
					two_hop_list_tmp->neighbor_2=two_hop_neighbor;
					two_hop_list_tmp->neighbor_2_next=two_hop_list;
					two_hop_list= two_hop_list_tmp;
				}
			}
		}      
	}
  	return(two_hop_list_tmp);
}
  
/*---------------------------------------------------------------------------*/
/************** added by Y.Ge ***************/
/* qos OLSR */
struct neighbor_entry 
*olsr_find_maximum_covered_with_qos(int willingness) //"willingness" is added by Y.Ge, define which willingness of the neighbor we should look in this round
{
	olsr_u16_t                  maximum=0;
	olsr_u8_t                   index;
	struct neighborhash         *neighbor_hash_table;
	struct neighbor_entry       *a_neighbor;
	struct neighbor_entry       *mpr_candidate=NULL;
	olsr_u32_t           	    min_busy_time = -1; /* set the busy time as the maximum posssible value */
   
	neighbor_hash_table=neighbortable.neighborhash;
	for (index=0;index<HASHSIZE;index++)
	{
		for(a_neighbor=neighbor_hash_table[index].neighbor_forw;a_neighbor!=(struct neighbor_entry  *)&neighbor_hash_table[index];a_neighbor=a_neighbor->neighbor_forw)
		{
			/* if(maximum<a_neighbor->neighbor_2_nocov) */ //commented by Y.Ge
			
			/* added by Y.Ge
			 * choose the certain willingness neighbor
			 * as MPR
			 */
			if(a_neighbor->neighbor_main_info->main_neighbor->main_addr_neigh_willingness == willingness)
			{
				if(maximum<a_neighbor->neighbor_2_nocov)
				{
					maximum=a_neighbor->neighbor_2_nocov;
					mpr_candidate=a_neighbor;
					min_busy_time = a_neighbor->neighbor_busy_time;
				}
				else
				{
					if (maximum == a_neighbor->neighbor_2_nocov)
					{
						if (min_busy_time > a_neighbor->neighbor_busy_time)
						{
							mpr_candidate = a_neighbor;
							min_busy_time = a_neighbor->neighbor_busy_time;
						}
					}
				}
			}
		}
	}
	return (mpr_candidate);
}

/*---------------------------------------------------------------------------*/
struct iface_addr_list_entry
*olsr_find_will_always_neighbor()
{
	olsr_u8_t               	index;
	struct iface_addr_list_entry	*will_always_neighbor_list = NULL;
	struct iface_addr_list_entry	*will_always_neighbor_list_tmp = NULL;
	struct neighbor_entry       	*neighbor = NULL;
	struct neighborhash          	*hash_neighbor;
	
	for(index=0;index<HASHSIZE;index++)
	{
		hash_neighbor=&neighbortable.neighborhash[index];
		for(neighbor=hash_neighbor->neighbor_forw;neighbor!=(struct neighbor_entry *)hash_neighbor;neighbor=neighbor->neighbor_forw)
		{

			if (neighbor->neighbor_main_info->main_neighbor->main_addr_neigh_willingness == WILL_ALWAYS) 
			{
				if (neighbor->neighbor_status == SYM_LINK)
				{
					will_always_neighbor_list_tmp = (struct iface_addr_list_entry *)malloc(sizeof(struct iface_addr_list_entry));
					will_always_neighbor_list_tmp->neighbor_iface = neighbor;
					will_always_neighbor_list_tmp->iface_addr_next = will_always_neighbor_list;
					will_always_neighbor_list = will_always_neighbor_list_tmp;
				}
			}
		}
	}	
	return (will_always_neighbor_list_tmp); 
}
/************** end of revision *************/
/*---------------------------------------------------------------------------*/

int
olsr_chosen_mpr(struct neighbor_entry *one_hop_neighbor,olsr_u16_t *two_hop_covered_count)
{
  /*
    This function  processes the chosen  and updates the counters
    used in calculations  
  */
  
	struct neighbor_list_entry   *the_one_hop_list;
  	struct neighbor_2_list_entry *second_hop_entries; 
	olsr_u16_t                   count=0;
  
	count=*two_hop_covered_count;
	//one_hop_neighbor->neighbor_status=NBS_MPR; //commented  by Y.Ge
	one_hop_neighbor->neighbor_main_info->main_neighbor->main_addr_neigh_status = MPR_NEIGH; //added by Y.Ge

	TRACE_ACTION("CHANGE NEIGHBOR STATUS : MPR ",&one_hop_neighbor->neighbor_addr,NULL,0);
	second_hop_entries=one_hop_neighbor->neighbor_2_list;
	while(second_hop_entries!=NULL)
	{
		if(!second_hop_entries->neighbor_2->neighbor_2_state)
		{
			/*
			  Now the neighbor is covered by this mpr
			 */
			second_hop_entries->neighbor_2->neighbor_2_state=NB2S_COVERED;  /* =1*/	  
			the_one_hop_list=second_hop_entries->neighbor_2->neighbor_2_nblist;
			while(the_one_hop_list!=NULL)
			{
				//if((the_one_hop_list->neighbor->neighbor_status!=NBS_ASYM)&&(the_one_hop_list->neighbor->neighbor_status!=NBS_LOST)&&(the_one_hop_list->neighbor->neighbor_status!=NBS_PENDING))//commented by Y.Ge
				if(the_one_hop_list->neighbor->neighbor_status == SYM_LINK)//added by Y.Ge
				{
					count++;
					the_one_hop_list->neighbor->neighbor_2_nocov--;
				}
				the_one_hop_list=the_one_hop_list->neighbor_next;
			}
		}
		second_hop_entries=second_hop_entries->neighbor_2_next;
	}
	*two_hop_covered_count=count;
	return (0);
}
/*--------------------------------------------------------------------------*/
void
olsr_calculate_neighbors(olsr_u16_t *two_hop_count)
{
  /*
    This function calculates the number of  second hop neighbors for each 
    neighbor
  */

	olsr_u8_t                    index;
	struct neighborhash          *neighbor_hash_table;
	struct neighbor_entry        *a_neighbor;
	olsr_u16_t                   count=0;
	struct neighbor_2_list_entry *twohop_neighbors;
  
	neighbor_hash_table=neighbortable.neighborhash;
	for (index=0;index<HASHSIZE;index++)
	{
		for(a_neighbor=neighbor_hash_table[index].neighbor_forw;a_neighbor!=(struct neighbor_entry  *)&neighbor_hash_table[index];a_neighbor=a_neighbor->neighbor_forw)
		{ 
			count=0;
			//if((a_neighbor->neighbor_status==NBS_ASYM)||(a_neighbor->neighbor_status==NBS_LOST)||(a_neighbor->neighbor_status==NBS_PENDING)) //commented by Y.Ge
			if((a_neighbor->neighbor_status==ASYM_LINK)||(a_neighbor->neighbor_status==LOST_LINK)||(a_neighbor->neighbor_status==UNSPEC_LINK)) //addeded by Y.Ge
			{	    
				a_neighbor->neighbor_2_nocov=count;
				continue;
			}
			
			/************ added by Y.Ge ***********/
			/*
			 * don't calculate the two hop neighbors that who's 1-hop-neighbor is WILL_NEVER
			 */
			if (a_neighbor->neighbor_main_info->main_neighbor->main_addr_neigh_status == WILL_NEVER)
			{
				a_neighbor->neighbor_2_nocov=count;
				continue;
			}/*********** end of revision ********/
				
			/* 
			Turn the neighbor status on symetric to re calculate the MPR set
			*/
			/*if(a_neighbor->neighbor_status==NBS_MPR)
				a_neighbor->neighbor_status=NBS_SYM;*/ //comented by Y.Ge
			count=0;
			twohop_neighbors=a_neighbor->neighbor_2_list;
			while(twohop_neighbors!=NULL)
			{