aodv_router.cc

在Linux下做的QuadTree的程序

  hdr_cmn* cmn=(hdr_cmn *)p->access(off_cmn_);
  //type Type hop_count broadcast_id dest dest_seqnum src_ip src_sno
  p->accessdata((unsigned char *)buff);
  sscanf(buff,"%d %d %d %d %d %d %d %d", &type, &Type, &num_hops, 
	  &broadcast_id,&dest,&dest_seqno, &src_ip,&src_seqno);
  if(src_ip==addr_){
    // got my own request because some neighbor rebroadcast it
    drop(p);
    return;
  }
  index=route(dest);
  int index_nexthop=0;
  if(index!=-1){
    index_nexthop=route(rts[index].next_hop);
  }
  BroadCast=FALSE;

  if(bi_last>-1){
    BroadCast=DropBroadcast(src_ip,broadcast_id);
  }
  if(BroadCast==TRUE){  // we've received the same broadcast within the past BCAST_ID_SAVE seconds
    drop(p);
    return;
  }  
  // assume we are not in our own routing table
  // no route or stale route or broken route or expired route or the next_hop for that 
  // route is unreachable

  else if((index_nexthop==-1)||((index==-1)&&(dest!=(addr_)))||
	  ((index!=-1)&&(rts[index].seqnum<dest_seqno+1))||
	   ((index!=-1)&&(rts[index].hop_count==INFINITY))||
	  ((index!=-1)&&(rts[index].lifetime<now)))  
    {   //stale route message to active neighbors is suggested by the paper but is not done here -- seems like
      assert(dest!=addr_);                         // unnecessary overhead and is not specified in the paper
      num_hops++;
      next_hop=cmn->src_;
      int index3=0;

      index3=route(next_hop);
      if(index3==-1){
	add_route(next_hop, -1,1, next_hop,HELLO_INTERVAL);
      }
      else{
	rts[index3].hop_count=1;
	rts[index3].lifetime=now+HELLO_INTERVAL;
      }

      // else update shouldn't be neecessary in the presence of beacons
      index1=route(src_ip);
      if(index1==-1){
	add_route(src_ip, src_seqno,num_hops-1, next_hop,
		  REV_ROUTE_LIFE);
      }
      else {
	rts[index1].next_hop=next_hop;
	if(rts[index1].lifetime<now+REV_ROUTE_LIFE){
	  rts[index1].lifetime=now+REV_ROUTE_LIFE;
	}
      }
      iph->src()=addr_;
      sprintf(buff, "%d %d %d %d %d %d %d %d", type, 0, num_hops, 
	      broadcast_id,dest,dest_seqno, src_ip,src_seqno);
      p->init_databuf((unsigned char *)buff);
      
      iph->ttl_--;
      cmn->src_=addr_;
      assert(cmn->next_hop()!=addr_);
      s.schedule(target_,p,jitter(JIT, make_random_));
    }
  // we are the dest or we have a fresh route 
  else {
    next_hop=cmn->src_;  
    int index3;
    index3=route(next_hop);
    if(index3==-1){
      add_route(next_hop,-1,1,next_hop,HELLO_INTERVAL);
    }
    else{
      rts[index3].hop_count=1;
      rts[index3].lifetime=now+HELLO_INTERVAL;
    }
    index1=route(src_ip);
    if(index1==-1){
      add_route(src_ip, src_seqno,num_hops, next_hop,ACTIVE_ROUTE_TIMEOUT);
    }
    else {  
      rts[index1].next_hop=next_hop;
      if(rts[index1].lifetime<now+ACTIVE_ROUTE_TIMEOUT){
	rts[index1].lifetime=now+ACTIVE_ROUTE_TIMEOUT;
      }
    }

    if(dest==addr_){
      dest_seqno=seqnum;  
      lifetime=MY_ROUTE_TIMEOUT;
    }
    else {
      num_hops=num_hops+rts[index].hop_count;
      dest_seqno=rts[index].seqnum;
      lifetime=rts[index].lifetime-now; 
      assert(lifetime>0);
      int index3=route(rts[index].next_hop); // do we absolutely need a route to the next hop?
      if(index3==-1){  // we 
	// this case is now handled as if we don't have a route --
	// for new measurements tho, that might need to be printed out or sth *****************
	printf("we do\n, %d", rts[index].next_hop);  // we have a valid route but next hop has expired or unreachable
	drop(p);          
	return;
      }
      else{
	rts[index3].hop_count=1;
	rts[index3].lifetime=now+HELLO_INTERVAL;
      }

      add_to_active_neighbors_list(rts[index].next_hop,src_ip);
    }
    cmn->next_hop()=next_hop;

    cmn->addr_type()=AF_INET;  
    iph->src()=addr_; 
    iph->dst()=src_ip;
    iph->dport_=0xff;

    sprintf(buff, "%d %d %d %d %d %f ", RREP,num_hops,0, 
	    dest,dest_seqno, lifetime);
    cmn->src_=addr_;
    p->init_databuf((unsigned char *)buff);
    if(p->accessdatalen()<1) {printf("DORK"); assert(0);}
    cmn->size_=44;
    assert(cmn->next_hop()!=addr_);
    s.schedule(target_,p,jitter(JIT, make_random_));
  }
  // save the broadcast so that you don't rebroadcast it again later -- that would cause a broadcast storm
  bi_last++;
  if(bi_last==NUM_BROADCASTS){
    printf("out of space for the broadcast ids\n");
    exit(3);
  }
  broadcast_ids[bi_last].id=broadcast_id;
  broadcast_ids[bi_last].dest=src_ip;
  broadcast_ids[bi_last].lifetime=now+(double)BCAST_ID_SAVE;
}


