zrp.cc

#include <random.h>
#include <object.h>
#include <route.h>
#include <packet.h>
#include <cmu-trace.h>

#include "zrp.h"

#if defined(WIN32) && !defined(snprintf)
#define snprintf _snprintf
#endif /* WIN32 && !snprintf */

// Nominal settings for some parameters:
//- beacon frequency: 5 seconds
//- ack timeout: 2 seconds
//- neighbor timeout: 15 seconds
//- jitter (and where should I apply it): uniformly distributed 0-2 sec;
// should be applied to the beacon transmission

// main defaults
#define TIME_FACTOR 1
#define DEFAULT_TRANSMIT_JITTER 1
#define DEFAULT_STARTUP_JITTER 3
#define DEFAULT_PROCESS_JITTER 1 
#define DEFAULT_BEACON_PERIOD 5*TIME_FACTOR  // period of beacon transmission in sec
#define DEFAULT_BEACON_PERIOD_JITTER 0
#define DEFAULT_NEIGHBOR_TIMEOUT 15  //seconds
#define DEFAULT_NEIGHBOR_ACK_TIMEOUT 2*TIME_FACTOR // sec
#define DEFAULT_NEIGHBORTABLE_SCAN_PERIOD 11*TIME_FACTOR // scan table every n sec
#define DEFAULT_IARP_UPDATE_PERIOD 22*TIME_FACTOR // time between periodic update in sec
#define SUSPEND_FLAG FALSE // all in/outgoing packets are dropped if TRUE

#define MAX_ROUTE_LENGTH 1000
#define IERP_TTL 40

#define MAX_NUM_NEIGHBORS 20
#define MAX_LINKIE 10 
#define MAX_OUTBOUND_PENDING 20 // max queue for pkts waiting for ierp requests

#define MAX_DETECTED_QUERIES 20 // max queries that can be detected 
#define IERP_REQUEST_TIMEOUT 5 // secs before timeout on an ierp request
#define OUTER_ROUTE_EXPIRATION 20 // secs that a cached route will last

#define HDR_BEACON_LEN 20 // bytes
// zone radius related defines in rtable.h

#define IERPCACHE_SCAN_PERIOD 5
        // scan ierp cache every n number of beacon timeout cycles
#define MAX_ROUTE_LENGTH 20
#define ROUTER_PORT      0xff
#define FOUND 1
#define LOST 0
#define TRUE 1
#define FALSE 0


//========================================================
// ZRP:
// Returns a random number between 0 and max, used for jitter 
//========================================================
static inline double 
jitter (double max, int be_random_) {
  return (be_random_ ? Random::uniform(max) : 0);
}

//========================================================
// ZRP:
// prints to STDOUT Route table and Peripheral list
//========================================================
void ZRPAgent::print_routes() 
{
  rtable_node *j;
  int i;

  printf("Routes ");
  for (i=1; rtable.route[i] != NULL ; i++) {
    printf("[");
    for (j=rtable.route[i]; j!=NULL; j=j->next_  ) {
      printf("%d ",(int)j->id_,j->numhops_);
    }
    printf("] ");
  }
        
  if (rtable.route[1] == NULL) {
    printf("empty "); 
  }

  printf("Periph[");
  for (j=rtable.periphnodes_; j!=NULL; j=j->next_) {
    printf("%d ",(int)j->id_);
  }
  printf("]");
}

// Prints list of neighbors, list of link states, route and peripheral tables
void ZRPAgent::print_tables()
{
  int flag = TRUE;
  
  printf("! Neighbor Table: ");
  for (neighbor_struct* np=neighbors_;
       np != NULL; np=np->next_ ){
    printf("%d ",np->addr_);
    flag = FALSE;
  }
  if (flag) {
    printf("empty ");
  }
  
  printf("! ");
  lstable.print_links();

  printf("! ");
  print_routes();
  
}

//===================================================================
// ZRP:
// A supporting function used in finding the ZRP header in a packet
// You will most likely not use this directly, used by TCL
//===================================================================
int hdr_zrp::offset_;
static class ZRPHeaderClass : public PacketHeaderClass {
public:
        ZRPHeaderClass() : PacketHeaderClass("PacketHeader/ZRP",
                                              sizeof(hdr_zrp)) {
          bind_offset(&hdr_zrp::offset_);
        } 
} class_zrp_hdr;

//===================================================================
// ZRP:
// A binding between ZRP and TCL, you will most likely not change this
//===================================================================
static class ZRPClass : public TclClass {
public:
	ZRPClass() : TclClass("Agent/ZRP") {}
	TclObject* create(int argc, const char*const* argv) {

		return(new ZRPAgent((nsaddr_t) atoi(argv[4])));
		// Tcl code will attach me and then pass in addr to me
		// see tcl/lib/ns-lib.tcl, under create-zrp-agent,
		// is done by "set ragent [new Agent/ZRP [$node id]]"
	}
} class_zrp;

//===================================================================
// ZRP:
// Default Constructor, not really used
// The Tcl script should call the other Main constructor
//===================================================================
ZRPAgent::ZRPAgent() : Agent(PT_TCP), NeighborScanTimer_(this),
		       BeaconTransmitTimer_(this),suspend_flag_(0) ,
		       PeriodicUpdateTimer_(this), AckTimer_(this),
		       rtable(this), 
                       myaddr_(0), myid_('\0'), seq_(1), qid_(1),
		       radius_(DEFAULT_ZONE_RADIUS) {
  // Prashant's Theory on how this works (could be wrong):
  // initialize my address, both int and string forms.
  // this constructor normally isn't called
  // if you decide to use it, my address has to be obtained from
  // some parent Tcl script, ie in my case
  // command("addr id")
  // normally, the other constructor is usually what is called
  myaddr_= this->addr(); // This might not give anything useful back,
  // I do not know my own address, my node does, have to wait for Tcl
  // to connect us and give my my id
  myid_ = Address::instance().print_nodeaddr(myaddr_);
  bind("radius_", (int*)&radius_);

}

//===================================================================
// ZRP:
// Main Constructor for ZRP Agent
//===================================================================
ZRPAgent::ZRPAgent(nsaddr_t id):Agent(PT_TCP), NeighborScanTimer_(this),
				BeaconTransmitTimer_(this), AckTimer_(this),
				num_neighbors_(0), suspend_flag_(0) ,
				PeriodicUpdateTimer_(this), rtable(this),
				myaddr_(id), myid_('\0'), seq_(1),qid_(1),
				radius_(DEFAULT_ZONE_RADIUS),
				transmit_jitter_(DEFAULT_TRANSMIT_JITTER),
				startup_jitter_(DEFAULT_STARTUP_JITTER),
				process_jitter_(DEFAULT_PROCESS_JITTER),
				beacon_period_(DEFAULT_BEACON_PERIOD),
				beacon_period_jitter_(DEFAULT_BEACON_PERIOD_JITTER),
				neighbor_timeout_(DEFAULT_NEIGHBOR_TIMEOUT),
				neighbor_ack_timeout_(DEFAULT_NEIGHBOR_ACK_TIMEOUT),
				neighbortable_scan_period_(DEFAULT_NEIGHBORTABLE_SCAN_PERIOD),
				iarp_update_period_(DEFAULT_IARP_UPDATE_PERIOD)
{

  // initialize my address, both int and string forms
  // my node knows its id, but I (ragent) didn't until now (I think?)
  myid_ = Address::instance().print_nodeaddr(myaddr_);
  Time now = Scheduler::instance().clock(); // get the time

  tx_=0; // initialize counter for transmitted packets
  rx_=0; // initialize counter for received packets

  // inits for tables
  // These are so the table classes know each other and their own IP address
  rtable.my_address_ = id;
  lstable.my_address_ = id;
  rtable.linkstatetable = &lstable;

  // Sequence counter starts at one
  seq_ = 1;

  // This ZRPAgent was just created.
  printf("\n_%2d_ [%6.6f] | Node %d was created. ", myaddr_, (float)now,
	 myaddr_);

  print_tables();
  
  printf("\n");
}

//===================================================================
// ZRP:
// Here are bindings for parameters you can tweak from TCL.
// The first set take no arguments.
// The second set take one argument.
//===================================================================
int  
ZRPAgent::command (int argc, const char *const *argv) {
  Time now = Scheduler::instance().clock(); // get the time

  // First set
  if (argc == 2) { // No argument from TCL
    if (strcmp (argv[1], "start") == 0) { // Init ZRP Agent
      startup();
      return (TCL_OK);
    }
    else if (strcasecmp (argv[1], "ll-queue") == 0) { // who is my ll
      if (!(ll_queue = (PriQueue *) TclObject::lookup (argv[2]))) {
	fprintf (stderr, "ZRP_Agent: ll-queue lookup "
		 "of %s failed\n", argv[2]);
	return TCL_ERROR;
      }
      return TCL_OK; 
    } else if (strcmp (argv[1], "suspend") == 0) { // turns off receipt of pkts
      suspend_flag_ = TRUE;
	printf("_%2d_ [%6.6f] | Node %d suspended. ",
	       myaddr_,now, myaddr_);
	print_tables();
	printf("\n");
      return (TCL_OK);
    } else if (strcmp (argv[1], "unsuspend") == 0) { // turns it back on
      suspend_flag_ = FALSE;
	printf("_%2d_ [%6.6f] | Node %d un-suspended. ",
	       myaddr_,now, myaddr_);
	print_tables();
	printf("\n");
      return (TCL_OK);
    }
    
    // Second set
  } // if argc == 2
  else if (argc == 3)   { // One argument from TCL
    if (strcasecmp (argv[1], "radius") == 0) {
      // change the radius, takes (int) num hops
      int temp;
      temp = atoi(argv[2]);
      if (temp > 0) { // don't change radius unless input is valid value
	printf("_%2d_ [%6.6f] | Radius change from %d to %d ",myaddr_,now,
	       radius_, temp);
	print_tables();
	printf("\n");
	radius_ = temp;
      }
      return TCL_OK;
    }

    // change beacon period, takes (int) number of secs
    if (strcasecmp (argv[1], "beacon_period") == 0) {
      int temp;
      temp = atoi(argv[2]);
      if (temp > 0) { // don't change unless input is valid value
	printf("_%2d_ [%6.6f] | Beacon period change from %d to %d ",
	       myaddr_,now, beacon_period_, temp);
	print_tables();
	printf("\n");
	beacon_period_ = temp;
      }
      return TCL_OK;
    }

    // change beacon period jitter, takes (int) number of secs
    if (strcasecmp (argv[1], "beacon_period_jitter") == 0) { 
      int temp;
      temp = atoi(argv[2]);
      if (temp > 0) { // don't change unless input is valid value
	printf("_%2d_ [%6.6f] | Beacon period jitter change from %d to %d ",
	       myaddr_,now, beacon_period_jitter_, temp);
	print_tables();
	printf("\n");
	beacon_period_jitter_ = temp;
      }
      return TCL_OK;
    }
    
    // change neighbor timeout, takes (int) number of secs    
    if (strcasecmp (argv[1], "neighbor_timeout") == 0) {
      int temp;
      temp = atoi(argv[2]);
      if (temp > 0) { // don't change unless input is valid value
	printf("_%2d_ [%6.6f] | Neighbor timeout change from %d to %d ",
	       myaddr_,now, neighbor_timeout_, temp);
	print_tables();
	printf("\n");
	neighbor_timeout_ = temp;
      }
      return TCL_OK;
    }

    // change neighbor ack timeout, takes (int) number of secs    
    if (strcasecmp (argv[1], "neighbor_ack_timeout") == 0) {
      int temp;
      temp = atoi(argv[2]);
      if (temp > 0) { // don't change unless input is valid value
	printf("_%2d_ [%6.6f] | Neighbor timeout change from %d to %d ",
	       myaddr_,now, neighbor_ack_timeout_, temp);
	print_tables();
	printf("\n");
	neighbor_ack_timeout_ = temp;
      }
      return TCL_OK;
    }
    
    // resets myid_ to correct address
    if (strcasecmp (argv[1], "addr") == 0) {
      char str;
      myaddr_ = Address::instance().str2addr(argv[2]);
      delete myid_; // remove old string @ myid_, avoid memory leak
      myid_ = Address::instance().print_nodeaddr(myaddr_);
      return TCL_OK;
    }

    // Error if we cannot find TclObject
    TclObject *obj;
    if ((obj = TclObject::lookup (argv[2])) == 0) {
      fprintf (stderr, "%s: %s lookup of %s failed\n", __FILE__, argv[1],
	       argv[2]);
      return TCL_ERROR;
    }

    // Returns pointer to a trace target 
    if (strcasecmp (argv[1], "tracetarget") == 0)  {
      tracetarget = (Trace *) obj;
      return TCL_OK;
    }
    // Returns pointer to our node
    else if (strcasecmp (argv[1], "node") == 0) {
      node_ = (MobileNode*) obj;
      return TCL_OK;
    }
    // Returns pointer to port-demux
    else if (strcasecmp (argv[1], "port-dmux") == 0) {
      port_dmux_ = (NsObject *) obj;
	return TCL_OK;
    }
  }  // if argc == 3
  
  return (Agent::command (argc, argv));
}

