dsdv.cc

Go to the documentation of this file.

/* -*-  Mode:C++; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */
/*
 * Copyright (c) 1997 Regents of the University of California.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *      This product includes software developed by the Computer Systems
 *      Engineering Group at Lawrence Berkeley Laboratory.
 * 4. Neither the name of the University nor of the Laboratory may be used
 *    to endorse or promote products derived from this software without
 *    specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 * Ported from CMU/Monarch's code, nov'98 -Padma.
 *
 * $Header: /nfs/jade/vint/CVSROOT/ns-2/dsdv/dsdv.cc,v 1.22 2001/05/21 19:27:33 haldar Exp $
 */

extern "C" {
#include <stdarg.h>
#include <float.h>
};

#include "dsdv.h"
#include "priqueue.h"

#include <random.h>

#include <cmu-trace.h>
#include <address.h>
#include <mobilenode.h>


#define DSDV_STARTUP_JITTER 2.0 // secs to jitter start of periodic activity from
                                // when start-dsr msg sent to agent
#define DSDV_ALMOST_NOW     0.1 // jitter used for events that should be effectively
                                // instantaneous but are jittered to prevent
                                // synchronization
#define DSDV_BROADCAST_JITTER 0.01 // jitter for all broadcast packets
#define DSDV_MIN_TUP_PERIOD 1.0 // minimum time between triggered updates
#define IP_DEF_TTL   32 // default TTTL

#undef TRIGGER_UPDATE_ON_FRESH_SEQNUM
//#define TRIGGER_UPDATE_ON_FRESH_SEQNUM
/* should the receipt of a fresh (newer) sequence number cause us
   to send a triggered update?  If undef'd, we'll only trigger on
   routing metric changes */

// Returns a random number between 0 and max
static inline double 
jitter (double max, int be_random_)
{
  return (be_random_ ? Random::uniform(max) : 0);
}

void DSDV_Agent::
trace (char *fmt,...)
{
  va_list ap;

  if (!tracetarget)
    return;

  va_start (ap, fmt);
  vsprintf (tracetarget->pt_->buffer (), fmt, ap);
  tracetarget->pt_->dump ();
  va_end (ap);
}

void 
DSDV_Agent::tracepkt (Packet * p, double now, int me, const char *type)
{
  char buf[1024];

  unsigned char *walk = p->accessdata ();

  int ct = *(walk++);
  int seq, dst, met;

  snprintf (buf, 1024, "V%s %.5f _%d_ [%d]:", type, now, me, ct);
  while (ct--)
    {
      dst = *(walk++);
      dst = dst << 8 | *(walk++);
      dst = dst << 8 | *(walk++);
      dst = dst << 8 | *(walk++);
      met = *(walk++);
      seq = *(walk++);
      seq = seq << 8 | *(walk++);
      seq = seq << 8 | *(walk++);
      seq = seq << 8 | *(walk++);
      snprintf (buf, 1024, "%s (%d,%d,%d)", buf, dst, met, seq);
    }
  // Now do trigger handling.
  //trace("VTU %.5f %d", now, me);
  if (verbose_)
    trace ("%s", buf);
}

// Prints out an rtable element.
void
DSDV_Agent::output_rte(const char *prefix, rtable_ent * prte, DSDV_Agent * a)
{
  a->trace("DFU: deimplemented");
  printf("DFU: deimplemented");

  prte = 0;
  prefix = 0;
#if 0
  printf ("%s%d %d %d %d %f %f %f %f 0x%08x\n",
          prefix, prte->dst, prte->hop, prte->metric, prte->seqnum,
          prte->udtime, prte->new_seqnum_at, prte->wst, prte->changed_at,
          (unsigned int) prte->timeout_event);
  a->trace ("VTE %.5f %d %d %d %d %f %f %f %f 0x%08x",
          Scheduler::instance ().clock (), prte->dst, prte->hop, prte->metric,
          prte->seqnum, prte->udtime, prte->new_seqnum_at, prte->wst, prte->changed_at,
            prte->timeout_event);
#endif
}

class DSDVTriggerHandler : public Handler {
  public:
    DSDVTriggerHandler(DSDV_Agent *a_) { a = a_; }
    virtual void handle(Event *e);
  private:
    DSDV_Agent *a;
};


