/* -*- 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 Borovkova <borovkovaes@iitp.ru>

 *          Pavel Boyko <boyko@iitp.ru>

 */

#include "aodv-routing-protocol.h"

#include "ns3/socket.h"

#include "ns3/simulator.h"

#include "ns3/log.h"

#include "ns3/random-variable.h"

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

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

#include "ns3/ipv4-route.h"

#include "ns3/boolean.h"

#include "ns3/uinteger.h"

#include "ns3/enum.h"

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

#include "ns3/ipv4-header.h"

#include "ns3/udp-header.h"

#include "ns3/nstime.h"

#include "ns3/net-device.h"

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

#include "src/internet-stack/udp-l4-protocol.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),

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

  TtlStart (2),

  TtlIncrement (2),

  TtlThreshold (7),

  MaxRepairTtl (0.3* NetDiameter),

  LocalAddTtl (2),

  TimeoutBuffer (2),

  BlackListTimeout(Scalar (RreqRetries) * NetTraversalTime),

  MaxQueueLen (64),

  MaxQueueTime (Seconds(30)),

  DestinationOnly (false),

  GratuitousReply (true),

  EnableExpandingRingSearch (false),

  EnableLocalRepair (true),

  m_routingTable (DeletePeriod),

  m_queue (MaxQueueLen, MaxQueueTime),

  m_requestId (0),

  m_seqNo (0),

  m_nb(HelloInterval),

  htimer (Timer::CANCEL_ON_DESTROY),

  rtimer (Timer::CANCEL_ON_DESTROY),

  lrtimer (Timer::CANCEL_ON_DESTROY)

{

  if (EnableHello)

    {

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

    }

  /* BlackListTimeout should be suitably increased if an expanding ring search is used.  In such cases, it should be

   *    {[(TtlThreshold - TtlStart)/TtlIncrement] + 1 + RreqRetries} *NetTraversalTime.

   * This is to account for possible additional route discovery attempts.

   */

  if (EnableExpandingRingSearch)

    {

      BlackListTimeout = Scalar ((((TtlThreshold - TtlStart) / TtlIncrement) + 1 + RreqRetries)) * NetTraversalTime;

    }

}

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 ("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 ("ActiveRouteTimeout", "Period of time during which the route is considered to be valid",

                     TimeValue (Seconds (3)),

                     MakeTimeAccessor (&RoutingProtocol::ActiveRouteTimeout),

                     MakeTimeChecker ())

      .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 ("TtlStart", "Initial value of TTL in RREQ  when use an expanding ring search "

                     "(should be set to at least 2 if Hello messages are used for local connectivity information.)",

                     UintegerValue (2),

                     MakeUintegerAccessor (&RoutingProtocol::TtlStart),

                     MakeUintegerChecker<uint16_t> ())

      .AddAttribute ("TtlIncrement", "Increment value of RREQ TTL when use an expanding ring search",

                     UintegerValue (2),

                     MakeUintegerAccessor (&RoutingProtocol::TtlIncrement),

                     MakeUintegerChecker<uint16_t> ())

      .AddAttribute ("TtlThreshold", "Threshold, beyond which TTL = NetDiameter is used for each attempt in RREQ.",

                     UintegerValue (7),

                     MakeUintegerAccessor (&RoutingProtocol::TtlThreshold),

                     MakeUintegerChecker<uint16_t> ())

      .AddAttribute ("LocalAddTtl", "Value used in calculation RREQ TTL when use local repair.",

                     UintegerValue (7),

                     MakeUintegerAccessor (&RoutingProtocol::LocalAddTtl),

                     MakeUintegerChecker<uint16_t> ())

      .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 ("EnableExpandingRingSearch", "Enable expanding ring search technique.",

                     BooleanValue (false),

                     MakeBooleanAccessor (&RoutingProtocol::SetExpandingRingSearchEnable,

                                          &RoutingProtocol::GetExpandingRingSearchEnable),

                     MakeBooleanChecker ())

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

                     MakeBooleanAccessor (&RoutingProtocol::SetHelloEnable,

                                          &RoutingProtocol::GetHelloEnable),

                     MakeBooleanChecker ())

      .AddAttribute ("EnableLocalRepair", "Enable local repair.",

                     BooleanValue (true),

                     MakeBooleanAccessor (&RoutingProtocol::SetLocalRepairEnable,

                                          &RoutingProtocol::GetLocalRepairEnable),

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

{

  // Open sockets for control traffic on each IP interface

  const Ipv4Address loopback ("127.0.0.1");

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

  {

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

    if (iface.GetLocal () == loopback)

      continue;

    // Create a socket to listen only on this interface

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

    Ptr<Socket> socket = l3->CreateRawSocket2();

    NS_ASSERT (socket != 0);

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

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

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

    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=*/Seconds (1e9)); // TODO use infty

    m_routingTable.AddRoute (rt);

  }

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

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

  if (EnableHello)

    {

      m_nb.ScheduleTimer ();

    }

}

