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

/*

 * Copyright (c) 2010 Hemanth Narra, 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: Hemanth Narra <hemanth@ittc.ku.com>

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

 */

#include "dsdv-routing-protocol.h"

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

#include "ns3/double.h"

#include "ns3/uinteger.h"

namespace dsdv {

NS_OBJECT_ENSURE_REGISTERED (RoutingProtocol);

/// UDP Port for DSDV control traffic

const uint32_t RoutingProtocol::DSDV_PORT = 269;

/// Tag used by DSDV 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::dsdv::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;

  }

};

TypeId

RoutingProtocol::GetTypeId (void)

{

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

    .SetParent<Ipv4RoutingProtocol> ()

    .AddConstructor<RoutingProtocol> ()

    .AddAttribute ("PeriodicUpdateInterval","Periodic interval between exchange of full routing tables among nodes. ",

                   TimeValue (Seconds (15)),

                   MakeTimeAccessor (&RoutingProtocol::m_periodicUpdateInterval),

                   MakeTimeChecker ())

    .AddAttribute ("SettlingTime", "Minimum time an update is to be stored in adv table before sending out"

                   "in case of change in metric (in seconds)",

                   TimeValue (Seconds (5)),

                   MakeTimeAccessor (&RoutingProtocol::m_settlingTime),

                   MakeTimeChecker ())

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

                   UintegerValue (500 /*assuming maximum nodes in simulation is 100*/),

                   MakeUintegerAccessor (&RoutingProtocol::m_maxQueueLen),

                   MakeUintegerChecker<uint32_t> ())

    .AddAttribute ("MaxQueuedPacketsPerDst", "Maximum number of packets that we allow per destination to buffer.",

                   UintegerValue (5),

                   MakeUintegerAccessor (&RoutingProtocol::m_maxQueuedPacketsPerDst),

                   MakeUintegerChecker<uint32_t> ())

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

                   TimeValue (Seconds (30)),

                   MakeTimeAccessor (&RoutingProtocol::m_maxQueueTime),

                   MakeTimeChecker ())

    .AddAttribute ("EnableBuffering","Enables buffering of data packets if no route to destination is available",

                   BooleanValue (true),

                   MakeBooleanAccessor (&RoutingProtocol::SetEnableBufferFlag,

                                        &RoutingProtocol::GetEnableBufferFlag),

                   MakeBooleanChecker ())

    .AddAttribute ("EnableWST","Enables Weighted Settling Time for the updates before advertising",

                   BooleanValue (true),

                   MakeBooleanAccessor (&RoutingProtocol::SetWSTFlag,

                                        &RoutingProtocol::GetWSTFlag),

                   MakeBooleanChecker ())

    .AddAttribute ("Holdtimes","Times the forwarding Interval to purge the route.",

                   UintegerValue (3),

                   MakeUintegerAccessor (&RoutingProtocol::Holdtimes),

                   MakeUintegerChecker<uint32_t> ())

    .AddAttribute ("WeightedFactor","WeightedFactor for the settling time if Weighted Settling Time is enabled",

                   DoubleValue (0.875),

                   MakeDoubleAccessor (&RoutingProtocol::m_weightedFactor),

                   MakeDoubleChecker<double> ())

    .AddAttribute ("EnableRouteAggregation","Enables Weighted Settling Time for the updates before advertising",

                   BooleanValue (false),

                   MakeBooleanAccessor (&RoutingProtocol::SetEnableRAFlag,

                                        &RoutingProtocol::GetEnableRAFlag),

                   MakeBooleanChecker ())

    .AddAttribute ("RouteAggregationTime","Time to aggregate updates before sending them out (in seconds)",

                   TimeValue (Seconds (1)),

                   MakeTimeAccessor (&RoutingProtocol::m_routeAggregationTime),

                   MakeTimeChecker ());

  return tid;

}

void

RoutingProtocol::SetEnableBufferFlag (bool f)

{

  EnableBuffering = f;

}

bool

RoutingProtocol::GetEnableBufferFlag () const

{

  return EnableBuffering;

}

void

RoutingProtocol::SetWSTFlag (bool f)

{

  EnableWST = f;

}

bool

RoutingProtocol::GetWSTFlag () const

{

  return EnableWST;

}

void

RoutingProtocol::SetEnableRAFlag (bool f)

{

  EnableRouteAggregation = f;

}

bool

