routingtable.c

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

	 ||(
	    (destSeqNum == entry->destSeqNum) 
	    && (hopCount >= entry->hopCount)))){
    return;
  }


  entry->destSeqNum = destSeqNum;
  entry->interface=0; //TODO FUTURE what goes here?
  entry->lastHopCount=entry->hopCount;
  entry->hopCount=hopCount;
  entry->routingFlags=0; //TODO FUTURE what goes here?
  
  //if this is an expired route we need to create a
  //new entry in the routing table
  if(entry->hopCount == DELETE_ROUTE){
    //mySeqNum++;
    //trace(TRACE_RT,"Increasing SeqNum to %d because got route to expired"
    //  ,mySeqNum);
  }else if(entry->nextHop != nextHop){
    //remove old route
    deleteRouteFromIP(entry->dest,interface);
    //mySeqNum++;
    //trace(TRACE_RT,"Increasing SeqNum to %d because route changed nextHop"
    //  ,mySeqNum);
  }
  entry->nextHop=nextHop;
  routeToIP(entry->dest,entry->nextHop,interface);
  printRoutingTable();

}

/*
 * update the reverse route to the source using a rreq
 */
void updateReverseRoute(u_int32_t src
			, struct RREQ *rreq){
  struct RoutingTableEntry *entry = NULL;
  removeFromRreqResend(src);
  trace(TRACE_RT, "updateReverseRoute(src=%s)"
      ,inet_fmt_h(src,s1));
  trace(TRACE_RT, "updateReverseRoute(rreq->src=%s)"
      ,inet_fmt_h(ntohl(rreq->src),s1));



  entry = getRoute(ntohl(rreq->src));
  if(entry == NULL){
    trace(TRACE_RT, "updateReverseRoute:new route");
    entry=newRoute(ntohl(rreq->src)
		   , ntohl(rreq->srcSeqNum)
		   , src
		   , rreq->hopCount+1);
  } else {
    trace(TRACE_RT, "updateReverseRoute:modify route");
    modifyRoute(entry
		, ntohl(rreq->src)
		, ntohl(rreq->srcSeqNum)
		, src
		, rreq->hopCount+1); 
  }
  entry = NULL;
}

/*
 * update a route to the destination using rrep
 */
void updateRoute(u_int32_t src
		 , struct RREP *rrep){
  
  struct RoutingTableEntry *entry = NULL;
  trace(TRACE_RT, "updateRoute(src=%s)",inet_fmt_h(src,s1));
  trace(TRACE_RT, "updateRoute(rrep->dest=%s)",inet_fmt_h(ntohl(rrep->dest),s1));

  entry = getRoute(ntohl(rrep->dest));
  if(entry == NULL){
    trace(TRACE_RT, "updateRoute:creating new route");
    entry=newRoute(ntohl(rrep->dest)
		   ,ntohl(rrep->destSeqNum)
		   ,src,rrep->hopCount);
  } else {
    trace(TRACE_RT, "updateRoute:modify route");
    modifyRoute(entry
		,ntohl(rrep->dest)
		,ntohl(rrep->destSeqNum)
		,src
		,rrep->hopCount);
  }
  entry = NULL;
}

/*
 * check if a precuror is already in the list of precursors
 */
int precurDNE(struct Precursor *first, u_int32_t dest_to_add){
  struct Precursor *precur = NULL;
  for(precur = first
	;precur != NULL
	;precur = precur->next) {
    if(precur->dest == dest_to_add){
      trace(TRACE_RT,"precurDNE FALSE");
      return FALSE;
    }
  }
  trace(TRACE_RT,"precurDNE FALSE");
  return TRUE;
}

/*
 * add a precursor to the list of precursors for a particular dest
 */
void addPrecursor(u_int32_t dest, u_int32_t dest_to_add){
  struct RoutingTableEntry *entry = NULL;
  struct Precursor *precur = NULL;
  struct Precursor *tempPrecur = NULL;

  trace(TRACE_RT,"addPrecursor(dest=%s,dest_to_add=%s"
      ,inet_fmt_h(dest,s1),inet_fmt_h(dest_to_add,s2));

  entry=getRoute(dest);
  if((entry != NULL) && (entry->dest != dest_to_add) 
     && (precurDNE(entry->precursors,dest_to_add)) == TRUE){
    
    precur=(struct Precursor *)malloc(sizeof(struct Precursor));

    if(precur == NULL){
      log(LOG_ERR,TRUE,"unable to allocate memory, Precursor");
    }

    precur->dest = dest_to_add;

    if(entry->precursors == NULL){
      trace(TRACE_RT,"first precursor");
      entry->precursors=precur;
      precur->next = NULL;
    } else {
      trace(TRACE_RT,"not first precursor");
      //insert at top
      tempPrecur=entry->precursors;
      entry->precursors=precur;
      precur->next=tempPrecur;
    }
  }
}