//===================================================================
// ZRP:
// This is run only when ns-lib.tcl does a "start", see first if-statement
// under command() which calls this 
//===================================================================
void
ZRPAgent::startup() {

  // give to rtable the pointer to lstable, a form of call-back
  rtable.linkstatetable = &lstable;

  // pgi - blank all tables
  for (int i=0; (i< MAX_NODES_PER_ZONE); i++) 
    rtable.route[i] = NULL;
  rtable.periphnodes_=NULL;
  rtable.agent_ = this;
  for (int i=0; i<MAX_QUERY_DETECT_TABLE_SIZE; i++) 
    queries_[i] = NULL;
  
  // Start timers  
  // The timers start at slightly different times. You can also just remove
  // the "start ragent" under create-zrp-agent in ns-lib.tcl
  // and start agents manually in your simulation Tcl script
  // don't forget do a make depend for any changes to tcl/lib/*
  double ttt;
  ttt =  Random::uniform(startup_jitter_);
  NeighborScanTimer_.start(ttt);

  ttt =  Random::uniform(startup_jitter_);
  BeaconTransmitTimer_.start(ttt);

  ttt =  Random::uniform(startup_jitter_);
  PeriodicUpdateTimer_.start(ttt);

  // erase ierp route cache
  for (int i=0; i<MAX_IERP_CACHE; i++) {
    ierpcache[i] = NULL;
  }
  
  // Erase Outer route list
  for (int i=0; i<MAX_NODES_PER_ZONE+1; i++)
      rtable.route[i] = NULL;
  for (int i=0; i<MAX_NODES_PER_ZONE+1; i++)
    rtable.outer_route[i] = NULL;

  // init route table to know its own address
  rtable.my_address_=myaddr_;
}
//=======================================================================
// P a c k e t   Ro u t i n e s
//
//=======================================================================
// Packet routines:
// Creates a fresh new packet and initializes as much as it knows how.
//=======================================================================
Packet* ZRPAgent::pkt_create(ZRPTYPE zrp_type, nsaddr_t addressee, int ttl) 
{
    
  Scheduler & s = Scheduler::instance();  // Useful to send (Schedule) packets
  Packet *p = allocpkt(); // fresh new packet
  hdr_ip *hdrip = HDR_IP(p);
  hdr_cmn *hdrc = HDR_CMN(p);
  hdr_zrp *hdrz = HDR_ZRP(p);

  hdrc->ptype() = PT_ZRP;   // ZRP pkt type
  hdrc->next_hop() = addressee;  
  hdrc->addr_type_ = NS_AF_NONE;
  hdrc->size() = IP_HDR_LEN ;  //  set default packet size
  hdrip->ttl() = ttl;  
  hdrip->saddr() = myaddr_;        // source address
  hdrip->sport() = ROUTER_PORT;    // source port
  hdrip->daddr() = addressee;      // dest address
  hdrip->dport() = ROUTER_PORT;    // dest port
  hdrz->zrptype_ = zrp_type;       // which zrp pkt am I?
  hdrz->numentries_ = 0;           // no entries in data space
  hdrz->seq_ = seq_;               // copy from gobal sequence counter
  hdrz->forwarded_ = 0;            // have not been forwarded before
  hdrz->originator_ = myaddr_;     // I am originator, this is used by NDP/IARP
  hdrz->routeindex_=0;             // where in the route list am I sending ?
  // init to first hop

  // thought I needed this?! but I don't 
  // Looks like free() does take care of an already freed space ok, but I leave
  // this here in case your compiler acts differently
  //hdrz->route_ = (nsaddr_t *)malloc(sizeof(nsaddr_t));
  //hdrz->links_ = (linkie *)malloc(sizeof(linkie));

  inc_seq(); // increments global sequence counter
  return(p);
}

//========================================================
// Packet Routines:
// Dynamically allocates memory for route data in a packet 
// given size is number of nodes in route list
//========================================================
void ZRPAgent::pkt_create_route_data_space(Packet *p, int size) {
  // size is in number of nsaddr_t
  hdr_zrp *hdrz = HDR_ZRP(p);

  free(hdrz->route_); // clear out if there is data already
  hdrz->route_ = (nsaddr_t *)malloc(size*sizeof(nsaddr_t) ) ;      
}

//========================================================
// Packet Routines:
// Frees allocated memory for route data in a packet 
//========================================================
void ZRPAgent::pkt_free_route_data_space(Packet *p) {
  hdr_zrp *hdrz = HDR_ZRP(p);
  free(hdrz->route_);
}

//========================================================
// Packet Routines:
// Dynamically allocates memory for link state data
// in a packet, given size is number of links
//========================================================
void ZRPAgent::pkt_create_link_data_space(Packet *p, int size) {
  // size is in number of linkie
  hdr_zrp *hdrz = HDR_ZRP(p);
  free(hdrz->links_); // clear out if there is data already
  hdrz->links_ = (linkie *)malloc(size*sizeof(linkie) ) ;      
}

//========================================================
// Packet Routines:
// Frees allocated memory for link state data in a packet
//========================================================
void ZRPAgent::pkt_free_link_data_space(Packet *p) {
  hdr_zrp *hdrz = HDR_ZRP(p);
  free(hdrz->links_);
}

//=======================================================================
// Packet Routines:
// Copy an entire packet to another.
//=======================================================================
void ZRPAgent::pkt_copy(Packet *pfrom, Packet *pto) {
  hdr_cmn *hdrcfrom = HDR_CMN(pfrom);
  hdr_ip *hdripfrom = HDR_IP(pfrom);
  hdr_zrp *hdrzfrom = HDR_ZRP(pfrom);
  hdr_cmn *hdrcto = HDR_CMN(pto);
  hdr_ip *hdripto = HDR_IP(pto);
  hdr_zrp *hdrzto = HDR_ZRP(pto);
  int size;
  nsaddr_t *ptrto;
  nsaddr_t *ptrfrom;
  
  size = hdrzfrom->numentries_; // 
  hdrcto->direction() = hdrcfrom->direction();
  hdrcto->ptype() = hdrcfrom->ptype();
  hdrcto->next_hop() = hdrcfrom->next_hop();
  hdrcto->addr_type_ = hdrcfrom->addr_type_;
  hdrcto->size() = hdrcfrom->size() ;

  hdripto->ttl() = hdripfrom->ttl();
  hdripto->saddr() = hdripfrom->saddr();
  hdripto->sport() = hdripfrom->sport();
  hdripto->daddr() =  hdripfrom->daddr();
  hdripto->dport() = hdripfrom->dport();

  hdrzto->zrptype_ = hdrzfrom->zrptype_;
  hdrzto->seq_ = hdrzfrom->seq_;
  hdrzto->numentries_ = hdrzfrom->numentries_;
  hdrzto->originator_ = hdrzfrom->originator_;
  hdrzto->ierpsource_ = hdrzfrom->ierpsource_;
  hdrzto->ierpdest_ = hdrzfrom->ierpdest_;
  hdrzto->iarpsource_ = hdrzfrom->iarpsource_;
  hdrzto->iarpdest_ = hdrzfrom->iarpdest_ ;
  hdrzto->lastbordercaster_ = hdrzfrom->lastbordercaster_;
  hdrzto->pktsent_ = hdrzfrom->pktsent_;
  hdrzto->enc_dport_ = hdrzfrom->enc_dport_;
  hdrzto->enc_daddr_ = hdrzfrom->enc_daddr_;
  hdrzto->enc_ptype_ = hdrzfrom->enc_ptype_;
  hdrzto->qid_ = hdrzfrom->qid_;
  hdrzto->forwarded_ = hdrzfrom->forwarded_;
  hdrzto->routeindex_ = hdrzfrom->routeindex_;

  //free(ptrto);
  pkt_create_route_data_space(pto,size);

  ptrto = hdrzto->route_;
  ptrfrom = hdrzfrom->route_;

  // copy route entries
  for (int i=0; i<size; i++) {
    ptrto[i] = ptrfrom[i];
  }
  // we don't need to copy link data, but if you need to,
  // place code here
}

//=======================================================================
// Packet routines:
// Adds a link state entry to a packet data space
//=======================================================================
void ZRPAgent::pkt_add_link(Packet* p, nsaddr_t lnksrc, nsaddr_t lnkdest,
			    int isup) {
  linkie* ls;
  neighbor_struct* ns;
  int numentries;
  int* seq_stamp;
  hdr_zrp *hdrz = HDR_ZRP(p);

  // current number of entries in our data space
  numentries = hdrz->numentries_;

  // this assumes space has ALREADY been allocated
  // pointer to head of link state entries
  ls = hdrz->links_;

  // add at end of entry list
  ls[numentries].src_ = lnksrc;
  ls[numentries].dest_ = lnkdest;
  ls[numentries].isup_ = isup;
  hdrz->numentries_++; // we just added one
}

//=======================================================================
// Packet routines:
// Add all neighbors link states to this packet p
//=======================================================================
void ZRPAgent::pkt_add_all_links(Packet* p) {
  int* num_entries;
  linkie* ls;
  int neighbor_cnt;
  int seq_stamp;
  hdr_zrp *hdrz = HDR_ZRP(p);
  neighbor_struct* ns;

  // ptr to data area of pkt
  ls = hdrz->links_;

  // place link states consecutively into space
  neighbor_cnt = 0;
  for (ns=neighbors_; ns != NULL; ns=ns->next_) {
    ls[neighbor_cnt].src_ = myaddr_;
    ls[neighbor_cnt].dest_ = ns->addr_;
    ls[neighbor_cnt].isup_ = TRUE; // all on my neighbors are "up"
    neighbor_cnt++;
  }
  hdrz->numentries_ = neighbor_cnt; // will be zero if no neighbors
}

//=======================================================================
// Packet routines:
// Send packet, ie schedule it for sometime in future to target_ of ZRP
// which is handled by LL. This is unicast only to "addressee"
//=======================================================================
void ZRPAgent::pkt_send(Packet* p, nsaddr_t addressee)
{
  Scheduler & s = Scheduler::instance();  // Useful to send (Schedule) packets
  hdr_ip *hdrip = HDR_IP(p);
  hdr_cmn *hdrc = HDR_CMN(p);
  hdr_zrp *hdrz = HDR_ZRP(p);

  // if this node is suspended, drop the packet
  if (suspend_flag_ == TRUE) {
    zdrop(p, DROP_RTR_IARP);
    return;
  }

  // set next hop and dest to addressee
  hdrc->next_hop() = addressee;
  hdrip->daddr() = addressee;
  
  // transmit, no delay
  s.schedule(target_, p, 0);

  tx_++; // increment pkt transmitted counter
  
}

//=======================================================================
// Packet routines:
// Loads link update information indexed by "index" from pkt data
// into link struct 
//=======================================================================
void ZRPAgent::pkt_read_update(Packet* p, link_struct *ls, int index ) {
  hdr_zrp *hdrz = HDR_ZRP(p);
  linkie* ptr;
  link_struct* lnew;

  ptr = hdrz->links_;  // ptr to data area of pkt
  
  ls->src_ = ptr[index].src_ ;
  ls->dest_ = ptr[index].dest_ ;
  ls->isup_ = ptr[index].isup_ ;
}

//=======================================================================
// Packet routines:
// Broadcast packet to all neighbors 
//=======================================================================
void ZRPAgent::pkt_broadcast(Packet* p) {
 Scheduler & s = Scheduler::instance();  // Useful to send (Schedule) packets

  hdr_ip *hdrip = HDR_IP(p);
  hdr_cmn *hdrc = HDR_CMN(p);
  hdr_zrp *hdrz = HDR_ZRP(p);

  // if this node is suspended, drop the packet
  if (suspend_flag_ == TRUE) {
    zdrop(p, DROP_RTR_IARP);
    return;
  }
  hdrc->next_hop() = IP_BROADCAST;
  hdrip->daddr() = IP_BROADCAST;
  // transmit with jitter
  s.schedule(target_, p, Random::uniform(transmit_jitter_) );
  tx_++;
}

//=======================================================================
// Packet routines:
// Add entry (indexed by "entry") for "node" to route list in packet 
// The caller HAS to update hdrz->numentries_ .
//=======================================================================
void ZRPAgent::pkt_add_node(Packet* p, nsaddr_t node, int entry)
{
  int num_entries;
  nsaddr_t *ptr;
  hdr_zrp *hdrz = HDR_ZRP(p);
  hdrz->route_[entry] = node;
}

//=======================================================================
// Packet routines:
// returns the address of the next hop on the route list of a packet
// If error, returns the first node on list
//=======================================================================
nsaddr_t ZRPAgent::find_next_hop(Packet* p)
{
  hdr_zrp *hdrz = HDR_ZRP(p);
  nsaddr_t *ptr;
  nsaddr_t junk;
  int junkie ;
  int i;
  i=hdrz->routeindex_;
  return(hdrz->route_[i+1]);

  junkie = hdrz->numentries_;
  
  if (hdrz->numentries_ > 0) {
    
    ptr = hdrz->route_;
    
    for (int i = 0; i<hdrz->numentries_-1; i++) {
      
      if (ptr[i] == myaddr_) {
	junk = ptr[i+1];
	
	return(junk);
      }
    }
  } else {
    return(-1);
  } 
  
  // default, just return the node first on list
  return(hdrz->route_[0]);
  // ie no next hop
}

//=======================================================================
// Packet routines:
// Sends packet to next hop on the route list of a packet
//=======================================================================
void ZRPAgent::send_next_hop(Packet *p) {
  hdr_zrp *hdrz = HDR_ZRP(p);
  int i;
  hdrz->routeindex_++;
  i=hdrz->routeindex_;
  pkt_send(p,hdrz->route_[i]);  
}

//=======================================================================
// Packet routines:
// Sends packet to previous hop on the route list of a packet
//=======================================================================
void ZRPAgent::send_prev_hop(Packet *p) {
  hdr_zrp *hdrz = HDR_ZRP(p);
  int i;
  hdrz->routeindex_--;
  i=hdrz->routeindex_;
  pkt_send(p,hdrz->route_[i]);  
}

//=======================================================================
// Packet routines:
// Returns the address of the previous hop on the route list of a packet.
// If error, returns the current node's address
//=======================================================================
nsaddr_t ZRPAgent::find_prev_hop(Packet* p) {
  hdr_zrp *hdrz = HDR_ZRP(p);
  nsaddr_t *ptr;
  int i;
  i=hdrz->routeindex_;
  return(hdrz->route_[i-1]);
  
  
  if (hdrz->numentries_ < 2)
    return(myaddr_);  // need more than 1 entry
  ptr = hdrz->route_;

  for (int i = 1; i<hdrz->numentries_; i++) {
    
    if (ptr[i] == myaddr_) {
      return(ptr[i-1]);
    }
  }
  return(myaddr_); // ie no prev hop
}

//=======================================================================
// Packet routines:
// Wrapper for drop().
// Drops packet after properly free dynamic memory allocation.
//=======================================================================
void ZRPAgent::zdrop(Packet *p, const char *s) {
  hdr_zrp *hdrz = HDR_ZRP(p);

  drop(p,s);
  return;    
    
  if (hdrz->links_ != NULL)
    free((void *)hdrz->links_); // extra: free links_ data
  if (hdrz->route_ != NULL)
    free((void *)hdrz->route_); // extra: free route_ data

}

//=======================================================================
// Packet routines:
// Adds an outer route to destination "daddr" to a route list in a packet 
//=======================================================================
int ZRPAgent::add_outer_route(Packet* p, nsaddr_t daddr) {
  nsaddr_t tmp[100];
  int flag = FALSE;
  hdr_zrp *hdrz = HDR_ZRP(p);
  int cntr = 0;
  int gg;
    
  for ( int i = 0; i < MAX_NODES_PER_ZONE && !flag ; i++) {

    if (rtable.outer_route[i] != NULL && rtable.outer_route[i]->id_ == daddr) {
      // found outer route
      flag = TRUE;
      printf("| Added outer route ");
      
      // by definition: numhops+1 = numentries
      gg = rtable.outer_route[i]->numhops_+1 ;
      pkt_create_route_data_space(p, gg);
      
      nsaddr_t *zroute = hdrz->route_;
	
      for (rtable_node *ptr=rtable.outer_route[i]->next_; ptr != NULL;
	   ptr=ptr->next_) {
	zroute[cntr] = ptr->id_;
	printf("%d[%d] ",cntr,zroute[cntr]);
	cntr++;
      } // end for ptr
      printf("\n");
      hdrz->numentries_ = cntr;
    } // end if
  } // end for i
  return(flag);
}

