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

/*

 * Copyright (c) 2009 IITP RAS

 *

 * 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

 *

 * Based on 

 *      NS-2 AODV model developed by the CMU/MONARCH group and optimized and

 *      tuned by Samir Das and Mahesh Marina, University of Cincinnati;

 * 

 *      AODV-UU implementation by Erik Nordström of Uppsala University

 *      http://core.it.uu.se/core/index.php/AODV-UU

 *

 * Authors: Elena Buchatskaia <borovkovaes@iitp.ru>

 *          Pavel Boyko <boyko@iitp.ru>

 */

#include "aodv-routing-protocol.h"

#include "ns3/log.h"

#include "ns3/random-variable.h"

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

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

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

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

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

#include <algorithm>

NS_LOG_COMPONENT_DEFINE ("AodvRoutingProtocol");

namespace ns3

{

namespace aodv

{

NS_OBJECT_ENSURE_REGISTERED (RoutingProtocol);

/// UDP Port for AODV control traffic

const uint32_t RoutingProtocol::AODV_PORT = 654;

RoutingProtocol::RoutingProtocol () :

  RreqRetries (2),

  RreqRateLimit (10),

  ActiveRouteTimeout (Seconds (3)),

  NetDiameter (35),

  NodeTraversalTime (MilliSeconds (40)),

  NetTraversalTime (Scalar (2 * NetDiameter) * NodeTraversalTime),

  PathDiscoveryTime ( Scalar (2) * NetTraversalTime),

  MyRouteTimeout (Scalar (2) * std::max (PathDiscoveryTime, ActiveRouteTimeout)),

  HelloInterval(Seconds (1)),

  AllowedHelloLoss (2),

  DeletePeriod (Scalar(5) * std::max(ActiveRouteTimeout, HelloInterval)),

  NextHopWait (NodeTraversalTime + MilliSeconds (10)),

  TimeoutBuffer (2),

  BlackListTimeout(Scalar (RreqRetries) * NetTraversalTime),

  MaxQueueLen (64),

  MaxQueueTime (Seconds(30)),

  DestinationOnly (false),

  GratuitousReply (true),

  EnableHello (true),

  m_routingTable (DeletePeriod),

  m_queue (MaxQueueLen, MaxQueueTime),

  m_requestId (0),

  m_seqNo (0),

  m_rreqIdCache (PathDiscoveryTime),

  m_dpd (PathDiscoveryTime),

  m_nb(HelloInterval),

  m_rreqCount (0),

  m_htimer (Timer::CANCEL_ON_DESTROY),

