/* * 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: /nfs/jade/vint/CVSROOT/ns-2/sensor-nets/landmark.cc,v 1.8 2005/08/25 18:58:12 johnh Exp $ // Author: Satish Kumar, kkumar@isi.edu #include #include #include "landmark.h" #include #include #include 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, %d\n",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 %f\n",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 %f\n", 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 ProcessHierUpdate\n",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 ProcessHierUpdate\n",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 %d\n",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 here\n"); 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("ProcessHierUpdate2\n"); // 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,%d\n",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,%d\n",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,%d\n",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 %d\n", 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 %d\n",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,%d\n",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:%d\n", 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: %d\n", pcl->num_potl_children_); if(myaddr_ == 166) { trace("Number of children: %d\n", pcl->num_children_); trace("Number of level %d nodes heard: %d\n", (pcl->level_)-1, pcl->num_heard_); trace("Number of potl parent: %d\n", 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 failed\n", __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 failed\n", __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 failed\n", __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 failed\n", 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 timer\n"); 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); }