dsr_route_cache.ex.c

opnet11.5 manet dsr和aodv协议

/* dsr_route_cache.ex.c */
/* C file for DSR Route Cache APIs */


/****************************************/
/*		Copyright (c) 1987-2005			*/
/*		by OPNET Technologies, Inc.		*/
/*		(A Delaware Corporation)		*/
/*	7255 Woodmont Av., Suite 250  		*/
/*     Bethesda, MD 20814, U.S.A.       */
/*			All Rights Reserved.		*/
/****************************************/

/***** Includes *****/
#include <opnet.h>
#include <dsr.h>
#include <dsr_ptypes.h>
#include <ip_addr_v4.h>
#include <ip_support.h>
#include <manet.h>
#include <oms_ot_support.h>
#include <oms_tan.h>

/* These arrays hold the names of the different columns					*/
/* in the respective table. The arrays will be used for column names	*/
/* while creating the templates, and will also be used as column tags	*/
/* while wrting into the tables											*/
int			routes_cache_columns_name_array_size = 6;
const char*	routes_cache_columns_name_array [] 	= {"Destination Node Name", "Time Installed", "First Hop External", 
														"Last Hop External", "Hop Count", "Route(s)"};

/**** Prototypes ****/
static DsrT_Path_Info*				dsr_route_cache_entry_create (List* path_lptr, Boolean first_hop_external, 
																	Boolean last_hop_external);
static Boolean						dsr_route_cache_route_exists (List* dest_routes_lptr, List* new_path_lptr);
static Boolean						dsr_route_cache_size_exceed (DsrT_Route_Cache* route_cache_ptr);
static void							dsr_route_cache_insert_route_sorted (List* paths_lptr, DsrT_Path_Info* path_info_ptr);
static void							dsr_route_cache_insert_route_priority (DsrT_Route_Cache* route_cache_ptr, 
																		List* paths_lptr, DsrT_Path_Info* path_info_ptr);
static void							dsr_route_cache_all_expired_routes_delete (DsrT_Route_Cache* route_cache_ptr);
static void							dsr_route_cache_size_stat_update (DsrT_Route_Cache*);
static void							dsr_route_cache_num_hops_stat_update (DsrT_Route_Cache*, List*);
static void							dsr_route_cache_hit_success_stat_update (DsrT_Route_Cache*);
static void							dsr_route_cache_hit_failure_stat_update (DsrT_Route_Cache*);

static DsrT_Route_Cache*			dsr_route_cache_mem_alloc (void);
static DsrT_Path_Info*				dsr_route_cache_entry_mem_alloc (void);
static void							dsr_route_cache_entry_mem_free (DsrT_Path_Info* path_ptr);


DsrT_Route_Cache*
dsr_route_cache_create (int max_cache_size, double path_expiry_time, DsrT_Stathandles* stat_handle_ptr)
	{
	DsrT_Route_Cache*		route_cache_ptr = OPC_NIL;
	
	/** Creates the route cache for storing	**/
	/** the source routes discovered		**/
	FIN (dsr_route_cache_create ());
	
	/* Allocate memory for the route cache	*/
	route_cache_ptr = dsr_route_cache_mem_alloc ();
	
	/* Set the maximum size of the cache	*/
	route_cache_ptr->max_cache_size = max_cache_size;
	
	/* Set the time for paths in the route	*/
	/* cache to expire after which the 		*/
	/* paths will be deleted				*/
	route_cache_ptr->path_expiry_time = path_expiry_time;
	
	/* Set the statistic handles	*/
	route_cache_ptr->dsr_stat_ptr = stat_handle_ptr;
	
	FRET (route_cache_ptr);
	}


