locserver.cc

在Linux下做的QuadTree的程序

#else

/* this function handles GLS query packet */
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) {
	//check info in my fp_table
	for (int i=0;i<MAX_FP_TABLE_SIZE;i++) {
	   if(fp_table[i].id == iph->dst()) {
	       //my forwarding pointer saved this query
	       if ((fp_table[i].lastupdate_time > hgpsh->dst_loc_time_) && (hgpsh->dst_loc_.loc != fp_table[i].loc.loc)) {
		  hgpsh->dst_loc_ = fp_table[i].loc;
		  hgpsh->dst_loc_time_ = fp_table[i].lastupdate_time;
		  if (iph->dst() == hgpsh->id_) {
		      hgpsh->lastupdate_dst_time_ = fp_table[i].lastupdate_time;
		  }
		  if (parent->verbose_) {
		    parent->trace("HGPS %.5f _%d_ fp directs to new loc %d for loc server %d (query %d->%d)",Scheduler::instance().clock(),hgpsh->dst_loc_,iph->dst(),iph->src(),hgpsh->id_);
		  }
		  //send out the pkt, if there is error again, just discard the packet
		  router->sendOutPktWithLocation(pkt,0.0,true,false);
		  return;
	       }
	       break;
	    }
	}
	/* if location failure is encountered for the dst, and forwarding pointers
	       did not save the query, the query is restarted */
	if (iph->dst() == hgpsh->id_) {
	    table->deleteEntry(iph->dst());
	    loc_cache->deleteEntry(iph->dst());
	    iph->dst() = 0; 
	}else{
	    // forwarding pointer could not save the query, discard!
	    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_){
	/*location for the query target is known, forward GLS Query directly to dst*/
	//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;

	} else {

	    exists = table->findClosest(parent->myaddr_,myloc,hgpsh->id_,router->nt,closest,hgpsh->lastupdate_dst_time_);
	    if (!exists) {
		if ((iph->dst()) && (closer(iph->dst(),parent->myaddr_,hgpsh->id_))) {
		    router->sendOutPktWithLocation(pkt,0.0,true,true);
		}else{
		    assert(parent->asleep == false);
		    parent->trace("HGPS %.5f _%d_ loc-query-failure-2(%d %d)%d->%d",now,parent->myaddr_,parent->myaddr_,hgpsh->id_,iph->src(),iph->dst());
		    Packet::free(pkt);
		}
		return;
	    }
	    /*
	    if (!exists) {
		//check cache first
		exists = loc_cache->findClosest(parent->myaddr_,myloc,hgpsh->id_,router->nt,closest,hgpsh->lastupdate_dst_time_);
		if (exists && ((now-closest.lastupdate_time)<CACHE_VALID_TIME)) {
#ifdef HGPS_DEBUG
		    printf("_%d_ my cache saved this loc query from %d->%d\n",parent->myaddr_,iph->src(),hgpsh->id_);
#endif
		}else if ((exists = table->findClosestinRT(parent->myaddr_,myloc,hgpsh->id_,router->nt,closest,false))){
#ifdef HGPS_DEBUG
		    printf("_%d_ my routing table saved this loc query from %d->%d\n",parent->myaddr_,iph->src(),hgpsh->id_);
#endif
		}else {
		    //relay the packet if iph->dst() is closer to the dst than myself in ID space
		    if ((iph->dst()) && closer(iph->dst(),parent->myaddr_,hgpsh->id_)) {
			router->sendOutPktWithLocation(pkt,0.0,true,true);
		    }else{
			assert(parent->asleep == false);
#ifdef TEST_WS
			//infer some potential reasons for query failure if the program is in Test wake sleep mode
			if ((now - parent->wakeup_time) < 10) {
			    //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_,hgpsh->id_,iph->src(),iph->dst());
			}else{
			    double his_wakeuptime = (God::instance()->wakeup_list)[hgpsh->id_];
			    if ((now-his_wakeuptime)<7) {
				//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_,hgpsh->id_,parent->myaddr_,hgpsh->id_);
			    }else{
#endif
#ifdef HGPS_DEBUG
				printf("HGPS DROP: LOC QUERY FAILED _%d_ %d->%d asking for %d\n",parent->myaddr_,iph->src(),iph->dst(), hgpsh->id_);
#endif
				parent->trace("HGPS %.5f _%d_ loc-query-failure-2(%d %d)%d->%d",now,parent->myaddr_,parent->myaddr_,hgpsh->id_,iph->src(),iph->dst());
#ifdef TEST_WS
			    }
			}
#endif
			Packet::free(pkt);
		    }
		return;
		}
	    }
	    */

	}

    }

   //I'll have to forward the query packet on...
    if ((!iph->dst())||closer(closest.id, iph->dst(),hgpsh->id_)) { 
	iph->dst() = closest.id;
	if (iph->dst() == hgpsh->id_) {
	    hgpsh->lastupdate_dst_time_ = closest.lastupdate_time;
	}
	hgpsh->dst_loc_ = closest.loc;
	hgpsh->prev_hop_num_ = 0;
    }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;
	if (iph->dst() == hgpsh->id_) {
	    hgpsh->lastupdate_dst_time_ = closest.lastupdate_time;
	}

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

