aodv.cc

linux平台下,在ns2里面实现的基于价格的分布式优化算法源代码

            if (ph->flag()!=0) {
                double hop_price = get_price(ch->next_hop_);
                ph->price_ += hop_price;
                printf("%d->%d per-hop-price %f, aggr-price %f\n",index,ch->next_hop_,hop_price, ph->price_);
            }
        }else{
            ph->flag() = 0;
		    ph->grad_ = 0;
            ch->prev_hop_ = LARGE_INT8;
        }
    //Yuan add end
    }
 }
 else { // if it is a broadcast packet
   // assert(ch->ptype() == PT_AODV); // maybe a diff pkt type like gaf
   assert(ih->daddr() == (nsaddr_t) IP_BROADCAST);
   ch->addr_type() = NS_AF_NONE;
   ch->direction() = hdr_cmn::DOWN;       //important: change the packet's direction
 }

if (ih->daddr() == (nsaddr_t) IP_BROADCAST) {
 // If it is a broadcast packet
   assert(rt == 0);
   /*
    *  Jitter the sending of broadcast packets by 10ms
    */
   Scheduler::instance().schedule(target_, p,
      				   0.01 * Random::uniform());
 }
 else { // Not a broadcast packet 
   if(delay > 0.0) {
     Scheduler::instance().schedule(target_, p, delay);
   }
   else {
   // Not a broadcast packet, no delay, send immediately
     Scheduler::instance().schedule(target_, p, 0.);
   }
 }

}


void
AODV::sendRequest(nsaddr_t dst) {
// Allocate a RREQ packet 
Packet *p = Packet::alloc();
struct hdr_cmn *ch = HDR_CMN(p);
struct hdr_ip *ih = HDR_IP(p);
struct hdr_aodv_request *rq = HDR_AODV_REQUEST(p);
aodv_rt_entry *rt = rtable.rt_lookup(dst);

 assert(rt);

 /*
  *  Rate limit sending of Route Requests. We are very conservative
  *  about sending out route requests. 
  */

 if (rt->rt_flags == RTF_UP) {
   assert(rt->rt_hops != INFINITY2);
   Packet::free((Packet *)p);
   return;
 }

 if (rt->rt_req_timeout > CURRENT_TIME) {
   Packet::free((Packet *)p);
   return;
 }

 // rt_req_cnt is the no. of times we did network-wide broadcast
 // RREQ_RETRIES is the maximum number we will allow before 
 // going to a long timeout.

 if (rt->rt_req_cnt > RREQ_RETRIES) {
   rt->rt_req_timeout = CURRENT_TIME + MAX_RREQ_TIMEOUT;
   rt->rt_req_cnt = 0;
 Packet *buf_pkt;
   while ((buf_pkt = rqueue.deque(rt->rt_dst))) {
       drop(buf_pkt, DROP_RTR_NO_ROUTE);
   }
   Packet::free((Packet *)p);
   return;
 }

#ifdef DEBUG
   fprintf(stderr, "(%2d) - %2d sending Route Request, dst: %d\n",
                    ++route_request, index, rt->rt_dst);
#endif // DEBUG

 // Determine the TTL to be used this time. 
 // Dynamic TTL evaluation - SRD

 rt->rt_req_last_ttl = max(rt->rt_req_last_ttl,rt->rt_last_hop_count);

 if (0 == rt->rt_req_last_ttl) {
 // first time query broadcast
   ih->ttl_ = TTL_START;
 }
 else {
 // Expanding ring search.
   if (rt->rt_req_last_ttl < TTL_THRESHOLD)
     ih->ttl_ = rt->rt_req_last_ttl + TTL_INCREMENT;
   else {
   // network-wide broadcast
     ih->ttl_ = NETWORK_DIAMETER;
     rt->rt_req_cnt += 1;
   }
 }

 // remember the TTL used  for the next time
 rt->rt_req_last_ttl = ih->ttl_;

 // PerHopTime is the roundtrip time per hop for route requests.
 // The factor 2.0 is just to be safe .. SRD 5/22/99
 // Also note that we are making timeouts to be larger if we have 
 // done network wide broadcast before. 

 rt->rt_req_timeout = 2.0 * (double) ih->ttl_ * PerHopTime(rt); 
 if (rt->rt_req_cnt > 0)
   rt->rt_req_timeout *= rt->rt_req_cnt;
 rt->rt_req_timeout += CURRENT_TIME;

 // Don't let the timeout to be too large, however .. SRD 6/8/99
 if (rt->rt_req_timeout > CURRENT_TIME + MAX_RREQ_TIMEOUT)
   rt->rt_req_timeout = CURRENT_TIME + MAX_RREQ_TIMEOUT;
 rt->rt_expire = 0;

#ifdef DEBUG
 fprintf(stderr, "(%2d) - %2d sending Route Request, dst: %d, tout %f ms\n",
	         ++route_request, 
		 index, rt->rt_dst, 
		 rt->rt_req_timeout - CURRENT_TIME);
#endif	// DEBUG
	

 // Fill out the RREQ packet 
 // ch->uid() = 0;
 ch->ptype() = PT_AODV;
 ch->size() = IP_HDR_LEN + rq->size();
 ch->iface() = -2;
 ch->error() = 0;
 ch->addr_type() = NS_AF_NONE;
 ch->prev_hop_ = index;          // AODV hack

 ih->saddr() = index;
 ih->daddr() = IP_BROADCAST;
 ih->sport() = RT_PORT;
 ih->dport() = RT_PORT;

 // Fill up some more fields. 
 rq->rq_type = AODVTYPE_RREQ;
 rq->rq_hop_count = 1;
 rq->rq_bcast_id = bid++;
 rq->rq_dst = dst;
 rq->rq_dst_seqno = (rt ? rt->rt_seqno : 0);
 rq->rq_src = index;
 seqno += 2;
 assert ((seqno%2) == 0);
 rq->rq_src_seqno = seqno;
 rq->rq_timestamp = CURRENT_TIME;

 Scheduler::instance().schedule(target_, p, 0.);

}

