/************************************************************************* *   @<title> Self Healing Routing </title>@ * *   @<!-- Copyright 2006, 2003 Mark Lisee, Gilbert (Gang) Chen, Boleslaw *   K. Szymanski and Rensselaer Polytechnic Institute. All worldwide rights *   reserved.  A license to use, copy, modify and distribute this software *   for non-commercial research purposes only is hereby granted, provided *   that this copyright notice and accompanying disclaimer is not modified or *   removed from the software. * *   DISCLAIMER: The software is distributed "AS IS" without any *   express or implied warranty, including but not limited to, any *   implied warranties of merchantability or fitness for a particular *   purpose or any warranty of non-infringement of any current or *   pending patent rights. The authors of the software make no *   representations about the suitability of this software for any *   particular purpose. The entire risk as to the quality and *   performance of the software is with the user. Should the software *   prove defective, the user assumes the cost of all necessary *   servicing, repair or correction. In particular, neither Rensselaer *   Polytechnic Institute, nor the authors of the software are liable *   for any indirect, special, consequential, or incidental damages *   related to the software, to the maximum extent the law *   permits.-->@ * *************************************************************************/#ifndef _shr_h_#define _shr_h_#include <map>#include <list>#define	MWL_DOUBLE_DELAYconst int	MWLTimeoutMultiplier = 10;#ifdef	SHR_PRINT#define shrDoPrint	(true)#define	shrPrint(x)	 printf x#else	//SHR_PRINT#define	shrPrint(x)#define	shrDoPrint	(false)#endif	//SHR_PRINTtemplate <class PLD>struct SHR_Struct{  enum PktType { REQUEST, REPLY, DATA, ACK, HELLO };  enum AckType { AT_Destination, AT_Intermediate };  // RREQ: type + src_addr + dst_addr + seq_number + hop  enum { REQUEST_SIZE = 3 * sizeof(int) + 2 * ether_addr_t::LENGTH };  // RREP: type + src_addr + dst_addr + seq_number + 2 * hop  enum { REPLY_SIZE = 4 * sizeof(int) + 4 * ether_addr_t::LENGTH };  // DATA: type + src_addr + dst_addr + seq_number + 2* hop   enum { DATA_SIZE = 4 * sizeof(int) + 4 * ether_addr_t::LENGTH };  // ACK: type + ACK Type + src_addr + dst_addr + seq_number  enum { ACK_SIZE = 3 * sizeof(int) + 2 * ether_addr_t::LENGTH };  // HELLO: type + src_addr + dest_addr + hopCount  enum { HELLO_SIZE = 2 * sizeof( int) + 2 * ether_addr_t::LENGTH };      struct hdr_struct  {    PktType	type;    AckType	ackType;    ether_addr_t src_addr;    ether_addr_t dst_addr;    ether_addr_t cur_addr;    ether_addr_t pre_addr;    unsigned int seq_number;    unsigned int size;    double	send_time;    unsigned int actual_hop;    unsigned int expected_hop;    unsigned int max_hop;    double	delay;    int		ackIndex;    int		pktDelayIndex;    bool	canceled;    int		resend;    bool	suboptimal;    bool	newSeqNumber;    int		helloData;    Path	path;    bool dump(std::string& str) const;  };  typedef PLD payload_t;  typedef smart_packet_t<hdr_struct,PLD> packet_t;};/*** Array to keep track of how many packets required a certain number of hop** counts to reach the destination.*/#define	HCArraySize	(20+1)enum SHRBackOff{  SHRBackOff_SSR = 1,  SHRBackOff_SHR = 2,  SHRBackOff_Incorrect = 3};/*** The AckWindow is a period of time during which only Acks from intermediate** nodes are sent. This prevents the Acks from colliding with packets that are** being forwarded. Note that the destination sends its Ack as a normal packet,** i.e. after the AckWindow. This is because when node N forwards a packet, it** causes node N-1 to send an Ack (during the AckWindow) and N+1 to forward the** packet (after the AckWindow).*/template <class PLD>component SHR : public TypeII, public SHR_Struct<PLD>{ public:  ether_addr_t	MyEtherAddr;  simtime_t	ForwardDelay;  double	RXThresh;  bool		DumpPackets;  double	AckWindow;	// see comment above  int		MaxResend;  unsigned int	TimeToLive;  unsigned int	AdditionalHop;      // statistics  int		SentPackets;  int		SentSuboptimal;  int		CanceledPackets;  int		CanceledSuboptimal;  int		RecvPackets;  int		RecvUniPackets;  int		RecvDataPackets;  double	TotalDelay;  int		TotalSamples;  int		TotalHop;  int		HopCounts[ HCArraySize];  Timer <trigger_t> transitionTimer;	// time it takes to go from sense to send  inport void	TransitionTimer( trigger_t &);  packet_t	*transitionPkt;		// pkt to be sent when timer expires  inport inline void	from_transport( payload_t& pld, ether_addr_t& dst,					unsigned int size);  inport inline void	from_mac_data( packet_t* pkt, double power);  inport inline void	from_mac_ack( bool errflag);  inport inline void	from_mac_recv_recv_coll( packet_t *pkt1, packet_t *pkt2);  // This is called when the power manager wakes up the node.  inport void	from_pm_node_up();  outport void		cancel();  outport void		to_transport( payload_t &pld);  outport void		to_mac( packet_t *pkt, unsigned int size,				double backoff);  InfiTimer <SHR_Struct<PLD>::packet_t *> ackTimer;  inport inline void	AckTimer( packet_t *pkt, unsigned int index);/*** These methods must be defined even though they aren't used with the radio** model. This is due to a limitation of the cxx utility.**** This timer schedules the first HELLO packet that is generated when a node** comes back. Events on this timer should be scheduled only as a result of** parsing the configuration file.*/ private:  Timer <trigger_t> helloTimer; public:  inport inline void	HelloTimer( trigger_t &);/*** The public interface to schedule a HELLO packet.*/ public:  void		scheduleHELLO( double time);  void		Start();  void		Stop();  void		clearStats();		SHR();  virtual	~SHR();  int		getHCFromCostTable( int addr);  void		dumpStatic( FILE *fp, int indent, int offset) const;  void		dumpCacheStatic( FILE *fp, int indent, int offset) const;  void		dump( FILE *fp, int indent, int offset) const;  void		dumpCostTable( FILE *fp, int indent, int offset) const;  void		generateHELLO();  static void		setSlotWidth( double);  static double		getSlotWidth();  static void		setTransitionTime( double);  static double		getTransitionTime();  static void		setBackOff( SHRBackOff);  static SHRBackOff	getBackOff();  static void		setContinuousBackOff( bool);  static bool		getContinuousBackOff();  static void		setRouteRepair( int);  static void		setVisualizer( Visualizer *ptr);	 private:  enum UpdateType {Lower, Always, Hello};  bool		updateHopCountInCache( ether_addr_t src,				       unsigned int hopCount, UpdateType,				       const char *, packet_t *pkt); protected:  static SHRBackOff	backOff;  static bool		continuousBackOff;  static double		slotWidth;  static double		transitionTime;  static bool		RouteRepairEnabled;  static Visualizer	*visualizer;  void		CancelPacket( ether_addr_t& src, unsigned int seq_number);  void		SendPacket( packet_t *pkt);  void		AssignSeqNumber( packet_t *pkt);  void		SendToMac( packet_t *pkt);  void		SendAck( ether_addr_t, ether_addr_t, ether_addr_t, unsigned int,			 simtime_t, bool fromDest);  void		CheckBuffer( ether_addr_t, unsigned int);  void		AddToSendQueue( packet_t *pkt);  void		forwardAsFlood( packet_t *pkt);    // these return pointers to packet_t, but I wasn't able to figure out  // how to avoid compiler errors, therefore cast them to void *  void		*createBasicPkt();  void		*createDataPkt( payload_t &pld, ether_addr_t dst,				unsigned int size);  void		*createRequestPkt( ether_addr_t dst);  void		*createReplyPkt( ether_addr_t src, unsigned int expectedHop);  void		*createAckPkt( ether_addr_t src_addr, ether_addr_t cur_addr,			       ether_addr_t pre_addr, unsigned int seq_number,			       simtime_t delay, bool fromDest);  void		*createHelloPkt( ether_addr_t dest_addr, int hopCount);  bool		m_mac_busy;                  // if the mac layer is busy  unsigned int	m_seq_number;        // current sequence number  typedef std::list<packet_t* > packet_queue_t;  class seq_number_t  {  public:    seq_number_t () : state( Initial), current(0), bits(0u) {}    bool check(int n)      {	if( n + (int)sizeof(unsigned long) <= current )	  return true;	if ( n > current )	{	  bits = bits << (n - current);	  current = n;	}		unsigned long flag = 1 << (current - n);	unsigned long r = flag & bits;	bits |= flag;	return r;      }    unsigned int	hopCount() const;    void		hopCount( unsigned int newHC, bool force, bool print);    static void		setCounter( int);    static int		getCounter();    void		dumpStatic( FILE *fp, int indent, int offset) const;    void		dump( FILE *fp, int dest, int indent, int offset) const;  private:    unsigned int	currentHC;    unsigned int	pendingHC;    enum { Initial, Steady, Changing}	state;    int		updateCtr;    int		current;    uint32_t	bits;    static int	maxCounter;  };/******************************************************************* * For each source, we must maintain a @seq_number_t@ object, so we better * keep them in a map. *******************************************************************/  typedef std::map<ether_addr_t, seq_number_t, ether_addr_t::compare> cache_t;  cache_t	m_seq_cache;  packet_queue_t m_data_buffer;     private:  void		receiveAck( packet_t *ackPkt);  void		receiveDataRep( packet_t *rcvdPkt);  void		receiveHelloPacket( packet_t *pkt);  void		*getFromAckList( packet_t *rcvdPkt);  void		removeFromAckList( packet_t *pktToRemove, bool cancelTimer);  void		doRouteRepair( packet_t *pktFromList, packet_t *rcvdPkt);  static bool	doubleMsgPrinted;  packet_queue_t m_send_queue;  packet_queue_t m_ack_list;  packet_t	*m_active_packet; public:  InfiTimer <SHR_Struct<PLD>::packet_t *> pktDelayTimer;  inport inline void	PktDelayTimer( packet_t *pkt, unsigned int index); private:  packet_queue_t m_delay_list;};template <class PLD> SHRBackOff	SHR<PLD>::backOff;template <class PLD> bool	SHR<PLD>::continuousBackOff;template <class PLD> double	SHR<PLD>::slotWidth;template <class PLD> double	SHR<PLD>::transitionTime;template <class PLD> bool	SHR<PLD>::RouteRepairEnabled;template <class PLD> int	SHR<PLD>::seq_number_t::maxCounter = 1;template <class PLD> bool	SHR<PLD>::doubleMsgPrinted = false;template <class PLD> Visualizer	*SHR<PLD>::visualizer = NULL;template <class PLD>void SHR<PLD>::setVisualizer(  Visualizer	*ptr){  visualizer = ptr;  return;}template <class PLD>int SHR<PLD>::seq_number_t::getCounter(){  return maxCounter;}template <class PLD>void SHR<PLD>::seq_number_t::setCounter(  int	newCounter){  maxCounter = newCounter;  return;}template <class PLD>unsigned int SHR<PLD>::seq_number_t::hopCount() const{  switch( state)  {    case Initial:      return 0;    case Steady:    case Changing:      return currentHC;    default:      assert( 0);	// something really bad happened      return 0;  }}template <class PLD>void SHR<PLD>::seq_number_t::hopCount(  unsigned int	newHC,  bool		force,	// if true, then don't go through count  bool		print){  switch( state)  {    case Initial:      currentHC = newHC;      updateCtr = maxCounter;      state = Steady;      if( print) printf( "\n");      break;    case Steady:      if( newHC != currentHC)      {	if( force == true || maxCounter < 2)		// single step, so don't use state Changing	  currentHC = newHC;	else	{	  --updateCtr;	  pendingHC = newHC;	  state = Changing;	  if( print) printf( " start change");	}      }      if( print) printf( "\n");      break;    case Changing:			// only happens if maxCounter >= 2      if( force == true)      {	state = Steady;	currentHC = newHC;	updateCtr = maxCounter;	if( print) printf( " forced\n");      }      else if( newHC == currentHC)      {	if( ++updateCtr == maxCounter)	{	  state = Steady;	  if( print) printf(" back out of change\n");	}	else	  if( print) printf(" reversing\n");      }      else if( newHC == pendingHC)      {	if( --updateCtr == 0)	{	  currentHC = newHC;	  updateCtr = maxCounter;	  state = Steady;	  if( print) printf(" end change\n");	}	else	  if( print) printf(" still changing\n");      }      else	// newHC is neither the old nor new HC      {	pendingHC = newHC;	if( print) printf(" new HC during change\n");      }      break;    default:      assert( 0);	// something really bad happened  }  return;}template <class PLD>void *SHR<PLD>::createBasicPkt(){  packet_t	*newPkt = packet_t::alloc();  // type, ack_type, addresses set by caller  newPkt->hdr.seq_number = 0xFFFFFFFF;  // size set by caller  newPkt->hdr.send_time = SimTime();  newPkt->hdr.actual_hop = 1;  newPkt->hdr.expected_hop = 0;  newPkt->hdr.max_hop = 1;  newPkt->hdr.delay = 0.0;  newPkt->hdr.ackIndex = 0;  newPkt->hdr.pktDelayIndex = 0;  newPkt->hdr.canceled = false;  newPkt->hdr.resend = 0;  newPkt->hdr.suboptimal = false;  newPkt->hdr.newSeqNumber = false;  return newPkt;}/*** There is no delay when the source sends an packet.** This method isn't called when a packet is forwarded. Instead, the incoming** packet is copied to make the outgoing packet.*/template <class PLD>void *SHR<PLD>::createDataPkt(  payload_t	&pld,  ether_addr_t	dst,  unsigned int	size){  packet_t	*newPkt = (packet_t *) createBasicPkt();  newPkt->hdr.type = DATA;  newPkt->hdr.size = size + DATA_SIZE;  newPkt->hdr.src_addr = MyEtherAddr;  newPkt->hdr.dst_addr = dst;  newPkt->hdr.cur_addr = MyEtherAddr;  newPkt->hdr.pre_addr = MyEtherAddr;  newPkt->hdr.newSeqNumber = true;  newPkt->pld = pld;  return newPkt;}template <class PLD>void *SHR<PLD>::createRequestPkt(  ether_addr_t	dst){  packet_t	*newPkt = (packet_t *) createBasicPkt();  newPkt->hdr.type = REQUEST;  newPkt->hdr.size = REQUEST_SIZE;  newPkt->hdr.expected_hop  =  1;  newPkt->hdr.max_hop = TimeToLive;