landmark.cc

柯老师网站上找到的

    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->access(off_ip_);
	    new_cmh = (hdr_cmn *) newp->access (off_cmn_);
	    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->access(off_ip_);
	  cmh = (hdr_cmn *) p->access (off_cmn_);
	  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->access(off_ip_);
  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;