/*
 * delete precursors
 */
void deletePrecursors(struct Precursor *first){
  struct Precursor *precur = NULL;
  struct Precursor *next = NULL;
  trace(TRACE_RT,"deletePrecursors");
  if(first != NULL) {
    precur=first;
    while(precur != NULL){
      next=precur->next;
      //free Precursor
      free(precur);
      precur=next;
    }
    first = NULL;
  }
}

/*
 * expire a route
 */
static void expireRoute(struct RoutingTableEntry *entry){

  deleteRouteFromIP(entry->dest,interface);
  
  //time to expire route
  entry->destSeqNum++;
  entry->lastHopCount = entry->hopCount;
  entry->hopCount = DELETE_ROUTE;
  entry->lifetime = getTime() + DELETE_PERIOD;
}


/*
 * called by timer every second, to expire and delete routes
 * whose lifetime is up
 */
void expireRoutes(){
  struct RoutingTableEntry *entry = NULL;
  struct RoutingTableEntry *next = NULL;
  struct RoutingTableEntry *prev = NULL;

  trace(TRACE_RT_EXPIRE,"expireRoutes");
  if(firstRTEntry != NULL) {
    trace(TRACE_RT_EXPIRE,"expireRoutes: time=%u" 
	  , getTime());
    entry = firstRTEntry;
    while(entry != NULL) {
      next=entry->next;
      //check lifetime
      if(entry->lifetime < getTime()) { 
	trace(TRACE_RT_EXPIRE,"expireRoutes: time to do something");
	if (entry->hopCount != DELETE_ROUTE) {
	  trace(TRACE_RT_EXPIRE,"expireRoutes: time to expire route to %s"
	      ,inet_fmt_h(entry->dest,s1));
	  expireRoute(entry);
	} else {
	  trace(TRACE_RT_EXPIRE,"expireRoutes: time to delete route to %s"
	      ,inet_fmt_h(entry->dest,s1));
	  trace(TRACE_DEMO,"time to delete route to %s"
	      ,inet_fmt_h(entry->dest,s1));

	  //time to delete route
	  deletePrecursors(entry->precursors);
	  //free RoutingTableEntry
	  if(entry == firstRTEntry){
	    trace(TRACE_RT_EXPIRE,"expireRoutes: deleting first route");
	    firstRTEntry=next;
	  }
	  free(entry);
	  if(prev != NULL){
	    prev->next = next;
	  }
	  entry=next;
	}
	printRoutingTable();
      } else {
	prev=entry;
	entry=entry->next;
      }
    }
  } else {
    //nothing to do!
    trace(TRACE_RT_EXPIRE,"expireRoutes: nothing to do");
  }
}

/*
 * when generating a rerr
 * append unreachable destinations
 * expire the routes associated with those destinations
 */
void appendUnreachables(struct RERR *rerr, u_int32_t broken){
  struct RoutingTableEntry *route = NULL;
  trace(TRACE_RT|TRACE_RERR,"appendUnreachables");

  //include the broken one if we don't have a route to it
  if (getRoute(broken) == NULL) {
    appendUnreachable(rerr,broken,0);
  }
  
  //for each route in the routing table 
  //that uses this broken as the nextHop
  for(route = firstRTEntry; route != NULL ; route = route->next){
    if((route->nextHop == broken) && (route->hopCount != DELETE_ROUTE )){
      appendUnreachable(rerr,route->dest,route->destSeqNum);
      expireRoute(route);
    }
  }
  printRoutingTable();
}

/*
 * when a link is broken it is removed from the list of precursors
 */
void removeBrokenFromPrecursors(u_int32_t broken){
  struct RoutingTableEntry *route = NULL;
  struct Precursor *precur = NULL;
  struct Precursor *next = NULL;
  struct Precursor *prev = NULL;

  trace(TRACE_RT|TRACE_RERR,"removeBrokenFromPrecursors");

  //check each route for this percursor if found remove it.
  for(route = firstRTEntry
	; route != NULL 
	; route = route->next){
    precur = route->precursors;
    while(precur != NULL) {
      next = precur->next;
      if(precur->dest == broken){
	if(route->precursors == precur){
	  //free Precursors
	  free(route->precursors);
	  route->precursors=next;
	} else {
	  //free Precursors
	  free(precur);
	  prev->next=next;
	}
	precur=next;
      } else {
	prev=precur;
	precur=precur->next;
      }
    }
  }
}

/*
 * When a RERR is received
 * it effects the routing table
 * broken routes are expired
 * route depending on this are added to a new rerr packet
 * and sent out.
 */
