cbrpagent.cc

CBRP协议（移动adhoc中基于分簇的路由协议）ns2下的源码

  // sendOutPacketWithRoute will add in the size of the src hdr, so
  // we have to subtract it out here
  struct hdr_cmn *ch = HDR_CMN(p.pkt);

  if (cbrph->route_shortening()) {
    //the previous node has successfully shortened one node
    for (int c = (cbrph->cur_addr()-1); c < cbrph->num_addrs()-1 ; c++)
      {
         cbrph->addrs[c].addr = cbrph->addrs[c+1].addr;
         p.route[c].addr = p.route[c+1].addr;
      }
    cbrph->cur_addr() -= 1;
    p.route.setIterator(cbrph->cur_addr());
    cbrph->num_addrs()-= 1;
    p.route.setLength(cbrph->num_addrs());
    cbrph->route_shortening() = 0;
    cbrph->route_shortened() = 1;
    trace("CBRP %.5f _%d_ success-shorten %s", Scheduler::instance().clock(),myaddr_, p.route.dump());
  }
  ch->size() -= cbrph->size();
  sendOutPacketWithRoute(p, false);
}

int
CBRP_Agent::handleRREP(CBRP_Packet &p)
{
 
  hdr_cbrp *cbrph = (hdr_cbrp*)p.pkt->access(off_cbrp_);
  hdr_cmn *cmnh =  (hdr_cmn*)p.pkt->access(off_cmn_);

  cmnh->addr_type() = AF_INET;

  cmnh->xmit_failure_ = CBRP_XmitFailureCallback;
  cmnh->xmit_failure_data_ = (void *) this;

  //just a cautionary step...
  if (p.route.length()<=0) {

#ifdef CBRP_DEBUG
    printf("ERROR route len %d\n", p.route.length());
    printf("p.src %s, p.dest %s, me %s, route-reply %s\n",
            p.src.dump(),p.dest.dump(),net_id.dump(),return_reply_path(p.pkt, off_cbrp_));
#endif
    abort();
  }

  if ((cbrph->cur_addr() >= 0) && (p.route[p.route.index()] == net_id) && (ntable->my_status == CLUSTER_HEAD)) {
    // I am the cluster head and have to calculate the route
    cbrph->cur_addr()--;
 
    if (cbrph->cur_addr()<0) {
      //i am the first cluster head, should be able to reach src
      if (ntable->isNeighbor(p.dest.getNSAddr_t())) {
        cmnh->next_hop() = p.dest.getNSAddr_t();

      }else {

        if (!(cmnh->next_hop()=ntable->GetQuickNextNode(p.dest.getNSAddr_t()))) {
          trace("CBRP %.5f _%d_ drop-reply-no-route unable return route to %s",Scheduler::instance().clock(), myaddr_,p.dest.dump());
          Packet::free(p.pkt);
          p.pkt = NULL;
          return 0;
        }
      }

      //if there is a link between next hop and the previous calculated hop, i am bypassed.
      //otherwise include me in the calculated route. 
      //Right now, the head won't search in its two-hop-topology table 
      //for a non-cluster-head guy to take off its work as the current 2-hop topology table 
      //implementation is not complete.  A more efficient data structure
      //has to be implemented to speed up the search. :)
      if (!ntable->existsLink(cmnh->next_hop(), 
                             (cbrph->reply_addrs()[cbrph->route_reply_len()-1]).addr)) {
        (cbrph->reply_addrs()[cbrph->route_reply_len()]).addr = net_id.addr;
        (cbrph->reply_addrs()[cbrph->route_reply_len()]).addr_type = AF_INET;
        cbrph->route_reply_len()++;
      }
      cmnh->prev_hop_ = net_id.getNSAddr_t();

      cmnh->size() = cbrph->size();
      Scheduler::instance().schedule(ll, p.pkt, 0);
      goto done;
    }

    // I am not the first cluster head, I'll try to reach the prev. cluster head  
    nsaddr_t prev_cluster = (cbrph->addrs)[cbrph->cur_addr_].addr;
    nsaddr_t next_node = (cbrph->reply_addrs()[cbrph->route_reply_len()-1]).addr;

    // firstly try to reach the prev_cluster by 2 hops
    adjtable_ent *ent = ntable->GetAdjEntry(prev_cluster,1);

    if (ent == NULL) {
      //if i could not reach prev_cluster by 2 hops, try 3-hop gateway.
      ent = ntable->GetAdjEntry(prev_cluster, 0);
    }

    if (ent == NULL) {
      //I failed to reach prev_cluster
      trace("CBRP %.5f _%s_ drop-reply-no-route #%d (route reply %s -> %s cannot reach prev cluster %d on route %s) previous hop %d", Scheduler::instance().clock(), net_id.dump(), cbrph->rtreq_seq(), p.src.dump(), p.dest.dump(),prev_cluster, p.route.dump(), cmnh->prev_hop_);
      Packet::free(p.pkt);
      p.pkt = NULL;
      return 0;
    }

    nexthop_ent *next_hop = ent->next_hop;
    assert(next_hop != NULL);
  
    while (next_hop) {
      //try to search for a gateway node that could be directly reached by route's next node
      //therefore, bypassing me.
      if (ntable->existsLink(next_hop->next_node,next_node)) {
        cmnh->next_hop() = next_hop->next_node;
        cmnh->addr_type() = AF_INET;
        break;
      }
      next_hop = next_hop->next;
    }

    if (next_hop == NULL) {
      cmnh->next_hop() = ent->next_hop->next_node;
      assert(cmnh->next_hop()>0);
      // it has to go pass me. -Jinyang
      (cbrph->reply_addrs()[cbrph->route_reply_len()]).addr = net_id.addr;
      (cbrph->reply_addrs()[cbrph->route_reply_len()]).addr_type = AF_INET;
      cbrph->route_reply_len()++;
    }     
    cmnh->size() = cbrph->size();
    cmnh->prev_hop_ = net_id.getNSAddr_t();
    Scheduler::instance().schedule(ll, p.pkt, 0);

  } else { 

    //I am an ordinary node non-CLUSTER_HEAD

    nsaddr_t next_cluster;

    //if I am just an ordinary node, I just forward it to the next cluster head
    cmnh->addr_type() = AF_INET;

    if (cbrph->cur_addr_<0) {
      //I am supposed to be two hop away from the destination node
      next_cluster = p.dest.addr;
      
      if (ntable->isNeighbor(next_cluster)) {
        cmnh->next_hop() = next_cluster;
      }else {
        cmnh->next_hop() = ntable->GetQuickNextNode(next_cluster);
        if (!cmnh->next_hop()) {
          trace("CBRP %.5f _%d_ drop-reply-no-route %s->%s #%d (route reply cannot reach prev cluster %d)",Scheduler::instance().clock(), myaddr_,p.src.dump(), p.dest.dump(), cbrph->rtreq_seq(),next_cluster);
          Packet::free(p.pkt);
          p.pkt = NULL;
          return 0;
        }
      }
    }else {
      //try to reach the next_cluster head.
      next_cluster = cbrph->addrs[cbrph->cur_addr()].addr;
      //check if the neighbor cluster is just one hop away
      if (ntable->isNeighbor(next_cluster)) {
        cmnh->next_hop() = next_cluster;
      } else { 
        cmnh->next_hop() = ntable->GetQuickNextNode(next_cluster);
        if (!cmnh->next_hop()) {
          trace("CBRP %.5f _%d_ drop-reply-no-route %s->%s #%d (route reply cannot reach prev cluster %d)", Scheduler::instance().clock(), myaddr_,p.src.dump(), p.dest.dump(), cbrph->rtreq_seq(),next_cluster);
          Packet::free(p.pkt);
          p.pkt = NULL;
          return 0;
        }
      }
 
    }

    //checking for wrong route reply calculation which could cause looping.
    int i;
    for (i=cbrph->route_reply_len();i>0;i--) {
      if (cbrph->reply_addrs()[i-1].addr == cmnh->next_hop()) {
        break;
      }
    }
    if (i>0) {
      trace("CBRP %.5f _%d_ drop-reply-looped %s->%s #%d existing route:%s reaching next cluster %d via %d",Scheduler::instance().clock(),myaddr_, p.src.dump(), p.dest.dump(), cbrph->rtreq_seq(),p.route.dump(),next_cluster,cmnh->next_hop());
       Packet::free(p.pkt);
       p.pkt = NULL;
       return 0;
     }
 
    //add myself to the route reply
    (cbrph->reply_addrs()[cbrph->route_reply_len()]).addr = net_id.addr;
    (cbrph->reply_addrs()[cbrph->route_reply_len()]).addr_type = AF_INET;
    cbrph->route_reply_len()++;
    
    cmnh->prev_hop_ = net_id.getNSAddr_t();
    cmnh->size() = cbrph->size();

    //Scheduler::instance().schedule(ll, p.pkt, Random::uniform(RREQ_JITTER));
    Scheduler::instance().schedule(ll, p.pkt,0 );
  }

done:
#ifdef CBPR_DEBUG
  trace("cbrp _%d_ route-reply-sent %s #%d -> %s , next hop %d to reach %d, rest of recorded cluster heads %s, constructed return path %s", myaddr_, p.src.dump(),cbrph->rtreq_seq(), p.dest.dump(), cmnh->next_hop(),(cbrph->cur_addr()>-1)?cbrph->addrs[cbrph->cur_addr()].addr:iph->dst(),p.route.dump(),return_reply_path(p.pkt, off_cbrp_)); 
#endif
  p.pkt = NULL;
  return 1;
}