void
DSDVTriggerHandler::handle(Event *e)
 // send a triggered update (or a full update if one's needed)
{
        //DEBUG
        //printf("(%d)-->triggered update with e=%x\n", a->myaddr_,e); 

  Scheduler & s = Scheduler::instance ();
  Time now = s.clock ();
  rtable_ent *prte;
  int update_type;       // we want periodic (=1) or triggered (=0) update?
  Time next_possible = a->lasttup_ + DSDV_MIN_TUP_PERIOD;

  for (a->table_->InitLoop(); (prte = a->table_->NextLoop());)
          if (prte->trigger_event == e) break;

  assert(prte && prte->trigger_event == e);

  if (now < next_possible)
    {
            //DEBUG
            //printf("(%d)..Re-scheduling triggered update\n",a->myaddr_);
      s.schedule(a->trigger_handler, e, next_possible - now);
      a->cancelTriggersBefore(next_possible);
      return;
    }

  update_type = 0;
  Packet * p = a->makeUpdate(/*in-out*/update_type);
      
  if (p != NULL) 
    {     
      if (update_type == 1)
        { // we got a periodic update, though we only asked for triggered
          // cancel and reschedule periodic update
          s.cancel(a->periodic_callback_);
          //DEBUG
          //printf("we got a periodic update, though asked for trigg\n");
          s.schedule (a->helper_, a->periodic_callback_, 
                      a->perup_ * (0.75 + jitter (0.25, a->be_random_)));
          if (a->verbose_) a->tracepkt (p, now, a->myaddr_, "PU");        
        }
      else
        {
          if (a->verbose_) a->tracepkt (p, now, a->myaddr_, "TU");        
        }
      assert (!HDR_CMN (p)->xmit_failure_);     // DEBUG 0x2      
      s.schedule (a->target_, p, jitter(DSDV_BROADCAST_JITTER, a->be_random_));
      
      a->lasttup_ = now; // even if we got a full update, it still counts
      // for our last triggered update time
    }
  
  // free this event
  for (a->table_->InitLoop (); (prte = a->table_->NextLoop ());)
    if (prte->trigger_event && prte->trigger_event == e)
      {
        prte->trigger_event = 0;
        delete e;
      }
}

void
DSDV_Agent::cancelTriggersBefore(Time t)
  // Cancel any triggered events scheduled to take place *before* time
  // t (exclusive)
{
  rtable_ent *prte;
  Scheduler & s = Scheduler::instance ();

  for (table_->InitLoop (); (prte = table_->NextLoop ());)
    if (prte->trigger_event && prte->trigger_event->time_ < t)
      {
              //DEBUG
              //printf("(%d) cancel event %x\n",myaddr_,prte->trigger_event);
        s.cancel(prte->trigger_event);
        delete prte->trigger_event;
        prte->trigger_event = 0;
      }
}

void
DSDV_Agent::needTriggeredUpdate(rtable_ent *prte, Time t)
  // if no triggered update already pending, make one so
{
  Scheduler & s = Scheduler::instance();
  Time now = Scheduler::instance().clock();

  assert(t >= now);

  if (prte->trigger_event) 
    s.cancel(prte->trigger_event);
  else
    prte->trigger_event = new Event;
  //DEBUG
  //printf("(%d)..scheduling trigger-update with event %x\n",myaddr_,prte->trigger_event);
  s.schedule(trigger_handler, prte->trigger_event, t - now);
}

void
DSDV_Agent::helper_callback (Event * e)
{
  Scheduler & s = Scheduler::instance ();
  double now = s.clock ();
  rtable_ent *prte;
  rtable_ent *pr2;
  int update_type;       // we want periodic (=1) or triggered (=0) update?
  //DEBUG
  //printf("Triggered handler on 0x%08x\n", e);

  // Check for periodic callback
  if (periodic_callback_ && e == periodic_callback_)
    {
      update_type = 1;
      Packet *p = makeUpdate(/*in-out*/update_type);
      if (verbose_)
        {
          trace ("VPC %.5f _%d_", now, myaddr_);
          tracepkt (p, now, myaddr_, "PU");
        }

      
      if (p) {
              assert (!HDR_CMN (p)->xmit_failure_);     // DEBUG 0x2
              // send out update packet jitter to avoid sync
              //DEBUG
              //printf("(%d)..sendout update pkt (periodic=%d)\n",myaddr_,update_type);
              s.schedule (target_, p, jitter(DSDV_BROADCAST_JITTER, be_random_));
      }
      
      // put the periodic update sending callback back onto the 
      // the scheduler queue for next time....
      s.schedule (helper_, periodic_callback_, 
                  perup_ * (0.75 + jitter (0.25, be_random_)));

      // this will take the place of any planned triggered updates
      lasttup_ = now;
      return;
    }

  // Check for timeout
  // If it was a timeout, fix the routing table.
  for (table_->InitLoop (); (prte = table_->NextLoop ());)
    if (prte->timeout_event && (prte->timeout_event == e))
      break;

  // If it was a timeout, prte will be non-NULL
  // Note that in the if we don't touch the changed_at time, so that when
  // wst is computed, it doesn't consider the infinte metric the best
  // one at that sequence number.
  if (prte)
          {
      if (verbose_)
        {
          trace ("VTO %.5f _%d_ %d->%d", now, myaddr_, myaddr_, prte->dst);
          /*      trace ("VTO %.5f _%d_ trg_sch %x on sched %x time %f", now, myaddr_, 
                 trigupd_scheduled, 
                 trigupd_scheduled ? s.lookup(trigupd_scheduled->uid_) : 0,
                 trigupd_scheduled ? trigupd_scheduled->time_ : 0); */
        }
      
      for (table_->InitLoop (); (pr2 = table_->NextLoop ()); )
        {
          if (pr2->hop == prte->dst && pr2->metric != BIG)
            {
              if (verbose_)
                trace ("VTO %.5f _%d_ marking %d", now, myaddr_, pr2->dst);
              pr2->metric = BIG;
              pr2->advertise_ok_at = now;
              pr2->advert_metric = true;
              pr2->advert_seqnum = true;
              pr2->seqnum++;
              // And we have routing info to propogate.
              //DEBUG
              //printf("(%d)..we have routing info to propagate..trigger update for dst %d\n",myaddr_,pr2->dst);
              needTriggeredUpdate(pr2, now);
            }
        }

      // OK the timeout expired, so we'll free it. No dangling pointers.
      prte->timeout_event = 0;    
    }
  else 
    { // unknown event on  queue
      fprintf(stderr,"DFU: unknown queue event\n");
     abort();
    }

  if (e)
    delete e;
}

