dsr-routing.h

Go to the documentation of this file.

/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/*
 * Copyright (c) 2011 Yufei Cheng
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as
 * published by the Free Software Foundation;
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 * Author: Yufei Cheng   <yfcheng@ittc.ku.edu>
 *
 * James P.G. Sterbenz <jpgs@ittc.ku.edu>, director
 * ResiliNets Research Group  http://wiki.ittc.ku.edu/resilinets
 * Information and Telecommunication Technology Center (ITTC)
 * and Department of Electrical Engineering and Computer Science
 * The University of Kansas Lawrence, KS USA.
 *
 * Work supported in part by NSF FIND (Future Internet Design) Program
 * under grant CNS-0626918 (Postmodern Internet Architecture),
 * NSF grant CNS-1050226 (Multilayer Network Resilience Analysis and Experimentation on GENI),
 * US Department of Defense (DoD), and ITTC at The University of Kansas.
 */

#ifndef DSR_ROUTING_H
#define DSR_ROUTING_H

#include <map>
#include <list>
#include <vector>
#include <stdint.h>
#include <cassert>
#include <sys/types.h>

#include "ns3/callback.h"
#include "ns3/object.h"
#include "ns3/node.h"
#include "ns3/ptr.h"
#include "ns3/buffer.h"
#include "ns3/packet.h"
#include "ns3/ipv4.h"
#include "ns3/ip-l4-protocol.h"
#include "ns3/ipv4-l3-protocol.h"
#include "ns3/icmpv4-l4-protocol.h"
#include "ns3/ipv4-interface.h"
#include "ns3/ipv4-header.h"
#include "ns3/ipv4-address.h"
#include "ns3/traced-callback.h"
#include "ns3/random-variable-stream.h"
#include "ns3/ipv4-route.h"
#include "ns3/timer.h"
#include "ns3/net-device.h"
#include "ns3/output-stream-wrapper.h"
#include "ns3/wifi-mac.h"
#include "ns3/socket.h"
#include "ns3/event-garbage-collector.h"
#include "ns3/test.h"

#include "dsr-network-queue.h"
#include "dsr-rcache.h"
#include "dsr-rreq-table.h"
#include "dsr-maintain-buff.h"
#include "dsr-option-header.h"
#include "dsr-fs-header.h"
#include "dsr-rsendbuff.h"
#include "dsr-errorbuff.h"
#include "dsr-gratuitous-reply-table.h"

namespace ns3 {

class Packet;
class Node;
class Ipv4;
class Ipv4Address;
class Ipv4Header;
class Ipv4Interface;
class Ipv4L3Protocol;
class Time;

namespace dsr {

class DsrOptions;
class DsrRouting : public IpL4Protocol
{
public:
  static TypeId GetTypeId ();
  static const uint8_t PROT_NUMBER;
  DsrRouting ();
  virtual ~DsrRouting ();
  Ptr<Node> GetNode () const;
  void SetNode (Ptr<Node> node);
  void SetRouteCache (Ptr<dsr::RouteCache> r);
  Ptr<dsr::RouteCache> GetRouteCache () const;
  void SetRequestTable (Ptr<dsr::RreqTable> r);
  Ptr<dsr::RreqTable> GetRequestTable () const;

  //\{
  bool IsLinkCache ();
  void UseExtends (RouteCacheEntry::IP_VECTOR rt);
  bool LookupRoute (Ipv4Address id, RouteCacheEntry & rt);
  bool AddRoute_Link (RouteCacheEntry::IP_VECTOR nodelist, Ipv4Address source);
  bool AddRoute (RouteCacheEntry & rt);
  void DeleteAllRoutesIncludeLink (Ipv4Address errorSrc, Ipv4Address unreachNode, Ipv4Address node);
  bool UpdateRouteEntry (Ipv4Address dst);
  //\}

