dsdv.cc

在Linux下做的QuadTree的程序

  char buf[1024];
  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 : -1, new_rte->metric, 
	    old_rte ? old_rte->seqnum : -1,  new_rte->seqnum,
	    old_rte ? old_rte->hop : -1,  new_rte->hop, 
	    new_rte->advertise_ok_at);
  
  table_->AddEntry (*new_rte);

  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->access (off_ip_);
  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
         printf("Received DSDV packet from %d(%d) to %d(%d) [%d(%d)]\n", 
         iph->src_, iph->sport_, iph->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++);

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

      rte.dst = dst;
      rte.hop = iph->src_;
      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()))
	    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 (iph->src_);
  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 = iph->src_;
      rte.hop = iph->src_;
      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);
}

void
DSDV_Agent::forwardPacket (Packet * p)
{
  hdr_ip *iph = (hdr_ip *) p->access (off_ip_);
  Scheduler & s = Scheduler::instance ();
  double now = s.clock ();

  // We should route it.
  hdr_cmn *hdrc = HDR_CMN (p);
  rtable_ent *prte = table_->GetEntry (iph->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)
    {
      hdrc->addr_type_ = 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_ = iph->dst_;

      if (verbose_)
	trace ("VFP %.5f _%d_ %d:%d -> %d:%d", now, myaddr_, iph->src_,
	       iph->sport_, iph->dst_, iph->dport_);

      //trace("VDEBUG-TX %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);

      assert (!HDR_CMN(p)->xmit_failure_ ||
	      HDR_CMN(p)->xmit_failure_ == mac_callback);	// DEBUG 0x2

      target_->recv(p, (Handler *)0);
    }
  else if (prte)
    { /* must queue the packet */
      if (!prte->q)
	{
	  prte->q = new PacketQueue();
	}

      prte->q->enque(p);

      if (verbose_)
	trace ("VBP %.5f _%d_ %d:%d -> %d:%d", now, myaddr_, iph->src_,
	       iph->sport_, iph->dst_, iph->dport_);

      while (prte->q->length() > MAX_QUEUE_LENGTH)
	drop (prte->q->deque(), DROP_RTR_QFULL);
    }
  else
    { // Brand new destination
      rtable_ent rte;
      double now = s.clock();
      
      bzero(&rte, sizeof(rte));
      rte.dst = iph->dst_;
      rte.hop = iph->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->src_,
	       iph->sport_, iph->dst_, iph->dport_);
    }

}

void
DSDV_Agent::recv (Packet * p, Handler *)
{
  hdr_ip *iph = (hdr_ip *) p->access (off_ip_);
  hdr_cmn *cmh = (hdr_cmn *) p->access (off_cmn_);

  /*
   *  Must be a packet I'm originating...
   */
  if(iph->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(iph->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 ((iph->src_ != myaddr_) && (iph->dport_ == ROUTER_PORT))
    {
      processUpdate(p);
    }
  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), 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 ("myaddr_", &myaddr_);
  bind ("verbose_", &verbose_);
  bind ("trace_wst_", &trace_wst_);
  
}

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

  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->access (off_ip_);
	  rtable_ent *prte;

	  printf ("Table Dump %d[%d]\n----------------------------------\n",
		  iph2->src_, iph2->sport_);
	trace ("VTD %.5f %d:%d\n", Scheduler::instance ().clock (),
		 iph2->src_, 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], "tracetarget") == 0)
	{
	  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;
	    }
	  tracetarget = (Trace *) obj;
	  return TCL_OK;
	}
    }

return (Agent::command (argc, argv));
}