aodv_router.cc

在Linux下做的QuadTree的程序

}

void AODV_Agent::update_route(int index,int seqnum,int metric,
			      nsaddr_t next_hop,double lifetime){
  double now=Scheduler::instance().clock();
  Scheduler& s=Scheduler::instance();
  int rindex;

  rindex=in_reply_queue(rts[index].destination);
 // you haven't gotten a route reply but you got a route to that destination 
  // so you count it as if you've gotten a RREP
  if(rindex!=-1){
    replies[rindex].install_time=now;
  }
  // if we thought that route was broken and now we are updating, so its no
  // longer broken, we want to send the packets that we have queued in the 
  // meantime
  if((rts[index].hop_count==INFINITY)&&(rts[index].q)){
      while(1){
	Packet *p1;
	p1=rts[index].q->deque();
	
	if(!p1) { 
	  //printf("no more packets to deque\n");
	  delete rts[index].q;
	  rts[index].q=0;
	  rts[index].queue_length=0;
	  break;
	}
	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()=next_hop;  // SH
	cmn1->addr_type()=AF_INET;
	cmn1->src_=addr_;
	assert(cmn1->next_hop()!=addr_);
	s.schedule(target_,p1,jitter(JIT, 0));
      }
  }

  // update the route
  if(rts[index].seqnum<seqnum){
    rts[index].seqnum=seqnum;
    rts[index].hop_count=metric;
    rts[index].next_hop=next_hop;
    rts[index].lifetime=now+lifetime;
  }
  else if(rts[index].seqnum==seqnum){
    if(rts[index].hop_count>metric){
      rts[index].hop_count=metric;
      rts[index].next_hop=next_hop;
    }
    if(rts[index].lifetime<now+lifetime){
      rts[index].lifetime=now+lifetime;
    }
  }
 
  else if(seqnum==-1) {
    printf("seqnum is -1 -- oopsie\n");
  }

  //  print_routing_table();
}

// this function checks if we have received the same broadcast and rebroadcasted
// it in the recent past, if so it returns true and we'll drop it

int AODV_Agent::DropBroadcast(nsaddr_t dest, int broadcast_id){
  double now=Scheduler::instance().clock();
  int i;

  // clean up the expired broadcasts first
  for(i=0;i<bi_last+1;i++){
    if(broadcast_ids[i].lifetime<now){
      broadcast_ids[i].id=broadcast_ids[bi_last].id;
      broadcast_ids[i].dest=broadcast_ids[bi_last].dest;
      broadcast_ids[i].lifetime=
	broadcast_ids[bi_last].lifetime;      
      bi_last--;
    }
  }
  // have we seen this broadcast recently ?
  for(i=0;i<bi_last+1;i++){
    if((broadcast_ids[i].dest==dest)&&
       (broadcast_ids[i].id==broadcast_id)){
      return TRUE;
    }
  }
  return FALSE;
}

 
void AODV_Agent::recv(Packet *p, Handler *h){
  hdr_cmn* ch=(hdr_cmn *)p->access(off_cmn_);
  hdr_ip* iph=(hdr_ip *)p->access(off_ip_);
  unsigned char buff[UPDATE_MESSAGES];
  int size_of_data, mesage;

  
    size_of_data=p->accessdatalen();
    if((size_of_data>0)||(ch->ptype_==10)){
      p->accessdata((unsigned char *)buff);
      sscanf((char *)buff,"%d",&mesage);
      if(mesage==HELLO){  // received a hello message 
	process_hello(p);
	return;
      }
      else if(mesage==RREP){
	handle_reply(p);
	return;
      }
      else if(mesage==RREQ){
	handle_request(p);
	return;
      }
      else if(mesage==UREP){
	handle_unsolicited_reply(p);
	return;
      }
      else printf("UNDETERMINED, i.e. sth got garbled\n");
    }
    route_data(p);  
}

// process a hello message
void AODV_Agent::process_hello(Packet* p){
  int lt,index,type, dest, dest_seqnum,hop_count;
  float lifetime;
  Scheduler& s=Scheduler::instance();
  char buff[HELLO_SIZE];
  //  hdr_ip* iph = (hdr_ip*)p->access(off_ip_);
  //  double now=0;
  //now=Scheduler::instance().clock();
  p->accessdata((unsigned char *)buff);

  sscanf(buff,"%d %d %d %d %d", &type,&dest,&dest_seqnum,&hop_count,
	 &lt); 
  lifetime=(float)lt;
  hop_count++;
  if(dest==addr_){
    // printf("got my own hello\n");  // possible with current mac layer?
    Packet::free(p);
    return;
  }
  index=route(dest);

  // we have no route to that neighbor yet
  if(index==-1){
    index=add_route(dest, dest_seqnum,hop_count,dest,lifetime);
    if(index==-1){
      Packet::free(p);
      return;
    }  
    seqnum++;  // change in neighbors => should increment own seqnum

    s.schedule(&handle_broken_link,    // sched an event to keep track of lost HELLO's
	       new Event(),lifetime);  // and signal broken link when several haven't 
    last_event++;                      // been received
    if(last_event==NUM_EVENTS){
      last_event=0;
    }
    event_index[last_event]=index;
  }
  // we have a route to the sender of the hello message, so we update it
  else {
    update_route(index,dest_seqnum, hop_count,dest,lifetime);
    s.schedule(&handle_broken_link,                          // sched an event to keep track of lost HELLO's
	       new Event(),lifetime);                        // and signal broken link when several haven't  
    last_event++;                                            // been received
    if(last_event==NUM_EVENTS){
      last_event=0;
    }
    event_index[last_event]=index;     // keeps track of what index corresponds to what event
  }
  Packet::free(p);
}

