locserver.cc

在Linux下做的QuadTree的程序

#include "locserver.h"

static const int verbose_ = 1;

// Returns a random number between 0 and max, implemented by dmaltz
static inline double
jitter (double max, int be_random_)
{
    return (be_random_ ? Random::uniform(max) : 0);
}

static bool
BackOffTest(HGPSEntry *e, double time)
    // look at the entry and decide if we can send another route
    // request or not.  update entry as well, by dmaltz
{
    double next = ((double) (0x1<<(e->rt_reqs_outstanding*2))) * RT_RQ_PERIOD;
    if (next> RT_RQ_MAX_PERIOD) next = RT_RQ_MAX_PERIOD;
    if (next + e->last_rt_req > time) return false;
    // don't let rt_reqs_outstanding overflow next on the LogicalShiftsLeft's
    if (e->rt_reqs_outstanding < 15) e->rt_reqs_outstanding++;
    e->last_rt_req = time;
    return true;
}

/* test if src and dst are in the same grid. At least src or dst must be
   a higher level grid in order for the function to be true*/
static bool
inSameGrid(location src, location dst)
{
     int m_mask;
     int mask;
     
     if (src.mask > dst.mask) {
	 m_mask = dst.mask;
     }else{
	 m_mask = src.mask;
     }
    
     mask = 0xffffffff << (BIGGEST_MASK - m_mask);
     return (((src.loc & mask) == (dst.loc & mask))? true:false);
}

/* am "I" closer to "dst" than "he" is to "dst" in ID space? */
static bool
closer(nsaddr_t me, nsaddr_t him, nsaddr_t dst)
{
    int my_dist = me - dst;
    int his_dist = him - dst;

    if (me == him) return false;

    if (my_dist == 0) return true;
    if (his_dist == 0) return false;

    if (((my_dist > 0) && (his_dist<0))||
	((my_dist < 0) && (his_dist<0) && (my_dist < his_dist)) ||
	((my_dist > 0) && (his_dist>0) && (my_dist < his_dist))) {
	return true;
    }else{
	return false;
    }
}

/* this function is for predicting how soon the node will move out of the
   range defined by min-max given its current speed and position.
   the speed is given in speed along x-axis or y-axis*/
static inline double
getOutofRangeTime(double min, double max, double speed, double now_pos)
{
    double when;
    if (speed>0) {
	when = (double)((max-now_pos)/(speed));	
    }else{
	when = (double)((now_pos-min)/(-speed));
    }
    assert(when>0);
    return when;

}

/* given a grid location, this function calculates the corresponding x, y
   coordinate range */
static inline void
getXY(double &min_x, double &max_x, double &min_y,double &max_y, location loc)
{
    int stop =loc.mask;
    int shift = BIGGEST_MASK;
    unsigned int tmp_mask = 0xffffffff;
    int the_loc = loc.loc;
    int x,y;

    x = 0;
    y = 0;
    while (stop>=2) {
	shift = shift -2;
	x = x *2 + 2* (the_loc >> (shift+1));
	y = y *2 + 2* ((the_loc & 0x55555555)>>shift);
	stop -= 2;
	//clear the examined two bits
	tmp_mask = tmp_mask >> 2;
	the_loc = the_loc & tmp_mask;
    }
    if (shift == 0) {
	x = x +1;
	y = y +1;
    }else {
	x = x*((int)pow(2,(shift/2)));
	x = x+((int)pow(2,(shift/2)));
	y = y*((int)pow(2,(shift/2)));
	y = y+((int)pow(2,(shift/2)));
    }
  
    int minus = BIGGEST_MASK - loc.mask;
    minus = minus/2;
    minus = (int)pow(2,minus);
    min_x = (x - minus)* 125;
    max_x = (x + minus) * 125;
    min_y = (y - minus) * 125;
    max_y = (y + minus) * 125;

}
/* LocServerTriggerHandler is actually a periodic handler, it is invoked
   every TRIGGER_PERIOD seconds to check if any loc updates need to be sent*/
LocServerTriggerHandler::LocServerTriggerHandler(LocServer *s, HGPSAgent *p)
{
    prev_location.loc = 0;
    prev_location.mask = 0;

    locserver = s;
    parent = p;

    /* log the loc table size later */
    counter = -4;
}