void
AODV::sendReply(nsaddr_t ipdst, u_int32_t hop_count, nsaddr_t rpdst,
                u_int32_t rpseq, u_int32_t lifetime, double timestamp) {
Packet *p = Packet::alloc();
struct hdr_cmn *ch = HDR_CMN(p);
struct hdr_ip *ih = HDR_IP(p);
struct hdr_aodv_reply *rp = HDR_AODV_REPLY(p);
aodv_rt_entry *rt = rtable.rt_lookup(ipdst);

#ifdef DEBUG
fprintf(stderr, "sending Reply from %d at %.2f\n", index, Scheduler::instance().clock());
#endif // DEBUG
 assert(rt);

 rp->rp_type = AODVTYPE_RREP;
 //rp->rp_flags = 0x00;
 rp->rp_hop_count = hop_count;
 rp->rp_dst = rpdst;
 rp->rp_dst_seqno = rpseq;
 rp->rp_src = index;
 rp->rp_lifetime = lifetime;
 rp->rp_timestamp = timestamp;
   
 // ch->uid() = 0;
 ch->ptype() = PT_AODV;
 ch->size() = IP_HDR_LEN + rp->size();
 ch->iface() = -2;
 ch->error() = 0;
 ch->addr_type() = NS_AF_INET;
 ch->next_hop_ = rt->rt_nexthop;
 ch->prev_hop_ = index;          // AODV hack
 ch->direction() = hdr_cmn::DOWN;

 ih->saddr() = index;
 ih->daddr() = ipdst;
 ih->sport() = RT_PORT;
 ih->dport() = RT_PORT;
 ih->ttl_ = NETWORK_DIAMETER;

 Scheduler::instance().schedule(target_, p, 0.);

}

void
AODV::sendError(Packet *p, bool jitter) {
struct hdr_cmn *ch = HDR_CMN(p);
struct hdr_ip *ih = HDR_IP(p);
struct hdr_aodv_error *re = HDR_AODV_ERROR(p);
    
#ifdef ERROR
fprintf(stderr, "sending Error from %d at %.2f\n", index, Scheduler::instance().clock());
#endif // DEBUG

 re->re_type = AODVTYPE_RERR;
 //re->reserved[0] = 0x00; re->reserved[1] = 0x00;
 // DestCount and list of unreachable destinations are already filled

 // ch->uid() = 0;
 ch->ptype() = PT_AODV;
 ch->size() = IP_HDR_LEN + re->size();
 ch->iface() = -2;
 ch->error() = 0;
 ch->addr_type() = NS_AF_NONE;
 ch->next_hop_ = 0;
 ch->prev_hop_ = index;          // AODV hack
 ch->direction() = hdr_cmn::DOWN;       //important: change the packet's direction

 ih->saddr() = index;
 ih->daddr() = IP_BROADCAST;
 ih->sport() = RT_PORT;
 ih->dport() = RT_PORT;
 ih->ttl_ = 1;

 // Do we need any jitter? Yes
 if (jitter)
 	Scheduler::instance().schedule(target_, p, 0.01*Random::uniform());
 else
 	Scheduler::instance().schedule(target_, p, 0.0);

}


/*
   Neighbor Management Functions
*/

