dsr_route_discovery.ex.c

opnet11.5 manet dsr和aodv协议

/* dsr_route_discovery.ex.c */
/* C support file for the route discovery	*/
/* which includes route requests and route	*/
/* reply message information buffers		*/


/****************************************/
/*		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>

/**** Prototypes ****/
static void							dsr_route_request_max_request_entries_check (PrgT_String_Hash_Table*, int);
static void							dsr_route_request_table_size_check (DsrT_Route_Request_Table*);
static void							dsr_request_table_size_stat_update (DsrT_Route_Request_Table*);
static DsrT_Route_Request_Table*	dsr_request_table_mem_alloc (void);
static DsrT_Request_Orig_Entry*		dsr_route_request_orig_entry_mem_alloc (void);
static void							dsr_route_request_orig_entry_mem_free (DsrT_Request_Orig_Entry*);
static DsrT_Request_Forward_Entry*	dsr_route_request_forward_entry_mem_alloc (void);
static void							dsr_route_request_forward_entry_mem_free (DsrT_Request_Forward_Entry*);
static void							dsr_expired_grat_reply_entries_delete (DsrT_Route_Reply_Table*);
static DsrT_Route_Reply_Table*		dsr_grat_reply_table_mem_alloc (void);
static DsrT_Route_Reply_Entry*		dsr_grat_reply_entry_mem_alloc (void);
static void							dsr_grat_reply_entry_mem_free (DsrT_Route_Reply_Entry*);

EXTERN_C_BEGIN
void							dsr_rte_route_request_expiry_handle (void*, int);
EXTERN_C_END


/**********************************************************/
/***************** ROUTE REQUEST TABLE ********************/
/**********************************************************/
DsrT_Route_Request_Table*
dsr_route_request_tables_create (int max_size, int max_request_entries, int max_request_retrans,
								double init_request_timeout, double max_request_timeout, 
								double non_propagating_request_timer, 
								DsrT_Stathandles* stat_handle_ptr)
	{
	DsrT_Route_Request_Table*		route_request_table_ptr = OPC_NIL;
	
	/** Creates and initializes the route request table	**/	
	FIN (dsr_route_request_tables_create (<args>));
	
	route_request_table_ptr = dsr_request_table_mem_alloc ();
	route_request_table_ptr->max_table_size = max_size;
	route_request_table_ptr->max_request_table_entries = max_request_entries;
	route_request_table_ptr->max_request_retransmissions = max_request_retrans;
	route_request_table_ptr->init_request_period = init_request_timeout;
	route_request_table_ptr->max_request_period = max_request_timeout;
	route_request_table_ptr->non_prop_request_period = non_propagating_request_timer;
	route_request_table_ptr->dsr_stat_ptr = stat_handle_ptr;
	
	FRET (route_request_table_ptr);
	}	