#endif

/* this function is invoked when the query's initiator gets a query reply back */
void
LocServer::recvQueryResponse(Packet *pkt)
{
    hdr_hgps *hgpsh =  (hdr_hgps*)pkt->access(parent->off_hgps_);
 
    //i've received a query response, cache it!!
    loc_cache->addUpdateEntry(hgpsh->id_,hgpsh->loc_,hgpsh->timeout_inteval_);
    parent->trace("HGPS %.5f _%d_ loc-reply-received %d %d %d(%d)",Scheduler::instance().clock(),
	    parent->myaddr_,hgpsh->query_forwards_,hgpsh->query_response_forwards_,hgpsh->id_,hgpsh->loc_);
    parent->notifyLocation(hgpsh->id_,hgpsh->loc_);
    
    Packet::free(pkt);
}

void
LocServer::checkPeriodicUpdateLoc()
{
    double x, y, z;
    mynode->getLoc(&x,&y,&z);
    double dist = sqrt((x-prev_x)*(x-prev_x) + (y-prev_y)*(y-prev_y));
    double now = Scheduler::instance().clock();

    if ((dist >= parent->update_distance_) || (now > prev_timeout)) {
	// the second hierarchy level 's update rate is one half of the first level's etc. etc.
	prev_level = prev_level+2;
	int max =(int)pow(2,max_mask/2);
	if (prev_level > max) {
	    prev_level = 2; //reset prev_level
	}
	int level = 0;
	int tmp_prev_level = prev_level;
	while (tmp_prev_level % 2 == 0) {
	    level += 2;
	    tmp_prev_level = tmp_prev_level >> 1;
	}
	if (parent->myaddr_ == 1) {
	    printf("updating level %d %d\n",level, prev_level);
	}
	updateLoc(level);
	prev_timeout= now + (double)2 * parent->update_distance_/getSpeed();
	prev_x = x;
	prev_y = y;
    }

    Packet *pkt;
    hdr_hgps *hgpsh;
    hdr_cmn *cmnh;
    hdr_ip *iph;
    //inform the sources of active connections about location change
    if (myloc.loc != curr_loc.loc) {
	//update all my live connection peers!
	for (int i=0;i<live_connections->size;i++) {
	    if ((now-live_connections->table[i].lastupdate_time)< LIVE_CONN_TIMEOUT) {

		pkt = parent->allocpkt();

		hgpsh =  (hdr_hgps*)pkt->access(parent->off_hgps_); 
		iph =  (hdr_ip*)pkt->access(parent->off_ip_); 
		cmnh =  (hdr_cmn*)pkt->access(parent->off_cmn_);

		iph->dport_ = RT_PORT;
		iph->dst() = live_connections->table[i].id;
		iph->src() = parent->myaddr_;

		hgpsh->init();
		hgpsh->type_ = LOC_NOTIFICATION;
		hgpsh->dst_loc_ = live_connections->table[i].loc;
		hgpsh->src_loc_ = myloc;

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

		router->sendOutPktWithLocation(pkt,0.0,false);
	    }
	}
	curr_loc = myloc;
    }
 
}

void
LocServer::logTableSize()
{
    parent->trace("HGPS LocTable _%d_ %d",parent->myaddr_,table->printTableNum());
}

/* this function sends out a broadcast location update packet to 
   the node's old grid (which_loc) */
void
LocServer::updateFPGrid(location which_loc)
{
    Packet *pkt;
    hdr_hgps *hgpsh;
    hdr_cmn *cmnh;
    hdr_ip *iph;

    pkt = parent->allocpkt();
    hgpsh =  (hdr_hgps*)pkt->access(parent->off_hgps_); 
    iph =  (hdr_ip*)pkt->access(parent->off_ip_); 
    cmnh =  (hdr_cmn*)pkt->access(parent->off_cmn_);

    iph->dport_ = RT_PORT;
    iph->dst() = 0; //i don't care about specific recipient
    iph->src() = parent->myaddr_;

    hgpsh->init();
    hgpsh->type_ = LOC_UPDATE_FP;
    hgpsh->src_loc_ = myloc;
    hgpsh->dst_loc_ = which_loc;

    hgpsh->update_loc_ = which_loc; //the area that the update takes effect
    
    /* -jinyang don't set tmeout interval, 
       just keep all the FPs until they overflow (karger)
       so this hgpsh->timeout_inteval_ is essentially not used*/
    hgpsh->timeout_inteval_ = max_mask *((double)parent->update_distance_/getSpeed()) + 1.5 ;
    hgpsh->timeout_inteval_ = (hgpsh->timeout_inteval_* 3/2);

    /* set up the fp pointer info */
    hgpsh->fp_ids_[0] = parent->myaddr_;
    hgpsh->fp_locs_[0] = myloc;
    hgpsh->fp_lastupdate_time_[0] = Scheduler::instance().clock();
    hgpsh->fp_num_ = 1;
    hgpsh->fp_old_loc = which_loc;

    cmnh->ptype() = PT_HGPS;
    cmnh->size() = hgpsh->size();
   
    /* instead of sending this FP pointer geographically to anybody
       in the grid, I could just broadcast it and hopefull(very likely)
       somebody in that grid will pick my FP up
    */
    cmnh->next_hop() = MAC_BROADCAST;
    iph->dst() = IP_BROADCAST;
    Scheduler::instance().schedule(parent->ll,pkt,0);
}

