imep.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 */


/*
  imep.cc
  $Id: imep.cc,v 1.8 1999/10/13 22:53:05 heideman Exp $
  */

#include <packet.h>
#include <ip.h>
#include <random.h>

#include <cmu-trace.h>
#include <imep/imep.h>

#define CURRENT_TIME	Scheduler::instance().clock()

static const int verbose = 0;
static const int imep_use_mac_callback = 1;

// ======================================================================
//   TCL Hooks
// ======================================================================

static class IMEPHeaderClass : public PacketHeaderClass {
public:
        IMEPHeaderClass() : PacketHeaderClass("PacketHeader/IMEP",
					      IMEP_HDR_LEN) { } 
} class_imep_hdr;

static class agentIMEPclass : public TclClass {
public:
	agentIMEPclass() : TclClass("Agent/IMEP") {}
	TclObject* create(int argc, const char*const* argv) {
		assert(argc == 5);
		return (new imepAgent((nsaddr_t) atoi(argv[4])));
	}
} class_imepAgent;


// ======================================================================
// ======================================================================

// MAC layer callback
static void
imep_failed_callback(Packet *p, void *arg)
{
	if(imep_use_mac_callback)
		((imepAgent*) arg)->imepPacketUndeliverable(p);
	else {
		Packet::free(p);
		// XXX: Should probably call a "drop" agent here
	}
}

imepAgent::imepAgent(nsaddr_t index) :
	Agent(PT_TORA),
	beaconTimer(this, BEACON_TIMER),
	controlTimer(this, CONTROL_TIMER),
	rexmitTimer(this, REXMIT_TIMER),
	incomingTimer(this, INCOMING_TIMER),
	ipaddr(index),
	incomingQ(this, index)
{
	bind("off_IMEP_", &off_IMEP_);
	bind("off_TORA_", &off_TORA_);
	controlSequence = 0;
	recvtarget_ = sendtarget_ = 0;
	logtarget_ = 0;
	rtagent_ = 0;
	LIST_INIT(&imepLinkHead);
	bzero(&stats, sizeof(stats));
}

int
imepAgent::command(int argc, const char*const* argv)
{
	if(argc == 2) {
		if(strcmp(argv[1], "start") == 0) {
			beaconTimer.start(BEACON_PERIOD);
			return TCL_OK;
		} 
		else if(strcmp(argv[1], "reset") == 0) {
		        Terminate();
			return TCL_OK;
		}
	} else if (argc == 3) {
		if (strcmp(argv[1], "recvtarget") == 0) {
			recvtarget_ = (NsObject*) TclObject::lookup(argv[2]);
                        assert(recvtarget_);
			return (TCL_OK);
		}
		else if (strcmp(argv[1], "sendtarget") == 0) {
			sendtarget_ = (NsObject*) TclObject::lookup(argv[2]);
                        assert(sendtarget_);
			return (TCL_OK);
		}
		else if (strcmp(argv[1], "rtagent") == 0) {
			rtagent_ = (rtAgent*) TclObject::lookup(argv[2]);
			assert(rtagent_);
			return (TCL_OK);
		}
		else if(strcmp(argv[1], "log-target") == 0) {
			logtarget_ = (Trace*) TclObject::lookup(argv[2]);
			assert(logtarget_);
			return (TCL_OK);
		}
	}
	return Agent::command(argc, argv);
}


imepLink*
imepAgent::findLink(nsaddr_t index)
{
	imepLink *l;

	for(l = imepLinkHead.lh_first; l; l = l->link.le_next) {
		if(l->index() == index)
			return l;
	}
	return 0;
}

Packet*
imepAgent::findObjectSequence(u_int8_t seqno)
{
        Packet *p;	
	ReXmitQIter iter = rexmitq.iter();
	struct imep_object_block *ob;
	
	while ((p = iter.next())) {
		ob = findObjectBlock(p);

		if(ob == 0) continue;
		// no OBJECT block

		if(ob->ob_sequence != seqno) continue;
		// wrong SEQUENCE number

		if(ob->ob_num_responses <=0) {
			fprintf(stderr,
				"imepAgent::findObjectSequence: "
				"Object Block without response list\n");
			abort();
		}

		return p;
	}

	/*	abort();
		this isn't an abort condition.  consider an ack arriving 
		for a pkt after it's timed out from the rexmit q -dam */

	return NULL;
}


