routing_table.c

OLSR Implementation for XORP

					}
					
					list_of_my_interface_address=list_of_my_interface_address->next;
				}
				
			}
		}
	}
	/************************* end of revision ***********************/

	//CRC add for HNA
	olsr_add_routing_table_with_hna();
	
	if(debug_level > 4)
	{
		printf ("\n********************** after calculate routing table, the routing table is: ********************\n");
		olsr_print_routing_table(routingtable);
		
		fprintf (y_file,"\n********************** after calculate routing table, the routing table is: ********************\n");
		olsr_print_trace_routing_table(routingtable);
	}
	/*-----------------*/
  
	olsr_update_kernel_routes();
  
	/*-----------------*/
	if(debug_level > 6)
	{
		olsr_print_routing_table(routingtable);
		printf("l'acienne table de routage est:\n");
		olsr_print_routing_table(mirror_table);
	}

	olsr_release_routing_table(mirror_table);	
}
/*------------------------------------------------------------------------*/
/*void
olsr_print_trace_routing_table(struct rthash *table)
{

	struct rt_entry     *destination;
	struct rthash       *routing_hash;
	olsr_u8_t           index;

	fprintf(f_r_id,"Current time is %s\n",ctime((time_t *)&now.tv_sec));
	fprintf(f_r_id,"ROUTING TABLE\n");
	fprintf(f_r_id,"DESTINATION       NEXT HOP\n");
	for(index=0;index<HASHSIZE;index++)
	{
		routing_hash=&table[index];
		for(destination=routing_hash->rt_forw;destination!=(struct rt_entry *)routing_hash;destination=destination->rt_forw)
		{
			fprintf(f_r_id,"%s            ",convert_address_to_string(&destination->rt_dst));
			fprintf(f_r_id,"%s           \n ",convert_address_to_string(&destination->rt_router));
		}
	}
	fflush(f_r_id);
}*/ //commented by Y.Ge
/*------------------------------------------------------------------------*/
/***************** revised by Y.Ge ******************/
/* qos OLSR */

/* Y.Ge: in qos_olsr_fill_routing_table_with_neighbors,
 * different from  RFC, we don't look at two hop neighbors. 
 * the two hop neighbors will be added into routing table
 * as an oridinary node in topology table */