void
DSDV_Agent::lost_link (Packet *p)
{
  hdr_cmn *hdrc = HDR_CMN (p);
  rtable_ent *prte = table_->GetEntry (hdrc->next_hop_);

  if(use_mac_ == 0) {
          drop(p, DROP_RTR_MAC_CALLBACK);
          return;
  }

  //DEBUG
  //printf("(%d)..Lost link..\n",myaddr_);
  if (verbose_ && hdrc->addr_type_ == NS_AF_INET)
    trace("VLL %.8f %d->%d lost at %d",
    Scheduler::instance().clock(),
           hdr_ip::access(p)->saddr(), hdr_ip::access(p)->daddr(),
           myaddr_);

  if (!use_mac_ || !prte || hdrc->addr_type_ != NS_AF_INET)
    return;

  if (verbose_)
    trace ("VLP %.5f %d:%d->%d:%d lost at %d [hop %d]",
  Scheduler::instance ().clock (),
           hdr_ip::access (p)->saddr(),
           hdr_ip::access (p)->sport(),
           hdr_ip::access (p)->daddr(),
           hdr_ip::access (p)->dport(),
           myaddr_, prte->dst);

  if (prte->timeout_event)
    {
      Scheduler::instance ().cancel (prte->timeout_event);
      helper_callback (prte->timeout_event);
    }
  else if (prte->metric != BIG)
    {
      assert(prte->timeout_event == 0);
      prte->timeout_event = new Event ();
      helper_callback (prte->timeout_event);
    }

  // Queue these packets up...
  recv(p, 0);

#if 0
  while (p2 = ((PriQueue *) target_)->filter (prte->dst))
    {
      if (verbose_)
      trace ("VRS %.5f %d:%d->%d:%d lost at %d", Scheduler::instance ().clock (),
               hdr_ip::access (p2)->saddr(),
               hdr_ip::access (p2)->sport(),
               hdr_ip::access (p2)->daddr(),
               hdr_ip::access (p2)->dport(), myaddr_);

      recv(p2, 0);
    }

  while (p2 = ll_queue->filter (prte->dst))
    {
      if (verbose_)
      trace ("VRS %.5f %d:%d->%d:%d lost at %d", Scheduler::instance ().clock (),
               hdr_ip::access (p2)->saddr(),
               hdr_ip::access (p2)->sport(),
               hdr_ip::access (p2)->daddr(),
               hdr_ip::access (p2)->dport(), myaddr_);

      recv (p2, 0);
    }
#endif
}

static void 
mac_callback (Packet * p, void *arg)
{
  ((DSDV_Agent *) arg)->lost_link (p);
}

Packet *
DSDV_Agent::makeUpdate(int& periodic)
    // return a packet advertising the state in the routing table
    // makes a full ``periodic'' update if requested, or a ``triggered''
    // partial update if there are only a few changes and full update otherwise
    // returns with periodic = 1 if full update returned, or = 0 if partial
  //   update returned
        
