通讯编程

开发平台：
Visual C++

landmark.cc：源码内容
							
/*
 * landmark.cc
 * Copyright (C) 2000 by the University of Southern California
 * $Id: landmark.cc,v 1.8 2005/08/25 18:58:12 johnh Exp $
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License,
 * version 2, as published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program; if not, write to the Free Software Foundation, Inc.,
 * 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
 *
 *
 * The copyright of this module includes the following
 * linking-with-specific-other-licenses addition:
 *
 * In addition, as a special exception, the copyright holders of
 * this module give you permission to combine (via static or
 * dynamic linking) this module with free software programs or
 * libraries that are released under the GNU LGPL and with code
 * included in the standard release of ns-2 under the Apache 2.0
 * license or under otherwise-compatible licenses with advertising
 * requirements (or modified versions of such code, with unchanged
 * license).  You may copy and distribute such a system following the
 * terms of the GNU GPL for this module and the licenses of the
 * other code concerned, provided that you include the source code of
 * that other code when and as the GNU GPL requires distribution of
 * source code.
 *
 * Note that people who make modified versions of this module
 * are not obligated to grant this special exception for their
 * modified versions; it is their choice whether to do so.  The GNU
 * General Public License gives permission to release a modified
 * version without this exception; this exception also makes it
 * possible to release a modified version which carries forward this
 * exception.
 *
 */