//===================================================================
// Timers: NeighborScanTimer
// Starts NeighborScanTimer, called by startup(), delayed by thistime
// Protocols: NDP
//===================================================================
void ZRPNeighborScanTimer::start(double thistime) {
  Scheduler::instance().schedule(this, &intr, thistime ); 
}

//===================================================================
// Timers: ZRPBeaconTransmitTimer
// Starts BeaconTransmitTimer, called by startup(), delayed by this time
//===================================================================
void ZRPBeaconTransmitTimer::start(double thistime) {
  Scheduler::instance().schedule(this, &intr, thistime ); 
}

//===================================================================
// Timers: PeriodicUpdateTimer
// Starts PeriodicUpdateTimer, called by startup(), delayed by thistime
// Protocols: IARP
//===================================================================
void ZRPPeriodicUpdateTimer::start(double thistime) {
  Scheduler::instance().schedule(this, &intr, thistime ); 
}

//===================================================================
// Timers: BeaconTransmitTimer
// Triggered when it is time to Transmit a Beacon
//===================================================================
void ZRPBeaconTransmitTimer::handle(Event* e) {
  Time now = Scheduler::instance().clock(); // get the time
  char* address;
  Packet* p;
  hdr_zrp *hdrz;

  // Note: we need to specify agent-> to access ZRPAgent methods
  // for all timer classes

  // transmit beacon
  p = agent->pkt_create(NDP_BEACON, IP_BROADCAST, 1); // last arg is TTL
  hdrz = HDR_ZRP(p); // access ZRP part of pkt header
  hdrz->originator_ = agent->myaddr_; // I am originator of pkt
  agent->pkt_broadcast(p); // broadcast pkt
  printf("\n_%2d_ [%6.6f] | Node %d sent a beacon (seq no. %d). "
	 "| Node %d started an ack-timer to expire at %6.6f sec. ",
	 agent->myaddr_, now, agent->myaddr_, hdrz->seq_,
	 agent->myaddr_, (float)now + agent->neighbor_ack_timeout_);

  printf("| radius is %d ",agent->radius_); 

  agent->print_tables();

  printf("\n");  

  agent->AckTimer_.start();   // start ack timer for the beacon sent

  // check outer route requests for expirations
  agent->outer_route_expiration();  
  // check ierp cache for expirations
  agent->scan_ierp_cache();
  // check query detect for expirations
  agent->scan_query_detections();
  // check linkstate expiries, mark for purging later
  agent->scan_linkstate_table();
    
  // schedule next scan in BEACON_PERIOD+jitter() sec
  Scheduler::instance().schedule(this, &intr, agent->beacon_period_ +
				 Random::uniform(agent->beacon_period_jitter_)
				 );
}

//=====================================================================
// Timers: Scanning Query Detect Table
// Scan query detect table, delete expired entries.
//=====================================================================
void ZRPAgent::scan_linkstate_table() {
 Time now = Scheduler::instance().clock(); // get the time
 link_struct *ls;

 // loop through whole link state table
 for (ls=lstable.lshead_ ; ls != NULL; ls=ls->next_) {
   if (ls->expiry_ < now) // if past expiration stamp
     ls->isup_ = FALSE; // mark for purging later
 }
 
}

//=====================================================================
// Timers: Scanning Query Detect Table
// Scan query detect table, delete expired entries.
//=====================================================================
void ZRPAgent::scan_query_detections() {
  QueryDetectEntry *entr;
  int i;
  rtable_node *tmp;
  Time now = Scheduler::instance().clock(); // get the time

  for (i=0; i<MAX_QUERY_DETECT_TABLE_SIZE; i++) {
    // if entry is not NULL and has expired, delete
    if ( (queries_[i] != NULL) && (queries_[i]->expiry_ < now) ) {

      // delete entire list of covered nodes
      for (rtable_node *p=queries_[i]->next_; p!=NULL; ) {
	tmp = p;
	p=p->next_;
	delete tmp;
      }

      // delete entry
      delete queries_[i];
      queries_[i] = NULL; 
    } // endif
  }
}

//=====================================================================
// IERP:
// Checks all outer routes to see if they have expired, deletes those
// that have. Triggered by timer.
//=====================================================================
void ZRPAgent::outer_route_expiration() {
  Time now = Scheduler::instance().clock(); // get the time
  rtable_node *tmp;
  int i;
  int flag;
  flag = FALSE;
    
  printf("\n_%2d_ [%6.6f] | Checking outer route expirations. ",myaddr_,now);

  // Check table
  for (  i = 0; i < MAX_OUTER_ROUTES ; i++) {

    if (rtable.outer_route[i] != NULL && rtable.outer_route[i]->id_ != -99 &&
	rtable.outer_route[i]->expiry_ < now) { // if expired
      flag=TRUE;
      
      printf("| Outer route for node %d expired at %6.3f. "
	     "It has been DELETED . Route = ",
	     rtable.outer_route[i]->id_, rtable.outer_route[i]->expiry_);

      // delete the outer route entry - it is a linked list
      for (rtable_node *ptr=rtable.outer_route[i]->next_; ptr!=NULL; ) {
	tmp = ptr;
	printf("%d ",tmp->id_);
	ptr=ptr->next_;
      }

      // mark deleted 
      rtable.outer_route[i]->id_ = -99;
      
    }
  }
  if (!flag)
    printf("| None expired.");
  
  printf("\n");
  
}
//===========================================================
// Timers: NeighborScanTimer
// Triggered by alarm for scanning NDP table. If there is a new
// neighbor, update IARP and re-compute route table.
// Protocols: NDP, NDP notifies IARP
//===========================================================
void ZRPNeighborScanTimer::handle(Event* e) {
  Time now = Scheduler::instance().clock(); // get the time
  neighbor_struct* ns,nstemp;
  neighbor_struct* tmp;
  Packet* p;
  nsaddr_t na;
  Time tout;
  int flag = FALSE; // have we deleted a neighbor ?
  int ls;
  int seq_match;
  int* seq_stamp, num_entries;
  hdr_zrp *hdrz;
  
  // no neighbors yet, nothing to tell IARP
  if (agent->neighbors_ == NULL) {
    printf("\n_%2d_ [%6.6f] | Node %d neighborscan-timer timed out, "
	   "but neighbor table is empty. Next scan at %6.6f sec.",
	   agent->myaddr_, now, agent->myaddr_,
	   now + agent->neighbortable_scan_period_);
    
    goto EOFF;
  }
  
  // insert a dummy struct at head to make it work
  neighbor_struct dummy;  
  dummy.next_ = agent->neighbors_;
  agent->neighbors_ = &dummy;

  printf("\n_%2d_ [%6.6f] | Node %d neighborscan-timer timed out. "
	 "Next scan at %6.6f sec.  ",
	 agent->myaddr_, now, agent->myaddr_,
	 now + agent->neighbortable_scan_period_);
  
  // drop timed-out neighbors who didn't ack 
  for (ns=agent->neighbors_; ns->next_ != NULL; ) {

    if (ns->next_->expiry_ < now) { // timed out
      na = ns->next_->addr_;
      tout = ns->next_->expiry_;
      
      printf("| Node %d detected that the entry for Node %d has expired. "
	     "Expiry was at %6.6f sec. ",
	     agent->myaddr_, na, tout);

      // delete node
      neighbor_struct *temp = ns->next_;
      ns->next_ = ns->next_->next_;
      delete temp;
      
      if (flag == FALSE) { // if first time we detect a timeout in this for-loop
	p = agent->pkt_create(IARP_UPDATE, IP_BROADCAST, agent->radius_*2-1); 
	// allocate area for our update data in packet, we set it to max
	// current number of neighbors, but we only will use number of
	// neighbors that timed out
	agent->pkt_create_link_data_space(p,MAX_LINKIE);
	hdrz = HDR_ZRP(p);
      }

      // NDP TO IARP: update lstable
      ls = agent->lstable.update(na,agent->myaddr_,FALSE,0,&seq_match) ;

      agent->rtable.compute_routes(agent->myaddr_,agent->radius_);
      // Don't care if my table was updated or not, let's
      // tell all other nodes regardless
      agent->pkt_add_link(p,agent->myaddr_, na, FALSE);
      flag=TRUE; //indicates we have at least one drop and subsequent update
    } else {
      printf("| Node %d detected that the entry for Node %d has not expired. "
	     "Expiry will be at %6.6f sec.", agent->myaddr_, ns->next_->addr_,
	     ns->next_->expiry_);
      ns=ns->next_;
    }
  }
  
  // reset neighbors_ to head of list
  agent->neighbors_ = dummy.next_;
  
  if (flag) { // we had at least one update, increment sequence
    agent->pkt_broadcast(p);
    printf("| Node %d sent update (seq no. %d) about neighbors "
	   "dropped ( ", agent->myaddr_, hdrz->seq_);
    for (int i=0; i<hdrz->numentries_; i++) {
      link_struct curr;
      agent->pkt_read_update(p, &curr, i);
      printf("%d ",curr.dest_);
    }
    printf(") due to expiry timeout. ");
  }

 EOFF:
  agent->print_tables();
  printf("\n");
  // re-schedule timer
  Scheduler::instance().schedule(this, &intr, agent->neighbortable_scan_period_);
}


//=====================================================================
// Timers: PeriodicUpdateTimer
// Triggered when it is time to do a link update
// Protocols: IARP
//=====================================================================
void ZRPPeriodicUpdateTimer::handle(Event* e) {
  Scheduler & s = Scheduler::instance();  // Useful to send (Schedule) packets

  agent->do_update(); 
  Scheduler::instance().schedule(this, &intr, agent->iarp_update_period_ );

}

//=====================================================================
// IARP:
// This actually does the work for doing link update,
// re-computes route table. Called by ZRPPeriodicUpdateTimer::handle().
//=====================================================================
void ZRPAgent::do_update() {
  Time now = Scheduler::instance().clock(); // get the time
  Packet* p;
  hdr_zrp *hdrz = HDR_ZRP(p);
  link_struct templink;
  
  // clean_link_table_of_down_and_expired_links
  lstable.purge_links();
  // re-compute route table
  rtable.compute_routes(myaddr_, radius_);

  // only send an update if we have neighbors
  if (neighbors_ != NULL) {
    printf("\n_%2d_ [%6.6f] | Node %d sent periodic update (seq no. %d) "
	   "containing ( ", myaddr_, (float)now , myaddr_, seq_);
	
    p = pkt_create(IARP_UPDATE, IP_BROADCAST, radius_*2-1); 

    pkt_create_link_data_space(p,MAX_LINKIE); // make space in packet
    pkt_add_all_links(p); // add entire link state table to packet data space

    // Print link states in pkt data, redundant but for debug purposes
    for (int i=0; i<num_neighbors_; i++) {
      pkt_read_update(p, &templink, i);
      if (templink.isup_ == TRUE) 
	printf("%d=%d ",templink.src_,templink.dest_ );
      else
	printf("%d#%d ",templink.src_,templink.dest_ );
    }

    printf("). ");

    pkt_broadcast(p); // broadcast packet

  } else {
    printf("\n_%2d_ [%6.6f] | Node %d has no neighbors to put in this"
	   "periodic update.", myaddr_, now, myaddr_);
  }
  print_tables();
  printf("\n");
}

//=======================================================================
// Timers:  AckTimer
// Schedule timeout at neighbor_ack_timeout_, just sent a Beacon.
// Protocol: NDP
//=======================================================================
void ZRPAckTimer::start() {
  Scheduler::instance().schedule(this, &intr, agent->neighbor_ack_timeout_);
}

//=======================================================================
// Timers:  AckTimer
// Handle a scheduled timeout neighbor_ack_timeout_ secs since we sent
// original Beacon.
// Remove neighbor if it is in our list. If any were removed, update IARP &
// send an immediate update ("triggered update").
// Protocols: NDP, a call to IARP
//=======================================================================
void ZRPAckTimer::handle(Event* e) {
  Time now = Scheduler::instance().clock(); // get the time
  neighbor_struct* ns,nstemp;
  neighbor_struct* tmp;
  Packet* p;
  nsaddr_t na;
  Time tout;
  Time lastack;
  int flag = FALSE; // have we deleted a neighbor ?
  int ls;
  int seq_match;
  int* seq_stamp, num_entries;
  hdr_zrp *hdrz;
  
  // no neighbors yet, nothing to tell IARP
  if (agent->neighbors_ == NULL) {
    printf("\n_%2d_ [%6.6f] | Node %d ack-timer timed out, but neighbor"
	   "table is empty. ", agent->myaddr_, now, agent->myaddr_);
    agent->print_tables();
    printf("\n");
    return;
  }
  
  // insert a dummy struct at head
  neighbor_struct dummy;  
  dummy.next_ = agent->neighbors_;
  agent->neighbors_ = &dummy;
  
  printf("\n_%2d_ [%6.6f] | Node %d ack-timer timed out. ",
	 agent->myaddr_, now, agent->myaddr_);
  
  // drop timed-out neighbors who didn't ack 
  for (ns=agent->neighbors_; ns->next_ != NULL; ) {

    if ( (now - ns->next_->lastack_) > agent->neighbor_ack_timeout_ ) {
      printf("| Node %d did not receive ack from Node %d before timeout. "
	     "Lastack expiry was at %6.6f sec. ",
	     agent->myaddr_, ns->next_->addr_,
	     ns->next_->lastack_+ agent->neighbor_ack_timeout_);
      
      na = ns->next_->addr_;
      tout = ns->next_->expiry_;
      lastack =  ns->next_->lastack_;
          
      // delete node
      neighbor_struct *temp = ns->next_;
      ns->next_ = ns->next_->next_;
      delete temp;

      // total number of neighbors
      agent->num_neighbors_ --;
 
      if (flag == FALSE) { // if occurring for first time

	p = agent->pkt_create(IARP_UPDATE, IP_BROADCAST, agent->radius_*2-1); 
	// allocate area for our update data in packet, we set it to max
	// current number of neighbors, but we only will use number of
	// neighbors that timed out
	agent->pkt_create_link_data_space(p,MAX_LINKIE);
	    
	hdrz = HDR_ZRP(p);
      }

      // NDP TO IARP: update lstable
      ls = agent->lstable.update(na,agent->myaddr_,FALSE,0,&seq_match) ;
      agent->rtable.compute_routes(agent->myaddr_,agent->radius_);
      //      if (ls) { Don't care if my table was updated or not, let's
      // tell all other nodes regardless
      agent->pkt_add_link(p,agent->myaddr_, na, FALSE);
      flag=TRUE; //indicates we have at least one drop and subsequent update
      //      }
    } else {
      printf("| Node %d received ack from Node %d before time-out. "
	     "Lastack expiry was at %6.6f sec.", agent->myaddr_, ns->next_->addr_,
	     ns->next_->lastack_ + agent->neighbor_ack_timeout_);
      /// ns->next_->lastack_ = now; // update neighbor lastack WRONG
      // the acktimer and the neighborscantimer routines DO NOT
      // alter the last/expiry field of the neighbor
      // they only read it, and decide to delete the neighbor from the
      // table or not
      ns=ns->next_;
    }
  }
  
  // reset neighbors_ to head of list, see hack above
  // FUTURE can do this a different way without changing neighbors_
  // in for loop, say ns=&dummy ?
  agent->neighbors_ = dummy.next_;
  //  delete dptr doesn't work! 
  
  if (flag) { // we had at least one update, send
    agent->pkt_broadcast(p);
    printf("| Node %d sent update (seq no. %d) about neighbors "
	   "dropped ( ", agent->myaddr_, hdrz->seq_);
    for (int i=0; i<hdrz->numentries_; i++) {
      link_struct curr;
      agent->pkt_read_update(p, &curr, i);
      printf("%d ",curr.dest_);
    }
    printf(") due to ack timeout. ");
    
  }

 EOFF:
  agent->print_tables();
  printf("\n");  
}