{
        //DEBUG
        //printf("(%d)-->Making update pkt\n",myaddr_);
        
  Packet *p = allocpkt ();
  hdr_ip *iph = hdr_ip::access(p);
  hdr_cmn *hdrc = HDR_CMN (p);
  double now = Scheduler::instance ().clock ();
  rtable_ent *prte;
  unsigned char *walk;

  int change_count;             // count of entries to go in this update
  int rtbl_sz;                  // counts total entries in rt table
  int unadvertiseable;          // number of routes we can't advertise yet

  //printf("Update packet from %d [per=%d]\n", myaddr_, periodic);

  // The packet we send wants to be broadcast
  hdrc->next_hop_ = IP_BROADCAST;
  hdrc->addr_type_ = NS_AF_INET;
  iph->daddr() = IP_BROADCAST << Address::instance().nodeshift();
  iph->dport() = ROUTER_PORT;

  change_count = 0;
  rtbl_sz = 0;
  unadvertiseable = 0;
  for (table_->InitLoop (); 
       (prte = table_->NextLoop ()); )
    {
      rtbl_sz++;
      if ((prte->advert_seqnum || prte->advert_metric) 
          && prte->advertise_ok_at <= now) 
        change_count++;

      if (prte->advertise_ok_at > now) unadvertiseable++;
    }
  //printf("change_count = %d\n",change_count);
  if (change_count * 3 > rtbl_sz && change_count > 3)
    { // much of the table has changed, just do a periodic update now
      periodic = 1;
    }

  // Periodic update... increment the sequence number...
  if (periodic)
    {
      change_count = rtbl_sz - unadvertiseable;
      //printf("rtbsize-%d, unadvert-%d\n",rtbl_sz,unadvertiseable);
      rtable_ent rte;
      bzero(&rte, sizeof(rte));

      /* inc sequence number on any periodic update, even if we started
         off wanting to do a triggered update, b/c we're doing a real
         live periodic update now that'll take the place of our next
         periodic update */
      seqno_ += 2;

      rte.dst = myaddr_;
      //rte.hop = iph->src();
      rte.hop = Address::instance().get_nodeaddr(iph->saddr());
      rte.metric = 0;
      rte.seqnum = seqno_;

      rte.advertise_ok_at = 0.0; // can always advert ourselves
      rte.advert_seqnum = true;  // always include ourselves in Triggered Upds
      rte.changed_at = now;
      rte.new_seqnum_at = now;
      rte.wst = 0;
      rte.timeout_event = 0;            // Don't time out our localhost :)

      rte.q = 0;                // Don't buffer pkts for self!

      table_->AddEntry (rte);
    }

  if (change_count == 0) 
    {
      Packet::free(p); // allocated by us, no drop needed

      return NULL; // nothing to advertise
    }

  /* ****** make the update packet.... ***********
     with less than 100+ nodes, an update for all nodes is less than the
     MTU, so don't bother worrying about splitting the update over
     multiple packets -dam 4/26/98 */
  assert(rtbl_sz <= (1500 / 12));

  p->allocdata((change_count * 9) + 1);
  walk = p->accessdata ();
  *(walk++) = change_count;

  // hdrc->size_ = change_count * 12 + 20;      // DSDV + IP
  hdrc->size_ = change_count * 12 + IP_HDR_LEN; // DSDV + IP

  for (table_->InitLoop (); (prte = table_->NextLoop ());)
    {

      if (periodic && prte->advertise_ok_at > now)
        { // don't send out routes that shouldn't be advertised
          // even in periodic updates
          continue;
        }

      if (periodic || 
          ((prte->advert_seqnum || prte->advert_metric) 
           && prte->advertise_ok_at <= now))
        { // include this rte in the advert
          if (!periodic && verbose_)
            trace ("VCT %.5f _%d_ %d", now, myaddr_, prte->dst);

          //assert (prte->dst < 256 && prte->metric < 256);
          //*(walk++) = prte->dst;
          *(walk++) = prte->dst >> 24;
          *(walk++) = (prte->dst >> 16) & 0xFF;
          *(walk++) = (prte->dst >> 8) & 0xFF;
          *(walk++) = (prte->dst >> 0) & 0xFF;
          *(walk++) = prte->metric;
          *(walk++) = (prte->seqnum) >> 24;
          *(walk++) = ((prte->seqnum) >> 16) & 0xFF;
          *(walk++) = ((prte->seqnum) >> 8) & 0xFF;
          *(walk++) = (prte->seqnum) & 0xFF;

          prte->last_advertised_metric = prte->metric;

          // seqnum's only need to be advertised once after they change
          prte->advert_seqnum = false; // don't need to advert seqnum again

          if (periodic) 
            { // a full advert means we don't have to re-advert either 
              // metrics or seqnums again until they change
              prte->advert_seqnum = false;
              prte->advert_metric = false;
            }
          change_count--;
        }
    }  
  assert(change_count == 0);
  return p;
}

void
DSDV_Agent::updateRoute(rtable_ent *old_rte, rtable_ent *new_rte)
{
  int negvalue = -1;
  assert(new_rte);

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

  char buf[1024];
  //  snprintf (buf, 1024, "%c %.5f _%d_ (%d,%d->%d,%d->%d,%d->%d,%lf)",
  snprintf (buf, 1024, "%c %.5f _%d_ (%d,%d->%d,%d->%d,%d->%d,%f)",
            (new_rte->metric != BIG 
             && (!old_rte || old_rte->metric != BIG)) ? 'D' : 'U', 
            now, myaddr_, new_rte->dst, 
            old_rte ? old_rte->metric : negvalue, new_rte->metric, 
            old_rte ? old_rte->seqnum : negvalue,  new_rte->seqnum,
            old_rte ? old_rte->hop : -1,  new_rte->hop, 
            new_rte->advertise_ok_at);

  table_->AddEntry (*new_rte);
  //printf("(%d),Route table updated..\n",myaddr_);
  if (trace_wst_)
    trace ("VWST %.12lf frm %d to %d wst %.12lf nxthp %d [of %d]",
           now, myaddr_, new_rte->dst, new_rte->wst, new_rte->hop, 
           new_rte->metric);
  if (verbose_)
    trace ("VS%s", buf);
}

