routing_table.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
 */
/*
 * 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 routing_table_rcsid[] = 
  "$Id: routing_table.c,v 1.2 2000/12/06 10:36:12 prima Exp $";


#include "defs.h"

struct rthash                     routingtable[HASHSIZE];

/*------------------------------------------------------------------------*/
struct rt_entry
*olsr_lookup_routing_table(struct olsr_ip_addr *dst)
{

	struct rt_entry *destination;
	struct rthash   *routing_hash;
	olsr_u32_t      hash;

	olsr_hashing(dst,&hash);
	routing_hash=&routingtable[hash & HASHMASK];
  
	for(destination=routing_hash->rt_forw;destination!=(struct rt_entry *)routing_hash;destination=destination->rt_forw)
	{
		if(destination->rt_hash!=hash)
		continue;

		if (0==memcmp(&destination->rt_dst,dst,sizeof(struct olsr_ip_addr)))
		return(destination);
	}
	return(NULL);  
}
/*------------------------------------------------------------------------*/
void
olsr_delete_routing_table(struct rt_entry* destination)
{

	if(destination->rt_ifp!=NULL)
		free(destination->rt_ifp);    
	olsr_remque((struct olsr_qelem *)destination);
	free((void *)destination);
}
/*------------------------------------------------------------------------*/
void
olsr_release_routing_table(struct rthash *table)
{ 
	struct rt_entry *destination;
	struct rt_entry *destination_tmp;
	struct rthash   *routing_hash;
	olsr_u8_t             index;
  
	for(index=0;index<HASHSIZE;index++)
	{
		routing_hash=&table[index];
		destination=routing_hash->rt_forw;
		while(destination!=(struct rt_entry *)routing_hash)
		{
			destination_tmp=destination;
			destination=destination->rt_forw;
			olsr_delete_routing_table(destination_tmp);
		}
	}
}
/*------------------------------------------------------------------------*/
struct rt_entry 
*olsr_insert_routing_table(struct olsr_ip_addr *dst)
{
	struct rt_entry *new_route_entry;
	struct rthash   *routing_hash;
	olsr_u32_t       hash;

	olsr_hashing(dst,&hash);
	routing_hash=&routingtable[hash & HASHMASK];

	new_route_entry=(struct rt_entry *)malloc(sizeof(struct rt_entry));
	new_route_entry->rt_hash=hash;

	memcpy(&new_route_entry->rt_dst,dst,sizeof(struct olsr_ip_addr));
  
  	/************* commented by Y.Ge  **********/
	/* 
	 * should set the rt_src based on the interface address
	 * do it in other functions - olsr_fill_routing_table_with_neighbors(), olsr_insert_routing_table_from_topo, etc
	 */ 
	//CRC HNA add
	//------------------------------------------------------------------------
	//memcpy(&new_route_entry->rt_src,&addr_ip,sizeof(struct olsr_ip_addr));
	//CRC: don't know if it should be addr_ip or addr_manet? 
	/*memcpy(&new_route_entry->rt_src,&addr_manet,sizeof(struct olsr_ip_addr));*/
	//------------------------------------------------------------------------
  	/************ end of revision *************/
  
	/*
	 No timeout is needed since the routing table is calculated for each network change
	*/

	new_route_entry->rt_metric=0;
	new_route_entry->rt_ifmetric=0;
	new_route_entry->rt_state=0; 
	new_route_entry->rt_flags=(RTF_UP|RTF_GATEWAY|RTF_HOST);
	new_route_entry->rt_ifp=NULL;
	//CRC HNA add
	/*--------------------------------------------------------------------------*/
	new_route_entry->rt_dst_prefix=128;
	new_route_entry->rt_src_prefix=128;
	new_route_entry->rt_router_prefix=128;
	/*--------------------------------------------------------------------------*/

	olsr_insque((struct olsr_qelem *)new_route_entry, (struct olsr_qelem *)routing_hash);
  
	return(new_route_entry);
	/*
	  We need this pointer to use it for the next routing calculation
	*/
}
/*------------------------------------------------------------------------*/
struct rt_entry 
*olsr_insert_routing_table_from_topo(struct rt_entry *r_last,struct topology_destination_entry *destination)
{
	struct rt_entry *new_route_entry=NULL;
	struct rthash   *routing_hash;
	olsr_u32_t      hash;

	/*
	the hash calculation is the same
	*/
	/*-----------------*/
	if (debug_level > 6)
		printf("Insertion from the topology/////////\n");
	/*-----------------*/
	new_route_entry=olsr_insert_routing_table(&destination->topology_destination_dst);
	new_route_entry->rt_flags=(RTF_UP|RTF_HOST|RTF_GATEWAY);
	memcpy(&new_route_entry->rt_router,&r_last->rt_router,sizeof(struct olsr_ip_addr));
	memcpy(&new_route_entry->rt_src, &r_last->rt_src, sizeof (struct olsr_ip_addr)); //added by Y.Ge
	new_route_entry->rt_metric=r_last->rt_metric+1;
	new_route_entry->rt_willingness = r_last->rt_willingness; //added by Y.Ge
	new_route_entry->rt_local_if = r_last->rt_local_if; //added by Y.Ge 

	return(new_route_entry);  
}
/*NRL code------------------------------------------------------------------
void
olsr_add_default_gateway()
{
  // This function adds a new entry for the default destination
  
  struct rt_entry *default_gateway_entry;
  struct rt_entry  *gateway_entry;
  struct olsr_ip_addr     inaddr_any = in6addr_any;
  
  //if(default_gateway!=0)
  if(memcpy(&default_gateway,0,sizeof(struct olsr_ip_addr)))
    
    if(NULL!=(gateway_entry=olsr_lookup_routing_table(&default_gateway)))
      {      
	default_gateway_entry=olsr_insert_routing_table(&inaddr_any); 
	default_gateway_entry->rt_flags=0;
	default_gateway_entry->rt_flags=(RTF_UP|RTF_GATEWAY);
	memcpy(&default_gateway_entry->rt_router,&gateway_entry->rt_router,sizeof(struct
olsr_ip_addr));
	default_gateway_entry->rt_metric=gateway_entry->rt_metric;
      }
}
-----------------------------------------------------------------------*/