// sends an RREQ message
void AODV_Agent::send_request(nsaddr_t dest){
  char buff[RREQ_SIZE];
  int rindex, index;
  int dest_seqno;
  Scheduler& s=Scheduler::instance();
  double now=0;
 
  Packet* p=allocpkt();
  hdr_ip* iph = (hdr_ip*)p->access(off_ip_);
  hdr_cmn* ch=(hdr_cmn *)p->access(off_cmn_);
  iph->dst()=IP_BROADCAST;
  ch->next_hop()=IP_BROADCAST;
  ch->addr_type()=AF_INET;
  ch->src_=addr_;

  rindex=in_reply_queue(dest);

  if(rindex==-1){  // this seems like it's not necessary as rindex has got to be -1 at this point
    last_reply++;
    if(last_reply==NUM_REPLIES){
      last_reply=0;
    }
    replies[last_reply].dest=dest;
    replies[last_reply].num_retries=0;
    replies[last_reply].install_time=0;
    s.schedule(&handle_request_retry, 
	       new Event(),(double)RREP_WAIT_TIME);
  }
  index=route(dest);
  if(index==-1){  // we are sending a request for a route that was deleted or which we never knew about in the past
    dest_seqno=-1;
  }
  else { // we are sending a request for an expired or broken route
    dest_seqno=rts[index].seqnum;
  }

  sprintf(buff,"%d %d %d %d %d %d %d %d", RREQ, 0, 1, req_id++,dest,
	  dest_seqno, addr_,seqnum); 

  p->init_data(RREQ_SIZE, (unsigned char *)buff);
  ch->size_=52;
  assert(ch->next_hop()!=addr_);
  s.schedule(target_,p,jitter(JIT, make_random_));
}