  m_rreqRateLimitTimer (Timer::CANCEL_ON_DESTROY)

{

  if (EnableHello)

    {

      m_nb.SetCallback (MakeCallback (&RoutingProtocol::SendRerrWhenBreaksLinkToNextHop, this));

    }

}

TypeId

RoutingProtocol::GetTypeId (void)

{

  static TypeId tid = TypeId ("ns3::aodv::RoutingProtocol")

      .SetParent<Ipv4RoutingProtocol> ()

      .AddConstructor<RoutingProtocol> ()

      .AddAttribute ("HelloInterval", "HELLO messages emission interval.",

                     TimeValue (Seconds (1)),

                     MakeTimeAccessor (&RoutingProtocol::HelloInterval),

                     MakeTimeChecker ())

      .AddAttribute ("RreqRetries", "Maximum number of retransmissions of RREQ to discover a route",

                     UintegerValue (2),

                     MakeUintegerAccessor (&RoutingProtocol::RreqRetries),

                     MakeUintegerChecker<uint32_t> ())

      .AddAttribute ("RreqRateLimit", "Maximum number of RREQ per second.",

                     UintegerValue (10),

                     MakeUintegerAccessor (&RoutingProtocol::RreqRateLimit),

                     MakeUintegerChecker<uint32_t> ())

      .AddAttribute ("NodeTraversalTime", "Conservative estimate of the average one hop traversal time for packets and should include "

                     "queuing delays, interrupt processing times and transfer times.",

                     TimeValue (MilliSeconds (40)),

                     MakeTimeAccessor (&RoutingProtocol::NodeTraversalTime),

                     MakeTimeChecker ())

      .AddAttribute ("NextHopWait", "Period of our waiting for the neighbour's RREP_ACK = 10 ms + NodeTraversalTime",

                     TimeValue (MilliSeconds (50)),

                     MakeTimeAccessor (&RoutingProtocol::NextHopWait),

                     MakeTimeChecker ())

      .AddAttribute ("ActiveRouteTimeout", "Period of time during which the route is considered to be valid",

                     TimeValue (Seconds (3)),

                     MakeTimeAccessor (&RoutingProtocol::ActiveRouteTimeout),

                     MakeTimeChecker ())

      .AddAttribute ("MyRouteTimeout", "Value of lifetime field in RREP generating by this node = 2 * max(ActiveRouteTimeout, PathDiscoveryTime)",

                     TimeValue (Seconds (11.2)),

                     MakeTimeAccessor (&RoutingProtocol::MyRouteTimeout),

                     MakeTimeChecker ())

      .AddAttribute ("BlackListTimeout", "Time for which the node is put into the blacklist = RreqRetries * NetTraversalTime",

                     TimeValue (Seconds (5.6)),

                     MakeTimeAccessor (&RoutingProtocol::BlackListTimeout),

                     MakeTimeChecker ())

      .AddAttribute ("DeletePeriod", "DeletePeriod is intended to provide an upper bound on the time for which an upstream node A "

                     "can have a neighbor B as an active next hop for destination D, while B has invalidated the route to D."

                     " = 5 * max (HelloInterval, ActiveRouteTimeout)",

                     TimeValue (Seconds (15)),

                     MakeTimeAccessor (&RoutingProtocol::DeletePeriod),

                     MakeTimeChecker ())

      .AddAttribute ("TimeoutBuffer", "Its purpose is to provide a buffer for the timeout so that if the RREP is delayed"

                     " due to congestion, a timeout is less likely to occur while the RREP is still en route back to the source.",

                     UintegerValue (2),

                     MakeUintegerAccessor (&RoutingProtocol::TimeoutBuffer),

                     MakeUintegerChecker<uint16_t> ())

      .AddAttribute ("NetDiameter", "Net diameter measures the maximum possible number of hops between two nodes in the network",

                     UintegerValue (35),

                     MakeUintegerAccessor (&RoutingProtocol::NetDiameter),

                     MakeUintegerChecker<uint32_t> ())

      .AddAttribute ("NetTraversalTime", "Estimate of the average net traversal time = 2 * NodeTraversalTime * NetDiameter",

                     TimeValue (Seconds (2.8)),

                     MakeTimeAccessor (&RoutingProtocol::NetTraversalTime),

                     MakeTimeChecker ())

      .AddAttribute ("PathDiscoveryTime", "Estimate of maximum time needed to find route in network = 2 * NetTraversalTime",

                     TimeValue (Seconds (5.6)),

                     MakeTimeAccessor (&RoutingProtocol::PathDiscoveryTime),

                     MakeTimeChecker ())

      .AddAttribute ("MaxQueueLen", "Maximum number of packets that we allow a routing protocol to buffer.",

                     UintegerValue (64),

                     MakeUintegerAccessor (&RoutingProtocol::MaxQueueLen),

                     MakeUintegerChecker<uint32_t> ())

      .AddAttribute ("MaxQueueTime", "Maximum time packets can be queued (in seconds)",

                     TimeValue (Seconds (30)),

                     MakeTimeAccessor (&RoutingProtocol::MaxQueueTime),

                     MakeTimeChecker ())

      .AddAttribute ("AllowedHelloLoss", "Number of hello messages which may be loss for valid link.",

                     UintegerValue (2),

                     MakeUintegerAccessor (&RoutingProtocol::AllowedHelloLoss),

                     MakeUintegerChecker<uint16_t> ())

      .AddAttribute ("GratuitousReply", "Indicates whether a gratuitous RREP should be unicast to the node originated route discovery.",

                     BooleanValue (true),

                     MakeBooleanAccessor (&RoutingProtocol::SetGratuitousReplyFlag,

                                          &RoutingProtocol::GetGratuitousReplyFlag),

                     MakeBooleanChecker ())

      .AddAttribute ("DestinationOnly", "Indicates only the destination may respond to this RREQ.",

                     BooleanValue (false),

                     MakeBooleanAccessor (&RoutingProtocol::SetDesinationOnlyFlag,

                                          &RoutingProtocol::GetDesinationOnlyFlag),

                     MakeBooleanChecker ())

      .AddAttribute ("EnableHello", "Indicates whether a hello messages enable.",

                     BooleanValue (true),

                     MakeBooleanAccessor (&RoutingProtocol::SetHelloEnable,

                                          &RoutingProtocol::GetHelloEnable),

                     MakeBooleanChecker ())

      .AddAttribute ("EnableBroadcast", "Indicates whether a broadcast data packets forwarding enable.",

                     BooleanValue (true),

                     MakeBooleanAccessor (&RoutingProtocol::SetBroadcastEnable,

                                          &RoutingProtocol::GetBroadcastEnable),

                     MakeBooleanChecker ())

  ;

  return tid;

}

RoutingProtocol::~RoutingProtocol ()

{

}

void

RoutingProtocol::DoDispose ()

{

  m_ipv4 = 0;

  for (std::map<Ptr<Socket> , Ipv4InterfaceAddress>::iterator iter =

      m_socketAddresses.begin (); iter != m_socketAddresses.end (); iter++)

    {

      iter->first->Close ();

    }

  m_socketAddresses.clear ();

  Ipv4RoutingProtocol::DoDispose ();

}

void

RoutingProtocol::Start ()

{

  m_scb = MakeCallback (&RoutingProtocol::Send, this);

  m_ecb = MakeCallback (&RoutingProtocol::Drop, this);

  if (EnableHello)

    {

      m_nb.ScheduleTimer ();

    }

  m_rreqRateLimitTimer.SetFunction (&RoutingProtocol::RreqRateLimitTimerExpire,

      this);

  m_rreqRateLimitTimer.Schedule (Seconds (1));

}

Ptr<Ipv4Route>

RoutingProtocol::RouteOutput (Ptr<Packet> p, const Ipv4Header &header,

    uint32_t oif, Socket::SocketErrno &sockerr)

{

  NS_LOG_FUNCTION (this << header.GetDestination ());

  if (m_socketAddresses.empty ())

    {

      sockerr = Socket::ERROR_NOROUTETOHOST;

      NS_LOG_LOGIC ("No aodv interfaces");

      Ptr<Ipv4Route> route;

      return route;

    }

  sockerr = Socket::ERROR_NOTERROR;

  Ptr<Ipv4Route> route;

  Ipv4Address dst = header.GetDestination ();

  RoutingTableEntry rt;

  if (m_routingTable.LookupRoute (dst, rt))

    {

      if (rt.GetFlag () == VALID)

        {

          route = rt.GetRoute ();

          NS_ASSERT (route != 0);

          NS_LOG_LOGIC("exist route to " << route->GetDestination() << " from interface " << route->GetSource());

          UpdateRouteLifeTime (dst, ActiveRouteTimeout);

          UpdateRouteLifeTime (route->GetGateway (), ActiveRouteTimeout);

        }

      else

        {

          bool result = true;

          // May be null pointer (e.g. tcp-socket give null pointer)

          if (p != Ptr<Packet> ())

            {

              QueueEntry newEntry (p, header, m_scb, m_ecb);

              result = m_queue.Enqueue (newEntry);

              if (result)

                NS_LOG_LOGIC ("Add packet " << p->GetUid() << " to queue");

            }

          if ((rt.GetFlag () == INVALID) && result)

            {

              SendRequest (dst);

            }

        }

    }

  else

    {

      bool result = true;

      if (p != Ptr<Packet> ())

        {

          QueueEntry newEntry (p, header, m_scb, m_ecb);

          // Some protocols may ask route several times for a single packet.

          result = m_queue.Enqueue (newEntry);

          if (result)

            NS_LOG_LOGIC ("Add packet " << p->GetUid() << " to queue. Protocol " << (uint16_t) header.GetProtocol ());

        }

      if (result)

        SendRequest (dst);

    }

  return route;

}

bool

RoutingProtocol::RouteInput (Ptr<const Packet> p, const Ipv4Header &header,

    Ptr<const NetDevice> idev, UnicastForwardCallback ucb,

    MulticastForwardCallback mcb, LocalDeliverCallback lcb, ErrorCallback ecb)

{

  NS_LOG_FUNCTION (this << p->GetUid() << header.GetDestination() << idev->GetAddress());

  if (m_socketAddresses.empty ())

    {

      NS_LOG_LOGIC ("No aodv interfaces");

      return false;

    }

  NS_ASSERT (m_ipv4 != 0);

  // Check if input device supports IP

  NS_ASSERT (m_ipv4->GetInterfaceForDevice (idev) >= 0);

  int32_t iif = m_ipv4->GetInterfaceForDevice (idev);

  Ipv4Address dst = header.GetDestination ();

  Ipv4Address origin = header.GetSource ();

  if (IsMyOwnAddress (origin))

    return true;

  // Local delivery to AODV interfaces

  for (std::map<Ptr<Socket> , Ipv4InterfaceAddress>::const_iterator j =

      m_socketAddresses.begin (); j != m_socketAddresses.end (); ++j)

    {

      Ipv4InterfaceAddress iface = j->second;

      if (m_ipv4->GetInterfaceForAddress (iface.GetLocal ()) == iif)

        if (dst == iface.GetBroadcast ())

          {

            if (!EnableBroadcast)

              {

                return true;

              }

            if (m_dpd.IsDuplicate (p, header))

              {

                NS_LOG_DEBUG ("Duplicated packet " << p->GetUid () << " from " << origin << ". Drop.");

                return true;

              }

            UpdateRouteLifeTime (origin, ActiveRouteTimeout);

            NS_LOG_LOGIC ("Broadcast local delivery to " << iface.GetLocal ());

            Ptr<Packet> packet = p->Copy ();

            lcb (p, header, iif);

            if (header.GetTtl () > 1)

              {

                NS_LOG_LOGIC ("Forward broadcast. TTL " << (uint16_t) header.GetTtl ());

                RoutingTableEntry toBroadcast;

                if (m_routingTable.LookupRoute (dst, toBroadcast))

                  {

                    Ptr<Ipv4Route> route = toBroadcast.GetRoute ();

                    ucb (route, packet, header);

                  }

                else

                  {

                    NS_LOG_DEBUG ("No route to forward broadcast. Drop packet " << p->GetUid ());

                  }

              }

            else

              {

                NS_LOG_DEBUG ("TTL exceeded. Drop packet " << p->GetUid ());

              }

            return true;

          }

    }

  for (std::map<Ptr<Socket> , Ipv4InterfaceAddress>::const_iterator j =

      m_socketAddresses.begin (); j != m_socketAddresses.end (); ++j)

    {

      Ipv4InterfaceAddress iface = j->second;

      if (dst == iface.GetLocal ())

        {

          UpdateRouteLifeTime (origin, ActiveRouteTimeout);

          RoutingTableEntry toOrigin;

          if (m_routingTable.LookupRoute (origin, toOrigin))

            {

              UpdateRouteLifeTime (toOrigin.GetNextHop (), ActiveRouteTimeout);

              m_nb.Update (toOrigin.GetNextHop (), ActiveRouteTimeout);

            }

          NS_LOG_LOGIC ("Unicast local delivery to " << iface.GetLocal ());

          lcb (p, header, iif);

          return true;

        }

    }

  // Forwarding

  return Forwarding (p, header, ucb, ecb);

}

bool

RoutingProtocol::Forwarding (Ptr<const Packet> p, const Ipv4Header & header,

    UnicastForwardCallback ucb, ErrorCallback ecb)

{

  Ipv4Address dst = header.GetDestination ();

  Ipv4Address origin = header.GetSource ();

  m_routingTable.Purge ();

  RoutingTableEntry toDst;

  if (m_routingTable.LookupRoute (dst, toDst))

    {

      if (toDst.GetFlag () == VALID)

        {

          Ptr<Ipv4Route> route = toDst.GetRoute ();

          NS_LOG_LOGIC (route->GetSource()<<" forwarding to " << dst << " from " << origin << " packet " << p->GetUid ());

          /*

           *  Each time a route is used to forward a data packet, its Active Route

           *  Lifetime field of the source, destination and the next hop on the

           *  path to the destination is updated to be no less than the current

           *  time plus ActiveRouteTimeout.

           */

          UpdateRouteLifeTime (origin, ActiveRouteTimeout);

          UpdateRouteLifeTime (dst, ActiveRouteTimeout);

          UpdateRouteLifeTime (route->GetGateway (), ActiveRouteTimeout);

          /*

           *  Since the route between each originator and destination pair is expected to be symmetric, the

           *  Active Route Lifetime for the previous hop, along the reverse path back to the IP source, is also updated

           *  to be no less than the current time plus ActiveRouteTimeout

           */

          RoutingTableEntry toOrigin;

          m_routingTable.LookupRoute (origin, toOrigin);

          UpdateRouteLifeTime (toOrigin.GetNextHop (), ActiveRouteTimeout);

          m_nb.Update (route->GetGateway (), ActiveRouteTimeout);

          m_nb.Update (toOrigin.GetNextHop (), ActiveRouteTimeout);

          ucb (route, p, header);

          return true;

        }

      else

        {

          if (toDst.GetValidSeqNo ())

            {

              SendRerrWhenNoRouteToForward (dst, toDst.GetSeqNo (), origin);

              NS_LOG_DEBUG ("Drop packet " << p->GetUid () << " because no route to forward it.");

              return false;

            }

        }

    }

  NS_LOG_LOGIC ("route not found to "<< dst << ". Send RERR message.");

  NS_LOG_DEBUG ("Drop packet " << p->GetUid () << " because no route to forward it.");

  SendRerrWhenNoRouteToForward (dst, 0, origin);

  return false;

}

void

RoutingProtocol::SetIpv4 (Ptr<Ipv4> ipv4)

{

  NS_ASSERT (ipv4 != 0);

  NS_ASSERT (m_ipv4 == 0);

  if (EnableHello)

    {

      m_htimer.SetFunction (&RoutingProtocol::HelloTimerExpire, this);

      m_htimer.Schedule (MilliSeconds (UniformVariable ().GetInteger (0, 100)));

    }

  m_ipv4 = ipv4;

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

}

void

RoutingProtocol::NotifyInterfaceUp (uint32_t i)

{

  NS_LOG_FUNCTION (this << m_ipv4->GetAddress (i, 0).GetLocal ());

  Ptr<Ipv4L3Protocol> l3 = m_ipv4->GetObject<Ipv4L3Protocol> ();

  if (l3->GetNAddresses (i) > 1)

    {

      NS_LOG_WARN ("AODV does not work with more then one address per each interface.");

    }

  Ipv4InterfaceAddress iface = l3->GetAddress (i, 0);

  if (iface.GetLocal () == Ipv4Address ("127.0.0.1"))

    return;

  // Create a socket to listen only on this interface

  Ptr<Socket> socket = Socket::CreateSocket (GetObject<Node> (),

      UdpSocketFactory::GetTypeId ());

  NS_ASSERT (socket != 0);

  socket->SetRecvCallback (MakeCallback (&RoutingProtocol::RecvAodv, this));

  socket->Bind (InetSocketAddress (iface.GetLocal (), AODV_PORT));

  socket->Connect (InetSocketAddress (iface.GetBroadcast (), AODV_PORT));

  socket->SetAttribute ("IpTtl", UintegerValue (1));

  m_socketAddresses.insert (std::make_pair (socket, iface));

  // Add local broadcast record to the routing table

  Ptr<NetDevice> dev = m_ipv4->GetNetDevice (m_ipv4->GetInterfaceForAddress (iface.GetLocal ()));

  RoutingTableEntry rt (/*device=*/dev, /*dst=*/iface.GetBroadcast (), /*know seqno=*/true, /*seqno=*/0, /*iface=*/iface,

                        /*hops=*/1, /*next hop=*/iface.GetBroadcast (), /*lifetime=*/Simulator::GetMaximumSimulationTime ());

  m_routingTable.AddRoute (rt);

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

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

  if (wifi == 0)

    return;

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

  if (mac == 0)

    return;

  mac->TraceConnectWithoutContext ("TxErrHeader", m_nb.GetTxErrorCallback ());

  m_nb.AddArpCache (l3->GetInterface (i)->GetArpCache ());

}

void

RoutingProtocol::NotifyInterfaceDown (uint32_t i)

{

  NS_LOG_FUNCTION (this << m_ipv4->GetAddress (i, 0).GetLocal ());

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

  Ptr<Ipv4L3Protocol> l3 = m_ipv4->GetObject<Ipv4L3Protocol> ();

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

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

  if (wifi != 0)