dsr_route_cache.ex.c

opnet11.5 manet dsr和aodv协议

			FRET (OPC_TRUE);
			}
		}
	
	FRET (OPC_FALSE);
	}


static Boolean
dsr_route_cache_size_exceed (DsrT_Route_Cache* route_cache_ptr)
	{
	/** This function checks if there is any more	**/
	/** space in the route cache to insert any more	**/
	/** routes. Returns a true if there is no space	**/
	FIN (dsr_route_cache_size_exceed (<args>));
	
	if (route_cache_ptr->max_cache_size == -1)
		{
		/* The size of the route cache is infinity	*/
		FRET (OPC_FALSE);
		}
	
	if (route_cache_ptr->current_cache_size >= route_cache_ptr->max_cache_size)
		{
		/* There is no more space in the route cache	*/
		/* to insert any more routes.					*/
		FRET (OPC_TRUE);
		}

	FRET (OPC_FALSE);
	}


static void
dsr_route_cache_insert_route_sorted (List* paths_lptr, DsrT_Path_Info* path_info_ptr)
	{
	int					num_routes;
	int					count;
	DsrT_Path_Info*		path_ptr = OPC_NIL;
	
	/** Inserts the route into the list of routes	**/
	/** based on the sort criteria					**/
	FIN (dsr_route_cache_insert_route_sorted (<args>));
	
	/* Get the number of routes to the destination	*/
	num_routes = op_prg_list_size (paths_lptr);
	
	if (num_routes == 0)
		{
		/* No routes exists to this destination.	*/
		/* Insert the route and exit				*/
		op_prg_list_insert (paths_lptr, path_info_ptr, OPC_LISTPOS_TAIL);
		
		FOUT;
		}
	
	/* The sort criteria is the number of hops.		*/
	/* Place the route with the least number of at	*/
	/* the head of the list							*/
	for (count = 0; count < num_routes; count++)
		{
		path_ptr = (DsrT_Path_Info*) op_prg_list_access (paths_lptr, count);
		
		/* The list of routes is an already sorted	*/
		/* list, so if we find any route that has	*/
		/* more hops, then just insert before that	*/
		/* route and finish the search				*/
		if (path_ptr->num_hops > path_info_ptr->num_hops)
			{
			/* This path has equal or more number 	*/
			/* of hops than the one just about to   */
			/* beinserted. Insert the new path at	*/
			/* this location in the list			*/
			op_prg_list_insert (paths_lptr, path_info_ptr, count);
			
			break;
			}
		}
	
	if (count == num_routes)
		{
		/* This new route has the most number of	*/
		/* hops. Insert it at the tail of the list	*/
		op_prg_list_insert (paths_lptr, path_info_ptr, OPC_LISTPOS_TAIL);
		}
	
	FOUT;
	}
	