// this function handles RREP messages
void AODV_Agent::handle_reply(Packet* p){
  int type, num_hops, L, dest_seqno,rindex, index;
  nsaddr_t dest;
  float lifetime;
  Scheduler& s=Scheduler::instance();

  double now=Scheduler::instance().clock();
  char buff[RREP_SIZE];
  hdr_cmn* ch = (hdr_cmn*)p->access(off_cmn_);
  hdr_ip* iph = (hdr_ip*)p->access(off_ip_);

  p->accessdata((unsigned char *)buff);    
 
  sscanf(buff, "%d %d %d %d %d %f ", &type,&num_hops,&L,   
	 &dest,&dest_seqno, &lifetime);                    
  rindex=in_reply_queue(dest);
                                                           
  if(iph->dst()!=addr_){
    assert(ch->src_!=addr_);  // we'd better not have received a RREP which we just fwded on--
    int index2=route(ch->src_);
    if(index2==-1){   // register the neighbor that sent the route reply, in case you don't have it in 
      add_route(ch->src_, -1,1, ch->src_,HELLO_INTERVAL);  // the route table
    }
    else{
      rts[index2].hop_count=1;
      rts[index2].lifetime=now+HELLO_INTERVAL;
    }
    // else {
      // not necessary, will be getting a beacon -- if we remove beacons tho yeah! update_route(index2, X, 1, ch->src_

    index=route(iph->dst()); 
    // we have to fwd the reply back but we don't have a route --  REV time has expired
    if(index==-1){
      printf("REV_ROUTE expired\n");
      drop(p);  
      return;
    }
    // in case this route to the destination from the RREQ is chosen by the source/the requestor, we would need to 
    // be able to forward packets to that destination
    int backindex=route(dest);
    if(backindex==-1){
      add_route(dest, dest_seqno, num_hops,ch->src_, lifetime);
    }
    else{
      // Note to myself: 
      // we are updating the route to the destination -- promiscuous action-- is this part of the protocol?
      update_route(backindex, dest_seqno, num_hops, ch->src_, lifetime);
    }
    ch->next_hop()=rts[index].next_hop;
    ch->addr_type()=AF_INET;  // this is probably already done
    ch->src_=addr_;
    assert(ch->next_hop()!=addr_);
    s.schedule(target_,p,jitter(JIT, make_random_));
    return;
  }
  else {  // the reply is for us 
    assert((index!=-1)||(iph->dst()==addr_));
    if(rindex==-1){  // we already got another reply for that request
      index=route(dest);
      if(index!=-1){
	int index3=route(ch->src_);
	if(index3==-1){
	  add_route(ch->src_, -1,1, ch->src_,HELLO_INTERVAL);
	}
	else{
	  rts[index3].hop_count=1;
	  rts[index3].lifetime=now+HELLO_INTERVAL;
	}
	update_route(index,dest_seqno,num_hops,ch->src_,lifetime);
	
      }
      Packet::free(p);
      return;
    }
    // this is the first reply to that request that we got
    replies[rindex].install_time=now;
    // num requests is maintained by the requester,as well as time init
    assert(dest==replies[rindex].dest);
    index=route(dest);
    if(index==-1){  // this shouldn't happen since we are creating dummy routes for RREQ'sted routes
       printf("its happenin\n");
      int index3=route(ch->src_);
      if(index3==-1){
	add_route(ch->src_, -1,1, ch->src_,HELLO_INTERVAL);
      }
      else{
	rts[index3].hop_count=1;
	rts[index3].lifetime=now+HELLO_INTERVAL;
      }
      add_route(dest,dest_seqno,num_hops,ch->src_,lifetime);
    }
    else{
      // first register the neighbor in your route table or update the route that you have for it
      int index3=route(ch->src_);
      if(index3==-1){  
	add_route(ch->src_, -1,1, ch->src_,HELLO_INTERVAL);
      }
      else{
	rts[index3].hop_count=1;
	rts[index3].lifetime=now+HELLO_INTERVAL;
      }
      update_route(index,dest_seqno,num_hops,ch->src_,lifetime);

      if(rts[index].q==0) {  // if nothing on the queue for that destination return
	Packet::free(p);
	return;
      }
      Packet::free(p);
      while(1){         // there are packets on the queue -- send them
	Packet *p1;
	p1=rts[index].q->deque();

	if(!p1) { 
	  delete rts[index].q;
	  rts[index].q=0;
	  rts[index].queue_length=0;
	  return;
	}
	rts[index].queue_length--;
	hdr_cmn* cmn1 = (hdr_cmn*)p1->access(off_cmn_);
	hdr_ip* iph1 = (hdr_ip*)p1->access(off_ip_);
	cmn1->next_hop()=rts[index].next_hop;
	cmn1->addr_type()=AF_INET;
	cmn1->src_=addr_;

	assert(cmn1->next_hop()!=addr_);
	s.schedule(target_,p1,jitter(JIT, 0));
      }
    }
  }
}