int processRERR(u_int32_t src
		, struct RERR *rerr
		, struct RERR *new_rerr) {

  struct UnreachableDest *unreach = NULL;
  struct RoutingTableEntry *route = NULL;
  
  int changed=FALSE;

  trace(TRACE_RERR,"processRERR");
  for( unreach = rerr->unreachables
	 ; unreach != NULL
	 ; unreach = unreach->next ) {

    trace(TRACE_RERR,"processRERR:dest %s"
	,inet_fmt_n(unreach->unreachableDest,s1));
    if(unreach->unreachableDest == getip()){
      //update my sequence number
      if(ntohl(unreach->unreachableDestSeqNum)+1 > mySeqNum){
	mySeqNum = ntohl(unreach->unreachableDestSeqNum)+1;
      }
    }else{
      route = getRoute(ntohl(unreach->unreachableDest));
      if((route != NULL) && (src == route->nextHop)){
	trace(TRACE_RERR,"processRERR:1");
	if( route->destSeqNum <= ntohl(unreach->unreachableDestSeqNum)){
	  trace(TRACE_RERR,"processRERR:2");
	  route->destSeqNum = ntohl(unreach->unreachableDestSeqNum);
	  expireRoute(route);
	  if(route->precursors != NULL){
	    trace(TRACE_RERR,"processRERR:3");
	    appendUnreachable(new_rerr
			      , ntohl(unreach->unreachableDest)
			      , ntohl(unreach->unreachableDestSeqNum));
	  }
	  changed=TRUE;
	} 
      }
    }
    if(changed == TRUE){
      printRoutingTable();
    }
  }

  if(new_rerr->unreachables == NULL){
    trace(TRACE_RERR,"processRERR:FALSE");
    return FALSE;
  } else {
    trace(TRACE_RERR,"processRERR:TRUE");
    return TRUE;
  }
}

/*
 * update the lifetime of a route
 * if one is known
 */
int routeUsed(u_int32_t dest){
  struct RoutingTableEntry *route = NULL;
  if(dest == getip()){
    trace(TRACE_RT,"routeUsed TRUE am dest");
    return TRUE;
  }
  route = getRoute(dest);
  if ( (route != NULL) && (route->hopCount != DELETE_ROUTE) ) {
    route->lifetime = getTime() + ACTIVE_ROUTE_TIMEOUT;
    trace(TRACE_RT|TRACE_DEMO,"routeUsed %s",inet_fmt_h(dest,s1));
    //update nextHop used 
    route = getRoute(route->nextHop);
    if ( (route != NULL) && (route->hopCount != DELETE_ROUTE) ) {
      route->lifetime = getTime() + ACTIVE_ROUTE_TIMEOUT;
      trace(TRACE_RT|TRACE_DEMO
	    ,"routeUsed nexthop %s"
	    ,inet_fmt_h(route->dest,s1));
      trace(TRACE_RT,"routeUsed TRUE");
      return TRUE;
    }
  }
  trace(TRACE_RT,"routeUsed FALSE");
  return FALSE;
  
}

/*
 * check if the destination is a nexthop for someone
 *
 */
int isNextHop(u_int32_t dest){
  struct RoutingTableEntry *entry = NULL;
  
  trace(TRACE_RT,"isNextHop(dest=%s",inet_fmt_h(dest,s1));
  for(entry=firstRTEntry
	;entry != NULL
	;entry = entry->next) {
    if(entry->nextHop == dest){
      return TRUE;
    }
  }
  return FALSE;
}

void incrementDestSeqNum(u_int32_t dest){
  struct RoutingTableEntry *entry = NULL;
  trace(TRACE_RT,"incrementDestSeqNum(dest=%s",inet_fmt_h(dest,s1));
  entry = getRoute(dest);
  if(entry != NULL){
    entry->destSeqNum++;
  }
}

static void neighborTimeout(u_int32_t dest){
  struct RoutingTableEntry *entry = NULL;
  trace(TRACE_RT,"neighborTimeout(dest=%s",inet_fmt_h(dest,s1));
  entry = getRoute(dest);
  if(entry != NULL){
    trace(TRACE_RT|TRACE_RERR|TRACE_HELLO|TRACE_DEMO
	  ,"neighborTimeout for dest=%s"
	  ,inet_fmt_h(dest,s1));
    generateRERR(dest);
  }
}

void updateNeighbor(u_int32_t neighbor, u_int32_t seqNum){
  struct RoutingTableEntry *entry = NULL;
  trace(TRACE_RT,"updateNeighbor(neighbor=%s",inet_fmt_h(neighbor,s1));
  
  if(kofn_flag == TRUE && addkofn(neighbor) < KOFN_REQ){
    return;
  }

  entry = getRoute(neighbor);
  if(entry == NULL){
    //create a new route
    entry=newRoute(neighbor,seqNum,neighbor,1);
  } else {
    //update the route
    modifyRoute(entry,neighbor,seqNum,neighbor,1);
  }
}