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

 */

#define NS_LOG_APPEND_CONTEXT                                   \

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

#include "aodv-routing-protocol.h"

#include "ns3/log.h"

#include "ns3/boolean.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>

#include <limits>

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;

//-----------------------------------------------------------------------------

/// Tag used by AODV implementation

struct DeferredRouteOutputTag : public Tag

{

  /// Positive if output device is fixed in RouteOutput

  int32_t oif;

  DeferredRouteOutputTag (int32_t o = -1) : Tag(), oif (o) {}

  static TypeId GetTypeId ()

  {

    static TypeId tid = TypeId ("ns3::aodv::DeferredRouteOutputTag").SetParent<Tag> ();

    return tid;

  }

  TypeId  GetInstanceTypeId () const 

  {

    return GetTypeId ();

  }

  uint32_t GetSerializedSize () const

  {

    return sizeof(int32_t);

  }

  void  Serialize (TagBuffer i) const

  {

    i.WriteU32 (oif);

  }

  void  Deserialize (TagBuffer i)

  {

    oif = i.ReadU32 ();

  }

  void  Print (std::ostream &os) const

  {

    os << "DeferredRouteOutputTag: output interface = " << oif;

  }

};

//-----------------------------------------------------------------------------

RoutingProtocol::RoutingProtocol () :

  RreqRetries (2),

  RreqRateLimit (10),

  ActiveRouteTimeout (Seconds (3)),

  NetDiameter (35),

  NodeTraversalTime (MilliSeconds (40)),

  HelloInterval(Seconds (1)),

  AllowedHelloLoss (2),

  NextHopWait (NodeTraversalTime + MilliSeconds (10)),

  TimeoutBuffer (2),

  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 ()

{

  NS_LOG_FUNCTION (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,

    Ptr<NetDevice> oif, Socket::SocketErrno &sockerr)

{

  NS_LOG_FUNCTION (this << header << (oif? oif->GetIfIndex () : 0));

  if (! p)

    {

      return LoopbackRoute (header, oif); // later

    }

  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.LookupValidRoute (dst, rt))

    {

      route = rt.GetRoute ();

      NS_ASSERT (route != 0);

      NS_LOG_DEBUG ("Exist route to " << route->GetDestination() << " from interface " << route->GetSource());

      if (oif != 0 && route->GetOutputDevice () != oif)

        {

          NS_LOG_DEBUG ("Output device doesn't match. Dropped.");

          sockerr = Socket::ERROR_NOROUTETOHOST;

          return Ptr<Ipv4Route> ();

        }

      UpdateRouteLifeTime (dst, ActiveRouteTimeout);

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

      return route;

    }

  // Valid route not found, in this case we return loopback. 

  // Actual route request will be deferred until packet will be fully formed, 

  // routed to loopback, received from loopback and passed to RouteInput (see below)

  uint32_t iif = (oif ? m_ipv4->GetInterfaceForDevice (oif) : -1);

  DeferredRouteOutputTag tag (iif);

  if (! p->PeekPacketTag (tag))

    {

      p->AddPacketTag (tag);

    }

  return LoopbackRoute (header, oif);

}

void

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

    UnicastForwardCallback ucb, ErrorCallback ecb)

{

  NS_LOG_FUNCTION (this << p << header);

  NS_ASSERT (p != 0 && p != Ptr<Packet> ());

  QueueEntry newEntry (p, header, ucb, ecb);

  bool result = m_queue.Enqueue (newEntry);

  if (result)

    {

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

      RoutingTableEntry rt;

      bool result = m_routingTable.LookupRoute(header.GetDestination (), rt);

      if(!result || ((rt.GetFlag() != IN_SEARCH) && result))

        {

          NS_LOG_LOGIC ("Send RREQ to" <<header.GetDestination ());

          SendRequest (header.GetDestination ());

        }

    }

}

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);

  NS_ASSERT (p != 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 ();

  // Deferred route request

  if (idev == m_lo)

    {

      DeferredRouteOutputTag tag;

      if (p->PeekPacketTag (tag))

        {

          DeferredRouteOutput (p, header, ucb, ecb);

          return true;

        }

    }

  // Duplicate of own packet

  if (IsMyOwnAddress (origin))

    return true;

  // Broadcast local delivery/forwarding

  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 () || dst.IsBroadcast ())

          {

            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 (!EnableBroadcast)

              {

                return true;

              }

            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;

          }

    }

  // Unicast local delivery

  if (m_ipv4->IsDestinationAddress (dst, iif))

    {

      UpdateRouteLifeTime (origin, ActiveRouteTimeout);

      RoutingTableEntry toOrigin;

      if (m_routingTable.LookupValidRoute (origin, toOrigin))

        {

          UpdateRouteLifeTime (toOrigin.GetNextHop (), ActiveRouteTimeout);

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

        }

      NS_LOG_LOGIC ("Unicast local delivery to " << dst);

      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)

{

  NS_LOG_FUNCTION (this);

  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)

{