/******************************************************************* 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.*********************************************************************//*Copyright (c) 1997, 1998 Carnegie Mellon University.  All RightsReserved. Permission to use, copy, modify, and distribute thissoftware and its documentation is hereby granted (including forcommercial or for-profit use), provided that both the copyright notice and this permission notice appear in all copies of the software, derivative works, or modified versions, and any portions thereof, and that both notices appear in supporting documentation, and that credit is given to Carnegie Mellon University in all publications reporting on direct or indirect use of this code or its derivatives.ALL CODE, SOFTWARE, PROTOCOLS, AND ARCHITECTURES DEVELOPED BY THE CMUMONARCH PROJECT ARE EXPERIMENTAL AND ARE KNOWN TO HAVE BUGS, SOME OFWHICH MAY HAVE SERIOUS CONSEQUENCES. CARNEGIE MELLON PROVIDES THISSOFTWARE OR OTHER INTELLECTUAL PROPERTY IN ITS ``AS IS'' CONDITION,AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULARPURPOSE ARE DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITYBE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, ORCONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OFSUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; ORBUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCEOR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE ORINTELLECTUAL PROPERTY, EVEN IF ADVISED OF THE POSSIBILITY OF SUCHDAMAGE.Carnegie Mellon encourages (but does not require) users of thissoftware or intellectual property to return any improvements orextensions that they make, and to grant Carnegie Mellon the rights to redistribute these changes without encumbrance.*//*  * The original AODV code was modified heavily to implement efficient  * broadcasting (BCAST) by Thomas Kunz. */#include <bcast/bcast.h>#include <bcast/bcast_packet.h>#include <MANET_multicast/mttable.h>#include <random.h>#include <cmu-trace.h>#define max(a,b)        a > b ? a : b#define CURRENT_TIME    Scheduler::instance().clock()//#define DEBUG//#define ERROR/*  TCL Hooks*/int hdr_bcast::offset_;static class BCASTHeaderClass : public PacketHeaderClass {public:        BCASTHeaderClass() : PacketHeaderClass("PacketHeader/BCAST",                                              BCAST_HDR_LEN) {		bind_offset(&hdr_bcast::offset_);	} } class_rtProtoBCAST_hdr;static class BCASTclass : public TclClass {public:        BCASTclass() : TclClass("Agent/BCAST") {}        TclObject* create(int argc, const char*const* argv) {          assert(argc == 5);          return (new BCAST((nsaddr_t) atoi(argv[4])));        }} class_rtProtoBCAST;intBCAST::command(int argc, const char*const* argv) {  if(argc == 2) {  Tcl& tcl = Tcl::instance();        if(strncasecmp(argv[1], "id", 2) == 0) {      tcl.resultf("%d", index);      return TCL_OK;    }        if(strncasecmp(argv[1], "start", 2) == 0) {      htimer.handle((Event*) 0);      ntimer.handle((Event*) 0);      uid_handler.handle((Event*) 0);      //bcast_queue.handle((Event*) 0);      return TCL_OK;     }                 }  else if(argc == 3) {    if(strcmp(argv[1], "index") == 0) {      index = atoi(argv[2]);      return TCL_OK;    }    else 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], "bcast-join-group")==0) {      nsaddr_t mcast_addr = atoi(argv[2]);      if (mcast_addr < IP_MULTICAST_RANGE) return TCL_ERROR;				      mt_entry *mt = mtable.mt_lookup(mcast_addr);      if (!mt) mt = mtable.mt_add(mcast_addr);      return TCL_OK;    }    else if(strcmp(argv[1], "bcast-leave-group")==0) {      nsaddr_t mcast_addr = atoi(argv[2]);      if (mcast_addr < IP_MULTICAST_RANGE) return TCL_ERROR;				      mt_entry *mt = mtable.mt_lookup(mcast_addr);      if (!mt) mtable.mt_delete(mcast_addr);      return TCL_OK;    }    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], "port-dmux") == 0) {        dmux_ = (PortClassifier *)TclObject::lookup(argv[2]);        if (dmux_ == 0) {                fprintf (stderr, "%s: %s lookup of %s failed\n", __FILE__,                argv[1], argv[2]);                return TCL_ERROR;        }        return TCL_OK;    }  }  return Agent::command(argc, argv);}/*    Constructor*/BCAST::BCAST(nsaddr_t id) : Agent(PT_BCAST), nacktimer(this), rtxtimer(this),				htimer(this), ntimer(this),				mtable(), bcast_queue(this), p_cache(CACHE_SIZE) {                  index = id;  LIST_INIT(&nbhead);  logtarget = 0;  ifqueue = 0;}/*******************************************************************************                                TIMERS *******************************************************************************/voidNackTimer_bcast::handle(Event*) {   // if we receibed the packet, silent discard the NACK   if (seqno > 0 && agent->uid_handler.id_lookup(src, seqno)) 	   return;   // otherwise, issue a NACK (up to MAX_NACK times only)   if (retry_count++ < MAX_NACK) {#ifdef DEBUG     fprintf(stderr, "Node %d: NACK timed out at %f, try again (%d)\n",        agent->index, CURRENT_TIME, retry_count);#endif     if (control_nack_flood()) {#ifdef DEBUG        fprintf(stderr, "Node %d: throttle nack\n", agent->index);#endif	return;     }     agent->sendNack(src, seqno);     Scheduler::instance().schedule(this, &intr, NACK_TIMEOUT);   }   else {     src = ILLEGAL_NODE; seqno = 0;   }}void NackTimer_bcast::start_nack_timer(nsaddr_t p_src, 		unsigned int p_seqno, double delay) {   // there is a slight potential for trouble: assume we miss packets   // N-2, N-1, and N from the same source. Upon receipt of packet N+1,   // a NACK for packet N is issued. While we wait for packet N to be   // retransmitted by a neighbour, due to the broadcast nature of the medium,    // we may overhear (and receive) retransmission of packet N-1 (requested   // by another node in the neighborhood). This will trigger a NACK for N-2.    //   // The code supports only a single outstanding NACK timeout. In this (rare)   // case, our scheme fails: we will not set the NACK timer for N-2. If the   // retransmission attempt of packet N-2 fails, we will not have a timeout to   // recover.   //   if (intr.uid_ > 0) {      // there is already a timer set, silently quit      return;   }   src = p_src;   seqno = p_seqno;   retry_count = 0;#ifdef DEBUG   fprintf(stderr, "Node %d: starting NACK timer for packet (%d,%d)\n",     agent->index, src, seqno);#endif   Scheduler::instance().schedule(this, &intr, delay);}voidNackTimer_bcast::cancel_nack_timer(nsaddr_t p_src, unsigned int p_seqno) {   // check whether we had a NACK pending for this packet   // and cancel   if (intr.uid_) {     if (p_src == src && p_seqno == seqno) {#ifdef DEBUG       fprintf(stderr, "Node %d: cancelling NACK timer for packet (%d,%d)\n",         agent->index, src, seqno);#endif       Scheduler::instance().cancel(&intr);       src = 0; seqno = 0;     }   }}// keep track of packet being sent or received to control NACK frequencyvoidNackTimer_bcast::save_packet_time(double t_packet) {    packet_times[packet_ptr] = t_packet;    packet_ptr = (packet_ptr + 1) % PACKET_COUNT;   if (packet_ptr == 0) count = PACKET_COUNT;}// if it is okay to send a NACK, return TRUEintNackTimer_bcast::control_nack_flood() {// nack_ptr points to the next element to be overwritten, so// this is the one the longest in the array...if (count == PACKET_COUNT &&    CURRENT_TIME - packet_times[packet_ptr] < MIN_DIFF) 	return 0;else	return 1;}voidRetransmitTimer_bcast::handle(Event*) {   // retransmit NACK-ed packet#ifdef DEBUG   fprintf(stderr, "Node %d: retransmit packet (%d,%d) at %f\n",     agent->index, src, seqno, CURRENT_TIME);#endif   agent->sendPacket(p, 0.0);   src = ILLEGAL_NODE; seqno = 0;}void RetransmitTimer_bcast::start_rtx_timer(Packet *pck, double delay) {   if (intr.uid_ > 0) {      // there is already a timer set, silently quit      return;   }   // extract and save SRC and SEQNO for easier/faster comparison   struct hdr_ip *ih = HDR_IP(pck);   struct hdr_rtp *rh = HDR_RTP(pck);   src = ih->saddr();   seqno = rh->seqno_;   // save a copy of the packet: by the time we retransmit, it may not   // be in the node cache anymore....   p = pck->copy();   struct hdr_cmn *ch = HDR_CMN(p);   ch->direction() = hdr_cmn::DOWN;#ifdef DEBUG   fprintf(stderr, "Node %d: RTX timer for packet (%d,%d) at %f, delay %f\n",     agent->index, src, seqno, CURRENT_TIME, delay);#endif   Scheduler::instance().schedule(this, &intr, delay);}voidRetransmitTimer_bcast::cancel_rtx_timer(nsaddr_t p_src, unsigned int p_seqno) {   // check whether we had a timer pending for this packet   // and cancel   if (intr.uid_) {     if (p_src == src && p_seqno == seqno) {#ifdef DEBUG       fprintf(stderr, "Node %d: cancelling RTX timer for packet (%d,%d)\n",         agent->index, src, seqno);#endif       Scheduler::instance().cancel(&intr);       Packet::free(p); src = 0; seqno = 0;     }   }}voidHelloTimer_bcast::handle(Event*) {   agent->sendHello();   double interval = MinHelloInterval +                  ((MaxHelloInterval - MinHelloInterval) * Random::uniform());   assert(interval >= 0);   Scheduler::instance().schedule(this, &intr, interval);}voidHelloTimer_bcast::reschedule() {   if (intr.uid_) {#ifdef DEBUG	fprintf(stderr, "Node %d: Reschedule hello message\n",			agent->index);#endif	Scheduler::instance().cancel(&intr);   }   double interval = MinHelloInterval +                  ((MaxHelloInterval - MinHelloInterval) * Random::uniform());   assert(interval >= 0);   Scheduler::instance().schedule(this, &intr, interval);}voidNeighborTimer_bcast::handle(Event*) {  agent->nb_purge();  Scheduler::instance().schedule(this, &intr, HELLO_INTERVAL);}/*  Packet Reception Routines*/voidBCAST::recv(Packet *p, Handler*) {struct hdr_cmn *ch = HDR_CMN(p);struct hdr_ip *ih = HDR_IP(p);struct hdr_bcast *bh = HDR_BCAST(p); assert(initialized()); if(ch->ptype() == PT_BCAST) {   ih->ttl_ -= 1;   recvBCAST(p);   return; } /*  *  Must be a packet I'm originating...  */ if((ih->saddr() == index) && (ch->num_forwards() == 0)) { /*  * Add the IP Header  */   ch->size() += IP_HDR_LEN;   ih->ttl_ = NETWORK_DIAMETER; } /*  *  I received a packet that I sent.  Probably  *  a routing loop.  */ else if(ih->saddr() == index) {   drop(p, DROP_RTR_ROUTE_LOOP);   return; } /*  *  Packet I'm forwarding...  */ else { /*  *  Check the TTL.  If it is zero, then discard.  */   if(--ih->ttl_ == 0) {     drop(p, DROP_RTR_TTL);     return;   } }#ifdef PIGGYBACK_HELLO // turn packet into BCASTTYPE_DATA packet so we can pihhyback HELLO msg ch->size() += BCAST_HDR_LEN; bh->old_type = ch->ptype(); // save old packet type ch->ptype() = PT_BCAST; bh->type = BCASTTYPE_DATA;#endif // pass this packet on to be forwarded  forward(p);}voidBCAST::recvBCAST(Packet *p) {struct hdr_bcast *bh = HDR_BCAST(p);struct hdr_ip *ih = HDR_IP(p); assert(ih->sport() == RT_PORT); assert(ih->dport() == RT_PORT); // keep info about PACKET being received by node nacktimer.save_packet_time(CURRENT_TIME); /*  * Incoming Packets.  */ switch(bh->type) { case BCASTTYPE_HELLO:   recvHello(p);   break; case BCASTTYPE_NACK:   recvNack(p);   break;#ifdef PIGGYBACK_HELLO case BCASTTYPE_DATA:   // Each packet of type BCAST_DATA has a HELLO message piggybacked, so   // process this first   BCAST_Neighbor *nb;#ifdef DEBUG   fprintf(stderr, "Node %d: processing piggybacked HELLO from %d\n",	index, bh->dst);#endif   nb = nb_lookup(bh->dst);   if(nb == 0) {	nb_insert(bh->dst);	nb = nb_lookup(bh->dst);   }   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);   forward(p);   break;#endif default:   fprintf(stderr, "Invalid BCAST type (%x)\n", bh->type);   exit(1); }}/*   Packet Transmission Routines*/voidBCAST::forward(Packet *p) {struct hdr_cmn *ch = HDR_CMN(p);struct hdr_ip *ih = HDR_IP(p);struct hdr_rtp *rh = HDR_RTP(p);#ifdef PIGGYBACK_HELLOstruct hdr_bcast *bh = HDR_BCAST(p);#endif// keep track of neighbors not coveredint no_of_neighbors;nsaddr_t neighbors[NEIGHBOR_COUNT];nsaddr_t src = ih->saddr();unsigned int seqno = rh->seqno_;mt_entry *mt;int n, max; // keep track of packet reception to control NACK frequency nacktimer.save_packet_time(CURRENT_TIME); // See whether received packet (i.e. not originating from us) allows us  // to prune pending BCASTS. // We need to find the neighbourhood information for the sender and // process this against the information stored in each pending BCAST BCAST_Neighbor* nb; if (ih->saddr() != index && ((nb = nb_lookup(ch->prev_hop_)) != NULL)) {