//=======================================================================
// Timers:  Scanning IERP Cache
// If any IERP requests time out, delete them.
// Protocol: IERP
//=======================================================================
void ZRPAgent::scan_ierp_cache() {
  IERPCacheEntry *entr;
  int i;
  Time now = Scheduler::instance().clock(); // get the time

  for (i=0; i<MAX_IERP_CACHE; i++) {
    if ( (ierpcache[i] != NULL) && (ierpcache[i]->expiry_ < now) ) {
      zdrop(ierpcache[i]->pkt_ ,DROP_RTR_NO_ROUTE);
      delete ierpcache[i];  // the request is dead
      ierpcache[i] = NULL;
    }
  }
}

//=======================================================================
// IERP:
// Pass route in proute to iarp to add to cached packet and send,
// and also save route in outer_route table
// Protocol: IERP, notifies IARP
//=======================================================================
void ZRPAgent::ierp_notify_iarp(Packet *proute) { 
  hdr_zrp *hdrzroute = HDR_ZRP(proute);
  nsaddr_t junk,daddr;
  Time now = Scheduler::instance().clock(); // get the time
  int dst, st,cntr;
  int found,flag;
  rtable_node *ptr;
  nsaddr_t *zroute;
  int numentries,qid;
    
  zroute = hdrzroute->route_;
  numentries = hdrzroute->numentries_;
  qid = hdrzroute->qid_;
    
  // 1. copy new route to outer_route table
  // 2. find cached packet
  // 3. if not found, return "drop cached packet, delete cache entry" is WRONG
  // 4. if found, add_outer_route to it and send it
  
  // 1. copy new outer_route to outer_route table

  // flag indicates true if we find a free spot
  flag = FALSE;
  
  // find a free spot in outer_route table
  for ( int i = 0; i < MAX_OUTER_ROUTES && !flag ; i++) {
    if (rtable.outer_route[i] == NULL) {
      flag = TRUE;
      dst = i;

      // If we happen to find the route in table, keep the shorter route 
    } else if (rtable.outer_route[i]->id_ == hdrzroute->ierpdest_) {
      dst=i;

      printf("| Outer route already in ierp cache, ");

      // keep the shorter route	    
      // by definition: numhops+1 = numentries
      // if length of store route < length of newly received accum route 
      if (rtable.outer_route[dst]->numhops_+1 <= numentries) {
	printf("newly received route is longer or the same, keeping "
	       "stored route. ");
	return;
      }

      // the printf explains the next section 
      printf("new route is shorter, replacing stored with new route [");
      // delete old route
      rtable_node *tmp;
      for (ptr=rtable.outer_route[dst]->next_; ptr!=NULL; ){
	tmp = ptr;
	ptr=ptr->next_;
	delete tmp;
      }

      rtable_node * nptr = NULL;
      
      // create list backward
      for (int i=numentries-1; i >=0; i--) {
	//printf("%d ",zroute[i]);
	tmp = new rtable_node;
	tmp->id_ = zroute[i];
	tmp->next_ = nptr;
	nptr=tmp;
      }

      // put new route list into route entry 
      rtable.outer_route[dst]->next_ = nptr;
      for (rtable_node *ptr=rtable.outer_route[dst]->next_; ptr!=NULL;
         ptr=ptr->next_)
      printf("%d ",ptr->id_);

      printf("].\n");

      return; // pkt deleted upon return
    }
    
  }

  // Our outer route table is full
  
  if (!flag) {
    printf("No more room in outer_route table for new routes!\n");
    zdrop(proute,DROP_RTR_IARP); // drop route reply
    return;
  }

  assert(flag); // if no more room in outer_route table, need to increase

  // create new head for entry
  rtable.outer_route[dst] = new rtable_entry;

  // copy the dest id to the header node, stamp with expiry, add numhops
  rtable.outer_route[dst]->id_ = zroute[numentries - 1];
  rtable.outer_route[dst]->expiry_ = now + OUTER_ROUTE_EXPIRATION;
  rtable.outer_route[dst]->numhops_ = numentries - 1; 

  // copy first node address of route list
  ptr = new rtable_node;
  rtable.outer_route[dst]->next_ = ptr;
  
  // copy rest of route to the linked list in outer_route entry
  for (int j=0; j <= rtable.outer_route[dst]->numhops_ ; j++) {
    ptr->next_ = new rtable_node;
    ptr = ptr->next_; 
    ptr->id_ = zroute[j];
    ptr->numhops_ = j;
  }
  ptr = rtable.outer_route[dst]->next_;
  rtable.outer_route[dst]->next_ = ptr->next_;
  delete(ptr);
    
  printf("copied route ");
  cntr=0;
  
  for (ptr=rtable.outer_route[dst]->next_; ptr !=NULL; ptr=ptr->next_) {
    printf("%d(%d) ",cntr++,ptr->id_);
  } printf("\n");
  
  // 2. find cached packet

  assert(numentries > 3); // the route list must at minimum
  // include myself + 1 more + 1 more for outer routes at radius=1 

  // finding cached request, flag = TRUE if found, $found = index
  flag = FALSE;
  for (int i=0; i<MAX_IERP_CACHE && !flag; i++) { 
    
    if (ierpcache[i] != NULL && qid == ierpcache[i]->qid_) {
	flag = TRUE;
	found = i;
    }
  }
      
  if (!flag) {
    // 3. if not found, return 
    // no cached route, must have expired
    // should we try again, another request?
    printf("cached ierp request not found, must have expired."
	   "Dropping ierp reply.\n");
    
  } else {

    // 4. if found, add_outer_route to it and send it    
    Packet *p = ierpcache[found]->pkt_;
    hdr_zrp *hdrz = HDR_ZRP(p);
    hdr_ip *hdrip = HDR_IP(p);
    hdr_cmn *hdrc = HDR_CMN(p);
    
    // add new outer route entry to packet
    st = add_outer_route(p, zroute[numentries - 1] );
  	   
    //encapsulate upper layer info
    hdrz->enc_daddr_ = hdrip->daddr() ;
    hdrz->enc_dport_ = hdrip->dport() ;
    hdrz->enc_ptype_ =  hdrc->ptype();
    // send to next hop
    hdrc->direction() = hdr_cmn::DOWN; // this is default, but just in case
    hdrc->ptype() = PT_ZRP;
    //hdrc->next_hop() = nto[0];
    hdrc->addr_type_ = NS_AF_NONE;
    hdrc->size() = IP_HDR_LEN ;  //  set default packet size
    hdrip->ttl() = 100;
    //	hdrip->daddr() = find_next_hop ;
    hdrip->dport() = ROUTER_PORT;
    hdrz->zrptype_ = IARP_DATA;
    hdrz->numentries_ = numentries ;
    hdrz->forwarded_ = 0;
    hdrz->originator_ = myaddr_;
    hdrz->pktsent_ = now;
    
    hdrz->zrptype_ = IARP_DATA;
    hdrc->direction() = hdr_cmn::DOWN;
    
    junk = find_next_hop(p);
    
    printf("| Sending data packet to next hop %d )\n",junk);
    send_next_hop(p);
  }

}

//=======================================================================
// ZRP:
// Receives incoming packet, determines if it is a ZRP packet or not
// If it is, it is processed by ZRP (IERP) at recvZRP.
// If not, that means the packet is coming from the upper layer, and the
// packet needs to be routed using route_pkt.
// Protocols: IERP and IARP
//=======================================================================
void
ZRPAgent::recv(Packet * p, Handler *)  {
  hdr_ip *hdrip = HDR_IP(p);
  hdr_cmn *hdrc = HDR_CMN(p);
  hdr_zrp *hdrz = HDR_ZRP(p);
  int src = Address::instance().get_nodeaddr(hdrip->saddr());
  int dst = hdrc->next_hop();
  int jem;
  Time now = Scheduler::instance().clock(); // get the time

  rx_++; // just received a new packet

  // check if we are in suspend mode
  if (suspend_flag_ == TRUE) {
        zdrop(p, DROP_RTR_IARP);
	return;
  }
  
  if (hdrc->ptype() == PT_ZRP) {
    jem =  hdrip->ttl();
    hdrip->ttl() -= 1;
    assert(jem == (hdrip->ttl() + 1) );
    if (hdrip->ttl() < 0) {
      zdrop(p, DROP_RTR_TTL);
      return;
    }

    // it is a proper ZRP packet, let ZRP process it
    recvZRP(p);
    return;
  }

  // if other type
  if(src == myaddr_ && hdrc->num_forwards() == 0) { 
    // A packet from higher layer
    hdrc->size() += IP_HDR_LEN;     //  Add the IP Header size
    //   hdrip->ttl_ = IP_DEF_TTL;
    hdrip->ttl() = radius_ ;
  } else if (src == myaddr_) { // rcving a pkt I sent, prob a routing loop
    zdrop(p, DROP_RTR_ROUTE_LOOP);
    return;
  } else {
    
    // forwarding a non-ZRP packet from another node
    // Check the TTL.  If it is zero, then discard.
    if(--hdrip->ttl() == 0) {
      zdrop(p, DROP_RTR_TTL);
      return;
    }

    // WHAT do I do with non-ZRP packets rcvd from another node?
    // just route_pkt it like any other? then this else clause is superfluous
  }

  printf("\n_%2d_ [%6.3f] | Got non-ZRP packet type %d from upper layer "
	 "seq no. %d (daddr=%d dport=%d) ",
	 // "(%2d,PT_ZRP=%2d,PT_TCP=%d) ",
	 myaddr_, now, hdrip->daddr(),
	 seq_, hdrip->daddr(), hdrip->dport() );
  
    print_tables();
  printf("\n");

  // This packet is not a ZRP packet, it needs to be routed.
  route_pkt(p, hdrip->daddr() );
}