void
LocServerTriggerHandler::handle(Event *e)
{
    location now_location; 
    
    now_location = locserver->getGrid();
   
    if ((prev_location.loc == 0) && (prev_location.mask == 0)) {
	prev_location = now_location;
	locserver->myloc = now_location;

#ifdef TRIGGER_UPDATE_ONLY
	//the node has just started, send updates to all levels
	locserver->updateLoc(locserver->max_mask);
#endif
    }else {	
	
	prev_location = locserver->myloc;
	// update locserver's myloc
	locserver->myloc = now_location;

//#ifdef TRIGGER_UPDATE_ONLY
	/*check how much off I am in the hierarchical level from
	my previous position
	*/
	int ud_hierarchy_level = locserver->max_mask;
	//same_mask = (0xffffffff)>>(BIGGEST_MASK - ud_hierarchy_level);
	int same_mask = (3) << (ud_hierarchy_level-2);
	while (ud_hierarchy_level) {
	    if ((now_location.loc & same_mask) != (prev_location.loc & same_mask)) {
		locserver->updateLoc(ud_hierarchy_level); //update my old servers
		break;
	    }
	    ud_hierarchy_level -= 2;
	    same_mask = same_mask >> 2;
	}
//#endif

#ifndef TRIGGER_UPDATE_ONLY
	//spread out forwarding pointers
	if (now_location.loc != prev_location.loc) {
	    //update people in the previous grid
	    //parent->trace("HGPS trigger update _%d_ %.2f (now %d, prev%d)",parent->myaddr_,Scheduler::instance().clock(),now_location.loc,prev_location.loc);
	    locserver->updateFPGrid(prev_location);
	    /* discard all my previous fp table */
	    locserver->dumpFPTable();    
	}
	//periodic update of location info.
	locserver->checkPeriodicUpdateLoc();
#endif

    }

    //log my loctable size every 10*TRIGGER_PERIOD seconds
    counter++;
    if (counter == 10) {
	locserver->logTableSize();
	counter = 0;
    }

#ifdef TRIGGER_UPDATE_ONLY
    /* some updates may be expiring prematurely due to node changing 
       movement destinations*/
    locserver->checkExpiringUpdates();
#endif

        //reschedule the next timer event
    Scheduler::instance().schedule(this,e,TRIGGER_PERIOD);
    
}


LocServer::LocServer(HGPSAgent *p) : request_table(128) {

    parent = p;
    
    loc_trigger_handler = new LocServerTriggerHandler(this, parent);
    trigger_event = new Event();

    table = new LocTable(250,false);
    loc_cache = new LocTable(100,true);
    live_connections = new LocTable(10,true);

    /* initialize all forwarding pointer table */
    for (int i=0;i<MAX_FP_TABLE_SIZE;i++) {
	fp_table[i].id = 0;
    }
    fp_table_num = 0;
    fp_table_tail = 0;
}

void
LocServer::setRouter(HGPSRouter *r)
{
    router = r;
}

void
LocServer::setMobileNode(MobileNode *m)
{
    mynode = m;
}

/* start locserver's timer event, begin location update */
void
LocServer::start() {

    //get the max x, y coordinates of the entire terrain
    double maxx = mynode->T->upperX();
    double maxy = mynode->T->upperY();

    double len;

    if (maxx>maxy) {
	len = maxx;
    }else{
	len = maxy;
    }

    len = len - 0.1;
    max_mask = 0;
    max_len = SMALLEST_GRID;

    while (max_len < len) {
	max_len = max_len * 2;
	max_mask = max_mask + 2;
    }

 
    //prepare for the periodic update of my location 
    prev_x = -50;
    prev_y = -50;
    prev_level = max_mask-2;
    prev_timeout= -50;

    //makes sure when periodic update checker first starts, it will update all levels
    prev_level = (int)pow(2,max_mask/2) - 2;

    Scheduler::instance().schedule(loc_trigger_handler, trigger_event,5+jitter(HGPS_LOC_STARTUP_JITTER,1));

    expiration_times = new double[max_mask/2];
}

/* put locserver to sleep, could be used to emulate node crash */
void
LocServer::sleep()
{
    Scheduler::instance().cancel(trigger_event);
    table->cleanTable();
    loc_cache->cleanTable();
    live_connections->cleanTable();
}

/* get the grid position of myself*/
location
LocServer::getGrid() {
  double x,y,z;

  mynode->getLoc(&x,&y,&z);
  return getGrid(x,y);
}

double
LocServer::getSpeed() {
    return mynode->getSpeed();
}

location
LocServer::getGridPos(double &my_x, double &my_y) {
    double x, y, z;
    mynode->getLoc(&x,&y,&z);
    my_x = x;
    my_y = y;
    return getGrid(x,y);
}

void
LocServer::getPos(double &my_x, double &my_y) {
    double x, y,z;
    mynode->getLoc(&x,&y,&z);
    my_x = x;
    my_y = y;
}