struct destination_n
*qos_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
				
				/* qos OLSR */
				new_route_entry->rt_busy = my_busy_time > neighbor->neighbor_busy_time? my_busy_time : neighbor->neighbor_busy_time;
				
				/*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;
				list_destination_n=list_destination_tmp;
			}
		}
	}
	
	/******************* added by Y.Ge ****************/
	/*** add main address of the neighbor into routing list ***/
	for(index=0;index<HASHSIZE;index++)
	{
		main_addr_neighhash=&mainaddrneightable[index];
		for(main_addr_neigh=main_addr_neighhash->mainaddrneigh_forw;main_addr_neigh!=(struct main_addr_neigh_entry *)main_addr_neighhash;main_addr_neigh=main_addr_neigh->main_addr_neigh_forw)
		{
			if ((main_addr_neigh->main_addr_neigh_status != NOT_NEIGH) && (main_addr_neigh->covered_in_routing != 1))
			{
				main_addr_neigh->covered_in_routing = 1;
				
				neighbor_any = olsr_find_highest_bw_neighbor(main_addr_neigh); //select a SYM neighbor that connect to the main address neigghbor
				
				if (neighbor_any == NULL)
				{
					printf ("XXXXXXXXX error in find QOS neighbor_any!\n");
					exit (1);
				}
				
				new_route_entry=olsr_insert_routing_table(&main_addr_neigh->main_addr_neigh_addr);
				memcpy(&new_route_entry->rt_src, &neighbor_any->my_iface_addr, sizeof (struct olsr_ip_addr)); 
				memcpy(&new_route_entry->rt_router, &neighbor_any->neighbor_addr, sizeof (struct olsr_ip_addr));
				new_route_entry->rt_willingness = main_addr_neigh->main_addr_neigh_willingness;
				new_route_entry->rt_local_if = neighbor_any->my_iface_index; //added by Y.Ge
				
				/*The next router is the neighbor itself*/
				new_route_entry->rt_metric=2; 
				
				/* qos information */
				new_route_entry->rt_busy = my_busy_time > neighbor_any->neighbor_busy_time? my_busy_time : neighbor_any->neighbor_busy_time;
				
				/*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;
				list_destination_n=list_destination_tmp;				
			} 
		}
	}
	
	return(list_destination_n);
}
/*------------------------------------------------------------------------*/
void
olsr_calculate_routing_table_with_qos()
{
	struct destination_n               *list_destination_n=NULL;	//(S_new)
	struct destination_n               *list_destination_n_1=NULL;  //(S_prev)
	struct destination_n               *destination_n_1=NULL;

	struct topology_last_entry       	*topo_last, *topo_current_dst;
	struct topology_destination_entry	*topo_destination;
	struct  destination_list        	*topo_dest;
	struct  last_list	         	*topo_last_list;	
	struct  rt_entry			*new_rt_entry;
	olsr_u32_t		         	current_bw, current_busy_time;
	
   	struct destination_n               	*tmp_list=NULL;

	double bw_factor, old_bw_factor;
	
	int index;
	struct rt_entry            	*returned_destination=NULL, *new_route_entry=NULL;
	struct main_addr_entry  	*main_address;
	struct main_addr_hash   	*main_address_hash; 
	struct interface_addr_list	*list_of_my_interface_address;   
	
	if (debug_level>4)
	{
		printf ("\n\n============= in olsr_calculate_routing_table with QOS ================\n");
		printf ("before calculation, the routing table is: \n");
		qos_olsr_print_routing_table(routingtable);
		
		fprintf (y_file,"\n\n============= in olsr_calculate_routing_table with QOS ================\n");
		fprintf (y_file,"before calculation, the routing table is: \n");
		qos_olsr_print_trace_routing_table(routingtable);
	}

	olsr_routing_mirror();
	
	if(debug_level >4)
	{
		printf ("\n************* fill routinting table with neighbors\n");
		printf("the neighbor tables are:\n");
		olsr_print_neighbor_table();
		olsr_print_main_addr_neigh_table(); 
		
		fprintf (y_file,"\n************* fill routinting table with neighbors\n");
		fprintf(y_file,"the neighbor tables are:\n");
		olsr_print_trace_neighbor_table();
		olsr_print_trace_main_addr_neigh_table(); 
	} 
	
	list_destination_n_1=qos_olsr_fill_routing_table_with_neighbors();
	
	/*--------------------------*/
	if (debug_level > 4)
	{
		printf ("\n........after fill routing  table with neighbors, the routing table is:\n");
		qos_olsr_print_routing_table(routingtable);
		
		fprintf (y_file,"\n........after fill routing  table with neighbors, the routing table is:\n");
		qos_olsr_print_trace_routing_table(routingtable);
	}
	/*--------------------------*/
	
	list_destination_n=list_destination_n_1;
	
	while(list_destination_n_1!=NULL)
	{
		if (debug_level > 5)
		{
			printf ("############### now, S_prev is: ############\n");
			fprintf (y_file,"############### now, S_prev is: ############\n");
			
			tmp_list = list_destination_n_1;
			while(tmp_list!=NULL)
			{
				printf("%s, ", convert_address_to_string(&tmp_list->destination->rt_entry_infos.rtu_dst));
				fprintf(y_file,"%s, ", convert_address_to_string(&tmp_list->destination->rt_entry_infos.rtu_dst));
				
				tmp_list = tmp_list->next;
			}
			printf ("\n");
		}

		list_destination_n_1=NULL;
		while(list_destination_n!=NULL)
		{
			if (debug_level > 5)
			{
			    printf("...........................now consider %s\n",convert_address_to_string(&list_destination_n->destination->rt_entry_infos.rtu_dst));
			    fprintf(y_file,"...........................now consider %s\n",convert_address_to_string(&list_destination_n->destination->rt_entry_infos.rtu_dst));
			}

			if(NULL!=(topo_last=olsr_lookup_last_topology_table(&list_destination_n->destination->rt_entry_infos.rtu_dst)))
			{
				topo_dest=topo_last->topology_list_of_destinations;
				while(topo_dest!=NULL)
				{
					if (debug_level > 5)
					{
						printf("%s(%d) -> ", convert_address_to_string(&list_destination_n->destination->rt_entry_infos.rtu_dst), list_destination_n->destination->rt_busy);
						printf("%s(%d) \n",convert_address_to_string(&topo_dest->destination_node->topology_destination_dst), topo_dest->destination_node->topology_destination_dst_busy);
						
						fprintf(y_file,"%s(%d) -> ", convert_address_to_string(&list_destination_n->destination->rt_entry_infos.rtu_dst), list_destination_n->destination->rt_busy);
						fprintf(y_file,"%s(%d) \n",convert_address_to_string(&topo_dest->destination_node->topology_destination_dst), topo_dest->destination_node->topology_destination_dst_busy);
					 }

					new_rt_entry = olsr_lookup_routing_table(&topo_dest->destination_node->topology_destination_dst);
					
					
					current_bw = list_destination_n->destination->rt_busy > topo_dest->destination_node->topology_destination_dst_busy? list_destination_n->destination->rt_busy : topo_dest->destination_node->topology_destination_dst_busy;
					
					if (debug_level > 5)
					{
						printf ("new_bw is:%d\n", current_bw);
						fprintf (y_file,"new_bw is:%d\n", current_bw);
					}

					
				 	if(new_rt_entry == NULL)
					{
						if (debug_level > 5)
						{
							printf ("*** add new entry to the table!\n");
							fprintf (y_file,"*** add new entry to the table!\n");
						}
						destination_n_1=(struct destination_n *)malloc(sizeof(struct destination_n));
						destination_n_1->destination=olsr_insert_routing_table_from_topo(list_destination_n->destination,topo_dest->destination_node);
						destination_n_1->destination->rt_busy = current_bw;
						
						destination_n_1->next=list_destination_n_1;
						list_destination_n_1=destination_n_1;
						
						if (debug_level > 5)
						{
							printf ("after add new entries, the routing table is:\n");
							qos_olsr_print_routing_table (routingtable);
							
							fprintf (y_file,"after add new entries, the routing table is:\n");
							qos_olsr_print_trace_routing_table (routingtable);
						}
					}
					else
					{
						if (new_rt_entry->rt_busy > current_bw && new_rt_entry->rt_entry_infos.rtu_metric!=1)
						{
						
							if (debug_level > 5)
							{
								printf ("*** WE MAY NEED to update old entry to the table!\n");
								fprintf (y_file,"*** WE MAY NEED to update old entry to the table!\n");
							}
							
							bw_factor = (double)(100-current_bw)/(sqrt(list_destination_n->destination->rt_entry_infos.rtu_metric+1));
							
							old_bw_factor = (double)(100-new_rt_entry->rt_busy)/(sqrt(new_rt_entry->rt_entry_infos.rtu_metric));
							
							
							if (debug_level > 5)
							{
								printf ("************************ bw_factor is: %f, old_bw_factor is: %f\n", bw_factor, old_bw_factor);
								fprintf (y_file,"************************ bw_factor is: %f, old_bw_factor is: %f\n", bw_factor, old_bw_factor);
							}
							
							if (bw_factor > old_bw_factor)
							{
								memcpy(&new_rt_entry->rt_entry_infos.rtu_dst,&topo_dest->destination_node->topology_destination_dst,sizeof(struct olsr_ip_addr));
								new_rt_entry->rt_entry_infos.rtu_flags=(RTF_UP|RTF_HOST|RTF_GATEWAY);
								memcpy(&new_rt_entry->rt_entry_infos.rtu_router,&list_destination_n->destination->rt_entry_infos.rtu_router,sizeof(struct olsr_ip_addr));
								new_rt_entry->rt_entry_infos.rtu_metric=list_destination_n->destination->rt_entry_infos.rtu_metric+1; 
								new_rt_entry->rt_entry_infos.rtu_busy = current_bw;