/* -*- 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.

 */

#define NS_LOG_APPEND_CONTEXT                                   \

  if (GetObject<Node> ()) { std::clog << "[node " << GetObject<Node> ()->GetId () << "] "; }

#include <list>

#include <ctime>

#include <map>

#include <limits>

#include <algorithm>

#include <iostream>

#include "ns3/enum.h"

#include "ns3/string.h"

#include "ns3/ptr.h"

#include "ns3/log.h"

#include "ns3/assert.h"

#include "ns3/uinteger.h"

#include "ns3/packet.h"

#include "ns3/boolean.h"

#include "ns3/node-list.h"

#include "ns3/double.h"

#include "ns3/pointer.h"

#include "ns3/object-vector.h"

#include "ns3/ipv4-address.h"

#include "ns3/ipv4-header.h"

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

#include "ns3/ipv4-route.h"

#include "ns3/trace-source-accessor.h"

#include "ns3/random-variable.h"

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

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

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

#include "ns3/inet-socket-address.h"

#include "ns3/udp-l4-protocol.h"

#include "ns3/udp-socket-factory.h"

#include "ns3/tcp-socket-factory.h"

#include "dsr-rreq-table.h"

#include "dsr-rcache.h"

#include "dsr-routing.h"

#include "dsr-fs-header.h"

#include "dsr-options.h"

NS_LOG_COMPONENT_DEFINE ("DsrRouting");

