hgpsrouter.cc

在Linux下做的QuadTree的程序

			}
			rt_1[i].next_hop = new_pt;
			new_pt->prev = NULL;
		    }else {
			assert(nexthop_pt->next == NULL);
			//insert at the end of list
			nexthop_pt->next = new_pt;
			new_pt->prev = nexthop_pt;
			new_pt->next = NULL;
		    }
		}
	    }
	    return;
	}else if ((freeslot ==-1) && ((now - rt_1[i].lastupdate_time)>NEIGHBOR_TIMEOUT_INTEVAL)) {
	    //remove all the outdated next hop nodes
	    nexthop_pt = rt_1[i].next_hop;
	    while(nexthop_pt) {
		nexthop_pt = nexthop_pt->next;
		if (nexthop_pt) {
		    delete nexthop_pt->prev;
		}
	    }
	    rt_1[i].next_hop = NULL;
	    freeslot = i;
	}
    }
    assert(freeslot >= 0);

    new_pt = new nexthop_entry;
    new_pt->lastupdate_time = now;
    new_pt->speed = speed;
    new_pt->next_node = next_hop;
    new_pt->x = x;
    new_pt->y = y;
    new_pt->dist = distance;
    new_pt->prev = NULL;
    new_pt->next = NULL;
    rt_1[freeslot].next_hop = new_pt;
    rt_1[freeslot].loc = loc;
    rt_1[freeslot].lastupdate_time = now;
}



nsaddr_t
HGPSRouter::getBestNextHopNode(route_entry &rnt)
{
    nexthop_entry *pt;
    pt = getNextHopNode(rnt.next_hop);
    if (!pt) {
	assert(rnt.next_hop == NULL);
	rnt.dst = 0;
	rnt.lastupdate_time = -3 * NEIGHBOR_TIMEOUT_INTEVAL;
	return 0;
    }
    int dstdst_x,dstdst_y;
    loctodistance(dstdst_x,dstdst_y,rnt.loc);
    dstdst_x = dstdst_x*125;
    dstdst_y = dstdst_y*125;
    double best_dist = 5*RADIO_PROPAGATION*RADIO_PROPAGATION;
    double dist;
    nsaddr_t best_node = pt->next_node;
    while (pt) {
	dist = (pt->x-dstdst_x)*(pt->x-dstdst_x)+(pt->y-dstdst_y)*(pt->y-dstdst_y);
	if (dist<best_dist) {
	    best_node = pt->next_node;
	    best_dist = dist;
	}
	pt = getNextHopNode(pt->next);
    }
    return best_node;
}

bool
HGPSRouter::outdatedNeighbor(nexthop_entry *next_hop, double now)
{
    if ((now - next_hop->lastupdate_time) < NEIGHBOR_TIMEOUT_INTEVAL) {
	return false;
    }else {
	return true;
    }
	
    /*
    double x, y, dist;
    locserver->getPos(x,y);
    dist = (x - next_hop->x)*(x - next_hop->x) + (y-next_hop->y)*(y-next_hop->y);
    dist = sqrt(dist);
    dist += next_hop->speed*(now-next_hop->lastupdate_time);
    if (dist < (0.97*RADIO_PROPAGATION)) {
	return false;
    }else {
	return true;
    }
    */
}

nsaddr_t
HGPSRouter::getNextHopNode(route_entry &rnt)
{
    nexthop_entry *pt;
    pt = getNextHopNode(rnt.next_hop);
    if (!pt) {
	assert(rnt.next_hop == NULL);
	rnt.dst = 0;
	rnt.lastupdate_time = -3*NEIGHBOR_TIMEOUT_INTEVAL;
	return 0;
    }
    return pt->next_node;

}

nexthop_entry *
HGPSRouter::getNextHopNode(nexthop_entry *&next_hop)
{

    nexthop_entry *nexthop_pt;
    nexthop_entry *tmp_pt;

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

    nexthop_pt = next_hop;

    while(nexthop_pt && outdatedNeighbor(nexthop_pt, now)) {
	//delete one entry
	if (nexthop_pt->prev){
	    nexthop_pt->prev->next = nexthop_pt->next;
	    if (nexthop_pt->next) {
	       nexthop_pt->next->prev = nexthop_pt->prev;
	    }
	}else{
	    next_hop = nexthop_pt->next;
	    if (nexthop_pt->next) {
		nexthop_pt->next->prev = NULL;
	    }
	}
	tmp_pt = nexthop_pt;
	nexthop_pt = nexthop_pt->next;
	delete tmp_pt;
    }
    if (nexthop_pt) {
	assert(next_hop !=NULL);
	return nexthop_pt;
    }else{
	return NULL;
    }
}

