locserver.cc

在Linux下做的QuadTree的程序

      //if ((!inSameGrid(myloc,hgpsh->update_loc_)) && (!inSameGrid(hgpsh->dst_loc_, hgpsh->update_loc_))) {
      if ((!inSameGrid(myloc,hgpsh->update_loc_))) {

	  if (hgpsh->in_correct_grid_ && (iph->dst()!=parent->myaddr_)) {
	      //This packet has been in the correct grid before, probably the previous guy just asks me to relay the packet
	      router->sendOutPktWithLocation(packet,0.0,true);
	      return;
	  }

	  /* if somebody mistook me as being in the to-be-updated grid, or
	     the update packet has been in the to-be-updated grid before, 
	     i should try to forward to somebody I know that's closer to 
	     dst in ID space than me.  and who is actually in that to-be-updated grid*/
	  if (hgpsh->in_correct_grid_) {
	  }else if ((iph->dst() == parent->myaddr_) && ((hgpsh->dst_loc_.mask == BIGGEST_MASK) && inSameGrid(hgpsh->dst_loc_,hgpsh->update_loc_))) {
	    hgps->in_correct_grid_ = 1;
	  }else{
	    hgpsh->dst_loc_ = hgpsh->update_loc_;
	    iph->dst() = 0;
	    parent->trace("HGPS: _%d_(grid %d) forward update(%d) to correct grid %d",parent->myaddr_,myloc.loc,iph->src(),hgpsh->update_loc_.loc);
	    router->sendOutPktWithLocation(packet,0.0,true);
	    return;
	  }
      }else {
	  if (!hgpsh->in_correct_grid_) {
	    hgpsh->in_correct_grid_ = 1;
	    iph->dst() = 0;
	  }
      }

      /* see if I have to forward the packet on or should I just update my own location table*/
      if (hgpsh->next_locserver_ != 0) {
	  closest.id = hgpsh->locservers_[hgpsh->next_locserver_-1].id;
	  closest.loc = hgpsh->locservers_[hgpsh->next_locserver_-1].loc;
      }else{
	  closest.id = 0;
      }

      table->findClosestExceptDst(parent->myaddr_,myloc,iph->src(),router->nt,hgpsh->update_loc_,closest);

      if ( closest.id == parent->myaddr_) {

	  //I am the closest node to the updater, i should keep his information
	  if (parent->verbose_) {
	      parent->trace("HGPS: _%d_(%d) add (%d,loc %d) update area(%d,%d) to table %.5f",parent->myaddr_,
		      myloc.loc,iph->src(),hgpsh->src_loc_.loc,hgpsh->update_loc_.loc,hgpsh->update_loc_.mask,(Scheduler::instance().clock()+hgpsh->timeout_interval_));
	  }
	  hgpsh->src_loc_.mask = hgpsh->update_loc_.mask;
	  table->addUpdateEntry(iph->src(),hgpsh->src_loc_,hgpsh->timeout_inteval_);
	  Packet::free(packet);
      
      }else if ((!iph->dst()) || (closest.id != hgpsh->locservers_[hgpsh->next_locserver_-1].id)) {
	  
	  hgpsh->locservers_[0].id = closest.id;
	  hgpsh->locservers_[0].loc = closest.loc;
	  hgpsh->next_locserver_ = 1;
	  iph->dst() = closest.id;
	  hgpsh->dst_loc_ = closest.loc;
	  //hgpsh->lastupdate_dst_time_ = closest.lastupdate_time;
	  hgpsh->prev_hop_num_ = 0;

	  router->sendOutPktWithLocation(packet,0.0,true);
	  
      }else { //closest.id == hgpsh->locservers_[hgpsh->next_locserver-1].id
	 
	  if (iph->dst() == parent->myaddr_) {
	      assert(hgpsh->locservers_[hgpsh->next_locserver_ - 1].id == parent->myaddr_);	
	      hgpsh->next_locserver_--;
	      if (hgpsh->next_locserver_ == 0) {
		  //location query failure
		  if (parent->verbose_) {
		      parent->trace("HGPS %.5f _%d_ loc update location failure %d(%d,%d)",Scheduler::instance().clock(),parent->myaddr_,iph->src(),hgpsh->update_loc_.loc,hgpsh->update_loc_.mask);
		  }
		  Packet::free(packet);
		  return;
	      }
	      iph->dst() = hgpsh->locservers_[hgpsh->next_locserver_ - 1].id;
	      hgpsh->dst_loc_ = hgpsh->locservers_[hgpsh->next_locserver_-1].loc;
	      assert(inSameGrid(myloc,hgpsh->dst_loc_));
	  }
	  //check if I am in the same grid as the destination grid and need to restart query
	  if (inSameGrid(myloc, hgpsh->dst_loc_) && (hgpsh->dst_loc_.mask != BIGGEST_MASK)) {
	      //I have to query for iph->dst in order to continue
	      bool exists = table->findClosestInGrid(parent->myaddr_,myloc,iph->dst(),hgpsh->dst_loc_,router->nt,closest,0.0); //jinyang -- I'm not using hgpsh->lastupdate_dst_time_, worth more consideration
	      if (!exists) {
		  //location query failure
		  parent->trace("HGPS %.5f _%d_(%d) update loc failure %d(%d %d)->%d",Scheduler::instance().clock(),parent->myaddr_,myloc.loc,iph->src(),hgpsh->update_loc_.loc,hgpsh->update_loc_.mask,iph->dst());
		  Packet::free(packet);
		  return;
	      }
	      if (parent->verbose_) {
		  parent->trace("HGPS _%d_ (update myloc %d) recursive query for next location server %d (%d,%d), find server %d(%d,%d)", parent->myaddr_,myloc.loc,iph->dst(),hgpsh->dst_loc_.loc,hgpsh->dst_loc_.mask,closest.id,closest.loc.loc,closest.loc.mask);
	      }


	      //put iph->dst() in hgpsh->locservers_
	      assert(hgpsh->next_locserver_<MAX_LOC_SERVERS);
	      if (iph->dst()!=closest.id) {
		  hgpsh->locservers_[hgpsh->next_locserver_].loc = closest.loc;
		  hgpsh->locservers_[hgpsh->next_locserver_].id = closest.id;
		  hgpsh->next_locserver_++;
	      }

	      iph->dst() = closest.id;
	      hgpsh->dst_loc_ = closest.loc;
	      //hgpsh->lastupdate_dst_time_ = closest.lastupdate_time;
	      hgpsh->prev_hop_num_ = 0;
	  }

	  router->sendOutPktWithLocation(packet,0.0,true);
      }
}