void
imepAgent::removeObjectResponse(Packet *p, nsaddr_t index)
{
	struct imep_object_block *ob = findObjectBlock(p);
	struct imep_response *r = findResponseList(p);
	struct imep_response *r0;
	struct hdr_cmn *ch = HDR_CMN(p);
	int i;

	assert(ob && r);

	for(i = 0, r0 = r; i < ob->ob_num_responses; i++, r0++) {
		if(INT32_T(r0->resp_ipaddr) == index)
			break;
	}

	if(INT32_T(r0->resp_ipaddr) != index) {
	  if (verbose) 
	    trace("T %.9f _%d_ dup ack(?) from %d", CURRENT_TIME, ipaddr, index);
	  return;
	}

	if(ob->ob_num_responses == 1) {
	        if (verbose) 
	           trace("T %.9f _%d_ remove from reXq pkt %d", 
		         CURRENT_TIME, ipaddr, ch->uid());
	        rexmitq.remove(p);
	        Packet::free(p);
		stats.num_rexmitable_fully_acked++;
	} else {
		// find the last "response"
  	        r += (ob->ob_num_responses - 1);

		if(r != r0) {
			INT32_T(r0->resp_ipaddr) = INT32_T(r->resp_ipaddr);
		}
		
		ob->ob_num_responses -= 1;			

	        if (verbose) 
	           trace("T %.9f _%d_ remove %d from resp list %d (%d left) RL %s", 
		         CURRENT_TIME, ipaddr, index, ch->uid(), ob->ob_num_responses, 
			 dumpResponseList(p));

		struct hdr_imep *im = HDR_IMEP(p);
		ch->size() -= sizeof(struct imep_response);
		U_INT16_T(im->imep_length) -= sizeof(struct imep_response);
	}
}


void 
imepAgent::purgeReXmitQ(nsaddr_t index)
  // remove index from any response lists in the rexmit q
{
  Packet *p;	
  ReXmitQIter iter = rexmitq.iter();
  struct imep_object_block *ob;
  struct imep_response *r,*r0;
  struct hdr_cmn *ch;
  int i;

  if (verbose)
    trace("T %.9f _%d_ purge %d from reXmit Q", 
	  CURRENT_TIME, ipaddr, index);

  while ((p = iter.next())) {
    ob = findObjectBlock(p);
    if(ob == 0) assert(0); // should always be an object block

    r = findResponseList(p);
    ch = HDR_CMN(p);

    assert(ob && r);

    for(i = 0, r0 = r; i < ob->ob_num_responses; i++, r0++) {
      if(INT32_T(r0->resp_ipaddr) == index)
	break;
    }

    if(INT32_T(r0->resp_ipaddr) != index) {
      continue; // index not in this response list
    }

    if(ob->ob_num_responses == 1) {
      if (verbose) 
	trace("T %.9f _%d_ remove from reXq pkt %d",
	      CURRENT_TIME, ipaddr, ch->uid());
      rexmitq.remove(p);
      drop(p, DROP_RTR_QTIMEOUT);
      stats.num_rexmitable_fully_acked++;
    } else {
      // find the last "response"
      r += (ob->ob_num_responses - 1);

      if(r != r0) {
	INT32_T(r0->resp_ipaddr) = INT32_T(r->resp_ipaddr);
      }
		
      ob->ob_num_responses -= 1;			

      if (verbose) 
	trace("T %.9f _%d_ purge %d from resp list %d (%d left) RL %s", 
	      CURRENT_TIME, ipaddr, index, ch->uid(), ob->ob_num_responses, 
	      dumpResponseList(p));

      struct hdr_imep *im = HDR_IMEP(p);
      ch->size() -= sizeof(struct imep_response);
      U_INT16_T(im->imep_length) -= sizeof(struct imep_response);
    }
  }
}


// ======================================================================
// ======================================================================
// Timer Handling Functions