void
DSDV_Agent::processUpdate (Packet * p)
{
  hdr_ip *iph = HDR_IP(p);
  Scheduler & s = Scheduler::instance ();
  double now = s.clock ();
  
  // it's a dsdv packet
  int i;
  unsigned char *d = p->accessdata ();
  unsigned char *w = d + 1;
  rtable_ent rte;               // new rte learned from update being processed
  rtable_ent *prte;             // ptr to entry *in* routing tbl

  //DEBUG
  //int src, dst;
  //src = Address::instance().get_nodeaddr(iph->src());
  //dst = Address::instance().get_nodeaddr(iph->dst());
  //printf("Received DSDV packet from %d(%d) to %d(%d) [%d)]\n", src, iph->sport(), dst, iph->dport(), myaddr_);

  for (i = *d; i > 0; i--)
    {
      bool trigger_update = false;  // do we need to do a triggered update?
      nsaddr_t dst;
      prte = NULL;

      dst = *(w++);
      dst = dst << 8 | *(w++);
      dst = dst << 8 | *(w++);
      dst = dst << 8 | *(w++);

      if ((prte = table_->GetEntry (dst)))
        {
          bcopy(prte, &rte, sizeof(rte));
        }
      else
        {
          bzero(&rte, sizeof(rte));
        }

      rte.dst = dst;
      //rte.hop = iph->src();
      rte.hop = Address::instance().get_nodeaddr(iph->saddr());
      rte.metric = *(w++);
      rte.seqnum = *(w++);
      rte.seqnum = rte.seqnum << 8 | *(w++);
      rte.seqnum = rte.seqnum << 8 | *(w++);
      rte.seqnum = rte.seqnum << 8 | *(w++);
      rte.changed_at = now;
      if (rte.metric != BIG) rte.metric += 1;

      if (rte.dst == myaddr_)
        {
          if (rte.metric == BIG && periodic_callback_)
            {
              // You have the last word on yourself...
              // Tell the world right now that I'm still here....
              // This is a CMU Monarch optimiziation to fix the 
              // the problem of other nodes telling you and your neighbors
              // that you don't exist described in the paper.
              s.cancel (periodic_callback_);
              s.schedule (helper_, periodic_callback_, 0);
            }
          continue;             // don't corrupt your own routing table.

        }

      /**********  fill in meta data for new route ***********/
      // If it's in the table, make it the same timeout and queue.
      if (prte)
        { // we already have a route to this dst
          if (prte->seqnum == rte.seqnum)
            { // we've got an update with out a new squenece number
              // this update must have come along a different path
              // than the previous one, and is just the kind of thing
              // the weighted settling time is supposed to track.

              // this code is now a no-op left here for clarity -dam XXX
              rte.wst = prte->wst;
              rte.new_seqnum_at = prte->new_seqnum_at;
            }
          else 
            { // we've got a new seq number, end the measurement period
              // for wst over the course of the old sequence number
              // and update wst with the difference between the last
              // time we changed the route (which would be when the 
              // best route metric arrives) and the first time we heard
              // the sequence number that started the measurement period

              // do we care if we've missed a sequence number, such
              // that we have a wst measurement period that streches over
              // more than a single sequence number??? XXX -dam 4/20/98
              rte.wst = alpha_ * prte->wst + 
                (1.0 - alpha_) * (prte->changed_at - prte->new_seqnum_at);
              rte.new_seqnum_at = now;
            }
        }
      else
        { // inititallize the wst for the new route
          rte.wst = wst0_;
          rte.new_seqnum_at = now;
        }
          
      // Now that we know the wst_, we know when to update...
      if (rte.metric != BIG && (!prte || prte->metric != BIG))
        rte.advertise_ok_at = now + (rte.wst * 2);
      else
        rte.advertise_ok_at = now;

      /*********** decide whether to update our routing table *********/
      if (!prte)
        { // we've heard from a brand new destination
          if (rte.metric < BIG) 
            {
              rte.advert_metric = true;
              trigger_update = true;
            }
          updateRoute(prte,&rte);
        }
      else if ( prte->seqnum == rte.seqnum )
        { // stnd dist vector case
          if (rte.metric < prte->metric) 
            { // a shorter route!
              if (rte.metric == prte->last_advertised_metric)
                { // we've just gone back to a metric we've already advertised
                  rte.advert_metric = false;
                  trigger_update = false;
                }
              else
                { // we're changing away from the last metric we announced
                  rte.advert_metric = true;
                  trigger_update = true;
                }
              updateRoute(prte,&rte);
            }
          else
            { // ignore the longer route
            }
        }
      else if ( prte->seqnum < rte.seqnum )
        { // we've heard a fresher sequence number
          // we *must* believe its rt metric
          rte.advert_seqnum = true;     // we've got a new seqnum to advert
          if (rte.metric == prte->last_advertised_metric)
            { // we've just gone back to our old metric
              rte.advert_metric = false;
            }
          else
            { // we're using a metric different from our last advert
              rte.advert_metric = true;
            }

          updateRoute(prte,&rte);

#ifdef TRIGGER_UPDATE_ON_FRESH_SEQNUM
          trigger_update = true;
#else
          trigger_update = false;
#endif
        }
      else if ( prte->seqnum > rte.seqnum )
        { // our neighbor has older sequnum info than we do
          if (rte.metric == BIG && prte->metric != BIG)
            { // we must go forth and educate this ignorant fellow
              // about our more glorious and happy metric
              prte->advertise_ok_at = now;
              prte->advert_metric = true;
              // directly schedule a triggered update now for 
              // prte, since the other logic only works with rte.*
              needTriggeredUpdate(prte,now);
            }
          else
            { // we don't care about their stale info
            }
        }
      else
        {
          fprintf(stderr,
                  "%s DFU: unhandled adding a route entry?\n", __FILE__);
          abort();
        }
      
      if (trigger_update)
        {
          prte = table_->GetEntry (rte.dst);
          assert(prte != NULL && prte->advertise_ok_at == rte.advertise_ok_at);
          needTriggeredUpdate(prte, prte->advertise_ok_at);
        }

      // see if we can send off any packets we've got queued
      if (rte.q && rte.metric != BIG)
        {
          Packet *queued_p;
          while ((queued_p = rte.q->deque()))
          // XXX possible loop here  
          // while ((queued_p = rte.q->deque()))
          // Only retry once to avoid looping
          // for (int jj = 0; jj < rte.q->length(); jj++){
          //  queued_p = rte.q->deque();
            recv(queued_p, 0); // give the packets to ourselves to forward
          // }
          delete rte.q;
          rte.q = 0;
          table_->AddEntry(rte); // record the now zero'd queue
        }
    } // end of all destination mentioned in routing update packet

  // Reschedule the timeout for this neighbor
  prte = table_->GetEntry(Address::instance().get_nodeaddr(iph->saddr()));
  if (prte)
    {
      if (prte->timeout_event)
        s.cancel (prte->timeout_event);
      else
        {
          prte->timeout_event = new Event ();
        }
      
      s.schedule (helper_, prte->timeout_event, min_update_periods_ * perup_);
    }
  else
    { // If the first thing we hear from a node is a triggered update
      // that doesn't list the node sending the update as the first
      // thing in the packet (which is disrecommended by the paper)
      // we won't have a route to that node already.  In order to timeout
      // the routes we just learned, we need a harmless route to keep the
      // timeout metadata straight.
      
      // Hi there, nice to meet you. I'll make a fake advertisement
      bzero(&rte, sizeof(rte));
      rte.dst = Address::instance().get_nodeaddr(iph->saddr());
      rte.hop = Address::instance().get_nodeaddr(iph->saddr());
      rte.metric = 1;
      rte.seqnum = 0;
      rte.advertise_ok_at = now + 604800;       // check back next week... :)
      
      rte.changed_at = now;
      rte.new_seqnum_at = now;
      rte.wst = wst0_;
      rte.timeout_event = new Event ();
      rte.q = 0;
      
      updateRoute(NULL, &rte);
      s.schedule(helper_, rte.timeout_event, min_update_periods_ * perup_);
    }
  
  /*
   * Freeing a routing layer packet --> don't need to
   * call drop here.
   */
  Packet::free (p);

}