void
CBRP_Agent::handleRREQ(CBRP_Packet &p)
  /* process a route request that isn't targeted at us 
     cluster heads will broadcast RREQ to all chosen gateways
     Chosen gateways will unicast RREQ to neighbor cluster head*/
{
  hdr_cbrp *cbrph =  (hdr_cbrp*)p.pkt->access(off_cbrp_);
  hdr_ip *iph = (hdr_ip*)p.pkt->access(off_ip_);

  assert (cbrph->route_request());
  if ((u_int32_t)iph->dst() != IP_BROADCAST) {
    //I am the neighborcluster head, i should broadcast this RREQ to my neighbors
    if (ntable->my_status == CLUSTER_HEAD || (iph->dst() == myaddr_)) {
       BroadcastRREQ(p);
    }else {
    //i should forward packet to the clusterhead as specified in ip destination
    //this could happen when the neighbor cluster head is 3 hops away and I am the second gateway
       UnicastRREQ(p,iph->dst());
    }

  }else {
   
    Packet *p_ori = p.pkt; 

    for (int i=0;i<cbrph->num_forwarders();i++) {


       if (cbrph->forwarders[i].which_gateway == myaddr_) {
          p.pkt = p_ori->copy();

          if ((cbrph->forwarders[i].which_head == myaddr_) && (ntable->my_status == CLUSTER_HEAD)) {
            //broadcast the pkt to other cluster heads
            BroadcastRREQ(p);
          }else {
            // if I am just an ordinary node, then just forward the RREQ as indicated in header
            UnicastRREQ(p,cbrph->forwarders[i].which_head);
          }
       }
    }
    // discard un-used RREQ packet
    if (p_ori) Packet::free(p_ori);

  }
  p.pkt = NULL;

}