nsaddr_t 
HGPSRouter::getNextHopFromNT(nsaddr_t dst, location & hisloc)
{
    int i;
    for (int j=0;j<MAX_RT_ENTRIES;j++) {
	i = (j+dst) % MAX_RT_ENTRIES;//some simple hash functions
	if (dst == nt[i].dst) {
	    //if (hisloc.loc != 0) {
		hisloc = nt[i].loc;
	    //}
	    //return getBestNextHopNode(nt[i]);
	    return getNextHopNode(nt[i]);
	}
    }
    return 0;
}

/* this function implements the simplest greedy geographic forwarding
   it sends the packet towards its destination location grid by
   searching in its 1 and 2 hop neighbor table, to prevent from routing
   loop, prev_hop of this route is avoided.  It turns out in the simulation,
   recording only the prev_hop is enough to prevent routing loop for geographic
   forwarding.  More investigation on this issue needs to be done*/
nsaddr_t
HGPSRouter::getNextHop(location hisloc, nsaddr_t prev_hop)
{

    location myloc;
    int dist,min_dist;
    double now = Scheduler::instance().clock();
    nexthop_entry *next_hop_node = NULL;
    int srcdst_x,srcdst_y,dstdst_x,dstdst_y;
    
    myloc = locserver->myloc;
       
    if ((hisloc.mask == BIGGEST_MASK) && (inSameGrid(myloc, hisloc))) {
	//I should be able to reach the destination via my neighbor table
	return parent->myaddr_;
    }

    loctodistance(dstdst_x,dstdst_y,hisloc);
    loctodistance(srcdst_x,srcdst_y,myloc);
    min_dist = (srcdst_x-dstdst_x)*(srcdst_x-dstdst_x)+ (srcdst_y-dstdst_y)*(srcdst_y-dstdst_y);
    
    for (int i=0;i<MAX_ADJ_GRID;i++) {
	if ((now - rt_1[i].lastupdate_time) < NEIGHBOR_TIMEOUT_INTEVAL) {
	    loctodistance(srcdst_x,srcdst_y,rt_1[i].loc);
	    dist = (srcdst_x-dstdst_x)*(srcdst_x-dstdst_x)+ (srcdst_y-dstdst_y)*(srcdst_y-dstdst_y);
	    if (dist < min_dist) {
		if ((next_hop_node = getNextHopNode(rt_1[i].next_hop))) {
		    min_dist = dist;
		}
	    }
	}
    }
    
    if (!next_hop_node) {
	return 0;
    }else {
	//select one that makes the most progress among a set of valid next hops
	nsaddr_t best_next_hop = next_hop_node->next_node;
	double best_dist = (next_hop_node->x-dstdst_x*125)*(next_hop_node->x-dstdst_x*125)+(next_hop_node->y-dstdst_y*125)*(next_hop_node->y-dstdst_y*125);
	double new_dist;
	while (next_hop_node->next) {
	    next_hop_node = getNextHopNode(next_hop_node->next);
	    if (!next_hop_node) return best_next_hop;
	    new_dist = (next_hop_node->x-dstdst_x*125)*(next_hop_node->x-dstdst_x*125)+(next_hop_node->y-dstdst_y*125)*(next_hop_node->y-dstdst_y*125);
	    if ((new_dist < best_dist) && (next_hop_node->next_node!= prev_hop)){
		best_next_hop = next_hop_node->next_node;
		best_dist = new_dist;
	    }
	}
	return best_next_hop;
    }

}

void
HGPSRouter::sendOutPktWithLocation(Packet *&packet, double delay, bool checkNT)
{
    hdr_hgps *hgpsh =  (hdr_hgps*)packet->access(parent->off_hgps_);

    assert(hgpsh->type_ != LOC_QUERY);
    this->sendOutPktWithLocation(packet,delay,checkNT,false);
}