  uint16_t GetIDfromIP (Ipv4Address address);
  Ipv4Address GetIPfromID (uint16_t id);
  Ipv4Address GetIPfromMAC (Mac48Address address);
  void PrintVector (std::vector<Ipv4Address>& vec);
  Ipv4Address SearchNextHop (Ipv4Address ipv4Address, std::vector<Ipv4Address>& vec);
  int GetProtocolNumber (void) const;
  void SendBuffTimerExpire ();
  void CheckSendBuffer ();
  void PacketNewRoute (Ptr<Packet> packet,
                       Ipv4Address source,
                       Ipv4Address destination,
                       uint8_t protocol);
  /*
   * \brief Set the route to use for data packets
   * \return the route
   * \used by the option headers when sending data/control packets
   */
  Ptr<Ipv4Route> SetRoute (Ipv4Address nextHop, Ipv4Address srcAddress);
  /*
   * \brief Set the priority of the packet in network queue
   * \return the priority value
   */
  uint32_t GetPriority (DsrMessageType messageType);
  /*
   * \brief This function is responsible for sending error packets in case of break link to next hop
   */
  void SendUnreachError (Ipv4Address errorHop, Ipv4Address destination, Ipv4Address originalDst, uint8_t salvage, uint8_t protocol);
  /*
   * \brief This function is responsible for forwarding error packets along the route
   */
  void ForwardErrPacket (DsrOptionRerrUnreachHeader &rerr,
                         DsrOptionSRHeader &sourceRoute,
                         Ipv4Address nextHop,
                         uint8_t protocol,
                         Ptr<Ipv4Route> route);
  /*
   * \brief This function is called by higher layer protocol when sending packets
   */
  void Send (Ptr<Packet> packet, Ipv4Address source,
             Ipv4Address destination, uint8_t protocol, Ptr<Ipv4Route> route);
  /*
   * \brief This function is called to add ack request header for network acknowledgement
   */
  uint16_t AddAckReqHeader (Ptr<Packet> &packet, Ipv4Address nextHop);
  /*
   * \brief This function is called by when really sending out the packet
   */
  void SendPacket (Ptr<Packet> packet, Ipv4Address source, Ipv4Address nextHop, uint8_t protocol);
  /*
   * \brief This function is called to schedule sending packets from the network queue
   */
  void Scheduler (uint32_t priority);
  /*
   * \brief This function is called to schedule sending packets from the network queue by priority
   */
  void PriorityScheduler (uint32_t priority, bool continueWithFirst);
  /*
   * \brief This function is called to increase the retransmission timer for data packet in the network queue
   */
  void IncreaseRetransTimer ();
  /*
   * \brief This function is called to send packets down stack
   */
  bool SendRealDown (DsrNetworkQueueEntry & newEntry);
  /*
   * This function is responsible for sending out data packets when have route, if no route found, it will
   * cache the packet and send out route requests
   */
  void SendPacketFromBuffer (DsrOptionSRHeader const &sourceRoute,
                             Ipv4Address nextHop,
                             uint8_t protocol);
  /*
   * \brief Find the similar entries in the maintenance buffer
   */
  bool FindSamePackets (Ptr<Packet> packet, Ipv4Address source, Ipv4Address destination, uint8_t segsLeft);
  /*
   * Call the cancel packet retransmission timer function
   */
  void CallCancelPacketTimer (uint16_t ackId, Ipv4Header const& ipv4Header, Ipv4Address realSrc, Ipv4Address realDst);
  /*
   * Cancel the network packet retransmission timer for a specific maintenance entry
   */
  void CancelNetworkPacketTimer (MaintainBuffEntry & mb);
  /*
   * Cancel the passive packet retransmission timer for a specific maintenance entry
   */
  void CancelPassivePacketTimer (MaintainBuffEntry & mb);
  /*
   * Cancel the packet retransmission timer for a all maintenance entries with nextHop address
   */
  void CancelPacketTimerNextHop (Ipv4Address nextHop, uint8_t protocol);
  /*
   * Salvage the packet which has been transmitted for 3 times
   */
  void SalvagePacket (Ptr<const Packet> packet, Ipv4Address source, Ipv4Address dst, uint8_t protocol);
  /*
   * Schedule the packet retransmission when the packet has not reached to the next hop address
   */
  void SchedulePassivePacketRetry   (MaintainBuffEntry & mb,
                                     bool onlyPassive,
                                     uint8_t protocol);
  /*
   * Schedule the packet retransmission when the packet has not reached to the next hop address
   */
  void ScheduleNetworkPacketRetry   (MaintainBuffEntry & mb,
                                     bool isFirst,
                                     uint8_t protocol);
  /*
   * This function deals with packet retransmission timer expire
   */
  void NetworkScheduleTimerExpire  (MaintainBuffEntry & mb,
                                    uint8_t protocol);
  /*
   * This function deals with packet retransmission timer expire
   */
  void PassiveScheduleTimerExpire  (MaintainBuffEntry & mb,
                                    bool onlyPassive,
                                    uint8_t protocol);
  /*
   * Forward the packet using the route saved in the source route option header
   */
  void ForwardPacket (Ptr<const Packet> packet,
                      DsrOptionSRHeader &sourceRoute,
                      Ipv4Header const& ipv4Header,
                      Ipv4Address source,
                      Ipv4Address destination,
                      Ipv4Address targetAddress,
                      uint8_t protocol,
                      Ptr<Ipv4Route> route);
  /*
   * Broadcast the route request packet in subnet
   */
  void SendInitialRequest (Ipv4Address source,
                           Ipv4Address destination,
                           uint8_t protocol);
  /*
   * \brief Send the error request packet
   * \param the route error header
   * \param the protocol number
   */
  void SendErrorRequest (DsrOptionRerrUnreachHeader &rerr, uint8_t protocol);
  /*
   * \brief Send the route request and increment the request count
   * \param the original packet
   * \param source address
   * \param destination address
   */
  void SendRequestAndIncrement (Ptr<Packet> packet,
                                Ipv4Address source,
                                Ipv4Address destination);
  /*
   * \brief Forward the route request if the node is not the destination
   * \param the original packet
   * \param source address
   */
  void SendRequest (Ptr<Packet> packet,
                    Ipv4Address source);
  /*
   * \brief Schedule the intermediate route request
   * \param the original packet
   * \param source The source address
   * \param destination The destination address
   */
  void ScheduleInterRequest (Ptr<Packet> packet);
  /*
   * \brief Send the gratuitous reply
   * \param replyTo The destination address to send the reply to
   * \param replyFrom The source address sending the reply
   */
  void SendGratuitousReply (Ipv4Address replyTo,
                            Ipv4Address replyFrom,
                            std::vector<Ipv4Address> &nodeList,
                            uint8_t protocol);
  /*
   * Send the route reply back to the request originator with the cumulated route
   */
  void SendReply (Ptr<Packet> packet,
                  Ipv4Address source,
                  Ipv4Address nextHop,
                  Ptr<Ipv4Route> route);
  /*
   * this is a generating the initial route reply from the destination address, a random delay time
   * [0, m_broadcastJitter] is used before unicasting back the route reply packet
   */
  void ScheduleInitialReply (Ptr<Packet> packet,
                             Ipv4Address source,
                             Ipv4Address nextHop,
                             Ptr<Ipv4Route> route);
  /*
   * Schedule the cached reply to a random start time to avoid possible route reply storm
   */
  void ScheduleCachedReply (Ptr<Packet> packet,
                            Ipv4Address source,
                            Ipv4Address destination,
                            Ptr<Ipv4Route> route,
                            double hops);
  /*
   * Send network layer acknowledgment back to the earlier hop to notify the receipt of data packet
   */
  void SendAck   (uint16_t ackId,
                  Ipv4Address destination,
                  Ipv4Address realSrc,
                  Ipv4Address realDst,
                  uint8_t protocol,
                  Ptr<Ipv4Route> route);
  /*
   * Get the node using the ip address
   */
  Ptr<Node> GetNodeWithAddress (Ipv4Address ipv4Address);
  virtual enum IpL4Protocol::RxStatus Receive (Ptr<Packet> p,
                                               Ipv4Header const &header,
                                               Ptr<Ipv4Interface> incomingInterface);