RoutingProtocol::GetEnableRAFlag () const

{

  return EnableRouteAggregation;

}

int64_t

RoutingProtocol::AssignStreams (int64_t stream)

{

  NS_LOG_FUNCTION (this << stream);

  m_uniformRandomVariable->SetStream (stream);

  return 1;

}

RoutingProtocol::RoutingProtocol ()

  : m_routingTable (),

    m_advRoutingTable (),

    m_queue (),

    m_periodicUpdateTimer (Timer::CANCEL_ON_DESTROY)

{

  m_uniformRandomVariable = CreateObject<UniformRandomVariable> ();

}

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::PrintRoutingTable (Ptr<OutputStreamWrapper> stream) const

{

  *stream->GetStream () << "Node: " << m_ipv4->GetObject<Node> ()->GetId () << " Time: " << Simulator::Now ().GetSeconds () << "s ";

  m_routingTable.Print (stream);

}

void

RoutingProtocol::Start ()

{

  m_queue.SetMaxPacketsPerDst (m_maxQueuedPacketsPerDst);

  m_queue.SetMaxQueueLen (m_maxQueueLen);

  m_queue.SetQueueTimeout (m_maxQueueTime);

  m_routingTable.Setholddowntime (Time (Holdtimes * m_periodicUpdateInterval));

  m_advRoutingTable.Setholddowntime (Time (Holdtimes * m_periodicUpdateInterval));

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

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

  m_periodicUpdateTimer.SetFunction (&RoutingProtocol::SendPeriodicUpdate,this);

  m_periodicUpdateTimer.Schedule (MicroSeconds (m_uniformRandomVariable->GetInteger (0,1000)));

}

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

    }

  if (m_socketAddresses.empty ())

    {

      sockerr = Socket::ERROR_NOROUTETOHOST;

      NS_LOG_LOGIC ("No dsdv interfaces");

      Ptr<Ipv4Route> route;

      return route;

    }

  std::map<Ipv4Address, RoutingTableEntry> removedAddresses;

  sockerr = Socket::ERROR_NOTERROR;

  Ptr<Ipv4Route> route;

  Ipv4Address dst = header.GetDestination ();

  NS_LOG_DEBUG ("Packet Size: " << p->GetSize ()

                                << ", Packet id: " << p->GetUid () << ", Destination address in Packet: " << dst);

  RoutingTableEntry rt;

  m_routingTable.Purge (removedAddresses);

  for (std::map<Ipv4Address, RoutingTableEntry>::iterator rmItr = removedAddresses.begin ();

       rmItr != removedAddresses.end (); ++rmItr)

    {

      rmItr->second.SetEntriesChanged (true);

      rmItr->second.SetSeqNo (rmItr->second.GetSeqNo () + 1);

      m_advRoutingTable.AddRoute (rmItr->second);

    }

  if (!removedAddresses.empty ())

    {

      Simulator::Schedule (MicroSeconds (m_uniformRandomVariable->GetInteger (0,1000)),&RoutingProtocol::SendTriggeredUpdate,this);

    }

  if (m_routingTable.LookupRoute (dst,rt))

    {

      if (EnableBuffering)

        {

          LookForQueuedPackets ();

        }

      if (rt.GetHop () == 1)

        {

          route = rt.GetRoute ();

          NS_ASSERT (route != 0);

          NS_LOG_DEBUG ("A route exists from " << route->GetSource ()

                                               << " to neighboring destination "

                                               << route->GetDestination ());

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

            {

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

              sockerr = Socket::ERROR_NOROUTETOHOST;

              return Ptr<Ipv4Route> ();

            }

          return route;

        }

      else

        {

          RoutingTableEntry newrt;

          if (m_routingTable.LookupRoute (rt.GetNextHop (),newrt))

            {

              route = newrt.GetRoute ();

              NS_ASSERT (route != 0);

              NS_LOG_DEBUG ("A route exists from " << route->GetSource ()

                                                   << " to destination " << dst << " via "

                                                   << rt.GetNextHop ());

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

                {

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

                  sockerr = Socket::ERROR_NOROUTETOHOST;

                  return Ptr<Ipv4Route> ();

                }

              return route;

            }

        }

    }

  if (EnableBuffering)

    {

      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_DEBUG ("Added packet " << p->GetUid () << " to queue.");

    }

}

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 (m_mainAddress << " received packet " << p->GetUid ()

                                 << " from " << header.GetSource ()

                                 << " on interface " << idev->GetAddress ()

                                 << " to destination " << header.GetDestination ());

  if (m_socketAddresses.empty ())

    {

      NS_LOG_DEBUG ("No dsdv 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 ();

  // DSDV is not a multicast routing protocol

  if (dst.IsMulticast ())

    {

      return false;

    }

  // Deferred route request

  if (EnableBuffering == true && idev == m_lo)

    {

      DeferredRouteOutputTag tag;

      if (p->PeekPacketTag (tag))

        {

          DeferredRouteOutput (p,header,ucb,ecb);

          return true;

        }

    }

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

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

    {

      Ipv4InterfaceAddress iface = j->second;

      if (origin == iface.GetLocal ())

        {

          return true;

        }

    }

  // LOCAL DELIVARY TO DSDV 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 () || dst.IsBroadcast ())

            {

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

              if (lcb.IsNull () == false)

                {

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

                  lcb (p, header, iif);

                  // Fall through to additional processing

                }

              else

                {

                  NS_LOG_ERROR ("Unable to deliver packet locally due to null callback " << p->GetUid () << " from " << origin);

                  ecb (p, header, Socket::ERROR_NOROUTETOHOST);

                }

              if (header.GetTtl () > 1)

                {

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

                  RoutingTableEntry toBroadcast;

                  if (m_routingTable.LookupRoute (dst,toBroadcast,true))

                    {

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

                      ucb (route,packet,header);

                    }

                  else

                    {

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

                    }

                }

              return true;

            }

        }

    }

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

    {

      if (lcb.IsNull () == false)

        {

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

          lcb (p, header, iif);

        }

      else

        {

          NS_LOG_ERROR ("Unable to deliver packet locally due to null callback " << p->GetUid () << " from " << origin);

          ecb (p, header, Socket::ERROR_NOROUTETOHOST);

        }

      return true;

    }

  RoutingTableEntry toDst;

  if (m_routingTable.LookupRoute (dst,toDst))

    {

      RoutingTableEntry ne;

      if (m_routingTable.LookupRoute (toDst.GetNextHop (),ne))

        {

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

          NS_LOG_LOGIC (m_mainAddress << " is forwarding packet " << p->GetUid ()

                                      << " to " << dst

                                      << " from " << header.GetSource ()

                                      << " via nexthop neighbor " << toDst.GetNextHop ());

          ucb (route,p,header);

          return true;

        }

    }

  NS_LOG_LOGIC ("Drop packet " << p->GetUid ()

                               << " as there is no route to forward it.");

  return false;

}