void
AODV::sendHello() {

printf("AODV: %d send Hello\n", index);
//Yuan add to hook mac handler
if (first_time){
    assert(mac);
    mac->routing_agent = this;
    first_time =0;
}
    
Packet *p = Packet::alloc();
struct hdr_cmn *ch = HDR_CMN(p);
struct hdr_ip *ih = HDR_IP(p);
struct hdr_aodv_hello *rh = HDR_AODV_HELLO(p);

#ifdef DEBUG
fprintf(stderr, "sending Hello from %d at %.2f\n", index, Scheduler::instance().clock());
#endif // DEBUG

 rh->rh_type = AODVTYPE_HELLO;
 //rh->rp_flags = 0x00;
 rh->rh_hop_count = 1;
 rh->rh_src = index;
 rh->rh_dst_seqno = seqno;
 rh->rh_lifetime = (1 + ALLOWED_HELLO_LOSS) * HELLO_INTERVAL;
 
 //Yuan add to piggyback views on Hello msg.

 AODV_View *view = vhead.lh_first;

 int k =0;
 for(; view; view = view->view_link.le_next) {
	 if ((view->one_hop <= NUM_COMM_HOP)||(view->other_hop <= NUM_COMM_HOP)) {
        rh->rh_one[k] = view->view_one;
		rh->rh_one_hop[k] = view->one_hop;
		rh->rh_other[k] = view->view_other;
		rh->rh_other_hop[k] = view->other_hop;
        rh->rh_grad[k] = view->view_grad;
        rh->rh_timestamp[k] = view->view_timestamp;
        k++;
        if (k >=MAX_VIEW_PER_NODE) {
            printf("AODV error: too many view entries\n");
            break;           
        }
      }
     //printf("sendHello from %d (%d,%d)\n", index, view->view_one, view->view_other);
 }
 rh->rh_view_num = k;

#ifdef CENTRAL
 int j = 0;
 for (AODV_Clique *clique = cliquehead.lh_first ;clique; clique = clique->clique_link.le_next){

    if (2*clique->clique_num_subflow >=MAX_VIEW_PER_NODE) {
            printf("AODV error: too many view entries in a clique\n");
            continue;           
    }
	for (int i =0; i< 2*clique->clique_num_subflow; i++) 
		rh->rh_clique_ID[j][i] = clique->clique_ID[i];
    rh->rh_clique_num_subflow[j] = clique->clique_num_subflow;
	rh->rh_clique_price[j] = clique->clique_price;
    printf("AODV: %d sendHello with price %f\n", index, clique->clique_price);
    j++;
 }
 rh->rh_clique_num = j;
#endif

 // ch->uid() = 0;
 ch->ptype() = PT_AODV;
 ch->size() = IP_HDR_LEN + rh->size();
 ch->iface() = -2;
 ch->error() = 0;
 ch->addr_type() = NS_AF_NONE;
 ch->prev_hop_ = index;          // AODV hack

 ih->saddr() = index;
 ih->daddr() = IP_BROADCAST;
 ih->sport() = RT_PORT;
 ih->dport() = RT_PORT;
 ih->ttl_ = 1;

 Scheduler::instance().schedule(target_, p, 0.0);
}

//Yuan change
void
AODV::recvHello(Packet *p) {
    printf("AODV: %d recv Hello\n", index);
struct hdr_aodv_hello *rh = HDR_AODV_HELLO(p);
AODV_Neighbor *nb;

 nb = nb_lookup(rh->rh_src);
 if(nb == 0) {
   nb_insert(rh->rh_src);
   view_update(rh);
 }
 else {
   nb->nb_expire = CURRENT_TIME + (1.5 * ALLOWED_HELLO_LOSS * HELLO_INTERVAL);
   view_update(rh);
 }
#ifdef CENTRAL
 if (rh->rh_src < index) // smaller one is the master
	direct_price_update(rh);
#endif
 Packet::free(p);
}

void
AODV::nb_insert(nsaddr_t id) {
AODV_Neighbor *nb = new AODV_Neighbor(id);

 assert(nb);
 nb->nb_expire = CURRENT_TIME + (1.5 * ALLOWED_HELLO_LOSS * HELLO_INTERVAL);
 LIST_INSERT_HEAD(&nbhead, nb, nb_link);
 seqno += 2;             // set of neighbors changed
 assert ((seqno%2) == 0);
 //Yuan add
 nb->nb_price =0;
 nb->nb_flag = 0;
 
 for (int k = 0; k< MAX_FLOW_PER_NB; k++){
    nb->nb_rate[k] = 0;
 }
 nb->nb_aggr_rate = 0;
 nb->nb_grad = 0;
 //Yuan add end
}


AODV_Neighbor*
AODV::nb_lookup(nsaddr_t id) {
AODV_Neighbor *nb = nbhead.lh_first;

 for(; nb; nb = nb->nb_link.le_next) {
   if(nb->nb_addr == id) break;
 }
 return nb;
}