void
dsr_route_request_originating_table_entry_insert (DsrT_Route_Request_Table* route_request_table_ptr, InetT_Address dest_address, 
											int ttl_value)
	{
	DsrT_Request_Orig_Entry*		route_request_orig_entry = OPC_NIL;
	char							dest_str [INETC_ADDR_STR_LEN];
	void*							old_contents_ptr = OPC_NIL;
	Boolean							new_entry = OPC_FALSE;
	InetT_Address*					copy_dest_address_ptr;
	double 							backoff_period;
	
	/** Inserts the route request into the originating	**/
	/** route request table								**/
	FIN (dsr_route_request_originating_table_entry_insert (<args>));
	
	/* Get the destination address as a */
	/* string to index the hash table	*/
	inet_address_print (dest_str, dest_address);
	
	/* Check if there exists an entry for this destination	*/
	/* node in the route request table						*/
	route_request_orig_entry = (DsrT_Request_Orig_Entry*) prg_string_hash_table_item_get 
													(route_request_table_ptr->route_request_send_table, dest_str);
	
	if (route_request_orig_entry == OPC_NIL)
		{
		/* There does not exist an entry for this destination	*/
		/* Check if there is space in the route request table	*/
		/* If the table is full, delete the entry which is 		*/
		/* least recently used (LRU)							*/
		dsr_route_request_table_size_check (route_request_table_ptr);
		
		/* There does not exist an entry for	*/
		/* this destination in the table		*/
		route_request_orig_entry = dsr_route_request_orig_entry_mem_alloc ();
			
		/* Insert the entry in the hash table	*/
		prg_string_hash_table_item_insert (route_request_table_ptr->route_request_send_table, dest_str, 
							route_request_orig_entry, &old_contents_ptr);
		
		/* Increment the size of the request table	*/
		route_request_table_ptr->current_table_size++;
		
		/* Update the request table size statistic	*/
		dsr_request_table_size_stat_update (route_request_table_ptr);
		
		/* Set the new entry flag	*/
		new_entry = OPC_TRUE;
		}
	
	/* Schedule the next route request if there	*/
	/* is no route reply within that period		*/
	if (new_entry)
		{
		if (ttl_value == 1)
			{
			/* This is a non-propagating request	*/
			/* Set the timer to the non propagating	*/
			/* request timer.						*/
			route_request_orig_entry->current_request_period = route_request_table_ptr->non_prop_request_period;
			}
		else
			{
			/* This is a propagating request.		*/
			/* This is a new entry. Initialize the	*/
			/* request period to the initial value	*/
			route_request_orig_entry->current_request_period = route_request_table_ptr->init_request_period;
			}
		}
	else
		{
		/****** THIS IS AN EXISTING ENTRY *******/
		/* Make sure the previous timer is 		*/
		/* either the current event or has 		*/
		/* already passed. If not, cancel it	*/
		if (op_ev_valid (route_request_orig_entry->retry_timer) && op_ev_pending (route_request_orig_entry->retry_timer))
			op_ev_cancel (route_request_orig_entry->retry_timer);
		
		if (route_request_orig_entry->current_request_period == route_request_table_ptr->non_prop_request_period)
			{
			/* The previous route request for this destination	*/
			/* was a non propagating request. Set the new 		*/
			/* request to the initial request period			*/
			route_request_orig_entry->current_request_period = route_request_table_ptr->init_request_period;
			}
		else
			{
			/* This is an existing entry which was	*/
			/* a propagating request the previous 	*/
			/* attempt. Implement the exponential  	*/
			/* backoff algorithm by doubling the  	*/
			/* request period for every timeout		*/
			
			/* Do exponential backoff on the time	*/
			/* interval between this and last RREQ	*/			
			backoff_period = 2 * (op_sim_time () - route_request_orig_entry->last_route_req_time);
			route_request_orig_entry->current_request_period = backoff_period;
			}
		}
	
	/* Schedule the expiry timer to recreate a	*/
	/* new route request if needed				*/
	copy_dest_address_ptr = inet_address_create_dynamic (dest_address);
	route_request_orig_entry->retry_timer = op_intrpt_schedule_call (
		op_sim_time () + route_request_orig_entry->current_request_period, DSRC_ROUTE_REQUEST_TIMER,
											dsr_rte_route_request_expiry_handle, copy_dest_address_ptr);
	
	route_request_orig_entry->last_route_req_time = op_sim_time ();
	route_request_orig_entry->ttl = ttl_value;
	route_request_orig_entry->num_route_discoveries++;
	
	FOUT;
	}


void
dsr_route_request_originating_table_entry_delete (DsrT_Route_Request_Table* route_request_table_ptr, InetT_Address dest_address)
	{
	DsrT_Request_Orig_Entry*		route_request_orig_entry = OPC_NIL;
	char							dest_str [INETC_ADDR_STR_LEN];
	
	/** Deletes an entry from the originating request table	**/
	FIN (dsr_route_request_originating_table_entry_delete (<args>));
	
	/* Get the destination address as a */
	/* string to index the hash table	*/
	inet_address_print (dest_str, dest_address);
	
	/* Check if there exists an entry for this destination	*/
	/* node in the route request table						*/
	route_request_orig_entry = (DsrT_Request_Orig_Entry*) prg_string_hash_table_item_remove 
													(route_request_table_ptr->route_request_send_table, dest_str);
	
	/* Decrement the table size	*/
	route_request_table_ptr->current_table_size--;
	
	/* Update the request table size statistic	*/
	dsr_request_table_size_stat_update (route_request_table_ptr);
	
	/* Free the entry	*/
	dsr_route_request_orig_entry_mem_free (route_request_orig_entry);
	
	FOUT;
	}


