aodv_rtable.cc

一个无线自组网aodv路由的扩展版---AOMDV（多径路由协议）。

/* The AODV code developed by the CMU/MONARCH group was optimized
 * and tuned by Samir Das and Mahesh Marina, University of Cincinnati. The 
 * work was partially done in Sun Microsystems.
 * 
 * The original CMU copyright is below. 
 */

/*
Copyright (c) 1997, 1998 Carnegie Mellon University.  All Rights
Reserved. 

Permission to use, copy, modify, and distribute this
software and its documentation is hereby granted (including for
commercial or for-profit use), provided that both the copyright notice
and this permission notice appear in all copies of the software,
derivative works, or modified versions, and any portions thereof, and
that both notices appear in supporting documentation, and that credit
is given to Carnegie Mellon University in all publications reporting
on direct or indirect use of this code or its derivatives.

ALL CODE, SOFTWARE, PROTOCOLS, AND ARCHITECTURES DEVELOPED BY THE CMU
MONARCH PROJECT ARE EXPERIMENTAL AND ARE KNOWN TO HAVE BUGS, SOME OF
WHICH MAY HAVE SERIOUS CONSEQUENCES. CARNEGIE MELLON PROVIDES THIS
SOFTWARE OR OTHER INTELLECTUAL PROPERTY IN ITS ``AS IS'' CONDITION,
AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY
BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE OR
INTELLECTUAL PROPERTY, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
DAMAGE.

Carnegie Mellon encourages (but does not require) users of this
software or intellectual property to return any improvements or
extensions that they make, and to grant Carnegie Mellon the rights to
redistribute these changes without encumbrance.

*/

#include <random.h>
#include <cmu/aodv/aodv.h>

/*
  The Routing Table
*/

aodv_rt_entry::aodv_rt_entry()
{
int i;

 rt_req_timeout = 0.0;
 rt_req_cnt = 0;

 rt_dst = 0;
 rt_seqno = 1;

 rt_last_hop_count = 0;

#ifndef AOMDV
 rt_hops = INFINITY;
 rt_nexthop = 0;
#else // AOMDV
 rt_advertised_hops = INFINITY;
 LIST_INIT(&rt_path_list);
 rt_highest_seqno_heard = 0;
 rt_num_paths_ = 0;
#endif // AOMDV

 // CHANGE
 rt_error = false;
 // CHANGE
 LIST_INIT(&rt_pclist);
 rt_expire = 0.0;
 rt_flags = RTF_DOWN;

 /*
 rt_errors = 0;
 rt_error_time = 0.0;
 */


 for (i=0; i < MAX_HISTORY; i++) {
   rt_disc_latency[i] = 0.0;
 }
 hist_indx = 0;
 rt_req_last_ttl = 0;

 LIST_INIT(&rt_nblist);

};


aodv_rt_entry::~aodv_rt_entry()
{
AODV_Neighbor *nb;

 while((nb = rt_nblist.lh_first)) {
   LIST_REMOVE(nb, nb_link);
   delete nb;
 }

#ifdef AOMDV
AODV_Path *path;

 while((path = rt_path_list.lh_first)) {
   LIST_REMOVE(path, path_link);
   delete path;
 }
#endif // AOMDV

AODV_Precursor *pc;

 while((pc = rt_pclist.lh_first)) {
   LIST_REMOVE(pc, pc_link);
   delete pc;
 }

}


/*
 * Neighbor List Management Functions
 */

void
aodv_rt_entry::nb_insert(nsaddr_t id)
{
AODV_Neighbor *nb = new AODV_Neighbor(id);
        
 assert(nb);
 nb->nb_expire = 0;
 LIST_INSERT_HEAD(&rt_nblist, nb, nb_link);

}


AODV_Neighbor*
aodv_rt_entry::nb_lookup(nsaddr_t id)
{
AODV_Neighbor *nb = rt_nblist.lh_first;

 for(; nb; nb = nb->nb_link.le_next) {
   if(nb->nb_addr == id)
     break;
 }
 return nb;

}