#else

void 
LocServer::recvUpdate(Packet *packet)
{
      hdr_hgps *hgpsh =  (hdr_hgps*)packet->access(parent->off_hgps_);
      hdr_ip *iph =  (hdr_ip*)packet->access(parent->off_ip_);
      loc_entry closest;
      assert(hgpsh->type_ == LOC_UPDATE);

      int divide = (BIGGEST_MASK - hgpsh->update_loc_.mask + 2)/2;
      loc_cache->addUpdateEntry(iph->src(),hgpsh->src_loc_,(double)(hgpsh->timeout_inteval_/divide));


      /* if I'm not in the update area, forward the packet on*/
      if ((!inSameGrid(myloc,hgpsh->update_loc_))) {

	  if (hgpsh->in_correct_grid_ && (iph->dst()!=parent->myaddr_)) {
	      //This packet has been in the correct grid before, probably the previous guy just asks me to relay the packet
	      parent->trace("HGPS: _%d_ forward directly to %d(%d) in update area (%d,%d)",parent->myaddr_,iph->dst(),hgpsh->dst_loc_.loc,hgpsh->update_loc_.loc,hgpsh->update_loc_.mask);
	      router->sendOutPktWithLocation(packet,0.0,true);
	      return;
	  }

	  if (hgpsh->in_correct_grid_) {
	      
           /* if somebody mistook me as being in the to-be-updated grid, or
	     the update packet has been in the to-be-updated grid before, 
	     i should try to forward to somebody I know that's closer to 
	     dst in ID space than me.  and who is actually in that to-be-updated grid*/
	  }else if ((iph->dst() == parent->myaddr_) && ((hgpsh->dst_loc_.mask == BIGGEST_MASK) && inSameGrid(hgpsh->dst_loc_,hgpsh->update_loc_))) {
	    hgpsh->in_correct_grid_ = 1;
	  }else{
	    hgpsh->dst_loc_ = hgpsh->update_loc_;
	    iph->dst() = 0;
	    parent->trace("HGPS: _%d_(grid %d) forward update(%d) to correct grid %d",parent->myaddr_,myloc.loc,iph->src(),hgpsh->update_loc_.loc);
	    router->sendOutPktWithLocation(packet,0.0,true);
	    return;
	  }
      }else {
	  hgpsh->in_correct_grid_ = 1;
      }

      /* see if I have to forward the packet on or should I just update my own location table*/
      if (iph->dst()) {
	  closest.id = iph->dst();
	  closest.loc = hgpsh->dst_loc_;
      }

      table->findClosestExceptDst(parent->myaddr_,myloc,iph->src(),router->nt,hgpsh->update_loc_,closest);

      if ( closest.id == parent->myaddr_) {
	  //I am the closest node to the updater, i should keep his information
	  if (parent->verbose_) {
	      parent->trace("HGPS: _%d_(%d) add (%d,loc %d) update area(%d,%d) to table %.5f",parent->myaddr_,
		      myloc.loc,iph->src(),hgpsh->src_loc_.loc,hgpsh->update_loc_.loc,hgpsh->update_loc_.mask,(Scheduler::instance().clock()+hgpsh->timeout_inteval_));
	  }
	  table->addUpdateEntry(iph->src(),hgpsh->src_loc_,hgpsh->timeout_inteval_);
	  Packet::free(packet);
      }else {
	  hgpsh->dst_loc_ = closest.loc;
	  //I should forward the packet to the closest next guy
	  if (parent->verbose_) {
	      parent->trace("HGPS: _%d_(%d) forward to %d(%d,%d) nearer to (%d)",parent->myaddr_,myloc.loc,closest.id,closest.loc.loc,closest.loc.mask,iph->src());
	  }
	  if (iph->dst() != closest.id) {
	    hgpsh->prev_hop_num_ = 0;
	    iph->dst() = closest.id;
	   }
	  router->sendOutPktWithLocation(packet,0.0,true);
      }
}
#endif