static void
dsr_route_cache_insert_route_priority (DsrT_Route_Cache* route_cache_ptr, List* paths_lptr, DsrT_Path_Info* path_info_ptr)
	{
	int					num_routes, num_nodes, num_paths;
	int					count;
	DsrT_Path_Info*		path_ptr = OPC_NIL;
	List*				keys_lptr = OPC_NIL;
	char*				key_str = OPC_NIL;
	List*				dest_routes_lptr = OPC_NIL;
	Boolean				multiple_paths_exist = OPC_FALSE;
	int					max_hops = 0;
	double				max_lru_time = 0.0;
	List*				path_delete_lptr = OPC_NIL;
	char*				dest_key_str = OPC_NIL;
	
	/** Determines whether to insert a route into	**/
	/** the route cache as there is no space in the	**/
	/** route cache. Based on various criteria, it 	**/
	/** determines which route to hold and which	**/
	/** one to delete from the route cache			**/
	FIN (dsr_route_cache_insert_route_priority (<args));
	
	/****************************************************************************************/
	/* The order of determining the priority of routes in the route cache are as follows :	*/
	/* 1. MULTIPLE ROUTES TO SAME DESTINATION												*/
	/*		a. If there are multiple routes to the same destination, then delete the route	*/
	/*		   with the maximum number of hops.												*/
	/* 		b. If there are multiple routes with the same number of hops to the same		*/
	/*		   destination, then delete the one which was least recently used				*/
	/* 2. NO ROUTE TO DESTINATION															*/
	/*		a. There exists no route to the destination that needs to be inserted, 			*/
	/* 		   determine the destiantions that have multiple routes and delete the one		*/
	/*		   which has the most number of hops and is least recently used.				*/
	/*		b. If all destinations have only one route, delete the route which is least		*/
	/*		   recently used among all the destinations										*/
	/****************************************************************************************/
	
	/* If the route cache size if zero, then no route can	*/
	/* be inserted into the route cache						*/
	if (route_cache_ptr->max_cache_size == 0)
		FOUT;
	
	/* Determine the number of routes to the destination	*/
	num_routes = op_prg_list_size (paths_lptr);
	
	if (num_routes > 0)
		{
		/* There already exists routes to the destination	*/
		/* The route at the bottom of the list will be the	*/
		/* route with the maximum number of hops and least	*/
		/* recently used.									*/
		path_ptr = (DsrT_Path_Info*) op_prg_list_remove (paths_lptr, OPC_LISTPOS_TAIL);
		dsr_route_cache_entry_mem_free (path_ptr);
		
		/* Insert the new route at the correct location		*/
		dsr_route_cache_insert_route_sorted (paths_lptr, path_info_ptr);
			
		FOUT;
		}
		
	/* There is no route to the destination. Determine		*/
	/* criteria 2 to discard the appropriate route			*/
	
	/* Get all the keys to all destinations in the table	*/
	keys_lptr = prg_string_hash_table_keys_get (route_cache_ptr->route_cache_table);
	
	/* Get the size of the table	*/
	num_nodes = op_prg_list_size (keys_lptr);
	
	for (count = 0; count < num_nodes; count++)
		{
		/* Get each destination key	*/
		key_str = (char*) op_prg_list_access (keys_lptr, count);
		
		/* Access the routes to each destination	*/
		dest_routes_lptr = (List*) prg_string_hash_table_item_get (route_cache_ptr->route_cache_table, key_str);
		
		if (dest_routes_lptr == OPC_NIL)
			continue;
		
		num_paths = op_prg_list_size (dest_routes_lptr);
		
		if (num_paths == 0)
			continue;

		if ((multiple_paths_exist == OPC_TRUE) && (num_paths == 1))
			continue;
		
		if (num_paths > 1)
			multiple_paths_exist = OPC_TRUE;
		
		/* Determine the maximum hops and the least	*/
		/* recently used time for all the paths		*/
		path_ptr = (DsrT_Path_Info*) op_prg_list_access (dest_routes_lptr, OPC_LISTPOS_TAIL);
			
		if (path_ptr->num_hops < max_hops)
			continue;
		
		if (path_ptr->last_access_time <= max_lru_time)
			continue;
		
		/* Set the values	*/
		max_hops = path_ptr->num_hops;
		max_lru_time = path_ptr->last_access_time;
		path_delete_lptr = dest_routes_lptr;
		dest_key_str = key_str;
		}
	
	path_ptr = (DsrT_Path_Info*) op_prg_list_remove (path_delete_lptr, OPC_LISTPOS_TAIL);
	dsr_route_cache_entry_mem_free (path_ptr);
	
	/* Insert the new route at the correct location		*/
	dsr_route_cache_insert_route_sorted (paths_lptr, path_info_ptr);
	
	/* If the exists no route to the destination just 	*/
	/* delete, remove the list form the hash table		*/
	if (op_prg_list_size (path_delete_lptr) == 0)
		{
		/* All paths to the destination node were deleted	*/
		/* Remove this node entry from the route cache		*/
		dest_routes_lptr = (List*) prg_string_hash_table_item_remove (route_cache_ptr->route_cache_table, dest_key_str);
		op_prg_list_free (dest_routes_lptr);
		op_prg_mem_free (dest_routes_lptr);
		}
	
	/* Free the hash table keys	*/
	op_prg_list_free (keys_lptr);
	op_prg_mem_free (keys_lptr);
	
	/* The size of the cache table will not change since	*/
	/* a route is deleted before adding another route		*/
	FOUT;
	}
	