//=======================================================================
// IERP:
// Process received ZRP type packet.
// Protocols: IERP, IERP calling IARP, IARP, NDP, NDP notifying IARP
// IARP calling IERP 
//=======================================================================
void
ZRPAgent::recvZRP(Packet* p)
{
  hdr_ip *hdrip = HDR_IP(p);
  hdr_cmn *hdrc = HDR_CMN(p);
  hdr_zrp *hdrz = HDR_ZRP(p);
  int tmp[MAX_ROUTE_LENGTH];
  int src = Address::instance().get_nodeaddr(hdrip->saddr());
  int dst = hdrc->next_hop();
  int st;
  int ne,ma;
  int aaa,bbb;
  int cntr,qqqid;
  link_struct templink;
  nsaddr_t *nodeptr;
  nsaddr_t *nptr;
  nsaddr_t *mptr;
  nsaddr_t* ptr;
  nsaddr_t prev_hop;    
  nsaddr_t nextbc,isrc;
  int flag,ii,found;
  int seq_match;
  char *walk;
  link_struct* joe;
  link_struct* currlink;
  Packet *pnew;
  Time now = Scheduler::instance().clock(); // get the time
  
  Scheduler & s = Scheduler::instance();  // Useful to send (Schedule) packets

  // if I get my own transmission (excluding ierp_replies)
  if (hdrip->saddr() == myaddr_ && hdrz->ierpsource_ != myaddr_) {
    zdrop(p,DROP_RTR_HIYA);
    return;
  }

  //assert we're talking from network layer(rtagent) to network layer(rtagent)
  assert(hdrip->sport() == RT_PORT);   assert(hdrip->dport() == RT_PORT);
  assert(hdrc->ptype() == PT_ZRP);
  
  switch (hdrz->zrptype_)
    {

    case NDP_BEACON: // getting a beacon, send ack

      // re-use packet to create beacon ack, no need to drop 
      hdrz->zrptype_ = NDP_BEACON_ACK;
      hdrc->next_hop_ = hdrz->originator_; // send directly to originator
      hdrc->direction() = hdr_cmn::DOWN; // this is default, but just in case
      hdrip->ttl() = 1;
      hdrip->saddr() = myaddr_;

      pkt_send(p,hdrz->originator_);  // send ack
      
      printf("\n_%2d_ [%6.6f] | Node %d received a beacon from Node %d "
	     "(seq no. %d) | Node %d sent ack to Node %d (seq no. %d). ",
	     myaddr_, (float)now, myaddr_,hdrz->originator_ , hdrz->seq_ ,
	     myaddr_, hdrz->originator_, hdrz->seq_);

      print_tables();
      
      printf("\n");
      break;
      
    case NDP_BEACON_ACK: // getting an ack, update neighbor table and
      // send update, and update link state table.

      printf("\n_%2d_ [%6.6f] "
	     "| Node %d received an ack (seq no. %d) from Node %d. ",
	     myaddr_, now, myaddr_, hdrz->seq_, hdrip->saddr());
      
      st = FALSE; // assume no change in N table

      // check if I am getting an ack for a beacon I sent
      if (hdrz->originator_ == myaddr_) {

	printf("");
	
	// add, or update if already in table
	st = neighbor_add(hdrip->saddr() );
	
      } else {
	zdrop(p,DROP_RTR_IARP);  
	printf("| Node %d dropped an ack (seq no. %d) originating from a"
	       " different Node %d", myaddr_, hdrz->seq_, hdrz->originator_ );
	print_tables();
	printf("\n");
	return;
      }
      aaa = st;
      bbb = hdrip->saddr();

      if (st) { // @@if (st)  change in NDP table, notify IARP
	
	// seq=0 means update from NDP  
	st = lstable.update(hdrip->saddr(),myaddr_,TRUE,0,&seq_match);
	aaa= st;

	if (st) {
	  // re-compute if there is a change in link state table
	  //	  rtable.compute_routes();
	  rtable.compute_routes(myaddr_,radius_);
	}
      
	// always send update if neighbor has been added
	
	// send out immediate update (event-driven)
	pnew = pkt_create(IARP_UPDATE, IP_BROADCAST, radius_*2-1);
	
	hdr_zrp *hdrz_new = HDR_ZRP(pnew);
	
	pkt_create_link_data_space(pnew,MAX_LINKIE);
	pkt_add_link(pnew,myaddr_, hdrip->saddr(), TRUE);
	
	pkt_broadcast(pnew);
	
	printf("| Node %d sent update (seq no. %d) about new "
	       "neighbor Node %d. ",myaddr_, hdrz_new->seq_,hdrip->saddr());
	
      }

      print_tables();
      printf("\n"); 

      zdrop(p,DROP_RTR_TTL);  // packet expired  
      break;
      
    case IARP_UPDATE:  // received update, forward if appropriate.

      char msg[100] ;
      
      sprintf(msg,"");

      if (hdrz->forwarded_ == 1 ) {
	sprintf(msg,"forwarded");
      }
      
      printf("\n_%2d_ [%6.6f] | Node %d received %s update (seq no. %d) "
	     "sent from Node %d originating from Node %d (contains: ",
	     myaddr_, (float)now, myaddr_, msg, hdrz->seq_, hdrip->saddr(),
	     hdrz->originator_); 

      for (int i=0; i<hdrz->numentries_; i++) {

	pkt_read_update(p, &templink, i);
	if (templink.isup_ == TRUE) 
	  printf("%d=%d ",templink.src_,templink.dest_ );
	else
	  printf("%d#%d ",templink.src_,templink.dest_ );
      }
      
      printf("). ");
      
      flag = FALSE; // assume no updates to our table
      // go through list of updates in pkt
      for (int i=0; i<hdrz->numentries_; i++) {

	// load link[i] from update
	pkt_read_update(p, &templink, i);
	
	// update link state table
	st = lstable.update(templink.src_,templink.dest_,templink.isup_,
			    hdrz->seq_,&seq_match);
	
	// if change in link state table, recompute routes
	if (st) {
	  flag = TRUE; // link table has been changed
	  //	  rtable.compute_routes();
	  rtable.compute_routes(myaddr_,radius_);
	}
	
	if ( seq_match == TRUE) { // update was received before
	  zdrop(p,DROP_RTR_IARP);  
	  printf("| Node %d dropped packet because seq id is same or older as "
		 "id in table. ", myaddr_);
	  // return;
	  goto EOFF;
	}

      }
      
      // check ttl
      if ( (hdrip->ttl() < 1) ) {  // TTL expired, don't forward
	printf("| Node %d dropped packet due to TTL. ",myaddr_);
     	zdrop(p,DROP_RTR_TTL);
	goto EOFF;
      }

      // let's forward by broadcast
      // re-use packet, no need to drop 
      printf("| Node %d forwarded update (seq no. %d) "
	     "sent from Node %d originating from Node %d (contains: ",
	     myaddr_, hdrz->seq_, hdrip->saddr(), hdrz->originator_); 
      for (int i=0; i<hdrz->numentries_; i++) {
	pkt_read_update(p, &templink, i);
	if (templink.isup_ == TRUE) 
	  printf("%d=%d ",templink.src_,templink.dest_ );
	else
	  printf("%d#%d ",templink.src_,templink.dest_ );
      }
      
      printf("). ttl=%d",hdrip->ttl());
      hdrc->direction() = hdr_cmn::DOWN;
      hdrz->forwarded_ = 1;	  
      
      pkt_send(p,IP_BROADCAST);
      
    EOFF:

      print_tables();
      
      printf("\n");
      
      // pgi - this was changed for the Haas demo in June! Do I need this?
      // quenching IARP updates
      // check if either lnksrc or lnkdest is me, don't forward, drop
      // this is my neighborhood.
      //      if ((hdrz->lnksrc_ == myaddr_) || (hdrz->lnkdest_ == myaddr_)){
      //drop(p,DROP_RTR_IARP);  
      //return;
      //}
      return;
      
      break;
      
    case IARP_DATA: // got a data packet, forward if I am relay,
      // or send up if I am destination.

      nodeptr = hdrz->route_;  // ptr to route list 
            
      printf("\n_%2d_ [%6.6f] | Got IARP_Data packet orig=%d dest=%d ",myaddr_,
	     now, hdrz->originator_,nodeptr[hdrz->numentries_ - 1]);

      printf("(");
      for (ii=0; ii<MAX_IERP_CACHE ; ii++) 
	if (ierpcache[ii] != NULL) 
	  printf("%d.%d.%d ",ii,HDR_ZRP(ierpcache[ii]->pkt_)->enc_daddr_,
		HDR_ZRP(ierpcache[ii]->pkt_)->enc_daddr_ );
	
      // if pkt has arrived at dest (me)
      if (nodeptr[hdrz->numentries_ - 1] == myaddr_) { 

	printf(" >>> we are at destination "
	       "(delay=%3.2f ms seq=%d daddr=%d dport=%d ptype=%d) ",
	       1000* ((float)now - (float)hdrz->pktsent_), hdrz->seq_,
	       hdrz->enc_daddr_, hdrz->enc_dport_, hdrz->enc_ptype_);

	// copy ecnapsulated data back to this packet
	hdrip->daddr() = hdrz->enc_daddr_; 
	hdrip->dport() = hdrz->enc_dport_;
	hdrc->ptype() = hdrz->enc_ptype_;
	hdrc->next_hop() = myaddr_;
	hdrc->addr_type_ = NS_AF_NONE;
	hdrc->size() = IP_HDR_LEN ;  //  set default packet size
	hdrip->ttl() = 1;  
	hdrip->daddr() = myaddr_;
	hdrc->direction() = hdr_cmn::UP; // and is sent up

	// unicast
	pkt_send(p,myaddr_);
	
      } else {

	// forward onto next hop on list
	int nexthop = find_next_hop(p);
	if (nexthop == myaddr_) {
	  // no next hop error
	}
	printf(" >>> forwarding to next hop %d ",nexthop);
	hdrc->next_hop() = nexthop; 
	
	hdrc->direction() = hdr_cmn::DOWN;
	send_next_hop(p);
      } 
      
      print_tables();
      printf("\n"); 

      break;

    case IERP_REPLY: // got a reply, process as a relay or destination.
      
      ne = hdrz->numentries_;
      ma = myaddr_;
      
      printf("\n_%2d_ [%6.6f] | Got an ierp_reply, ",
	     myaddr_,now,ne,hdrz->numentries_,ma,myaddr_);

      // if I am source, wake up IARP
      if (hdrz->ierpsource_ == ma) {
	printf("I am originator. \n");
        // wake up IARP, pass packet to it
        ierp_notify_iarp(p);
	zdrop(p,DROP_RTR_IERP); // finished with reply packet
        return;

      } else { // if I am not source
	// I am a relay node
	printf("forwarding route ");
        ptr = hdrz->route_;
	printf("[%d ",ptr[0] );
	// find prev hop, forward reply to it
	for (int i = 1; i<ne; i++) {
	  printf("%d ",ptr[i] );
	  if (ptr[i] == ma) {
	    prev_hop = ptr[i-1]; printf("<");
	    
	  }
	}
	printf("]");
	
      	printf(" to %d. \n",find_prev_hop(p));
	
	hdrc->direction() = hdr_cmn::DOWN; // send back down to prev node
	hdrip->ttl() = 3;  
	hdrc->next_hop() = find_prev_hop(p);
	send_prev_hop(p);
      }
      break;

    case IERP_REQUEST: // outgoing request. QD,ET as a relay or bordercaster.
      printf("\n_%2d_ [%6.6f] | Got an ierp_request, ",myaddr_,now);
      printf("origin of request is %d, queryid is %d. ",
	     hdrz->ierpsource_,hdrz->qid_);
      
      printf("Last bordercaster was %d. Last hop was %d.",
	     hdrz->lastbordercaster_,find_prev_hop(p) );
      ne = hdrz->numentries_;
      nextbc = hdrz->route_[ne-1];
      qqqid = hdrz->qid_;
      isrc = hdrz->ierpsource_;
      
      ptr = hdrz->route_;

      // if dest is in my zone, originate reply and send back route 
      if (rtable.route_exists(hdrz->ierpdest_)) { 
	
	printf("\n\t| ierpdest (%d) is in my zone, sending IERP Reply "
	       "with accumulated route", hdrz->ierpdest_);

	// where am I on route list? store in cntr
	cntr=999;
	for (int i=0; i<hdrz->numentries_; i++) {
	  if (ptr[i] == myaddr_ ) {
	    cntr=i+1;
	  }
	}
	assert(cntr != 999); // I have to be on list!
	// clip route after me 
	//memcp data to tmp
	bcopy(hdrz->route_,tmp,cntr*sizeof(nsaddr_t));
	// allocate a possibly smaller space, enough for accum route up to me
	pkt_create_route_data_space(p,100); //cntr+1);
	//memcp tmp back to data
	bcopy(tmp,hdrz->route_,cntr*sizeof(nsaddr_t));
	hdrz->numentries_ = cntr;
	add_local_route(p,hdrz->ierpdest_);

	//reuse packet, change to ierp reply
	hdrz->zrptype_ = IERP_REPLY;
	hdrc->direction() = hdr_cmn::DOWN; // send back down protocol stack
	send_prev_hop(p);
	printf("\n");
	return;
      } 
      
      if (ptr[hdrz->numentries_-1] == myaddr_) { // if last entry is me
	// I am a periph node
	printf("\n\t| I am a peripheral node. My peripherals are [");
	for (rtable_node *mptr = rtable.periphnodes_; mptr != NULL;
	     mptr=mptr->next_) { 
	  printf("%d ",mptr->id_);
	}
	printf("].");
	 
	// QD - cover last bordercaster's zone
	found = query_detect1(hdrz->qid_, hdrz->ierpsource_,
			      hdrz->lastbordercaster_, radius_);
	
	// unicast to each peripheral node
	for (rtable_node *mptr = rtable.periphnodes_; mptr != NULL;
	     mptr=mptr->next_) {

	  // check if node is covered, otherwise bordercast 
	  if (node_is_covered(mptr->id_, hdrz->qid_, hdrz->ierpsource_)) {
	    // Early Termination  
	    printf("\n\t| ET - Query detected peripheral node %d is in zone"
		   " of previous bordercaster %d or is just on covered list",
		   mptr->id_, hdrz->lastbordercaster_);
	  } else {

	    Packet *pnext = pkt_create(IERP_REQUEST, IP_BROADCAST, 1);
	    // parameters don't matter, will be overwritten by pkt_copy    
	    pkt_copy(p,pnext);
	    // add myself as first route entry 
	    
	    add_local_route(pnext,mptr->id_); // add rest
	    
	    hdr_cmn *hdrcnext = HDR_CMN(pnext);
	    hdr_zrp *hdrznext = HDR_ZRP(pnext);
 	    hdrcnext->direction() = hdr_cmn::DOWN; // send back down 
	    hdrznext->lastbordercaster_ = myaddr_;
	    printf("\n\t| Sending ierp request to next bordercaster %d, "
		   "next hop is %d. ", mptr->id_, find_next_hop(pnext));
	    printf("Route list [");
	    for (int i=0; i<hdrznext->numentries_; i++)
	      printf("%d ",hdrznext->route_[i]);
	    printf("] ");
	    send_next_hop(pnext);
	    
	  }
	} // for mptr
	zdrop(p,DROP_RTR_IERP);

	// QD - cover my zone
	query_detect1(qqqid,isrc,myaddr_, radius_);
	
      } else { // I am a "relay"
	printf("| I am a relay node. ");
	printf("Route list [");
	for (int i=0; i<ne; i++) printf("%d ",hdrz->route_[i]);
	printf("]");

	hdr_zrp *hdrz = HDR_ZRP(p);

	// send if next bordercaster is not covered
	if (node_is_covered(nextbc, hdrz->qid_, hdrz->ierpsource_)){
	  printf("\n\t| ET - Query detected next bordercaster %d is in "
		 "covered list. ", nextbc);
	  zdrop(p,DROP_RTR_IERP);
	} else {  
	  hdrc->direction() = hdr_cmn::DOWN; 
	  printf("| Sending to next hop %d, next bordercaster is %d.",
		 find_next_hop(p), nextbc);
	  send_next_hop(p);
	}
	
	// QD - mark last bordercaster's zone's inner nodes as covered
	found = query_detect1(hdrz->qid_, hdrz->ierpsource_,
			      hdrz->lastbordercaster_, radius_-1);
	
	// add next bordercaster to covered list
	// check node against list in query entry 
	flag = FALSE;
	for (rtable_node *ptr=queries_[found]->next_;
	     ptr!=NULL; ptr=ptr->next_) {
	  // if node in query entry  == next bordercaster
	  if (ptr->id_ == nextbc) {
	    flag=TRUE; //=found, don't need to add again
	    break;
	  } 
	}
	if (!flag) { // if not in list, add at head
	  rtable_node *tmp;
	  tmp = new rtable_node; 
	  tmp->id_ = nextbc;
	  tmp->next_ = queries_[found]->next_;
	  queries_[found]->next_ = tmp;
	  printf("\n\t| QD - Next bordercaster [%d] added to covered list.",
		 (int)tmp->id_ );
	} else {
	  printf("\n\t| QD - Next bordercaster [%d] already added to covered "
		 "list.", nextbc);
	}
      }


      printf("\n\t| Covered list for query=%d origin=%d [",
	     qqqid,isrc);
      for (rtable_node *p=queries_[found]->next_; p!=NULL; p=p->next_) {
	printf("%d ",p->id_);
      }
            
      printf("]\n");

      break;

    default:
      // error, unknown zrptype, drop 
      // debug - printf("Uknown ZRPTYPE !\n");
      fprintf(stderr, "Invalid ZRP type (%x)\n", hdrz->zrptype_);
      exit(1);
    }
}
//=======================================================================
// IARP:
// Called by IARP to update list of outer routes for any changes to
// local routes.
//=======================================================================
void ZRPAgent::IARP_update_outer_route(int route_index) {
  rtable_node *nptr;
  rtable_node *mptr;
  rtable_node *newnode;
  rtable_node *newhead;
  rtable_node *deleteme;
  int index;

  // if entry is empty or route list is empty (latter is unlikely)
  if (rtable.outer_route[route_index] == NULL ||
      rtable.outer_route[route_index]->next_ == NULL)
    return;
    
  // finds all the nodes in outer route that exist in current node's zone
  // and returns pointer to the furthest in hops from current node (should be
  // a peripheral), and guarantees it is the last inner node before end of outer route list
  for ( nptr=rtable.outer_route[route_index]->next_; nptr != NULL;
	nptr=nptr->next_) {
    index = rtable.node_exists(nptr->id_ );
    
    if (index != -1 ) {
      mptr = nptr; // found peripheral
    } 
    
  } // end for

  if (index == -1)
    return; // nothing to do, in future return error so we can delete route
  // outer route must contain an inner route as a subset!

  // mark where we are going to start deleting on old clipped list
  deleteme = rtable.outer_route[route_index]->next_;

  // start creating new local route and pre-pending to where mptr left off
  // list looks like this:                 
  // rtable.outer_route[route_index]->next_->O -> -> -> mptr-> last
  // inner node-> -> -> dest ->NULL 
  newhead = new rtable_node;
  newhead->id_ = rtable.route[index]->id_;
  newhead->next_ = mptr->next_;

  //for each route entry list node, copy to newnode and insert newnode
  // at head of newhead
  for (nptr=rtable.route[index]->next_; nptr != NULL; nptr=nptr->next_) {
    newnode = new rtable_node;
    newnode->id_ = nptr->id_;
    newnode->next_ = newhead;
    newhead = newnode;
  }

  // attach newhead to outer route entry
  rtable.outer_route[route_index]->next_ = newhead;

  //delete old inner route
  // cut at last inner route node
  mptr->next_ = NULL;
  for (nptr=deleteme; nptr != NULL; ) {
    nptr=nptr->next_;
    delete deleteme;
    deleteme = nptr;
  }
}