/* hgpsagent calls this function to obtain the location information for dst
   it returns immmediately if dst is in loc_cache or loc_table
   otherwise, a LOC_QUERY is sent out in search of dst's location server */

bool
LocServer::getLocation(nsaddr_t dst, location & dst_loc)
{

    double now = Scheduler::instance().clock();
    loc_entry closest;
    bool exists = false;

    dst_loc.loc = -1;
    dst_loc.mask = BIGGEST_MASK;

    //try to get location from location cache
    loc_entry *entry = loc_cache->getEntry(dst,now);

    if (entry && ((now - entry->lastupdate_time)<CACHE_VALID_TIME)) { 
	dst_loc = entry->loc;
	if (parent->verbose_) {
	    parent->trace("S$hit cache %.5f _%d_ ??->%d(%d)",now,parent->myaddr_,dst,dst_loc.loc);
	}

#ifndef TEST_QUERY
	/* according to the actual protocol, the location of the dst is considered known and data pkt
	   could be sent. If this program is used for testing accuracy of GLS
	   query, a query packet is directly sent to the dst to check that the location is
	   indeed valid. */
	return true;
#else
        closest.id = dst;
        closest.loc = entry->loc;
        goto SEND_Q;
#endif
    }

    exists= table->findClosest(parent->myaddr_,myloc,dst,router->nt,closest,0.0);

    if (exists && (closest.id == dst)) {
	 if (parent->verbose_) {
	     parent->trace("S$hit loc table %.5f _%d_ ??->%d(%d)",now,parent->myaddr_,
		     dst,(closest.loc).loc);
	 }
	dst_loc = closest.loc;

#ifndef TEST_QUERY
	/* if the program is used for testing query only, a GLS query is still sent to
	   check that the location is indeed valid.*/
	return true;
#else
        goto SEND_Q;
#endif
    }

    if (!exists) {
	//in desperation, I search in the cache and 2-hop routing table. this should happen very rarely.
	exists = loc_cache->findClosest(parent->myaddr_,myloc,dst,router->nt,closest,0.0);
	if (exists && ((now-closest.lastupdate_time)<CACHE_VALID_TIME)) {
#ifdef HGPS_DEBUG
	    printf("_%d_ my cache saved this loc query ->%d\n",parent->myaddr_,dst);
#endif
	}else if ((exists = table->findClosestinRT(parent->myaddr_,myloc,dst,router->nt,closest,false))){
#ifdef HGPS_DEBUG
	    printf("_%d_ my routing table saved this loc query from %d->%d\n",parent->myaddr_,parent->myaddr_,dst);
#endif
	}else {
	    assert(parent->asleep == false);
#ifdef TEST_WS
	    /* if the program is in testing node up and down mode, I could infer some reasons
	       for the failure of location query */
	    if ((now - parent->wakeup_time) < 10) {//just some threshold value
		//it's because i have not stayed alive long enough
		parent->trace("HGPS %.5f _%d_ loc-query-failure-3(%d %d)%d->%d",now,parent->myaddr_,parent->myaddr_,dst,parent->myaddr_,dst);
	    }else {
		double his_wakeuptime = (God::instance()->wakeup_list)[dst];
		if ((now-his_wakeuptime)<10) {
		    //this is because the other guy has not stayed alive long enough
		    parent->trace("HGPS %.5f _%d_ loc-query-failure-4(%d %d)%d->%d",now,parent->myaddr_,parent->myaddr_,dst,parent->myaddr_,dst);
		}else {
#endif
		    printf("LOC QUERY FAILED _%d_ %d->%d\n",parent->myaddr_,parent->myaddr_,dst);
		    parent->trace("HGPS %.5f _%d_ loc-query-failure-2(%d %d)%d->%d",now,parent->myaddr_,parent->myaddr_,dst,parent->myaddr_,dst);
#ifdef TEST_WS
		}
	    }
#endif
	    return false;
	}
    }

SEND_Q:

    HGPSEntry *e = request_table.getHGPSEntry(dst);

    Packet *pkt = parent->allocpkt();
    hdr_hgps *hgpsh =  (hdr_hgps*)pkt->access(parent->off_hgps_);
    hdr_ip *iph =  (hdr_ip*)pkt->access(parent->off_ip_);
    hdr_cmn *cmnh =  (hdr_cmn*)pkt->access(parent->off_cmn_);
     
   
    hgpsh->init();
    hgpsh->type_ = LOC_QUERY;
    hgpsh->id_ = dst;
    hgpsh->src_loc_ = getGrid();
    
    iph->dport_ = RT_PORT;
    iph->src() = parent->myaddr_;

    cmnh->ptype() = PT_HGPS;
    cmnh->num_forwards() = 0;
    cmnh->size() = hgpsh->size();

    hgpsh->dst_loc_ = closest.loc;
    iph->dst() = closest.id;

    hgpsh->locservers_[0].id = closest.id;
    hgpsh->locservers_[0].loc = closest.loc;
    hgpsh->next_locserver_ = 1;

    if (BackOffTest(e,now)) {
	parent->trace("HGPS %.5f _%d_ new-loc-query %d->%d(%d)",now,parent->myaddr_,iph->src(),iph->dst(),dst);
	router->sendOutPktWithLocation(pkt,0.0,true,true);
    }else{
	if (parent->verbose_) {
	    parent->trace("HGPS LOC_QUERY not sent %.5f _%d_ %d(%d)",now,parent->myaddr_,iph->src(),dst);
	}
	Packet::free(pkt);
    }
    return true;
}