Boolean
dsr_route_request_next_request_schedule_possible (DsrT_Route_Request_Table* route_request_table_ptr, 
													InetT_Address dest_address)
	{
	DsrT_Request_Orig_Entry*		route_request_orig_entry = OPC_NIL;
	char							dest_str [INETC_ADDR_STR_LEN];
	
	/** Determines whether to schedule another route request	**/
	/** for the node to the same destination					**/
	FIN (dsr_route_request_next_request_schedule_possible (<args>));
	
	/* Get the destination address as a */
	/* string to index the hash table	*/
	inet_address_print (dest_str, dest_address);
	
	/* Check if there exists an entry for this destination	*/
	/* node in the route request table						*/
	route_request_orig_entry = (DsrT_Request_Orig_Entry*) prg_string_hash_table_item_get 
													(route_request_table_ptr->route_request_send_table, dest_str);
	
	if (route_request_orig_entry->num_route_discoveries >= route_request_table_ptr->max_request_retransmissions)
		{
		/* Maximum number of retransmissions have been reached	*/
		/* No more route requests can be scheduled for this	node*/
		FRET (OPC_FALSE);
		}
	
	/* The next request attempt will double the request timeout	*/
	/* Check if this new doubled request timeout is within the	*/
	/* maximum request period requirements.						*/
	if ((route_request_orig_entry->current_request_period * 2) >= route_request_table_ptr->max_request_period)
		{
		/* The maximum request period has been reached	*/
		/* No more route requests can be scheduled for	*/
		/* this	node									*/
		FRET (OPC_FALSE);
		}
	
	FRET (OPC_TRUE);
	}


void
dsr_route_request_forwarding_table_entry_insert (DsrT_Route_Request_Table* route_request_table_ptr, InetT_Address src_address, 
											InetT_Address dest_address, int request_id)
	{
	PrgT_String_Hash_Table*			src_requests_forward_table = OPC_NIL;
	DsrT_Request_Forward_Entry*		route_request_forward_entry = OPC_NIL;
	char							source_str [INETC_ADDR_STR_LEN];
	char							req_id_str [INETC_ADDR_STR_LEN];
	void*							old_contents_ptr = OPC_NIL;
	
	/** Inserts a route request received from another node	**/
	/** that is to be forwarded into the route request		**/
	/** forward table.										**/
	FIN (dsr_route_request_forwarding_table_entry_insert (<args>));
	
	/* Get the source address as a 		*/
	/* string to index the hash table	*/
	inet_address_print (source_str, src_address);
	
	/* Check if there exists an entry for this source	*/
	/* node in the route request table					*/
	src_requests_forward_table = (PrgT_String_Hash_Table*) prg_string_hash_table_item_get 
													(route_request_table_ptr->route_request_forward_table, source_str);
	
	if (src_requests_forward_table == OPC_NIL)
		{
		/* There does not exist an entry for this source		*/
		/* Check if there is space in the route request table	*/
		/* If the table is full, delete the entry which is 		*/
		/* least recently used (LRU)							*/
		dsr_route_request_table_size_check (route_request_table_ptr);
		
		/* Create the table of route requests received from this source	*/
		src_requests_forward_table = prg_string_hash_table_create (10, 16);
		
		/* Insert the new table for that source into	*/
		/* the forwarded requests table					*/
		prg_string_hash_table_item_insert (route_request_table_ptr->route_request_forward_table, source_str, 
								src_requests_forward_table, &old_contents_ptr);
		
		/* Increment the size of the request table	*/
		route_request_table_ptr->current_table_size++;
		
		/* Update the request table size statistic	*/
		dsr_request_table_size_stat_update (route_request_table_ptr);
		}
	
	/* Get the request ID string	*/
	sprintf (req_id_str, "%d", request_id);
	
	/* Check if there already exists an entry for	*/
	/* the request ID from this source				*/
	route_request_forward_entry  = (DsrT_Request_Forward_Entry*) prg_string_hash_table_item_get 
													(src_requests_forward_table, req_id_str);
	
	if (route_request_forward_entry != OPC_NIL)
		{
		/* There already exists a duplicate entry 	*/