开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > Windows编程 > 通讯编程 > 查看源码
aodv.cc
资源名称：ns-allinone-2.33.tar.gz　[点击查看]
上传用户：rrhhcc
上传日期：2015-12-11
资源大小：54129k
文件大小：34k
源码类别：

通讯编程

开发平台：

Visual C++

aodv.cc：源码内容
  1. /*
  2. Copyright (c) 1997, 1998 Carnegie Mellon University.  All Rights
  3. Reserved. 
  5. Redistribution and use in source and binary forms, with or without
  6. modification, are permitted provided that the following conditions are met:
  8. 1. Redistributions of source code must retain the above copyright notice,
  9. this list of conditions and the following disclaimer.
  10. 2. Redistributions in binary form must reproduce the above copyright notice,
  11. this list of conditions and the following disclaimer in the documentation
  12. and/or other materials provided with the distribution.
  13. 3. The name of the author may not be used to endorse or promote products
  14. derived from this software without specific prior written permission.
  16. THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  17. IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  18. OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  19. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  20. SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  21. PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
  22. OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  23. WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
  24. OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  25. ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27. The AODV code developed by the CMU/MONARCH group was optimized and tuned by Samir Das and Mahesh Marina, University of Cincinnati. The work was partially done in Sun Microsystems. Modified for gratuitous replies by Anant Utgikar, 09/16/02.
  29. */
  31. //#include <ip.h>
  33. #include <aodv/aodv.h>
  34. #include <aodv/aodv_packet.h>
  35. #include <random.h>
  36. #include <cmu-trace.h>
  37. //#include <energy-model.h>
  39. #define max(a,b)        ( (a) > (b) ? (a) : (b) )
  40. #define CURRENT_TIME    Scheduler::instance().clock()
  42. //#define DEBUG
  43. //#define ERROR
  45. #ifdef DEBUG
  46. static int extra_route_reply = 0;
  47. static int limit_route_request = 0;
  48. static int route_request = 0;
  49. #endif
  52. /*
  53.   TCL Hooks
  54. */
  57. int hdr_aodv::offset_;
  58. static class AODVHeaderClass : public PacketHeaderClass {
  59. public:
  60.         AODVHeaderClass() : PacketHeaderClass("PacketHeader/AODV",
  61.                                               sizeof(hdr_all_aodv)) {
  62.   bind_offset(&hdr_aodv::offset_);
  63. } 
  64. } class_rtProtoAODV_hdr;
  66. static class AODVclass : public TclClass {
  67. public:
  68.         AODVclass() : TclClass("Agent/AODV") {}
  69.         TclObject* create(int argc, const char*const* argv) {
  70.           assert(argc == 5);
  71.           //return (new AODV((nsaddr_t) atoi(argv[4])));
  72.   return (new AODV((nsaddr_t) Address::instance().str2addr(argv[4])));
  73.         }
  74. } class_rtProtoAODV;
  77. int
  78. AODV::command(int argc, const char*const* argv) {
  79.   if(argc == 2) {
  80.   Tcl& tcl = Tcl::instance();
  81.     
  82.     if(strncasecmp(argv[1], "id", 2) == 0) {
  83.       tcl.resultf("%d", index);
  84.       return TCL_OK;
  85.     }
  86.     
  87.     if(strncasecmp(argv[1], "start", 2) == 0) {
  88.       btimer.handle((Event*) 0);
  90. #ifndef AODV_LINK_LAYER_DETECTION
  91.       htimer.handle((Event*) 0);
  92.       ntimer.handle((Event*) 0);
  93. #endif // LINK LAYER DETECTION
  95.       rtimer.handle((Event*) 0);
  96.       return TCL_OK;
  97.      }               
  98.   }
  99.   else if(argc == 3) {
  100.     if(strcmp(argv[1], "index") == 0) {
  101.       index = atoi(argv[2]);
  102.       return TCL_OK;
  103.     }
  105.     else if(strcmp(argv[1], "log-target") == 0 || strcmp(argv[1], "tracetarget") == 0) {
  106.       logtarget = (Trace*) TclObject::lookup(argv[2]);
  107.       if(logtarget == 0)
  108. return TCL_ERROR;
  109.       return TCL_OK;
  110.     }
  111.     else if(strcmp(argv[1], "drop-target") == 0) {
  112.     int stat = rqueue.command(argc,argv);
  113.       if (stat != TCL_OK) return stat;
  114.       return Agent::command(argc, argv);
  115.     }
  116.     else if(strcmp(argv[1], "if-queue") == 0) {
  117.     ifqueue = (PriQueue*) TclObject::lookup(argv[2]);
  118.       
  119.       if(ifqueue == 0)
  120. return TCL_ERROR;
  121.       return TCL_OK;
  122.     }
  123.     else if (strcmp(argv[1], "port-dmux") == 0) {
  124.      dmux_ = (PortClassifier *)TclObject::lookup(argv[2]);
  125. if (dmux_ == 0) {
  126. fprintf (stderr, "%s: %s lookup of %s failedn", __FILE__,
  127. argv[1], argv[2]);
  128. return TCL_ERROR;
  129. }
  130. return TCL_OK;
  131.     }
  132.   }
  133.   return Agent::command(argc, argv);
  134. }
  136. /* 
  137.    Constructor
  138. */
  140. AODV::AODV(nsaddr_t id) : Agent(PT_AODV),
  141.   btimer(this), htimer(this), ntimer(this), 
  142.   rtimer(this), lrtimer(this), rqueue() {
  143.  
  144.                 
  145.   index = id;
  146.   seqno = 2;
  147.   bid = 1;
  149.   LIST_INIT(&nbhead);
  150.   LIST_INIT(&bihead);
  152.   logtarget = 0;
  153.   ifqueue = 0;
  154. }
  156. /*
  157.   Timers
  158. */
  160. void
  161. BroadcastTimer::handle(Event*) {
  162.   agent->id_purge();
  163.   Scheduler::instance().schedule(this, &intr, BCAST_ID_SAVE);
  164. }
  166. void
  167. HelloTimer::handle(Event*) {
  168.    agent->sendHello();
  169.    double interval = MinHelloInterval + 
  170.                  ((MaxHelloInterval - MinHelloInterval) * Random::uniform());
  171.    assert(interval >= 0);
  172.    Scheduler::instance().schedule(this, &intr, interval);
  173. }
  175. void
  176. NeighborTimer::handle(Event*) {
  177.   agent->nb_purge();
  178.   Scheduler::instance().schedule(this, &intr, HELLO_INTERVAL);
  179. }
  181. void
  182. RouteCacheTimer::handle(Event*) {
  183.   agent->rt_purge();
  184. #define FREQUENCY 0.5 // sec
  185.   Scheduler::instance().schedule(this, &intr, FREQUENCY);
  186. }
  188. void
  189. LocalRepairTimer::handle(Event* p)  {  // SRD: 5/4/99
  190. aodv_rt_entry *rt;
  191. struct hdr_ip *ih = HDR_IP( (Packet *)p);
  193.    /* you get here after the timeout in a local repair attempt */
  194.    /* fprintf(stderr, "%sn", __FUNCTION__); */
  197.     rt = agent->rtable.rt_lookup(ih->daddr());
  199.     if (rt && rt->rt_flags != RTF_UP) {
  200.     // route is yet to be repaired
  201.     // I will be conservative and bring down the route
  202.     // and send route errors upstream.
  203.     /* The following assert fails, not sure why */
  204.     /* assert (rt->rt_flags == RTF_IN_REPAIR); */
  206.       //rt->rt_seqno++;
  207.       agent->rt_down(rt);
  208.       // send RERR
  209. #ifdef DEBUG
  210.       fprintf(stderr,"Node %d: Dst - %d, failed local repairn",index, rt->rt_dst);
  211. #endif      
  212.     }
  213.     Packet::free((Packet *)p);
  214. }
  217. /*
  218.    Broadcast ID Management  Functions
  219. */
  222. void
  223. AODV::id_insert(nsaddr_t id, u_int32_t bid) {
  224. BroadcastID *b = new BroadcastID(id, bid);
  226.  assert(b);
  227.  b->expire = CURRENT_TIME + BCAST_ID_SAVE;
  228.  LIST_INSERT_HEAD(&bihead, b, link);
  229. }
  231. /* SRD */
  232. bool
  233. AODV::id_lookup(nsaddr_t id, u_int32_t bid) {
  234. BroadcastID *b = bihead.lh_first;
  235.  
  236.  // Search the list for a match of source and bid
  237.  for( ; b; b = b->link.le_next) {
  238.    if ((b->src == id) && (b->id == bid))
  239.      return true;     
  240.  }
  241.  return false;
  242. }
  244. void
  245. AODV::id_purge() {
  246. BroadcastID *b = bihead.lh_first;
  247. BroadcastID *bn;
  248. double now = CURRENT_TIME;
  250.  for(; b; b = bn) {
  251.    bn = b->link.le_next;
  252.    if(b->expire <= now) {
  253.      LIST_REMOVE(b,link);
  254.      delete b;
  255.    }
  256.  }
  257. }
  259. /*
  260.   Helper Functions
  261. */
  263. double
  264. AODV::PerHopTime(aodv_rt_entry *rt) {
  265. int num_non_zero = 0, i;
  266. double total_latency = 0.0;
  268.  if (!rt)
  269.    return ((double) NODE_TRAVERSAL_TIME );
  271.  for (i=0; i < MAX_HISTORY; i++) {
  272.    if (rt->rt_disc_latency[i] > 0.0) {
  273.       num_non_zero++;
  274.       total_latency += rt->rt_disc_latency[i];
  275.    }
  276.  }
  277.  if (num_non_zero > 0)
  278.    return(total_latency / (double) num_non_zero);
  279.  else
  280.    return((double) NODE_TRAVERSAL_TIME);
  282. }
  284. /*
  285.   Link Failure Management Functions
  286. */
  288. static void
  289. aodv_rt_failed_callback(Packet *p, void *arg) {
  290.   ((AODV*) arg)->rt_ll_failed(p);
  291. }
  293. /*
  294.  * This routine is invoked when the link-layer reports a route failed.
  295.  */
  296. void
  297. AODV::rt_ll_failed(Packet *p) {
  298. struct hdr_cmn *ch = HDR_CMN(p);
  299. struct hdr_ip *ih = HDR_IP(p);
  300. aodv_rt_entry *rt;
  301. nsaddr_t broken_nbr = ch->next_hop_;
  303. #ifndef AODV_LINK_LAYER_DETECTION
  304.  drop(p, DROP_RTR_MAC_CALLBACK);
  305. #else 
  307.  /*
  308.   * Non-data packets and Broadcast Packets can be dropped.
  309.   */
  310.   if(! DATA_PACKET(ch->ptype()) ||
  311.      (u_int32_t) ih->daddr() == IP_BROADCAST) {
  312.     drop(p, DROP_RTR_MAC_CALLBACK);
  313.     return;
  314.   }
  315.   log_link_broke(p);
  316. if((rt = rtable.rt_lookup(ih->daddr())) == 0) {
  317.     drop(p, DROP_RTR_MAC_CALLBACK);
  318.     return;
  319.   }
  320.   log_link_del(ch->next_hop_);
  322. #ifdef AODV_LOCAL_REPAIR
  323.   /* if the broken link is closer to the dest than source, 
  324.      attempt a local repair. Otherwise, bring down the route. */
  327.   if (ch->num_forwards() > rt->rt_hops) {
  328.     local_rt_repair(rt, p); // local repair
  329.     // retrieve all the packets in the ifq using this link,
  330.     // queue the packets for which local repair is done, 
  331.     return;
  332.   }
  333.   else
  334. #endif // LOCAL REPAIR
  336.   {
  337.     drop(p, DROP_RTR_MAC_CALLBACK);
  338.     // Do the same thing for other packets in the interface queue using the
  339.     // broken link -Mahesh
  340. while((p = ifqueue->filter(broken_nbr))) {
  341.      drop(p, DROP_RTR_MAC_CALLBACK);
  342.     }
  343.     nb_delete(broken_nbr);
  344.   }
  346. #endif // LINK LAYER DETECTION
  347. }
  349. void
  350. AODV::handle_link_failure(nsaddr_t id) {
  351. aodv_rt_entry *rt, *rtn;
  352. Packet *rerr = Packet::alloc();
  353. struct hdr_aodv_error *re = HDR_AODV_ERROR(rerr);
  355.  re->DestCount = 0;
  356.  for(rt = rtable.head(); rt; rt = rtn) {  // for each rt entry
  357.    rtn = rt->rt_link.le_next; 
  358.    if ((rt->rt_hops != INFINITY2) && (rt->rt_nexthop == id) ) {
  359.      assert (rt->rt_flags == RTF_UP);
  360.      assert((rt->rt_seqno%2) == 0);
  361.      rt->rt_seqno++;
  362.      re->unreachable_dst[re->DestCount] = rt->rt_dst;
  363.      re->unreachable_dst_seqno[re->DestCount] = rt->rt_seqno;
  364. #ifdef DEBUG
  365.      fprintf(stderr, "%s(%f): %dt(%dt%ut%d)n", __FUNCTION__, CURRENT_TIME,
  366.      index, re->unreachable_dst[re->DestCount],
  367.      re->unreachable_dst_seqno[re->DestCount], rt->rt_nexthop);
  368. #endif // DEBUG
  369.      re->DestCount += 1;
  370.      rt_down(rt);
  371.    }
  372.    // remove the lost neighbor from all the precursor lists
  373.    rt->pc_delete(id);
  374.  }   
  376.  if (re->DestCount > 0) {
  377. #ifdef DEBUG
  378.    fprintf(stderr, "%s(%f): %dtsending RERR...n", __FUNCTION__, CURRENT_TIME, index);
  379. #endif // DEBUG
  380.    sendError(rerr, false);
  381.  }
  382.  else {
  383.    Packet::free(rerr);
  384.  }
  385. }
  387. void
  388. AODV::local_rt_repair(aodv_rt_entry *rt, Packet *p) {
  389. #ifdef DEBUG
  390.   fprintf(stderr,"%s: Dst - %dn", __FUNCTION__, rt->rt_dst); 
  391. #endif  
  392.   // Buffer the packet 
  393.   rqueue.enque(p);
  395.   // mark the route as under repair 
  396.   rt->rt_flags = RTF_IN_REPAIR;
  398.   sendRequest(rt->rt_dst);
  400.   // set up a timer interrupt
  401.   Scheduler::instance().schedule(&lrtimer, p->copy(), rt->rt_req_timeout);
  402. }
  404. void
  405. AODV::rt_update(aodv_rt_entry *rt, u_int32_t seqnum, u_int16_t metric,
  406.         nsaddr_t nexthop, double expire_time) {
  408.      rt->rt_seqno = seqnum;
  409.      rt->rt_hops = metric;
  410.      rt->rt_flags = RTF_UP;
  411.      rt->rt_nexthop = nexthop;
  412.      rt->rt_expire = expire_time;
  413. }
  415. void
  416. AODV::rt_down(aodv_rt_entry *rt) {
  417.   /*
  418.    *  Make sure that you don't "down" a route more than once.
  419.    */
  421.   if(rt->rt_flags == RTF_DOWN) {
  422.     return;
  423.   }
  425.   // assert (rt->rt_seqno%2); // is the seqno odd?
  426.   rt->rt_last_hop_count = rt->rt_hops;
  427.   rt->rt_hops = INFINITY2;
  428.   rt->rt_flags = RTF_DOWN;
  429.   rt->rt_nexthop = 0;
  430.   rt->rt_expire = 0;
  432. } /* rt_down function */
  434. /*
  435.   Route Handling Functions
  436. */
  438. void
  439. AODV::rt_resolve(Packet *p) {
  440. struct hdr_cmn *ch = HDR_CMN(p);
  441. struct hdr_ip *ih = HDR_IP(p);
  442. aodv_rt_entry *rt;
  444.  /*
  445.   *  Set the transmit failure callback.  That
  446.   *  won't change.
  447.   */
  448.  ch->xmit_failure_ = aodv_rt_failed_callback;
  449.  ch->xmit_failure_data_ = (void*) this;
  450. rt = rtable.rt_lookup(ih->daddr());
  451.  if(rt == 0) {
  452.   rt = rtable.rt_add(ih->daddr());
  453.  }
  455.  /*
  456.   * If the route is up, forward the packet 
  457.   */
  459.  if(rt->rt_flags == RTF_UP) {
  460.    assert(rt->rt_hops != INFINITY2);
  461.    forward(rt, p, NO_DELAY);
  462.  }
  463.  /*
  464.   *  if I am the source of the packet, then do a Route Request.
  465.   */
  466. else if(ih->saddr() == index) {
  467.    rqueue.enque(p);
  468.    sendRequest(rt->rt_dst);
  469.  }
  470.  /*
  471.   * A local repair is in progress. Buffer the packet. 
  472.   */
  473.  else if (rt->rt_flags == RTF_IN_REPAIR) {
  474.    rqueue.enque(p);
  475.  }
  477.  /*
  478.   * I am trying to forward a packet for someone else to which
  479.   * I don't have a route.
  480.   */
  481.  else {
  482.  Packet *rerr = Packet::alloc();
  483.  struct hdr_aodv_error *re = HDR_AODV_ERROR(rerr);
  484.  /* 
  485.   * For now, drop the packet and send error upstream.
  486.   * Now the route errors are broadcast to upstream
  487.   * neighbors - Mahesh 09/11/99
  488.   */
  489.  
  490.    assert (rt->rt_flags == RTF_DOWN);
  491.    re->DestCount = 0;
  492.    re->unreachable_dst[re->DestCount] = rt->rt_dst;
  493.    re->unreachable_dst_seqno[re->DestCount] = rt->rt_seqno;
  494.    re->DestCount += 1;
  495. #ifdef DEBUG
  496.    fprintf(stderr, "%s: sending RERR...n", __FUNCTION__);
  497. #endif
  498.    sendError(rerr, false);
  500.    drop(p, DROP_RTR_NO_ROUTE);
  501.  }
  503. }
  505. void
  506. AODV::rt_purge() {
  507. aodv_rt_entry *rt, *rtn;
  508. double now = CURRENT_TIME;
  509. double delay = 0.0;
  510. Packet *p;
  512.  for(rt = rtable.head(); rt; rt = rtn) {  // for each rt entry
  513.    rtn = rt->rt_link.le_next;
  514.    if ((rt->rt_flags == RTF_UP) && (rt->rt_expire < now)) {
  515.    // if a valid route has expired, purge all packets from 
  516.    // send buffer and invalidate the route.                    
  517. assert(rt->rt_hops != INFINITY2);
  518.      while((p = rqueue.deque(rt->rt_dst))) {
  519. #ifdef DEBUG
  520.        fprintf(stderr, "%s: calling drop()n",
  521.                        __FUNCTION__);
  522. #endif // DEBUG
  523.        drop(p, DROP_RTR_NO_ROUTE);
  524.      }
  525.      rt->rt_seqno++;
  526.      assert (rt->rt_seqno%2);
  527.      rt_down(rt);
  528.    }
  529.    else if (rt->rt_flags == RTF_UP) {
  530.    // If the route is not expired,
  531.    // and there are packets in the sendbuffer waiting,
  532.    // forward them. This should not be needed, but this extra 
  533.    // check does no harm.
  534.      assert(rt->rt_hops != INFINITY2);
  535.      while((p = rqueue.deque(rt->rt_dst))) {
  536.        forward (rt, p, delay);
  537.        delay += ARP_DELAY;
  538.      }
  539.    } 
  540.    else if (rqueue.find(rt->rt_dst))
  541.    // If the route is down and 
  542.    // if there is a packet for this destination waiting in
  543.    // the sendbuffer, then send out route request. sendRequest
  544.    // will check whether it is time to really send out request
  545.    // or not.
  546.    // This may not be crucial to do it here, as each generated 
  547.    // packet will do a sendRequest anyway.
  549.      sendRequest(rt->rt_dst); 
  550.    }
  552. }
  554. /*
  555.   Packet Reception Routines
  556. */
  558. void
  559. AODV::recv(Packet *p, Handler*) {
  560. struct hdr_cmn *ch = HDR_CMN(p);
  561. struct hdr_ip *ih = HDR_IP(p);
  563.  assert(initialized());
  564.  //assert(p->incoming == 0);
  565.  // XXXXX NOTE: use of incoming flag has been depracated; In order to track direction of pkt flow, direction_ in hdr_cmn is used instead. see packet.h for details.
  567.  if(ch->ptype() == PT_AODV) {
  568.    ih->ttl_ -= 1;
  569.    recvAODV(p);
  570.    return;
  571.  }
  574.  /*
  575.   *  Must be a packet I'm originating...
  576.   */
  577. if((ih->saddr() == index) && (ch->num_forwards() == 0)) {
  578.  /*
  579.   * Add the IP Header
  580.   */
  581.    ch->size() += IP_HDR_LEN;
  582.    // Added by Parag Dadhania && John Novatnack to handle broadcasting
  583.    if ( (u_int32_t)ih->daddr() != IP_BROADCAST)
  584.      ih->ttl_ = NETWORK_DIAMETER;
  585. }
  586.  /*
  587.   *  I received a packet that I sent.  Probably
  588.   *  a routing loop.
  589.   */
  590. else if(ih->saddr() == index) {
  591.    drop(p, DROP_RTR_ROUTE_LOOP);
  592.    return;
  593.  }
  594.  /*
  595.   *  Packet I'm forwarding...
  596.   */
  597.  else {
  598.  /*
  599.   *  Check the TTL.  If it is zero, then discard.
  600.   */
  601.    if(--ih->ttl_ == 0) {
  602.      drop(p, DROP_RTR_TTL);
  603.      return;
  604.    }
  605.  }
  606. // Added by Parag Dadhania && John Novatnack to handle broadcasting
  607.  if ( (u_int32_t)ih->daddr() != IP_BROADCAST)
  608.    rt_resolve(p);
  609.  else
  610.    forward((aodv_rt_entry*) 0, p, NO_DELAY);
  611. }
  614. void
  615. AODV::recvAODV(Packet *p) {
  616.  struct hdr_aodv *ah = HDR_AODV(p);
  618.  assert(HDR_IP (p)->sport() == RT_PORT);
  619.  assert(HDR_IP (p)->dport() == RT_PORT);
  621.  /*
  622.   * Incoming Packets.
  623.   */
  624.  switch(ah->ah_type) {
  626.  case AODVTYPE_RREQ:
  627.    recvRequest(p);
  628.    break;
  630.  case AODVTYPE_RREP:
  631.    recvReply(p);
  632.    break;
  634.  case AODVTYPE_RERR:
  635.    recvError(p);
  636.    break;
  638.  case AODVTYPE_HELLO:
  639.    recvHello(p);
  640.    break;
  641.         
  642.  default:
  643.    fprintf(stderr, "Invalid AODV type (%x)n", ah->ah_type);
  644.    exit(1);
  645.  }
  647. }
  650. void
  651. AODV::recvRequest(Packet *p) {
  652. struct hdr_ip *ih = HDR_IP(p);
  653. struct hdr_aodv_request *rq = HDR_AODV_REQUEST(p);
  654. aodv_rt_entry *rt;
  656.   /*
  657.    * Drop if:
  658.    *      - I'm the source
  659.    *      - I recently heard this request.
  660.    */
  662.   if(rq->rq_src == index) {
  663. #ifdef DEBUG
  664.     fprintf(stderr, "%s: got my own REQUESTn", __FUNCTION__);
  665. #endif // DEBUG
  666.     Packet::free(p);
  667.     return;
  668.   } 
  670.  if (id_lookup(rq->rq_src, rq->rq_bcast_id)) {
  672. #ifdef DEBUG
  673.    fprintf(stderr, "%s: discarding requestn", __FUNCTION__);
  674. #endif // DEBUG
  675.  
  676.    Packet::free(p);
  677.    return;
  678.  }
  680.  /*
  681.   * Cache the broadcast ID
  682.   */
  683.  id_insert(rq->rq_src, rq->rq_bcast_id);
  687.  /* 
  688.   * We are either going to forward the REQUEST or generate a
  689.   * REPLY. Before we do anything, we make sure that the REVERSE
  690.   * route is in the route table.
  691.   */
  692.  aodv_rt_entry *rt0; // rt0 is the reverse route 
  693.    
  694.    rt0 = rtable.rt_lookup(rq->rq_src);
  695.    if(rt0 == 0) { /* if not in the route table */
  696.    // create an entry for the reverse route.
  697.      rt0 = rtable.rt_add(rq->rq_src);
  698.    }
  699.   
  700.    rt0->rt_expire = max(rt0->rt_expire, (CURRENT_TIME + REV_ROUTE_LIFE));
  702.    if ( (rq->rq_src_seqno > rt0->rt_seqno ) ||
  703.      ((rq->rq_src_seqno == rt0->rt_seqno) && 
  704.  (rq->rq_hop_count < rt0->rt_hops)) ) {
  705.    // If we have a fresher seq no. or lesser #hops for the 
  706.    // same seq no., update the rt entry. Else don't bother.
  707. rt_update(rt0, rq->rq_src_seqno, rq->rq_hop_count, ih->saddr(),
  708.              max(rt0->rt_expire, (CURRENT_TIME + REV_ROUTE_LIFE)) );
  709.      if (rt0->rt_req_timeout > 0.0) {
  710.      // Reset the soft state and 
  711.      // Set expiry time to CURRENT_TIME + ACTIVE_ROUTE_TIMEOUT
  712.      // This is because route is used in the forward direction,
  713.      // but only sources get benefited by this change
  714.        rt0->rt_req_cnt = 0;
  715.        rt0->rt_req_timeout = 0.0; 
  716.        rt0->rt_req_last_ttl = rq->rq_hop_count;
  717.        rt0->rt_expire = CURRENT_TIME + ACTIVE_ROUTE_TIMEOUT;
  718.      }
  720.      /* Find out whether any buffered packet can benefit from the 
  721.       * reverse route.
  722.       * May need some change in the following code - Mahesh 09/11/99
  723.       */
  724.      assert (rt0->rt_flags == RTF_UP);
  725.      Packet *buffered_pkt;
  726.      while ((buffered_pkt = rqueue.deque(rt0->rt_dst))) {
  727.        if (rt0 && (rt0->rt_flags == RTF_UP)) {
  728. assert(rt0->rt_hops != INFINITY2);
  729.          forward(rt0, buffered_pkt, NO_DELAY);
  730.        }
  731.      }
  732.    } 
  733.    // End for putting reverse route in rt table
  736.  /*
  737.   * We have taken care of the reverse route stuff.
  738.   * Now see whether we can send a route reply. 
  739.   */
  741.  rt = rtable.rt_lookup(rq->rq_dst);
  743.  // First check if I am the destination ..
  745.  if(rq->rq_dst == index) {
  747. #ifdef DEBUG
  748.    fprintf(stderr, "%d - %s: destination sending replyn",
  749.                    index, __FUNCTION__);
  750. #endif // DEBUG
  752.                
  753.    // Just to be safe, I use the max. Somebody may have
  754.    // incremented the dst seqno.
  755.    seqno = max(seqno, rq->rq_dst_seqno)+1;
  756.    if (seqno%2) seqno++;
  758.    sendReply(rq->rq_src,           // IP Destination
  759.              1,                    // Hop Count
  760.              index,                // Dest IP Address
  761.              seqno,                // Dest Sequence Num
  762.              MY_ROUTE_TIMEOUT,     // Lifetime
  763.              rq->rq_timestamp);    // timestamp
  764.  
  765.    Packet::free(p);
  766.  }
  768.  // I am not the destination, but I may have a fresh enough route.
  770.  else if (rt && (rt->rt_hops != INFINITY2) && 
  771.    (rt->rt_seqno >= rq->rq_dst_seqno) ) {
  773.    //assert (rt->rt_flags == RTF_UP);
  774.    assert(rq->rq_dst == rt->rt_dst);
  775.    //assert ((rt->rt_seqno%2) == 0); // is the seqno even?
  776.    sendReply(rq->rq_src,
  777.              rt->rt_hops + 1,
  778.              rq->rq_dst,
  779.              rt->rt_seqno,
  780.      (u_int32_t) (rt->rt_expire - CURRENT_TIME),
  781.      //             rt->rt_expire - CURRENT_TIME,
  782.              rq->rq_timestamp);
  783.    // Insert nexthops to RREQ source and RREQ destination in the
  784.    // precursor lists of destination and source respectively
  785.    rt->pc_insert(rt0->rt_nexthop); // nexthop to RREQ source
  786.    rt0->pc_insert(rt->rt_nexthop); // nexthop to RREQ destination
  788. #ifdef RREQ_GRAT_RREP  
  790.    sendReply(rq->rq_dst,
  791.              rq->rq_hop_count,
  792.              rq->rq_src,
  793.              rq->rq_src_seqno,
  794.      (u_int32_t) (rt->rt_expire - CURRENT_TIME),
  795.      //             rt->rt_expire - CURRENT_TIME,
  796.              rq->rq_timestamp);
  797. #endif
  798.    
  799. // TODO: send grat RREP to dst if G flag set in RREQ using rq->rq_src_seqno, rq->rq_hop_counT
  800.    
  801. // DONE: Included gratuitous replies to be sent as per IETF aodv draft specification. As of now, G flag has not been dynamically used and is always set or reset in aodv-packet.h --- Anant Utgikar, 09/16/02.
  803. Packet::free(p);
  804.  }
  805.  /*
  806.   * Can't reply. So forward the  Route Request
  807.   */
  808.  else {
  809.    ih->saddr() = index;
  810.    ih->daddr() = IP_BROADCAST;
  811.    rq->rq_hop_count += 1;
  812.    // Maximum sequence number seen en route
  813.    if (rt) rq->rq_dst_seqno = max(rt->rt_seqno, rq->rq_dst_seqno);
  814.    forward((aodv_rt_entry*) 0, p, DELAY);
  815.  }
  817. }
  820. void
  821. AODV::recvReply(Packet *p) {
  822. //struct hdr_cmn *ch = HDR_CMN(p);
  823. struct hdr_ip *ih = HDR_IP(p);
  824. struct hdr_aodv_reply *rp = HDR_AODV_REPLY(p);
  825. aodv_rt_entry *rt;
  826. char suppress_reply = 0;
  827. double delay = 0.0;
  829. #ifdef DEBUG
  830.  fprintf(stderr, "%d - %s: received a REPLYn", index, __FUNCTION__);
  831. #endif // DEBUG
  834.  /*
  835.   *  Got a reply. So reset the "soft state" maintained for 
  836.   *  route requests in the request table. We don't really have
  837.   *  have a separate request table. It is just a part of the
  838.   *  routing table itself. 
  839.   */
  840.  // Note that rp_dst is the dest of the data packets, not the
  841.  // the dest of the reply, which is the src of the data packets.
  843.  rt = rtable.rt_lookup(rp->rp_dst);
  844.         
  845.  /*
  846.   *  If I don't have a rt entry to this host... adding
  847.   */
  848.  if(rt == 0) {
  849.    rt = rtable.rt_add(rp->rp_dst);
  850.  }
  852.  /*
  853.   * Add a forward route table entry... here I am following 
  854.   * Perkins-Royer AODV paper almost literally - SRD 5/99
  855.   */
  857.  if ( (rt->rt_seqno < rp->rp_dst_seqno) ||   // newer route 
  858.       ((rt->rt_seqno == rp->rp_dst_seqno) &&  
  859.        (rt->rt_hops > rp->rp_hop_count)) ) { // shorter or better route
  861.   // Update the rt entry 
  862.   rt_update(rt, rp->rp_dst_seqno, rp->rp_hop_count,
  863. rp->rp_src, CURRENT_TIME + rp->rp_lifetime);
  865.   // reset the soft state
  866.   rt->rt_req_cnt = 0;
  867.   rt->rt_req_timeout = 0.0; 
  868.   rt->rt_req_last_ttl = rp->rp_hop_count;
  869.   
  870. if (ih->daddr() == index) { // If I am the original source
  871.   // Update the route discovery latency statistics
  872.   // rp->rp_timestamp is the time of request origination
  874.     rt->rt_disc_latency[(unsigned char)rt->hist_indx] = (CURRENT_TIME - rp->rp_timestamp)
  875.                                          / (double) rp->rp_hop_count;
  876.     // increment indx for next time
  877.     rt->hist_indx = (rt->hist_indx + 1) % MAX_HISTORY;
  878.   }
  880.   /*
  881.    * Send all packets queued in the sendbuffer destined for
  882.    * this destination. 
  883.    * XXX - observe the "second" use of p.
  884.    */
  885.   Packet *buf_pkt;
  886.   while((buf_pkt = rqueue.deque(rt->rt_dst))) {
  887.     if(rt->rt_hops != INFINITY2) {
  888.           assert (rt->rt_flags == RTF_UP);
  889.     // Delay them a little to help ARP. Otherwise ARP 
  890.     // may drop packets. -SRD 5/23/99
  891.       forward(rt, buf_pkt, delay);
  892.       delay += ARP_DELAY;
  893.     }
  894.   }
  895.  }
  896.  else {
  897.   suppress_reply = 1;
  898.  }
  900.  /*
  901.   * If reply is for me, discard it.
  902.   */
  904. if(ih->daddr() == index || suppress_reply) {
  905.    Packet::free(p);
  906.  }
  907.  /*
  908.   * Otherwise, forward the Route Reply.
  909.   */
  910.  else {
  911.  // Find the rt entry
  912. aodv_rt_entry *rt0 = rtable.rt_lookup(ih->daddr());
  913.    // If the rt is up, forward
  914.    if(rt0 && (rt0->rt_hops != INFINITY2)) {
  915.         assert (rt0->rt_flags == RTF_UP);
  916.      rp->rp_hop_count += 1;
  917.      rp->rp_src = index;
  918.      forward(rt0, p, NO_DELAY);
  919.      // Insert the nexthop towards the RREQ source to 
  920.      // the precursor list of the RREQ destination
  921.      rt->pc_insert(rt0->rt_nexthop); // nexthop to RREQ source
  922.      
  923.    }
  924.    else {
  925.    // I don't know how to forward .. drop the reply. 
  926. #ifdef DEBUG
  927.      fprintf(stderr, "%s: dropping Route Replyn", __FUNCTION__);
  928. #endif // DEBUG
  929.      drop(p, DROP_RTR_NO_ROUTE);
  930.    }
  931.  }
  932. }
  935. void
  936. AODV::recvError(Packet *p) {
  937. struct hdr_ip *ih = HDR_IP(p);
  938. struct hdr_aodv_error *re = HDR_AODV_ERROR(p);
  939. aodv_rt_entry *rt;
  940. u_int8_t i;
  941. Packet *rerr = Packet::alloc();
  942. struct hdr_aodv_error *nre = HDR_AODV_ERROR(rerr);
  944.  nre->DestCount = 0;
  946.  for (i=0; i<re->DestCount; i++) {
  947.  // For each unreachable destination
  948.    rt = rtable.rt_lookup(re->unreachable_dst[i]);
  949.    if ( rt && (rt->rt_hops != INFINITY2) &&
  950. (rt->rt_nexthop == ih->saddr()) &&
  951.       (rt->rt_seqno <= re->unreachable_dst_seqno[i]) ) {
  952. assert(rt->rt_flags == RTF_UP);
  953. assert((rt->rt_seqno%2) == 0); // is the seqno even?
  954. #ifdef DEBUG
  955.      fprintf(stderr, "%s(%f): %dt(%dt%ut%d)t(%dt%ut%d)n", __FUNCTION__,CURRENT_TIME,
  956.      index, rt->rt_dst, rt->rt_seqno, rt->rt_nexthop,
  957.      re->unreachable_dst[i],re->unreachable_dst_seqno[i],
  958.              ih->saddr());
  959. #endif // DEBUG
  960.       rt->rt_seqno = re->unreachable_dst_seqno[i];
  961.       rt_down(rt);
  963.    // Not sure whether this is the right thing to do
  964.    Packet *pkt;
  965. while((pkt = ifqueue->filter(ih->saddr()))) {
  966.          drop(pkt, DROP_RTR_MAC_CALLBACK);
  967.       }
  969.      // if precursor list non-empty add to RERR and delete the precursor list
  970.       if (!rt->pc_empty()) {
  971.       nre->unreachable_dst[nre->DestCount] = rt->rt_dst;
  972.       nre->unreachable_dst_seqno[nre->DestCount] = rt->rt_seqno;
  973.       nre->DestCount += 1;
  974. rt->pc_delete();
  975.       }
  976.    }
  977.  } 
  979.  if (nre->DestCount > 0) {
  980. #ifdef DEBUG
  981.    fprintf(stderr, "%s(%f): %dt sending RERR...n", __FUNCTION__, CURRENT_TIME, index);
  982. #endif // DEBUG
  983.    sendError(rerr);
  984.  }
  985.  else {
  986.    Packet::free(rerr);
  987.  }
  989.  Packet::free(p);
  990. }
  993. /*
  994.    Packet Transmission Routines
  995. */
  997. void
  998. AODV::forward(aodv_rt_entry *rt, Packet *p, double delay) {
  999. struct hdr_cmn *ch = HDR_CMN(p);
  1000. struct hdr_ip *ih = HDR_IP(p);
  1002.  if(ih->ttl_ == 0) {
  1004. #ifdef DEBUG
  1005.   fprintf(stderr, "%s: calling drop()n", __PRETTY_FUNCTION__);
  1006. #endif // DEBUG
  1007.  
  1008.   drop(p, DROP_RTR_TTL);
  1009.   return;
  1010.  }
  1012.  if (ch->ptype() != PT_AODV && ch->direction() == hdr_cmn::UP &&
  1013. ((u_int32_t)ih->daddr() == IP_BROADCAST)
  1014. || (ih->daddr() == here_.addr_)) {
  1015. dmux_->recv(p,0);
  1016. return;
  1017.  }
  1019.  if (rt) {
  1020.    assert(rt->rt_flags == RTF_UP);
  1021.    rt->rt_expire = CURRENT_TIME + ACTIVE_ROUTE_TIMEOUT;
  1022.    ch->next_hop_ = rt->rt_nexthop;
  1023.    ch->addr_type() = NS_AF_INET;
  1024.    ch->direction() = hdr_cmn::DOWN;       //important: change the packet's direction
  1025.  }
  1026.  else { // if it is a broadcast packet
  1027.    // assert(ch->ptype() == PT_AODV); // maybe a diff pkt type like gaf
  1028.    assert(ih->daddr() == (nsaddr_t) IP_BROADCAST);
  1029.    ch->addr_type() = NS_AF_NONE;
  1030.    ch->direction() = hdr_cmn::DOWN;       //important: change the packet's direction
  1031.  }
  1033. if (ih->daddr() == (nsaddr_t) IP_BROADCAST) {
  1034.  // If it is a broadcast packet
  1035.    assert(rt == 0);
  1036.    if (ch->ptype() == PT_AODV) {
  1037.      /*
  1038.       *  Jitter the sending of AODV broadcast packets by 10ms
  1039.       */
  1040.      Scheduler::instance().schedule(target_, p,
  1041.           0.01 * Random::uniform());
  1042.    } else {
  1043.      Scheduler::instance().schedule(target_, p, 0.);  // No jitter
  1044.    }
  1045.  }
  1046.  else { // Not a broadcast packet 
  1047.    if(delay > 0.0) {
  1048.      Scheduler::instance().schedule(target_, p, delay);
  1049.    }
  1050.    else {
  1051.    // Not a broadcast packet, no delay, send immediately
  1052.      Scheduler::instance().schedule(target_, p, 0.);
  1053.    }
  1054.  }
  1056. }
  1059. void
  1060. AODV::sendRequest(nsaddr_t dst) {
  1061. // Allocate a RREQ packet 
  1062. Packet *p = Packet::alloc();
  1063. struct hdr_cmn *ch = HDR_CMN(p);
  1064. struct hdr_ip *ih = HDR_IP(p);
  1065. struct hdr_aodv_request *rq = HDR_AODV_REQUEST(p);
  1066. aodv_rt_entry *rt = rtable.rt_lookup(dst);
  1068.  assert(rt);
  1070.  /*
  1071.   *  Rate limit sending of Route Requests. We are very conservative
  1072.   *  about sending out route requests. 
  1073.   */
  1075.  if (rt->rt_flags == RTF_UP) {
  1076.    assert(rt->rt_hops != INFINITY2);
  1077.    Packet::free((Packet *)p);
  1078.    return;
  1079.  }
  1081.  if (rt->rt_req_timeout > CURRENT_TIME) {
  1082.    Packet::free((Packet *)p);
  1083.    return;
  1084.  }
  1086.  // rt_req_cnt is the no. of times we did network-wide broadcast
  1087.  // RREQ_RETRIES is the maximum number we will allow before 
  1088.  // going to a long timeout.
  1090.  if (rt->rt_req_cnt > RREQ_RETRIES) {
  1091.    rt->rt_req_timeout = CURRENT_TIME + MAX_RREQ_TIMEOUT;
  1092.    rt->rt_req_cnt = 0;
  1093.  Packet *buf_pkt;
  1094.    while ((buf_pkt = rqueue.deque(rt->rt_dst))) {
  1095.        drop(buf_pkt, DROP_RTR_NO_ROUTE);
  1096.    }
  1097.    Packet::free((Packet *)p);
  1098.    return;
  1099.  }
  1101. #ifdef DEBUG
  1102.    fprintf(stderr, "(%2d) - %2d sending Route Request, dst: %dn",
  1103.                     ++route_request, index, rt->rt_dst);
  1104. #endif // DEBUG
  1106.  // Determine the TTL to be used this time. 
  1107.  // Dynamic TTL evaluation - SRD
  1109.  rt->rt_req_last_ttl = max(rt->rt_req_last_ttl,rt->rt_last_hop_count);
  1111.  if (0 == rt->rt_req_last_ttl) {
  1112.  // first time query broadcast
  1113.    ih->ttl_ = TTL_START;
  1114.  }
  1115.  else {
  1116.  // Expanding ring search.
  1117.    if (rt->rt_req_last_ttl < TTL_THRESHOLD)
  1118.      ih->ttl_ = rt->rt_req_last_ttl + TTL_INCREMENT;
  1119.    else {
  1120.    // network-wide broadcast
  1121.      ih->ttl_ = NETWORK_DIAMETER;
  1122.      rt->rt_req_cnt += 1;
  1123.    }
  1124.  }
  1126.  // remember the TTL used  for the next time
  1127.  rt->rt_req_last_ttl = ih->ttl_;
  1129.  // PerHopTime is the roundtrip time per hop for route requests.
  1130.  // The factor 2.0 is just to be safe .. SRD 5/22/99
  1131.  // Also note that we are making timeouts to be larger if we have 
  1132.  // done network wide broadcast before. 
  1134.  rt->rt_req_timeout = 2.0 * (double) ih->ttl_ * PerHopTime(rt); 
  1135.  if (rt->rt_req_cnt > 0)
  1136.    rt->rt_req_timeout *= rt->rt_req_cnt;
  1137.  rt->rt_req_timeout += CURRENT_TIME;
  1139.  // Don't let the timeout to be too large, however .. SRD 6/8/99
  1140.  if (rt->rt_req_timeout > CURRENT_TIME + MAX_RREQ_TIMEOUT)
  1141.    rt->rt_req_timeout = CURRENT_TIME + MAX_RREQ_TIMEOUT;
  1142.  rt->rt_expire = 0;
  1144. #ifdef DEBUG
  1145.  fprintf(stderr, "(%2d) - %2d sending Route Request, dst: %d, tout %f msn",
  1146.          ++route_request, 
  1147.  index, rt->rt_dst, 
  1148.  rt->rt_req_timeout - CURRENT_TIME);
  1149. #endif // DEBUG
  1152.  // Fill out the RREQ packet 
  1153.  // ch->uid() = 0;
  1154.  ch->ptype() = PT_AODV;
  1155.  ch->size() = IP_HDR_LEN + rq->size();
  1156.  ch->iface() = -2;
  1157.  ch->error() = 0;
  1158.  ch->addr_type() = NS_AF_NONE;
  1159.  ch->prev_hop_ = index;          // AODV hack
  1161.  ih->saddr() = index;
  1162.  ih->daddr() = IP_BROADCAST;
  1163.  ih->sport() = RT_PORT;
  1164.  ih->dport() = RT_PORT;
  1166.  // Fill up some more fields. 
  1167.  rq->rq_type = AODVTYPE_RREQ;
  1168.  rq->rq_hop_count = 1;
  1169.  rq->rq_bcast_id = bid++;
  1170.  rq->rq_dst = dst;
  1171.  rq->rq_dst_seqno = (rt ? rt->rt_seqno : 0);
  1172.  rq->rq_src = index;
  1173.  seqno += 2;
  1174.  assert ((seqno%2) == 0);
  1175.  rq->rq_src_seqno = seqno;
  1176.  rq->rq_timestamp = CURRENT_TIME;
  1178.  Scheduler::instance().schedule(target_, p, 0.);
  1180. }
  1182. void
  1183. AODV::sendReply(nsaddr_t ipdst, u_int32_t hop_count, nsaddr_t rpdst,
  1184.                 u_int32_t rpseq, u_int32_t lifetime, double timestamp) {
  1185. Packet *p = Packet::alloc();
  1186. struct hdr_cmn *ch = HDR_CMN(p);
  1187. struct hdr_ip *ih = HDR_IP(p);
  1188. struct hdr_aodv_reply *rp = HDR_AODV_REPLY(p);
  1189. aodv_rt_entry *rt = rtable.rt_lookup(ipdst);
  1191. #ifdef DEBUG
  1192. fprintf(stderr, "sending Reply from %d at %.2fn", index, Scheduler::instance().clock());
  1193. #endif // DEBUG
  1194.  assert(rt);
  1196.  rp->rp_type = AODVTYPE_RREP;
  1197.  //rp->rp_flags = 0x00;
  1198.  rp->rp_hop_count = hop_count;
  1199.  rp->rp_dst = rpdst;
  1200.  rp->rp_dst_seqno = rpseq;
  1201.  rp->rp_src = index;
  1202.  rp->rp_lifetime = lifetime;
  1203.  rp->rp_timestamp = timestamp;
  1204.    
  1205.  // ch->uid() = 0;
  1206.  ch->ptype() = PT_AODV;
  1207.  ch->size() = IP_HDR_LEN + rp->size();
  1208.  ch->iface() = -2;
  1209.  ch->error() = 0;
  1210.  ch->addr_type() = NS_AF_INET;
  1211.  ch->next_hop_ = rt->rt_nexthop;
  1212.  ch->prev_hop_ = index;          // AODV hack
  1213.  ch->direction() = hdr_cmn::DOWN;
  1215.  ih->saddr() = index;
  1216.  ih->daddr() = ipdst;
  1217.  ih->sport() = RT_PORT;
  1218.  ih->dport() = RT_PORT;
  1219.  ih->ttl_ = NETWORK_DIAMETER;
  1221.  Scheduler::instance().schedule(target_, p, 0.);
  1223. }
  1225. void
  1226. AODV::sendError(Packet *p, bool jitter) {
  1227. struct hdr_cmn *ch = HDR_CMN(p);
  1228. struct hdr_ip *ih = HDR_IP(p);
  1229. struct hdr_aodv_error *re = HDR_AODV_ERROR(p);
  1230.     
  1231. #ifdef ERROR
  1232. fprintf(stderr, "sending Error from %d at %.2fn", index, Scheduler::instance().clock());
  1233. #endif // DEBUG
  1235.  re->re_type = AODVTYPE_RERR;
  1236.  //re->reserved[0] = 0x00; re->reserved[1] = 0x00;
  1237.  // DestCount and list of unreachable destinations are already filled
  1239.  // ch->uid() = 0;
  1240.  ch->ptype() = PT_AODV;
  1241.  ch->size() = IP_HDR_LEN + re->size();
  1242.  ch->iface() = -2;
  1243.  ch->error() = 0;
  1244.  ch->addr_type() = NS_AF_NONE;
  1245.  ch->next_hop_ = 0;
  1246.  ch->prev_hop_ = index;          // AODV hack
  1247.  ch->direction() = hdr_cmn::DOWN;       //important: change the packet's direction
  1249.  ih->saddr() = index;
  1250.  ih->daddr() = IP_BROADCAST;
  1251.  ih->sport() = RT_PORT;
  1252.  ih->dport() = RT_PORT;
  1253.  ih->ttl_ = 1;
  1255.  // Do we need any jitter? Yes
  1256.  if (jitter)
  1257.   Scheduler::instance().schedule(target_, p, 0.01*Random::uniform());
  1258.  else
  1259.   Scheduler::instance().schedule(target_, p, 0.0);
  1261. }
  1264. /*
  1265.    Neighbor Management Functions
  1266. */
  1268. void
  1269. AODV::sendHello() {
  1270. Packet *p = Packet::alloc();
  1271. struct hdr_cmn *ch = HDR_CMN(p);
  1272. struct hdr_ip *ih = HDR_IP(p);
  1273. struct hdr_aodv_reply *rh = HDR_AODV_REPLY(p);
  1275. #ifdef DEBUG
  1276. fprintf(stderr, "sending Hello from %d at %.2fn", index, Scheduler::instance().clock());
  1277. #endif // DEBUG
  1279.  rh->rp_type = AODVTYPE_HELLO;
  1280.  //rh->rp_flags = 0x00;
  1281.  rh->rp_hop_count = 1;
  1282.  rh->rp_dst = index;
  1283.  rh->rp_dst_seqno = seqno;
  1284.  rh->rp_lifetime = (1 + ALLOWED_HELLO_LOSS) * HELLO_INTERVAL;
  1286.  // ch->uid() = 0;
  1287.  ch->ptype() = PT_AODV;
  1288.  ch->size() = IP_HDR_LEN + rh->size();
  1289.  ch->iface() = -2;
  1290.  ch->error() = 0;
  1291.  ch->addr_type() = NS_AF_NONE;
  1292.  ch->prev_hop_ = index;          // AODV hack
  1294.  ih->saddr() = index;
  1295.  ih->daddr() = IP_BROADCAST;
  1296.  ih->sport() = RT_PORT;
  1297.  ih->dport() = RT_PORT;
  1298.  ih->ttl_ = 1;
  1300.  Scheduler::instance().schedule(target_, p, 0.0);
  1301. }
  1304. void
  1305. AODV::recvHello(Packet *p) {
  1306. //struct hdr_ip *ih = HDR_IP(p);
  1307. struct hdr_aodv_reply *rp = HDR_AODV_REPLY(p);
  1308. AODV_Neighbor *nb;
  1310.  nb = nb_lookup(rp->rp_dst);
  1311.  if(nb == 0) {
  1312.    nb_insert(rp->rp_dst);
  1313.  }
  1314.  else {
  1315.    nb->nb_expire = CURRENT_TIME +
  1316.                    (1.5 * ALLOWED_HELLO_LOSS * HELLO_INTERVAL);
  1317.  }
  1319.  Packet::free(p);
  1320. }
  1322. void
  1323. AODV::nb_insert(nsaddr_t id) {
  1324. AODV_Neighbor *nb = new AODV_Neighbor(id);
  1326.  assert(nb);
  1327.  nb->nb_expire = CURRENT_TIME +
  1328.                 (1.5 * ALLOWED_HELLO_LOSS * HELLO_INTERVAL);
  1329.  LIST_INSERT_HEAD(&nbhead, nb, nb_link);
  1330.  seqno += 2;             // set of neighbors changed
  1331.  assert ((seqno%2) == 0);
  1332. }
  1335. AODV_Neighbor*
  1336. AODV::nb_lookup(nsaddr_t id) {
  1337. AODV_Neighbor *nb = nbhead.lh_first;
  1339.  for(; nb; nb = nb->nb_link.le_next) {
  1340.    if(nb->nb_addr == id) break;
  1341.  }
  1342.  return nb;
  1343. }
  1346. /*
  1347.  * Called when we receive *explicit* notification that a Neighbor
  1348.  * is no longer reachable.
  1349.  */
  1350. void
  1351. AODV::nb_delete(nsaddr_t id) {
  1352. AODV_Neighbor *nb = nbhead.lh_first;
  1354.  log_link_del(id);
  1355.  seqno += 2;     // Set of neighbors changed
  1356.  assert ((seqno%2) == 0);
  1358.  for(; nb; nb = nb->nb_link.le_next) {
  1359.    if(nb->nb_addr == id) {
  1360.      LIST_REMOVE(nb,nb_link);
  1361.      delete nb;
  1362.      break;
  1363.    }
  1364.  }
  1366.  handle_link_failure(id);
  1368. }
  1371. /*
  1372.  * Purges all timed-out Neighbor Entries - runs every
  1373.  * HELLO_INTERVAL * 1.5 seconds.
  1374.  */
  1375. void
  1376. AODV::nb_purge() {
  1377. AODV_Neighbor *nb = nbhead.lh_first;
  1378. AODV_Neighbor *nbn;
  1379. double now = CURRENT_TIME;
  1381.  for(; nb; nb = nbn) {
  1382.    nbn = nb->nb_link.le_next;
  1383.    if(nb->nb_expire <= now) {
  1384.      nb_delete(nb->nb_addr);
  1385.    }
  1386.  }
  1388. }