tora.cc

一个EPI路由协议的实现

/*
 * Modified by Felix Hernandez-Campos ([e-mail])
 * during the porting and extension of Duke's Epidemic Routing  
 * implementation (by Amin Vahdat and David Becker)
 *
 * Fall 2000
 */

/* -*-  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
 *
 * $Header: /nfs/jade/vint/CVSROOT/ns-2/tora/tora.cc,v 1.12 2000/09/01 03:04:12 haoboy Exp $
 */

#include <agent.h>
#include <random.h>
#include <trace.h>

#include <ll.h>
#include <priqueue.h>
#include <tora/tora_packet.h>
#include <tora/tora.h>

#define LOG(s)							\
	fprintf(stdout, "%s --- %s (index: %d, time: %f)\n",	\
		__PRETTY_FUNCTION__, (s), index, Scheduler::instance().clock())

// --- EPIC ----------------------------------------------------------- [Felix]

//#define DEBUG

//#define SHOWALL

int debug_fname = 0;
int debug_recv  = 0;
int debug_drop  = 0;
int debug_loop  = 0;

// --- end of EPIC ---------------------------------------------------- [Felix]

#define	CURRENT_TIME	Scheduler::instance().clock()   //我需要哈哈~~~

/* sec of spacing inserted between pkts when a bunch of packets are
   dumped into the link layer all at once.  Allows arp time to resolve
   dst, preventing the dumping of all but the last pkt on the floor */
#define ARP_SEPARATION_DELAY 0.030
	  

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

// Added in NS [Felix]
int hdr_tora::offset_;

static class TORAHeaderClass : public PacketHeaderClass {
public:
        TORAHeaderClass() : PacketHeaderClass("PacketHeader/TORA",
					      TORA_HDR_LEN) { 
		// Added in NS [Felix]
		bind_offset(&hdr_tora::offset_);
	} 
} class_toraAgent_hdr;

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


/* ======================================================================
   toraAgent Class Functions
   ====================================================================== */
toraAgent::toraAgent(nsaddr_t id) :
	rtAgent(id, PT_TORA),
	rqueue()
{
	// --- EPIC --------------------------------------------------- [Felix]

	// LIST_INIT(&dstlist);
	//	bind("off_TORA_", &off_TORA_);
	bind("opt_qlen_", &opt_qlen_);    //绑定变量 qlen；
	bind("opt_hops_", &opt_hops_);    //绑定变量 hops；
	LIST_INIT(&dstlist);              //初始化dstlist；
	LIST_INIT(&nblist);               //初始化nblist；
	LIST_INIT(&copylist);             //初始化copylist；

	// TO DO: get rid of this variable and use only hdr_tora::offset
	// or equivalent (see ip.h) [Felix]
	off_TORA_ = hdr_tora::offset_;

#ifdef HASH
	for(int i=0; i<COPYTABLELEN; ++i) LIST_INIT(copytable+i);   //初始化 copytable；
	for(u_int i=0; i<SUMMSIZE; ++i) prevask[i]=ihave[i]=0;       //初始化自身和前一ask的SUMMARYVECTOR；
#endif

	nbcnt=0;
	previhave=-1;
	prevdest=-1;
	prevnb=-1;
	prevupd=-1;
	fwdqcnt = 0;

	// --- end of EPIC -------------------------------------------- [Felix]

	imepagent = 0;
	logtarget = 0;
	ifqueue = 0;
}