// sending a beacon
void AODV_Agent::send_hello(){
  char buff[HELLO_SIZE];
  //  double now=0;
  Scheduler& s=Scheduler::instance();
  //now=Scheduler::instance().clock(
  //printf("%d: Sending hello to %d at %f\n", addr_, IP_BROADCAST,now);

  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_;

  // type node address, seqno, hop count, lifetime
  int jj=(1+ALLOWED_HELLO_LOSS)*HELLO_INTERVAL;
  sprintf(buff, "%d %d %d %d %d",HELLO,addr_,seqnum,0,jj);

  p->init_data(HELLO_SIZE,(unsigned char *)buff);

  ch->size_=40;
  assert(ch->next_hop()!=addr_);
  s.schedule(target_,p,JIT_BASE+jitter(JIT_PERIODIC,make_random_));
}


// add neighbor to the list of active neighbors for a particular destination
void AODV_Agent::add_to_active_neighbors_list(nsaddr_t neighbor,nsaddr_t dest){
  double now;
  int index,j;
  
  if(neighbor==addr_){
    printf("%d: trying to add myself as a neighbor -- hm\n", addr_);
  }

  index=route(dest);
  if(index==-1){
    // no route yet
    printf("no route yet\n");  // this can't happen
    assert(0);
    return;
  }
  else{
    now=Scheduler::instance().clock();
    j=rts[index].end_an_list;
    while(j>-1){  // if neighbor is already registered, just increase its lifetime
      if(rts[index].active_neighbors[j].id==neighbor){
	rts[index].active_neighbors[j].install_time=now+
	  ACTIVE_NEIGHBOR_TIME;
	return;
      }
      j--;
    }
    // neighbor has not been registered yet, so register it
    rts[index].end_an_list++;

    assert(rts[index].end_an_list < NUM_ENTRIES);

    rts[index].active_neighbors[rts[index].end_an_list].id=neighbor;
    rts[index].active_neighbors[rts[index].end_an_list].install_time=now+ACTIVE_NEIGHBOR_TIME;
  }
}

// purge queues from packets to a particular destination that the mac layer considers
// unreachable
void AODV_Agent::purge_queues(nsaddr_t id){

  Scheduler &s = Scheduler::instance();
  Packet *head = 0, *p, *np = 0;
  LL *ll;
  PriQueue* pq;
  int index;

  
  while((p = ifqueue->filter(id))) {
    p->next_ = head;
    head = p; 
  }
  
  /* ll = (LL*) ifqueue->target();
  assert(ll);
  
  pq = (PriQueue*) ll->sendtarget();
  assert(pq);
  
  while((p = pq->filter(id))) {
    p->next_ = head;
    head = p;
  }
  */
  for(p = head; p; p = np) {  
    np = p->next_;
    struct hdr_cmn *cmn;
    cmn=(hdr_cmn *)p->access(off_cmn_);

    if((p->accessdatalen()>0)||(cmn->ptype()==10)){  // message type packets should 
                                                   // not even be here -- they have
     printf("a broadcast in purge queues!\n");     // no callback on them
    }
    route_data(p); 
  }
}       

// callback for packets that the mac layer cannot deliver

void rt_failed_callback(Packet *p, void *arg){

   ((AODV_Agent*) arg)->link_break(p);

}

void AODV_Agent::link_break(Packet* p){
  struct hdr_cmn *cmn;
  int index;
  nsaddr_t dest;
  Scheduler& s=Scheduler::instance();

  cmn=(hdr_cmn *)p->access(off_cmn_);
  struct hdr_ip *iph = (hdr_ip*)p->access(off_ip_);

  if(cmn->next_hop() == addr_) {
    int x=1/0; 
    printf("next_hop=addr\n"); 
    drop(p);return;
  }

  dest=cmn->next_hop();
  
  // broadcasts are not queued and in fact they shouldn't even be here because 
  // they have no callback on them
  if(dest==IP_BROADCAST)
    {
      printf("broadcast in link_break\n");
      drop(p);
      return;
    }
  index=route(dest);
  // check for a bug that existed at one point
  if((index!=-1)&&(rts[index].destination<1)) {printf("dest is < 0\n"); return;}

  if(index!=-1){
    // send an unsilicited reply to all active neughbors unless you've already 
    // done so in which case hop_count will be INFINITY
    if(rts[index].hop_count!=INFINITY){
      send_unsolicited_reply(index);
    }
  }
  purge_queues(dest);
}