// handle usolicited reply messages for broken routes

void AODV_Agent::handle_unsolicited_reply(Packet* p){
   hdr_ip* iph = (hdr_ip*)p->access(off_ip_);
   char buff[UREP_SIZE];
   int type, L, seqno, metric,index; 
   nsaddr_t dest;
 
#ifdef JOSH
   assert(strlen(p->accessdata()) < sizeof(buff) - 1);
#endif
   p->accessdata((unsigned char*)buff);
   sscanf(buff,"%d %d %d %d %d", &type, &L,&metric,&dest,&seqno);
   
   if((iph->src())==addr_){
     printf("got my own unsol reply\n");
     Packet::free(p);
     return;
   }

 if(in_reply_queue(dest)!=-1){
    //    printf("attempting to delete a RREQ-ed route\n");
    return;
  }
   index=route(dest);
   if(index==-1){   // you had a route but it got deleted in the meantime?
//printf("%d: got an unsolicited reply for a dest ( %d )I no longer have a route to\n",addr_, dest);
     Packet::free(p);
     return;
   }
   else if(rts[index].hop_count==INFINITY){  
     Packet::free(p);  // I already know the route is broken
     return;
   }
   Packet::free(p);
   if(rts[index].destination<1) printf("DEST 0 IN HANDLE_UNSOLICITED_REPLY\n");
   send_unsolicited_reply(index);
}


AODV_Agent::AODV_Agent() : Agent(PT_MESSAGE), update_timer_(this), 
  handle_broken_link(this), handle_request_retry(this), make_random_(1) { 
  interval_=HELLO_INTERVAL;
  end_of_table=-1;
  seqnum=0;
  req_id=0;
  next_event=-1;
  last_event=-1;
  next_reply=0;
  last_reply=-1;
  bi_last=-1;
  bind("node_",&node_);
  bind("portID_",&portID_);
  bind("make_random_",&make_random_);
}


void AODV_Agent::timeout(int p)
{
    send_hello();
    update_timer_.resched(interval_);
}

void UPDATE_Timer::expire(Event *e)
{ 
  a_->timeout(0);
}


static class AODVClass : public TclClass {
public:
  AODVClass() : TclClass("Agent/AODV")
  {}
  TclObject* create(int argc, const char*const* argv){
    return (new AODV_Agent());
  }
}class_aodv;

int AODV_Agent::command(int argc, const char*const* argv){

  Tcl& tcl = Tcl::instance();
  double now=0;
  if(argc>1){
    if(strcmp(argv[1],"start")==0){
      timeout(0);
      return(TCL_OK);
    }
    if (argc == 3) {
      if (strcmp(argv[1], "if-queue") == 0) {
	ifqueue = (PriQueue*)TclObject::lookup(argv[2]);
	if (ifqueue == 0) {
	  tcl.resultf("no such object %s", argv[2]);
	  return (TCL_ERROR);
	}
	return (TCL_OK);
      }
    }
  }
    return (Agent::command(argc, argv));
}


// checks if we have sent out a RREQ for destination dest
int AODV_Agent::in_reply_queue(nsaddr_t dest){
  int i;

  if(last_reply==-1){
    return -1;
  }

  if(last_reply>next_reply){
    for(i=next_reply;i<last_reply+1;i++){
      if(replies[i].dest==dest){
	return i;
      }
    }
  }
  else if(last_reply==next_reply){
      if(replies[last_reply].dest==dest){
	return last_reply;
      }
  }
  else {
    for(i=next_reply;i<NUM_REPLIES;i++){
      if(replies[i].dest==dest){
	return i;
      }
    }
    for(i=0;i<last_reply+1;i++){
      if(replies[i].dest==dest){
	return i;
      }
    }
  }
  return -1;
}