#ifdef TRIGGER_UPDATE_ONLY

void
LocServer::recvQuery(Packet *pkt, bool dst_loc_failure)
{
    hdr_hgps *hgpsh =  (hdr_hgps*)pkt->access(parent->off_hgps_);
    hdr_ip *iph =  (hdr_ip*)pkt->access(parent->off_ip_);

    loc_entry closest;
    loc_entry *cache_ent;
    bool exists;
    double now = Scheduler::instance().clock();

    /* if location failure is encountered immediately at this node, routing layer
    would call function recvQuery again with dst_loc_failure set to true */
    if (dst_loc_failure) {
        parent->trace("HGPS %.5f _%d_ loc-query-failure-1(%d %d)%d->%d",now,parent->myaddr_,parent->myaddr_,hgpsh->id_,iph->src(),iph->dst());
	Packet::free(pkt);
	return;
    }

    /* the query target is me. Send out GLS response packet immediately */
    if (hgpsh->id_ == parent->myaddr_) {
	if (parent->verbose_) {
	    parent->trace("HGPS %.5f _%d_ loc-reply-sent %d->%d about %d(%d)", Scheduler::instance().clock(),
		parent->myaddr_, parent->myaddr_, iph->src(), hgpsh->id_, hgpsh->src_loc_);
	}
	
	//send out the GLS RESPONSE
	Packet *p = parent->allocpkt();

	hdr_hgps *new_hgpsh =  (hdr_hgps*)p->access(parent->off_hgps_); 
	hdr_ip *new_iph =  (hdr_ip*)p->access(parent->off_ip_); 
	hdr_cmn *new_cmnh =  (hdr_cmn*)p->access(parent->off_cmn_);
	new_iph->dport_ = RT_PORT;
	new_iph->src() = parent->myaddr_;

	new_hgpsh->init();
	new_hgpsh->src_loc_ = getGrid();
	new_hgpsh->type_ = LOC_QUERY_RESPONSE;

	new_hgpsh->loc_ = new_hgpsh->src_loc_;
	new_hgpsh->id_ = parent->myaddr_;
	new_iph->dst() = iph->src();
	new_hgpsh->dst_loc_ = hgpsh->src_loc_;

	//copy the variable for recording how many steps GLS query has taken
	new_hgpsh->query_forwards_ = hgpsh->query_forwards_; 

	new_cmnh->ptype() = PT_HGPS;
	new_cmnh->size() = new_hgpsh->size();

	Packet::free(pkt);
	router->sendOutPktWithLocation(p,0.0,true);
	return;
    }

    if ((iph->dst() == hgpsh->id_) && (hgpsh->dst_loc_.mask == BIGGEST_MASK)){
	//inform me of any location failures for this packet
	router->sendOutPktWithLocation(pkt,0.0,true,true);
	return;

    }else {//iph->dst()!=hgpsh->id_ , the dst location is not known yet

	//check cache for direct location entry for dst first, (just a slight optimization)
	if ((cache_ent=loc_cache->getEntry(hgpsh->id_,now))  
	    && ((now - cache_ent->lastupdate_time)<CACHE_VALID_TIME)
	    && ((iph->dst() != hgpsh->id_)||(cache_ent->lastupdate_time > hgpsh->lastupdate_time_))) {
	    
	    //good good it hits the cache!
	    parent->trace("HGPS %.2f _%d_ cache-reply-sent (%d->%d)", now, parent->myaddr_, iph->src(),hgpsh->id_);
	    closest.id = hgpsh->id_;
	    closest.loc = cache_ent->loc;
	    closest.lastupdate_time = cache_ent->lastupdate_time;
	    router->sendOutPktWithLocation(pkt,0.0,true,true);
	    return;

	} else {

	    exists = table->findClosest(parent->myaddr_,myloc,hgpsh->id_,router->nt,closest,hgpsh->lastupdate_dst_time_);
	    if (!exists) {
		goto QUERY_AGAIN;	
	    }
	}
    }
		
   //I'll have to forward the query packet on...
    if ((!iph->dst())||closer(closest.id, hgpsh->locservers_[0].id,hgpsh->id_)) {
	iph->dst() = closest.id;
	//hgpsh->lastupdate_dst_time_ = closest.lastupdate_time;
	hgpsh->dst_loc_ = closest.loc;
	hgpsh->prev_hop_num_ = 0;
	//put the loc server that is the closest to hgpsh->id_ on the head of the list, removing the old list
	hgpsh->locservers_[0].id = iph->dst();
	hgpsh->locservers_[0].loc = closest.loc;
	hgpsh->next_locserver_ = 1;

    }else if ((closest.id == iph->dst()) && ((closest.lastupdate_time-0.1) > hgpsh->lastupdate_time_)) {
	hgpsh->lastupdate_time_ = closest.lastupdate_time;
	hgpsh->dst_loc_ = closest.loc;
	//hgpsh->lastupdate_dst_time_ = closest.lastupdate_time; 
    }

QUERY_AGAIN:
    bool check_exempted = false;
    if (iph->dst() == parent->myaddr_) {
	assert(hgpsh->locservers_[hgpsh->next_locserver_ - 1].id == parent->myaddr_);	
	//assert(inSameGrid(hgpsh->locservers_[hgpsh->next_locserver_-1].loc,hgpsh->dst_loc_));
	check_exempted = true;
	hgpsh->next_locserver_--;
	if (hgpsh->next_locserver_ == 0) {
	    //location query failure
	    parent->trace("HGPS %.5f _%d_ loc-query-failure-1(%d %d)%d->%d",now,parent->myaddr_,parent->myaddr_,hgpsh->id_,iph->src(),iph->dst());
	    Packet::free(pkt);
	    return;
	}
	iph->dst() = hgpsh->locservers_[hgpsh->next_locserver_ - 1].id;
	hgpsh->dst_loc_ = hgpsh->locservers_[hgpsh->next_locserver_-1].loc;
    }
    //check if I am in the same grid as the destination grid and need to restart query
    if ((check_exempted || inSameGrid(myloc, hgpsh->dst_loc_)) && (hgpsh->dst_loc_.mask != BIGGEST_MASK)) {
	//I have to query for iph->dst in order to continue
	exists = table->findClosestInGrid(parent->myaddr_,myloc,iph->dst(),hgpsh->dst_loc_,router->nt,closest,0.0); //jinyang hgpsh->lastupdate_dst_time_ has been deleted here
	if (parent->verbose_) {
	    parent->trace("HGPS _%d_ recursive query for next location server %d (%d,%d), find server %d(%d,%d)", parent->myaddr_,iph->dst(),hgpsh->dst_loc_.loc,hgpsh->dst_loc_.mask,closest.id,closest.loc.loc,closest.loc.mask);
	}

	if (!exists) {
	    //location query failure
	    parent->trace("HGPS %.5f _%d_ loc-query-failure-1(%d %d)%d->%d",now,parent->myaddr_,parent->myaddr_,hgpsh->id_,iph->src(),iph->dst());
	    Packet::free(pkt);
	    return;
	}
	//put iph->dst() in hgpsh->locservers_
	assert(hgpsh->next_locserver_<MAX_LOC_SERVERS);
	if (closest.id!=iph->dst()) {
	    hgpsh->locservers_[hgpsh->next_locserver_].loc = closest.loc;
	    hgpsh->locservers_[hgpsh->next_locserver_].id = closest.id;
	    hgpsh->next_locserver_++;
	}
	iph->dst() = closest.id;
	hgpsh->dst_loc_ = closest.loc;
	//hgpsh->lastupdate_dst_time_ = closest.lastupdate_time;
    }

    router->sendOutPktWithLocation(pkt,0.0,true,true);
}