/* for triggered update, there is a speculative timeout value in 
   location update. In order to prevent correct location entry
   from expiring prematurely, this function is invoked to
   correct speculative timeout value when needed by sending
   out new location updates*/
void
LocServer::checkExpiringUpdates()
{
    int stop;
    double min_x,max_x,min_y,max_y;
    location tmp_loc,dst_loc;
    double speedX, speedY,speedZ;
    double dist_x, dist_y,dist_z;
    double outdate_x,outdate_y,timeout_int;
    int x, y;

    Packet *pkt;
    hdr_hgps *hgpsh;
    hdr_cmn *cmnh;
    hdr_ip *iph;

    double now = Scheduler::instance().clock();

    mynode->getVelo(&speedX,&speedY,&speedZ);
    mynode->getLoc(&dist_x,&dist_y,&dist_z);

    for (stop=2;stop<=max_mask;stop+=2) {
	
	if (now > expiration_times[stop/2-1]) {
	    
	    //I need to send out "new" updates
	    tmp_loc.loc = myloc.loc;
	    tmp_loc.mask = BIGGEST_MASK - stop + 2;

	    getXY(min_x,max_x,min_y,max_y,tmp_loc);
	    outdate_x = getOutofRangeTime(min_x,max_x,speedX,dist_x);
	    outdate_y = getOutofRangeTime(min_y,max_y,speedY,dist_y);

	    if (outdate_x < outdate_y) {
		timeout_int = outdate_x;
	    }else{
		timeout_int = outdate_y;
	    }

	    if (timeout_int < TRIGGER_PERIOD) {
		timeout_int = TRIGGER_PERIOD;
	    }
	    
	    /* store the expiration time, inflate it a bit*/
	    expiration_times[stop/2-1] = now + timeout_int + 2;
	
	    /* inflate the timeout value a bit*/
	    timeout_int = timeout_int + 4 ;

	    for (int i=0;i<4;i++) {
		if ((i << (stop-2)) == (myloc.loc & (0x3 << (stop-2)))) {
	        }else{
		
		    x = myloc.loc & (0xffffffff << stop);
		    y = i<<(stop-2);

		    dst_loc.loc = x+y;
		    dst_loc.mask = myloc.mask - stop +2;
		    assert(!inSameGrid(myloc,dst_loc));

		    pkt = parent->allocpkt();
		    hgpsh =  (hdr_hgps*)pkt->access(parent->off_hgps_); 
		    iph =  (hdr_ip*)pkt->access(parent->off_ip_); 
		    cmnh =  (hdr_cmn*)pkt->access(parent->off_cmn_);

		    iph->dport_ = RT_PORT;
		    iph->dst() = 0; //i don't care about specific recipient
		    iph->src() = parent->myaddr_;

		    hgpsh->init();
		    hgpsh->src_loc_ = myloc;
		    hgpsh->dst_loc_ = dst_loc;

		    hgpsh->update_loc_ = dst_loc; //the area that the update takes effect
		    hgpsh->timeout_inteval_ = timeout_int;
		    hgpsh->type_ = LOC_UPDATE;

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

		    router->sendOutPktWithLocation(pkt,jitter(1,1),false);
		
		}
	
	    }

	}
    }
}

void
LocServer::updateLoc(int level) 
{
    int stop = 2;
    location dst_loc;

    Packet *pkt;
    hdr_hgps *hgpsh;
    hdr_cmn *cmnh;
    hdr_ip *iph;

    int x,y;
    double timeout_int,bigtimeout_int;
    double speedX, speedY,speedZ;
    double outdate_x,outdate_y;
    double min_x,max_x,min_y,max_y;
    double dist_x, dist_y,dist_z;
    location tmp_loc = myloc;	

    double now = Scheduler::instance().clock();

    mynode->getVelo(&speedX,&speedY,&speedZ);
    mynode->getLoc(&dist_x,&dist_y,&dist_z);

    
    while (stop<=level) {
	//determine when will i do the next triggered update
	tmp_loc.mask = BIGGEST_MASK - stop + 2;
	getXY(min_x,max_x,min_y,max_y,tmp_loc);
	outdate_x = getOutofRangeTime(min_x,max_x,speedX,dist_x);
	outdate_y = getOutofRangeTime(min_y,max_y,speedY,dist_y);

#ifdef TRIGGER_UPDATE_ONLY
	if (outdate_x < outdate_y) {
	    timeout_int = outdate_x;
	}else{
	    timeout_int = outdate_y;
	}

	if (timeout_int < TRIGGER_PERIOD) {
	    timeout_int = TRIGGER_PERIOD;
	}

	/* store the expiration time*/
	expiration_times[stop/2-1] = now + 2*timeout_int + 2;