bcast.cc

code that can compile NS-2.27 on Fedora Core 4

#ifdef DEBUG
	fprintf(stderr, "Node %d: Processing neighbor info for neighbor %d\n",
		index, bh->src);
#endif
	bcast_queue.process(ih->saddr(), ch->uid(), nb->nb_no_of_neighbors,
		nb->nb_neighbors);
 }

 // check whether received packet is in response to a NACK and cancel
 // pending NACK timer
 nacktimer.cancel_nack_timer(src, seqno);

 // check whether received packet allows us to drop a pending retransmission
 rtxtimer.cancel_rtx_timer(src, seqno);

 if(ih->ttl_ == 0) {

#ifdef DEBUG
  fprintf(stderr, "Node %d: calling drop() (TTL expired)\n", index);
#endif // DEBUG
 
  drop(p, DROP_RTR_TTL);
  return;
 }

 if (uid_handler.id_lookup(src, seqno)) {
#ifdef DEBUG
   fprintf(stderr, "Node %d: discarding packet (not first time)\n", index);
#endif
   Packet::free(p);
   return;
 }

#ifdef RELIABLE
 // we also check whether we received previous packet (based on cached
 // unique IDs....)
 if (seqno > 0 && !uid_handler.id_lookup(src, seqno-1)) {
#ifdef DEBUG
   fprintf(stderr, "Node %d: missed packet (%d,%d) at %f, NACK it\n",
     index, src, seqno-1, CURRENT_TIME);
#endif
   if (nacktimer.control_nack_flood())
   	sendNack(src,seqno-1);
 }
#endif

 /*
  * Check whether this packet belongs to a multicast group 
  * this node subscribed to?
  */
 mt = mtable.mt_lookup(ih->daddr());
 if (mt) {

   // Need to make a copy of the packet
   Packet *p_new = p->copy();
   struct hdr_cmn *ch_new = HDR_CMN(p_new);
#ifdef PIGGYBACK_HELLO
   struct hdr_bcast *bh_new = HDR_BCAST(p);
#endif

   ch_new->addr_type() = NS_AF_INET;
   ch_new->direction() = hdr_cmn::UP;
   struct hdr_ip *ih_new = HDR_IP(p_new);

#ifdef PIGGYBACK_HELLO
   // "strip" BCAST header and make it a "regular" packet again
   ch_new->size() -= BCAST_HDR_LEN;
   ch_new->ptype() = bh_new->old_type;
#endif

   // "strip" the IP header...
   ch_new->size() -= IP_HDR_LEN;

   // send to "myself" at port 0 
   // (assume that receiving NULL agent sits there...)
   ih_new->daddr() = index;
   ih_new->dport() = 0;

   // pass packet to Link Layer, from where it will be passed up the stack to
   // agent at port 0 (routing agent cannot directly pass packets up the stack
   // unless we emulate the way DSR agents are linked in the protocol stack)
   Scheduler::instance().schedule(target_, p_new, 0.);
 } 

 /*
  * Cache the packet ID
  */
 uid_handler.id_insert(src, seqno);

 ch->addr_type() = NS_AF_ILINK; // allows us to force MAC broadcast 
 ch->direction() = hdr_cmn::DOWN; //important: change the packet's direction

 /* force MAC broadcast, bypassing ARP etc. Better than IP broadcast, which
    would override IP destination address */
 ch->next_hop_ = MAC_BROADCAST;

 /*
  * Cache the packet itself (neighbourhood information will be filled in
  * when the cached copy will be retransmitted, but it is important that
  * the direction etc. have been set, so the packet is ready to go....
  */
 p_cache.packet_insert(p);

 /*
  * determine and save my neighborhood information, minus sender of packet
  */
 int count = 0;
 nb = nbhead.lh_first;
 for(; nb; nb = nb->nb_link.le_next) {
	// skip sender of packet
	if (ch->prev_hop_ != nb->nb_addr) {
		neighbors[count++] = nb->nb_addr;
	}
 }
 no_of_neighbors = count;

 /*
  * if we originate that packet or do not have neighbor info
  * there is no need to process this further
  */
 if (ih->saddr() != index && ((nb = nb_lookup(ch->prev_hop_)) != NULL)) {
	// eliminate all neighbors that are also covered by sender...
#ifdef DEBUG
	fprintf(stderr, "Node %d: eliminate known neighbors of %d\n", 
		index, ch->prev_hop_);
#endif
	for (int i = 0; i < nb->nb_no_of_neighbors; i++) {
		for (int j = 0; j < no_of_neighbors; j++) {
			if (neighbors[j] == nb->nb_neighbors[i]) {
				for (int l = j+1; l < no_of_neighbors; l++) {
					neighbors[l-1] = neighbors[l];
				}
				no_of_neighbors--;
				break;
			}
		}
	}
 }