int 
DSDV_Agent::diff_subnet(int dst) 
{
        char* dstnet = Address::instance().get_subnetaddr(dst);
        if (subnet_ != NULL) {
                if (dstnet != NULL) {
                        if (strcmp(dstnet, subnet_) != 0) {
                                delete [] dstnet;
                                return 1;
                        }
                        delete [] dstnet;
                }
        }
        //assert(dstnet == NULL);
        return 0;
}



void
DSDV_Agent::forwardPacket (Packet * p)
{
  hdr_ip *iph = HDR_IP(p);
  Scheduler & s = Scheduler::instance ();
  double now = s.clock ();
  hdr_cmn *hdrc = HDR_CMN (p);
  int dst;
  rtable_ent *prte;
  
  // We should route it.
  //printf("(%d)-->forwardig pkt\n",myaddr_);
  // set direction of pkt to -1 , i.e downward
  hdrc->direction() = hdr_cmn::DOWN;

  // if the destination is outside mobilenode's domain
  // forward it to base_stn node
  // Note: pkt is not buffered if route to base_stn is unknown

  dst = Address::instance().get_nodeaddr(iph->daddr());  
  if (diff_subnet(iph->daddr())) {
           prte = table_->GetEntry (dst);
          if (prte && prte->metric != BIG) 
                  goto send;
          
          //int dst = (node_->base_stn())->address();
          dst = node_->base_stn();
          prte = table_->GetEntry (dst);
          if (prte && prte->metric != BIG) 
                  goto send;
          
          else {
                  //drop pkt with warning
                  fprintf(stderr, "warning: Route to base_stn not known: dropping pkt\n");
                  Packet::free(p);
                  return;
          }
  }
  
  prte = table_->GetEntry (dst);
  
  //  trace("VDEBUG-RX %d %d->%d %d %d 0x%08x 0x%08x %d %d", 
  //  myaddr_, iph->src(), iph->dst(), hdrc->next_hop_, hdrc->addr_type_,
  //  hdrc->xmit_failure_, hdrc->xmit_failure_data_,
  //  hdrc->num_forwards_, hdrc->opt_num_forwards);

  if (prte && prte->metric != BIG)
    {
       //printf("(%d)-have route for dst\n",myaddr_);
       goto send;
    }
  else if (prte)
    { /* must queue the packet */
            //printf("(%d)-no route, queue pkt\n",myaddr_);
      if (!prte->q)
        {
          prte->q = new PacketQueue ();
        }

      prte->q->enque(p);

      if (verbose_)
        trace ("VBP %.5f _%d_ %d:%d -> %d:%d", now, myaddr_, iph->saddr(),
               iph->sport(), iph->daddr(), iph->dport());

      while (prte->q->length () > MAX_QUEUE_LENGTH)
              drop (prte->q->deque (), DROP_RTR_QFULL);
      return;
    }
  else
    { // Brand new destination
      rtable_ent rte;
      double now = s.clock();
      
      bzero(&rte, sizeof(rte));
      rte.dst = dst;
      rte.hop = dst;
      rte.metric = BIG;
      rte.seqnum = 0;

      rte.advertise_ok_at = now + 604800;       // check back next week... :)
      rte.changed_at = now;
      rte.new_seqnum_at = now;  // was now + wst0_, why??? XXX -dam
      rte.wst = wst0_;
      rte.timeout_event = 0;

      rte.q = new PacketQueue();
      rte.q->enque(p);
          
      assert (rte.q->length() == 1 && 1 <= MAX_QUEUE_LENGTH);
      table_->AddEntry(rte);
      
      if (verbose_)
              trace ("VBP %.5f _%d_ %d:%d -> %d:%d", now, myaddr_,
                     iph->saddr(), iph->sport(), iph->daddr(), iph->dport());
      return;
    }


 send:
  hdrc->addr_type_ = NS_AF_INET;
  hdrc->xmit_failure_ = mac_callback;
  hdrc->xmit_failure_data_ = this;
  if (prte->metric > 1)
          hdrc->next_hop_ = prte->hop;
  else
          hdrc->next_hop_ = dst;
  if (verbose_)
          trace ("Routing pkts outside domain: \
VFP %.5f _%d_ %d:%d -> %d:%d", now, myaddr_, iph->saddr(),
                 iph->sport(), iph->daddr(), iph->dport());  

  assert (!HDR_CMN (p)->xmit_failure_ ||
          HDR_CMN (p)->xmit_failure_ == mac_callback);
  target_->recv(p, (Handler *)0);
  return;
  
}