//=================================================================
// IERP:
// Call by IERP to start a request from source node.
// Protocols: IERP, get local route from IARP
//=================================================================
void ZRPAgent::originate_request(nsaddr_t final, int qid) {
  rtable_node* ptr;
  nsaddr_t *nptr;
  int ind;
  Scheduler & s = Scheduler::instance();  // Useful to send (Schedule) packets  
  Packet* p;

  printf("\n_%2d_ | Bordercast to ", myaddr_ );  
  // unicast to each peripheral node
  for (ptr = rtable.periphnodes_; ptr != NULL; ptr=ptr->next_) {
    printf("[%d - route ",ptr->id_);
    p = pkt_create(IERP_REQUEST, IP_BROADCAST, MAX_ROUTE_LENGTH*2);    
    hdr_zrp *hdrz = HDR_ZRP(p);
    hdr_cmn *hdrc = HDR_CMN(p);    
    hdr_ip *hdrip = HDR_IP(p);
    
    hdrz->lastbordercaster_ = myaddr_;
    hdrz->ierpsource_ = myaddr_;
    hdrz->ierpdest_ = final;
    hdrz->qid_ = qid;
    pkt_create_route_data_space(p,1);
    
    // add myself in source route list 
    pkt_add_node(p, myaddr_, 0);
    hdrz->numentries_ = 1;
    hdrz->routeindex_ = 0;
    
    // add the rest of the route to the peripheral node
    add_local_route(p,ptr->id_);

    nptr = hdrz->route_;
    for (int i=0; i<hdrz->numentries_ ; i++) {
      printf("%d ",nptr[i]);
    }
    printf("(nexthop=%d) ]",find_next_hop(p) );
    hdrc->direction() = hdr_cmn::DOWN;

    // since we are in request mode, we move route index forward
    hdrz->routeindex_++;
    ind=hdrz->routeindex_;
    // then send it
    pkt_send(p,hdrz->route_[ind]);  
  }
  
  // pseudo-code:
  // for each periph node
  // create packet
  // add to hdrzrp ORIGINATOR, REQUESTED, NEXTPERIPH, LASTPERIPH
  // add src route to that node, attach to pkt
  // saddr() = me
  // daddr() = periph node
  // nexthop = next on src lst
  // send 
}

//=================================================================
// IERP:
// Route Packet, first check if there is a local route. If so, add
// route to packet and send.
// Otherwise check if there is an outer route. If so, add and send.
// Otherwise, originat request.
// Protocols: IERP, IERP calls IARP
//=================================================================
void ZRPAgent::route_pkt(Packet* p, nsaddr_t daddr) {
  hdr_cmn *hdrc = HDR_CMN(p);
  hdr_ip *hdrip = HDR_IP(p);
  hdr_zrp *hdrz = HDR_ZRP(p);
  nsaddr_t *nexthop;
  int st;
  int ierpd;
  Time now = Scheduler::instance().clock(); // get the time
  
  hdrz->routeindex_=0;
  hdrz->numentries_ =0;
  
  st = add_local_route(p,daddr);
  if (!st) {
    st = add_outer_route(p,daddr); //printf("the route saved is now:");
    nsaddr_t *rrr = hdrz->route_;
  }
  
  if (st) { // if a local or outer route exists, it was added, start sending...
    //send to first addr on list
    //nexthop = (nsaddr_t *)p->accessdata();
    nexthop = hdrz->route_;

    // this packet will now be encapsulated into an IARP_DATA packet
    
    // save upper layer info in encapsulated area
    hdrz->enc_daddr_ = hdrip->daddr() ;
    hdrz->enc_dport_ = hdrip->dport() ;
    hdrz->enc_ptype_ =  hdrc->ptype();
         
    hdrc->direction() = hdr_cmn::DOWN; // this is default, but just in case
    hdrc->ptype() = PT_ZRP;
    hdrc->next_hop() = nexthop[0];
    hdrc->addr_type_ = NS_AF_NONE;
    hdrc->size() = IP_HDR_LEN ;  //  set default packet size
    hdrip->ttl() = IERP_TTL;  
    hdrip->daddr() = nexthop[0] ;
    hdrip->dport() = ROUTER_PORT;
    hdrz->zrptype_ = IARP_DATA;
    hdrz->originator_ = myaddr_;
    hdrz->pktsent_ = Scheduler::instance().clock(); // get the time
    hdrz->seq_ = seq_ ;
    inc_seq();
    send_next_hop(p);
    return;
  }
  
  // no local or cached route, call IERP   
  // push onto ierp request queue
  int flag = FALSE;
  ierpd = hdrz->ierpdest_;
  
  for (int i=0; i<MAX_IERP_CACHE; i++) {
    if (ierpcache[i] == NULL) {
      flag = TRUE;
      st = i;
    } else if (HDR_ZRP(ierpcache[i]->pkt_)->ierpdest_ == ierpd) {
      // ierp request pending
      // drop packet
      printf("\n_%2d_ [%6.6f] | A request for destination already in "
	     "ierpcache, dropping packet\n",myaddr_,now);
      zdrop(p,DROP_RTR_IERP);
      // or add buffer data structure
      return;
      
    }
    
  }
  assert(flag == TRUE); // increase MAX_IERP_CACHE otherwise
  if (flag == FALSE) { // don't like assertion? comment out and keep this 
    zdrop(p,DROP_RTR_HIYA);
    return;
  }
  
  // new entry for ierp request cache
  ierpcache[st] = new IERPCacheEntry;
  ierpcache[st]->qid_ = qid_;
  ierpcache[st]->expiry_ = Scheduler::instance().clock() +
    IERP_REQUEST_TIMEOUT;
  ierpcache[st]->pkt_ = p;
  originate_request(daddr, qid_ ) ;
  qid_++;
  printf("\n\t| New ierpcache entry: qid=%d expiry=%3.3f (daddr=%d)\n",
	 ierpcache[st]->qid_,
	 ierpcache[st]->expiry_,daddr);
  
}

//=================================================================
// IARP:
// Add route to packet if local route to daddr exists. Return true if so.
// Otherwise return false.
//=================================================================
int ZRPAgent::add_local_route(Packet* p, nsaddr_t daddr) {
  rtable_node *nptr;
  int totalhops; int cntr;
  nsaddr_t *ptr;
  hdr_zrp *hdrz = HDR_ZRP(p);
  int tmp[MAX_ROUTE_LENGTH];
    
  // assuming there could be node entries (hdrz->numentries_)
  // already in pkt
  // should work even if hdrz->numentries_ = 0
  
  for (int i=0; i< MAX_NODES_PER_ZONE; i++) {

    // if not found return FALSE
    if (rtable.route[i] == NULL) {
      return FALSE; // end of table, not found
    } else { // still looking
      if (rtable.route[i]->id_ == daddr) { // if found
	totalhops = hdrz->numentries_ + rtable.route[i]->numhops_ ;

	//memcp data to tmp
	bcopy(hdrz->route_,tmp,hdrz->numentries_*sizeof(nsaddr_t));

	// allocate a BIGGER space, enough for prev entries + new entries
	pkt_create_route_data_space(p,totalhops);

	//memcp tmp back to data
	bcopy(tmp,hdrz->route_,hdrz->numentries_*sizeof(nsaddr_t));
	//
	cntr = totalhops-1;

	// copy route list to data portion of packet (reverse order)
	for (nptr = rtable.route[i]; nptr->id_ != myaddr_;  nptr=nptr->next_) {
	  pkt_add_node(p, nptr->id_, cntr ) ;
	  cntr--;
	} // end for nptr
	
	hdrz->numentries_ = totalhops;
	return TRUE;
      } // end if (rtable.route[i]->id_ == daddr)
      
    }  //end if (rtable.route[i] == NULL) 
  
  // find daddr in lookup
  // else
  // create data area of size (num hops is stored in table)
  // step through table, adding each node to data area
  // 
  } // end for i
}

//===========================================================
// NDP:
// Add neigbor with address "addr" to NDP table if it is not
// already there. If already there, return false. Otherwise true.
//===========================================================
int ZRPAgent::neighbor_add(nsaddr_t neighbor_addr) {
  neighbor_struct *ns;
  Time now = Scheduler::instance().clock(); // get the time

  if (neighbors_ == NULL) {

    num_neighbors_ ++;
    
    neighbors_ = new neighbor_struct;
    neighbors_->addr_ = neighbor_addr;
    neighbors_->expiry_ = now+neighbor_timeout_;
    neighbors_->lastack_ = now;
    neighbors_->next_ = NULL;

    printf("| Node %d added new neighbor Node %d, will expire at %6.6f sec, "
	 "lastack timer will expire at %6.6f sec.",
	   myaddr_, neighbor_addr , neighbors_->expiry_,
	   neighbors_->lastack_ + neighbor_ack_timeout_);
        return TRUE;
  }

  for (ns=neighbors_; ns != NULL; ns=ns->next_ ){
    if (ns->addr_ == neighbor_addr){
      // update neighbor timeout

      printf("| Node %d updated neighbor table, changed neighbor Node %d "
	     "expiry from %6.6f to %6.6f sec and lastack timer expiry "
	     "from %6.6f to %6.6f. ",
	     myaddr_, neighbor_addr,
	     (float)neighbors_->expiry_, (float)now + neighbor_timeout_,
	     ns->lastack_, now + neighbor_ack_timeout_ );

      ns->expiry_ = now+neighbor_timeout_;
      ns->lastack_ = now;
      
      return FALSE; // no change, we have that node in our table
    }
  }

  // if we end up here, we have at least one neighbor on list but no match
  // so add our new neighbor to top of list
  ns = new neighbor_struct;
  ns->addr_ = neighbor_addr;
  ns->expiry_ = now+neighbor_timeout_;
  ns->lastack_ = now;
  ns->next_ = neighbors_;
  neighbors_ = ns;
  num_neighbors_ ++;
  printf("| Node %d added new neighbor Node %d, entry will expire at "
	 "%6.6f sec, lastack timer will expire at %6.6f sec.",
	 myaddr_,neighbor_addr, neighbors_->expiry_,
	 neighbors_->lastack_ + neighbor_ack_timeout_);
  	   
  return TRUE;
  
}

//===================================================================
// BRP:
// Mark "node" as covered for given query (qid,origin).
//===================================================================
int ZRPAgent::node_is_covered(nsaddr_t node, int queryid, nsaddr_t originid) {
  int flag = FALSE;
  rtable_node *ptr;
  Time now = Scheduler::instance().clock(); // get the time
  int found = 999;

  for (int i=0; i<MAX_QUERY_DETECT_TABLE_SIZE; i++) {
    if (!flag && queries_[i] != NULL && queries_[i]->originid_ == originid &&
	queries_[i]->qid_ == queryid)  {
      //  refresh expiry unconditionally
      queries_[i]->expiry_ = now +  QUERY_TABLE_EXPIRATION;
      found = i;
      for (rtable_node *ptr=queries_[i]->next_; ptr!=NULL; ptr=ptr->next_) {
	if (ptr->id_ == node) {
	  flag=TRUE;
	  break;
	}
      }
      break;
    }
  }
  
  // return FALSE if we do not find query entry at all
  // return TRUE only if we find query entry AND the node is in its list
  // all else is FALSE!!
  return(flag);
}

//===================================================================
// BRP:
// Query detect given (qid,origin). Will add nodes of covered area (nodes
// that are "radius" hops away from "lastbordercaster") to a cached
// query detect entry. If this query has not been received before, will
// create a new entry and add covered nodes to entry.
// Returns TRUE if query was received before, else FALSE.
//===================================================================
int ZRPAgent::query_detect1(int queryid, nsaddr_t originid,
                             nsaddr_t lastbordercaster, int radius) {
  RoutingTable prevtable(this);
  int flag = FALSE;
  int found;
  Time now = Scheduler::instance().clock(); // get the time
  int iii;
  
  // 1. if query exists in our cache, =queries[found] 
  // 2. if not exist, find an empty slot, queries[found],
  //    add new entry at queries[found]
  // 3. create route table for prev bordercaster
  // 4. add nodes in table to queries[found], ie
  //    for each node in table:
  //       if node_is_covered is false (node is NOT in queries),
  //          add to queries[found]
  // 5.  look for query id in queries_[] 

  // 1. if exist in queries_[], queries[found] is the one
  for (int i=0; i<MAX_QUERY_DETECT_TABLE_SIZE; i++) {
    if (!flag && queries_[i] != NULL && queries_[i]->originid_ == originid &&
        queries_[i]->qid_ == queryid)  {
      flag = TRUE;
      found = i;

      // refresh expiration
      if (now > queries_[i]->expiry_) {
        queries_[i]->expiry_ = now +  QUERY_TABLE_EXPIRATION;
      }
      break;
    }
  }

  // 2. if not exist, find an empty slot, queries[found],
  //    add new entry at queries[found]
  if (!flag) { // if no entry already, create one
    for (int i=0; i<MAX_QUERY_DETECT_TABLE_SIZE; i++) {
      if (!flag && queries_[i] == NULL) {
        flag = TRUE;
        found = i;
        queries_[i] = new QueryDetectEntry;
        queries_[i]->originid_ = originid;
        queries_[i]->qid_ = queryid;
        queries_[i]->expiry_ = now +QUERY_TABLE_EXPIRATION;
	queries_[i]->next_ = NULL;
	break;
      }
    }
  }
  
  // 3. create+compute route table for prev bordercaster
  prevtable.my_address_ = lastbordercaster; //  get route table for last bc
  prevtable.linkstatetable = &lstable;

  for (int i=0; (i< MAX_NODES_PER_ZONE); i++) {
    prevtable.route[i] = NULL;
  }
  prevtable.periphnodes_=NULL;
  prevtable.agent_ = this;
  prevtable.compute_routes(lastbordercaster, radius);

  // 4. add nodes in table to queries[found], ie
  //    for each node in table:
  //       if node_is_covered is false (node is NOT in queries),
  //          add to queries[found]
  printf("\n\t| QD - Calculated Route Table of bordercaster %d: ",
	 lastbordercaster);
  for (int i=1; prevtable.route[i] != NULL ; i++) {
    printf("[");
    for (rtable_node *j=prevtable.route[i]; j != NULL; j=j->next_  ) {
      printf("%d ",j->id_);
    }
    printf("] ");
  }

  printf("\n\t| QD - added [");
  rtable_node *tmp;
  for (iii=0; prevtable.route[iii] != NULL &&
	 prevtable.route[iii]->numhops_<=radius ; iii++) {
    flag = FALSE; // =not found
    
    // check node against list in query entry 
    for (rtable_node *ptr=queries_[found]->next_; (!flag) && (ptr != NULL);
	 ptr=ptr->next_) {
      if (ptr->id_ == prevtable.route[iii]->id_) {
	flag=TRUE; //=found
	printf("");
      }
    }

    // debug only
    if (flag) { // just to illustrate that this flag tells us if
      //the query was in our cache or not
      //printf("FOUND");
    } else {
      //printf("NOTFOUND");
    }
    if (!flag) { // if not in list, add at head
      // want to add to a separate list, then join afterwards. more efficient
      tmp = new rtable_node; 
      tmp->id_ = prevtable.route[iii]->id_;
      tmp->next_ = queries_[found]->next_;
      queries_[found]->next_ = tmp;
      printf("%d ", queries_[found]->next_->id_ );
    } 
  }
  printf("] to covered list. ");
  return(found) ;
}

