dsdv.cc

动态网络路由协议

      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)); ---how about 100++ node topologies

  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_);