void
toraAgent::reset()
{
	if (debug_fname) trace("CALL %d reset() - %g", ipaddr(), Scheduler::instance().clock());

	Packet *p;
	while((p = rqueue.deque())) {
		if (debug_drop) trace("drop end of simulation");
		drop(p,DROP_END_OF_SIMULATION);
	}

	// --- EPIC --------------------------------------------------- [Felix]似乎是显示还有多少个节点以及对应报文。

	trace("NN %.9f _%d_ end of node.", CURRENT_TIME, ipaddr());
#ifndef TTL
	EPIpkt* ep;
	for(ep = copylist.lh_first ; ep; ep = ep->link.le_next) {         //copylist.le_first?
		struct hdr_epi *eh = HDR_EPI(ep->packet);
		if (eh->copies_allowed>0)
			trace("NN %.9f _%d_ pkt 0x%x %d copies left",
			      CURRENT_TIME, ipaddr(), eh->id, eh->copies_allowed);
  	}
#endif
	trace("NN %.9f _%d_ infected by %d fwdqcnt msgs and %d neighbors",
	      CURRENT_TIME, ipaddr(), fwdqcnt, nbcnt);

	// --- end of EPIC -------------------------------------------- [Felix]

	if (debug_fname) trace("CALL %d end of reset() - %g", ipaddr(), Scheduler::instance().clock());
}