void
imepAgent::handlerTimer(imepTimerType t)
{
	switch(t) {
	case BEACON_TIMER:
		handlerBeaconTimer();
		break;
	case CONTROL_TIMER:
		handlerControlTimer();
		break;
	case REXMIT_TIMER:
	        handlerReXmitTimer();
		break;
	case INCOMING_TIMER:
		handlerIncomingTimer();
		break;
	default:
		abort();
	}
}

void
imepAgent::handlerBeaconTimer(void)
{
  imepLink *l;

  // garbage collect old links
  purgeLink();

  if (verbose) log_neighbor_list();

  /* aside from the debugging asserts, handleControlTimer will generate a
   ``beacon'' packet if there are no objects pending, so we could
   just call it.  Since we have sendBeacon() laying around, though, 
   I'll call it and leave the debugging asserts in handleControlTimer()

   The packet generated by handlerControlTimer is a beacon equivelent, 
   so we don't need to generate a beacon. */

  if (controlTimer.busy() || helloQueue.length() > 0)
    { // a control timer is pending or there's left over Hello's in the queue, 
      // but we're about to service all pending acks, hellos, and objects now, 
      // so cancel the timer
      if (controlTimer.busy()) controlTimer.cancel();
      handlerControlTimer();
    }
  else 
    { // all the Hellos we had to send out during the last BEACON_PERIOD
      // went out.  Assuming there were some, they were beacon equivelent,
      // and we don't need to send a beacon now.  If there were none, beacon
      if (NULL == imepLinkHead.lh_first) sendBeacon();
      // this is a touch conservative, since if there were hellos that went out
      // but their links were down'd by purgeLink, we'll still beacon.
      // But, if we *have*no* adjacencies, we should do something to get some
    }

  /* Send a hello to all our IN adjacencies (everyone we've heard a
     packet from). This loads up the helloQueue with all the hellos that
     that need to go out sometime in the next BEACON_PERIOD before the
     beaconTimer goes off, but doesn't start the controlTimer.  If a
     control packet is sent for some other reason, the hellos will ride out
     for free, otherwise they'll go out when the beacon timer goes off.
     */
  int busy_before_hello_load = controlTimer.busy();
  for(l = imepLinkHead.lh_first; l; l = l->link.le_next) 
    {
      if (l->status() & LINK_IN) sendHello(l->index());
    }
  if (!busy_before_hello_load && controlTimer.busy()) controlTimer.cancel();

  // restart the beacon timer
  beaconTimer.start(BEACON_PERIOD);
}


// transmit all queued ACKs, HELLOs, and OBJECTs.
void
imepAgent::handlerControlTimer(void)
{
	Packet *p;

	int num_acks = ackQueue.length();
	int num_hellos = helloQueue.length();
	int num_objects = objectQueue.length();

MAKE_PACKET:
	assert(num_acks + num_hellos + num_objects > 0);

	// now have to aggregate multiple control packets

	p = Packet::alloc();
	
	struct hdr_cmn *ch = HDR_CMN(p);
	struct hdr_ip *ih = HDR_IP(p);
	struct hdr_imep *im = HDR_IMEP(p);

	ch->uid() = uidcnt_++;
	ch->ptype() = PT_IMEP;
	ch->size() = BEACON_HDR_LEN;
	ch->iface() = -2;
	ch->error() = 0;
	ch->addr_type() = NS_AF_NONE;
        ch->prev_hop_ = ipaddr;

	ih->saddr() = ipaddr;
	ih->daddr() = IP_BROADCAST;
	ih->sport() = RT_PORT;
	ih->dport() = RT_PORT;
	ih->ttl_ = 1;

	im->imep_version = IMEP_VERSION;
	im->imep_block_flags = 0x00;
	U_INT16_T(im->imep_length) = sizeof(struct hdr_imep);

	aggregateAckBlock(p);
	aggregateHelloBlock(p);
	aggregateObjectBlock(p);

	imep_output(p);

	num_acks = ackQueue.length();
	num_hellos = helloQueue.length();
	num_objects = objectQueue.length();
	if (num_acks + num_hellos + num_objects > 0)
	  { // not done yet...
	    if (verbose) 
	      trace("T %.9f _%d_ imep pkt overflow %d %d %d leftover",
		    CURRENT_TIME, ipaddr, num_acks, num_hellos, num_objects);
	    goto MAKE_PACKET;
	  }

	// don't need to restart the controlTimer because the arrival of
	// the next packet from an ULP will start it.
}

