routingtable.c

ucsb大学开发的aodv路由协议代码。

/*
 * Copyright (C) 2001, University of California, Santa Barbara
 * 
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 * 
 * Other copyrights might apply to parts of this software and are so
 * noted when applicable.
 */

/*
 * Parts of this program has been derived from PIM sparse-mode pimd.
 * The pimd program is covered by the license in the accompanying file
 * named "LICENSE.pimd".
 *  
 * The pimd program is COPYRIGHT 1998 by University of Southern California.
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <sys/types.h>
#include <time.h>

#include "aodvConst.h"
#include "aodvSocket.h"
#include "callout.h"
#include "const.h"
#include "debug.h"
#include "helloMsg.h"
#include "inet.h"
#include "kofn.h"
#include "routingTableEntry.h"
#include "rerr.h"
#include "rrep.h"
#include "rreq.h"
#include "rreqResend.h"

#define DELETE_ROUTE 255

static struct RoutingTableEntry *firstRTEntry = NULL;

static void neighborTimeout __P((u_int32_t));

u_int32_t getTime() {
  struct timeval tv;
  
  if (gettimeofday(&tv, NULL) < 0){
    /* Couldn't get time of day */
    return INF;
  }
  return (tv.tv_sec) * 1000 + (tv.tv_usec) / 1000;
}

/*
 * print the routing table
 */
void printRoutingTable(){
  struct RoutingTableEntry *entry = NULL;
  
  trace(TRACE_RT_CHANGE,"Printing Routing Table");
  trace(TRACE_RT_CHANGE,"********************************");
  for(entry=firstRTEntry
	;entry != NULL
	;entry = entry->next) {
    printEntryForChange(entry);
  }
  trace(TRACE_RT_CHANGE,"********************************");
}


/*
 * add the specified route to the kernel's routing table
 */
static int routeToIP(u_int32_t dest, u_int32_t nextHop, char *p_interface){
  char tmp1[150];
  //char tmp2[150];
  trace(TRACE_RT,"routeToIP ");
  trace(TRACE_RT,"routeToIP(dest=%s",inet_fmt_h(dest,s1));
  //trace(TRACE_DEMO,"have route to %s",inet_fmt_h(dest,s1));
  if(dest != getip()){
    trace(TRACE_RT,"routeToIP(nextHop=%s",inet_fmt_h(nextHop,s2));
    
    //add nextHop directly
    sprintf(tmp1,"/sbin/route add -host %s dev %s >/dev/null 2>&1"
        , inet_fmt_h(nextHop,s1), p_interface);
    trace(TRACE_RT,"routeToIP executing:%s", tmp1);
    system(tmp1);
    
    trace(TRACE_DEMO,"have route to %s", inet_fmt_h(nextHop,s1));
    
    if( dest != nextHop ){
      trace(TRACE_DEMO|TRACE_RT,"have route to %s", inet_fmt_h(dest,s1));
      //add destination through nextHop
      sprintf(tmp1,"/sbin/route add -host %s gw %s dev %s >/dev/null 2>&1"
	      , inet_fmt_h(dest,s1), inet_fmt_h(nextHop,s2), p_interface);
      trace(TRACE_RT,"routeToIP executing:%s", tmp1);
      system(tmp1);
    }
  }
  return 0;
}

/*
 * delete the specified route from the kernel's routing table
 * also delete any arp information 
 *      so subsuquent calls will generate RREQ
 */
static int deleteRouteFromIP(u_int32_t dest, char *p_interface){
  static char tmp[150];
  trace(TRACE_DEMO,"removing route to %s",inet_fmt_h(dest,s1));
  //sprintf(tmp,"/sbin/route del -host %s dev %s >/dev/null 2>&1"
  //  , inet_fmt_h(dest,s1), p_interface);
  sprintf(tmp,"/sbin/route del -host %s dev %s"
	  , inet_fmt_h(dest,s1), p_interface);
  trace(TRACE_RT|TRACE_RT_EXPIRE,"deleteRouteFromIP executing:%s", tmp);
  system(tmp);
  return 0;
}



/*
 * get a handle to a route if it exists
 * otherwise return null
 */
struct RoutingTableEntry *getRoute(u_int32_t dest){
  struct RoutingTableEntry *entry = NULL;
  
  trace(TRACE_RT, "getRoute(destintation=%s)",inet_fmt_h(dest,s1));
  //search through linked list
  if (firstRTEntry == NULL){
    trace(TRACE_RT, "getRoute:firstRTEntry was NULL");
    return NULL;
  } else {
    trace(TRACE_RT, "getRoute:first route:%s"
	,inet_fmt_h(firstRTEntry->dest,s1));
    for(entry = firstRTEntry
	  ;entry != NULL
	  ;entry = entry->next){
      //check entry
      trace(TRACE_RT, "getRoute:checking route:%s"
	  ,inet_fmt_h(entry->dest,s1));
      //printEntry(entry);
      if(entry->dest == dest){
	trace(TRACE_RT, "getRoute:found destintation:%s"
	    ,inet_fmt_h(entry->dest,s1));
	return entry;
      } 
    } 
    trace(TRACE_RT, "getRoute:destination not found NULL");
    return NULL;
  }
}