void
dsr_route_cache_entry_add (DsrT_Route_Cache* route_cache_ptr, List* hops_lptr, 
						Boolean first_hop_external, Boolean last_hop_external)
	{
	char				dest_addr_str [INETC_ADDR_STR_LEN];
	List*				dest_routes_lptr = OPC_NIL;
	void*				old_contents_ptr = OPC_NIL;
	Boolean				temp_last_hop_external = OPC_FALSE;
	int					num_hops, count;
	List*				temp_lptr = OPC_NIL;
	InetT_Address*		hop_address_ptr;
	DsrT_Path_Info*		path_info_ptr = OPC_NIL;
	
	/** Adds a new route to a specific 	**/
	/** destination to the route cache	**/
	FIN (dsr_route_cache_entry_add (<args>));
	
	/* Delete all routes that have expired	*/
	dsr_route_cache_all_expired_routes_delete (route_cache_ptr);
	
	/* For each hop, enter it as a reachable	*/
	/* destination in the route cache			*/
	num_hops = op_prg_list_size (hops_lptr);
	
	/* Create a temporary list to store the hops	*/
	/* to each destination that is to be entered	*/
	temp_lptr = op_prg_list_create ();
	
	for (count = 0; count < num_hops; count++)
		{
		/* Get each hop in the path	*/
		hop_address_ptr = (InetT_Address *) op_prg_list_access (hops_lptr, count);
		
		/* Insert it into the temporary list	*/
		op_prg_list_insert (temp_lptr, hop_address_ptr, count);
		
		/* The first hop is this node itself	*/
		/* Do not consider the first hop		*/
		if (count == 0)
			continue;
		
		/* The last hop will be external only	*/
		/* for the last hop in this path		*/
		if (count == (num_hops - 1))
			temp_last_hop_external = last_hop_external;
		
		/* Get the destination address as a 	*/
		/* string to index the hash table		*/
		inet_address_ptr_print (dest_addr_str, hop_address_ptr);
		
		/* Check if this destination exists in the hash table	*/
		dest_routes_lptr = (List*) prg_string_hash_table_item_get (route_cache_ptr->route_cache_table, dest_addr_str);
		
		if (dest_routes_lptr != OPC_NIL)
			{
			/* Check if there is a matching route already	*/
			/* to the same destination. Do not insert		*/
			/* matching routes								*/
			if (dsr_route_cache_route_exists (dest_routes_lptr, temp_lptr) == OPC_TRUE)
				continue;
			}
		else
			{
			/* No route currently exists to this destination	*/
			/* Create a new entry and add it to the route cache	*/
			dest_routes_lptr = op_prg_list_create ();
		
			/* Set the route list in the route cache hash table	*/
			prg_string_hash_table_item_insert (route_cache_ptr->route_cache_table, dest_addr_str, dest_routes_lptr, &old_contents_ptr);
			}
		
		/* The route does not exist in the route cache	*/
		/* Create an entry for the route				*/
		path_info_ptr = dsr_route_cache_entry_create (temp_lptr, first_hop_external, temp_last_hop_external);
		
		/* Update the number of hops per route in the	*/
		/* route cache statictic						*/
		dsr_route_cache_num_hops_stat_update (route_cache_ptr, temp_lptr);
	
		/* Check if there is any space in the 	*/
		/* route cache to insert a new route	*/
		if (dsr_route_cache_size_exceed (route_cache_ptr) == OPC_FALSE)
			{
			/* Insert the new route to the route list to that destination	*/
			/* The route is inserted in the list of routes to that 			*/
			/* destination based on priorities with the highest priority	*/
			/* route at the head of the list and the lowest priority route	*/
			/* at the tail of the list										*/
			dsr_route_cache_insert_route_sorted (dest_routes_lptr, path_info_ptr);
			route_cache_ptr->current_cache_size += 1;
			dsr_route_cache_size_stat_update (route_cache_ptr);
			}
		else
			{
			/* The route cache size is full and there is no space	*/
			/* in the route cache to hold any more routes			*/
			/* Insert the route based on priority (number of hops,	*/
			/* no external flag, etc) and a "least recently used"	*/
			/* cache replacement policy.							*/
			
			/* Determine whether to insert this route into the		*/
			/* route cache. If a success is returned, the route		*/
			/* has been inserted and another route was deleted		*/
			/* based on the priority of the routes.					*/
			dsr_route_cache_insert_route_priority (route_cache_ptr, dest_routes_lptr, path_info_ptr);
			}
		}
	
	while (op_prg_list_size (temp_lptr) > 0)
		op_prg_list_remove (temp_lptr, OPC_LISTPOS_HEAD);

	/* Free the temporary list	*/
	op_prg_mem_free (temp_lptr);
	
	
	FOUT;
	}
		
		