void
imepAgent::handlerReXmitTimer() 
{
  Packet *p;
  Time rexat;
  int num_xmits_left;

  rexmitq.peekHead(&rexat, &p, &num_xmits_left);

  if (NULL == p) return;  //  no more pkts on queue
  struct hdr_cmn *ch = HDR_CMN(p);

  if (0 == num_xmits_left)
    {
      if (verbose) 
	{
	  trace("T %.9f _%d_ rexmit timed out %d RL:%s",
		CURRENT_TIME, ipaddr, ch->uid(), dumpResponseList(p));
	}

        struct imep_object_block *ob = findObjectBlock(p);
	struct imep_response *r = findResponseList(p);
	int i;

	for(i = 0; i < ob->ob_num_responses; i++, r++) 
	  {
	    if (verbose) trace("T %.9f _%d_ punting neighbor %d",
			       CURRENT_TIME, ipaddr, INT32_T(r->resp_ipaddr));
	    imepSetLinkDownStatus(INT32_T(r->resp_ipaddr));
	  }

      stats.num_rexmitable_retired++;
      stats.sum_rexmitable_retired_response_sz += ob->ob_num_responses;


      // don't need to explicitly remove p from q and drop it, since
      // by downing all the links on it's response list, it'll have bee
      // dropped anyway
      // rexmitq.removeHead();
      // drop(p, DROP_RTR_QTIMEOUT);
    }
  else if (rexat <= CURRENT_TIME) 
    {
      if (verbose) 
	trace("T %.9f _%d_ rexmit %d as %d",
	      CURRENT_TIME, ipaddr, ch->uid(), uidcnt_);
      ch->uid() = uidcnt_++;
      imep_output(p->copy());

      num_xmits_left--;
      rexmitq.removeHead(); // take it off the queue and reinsert it
      rexmitq.insert(CURRENT_TIME + RETRANS_PERIOD, p, num_xmits_left);

      stats.num_rexmits++;
    }  
  
  // reschedule the timer
  rexmitq.peekHead(&rexat, &p, &num_xmits_left);
  if (NULL == p) return;  //  no more pkts on queue
  if (verbose) trace("T %.9f _%d_ rexmit trigger again for %d at %.9f (in %.9f)",
		     CURRENT_TIME, ipaddr, ch->uid(), rexat, rexat - CURRENT_TIME );
  rexmitTimer.start(rexat - CURRENT_TIME);
}


void
imepAgent::handlerIncomingTimer()
{
	Packet *p;
	u_int32_t s;
	double expire;
	int index;

	if (verbose) trace("T %.9f _%d_ inorder - timer expired",
	      CURRENT_TIME, ipaddr);

	incomingQ.dumpAll();

	while((p = incomingQ.getNextPacket(s))) {
		stats.num_holes_retired++;
		
		index = HDR_IP(p)->saddr();
		imepLink *l = findLink(index);		
		assert(l);  // if there's no link entry, then the incoming
		// q should have been cleared, when the link entry was destroyed

		if(verbose) 
		  trace("T %.9f _%d_ inorder - src %d hole retired seq %d -> %d",
			CURRENT_TIME, ipaddr, index, l->lastSeq(), s);

		/* tell ULP that we've effectively broken our link to 
		   neighbor by retiring the hole and accepting the deletion.
		   since we don't do this till at least MAX_REXMIT_TIME after
		   receiving the out of seq packet, we're sure the packet's sender
		   must have timed us out when we didn't ack their packet.
		   can't call imepLinkDown b/c it'll purge the reseq q */
		rtagent_->rtNotifyLinkDN(index);
		stats.delete_neighbor3++;
		rtagent_->rtNotifyLinkUP(index);
		stats.new_neighbor++;

		if (verbose)
		  trace("T %.9f _%d_ inorder - src %d seq %d (timer delivery)",
			CURRENT_TIME, ipaddr, index, s);