// $Header: /cvsroot/nsnam/ns-2/sensor-nets/landmark.cc,v 1.8 2005/08/25 18:58:12 johnh Exp $
// Author: Satish Kumar, kkumar@isi.edu
#include <stdarg.h>
#include <float.h>
#include "landmark.h"
#include <random.h>
#include <cmu-trace.h>
#include <address.h>
static int lm_index = 0;
void
LMNode::copy_tag_list(compr_taglist *taglist)
{
  compr_taglist *tags = NULL;
  compr_taglist *tag_ptr1, *tag_ptr2;
  // Delete the old tag list if it exists
  if(tag_list_) {
    tag_ptr1 = tag_list_;
    while(tag_ptr1) {
      tag_ptr2 = tag_ptr1;
      tag_ptr1 = tag_ptr1->next_;
      delete tag_ptr2;
    }
    tag_list_ = NULL;
  }
  // Copy the specified taglist
  tag_ptr1 = taglist;
  while(tag_ptr1) {
    if(!tag_list_) {
      tag_list_ = new compr_taglist;
      tag_ptr2 = tag_list_;
    }
    else {
      tag_ptr2->next_ = new compr_taglist;
      tag_ptr2 = tag_ptr2->next_;
    }
    tag_ptr2->obj_name_ = tag_ptr1->obj_name_;
    tag_ptr1 = tag_ptr1->next_;
  }
}
// Returns a random number between 0 and max
inline double 
LandmarkAgent::jitter(double max, int be_random_)
{
  return (be_random_ ? Random::uniform(max) : 0);
}
// Returns a random number between 0 and max
inline double 
LandmarkAgent::random_timer(double max, int be_random_)
{
  return (be_random_ ? rn_->uniform(max) : 0);
}
void
LandmarkAgent::stop()
{
  ParentChildrenList *pcl = parent_children_list_, *tmp_pcl;
  trace("Node %d: LM Agent going down at time %f",myaddr_,NOW);
  // Cancel any running timers and reset relevant variables
  if(promo_timer_running_) {
    promo_timer_running_ = 0;
    promo_timer_->cancel();
  }
  num_resched_ = 0;
  wait_state_ = 0;
  total_wait_time_ = 0;
  // Reset highest level of node
  highest_level_ = 0;
  // Delete ParentChildrenList objects for all levels
  while(pcl) {
    tmp_pcl = pcl;
    pcl = pcl->next_;
    delete tmp_pcl;
  }
  parent_children_list_ = NULL;
  // Indicate that node is dead so that packets will not be processed
  node_dead_ = 1;
  global_lm_id_ = NO_GLOBAL_LM;
  global_lm_level_ = -1;
  // Event id > 0 for scheduled event
  if(tag_advt_event_->uid_ > 0) {
    Scheduler &s = Scheduler::instance();
    s.cancel(tag_advt_event_);
  }
}
void LandmarkAgent::
trace (char *fmt,...)
{
  va_list ap; // Define a variable ap that will refer to each argument in turn
  if (!tracetarget_)
    return;
  // Initializes ap to first argument
  va_start (ap, fmt); 
  // Prints the elements in turn
  vsprintf (tracetarget_->buffer (), fmt, ap); 
  tracetarget_->dump ();
  // Does the necessary clean-up before returning
  va_end (ap); 
}
static class LandmarkClass:public TclClass
{
  public:
  LandmarkClass ():TclClass ("Agent/landmark")
  {
  }
  TclObject *create (int, const char *const *)
  {
    return (new LandmarkAgent ());
  }
} class_landmark;
LandmarkAgent::LandmarkAgent (): Agent(PT_MESSAGE), promo_start_time_(0), promo_timeout_(50), promo_timeout_decr_(1), promo_timer_running_(0), seqno_(0), highest_level_(0), parent_children_list_(NULL), ll_queue(0), be_random_(1), wait_state_(0), total_wait_time_(0), debug_(1) ,qry_debug_(0)
 {
  promo_timer_ = new PromotionTimer(this);
  //  bind_time ("promo_timeout_", "&promo_timeout_");
  num_resched_ = 0;
  tag_dbase_ = NULL;
  node_ = NULL;
  cache_ = 0; // default is to disable caching
  tag_cache_ = new TagCache[MAX_CACHE_ITEMS];
  num_cached_items_ = 0;
  recent_demotion_msgs_ = new RecentMsgRecord[MAX_DEMOTION_RECORDS];
  num_demotion_msgs_ = 0;
  // default value for the update period
  update_period_ = 400;
  update_timeout_ = update_period_ + 4 * LM_STARTUP_JITTER;
  adverts_type_ = FLOOD;  // default is to flood adverts
  global_lm_ = 0; // No global LMs by default
  global_lm_id_ = NO_GLOBAL_LM;
  global_lm_level_ = -1;
  // myaddr_ not defined at this point ... So use lm_index for init
  rn_ = new RNG(RNG::RAW_SEED_SOURCE,lm_index++);;
  // Throw away a bunch of initial values
  for(int i = 0; i < 128; ++i) {
    rn_->uniform(200);
  }
  node_dead_ = 0;
  bind ("be_random_", &be_random_);
  //  bind ("myaddr_", &myaddr_);
  bind ("debug_", &debug_);
  num_nbrs_ = 0;
  nbrs_ = NULL;
  tag_mobility_ = new TagMobilityHandler(this);
  tag_mobility_event_ = new Event;
  // myaddr_ not defined at this point ... So use lm_index for init
  tag_rng_ = new RNG(RNG::RAW_SEED_SOURCE,lm_index++);;
  // Throw away a bunch of initial values
  for(int i = 0; i < 128; ++i) {
    tag_rng_->uniform(200);
  }
  mobility_period_ = 60;
  mobile_tags_ = NULL;
  tag_advt_handler_ = new TagAdvtHandler(this);
  tag_advt_event_ = new Event;
}
int
LandmarkAgent::CheckDemotionMsg(nsaddr_t id, int level, int origin_time)
{
  int i = 0;
  // If object already exists in cache, update info if necessary
  for(i = 0; i < num_demotion_msgs_; ++i) {
    if(recent_demotion_msgs_[i].id_ == id && recent_demotion_msgs_[i].level_ == level) {
      if(recent_demotion_msgs_[i].origin_time_ >= origin_time) {
        return(OLD_MESSAGE);
      }
      else {
        recent_demotion_msgs_[i].origin_time_ = origin_time;
        return(NEW_ENTRY);
      }
    }
  }
  if(num_demotion_msgs_ < MAX_DEMOTION_RECORDS) {
    i = num_demotion_msgs_;
    ++num_demotion_msgs_;
    recent_demotion_msgs_[i].id_ = id;
    recent_demotion_msgs_[i].level_ = level;
    recent_demotion_msgs_[i].origin_time_ = origin_time;
  }
  else {
    // Use LRU cache replacement
    int replace_index = 0;
    int least_time = recent_demotion_msgs_[replace_index].origin_time_;
    for(i = 0; i < MAX_DEMOTION_RECORDS; ++i) {
      if(recent_demotion_msgs_[i].origin_time_ < least_time)
        replace_index = i;
    }
    recent_demotion_msgs_[replace_index].id_ = id;
    recent_demotion_msgs_[replace_index].level_ = level;
    recent_demotion_msgs_[replace_index].origin_time_ = origin_time;
  }
  return(NEW_ENTRY);
}
void
ParentChildrenList::UpdateChildLMAddr(nsaddr_t id, int num_lm_addrs, int64_t *lm_addrs)
{
  LMNode *potl_ch = NULL;
  potl_ch = pchildren_;
  while(potl_ch) {
    if(potl_ch->id_ == id)
      break;
    potl_ch = potl_ch->next_;
  }
  assert(potl_ch);
  (potl_ch->lmaddr_)->delete_lm_addrs();
  for(int i = 0; i < num_lm_addrs; ++i)
    (potl_ch->lmaddr_)->add_lm_addr(lm_addrs[i]);
}
int
ParentChildrenList::UpdatePotlParent(nsaddr_t id, nsaddr_t next_hop, int num_hops, int level, int num_children, int energy, int origin_time, int delete_flag)
{
  LMNode *potl_parent, *list_ptr;
  double now = Scheduler::instance().clock();
  // Extract seqnum and origin time
  int seqnum = origin_time & 0xFFFF;
  origin_time = origin_time >> 16;
  
  assert(num_pparent_ >= 0);
  // cannot delete from an empty list!
  if(delete_flag && !pparent_)
    return(ENTRY_NOT_FOUND);
  //  if((a_->debug_) && (a_->myaddr_ == 24)) {
  //    a_->trace("Node %d: Updating Potl Parent level %d, id %d, delete_flag %d, time %f",a_->myaddr_,level_,id,delete_flag,now);
  //  }
  if(pparent_ == NULL) {
    pparent_ = new LMNode(id, next_hop, num_hops, level, num_children, energy, origin_time, now);
    pparent_->last_upd_seqnum_ = seqnum;
    parent_ = pparent_;
    ++num_pparent_;
    return(NEW_ENTRY);
  }
  
  list_ptr = pparent_;
  potl_parent = list_ptr;
  while(list_ptr != NULL) {
    if(list_ptr->id_ == id) {
      // Check if this is a old message floating around in the network
      if(list_ptr->last_upd_origin_time_ > origin_time || (list_ptr->last_upd_origin_time_ == origin_time && list_ptr->last_upd_seqnum_ >= seqnum)) {
	// Check if we got the old update on a shorter path
	if(list_ptr->num_hops_ > num_hops) {
	  list_ptr->next_hop_ = next_hop;
	  list_ptr->num_hops_ = num_hops;
	  return(OLD_ENTRY);
	}
	return(OLD_MESSAGE); 
      }
      if(!delete_flag) {
	// Make this node as parent if it's closer than current parent
	if(parent_->num_hops_ > num_hops + 10 || num_hops == 0) {
	  parent_ = list_ptr;
	}
	list_ptr->next_hop_ = next_hop;
	list_ptr->num_hops_ = num_hops;
	list_ptr->level_ = level;
	list_ptr->num_children_ = num_children;
	list_ptr->energy_ = energy;
	list_ptr->last_upd_origin_time_ = origin_time;
	list_ptr->last_upd_seqnum_ = seqnum;
	list_ptr->last_update_rcvd_ = Scheduler::instance().clock();
      }
      else { // delete the entry
	if(num_pparent_)
	  --(num_pparent_);
	if(pparent_ == list_ptr)
	  pparent_ = list_ptr->next_;
	else
	  potl_parent->next_ = list_ptr->next_;
	if(parent_->id_ == list_ptr->id_)
	  assert(parent_ == list_ptr);
	// No parent if potl parent list is empty
	if(pparent_ == NULL) {
	  parent_ = NULL;
	}
	else if(parent_ == list_ptr) {
	// Select new parent if current parent is deleted and
	// potl parent is not empty; closest potl parent is new parent
	  LMNode *tmp = pparent_;
	  int best_num_hops = pparent_->num_hops_;
	  LMNode *best_parent = pparent_;
	  while(tmp != NULL) {
	    if(tmp->num_hops_ < best_num_hops) {
	      best_num_hops = tmp->num_hops_;
	      best_parent = tmp;
	    }
	    tmp = tmp->next_;
	  }
	  parent_ = best_parent;
	}
	delete list_ptr;
      }
      return(OLD_ENTRY);
    }
    potl_parent = list_ptr;
    list_ptr = list_ptr->next_;
  }
  if(delete_flag)
    return(ENTRY_NOT_FOUND);
  potl_parent->next_ = new LMNode(id, next_hop, num_hops, level, num_children, energy, origin_time, now);
  (potl_parent->next_)->last_upd_seqnum_ = seqnum;
  ++num_pparent_;
  // Make this node as parent if it's closer than current parent
  if(parent_->num_hops_ > num_hops) {
    parent_ = potl_parent->next_;
  }
  return(NEW_ENTRY);
}
int
ParentChildrenList::UpdatePotlChild(nsaddr_t id, nsaddr_t next_hop, int num_hops, int level, int num_children, int energy, int origin_time, int child_flag, int delete_flag, compr_taglist *taglist)
{
  LMNode *potl_child, *list_ptr;
  double now = Scheduler::instance().clock();
  int new_child = 0;
  int tags_changed = 0;
  int seqnum = origin_time & 0xFFFF;
  origin_time = origin_time >> 16;
  //  if(a_->debug_) printf("Node %d: Number of potl children %d",a_->myaddr_,num_potl_children_);
  // cannot delete from an empty list!
  if(delete_flag && !pchildren_) {
    return(ENTRY_NOT_FOUND);
  }
  assert(num_potl_children_ >= 0);
  assert(num_children_ >= 0);
  if(pchildren_ == NULL) {
    pchildren_ = new LMNode(id, next_hop, num_hops, level, num_children, energy, origin_time, now);
    pchildren_->child_flag_ = child_flag;
    pchildren_->last_upd_seqnum_ = seqnum;
    if(child_flag == IS_CHILD) ++(num_children_);
    if(child_flag != NOT_POTL_CHILD) ++(num_potl_children_);
    ++(num_heard_);
    pchildren_->copy_tag_list(taglist);
    if(child_flag == IS_CHILD)
      return(NEW_CHILD);
    else
      return(NEW_ENTRY);
  }
  
  list_ptr = pchildren_;
  potl_child = list_ptr;
  while(list_ptr != NULL) {
    if(list_ptr->id_ == id) {
      // Check if this is a old message floating around in the network
      if(list_ptr->last_upd_origin_time_ > origin_time || (list_ptr->last_upd_origin_time_ == origin_time && list_ptr->last_upd_seqnum_ >= seqnum)) {
	// Check if we got this update on a shorter path; If the update rcvd
	// on a shorter path, we need to forward this message to ensure that
	// this message reaches all nodes in the advertising node's vicinity
	if(list_ptr->num_hops_ > num_hops) {
	  list_ptr->next_hop_ = next_hop;
	  list_ptr->num_hops_ = num_hops;
	  return(OLD_ENTRY);
	}
	
	return(OLD_MESSAGE);
      }
      if(!delete_flag) {
	// Old entry but the status has changed to child or vice-versa
	if((list_ptr->child_flag_ == NOT_CHILD || list_ptr->child_flag_ == NOT_POTL_CHILD) && (child_flag == IS_CHILD)) {
	  list_ptr->child_flag_ = child_flag;
	  ++(num_children_);
	  new_child = 1;
	}
	else if((list_ptr->child_flag_ == IS_CHILD) && (child_flag == NOT_CHILD || child_flag == NOT_POTL_CHILD)) {
	  list_ptr->child_flag_ = child_flag;
	  --(num_children_);
	}
	list_ptr->next_hop_ = next_hop;
	list_ptr->num_hops_ = num_hops;
	list_ptr->level_ = level;
	list_ptr->num_children_ = num_children;
	list_ptr->energy_ = energy;
	list_ptr->last_upd_origin_time_ = origin_time;
	list_ptr->last_upd_seqnum_ = seqnum;
	list_ptr->last_update_rcvd_ = Scheduler::instance().clock();
	if(!a_->compare_tag_lists(list_ptr->tag_list_,-1,taglist,-1)) {
	  tags_changed = 1;
	  // Delete the old tag list and copy the specified taglist
	  list_ptr->copy_tag_list(taglist);
	}
      }
      else {
	if(pchildren_ == list_ptr)
	  pchildren_ = list_ptr->next_;
	else
	  potl_child->next_ = list_ptr->next_;
	if(list_ptr->child_flag_ == IS_CHILD) --num_children_;
	if(list_ptr->child_flag_ != NOT_POTL_CHILD) --num_potl_children_;
	--num_heard_;
	delete list_ptr;
      }
      if(new_child)
	return(NEW_CHILD);
      else if(tags_changed && child_flag == IS_CHILD)
	return(OLD_CHILD_TAGS_CHANGED);
      else
	return(OLD_ENTRY);
    }
    potl_child = list_ptr;
    list_ptr = list_ptr->next_;
  }
  // delete flag must be FALSE if we are here
  // assert(!delete_flag);
  if(delete_flag) {
    return(ENTRY_NOT_FOUND);
  }
  
  potl_child->next_ = new LMNode(id, next_hop, num_hops, level, num_children, energy, origin_time, now);
  (potl_child->next_)->copy_tag_list(taglist);
  (potl_child->next_)->child_flag_ = child_flag;
  (potl_child->next_)->last_upd_seqnum_ = seqnum;
  if(child_flag == IS_CHILD) ++(num_children_);
  if(child_flag != NOT_POTL_CHILD) ++(num_potl_children_);
  ++(num_heard_);
  if(child_flag == IS_CHILD)
    return(NEW_CHILD);
  else
    return(NEW_ENTRY);
}
void
LandmarkAgent::ProcessHierUpdate(Packet *p)
{
  hdr_ip *iph = HDR_IP(p);
  hdr_cmn *hdrc = HDR_CMN(p);
  Scheduler &s = Scheduler::instance();
  double now = s.clock();
  int origin_time = 0;
  unsigned char *walk;
  nsaddr_t origin_id, parent, next_hop;
  int i, level, vicinity_radius, num_hops, potl_parent_flag = FALSE;
  int action, energy = 0;
  nsaddr_t *potl_children;
  int num_children = 0;
  int num_potl_children = 0;
  int num_lm_addrs = 0;
  int num_advert_lm_addrs = 0;
  int64_t *advert_lm_addrs = NULL;
  int64_t *lm_addrs = NULL;
  // Packet will have seqnum, level, vicinity radii, parent info
  // and possibly potential children (if the node is at level > 0)
  int num_tags = 0;
  compr_taglist *adv_tags = NULL, *tag_ptr;
  compr_taglist *tag_ptr1, *tag_ptr2;
  Packet *newp;
  //  if(now > 412.5) {
  //    purify_printf("ProcessHierUpdate1, %f, %dn",now,myaddr_);
  //    purify_new_leaks();
  //  }
  //  if(debug_)
  //    trace("Node %d: Received packet from %d with ttl %d", myaddr_,iph->saddr(),iph->ttl_);
  walk = p->accessdata();
  // Originator of the LM advertisement and the next hop to reach originator
  origin_id = iph->saddr();    
  // Free and return if we are seeing our own packet again
  if(origin_id == myaddr_) {
    Packet::free(p);
    return;
  }
  
  // type of advertisement
  action = *walk++;
  num_advert_lm_addrs = *walk++;
  if(num_advert_lm_addrs)
    advert_lm_addrs = new int64_t[num_advert_lm_addrs];
  for(int j = 0; j < num_advert_lm_addrs; ++j) {
    advert_lm_addrs[j] = *walk++;
    advert_lm_addrs[j] = (advert_lm_addrs[j] << 8) | *walk++;
    advert_lm_addrs[j] = (advert_lm_addrs[j] << 8) | *walk++;
    advert_lm_addrs[j] = (advert_lm_addrs[j] << 8) | *walk++;
    advert_lm_addrs[j] = (advert_lm_addrs[j] << 8) | *walk++;
    advert_lm_addrs[j] = (advert_lm_addrs[j] << 8) | *walk++;
    advert_lm_addrs[j] = (advert_lm_addrs[j] << 8) | *walk++;
    advert_lm_addrs[j] = (advert_lm_addrs[j] << 8) | *walk++;
  }
  
  // level of the originator
  level = *walk++;
    //    if(num_advert_lm_addrs)
    //      trace("Node 10: Rcved msg from 0, level %d, num_lm_addrs %d, advert_lm_addrs %x, time %f",level,num_advert_lm_addrs,advert_lm_addrs[0],now);
  //  trace("Node %d: Processing Hierarchy Update Packet", myaddr_);
  //  if((myaddr_ == 153) && (origin_id == 29)) {
  //    trace("Node 153: Receiving level %d update from node 29 at time %f,action = %d",level,s.clock(),action);
  //  }
  // energy level of advertising node
  energy = *walk++;
  energy = (energy << 8) | *walk++;
  energy = (energy << 8) | *walk++;
  energy = (energy << 8) | *walk++;
  // next hop info
  next_hop = *walk++;
  next_hop = (next_hop << 8) | *walk;
  // Change next hop to ourselves for the outgoing packet
  --walk;
  (*walk++) = (myaddr_ >> 8) & 0xFF;
  (*walk++) = (myaddr_) & 0xFF;
  
  // vicinity radius
  vicinity_radius = *walk++;
  vicinity_radius = (vicinity_radius << 8) | *walk++;
  // number of hops away from advertising LM
  num_hops = vicinity_radius - (iph->ttl_ - 1);
  //  if(myaddr_ == 155)
  //    trace("Node 155: Receiving level %d update from node %d at time %f,action = %d, num_hops = %d",level,origin_id,s.clock(),action,num_hops);
  // origin time of advertisement
  origin_time = *walk++;
  origin_time = (origin_time << 8) | *walk++;
  origin_time = (origin_time << 8) | *walk++;
  origin_time = (origin_time << 8) | *walk++;
  
  //  if(debug_ && myaddr_ == 33)
  //    trace("Node %d: Processing level %d pkt from %d at t=%f, origin %d, num hops %d", myaddr_,level,iph->saddr_,now,origin_time,num_hops);
  // Parent of the originator
  parent = *walk++;
  parent = parent << 8 | *walk++;
  // Number of hops has to be less than vicinity radius to ensure that atleast
  // 2 level K LMs see each other if they exist
  if(level > 0 && (action == PERIODIC_ADVERTS || action == GLOBAL_ADVERT || action == UNICAST_ADVERT_CHILD || action == UNICAST_ADVERT_PARENT)) {
    // Number of children
    num_children = *walk++;
    num_children = num_children << 8 | *walk++;
    // Number of potential children
    num_potl_children = *walk++;
    num_potl_children = num_potl_children << 8 | *walk++;
  // If level of advertising LM > 1, check if we are in potl children list.
  // If so, add as potl parent to level - 1
    if(num_potl_children) {
      potl_children = new nsaddr_t[num_potl_children];
      for(i = 0; i < num_potl_children; ++i) {
	potl_children[i] = *walk++;
	potl_children[i] = potl_children[i] << 8 | *walk++;
	int tmp_num_addrs = *walk++;
	if(potl_children[i] == myaddr_) {
	  potl_parent_flag = TRUE;
	  num_lm_addrs = tmp_num_addrs;
	  if(num_lm_addrs) {
	    lm_addrs = new int64_t[num_lm_addrs];
	    for(int j = 0; j < num_lm_addrs; ++j) {
	      lm_addrs[j] = *walk++;
	      lm_addrs[j] = (lm_addrs[j] << 8) | *walk++;
	      lm_addrs[j] = (lm_addrs[j] << 8) | *walk++;
	      lm_addrs[j] = (lm_addrs[j] << 8) | *walk++;
	      lm_addrs[j] = (lm_addrs[j] << 8) | *walk++;
	      lm_addrs[j] = (lm_addrs[j] << 8) | *walk++;
	      lm_addrs[j] = (lm_addrs[j] << 8) | *walk++;
	      lm_addrs[j] = (lm_addrs[j] << 8) | *walk++;
	    }
	  }
	}
	else 
	  walk = walk + tmp_num_addrs*8;
      }
    }
  }
  
  num_tags = 0;
  if(action == PERIODIC_ADVERTS || action == GLOBAL_ADVERT || action == UNICAST_ADVERT_CHILD || action == UNICAST_ADVERT_PARENT) {
    num_tags = *walk++;
    num_tags = (num_tags << 8) | *walk++;
  }
  adv_tags = NULL;
  // Store tag info only if the level of advertising LM is less than 
  // our highest level; otherwise we dont need this information
  if(num_tags && level < highest_level_) {
    adv_tags = new compr_taglist;
    tag_ptr = adv_tags;
    i = 0;
    while(i < num_tags) {
      if(i) {
	tag_ptr->next_ = new compr_taglist;
	tag_ptr = tag_ptr->next_;
      }
      tag_ptr->obj_name_ = *walk++;
      tag_ptr->obj_name_ = (tag_ptr->obj_name_ << 8) | *walk++;
      tag_ptr->obj_name_ = (tag_ptr->obj_name_ << 8) | *walk++;
      tag_ptr->obj_name_ = (tag_ptr->obj_name_ << 8) | *walk++;
      ++i;
      //	trace("tag name: %d.%d.%d",(tag_ptr->obj_name_ >> 24) & 0xFF,(tag_ptr->obj_name_ >> 16) & 0xFF,(tag_ptr->obj_name_) & 0xFFFF);
    }
  }
  //  if(level == 253)
  //    trace("Level is 253 at time %fn",now);
  ParentChildrenList **pcl1 = NULL;
  ParentChildrenList **pcl2 = NULL;
  int found1 = FALSE;
  int found2 = FALSE;
  ParentChildrenList **pcl = &parent_children_list_;
  // Insert parent-child objects for levels: level-1 (if level > 0) & level + 1
  while((*pcl) != NULL) {
    if((*pcl)->level_ == (level-1)) {
      found1 = TRUE;
      pcl1 = pcl;
    }
    if((*pcl)->level_ == (level+1)) {
      found2 = TRUE;
      pcl2 = pcl;
    }
    pcl = &((*pcl)->next_);
  }
  // check if level > 0
  if(!found1 && level) {
    *pcl = new ParentChildrenList(level-1, this);
    pcl1 = pcl;
    pcl = &((*pcl)->next_);
  }
  if(!found2) {
    *pcl = new ParentChildrenList(level+1, this);
    pcl2 = pcl;
    pcl = &((*pcl)->next_);
  }
  // If level is same as our level, we can decrease the promotion timer 
  // if it's running provided we havent already heard advertisements from
  // this node
  int delete_flag = FALSE; // Add the child/potl parent entry
  if(action == DEMOTION) delete_flag = TRUE;
  int child_flag = NOT_CHILD; // Indicates whether this node is our child
  if(parent == myaddr_) 
    child_flag = IS_CHILD;
  else if(action == GLOBAL_ADVERT && num_hops > vicinity_radius) 
  // The global LM may not be a potential child for us at any level if
  // it is farther away than the vicinity radius
    child_flag = NOT_POTL_CHILD;
  int ret_value = (*pcl2)->UpdatePotlChild(origin_id, next_hop, num_hops, level, num_children, energy, origin_time, child_flag, delete_flag,adv_tags);
  // Free packet and return if we have seen this packet before
  if(ret_value == OLD_MESSAGE && action != UNICAST_ADVERT_CHILD && action != UNICAST_ADVERT_PARENT) {
    if(num_potl_children) delete[] potl_children;
    if(num_lm_addrs) delete[] lm_addrs;
    if(num_advert_lm_addrs) delete[] advert_lm_addrs;
    // Free the tag list
    tag_ptr1 = adv_tags;
    while(tag_ptr1) {
      tag_ptr2 = tag_ptr1;
      tag_ptr1 = tag_ptr1->next_;
      delete tag_ptr2;
    }
    Packet::free(p);
    return;
  }
  
  // Send hierarchy advts if tag list has changed due to new child 
  // or change in the taglist of an old child
  if(ret_value == NEW_CHILD || ret_value == OLD_CHILD_TAGS_CHANGED)
    SendChangedTagListUpdate(0,level);
  
  
  //  if(level == highest_level_)
  //     num_resched_ = (*pcl2)->num_potl_children_ - 1;
  // If promotion timer is running, decrement by constant amount
  if((ret_value == NEW_ENTRY) && (level == highest_level_) && (action == PERIODIC_ADVERTS || action == UNICAST_ADVERT_CHILD || action == UNICAST_ADVERT_PARENT) && (num_hops < radius(level))) {
    // Promotion timer is running but is not in wait state
    if(promo_timer_running_ && !wait_state_) {
      double resched_time = promo_timeout_ - (now - promo_start_time_) - promo_timeout_decr_;
      if(resched_time < 0) resched_time = 0;
      //      trace("Node %d: Rescheduling timer in ProcessHierUpdate, now %f, st %f, decr %f, resch %fn", myaddr_, now, promo_start_time_, promo_timeout_decr_, resched_time);
      promo_timer_->resched(resched_time);
    }
  }
  // If our parent has demoted itself, we might have to start 
  // the election process again
  if(action == DEMOTION) {
    (*pcl1)->UpdatePotlParent(origin_id, next_hop, num_hops, level, num_children, energy, origin_time, TRUE);
    if(((*pcl1)->parent_ == NULL) && (!promo_timer_running_ || (promo_timer_running_ && wait_state_)) && (highest_level_ == level-1)) {
      //      if (debug_) printf("Node %d: sched timer in ProcessHierUpdaten",myaddr_);
      ParentChildrenList *tmp_pcl = parent_children_list_;
      while(tmp_pcl) {
	if(tmp_pcl->level_ == level) break;
	tmp_pcl = tmp_pcl->next_;
      }
      assert(tmp_pcl);
      
      num_resched_ = tmp_pcl->num_heard_ - 1;
      if(num_resched_) {
	// Cancel any timer running in wait state
	if(promo_timer_running_)
	  promo_timer_->cancel();
	promo_timer_running_ = 1;
	wait_state_ = 0;
	total_wait_time_ = 0;
	promo_timeout_ = random_timer(double(CONST_TIMEOUT + PROMO_TIMEOUT_MULTIPLES * radius(level) + MAX_TIMEOUT/((num_resched_+1) * pow(2,highest_level_+1))), be_random_);
	trace("Node %d: Promotion timeout after wait period in ProcessHierUpdate: %f", myaddr_,promo_timeout_);
	num_resched_ = 0;
	promo_start_time_ = s.clock();
	promo_timer_->resched(promo_timeout_);
      }
      else if(!promo_timer_running_) {
	double wait_time = PERIODIC_WAIT_TIME;
	promo_timer_running_ = 1;
	wait_state_ = 1;
	total_wait_time_ += wait_time;
	trace("Node %d: Entering wait state in ProcessHierUpdate because of no parent: %f", myaddr_,now);
	promo_timer_->resched(wait_time);
      }
    }
  }
  // If the advertising LM is a potl parent, add to level-1 
  // ParentChildrenList object
  else if(potl_parent_flag) {
    LMNode *old_parent = (*pcl1)->parent_;
    (*pcl1)->UpdatePotlParent(origin_id, next_hop, num_hops, level, num_children, energy, origin_time, FALSE);
    // If we receive this message from a parent at some level, update
    // the assigned addresses
    if((((*pcl1)->parent_)->id_ == origin_id) && (level-1 == highest_level_)) {
      //      if(num_lm_addrs) 
      //	trace("Node %d: Rcvd higher level lm addr from %d at time %f",myaddr_,origin_id,now);
      //      else
      //	trace("Node %d: Rcvd higher level lm addr msg with no addrs from %d at time %f",myaddr_,origin_id,now);
      ((*pcl1)->mylmaddrs_)->delete_lm_addrs();
      assign_lmaddress(lm_addrs, num_lm_addrs, (*pcl1)->level_);
    }
    // Check if parent has changed
    int new_advert = 0;
    // The first condition may arise if the old parent obj is deleted ... (?)
    if((*pcl1)->parent_ == old_parent && old_parent) {
      if(((*pcl1)->parent_)->id_ != old_parent->id_)
	new_advert = 1;
    }
    else if((*pcl1)->parent_ != old_parent && (*pcl1)->parent_ && old_parent) {
      if(((*pcl1)->parent_)->id_ != old_parent->id_)
	new_advert = 1;
    }
    else if((*pcl1)->parent_ != old_parent)
      new_advert = 1;
    
    // Trigger advertisement if parent has changed
    if(new_advert && (level-1 <= highest_level_)) {
      newp = makeUpdate((*pcl1), HIER_ADVS, PERIODIC_ADVERTS);
      s.schedule(target_,newp,0);
      (*pcl1)->last_update_sent_ = now;
    }
  // If a parent has been selected for highest_level_, cancel promotion timer
  // (for promotion to highest_level_+1) if it's running
    if((level == (highest_level_ + 1)) && ((*pcl1)->parent_ != NULL)) {
      if(promo_timer_running_ && !wait_state_) {
	trace("Node %d: Promotion timer cancelled at time %f in ProcessHierUpdaten",myaddr_,s.clock());
	promo_timer_->cancel();
	total_wait_time_ = 0;
	wait_state_ = 1;
	double wait_time = PERIODIC_WAIT_TIME;
	total_wait_time_ += wait_time;
	promo_timer_->sched(wait_time);
      }
    }
    else if(level > 0 && level == highest_level_) {
      // Check if the potl parent for highest_level_-1 that we see covers our
      // potential children. If so, we can demote ourselves and cancel our 
      // current promotion timer
      pcl = &parent_children_list_;
      while((*pcl) != NULL) {
	if((*pcl)->level_ == level) {
	  break;
	}
	pcl = &((*pcl)->next_);
      }
      assert(*pcl);
      LMNode *lm = (*pcl)->pchildren_;
      int is_subset = TRUE;
      if((*pcl)->num_potl_children_ > num_potl_children) {
	is_subset = FALSE;
	lm = NULL;
      }
      int is_element = FALSE;
      while(lm) {
	is_element = FALSE;
	for(i = 0; i < num_potl_children; ++i) 
	  if(lm->id_ == potl_children[i] && lm->child_flag_ != NOT_POTL_CHILD) {
	    is_element = TRUE;
	    break;
	  }
	if(is_element == FALSE && lm->child_flag_ != NOT_POTL_CHILD) {
	  is_subset = FALSE;
	  break;
	}
	lm = lm->next_;
      }
      // Demotion process
      if(is_subset == TRUE) {
    	--(highest_level_);
    	delete_flag = TRUE;
	if((*pcl1)->parent_)
	  trace("Node %d: Num potl ch %d, Node %d: Num potl ch %d, time %d",myaddr_, (*pcl)->num_potl_children_,origin_id,num_potl_children,(int)now);
	trace("Node %d: Parent before demotion: %d, msg from %d at time %f",myaddr_, ((*pcl1)->parent_)->id_,origin_id,now);
	
	int upd_time = (int)now;
	upd_time = (upd_time << 16) | ((*pcl1)->seqnum_ & 0xFFFF);
	++((*pcl1)->seqnum_);
	(*pcl1)->UpdatePotlParent(myaddr_, 0, 0, 0, 0, 0, upd_time, delete_flag);
	if((*pcl1)->parent_)
	  trace("Node %d: Parent after demotion: %d",myaddr_, ((*pcl1)->parent_)->id_);
	upd_time = (int) now;
	upd_time = (upd_time << 16) | ((*pcl2)->seqnum_ & 0xFFFF);
	++((*pcl2)->seqnum_);
    	(*pcl2)->UpdatePotlChild(myaddr_, 0, 0, 0, 0, 0, upd_time, IS_CHILD, delete_flag,NULL);
	// Send out demotion messages
	newp = makeUpdate(*pcl, HIER_ADVS, DEMOTION);
	s.schedule(target_, newp, 0);
    	if(promo_timer_running_ && !wait_state_) {
    	  trace("Node %d: Promotion timer cancelled due to demotion at time %dn",myaddr_,(int)now);
    	  promo_timer_->cancel();
	  total_wait_time_ = 0;
	  wait_state_ = 1;
	  double wait_time = PERIODIC_WAIT_TIME;
	  total_wait_time_ += wait_time;
	  promo_timer_->sched(wait_time);
    	}
      }
    }      
  }
  // If new entry, flood advertisements for level > adv LM's level
  if(ret_value == NEW_ENTRY) {
    ParentChildrenList *tmp_pcl = parent_children_list_;
    while(tmp_pcl) {
      // New nodes should have an initial wait time of atleast 0.1 seconds
      if(tmp_pcl->level_ <= highest_level_ && tmp_pcl->level_ >= level && (now - tmp_pcl->last_update_sent_) > 0.1) {
	newp = makeUpdate(tmp_pcl, HIER_ADVS, PERIODIC_ADVERTS);
	s.schedule(target_,newp,0);
	tmp_pcl->last_update_sent_ = now;
      }
      tmp_pcl = tmp_pcl->next_;
    }
  }
  if(num_potl_children) delete[] potl_children;
  if(num_lm_addrs) delete[] lm_addrs;
  if(num_advert_lm_addrs) delete[] advert_lm_addrs;
  // Delete tag list
  tag_ptr1 = adv_tags;
  while(tag_ptr1) {
    tag_ptr2 = tag_ptr1;
    tag_ptr1 = tag_ptr1->next_;
    delete tag_ptr2;
  }
  
  // Do not forward demotion message if we have seen this message before
  if(action == DEMOTION) {
    //    if(myaddr_ == 30)
    //      printf("Am heren");
    if(CheckDemotionMsg(origin_id, level, (int)origin_time) == OLD_MESSAGE) {
      Packet::free(p);
      return;
    }
  }
  // Do not forward packet if ttl is lower unless the packet is from the global
  // LM in which case the packet needs to be flooded throughout the network
  if(--iph->ttl_ == 0 && action != GLOBAL_ADVERT) {
    //    drop(p, DROP_RTR_TTL);
    Packet::free(p);
    return;
  }
  // Do not forward if the advertisement is for this node
  if((iph->daddr() >> 8) == myaddr_) {
    //    trace("Node %d: Received unicast advert from %d at level %d for us at time %f",myaddr_,iph->saddr(),level,now);
    Packet::free(p);
    return;
  }
  if(action == UNICAST_ADVERT_CHILD) {
    hdrc->next_hop() = get_next_hop(iph->daddr(),level);
    //    if(myaddr_ == 153)
    //      trace("Node %d: Received child unicast advert from %d to %d at level %d at time %f, next hop %d",myaddr_,iph->saddr(),iph->daddr(),level,now,hdrc->next_hop());
  }
  else if(action == UNICAST_ADVERT_PARENT) {
    //    trace("Node %d: Received parent unicast advert from %d to %d at level %d at time %f",myaddr_,iph->saddr(),iph->daddr(),level,now);
    hdrc->next_hop() = get_next_hop(iph->daddr(),level+2);
  }
  
  assert(hdrc->next_hop() != NO_NEXT_HOP);
  //  if(now > 412.5) {
  //    purify_printf("ProcessHierUpdate2n");
  //    purify_new_leaks();
  //  }
  // Need to send the packet down the stack
  hdrc->direction() = hdr_cmn::DOWN;
  
  //  if(debug_) printf("Node %d: Forwarding Hierarchy Update Packet", myaddr_);
  s.schedule(target_, p, 0);
}
  