static void
dsr_route_cache_all_expired_routes_delete (DsrT_Route_Cache* route_cache_ptr)
	{
	double				current_time;
	double				update_time;
	List*				keys_lptr = OPC_NIL;
	int					num_dest, num_paths;
	int					count, size;
	char*				dest_key_str = OPC_NIL;
	List*				dest_routes_lptr = OPC_NIL;
	DsrT_Path_Info*		path_ptr = OPC_NIL;
	
	/** Deletes all routes in the route cache that have expired	**/
	/** This function should be called every time a route is	**/
	/** either inserted or accessed								**/
	FIN (dsr_route_cache_all_expired_routes_delete (<args>));
	
	/* Get the current time	*/
	current_time = op_sim_time ();
	
	/* Get all the keys to all destinations in the table	*/
	keys_lptr = prg_string_hash_table_keys_get (route_cache_ptr->route_cache_table);
	
	/* Get the number of destinations	*/
	num_dest = op_prg_list_size (keys_lptr);
	
	/* Delete all routes to each destination that have expired	*/
	for (count = 0; count < num_dest; count++)
		{
		/* Initailize the variables	*/
		size = 0;
		
		/* Get the destination key	*/
		dest_key_str = (char*) op_prg_list_access (keys_lptr, count);
		
		/* Get the list of routes to this destination	*/
		dest_routes_lptr = (List*) prg_string_hash_table_item_get (route_cache_ptr->route_cache_table, dest_key_str);
		
		/* Get the number of paths to this destination	*/
		num_paths = op_prg_list_size (dest_routes_lptr);
		
		while (size < num_paths)
			{
			/* Get each path to that destination	*/
			path_ptr = (DsrT_Path_Info*) op_prg_list_access (dest_routes_lptr, size);
			
			/* Determine if this route has expired	*/
			if ((current_time - path_ptr->last_access_time) >= route_cache_ptr->path_expiry_time)
				{
				/* This route has expired. Delete this entry	*/
				path_ptr = (DsrT_Path_Info*) op_prg_list_remove (dest_routes_lptr, size);
				route_cache_ptr->current_cache_size -= 1;
				
				/* Update the route cache size statistic at the	*/
				/* time this route was to be deleted			*/
				update_time = path_ptr->installed_time + route_cache_ptr->path_expiry_time;
				op_stat_write_t (route_cache_ptr->dsr_stat_ptr->route_cache_size_shandle, 
									(double) route_cache_ptr->current_cache_size, update_time);
				
				dsr_route_cache_entry_mem_free (path_ptr);
				num_paths--;
				
				continue;
				}
			
			size++;
			}
		
		/* If there are no routes to this destination	*/
		/* free its memory								*/
		if (op_prg_list_size (dest_routes_lptr) == 0)
			{
			dest_routes_lptr = (List*) prg_string_hash_table_item_remove (route_cache_ptr->route_cache_table, dest_key_str);
			op_prg_list_free (dest_routes_lptr);
			op_prg_mem_free (dest_routes_lptr);
			}
		}
	
	/* Free the keys list	*/
	op_prg_list_free (keys_lptr);
	op_prg_mem_free (keys_lptr);
	
	FOUT;
	}


static void
dsr_route_cache_size_stat_update (DsrT_Route_Cache* route_cache_ptr)
	{
	/** Updates the route cache size statistic	*/
	FIN (dsr_route_cache_size_stat_update (<args>));
	
	/* Update the size of the route cache statistic	*/
	op_stat_write (route_cache_ptr->dsr_stat_ptr->route_cache_size_shandle, (double) route_cache_ptr->current_cache_size);
	
	FOUT;
	}