Ptr<Ipv4Route>

RoutingProtocol::RouteOutput (Ptr<Packet> p, const Ipv4Header &header, uint32_t oif, Socket::SocketErrno &sockerr )

{

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

  sockerr = Socket::ERROR_NOTERROR;

  Ptr<Ipv4Route> route;

  Ipv4Address dst = header.GetDestination ();

  RoutingTableEntry rt;

  if (m_routingTable.LookupRoute (dst, rt))

    {

      if (rt.GetFlag () == RTF_UP)

        {

          route = rt.GetRoute ();

          NS_ASSERT (route != 0);

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

          UpdateRouteLifeTime (dst, ActiveRouteTimeout);

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

        }

      else

        {

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

          m_queue.Enqueue (newEntry);

          if (rt.GetFlag () == RTF_DOWN)

            {

              m_routingTable.SetEntryState (dst, RTF_IN_SEARCH);

              if (EnableExpandingRingSearch)

                SendRequest (dst, rt.GetHop () + TtlIncrement);

              else

                SendRequest (dst, NetDiameter);

            }

        }

    }

  else

    {

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

      m_queue.Enqueue (newEntry);

      if (EnableExpandingRingSearch)

        SendRequest (dst, TtlStart);

      else

        SendRequest (dst, NetDiameter);

    }

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

  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 (m_idCache.LookupId (origin, p->GetUid ()))

              {

                NS_LOG_LOGIC("Duplicated packet from " << origin);

                return true;

              }

            m_idCache.InsertId (origin, p->GetUid (), PathDiscoveryTime);

            UpdateRouteLifeTime (origin, ActiveRouteTimeout);

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

            lcb (p, header, iif);

            // TODO has TTL, forward

            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;

          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;

        }

    }

  // TODO: local delivery to non-AODV interfaces

  // 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 () == RTF_DOWN && EnableLocalRepair)

        {

          if (toDst.GetHop () > MaxRepairTtl)

            return false;

          LocalRouteRepair (dst, origin);

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

          m_queue.Enqueue (newEntry);

          NS_LOG_LOGIC("Local repair "<< dst);

          return true;

        }

      else if (toDst.GetFlag () == RTF_IN_REPAIR)

        {

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

          m_queue.Enqueue (newEntry);

          return true;

        }

      else if (toDst.GetFlag () == RTF_UP)

        {

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

          NS_LOG_LOGIC ("Forwarding");

          m_routingTable.Print(std::cout);

          ucb (route, p, header);

          return true;

        }

    }

  NS_LOG_LOGIC("route not found to "<< dst);

  return false;

}

void

RoutingProtocol::SetIpv4 (Ptr<Ipv4> ipv4)

{

  NS_ASSERT (ipv4 != 0);

  NS_ASSERT (m_ipv4 == 0);

  if (EnableLocalRepair)

    {

      lrtimer.SetFunction (&RoutingProtocol::LocalRepairTimerExpire, this);

    }

  if (EnableHello)

    {

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

      htimer.Schedule(MilliSeconds(UniformVariable().GetValue (0.0, 10.0)));

    }

  m_ipv4 = ipv4;

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

}

void

RoutingProtocol::NotifyInterfaceUp (uint32_t i )

{

  // TODO

}

void

RoutingProtocol::NotifyInterfaceDown (uint32_t i )

{

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

  // TODO

}

void

RoutingProtocol::NotifyAddAddress (uint32_t interface, Ipv4InterfaceAddress address )

{

}

void

RoutingProtocol::NotifyRemoveAddress (uint32_t interface, Ipv4InterfaceAddress address )

{

}

bool

RoutingProtocol::IsMyOwnAddress (Ipv4Address src )

{

  for (std::map<Ptr<Socket> , Ipv4InterfaceAddress>::const_iterator j = m_socketAddresses.begin (); j != m_socketAddresses.end (); ++j)

    {

      Ipv4InterfaceAddress iface = j->second;

      if (src == iface.GetLocal ())

        {

          return true;

        }

    }

  return false;

}

void

RoutingProtocol::SendRequest (Ipv4Address dst, uint16_t ttl)

{

  NS_LOG_FUNCTION ( this << dst);

  // Create RREQ header

  RreqHeader rreqHeader;

  rreqHeader.SetDst (dst);

  RoutingTableEntry rt;

  if (m_routingTable.LookupRoute (dst, rt))

    {

      rreqHeader.SetHopCount (rt.GetHop ());

      if (rt.GetValidSeqNo ())

        rreqHeader.SetDstSeqno (rt.GetSeqNo ());

      else

        rreqHeader.SetUnknownSeqno (true);

    }

  else

    {