aodv_router.cc

在Linux下做的QuadTree的程序

#include <stdlib.h>
#include <math.h>
#include <string.h>
#include "tclcl.h"
#include "packet.h"
#include "ip.h"
#include "tcp.h"
#include "tcp-sink.h"
#include "agent.h"
#include "flags.h"
#include "random.h"
#include <stdio.h>
#include <stdarg.h>
#include "template.h"
#include "timer-handler.h"
#include "mac.h"
#include <assert.h>
#include "cmu/priqueue.h"

#define NUM_ENTRIES 1000
#define HELLO 1
#define RREQ  2
#define RREP  3
#define UREP  4  // unsolicited rrep - when a broken link is detected
#define HELLO_SIZE 50
#define RREQ_SIZE 50
#define RREP_SIZE 50 
#define UREP_SIZE 50
#define NUM_ACTIVE_NEIGHBORS  NUM_ENTRIES
#define NUM_BROADCASTS        3*NUM_ENTRIES // ... HM 
#define INFINITY              NUM_ENTRIES*2
#define NUM_REPLIES           NUM_ENTRIES*3
#define ACTIVE_NEIGHBOR_TIME  300 
#define NUM_EVENTS            2000
#define DELETE_EXPIRED        2
#define UPDATE_MESSAGES       50
#define TRUE                  1 
#define FALSE                 0
#define MAX_QUEUE_LENGTH      5
#define JIT                   0.1


#define HELLO_INTERVAL       1
#define JIT_PERIODIC         0.25*HELLO_INTERVAL
#define JIT_BASE             0.75*HELLO_INTERVAL

#define ACTIVE_ROUTE_TIMEOUT  300
#define ALLOWED_HELLO_LOSS      2
#define BAD_LINK_LIFETIME       3
#define BCAST_ID_SAVE           3  // hm **********
#define NETWORK_DIAMETER      100
#define NODE_TRAVERSAL_TIME     0.4 // that would make a difference when errors are introduced
#define MY_ROUTE_TIMEOUT      600
#define REV_ROUTE_LIFE       3  
#define RREP_WAIT_TIME       3*NODE_TRAVERSAL_TIME*NETWORK_DIAMETER 
#define PREQ_RETRIES         3

static inline double jitter(double max, int make_random_) {
  return (make_random_ ? max*(((double)(random()&0xFFFF))/65536.0) : 0);
}


class AODV_Agent;

class UPDATE_Timer : public TimerHandler {
public:
  UPDATE_Timer(AODV_Agent* a) : TimerHandler()
  { a_=a; }
protected:
  virtual void expire(Event* e);
  AODV_Agent* a_;
};

struct active_neighbor{ 
  int id;
  double install_time;
};

struct routing_table {
  nsaddr_t destination;
  int seqnum;
  int hop_count;
  nsaddr_t next_hop;
  double lifetime;
  struct active_neighbor active_neighbors[NUM_ACTIVE_NEIGHBORS];
  int end_an_list;
  PacketQueue *q;
  int queue_length;
};

// saves the (broadcast_id, source) pairs so that if the agent receives a recenly rebroadcast by it request, it would 
// discard it -- that avoids routing loops of the RREQs

struct broadcast{
  int id;
  nsaddr_t dest;
  double lifetime;
};

// used to keep track of replies to an RREQ

struct reply_info{
  nsaddr_t dest;
  int num_retries;
  double install_time;
};

// handler for the HELLO messages

class UpdateHandler : public Handler {
public:
  UpdateHandler(AODV_Agent* a): a_(a) {}
  void handle(Event*);
protected:
  AODV_Agent* a_;
};

// handler for RREQ messages;  keeps track of when to retry a RREQ if a reply has not been received for a while

class RequestHandler : public Handler {
public:
  RequestHandler(AODV_Agent* a): a_(a) {}
  void handle(Event*);
protected:
  AODV_Agent* a_;
};


class AODV_Agent : public Agent {
public:
  AODV_Agent();
  struct routing_table rts[NUM_ENTRIES];
  int end_of_table;

  void recv(Packet *, Handler *);
  void route_data(Packet *);
  void send_hello();
  void send_request(nsaddr_t);
  void handle_request(Packet *);
  void handle_reply(Packet *);
  void handle_unsolicited_reply(Packet *);
  void send_unsolicited_reply(int);
  void add_to_active_neighbors_list(nsaddr_t neighbor,nsaddr_t dest);
  int add_route(nsaddr_t,int,int,nsaddr_t,double);
  int delete_route(int); 
  void link_break(Packet*);
  void update_route(int,int,int,nsaddr_t,double);
  int DropBroadcast(nsaddr_t, int);
  void process_hello(Packet*);
  int route(nsaddr_t);
  int in_reply_queue(nsaddr_t);
  void purge_queues(nsaddr_t id);
  void print_routing_table(); 
  int command(int,const char*const*);
  void timeout(int);

  //variables