/*
 * get the destination sequence number for the destination
 * if unknown return 0
 * OK
 */
u_int32_t getDestinationSeqNum(u_int32_t dest){
  struct RoutingTableEntry *entry = NULL;
  trace(TRACE_RT, "getDestinationSeqNum(dest=%s)",inet_fmt_h(dest,s1));
  entry = getRoute(dest);
  if(entry != NULL){
    trace(TRACE_RT, "getDestinationSeqNum:destSeqNum:%u"
	,entry->destSeqNum);
    return entry->destSeqNum;
  } else {
    trace(TRACE_RT
	, "getDestinationSeqNum:destSeqNum not found returning:0");
    return 0;
  }
}

/*
 * determine if a route is known to the destination
 */
int routeExists(u_int32_t dest){
  trace(TRACE_RT, "routeExists(dest=%s)",inet_fmt_h(dest,s1));;
  if(getRoute(dest) == NULL){
    trace(TRACE_RT, "routeExists:FALSE");
    return FALSE;
  } else {
    trace(TRACE_RT, "routeExists:TRUE");
    return TRUE;
  }
}

/*
 * determine if a route is valid and known to the destination
 */
int routeIsValid(u_int32_t dest){
  struct RoutingTableEntry *entry = NULL;
  
  trace(TRACE_RT, "routeIsValid(dest=%s)",inet_fmt_h(dest,s1));
  if((entry = getRoute(dest)) == NULL){
    trace(TRACE_RT, "routeIsValid:FALSE");
    return FALSE;
  } else {
    if(
       (entry->hopCount < DELETE_ROUTE)
       && (entry->lifetime > getTime())){
      trace(TRACE_RT, "routeIsValid:TRUE");
      return TRUE;
    } else {
      trace(TRACE_RT, "routeIsValid:FALSE");
      return FALSE;
    }
  }
}

/*
 * check if we have an active route to the destination 
 * with a sequence number >= the sequence number specifed
 */
int haveActiveRoute(u_int32_t dest, u_int32_t destSeqNum){
  trace(TRACE_RT, "haveActiveRoute(dest=%s,destSeqNum=%u)"
      ,inet_fmt_h(dest,s1),destSeqNum);
  if(routeIsValid(dest)){
    if(destSeqNum <= getRoute(dest)->destSeqNum){
      trace(TRACE_RT, "haveActiveRoute:TRUE");
      return TRUE;
    }
  }
  trace(TRACE_RT, "haveActiveRoute:FALSE");
  return FALSE;
}

/*
 * get the TTL (hopCount or lastHopCount) 
 * to a particular destination
 * OK
 * used by expandingRingSearch
 */
u_int32_t getTTL(u_int32_t dest){
  struct RoutingTableEntry *route = NULL;
  route = getRoute(dest);
  if(route != NULL){
    if(routeIsValid(dest)){
      return route->hopCount;
    } else {
      return route->lastHopCount;
    }
  } else {
    return TTL_START;
  }
}


/*
 * get the hopCountto a particular destination
 * if it doesn't exist return -1
 */
int getHopCount(u_int32_t dest){
  struct RoutingTableEntry *route = NULL;
  route = getRoute(dest);
  if(route != NULL){
    return route->hopCount;
  } else {
    return -1;
  }
}

/*
 * determine the next hop
 * if unknown return 0
 */
u_int32_t getNextHop(u_int32_t dest){
  struct RoutingTableEntry *route = NULL;
  trace(TRACE_RT,"getNextHop for %s"
	  ,inet_fmt_h(dest,s1));
  route = getRoute(dest);
  if(route != NULL){
    trace(TRACE_RT,"getNextHop returning %s"
	  ,inet_fmt_h(route->nextHop,s1));
    return route->nextHop;
  } else {
    return 0;
  }
}
/*
 * return the lifetime associated with a particular dest
 */
u_int32_t getLifetime(u_int32_t dest){
  struct RoutingTableEntry *route = NULL;
  route = getRoute(dest);
  if(route != NULL){
    return route->lifetime;
  } else {
    return INF;
  }
}

/*
 * update the lifetime field associated with a particular dest
 */
void updateLifetime(u_int32_t dest, u_int32_t lifetime){
  struct RoutingTableEntry *route = NULL;
  route = getRoute(dest);
  if(route != NULL){
    route->lifetime = lifetime + getTime();
    trace(TRACE_RT,"updating lifetime for %s to %d"
	  ,inet_fmt_h(dest,s1),route->lifetime);
  } else {
    //nothing to do route doesn't exist
  }
}

/*
 * create a new route
 * return a pointer to the new route
 */