zrp.h

#ifndef _zrp_h_
#define _zrp_h_

#include <config.h>
#include <assert.h>
#include <agent.h>
#include <packet.h>
#include <ip.h>
#include <delay.h>
#include <scheduler.h>
#include <queue.h>
#include <trace.h>
#include <arp.h>
#include <ll.h>
#include <mac.h>
#include <priqueue.h>
#include <delay.h>
#include "zrp_table.h"

#if defined(WIN32) && !defined(snprintf)
#define snprintf _snprintf
#endif /* WIN32 && !snprintf */

#define ROUTER_PORT      0xff
#define FOUND 1
#define LOST 0
#define TRUE 1
#define FALSE 0
#define NULL 0

#define MAX_OUTBOUND_PENDING 20 // max queue for pkts waiting for ierp requests
#define DEFAULT_ZONE_RADIUS 3 

#define MAX_DETECTED_QUERIES 20 // max queries that can be detected 
#define IERP_REQUEST_TIMEOUT 30 // secs before timeout on an ierp request
#define ZRP_STARTUP_JITTER 2.0	// secs to jitter start of periodic activity
#define MAX_SEQUENCE_ID 1000000000
#define QUERY_TABLE_EXPIRATION 1000
#define MAX_QUERY_DETECT_TABLE_SIZE 50

#define NEIGHBOR_ACK_TIMEOUT 10 // sec
#define TIMER_JITTER 3

#define BEACON_PERIOD 1  // period of beacon transmission in sec
#define NDP_SCAN_PERIOD 5
        // scan NDP table every number of beacon timeout cycles 
#define MAX_NODE_ID_CHAR_SIZE 10 // longest name string for my node address
                             // (char *)myid_ is string equiv of (int)myaddr_ 
#define MAX_IERP_CACHE    50  // max ierp requests cache size
#define MAX_QID           50  // max size query detect table
#define FOUND 1
#define LOST 0
#define TRUE 1
#define FALSE 0

typedef double Time;   
typedef int32_t Query_ID;

class ZRPAgent;

enum ZRPTYPE // Types of ZRP packets
{
  NDP_BEACON, NDP_BEACON_ACK, IARP_UPDATE, IARP_DATA, IERP_REPLY, IERP_REQUEST 
};

// link state data used in updates
struct linkie {
  
  int src_;   // 32 bits
  int dest_;  // 32 bits
  int isup_;
};

// ZRP header structure
struct hdr_zrp {
  int zrptype_;
  //  int safe_;
  int routeindex_;
    
  // IARP hdr
  int seq_;
  int numentries_; // number of link entries in this update
  // or length of direct routing list
  // info is in data portion of packet, use accessdata()

  nsaddr_t originator_; // for ndp, iarp or ierp
  nsaddr_t ierpsource_;
  nsaddr_t ierpdest_;
  nsaddr_t iarpsource_;
  nsaddr_t iarpdest_;
  nsaddr_t lastbordercaster_;
  Time pktsent_;
    
  // this is where the original data for upper layer pkts
  // is saved while ZRP routes pkt, at dest this is placed
  // back into hdrip->dport(), ie this is part of encapsulated data
  int enc_dport_;
  int enc_daddr_;
  packet_t enc_ptype_;
  
  int qid_;  // query id counter

  nsaddr_t *route_; // pointer to route list data
  linkie *links_;  // pointer to link state list 
  
  int forwarded_;  // TRUE if forwarded before
  
  // Packet header access functions
  static int offset_;
  inline static int& offset() { return offset_; }
  inline static hdr_zrp* access(const Packet* p) {
    return (hdr_zrp*) p->access(offset_);
  }
  
};

class ZRPBeaconTransmitTimer : public Handler {
 public:
  
  ZRPBeaconTransmitTimer(ZRPAgent* a)  { agent = a; } 
  // pgi- set zrp_agent to 'a', ie our ZRP_Agent
  void handle(Event*);  // function handling the event
  void start(double thistime);
  
  //  private:
  ZRPAgent *agent;
  Event intr;
  
};

class ZRPNeighborScanTimer : public Handler {
 public:
  
  ZRPNeighborScanTimer(ZRPAgent* a)  { agent = a; } 
  // pgi- set zrp_agent to 'a', ie our ZRP_Agent
  void handle(Event*);  // function handling the event
  void start(double thistime);
  
  //  private:
  ZRPAgent *agent;
  Event intr;
  
};

class ZRPPeriodicUpdateTimer : public Handler {
 public:
  
  ZRPPeriodicUpdateTimer(ZRPAgent* a)  { agent = a; } 
  // pgi- set zrp_agent to 'a', ie our ZRP_Agent
  void handle(Event*);  // function handling the event
  void start(double thistime);
    
  //  private:
  ZRPAgent *agent;
  Event intr;
  
};

class ZRPAckTimer : public Handler {
 public:
  
  ZRPAckTimer(ZRPAgent* a)  { agent = a; } 
  // pgi- set zrp_agent to 'a', ie our ZRP_Agent
  void handle(Event*);  // function handling the event
  void start();
  
  //  private:
  ZRPAgent *agent;
  Event intr;
  
};


class ZRPAgent : public Agent {

  friend class ZRPBeaconTimer;
 public:
  ZRPAgent(); // not generally used
  ZRPAgent(nsaddr_t id);
  
  void recv(Packet * p, Handler *);
  int  initialized() { return 1 && target_; } 

  //== Tcl Related ======================================
  char*  myid_;   // (char *)myid_ is string equiv of (int)myaddr_ 
  PriQueue* ll_queue;
  Trace* tracetarget;
  MobileNode* node_;
  NsObject* port_dmux_;
  
  //==Timer Related ==========================================

  ZRPNeighborScanTimer NeighborScanTimer_;
  ZRPBeaconTransmitTimer BeaconTransmitTimer_;
  ZRPPeriodicUpdateTimer PeriodicUpdateTimer_;
  ZRPAckTimer AckTimer_;
    
  //==Methods ================================================
  
  void startup();
  int  command (int argc, const char*const* argv);
  void scan_ierp_cache();
  void ierp_notify_iarp(Packet *p);
  void recvZRP(Packet* p);
  void forward_update(Packet* p);
  void route_pkt(Packet* p, nsaddr_t dest);
  void print_tables();
  
  int  neighbor_add(nsaddr_t newneighbor);
  void send_periodic_update();
  void sendp(nsaddr_t ns);
  void originate_request(nsaddr_t final, int qid);
  void scan_query_detections();
  void scan_linkstate_table();
  int query_detect1(int qid, nsaddr_t originid, nsaddr_t lastbordercaster,
		    int radius);
  int  node_is_covered(int queryid, nsaddr_t node);
  void inc_seq() { seq_++; if (seq_ > MAX_SEQUENCE_ID) seq_ = 1;}
  void dec_seq() { seq_--; if (seq_ < 1)  seq_ = MAX_SEQUENCE_ID;} 
  void pkt_add_all_links(Packet *p);
  void pkt_send(Packet *p, nsaddr_t addressee);
  void send_next_hop(Packet *p);
  void send_prev_hop(Packet *p);
  void pkt_broadcast(Packet *p);
  Packet* pkt_create(ZRPTYPE zrp_type, nsaddr_t addressee, int ttl);
  void pkt_add_node(Packet* p, nsaddr_t node, int total);
  void pkt_add_link(Packet* p, nsaddr_t lnksrc, nsaddr_t lnkdest, int isup);
  void pkt_read_update(Packet* p, link_struct *ls, int index) ;
  nsaddr_t find_next_hop(Packet* p);
  nsaddr_t find_prev_hop(Packet* p);
  int add_local_route(Packet* p, nsaddr_t node);
  int add_outer_route(Packet* p, nsaddr_t node);
  void do_update();
  void print_routes();
  void pkt_create_route_data_space(Packet *p, int size);
  void pkt_free_route_data_space(Packet *p);
  void pkt_create_link_data_space(Packet *p, int size);
  void pkt_free_link_data_space(Packet *p);
  void pkt_copy(Packet *pfrom, Packet *pto);
  void zdrop(Packet *p, const char *s);
  int  node_is_covered(nsaddr_t node, int queryid, nsaddr_t originid);
  void outer_route_expiration();
  void IARP_update_outer_route(int index);
    
  //==Data ===================================================

  int myaddr_;
  int radius_;   // Can be set from Tcl script, see ZRPAgent::command
  int transmit_jitter_;
  int startup_jitter_;
  int process_jitter_;
  int beacon_period_; // Can be set from Tcl script, see ZRPAgent::command
  int beacon_period_jitter_;
  int neighbor_timeout_;
  int neighbor_ack_timeout_;
  int iarp_update_period_;
  int neighbortable_scan_period_;
  
  int num_neighbors_;
  
  int tx_; // total pkts transmitted by agent
  int rx_; // total pkts received by agent
  int seq_; // current sequence id for outgoing IARP updates
  int qid_; // global query id counter, updated for every query sent by node
  
  int suspend_flag_; // Can be set from Tcl script, see ZRPAgent::command
  // "suspends" node, there are Tcl commands that work better "start","stop"

  //==Tables ===================================================
  neighbor_struct *neighbors_; // linked list of my neighbors
  LinkStateTable lstable;     // class, linked list
  RoutingTable rtable;        // class, array of pointers
  IERPCacheEntry *ierpcache[MAX_IERP_CACHE]; // array of pointers
  QueryDetectEntry *queries_[MAX_QUERY_DETECT_TABLE_SIZE];
};

#endif

zrp_table.cc

#include <config.h>
#include <agent.h>
#include <packet.h>
#include <ip.h>
#include <delay.h>
#include <scheduler.h>
#include <queue.h>
#include <trace.h>
#include <arp.h>
#include <ll.h>
#include <mac.h>
#include <priqueue.h>
#include <delay.h>
#include <random.h>
#include <object.h>
#include <route.h>
#include "zrp.h"
#include "zrp_table.h"

#define UP    1
#define DOWN  0

//===========================================================================
// Linkstate Table:
// Perform an update to table given a link state, Return seq_match=TRUE
// if there was a match. Return update=TRUE if any change in table.
//===========================================================================
BOOLEAN
LinkStateTable::update(int src, int dest, int lstate, int seq, int *seq_match) 
{
  Time now = Scheduler::instance().clock(); // get the time
  int flag; // TRUE indicates there has been a change in table
  link_struct* i;
  int found;

  *seq_match = FALSE;
  found = FALSE;
  flag = FALSE;
  
  if  (lshead_ == NULL) { // check if empty
    if (lstate == UP) { // add only if up
      // add to table, 
      lshead_ = new link_struct;
      lshead_->src_ = src;
      lshead_->dest_ = dest;
      lshead_->isup_ = lstate;
      lshead_->seq_ = seq;
      lshead_->expiry_ = now + LINKSTATE_EXPIRATION;
      lshead_->next_ = NULL;
      return TRUE;  // change in table
    }
    return FALSE;
  }
  
  for (i=lshead_; i != NULL; i=i->next_) {
    if ( ( (i->src_ == src)  && (i->dest_ == dest) ) || ( (i->src_ == dest) && (i->dest_ == src)  ) ) {  // src/dest match with update

      if ( (seq != 0) && (i->seq_ >= seq) ) {  // got this update before
	*seq_match = TRUE;
	return FALSE;
      }
      
      found = TRUE; // found a match (a,b) or (b,a)

      i->expiry_ = now + LINKSTATE_EXPIRATION; // update expiry
      
      if (seq != 0 )  // only update if new seq is non-zero (
	i->seq_ = seq; // update to new seq no.

      if ( i->isup_ != lstate) { //inequality=we need to change state to latest
	i->isup_ = lstate;
	flag = TRUE;
      }
    }
  }

  if (found) // return flag if there was change
    return flag;

  // we have found nothing up until this point, so add link
  
  if (lstate == UP) {  // don't want to add a downed link
    // add to table, 
    i = new link_struct;
    i->src_ = src;
    i->dest_ = dest;
    i->isup_ = lstate;
    i->seq_ = seq;
    i->next_ = lshead_;
    i->expiry_ = now + LINKSTATE_EXPIRATION;
    lshead_ = i;
    return TRUE;  // change in table    
  }
  return FALSE;
}

//=======================================================================
// Linkstate Table:
// Insert Link state entry into Link state table
//=======================================================================
void  
LinkStateTable::add(link_struct* link)
{  
  // insert link at head
  if (lshead_ != NULL) {  // if there is at least one link in list
    link->next_ = lshead_;       ;
    lshead_ = link;
  } else { // if empty
    lshead_ = link;
    lshead_->next_ = NULL;
  }

}

//========================================================================
// Route Table:
// Erases route and peripheral tables.
//========================================================================
void RoutingTable::erase() {
  // would be better if we saved fallow data structures 
  // on a free list - for version 2.0 ;)
  int i;
  rtable_node *tmp;

  //erase route table
  for (i=0; (i< MAX_NODES_PER_ZONE) && (route[i] != NULL) ; i++) {
    delete(route[i]);
    route[i] = NULL;
  } //end for
  
  // erase periph node list 
  while (periphnodes_ != NULL ) {
    tmp = periphnodes_;
    periphnodes_ = periphnodes_->next_;
    delete(tmp);
  }
  periphnodes_ = NULL;
}