void 
DSDV_Agent::sendOutBCastPkt(Packet *p)
{
  Scheduler & s = Scheduler::instance ();
  // send out bcast pkt with jitter to avoid sync
  s.schedule (target_, p, jitter(DSDV_BROADCAST_JITTER, be_random_));
}


void
DSDV_Agent::recv (Packet * p, Handler *)
{
  hdr_ip *iph = HDR_IP(p);
  hdr_cmn *cmh = HDR_CMN(p);
  int src = Address::instance().get_nodeaddr(iph->saddr());
  int dst = cmh->next_hop();
  /*
   *  Must be a packet I'm originating...
   */
  if(src == myaddr_ && cmh->num_forwards() == 0) {
    /*
     * Add the IP Header
     */
    cmh->size() += IP_HDR_LEN;    
    iph->ttl_ = IP_DEF_TTL;
  }
  /*
   *  I received a packet that I sent.  Probably
   *  a routing loop.
   */
  else if(src == myaddr_) {
    drop(p, DROP_RTR_ROUTE_LOOP);
    return;
  }
  /*
   *  Packet I'm forwarding...
   */
  else {
    /*
     *  Check the TTL.  If it is zero, then discard.
     */
    if(--iph->ttl_ == 0) {
      drop(p, DROP_RTR_TTL);
      return;
    }
  }
  
  if ((src != myaddr_) && (iph->dport() == ROUTER_PORT))
    {
            // XXX disable this feature for mobileIP where
            // the MH and FA (belonging to diff domains)
            // communicate with each other.

            // Drop pkt if rtg update from some other domain:
            // if (diff_subnet(iph->src())) 
            // drop(p, DROP_OUTSIDE_SUBNET);
            //else    
            processUpdate(p);
    }
  else if ((u_int32_t) dst == IP_BROADCAST && 
           (iph->dport() != ROUTER_PORT)) 
          {
             if (src == myaddr_) {
                     // handle brdcast pkt
                     sendOutBCastPkt(p);
             }
             else {
                     // hand it over to the port-demux
                    
                    port_dmux_->recv(p, (Handler*)0);
             }
          }
  else 
    {
            forwardPacket(p);
    }
}