DsrT_Path_Info*
dsr_route_cache_entry_access (DsrT_Route_Cache* route_cache_ptr, InetT_Address dest_address, Boolean discovery_performed)
	{
	char				dest_addr_str [INETC_ADDR_STR_LEN];
	List*				dest_routes_lptr = OPC_NIL;
	DsrT_Path_Info*		path_ptr = OPC_NIL;
	
	/** Accesses and returns a route to the	**/
	/** destination address specified. If 	**/
	/** no route exists, a NIL is returned	**/
	FIN (dsr_route_cache_entry_access (<args>));

	/* Get the destination string key	*/
	inet_address_print (dest_addr_str, dest_address);
	
	/* Delete all routes that have expired	*/
	dsr_route_cache_all_expired_routes_delete (route_cache_ptr);
	
	/* Get all routes to the destination	*/
	dest_routes_lptr = (List*) prg_string_hash_table_item_get (route_cache_ptr->route_cache_table, dest_addr_str);
	
	if (dest_routes_lptr == OPC_NIL)
		{
		/* Update the hit failure statistic to indicate	*/
		/* that the route cache did not have a route	*/
		dsr_route_cache_hit_failure_stat_update (route_cache_ptr);
		
		/* No routes exist in the route cache	*/
		/* to the destination. Return a NIL		*/
		FRET (OPC_NIL);
		}
	
	/* No routes exist to the destination	*/
	if (op_prg_list_size (dest_routes_lptr) == 0)
		FRET (OPC_NIL);
	
	/* The best route to the destination is always the first route	*/
	path_ptr = (DsrT_Path_Info*) op_prg_list_access (dest_routes_lptr, OPC_LISTPOS_HEAD);
	
	/* Update the access time	*/
	path_ptr->last_access_time = op_sim_time ();
	
	/* Update the statistic for a route cache hit	*/
	if (discovery_performed == OPC_FALSE)
		{
		/* A route discovery was not performed to	*/
		/* obtain a route to this destination for 	*/
		/* this packet. This means that this is a 	*/
		/* route cache hit							*/
		dsr_route_cache_hit_success_stat_update (route_cache_ptr);
		}
	
	FRET (path_ptr);
	}


List*
dsr_route_cache_all_routes_to_dest_access (DsrT_Route_Cache* route_cache_ptr, InetT_Address dest_address)
	{
	char				dest_addr_str [INETC_ADDR_STR_LEN];
	List*				dest_routes_lptr = OPC_NIL;
	
	/** Accesses and returns a route to the	**/
	/** destination address specified. If 	**/
	/** no route exists, a NIL is returned	**/
	FIN (dsr_route_cache_all_routes_to_dest_access (<args>));

	/* Get the destination string key	*/
	inet_address_print (dest_addr_str, dest_address);
	
	/* Delete all routes that have expired	*/
	dsr_route_cache_all_expired_routes_delete (route_cache_ptr);
	
	/* Get all routes to the destination	*/
	dest_routes_lptr = (List*) prg_string_hash_table_item_get (route_cache_ptr->route_cache_table, dest_addr_str);
	
	if (dest_routes_lptr == OPC_NIL)
		{
		/* No routes exist in the route cache	*/
		/* to the destination. Return a NIL		*/
		FRET (OPC_NIL);
		}
	
	FRET (dest_routes_lptr);
	}