  nsaddr_t node_;
  //nsaddr_t sport_;
  nsaddr_t portID_;
  double interval_;
  UPDATE_Timer update_timer_;
  UpdateHandler handle_broken_link;
  RequestHandler handle_request_retry;
  int seqnum;
  int req_id;
  struct broadcast broadcast_ids[NUM_BROADCASTS];
  int bi_last;
  int event_index[NUM_EVENTS];
  int last_event;
  int next_event; 
  struct reply_info replies[NUM_REPLIES];
  int next_reply;
  int last_reply;
  int make_random_;
  PriQueue* ifqueue;
};


void UpdateHandler::handle(Event *e){
  double now;
  now=Scheduler::instance().clock();
  
  // if route has an INFINITY metric and there was an event scheduled for it, 
  // then we have scheduled it for deletion

  if(a_->rts[a_->event_index[a_->next_event]].hop_count==INFINITY){
    a_->delete_route(a_->event_index[a_->next_event]);
  }
  // otherwise if it the route is expired: 1.  inc seq_num. because the set of 
  // neighbors has changed 2. send an unsolicited reply to the active neighbors for 
  // that route
  else if((a_->rts[a_->event_index[a_->next_event]].lifetime<now)&&
	  (a_->rts[a_->event_index[a_->next_event]].lifetime>0))
    {
      a_->seqnum++;
      a_->send_unsolicited_reply(a_->event_index[a_->next_event]);
  }
  a_->next_event++;

  if(a_->next_event==NUM_EVENTS){
    a_->next_event=0;
  }
  delete e;
}

void RequestHandler::handle(Event *e){
 
  if(e) delete e;
  // if we have gotten a reply to our RREQ or we have retried 3 times, stop retrying
  if((a_->replies[a_->next_reply].install_time>0)||
     (a_->replies[a_->next_reply].num_retries>2)){
    a_->next_reply++;
    if((a_->next_reply-a_->last_reply)==1){
      a_->next_reply=0;
      a_->last_reply=-1;
      //printf("reply queue is empty\n");
    }
    else if(a_->next_reply==NUM_REPLIES){
      a_->next_reply=0;
    }
    return;
  }
  // if we haven't gotten a reply yet and we have retired the request less than 3 times, 
  // retry again: 1. enque event for this RREQ at the end of the queue of request events
  // 2. inc retry 3. send request 4. schedule an event to "keep track of the request"
  else{
    Scheduler& s=Scheduler::instance();
    if(a_->last_reply!=a_->next_reply){
      a_->last_reply++;
      if(a_->last_reply==NUM_REPLIES){
	a_->last_reply=0;
      }
      a_->replies[a_->last_reply].dest=
	a_->replies[a_->next_reply].dest;
      a_->replies[a_->last_reply].install_time=
	a_->replies[a_->next_reply].install_time;    
      a_->replies[a_->last_reply].num_retries=1+
	a_->replies[a_->next_reply].num_retries;
      a_->next_reply++;
      if(a_->next_reply==NUM_REPLIES){
	a_->next_reply=0;
      }
    } 
      a_->send_request(a_->replies[a_->last_reply].dest);
      s.schedule(&(a_->handle_request_retry), 
		 new Event(),RREP_WAIT_TIME);
  }
}



void AODV_Agent::send_unsolicited_reply(int index) {
   nsaddr_t dest;
   double now;
   char buff[UREP_SIZE];
   int j;
   Scheduler& s=Scheduler::instance();

   now=Scheduler::instance().clock();

   // this should not occur -- there is no longrer a route for a route that 
   // expired, i.e. it was deleted in the meantime 
   if(index==-1){
     printf("index is -1 in unsolicited route reply\n");
     return;  
   }
   // you don't delete a route that you have sent a request for and you don't
   // send unsolicited replies for it either
   if(in_reply_queue(rts[index].destination)!=-1){
     //    printf("attempting to delete a RREQ-ed route3\n");
     return;
   }

   dest=rts[index].destination;
   // checks for a bug that existed at one point
   if((dest==0)||(dest==-1)) {printf("ROUTE DELETED\n"); return;}
   rts[index].hop_count=INFINITY;
   rts[index].lifetime=0;  
   // schedule the route for deletion
   s.schedule(&handle_broken_link, new Event(), BAD_LINK_LIFETIME); 
   last_event++;
   if(last_event==NUM_EVENTS){
     last_event=0;
   }
   event_index[last_event]=index;  // save the index that corresponds to the
   // event in event_index so that when the event fires up, we know what route 
   // it was for

   j=rts[index].end_an_list;
   
   // send a message to all the active neighbors,that have not expired, about 
   // the broken route 
   while(j>-1){
     // if a neighbor has expired, take it off the list
     if(rts[index].active_neighbors[j].install_time<now){
       rts[index].active_neighbors[j].id=
	 rts[index].active_neighbors[rts[index].end_an_list].id;
       rts[index].active_neighbors[j].install_time=
	 rts[index].active_neighbors[rts[index].end_an_list].install_time;
       rts[index].end_an_list--;
     }
     else {
       Packet* p=allocpkt();
       
       hdr_ip* iph=(hdr_ip *)p->access(off_ip_);
       hdr_cmn* ch=(hdr_cmn *)p->access(off_cmn_);
       iph->dst()=rts[index].active_neighbors[j].id;
       iph->dport_=0xff;      
       ch->next_hop()=rts[index].active_neighbors[j].id;
       ch->addr_type()=AF_INET;
       ch->src_=sport_;
       // UREP L=0 hop_count dest_ip dest_seqno 
       sprintf(buff,"%d %d %d %d %d", UREP, 0,65535,dest,
	       rts[index].seqnum+1);
       p->init_data(UREP_SIZE, (unsigned char *)buff);
       ch->size_=40;
       assert(ch->next_hop()!=addr_);
       //assert(ch->next_hop() != iph->src_);
       s.schedule(target_,p,jitter(JIT,make_random_));
     }
     j--;
   }
}