/* invoked by the location server or data packets to send out a packet with its destination grid known.*/
void
HGPSRouter::sendOutPktWithLocation(Packet *&packet,double delay,bool checkNT, bool invoke_loc_server)
{
    hdr_hgps *hgpsh =  (hdr_hgps*)packet->access(parent->off_hgps_);
    hdr_ip *iph =  (hdr_ip*)packet->access(parent->off_ip_);
    hdr_cmn *cmnh =  (hdr_cmn*)packet->access(parent->off_cmn_);
    Scheduler & s = Scheduler::instance();


    //insert failure handler to the packet
    cmnh->xmit_failure_ = HGPS_XmitFailureCallback;
    cmnh->xmit_failure_data_ = (void *) this;

    //check first if there's short-cut
    bool i_have_sent_before = false;

    if (checkNT) {

	for (int i = 0; i<hgpsh->prev_hop_num_; i++) {
	    deleteEntry(hgpsh->prev_hop_[i], iph->dst());
	    if (hgpsh->prev_hop_[i] == parent->myaddr_) {
		i_have_sent_before = true;
	    }
	}
	
	if ((iph->dst_!=0) && (cmnh->next_hop_ = getNextHopFromNT(iph->dst_,hgpsh->dst_loc_))) {
	    if (cmnh->next_hop_!=iph->dst()) {
		if (hgpsh->prev_hop_num_ >= 4) {
		    parent->drop(packet, DROP_RTR_ROUTE_LOOP);
		    return;
		}else{
		    if (hgpsh->prev_hop_[hgpsh->prev_hop_num_-1]!=parent->myaddr_) {
		    	hgpsh->prev_hop_[hgpsh->prev_hop_num_] = parent->myaddr_;
		    	hgpsh->prev_hop_num_++;
		    }
		}
	    }
    	    s.schedule(parent->ll,packet,0);
	    packet = NULL;
    	    return;
	}
    }
    assert((hgpsh->dst_loc_).mask != 0);

#ifdef IDEAL_ROUTE 
    //this part has not been tested!
    if (hgpsh->curr_addr_ == 0) {
	//i'll ask god to give me a perfect route!
	if (God::instance()->getRouteToLoc(parent->myaddr_,hgpsh->dst_loc_,hgpsh->addrs_,MAX_ADDR_LEN)) {
	    parent->drop(packet,DROP_RTR_NO_ROUTE);
	}else {
	    hgpsh->curr_addr_++;
	    cmnh->next_hop() = hgpsh->addrs_[hgpsh->curr_addr_];
	    s.schedule(parent->ll,packet,delay);
	}
    }else {
	//just forward the pkt along the source route
       hgpsh->curr_addr_++;
       cmnh->next_hop() = hgpsh->addrs_[hgpsh->curr_addr_];
       s.schedule(parent->ll,packet,delay);
    }
    packet = NULL;
    return;
#endif
    
    cmnh->next_hop_ = getNextHop(hgpsh->dst_loc_, (hgpsh->prev_hop_num_)? hgpsh->prev_hop_[0]:0);
    /* an location update might not have the idea of who to forward the pkt to*/
    /* i have to set iph->dst(), otherwise the link layer will complain*/
    if (!iph->dst()) {
	iph->dst() = cmnh->next_hop(); 
    }
    
    if (cmnh->next_hop() && (cmnh->next_hop() != parent->myaddr_)) {
	hgpsh->prev_hop_[0] = parent->myaddr_;
	hgpsh->prev_hop_num_ = 1;
	s.schedule(parent->ll,packet,delay);
    }else if (cmnh->next_hop() == parent->myaddr_) {
	//I should be the next hop to destination. i.e. destination has moved away
	//send out an ERR packet to information the source about this invalid dst_loc_
#ifdef HGPS_DEBUG
	printf("_%d_ %.2f location (%d) error dst %d\n",parent->myaddr_,s.clock(),hgpsh->dst_loc_.loc,iph->dst());
#endif
	if (hgpsh->type_ == DATA) {
    	    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->src() = parent->myaddr_;
	    new_iph->dst() = iph->src();
	    new_hgpsh->init();
	    new_hgpsh->dst_loc_ = hgpsh->src_loc_;
	    new_hgpsh->src_loc_ = locserver->getGrid();
	    new_hgpsh->type_ = ERR;
	    new_hgpsh->id_ = iph->dst();
	    new_hgpsh->loc_ = hgpsh->dst_loc_;

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

	    sendOutPktWithLocation(p,0.0,true);
    	    parent->trace("HGPS DROP: _%d_ %.2f outdated location %d->%d(%d)",parent->myaddr_,s.clock(),iph->src(),iph->dst(),(hgpsh->dst_loc_).loc);

	}else if ((hgpsh->type_ == LOC_QUERY)) {
	    if (parent->verbose_) {
		parent->trace("HGPS dst %d loc %d error",iph->dst(),hgpsh->dst_loc_.loc);
	    }

	    if (invoke_loc_server) {
		locserver->recvQuery(packet,true);
		return;
	    }else{
		parent->trace("HGPS %.5f _%d_ loc-query-failure-1(%d %d)%d->%d",s.clock(),parent->myaddr_,parent->myaddr_,hgpsh->id_,iph->src(),iph->dst());
	    }
	}else if (hgpsh->type_ == LOC_UPDATE) {
	    printf("_%d_ update dst %d location(%d) error\n", parent->myaddr_,iph->dst(),hgpsh->dst_loc_.loc);
	}
	//i classify location error as no route temporarily
	parent->drop(packet,DROP_RTR_NO_ROUTE);

    }else{
	double x, y, z;
	locserver->mynode->getLoc(&x,&y,&z);
#ifdef HGPS_DEBUG
	printf("_%d_ (%d, %.2f, %.2f) %.5f no route to dst %d (%d,%d)\n",parent->myaddr_,
		(locserver->getGrid()).loc,x,y,s.clock(),iph->dst(),(hgpsh->dst_loc_).loc,(hgpsh->dst_loc_).mask);
#endif
	parent->drop(packet,DROP_RTR_NO_ROUTE);
	packet = NULL;
	return;
    }
    packet = NULL;
}