#ifdef DEBUG
	fprintf(stderr, "Node %d: remaining %d uncovered neighbours\n", 
		index, no_of_neighbors);
	for (int i = 0; i < no_of_neighbors; i++)
		fprintf(stderr, " %d", neighbors[i]);
	fprintf(stderr, "\n");
#endif

 ch->prev_hop_ = index; // mark current node as forwarder

 /* enqueue packet if there are uncovered neigbors */
 if (no_of_neighbors != 0) {
	// determine right amount of jitter
	nb_determine_degrees(&max, &n);
	bcast_queue.insert(p, no_of_neighbors, neighbors,
		CURRENT_TIME+((double)max/n) * BCAST_DELAY * Random::uniform());
 }
}

void
BCAST::sendPacket(Packet *p, double delay) {
 // we need to do 3 things:
 // 1) add neighbourhood info into Packet
 // 2) cancel and reschedule HELLO message
 // 3) send packet out
 struct hdr_cmn *ch = HDR_CMN(p);

#ifdef PIGGYBACK_HELLO
 struct hdr_bcast *bh = HDR_BCAST(p);
#endif

 // keep info about PACKET being sent by node
 nacktimer.save_packet_time(CURRENT_TIME);

#ifdef PIGGYBACK_HELLO
 // 1) fill in neighborhood information 
 // (i.e., piggyback info in HELLO message)
 int count = 0;
 BCAST_Neighbor *nb = nbhead.lh_first;
 for(; nb; nb = nb->nb_link.le_next) {
	bh->neighbors[count++] = nb->nb_addr;
 }
 bh->no_of_neighbors = count;

 if (count > NEIGHBOR_COUNT) {
	fprintf(stderr, "Node %d: too many neighbors (%d vs. max %d)\n", 
		index, count, NEIGHBOR_COUNT);
	exit(1);
 }

 // 2) check and cancel pending HELLO message, reschedule one for later
 htimer.reschedule();
#endif

 // mark current node as forwarder
 ch->prev_hop_ = index;

 // 3) send packet out
 Scheduler::instance().schedule(target_, p, delay);
}

/*
 * Dealing with retransmission requests
 */

void
BCAST::sendNack(nsaddr_t src, u_int32_t seqno) {
Packet *p = Packet::alloc();
struct hdr_cmn *ch = HDR_CMN(p);
struct hdr_ip *ih = HDR_IP(p);
struct hdr_bcast *bh = HDR_BCAST(p);

#ifdef DEBUG
 fprintf(stderr, "Node %d: sending NACK for (%d,%d) at %.2f\n", 
	index, src, seqno, Scheduler::instance().clock());
#endif

 // keep info about NACK being sent by node
 nacktimer.save_packet_time(CURRENT_TIME);

 bh->type = BCASTTYPE_NACK;
 bh->hop_count = 1;
 // ask for retransmission of packet from node ID with number BID
 bh->src = src;
 bh->src_seqno = seqno;

#ifdef PIGGYBACK_HELLO
 // piggyback neighbour information
 int count = 0;
 BCAST_Neighbor *nb = nbhead.lh_first;
 for(; nb; nb = nb->nb_link.le_next) {
	bh->neighbors[count++] = nb->nb_addr;
 }
 bh->no_of_neighbors = count;

 if (count > NEIGHBOR_COUNT) {
	fprintf(stderr, "Node %d: too many neighbors (%d vs. max %d)\n", 
		index, count, NEIGHBOR_COUNT);
	exit(1);
 }
 // check and cancel pending HELLO message, reschedule one for later
 htimer.reschedule();
#endif

 bh->dst = index;
 bh->lifetime = (1 + ALLOWED_HELLO_LOSS) * HELLO_INTERVAL;
 ch->ptype() = PT_BCAST;
 ch->size() = IP_HDR_LEN + sizeof(hdr_bcast);
 ch->iface() = -2;
 ch->error() = 0;
 ch->addr_type() = NS_AF_NONE;
 ch->prev_hop_ = index;

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

 /* send NACK, but add jitter..... */
 Scheduler::instance().schedule(target_, p, 0.01 * Random::uniform());
}