#ifdef AOMDV
AODV_Path*
aodv_rt_entry::path_insert(nsaddr_t nexthop, u_int16_t hopcount, double expire_time, nsaddr_t lasthop=0) {
AODV_Path *path = new AODV_Path(nexthop, hopcount, expire_time, lasthop);
        
	assert(path);
#ifdef DEBUG
  	fprintf(stderr, "%s: (%d\t%d)\n", __FUNCTION__, path->nexthop, path->hopcount);
#endif // DEBUG

	/*
	 * Insert path at the end of the list
	 */
AODV_Path *p = rt_path_list.lh_first;
	if (p) {
 		for(; p->path_link.le_next; p = p->path_link.le_next) ;
 		LIST_INSERT_AFTER(p, path, path_link);
	}
	else {
 		LIST_INSERT_HEAD(&rt_path_list, path, path_link);
	}
	rt_num_paths_ += 1;

	return path;
}

AODV_Path*
aodv_rt_entry::path_lookup(nsaddr_t id)
{
AODV_Path *path = rt_path_list.lh_first;

 for(; path; path = path->path_link.le_next) {
   if (path->nexthop == id)
   	return path;
 }
 return NULL;

}

AODV_Path*
aodv_rt_entry::disjoint_path_lookup(nsaddr_t nexthop, nsaddr_t lasthop)
{
AODV_Path *path = rt_path_list.lh_first;

 for(; path; path = path->path_link.le_next) {
   if ( (path->nexthop == nexthop) && (path->lasthop == lasthop) )
   	return path;
 }
 return NULL;

}

bool
aodv_rt_entry::new_disjoint_path(nsaddr_t nexthop, nsaddr_t lasthop)
{
AODV_Path *path = rt_path_list.lh_first;

 for(; path; path = path->path_link.le_next) {
   if ( (path->nexthop == nexthop) || (path->lasthop == lasthop) )
   	return false;
 }
 return true;

}


AODV_Path*
aodv_rt_entry::path_lookup_lasthop(nsaddr_t id)
{
AODV_Path *path = rt_path_list.lh_first;

 for(; path; path = path->path_link.le_next) {
   if (path->lasthop == id)
   	return path;
 }
 return NULL;

}


void
aodv_rt_entry::path_delete(nsaddr_t id) {
AODV_Path *path = rt_path_list.lh_first;

 for(; path; path = path->path_link.le_next) {
   if(path->nexthop == id) {
     LIST_REMOVE(path,path_link);
     delete path;
     rt_num_paths_ -= 1;
     break;
   }
 }

}

void
aodv_rt_entry::path_delete(void) {
AODV_Path *path;

 while((path = rt_path_list.lh_first)) {
   LIST_REMOVE(path, path_link);
   delete path;
 }
 rt_num_paths_ = 0;
}	

void
aodv_rt_entry::path_delete_longest(void) {
AODV_Path *p = rt_path_list.lh_first;
AODV_Path *path = NULL;
u_int16_t max_hopcount = 0;

 for(; p; p = p->path_link.le_next) {
   if(p->hopcount > max_hopcount) {
	   assert (p->hopcount != INFINITY);
	   path = p;
	   max_hopcount = p->hopcount;
   }
 }

 if (path) {
     LIST_REMOVE(path, path_link);
     delete path;
     rt_num_paths_ -= 1;
 }
}

bool
aodv_rt_entry::path_empty(void) {
AODV_Path *path;

 if ((path = rt_path_list.lh_first)) {
	 assert (rt_num_paths_ > 0);
	 return false;
 }
 else {	
	 assert (rt_num_paths_ == 0);
	 return true;
 }
}	

AODV_Path*
aodv_rt_entry::path_findMinHop(void)
{
AODV_Path *p = rt_path_list.lh_first;
AODV_Path *path = NULL;
u_int16_t min_hopcount = 0xffff;

 for (; p; p = p->path_link.le_next) {
   if (p->hopcount < min_hopcount) {
	   path = p;
	   min_hopcount = p->hopcount;
   }
 }

 return path;
}