/* get someone's position grid given x and y */
location
LocServer::getGrid(double x, double y)
{
     double len_x;
     double len_y;
     int grid_num = 0;
     location loc;
     
     /* assume minx = miny = 0. otherwise, use x - minx in place of x 
	similar for y
     */
     len_x = len_y = max_len;

     while ((len_x>SMALLEST_GRID)|| (len_y > SMALLEST_GRID)) {
       if (x < len_x/2) {
	 if (y < len_y/2) {
	   grid_num = grid_num * 4 + 0;
	 }else{
	   y -= len_y/2;
	   grid_num = grid_num * 4 + 1;
	 }
       }else{
	 x -= len_x/2;
	 if (y<len_y/2) {
	   grid_num = grid_num * 4 + 2;
	 }else{
	   y -= len_y/2;
	   grid_num = grid_num * 4 + 3;
	 }
       }
       len_x = len_x/2;
       len_y = len_y/2;
     }

     loc.loc = grid_num;
     loc.mask = BIGGEST_MASK;
     return loc;
}

/* hear forwarding poniter information from other's gossips, or from the 
   guy who has left. */
void
LocServer::recvFPUpdate(Packet *packet)
{
     hdr_hgps *hgpsh =  (hdr_hgps*)packet->access(parent->off_hgps_);
    
     if (myloc.loc != hgpsh->fp_old_loc.loc) {
	//i don't belong to the grid that should contain the FP pointers
	return;
     }

     double oldest_lastupdate_time = Scheduler::instance().clock();
     int oldest_entry = -1;

     for (int i=0;i<hgpsh->fp_num_;i++) {
	/*i maintain a fixed array for FP pointer table;
	  If I run out of space, I'll just get rid of the oldest one. */
	 int j;
	 for (j=0;j<MAX_FP_TABLE_SIZE;j++) {
	     if (fp_table[j].id == hgpsh->fp_ids_[i]) {
		 if (fp_table[j].lastupdate_time <= hgpsh->fp_lastupdate_time_[i]) {
		     fp_table[j].loc = hgpsh->fp_locs_[i];
		 }
		 break;
	     }else if (fp_table[j].id == 0) {
		 fp_table_num++; //cause I add a new entry
		 assert(fp_table_num <= MAX_FP_TABLE_SIZE);
		 break;
	     }

	     if (fp_table[j].lastupdate_time < oldest_lastupdate_time) {
		 oldest_entry = j;
		 oldest_lastupdate_time = fp_table[j].lastupdate_time;
	     }
	 }
	 
	 if (j==MAX_FP_TABLE_SIZE) {
	     //i.e. there's no existing fp pointer for this id, add a new one
	     fp_table[oldest_entry].id = hgpsh->fp_ids_[i];
	     fp_table[oldest_entry].lastupdate_time = hgpsh->fp_lastupdate_time_[i];
	     fp_table[oldest_entry].loc = hgpsh->fp_locs_[i];
	 }else {
	     fp_table[j].id = hgpsh->fp_ids_[i];
	     fp_table[j].lastupdate_time = hgpsh->fp_lastupdate_time_[i];
	     fp_table[j].loc = hgpsh->fp_locs_[i];
	 }

    }
    
}

/* gossip about FP pointers for the nodes in my grid 
   serveral FP pointers will be randomly selected and 
   piggybacked onto the packet passed in as argument
   this function is to be called by routing layer*/
void
LocServer::piggybackFP(Packet *packet)
{
    hdr_hgps *hgpsh =  (hdr_hgps*)packet->access(parent->off_hgps_);
    int which_fp;

    if (fp_table_num <= MAX_FP_IN_HELLO) {
	for (int i=0;i<fp_table_num;i++) {
	    hgpsh->fp_ids_[i] = fp_table[i].id;
	    hgpsh->fp_locs_[i] = fp_table[i].loc;
	    hgpsh->fp_lastupdate_time_[i] = fp_table[i].lastupdate_time;
	}
	hgpsh->fp_num_ = fp_table_num;
	hgpsh->fp_old_loc = myloc;

    }else {

	for (int i=0;i<MAX_FP_IN_HELLO;i++) {
	    which_fp = (int)(Random::uniform()*fp_table_num);
	    hgpsh->fp_ids_[i] = fp_table[which_fp].id;
	    hgpsh->fp_locs_[i] = fp_table[which_fp].loc;
	    hgpsh->fp_lastupdate_time_[i] = fp_table[which_fp].lastupdate_time;
	}
	hgpsh->fp_num_ = MAX_FP_IN_HELLO;
	hgpsh->fp_old_loc = myloc;
    }
}

void
LocServer::dumpFPTable()
{
    for (int i=0;i<MAX_FP_TABLE_SIZE;i++) {
	fp_table[i].id = 0;
    }
    fp_table_num = 0;
    fp_table_tail = 0;
}

#ifdef TRIGGER_UPDATE_ONLY
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*/