void
BCAST::recvNack(Packet *p) {
struct hdr_bcast *bh = HDR_BCAST(p);
struct hdr_cmn *ch = HDR_CMN(p);
BCAST_Neighbor *nb;
Packet *cached;
double delay;

#ifdef DEBUG
 fprintf(stderr, "Node %d: receiving NACK for (%d,%d) from %d at %.2f\n", 
	index, bh->src, bh->src_seqno, bh->dst, 
        Scheduler::instance().clock());
#endif

 /* see whether we have requested packet in cache and "queue" it for
    retransmission */
 cached = p_cache.packet_lookup(bh->src, bh->src_seqno);
 if (cached) {
   delay = 0.01 * Random::uniform();
#ifdef DEBUG
   fprintf(stderr, "Node %d: servicing NACK for (%d,%d) from %d at %.4f\n",
     index, bh->src, bh->src_seqno, bh->dst, 
     Scheduler::instance().clock() + delay);
#endif
   // sendPacket(cached->copy(), delay);
   rtxtimer.start_rtx_timer(cached, delay);
 }

#ifdef PIGGYBACK_HELLO
 /* extract piggyback'd neighbour information */
 nb = nb_lookup(ch->prev_hop_);
 if(nb == 0) {
   nb_insert(ch->prev_hop_);
   nb = nb_lookup(ch->prev_hop_);
 }
 else {
   nb->nb_expire = CURRENT_TIME +
                   (1.5 * ALLOWED_HELLO_LOSS * HELLO_INTERVAL);
 }
 // safe one-hop neighborhood information
 add_neighbors(nb, bh->no_of_neighbors, bh->neighbors);
#endif

 Packet::free(p);

#ifdef DEBUG
 fprintf(stderr, "Node %d: neighbours:\n", index);
 nb = nbhead.lh_first;

 for(; nb; nb = nb->nb_link.le_next) {
   fprintf(stderr," %d:", nb->nb_addr);
   for (int i = 0; i < nb->nb_no_of_neighbors; i++) {
	fprintf(stderr, " %d", nb->nb_neighbors[i]);
   }
   fprintf(stderr, "\n");
 }
#endif
}

/*
 * Neighbor Management Functions
 */

void
BCAST::sendHello() {
Packet *p = Packet::alloc();
struct hdr_cmn *ch = HDR_CMN(p);
struct hdr_ip *ih = HDR_IP(p);
struct hdr_bcast *bh = HDR_BCAST(p);

#ifdef DEBUG
 fprintf(stderr, "Node %d: sending Hello at %.2f\n", 
	index, Scheduler::instance().clock());
#endif

 // keep info about HELLO being sent by node
 nacktimer.save_packet_time(CURRENT_TIME);

 bh->type = BCASTTYPE_HELLO;
 bh->hop_count = 1;
 bh->dst = index;
 bh->lifetime = (1 + ALLOWED_HELLO_LOSS) * HELLO_INTERVAL;

 // fill in neighborhood information
 int count = 0;
 BCAST_Neighbor *nb = nbhead.lh_first;
 for(; nb; nb = nb->nb_link.le_next) {
	bh->neighbors[count++] = nb->nb_addr;
 }
 bh->no_of_neighbors = count;

 if (count > NEIGHBOR_COUNT) {
	fprintf(stderr, "Node %d: too many neighbors (%d vs. max %d)\n", 
		index, count, NEIGHBOR_COUNT);
	exit(1);
 }

 ch->ptype() = PT_BCAST;
 ch->size() = IP_HDR_LEN + sizeof(hdr_bcast);
 ch->iface() = -2;
 ch->error() = 0;
 ch->addr_type() = NS_AF_NONE;
 ch->prev_hop_ = index;

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

 Scheduler::instance().schedule(target_, p, 0.0);
}