void
HGPS_XmitFailureCallback(Packet *pkt, void *data)
{
    HGPSRouter *router = (HGPSRouter *)data; // cast of trust
    router->xmitFailed(pkt);
}

void
HGPSRouter::xmitFailed(Packet *pkt)
{
    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_);
    
    double now = Scheduler::instance().clock();


    //delete incorrect neighbor entry whatever
    deleteEntry(cmnh->next_hop());
    
    if (parent->verbose_) {
	parent->trace("HGPS: error from %d->%d %d",parent->myaddr_,cmnh->next_hop(),cmnh->uid());
    }

    nsaddr_t prev_cmnh_next_hop = cmnh->next_hop();
    cmnh->next_hop() = 0; //i have to reset next hop
/*
    if (hgpsh->prev_hop_num_ && (hgpsh->prev_hop_[hgpsh->prev_hop_num_-1] == parent->myaddr_)) {
	    hgpsh->prev_hop_num_ --;
	}
*/

    if (hgpsh->type_ == LOC_UPDATE) {
	//because my neighbor table has been changed, therefore iph->dst() might be different from recvUpdate()
        locserver->recvUpdate(pkt);     
    }else if (hgpsh->type_ == LOC_QUERY) {
        locserver->recvQuery(pkt,false);
    }else {
        sendOutPktWithLocation(pkt,0.0,true);
    }

    /* now kill all the other packets in the output queue that would
    use the same next hop.  This is reasonable, since 802.11 has
    already retried the xmission multiple times => a persistent failure. 
    from dmaltz*/

    Packet *r, *nr, *head = NULL;		// pkts to be recycled
    while ((r = (parent->ifq)->prq_get_nexthop(prev_cmnh_next_hop))) {
	r->next_ = head;
	head = r; 
    }

    // the packets are now in the reverse order of how they appeared in the IFQ
    // so reverse them again
    for (r = head, head = NULL; r; r = r->next_) {  
	r->next_ = head;
	head = r; 
    }

    // now process them in order
    for (r = head; r; r = nr) {  
	nr = r->next_;

	//depending on packet type, rescue differently
	hgpsh =  (hdr_hgps*)r->access(parent->off_hgps_);
	cmnh = (hdr_cmn*)r->access(parent->off_cmn_);

	cmnh->next_hop() = 0;
	/*
	if (hgpsh->prev_hop_num_ && (hgpsh->prev_hop_[hgpsh->prev_hop_num_-1] == parent->myaddr_)) {
	    hgpsh->prev_hop_num_ --;
	}
	*/

	if (hgpsh->type_ == LOC_UPDATE) {
	    locserver->recvUpdate(r);
	}else if (hgpsh->type_ == LOC_QUERY) {
	    locserver->recvQuery(r,false);
	}else {
	    sendOutPktWithLocation(r,jitter(0.2,1),true);
	}
    } 
}