1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */

     2 /*

     3  * Copyright (c) 2011 Yufei Cheng

     4  *

     5  * This program is free software; you can redistribute it and/or modify

     6  * it under the terms of the GNU General Public License version 2 as

     7  * published by the Free Software Foundation;

     8  *

     9  * This program is distributed in the hope that it will be useful,

    10  * but WITHOUT ANY WARRANTY; without even the implied warranty of

    11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

    12  * GNU General Public License for more details.

    13  *

    14  * You should have received a copy of the GNU General Public License

    15  * along with this program; if not, write to the Free Software

    16  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

    17  *

    18  * Author: Yufei Cheng   <yfcheng@ittc.ku.edu>

    19  *

    20  * James P.G. Sterbenz <jpgs@ittc.ku.edu>, director

    21  * ResiliNets Research Group  http://wiki.ittc.ku.edu/resilinets

    22  * Information and Telecommunication Technology Center (ITTC)

    23  * and Department of Electrical Engineering and Computer Science

    24  * The University of Kansas Lawrence, KS USA.

    25  *

    26  * Work supported in part by NSF FIND (Future Internet Design) Program

    27  * under grant CNS-0626918 (Postmodern Internet Architecture),

    28  * NSF grant CNS-1050226 (Multilayer Network Resilience Analysis and Experimentation on GENI),

    29  * US Department of Defense (DoD), and ITTC at The University of Kansas.

    30  */

    31 

    32 #ifndef DSR_ROUTING_H

    33 #define DSR_ROUTING_H

    34 

    35 #include <map>

    36 #include <list>

    37 #include <vector>

    38 #include <stdint.h>

    39 #include <cassert>

    40 #include <sys/types.h>

    41 

    42 #include "ns3/callback.h"

    43 #include "ns3/object.h"

    44 #include "ns3/node.h"

    45 #include "ns3/ptr.h"

    46 #include "ns3/buffer.h"

    47 #include "ns3/packet.h"

    48 #include "ns3/ipv4.h"

    49 #include "ns3/ipv4-l4-protocol.h"

    50 #include "ns3/ipv4-l3-protocol.h"

    51 #include "ns3/icmpv4-l4-protocol.h"

    52 #include "ns3/ipv4-interface.h"

    53 #include "ns3/ipv4-header.h"

    54 #include "ns3/ipv4-address.h"

    55 #include "ns3/traced-callback.h"

    56 #include "ns3/ipv4-route.h"

    57 #include "ns3/timer.h"

    58 #include "ns3/net-device.h"

    59 #include "ns3/output-stream-wrapper.h"

    60 #include "ns3/wifi-mac.h"

    61 #include "ns3/socket.h"

    62 #include "ns3/event-garbage-collector.h"

    63 #include "ns3/test.h"

    64 

    65 #include "dsr-rcache.h"

    66 #include "dsr-rreq-table.h"

    67 #include "dsr-maintain-buff.h"

    68 #include "dsr-option-header.h"

    69 #include "dsr-fs-header.h"

    70 #include "dsr-rsendbuff.h"

    71 #include "dsr-gratuitous-reply-table.h"

    72 

    73 namespace ns3 {

    74 

    75 class Packet;

    76 class Node;

    77 class Ipv4;

    78 class Ipv4Address;

    79 class Ipv4Header;

    80 class Ipv4Interface;

    81 class Ipv4L3Protocol;

    82 class Time;

    83 

    84 namespace dsr {

    85 

    86 class DsrOptions;

    87 /**

    88  * \class DsrRouting

    89  * \brief Dsr Routing base

    90  */

    91 class DsrRouting : public Ipv4L4Protocol

    92 {

    93 public:

    94   /**

    95    * \brief Get the type identificator.

    96    * \return type identificator

    97    */

    98   static TypeId GetTypeId ();

    99   /**

   100     * \brief Define the dsr protocol number.

   101     */

   102   static const uint8_t PROT_NUMBER;

   103   /**

   104    * \brief Constructor.

   105    */

   106   DsrRouting ();

   107   /**

   108    * \brief Destructor.

   109    */

   110   virtual ~DsrRouting ();

   111   /**

   112    * \brief Get the node.

   113    * \return the node

   114    */

   115   Ptr<Node> GetNode () const;

   116   /**

   117    * \brief Set the node.

   118    * \param node the node to set

   119    */

   120   void SetNode (Ptr<Node> node);

   121   /**

   122    * \brief Set the route cache.

   123    * \param the route cache to set

   124    */

   125   void SetRouteCache (Ptr<dsr::RouteCache> r);

   126   /**

   127    * \brief Get the route cache.

   128    * \return the route cache

   129    */

   130   Ptr<dsr::RouteCache> GetRouteCache () const;

   131   /**

   132    * \brief Set the node.

   133    * \param the request table to set

   134    */

   135   void SetRequestTable (Ptr<dsr::RreqTable> r);

   136   /**

   137     * \brief Get the request table.

   138     * \return the request table

   139     */

   140   Ptr<dsr::RreqTable> GetRequestTable () const;

   141   /**

   142     * \brief Get the node id from ip address.

   143     * \return the node id

   144     */

   145   uint32_t GetIDfromIP (Ipv4Address address);

   146   /**

   147     * \brief Get the ip address from id.

   148     * \return the ip address for the id

   149     */

   150   Ipv4Address GetIPfromID (uint32_t id);

   151   /**

   152     * \brief Get the Ip address from mac address.

   153     * \return the ip address

   154     */

   155   Ipv4Address GetIPfromMAC (Mac48Address address);

   156   /**

   157     * \brief Print the route vector.

   158     */

   159   void PrintVector (std::vector<Ipv4Address>& vec);

   160   /**

   161     * \brief Get the next hop of the route.

   162     * \return the next hop address of the route

   163     */

   164   Ipv4Address SearchNextHop (Ipv4Address ipv4Address, std::vector<Ipv4Address>& vec);

   165   /**

   166     * \brief Cut the route before our own ip address

   167     */

   168   void CutRoute (Ipv4Address ourAdd, std::vector<Ipv4Address>& nodeList);

   169   /**

   170     * \brief Get the dsr protocol number.

   171     * \return protocol number

   172     */

   173   int GetProtocolNumber (void) const;

   174   /**

   175     * \brief The send buffer timer expire.

   176     */

   177   void SendBuffTimerExpire ();

   178   /**

   179     * \brief Check the send buffer of packets with route when send buffer timer expire.

   180     */

   181   void CheckSendBuffer ();

   182   /**

   183     * \brief When route vector corrupted, originate a new packet, normally not happening.

   184     */

   185   void PacketNewRoute (Ptr<Packet> packet,

   186                        Ipv4Address source,

   187                        Ipv4Address destination,

   188                        uint8_t protocol);

   189   /*

   190    * \brief Set the route to use for data packets

   191    * \return the route

   192    * \used by the option headers when sending data/control packets

   193    */

   194   Ptr<Ipv4Route> SetRoute (Ipv4Address nextHop, Ipv4Address srcAddress);

   195   /*

   196    * \brief This function is responsible for sending error packets in case of break link to next hop

   197    */

   198   void SendUnreachError (Ipv4Address errorHop, Ipv4Address destination, uint8_t salvage, uint8_t protocol);

   199   /*

   200    * \brief This function is responsible for forwarding error packets along the route

   201    */

   202   void ForwardErrPacket (DsrOptionRerrUnreachHeader &rerr,

   203                          DsrOptionSRHeader &sourceRoute,

   204                          Ipv4Address nextHop,

   205                          uint8_t protocol,

   206                          Ptr<Ipv4Route> route);

   207   /*

   208    * \brief This function is called by higher layer protocol when sending packets

   209    */

   210   void Send (Ptr<Packet> packet, Ipv4Address source,

   211              Ipv4Address destination, uint8_t protocol, Ptr<Ipv4Route> route);

   212   /*

   213    * This function is responsible for sending out data packets when have route, if no route found, it will

   214    * cache the packet and send out route requests

   215    */

   216   void SendPacket (DsrOptionSRHeader const &sourceRoute,

   217                    Ipv4Address nextHop,

   218                    uint8_t protocol);

   219   /*

   220    * \brief Find the similar entries in the maintenance buffer

   221    */

   222   bool FindSamePackets (Ptr<Packet> packet, Ipv4Header const& ipv4Header, Ipv4Address source, Ipv4Address destination,

   223                         uint8_t segsLeft);

   224   /*

   225    * Call the cancel packet retransmission timer function

   226    */

   227   void CallCancelPacketTimer (uint16_t ackId, Ipv4Header const& ipv4Header, Ipv4Address realSrc, Ipv4Address realDst);

   228   /*

   229    * Cancel the network packet retransmission timer for a specific maintenance entry

   230    */

   231   void CancelNetworkPacketTimer (MaintainBuffEntry & mb);

   232   /*

   233    * Cancel the passive packet retransmission timer for a specific maintenance entry

   234    */

   235   void CancelPassivePacketTimer (MaintainBuffEntry & mb);

   236   /*

   237    * Cancel the packet retransmission timer for a all maintenance entries with nextHop address

   238    */

   239   void CancelPacketTimerNextHop (Ipv4Address nextHop, uint8_t protocol);

   240   /*

   241    * Salvage the packet which has been transmitted for 3 times

   242    */

   243   void SalvagePacket (Ptr<const Packet> packet, Ipv4Address source, Ipv4Address dst, uint8_t protocol);

   244   /*

   245    * Add ack request header to the data packet when need to use network acknowledgment

   246    */

   247   void AddAckReqHeader (Ptr<Packet> packet, DsrOptionSRHeader const &sourceRoute, Ipv4Address nextHop);

   248   /*

   249    * Schedule the packet retransmission when the packet has not reached to the next hop address

   250    */

   251   void SchedulePacketRetry   (MaintainBuffEntry & mb,

   252                               PacketKey const & packetKey,

   253                               uint8_t protocol);

   254   /*

   255    * This function deals with packet retransmission timer expire

   256    */

   257   void PacketScheduleTimerExpire  (MaintainBuffEntry & mb,

   258                                    PacketKey const & pk,

   259                                    uint8_t protocol,

   260                                    bool isPassive);

   261   /*

   262    * Forward the packet using the route saved in the source route option header

   263    */

   264   void ForwardPacket (Ptr<const Packet> packet,

   265                       DsrOptionSRHeader &sourceRoute,

   266                       Ipv4Header const& ipv4Header,

   267                       Ipv4Address source,

   268                       Ipv4Address destination,

   269                       Ipv4Address targetAddress,

   270                       uint8_t protocol,

   271                       Ptr<Ipv4Route> route);

   272   /*

   273    * Broadcast the route request packet in subnet

   274    */

   275   void SendInitialRequest (Ipv4Address source,

   276                            Ipv4Address destination,

   277                            uint8_t protocol);

   278   /*

   279    * \brief Send the error request packet

   280    * \param the route error header

   281    * \param the protocol number

   282    */

   283   void SendErrorRequest (DsrOptionRerrUnreachHeader &rerr, uint8_t protocol);

   284   /*

   285    * \brief Send the route request and increment the request count

   286    * \param the original packet

   287    * \param source address

   288    * \param destination address

   289    */

   290   void SendRequestAndIncrement (Ptr<Packet> packet,

   291                                 Ipv4Address source,

   292                                 Ipv4Address destination);

   293   /*

   294    * \brief Forward the route request if the node is not the destination

   295    * \param the original packet

   296    * \param source address

   297    */

   298   void SendRequest (Ptr<Packet> packet,

   299                     Ipv4Address source);

   300   /*

   301    * \brief Schedule the intermediate route request

   302    * \param the original packet

   303    * \param source The source address

   304    * \param destination The destination address

   305    */

   306   void ScheduleInterRequest (Ptr<Packet> packet);

   307   /*

   308    * \brief Send the gratuitous reply

   309    * \param replyTo The destination address to send the reply to

   310    * \param replyFrom The source address sending the reply

   311    */

   312   void SendGratuitousReply (Ipv4Address replyTo,

   313                             Ipv4Address replyFrom,

   314                             std::vector<Ipv4Address> &nodeList,

   315                             uint8_t protocol);

   316   /*

   317    * Send the route reply back to the request originator with the cumulated route

   318    */

   319   void SendReply (Ptr<Packet> packet,

   320                   Ipv4Address source,

   321                   Ipv4Address nextHop,

   322                   Ptr<Ipv4Route> route);

   323   /*

   324    * this is a generating the initial route reply from the destination address, a random delay time

   325    * [0, m_broadcastJitter] is used before unicasting back the route reply packet

   326    */

   327   void ScheduleInitialReply (Ptr<Packet> packet,

   328                              Ipv4Address source,

   329                              Ipv4Address nextHop,

   330                              Ptr<Ipv4Route> route);

   331   /*

   332    * Schedule the cached reply to a random start time to avoid possible route reply storm

   333    */

   334   void ScheduleCachedReply (Ptr<Packet> packet,

   335                             Ipv4Address source,

   336                             Ipv4Address destination,

   337                             Ptr<Ipv4Route> route,

   338                             uint16_t hops);

   339   /*

   340    * Send network layer acknowledgment back to the earlier hop to notify the receipt of data packet

   341    */

   342   void SendAck   (uint16_t ackId,

   343                   Ipv4Address destination,

   344                   Ipv4Address realSrc,

   345                   Ipv4Address realDst,

   346                   uint8_t protocol,

   347                   Ptr<Ipv4Route> route);

   348   /*

   349    * Get the node using the ip address

   350    */

   351   Ptr<Node> GetNodeWithAddress (Ipv4Address ipv4Address);

   352   /**

   353    * \param p packet to forward up

   354    * \param header IPv4 Header information

   355    * \param incomingInterface the Ipv4Interface on which the packet arrived

   356    *

   357    * Called from lower-level layers to send the packet up

   358    * in the stack.

   359    */

   360   virtual enum Ipv4L4Protocol::RxStatus Receive (Ptr<Packet> p,

   361                                                  Ipv4Header const &header,

   362                                                  Ptr<Ipv4Interface> incomingInterface);

   363 

   364   void SetDownTarget (Ipv4L4Protocol::DownTargetCallback callback);

   365   Ipv4L4Protocol::DownTargetCallback GetDownTarget (void) const;

   366   /**

   367    * \brief Get the extension number.

   368    * \return extension number

   369    */

   370   uint8_t GetExtensionNumber () const;

   371   /**

   372    * \brief Process method

   373    * Called from Ipv4L3Protocol::Receive.

   374    *

   375    * \param packet the packet

   376    * \param offset the offset of the extension to process

   377    * \param dst destination address of the packet received (i.e. us)

   378    * \param nextHeader the next header

   379    * \param isDropped if the packet must be dropped

   380    * \return the size processed

   381    */

   382   uint8_t Process (Ptr<Packet>& packet, Ipv4Header const& ipv4Header, Ipv4Address dst, uint8_t *nextHeader, uint8_t protocol, bool& isDropped);

   383   /**

   384    * \brief Insert a new Dsr Option.

   385    * \param option the option to insert

   386    */

   387   void Insert (Ptr<dsr::DsrOptions> option);

   388   /**

   389    * \brief Get the option corresponding to optionNumber.

   390    * \param optionNumber the option number of the option to retrieve

   391    * \return a matching Dsr option

   392    */

   393   Ptr<dsr::DsrOptions> GetOption (int optionNumber);

   394   /**

   395    * \brief Cancel the route request timer.

   396    * \param dst The dst address of the route request timer

   397    */

   398   void CancelRreqTimer (Ipv4Address dst);

   399   /**

   400    * \brief Schedule the route request retry.

   401    * \param dst The dst address of the route request

   402    */

   403   void ScheduleRreqRetry (Ptr<Packet> packet, Ipv4Address source, Ipv4Address dst, bool nonProp, uint8_t protocol);

   404   // / Handle route discovery timer

   405   void RouteRequestTimerExpire (Ptr<Packet> packet, Ipv4Address source, Ipv4Address dst, uint8_t protocol);

   406 

   407 protected:

   408   /*

   409  *    * This function will notify other components connected to the node that a new stack member is now connected

   410  *       * This will be used to notify Layer 3 protocol of layer 4 protocol stack to connect them together.

   411  *          */

   412   virtual void NotifyNewAggregate ();

   413   /**

   414    * \brief Drop trace callback.

   415    */

   416   virtual void DoDispose (void);

   417   /*

   418    * The trace for drop, receive and send data packets

   419    */

   420   TracedCallback<Ptr<const Packet> > m_dropTrace;

   421   TracedCallback <const DsrOptionSRHeader &> m_txPacketTrace;

   422 

   423 private:

   424   void Start ();

   425   /**

   426    * \brief Send the route error message when the link breaks to the next hop.

   427    */

   428   void SendRerrWhenBreaksLinkToNextHop (Ipv4Address nextHop, uint8_t protocol);

   429   /**

   430    * \brief Promiscuous receive data packets destined to some other node.

   431    */

   432   bool PromiscReceive (Ptr<NetDevice> device, Ptr<const Packet> packet, uint16_t protocol, const Address &from,

   433                        const Address &to, NetDevice::PacketType packetType);

   434   /**

   435    * \brief Define the list to hold DSR options.

   436    */

   437   typedef std::list<Ptr<DsrOptions> > DsrOptionList_t;

   438   /**

   439    * \brief List of DSR Options supported.

   440    */

   441   DsrOptionList_t m_options;

   442 

   443   Ptr<Ipv4L3Protocol> m_ipv4;        // / Ipv4l3Protocol

   444 

   445   Ptr<Ipv4Route> m_ipv4Route;        // / Ipv4 Route

   446 

   447   Ptr<Ipv4> m_ip;                    // / The ip ptr

   448 

   449   Ptr<Node> m_node;                  // / The node ptr

   450 

   451   Ipv4Address m_mainAddress;         // / Our own Ip address

   452 

   453   uint8_t segsLeft;                  // / The segment left value from SR header

   454 

   455   Ipv4L4Protocol::DownTargetCallback m_downTarget;    // The callback for down layer

   456 

   457   uint8_t m_discoveryHopLimit;             // / Maximum hops to go for route request

   458 

   459   uint8_t m_maxSalvageCount;             // / Maximum # times to salvage a packet

   460 

   461   Time  m_requestPeriod;                   // / The base time interval between route requests

   462 

   463   Time m_nonpropRequestTimeout;            // / The non-propagation request timeout

   464 

   465   uint32_t  m_sendRetries;                // / # of retries have been sent for data packet

   466 

   467   uint32_t m_rreqRetries;                  // /< Maximum number of retransmissions of RREQ with TTL = NetDiameter to discover a route

   468 

   469   uint32_t m_maxMaintRexmt;                  // /< Maximum number of retransmissions of data packets

   470 

   471   Time m_nodeTraversalTime;                // / Time estimated for packet to travel between two nodes

   472 

   473   uint32_t m_maxSendBuffLen;             // /< The maximum number of packets that we allow a routing protocol to buffer.

   474 

   475   Time  m_sendBufferTimeout;               // /< The maximum period of time that a routing protocol is allowed to buffer a packet for.

   476 

   477   SendBuffer m_sendBuffer;               // / The send buffer

   478 

   479   uint32_t  m_maxMaintainLen;            // / Max # of entries for maintainance buffer

   480 

   481   Time     m_maxMaintainTime;            // / Time out for maintainance buffer

   482 

   483   uint32_t m_maxCacheLen;                // / Max # of cache entries for route cache

   484 

   485   Time   m_maxCacheTime;                 // / Max time for caching the route cache entry

   486 

   487   Time  m_maxRreqTime;                   // / Max time for caching the route request entry

   488 

   489   uint32_t  m_maxEntriesEachDst;         // / Max number of route entries to save for each destination

   490 

   491   MaintainBuffer m_maintainBuffer;       // / The declaration of maintain buffer

   492 

   493   uint16_t m_requestId;                  // / The id assigned to each route request

   494 

   495   uint16_t m_ackId;                      // / The ack id assigned to each acknowledge

   496 

   497   uint32_t m_requestTableSize;             // / The max size of the request table size

   498 

   499   uint32_t m_requestTableIds;              // / The request table identifiers

   500 

   501   uint32_t m_maxRreqId;                  // / The max number of request ids for a single destination

   502 

   503   Time  m_blacklistTimeout;                // / The black list time out

   504 

   505   Ipv4Address m_broadcast;                 // / The broadcast IP address

   506 

   507   uint16_t m_broadcastJitter;              // / The max time to delay route request broadcast.

   508 

   509   Time  m_passiveAckTimeout;               // / The timeout value for passive acknowledge

   510 

   511   uint32_t m_tryPassiveAcks;               // /< Maximum number of packet transmission using passive acknowledgment

   512 

   513   Timer m_sendBuffTimer;                 // / The send buffer timer

   514 

   515   Time m_sendBuffInterval;               // / how often to check send buffer

   516 

   517   Time  m_gratReplyHoldoff;                // / The max gratuitous reply hold off time

   518 

   519   Time m_maxRequestPeriod;                 // / The max request period

   520 

   521   uint32_t m_graReplyTableSize;            // / Set the gratuitous reply table size

   522 

   523   std::string m_cacheType;                // / The type of route cache

   524 

   525   double m_stabilityDecrFactor;           // / The initial decrease factor for link cache

   526 

   527   double m_stabilityIncrFactor;           // / The initial increase factor for link cache

   528 

   529   double m_initStability;                 // / The initial stability value for link cache

   530 

   531   double m_minLifeTime;                   // / The min life time

   532 

   533   double m_useExtends;                    // / The use extension of the life time for link cache

   534 

   535   bool m_subRoute;                        // / Whether to save sub route or not

   536 

   537   std::vector<Ipv4Address> m_finalRoute; // / The route cache

   538 

   539   std::map<Ipv4Address, Timer> m_addressReqTimer;        // / Map IP address + RREQ timer.

   540 

   541   std::map<Ipv4Address, Timer> m_nonPropReqTimer;        // / Map IP address + RREQ timer.

   542 

   543   std::map<PacketKey, Timer>  m_addressForwardTimer;   // / Map packet key + forward timer.

   544 

   545   std::map<PacketKey, uint32_t> m_addressForwardCnt;    // / Map packet key + forward counts.

   546 

   547   std::map<PacketKey, Timer> m_passiveAckTimer;               // / The timer for passive acknowledgment

   548 

   549   Ptr<dsr::RouteCache> m_routeCache;      // / A "drop-front" queue used by the routing layer to cache routes found.

   550 

   551   Ptr<dsr::RreqTable> m_rreqTable;        // / A "drop-front" queue used by the routing layer to cache route request sent.

   552 

   553   GraReply m_graReply;                    // / The gratuitous route reply.

   554 

   555   std::vector<Ipv4Address> m_clearList;   // / The node that is clear to send packet to

   556 

   557   uint32_t m_newPacketSize;               // / The packet size of a newly created packet

   558 

   559   std::vector<Ipv4Address> m_addresses;   // / The bind ipv4 addresses with next hop, src, destination address in sequence

   560 };

   561 }  /* namespace dsr */

   562 }  /* namespace ns3 */

   563 #endif /* DSR_ROUTING_H */