/* CRC code------------------------------------------------------------*/
/*struct rt_entry
*olsr_add_default_gateway(struct olsr_ip_addr* gateway)
{
  //This function adds a new entry for the default destination
  
  struct rt_entry *default_gateway_entry;
  struct rt_entry  *gateway_entry;
  struct olsr_ip_addr     inaddr_any = in6addr_any;
  struct olsr_ip_addr	  inaddrany;

  memset(&inaddrany,0,sizeof(struct olsr_ip_addr));
  
  if(0!=memcmp(gateway,&inaddrany,sizeof(struct olsr_ip_addr)))
   {
     if(NULL!=(gateway_entry=olsr_lookup_routing_table(gateway)))
      {      
		default_gateway_entry=olsr_insert_routing_table(&inaddr_any); 
		memcpy(&(default_gateway_entry->rt_dst),&inaddr_any,sizeof(struct olsr_ip_addr));
		default_gateway_entry->rt_flags=0;
		default_gateway_entry->rt_flags=(RTF_UP|RTF_GATEWAY);
		memcpy(&default_gateway_entry->rt_router,&gateway_entry->rt_router,sizeof(struct
		olsr_ip_addr));
		default_gateway_entry->rt_metric=gateway_entry->rt_metric;
		return(default_gateway_entry);
      }
      else
      {
      	memset(&gwhna,0,sizeof(struct hna_message));
      	return(NULL);
      }
  }
  return(NULL);
}*/

/*void
olsr_del_default_gateway()
{
  //This function delete an entry for the default destination
  
  struct rt_entry *default_gateway_entry;
  struct olsr_ip_addr     inaddrany = in6addr_any;
  
  if(NULL!=(default_gateway_entry=olsr_lookup_routing_table(&inaddrany)))
  {      
  	default_gateway_entry->rt_flags=0;
  	default_gateway_entry->rt_flags=(RTF_UP|RTF_GATEWAY);
  	//memcpy(&default_gateway_entry->rt_router,&gateway_entry->rt_router,sizeof(struct
	//olsr_ip_addr));
  	//default_gateway_entry->rt_metric=gateway_entry->rt_metric;
  	olsr_ioctl_del_route(default_gateway_entry);
  	olsr_delete_routing_table(default_gateway_entry);
  }	
 }*/
/*-----------------------------------------------------------------------*/
/*
 * Y.Ge: based on the OLSR RFC, in the current implementation,
 * olsr_fill_routing_table_with_neighbors() not only deals with the 1-hop-neighbor,
 * but the 2-hop-neighbor as well
 */ 
struct destination_n
*olsr_fill_routing_table_with_neighbors()
{
	struct destination_n   *list_destination_n=NULL;
	struct destination_n   *list_destination_tmp=NULL;
	olsr_u8_t              index;
	struct neighbor_entry  *neighbor;
	struct neighborhash    *hash_neighbor;
	struct rt_entry        *new_route_entry=NULL;
	struct neighbor_entry  *neighbor_any, *next_hop_neighbor;	
	struct main_addr_neigh_entry	*main_addr_neigh; //added by Y.Ge
	struct main_addr_neighhash 	*main_addr_neighhash;  //added by Y.Ge
	struct neighbor_2_entry    *neighbor_2;  //added by Y.Ge
	struct neighbor2_hash      *hash_2_neighbor; //added by Y.Ge
	
	olsr_clear_main_addr_neigh_table_covered_in_routing(); //added by Y.Ge, no neighbor's main address has been included in the routing table 
	
	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_status==NBS_SYM)||(neighbor->neighbor_status==NBS_MPR)) //commented by Y.Ge
			if(neighbor->neighbor_status==SYM_LINK) //added by Y.Ge
			{
				new_route_entry=olsr_insert_routing_table(&neighbor->neighbor_addr);
				memcpy(&new_route_entry->rt_src, &neighbor->my_iface_addr, sizeof (struct olsr_ip_addr)); //added by Y.Ge
				memcpy(&new_route_entry->rt_router,&neighbor->neighbor_addr,sizeof(struct olsr_ip_addr));
				new_route_entry->rt_flags=(RTF_UP|RTF_HOST);
				new_route_entry->rt_willingness = neighbor->neighbor_main_info->main_neighbor->main_addr_neigh_willingness; //added by Y.Ge
				new_route_entry->rt_local_if = neighbor->my_iface_index; //added by Y.Ge
				
				/*The next router is the neighbor itself*/
				new_route_entry->rt_metric=1; 
				
				/************ added by Y.Ge *********/
				/*** check if the neighbor address is the main_addres ***/
				if (memcmp(&neighbor->neighbor_addr, &neighbor->neighbor_main_info->main_neighbor->main_addr_neigh_addr, sizeof(struct olsr_ip_addr))==0)
				{
					neighbor->neighbor_main_info->main_neighbor->covered_in_routing = 1;	
				}
				/********** end of revision *********/
				
				/*fisrt hop. may be we should use another metric*/
				list_destination_tmp=(struct destination_n *)malloc(sizeof(struct destination_n));
				list_destination_tmp->destination=new_route_entry;
				list_destination_tmp->next=list_destination_n;