bcast_queue.cc

code that can compile NS-2.27 on Fedora Core 4

/*******************************************************************
 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() 

void
BCASTHandler::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
*/

void
BCASTHandler::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++;
}

void
BCASTHandler::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;
		}
	}
 }
}