void
BCAST::recvHello(Packet *p) {
struct hdr_cmn *ch = HDR_CMN(p);
struct hdr_bcast *bh = HDR_BCAST(p);
BCAST_Neighbor *nb;

 nb = nb_lookup(ch->prev_hop_);
 if(nb == 0) {
   nb_insert(ch->prev_hop_);
   nb = nb_lookup(ch->prev_hop_);
 }
 else {
   nb->nb_expire = CURRENT_TIME +
                   (1.5 * ALLOWED_HELLO_LOSS * HELLO_INTERVAL);
 }
 // safe one-hop neighborhood information
 add_neighbors(nb, bh->no_of_neighbors, bh->neighbors);

 Packet::free(p);

#ifdef DEBUG
 fprintf(stderr, "Node %d: neighbours:\n", index);
 nb = nbhead.lh_first;

 for(; nb; nb = nb->nb_link.le_next) {
   fprintf(stderr," %d:", nb->nb_addr);
   for (int i = 0; i < nb->nb_no_of_neighbors; i++) {
	fprintf(stderr, " %d", nb->nb_neighbors[i]);
   }
   fprintf(stderr, "\n");
 }
#endif
}

void
BCAST::nb_insert(nsaddr_t id) {
BCAST_Neighbor *nb = new BCAST_Neighbor(id);

 assert(nb);
 nb->nb_expire = CURRENT_TIME +
                (1.5 * ALLOWED_HELLO_LOSS * HELLO_INTERVAL);
 LIST_INSERT_HEAD(&nbhead, nb, nb_link);
}

BCAST_Neighbor*
BCAST::nb_lookup(nsaddr_t id) {
BCAST_Neighbor *nb = nbhead.lh_first;

 for(; nb; nb = nb->nb_link.le_next) {
   if(nb->nb_addr == id) break;
 }
 return nb;
}

void
BCAST::nb_determine_degrees(int *max, int *n) {
BCAST_Neighbor *nb = nbhead.lh_first;

 *n = 0;
 *max = 0;
 
 for(; nb; nb = nb->nb_link.le_next) {
	(*n)++;
	if (nb->nb_no_of_neighbors > *max) {
		*max = nb->nb_no_of_neighbors;
	}
 }
}
/*
 * Called when we receive *explicit* notification that a Neighbor
 * is no longer reachable.
 */
void
BCAST::nb_delete(nsaddr_t id) {
BCAST_Neighbor *nb = nbhead.lh_first;

 for(; nb; nb = nb->nb_link.le_next) {
   if(nb->nb_addr == id) {
     LIST_REMOVE(nb,nb_link);
     delete nb;
     break;
   }
 }
}


/*
 * Purges all timed-out Neighbor Entries - runs every
 * HELLO_INTERVAL * 1.5 seconds.
 */
void
BCAST::nb_purge() {
BCAST_Neighbor *nb = nbhead.lh_first;
BCAST_Neighbor *nbn;
double now = CURRENT_TIME;

 for(; nb; nb = nbn) {
   nbn = nb->nb_link.le_next;
   if(nb->nb_expire <= now) {
     nb_delete(nb->nb_addr);
   }
 }
}

/* 
 * Add 1-hop neighbourhood info for neighbour NB
 */
void
BCAST::add_neighbors(BCAST_Neighbor *nb, int num_neighbors,
					nsaddr_t *one_hop_neighbors) {
 for (int i = 0; i < num_neighbors; i++) {
	nb->nb_neighbors[i] = one_hop_neighbors[i];
 }
  nb->nb_no_of_neighbors = num_neighbors;
}