/* -*- 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/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/udp-socket-factory.h"

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

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

#include <algorithm>

#include "ns3/icmpv4.h"

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_nb(HelloInterval),

  m_rreqCount (0),

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

  ;

  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 iface " << route->GetSource());

          UpdateRouteLifeTime (dst, ActiveRouteTimeout);

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

//          m_nb.Update (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 (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 ());

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

            lcb (p, header, iif);

            if (header.GetTtl () > 1)

              {

                ucb (route, packet, header);

              }

            else

              {

                NS_LOG_WARN ("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;

        }

    }

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

              return false;

            }

        }

    }

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

  SendRerrWhenNoRouteToForward (dst, 0, origin);

  return false;

}

void

RoutingProtocol::SetIpv4 (Ptr<Ipv4> ipv4)

{

  NS_ASSERT (ipv4 != 0);

  NS_ASSERT (m_ipv4 == 0);

  if (EnableHello)

    {

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

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

    }

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

  Ptr<Ipv4Interface> interface = l3->GetInterface (i);

  if (interface->GetNAddresses () > 1)

    {

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

    }

  Ipv4InterfaceAddress iface = interface->GetAddress (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));

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

  // 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 ()->GetObject<AdhocWifiMac> ();

  if (mac == 0) return;

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

  m_nb.AddArpCache (interface->GetArpCache());

}

void

RoutingProtocol::NotifyInterfaceDown (uint32_t i )

{

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

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

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

  Ptr<Ipv4Interface> interface = l3->GetInterface (i);

  Ptr<NetDevice> dev = interface->GetDevice();

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

  if (wifi != 0) 

    {

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

      if (mac != 0)

        {

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

          m_nb.DelArpCache (interface->GetArpCache());

        }

    }

  // Close socket 

  Ptr<Socket> socket = FindSocketWithInterfaceAddress (m_ipv4->GetAddress (i, 0));

  NS_ASSERT (socket);

  socket->Close ();

  m_socketAddresses.erase (socket);

  if (m_socketAddresses.empty ())

    {

      NS_LOG_LOGIC ("No aodv interfaces");

      htimer.Cancel ();

      m_nb.Clear ();

      m_routingTable.Clear ();

      return;

    }

  m_routingTable.DeleteAllRoutesFromInterface (m_ipv4->GetAddress (i, 0));

}

void

RoutingProtocol::NotifyAddAddress (uint32_t i, Ipv4InterfaceAddress address )

{

  NS_LOG_FUNCTION (this << " interface " << i << " address " << address);

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

  Ptr<Ipv4Interface> interface = l3->GetInterface (i);