//=========================================================================
// Linkstate Table:
// Clean table of expired links.
//==========================================================================
void
LinkStateTable::purge_links() 
{
  Time now = Scheduler::instance().clock(); // get the time
  link_struct *ls;
  
  // deletes down or expired links

  if (lshead_ == NULL) 
    return;

  // hack, insert a dummy node at head
  link_struct dummy;  
  dummy.next_ = lshead_;
  lshead_ = &dummy;
  
  for (ls=lshead_ ; ls->next_ != NULL; ) {

    if ( (ls->next_->expiry_ < now) || (ls->next_->isup_ == FALSE ) ) {
      link_struct *temp = ls->next_;
      ls->next_ = ls->next_->next_;
      delete temp;
      // other actions to take when you delete a node here
    } else {
      ls=ls->next_ ;
    }
        
  }
  lshead_ = dummy.next_;
  
}

//===========================================================================
// Linkstate Table:
// Print table to STDOUT.
//===========================================================================
void
LinkStateTable::print_links() 
{
  link_struct *ls;
  
  if (lshead_ == NULL) {
    printf("LinkTable: empty ");
  } else {
    printf("LinkTable: ");  
    
    for (ls = lshead_;  
	 (ls != NULL);
       ls=ls->next_) {   // If link list has one or more link
          
      if (ls->isup_) {
	printf("%d=%d ",ls->src_,ls->dest_); 
      } else {
	printf("%d#%d ",ls->src_,ls->dest_); 
      }
    } // for link_stuct 
  }
}

//===========================================================================
// Route Table:
// Print entries.
//===========================================================================
void 
RoutingTable::print() {
  rtable_node *j;
  int i;
  Time now = Scheduler::instance().clock(); // get the time
  printf("_%2d_ [%6.6f] | Route Table ",my_address_,now);
   
  for (i=0; route[i] != NULL && i< MAX_NODES_PER_ZONE ; i++) {
    
    printf("| Entry %d : ",i);
    
    if (route[i]==NULL) {
      printf("empty");
      return;
    } 
    
    for (j=route[i]; j!=NULL; j=j->next_  ) {
      printf("%d(%d)->",(int)j->id_,j->numhops_);
    } 
  }
  if (i==0) {
    printf("empty "); 
  }

}

//===========================================================================
// Route Table:
// Compute minimum hop routes to all nodes that are "radius" hops or less
// with respect to node myadd, given link state table. 
//===========================================================================
void
RoutingTable::compute_routes(nsaddr_t myadd, int radius) {
  link_struct *lptr; // a temp ptr for iterative loops
  link_struct *lst;  // a copy of link table
  link_struct* lnk;  // a ptr to newly created links
  link_struct* ls;   // a temp ptr for iterative loops
  int i;             // counter for iterative loop over route table
  int flag;
  Time now = Scheduler::instance().clock(); // get the time      
  rtable_node *tmp;
  
  flag = 0;
  lst = NULL;
  erase(); // route table
    
  if (linkstatetable->lshead_ == NULL) {    // If link list is empty
    return; // nothing broken, just ran out of link states
  }
    
  // copy valid links in linkstatetable list to lst
  for (lptr=linkstatetable->lshead_; lptr!=NULL; lptr=lptr->next_) { 
    flag = 1;
    
    if (lptr->isup_) {  // if link is valid, add to lst
      lnk = new link_struct(lptr->src_,lptr->dest_,TRUE,lst);
      lnk->src_ = lptr->src_;
      lnk->dest_ = lptr->dest_;
      lnk->isup_ = TRUE;
      // insert link at head of lst
      if (lst != NULL) { 
	lnk->next_ = lst;     
	lst = lnk;
      } else { // else if lst is empty
	lst = lnk;
	lst->next_ = NULL;
      } // end else
    }  // end if
    
  } // end while
  if (!flag)  { }

  route[0] = new rtable_node();
  route[0]->id_= myadd;
  route[0]->next_ = NULL;
  route[0]->numhops_ = 0;
  
  route[1] = NULL;

  num_entries_=1;
  
  // rtable[i] is "current" src we are looking at
  // search for all its neighbors dest(i), which gives us
  // a number of (current src,dest(i) pairs
  // for each pair found, check if dest is in route table
  // if not, add to route table. delete link from lst (set isup_=FALSE)
  // after you check the dest. 
  // add-drop will add/drop entries in route table
  for ( i=0; (i < MAX_NODES_PER_ZONE) && (route[i] != NULL); i++) {
  
    for (ls=lst;  // lst is a copy of linkstatetable, from above  
	 (ls != NULL);
	 ls=ls->next_)
      {
	if (ls->isup_ == TRUE) { // make sure it hasn't been "dropped"
	  add_drop(ls,i);
	}
      } // end for ls
  } // end for i

  // calculate peripheral nodes
  for (i=0; (i < MAX_NODES_PER_ZONE) && (route[i] != NULL); i++) {
    if (route[i]->numhops_ == radius ){
      rtable_node *temp = new rtable_node;
      temp->id_ = route[i]->id_;
      temp->next_ = periphnodes_;
      periphnodes_ = temp;
    }
  }
  empty_links(lst); 
  return;
}

//===========================================================================
// Route Table:
// Looks up node with address "id" in route table, returns index into table
// if it exists, otherwise sets to NotInTable.
//===========================================================================
int
RoutingTable::get_entry(nsaddr_t id) 
{
  int i;
  for (i=0;((route[i] != NULL) && (i<MAX_NODES_PER_ZONE+1)); i++) 
    if (route[i]->id_ == id) 
      return i;
  return (MAX_NODES_PER_ZONE+1);
}

//===========================================================================
// Route Table:
// Looks up node with address "id" in route table, returns TRUE if in table,
// otherwise false.
//===========================================================================
int
RoutingTable::route_exists(nsaddr_t id) 
{
 int i;
  for (i=0;((route[i] != NULL) && (i<MAX_NODES_PER_ZONE+1)); i++) 
    if (route[i]->id_ == id) 
      return TRUE;
  return FALSE;
}

//===========================================================================
// Linkstate Table:
// Delete out lstates in link state table.
//===========================================================================
void
RoutingTable::empty_links(link_struct *lst) 
{
  link_struct *lnk;
  while (lst != NULL) {
    lnk = lst;
    lst = lst->next_;
    delete lnk;
  }
}

//===========================================================================
// Route Table:
// Looks up node with address "nodeid" in route table,
// returns index if in table, otherwise -1.
//===========================================================================
int
RoutingTable::node_exists(nsaddr_t nodeid)
{
  int i;
  for (i=0;((route[i] != NULL) && (i<MAX_NODES_PER_ZONE+1)); i++) 
    if (route[i]->id_ == nodeid) 
      return i; // found
  return (-1); // not found
}

//============================================================================
// Route Table:
// Used by compute_routes() to calculate minimum hop tree.
// Add one more entry to route tree if this node "entree" is found to be
// one hop from an entry already in route tree, ie if node is equal to
// src or dest of this link, "lnk". If a match, this link is marked
// as covered for next pass. If no match, return, caller will continue
// iterating through link state table.
//============================================================================
void
RoutingTable::add_drop(link_struct *lnk, int entree)
{ 

  // if link is not up, nothing left to do
  if (lnk->isup_ == FALSE) { 
    return;
  }

  // if src is in route table
  if ( lnk->src_ == route[entree]->id_ ) {  
    // found a link with same src
    
    // see if dest exists in route table
    if (get_entry(lnk->dest_) != (MAX_NODES_PER_ZONE+1)) {
      
      // yes route already exists, don't add
      lnk->isup_ = FALSE; // in effect dropping link   
      //return TRUE; // but do delete current link_struct
      return;
      
    } else if ( route[ get_entry(lnk->src_) ]->numhops_ < agent_->radius_ ) {
      // add node to RouteTable if within radius
      
      if (num_entries_ == MAX_NODES_PER_ZONE) {
	// error, overflow
	printf("Need to increase MAX_NODES_PER_ZONE in zrp.h to greater"
	       "than %d\n",MAX_NODES_PER_ZONE);
      }
      // add a new route to route table, id=dest,
      // next is route entry with id=src
      route[num_entries_] = new rtable_node;
      route[num_entries_]->id_ = lnk->dest_;
      route[num_entries_]->next_ = route[ get_entry(lnk->src_) ];
      if (route[num_entries_]->next_) {
	route[num_entries_]->numhops_ = route[num_entries_]->next_->numhops_+1;
      } else {
	route[num_entries_]->numhops_ = 0;
      }
      num_entries_++;
      lnk->isup_ = FALSE; // in effect dropping link   
    }
    //return TRUE; // tell the caller to delete the current link_struct
    return;
    
  }  else if ( lnk->dest_ == route[entree]->id_ ) {  
    // found a link with same dest
    
    // see if src exists in route table
    if (get_entry(lnk->src_) != (MAX_NODES_PER_ZONE+1)) {
      
      // yes route already exists, don't add
      lnk->isup_ = FALSE; // in effect dropping link   
      //return TRUE; // but do delete current link_struct
      return;

      // if dest is in route table
    } else if ( route[ get_entry(lnk->dest_) ]->numhops_ < agent_->radius_ ) {

      if (num_entries_ == MAX_NODES_PER_ZONE) {
	// error, overflow
	printf("Need to increase MAX_NODES_PER_ZONE in zrp.h to greater"
	       "than %d\n",MAX_NODES_PER_ZONE);
      }
      // add a new route to route table, id=dest,
      //next is route entry with id=src
      route[num_entries_] = new rtable_node;
      route[num_entries_]->id_ = lnk->src_;
      route[num_entries_]->next_ = route[ get_entry(lnk->dest_) ];
      if (route[num_entries_]->next_) {
	route[num_entries_]->numhops_ = route[num_entries_]->next_->numhops_+1;
      } else {
	route[num_entries_]->numhops_ = 0;
      }
      num_entries_++;
      lnk->isup_ = FALSE; // in effect dropping link   
    }
    return;
  }
  return;
}

zrp_table.h

#ifndef _zrp_table_h_
#define _zrp_table_h_

#include <config.h>
#include <agent.h>
#include <packet.h>
#include <ip.h>
#include <delay.h>
#include <scheduler.h>
#include <queue.h>
#include <trace.h>
#include <arp.h>
#include <ll.h>
#include <mac.h>
#include <priqueue.h>
#include <delay.h>
#include <random.h>
#include <object.h>
#include <route.h>
#include "zrp.h"

//typedef int32_t Query_ID;
typedef int Query_ID;
typedef int BOOLEAN;
typedef double Time;



#define LINKSTATE_EXPIRATION 25

#define MAX_NODES_PER_ZONE 50
#define MAX_OUTER_ROUTES 50

class ZRPAgent; // pre-declaration

//===========================================================================
// IERP Cache Table:
// A single entry in the outgoing IERP requests table, has an expiry.
//===========================================================================
struct IERPCacheEntry {
  
  Query_ID qid_;
  Packet *pkt_;
  Time expiry_;
};

struct rtable_node; // pre-declaration needed for next struct

//===========================================================================
// Query Detect Table:
// A single entry in the QD table, has an expiry.
//===========================================================================
struct QueryDetectEntry {  

  nsaddr_t originid_;
  Query_ID qid_;
  Time expiry_;
  rtable_node *next_; // list of covered nodes

};

//===========================================================================
// Neighbor Table:
// Neighbor table is a linked list of these.
//===========================================================================
struct neighbor_struct 
{
  nsaddr_t addr_;
  neighbor_struct* next_;
  Time expiry_;
  Time lastack_;
  
};

//===========================================================================
// Linkstate Table:
// Link state atomic data, contains state in isup_ (up or down) ans seq.
//===========================================================================
class link_struct {
public:

  link_struct() : seq_(0), isup_(FALSE) {//, next_(NULL) {
    bzero(this, sizeof(link_struct));
  }

  link_struct(nsaddr_t srcid, nsaddr_t destid, BOOLEAN valid,link_struct* next)
    {
      src_=(srcid);
      dest_=(destid);
      isup_=(valid);
      //      next_=(next);
      seq_=0;
    }

  nsaddr_t src_;   // 32 bits
  nsaddr_t dest_;  // 32 bits

  int flag_; // flag used for Dijstkra's algorithm
  int isup_;
  int seq_;  // sequence number
  Time expiry_;
    
  //  Time timestamp;
  
  link_struct* next_;
};

//===========================================================================
// Linkstate Table:
// Class for storing Link States in node.
//===========================================================================
class LinkStateTable {   
 public:

  LinkStateTable() : lshead_(NULL) { }

  nsaddr_t  my_address_; // debug
  
  link_struct* lshead_;

  link_struct* last() ;

  void add(link_struct *link);  // quietly ignore errors ;)

  int remove(link_struct *link);

  BOOLEAN update(nsaddr_t src, nsaddr_t dest, 
		 int state, int seq, int *seq_match);

  int exist(link_struct *link);
  
  void print_links();
  void purge_links();
  

};

//===========================================================================
// Route Table:
// A single data struct naming a node, used for storing node addresses
// in various tables.
//===========================================================================
struct rtable_node {
  nsaddr_t id_;
  int numhops_; // number of hops from me
  rtable_node* next_;
  rtable_node() : id_(0), next_(NULL) { }
  rtable_node(nsaddr_t newid) : id_(newid), next_(NULL) { }
};

//===========================================================================
// Route Table:
// This struct is a head pointer for a route entry, has expiry timestamp.
// Route is at next_ .
//===========================================================================
struct rtable_entry {
  nsaddr_t id_;
  Time expiry_;
  int numhops_; // number of hops from me
  rtable_node* next_; // route is here
  rtable_entry() : id_(0), next_(NULL), expiry_(0), numhops_(0)  { }
  rtable_entry(nsaddr_t newid) : id_(newid), next_(NULL), expiry_(0),
    numhops_(0) { }
};

//===========================================================================
// Route Table:
// Class includes a tag (agent_) to agent it resides in to access friendly
// data and methods.
//===========================================================================
class RoutingTable {
  public:

  RoutingTable(ZRPAgent* a)  { // init
    num_entries_=(0);
    agent_ = a;
  }
  
  ZRPAgent* agent_;
  
  nsaddr_t  my_address_;

  int num_entries_;

  // Tables
  rtable_node* route[MAX_NODES_PER_ZONE+1]; // Last ptr is always null
  rtable_entry* outer_route[MAX_OUTER_ROUTES]; // Last ptr is always null
  rtable_node* periphnodes_;
  LinkStateTable *linkstatetable;

  // Methods    
  void RoutingTable::compute_routes(nsaddr_t myadd, int radius);
  void erase();
  void print();
  // returns pointer to entry to node's route
  int get_entry(nsaddr_t node_id);
  int route_exists(nsaddr_t id);

  // drop from link table, add node to RouteTable
  void add_drop(link_struct* ls, int i);

  // Finds Next Hop On route to given,
  //returns FALSE if doesn't exist
  int next_hop_to(nsaddr_t node) { }

  // returns route entry index for given node 
  int node_exists(nsaddr_t nodei);

  void empty_links(link_struct *lst);

  //  int rmax; // the number of hops to the farthest node in my LRZ
};

#endif