void
LandmarkAgent::assign_lmaddress(int64_t *lmaddr, int num_lm_addrs, int root_level)
{
  ParentChildrenList *tmp_pcl, *cur_pcl = NULL, *child_pcl = NULL;
  ParentChildrenList *parent_pcl = NULL;
  LMNode *pchild;
  int i;  
  int level = root_level;
  //  assert(root_level != 0);
  
  while(level >= 0) {
    tmp_pcl = parent_children_list_;
    while(tmp_pcl) {
      if(tmp_pcl->level_ == level)
	cur_pcl = tmp_pcl;
      if(tmp_pcl->level_ == (level-1))
	child_pcl = tmp_pcl;
      if(tmp_pcl->level_ == (level+1))
	parent_pcl = tmp_pcl;
      tmp_pcl = tmp_pcl->next_;
    }
    
    assert(cur_pcl);
    if(level) assert(child_pcl);
    assert(parent_pcl);
    // Update LM address at the appropriate level
    if(level == root_level) {
      (cur_pcl->mylmaddrs_)->delete_lm_addrs();
      if(num_lm_addrs) {
	for(i = 0; i < num_lm_addrs; ++i) {
	  (cur_pcl->mylmaddrs_)->add_lm_addr(lmaddr[i]);
	}
	parent_pcl->UpdateChildLMAddr(myaddr_,num_lm_addrs,lmaddr);
      }
    }
    
    int num_addrs = 0;
    int64_t *assigned_addrs = NULL;
    (cur_pcl->mylmaddrs_)->get_lm_addrs(&num_addrs,&assigned_addrs);
    if(num_addrs == 0) {
      pchild = cur_pcl->pchildren_;
      while(pchild) {
	if(pchild->child_flag_ == IS_CHILD) {
	  (pchild->lmaddr_)->delete_lm_addrs();
	  if(pchild->id_ == myaddr_ && level)
	      (child_pcl->mylmaddrs_)->delete_lm_addrs();
	}
	pchild = pchild->next_;
      }
    }
    else if(cur_pcl->num_children_) {
      // ID at a particular level starts from 1
      for(i = 0; i < num_addrs; ++i) {
	int64_t j = 1;
	int64_t addr = assigned_addrs[i] + (j << ((cur_pcl->level_-1)*8));
	// Assign addresses to child nodes
	
	//	while( j <= MAX_CHILDREN) {
	pchild = cur_pcl->pchildren_;
	assert(cur_pcl->num_children_ <= MAX_CHILDREN);
	
	while(pchild) {
	  if(pchild->child_flag_ == IS_CHILD) {
	    (pchild->lmaddr_)->delete_lm_addrs();
	    (pchild->lmaddr_)->add_lm_addr(addr);
	    if(pchild->id_ == myaddr_ && level) {
	      (child_pcl->mylmaddrs_)->delete_lm_addrs();
	      (child_pcl->mylmaddrs_)->add_lm_addr(addr);
	    }
	    ++j;
	    addr = assigned_addrs[i] + (j << ((cur_pcl->level_-1)*8));
	    //	    if(j > MAX_CHILDREN) break;
	    assert(j <= MAX_CHILDREN);
	  } /* if */
	  pchild = pchild->next_;
	  //	  }/* while */
	}
      }
    }
    if(num_addrs) delete[] assigned_addrs;
    --level;
  }
}
void
LandmarkAgent::periodic_callback(Event *e, int level)
{
  //  if(debug_) printf("Periodic Callback for level %d", level);
  Scheduler &s = Scheduler::instance();
  double now = Scheduler::instance().clock(), next_update_delay;
  int energy = (int)(node_->energy());
  int unicast_flag = FALSE, suppress_flag = FALSE;
  Packet *newp;
  hdr_ip *iph, *new_iph;
  hdr_cmn *cmh, *new_cmh;
  int action = PERIODIC_ADVERTS, parent_changed = 0, child_changed = 0;
  int upd_time = (int) now;
  //  if(now > 412.5) {
  //    purify_printf("periodic_callback1: %f,%dn",now,myaddr_);
  //    purify_new_leaks();
  //  }
  //  if(myaddr_ == 12 && now > 402)
  //    purify_new_leaks();
  // Should always have atleast the level 0 object
  assert(parent_children_list_ != NULL); 
  ParentChildrenList *pcl = parent_children_list_;
  ParentChildrenList *cur_pcl = NULL;
  ParentChildrenList *new_pcl = NULL;
  ParentChildrenList *pcl1 = NULL;
  ParentChildrenList *pcl2 = NULL;
  // return if we have been demoted from this level
  if(highest_level_ < level) 
    return; 
  
  while(pcl != NULL) {
    new_pcl = pcl;
    if(pcl->level_ == level){
      cur_pcl = pcl;
    }
    if(pcl->level_ == (level - 1)){
      pcl1 = pcl;
    }
    if(pcl->level_ == (level + 1)){
      pcl2 = pcl;
    }
    pcl = pcl->next_;
  }
  
  assert(cur_pcl);
  if(level)
    assert(pcl1);
  // Create level+1 object if it doesnt exist
  if(!pcl2) {
    new_pcl->next_ = new ParentChildrenList(level+1, this);
    pcl2 = new_pcl->next_;
  }
  assert(pcl2);
  // Delete stale potential parent entries
  LMNode *lmnode = cur_pcl->pparent_;
  LMNode *tmp_lmnode;
  int delete_flag = TRUE;
  LMNode *old_parent = cur_pcl->parent_;
  while(lmnode) {
    // Record next entry in linked list incase the current element is deleted
    tmp_lmnode = lmnode->next_;
    if(((now - lmnode->last_update_rcvd_) > cur_pcl->update_timeout_)) {
      //      if(debug_) trace("Node %d: Deleting stale entry for %d at time %d",myaddr_,lmnode->id_,(int)now);
      upd_time = (int) now;
      upd_time = (upd_time << 16) | ((lmnode->last_upd_seqnum_ + 1) & 0xFFFF);
      cur_pcl->UpdatePotlParent(lmnode->id_, 0, 0, 0, 0, 0, upd_time, delete_flag);
    }
    lmnode = tmp_lmnode;
  }
  
  // The first condition may arise if the old parent obj is deleted ... (?)
  if(cur_pcl->parent_ == old_parent && old_parent) {
    if((cur_pcl->parent_)->id_ != old_parent->id_)
      parent_changed = 1;
  }
  else if(cur_pcl->parent_ != old_parent && cur_pcl->parent_ && old_parent) {
    if((cur_pcl->parent_)->id_ != old_parent->id_)
      parent_changed = 1;
  }
  else if(cur_pcl->parent_ != old_parent)
    parent_changed = 1;
  
  // Delete stale potential children entries
  lmnode = cur_pcl->pchildren_;
  delete_flag = TRUE;
  int demotion = FALSE;
  while(lmnode) {
    // Record next entry in linked list incase the current element is deleted
    tmp_lmnode = lmnode->next_;
    if((now - lmnode->last_update_rcvd_) > cur_pcl->update_timeout_) {
      if(lmnode->child_flag_ == IS_CHILD)
	child_changed = 1;
      assert(level && lmnode->id_ != myaddr_);
      upd_time = (int) now;
      upd_time = (upd_time << 16) | ((lmnode->last_upd_seqnum_ + 1) & 0xFFFF);
      cur_pcl->UpdatePotlChild(lmnode->id_, 0, 0, 0, 0, 0, upd_time, lmnode->child_flag_, delete_flag,NULL);
    }
    lmnode = tmp_lmnode;
  }
  
  // Send updates if tag list has changed i.e., when a child has changed
  if(child_changed)
    SendChangedTagListUpdate(0,level-1);
  
  // Demote ourself if any child's energy > 30 % of our energy
  if(demotion) {
    trace("Node %d: Demotion due to lesser energy than child",myaddr_);
    highest_level_ = level - 1;
    Packet *p = makeUpdate(cur_pcl, HIER_ADVS, DEMOTION);
    s.schedule(target_, p, 0);
  }
  // Check if a parent exists after updating potl parents. If not, start
  // promotion timer.
  // A LM at level 3 is also at levels 0, 1 and 2. For each of these levels,
  // the LM designates itself as parent. At any given instant, only the 
  // level 3 (i.e., highest_level_) LM may not have a parent and may need to 
  // promote itself. But if the promotion timer is running, then the election
  // process for the next level has already begun.
  if(parent_changed && (cur_pcl->parent_ == NULL) && !demotion) {
    // Cancel any promotion timer that is running for promotion from a higher 
    // level and send out demotion messages
    if(promo_timer_running_ && level <= highest_level_) {
      wait_state_ = 0;
      total_wait_time_ = 0;
      promo_timer_running_ = 0;
      promo_timer_->cancel();
    }
    num_resched_ = pcl2->num_heard_ - 1;
    if(num_resched_) {
      promo_timer_running_ = 1;
      wait_state_ = 0;
      total_wait_time_ = 0;
      promo_timeout_ = random_timer(double(CONST_TIMEOUT + PROMO_TIMEOUT_MULTIPLES * radius(level+1) + MAX_TIMEOUT/((num_resched_+1) * pow(2,highest_level_+1))), be_random_);
      trace("Node %d: Promotion timeout after wait period in periodic_callback: %f", myaddr_,promo_timeout_);
      num_resched_ = 0;
      promo_start_time_ = s.clock();
      promo_timer_->resched(promo_timeout_);
    }
    else {
      double wait_time = PERIODIC_WAIT_TIME;
      promo_timer_running_ = 1;
      wait_state_ = 1;
      total_wait_time_ += wait_time;
      //	trace("Node %d: Entering wait period in periodic_callback at time %f", myaddr_,now);
      promo_timer_->resched(wait_time);
    }
  }
  // Update ourself as potential child and parent for appropriate levels
  // in our hierarchy tables
  if(!demotion) {
    if(level) {
      upd_time = (int) now;
      upd_time = (upd_time << 16) | (pcl1->seqnum_ & 0xFFFF);
      ++(pcl1->seqnum_);
      pcl1->UpdatePotlParent(myaddr_, myaddr_, 0, level, cur_pcl->num_children_, energy, upd_time, FALSE);
    }
    upd_time = (int) now;
    upd_time = (upd_time << 16) | (pcl2->seqnum_ & 0xFFFF);
    ++(pcl2->seqnum_);
    pcl2->UpdatePotlChild(myaddr_, myaddr_, 0, level, cur_pcl->num_children_, energy, upd_time, IS_CHILD, FALSE,cur_pcl->tag_list_);
  }
  
  // Check if this is the root node. If so, set the unicast flag or suppress
  // flag when no changes occur for 3 times the update period
  // If this is a lower level node that has a parent, either suppress 
  // (for hard-state case) or unicast maintenance messages
  if(!(cur_pcl->parent_) && (total_wait_time_ >= (2*PERIODIC_WAIT_TIME)) && wait_state_) {
    if(adverts_type_ == UNICAST) {
      unicast_flag = TRUE;
    }
    else if(adverts_type_ == SUPPRESS) {
      suppress_flag = TRUE;
    }
    
    // Start assigning landmark addresses to child nodes; 
    // Shift 1, number of levels * 8 times to left for address of root node
    int64_t *lmaddr = new int64_t[1];
    lmaddr[0] = 1;
    lmaddr[0] = (lmaddr[0] << (cur_pcl->level_ * 8));
    int num_lm_addrs = 1;
    assign_lmaddress(lmaddr, num_lm_addrs, cur_pcl->level_);
    // The advertisements from the root LM need to be broadcast in the hash
    // scheme
    delete[] lmaddr;
    if(global_lm_)
      action = GLOBAL_ADVERT;
  }
  else if(cur_pcl->parent_) {
    if(adverts_type_ == UNICAST) {
      unicast_flag = TRUE;
    }
    else if(adverts_type_ == SUPPRESS) {
      suppress_flag = TRUE;
    }
  } 
  
  //  if(!demotion && (now - cur_pcl->last_update_sent_ >= cur_pcl->update_period_) && !suppress_flag) 
  if(!demotion && !suppress_flag) {
    //    trace("Node %d: Sending update at time %f",myaddr_,now);
    Packet *p = makeUpdate(cur_pcl, HIER_ADVS, action);
    unsigned char *walk;
    if(unicast_flag) {
      if(level) {
	// Unicast updates to parent and children for level > 0
	lmnode = cur_pcl->pchildren_;
	while(lmnode) {
	  if(lmnode->id_ != myaddr_) {
	    newp = p->copy();
	    new_iph = HDR_IP(newp);
	    new_cmh = HDR_CMN(newp);
	    walk = newp->accessdata();
	    //    trace("Node %d: Generating unicast advert to child %d at time %f with next hop %d",myaddr_,lmnode->id_,now,lmnode->next_hop_);
	    
	    new_iph->daddr() = lmnode->id_ << 8;
	    new_iph->dport() = ROUTER_PORT;
	    new_cmh->next_hop() = lmnode->next_hop_;
	    new_cmh->addr_type() = NS_AF_INET;
	    if(cur_pcl->level_)
	      new_cmh->size() = new_cmh->size() - 4 * (cur_pcl->num_potl_children_ - 1);
	    (*walk) = (UNICAST_ADVERT_CHILD) & 0xFF;
	    walk++;
	    int num_addrs = (*walk);
	    walk += (10 + 8*num_addrs);
	    
	    // Update seqnum field for each packet; Otherwise subsequent 
            // (to first) messages would be dropped by intermediate nodes
	    (*walk++) = (cur_pcl->seqnum_ >> 24) & 0xFF;
	    (*walk++) = (cur_pcl->seqnum_ >> 16) & 0xFF;
	    (*walk++) = (cur_pcl->seqnum_ >> 8) & 0xFF;
	    (*walk++) = (cur_pcl->seqnum_) & 0xFF;
	    ++(cur_pcl->seqnum_);
	    
	    s.schedule(target_,newp,0);
	  }
	  lmnode = lmnode->next_;
	}
      }
      if(cur_pcl->parent_) {
	if((cur_pcl->parent_)->id_ != myaddr_) {
	  iph = HDR_IP(p);
	  cmh = HDR_CMN(p);
	  walk = p->accessdata();
	  
	  //	  trace("Node %d: Generating unicast advert to parent %d at time %f with next hop %d",myaddr_,cur_pcl->parent_->id_,now,(cur_pcl->parent_)->next_hop_);
	  iph->daddr() = (cur_pcl->parent_)->id_;
	  iph->dport() = ROUTER_PORT;
	  cmh->next_hop() = (cur_pcl->parent_)->next_hop_;
	  cmh->addr_type() = NS_AF_INET;
	  cmh->size() = cmh->size() - 4 * (cur_pcl->num_potl_children_);
	  
	  (*walk) = (UNICAST_ADVERT_PARENT) & 0xFF;
	  walk++;
	  int num_addrs = (*walk);
	  walk += (10 + 8*num_addrs);
	  // Update seqnum field for each packet; Otherwise subsequent 
	  // (to first) messages would be dropped by intermediate nodes
	  (*walk++) = (cur_pcl->seqnum_ >> 24) & 0xFF;
	  (*walk++) = (cur_pcl->seqnum_ >> 16) & 0xFF;
	  (*walk++) = (cur_pcl->seqnum_ >> 8) & 0xFF;
	  (*walk++) = (cur_pcl->seqnum_) & 0xFF;
	  ++(cur_pcl->seqnum_);
	  
	  s.schedule(target_,p,0);
	}
	else 
	  Packet::free(p);
      }
      else
	Packet::free(p);
    }
    else {
      //      trace("Node %d: Generating update msg at time %f",myaddr_,now);
      s.schedule(target_, p, 0);
    }
    cur_pcl->last_update_sent_ = now;
  }
  // Schedule next update 
  if(cur_pcl->last_update_sent_ == now || suppress_flag)
    next_update_delay = cur_pcl->update_period_ + jitter(LM_STARTUP_JITTER, be_random_);
  else
    next_update_delay = cur_pcl->update_period_ - (now - cur_pcl->last_update_sent_) + jitter(LM_STARTUP_JITTER, be_random_);
  
  if(!demotion)
    s.schedule(cur_pcl->periodic_handler_, cur_pcl->periodic_update_event_, next_update_delay);
  //  if(now > 412.5) {
  //    purify_printf("periodic_callback2: %f,%dn",now,myaddr_);
  //    purify_new_leaks();
  //  }
  //  if(myaddr_ == 12 && now > 402)
  //    purify_new_leaks();
  // Update entries for levels greater than our highest level in our
  // highest_level_ periodic_callback event
  if(level == highest_level_) {
    cur_pcl = parent_children_list_;
    while(cur_pcl) {
      if(cur_pcl->level_ > highest_level_) {
	lmnode = cur_pcl->pparent_;
	delete_flag = TRUE;
	while(lmnode) {
	  
	  // Update potential parent list
	  // Record next entry in list incase current element is deleted
	  tmp_lmnode = lmnode->next_;
	  if(((now - lmnode->last_update_rcvd_) > cur_pcl->update_timeout_)) {
	    //      if(debug_) trace("Node %d: Deleting stale entry for %d at time %d",myaddr_,lmnode->id_,(int)now);
	    upd_time = (int) now;
	    upd_time = (upd_time << 16) | ((lmnode->last_upd_seqnum_+1) & 0xFFFF);
	    cur_pcl->UpdatePotlParent(lmnode->id_, 0, 0, 0, 0, 0, upd_time, delete_flag);
	  }
	  lmnode = tmp_lmnode;
	}
	
	// Update children list
	lmnode = cur_pcl->pchildren_;
	while(lmnode) {
	  // Record next entry in list incase current element is deleted
	  tmp_lmnode = lmnode->next_;
	  if((now - lmnode->last_update_rcvd_) > cur_pcl->update_timeout_) {
	    upd_time = (int) now;
	    upd_time = (upd_time << 16) | ((lmnode->last_upd_seqnum_+1) & 0xFFFF);
	    // Check if global LM entry is being deleted; Global LM at level i
	    // will have entry in level i+1 pcl object
	    if(cur_pcl->level_ == global_lm_level_+1 && lmnode->id_ == global_lm_id_) {
	      global_lm_level_ = -1;
	      global_lm_id_ = NO_GLOBAL_LM;
	    }
	    cur_pcl->UpdatePotlChild(lmnode->id_, 0, 0, 0, 0, 0, upd_time, lmnode->child_flag_, delete_flag,NULL);
	  }
	  lmnode = tmp_lmnode;
	}
      }
      cur_pcl = cur_pcl->next_;
    }
  }
}
Packet *
LandmarkAgent::makeUpdate(ParentChildrenList *pcl, int pkt_type, int action)
{
  Packet *p = allocpkt();
  hdr_ip *iph = HDR_IP(p);
  hdr_cmn *hdrc = HDR_CMN(p);
  unsigned char *walk;
  compr_taglist *adv_tags = NULL;
  double now = Scheduler::instance().clock();
  int64_t *lmaddrs;
  int num_lm_addrs = 0;
  hdrc->next_hop_ = IP_BROADCAST; // need to broadcast packet
  hdrc->addr_type_ = NS_AF_INET;
  iph->daddr() = IP_BROADCAST;  // packet needs to be broadcast
  iph->dport() = ROUTER_PORT;
  iph->ttl_ = radius(pcl->level_);
  iph->saddr() = myaddr_;
  iph->sport() = ROUTER_PORT;
  if(action == GLOBAL_ADVERT)
    trace("Node %d: Generating global LM message at time %f",myaddr_,now);
  assert(pcl->num_tags_ >= 0);
  if(pkt_type == HIER_ADVS) {
    
    if(pcl->level_ == 0) {
      // A level 0 node cannot be demoted!
      assert(action != DEMOTION);
      // No children for level 0 LM
      // totally 12 bytes in packet for now; need to add our energy level later
      // each tag name is 4 bytes; 2 bytes for num_tags info
      // Landmark address; 1 byte to indicate #addrs and 8 bytes for each addr
      lmaddrs = NULL;
      num_lm_addrs = 0;
      (pcl->mylmaddrs_)->get_lm_addrs(&num_lm_addrs, &lmaddrs);
      p->allocdata(12 + (4 * pcl->num_tags_) + 2 + 4 + 1 + (8*num_lm_addrs)); 
      walk = p->accessdata();
      // Packet type; 1 byte
      (*walk++) = (action) & 0xFF;
      // Landmark address; 1 byte to indicate #addrs and 8 bytes for each addr
      (*walk++) = (num_lm_addrs) & 0xFF;
      //      if(num_lm_addrs)
      //	trace("Num_lm_addrs = %d",num_lm_addrs);
      for(int i = 0; i < num_lm_addrs; ++i) {
	// Landmark address of node
	(*walk++) = (lmaddrs[i] >> 56) & 0xFF;
	(*walk++) = (lmaddrs[i] >> 48) & 0xFF;
	(*walk++) = (lmaddrs[i] >> 40) & 0xFF;
	(*walk++) = (lmaddrs[i] >> 32) & 0xFF;
	(*walk++) = (lmaddrs[i] >> 24) & 0xFF;
	(*walk++) = (lmaddrs[i] >> 16) & 0xFF;
	(*walk++) = (lmaddrs[i] >> 8) & 0xFF;
	(*walk++) = (lmaddrs[i]) & 0xFF;
      }
      if(num_lm_addrs) 
	delete[] lmaddrs;
      // level of LM advertisement; 1 byte
      (*walk++) = (pcl->level_) & 0xFF;
      // Our energy level; 4 bytes (just integer portion)
      int energy = (int)(node_->energy());
      (*walk++) = (energy >> 24) & 0xFF;
      (*walk++) = (energy >> 16) & 0xFF;
      (*walk++) = (energy >> 8) & 0xFF;
      (*walk++) = (energy) & 0xFF;
      // make ourselves as next hop; 2 bytes
      (*walk++) = (myaddr_ >> 8) & 0xFF;
      (*walk++) = (myaddr_) & 0xFF;
      // Vicinity size in number of hops; Carrying this information allows
      // different LMs at same level to have different vicinity radii; 2 bytes
      (*walk++) = (radius(pcl->level_) >> 8) & 0xFF;
      (*walk++) = (radius(pcl->level_)) & 0xFF;
      // Time at which packet was originated;
      // 3 bytes for integer portion of time and 1 byte for fraction
      // Note that we probably need both an origin_time and sequence number
      // field to distinguish between msgs generated at same time.
      // (origin_time required to discard old state when net dynamics present)
      int origin_time = (int)now;
      (*walk++) = (origin_time >> 8) & 0xFF;
      (*walk++) = (origin_time) & 0xFF;
      (*walk++) = (pcl->seqnum_ >> 8) & 0xFF;
      (*walk++) = (pcl->seqnum_) & 0xFF;
      ++(pcl->seqnum_);
      // Parent ID; 2 bytes
      if(pcl->parent_ == NULL) {
	(*walk++) = (NO_PARENT >> 8) & 0xFF;
	(*walk++) = (NO_PARENT) & 0xFF;
      }
      else {
	(*walk++) = ((pcl->parent_)->id_ >> 8) & 0xFF;
	(*walk++) = ((pcl->parent_)->id_) & 0xFF;
      }
      (*walk++) = (pcl->num_tags_ >> 8) & 0xFF;
      (*walk++) = (pcl->num_tags_) & 0xFF;
      if(pcl->num_tags_) {
	adv_tags = pcl->tag_list_;
	while(adv_tags) {
	  (*walk++) = (adv_tags->obj_name_ >> 24) & 0xFF;
	  (*walk++) = (adv_tags->obj_name_ >> 16) & 0xFF;
      	  (*walk++) = (adv_tags->obj_name_ >> 8) & 0xFF;
	  (*walk++) = (adv_tags->obj_name_) & 0xFF;
	  adv_tags = adv_tags->next_;
	}
      }
      // In real life each of the above fields would be 
      // 4 byte integers; 20 bytes for IP addr + 2 bytes for num_children
      // 4 byte for number of tags; 4 byte for each tag name; 4 byte for energy
      hdrc->size_ = 20 + 20 + 4 + (4 * pcl->num_tags_) + 4 + 1 + (8*num_lm_addrs); 
    }
    else {
      // Need to list all the potential children LMs
      // Pkt size: 12 bytes (as before); 2 each for number of children 
      // and potl_children; 
      // 2 byte for each child's id + 8 bytes for landmark address
      // 4 bytes for each tag name; 2 bytes for num_tags info
      int pkt_size = 0;
      lmaddrs = NULL;
      num_lm_addrs = 0;
      if(action == PERIODIC_ADVERTS || action == GLOBAL_ADVERT) {
	LMNode *pch = pcl->pchildren_;
	// Compute number of landmark addrs of children for pkt size calc
	int size = 0;
	while(pch) {
	  int64_t *addrs;
	  int num_addrs = 0;
	  (pch->lmaddr_)->get_lm_addrs(&num_addrs,&addrs);
	  if(num_addrs) delete[] addrs;
	  size += (1 + num_addrs*8);
	  pch = pch->next_;
	}
	// Compute number of landmark addrs of this node for pkt size calc
	// Landmark address; 1 byte to indicate #addrs and 8 bytes for each 
	// addr
	(pcl->mylmaddrs_)->get_lm_addrs(&num_lm_addrs, &lmaddrs);
	pkt_size = 12 + 4 + (2 * pcl->num_potl_children_) + size + (4 * pcl->num_tags_) + 2 + 4 + 1 + (8*num_lm_addrs);
      }
      else
	pkt_size = 17; // Demotion message
      p->allocdata(pkt_size);
      walk = p->accessdata();
      // Packet type; 1 byte
      (*walk++) = (action) & 0xFF;
      //      if(myaddr_ == 0)
      //	trace("Node 0: Generating update message for level %d at time %f, num_lm_addrs %d",pcl->level_,now,num_lm_addrs);
      // Landmark address; 1 byte to indicate #addrs and 8 bytes for each addr
      (*walk++) = (num_lm_addrs) & 0xFF;
      for(int i = 0; i < num_lm_addrs; ++i) {
	// Landmark address of node
	(*walk++) = (lmaddrs[i] >> 56) & 0xFF;
	(*walk++) = (lmaddrs[i] >> 48) & 0xFF;
	(*walk++) = (lmaddrs[i] >> 40) & 0xFF;
	(*walk++) = (lmaddrs[i] >> 32) & 0xFF;
	(*walk++) = (lmaddrs[i] >> 24) & 0xFF;
	(*walk++) = (lmaddrs[i] >> 16) & 0xFF;
	(*walk++) = (lmaddrs[i] >> 8) & 0xFF;
	(*walk++) = (lmaddrs[i]) & 0xFF;
      }
      if(num_lm_addrs) 
	delete[] lmaddrs;
      
      // level of LM advertisement; 1 byte
      (*walk++) = (pcl->level_) & 0xFF;
      // Our energy level; 4 bytes (just integer portion)
      int energy = (int)(node_->energy());
      (*walk++) = (energy >> 24) & 0xFF;
      (*walk++) = (energy >> 16) & 0xFF;
      (*walk++) = (energy >> 8) & 0xFF;
      (*walk++) = (energy) & 0xFF;
      // make ourselves as next hop; 2 bytes
      (*walk++) = (myaddr_ >> 8) & 0xFF;
      (*walk++) = (myaddr_) & 0xFF;
      // Vicinity size in number of hops; 2 bytes
      (*walk++) = (radius(pcl->level_) >> 8) & 0xFF;
      (*walk++) = (radius(pcl->level_)) & 0xFF;
      // Time at which packet was originated;
      // 3 bytes for integer portion of time and 1 byte for fraction
      int origin_time = (int)now;
      (*walk++) = (origin_time >> 8) & 0xFF;
      (*walk++) = (origin_time) & 0xFF;
      (*walk++) = (pcl->seqnum_ >> 8) & 0xFF;
      (*walk++) = (pcl->seqnum_) & 0xFF;
      ++(pcl->seqnum_);
      if(origin_time > now) {
	printf("Node %d: id %d, level %d, vicinity_radius %d",myaddr_,myaddr_,pcl->level_,radius(pcl->level_));
	assert(origin_time < now);
      }
      // Parent's id; 2 bytes
      if(pcl->parent_ == NULL) {
	(*walk++) = (NO_PARENT >> 8) & 0xFF;
	(*walk++) = (NO_PARENT) & 0xFF;
      }
      else {
	(*walk++) = ((pcl->parent_)->id_ >> 8) & 0xFF;
	(*walk++) = ((pcl->parent_)->id_) & 0xFF;
      }
      
      if(action == PERIODIC_ADVERTS || action == GLOBAL_ADVERT) {
	// Number of children; 2 bytes
	(*walk++) = (pcl->num_children_ >> 8) & 0xFF;
	(*walk++) = (pcl->num_children_) & 0xFF;
	
	// Number of potential children; 2 bytes
	(*walk++) = (pcl->num_potl_children_ >> 8) & 0xFF;
	(*walk++) = (pcl->num_potl_children_) & 0xFF;
	
	LMNode *potl_ch = pcl->pchildren_;
	while(potl_ch) {
	  if(potl_ch->child_flag_ != NOT_POTL_CHILD) {
	    (*walk++) = (potl_ch->id_ >> 8) & 0xFF;
	    (*walk++) = (potl_ch->id_) & 0xFF;
	    int64_t *addrs = NULL;
	    int num_addrs = 0;
	    ((potl_ch)->lmaddr_)->get_lm_addrs(&num_addrs, &addrs);
	    //	    if(myaddr_ == 0 && now > 1000)
	    //	      trace("Node 0: Child %d, num_addrs: %d at time %f",potl_ch->id_,num_addrs,now);
	    // Number of landmark addrs
	    (*walk++) = (num_addrs) & 0xFF;
	    for(int i = 0; i < num_addrs; ++i) {
	      // Landmark address of node
	      (*walk++) = (addrs[i] >> 56) & 0xFF;
	      (*walk++) = (addrs[i] >> 48) & 0xFF;
	      (*walk++) = (addrs[i] >> 40) & 0xFF;
	      (*walk++) = (addrs[i] >> 32) & 0xFF;
	      (*walk++) = (addrs[i] >> 24) & 0xFF;
	      (*walk++) = (addrs[i] >> 16) & 0xFF;
	      (*walk++) = (addrs[i] >> 8) & 0xFF;
	      (*walk++) = (addrs[i]) & 0xFF;
	    }
	    if(num_addrs) 
	      delete[] addrs;
	  }
	  potl_ch = potl_ch->next_;
	}
	(*walk++) = (pcl->num_tags_ >> 8) & 0xFF;
	(*walk++) = (pcl->num_tags_) & 0xFF;
	if(pcl->num_tags_) {
	  adv_tags = pcl->tag_list_;
	  while(adv_tags) {
	    (*walk++) = (adv_tags->obj_name_ >> 24) & 0xFF;
	    (*walk++) = (adv_tags->obj_name_ >> 16) & 0xFF;
	    (*walk++) = (adv_tags->obj_name_ >> 8) & 0xFF;
	    (*walk++) = (adv_tags->obj_name_) & 0xFF;
	    adv_tags = adv_tags->next_;
	  }
	}
	
	// 8 addl bytes for num_children and num_potl_children info; Assuming 
	// worst case of 8 levels in computing packet size
	// SHOULD DISABLE SENDING TAG INFO IN THE HASH SCHEME
	// Landmark address; 1 byte to indicate #addrs and 8 bytes 
	// for each addr
	hdrc->size_ = 20 + 8 + ((4+8) * pcl->num_potl_children_) + 20 + 4 + (4 * pcl->num_tags_) + 4 + 1 + (8 * num_lm_addrs); 
	// In real life each of the above fields would be
	// 4 byte integers; 20 bytes for IP addr
	//	if(myaddr_ == 11) 
	//	  trace("Node 11: Packet size: %d",hdrc->size_);
      }
      else if(action == DEMOTION) {
	hdrc->size_ = 20 + 20;
      }      
    }
  }
  // Optimization for reducing energy consumption; Just advertise
  // sequence number in steady state
  //  if(pcl->parent_ == NULL && action != DEMOTION) 
  //    hdrc->size_ = 20 + 4;
  // Cancel periodic_callback event if node is being demoted
  if(action == DEMOTION && pcl->periodic_update_event_->uid_)
      Scheduler::instance().cancel(pcl->periodic_update_event_);
  hdrc->direction() = hdr_cmn::DOWN;
  return p;
}
int
LandmarkAgent::radius(int level)
{
  // level i's radius >= (2 *level i-1's radius) + 1
  return((int(pow(2,level+1) + pow(2,level) - 1)));
  //  return((level + 1)*2 + 1);
  //  return(int(pow(2,level+1)) + 1);
}
ParentChildrenList::ParentChildrenList(int level, LandmarkAgent *a) : parent_(NULL), num_heard_(0), num_children_(0), num_potl_children_(0), num_pparent_(0), pchildren_(NULL), pparent_(NULL) , seqnum_(0) ,last_update_sent_(-(a->update_period_)), update_period_(a->update_period_), update_timeout_(a->update_timeout_), next_(NULL)
{
  level_ = level;
  periodic_update_event_ = new Event;
  periodic_handler_ = new LMPeriodicAdvtHandler(this);
  a_ = a;
  tag_list_ = NULL;
  num_tags_ = 0;
  adverts_type_ = FLOOD; // default is to flood adverts
  mylmaddrs_ = new LMAddrs;
}
void
PromotionTimer::expire(Event *e) {
  ParentChildrenList *pcl = a_->parent_children_list_;
  ParentChildrenList *new_pcl, *higher_level_pcl = NULL, *lower_level_pcl;
  ParentChildrenList *pcl1 = NULL; // Pointer to new highest_level_-1 object
  ParentChildrenList *pcl2 = NULL; // Pointer to new highest_level_+1 object
  ParentChildrenList *cur_pcl = NULL;
  int found = FALSE, has_parent = FALSE;
  int64_t *my_lm_addrs = NULL;
  int num_my_lm_addrs = 0;
  int num_potl_ch = 0;
  int addr_changed = 0;
  Scheduler &s = Scheduler::instance();
  double now = s.clock();
  Packet *p, *newp;
  //  if(now > 412.5) {
  //    purify_printf("expire1: %f,%dn",now,a_->myaddr_);
  //    purify_new_leaks();
  //  }
  while(pcl != NULL) {
    if(pcl->level_ == (a_->highest_level_ + 1)) {
      // Exclude ourself from the count of the lower level nodes heard
      higher_level_pcl = pcl;
      a_->num_resched_ = pcl->num_heard_ - 1;
      num_potl_ch = pcl->num_potl_children_;
    }
    else if(pcl->level_ == a_->highest_level_) {
      cur_pcl = pcl;
      if(pcl->parent_) {
	has_parent = TRUE;
      }
    }
    else if(pcl->level_ == (a_->highest_level_-1)) {
      lower_level_pcl = pcl;
    }
    pcl = pcl->next_;
  }
  assert(higher_level_pcl);
  if(a_->highest_level_)
    assert(lower_level_pcl);
  assert(cur_pcl);
  if(a_->wait_state_) {
    if(a_->num_resched_ && !has_parent) {
      a_->wait_state_ = 0;
      a_->total_wait_time_ = 0;
      
      // Promotion timeout is num_resched_ times the estimated time for 
      // a message to reach other nodes in its vicinity
      // PROM0_TIMEOUT_MULTIPLE is an estimate of time for adv to reach 
      // all nodes in vicinity
      a_->promo_timeout_ = a_->random_timer(double(CONST_TIMEOUT + PROMO_TIMEOUT_MULTIPLES * a_->radius(a_->highest_level_) + MAX_TIMEOUT/((a_->num_resched_+1) * pow(2,a_->highest_level_))), a_->be_random_);
      //      a_->promo_timeout_ = a_->random_timer(double(CONST_TIMEOUT + PROMO_TIMEOUT_MULTIPLES * a_->radius(a_->highest_level_) + MAX_TIMEOUT/((a_->num_resched_+1) * pow(2,a_->highest_level_))), a_->be_random_) + (MAX_ENERGY - (a_->node_)->energy())*200/MAX_ENERGY;
      a_->trace("Node %d: Promotion timeout after wait period in expire1: %f at time %f", a_->myaddr_,a_->promo_timeout_,s.clock());
      a_->num_resched_ = 0;
      a_->promo_start_time_ = s.clock();
      a_->promo_timer_->resched(a_->promo_timeout_);
    }
    else {
      double wait_time = PERIODIC_WAIT_TIME;
      a_->total_wait_time_ += wait_time;
      //      a_->trace("Node %d: Entering wait period in expire1 at time %f, highest level %d", a_->myaddr_,now,a_->highest_level_);
      a_->promo_timer_->resched(wait_time);
      // Demote ourself we do not have any children (excluding ourself) after
      // waiting for 1.5 times the update period
      if(a_->highest_level_ && (a_->total_wait_time_ > (a_->update_period_*1.5))) {
	//	a_->trace("Node %d: cur_pcl's number of children %d",a_->myaddr_,cur_pcl->num_children_);
	// Demote ourself from this level if we have only one children
	// and we have more than one potential parent at lower level
	// If we dont have more than one potl parent at lower level,
	// this node will oscillate between the two levels
	 if(cur_pcl->num_children_ == 1 && lower_level_pcl->num_pparent_ > 1) {
	   a_->trace("Node %d: Demoting from level %d because of no children at time %f",a_->myaddr_,a_->highest_level_,s.clock());
	   // Update appropriate lists
	   int delete_flag = TRUE;
	   int upd_time = (int) now;
	   upd_time = (upd_time << 16) | (lower_level_pcl->seqnum_ & 0xFFFF);
	   ++(lower_level_pcl->seqnum_);
	   lower_level_pcl->UpdatePotlParent(a_->myaddr_, 0, 0, 0, 0, 0, upd_time, delete_flag);
	   upd_time = (int) now;
	   upd_time = (upd_time << 16) | (higher_level_pcl->seqnum_ & 0xFFFF);
	   ++(higher_level_pcl->seqnum_);
	   higher_level_pcl->UpdatePotlChild(a_->myaddr_, 0, 0, 0, 0, 0, upd_time, IS_CHILD, delete_flag,NULL);
	   --(a_->highest_level_);
	   Packet *p = a_->makeUpdate(cur_pcl, HIER_ADVS, DEMOTION);
	   s.schedule(a_->target_,p,0);
	 }
      }
      else if(!(cur_pcl->parent_) && (a_->total_wait_time_ >= (2*PERIODIC_WAIT_TIME))) {
	// We must be the global LM
	a_->global_lm_id_ = a_->myaddr_;
	a_->global_lm_level_ = a_->highest_level_;
	// Get LM addresses if any
	(cur_pcl->mylmaddrs_)->get_lm_addrs(&num_my_lm_addrs,&my_lm_addrs);
	// Start assigning landmark addresses to child nodes; 
	// Shift 1, number of levels * 8 times to left for address of root node
	int64_t *lmaddr = new int64_t[1];
	lmaddr[0] = 1;
	lmaddr[0] = (lmaddr[0] << (cur_pcl->level_ * 8));
	int num_lm_addrs = 1;
	assert(num_my_lm_addrs <= 1);
	if(num_my_lm_addrs == 0) {
	  addr_changed = 1;
	}
	else {
	  if(my_lm_addrs[0] != lmaddr[0])
	    addr_changed = 1;
	}
	
	if(num_my_lm_addrs) delete[] my_lm_addrs;
	
	if(addr_changed) {
	  a_->trace("Node %d: LM addrs being assigned by global LM at time %f, level %d",a_->myaddr_,now,a_->highest_level_);
	  a_->assign_lmaddress(lmaddr, num_lm_addrs, cur_pcl->level_);
	  if(a_->global_lm_)
	    p = a_->makeUpdate(cur_pcl, HIER_ADVS, GLOBAL_ADVERT);
	  else
	    p = a_->makeUpdate(cur_pcl, HIER_ADVS, PERIODIC_ADVERTS);
	  a_->trace("Node %d: Generating ReHash msg at time %f",a_->myaddr_,NOW);
	  a_->GenerateReHashMsg(lmaddr[0],NOW);
	  // Generate updates for LM at lower levels as well since their LM
	  // addresses have also changed
	  ParentChildrenList *tmp_pcl = a_->parent_children_list_;
	  while(tmp_pcl) {
	    if(tmp_pcl->level_ < cur_pcl->level_) {
	      a_->trace("Node %d: Generating level %d update at time %f",a_->myaddr_,tmp_pcl->level_,now);
	      newp = a_->makeUpdate(tmp_pcl, HIER_ADVS, PERIODIC_ADVERTS);
	      s.schedule(a_->target_,newp,0);
	      tmp_pcl->last_update_sent_ = now;
	    }
	    tmp_pcl = tmp_pcl->next_;
	  }
	  s.schedule(a_->target_, p, 0);
	  cur_pcl->last_update_sent_ = now;
	}
	// The advertisements from the root LM need to be broadcast in the hash
	// scheme
	if(num_lm_addrs) delete[] lmaddr;
      }
    }      
    return;
  }    
  
  // Promotion timer is off
  a_->promo_timer_running_ = 0;
  // Only one promotion timer can be running at a node at a given instant. 
  // On expiry, the node will be promoted one level higher to highest_level_+1
  // Add a parentchildrenlist object for the higher level if one doesnt already
  // exist
  higher_level_pcl = NULL;
  pcl = a_->parent_children_list_;
  while(pcl != NULL) {
    new_pcl = pcl;
    if(pcl->level_ == a_->highest_level_+1){
      found = TRUE;
      higher_level_pcl = pcl;
    }
    if(pcl->level_ == (a_->highest_level_)){
      pcl1 = pcl;
    }
    if(pcl->level_ == (a_->highest_level_+2)){
      pcl2 = pcl;
    }
    pcl = pcl->next_;
  }
  
  // highest_level_-1 object should exist
  assert(pcl1);
  if(pcl1->parent_ != NULL) {
    a_->trace("Node %d: Not promoted to higher level %dn", a_->myaddr_, a_->highest_level_+1);
    return;
  }
  ++(a_->highest_level_);
  assert(a_->highest_level_ < MAX_LEVELS);
  if(!found) {
    new_pcl->next_ = new ParentChildrenList(a_->highest_level_, a_);
    higher_level_pcl = new_pcl->next_;
    new_pcl = new_pcl->next_;
  }
  // Create highest_level_+1 object if it doesnt exist
  if(!pcl2) {
    new_pcl->next_ = new ParentChildrenList((a_->highest_level_)+1, a_);
    pcl2 = new_pcl->next_;
  }
  assert(pcl2);
  if(a_->debug_) {
    a_->trace("Node %d: Promoted to level %d, num_potl_children %d at time %f", a_->myaddr_, a_->highest_level_, num_potl_ch, now);
    //    LMNode *lm = higher_level_pcl->pchildren_;
    //    a_->trace("Potential Children:");
    //    while(lm) {
    //      a_->trace("%d (level %d) Number of hops: %d", lm->id_,lm->level_,lm->num_hops_);
    //      lm = lm->next_;
    //    }
    
    //    lm = higher_level_pcl->pparent_;
    //    a_->trace("Potential Parent:");
    //    while(lm) {
    //      a_->trace("%d (level %d)", lm->id_,lm->level_);
    //      lm = lm->next_;
    //    }
  }
  // Update tag lists and send out corresponding advertisements
  a_->SendChangedTagListUpdate(0,a_->highest_level_-1);
  // start off periodic advertisements for this higher level
  s.schedule(higher_level_pcl->periodic_handler_, higher_level_pcl->periodic_update_event_, 0);
  
  // add myself as potential parent for highest_level-1 and child for 
  // highest_level+1 
  int num_hops = 0;
  int energy = (int)((a_->node_)->energy());
  int child_flag = IS_CHILD;
  int delete_flag = FALSE;
  int upd_time = (int) now;
  upd_time = (upd_time << 16) | (pcl1->seqnum_ & 0xFFFF);
  ++(pcl1->seqnum_);
  pcl1->UpdatePotlParent(a_->myaddr_, a_->myaddr_, num_hops, a_->highest_level_, higher_level_pcl->num_children_, energy, upd_time, delete_flag);
  // tag_list == NULL doesnt matter because we're at a smaller level than
  // pcl2->level_ at this point. periodic_callback_ will update this field
  // correctly
  upd_time = (int) now;
  upd_time = (upd_time << 16) | (pcl2->seqnum_ & 0xFFFF);
  ++(pcl2->seqnum_);
  pcl2->UpdatePotlChild(a_->myaddr_, a_->myaddr_, num_hops, a_->highest_level_,higher_level_pcl->num_children_, energy, upd_time, child_flag, delete_flag, higher_level_pcl->tag_list_);
  
  // If we havent seen a LM that can be our parent at this higher level, start
  // promotion timer for promotion to next level
  a_->num_resched_ = pcl2->num_heard_ - 1;
  if(higher_level_pcl->parent_ == NULL && a_->num_resched_) {
    //    if (a_->debug_) printf("PromotionTimer's expire method: Scheduling timer for promo to level %dn",a_->highest_level_);
    // Timer's status is TIMER_HANDLING in handle; so we just reschedule to
    // avoid "cant start timer" abort if sched is called
    a_->promo_timer_running_ = 1;
    a_->wait_state_ = 0;
    a_->total_wait_time_ = 0;
    a_->promo_timeout_ = a_->random_timer(double(CONST_TIMEOUT + PROMO_TIMEOUT_MULTIPLES * a_->radius(a_->highest_level_+1) + MAX_TIMEOUT/((a_->num_resched_+1) * pow(2,a_->highest_level_+1))), a_->be_random_);
    a_->trace("Node %d: Promotion timeout after wait period in expire2: %f at time %f, num_resched_ %d, energy %f", a_->myaddr_,a_->promo_timeout_,s.clock(),a_->num_resched_,(a_->node_)->energy());
    a_->num_resched_ = 0;
    a_->promo_start_time_ = s.clock();
    a_->promo_timer_->resched(a_->promo_timeout_);
  }
  else {
    double wait_time = PERIODIC_WAIT_TIME;
    a_->promo_timer_running_ = 1;
    a_->total_wait_time_ = 0;
    a_->wait_state_ = 1;
    a_->total_wait_time_ += wait_time;
    //    a_->trace("Node %d: Entering wait period in expire1 at time %f", a_->myaddr_,now);
    a_->promo_timer_->resched(wait_time);
  }
  
  //  if(now > 412.5) {
  //    purify_printf("expire2: %f,%dn",now,a_->myaddr_);
  //    purify_new_leaks();
  //  }
}
  