namespace ns3 {

namespace dsr {

NS_OBJECT_ENSURE_REGISTERED (DsrRouting);

/* see http://www.iana.org/assignments/protocol-numbers */

const uint8_t DsrRouting::PROT_NUMBER = 48;

/*

 * The extension header is the fixed size dsr header, it is response for recognizing DSR option types

 * and demux to right options to process the packet.

 *

 * The header format with neighboring layers is as follows:

 *

 +-+-+-+-+-+-+-+-+-+-+-

 |  Application Header |

 +-+-+-+-+-+-+-+-+-+-+-+

 |   Transport Header  |

 +-+-+-+-+-+-+-+-+-+-+-+

 |   Fixed DSR Header  |

 +---------------------+

 |     DSR Options     |

 +-+-+-+-+-+-+-+-+-+-+-+

 |      IP Header      |

 +-+-+-+-+-+-+-+-+-+-+-+

 */

TypeId DsrRouting::GetTypeId ()

{

  static TypeId tid = TypeId ("ns3::dsr::DsrRouting")

    .AddConstructor<DsrRouting> ()

    .AddAttribute ("RouteCache", "The route cache for saving routes from route discovery process.",

                   PointerValue (0),

                   MakePointerAccessor (&DsrRouting::SetRouteCache,

                                        &DsrRouting::GetRouteCache),

                   MakePointerChecker<RouteCache> ())

    .AddAttribute ("RreqTable", "The request table to manage route requests.",

                   PointerValue (0),

                   MakePointerAccessor (&DsrRouting::SetRequestTable,

                                        &DsrRouting::GetRequestTable),

                   MakePointerChecker<RreqTable> ())

    .AddAttribute ("MaxSendBuffLen","Maximum number of packets that can be stored in send buffer.",

                   UintegerValue (64),

                   MakeUintegerAccessor (&DsrRouting::m_maxSendBuffLen),

                   MakeUintegerChecker<uint32_t> ())

    .AddAttribute ("MaxSendBuffTime","Maximum time packets can be queued in the send buffer .",

                   TimeValue (Seconds (30)),

                   MakeTimeAccessor (&DsrRouting::m_sendBufferTimeout),

                   MakeTimeChecker ())

    .AddAttribute ("MaxMaintLen","Maximum number of packets that can be stored in maintenance buffer.",

                   UintegerValue (50),

                   MakeUintegerAccessor (&DsrRouting::m_maxMaintainLen),

                   MakeUintegerChecker<uint32_t> ())

    .AddAttribute ("MaxMaintTime","Maximum time packets can be queued in maintenance buffer.",

                   TimeValue (Seconds (30)),

                   MakeTimeAccessor (&DsrRouting::m_maxMaintainTime),

                   MakeTimeChecker ())

    .AddAttribute ("MaxCacheLen","Maximum number of route entries that can be stored in route cache.",

                   UintegerValue (64),

                   MakeUintegerAccessor (&DsrRouting::m_maxCacheLen),

                   MakeUintegerChecker<uint32_t> ())

    .AddAttribute ("RouteCacheTimeout","Maximum time the route cache can be queued in route cache.",

                   TimeValue (Seconds (300)),

                   MakeTimeAccessor (&DsrRouting::m_maxCacheTime),

                   MakeTimeChecker ())

    .AddAttribute ("MaxEntriesEachDst","Maximum number of route entries for a single destination to respond.",

                   UintegerValue (20),

                   MakeUintegerAccessor (&DsrRouting::m_maxEntriesEachDst),

                   MakeUintegerChecker<uint32_t> ())

    .AddAttribute ("SendBuffInterval","How often to check send buffer for packet with route.",

                   TimeValue (Seconds (500)),

                   MakeTimeAccessor (&DsrRouting::m_sendBuffInterval),

                   MakeTimeChecker ())

    .AddAttribute ("NodeTraversalTime","The time it takes to traverse two neighboring nodes.",

                   TimeValue (MilliSeconds (40)),

                   MakeTimeAccessor (&DsrRouting::m_nodeTraversalTime),

                   MakeTimeChecker ())

    .AddAttribute ("RreqRetries","Maximum number of retransmissions for request discovery of a route.",

                   UintegerValue (16),

                   MakeUintegerAccessor (&DsrRouting::m_rreqRetries),

                   MakeUintegerChecker<uint32_t> ())

    .AddAttribute ("MaintenanceRetries","Maximum number of retransmissions for data packets from maintenance buffer.",

                   DoubleValue (2),

                   MakeDoubleAccessor (&DsrRouting::m_maxMaintRexmt),

                   MakeDoubleChecker<uint32_t> ())

    .AddAttribute ("RequestTableSize","Maximum number of request entries in the request table.",

                   UintegerValue (64),

                   MakeUintegerAccessor (&DsrRouting::m_requestTableSize),

                   MakeUintegerChecker<uint32_t> ())

    .AddAttribute ("RequestIdSize","Maximum number of request source Ids in the request table.",

                   UintegerValue (16),

                   MakeUintegerAccessor (&DsrRouting::m_requestTableIds),

                   MakeUintegerChecker<uint32_t> ())

    .AddAttribute ("UniqueRequestIdSize","Maximum number of request Ids in the request table for a single destination.",

                   UintegerValue (256),

                   MakeUintegerAccessor (&DsrRouting::m_maxRreqId),

                   MakeUintegerChecker<uint16_t> ())

    .AddAttribute ("NonPropRequestTimeout","The timeout value for non-propagation request.",

                   TimeValue (MilliSeconds (30)),

                   MakeTimeAccessor (&DsrRouting::m_nonpropRequestTimeout),

                   MakeTimeChecker ())

    .AddAttribute ("DiscoveryHopLimit","The max discovery hop limit for route requests.",

                   DoubleValue (255),

                   MakeDoubleAccessor (&DsrRouting::m_discoveryHopLimit),

                   MakeDoubleChecker<uint32_t> ())

    .AddAttribute ("MaxSalvageCount","The max salvage count for a single data packet.",

                   UintegerValue (15),

                   MakeUintegerAccessor (&DsrRouting::m_maxSalvageCount),

                   MakeUintegerChecker<uint8_t> ())

    .AddAttribute ("BlacklistTimeout","The time for a neighbor to stay in blacklist.",

                   TimeValue (Seconds (3)),

                   MakeTimeAccessor (&DsrRouting::m_blacklistTimeout),

                   MakeTimeChecker ())

    .AddAttribute ("GratReplyHoldoff","The time for gratuitous reply entry to expire.",

                   TimeValue (Seconds (1)),

                   MakeTimeAccessor (&DsrRouting::m_gratReplyHoldoff),

                   MakeTimeChecker ())

    .AddAttribute ("BroadcastJitter","The jitter time to avoid collision for broadcast packets.",

                   UintegerValue (10),

                   MakeUintegerAccessor (&DsrRouting::m_broadcastJitter),

                   MakeUintegerChecker<uint16_t> ())

    .AddAttribute ("PassiveAckTimeout","The time a packet in maintenance buffer wait for passive acknowledgment.",

                   TimeValue (MilliSeconds (100)),

                   MakeTimeAccessor (&DsrRouting::m_passiveAckTimeout),

                   MakeTimeChecker ())

    .AddAttribute ("TryPassiveAcks","The number of passive acknowledgment to use.",

                   UintegerValue (1),

                   MakeUintegerAccessor (&DsrRouting::m_tryPassiveAcks),

                   MakeUintegerChecker<uint32_t> ())

    .AddAttribute ("RequestPeriod","The base time interval between route requests.",

                   TimeValue (MilliSeconds (500)),

                   MakeTimeAccessor (&DsrRouting::m_requestPeriod),

                   MakeTimeChecker ())

    .AddAttribute ("MaxRequestPeriod","The max time interval between route requests.",

                   TimeValue (Seconds (10)),

                   MakeTimeAccessor (&DsrRouting::m_maxRequestPeriod),

                   MakeTimeChecker ())

    .AddAttribute ("GraReplyTableSize","The gratuitous reply table size.",

                   UintegerValue (64),

                   MakeUintegerAccessor (&DsrRouting::m_graReplyTableSize),

                   MakeUintegerChecker<uint32_t> ())

    .AddAttribute ("CacheType","Use Link Cache or use Path Cache",

                   StringValue ("LinkCache"),

                   MakeStringAccessor (&DsrRouting::m_cacheType),

                   MakeStringChecker ())

    .AddAttribute ("StabilityDecrFactor","The stability decrease factor for link cache",

                   UintegerValue (2),

                   MakeUintegerAccessor (&DsrRouting::m_stabilityDecrFactor),

                   MakeUintegerChecker<uint64_t> ())

    .AddAttribute ("StabilityIncrFactor","The stability increase factor for link cache",

                   UintegerValue (4),

                   MakeUintegerAccessor (&DsrRouting::m_stabilityIncrFactor),

                   MakeUintegerChecker<uint64_t> ())

    .AddAttribute ("InitStability","The initial stability factor for link cache",

                   TimeValue (Seconds (25)),

                   MakeTimeAccessor (&DsrRouting::m_initStability),

                   MakeTimeChecker ())

    .AddAttribute ("MinLifeTime","The minimal life time for link cache",

                   TimeValue (Seconds (1)),

                   MakeTimeAccessor (&DsrRouting::m_minLifeTime),

                   MakeTimeChecker ())

    .AddAttribute ("UseExtends","The extension time for link cache",

                   TimeValue (Seconds (120)),

                   MakeTimeAccessor (&DsrRouting::m_useExtends),

                   MakeTimeChecker ())

    .AddAttribute ("EnableSubRoute","Enables saving of sub route when receiving route error messages, only available when using path route cache",

                   BooleanValue (true),

                   MakeBooleanAccessor (&DsrRouting::m_subRoute),

                   MakeBooleanChecker ())

    .AddAttribute ("RetransIncr","The increase time for retransmission timer when facing network congestion",

                   TimeValue (MilliSeconds (20)),

                   MakeTimeAccessor (&DsrRouting::m_retransIncr),

                   MakeTimeChecker ())

    .AddAttribute ("MaxNetworkQueueSize","The max number of packet to save in the network queue.",

                   UintegerValue (400),

                   MakeUintegerAccessor (&DsrRouting::m_maxNetworkSize),

                   MakeUintegerChecker<uint32_t> ())

    .AddAttribute ("MaxNetworkQueueDelay","The max time for a packet to stay in the network queue.",

                   TimeValue (Seconds (30.0)),

                   MakeTimeAccessor (&DsrRouting::m_maxNetworkDelay),

                   MakeTimeChecker ())

    .AddAttribute ("NumPriorityQueues","The max number of packet to save in the network queue.",

                   UintegerValue (2),

                   MakeUintegerAccessor (&DsrRouting::m_numPriorityQueues),

                   MakeUintegerChecker<uint32_t> ())

    .AddTraceSource ("Tx", "Send DSR packet.",

                     MakeTraceSourceAccessor (&DsrRouting::m_txPacketTrace))

    .AddTraceSource ("Drop", "Drop DSR packet",

                     MakeTraceSourceAccessor (&DsrRouting::m_dropTrace))

  ;

  return tid;

}

DsrRouting::DsrRouting ()

{

  NS_LOG_FUNCTION_NOARGS ();

  /*

   * The following Ptr statements created objects for all the options header for DSR, and each of them have

   * distinct option number assigned, when DSR Routing received a packet from higher layer, it will find

   * the following options based on the option number, and pass the packet to the appropriate option to

   * process it. After the option processing, it will pass the packet back to DSR Routing to send down layer.

   */

  Ptr<dsr::DsrOptionPad1> pad1Option = CreateObject<dsr::DsrOptionPad1> ();

  Ptr<dsr::DsrOptionPadn> padnOption = CreateObject<dsr::DsrOptionPadn> ();

  Ptr<dsr::DsrOptionRreq> rreqOption = CreateObject<dsr::DsrOptionRreq> ();

  Ptr<dsr::DsrOptionRrep> rrepOption = CreateObject<dsr::DsrOptionRrep> ();

  Ptr<dsr::DsrOptionSR>   srOption = CreateObject<dsr::DsrOptionSR> ();

  Ptr<dsr::DsrOptionRerr>   rerrOption = CreateObject<dsr::DsrOptionRerr> ();

  Ptr<dsr::DsrOptionAckReq> ackReq = CreateObject<dsr::DsrOptionAckReq> ();

  Ptr<dsr::DsrOptionAck> ack = CreateObject<dsr::DsrOptionAck> ();

  Insert (pad1Option);

  Insert (padnOption);

  Insert (rreqOption);

  Insert (rrepOption);

  Insert (srOption);

  Insert (rerrOption);

  Insert (ackReq);

  Insert (ack);

  // Check the send buffer for sending packets

  m_sendBuffTimer.SetFunction (&DsrRouting::SendBuffTimerExpire, this);

  m_sendBuffTimer.Schedule (Seconds (100));

}

DsrRouting::~DsrRouting ()

{

  NS_LOG_FUNCTION_NOARGS ();

}

void

DsrRouting::NotifyNewAggregate ()

{

  NS_LOG_FUNCTION (this << "NotifyNewAggregate");

  if (m_node == 0)

    {

      Ptr<Node> node = this->GetObject<Node> ();

      if (node != 0)

        {

          m_ipv4 = this->GetObject<Ipv4L3Protocol> ();

          if (m_ipv4 != 0)

            {

              this->SetNode (node);

              m_ipv4->Insert (this);

              this->SetDownTarget (MakeCallback (&Ipv4L3Protocol::Send, m_ipv4));

            }

          m_ip = node->GetObject<Ipv4> ();

          if (m_ip != 0)

            {

              NS_LOG_DEBUG ("Ipv4 started");

            }

        }

    }

  Object::NotifyNewAggregate ();

  Simulator::ScheduleNow (&DsrRouting::Start, this);

}

void DsrRouting::Start ()

{

  NS_LOG_FUNCTION (this << "Start DSR Routing protocol");

  Ptr<dsr::RouteCache> routeCache = CreateObject<dsr::RouteCache> ();

  // Configure the path cache parameters

  routeCache->SetCacheType (m_cacheType);

  routeCache->SetSubRoute (m_subRoute);

  routeCache->SetMaxCacheLen (m_maxCacheLen);

  routeCache->SetCacheTimeout (m_maxCacheTime);

  routeCache->SetMaxEntriesEachDst (m_maxEntriesEachDst);

  // Parameters for link cache

  routeCache->SetStabilityDecrFactor (m_stabilityDecrFactor);

  routeCache->SetStabilityIncrFactor (m_stabilityIncrFactor);

  routeCache->SetInitStability (m_initStability);

  routeCache->SetMinLifeTime (m_minLifeTime);

  routeCache->SetUseExtends (m_useExtends);

  routeCache->ScheduleTimer ();

  // The call back to handle link error and send error message to appropriate nodes

  routeCache->SetCallback (MakeCallback (&DsrRouting::SendRerrWhenBreaksLinkToNextHop, this));

  SetRouteCache (routeCache);

  if (m_mainAddress == Ipv4Address ())

    {

      Ipv4Address loopback ("127.0.0.1");

      for (uint32_t i = 0; i < m_ipv4->GetNInterfaces (); i++)

        {

          // Use primary address, if multiple

          Ipv4Address addr = m_ipv4->GetAddress (i, 0).GetLocal ();

          m_broadcast = m_ipv4->GetAddress (i, 0).GetBroadcast();

          NS_LOG_DEBUG ("The addr " << addr);

          if (addr != loopback)

            {

              m_mainAddress = addr;

              NS_LOG_DEBUG ("The node Address " << m_mainAddress);

              m_ipv4->GetNetDevice (1)->SetPromiscReceiveCallback (MakeCallback (&DsrRouting::PromiscReceive, this));

              // Allow neighbor manager use this interface for layer 2 feedback if possible

              Ptr<NetDevice> dev = m_ipv4->GetNetDevice (m_ipv4->GetInterfaceForAddress (addr));

              Ptr<WifiNetDevice> wifi = dev->GetObject<WifiNetDevice> ();

              if (wifi == 0)

                {

                  break;

                }

              Ptr<WifiMac> mac = wifi->GetMac ();

              if (mac == 0)

                {

                  break;

                }

              // trace back to link mac drop event to process tx error call back

              mac->TraceConnectWithoutContext ("TxErrHeader", routeCache->GetTxErrorCallback ());

              routeCache->AddArpCache (m_ipv4->GetInterface (i)->GetArpCache ());

              break;

            }

        }

      NS_ASSERT (m_mainAddress != Ipv4Address () && m_broadcast != Ipv4Address());

    }

  NS_LOG_DEBUG ("The number queues " << m_numPriorityQueues);

  for (uint32_t i = 0; i < m_numPriorityQueues; i++)

  {

    // Set the network queue max size and the delay

    NS_LOG_DEBUG ("The network size " << m_maxNetworkSize << " and the network delay " << m_maxNetworkDelay.GetSeconds());

    Ptr<dsr::DsrNetworkQueue> queue_i = CreateObject<dsr::DsrNetworkQueue> (m_maxNetworkSize,m_maxNetworkDelay);

    std::pair<std::map<uint32_t, Ptr<dsr::DsrNetworkQueue> >::iterator, bool> result_i = m_priorityQueue.insert (std::make_pair (i, queue_i));

    NS_ASSERT_MSG (result_i.second, "Error in creating queues");

  }

  Ptr<dsr::RreqTable> rreqTable = CreateObject<dsr::RreqTable> ();

  // Set the initial hop limit

  rreqTable->SetInitHopLimit (m_discoveryHopLimit);

  // Configure the request table parameters

  rreqTable->SetRreqTableSize (m_requestTableSize);

  rreqTable->SetRreqIdSize (m_requestTableIds);

  rreqTable->SetUniqueRreqIdSize (m_maxRreqId);

  SetRequestTable (rreqTable);

  // Set the send buffer parameters

  m_sendBuffer.SetMaxQueueLen (m_maxSendBuffLen);

  m_sendBuffer.SetSendBufferTimeout (m_sendBufferTimeout);

  // Set the error buffer parameters using just the send buffer parameters

  m_errorBuffer.SetMaxQueueLen (m_maxSendBuffLen);

  m_errorBuffer.SetErrorBufferTimeout (m_sendBufferTimeout);

  // Set the maintenance buffer parameters

  m_maintainBuffer.SetMaxQueueLen (m_maxMaintainLen);

  m_maintainBuffer.SetMaintainBufferTimeout (m_maxMaintainTime);

  // Set the gratuitous reply table size

  m_graReply.SetGraTableSize (m_graReplyTableSize);

  NS_LOG_DEBUG ("Starting DSR on node " << m_mainAddress);

}

void

DsrRouting::DoDispose (void)

{

  NS_LOG_FUNCTION_NOARGS ();

  m_node = 0;

  for (uint32_t i = 0; i < m_ipv4->GetNInterfaces (); i++)

    {

      // Disable layer 2 link state monitoring (if possible)

      Ptr<NetDevice> dev = m_ipv4->GetNetDevice (i);

      Ptr<WifiNetDevice> wifi = dev->GetObject<WifiNetDevice> ();

      if (wifi != 0)

        {

          Ptr<WifiMac> mac = wifi->GetMac ()->GetObject<AdhocWifiMac> ();

          if (mac != 0)

            {

              mac->TraceDisconnectWithoutContext ("TxErrHeader",

                                                  m_routeCache->GetTxErrorCallback ());

              m_routeCache->DelArpCache (m_ipv4->GetInterface (i)->GetArpCache ());

            }

        }

    }

}

void

DsrRouting::SetNode (Ptr<Node> node)

{

  m_node = node;

}

Ptr<Node>

DsrRouting::GetNode () const

{

  NS_LOG_FUNCTION_NOARGS ();

  return m_node;

}

void DsrRouting::SetRouteCache (Ptr<dsr::RouteCache> r)

{

  // / Set the route cache to use

  m_routeCache = r;

}

Ptr<dsr::RouteCache>

DsrRouting::GetRouteCache () const

{

  // / Get the route cache to use

  return m_routeCache;

}

void DsrRouting::SetRequestTable (Ptr<dsr::RreqTable> q)

{

  // / Set the request table to use

  m_rreqTable = q;

}

Ptr<dsr::RreqTable>

DsrRouting::GetRequestTable () const

{

  // / Get the request table to use

  return m_rreqTable;

}

bool DsrRouting::IsLinkCache ()

{

  return m_routeCache->IsLinkCache ();

}

void DsrRouting::UseExtends (RouteCacheEntry::IP_VECTOR rt)

{

  m_routeCache->UseExtends (rt);

}

bool DsrRouting::LookupRoute (Ipv4Address id, RouteCacheEntry & rt)

{

  return m_routeCache->LookupRoute (id, rt);

}

bool DsrRouting::AddRoute_Link (RouteCacheEntry::IP_VECTOR nodelist, Ipv4Address source)

{

  Ipv4Address nextHop = SearchNextHop (source, nodelist);

  m_errorBuffer.DropPacketForErrLink (source, nextHop);

  return m_routeCache->AddRoute_Link (nodelist, source);

}

bool DsrRouting::AddRoute (RouteCacheEntry & rt)

{

  std::vector<Ipv4Address> nodelist = rt.GetVector ();

  Ipv4Address nextHop = SearchNextHop (m_mainAddress, nodelist);

  m_errorBuffer.DropPacketForErrLink (m_mainAddress, nextHop);

  return m_routeCache->AddRoute (rt);

}