static class DSDVClass:public TclClass
{
  public:
  DSDVClass ():TclClass ("Agent/DSDV")
  {
  }
  TclObject *create (int, const char *const *)
  {
    return (new DSDV_Agent ());
  }
} class_dsdv;

DSDV_Agent::DSDV_Agent (): Agent (PT_MESSAGE), ll_queue (0), seqno_ (0), 
  myaddr_ (0), subnet_ (0), node_ (0), port_dmux_(0),
  periodic_callback_ (0), be_random_ (1), 
  use_mac_ (0), verbose_ (1), trace_wst_ (0), lasttup_ (-10), 
  alpha_ (0.875),  wst0_ (6), perup_ (15), 
  min_update_periods_ (3)       // constants
 {
  table_ = new RoutingTable ();
  helper_ = new DSDV_Helper (this);
  trigger_handler = new DSDVTriggerHandler(this);

  bind_time ("wst0_", &wst0_);
  bind_time ("perup_", &perup_);

  bind ("use_mac_", &use_mac_);
  bind ("be_random_", &be_random_);
  bind ("alpha_", &alpha_);
  bind ("min_update_periods_", &min_update_periods_);
  bind ("verbose_", &verbose_);
  bind ("trace_wst_", &trace_wst_);
  //DEBUG
  address = 0;
 
}

void
DSDV_Agent::startUp()
{
 Time now = Scheduler::instance().clock();

  subnet_ = Address::instance().get_subnetaddr(myaddr_);
  //DEBUG
  address = Address::instance().print_nodeaddr(myaddr_);
  //printf("myaddress: %d -> %s\n",myaddr_,address);
  
  rtable_ent rte;
  bzero(&rte, sizeof(rte));

  rte.dst = myaddr_;
  rte.hop = myaddr_;
  rte.metric = 0;
  rte.seqnum = seqno_;
  seqno_ += 2;

  rte.advertise_ok_at = 0.0; // can always advert ourselves
  rte.advert_seqnum = true;
  rte.advert_metric = true;
  rte.changed_at = now;
  rte.new_seqnum_at = now;
  rte.wst = 0;
  rte.timeout_event = 0;                // Don't time out our localhost :)
  
  rte.q = 0;            // Don't buffer pkts for self!
  
  table_->AddEntry (rte);

  // kick off periodic advertisments
  periodic_callback_ = new Event ();
  Scheduler::instance ().schedule (helper_, 
                                   periodic_callback_,
                                   jitter (DSDV_STARTUP_JITTER, be_random_));
}

int 
DSDV_Agent::command (int argc, const char *const *argv)
{
  if (argc == 2)
    {
      if (strcmp (argv[1], "start-dsdv") == 0)
        {
          startUp();
          return (TCL_OK);
        }
      else if (strcmp (argv[1], "dumprtab") == 0)
        {
          Packet *p2 = allocpkt ();
          hdr_ip *iph2 = HDR_IP(p2);
          rtable_ent *prte;

          printf ("Table Dump %d[%d]\n----------------------------------\n",
                  iph2->saddr(), iph2->sport());
        trace ("VTD %.5f %d:%d\n", Scheduler::instance ().clock (),
                 iph2->saddr(), iph2->sport());

          /*
           * Freeing a routing layer packet --> don't need to
           * call drop here.
           */
        Packet::free (p2);

          for (table_->InitLoop (); (prte = table_->NextLoop ());)
            output_rte ("\t", prte, this);

          printf ("\n");

          return (TCL_OK);
        }
      else if (strcasecmp (argv[1], "ll-queue") == 0)
        {
        if (!(ll_queue = (PriQueue *) TclObject::lookup (argv[2])))
            {
              fprintf (stderr, "DSDV_Agent: ll-queue lookup of %s failed\n", argv[2]);
              return TCL_ERROR;
            }

          return TCL_OK;
        }

    }
  else if (argc == 3)
    {
      if (strcasecmp (argv[1], "addr") == 0) {
         int temp;
         temp = Address::instance().str2addr(argv[2]);
         myaddr_ = temp;
         return TCL_OK;
      }
      TclObject *obj;
      if ((obj = TclObject::lookup (argv[2])) == 0)
        {
          fprintf (stderr, "%s: %s lookup of %s failed\n", __FILE__, argv[1],
                   argv[2]);
          return TCL_ERROR;
        }
      if (strcasecmp (argv[1], "tracetarget") == 0)
        {
          
          tracetarget = (Trace *) obj;
          return TCL_OK;
        }
      else if (strcasecmp (argv[1], "node") == 0) {
              node_ = (MobileNode*) obj;
              return TCL_OK;
      }
      else if (strcasecmp (argv[1], "port-dmux") == 0) {
              port_dmux_ = (NsObject *) obj;
              return TCL_OK;
      }
    }
  
  return (Agent::command (argc, argv));
}

---