dsdv.cc

动态网络路由协议

/* -*-	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.25 2005/07/13 03:51:24 tomh 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_);