/******************************************************************* Copyright (C) 2004 Thomas Kunz, CRC Canada, BCAST for IPv4. DISTRIBUTED WITH NO WARRANTY, EXPRESS OR IMPLIED. See the GNU Library General Public License (file COPYING in the MANET_multicast directory) for conditions of use and redistribution.*********************************************************************//* * Functions to manage pending broadcast messages. These are saved in  * an ordered list, with timeouts set to schedule the first packet in the * list. * * This queue structure is necessarily to implement the Scalable Broadcast * Algorithm described in "Comparison of Broadcasting Techniques for * Mobile Ad Hoc Networks" by Williams and Camp, MobiHoc 2002. */#include <random.h>#include <bcast/bcast.h>#include <bcast/bcast_packet.h> // #define DEBUG#define CURRENT_TIME    Scheduler::instance().clock() voidBCASTHandler::handle(Event*) {  if (pbcasts.lh_first) {	struct hdr_bcast *bh = HDR_BCAST(pbcasts.lh_first->p);	PendingBCAST *elem = pbcasts.lh_first;	if (elem->no_of_neighbors == 0) {		// no more neighbors left to cover, drop from list#ifdef DEBUG		fprintf(stderr, "Node %d: Pending BCAST cancelled\n",			agent->index);#endif	} else {		// transmit pending broadcast#ifdef DEBUG		fprintf(stderr,"Node %d: Send pending broadcast %f at %f\n", 			agent->index, pbcasts.lh_first->expire, CURRENT_TIME);#endif		agent->sendPacket(pbcasts.lh_first->p, 0.0);	}	LIST_REMOVE(elem, link);	delete elem;	no_bcasts--;	// schedule for next event in list	if (pbcasts.lh_first != NULL) {#ifdef DEBUG		fprintf(stderr, "Node %d: Schedule for %f at %f\n", 			agent->index, pbcasts.lh_first->expire, CURRENT_TIME);#endif		Scheduler::instance().schedule(this, &intr, 			pbcasts.lh_first->expire - CURRENT_TIME);	} }}/*   Unique ID Management  Functions*/voidBCASTHandler::insert(Packet *p, int no_of_neighbors, nsaddr_t neighbors[],		double delay) {PendingBCAST *b; PendingBCAST *list = pbcasts.lh_first;int inserted = 0; // Check whether queue is too full already if (no_bcasts >= MAX_QUEUE_LEN) {	// pass packet on for delivery right away#ifdef DEBUG	fprintf(stderr, "Node %d: BCAST queue full\n", agent->index);#endif	agent->sendPacket(p, 0.0);	return; } // We have to iterate through the list to see if earlier packets // from the same node are enqueued. If so, adjust the DELAY to ensure // in-order delivery. struct hdr_ip *ih = HDR_IP(p); struct hdr_rtp *rh = HDR_RTP(p); struct hdr_bcast *bh = HDR_BCAST(p); nsaddr_t src = ih->saddr(); unsigned int seqno = rh->seqno_; for (list = pbcasts.lh_first; list; list = list->link.le_next) {   // extract source and sequence number for enqueue packet   struct hdr_ip *ih_q = HDR_IP(list->p);   struct hdr_rtp *rh_q = HDR_RTP(list->p);   nsaddr_t src_q = ih_q->saddr();   unsigned int seqno_q = rh_q->seqno_;   if (src == src_q && seqno > seqno_q) {     // we found a packet from the same source with an earlier sequence number     if (delay < list->expire) {       // that earlier packet is scheduled for later transmission: adjust       // delay for the current packet       delay = list->expire + 0.02 * Random::uniform(); #ifdef DEBUG       fprintf(stderr, "Node %d: adjusting queuing delay for packet (%d,%d)\n",          agent->index, src, seqno);       fprintf(stderr, "         due to earlier packet (%d,%d) in queue\n",          src_q, seqno_q);#endif     }   } } // Check whether new element belongs at head of list#ifdef DEBUG fprintf(stderr,"Node %d: Adding packet %lx with delay %f at time %f\n",	agent->index, p, delay, CURRENT_TIME);#endif// agent->sendPacket(p, 0.0); b = new PendingBCAST(p, delay);// copy info about remaining uncovered neighborhood b->no_of_neighbors = no_of_neighbors; for (int i = 0; i < b->no_of_neighbors; i++) {	 b->neighbors[i] = neighbors[i]; } list = pbcasts.lh_first; if (list == NULL || delay < list->expire) {	LIST_INSERT_HEAD(&pbcasts, b, link);	// check if we need to cancel an already scheduled (later) event for	// this queue before scheduling for the new earliest event...	if (intr.uid_) {#ifdef DEBUG		fprintf(stderr, "Node %d: Reschedule earliest event\n",			agent->index);#endif		Scheduler::instance().cancel(&intr);	}	Scheduler::instance().schedule(this, &intr, 		pbcasts.lh_first->expire - CURRENT_TIME);	 } else {	// search in list for right place	for (; list->link.le_next; list = list->link.le_next) {		if (list->link.le_next && delay < list->link.le_next->expire) {			LIST_INSERT_AFTER(list, b, link);			inserted = 1;			break;		}	}	if (!inserted) {		// add at list end		LIST_INSERT_AFTER(list, b, link);	} } no_bcasts++;}voidBCASTHandler::process(nsaddr_t src, int unique_id, 	int count, nsaddr_t neighbors[]) {PendingBCAST *b = pbcasts.lh_first;// return;#ifdef DEBUG  fprintf(stderr, "Node %d: Process packet (%d,%d) at %f\n", agent->index, 	src, unique_id, CURRENT_TIME);#endif // Search the list for a match of source and bid for( ; b; b = b->link.le_next) {	struct hdr_cmn *ch = HDR_CMN(b->p);	struct hdr_ip *ih = HDR_IP(b->p);	struct hdr_bcast *bh = HDR_BCAST(b->p);#ifdef DEBUG	fprintf(stderr,"Node %d: Check against packet (%d,%d)\n", agent->index,		ih->saddr(), ch->uid());#endif 	if (ih->saddr()==src && ch->uid()==unique_id) {		compare(b, count, neighbors);	} }}/* =======================================================================   Private Routines   ======================================================================= */void BCASTHandler::compare(PendingBCAST *b, int count, 	nsaddr_t neighbors[]) {// struct hdr_bcast *bh = HDR_BCAST(p);#ifdef DEBUG fprintf(stderr, "Node %d: Compare pending neighbors with new information\n",	agent->index); fprintf(stderr, "Pending neighbors:"); for (int j = 0; j < b->no_of_neighbors; j++) {	fprintf(stderr, " %d", b->neighbors[j]); } fprintf(stderr, "\nNew neighbors:"); for (int i = 0; i < count; i++) {	fprintf(stderr, " %d", neighbors[i]); } fprintf(stderr, "\n");#endif for (int i = 0; i < count; i++) {	for (int j = 0; j < b->no_of_neighbors; j++) {		if (b->neighbors[j] == neighbors[i]) {			for (int l = j+1; l < b->no_of_neighbors; l++) {				b->neighbors[l-1] = b->neighbors[l];			}			b->no_of_neighbors = b->no_of_neighbors - 1;			break;		}	} }}