  virtual enum IpL4Protocol::RxStatus Receive (Ptr<Packet> p,
                                               Ipv6Header const &header,
                                               Ptr<Ipv6Interface> incomingInterface);

  void SetDownTarget (IpL4Protocol::DownTargetCallback callback);
  void SetDownTarget6 (IpL4Protocol::DownTargetCallback6 callback);
  IpL4Protocol::DownTargetCallback GetDownTarget (void) const;
  IpL4Protocol::DownTargetCallback6 GetDownTarget6 (void) const;
  uint8_t GetExtensionNumber () const;
  uint8_t Process (Ptr<Packet>& packet, Ipv4Header const& ipv4Header, Ipv4Address dst, uint8_t *nextHeader, uint8_t protocol, bool& isDropped);
  void Insert (Ptr<dsr::DsrOptions> option);
  Ptr<dsr::DsrOptions> GetOption (int optionNumber);
  void CancelRreqTimer (Ipv4Address dst, bool isRemove);
  void ScheduleRreqRetry (Ptr<Packet> packet, std::vector<Ipv4Address> address, bool nonProp, uint32_t requestId, uint8_t protocol);
  // / Handle route discovery timer
  void RouteRequestTimerExpire (Ptr<Packet> packet, std::vector<Ipv4Address> address, uint32_t requestId, uint8_t protocol);