/*
 * Called when we receive *explicit* notification that a Neighbor
 * is no longer reachable.
 */
void
AODV::nb_delete(nsaddr_t id) {
AODV_Neighbor *nb = nbhead.lh_first;

 log_link_del(id);
 seqno += 2;     // Set of neighbors changed
 assert ((seqno%2) == 0);

 for(; nb; nb = nb->nb_link.le_next) {
   if(nb->nb_addr == id) {
     LIST_REMOVE(nb,nb_link);
     delete nb;
     //Yuan add
     view_delete(index,id);
     break;
   }
 }
 printf("%d nb_delete %d\n", index, id);
 handle_link_failure(id);

}


/*
 * Purges all timed-out Neighbor Entries - runs every
 * HELLO_INTERVAL * 1.5 seconds.
 */

void
AODV::nb_purge() {
AODV_Neighbor *nb = nbhead.lh_first;
AODV_Neighbor *nbn;
double now = CURRENT_TIME;
 for(; nb; nb = nbn) {
   nbn = nb->nb_link.le_next;
   if(nb->nb_expire <= now) {
  printf("%d nb_purge %d\n", index, nb->nb_addr);
     nb_delete(nb->nb_addr);
   }
 }

}


void
AODV::rate_update(double rate, int flowid, AODV_Neighbor *nb, int pkt_size){
    printf("AODV:rate update\n");
    assert(nb);
    nb->nb_aggr_rate = nb->nb_aggr_rate - nb->nb_rate[flowid] + rate;
    nb->nb_rate[flowid] = rate;
    // rate expiration time as a function of rate and packet size
    nb->nb_rate_expire[flowid] = CURRENT_TIME + pkt_size/nb->nb_rate[flowid] * (2* ALLOWED_HELLO_LOSS); 

    if ((nb->nb_addr<0)||(nb->nb_addr>=MAX_NUM_NB)) {
        printf("invalid nb address\n");
        return;
    }
//YUAN WORKING HERE
/*
    if (ifq->length[nb->nb_addr] > 0) {
       nb->nb_grad = packetsize*(legnth+ lastlength - nowlength); 
    }
*/    

    if (mac->bandwidth[nb->nb_addr] > 0) {
        nb->nb_grad = nb->nb_aggr_rate - mac->bandwidth[nb->nb_addr];

        printf("AODV: at %f [%d->%d]: rate %f, bandwidth %f, grad %f \n",CURRENT_TIME,index, nb->nb_addr,nb->nb_aggr_rate,mac->bandwidth[nb->nb_addr],nb->nb_grad);
        view_update(nb->nb_addr, nb->nb_grad);
    }else{
        printf("error: mac bandwidth [%d->%d] not ready\n", index,nb->nb_addr);
        nb->nb_flag = 0;
    }
}

/*
 *
 */

void
AODV::rate_purge() {
AODV_Neighbor *nb = nbhead.lh_first;
AODV_Neighbor *nbn;
double now = CURRENT_TIME;

    for(; nb; nb = nbn) {
        double aggr_rate =0;
        nbn = nb->nb_link.le_next;
    for (int i = 0; i< MAX_FLOW_PER_NB; i++) {
        if (nb->nb_rate[i]>0) {
            if(nb->nb_rate_expire[i] <= now) {
//                printf("flow %d at (%d, %d) purged\n",i, index, nb->nb_addr);
                nb->nb_rate[i] = 0;
            }
            aggr_rate+=nb->nb_rate[i];
        } 
        nb->nb_aggr_rate = aggr_rate;
        if (nb->nb_aggr_rate == 0) {
            view_delete(index, nb->nb_addr);
        }
    }
    }
}

void
AODV::view_update(nsaddr_t nexthop, double grad) {
    printf("view_update on rate (%d,%d) %f\n",index,nexthop, grad);
    AODV_View* view;
    view = view_lookup (index, nexthop);
    if (view == NULL) {
        view = new AODV_View(index, nexthop, grad, CURRENT_TIME);
        assert(view);
		view->one_hop = 0;
		view->other_hop = 1;
        LIST_INSERT_HEAD(&vhead, view, view_link);
    } else{
        view->view_grad = grad;
        view->view_timestamp = CURRENT_TIME;
    }
    view_print();
   
    /* check whether this is a transmiting node, if it is,it calculates the
      price*/

    int tx_node = 0;
    AODV_Neighbor *nb = nbhead.lh_first;
    for(; nb; nb = nb->nb_link.le_next) {
        if(nb->nb_aggr_rate > 0) {
            tx_node = 1;
            break;
        }
    }
    //Yuan add temp
    tx_node = 1;
    if (tx_node) {
        price_update();
    }
}