tora.cc

一个EPI路由协议的实现

	// save packet to infect new neighbors
	if (newpkt) fwdqadd(p);

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

	return p;
}

#ifdef HASH
int toraAgent::epihash(Packet *p)
{
	return HDR_EPI(p)->id & (COPYTABLELEN - 1);
}

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

	struct hdr_epi *eh = HDR_EPI(p);
	int h = epihash(p);

#ifdef DEBUG
	if (SUMMGETBIT(ihave,h)) {
		trace("T %.9f _%d_ hashmatch 0x%x",
		      Scheduler::instance().clock(), ipaddr(), eh->id);
		}
#endif

	SUMMSETBIT(ihave,h);

	EPIpkt* ep;
	int newpkt=1;
        for(ep = copytable[h].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;
			break;
			}
#ifdef DEBUG
		else {
			trace("T %.9f _%d_ buckethit 0x%x",
			      Scheduler::instance().clock(), ipaddr(), eh->id);
			}
#endif
		}

	// Otherwise
	// save packet to infect new neighbors
	if (newpkt) {
		ep =  new EPIpkt(p);
		LIST_INSERT_HEAD(copytable+h, ep, link);
		}

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

	return p;
}
#endif

void toraAgent::traceroute(struct hdr_epi *eh)
{
	if (debug_fname) trace("CALL %d traceroute() - %g", ipaddr(), Scheduler::instance().clock());

	char path[256];
	path[0]=0;

	for(int i=0; i<eh->path_len; ++i) 
		sprintf(path,"%s%d ",path,eh->path_nodes[i]);
	trace("T %.9f _%d_ epipath 0x%x %d nodes %s",
	      Scheduler::instance().clock(), ipaddr(), eh->id, eh->path_len, path);
	if (debug_fname) trace("CALL %d end of traceroute() - %g", ipaddr(), Scheduler::instance().clock());
}

int
toraAgent::fwddirect(Packet *p)
{
	if (debug_fname) trace("CALL %d fwddirect() - %g", ipaddr(), Scheduler::instance().clock());

	TORADest *td;
	struct hdr_epi *eh = HDR_EPI(p);
	struct hdr_ip *ih = HDR_IP(p);
	// look for a direct connection
        for(td = nblist.lh_first ; td; td = td->link.le_next) {

		// Epic was using the old ip.h where addresses and
                // port were separated.
		// using daddr() instead of dst() [Felix]
		if (ih->daddr()==td->index) {
			if (!eh->master->delivered)
				forward(p->copy(), td->index);
			// eh->master->delivered++;

			// using saddr() and daddr() instead of 
                        // src_ and dst_ [Felix]
			trace("T %.9f _%d_ epideliver %d->%d fwd to %d",
			      Scheduler::instance().clock(), ipaddr(), 
			      ih->saddr(), ih->daddr(), td->index);
//			eh->path_nodes[eh->path_len++]= td->index;
			traceroute(eh);
			return 1;
			}
		}

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

	return 0;
}

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

	struct hdr_epi *eh = HDR_EPI(p);

	// Look for neighbors who have it already

	// the act of sending changes nblist, so we need destlist
	int	*dests = new int[nbcnt];
	int to_cnt = set_dest(eh,dests);

	// split copies available between this node and its neighbors,
	// then subtract the copy each neighbor node gets
	int copies_to_neighbor = eh->copies_allowed/(to_cnt+1);
	if (copies_to_neighbor) --copies_to_neighbor;

	int copies_available = eh->copies_allowed;
	eh->copies_allowed = copies_to_neighbor; // sets up new packet

#ifdef BLIND
	// update hit list before we send any out
	int i=copies_available;
	for(int to=0; to<to_cnt && i; ++to) {
		eh->node_hit[eh->hits++] = dests[to];
		i -=  1+copies_to_neighbor;
		}
