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

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

通讯编程

开发平台：

Visual C++

dsdv.cc：源码内容
  1. /* -*- Mode:C++; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */
  2. /*
  3.  * Copyright (c) 1997 Regents of the University of California.
  4.  * All rights reserved.
  5.  *
  6.  * Redistribution and use in source and binary forms, with or without
  7.  * modification, are permitted provided that the following conditions
  8.  * are met:
  9.  * 1. Redistributions of source code must retain the above copyright
  10.  *    notice, this list of conditions and the following disclaimer.
  11.  * 2. Redistributions in binary form must reproduce the above copyright
  12.  *    notice, this list of conditions and the following disclaimer in the
  13.  *    documentation and/or other materials provided with the distribution.
  14.  * 3. All advertising materials mentioning features or use of this software
  15.  *    must display the following acknowledgement:
  16.  * This product includes software developed by the Computer Systems
  17.  * Engineering Group at Lawrence Berkeley Laboratory.
  18.  * 4. Neither the name of the University nor of the Laboratory may be used
  19.  *    to endorse or promote products derived from this software without
  20.  *    specific prior written permission.
  21.  *
  22.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  23.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  24.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  25.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  26.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  27.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  28.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  29.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  31.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32.  * SUCH DAMAGE.
  33.  *
  34.  * Ported from CMU/Monarch's code, nov'98 -Padma.
  35.  *
  36.  * $Header: /cvsroot/nsnam/ns-2/dsdv/dsdv.cc,v 1.26 2006/02/21 15:20:18 mahrenho Exp $
  37.  */
  39. extern "C" {
  40. #include <stdarg.h>
  41. #include <float.h>
  42. }
  44. #include "dsdv.h"
  45. #include "priqueue.h"
  47. #include <random.h>
  49. #include <cmu-trace.h>
  50. #include <address.h>
  51. #include <mobilenode.h>
  54. #define DSDV_STARTUP_JITTER 2.0 // secs to jitter start of periodic activity from
  55. // when start-dsr msg sent to agent
  56. #define DSDV_ALMOST_NOW     0.1 // jitter used for events that should be effectively
  57. // instantaneous but are jittered to prevent
  58. // synchronization
  59. #define DSDV_BROADCAST_JITTER 0.01 // jitter for all broadcast packets
  60. #define DSDV_MIN_TUP_PERIOD 1.0 // minimum time between triggered updates
  61. #define IP_DEF_TTL   32 // default TTTL
  63. #undef TRIGGER_UPDATE_ON_FRESH_SEQNUM
  64. //#define TRIGGER_UPDATE_ON_FRESH_SEQNUM
  65. /* should the receipt of a fresh (newer) sequence number cause us
  66.    to send a triggered update?  If undef'd, we'll only trigger on
  67.    routing metric changes */
  69. // Returns a random number between 0 and max
  70. static inline double 
  71. jitter (double max, int be_random_)
  72. {
  73.   return (be_random_ ? Random::uniform(max) : 0);
  74. }
  76. void DSDV_Agent::
  77. trace (char *fmt,...)
  78. {
  79.   va_list ap;
  81.   if (!tracetarget)
  82.     return;
  84.   va_start (ap, fmt);
  85.   vsprintf (tracetarget->pt_->buffer (), fmt, ap);
  86.   tracetarget->pt_->dump ();
  87.   va_end (ap);
  88. }
  90. void 
  91. DSDV_Agent::tracepkt (Packet * p, double now, int me, const char *type)
  92. {
  93.   char buf[1024];
  95.   unsigned char *walk = p->accessdata ();
  97.   int ct = *(walk++);
  98.   int seq, dst, met;
  100.   snprintf (buf, 1024, "V%s %.5f _%d_ [%d]:", type, now, me, ct);
  101.   while (ct--)
  102.     {
  103.       dst = *(walk++);
  104.       dst = dst << 8 | *(walk++);
  105.       dst = dst << 8 | *(walk++);
  106.       dst = dst << 8 | *(walk++);
  107.       met = *(walk++);
  108.       seq = *(walk++);
  109.       seq = seq << 8 | *(walk++);
  110.       seq = seq << 8 | *(walk++);
  111.       seq = seq << 8 | *(walk++);
  112.       snprintf (buf, 1024, "%s (%d,%d,%d)", buf, dst, met, seq);
  113.     }
  114.   // Now do trigger handling.
  115.   //trace("VTU %.5f %d", now, me);
  116.   if (verbose_)
  117.     trace ("%s", buf);
  118. }
  120. // Prints out an rtable element.
  121. void
  122. DSDV_Agent::output_rte(const char *prefix, rtable_ent * prte, DSDV_Agent * a)
  123. {
  124.   a->trace("DFU: deimplemented");
  125.   printf("DFU: deimplemented");
  127.   prte = 0;
  128.   prefix = 0;
  129. #if 0
  130.   printf ("%s%d %d %d %d %f %f %f %f 0x%08xn",
  131.   prefix, prte->dst, prte->hop, prte->metric, prte->seqnum,
  132.   prte->udtime, prte->new_seqnum_at, prte->wst, prte->changed_at,
  133.   (unsigned int) prte->timeout_event);
  134.   a->trace ("VTE %.5f %d %d %d %d %f %f %f %f 0x%08x",
  135.           Scheduler::instance ().clock (), prte->dst, prte->hop, prte->metric,
  136.   prte->seqnum, prte->udtime, prte->new_seqnum_at, prte->wst, prte->changed_at,
  137.     prte->timeout_event);
  138. #endif
  139. }
  141. class DSDVTriggerHandler : public Handler {
  142.   public:
  143.     DSDVTriggerHandler(DSDV_Agent *a_) { a = a_; }
  144.     virtual void handle(Event *e);
  145.   private:
  146.     DSDV_Agent *a;
  147. };
  150. void
  151. DSDVTriggerHandler::handle(Event *e)
  152.  // send a triggered update (or a full update if one's needed)
  153. {
  154. //DEBUG
  155. //printf("(%d)-->triggered update with e=%xn", a->myaddr_,e); 
  157.   Scheduler & s = Scheduler::instance ();
  158.   Time now = s.clock ();
  159.   rtable_ent *prte;
  160.   int update_type;  // we want periodic (=1) or triggered (=0) update?
  161.   Time next_possible = a->lasttup_ + DSDV_MIN_TUP_PERIOD;
  163.   for (a->table_->InitLoop(); (prte = a->table_->NextLoop());)
  164.   if (prte->trigger_event == e) break;
  166.   assert(prte && prte->trigger_event == e);
  168.   if (now < next_possible)
  169.     {
  170.     //DEBUG
  171.     //printf("(%d)..Re-scheduling triggered updaten",a->myaddr_);
  172.       s.schedule(a->trigger_handler, e, next_possible - now);
  173.       a->cancelTriggersBefore(next_possible);
  174.       return;
  175.     }
  177.   update_type = 0;
  178.   Packet * p = a->makeUpdate(/*in-out*/update_type);
  179.       
  180.   if (p != NULL) 
  181.     {   
  182.       if (update_type == 1)
  183. { // we got a periodic update, though we only asked for triggered
  184.   // cancel and reschedule periodic update
  185.   s.cancel(a->periodic_callback_);
  186.   //DEBUG
  187.   //printf("we got a periodic update, though asked for triggn");
  188.   s.schedule (a->helper_, a->periodic_callback_, 
  189.       a->perup_ * (0.75 + jitter (0.25, a->be_random_)));
  190.   if (a->verbose_) a->tracepkt (p, now, a->myaddr_, "PU");   
  191. }
  192.       else
  193. {
  194.   if (a->verbose_) a->tracepkt (p, now, a->myaddr_, "TU");   
  195. }
  196.       assert (!HDR_CMN (p)->xmit_failure_); // DEBUG 0x2   
  197.       s.schedule (a->target_, p, jitter(DSDV_BROADCAST_JITTER, a->be_random_));
  198.       
  199.       a->lasttup_ = now; // even if we got a full update, it still counts
  200.       // for our last triggered update time
  201.     }
  202.   
  203.   // free this event
  204.   for (a->table_->InitLoop (); (prte = a->table_->NextLoop ());)
  205.     if (prte->trigger_event && prte->trigger_event == e)
  206.       {
  207. prte->trigger_event = 0;
  208. delete e;
  209.       }
  210. }
  212. void
  213. DSDV_Agent::cancelTriggersBefore(Time t)
  214.   // Cancel any triggered events scheduled to take place *before* time
  215.   // t (exclusive)
  216. {
  217.   rtable_ent *prte;
  218.   Scheduler & s = Scheduler::instance ();
  220.   for (table_->InitLoop (); (prte = table_->NextLoop ());)
  221.     if (prte->trigger_event && prte->trigger_event->time_ < t)
  222.       {
  223.       //DEBUG
  224.       //printf("(%d) cancel event %xn",myaddr_,prte->trigger_event);
  225. s.cancel(prte->trigger_event);
  226. delete prte->trigger_event;
  227. prte->trigger_event = 0;
  228.       }
  229. }
  231. void
  232. DSDV_Agent::needTriggeredUpdate(rtable_ent *prte, Time t)
  233.   // if no triggered update already pending, make one so
  234. {
  235.   Scheduler & s = Scheduler::instance();
  236.   Time now = Scheduler::instance().clock();
  238.   assert(t >= now);
  240.   if (prte->trigger_event) 
  241.     s.cancel(prte->trigger_event);
  242.   else
  243.     prte->trigger_event = new Event;
  244.   //DEBUG
  245.   //printf("(%d)..scheduling trigger-update with event %xn",myaddr_,prte->trigger_event);
  246.   s.schedule(trigger_handler, prte->trigger_event, t - now);
  247. }
  249. void
  250. DSDV_Agent::helper_callback (Event * e)
  251. {
  252.   Scheduler & s = Scheduler::instance ();
  253.   double now = s.clock ();
  254.   rtable_ent *prte;
  255.   rtable_ent *pr2;
  256.   int update_type;  // we want periodic (=1) or triggered (=0) update?
  257.   //DEBUG
  258.   //printf("Triggered handler on 0x%08xn", e);
  260.   // Check for periodic callback
  261.   if (periodic_callback_ && e == periodic_callback_)
  262.     {
  263.       update_type = 1;
  264.       Packet *p = makeUpdate(/*in-out*/update_type);
  265.       if (verbose_)
  266. {
  267.   trace ("VPC %.5f _%d_", now, myaddr_);
  268.   tracepkt (p, now, myaddr_, "PU");
  269. }
  271.       
  272.       if (p) {
  273.       assert (!HDR_CMN (p)->xmit_failure_); // DEBUG 0x2
  274.       // send out update packet jitter to avoid sync
  275.       //DEBUG
  276.       //printf("(%d)..sendout update pkt (periodic=%d)n",myaddr_,update_type);
  277.       s.schedule (target_, p, jitter(DSDV_BROADCAST_JITTER, be_random_));
  278.       }
  279.       
  280.       // put the periodic update sending callback back onto the 
  281.       // the scheduler queue for next time....
  282.       s.schedule (helper_, periodic_callback_, 
  283.   perup_ * (0.75 + jitter (0.25, be_random_)));
  285.       // this will take the place of any planned triggered updates
  286.       lasttup_ = now;
  287.       return;
  288.     }
  290.   // Check for timeout
  291.   // If it was a timeout, fix the routing table.
  292.   for (table_->InitLoop (); (prte = table_->NextLoop ());)
  293.     if (prte->timeout_event && (prte->timeout_event == e))
  294.       break;
  296.   // If it was a timeout, prte will be non-NULL
  297.   // Note that in the if we don't touch the changed_at time, so that when
  298.   // wst is computed, it doesn't consider the infinte metric the best
  299.   // one at that sequence number.
  300.   if (prte)
  301.   {
  302.       if (verbose_)
  303. {
  304.   trace ("VTO %.5f _%d_ %d->%d", now, myaddr_, myaddr_, prte->dst);
  305.   /*   trace ("VTO %.5f _%d_ trg_sch %x on sched %x time %f", now, myaddr_, 
  306.  trigupd_scheduled, 
  307.  trigupd_scheduled ? s.lookup(trigupd_scheduled->uid_) : 0,
  308.  trigupd_scheduled ? trigupd_scheduled->time_ : 0); */
  309. }
  310.       
  311.       for (table_->InitLoop (); (pr2 = table_->NextLoop ()); )
  312. {
  313.   if (pr2->hop == prte->dst && pr2->metric != BIG)
  314.     {
  315.       if (verbose_)
  316. trace ("VTO %.5f _%d_ marking %d", now, myaddr_, pr2->dst);
  317.       pr2->metric = BIG;
  318.       pr2->advertise_ok_at = now;
  319.       pr2->advert_metric = true;
  320.       pr2->advert_seqnum = true;
  321.       pr2->seqnum++;
  322.       // And we have routing info to propogate.
  323.       //DEBUG
  324.       //printf("(%d)..we have routing info to propagate..trigger update for dst %dn",myaddr_,pr2->dst);
  325.       needTriggeredUpdate(pr2, now);
  326.     }
  327. }
  329.       // OK the timeout expired, so we'll free it. No dangling pointers.
  330.       prte->timeout_event = 0;    
  331.     }
  332.   else 
  333.     { // unknown event on  queue
  334.       fprintf(stderr,"DFU: unknown queue eventn");
  335.      abort();
  336.     }
  338.   if (e)
  339.     delete e;
  340. }
  342. void
  343. DSDV_Agent::lost_link (Packet *p)
  344. {
  345.   hdr_cmn *hdrc = HDR_CMN (p);
  346.   rtable_ent *prte = table_->GetEntry (hdrc->next_hop_);
  348.   if(use_mac_ == 0) {
  349.           drop(p, DROP_RTR_MAC_CALLBACK);
  350.           return;
  351.   }
  353.   //DEBUG
  354.   //printf("(%d)..Lost link..n",myaddr_);
  355.   if (verbose_ && hdrc->addr_type_ == NS_AF_INET)
  356.     trace("VLL %.8f %d->%d lost at %d",
  357.     Scheduler::instance().clock(),
  358.    hdr_ip::access(p)->saddr(), hdr_ip::access(p)->daddr(),
  359.    myaddr_);
  361.   if (!use_mac_ || !prte || hdrc->addr_type_ != NS_AF_INET)
  362.     return;
  364.   if (verbose_)
  365.     trace ("VLP %.5f %d:%d->%d:%d lost at %d [hop %d]",
  366.   Scheduler::instance ().clock (),
  367.    hdr_ip::access (p)->saddr(),
  368.    hdr_ip::access (p)->sport(),
  369.    hdr_ip::access (p)->daddr(),
  370.    hdr_ip::access (p)->dport(),
  371.    myaddr_, prte->dst);
  373.   if (prte->timeout_event)
  374.     {
  375.       Scheduler::instance ().cancel (prte->timeout_event);
  376.       helper_callback (prte->timeout_event);
  377.     }
  378.   else if (prte->metric != BIG)
  379.     {
  380.       assert(prte->timeout_event == 0);
  381.       prte->timeout_event = new Event ();
  382.       helper_callback (prte->timeout_event);
  383.     }
  385.   // Queue these packets up...
  386.   recv(p, 0);
  388. #if 0
  389.   while (p2 = ((PriQueue *) target_)->filter (prte->dst))
  390.     {
  391.       if (verbose_)
  392.       trace ("VRS %.5f %d:%d->%d:%d lost at %d", Scheduler::instance ().clock (),
  393.        hdr_ip::access (p2)->saddr(),
  394.        hdr_ip::access (p2)->sport(),
  395.        hdr_ip::access (p2)->daddr(),
  396.        hdr_ip::access (p2)->dport(), myaddr_);
  398.       recv(p2, 0);
  399.     }
  401.   while (p2 = ll_queue->filter (prte->dst))
  402.     {
  403.       if (verbose_)
  404.       trace ("VRS %.5f %d:%d->%d:%d lost at %d", Scheduler::instance ().clock (),
  405.        hdr_ip::access (p2)->saddr(),
  406.        hdr_ip::access (p2)->sport(),
  407.        hdr_ip::access (p2)->daddr(),
  408.        hdr_ip::access (p2)->dport(), myaddr_);
  410.       recv (p2, 0);
  411.     }
  412. #endif
  413. }
  415. static void 
  416. mac_callback (Packet * p, void *arg)
  417. {
  418.   ((DSDV_Agent *) arg)->lost_link (p);
  419. }
  421. Packet *
  422. DSDV_Agent::makeUpdate(int& periodic)
  423.     // return a packet advertising the state in the routing table
  424.     // makes a full ``periodic'' update if requested, or a ``triggered''
  425.     // partial update if there are only a few changes and full update otherwise
  426.     // returns with periodic = 1 if full update returned, or = 0 if partial
  427.   //   update returned
  429. {
  430. //DEBUG
  431. //printf("(%d)-->Making update pktn",myaddr_);
  433.   Packet *p = allocpkt ();
  434.   hdr_ip *iph = hdr_ip::access(p);
  435.   hdr_cmn *hdrc = HDR_CMN (p);
  436.   double now = Scheduler::instance ().clock ();
  437.   rtable_ent *prte;
  438.   unsigned char *walk;
  440.   int change_count;             // count of entries to go in this update
  441.   int rtbl_sz; // counts total entries in rt table
  442.   int unadvertiseable; // number of routes we can't advertise yet
  444.   //printf("Update packet from %d [per=%d]n", myaddr_, periodic);
  446.   // The packet we send wants to be broadcast
  447.   hdrc->next_hop_ = IP_BROADCAST;
  448.   hdrc->addr_type_ = NS_AF_INET;
  449.   iph->daddr() = IP_BROADCAST << Address::instance().nodeshift();
  450.   iph->dport() = ROUTER_PORT;
  452.   change_count = 0;
  453.   rtbl_sz = 0;
  454.   unadvertiseable = 0;
  455.   for (table_->InitLoop (); 
  456.        (prte = table_->NextLoop ()); )
  457.     {
  458.       rtbl_sz++;
  459.       if ((prte->advert_seqnum || prte->advert_metric) 
  460.   && prte->advertise_ok_at <= now) 
  461. change_count++;
  463.       if (prte->advertise_ok_at > now) unadvertiseable++;
  464.     }
  465.   //printf("change_count = %dn",change_count);
  466.   if (change_count * 3 > rtbl_sz && change_count > 3)
  467.     { // much of the table has changed, just do a periodic update now
  468.       periodic = 1;
  469.     }
  471.   // Periodic update... increment the sequence number...
  472.   if (periodic)
  473.     {
  474.       change_count = rtbl_sz - unadvertiseable;
  475.       //printf("rtbsize-%d, unadvert-%dn",rtbl_sz,unadvertiseable);
  476.       rtable_ent rte;
  477.       bzero(&rte, sizeof(rte));
  479.       /* inc sequence number on any periodic update, even if we started
  480.  off wanting to do a triggered update, b/c we're doing a real
  481.  live periodic update now that'll take the place of our next
  482.  periodic update */
  483.       seqno_ += 2;
  485.       rte.dst = myaddr_;
  486.       //rte.hop = iph->src();
  487.       rte.hop = Address::instance().get_nodeaddr(iph->saddr());
  488.       rte.metric = 0;
  489.       rte.seqnum = seqno_;
  491.       rte.advertise_ok_at = 0.0; // can always advert ourselves
  492.       rte.advert_seqnum = true;  // always include ourselves in Triggered Upds
  493.       rte.changed_at = now;
  494.       rte.new_seqnum_at = now;
  495.       rte.wst = 0;
  496.       rte.timeout_event = 0; // Don't time out our localhost :)
  498.       rte.q = 0; // Don't buffer pkts for self!
  500.       table_->AddEntry (rte);
  501.     }
  503.   if (change_count == 0) 
  504.     {
  505.       Packet::free(p); // allocated by us, no drop needed
  507.       return NULL; // nothing to advertise
  508.     }
  510.   /* ****** make the update packet.... ***********
  511.      with less than 100+ nodes, an update for all nodes is less than the
  512.      MTU, so don't bother worrying about splitting the update over
  513.      multiple packets -dam 4/26/98 */
  514.   //assert(rtbl_sz <= (1500 / 12)); ---how about 100++ node topologies
  516.   p->allocdata((change_count * 9) + 1);
  517.   walk = p->accessdata ();
  518.   *(walk++) = change_count;
  520.   // hdrc->size_ = change_count * 12 + 20; // DSDV + IP
  521.   hdrc->size_ = change_count * 12 + IP_HDR_LEN; // DSDV + IP
  523.   for (table_->InitLoop (); (prte = table_->NextLoop ());)
  524.     {
  526.       if (periodic && prte->advertise_ok_at > now)
  527. { // don't send out routes that shouldn't be advertised
  528.   // even in periodic updates
  529.   continue;
  530. }
  532.       if (periodic || 
  533.   ((prte->advert_seqnum || prte->advert_metric) 
  534.    && prte->advertise_ok_at <= now))
  535. { // include this rte in the advert
  536.   if (!periodic && verbose_)
  537.     trace ("VCT %.5f _%d_ %d", now, myaddr_, prte->dst);
  539.   //assert (prte->dst < 256 && prte->metric < 256);
  540.   //*(walk++) = prte->dst;
  541.   *(walk++) = prte->dst >> 24;
  542.     *(walk++) = (prte->dst >> 16) & 0xFF;
  543.     *(walk++) = (prte->dst >> 8) & 0xFF;
  544.     *(walk++) = (prte->dst >> 0) & 0xFF;
  545.   *(walk++) = prte->metric;
  546.   *(walk++) = (prte->seqnum) >> 24;
  547.   *(walk++) = ((prte->seqnum) >> 16) & 0xFF;
  548.   *(walk++) = ((prte->seqnum) >> 8) & 0xFF;
  549.   *(walk++) = (prte->seqnum) & 0xFF;
  551.   prte->last_advertised_metric = prte->metric;
  553.   // seqnum's only need to be advertised once after they change
  554.   prte->advert_seqnum = false; // don't need to advert seqnum again
  556.   if (periodic) 
  557.     { // a full advert means we don't have to re-advert either 
  558.       // metrics or seqnums again until they change
  559.       prte->advert_seqnum = false;
  560.       prte->advert_metric = false;
  561.     }
  562.   change_count--;
  563. }
  564.     }  
  565.   assert(change_count == 0);
  566.   return p;
  567. }
  569. void
  570. DSDV_Agent::updateRoute(rtable_ent *old_rte, rtable_ent *new_rte)
  571. {
  572.   int negvalue = -1;
  573.   assert(new_rte);
  575.   Time now = Scheduler::instance().clock();
  577.   char buf[1024];
  578.   //  snprintf (buf, 1024, "%c %.5f _%d_ (%d,%d->%d,%d->%d,%d->%d,%lf)",
  579.   snprintf (buf, 1024, "%c %.5f _%d_ (%d,%d->%d,%d->%d,%d->%d,%f)",
  580.     (new_rte->metric != BIG 
  581.      && (!old_rte || old_rte->metric != BIG)) ? 'D' : 'U', 
  582.     now, myaddr_, new_rte->dst, 
  583.     old_rte ? old_rte->metric : negvalue, new_rte->metric, 
  584.     old_rte ? old_rte->seqnum : negvalue,  new_rte->seqnum,
  585.     old_rte ? old_rte->hop : -1,  new_rte->hop, 
  586.     new_rte->advertise_ok_at);
  588.   table_->AddEntry (*new_rte);
  589.   //printf("(%d),Route table updated..n",myaddr_);
  590.   if (trace_wst_)
  591.     trace ("VWST %.12lf frm %d to %d wst %.12lf nxthp %d [of %d]",
  592.    now, myaddr_, new_rte->dst, new_rte->wst, new_rte->hop, 
  593.    new_rte->metric);
  594.   if (verbose_)
  595.     trace ("VS%s", buf);
  596. }
  598. void
  599. DSDV_Agent::processUpdate (Packet * p)
  600. {
  601.   hdr_ip *iph = HDR_IP(p);
  602.   Scheduler & s = Scheduler::instance ();
  603.   double now = s.clock ();
  604.   
  605.   // it's a dsdv packet
  606.   int i;
  607.   unsigned char *d = p->accessdata ();
  608.   unsigned char *w = d + 1;
  609.   rtable_ent rte; // new rte learned from update being processed
  610.   rtable_ent *prte; // ptr to entry *in* routing tbl
  612.   //DEBUG
  613.   //int src, dst;
  614.   //src = Address::instance().get_nodeaddr(iph->src());
  615.   //dst = Address::instance().get_nodeaddr(iph->dst());
  616.   //printf("Received DSDV packet from %d(%d) to %d(%d) [%d)]n", src, iph->sport(), dst, iph->dport(), myaddr_);
  618.   for (i = *d; i > 0; i--)
  619.     {
  620.       bool trigger_update = false;  // do we need to do a triggered update?
  621.       nsaddr_t dst;
  622.       prte = NULL;
  624.       dst = *(w++);
  625.       dst = dst << 8 | *(w++);
  626.       dst = dst << 8 | *(w++);
  627.       dst = dst << 8 | *(w++);
  629.       if ((prte = table_->GetEntry (dst)))
  630. {
  631.   bcopy(prte, &rte, sizeof(rte));
  632. }
  633.       else
  634. {
  635.   bzero(&rte, sizeof(rte));
  636. }
  638.       rte.dst = dst;
  639.       //rte.hop = iph->src();
  640.       rte.hop = Address::instance().get_nodeaddr(iph->saddr());
  641.       rte.metric = *(w++);
  642.       rte.seqnum = *(w++);
  643.       rte.seqnum = rte.seqnum << 8 | *(w++);
  644.       rte.seqnum = rte.seqnum << 8 | *(w++);
  645.       rte.seqnum = rte.seqnum << 8 | *(w++);
  646.       rte.changed_at = now;
  647.       if (rte.metric != BIG) rte.metric += 1;
  649.       if (rte.dst == myaddr_)
  650. {
  651.   if (rte.metric == BIG && periodic_callback_)
  652.     {
  653.       // You have the last word on yourself...
  654.       // Tell the world right now that I'm still here....
  655.       // This is a CMU Monarch optimiziation to fix the 
  656.       // the problem of other nodes telling you and your neighbors
  657.       // that you don't exist described in the paper.
  658.       s.cancel (periodic_callback_);
  659.       s.schedule (helper_, periodic_callback_, 0);
  660.     }
  661.   continue; // don't corrupt your own routing table.
  663. }
  665.       /**********  fill in meta data for new route ***********/
  666.       // If it's in the table, make it the same timeout and queue.
  667.       if (prte)
  668. { // we already have a route to this dst
  669.   if (prte->seqnum == rte.seqnum)
  670.     { // we've got an update with out a new squenece number
  671.       // this update must have come along a different path
  672.       // than the previous one, and is just the kind of thing
  673.       // the weighted settling time is supposed to track.
  675.       // this code is now a no-op left here for clarity -dam XXX
  676.       rte.wst = prte->wst;
  677.       rte.new_seqnum_at = prte->new_seqnum_at;
  678.     }
  679.   else 
  680.     { // we've got a new seq number, end the measurement period
  681.       // for wst over the course of the old sequence number
  682.       // and update wst with the difference between the last
  683.       // time we changed the route (which would be when the 
  684.       // best route metric arrives) and the first time we heard
  685.       // the sequence number that started the measurement period
  687.       // do we care if we've missed a sequence number, such
  688.       // that we have a wst measurement period that streches over
  689.       // more than a single sequence number??? XXX -dam 4/20/98
  690.       rte.wst = alpha_ * prte->wst + 
  691. (1.0 - alpha_) * (prte->changed_at - prte->new_seqnum_at);
  692.       rte.new_seqnum_at = now;
  693.     }
  694. }
  695.       else
  696. { // inititallize the wst for the new route
  697.   rte.wst = wst0_;
  698.   rte.new_seqnum_at = now;
  699. }
  700.   
  701.       // Now that we know the wst_, we know when to update...
  702.       if (rte.metric != BIG && (!prte || prte->metric != BIG))
  703. rte.advertise_ok_at = now + (rte.wst * 2);
  704.       else
  705. rte.advertise_ok_at = now;
  707.       /*********** decide whether to update our routing table *********/
  708.       if (!prte)
  709. { // we've heard from a brand new destination
  710.   if (rte.metric < BIG) 
  711.     {
  712.       rte.advert_metric = true;
  713.       trigger_update = true;
  714.     }
  715.   updateRoute(prte,&rte);
  716. }
  717.       else if ( prte->seqnum == rte.seqnum )
  718. { // stnd dist vector case
  719.   if (rte.metric < prte->metric) 
  720.     { // a shorter route!
  721.       if (rte.metric == prte->last_advertised_metric)
  722. { // we've just gone back to a metric we've already advertised
  723.   rte.advert_metric = false;
  724.   trigger_update = false;
  725. }
  726.       else
  727. { // we're changing away from the last metric we announced
  728.   rte.advert_metric = true;
  729.   trigger_update = true;
  730. }
  731.       updateRoute(prte,&rte);
  732.     }
  733.   else
  734.     { // ignore the longer route
  735.     }
  736. }
  737.       else if ( prte->seqnum < rte.seqnum )
  738. { // we've heard a fresher sequence number
  739.   // we *must* believe its rt metric
  740.   rte.advert_seqnum = true; // we've got a new seqnum to advert
  741.   if (rte.metric == prte->last_advertised_metric)
  742.     { // we've just gone back to our old metric
  743.       rte.advert_metric = false;
  744.     }
  745.   else
  746.     { // we're using a metric different from our last advert
  747.       rte.advert_metric = true;
  748.     }
  750.   updateRoute(prte,&rte);
  752. #ifdef TRIGGER_UPDATE_ON_FRESH_SEQNUM
  753.   trigger_update = true;
  754. #else
  755.   trigger_update = false;
  756. #endif
  757. }
  758.       else if ( prte->seqnum > rte.seqnum )
  759. { // our neighbor has older sequnum info than we do
  760.   if (rte.metric == BIG && prte->metric != BIG)
  761.     { // we must go forth and educate this ignorant fellow
  762.       // about our more glorious and happy metric
  763.       prte->advertise_ok_at = now;
  764.       prte->advert_metric = true;
  765.       // directly schedule a triggered update now for 
  766.       // prte, since the other logic only works with rte.*
  767.       needTriggeredUpdate(prte,now);
  768.     }
  769.   else
  770.     { // we don't care about their stale info
  771.     }
  772. }
  773.       else
  774. {
  775.   fprintf(stderr,
  776.   "%s DFU: unhandled adding a route entry?n", __FILE__);
  777.   abort();
  778. }
  779.       
  780.       if (trigger_update)
  781. {
  782.   prte = table_->GetEntry (rte.dst);
  783.   assert(prte != NULL && prte->advertise_ok_at == rte.advertise_ok_at);
  784.   needTriggeredUpdate(prte, prte->advertise_ok_at);
  785. }
  787.       // see if we can send off any packets we've got queued
  788.       if (rte.q && rte.metric != BIG)
  789. {
  790.   Packet *queued_p;
  791.   while ((queued_p = rte.q->deque()))
  792.   // XXX possible loop here  
  793.   // while ((queued_p = rte.q->deque()))
  794.   // Only retry once to avoid looping
  795.   // for (int jj = 0; jj < rte.q->length(); jj++){
  796.   //  queued_p = rte.q->deque();
  797.     recv(queued_p, 0); // give the packets to ourselves to forward
  798.   // }
  799.   delete rte.q;
  800.   rte.q = 0;
  801.   table_->AddEntry(rte); // record the now zero'd queue
  802. }
  803.     } // end of all destination mentioned in routing update packet
  805.   // Reschedule the timeout for this neighbor
  806.   prte = table_->GetEntry(Address::instance().get_nodeaddr(iph->saddr()));
  807.   if (prte)
  808.     {
  809.       if (prte->timeout_event)
  810. s.cancel (prte->timeout_event);
  811.       else
  812. {
  813.   prte->timeout_event = new Event ();
  814. }
  815.       
  816.       s.schedule (helper_, prte->timeout_event, min_update_periods_ * perup_);
  817.     }
  818.   else
  819.     { // If the first thing we hear from a node is a triggered update
  820.       // that doesn't list the node sending the update as the first
  821.       // thing in the packet (which is disrecommended by the paper)
  822.       // we won't have a route to that node already.  In order to timeout
  823.       // the routes we just learned, we need a harmless route to keep the
  824.       // timeout metadata straight.
  825.       
  826.       // Hi there, nice to meet you. I'll make a fake advertisement
  827.       bzero(&rte, sizeof(rte));
  828.       rte.dst = Address::instance().get_nodeaddr(iph->saddr());
  829.       rte.hop = Address::instance().get_nodeaddr(iph->saddr());
  830.       rte.metric = 1;
  831.       rte.seqnum = 0;
  832.       rte.advertise_ok_at = now + 604800; // check back next week... :)
  833.       
  834.       rte.changed_at = now;
  835.       rte.new_seqnum_at = now;
  836.       rte.wst = wst0_;
  837.       rte.timeout_event = new Event ();
  838.       rte.q = 0;
  839.       
  840.       updateRoute(NULL, &rte);
  841.       s.schedule(helper_, rte.timeout_event, min_update_periods_ * perup_);
  842.     }
  843.   
  844.   /*
  845.    * Freeing a routing layer packet --> don't need to
  846.    * call drop here.
  847.    */
  848.   Packet::free (p);
  850. }
  852. int 
  853. DSDV_Agent::diff_subnet(int dst) 
  854. {
  855. char* dstnet = Address::instance().get_subnetaddr(dst);
  856. if (subnet_ != NULL) {
  857. if (dstnet != NULL) {
  858. if (strcmp(dstnet, subnet_) != 0) {
  859. delete [] dstnet;
  860. return 1;
  861. }
  862. delete [] dstnet;
  863. }
  864. }
  865. //assert(dstnet == NULL);
  866. return 0;
  867. }
  871. void
  872. DSDV_Agent::forwardPacket (Packet * p)
  873. {
  874.   hdr_ip *iph = HDR_IP(p);
  875.   Scheduler & s = Scheduler::instance ();
  876.   double now = s.clock ();
  877.   hdr_cmn *hdrc = HDR_CMN (p);
  878.   int dst;
  879.   rtable_ent *prte;
  880.   
  881.   // We should route it.
  882.   //printf("(%d)-->forwardig pktn",myaddr_);
  883.   // set direction of pkt to -1 , i.e downward
  884.   hdrc->direction() = hdr_cmn::DOWN;
  886.   // if the destination is outside mobilenode's domain
  887.   // forward it to base_stn node
  888.   // Note: pkt is not buffered if route to base_stn is unknown
  890.   dst = Address::instance().get_nodeaddr(iph->daddr());  
  891.   if (diff_subnet(iph->daddr())) {
  892.    prte = table_->GetEntry (dst);
  893.   if (prte && prte->metric != BIG) 
  894.   goto send;
  895.   
  896.   //int dst = (node_->base_stn())->address();
  897.   dst = node_->base_stn();
  898.   prte = table_->GetEntry (dst);
  899.   if (prte && prte->metric != BIG) 
  900.   goto send;
  901.   
  902.   else {
  903.   //drop pkt with warning
  904.   fprintf(stderr, "warning: Route to base_stn not known: dropping pktn");
  905.   Packet::free(p);
  906.   return;
  907.   }
  908.   }
  909.   
  910.   prte = table_->GetEntry (dst);
  911.   
  912.   //  trace("VDEBUG-RX %d %d->%d %d %d 0x%08x 0x%08x %d %d", 
  913.   //  myaddr_, iph->src(), iph->dst(), hdrc->next_hop_, hdrc->addr_type_,
  914.   //  hdrc->xmit_failure_, hdrc->xmit_failure_data_,
  915.   //  hdrc->num_forwards_, hdrc->opt_num_forwards);
  917.   if (prte && prte->metric != BIG)
  918.     {
  919.        //printf("(%d)-have route for dstn",myaddr_);
  920.        goto send;
  921.     }
  922.   else if (prte)
  923.     { /* must queue the packet */
  924.     //printf("(%d)-no route, queue pktn",myaddr_);
  925.       if (!prte->q)
  926. {
  927.   prte->q = new PacketQueue ();
  928. }
  930.       prte->q->enque(p);
  932.       if (verbose_)
  933. trace ("VBP %.5f _%d_ %d:%d -> %d:%d", now, myaddr_, iph->saddr(),
  934.        iph->sport(), iph->daddr(), iph->dport());
  936.       while (prte->q->length () > MAX_QUEUE_LENGTH)
  937.       drop (prte->q->deque (), DROP_RTR_QFULL);
  938.       return;
  939.     }
  940.   else
  941.     { // Brand new destination
  942.       rtable_ent rte;
  943.       double now = s.clock();
  944.       
  945.       bzero(&rte, sizeof(rte));
  946.       rte.dst = dst;
  947.       rte.hop = dst;
  948.       rte.metric = BIG;
  949.       rte.seqnum = 0;
  951.       rte.advertise_ok_at = now + 604800; // check back next week... :)
  952.       rte.changed_at = now;
  953.       rte.new_seqnum_at = now; // was now + wst0_, why??? XXX -dam
  954.       rte.wst = wst0_;
  955.       rte.timeout_event = 0;
  957.       rte.q = new PacketQueue();
  958.       rte.q->enque(p);
  959.   
  960.       assert (rte.q->length() == 1 && 1 <= MAX_QUEUE_LENGTH);
  961.       table_->AddEntry(rte);
  962.       
  963.       if (verbose_)
  964.       trace ("VBP %.5f _%d_ %d:%d -> %d:%d", now, myaddr_,
  965.      iph->saddr(), iph->sport(), iph->daddr(), iph->dport());
  966.       return;
  967.     }
  970.  send:
  971.   hdrc->addr_type_ = NS_AF_INET;
  972.   hdrc->xmit_failure_ = mac_callback;
  973.   hdrc->xmit_failure_data_ = this;
  974.   if (prte->metric > 1)
  975.   hdrc->next_hop_ = prte->hop;
  976.   else
  977.   hdrc->next_hop_ = dst;
  978.   if (verbose_)
  979.   trace ("Routing pkts outside domain: 
  980. VFP %.5f _%d_ %d:%d -> %d:%d", now, myaddr_, iph->saddr(),
  981.  iph->sport(), iph->daddr(), iph->dport());  
  983.   assert (!HDR_CMN (p)->xmit_failure_ ||
  984.   HDR_CMN (p)->xmit_failure_ == mac_callback);
  985.   target_->recv(p, (Handler *)0);
  986.   return;
  987.   
  988. }
  990. void 
  991. DSDV_Agent::sendOutBCastPkt(Packet *p)
  992. {
  993.   Scheduler & s = Scheduler::instance ();
  994.   // send out bcast pkt with jitter to avoid sync
  995.   s.schedule (target_, p, jitter(DSDV_BROADCAST_JITTER, be_random_));
  996. }
  999. void
  1000. DSDV_Agent::recv (Packet * p, Handler *)
  1001. {
  1002.   hdr_ip *iph = HDR_IP(p);
  1003.   hdr_cmn *cmh = HDR_CMN(p);
  1004.   int src = Address::instance().get_nodeaddr(iph->saddr());
  1005.   /*
  1006.    *  Must be a packet I'm originating...
  1007.    */
  1008.   if(src == myaddr_ && cmh->num_forwards() == 0) {
  1009.     /*
  1010.      * Add the IP Header
  1011.      */
  1012.     cmh->size() += IP_HDR_LEN;    
  1013.     iph->ttl_ = IP_DEF_TTL;
  1014.   }
  1015.   /*
  1016.    *  I received a packet that I sent.  Probably
  1017.    *  a routing loop.
  1018.    */
  1019.   else if(src == myaddr_) {
  1020.     drop(p, DROP_RTR_ROUTE_LOOP);
  1021.     return;
  1022.   }
  1023.   /*
  1024.    *  Packet I'm forwarding...
  1025.    */
  1026.   else {
  1027.     /*
  1028.      *  Check the TTL.  If it is zero, then discard.
  1029.      */
  1030.     if(--iph->ttl_ == 0) {
  1031.       drop(p, DROP_RTR_TTL);
  1032.       return;
  1033.     }
  1034.   }
  1035.   
  1036.   if ((src != myaddr_) && (iph->dport() == ROUTER_PORT))
  1037.     {
  1038.     // XXX disable this feature for mobileIP where
  1039.     // the MH and FA (belonging to diff domains)
  1040.     // communicate with each other.
  1042.     // Drop pkt if rtg update from some other domain:
  1043.     // if (diff_subnet(iph->src())) 
  1044.     // drop(p, DROP_OUTSIDE_SUBNET);
  1045.     //else    
  1046.     processUpdate(p);
  1047.     }
  1048.   else if (iph->daddr() == ((int)IP_BROADCAST) &&
  1049.    (iph->dport() != ROUTER_PORT)) 
  1050.   {
  1051.      if (src == myaddr_) {
  1052.      // handle brdcast pkt
  1053.      sendOutBCastPkt(p);
  1054.      }
  1055.      else {
  1056.      // hand it over to the port-demux
  1057.     port_dmux_->recv(p, (Handler*)0);
  1058.      }
  1059.   }
  1060.   else 
  1061.     {
  1062.     forwardPacket(p);
  1063.     }
  1064. }
  1066. static class DSDVClass:public TclClass
  1067. {
  1068.   public:
  1069.   DSDVClass ():TclClass ("Agent/DSDV")
  1070.   {
  1071.   }
  1072.   TclObject *create (int, const char *const *)
  1073.   {
  1074.     return (new DSDV_Agent ());
  1075.   }
  1076. } class_dsdv;
  1078. DSDV_Agent::DSDV_Agent (): Agent (PT_MESSAGE), ll_queue (0), seqno_ (0), 
  1079.   myaddr_ (0), subnet_ (0), node_ (0), port_dmux_(0),
  1080.   periodic_callback_ (0), be_random_ (1), 
  1081.   use_mac_ (0), verbose_ (1), trace_wst_ (0), lasttup_ (-10), 
  1082.   alpha_ (0.875),  wst0_ (6), perup_ (15), 
  1083.   min_update_periods_ (3) // constants
  1084.  {
  1085.   table_ = new RoutingTable ();
  1086.   helper_ = new DSDV_Helper (this);
  1087.   trigger_handler = new DSDVTriggerHandler(this);
  1089.   bind_time ("wst0_", &wst0_);
  1090.   bind_time ("perup_", &perup_);
  1092.   bind ("use_mac_", &use_mac_);
  1093.   bind ("be_random_", &be_random_);
  1094.   bind ("alpha_", &alpha_);
  1095.   bind ("min_update_periods_", &min_update_periods_);
  1096.   bind ("verbose_", &verbose_);
  1097.   bind ("trace_wst_", &trace_wst_);
  1098.   //DEBUG
  1099.   address = 0;
  1100.  
  1101. }
  1103. void
  1104. DSDV_Agent::startUp()
  1105. {
  1106.  Time now = Scheduler::instance().clock();
  1108.   subnet_ = Address::instance().get_subnetaddr(myaddr_);
  1109.   //DEBUG
  1110.   address = Address::instance().print_nodeaddr(myaddr_);
  1111.   //printf("myaddress: %d -> %sn",myaddr_,address);
  1112.   
  1113.   rtable_ent rte;
  1114.   bzero(&rte, sizeof(rte));
  1116.   rte.dst = myaddr_;
  1117.   rte.hop = myaddr_;
  1118.   rte.metric = 0;
  1119.   rte.seqnum = seqno_;
  1120.   seqno_ += 2;
  1122.   rte.advertise_ok_at = 0.0; // can always advert ourselves
  1123.   rte.advert_seqnum = true;
  1124.   rte.advert_metric = true;
  1125.   rte.changed_at = now;
  1126.   rte.new_seqnum_at = now;
  1127.   rte.wst = 0;
  1128.   rte.timeout_event = 0; // Don't time out our localhost :)
  1129.   
  1130.   rte.q = 0; // Don't buffer pkts for self!
  1131.   
  1132.   table_->AddEntry (rte);
  1134.   // kick off periodic advertisments
  1135.   periodic_callback_ = new Event ();
  1136.   Scheduler::instance ().schedule (helper_, 
  1137.    periodic_callback_,
  1138.    jitter (DSDV_STARTUP_JITTER, be_random_));
  1139. }
  1141. int 
  1142. DSDV_Agent::command (int argc, const char *const *argv)
  1143. {
  1144.   if (argc == 2)
  1145.     {
  1146.       if (strcmp (argv[1], "start-dsdv") == 0)
  1147. {
  1148.   startUp();
  1149.   return (TCL_OK);
  1150. }
  1151.       else if (strcmp (argv[1], "dumprtab") == 0)
  1152. {
  1153.   Packet *p2 = allocpkt ();
  1154.   hdr_ip *iph2 = HDR_IP(p2);
  1155.   rtable_ent *prte;
  1157.   printf ("Table Dump %d[%d]n----------------------------------n",
  1158.   iph2->saddr(), iph2->sport());
  1159. trace ("VTD %.5f %d:%dn", Scheduler::instance ().clock (),
  1160.  iph2->saddr(), iph2->sport());
  1162.   /*
  1163.    * Freeing a routing layer packet --> don't need to
  1164.    * call drop here.
  1165.    */
  1166. Packet::free (p2);
  1168.   for (table_->InitLoop (); (prte = table_->NextLoop ());)
  1169.     output_rte ("t", prte, this);
  1171.   printf ("n");
  1173.   return (TCL_OK);
  1174. }
  1175.       else if (strcasecmp (argv[1], "ll-queue") == 0)
  1176. {
  1177. if (!(ll_queue = (PriQueue *) TclObject::lookup (argv[2])))
  1178.     {
  1179.       fprintf (stderr, "DSDV_Agent: ll-queue lookup of %s failedn", argv[2]);
  1180.       return TCL_ERROR;
  1181.     }
  1183.   return TCL_OK;
  1184. }
  1186.     }
  1187.   else if (argc == 3)
  1188.     {
  1189.       if (strcasecmp (argv[1], "addr") == 0) {
  1190.  int temp;
  1191.  temp = Address::instance().str2addr(argv[2]);
  1192.  myaddr_ = temp;
  1193.  return TCL_OK;
  1194.       }
  1195.       TclObject *obj;
  1196.       if ((obj = TclObject::lookup (argv[2])) == 0)
  1197. {
  1198.   fprintf (stderr, "%s: %s lookup of %s failedn", __FILE__, argv[1],
  1199.    argv[2]);
  1200.   return TCL_ERROR;
  1201. }
  1202.       if (strcasecmp (argv[1], "tracetarget") == 0)
  1203. {
  1204.   
  1205.   tracetarget = (Trace *) obj;
  1206.   return TCL_OK;
  1207. }
  1208.       else if (strcasecmp (argv[1], "node") == 0) {
  1209.       node_ = (MobileNode*) obj;
  1210.       return TCL_OK;
  1211.       }
  1212.       else if (strcasecmp (argv[1], "port-dmux") == 0) {
  1213.       port_dmux_ = (NsObject *) obj;
  1214.       return TCL_OK;
  1215.       }
  1216.     }
  1217.   
  1218.   return (Agent::command (argc, argv));
  1219. }