landmark.cc

柯老师网站上找到的

    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->access(off_ip_);
  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);
      }