#endif

	for(int to=0; to<to_cnt && copies_available; ++to) {
		forward(p->copy(), dests[to]);
#ifdef SHOWALL
		struct hdr_ip *ih = HDR_IP(p);
		trace("T %.9f _%d_ epifwd 0x%x %d avail to fwd %d copies to %d ",
		      Scheduler::instance().clock(), ipaddr(), 
		      eh->id, copies_available,copies_to_neighbor,dests[to]);
#endif
		copies_available -=  1+copies_to_neighbor;
		}
	eh->copies_allowed = copies_available; // reset this nodes packet

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

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

	EPIpkt* ep = new EPIpkt(p);

	trace("T %.9f _%d_ epistore 0x%x",
		      Scheduler::instance().clock(), ipaddr(), HDR_EPI(p)->id);

	LIST_INSERT_HEAD(&copylist, ep, link);

	if (fwdqcnt< opt_qlen_) {
		if (fwdqcnt==0) fwdqlast=ep;
		++fwdqcnt;

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

	LIST_REMOVE(fwdqlast, link);
	// le_prev point the le_next field of the previous element
	Packet* last = fwdqlast->packet;
	fwdqlast = (EPIpkt*)(fwdqlast->link.le_prev-1);

	trace("T %.9f _%d_ epibump 0x%x",
		      Scheduler::instance().clock(), ipaddr(), HDR_EPI(last)->id);
#ifdef HASH
	int h = epihash(last);
	assert(copytable[h].lh_first->packet==last);
	LIST_REMOVE(copytable[h].lh_first, link);
	SUMMUNSETBIT(ihave,h);
#endif
	Packet::free(last);

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

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

// This method is intended to do routing resolution. In Epidemic Routing,
// this is just a broadcasting to the local neighborhood.

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

 	// --- EPIC --------------------------------------------------- [Felix]
	// This method is completely redefined under Epidemic Routing

	// See if node already has been infected.
	Packet *foundp = update_copylist(p);
#ifndef TTL
	p = foundp;
#endif

#ifdef FWDDIRECT
	if (fwddirect(p)) return;
#endif

#ifdef BLIND
	// forward copies of the message to all neighbors.
	fwdtoallnb(p);
#endif
#ifdef TTL
	if (p==foundp) { // we got a new packet
		struct hdr_epi *eh = HDR_EPI(p);
		if (eh->ttl) {
			--eh->ttl;
			if (nbcnt>1) {

				// Changed -1 to IP_BROADCAST [Felix]
				forward(p->copy(),IP_BROADCAST,.1);

				if (debug_loop) { // [Felix]
					int *neighs, count, j;
					imepagent->imepGetBiLinks(neighs, count);
					trace("EPIFWD info count=%d", count);
					for (j = 0; j < count; j++)
						trace("   %d", neighs[j]);
						
				}

				// nbcnt must be updated (nb was wrong)
				// [Felix]
				int *nblist = 0, nbcnt = 0;
				imepagent->imepGetBiLinks(nblist, nbcnt);
				trace("T %.9f _%d_ epifwd 0x%x ttl %d to %dnb ",
				      Scheduler::instance().clock(), ipaddr(), 
				      eh->id, eh->ttl,nbcnt);
				}
			}
		}
#endif
#ifdef ASK
	// ask neighbors if they want a copy
	struct hdr_epi *eh = HDR_EPI(p);
	if (eh->copies_allowed && previhave!=eh->id) {
		if (debug_recv) 
			trace("rt_resolve() node %d sending QRYs ask all (%g)", 
			      ipaddr(), Scheduler::instance().clock());
		sendQRY(IP_BROADCAST,p,.1);
		previhave=eh->id;
		}
	
#endif

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

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


/* ======================================================================
   Incoming Packets
   ====================================================================== */
void
toraAgent::recv(Packet *p, Handler *)
{
	if (debug_fname) trace("CALL %d recv() - %g", ipaddr(), Scheduler::instance().clock());

	struct hdr_cmn *ch = HDR_CMN(p);
	struct hdr_ip *ih = HDR_IP(p);

	// --- EPIC --------------------------------------------------- [Felix]
	struct hdr_epi *eh = HDR_EPI(p);
	// --- end of EPIC -------------------------------------------- [Felix]

	assert(initialized());

	// Commented out in NS [Felix] - EPIC had it activated
        //assert(p->incoming == 0);

	if(ch->ptype() == PT_TORA) {
		recvTORA(p);
		return;
	}

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

	if (debug_loop) 
		trace("recv() at %d [%d 0x%x %d->%d n_fwd_=%d prev=%d]",
		      ipaddr(), ch->uid(), eh->id, ih->saddr(), ih->daddr(), 
		      ch->num_forwards(), ch->prev_hop_);

	// using addr() instead of addr_ (ip.h changed) [Felix]
	// i think this had a bug: should be ipaddr() instead of addr()
	if (ch->prev_hop_ == ipaddr()) return;

	if (debug_recv) 
		trace("recv() %.9f ih->daddr() %d == %d ipaddr()", 
		      Scheduler::instance().clock(), ih->daddr(), ipaddr());

	// using daddr() instead of dst() [Felix]
	if (ih->daddr() == ipaddr()) {

		if (debug_recv) trace("recv() %.9f got something", 
		       Scheduler::instance().clock() );


		eh->path_nodes[eh->path_len++]= ipaddr();
		if (!eh->master->delivered++) {
			eh->master->stop = Scheduler::instance().clock();

			// using saddr() instead of src_ [Felix]
			trace("T %.9f _%d_ got 0x%x src %d from %d in %6.2f s",
			      Scheduler::instance().clock(), ipaddr(), 
			      eh->id,ih->saddr(),ch->prev_hop_,
			      eh->master->stop - eh->master->start
			      );
			traceroute(eh);
			eh->copies_allowed = 0;
			eh->ttl=0;
			p = update_copylist(p);
		} else {
			trace("T %.9f _%d_ extra delivery %d.  0x%x from %d",
			      Scheduler::instance().clock(), ipaddr(), 
			      eh->master->delivered,eh->id,
			      ch->prev_hop_);
			traceroute(eh);
			
			// Memory leakage (at least with my duplicating 
			// classifier)
			// [Felix]
#ifdef DEBUG_MEM
			printf("6\n");
#endif
			Packet::free(p);
		}

		return;
	}

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

        /*
         *  Must be a packet I'm originating...
         */
	// Changed in NS: ih->src_ [Felix]
	if(ih->saddr() == ipaddr() && ch->num_forwards() == 0) {


		if (debug_recv)
			trace("recv() %.9f my own packet prev_hop_ %d", 
			      Scheduler::instance().clock(),
			      ch->prev_hop_);

		/*
		 * HACK:
		 * prev_hop_ is always 0, what confuses forward()
		 * in some cases 
		 */
		if (!ch->prev_hop_) {
#ifdef SHOWALL
			trace("recv() %.9f prev_hop_ HACK", 
			      Scheduler::instance().clock(),
			      ch->prev_hop_);
#endif			
			ch->prev_hop_ = ipaddr();
		}

                /*
                 *  Add the IP Header.
                 */
                ch->size() += IP_HDR_LEN;
                ih->ttl_ = IP_DEF_TTL;

		// --- EPIC ------------------------------------------- [Felix]
                ch->size() = 1024;  // XXX epi pkt len

		eh->copies_allowed = 50; // XXX should be from otcl
		static int globalid; // XXX unique id cheat
		eh->id = globalid++; // XXX
#ifdef BLIND
		eh->hits = 0;
		eh->node_hit[eh->hits++] = ipaddr();
#endif
		eh->path_len= 0;
		eh->master= new MasterPacket;
		LIST_INIT(&eh->master->copylist);
		eh->master->delivered=0;
		eh->master->start = Scheduler::instance().clock();
		eh->master->stop = 0;

		eh->path_nodes[eh->path_len++]= ipaddr();

		EPIpkt* ep = new EPIpkt(p);
		LIST_INSERT_HEAD(&eh->master->copylist, ep, link);


#ifdef HASH
		int h = epihash(p);