AODV_Path*
aodv_rt_entry::path_find(void) {
AODV_Path *p = rt_path_list.lh_first;

	return p;
}

u_int16_t
aodv_rt_entry::path_get_max_hopcount(void)
{
AODV_Path *path = rt_path_list.lh_first;
u_int16_t max_hopcount = 0;

 for(; path; path = path->path_link.le_next) {
   if(path->hopcount > max_hopcount) {
	   max_hopcount = path->hopcount;
   }
 }
 if (max_hopcount == 0) return INFINITY;
 else return max_hopcount;
}

u_int16_t
aodv_rt_entry::path_get_min_hopcount(void)
{
AODV_Path *path = rt_path_list.lh_first;
u_int16_t min_hopcount = INFINITY;

 for(; path; path = path->path_link.le_next) {
   if(path->hopcount < min_hopcount) {
	   min_hopcount = path->hopcount;
   }
 }
 return min_hopcount;
}

double
aodv_rt_entry::path_get_max_expiration_time(void) {
AODV_Path *path = rt_path_list.lh_first;
double max_expire_time = 0;

 for(; path; path = path->path_link.le_next) {
   if(path->expire > max_expire_time) {
	   max_expire_time = path->expire;
   }
 }
 return max_expire_time;
}

void
aodv_rt_entry::path_purge(void) {
double now = Scheduler::instance().clock();
bool cond;

 do {
 AODV_Path *path = rt_path_list.lh_first;
  cond = false;
  for(; path; path = path->path_link.le_next) {
    if(path->expire < now) {
      cond = true;
      LIST_REMOVE(path, path_link);
      delete path;
      rt_num_paths_ -= 1;
      break;
    }
  }
 } while (cond);
}

#endif // AOMDV

/*
 * Precursor List Management Functions
 */

void
aodv_rt_entry::pc_insert(nsaddr_t id)
{
	if (pc_lookup(id) == NULL) {
	AODV_Precursor *pc = new AODV_Precursor(id);
        
 		assert(pc);
 		LIST_INSERT_HEAD(&rt_pclist, pc, pc_link);
	}
}


AODV_Precursor*
aodv_rt_entry::pc_lookup(nsaddr_t id)
{
AODV_Precursor *pc = rt_pclist.lh_first;

 for(; pc; pc = pc->pc_link.le_next) {
   if(pc->pc_addr == id)
   	return pc;
 }
 return NULL;

}

void
aodv_rt_entry::pc_delete(nsaddr_t id) {
AODV_Precursor *pc = rt_pclist.lh_first;

 for(; pc; pc = pc->pc_link.le_next) {
   if(pc->pc_addr == id) {
     LIST_REMOVE(pc,pc_link);
     delete pc;
     break;
   }
 }

}

void
aodv_rt_entry::pc_delete(void) {
AODV_Precursor *pc;

 while((pc = rt_pclist.lh_first)) {
   LIST_REMOVE(pc, pc_link);
   delete pc;
 }
}	

bool
aodv_rt_entry::pc_empty(void) {
AODV_Precursor *pc;

 if ((pc = rt_pclist.lh_first)) return false;
 else return true;
}	

/*
  The Routing Table
*/

aodv_rt_entry*
aodv_rtable::rt_lookup(nsaddr_t id)
{
aodv_rt_entry *rt = rthead.lh_first;

 for(; rt; rt = rt->rt_link.le_next) {
   if(rt->rt_dst == id)
     break;
 }
 return rt;

}

void
aodv_rtable::rt_delete(nsaddr_t id)
{
aodv_rt_entry *rt = rt_lookup(id);

 if(rt) {
   LIST_REMOVE(rt, rt_link);
   delete rt;
 }

}

aodv_rt_entry*
aodv_rtable::rt_add(nsaddr_t id)
{
aodv_rt_entry *rt;

 assert(rt_lookup(id) == 0);
 rt = new aodv_rt_entry;
 assert(rt);
 rt->rt_dst = id;
 LIST_INSERT_HEAD(&rthead, rt, rt_link);
 return rt;
}