landmark.cc

柯老师网站上找到的

      //      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)