static struct RoutingTableEntry *newRoute(u_int32_t dest
					  , u_int32_t destSeqNum
					  , u_int32_t nextHop
					  , u_int32_t hopCount) {
  //struct RoutingTableEntry tmp;
  struct RoutingTableEntry *entry = NULL;
  struct RoutingTableEntry *first = NULL;
  int currentTime;
  //mySeqNum++;
  //trace(TRACE_RT,"Increasing SeqNum to %d because new route",mySeqNum);
  trace(TRACE_RT,"newRoute");
  trace(TRACE_RT,"newRoute(dest=%s",inet_fmt_h(dest,s1));
  trace(TRACE_RT,"newRoute(nextHop=%s",inet_fmt_h(nextHop,s1));
  trace(TRACE_RT,"newRoute(hopCount=%d",hopCount);

  entry = (struct RoutingTableEntry *)
    malloc(sizeof(struct RoutingTableEntry));
  if(entry == NULL){
    log(LOG_ERR,TRUE,"unable to allocate memory, RoutingTableEntry");
  }
  trace(TRACE_RT,"newRoute:ADDRESS:%u",entry);
  
  entry->next = NULL;
  entry->precursors = NULL;
  entry->lifetime = 0;
  entry->dest = dest;
  entry->destSeqNum = destSeqNum;
  entry->interface=0; //TODO FUTURE what goes here?
  entry->lastHopCount=0;
  entry->hopCount=hopCount;
  currentTime=getTime();
  if (entry->lifetime < (REV_ROUTE_LIFE + currentTime)) {
    entry->lifetime = REV_ROUTE_LIFE + currentTime;
  }
  entry->routingFlags=0; //TODO FUTURE what goes here?
  entry->nextHop=nextHop;

  //if hello is on and this is a neighbor add an event for callback
  if((helloMsgRecv == TRUE) && (entry->nextHop == entry->dest)) {
    //don't need to clear time since this is a new route
    trace(TRACE_RT|TRACE_TIMER|TRACE_HELLO
	  ,"setting neighborTimeout timer %i for %s"
	  ,ALLOWED_HELLO_LOSS * HELLO_INTERVAL,inet_fmt_h(entry->dest,s1));
    entry->neighborHelloId 
      = timer_setTimer(ALLOWED_HELLO_LOSS * HELLO_INTERVAL
		       ,(cfunc_t) neighborTimeout
		       ,(void *) entry->dest);
    trace(TRACE_RT|TRACE_HELLO
	  ,"entry->neighborHelloId=%u"
	  ,entry->neighborHelloId);
  } else {
    entry->neighborHelloId = ZERO;
  }
  

  if(firstRTEntry == NULL){
    trace(TRACE_RT, "newRoute:first route added");
    firstRTEntry = entry;
  } else {
    //prepend
    trace(TRACE_RT, "new:route added");
    first = firstRTEntry;
    firstRTEntry = entry;
    firstRTEntry->next = first;
  }

  //add the route to the IP table
  routeToIP(entry->dest,entry->nextHop,interface);
  printRoutingTable();
  return firstRTEntry;
}

/*
 * modify an existing route
 */
static void modifyRoute(struct RoutingTableEntry *entry
			, u_int32_t dest
			, u_int32_t destSeqNum
			, u_int32_t nextHop
			, u_int32_t hopCount) {
  //struct RoutingTableEntry *first = NULL;
  int currentTime;
  
  trace(TRACE_RT,"modifyRoute(hopCount=%d",hopCount);

  //DO ALWAYS
  currentTime=getTime();
  if (entry->lifetime < (REV_ROUTE_LIFE + currentTime)) {
    entry->lifetime = REV_ROUTE_LIFE + currentTime;
  }


  //DO ALWAYS
  //if hello is on and this is a neighbor 
  //clear previous callback and
  //add an event for callback
  if( (helloMsgRecv == TRUE) && (entry->nextHop == entry->dest) ) {
    if(entry->neighborHelloId != ZERO){
      trace(TRACE_RT|TRACE_TIMER|TRACE_HELLO
	    ,"clear neighborTimeout timer, id=%u for %s"
	    ,entry->neighborHelloId,inet_fmt_h(entry->dest,s1));
      timer_clearTimer(entry->neighborHelloId);
    }
    trace(TRACE_RT|TRACE_TIMER|TRACE_HELLO
	  ,"setting neighborTimeout timer %i for %s"
	  ,ALLOWED_HELLO_LOSS * HELLO_INTERVAL,inet_fmt_h(entry->dest,s1));
    entry->neighborHelloId 
      = timer_setTimer(ALLOWED_HELLO_LOSS * HELLO_INTERVAL
		       ,(cfunc_t) neighborTimeout
		       ,(void *) entry->dest);
  } else {
    entry->neighborHelloId = ZERO;
  }

  //check that this is newer info than
  //we have already
  if((dest!=nextHop) 
     && ((destSeqNum < entry->destSeqNum)