void
dsr_route_cache_all_routes_with_link_delete (DsrT_Route_Cache* route_cache_ptr, InetT_Address address_A, InetT_Address address_B)
	{
	List*				keys_lptr = OPC_NIL;
	int					count, size, index;
	int					num_paths, num_nodes, num_hops;
	List*				dest_routes_lptr = OPC_NIL;
	DsrT_Path_Info*		path_ptr = OPC_NIL;
	InetT_Address*		first_addr_ptr;
	InetT_Address*		next_addr_ptr;
	Boolean				route_deleted = OPC_FALSE;
	char*				key_str = OPC_NIL;
	
	/** Deletes all routes that have the link in the hop	**/
	FIN (dsr_route_cache_all_routes_with_link_delete (<args>));
	
	/* Get all the keys in the hash 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++)
		{
		/* Reinitialize the variables	*/
		size = 0;
		num_paths = 0;
		
		/* 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)
			{
			/* No routes exist to this destination	*/
			continue;
			}
		
		num_paths = op_prg_list_size (dest_routes_lptr);
		
		while (size < num_paths)	
			{
			/* Initailization	*/
			route_deleted = OPC_FALSE;
			
			/* Get each path and check if the link exists	*/
			path_ptr = (DsrT_Path_Info*) op_prg_list_access (dest_routes_lptr, size);
			
			/* Get the size of the path	*/
			num_hops = op_prg_list_size (path_ptr->path_hops_lptr);
			
			for (index = 0; index < (num_hops - 1); index++)
				{
				first_addr_ptr = (InetT_Address*) op_prg_list_access (path_ptr->path_hops_lptr, index);
				next_addr_ptr = (InetT_Address*) op_prg_list_access (path_ptr->path_hops_lptr, (index + 1));
				
				if (((inet_address_equal (*first_addr_ptr, address_A)) && (inet_address_equal (*next_addr_ptr, address_B))) ||
					((inet_address_equal (*first_addr_ptr, address_B)) && (inet_address_equal (*next_addr_ptr, address_A))))
					{
					/* The route has this hop	*/
					/* Delete the route			*/
					path_ptr = (DsrT_Path_Info*) op_prg_list_remove (dest_routes_lptr, size);
					dsr_route_cache_entry_mem_free (path_ptr);
					route_cache_ptr->current_cache_size -= 1;
					num_paths--;
					route_deleted = OPC_TRUE;
					
					break;
					}
				} /* For each hop in the route */
			
			if (!route_deleted)
				size++;
			} /* For each route to a destination */
		
		/* Get the number of remaining paths to the destination	*/
		num_paths = op_prg_list_size (dest_routes_lptr);
		
		if (num_paths == 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, key_str);
			op_prg_list_free (dest_routes_lptr);
			op_prg_mem_free (dest_routes_lptr);
			}
		} /* For each destination node */
	
	/* Update the size of the route cache_statistic	*/
	dsr_route_cache_size_stat_update (route_cache_ptr);
	
	op_prg_list_free (keys_lptr);
	op_prg_mem_free (keys_lptr);
	
	FOUT;
	}


void
dsr_route_cache_src_node_with_next_hop_routes_delete (DsrT_Route_Cache* route_cache_ptr, InetT_Address next_hop_address)
	{
	List*				keys_lptr = OPC_NIL;
	int					count, size;
	int					num_paths, num_nodes;
	List*				dest_routes_lptr = OPC_NIL;
	DsrT_Path_Info*		path_ptr = OPC_NIL;
	InetT_Address*		first_hop_addr_ptr;
	Boolean				route_deleted = OPC_FALSE;
	char*				key_str = OPC_NIL;
	
	/** Deletes all routes that have the next hop	**/
	/** address specified. This function should 	**/
	/** only be called at the source node			**/
	FIN (dsr_route_cache_src_node_with_next_hop_routes_delete (<args>));
	
	/* Get all the keys in the hash 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++)
		{
		/* Reinitialize the variables	*/
		size = 0;
		num_paths = 0;
		
		/* 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)
			{
			/* No routes exist to this destination	*/
			continue;
			}
		
		num_paths = op_prg_list_size (dest_routes_lptr);
		
		while (size < num_paths)	
			{
			/* Initailization	*/
			route_deleted = OPC_FALSE;
			
			/* Get each path and check if the link exists	*/
			path_ptr = (DsrT_Path_Info*) op_prg_list_access (dest_routes_lptr, size);
			
			/* Access the first hop and check if it is the	*/
			/* next hop node since we are at the source		*/
			first_hop_addr_ptr = (InetT_Address*) op_prg_list_access (path_ptr->path_hops_lptr, 1);
			
			if (inet_address_equal (*first_hop_addr_ptr, next_hop_address))