  int64_t AssignStreams (int64_t stream);

protected:
  /*
 *    * This function will notify other components connected to the node that a new stack member is now connected
 *       * This will be used to notify Layer 3 protocol of layer 4 protocol stack to connect them together.
 *          */
  virtual void NotifyNewAggregate ();
  virtual void DoDispose (void);
  /*
   * The trace for drop, receive and send data packets
   */
  TracedCallback<Ptr<const Packet> > m_dropTrace;
  TracedCallback <const DsrOptionSRHeader &> m_txPacketTrace;

private:
  void Start ();
  void SendRerrWhenBreaksLinkToNextHop (Ipv4Address nextHop, uint8_t protocol);
  bool PromiscReceive (Ptr<NetDevice> device, Ptr<const Packet> packet, uint16_t protocol, const Address &from,
                       const Address &to, NetDevice::PacketType packetType);
  typedef std::list<Ptr<DsrOptions> > DsrOptionList_t;
  DsrOptionList_t m_options;

  Ptr<Ipv4L3Protocol> m_ipv4;        // / Ipv4l3Protocol

  Ptr<Ipv4Route> m_ipv4Route;        // / Ipv4 Route

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

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

  Ipv4Address m_mainAddress;         // / Our own Ip address

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

  IpL4Protocol::DownTargetCallback m_downTarget;    // The callback for down layer

  uint32_t m_maxNetworkSize;             // / Maximum network queue size

  Time m_maxNetworkDelay;                // / Maximum network delay

  uint32_t m_discoveryHopLimit;             // / Maximum hops to go for route request

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

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

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

  uint32_t m_sendRetries;                    // / # of retries have been sent for network acknowledgment

  uint32_t m_passiveRetries;                 // / # of retries have been sent for passive acknowledgment

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

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

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

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

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

  SendBuffer m_sendBuffer;               // / The send buffer

  ErrorBuffer m_errorBuffer;             // / The error buffer to save the error messages

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

  Time     m_maxMaintainTime;            // / Time out for maintainance buffer

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

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

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

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

  MaintainBuffer m_maintainBuffer;       // / The declaration of maintain buffer

  uint32_t m_requestId;                  // / The id assigned to each route request

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

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

  uint32_t m_requestTableIds;              // / The request table identifiers

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

  Time  m_blacklistTimeout;                // / The black list time out

  Ipv4Address m_broadcast;                 // / The broadcast IP address

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

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

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

  Timer m_sendBuffTimer;                 // / The send buffer timer

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

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

  Time m_maxRequestPeriod;                 // / The max request period

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

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

  std::string m_routeSortType;         // / The type of route sort methods

  uint64_t m_stabilityDecrFactor;           // / The initial decrease factor for link cache

  uint64_t m_stabilityIncrFactor;           // / The initial increase factor for link cache

  Time m_initStability;                 // / The initial stability value for link cache

  Time m_minLifeTime;                   // / The min life time

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

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

  Time m_retransIncr;                     // / the increase time for retransmission timer when face network congestion

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

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

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

  std::map<NetworkKey, Timer>  m_addressForwardTimer;    // / Map network key + forward timer.

  std::map<NetworkKey, uint32_t> m_addressForwardCnt;      // / Map network key + forward counts.

  std::map<PassiveKey, uint32_t> m_passiveCnt;             // / Map packet key + passive forward counts.

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

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

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

  uint32_t m_numPriorityQueues;

  std::map<uint32_t, Ptr<dsr::DsrNetworkQueue> > m_priorityQueue;   // / priority queueus

  GraReply m_graReply;                    // / The gratuitous route reply.

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

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

  Ptr<UniformRandomVariable> m_uniformRandomVariable;  
};
}  /* namespace dsr */
}  /* namespace ns3 */

#endif /* DSR_ROUTING_H */