void AODV_Agent::route_data(Packet* p){
  hdr_cmn* cmn=(hdr_cmn *)p->access(off_cmn_);
  hdr_ip* iph=(hdr_ip *)p->access(off_ip_);
  nsaddr_t dest;
  int index;
  double now=Scheduler::instance().clock();
  Scheduler& s=Scheduler::instance();

  //printf("%d: routing data, now is %f\n", addr_, now);

  dest=iph->dst();  // extracting the destination node (i.e. w/out the agent address)
  int source=iph->src();

  index=route(dest); // route returns -1 if no route 
  
  int index3=-1;
  if((index!=-1)&&((source)!=(addr_))&&(cmn->src_!=addr_)){
    index3=route(cmn->src_);
     if(index3==-1){
       //    printf("No route to neighbor before adding it to active neighbours, so we add a route to it\n");
       add_route(cmn->src_,-1,1,cmn->src_,HELLO_INTERVAL);
     }
     else{
       rts[index3].hop_count=1;
       rts[index3].lifetime=now+HELLO_INTERVAL;
       
     }
     add_to_active_neighbors_list(cmn->src_,dest);   // we can't be the dest
  }
   int index_nexthop=0;
   if(cmn->src_==addr_){  // packet dropped at the link layer
     index_nexthop=route(cmn->next_hop());
   }

  // if we have no route, or we have a route but its broken or expired
   if((index==-1)||((index!=-1)&&((rts[index].hop_count==INFINITY)
     ||(rts[index].lifetime<now)))){     

   if((source==addr_)&&(in_reply_queue(dest)==-1)){ // if we haven't sent out a request for that route yet

     // if we are the source of the packet and we have broken, expired or no route,
     // send out a RREQ

     if(index==-1){
	 index=add_route(dest,-1,0,0,0);  // adding a route for the proper functioning of
	 if(index==-1){                   // send_request which needs an index into the route
	   Packet::free(p);               // table that it will need when scheduling the request event
	   return;                          
	 }
	 rts[index].q=new PacketQueue;    // queue packets for that destination, so that 
	 rts[index].queue_length=0;       // if and when you get a route to it, you can send 
       }                                 // them
       
	 send_request(dest);  // send req has to be after adding the fake route!
   }
      if(!rts[index].q) {
        //printf("empty queue\n"); 
        rts[index].q=new PacketQueue;
        rts[index].queue_length=1;
	rts[index].q->enque(p);
      }
      else if(rts[index].queue_length==MAX_QUEUE_LENGTH){
          drop(p);
        }
        else{
          rts[index].q->enque(p);
          rts[index].queue_length++;
        }
   
   }  // a packet undeliverable by the mac layer has come back
   else if((index_nexthop==-1)||((index_nexthop!=-1)&&((rts[index_nexthop].hop_count==INFINITY)
						       ||(rts[index_nexthop].lifetime<now)))){     
     
     if((source==addr_)&&(in_reply_queue(cmn->next_hop())==-1)){ // if we haven't sent out a request for that route
       
       // if we are the source of the packet and we have broken, expired or no route,
       // send out a RREQ
       
       if(index_nexthop==-1){
	 index_nexthop=add_route(cmn->next_hop(),-1,0,0,0);  // adding a route for the proper functioning of
	 if(index_nexthop==-1){                   // send_request which needs an index_nexthop into the route
	   Packet::free(p);               // table that it will 
	   return;
	 }
	 rts[index_nexthop].q=new PacketQueue;    // queue packets for that destination, so that 
	 rts[index_nexthop].queue_length=0;       // if and when you get a route to it, you can send 
       }                                          // them
	 send_request(cmn->next_hop());  // send req has to be after adding the fake route!
     } 
     
     if(!rts[index_nexthop].q) {  // if no queue yet, create a queue
       rts[index_nexthop].q=new PacketQueue;
       rts[index_nexthop].queue_length=1;
       rts[index_nexthop].q->enque(p);
     }
      else{
        if(rts[index_nexthop].queue_length==MAX_QUEUE_LENGTH){
          drop(p);
        }
        else{
          rts[index_nexthop].q->enque(p);
          rts[index_nexthop].queue_length++;
        }
      }
   }
   else{
     assert(index!=-1);
     assert(rts[index].lifetime>now);
     assert(rts[index].hop_count!=INFINITY);
     cmn->next_hop()=rts[index].next_hop;
     cmn->addr_type()=AF_INET;
     cmn->src_=addr_;
     cmn->xmit_failure_=rt_failed_callback;
     cmn->xmit_failure_data_=(void*)this;
     assert(cmn->next_hop()!=addr_);
     s.schedule(target_,p,jitter(JIT, 0));
   }
}

// function that handles RREQ packets

void AODV_Agent::handle_request(Packet* p){
  int index,type, num_hops,broadcast_id, dest, dest_seqno,Type, 
    src_ip, src_seqno,BroadCast;
  double lifetime;
  nsaddr_t next_hop;

  double now=Scheduler::instance().clock();
  char buff[RREQ_SIZE];
  int index1;
  Scheduler& s=Scheduler::instance();
  hdr_ip* iph=(hdr_ip *)p->access(off_ip_);