void
CBRP_Agent::BroadcastRREQ(CBRP_Packet &p)
{

  hdr_cbrp *cbrph =  (hdr_cbrp*)p.pkt->access(off_cbrp_);
  hdr_cmn *cmnh = (hdr_cmn*)p.pkt->access(off_cmn_);
  hdr_ip *iph = (hdr_ip*)p.pkt->access(off_ip_);

  assert(cbrph->route_request());

  if (ignoreRouteRequestp(p))
    { 
      //-Jinyang only cluster heads records RREQs seen and drop RREQ if duplicate etc.
      if (verbose_srr)
        trace("cbrp %.5f _%s_ dropped %s #%d (ignored)",
            Scheduler::instance().clock(), net_id.dump(), p.src.dump(),
            cbrph->rtreq_seq());
      Packet::free(p.pkt);  // pkt is a route request we've already processed
      return; // drop silently

    }

  request_table.insert(p.src, p.src, cbrph->rtreq_seq());

  if (p.route.length() > (cbrph->max_propagation()/2))  
  // the chain of cluster heads are roughly twice as long as the hop by hop route
    {  
        if (verbose_srr)
          trace("cbrp %.5f _%s_ dropped %s #%d (prop limit exceeded)",
                Scheduler::instance().clock(), net_id.dump(), p.src.dump(),
                cbrph->rtreq_seq());
        Packet::free(p.pkt); // pkt isn't for us, and isn't data carrying
        p.pkt = 0;
        return;
     }


  if ((2*p.route.length()) > MAX_SR_LEN)
    {   
        // no propagation
        trace("cbrp %.5f _%s_ dropped %s #%d (SR full)",
              Scheduler::instance().clock(), net_id.dump(), p.src.dump(),
              cbrph->rtreq_seq());
        Packet::free(p.pkt);
        p.pkt = 0;
        return;
      }


  p.route.appendToPath(net_id);
  fillCBRPPath(p.route,cbrph);

  cmnh->ptype() = PT_CBRP;
  cmnh->addr_type() = AF_INET;

  if (ntable->isNeighbor(cbrph->request_destination())) {
      
    //directly unicast to the destination 
    cmnh->next_hop() = cbrph->request_destination();
    iph->dst() = cbrph->request_destination();
    cbrph->num_forwarders() = 0;
    cmnh->size() = cbrph->size();

    Scheduler &s = Scheduler::instance();
    s.schedule(ll,p.pkt,0.0);

    return;
       
   }

#ifdef CBRP_DEBUG
  trace("cbrp RREQ %d: %s",myaddr_,ntable->printNeighbors());
#endif
    
  if (ntable->GetQuickNextNode(cbrph->request_destination())) {

    iph->dst() = cbrph->request_destination();
    cmnh->next_hop() = ntable->GetQuickNextNode(cbrph->request_destination());

    cbrph->num_forwarders() = 0;
    cmnh->size() = cbrph->size();

    Scheduler::instance().schedule(ll,p.pkt,0.0);
    p.pkt = 0;
    return;
  }

  if (cbrp_reply_from_cache_on_propagating && replyFromRouteCache(p)) {
    p.pkt = NULL;
    return;
  }
 
  cmnh->next_hop() = MAC_BROADCAST;
  iph->dst() = IP_BROADCAST;

  int total = cbrph->num_forwarders();

  Packet *p_copy = p.pkt->copy();

  hdr_cbrp *new_cbrph = (hdr_cbrp*)p_copy->access(off_cbrp_);

  adjtable_ent *p_adj = ntable->adjtable_1;

  int i=0; 
  int j=0;

  while (p_adj && i<MAX_NEIGHBORS) {
    //check if a neighbor cluster head has been visited b4 by this RREQ by checking its recorded route so far
    if (p.route.member(ID(p_adj->neighbor_cluster, ::IP))) {

#ifdef CBRP_DEBUG
      trace("cbrp RREQ%d: ignored %d, duplicate in route(%s)",myaddr_,p_adj->neighbor_cluster,p.route.dump());
#endif
       p_adj = p_adj->next;
       continue;
     }
 
    //check if a neighbor cluster will have been visited by prev. cluster head by checking the forwarders' list
    for (j=0;j<total;j++) {

      if (p_adj->neighbor_cluster == cbrph->forwarders[j].which_head) {

#ifdef CBRP_DEBUG
        trace("cbrp RREQ%d: ignored %d, duplicate in previous broadcast",myaddr_,p_adj->neighbor_cluster);
#endif
        break;
      }
    }

    if (j>= total) {  //the next cluster head has NOT been visited to the best of our knowledge. :)

#ifdef CBRP_DEBUG
      trace("cbrp %.5f _%s_ rebroadcast %s #%d ->%d %s to 2 hop head %d via %d",Scheduler::instance().clock(), net_id.dump(), 
             p.src.dump(), cbrph->rtreq_seq(), cbrph->request_destination(), 
             p.route.dump(), p_adj->neighbor_cluster, 
             p_adj->next_hop->next_node);
#endif

      
      /*new_cbrph->reply_addrs()[i].which_gateway= p_adj->next_hop->next_node; */
      new_cbrph->forwarders[i].which_gateway= ntable->GetQuickNextNode(p_adj->neighbor_cluster);
      new_cbrph->forwarders[i++].which_head= p_adj->neighbor_cluster;

    }
    p_adj = p_adj->next;
  }  
 
  //if I am not a cluster head, i don't send RREQ to 3-hop neighbor cluster head 

  if (ntable->my_status != CLUSTER_HEAD) {
    goto DONE;
  }
   
  p_adj = ntable->adjtable_2;

  while (p_adj && i<MAX_NEIGHBORS) {

    if (p.route.member(ID(p_adj->neighbor_cluster, ::IP))) {

#ifdef CBRP_DEBUG