int
toraAgent::command(int argc, const char*const* argv)
{
	if (debug_fname) trace("CALL %d command() - %g", ipaddr(), Scheduler::instance().clock());
	
	if(argc == 2) {
		Tcl& tcl = Tcl::instance();

		if(strncasecmp(argv[1], "id", 2) == 0) {
			tcl.resultf("%d", index);
			return TCL_OK;
		}
		// [Felix]
		else if(strcmp(argv[1], "nbcount") == 0) {
			int *nbs, nbc;
			imepagent->imepGetBiLinks(nbs, nbc);
			tcl.resultf("%d", nbc);
			return TCL_OK;
		}
	}
	else if(argc == 3) {

		if(strcmp(argv[1], "log-target") == 0 
		   || strcmp(argv[1], "tracetarget") == 0 ) {
			logtarget = (Trace*) TclObject::lookup(argv[2]);
			if(logtarget == 0)
				return TCL_ERROR;
			return TCL_OK;
		}
		else if(strcmp(argv[1], "drop-target") == 0) {
		        int stat = rqueue.command(argc,argv);
			if (stat != TCL_OK) return stat;
                	return Agent::command(argc, argv);
		}
		else if(strcmp(argv[1], "if-queue") == 0) {
			ifqueue = (PriQueue*) TclObject::lookup(argv[2]);
			if(ifqueue == 0)
				return TCL_ERROR;
			return TCL_OK;
		}
		else if(strcmp(argv[1], "imep-agent") == 0) {
			imepagent = (imepAgent*) TclObject::lookup(argv[2]);
			if(imepagent == 0)
				return TCL_ERROR;
			imepagent->imepRegister((rtAgent*) this);
			return TCL_OK;
		}
	}

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


/* ======================================================================
   Destination Management Functions
   ====================================================================== */
TORADest*
toraAgent::dst_find(nsaddr_t id)
{
	if (debug_fname) trace("CALL %d dst_find() - %g", ipaddr(), Scheduler::instance().clock());

	TORADest* td = dstlist.lh_first;
	for( ; td; td = td->link.le_next) {
		if(td->index == id)
			return td;
	}
	return 0;

	if (debug_fname) trace("CALL %d end of dst_find() - %g", ipaddr(), Scheduler::instance().clock());
}

TORADest*
toraAgent::dst_add(nsaddr_t id)      //寻找dst；
{
	if (debug_fname) trace("CALL %d dst_add() - %g", ipaddr(), Scheduler::instance().clock());

	TORADest *td = new TORADest(id, this);
	assert(td);

	LIST_INSERT_HEAD(&dstlist, td, link);

	int *nblist = 0, nbcnt = 0;
	imepagent->imepGetBiLinks(nblist, nbcnt);

	for(int i = 0; i < nbcnt; i++)
		(void) td->nb_add(nblist[i]);

	if(nblist) delete[] nblist;

	if (debug_fname) trace("CALL %d end of dst_add() - %g", ipaddr(), Scheduler::instance().clock());

	return td;
}

void
toraAgent::dst_dump()     //？
{
	if (debug_fname) trace("CALL %d dst_dump() - %g", ipaddr(), Scheduler::instance().clock());

	TORADest *td = dstlist.lh_first;

	for( ; td; td = td = td->link.le_next)
		td->dump();

	if (debug_fname) trace("CALL %d end of dst_dump() - %g", ipaddr(), Scheduler::instance().clock());
}


/* ======================================================================
   Route Resolution
   ====================================================================== */

// --- EPIC -------------------------------------------- [Felix]

// #define ASK
// #define BLIND
#define TTL

// --- end of EPIC -------------------------------------------- [Felix]

// Send a packet (schedule the packet, so the receiver handles it at the 
// time it reaches the destination)

// Removed in NS: Time delay = 0.0 [Felix]
void
toraAgent::forward(Packet *p, nsaddr_t nexthop, Time delay)
{
	if (debug_fname) trace("CALL %d forward() nx_h %d t %g - %g", 
			       ipaddr(), nexthop, delay, 
			       Scheduler::instance().clock());

        struct hdr_cmn *ch = HDR_CMN(p);

#ifdef TORA_DISALLOW_ROUTE_LOOP
        if(nexthop == ch->prev_hop_) {
		log_route_loop(ch->prev_hop_, nexthop);

		if (debug_fname)  
			trace("forward() - %g drop at %d (next %d prev %d)",
			      Scheduler::instance().clock(),
			      ipaddr(), nexthop, ch->prev_hop_);

		if (debug_drop) trace("drop forward()");
                drop(p, DROP_RTR_ROUTE_LOOP);
                return;
        }
#endif
        ch->next_hop() = nexthop;
        ch->prev_hop_ = ipaddr();
        ch->addr_type() = NS_AF_INET;

	// Added in NS [Felix]
	// change the packet direction to DOWN
	ch->direction() = hdr_cmn::DOWN;

	if (0.0 == delay) {
		tora_output(p);
	} else {
		Scheduler::instance().schedule(target_, p, delay);
	}

	if (debug_fname) trace("CALL %d end of forward() - %g", ipaddr(), Scheduler::instance().clock());
}

// --- EPIC ----------------------------------------------------------- [Felix]

// set hitme on neighbors not in the node_hit array, return a count of them
int toraAgent::set_dest(struct hdr_epi *eh, int *dests)
{
	if (debug_fname) trace("CALL %d set_dest() - %g", ipaddr(), Scheduler::instance().clock());

	TORADest *td;
	int to_cnt = 0;
        for(td = nblist.lh_first ; td; td = td->link.le_next) {
		dests[to_cnt++] = td->index; 
#ifdef BLIND
		for(int i=0; i<eh->hits; ++i)
			if (td->index==eh->node_hit[i]) {
				--to_cnt;
				break;
				}
#endif
		}

	if (debug_fname) trace("CALL %d end of set_dest() - %g", ipaddr(), Scheduler::instance().clock());

	return to_cnt;
}

// if p in copylist, merge [BLIND: hitlist and ] copies_allowed and
//	return the copy node already has,
// otherwise add p to copylist.
Packet* toraAgent::update_copylist(Packet *p)
{
	if (debug_fname) trace("CALL %d update_copylist() - %g", ipaddr(), Scheduler::instance().clock());

	struct hdr_epi *eh = HDR_EPI(p);
	EPIpkt* ep;
	int newpkt=1;
#ifdef HASH
	update_copytable(p);
#endif
        for(ep = copylist.lh_first ; ep; ep = ep->link.le_next) {
		Packet *k = ep->packet;
		struct hdr_epi *kh = HDR_EPI(k);
		if (eh->id==kh->id) {
			newpkt=0;
#ifdef DEBUG
			trace("T %.9f _%d_ epimatch 0x%x copies now %d",
			      Scheduler::instance().clock(), ipaddr(), eh->id,
			      kh->copies_allowed);
#endif

#ifdef BLIND
			// merge hit list
			for(int i=0; i<eh->hits; ++i) {
				int j;
				for(j=0; j<kh->hits; ++j)
					if (eh->node_hit[i]==kh->node_hit[j])
						break;
				if (j==kh->hits)
					kh->node_hit[kh->hits++] = eh->node_hit[i];
				}
#endif

			kh->copies_allowed += eh->copies_allowed+1;
			Packet::free(p);

			// continue with packet from list instead
			p = k;
			break;
			}
		}

	// Otherwise