// check if we have a route to a particular destination.  If so return its index 
// into the routing table array, else return -1
int AODV_Agent::route(nsaddr_t dest){
  int index=-1;
  int i;
  //  double now=0;
  // now=Scheduler::instance().clock();

  for(i=0;i<end_of_table+1;i++){
    if(rts[i].destination==dest){
      return i;
    }
  }
  return index;
}

void AODV_Agent::print_routing_table(){
  int i;
  double now=now=Scheduler::instance().clock();

  printf("\nROUTING TABLE FOR NODE %d\n", addr_);
  printf("--------------------------------------------------\n");
  for(i=0;i<end_of_table+1;i++){
    printf("dest: %d, seqno: %d, hop_count: %d, next_hop: %d, lifetime is %f\n",  
	   rts[i].destination, rts[i].seqnum, rts[i].hop_count, rts[i].next_hop, rts[i].lifetime);
    //   for(j=0;j<rts[i].end_an_list+1;j++){
    // printf("\nn_id: %d, ", rts[i].active_neighbors[j].id);
    //  printf("install time: %f\n", rts[i].active_neighbors[j].install_time);
    //}
  }
}

// add a new route to the routing table
int AODV_Agent::add_route(nsaddr_t dest, int dest_seqno, 
			  int num_hops, nsaddr_t next_hop,
			  double lifetime){
  double now=Scheduler::instance().clock();
  int rindex;
  

  if(((lifetime<0)||(lifetime==0))&&(dest_seqno!=-1)){
    printf("in add_route\n");
    rindex=1/0;
  }

  
  if(dest==addr_){
    printf("trying to add myself to route table\n");
    return -1;
  }
  rindex=in_reply_queue(dest);

  // 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; 
  }
  end_of_table++;
  assert(end_of_table < NUM_ENTRIES);
  rts[end_of_table].destination=dest;
  rts[end_of_table].seqnum=dest_seqno;
  rts[end_of_table].hop_count=num_hops;
  rts[end_of_table].next_hop=next_hop;
  rts[end_of_table].end_an_list=-1;
  if(lifetime>0){
    rts[end_of_table].lifetime=lifetime+now;    
  }
  else {
    rts[end_of_table].lifetime=0;    
  }
  //  print_routing_table();
  return end_of_table;  
}



int AODV_Agent::delete_route(int index){
  //int i;
  //  float now=Scheduler::instance().clock();

  if(index==-1){
    printf("trying to delete a non-existent route\n");
  }

  if(rts[index].destination<1){
    printf("%d: trying to delete a < 1 route, index is %d, hop count is %d\n", addr_, index, rts[index].hop_count);
    assert(0);
  }
  // we've sent out a request for a broken route, but in the meantime we try to delete it b/c we got 
  // an unsol reply about it; we shouldn't be deleting it so we return
  if(in_reply_queue(rts[index].destination)!=-1){
    //    printf("attempting to delete a RREQ-ed route2\n");
    return;
  }

  //  printf("%d: DELETING route to %d\n", addr_,rts[index].destination);
  //  if(end_of_table==0){
    assert(rts[index].hop_count==INFINITY);
    rts[index].destination=-1;
    rts[index].hop_count=0;
    rts[index].lifetime=0;
    rts[index].end_an_list=-1;  
  if(rts[index].q){
      delete rts[index].q;
      rts[index].q=0;
      rts[index].queue_length=0;
    }
    return end_of_table;
    //} 


  /*

  rts[index].destination=rts[end_of_table].destination;
  rts[index].seqnum=rts[end_of_table].seqnum;
  rts[index].hop_count=rts[end_of_table].hop_count;
  rts[index].next_hop=rts[end_of_table].next_hop;
  rts[index].end_an_list=rts[end_of_table].end_an_list;
  rts[index].lifetime=rts[end_of_table].lifetime;
  for(i=0;i<rts[index].end_an_list+1;i++){
    rts[index].active_neighbors[i].id=
      rts[end_of_table].active_neighbors[i].id;
    rts[index].active_neighbors[i].install_time=
      rts[end_of_table].active_neighbors[i].install_time;
  }
  if(rts[index].q){
    delete rts[index].q;
    rts[index].q=0;
    rts[index].queue_length=0;
  }
  rts[end_of_table].destination=-1;
  rts[end_of_table].hop_count=0;
  rts[end_of_table].lifetime=0;
  end_of_table--;

  */