int 
LandmarkAgent::command (int argc, const char *const *argv)
{
  if (argc == 2)
    {
      if (strcmp (argv[1], "start") == 0)
	{
	  startUp();
	  return (TCL_OK);
	}
      if (strcmp (argv[1], "stop") == 0)
	{
	  stop();
	  return (TCL_OK);
	}
      if (strcmp (argv[1], "print-nbrs") == 0)
	{
	  get_nbrinfo();
	  return (TCL_OK);
	}
      if (strcmp (argv[1], "enable-caching") == 0)
	{
	  cache_ = 1;
	  return (TCL_OK);
	}
      if (strcmp (argv[1], "unicast-adverts") == 0)
	{
	  adverts_type_ = UNICAST;
	  return (TCL_OK);
	}
      if (strcmp (argv[1], "hard-state-adverts") == 0)
	{
	  adverts_type_ = SUPPRESS;
	  // Entries should never timeout in a hard-state scheme
	  update_timeout_ = 1000000;
	  return (TCL_OK);
	}
      if (strcmp (argv[1], "enable-global-landmark") == 0)
	{
	  global_lm_ = 1;
	  return (TCL_OK);
	}
      else if (strcmp (argv[1], "dumprtab") == 0)
	{
	  Packet *p2 = allocpkt ();
	  hdr_ip *iph2 = HDR_IP(p2);
	  //	  rtable_ent *prte;
          trace ("Table Dump %d[%d]n----------------------------------n",
	    myaddr_, iph2->sport());
	  trace ("VTD %.5f %d:%dn", Scheduler::instance ().clock (),
		 myaddr_, iph2->sport());
	  trace ("Remaining energy: %f", node_->energy());
	  //	  trace ("Energy consumed by queries: %f", node_->qry_energy());
	  /*
	   * Freeing a routing layer packet --> don't need to
	   * call drop here.
	   */
	  trace("Highest Level: %d", highest_level_);
	  Packet::free (p2);
	  ParentChildrenList *pcl = parent_children_list_;
	  LMNode *pch;
	  while(pcl) {
	    trace("Level %d:", pcl->level_);
	    if(pcl->parent_)
	      trace("Parent: %d", (pcl->parent_)->id_);
	    else
	      trace("Parent: NULL");
	    int num_lm_addrs = 0;
	    int64_t *lmaddrs = NULL;
	    (pcl->mylmaddrs_)->get_lm_addrs(&num_lm_addrs,&lmaddrs);
	    for( int i = 0; i < num_lm_addrs; ++i) {
	      int i1,i2,i3,i4,i5,i6,i7,i8;
	      i1 = (lmaddrs[i] >> 56) & 0xFF;
	      i2 = (lmaddrs[i] >> 48) & 0xFF;
	      i3 = (lmaddrs[i] >> 40) & 0xFF;
	      i4 = (lmaddrs[i] >> 32) & 0xFF;
	      i5 = (lmaddrs[i] >> 24) & 0xFF;
	      i6 = (lmaddrs[i] >> 16) & 0xFF;
	      i7 = (lmaddrs[i] >> 8) & 0xFF;
	      i8 = (lmaddrs[i]) & 0xFF;
	      trace("Landmark Address: %d.%d.%d.%d.%d.%d.%d.%d",i1,i2,i3,i4,i5,i6,i7,i8);
	    }
	    if(num_lm_addrs) delete[] lmaddrs;
	    if(myaddr_ == 134) {
	      pch = pcl->pchildren_;
	      while(pch) {
		int num_addrs = 0;
		int64_t *addrs = NULL;
		(pch->lmaddr_)->get_lm_addrs(&num_addrs,&addrs);
		
		int j1=0,j2=0,j3=0,j4=0,j5=0,j6=0,j7=0,j8=0;
		if(num_addrs) {
		  j1 = (addrs[0] >> 56) & 0xFF;
		  j2 = (addrs[0] >> 48) & 0xFF;
		  j3 = (addrs[0] >> 40) & 0xFF;
		  j4 = (addrs[0] >> 32) & 0xFF;
		  j5 = (addrs[0] >> 24) & 0xFF;
		  j6 = (addrs[0] >> 16) & 0xFF;
		  j7 = (addrs[0] >> 8) & 0xFF;
		  j8 = (addrs[0]) & 0xFF;
		}
		trace("Node %d: Potl Child id %d, LM addr %d.%d.%d.%d.%d.%d.%d.%d, next_hop %d, num_children %d",myaddr_,pch->id_,j1,j2,j3,j4,j5,j6,j7,j8,pch->next_hop_,pch->num_children_);
		if(num_addrs) delete[] addrs;
		pch = pch->next_;
	      }
	    }
	    trace("Number of potl children: %dn", pcl->num_potl_children_);
	    if(myaddr_ == 166) {
	      trace("Number of children: %dn", pcl->num_children_);
	      trace("Number of level %d nodes heard: %dn", (pcl->level_)-1, pcl->num_heard_);
	      
	      trace("Number of potl parent: %dn", pcl->num_pparent_);
	      if(pcl->level_ >= 1 && highest_level_ >= 1) {
		pch = pcl->pchildren_;
		trace("Potential Children (radius %d):",radius(pcl->level_));
		while(pch) {
		  if(pch->child_flag_ != NOT_POTL_CHILD)
		    trace("Node %d (%d hops away)",pch->id_,pch->num_hops_);
		  pch = pch->next_;
		}
		pch = pcl->pparent_;
		trace("Potential parent:");
		while(pch) {
		  trace("Node %d (%d hops away)",pch->id_,pch->num_hops_);
		  pch = pch->next_;
		} 
	      }
	    }
	    pcl = pcl->next_;
	  }
	  Packet::free(p2);
	  return (TCL_OK);
	}
    }
  else if (argc == 3)
    {
      if (strcasecmp (argv[1], "tracetarget") == 0)
	{
	  TclObject *obj;
	if ((obj = TclObject::lookup (argv[2])) == 0)
	    {
	      fprintf (stderr, "%s: %s lookup of %s failedn", __FILE__, argv[1],
		       argv[2]);
	      return TCL_ERROR;
	    }
	  tracetarget_ = (Trace *) obj;
	  return TCL_OK;
	}
      else if (strcasecmp (argv[1], "addr") == 0) {
	int temp;
	temp = Address::instance().str2addr(argv[2]);
	myaddr_ = temp;
	return TCL_OK;
      }
      else if (strcasecmp (argv[1], "set-update-period") == 0) {
	update_period_ = atof(argv[2]);
	if(adverts_type_ != SUPPRESS)
	  update_timeout_ = update_period_ + 4 * LM_STARTUP_JITTER;
	return TCL_OK;
      }
      else if (strcasecmp (argv[1], "set-update-timeout") == 0) {
	update_timeout_ = atof(argv[2]);
	return TCL_OK;
      }
      else if (strcasecmp (argv[1], "start-tag-motion") == 0) {
	mobility_period_ = atof(argv[2]);
	Scheduler::instance().schedule(tag_mobility_,tag_mobility_event_,Random::uniform(mobility_period_));
	return (TCL_OK);
      }
      else if (strcasecmp (argv[1], "attach-tag-dbase") == 0)
	{
	  TclObject *obj;
	if ((obj = TclObject::lookup (argv[2])) == 0)
	    {
	      fprintf (stderr, "%s: %s lookup of %s failedn", __FILE__, argv[1],
		       argv[2]);
	      return TCL_ERROR;
	    }
	  tag_dbase_ = (tags_database *) obj;
	  return TCL_OK;
	}
      else if (strcasecmp (argv[1], "node") == 0)
	{
	  assert(node_ == NULL);
	  TclObject *obj;
	if ((obj = TclObject::lookup (argv[2])) == 0)
	    {
	      fprintf (stderr, "%s: %s lookup of %s failedn", __FILE__, argv[1],
		       argv[2]);
	      return TCL_ERROR;
	    }
	  node_ = (MobileNode *) obj;
	  return TCL_OK;
	}
      else if (strcmp (argv[1], "query-debug") == 0)
	{
	  qry_debug_ = atoi(argv[2]);
	  return (TCL_OK);
	}
      else if (strcasecmp (argv[1], "ll-queue") == 0)
	{
	if (!(ll_queue = (PriQueue *) TclObject::lookup (argv[2])))
	    {
	      fprintf (stderr, "Landmark_Agent: ll-queue lookup of %s failedn", argv[2]);
	      return TCL_ERROR;
	    }
	  return TCL_OK;
	}
    }
return (Agent::command (argc, argv));
}
void
LandmarkAgent::startUp()
{
  int i,ntags, j = 0, read_new_mobile_tags = 0;
  Scheduler &s = Scheduler::instance();
  compr_taglist *local_tags0, *local_tags1, *local_tags2, *t_ptr;
  compr_taglist *tag_ptr1, *tag_ptr2;
  God *gd = God::instance();
  //  AgentList *alist = AgentList::instance();
  int *nbrs;
  int num_nbrs = 0, num_nodes = 0;
  
  // Adding ourself to global tag agent database
  //  alist->AddAgent(myaddr_,this);
  //  num_nodes = gd->numNodes()-1;
  //  nbrs = new int[num_nodes];
  
  //  for(i = 1; i <= num_nodes; ++i) {
      // God sees node id as id+1 ...
  //    if(gd->hops(myaddr_+1,i) == 1) {
  //      nbrs[num_nbrs++] = i-1;
  //    }
  //  }
  //  trace("Node %d: Number of nbrs %d, Neighbours:",myaddr_,num_nbrs);
  //  num_nbrs_ = num_nbrs;
  //  nbrs_ = new int[num_nbrs_];
  //  for(i = 0; i < num_nbrs_; ++i) {
  //    nbrs_[i] = nbrs[i];
    //    trace("%d",nbrs_[i]);
  //  }
  //  if(nbrs) delete[] nbrs;
  
  trace("Node %d: LM Agent starting up at time %f",myaddr_,NOW);
  // Set node to be alive (this method might be called after a call to reset
  node_dead_ = 0;
  
  double x,y,z;
  node_->getLoc(&x,&y,&z);
  //  printf("Node %d position: (%f,%f,%f)n",myaddr_,x,y,z);
  // Detection range smaller than transmission range. This is because, if 
  // the tags are passive, they may not have sufficient energy to re-radiate
  // information to the sensor
  double r = 60;
  local_tags0 = tag_dbase_->Gettags(x,y,r);
  //  trace("Node %d's at (%f,%f,%f) senses tags:",myaddr_,x,y,z);
  t_ptr = local_tags0;
  ntags = 0;
  while(t_ptr) {
    //    trace("tag name: %d.%d.%d",(t_ptr->obj_name_ >> 24) & 0xFF,(t_ptr->obj_name_ >> 16) & 0xFF,(t_ptr->obj_name_) & 0xFFFF);
    ++ntags;
    if(!(t_ptr->next_) && mobile_tags_ && !read_new_mobile_tags) {
      // Update our tag list with any new tags that have come into our range
      // while we were dead
      read_new_mobile_tags = 1;
      t_ptr->next_ = mobile_tags_;
      mobile_tags_ = NULL;
    }
    t_ptr = t_ptr->next_;
  }
  //  trace("Number of tags: %d",ntags);
  /*
  int agg_level = 1;
  int num_tags = 0;
  local_tags1 = aggregate_tags(local_tags0,agg_level,&num_tags);
  trace("Level 1 aggregates, num = %d",num_tags);
  t_ptr = local_tags1;
  while(t_ptr) {
    trace("tag name: %d.%d.%d",(t_ptr->obj_name_ >> 24) & 0xFF,(t_ptr->obj_name_ >> 16) & 0xFF,(t_ptr->obj_name_) & 0xFFFF);
    t_ptr = t_ptr->next_;
  }
  agg_level = 2;
  num_tags = 0;
  local_tags2 = aggregate_tags(local_tags1,agg_level,&num_tags);
  trace("Level 2 aggregates, num = %d",num_tags);
  t_ptr = local_tags2;
  while(t_ptr) {
    trace("tag name: %d.%d.%d",(t_ptr->obj_name_ >> 24) & 0xFF,(t_ptr->obj_name_ >> 16) & 0xFF,(t_ptr->obj_name_) & 0xFFFF);
    t_ptr = t_ptr->next_;
  }
  // Delete local_tags1
  tag_ptr1 = local_tags1;
  while(tag_ptr1) {
    tag_ptr2 = tag_ptr1;
    tag_ptr1 = tag_ptr1->next_;
    delete tag_ptr2;
  }
  // Delete local_tags2
  tag_ptr1 = local_tags2;
  while(tag_ptr1) {
    tag_ptr2 = tag_ptr1;
    tag_ptr1 = tag_ptr1->next_;
    delete tag_ptr2;
  }
  */
  assert(highest_level_ == 0);
  assert(parent_children_list_ == NULL);
  parent_children_list_ = new ParentChildrenList(highest_level_, this);
  ParentChildrenList **pcl = &parent_children_list_;
  // Start off periodic LM advertisements
  assert(highest_level_ == 0);
  s.schedule((*pcl)->periodic_handler_, (*pcl)->periodic_update_event_, INITIAL_WAIT_TIME + jitter(LM_STARTUP_JITTER, be_random_));
  (*pcl)->tag_list_ = local_tags0;
  (*pcl)->num_tags_ = ntags;
  // Start off promotion timer
  //  if (debug_) printf("startUp: Scheduling timern");
  promo_timer_running_ = 1;
  num_resched_ = 0;
  // Node enters "wait" state where it waits to receive other node's 
  // advertisements; Wait for 5 * radius(level) seconds; Should be
  // atleast the same as the period of LM advts (10s)
  total_wait_time_ = 0;
  wait_state_ = 1;
  double wait_time = WAIT_TIME * radius(highest_level_) + INITIAL_WAIT_TIME + LM_STARTUP_JITTER;
  total_wait_time_ += wait_time;
  //  trace("Node %d: Wait time at startUp: %f",myaddr_,wait_time);
  promo_timer_->sched(wait_time);
  //  promo_timer_->sched(promo_timeout_);
}
compr_taglist *
LandmarkAgent::aggregate_taginfo(compr_taglist *unagg_tags, int agg_level, int *num_tags)
{
  compr_taglist *agg_tags, *agg_ptr1, *agg_ptr2,  *last_agg_ptr;
  int found;
  
  *num_tags = 0;
  // agg_level is 1 implies ignore the last field
  // agg_level >= 2 implies ignore the last two fields
  agg_ptr1 = unagg_tags;
  agg_tags = NULL;
  
  while(agg_ptr1) {
    if(agg_level == 1) {
      found = FALSE;
      if(agg_tags) {
	agg_ptr2 = agg_tags;
	while(agg_ptr2) {
	  if((((agg_ptr2->obj_name_ >> 24) & 0xFF) == ((agg_ptr1->obj_name_ >> 24) & 0xFF)) && (((agg_ptr2->obj_name_ >> 16) & 0xFF) == ((agg_ptr1->obj_name_ >> 16) & 0xFF))) {
	    found = TRUE;
	    break;
	  }
	  last_agg_ptr = agg_ptr2;
	  agg_ptr2 = agg_ptr2->next_;
	}
      }
      if(!found) {
	++(*num_tags);
	if(!agg_tags) {
	  agg_tags = new compr_taglist;
	  last_agg_ptr = agg_tags;
	}
	else {
	  last_agg_ptr->next_ = new compr_taglist;
	  last_agg_ptr = last_agg_ptr->next_;
	}
	last_agg_ptr->obj_name_ = (agg_ptr1->obj_name_ & 0xFFFF0000);
      }
    }
    else if(agg_level >= 2) {
      found = FALSE;
      if(agg_tags) {
	agg_ptr2 = agg_tags;
	while(agg_ptr2) {
	  if(((agg_ptr2->obj_name_ >> 24) & 0xFF) == ((agg_ptr1->obj_name_ >> 24) & 0xFF)) {
	    found = TRUE;
	    break;
	  }
	  last_agg_ptr = agg_ptr2;
	  agg_ptr2 = agg_ptr2->next_;
	}
      }
      if(!found) {
	++(*num_tags);
	if(!agg_tags) {
	  agg_tags = new compr_taglist;
	  last_agg_ptr = agg_tags;
	}
	else {
	  last_agg_ptr->next_ = new compr_taglist;
	  last_agg_ptr = last_agg_ptr->next_;
	}
	last_agg_ptr->obj_name_ = (agg_ptr1->obj_name_ & 0xFF000000);
      }
    }
    agg_ptr1 = agg_ptr1->next_;	
  }
  return(agg_tags);
}
compr_taglist *
LandmarkAgent::aggregate_tags(compr_taglist *unagg_tags, int agg_level, int *num_tags)
{
  compr_taglist *agg_tags = NULL, *tag_ptr;
  aggreg_taglist *t1, *t2, *t3, *tmp_ptr;
  aggreg_taglist *list1 = NULL, *list2 = NULL, *list3 = NULL, *list = NULL;
  aggreg_taglist *prev_tag, *next_tag, *old_list;
  int found;
  int p1,p2,p3,q1,q2,q3,object_name;
  
  // Tag names have 3 fields
  // List 1 is list of tags with first field > 0, last 2 fields = 0
  // List 2 is list of tags with first two fields > 0 and last field = 0
  // List 3 is list of tags with all three fields > 0 
  tag_ptr = unagg_tags;
  while(tag_ptr) {
    p1 = (tag_ptr->obj_name_ >> 24) & 0xFF;
    p2 = (tag_ptr->obj_name_ >> 16) & 0xFF;
    p3 = tag_ptr->obj_name_ & 0xFFFF;
    found = 0;
    if(p1 && p2 && p3) {
      // Check if p1.p2.0 is already in list2; If so, goto next object
      object_name = (int)((p1 * pow(2,24)) + (p2 * pow(2,16))) ;
      old_list = list2;
      while(old_list) {
	if(old_list->obj_name_ == object_name) {
	  found = TRUE;
	  break;
	}
	old_list = old_list->next_;
      }
      // Check if p1.0.0 is already in list1; If so, goto next object
      old_list = list1;
      while(old_list) {
	q1 = (old_list->obj_name_ >> 24) & 0xFF;
	if(p1 == q1) {
	  found = TRUE;
	  break;
	}
	old_list = old_list->next_;
      }
      
      tmp_ptr = list3;
      while(tmp_ptr && !found) {
	q1 = (tmp_ptr->obj_name_ >> 24) & 0xFF;
	q2 = (tmp_ptr->obj_name_ >> 16) & 0xFF;
	q3 = tmp_ptr->obj_name_ & 0xFFFF;
	// If 2 objects have same value for first two fields, store the
	// aggregate p1.p2.0 in list2; We have already checked if p1.p2.0
	// is already in list2 or not
	if(p1 == q1 && p2 == q2 && p3 != q3) {
	  if(!list2) {
	    list2 = new aggreg_taglist;
	    t2 = list2;
	  }
	  else {
	    t2->next_ = new aggreg_taglist;
	    t2 = t2->next_;
	  }
	  t2->obj_name_ = object_name;
	  // Indicate that this is a new aggregate
	  t2->marked_ = 1;
	  // Remove this object from list3; We simply set the obj_name_ to 1
	  // to indicate that this tag object is not valid
	  tmp_ptr->obj_name_ = -1;
	  found = TRUE;
	  break;
	}
	else if(p1 == q1 && p2 == q2 && p3 == q3) {
	  found = TRUE;
	  break;
	}
	tmp_ptr = tmp_ptr->next_;
      }
      if(found) {
	tag_ptr = tag_ptr->next_;
	continue;
      }
      
      if(!list3) {
	list3 = new aggreg_taglist;
	t3 = list3;
      }
      else {
	t3->next_ = new aggreg_taglist;
	t3 = t3->next_;
      }
      t3->obj_name_ = tag_ptr->obj_name_;
    }
    else if(p1 && p2 && !p3) {
      // Check if p1.0.0 is already in list1; If so, goto next object
      object_name = (int)(p1 * pow(2,24)) ;
      if(list1) {
	old_list = list1;
	while(old_list) {
	  if(old_list->obj_name_ == object_name) {
	    found = TRUE;
	    break;
	  }
	  old_list = old_list->next_;
	}
      }
      tmp_ptr = list2;
      while(tmp_ptr && !found) {
	q1 = (tmp_ptr->obj_name_ >> 24) & 0xFF;
	q2 = (tmp_ptr->obj_name_ >> 16) & 0xFF;
	// If 2 objects have same value for the first field, store the
	// aggregate in list1 provided the other object is not a new aggregate
	if(p1 == q1 && p2 != q2 && !tmp_ptr->marked_) {
	  if(!list1) {
	    list1 = new aggreg_taglist;
	    t1 = list1;
	  }
	  else {
	    t1->next_ = new aggreg_taglist;
	    t1 = t1->next_;
	  }
	  t1->obj_name_ = object_name;
	  
	  // Indicate that this is a new aggregate
	  t1->marked_ = 1;
	  // Remove this object from list3; We simply set the obj_name_ to 1
	  // to indicate that this tag object is not valid
	  tmp_ptr->obj_name_ = -1;
	  // Remove any elements p1.*.* from list3 i.e., set obj_name_ to -1
	  old_list = list3;
	  while(old_list) {
	    q1 = (old_list->obj_name_ >> 24) & 0xFF;
	    if(p1 == q1)
	      old_list->obj_name_ = -1;
	    old_list = old_list->next_;
	  }
	  found = TRUE;
	  break;
	}
	else if(p1 == q1 && p2 == q2) {
	  found = TRUE;
	  break;
	}
	tmp_ptr = tmp_ptr->next_;
      }
      
      if(found) {
	tag_ptr = tag_ptr->next_;
	continue;
      }
      if(!list2) {
	list2 = new aggreg_taglist;
	t2 = list2;
      }
      else {
	t2->next_ = new aggreg_taglist;
	t2 = t2->next_;
      }
      t2->obj_name_ = tag_ptr->obj_name_;
      // Remove any elements p1.p2.* from list3 i.e., set obj_name_ to -1
      old_list = list3;
      while(old_list) {
	q1 = (old_list->obj_name_ >> 24) & 0xFF;
	q2 = (old_list->obj_name_ >> 16) & 0xFF;       
	if(p1 == q1 && p2 == q2)
	  old_list->obj_name_ = -1;
	old_list = old_list->next_;
      }
    }
    else if(p1 && !p2 && !p3) {
      // Check if object p1.0.0 already in list; If so, goto next object
      tmp_ptr = list1;
      while(tmp_ptr) {
	if(tmp_ptr->obj_name_ == tag_ptr->obj_name_) {
	  found = TRUE;
	  break;
	}
	tmp_ptr = tmp_ptr->next_;
      }
      
      // Add object to list1
      if(!found) {
	if(!list1) {
	  list1 = new aggreg_taglist;
	  t1 = list1;
	}
	else {
	  t1->next_ = new aggreg_taglist;
	  t1 = t1->next_;
	}
	t1->obj_name_ = tag_ptr->obj_name_;
      }
      // Remove any elements p1.*.* from list2 i.e., set obj_name_ to -1
      old_list = list2;
      while(old_list) {
	q1 = (old_list->obj_name_ >> 24) & 0xFF;
	if(p1 == q1)
	  old_list->obj_name_ = -1;
	old_list = old_list->next_;
      }
      // Remove any elements p1.*.* from list3 i.e., set obj_name_ to -1
      old_list = list3;
      while(old_list) {
	q1 = (old_list->obj_name_ >> 24) & 0xFF;
	if(p1 == q1)
	  old_list->obj_name_ = -1;
	old_list = old_list->next_;
      }
    }
    else
      assert(0);
    tag_ptr = tag_ptr->next_;
  }
  // Make list1, list2, list3 into one list
  list = NULL;
  if(list3) {
    list = list3;
    if(list2) {
      t3->next_ = list2;
      if(list1) {
	t2->next_ = list1;
      }
    }
    else if(list1)
      t3->next_ = list1;
  }
  else if(list2) {
    list = list2;
    if(list1)
      t2->next_ = list1;
  }
  else if(list1)
    list = list1;
  
  
  // Return the list of aggregated tags
  *num_tags = 0;
  agg_tags = NULL;
  tmp_ptr = list;
  while(tmp_ptr) {
    if(tmp_ptr->obj_name_ != -1) {
      if(!agg_tags) {
	agg_tags = new compr_taglist;
	tag_ptr = agg_tags;
      }
      else {
	tag_ptr->next_ = new compr_taglist;
	tag_ptr = tag_ptr->next_;
      }
      ++(*num_tags);
      tag_ptr->obj_name_ = tmp_ptr->obj_name_;
    }
    tmp_ptr = tmp_ptr->next_;
  }
  // Delete list
  list1 = NULL;
  list2 = NULL;
  list1 = list;
  while(list1) {
    list2 = list1;
    list1 = list1->next_;
    delete list2;
  }
  return(agg_tags);
}
void
LandmarkAgent::recv(Packet *p, Handler *)
{
  hdr_ip *iph = HDR_IP(p);
  hdr_cmn *cmh = HDR_CMN(p);
  /*
   *  Must be a packet being originated by the query agent at my node?
   */
  if(node_dead_) {
    Packet::free(p);
    return;
  }
  if(iph->saddr() == myaddr_ && iph->sport() == 0) {
    /*
     * Add the IP Header
     */
    cmh->size() += IP_HDR_LEN;    
  }
  /*
   *  I received a packet that I sent.  Probably
   *  a routing loop.
   */
  else if(iph->saddr() == myaddr_) {
    Packet::free(p);
    //   drop(p, DROP_RTR_ROUTE_LOOP);
    return;
  }
  /*
   *  Packet I'm forwarding...
   */
  // Move the ttl check to the following methods?
  //    if(--iph->ttl_ == 0) {
  //      drop(p, DROP_RTR_TTL);
  //      return;
  //    }
  
  // Packet will be forwarded down (if it's not dropped)
  cmh->direction_ = hdr_cmn::DOWN;
  
  unsigned char *walk = p->accessdata();
  int action = *walk++;
  int data_pkt = 0;
  if(action == QUERY_PKT || action == HASH_PKT || action == HASH_ACK_PKT || action == REHASH_PKT || action == DIR_QUERY_PKT || action == DIR_RESPONSE_PKT || action == OBJECT_QUERY_PKT || action == OBJECT_RESPONSE_PKT) 
    data_pkt = 1;
  if ((iph->saddr() != myaddr_) && (iph->dport() == ROUTER_PORT) && !data_pkt)
    {
      ProcessHierUpdate(p);
    }
  else
    {
      ForwardPacket(p);
    }
}
void
LandmarkAgent::ForwardPacket(Packet *p)
{
  hdr_ip *iph = HDR_IP(p);
  hdr_cmn *cmh = HDR_CMN(p);
  Packet *newp;
  hdr_ip *new_iph;
  hdr_cmn *new_cmh;
  unsigned char *walk, *X_ptr, *Y_ptr, *level_ptr, *num_src_hops_ptr;
  unsigned char *last_hop_ptr, *pkt_end_ptr;
  int X, Y, next_hop_level, prev_hop_level, obj_name, num_src_hops;
  double local_x, local_y, local_z;
  int num_dst = 0, action, origin_time;
  NodeIDList *dst_nodes = NULL, *dst_ptr = NULL;
  int query_for_us = FALSE;
  Scheduler &s = Scheduler::instance();
  double now = s.clock();
  nsaddr_t last_hop_id;
  int cache_index = -1; // index into cache if object is found
  int found = FALSE; // whether object has been found in cache
  walk = p->accessdata();
  // Type of advertisement
  action = *walk++;
  X = 0;
  X_ptr = walk;
  X = *walk++;
  X = (X << 8) | *walk++;
  Y_ptr = walk;
  Y = *walk++;
  Y = (Y << 8) | *walk++;
  // level of our parent/child node that forwarded the query to us
  level_ptr = walk;
  next_hop_level = *walk++;
  obj_name = *walk++;
  obj_name = (obj_name << 8) | *walk++;
  obj_name = (obj_name << 8) | *walk++;
  obj_name = (obj_name << 8) | *walk++;
    // origin time of advertisement
  origin_time = *walk++;
  origin_time = (origin_time << 8) | *walk++;
  origin_time = (origin_time << 8) | *walk++;
  origin_time = (origin_time << 8) | *walk++;
  
  num_src_hops_ptr = walk;
  num_src_hops = *walk++;
  num_src_hops = (num_src_hops << 8) | *walk++;
  assert(num_src_hops <= 30);
  last_hop_ptr = NULL;
  for(int i = 0; i < num_src_hops; ++i) {
    last_hop_ptr = walk;
    walk += 3;
  }
  if(last_hop_ptr) {
    prev_hop_level = *(last_hop_ptr+2);
    last_hop_id = *last_hop_ptr;
    last_hop_id = (last_hop_id << 8) | *(last_hop_ptr+1);
  }
  else {
    prev_hop_level = 0;
    last_hop_id = NO_NEXT_HOP;
  }
  // Used to add source route to packet
  pkt_end_ptr = walk;
  
  // If this is a response pkt, cache this information
  if(cache_) {
    if(X != 65000 && Y != 65000) {
      if(num_cached_items_ < MAX_CACHE_ITEMS) {
	
	int replace_index = num_cached_items_;
	// If object already exists in cache, update info if necessary
	for(int i = 0; i < num_cached_items_; ++i) {
	  if(tag_cache_[i].obj_name_ == obj_name && tag_cache_[i].origin_time_ < origin_time) {
	  replace_index = i;
	  break;
	  }
	}
	
	tag_cache_[replace_index].obj_name_ = obj_name;
	tag_cache_[replace_index].origin_time_ = origin_time;
	tag_cache_[replace_index].X_ = X;
	tag_cache_[replace_index].Y_ = Y;
	++num_cached_items_;
      }
      else {
	// Use LRU cache replacement
	int replace_index = 0;
	int least_time = tag_cache_[replace_index].origin_time_;
	for(int i = 0; i < MAX_CACHE_ITEMS; ++i) {
	  if(tag_cache_[i].origin_time_ < least_time)
	    replace_index = i;
      }
	tag_cache_[replace_index].obj_name_ = obj_name;
	tag_cache_[replace_index].origin_time_ = origin_time;
	tag_cache_[replace_index].X_ = X;
	tag_cache_[replace_index].Y_ = Y;
      }
    }
    else {
      // If this is a query pkt; check if we have the relevant information 
      // cached. TTL = 600 seconds for the cache entries
      found = FALSE;
      for(int i = 0; i < num_cached_items_; ++i) {
	if(tag_cache_[i].obj_name_ == obj_name && tag_cache_[i].origin_time_ > origin_time - 600) {
	  found = TRUE;
	  cache_index = i;
	  break;
	}
      }
    }
  }
  // Loop check i.e., if response to our query agent has looped back
  // Following not the correct condition to detect a loop!
  //  assert(!(iph->daddr() == myaddr_ && iph->dport() == 0));
  // Reduce the source route to just parent-children (O(#levels))
  // This is possible since parent and child in each others vicinity
  cmh->direction() = hdr_cmn::DOWN;
  if(iph->daddr() == myaddr_)
    query_for_us = TRUE;
  // Query pkt if X and Y are 65000
  if(X == 65000 && Y == 65000) {
    if(query_for_us || found) {
      if(qry_debug_)
	trace("Node %d: Rcved qry for us from node %d at time %f",myaddr_,last_hop_id,s.clock());
      if(!found)
	dst_nodes = search_tag(obj_name,prev_hop_level,next_hop_level,last_hop_id,&num_dst);
      if((num_dst == 0 && dst_nodes) || found) {
	delete dst_nodes;
	// if num_dst = 0 but dst_nodes is not NULL, we sense the
	// requested tag; add X,Y info and send response
	// if found is true, we have the cached information
	if(found) {
	  (*X_ptr++) = ((int)tag_cache_[cache_index].X_ >> 8) & 0xFF;
	  (*X_ptr) = ((int)tag_cache_[cache_index].X_) & 0xFF;
	  (*Y_ptr++) = ((int)tag_cache_[cache_index].Y_ >> 8) & 0xFF;
	  (*Y_ptr) = ((int)tag_cache_[cache_index].Y_) & 0xFF;
	}
	else {
	  node_->getLoc(&local_x, &local_y, &local_z);
	  (*X_ptr++) = ((int)local_x >> 8) & 0xFF;
	  (*X_ptr) = ((int)local_x) & 0xFF;
	  (*Y_ptr++) = ((int)local_y >> 8) & 0xFF;
	  (*Y_ptr) = ((int)local_y) & 0xFF;
	}
	// Send response
	iph->ttl_ = 1000;
	// Add 50 bytes to response 
	cmh->size() += 50;
	// Query from an agent at our node
	if(!num_src_hops) {
	  iph->daddr() = myaddr_;
	  iph->dport() = 0;
	  cmh->next_hop_ = myaddr_;
	}
	else {
	  --num_src_hops;
	  *num_src_hops_ptr = (num_src_hops >> 8) & 0xFF;
	  *(num_src_hops_ptr + 1) = num_src_hops & 0xFF;
	  // Decr pkt size
	  cmh->size() -= 4;
	  iph->daddr() = *last_hop_ptr++;
	  iph->daddr() = (iph->daddr() << 8) | *last_hop_ptr++;
	  if(!num_src_hops)
	    iph->dport() = 0;
	  else
	    iph->dport() = ROUTER_PORT;
	  
	  int relevant_level = *last_hop_ptr;
	  cmh->next_hop_ = get_next_hop(iph->daddr(),relevant_level);
	  //	  assert(cmh->next_hop_ != NO_NEXT_HOP);	  
	  if(cmh->next_hop_ == NO_NEXT_HOP) {
	    Packet::free(p);
	    trace("Node %d: Packet dropped because of no next hop info",myaddr_);
	    return;
	  }
	  *level_ptr = *last_hop_ptr;	  
	}
	//	if(found) 
	  //	  trace("Node %d: Gen response from cache at time %f to node %d",myaddr_,s.clock(),iph->daddr());
	//	else
	  //	  trace("Node %d: Gen response at time %f to node %d",myaddr_,s.clock(),iph->daddr() >> 8);
	if(!num_src_hops && iph->daddr() == myaddr_) {
	  // TEMPORARY HACK! Cant forward from routing agent to some other
	  // agent on our node!
	  Packet::free(p);
	  trace("Node %d: Found object %d.%d.%d at (%d,%d) at time %f",myaddr_, (obj_name >> 24) & 0xFF, (obj_name >> 16) & 0xFF, obj_name & 0xFFFF,X,Y,s.clock());
	  return;
	}
	else if(iph->daddr() == myaddr_) {
	  ForwardPacket(p);
	}
	else {
	  s.schedule(target_,p,0);
	}
      }
      else if(num_dst >= 1) {
	if(--iph->ttl_ == 0) {
	  drop(p, DROP_RTR_TTL);
	  return;
	}
	
	// Add ourself to source route and increase the number of src hops
	//	if(last_hop_id != myaddr_) {
	++num_src_hops;
	*num_src_hops_ptr = (num_src_hops >> 8) & 0xFF;
	*(num_src_hops_ptr+1) = num_src_hops & 0xFF;
	*pkt_end_ptr++ = (myaddr_ >> 8) & 0xFF;
	*pkt_end_ptr++ = myaddr_ & 0xFF;
	// Indicate the level of the pcl object that a node should look-up
	// to find the relevant routing table entry
	*pkt_end_ptr = (next_hop_level+1) & 0xFF;
	// Incr pkt size
	cmh->size() += 4;
	dst_ptr = dst_nodes;
	// Replicate pkt to each destination
	iph->daddr() = dst_ptr->dst_node_;
	iph->dport() = ROUTER_PORT;
	cmh->next_hop_ = dst_ptr->dst_next_hop_;
	cmh->addr_type_ = NS_AF_INET;
	// Copy next hop variable to this variable temporarily
	// Copy it back into packet before sending the packet
	int tmp_next_hop_level = dst_ptr->next_hop_level_;
	if(qry_debug_)
	  trace("Node %d: Forwarding qry to node %d at time %f",myaddr_,dst_ptr->dst_node_,s.clock());
	dst_ptr = dst_ptr->next_;
	delete dst_nodes;
	dst_nodes = dst_ptr;
	for(int i = 1; i < num_dst; ++i) {
	  if(qry_debug_)
	    trace("Node %d: Forwarding qry to node %d at time %f",myaddr_,dst_ptr->dst_node_,s.clock());
	  // Change level and copy the packet
	  *level_ptr = dst_ptr->next_hop_level_;
	  newp = p->copy();
	  new_iph = HDR_IP(newp);
	  new_cmh = HDR_CMN(newp);
	  new_iph->daddr() = dst_ptr->dst_node_;
	  new_iph->dport() = ROUTER_PORT;
	  new_cmh->next_hop_ = dst_ptr->dst_next_hop_;
	  new_cmh->addr_type_ = NS_AF_INET;
	  if(new_iph->daddr() == myaddr_)
	    ForwardPacket(newp);
	  else
	    s.schedule(target_,newp,0);
	  dst_ptr = dst_ptr->next_;
	  delete dst_nodes;
	  dst_nodes = dst_ptr;
	}
	
	*level_ptr = tmp_next_hop_level;
	if(iph->daddr() == myaddr_) {
	  ForwardPacket(p);
	}
	else
	  s.schedule(target_,p,0);
      }
      else if(num_dst == 0) {
	// Free packet if we dont have any dst to forward packet
	if(qry_debug_)
	  trace("Node %d: Dropping query from %d at time %f,num_src_hops %d",myaddr_,iph->saddr(),s.clock(),num_src_hops);
	
	Packet::free(p);
	return;
      }
    }
    else {
      // simply forward to next hop
      if(qry_debug_)
	trace("Node %d: Forwarding query to node %d at time %f,num_src_hops %d",myaddr_,iph->daddr(),s.clock(),num_src_hops);
      if(--iph->ttl_ == 0) {
	drop(p, DROP_RTR_TTL);
        return;
      }
      cmh->next_hop_ = get_next_hop(iph->daddr(),next_hop_level+1);
      //      assert(cmh->next_hop_ != NO_NEXT_HOP);	  
      if(cmh->next_hop_ == NO_NEXT_HOP) {
	Packet::free(p);
	trace("Node %d: Packet dropped because of no next hop info",myaddr_);
	return;
      }
      s.schedule(target_,p,0);
    }
  }
  else {
    // Forward the response packet
    if(qry_debug_)
      trace("Node %d: Forwarding response to node %d at time %f,num_src_hops %d",myaddr_,iph->daddr(),s.clock(),num_src_hops);
    if(--iph->ttl_ == 0) {
      drop(p, DROP_RTR_TTL);
      return;
    }
    // Check if query from an agent at our node
    if(query_for_us) {
      if(!num_src_hops) {
	iph->daddr() = myaddr_;
	iph->dport() = 0;
	cmh->next_hop_ = myaddr_;
      }
      else {
	--num_src_hops;
	*num_src_hops_ptr = (num_src_hops >> 8) & 0xFF;
	*(num_src_hops_ptr + 1) = num_src_hops & 0xFF;
	// Decr pkt size
	cmh->size() -= 4;
	
	iph->daddr() = *last_hop_ptr++;
	iph->daddr() = (iph->daddr() << 8) | *last_hop_ptr++;
	if(!num_src_hops)
	  iph->dport() = 0;
	else
	  iph->dport() = ROUTER_PORT;
	int relevant_level = *last_hop_ptr;
	cmh->next_hop_ = get_next_hop(iph->daddr(),relevant_level);
	//	assert(cmh->next_hop_ != NO_NEXT_HOP);	  
	if(cmh->next_hop_ == NO_NEXT_HOP) {
	  Packet::free(p);
	  trace("Node %d: Packet dropped because of no next hop info",myaddr_);
	  return;
	}
	
	*level_ptr = *last_hop_ptr;	  
      }
      if(!num_src_hops && iph->daddr() == myaddr_) {
	// TEMPORARY HACK! Cant forward from routing agent to some other
	// agent on our node!
	Packet::free(p);
	trace("Node %d: Found object %d.%d.%d at (%d,%d) at time %f",myaddr_, (obj_name >> 24) & 0xFF, (obj_name >> 16) & 0xFF, obj_name & 0xFFFF,X,Y,s.clock());
	return;
      }
      else if(iph->daddr() == myaddr_)
	ForwardPacket(p);
      else
	s.schedule(target_,p,0);      
    }
    else {
      cmh->next_hop_ = get_next_hop(iph->daddr(),next_hop_level);
      //      assert(cmh->next_hop_ != NO_NEXT_HOP);	  
      if(cmh->next_hop_ == NO_NEXT_HOP) {
	Packet::free(p);
	trace("Node %d: Packet dropped because of no next hop info",myaddr_);
	return;
      }
      s.schedule(target_,p,0);
    }
  }
}
NodeIDList *
LandmarkAgent::search_tag(int obj_name, int prev_hop_level, int next_hop_level,nsaddr_t last_hop_id, int *num_dst)
{
  ParentChildrenList *pcl = parent_children_list_;
  LMNode *child;
  compr_taglist *tag_ptr;
  int forward = FALSE;
  NodeIDList *nlist = NULL, *nlist_ptr = NULL;
  int p1, p2, p3, q1, q2, q3;
  int match = 0, exact_match = 0;
  *num_dst = 0;
  // Check if our node senses the requested tag
  while(pcl) {
    if(pcl->level_ == 0)
      break;
    pcl = pcl->next_;
  }
  if(!pcl)
    return(NULL);
  // if our node senses the tag, add the node to nlist but do not increase
  // num_dst
  tag_ptr = pcl->tag_list_;
  while(tag_ptr) {
    if(tag_ptr->obj_name_ == obj_name) {
      nlist = new NodeIDList;
      nlist->dst_node_ = myaddr_;
      nlist->dst_next_hop_ = myaddr_;
      return(nlist);
    }
    tag_ptr = tag_ptr->next_;
  }
  // If next_hop_level = 2, lookup would be done in the level 2 object
  // that would have level 1 tag aggregates
  //  if(next_hop_level == 2)
  //    obj_name = obj_name & 0xFFFF0000;
  //  else if(next_hop_level >= 3)
  //    obj_name = obj_name & 0xFF000000;
  p1 = (obj_name >> 24) & 0xFF;
  p2 = (obj_name >> 16) & 0xFF;
  p3 = obj_name & 0xFFFF;
  pcl = parent_children_list_;
  while(pcl) {
    if(pcl->level_ == next_hop_level)
      break;
    pcl = pcl->next_;
  }
  if(!pcl)
    return(NULL);
  //  assert(pcl);
  child = pcl->pchildren_;
  while(child) {
    // Dont forward back to child if child forwarded this query to us
    // We should forward to all children though if the message is going
    // down the hierarchy
    forward = FALSE;
    if(next_hop_level < prev_hop_level || (child->id_ != last_hop_id && next_hop_level >= prev_hop_level))
      forward = TRUE;
    if(child->child_flag_ == IS_CHILD && forward) {
      tag_ptr = child->tag_list_;
      match = 0;
      exact_match = 0;
      while(tag_ptr) {
	q1 = (tag_ptr->obj_name_ >> 24) & 0xFF;
	q2 = (tag_ptr->obj_name_ >> 16) & 0xFF;
	q3 = tag_ptr->obj_name_ & 0xFFFF;
	if(p1 == q1 && p2 == q2 && p3 == q3)
	  exact_match = 1;
	else if((p1 == q1 && p2 == q2 && !q3) || (p1 == q1 && !q2 && !q3))
	  match = 1;
	if(match) {
	  if(!nlist) {
	    nlist = new NodeIDList;
	    nlist_ptr = nlist;
	  }
	  else {
	    nlist_ptr->next_ = new NodeIDList;
	    nlist_ptr = nlist_ptr->next_;
	  }
	  nlist_ptr->dst_node_ = child->id_;
	  nlist_ptr->dst_next_hop_ = child->next_hop_;
	  nlist_ptr->next_hop_level_= next_hop_level - 1;
	  ++(*num_dst);
	  break;
	}
	else if(exact_match) {
	  // Delete all old elements
	  NodeIDList *n1, *n2;
	  n1 = nlist;
	  while(n1) {
	    n2 = n1;
	    n1 = n1->next_;
	    delete n2;
	  }
	  // Return just single element i.e., the ID of the child with an
	  // exact match for the object name
	  nlist = new NodeIDList;
	  nlist->dst_node_ = child->id_;
	  nlist->dst_next_hop_ = child->next_hop_;
	  nlist->next_hop_level_= next_hop_level - 1;
	  (*num_dst) = 1;
	  return(nlist);
	}
	tag_ptr = tag_ptr->next_;
      }
    }
    child = child->next_;
  }
  // Add parent if query is travelling up the hierarchy
  if(next_hop_level >= prev_hop_level && pcl->parent_) {
    if(!nlist) {
      nlist = new NodeIDList;
      nlist_ptr = nlist;
    }
    else {
      nlist_ptr->next_ = new NodeIDList;
      nlist_ptr = nlist_ptr->next_;
    }
    nlist_ptr->dst_node_ = (pcl->parent_)->id_;
    nlist_ptr->dst_next_hop_ = (pcl->parent_)->next_hop_;
    nlist_ptr->next_hop_level_= next_hop_level + 1;
    ++(*num_dst);
  }
  return(nlist);
}
nsaddr_t
LandmarkAgent::get_next_hop(nsaddr_t dst, int next_hop_level)
{
  ParentChildrenList *pcl = parent_children_list_;
  LMNode *pchild;
  while(pcl->level_ != next_hop_level) {
    pcl = pcl->next_;
  }
  
  assert(pcl);
  pchild = pcl->pchildren_;
  while(pchild) {
    if(pchild->id_ == dst)
      return(pchild->next_hop_);
    pchild = pchild->next_;
  }
  return(NO_NEXT_HOP);
}
void
LandmarkAgent::get_nbrinfo()
{
  ParentChildrenList *pcl;
  LMNode *pchild;
  int num_nbrs = 0;
  pcl = parent_children_list_;
  
  if(!pcl) {
    trace("Node %d: Neighbour info not available; perhaps the node is down");
    return;
  }
  while(pcl) {
    if(pcl->level_ == 1)
      break;
    pcl = pcl->next_;
  }
  //  assert(pcl);
  if(!pcl) {
    trace("Node %d: Neighbour info not available; perhaps the node is down");
    return;
  }
  pchild = pcl->pchildren_;
  //  assert(pchild);
  while(pchild) {
    if(pchild->num_hops_ == 1)
      ++num_nbrs;
    pchild = pchild->next_;
  }
  
  trace("Node %d: Number of neighbours: %d",myaddr_,num_nbrs);
}
void
LandmarkAgent::MoveTags() {
  ParentChildrenList *pcl = parent_children_list_;
  compr_taglist *tag = NULL, *prev_tag, *next_tag;
  int removed_tag = 0, our_tags_changed = 0;
  trace("Node %d: Moving tags at time %f", myaddr_,NOW);
  
  if(!pcl && !mobile_tags_) {
    Scheduler::instance().schedule(tag_mobility_,tag_mobility_event_,tag_rng_->uniform(mobility_period_));
    return;
  }
  
  if(pcl) {
    // Get level 0 pcl object
    while(pcl) {
      if(pcl->level_ == 0)
	break;
      pcl = pcl->next_;
    }
    assert(pcl);
  }    
  
  // Pick tag(s) at random and move them to one of the neighbours
  // Only tags with the last field > 5 are mobile.
  if(pcl)
    tag = pcl->tag_list_;
  else
    tag = mobile_tags_;
  
  prev_tag = tag;
  while(tag) {
    removed_tag = 0;
    // Tags with last field < 30 are not mobile
    if((tag->obj_name_ & 0xFFFF) > 30) {
      // Move tag to neighbouring node with probability of 0.3
      int n = tag_rng_->uniform(10);
      if(n <= 2) {
	assert(nbrs_);
	int nbr_index = tag_rng_->uniform(num_nbrs_);
	LandmarkAgent *nbr_agent = (LandmarkAgent *)AgentList::instance()->GetAgent(nbrs_[nbr_index]);
	assert(nbr_agent);
	trace("Node %d: Moving tag %d.%d.%d at time %f to nbr %d",myaddr_,(tag->obj_name_ >> 24) & 0xFF,(tag->obj_name_ >> 16) & 0xFF,tag->obj_name_ & 0xFFFF,NOW,nbrs_[nbr_index]);
	// Remove tag from our list
	removed_tag = 1;
	our_tags_changed = 1;
	if(prev_tag == tag) {
	  if(pcl)
	    pcl->tag_list_ = tag->next_;
	  else if(mobile_tags_)
	    mobile_tags_ = tag->next_;
	  prev_tag = tag->next_;
	}
	else
	  prev_tag->next_ = tag->next_;
	
	next_tag = tag->next_;
	if(pcl)
	  --(pcl->num_tags_);
	
	// Add this tag to neighbouring node
	nbr_agent->AddMobileTag(tag);
      }
    }
    if(!removed_tag) {
      prev_tag = tag;
      tag = tag->next_;
    }
    else {
      tag = next_tag;
    }
  }
  // Trigger hierarchy advertisement if our taglist has changed
  if(our_tags_changed)
    SendChangedTagListUpdate(our_tags_changed,0);
  
  Scheduler::instance().schedule(tag_mobility_,tag_mobility_event_,tag_rng_->uniform(mobility_period_));
}
void
LandmarkAgent::AddMobileTag(void *mobile_tag)
{
  ParentChildrenList *pcl = parent_children_list_;
  compr_taglist *tag = NULL, *new_tag = (compr_taglist *)mobile_tag;
  // Make sure that this tag object is not pointing to next member on
  // the previous list that this tag was part of
  new_tag->next_ = NULL;
  if(pcl) {
    // Get level 0 pcl object
    while(pcl) {
      if(pcl->level_ == 0)
	break;
      pcl = pcl->next_;
    }
    assert(pcl);
    ++(pcl->num_tags_);
    
    if(!pcl->tag_list_) {
      pcl->tag_list_ = new_tag;
    }
    else {
      tag = pcl->tag_list_;
      while(tag->next_) {
	tag = tag->next_;
      }
      tag->next_ = new_tag;
    }
  }
  else {
    if(!mobile_tags_) {
      mobile_tags_ = new_tag;
    }
    else {
      tag = mobile_tags_;
      while(tag->next_) {
	tag = tag->next_;
      }
      tag->next_ = new_tag;
    }
  }
  // Trigger hierarchy advertisements after a mean of 5 seconds if
  // the advt event has not already been scheduled
  if(tag_advt_event_->uid_ < 0)
    Scheduler::instance().schedule(tag_advt_handler_, tag_advt_event_, Random::uniform(10));
}
// new tag info received for specified level; Send updates if necessary
// i.e., if aggregates have changed etc.
void
LandmarkAgent::SendChangedTagListUpdate(int our_tag_changed, int level)
{
  ParentChildrenList *pcl = parent_children_list_;
  ParentChildrenList *child_pcl, *parent_pcl;
  compr_taglist *tag_ptr1 = NULL, *tag_ptr2 = NULL, *tag_list = NULL;
  compr_taglist *agg_tags = NULL;
  LMNode *lmnode;
  int upd_time, num_tags = 0;
  Scheduler &s = Scheduler::instance();
  double now = s.clock();
  if(node_dead_ || !pcl || level >= highest_level_)
    return;
  if(myaddr_ == 45)
    trace("Node %d: SendChangedTagListUpdate, level %d at time %f",myaddr_,level,now);
  while(pcl) {
    if(pcl->level_ == level)
      child_pcl = pcl;
    else if(pcl->level_ == level + 1) 
      parent_pcl = pcl;
    pcl = pcl->next_;
  }
  
  if(our_tag_changed) {
    assert(level == 0);
    upd_time = (int) now;
    upd_time = (upd_time << 16) | (parent_pcl->seqnum_ & 0xFFFF);
    ++(parent_pcl->seqnum_);
    parent_pcl->UpdatePotlChild(myaddr_, myaddr_,0,0,0,(int) node_->energy(),upd_time,IS_CHILD,FALSE,child_pcl->tag_list_);
    // Send out hierarchy advertisement since the tag list has changed
    Packet *newp = makeUpdate(child_pcl,HIER_ADVS,PERIODIC_ADVERTS);
    child_pcl->last_update_sent_ = now;
    s.schedule(target_,newp,0);
  }
  
  while(level < highest_level_) {
    if(myaddr_ == 45)
      trace("Node %d: Updating tag lists, level %d",myaddr_,level);
    
    lmnode = parent_pcl->pchildren_;
    tag_list = NULL;
    // Loop through all the children and add tags to tag_list
    while(lmnode) {
      if(lmnode->child_flag_ == IS_CHILD) {
	tag_ptr1 = lmnode->tag_list_;
    
	while(tag_ptr1) {
	  if(!tag_list) {
	    tag_list = new compr_taglist;
	    tag_ptr2 = tag_list;
	  }
	  else {
	    tag_ptr2->next_ = new compr_taglist;
	    tag_ptr2 = tag_ptr2->next_;
	  }
	  //        trace("tag name: %d.%d.%d",(tag_ptr1->obj_name_ >> 24) & 0xFF,(tag_ptr1->obj_name_ >> 16) & 0xFF,(tag_ptr1->obj_name_) & 0xFFFF);
	  tag_ptr2->obj_name_ = tag_ptr1->obj_name_;
	  tag_ptr1 = tag_ptr1->next_;
	}
      }
      lmnode = lmnode->next_;
    }
    
    // Aggregate tag_list
    agg_tags = aggregate_taginfo(tag_list,parent_pcl->level_,&num_tags);
    
    // Delete tag_list
    tag_ptr1 = tag_list;
    while(tag_ptr1) {
      tag_ptr2 = tag_ptr1;
      tag_ptr1 = tag_ptr1->next_;
      delete tag_ptr2;
    }
    
    if(!compare_tag_lists(parent_pcl->tag_list_,parent_pcl->num_tags_,agg_tags,num_tags)) {
      // Delete parent_pcl's tag_list and update with new tag_list
      tag_ptr1 = parent_pcl->tag_list_;
      while(tag_ptr1) {
	tag_ptr2 = tag_ptr1;
	tag_ptr1 = tag_ptr1->next_;
	delete tag_ptr2;
      }
      parent_pcl->tag_list_ = agg_tags;
      parent_pcl->num_tags_ = num_tags;
      // Send out hierarchy advertisement since the tag list has changed
      Packet *newp = makeUpdate(parent_pcl,HIER_ADVS,PERIODIC_ADVERTS);
      parent_pcl->last_update_sent_ = now;
      s.schedule(target_,newp,0);
   
      ++level;
      // Update our tag list in the higher level pcl object
      pcl = parent_children_list_;
      parent_pcl = NULL;
      child_pcl = NULL;
      while(pcl) {
	if(pcl->level_ == level)
	  child_pcl = pcl;
	else if(pcl->level_ == level + 1) 
	  parent_pcl = pcl;
	pcl = pcl->next_;
      }
      upd_time = (int) now;
      upd_time = (upd_time << 16) | (parent_pcl->seqnum_ & 0xFFFF);
      ++(parent_pcl->seqnum_);
      parent_pcl->UpdatePotlChild(myaddr_, myaddr_,0,0,0,(int) node_->energy(),upd_time,IS_CHILD,FALSE,child_pcl->tag_list_);
    }
    else {
      // Delete agg_tags
      tag_ptr1 = agg_tags;
      while(tag_ptr1) {
	tag_ptr2 = tag_ptr1;
	tag_ptr1 = tag_ptr1->next_;
	delete tag_ptr2;
      }
      break;
    }
  }
}
int
LandmarkAgent::compare_tag_lists(compr_taglist *tag_list1, int num_tags1, compr_taglist *tag_list2, int num_tags2)
{
  compr_taglist *tag1 = tag_list1, *tag2 = tag_list2;
  int found;
  // if num_tags == -1, it means that the number of tags was not computed
  if(num_tags1 == -1) {
    num_tags1 = 0;
    while(tag1) {
      ++num_tags1;
      tag1 = tag1->next_;
    }
    tag1 = tag_list1;
  }
  if(num_tags2 == -1) {
    num_tags2 = 0;
    while(tag2) {
      ++num_tags2;
      tag2 = tag2->next_;
    }
    tag2 = tag_list2;
  }
  if(num_tags1 != num_tags2)
    return(FALSE);
  while(tag1) {
    found = 0;
    while(tag2) {
      if(tag1->obj_name_ == tag2->obj_name_) {
	found = 1;
	break;
      }
      tag2 = tag2->next_;
    }
    if(!found)
      return(FALSE);
    tag1 = tag1->next_;
  }
  return(TRUE);
}

						