static void
dsr_route_cache_num_hops_stat_update (DsrT_Route_Cache* route_cache_ptr, List* temp_lptr)
	{
	int							num_hops;
	DsrT_Global_Stathandles*	global_stathandle_ptr = OPC_NIL;
	
	/** Updates the statistic for the number of hops	**/
	/** per route in the route cache					**/
	FIN (dsr_route_cache_num_hops_stat_update (<args>));
	
	/* Get the number of hops	*/
	num_hops = op_prg_list_size (temp_lptr);
	
	/* Get a handle to the global statistics	*/
	global_stathandle_ptr = dsr_support_global_stat_handles_obtain ();
	
	/* The number of hops is one less that the total	*/
	/* number of nodes in the route						*/
	op_stat_write (route_cache_ptr->dsr_stat_ptr->num_hops_shandle, (double) (num_hops - 1));
	
	/* Update the global number of hops per route statistic	*/
	op_stat_write (global_stathandle_ptr->num_hops_global_shandle, (double) (num_hops - 1));
	
	FOUT;
	}

static void
dsr_route_cache_hit_success_stat_update (DsrT_Route_Cache* route_cache_ptr)
	{
	/** Updates the route cache hit statistic on	**/
	/** the number of hits in the route cache when	**/
	/** trying to find a route to the destination	**/
	FIN (dsr_route_cache_hit_success_stat_update (<args>));
	
	op_stat_write (route_cache_ptr->dsr_stat_ptr->route_cache_hit_success_shandle, 1.0);
	
	FOUT;
	}

static void
dsr_route_cache_hit_failure_stat_update (DsrT_Route_Cache* route_cache_ptr)
	{
	/** Updates the route cache hit failure statistic 	**/
	/** when the route cache does not have a route to a **/
	/** particular destination when trying to find a 	**/
	/** route to the destination						**/
	FIN (dsr_route_cache_hit_failure_stat_update (<args>));
	
	op_stat_write (route_cache_ptr->dsr_stat_ptr->route_cache_hit_failure_shandle, 1.0);
	
	FOUT;
	}



/*********** MEMORY ALLOCATION AND DEALLOCATION ***********/
static DsrT_Route_Cache*
dsr_route_cache_mem_alloc (void)
	{
	DsrT_Route_Cache*		route_cache = OPC_NIL;
	
	/** Allocate memory for the route cache table	**/
	FIN (dsr_route_cache_mem_alloc (void));
	
	route_cache = (DsrT_Route_Cache*) op_prg_mem_alloc (sizeof (DsrT_Route_Cache));
	route_cache->route_cache_table = (PrgT_String_Hash_Table*) prg_string_hash_table_create (10, 10);
	route_cache->current_cache_size = 0;
	route_cache->max_cache_size = 0;
	
	FRET (route_cache);
	}

static DsrT_Path_Info*
dsr_route_cache_entry_mem_alloc (void)
	{
	DsrT_Path_Info*		route_cache_entry = OPC_NIL;
	
	/** Allocates memory for a specific path	**/
	FIN (dsr_route_cache_entry_mem_alloc (void));
	
	route_cache_entry = (DsrT_Path_Info*) op_prg_mem_alloc (sizeof (DsrT_Path_Info));
	route_cache_entry->path_hops_lptr = op_prg_list_create ();
	route_cache_entry->first_hop_external = OPC_FALSE;
	route_cache_entry->last_hop_external = OPC_FALSE;
	route_cache_entry->num_hops = 0;
	route_cache_entry->last_access_time = OPC_DBL_UNDEF;
	route_cache_entry->installed_time = OPC_DBL_UNDEF;
	
	FRET (route_cache_entry);
	}


static void
dsr_route_cache_entry_mem_free (DsrT_Path_Info* path_ptr)
	{
	int				count, num_hops;
	InetT_Address*	hop_address;
	
	/** Frees the route cache entry for a specific path	**/
	FIN (dsr_route_cache_entry_mem_free (<args>));
	
	num_hops = op_prg_list_size (path_ptr->path_hops_lptr);
	
	for (count = 0; count < num_hops; count++)
		{
		hop_address = (InetT_Address*) op_prg_list_remove (path_ptr->path_hops_lptr, OPC_LISTPOS_HEAD);
		inet_address_destroy_dynamic (hop_address);
		}
	
	op_prg_mem_free (path_ptr->path_hops_lptr);
	op_prg_mem_free (path_ptr);
	
	FOUT;
	}