Ptr<Ipv4Route>

RoutingProtocol::LoopbackRoute (const Ipv4Header & hdr, Ptr<NetDevice> oif) const

{

  NS_ASSERT (m_lo != 0);

  Ptr<Ipv4Route> rt = Create<Ipv4Route> ();

  rt->SetDestination (hdr.GetDestination ());

  // rt->SetSource (hdr.GetSource ());

  //

  // Source address selection here is tricky.  The loopback route is

  // returned when DSDV does not have a route; this causes the packet

  // to be looped back and handled (cached) in RouteInput() method

  // while a route is found. However, connection-oriented protocols

  // like TCP need to create an endpoint four-tuple (src, src port,

  // dst, dst port) and create a pseudo-header for checksumming.  So,

  // DSDV needs to guess correctly what the eventual source address

  // will be.

  //

  // For single interface, single address nodes, this is not a problem.

  // When there are possibly multiple outgoing interfaces, the policy

  // implemented here is to pick the first available DSDV interface.

  // If RouteOutput() caller specified an outgoing interface, that

  // further constrains the selection of source address

  //

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

  if (oif)

    {

      // Iterate to find an address on the oif device

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

        {

          Ipv4Address addr = j->second.GetLocal ();

          int32_t interface = m_ipv4->GetInterfaceForAddress (addr);

          if (oif == m_ipv4->GetNetDevice (static_cast<uint32_t> (interface)))

            {

              rt->SetSource (addr);

              break;

            }

        }

    }

  else

    {

      rt->SetSource (j->second.GetLocal ());

    }

  NS_ASSERT_MSG (rt->GetSource () != Ipv4Address (), "Valid DSDV source address not found");

  rt->SetGateway (Ipv4Address ("127.0.0.1"));