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

/*

 * Copyright (c) 2004 Francisco J. Ros 

 * Copyright (c) 2007 INESC Porto

 *

 * 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

 *

 * Authors: Francisco J. Ros  <fjrm@dif.um.es>

 *          Gustavo J. A. M. Carneiro <gjc@inescporto.pt>

 */

///

/// \file	OLSR.cc

/// \brief	Implementation of OLSR agent and related classes.

///

/// This is the main file of this software because %OLSR's behaviour is

/// implemented here.

///

#define NS_LOG_APPEND_CONTEXT                                   \

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

#include "olsr-routing-protocol.h"

#include "ns3/socket-factory.h"

#include "ns3/udp-socket-factory.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"

/********** Useful macros **********/

///

/// \brief Gets the delay between a given time and the current time.

///

/// If given time is previous to the current one, then this macro returns

/// a number close to 0. This is used for scheduling events at a certain moment.

///

#define DELAY(time) (((time) < (Simulator::Now ())) ? Seconds (0.000001) : \

                     (time - Simulator::Now () + Seconds (0.000001)))

///

/// \brief Period at which a node must cite every link and every neighbor.

///

/// We only use this value in order to define OLSR_NEIGHB_HOLD_TIME.

///

#define OLSR_REFRESH_INTERVAL	Seconds (2)

/********** Holding times **********/

/// Neighbor holding time.

#define OLSR_NEIGHB_HOLD_TIME	(Scalar (3) * OLSR_REFRESH_INTERVAL)

/// Top holding time.

#define OLSR_TOP_HOLD_TIME	(Scalar (3) * m_tcInterval)

/// Dup holding time.

#define OLSR_DUP_HOLD_TIME	Seconds (30)

/// MID holding time.

#define OLSR_MID_HOLD_TIME	(Scalar (3) * m_midInterval)

/********** Link types **********/

/// Unspecified link type.

#define OLSR_UNSPEC_LINK	0

/// Asymmetric link type.

#define OLSR_ASYM_LINK		1

/// Symmetric link type.

#define OLSR_SYM_LINK		2

/// Lost link type.

#define OLSR_LOST_LINK		3

/********** Neighbor types **********/

/// Not neighbor type.

#define OLSR_NOT_NEIGH		0

/// Symmetric neighbor type.

#define OLSR_SYM_NEIGH		1

/// Asymmetric neighbor type.

#define OLSR_MPR_NEIGH		2

/********** Willingness **********/

/// Willingness for forwarding packets from other nodes: never.

#define OLSR_WILL_NEVER		0

/// Willingness for forwarding packets from other nodes: low.

#define OLSR_WILL_LOW		1

/// Willingness for forwarding packets from other nodes: medium.

#define OLSR_WILL_DEFAULT	3

/// Willingness for forwarding packets from other nodes: high.

#define OLSR_WILL_HIGH		6

/// Willingness for forwarding packets from other nodes: always.

#define OLSR_WILL_ALWAYS	7

/********** Miscellaneous constants **********/

/// Maximum allowed jitter.

#define OLSR_MAXJITTER		(m_helloInterval.GetSeconds () / 4)

/// Maximum allowed sequence number.

#define OLSR_MAX_SEQ_NUM	65535

/// Random number between [0-OLSR_MAXJITTER] used to jitter OLSR packet transmission.

#define JITTER (Seconds (UniformVariable().GetValue (0, OLSR_MAXJITTER)))

#define OLSR_PORT_NUMBER 698

/// Maximum number of messages per packet.

#define OLSR_MAX_MSGS		64

/// Maximum number of hellos per message (4 possible link types * 3 possible nb types).

#define OLSR_MAX_HELLOS		12

/// Maximum number of addresses advertised on a message.

#define OLSR_MAX_ADDRS		64

namespace ns3 {

namespace olsr {

NS_LOG_COMPONENT_DEFINE ("OlsrRoutingProtocol");

/********** OLSR class **********/

NS_OBJECT_ENSURE_REGISTERED (RoutingProtocol);

TypeId 

RoutingProtocol::GetTypeId (void)

{

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

    .SetParent<Ipv4RoutingProtocol> ()

    .AddConstructor<RoutingProtocol> ()

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

                   TimeValue (Seconds (2)),

                   MakeTimeAccessor (&RoutingProtocol::m_helloInterval),

                   MakeTimeChecker ())

    .AddAttribute ("TcInterval", "TC messages emission interval.",

                   TimeValue (Seconds (5)),

                   MakeTimeAccessor (&RoutingProtocol::m_tcInterval),

                   MakeTimeChecker ())

    .AddAttribute ("MidInterval", "MID messages emission interval.  Normally it is equal to TcInterval.",

                   TimeValue (Seconds (5)),

                   MakeTimeAccessor (&RoutingProtocol::m_midInterval),

                   MakeTimeChecker ())

    .AddAttribute ("Willingness", "Willingness of a node to carry and forward traffic for other nodes.",

                   EnumValue (OLSR_WILL_DEFAULT),

                   MakeEnumAccessor (&RoutingProtocol::m_willingness),

                   MakeEnumChecker (OLSR_WILL_NEVER, "never",

                                    OLSR_WILL_LOW, "low",

                                    OLSR_WILL_DEFAULT, "default",

                                    OLSR_WILL_HIGH, "high",

                                    OLSR_WILL_ALWAYS, "always"))

    .AddTraceSource ("Rx", "Receive OLSR packet.",

                     MakeTraceSourceAccessor (&RoutingProtocol::m_rxPacketTrace))

    .AddTraceSource ("Tx", "Send OLSR packet.",

                     MakeTraceSourceAccessor (&RoutingProtocol::m_txPacketTrace))

    .AddTraceSource ("RoutingTableChanged", "The OLSR routing table has changed.",

		     MakeTraceSourceAccessor (&RoutingProtocol::m_routingTableChanged))

    ;

  return tid;

}

RoutingProtocol::RoutingProtocol ()

  : m_ipv4 (0),

    m_helloTimer (Timer::CANCEL_ON_DESTROY),

    m_tcTimer (Timer::CANCEL_ON_DESTROY),

    m_midTimer (Timer::CANCEL_ON_DESTROY),

    m_queuedMessagesTimer (Timer::CANCEL_ON_DESTROY)

{}

RoutingProtocol::~RoutingProtocol ()

{}

void

RoutingProtocol::SetIpv4 (Ptr<Ipv4> ipv4)

{

  NS_ASSERT (ipv4 != 0);

  NS_ASSERT (m_ipv4 == 0);

  NS_LOG_DEBUG ("Created olsr::RoutingProtocol");

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

  m_tcTimer.SetFunction (&RoutingProtocol::TcTimerExpire, this);

  m_midTimer.SetFunction (&RoutingProtocol::MidTimerExpire, this);

  m_queuedMessagesTimer.SetFunction (&RoutingProtocol::SendQueuedMessages, this);

  m_packetSequenceNumber = OLSR_MAX_SEQ_NUM;

  m_messageSequenceNumber = OLSR_MAX_SEQ_NUM;

  m_ansn = OLSR_MAX_SEQ_NUM;

  m_linkTupleTimerFirstTime = true;

  m_ipv4 = ipv4;

}

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

{

  if (m_mainAddress == Ipv4Address ())

    {

      Ipv4Address loopback ("127.0.0.1");

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

        {

          // Use primary address, if multiple

          Ipv4Address addr = m_ipv4->GetAddress (i, 0).GetLocal ();

          if (addr != loopback)

            {

              m_mainAddress = addr;

              break;

            }

        }

      NS_ASSERT (m_mainAddress != Ipv4Address ());

    }

  NS_LOG_DEBUG ("Starting OLSR on node " << m_mainAddress);

  Ipv4Address loopback ("127.0.0.1");

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

    {

      Ipv4Address addr = m_ipv4->GetAddress (i, 0).GetLocal ();

      if (addr == loopback)

        continue;

      if (addr != m_mainAddress)

        {

          // Create never expiring interface association tuple entries for our

          // own network interfaces, so that GetMainAddress () works to

          // translate the node's own interface addresses into the main address.

          IfaceAssocTuple tuple;

          tuple.ifaceAddr = addr;

          tuple.mainAddr = m_mainAddress;

          AddIfaceAssocTuple (tuple);

          NS_ASSERT (GetMainAddress (addr) == m_mainAddress);

        }

      // Create a socket to listen only on this interface

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

        UdpSocketFactory::GetTypeId()); 

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

      if (socket->Bind (InetSocketAddress (addr, OLSR_PORT_NUMBER)))

        {

          NS_FATAL_ERROR ("Failed to bind() OLSR receive socket");

        }

      socket->Connect (InetSocketAddress (Ipv4Address (0xffffffff), OLSR_PORT_NUMBER));

      m_socketAddresses[socket] = m_ipv4->GetAddress (i, 0);

    }

  HelloTimerExpire ();

  TcTimerExpire ();

  MidTimerExpire ();

  NS_LOG_DEBUG ("OLSR on node " << m_mainAddress << " started");

}

void RoutingProtocol::SetMainInterface (uint32_t interface)

{

  m_mainAddress = m_ipv4->GetAddress (interface, 0).GetLocal ();

}

//

// \brief Processes an incoming %OLSR packet following RFC 3626 specification.

void

RoutingProtocol::RecvOlsr (Ptr<Socket> socket)

{

  Ptr<Packet> receivedPacket;

  Address sourceAddress;

  receivedPacket = socket->RecvFrom (sourceAddress);

  InetSocketAddress inetSourceAddr = InetSocketAddress::ConvertFrom (sourceAddress);

  Ipv4Address senderIfaceAddr = inetSourceAddr.GetIpv4 ();

  Ipv4Address receiverIfaceAddr = m_socketAddresses[socket].GetLocal ();

  NS_ASSERT (receiverIfaceAddr != Ipv4Address ());

  NS_LOG_DEBUG ("OLSR node " << m_mainAddress << " received a OLSR packet from "

                << senderIfaceAddr << " to " << receiverIfaceAddr);

  // All routing messages are sent from and to port RT_PORT,

  // so we check it.

  NS_ASSERT (inetSourceAddr.GetPort () == OLSR_PORT_NUMBER);

  Ptr<Packet> packet = receivedPacket;

  olsr::PacketHeader olsrPacketHeader;

  packet->RemoveHeader (olsrPacketHeader);

  NS_ASSERT (olsrPacketHeader.GetPacketLength () >= olsrPacketHeader.GetSerializedSize ());

  uint32_t sizeLeft = olsrPacketHeader.GetPacketLength () - olsrPacketHeader.GetSerializedSize ();

  MessageList messages;

  while (sizeLeft)

    {

      MessageHeader messageHeader;

      if (packet->RemoveHeader (messageHeader) == 0)

        NS_ASSERT (false);

      sizeLeft -= messageHeader.GetSerializedSize ();

      NS_LOG_DEBUG ("Olsr Msg received with type "

                << std::dec << int (messageHeader.GetMessageType ())

                << " TTL=" << int (messageHeader.GetTimeToLive ())

                << " origAddr=" << messageHeader.GetOriginatorAddress ());

      messages.push_back (messageHeader);

    }

  m_rxPacketTrace (olsrPacketHeader, messages);

  for (MessageList::const_iterator messageIter = messages.begin ();

       messageIter != messages.end (); messageIter++)

    {

      const MessageHeader &messageHeader = *messageIter;

      // If ttl is less than or equal to zero, or

      // the receiver is the same as the originator,

      // the message must be silently dropped

      if (messageHeader.GetTimeToLive () == 0

          || messageHeader.GetOriginatorAddress () == m_mainAddress)

        {

          packet->RemoveAtStart (messageHeader.GetSerializedSize ()

                                 - messageHeader.GetSerializedSize ());

          continue;

        }

      // If the message has been processed it must not be processed again

      bool do_forwarding = true;

      DuplicateTuple *duplicated = m_state.FindDuplicateTuple

        (messageHeader.GetOriginatorAddress (),

         messageHeader.GetMessageSequenceNumber ());

      // Get main address of the peer, which may be different from the packet source address

//       const IfaceAssocTuple *ifaceAssoc = m_state.FindIfaceAssocTuple (inetSourceAddr.GetIpv4 ());

//       Ipv4Address peerMainAddress;

//       if (ifaceAssoc != NULL)

//         {

//           peerMainAddress = ifaceAssoc->mainAddr;

//         }

//       else

//         {

//           peerMainAddress = inetSourceAddr.GetIpv4 () ;

//         }

      if (duplicated == NULL)

        {

          switch (messageHeader.GetMessageType ())

            {

            case olsr::MessageHeader::HELLO_MESSAGE:

              NS_LOG_DEBUG (Simulator::Now ().GetSeconds ()

                            << "s OLSR node " << m_mainAddress

                            << " received HELLO message of size " << messageHeader.GetSerializedSize ());

              ProcessHello (messageHeader, receiverIfaceAddr, senderIfaceAddr);

              break;

            case olsr::MessageHeader::TC_MESSAGE:

              NS_LOG_DEBUG (Simulator::Now ().GetSeconds ()

                            << "s OLSR node " << m_mainAddress

                            << " received TC message of size " << messageHeader.GetSerializedSize ());

              ProcessTc (messageHeader, senderIfaceAddr);

              break;

            case olsr::MessageHeader::MID_MESSAGE:

              NS_LOG_DEBUG (Simulator::Now ().GetSeconds ()

                            << "s OLSR node " << m_mainAddress

                            <<  " received MID message of size " << messageHeader.GetSerializedSize ());

              ProcessMid (messageHeader, senderIfaceAddr);

              break;

            default:

              NS_LOG_DEBUG ("OLSR message type " <<

                        int (messageHeader.GetMessageType ()) <<

                        " not implemented");

            }

        }

      else

        {

          NS_LOG_DEBUG ("OLSR message is duplicated, not reading it.");

          // If the message has been considered for forwarding, it should

          // not be retransmitted again

          for (std::vector<Ipv4Address>::const_iterator it = duplicated->ifaceList.begin ();

               it != duplicated->ifaceList.end(); it++)

            {

              if (*it == receiverIfaceAddr)

                {

                  do_forwarding = false;

                  break;

                }

            }

        }

      if (do_forwarding)

        {

          // HELLO messages are never forwarded.

          // TC and MID messages are forwarded using the default algorithm.

          // Remaining messages are also forwarded using the default algorithm.

          if (messageHeader.GetMessageType ()  != olsr::MessageHeader::HELLO_MESSAGE)

            {

              ForwardDefault (messageHeader, duplicated,

                              receiverIfaceAddr, inetSourceAddr.GetIpv4 ());

            }

        }

    }

  // After processing all OLSR messages, we must recompute the routing table

  RoutingTableComputation ();

}

///

/// \brief This auxiliary function (defined in RFC 3626) is used for calculating the MPR Set.

///

/// \param tuple the neighbor tuple which has the main address of the node we are going to calculate its degree to.

/// \return the degree of the node.

///

int

RoutingProtocol::Degree (NeighborTuple const &tuple)

{

  int degree = 0;

  for (TwoHopNeighborSet::const_iterator it = m_state.GetTwoHopNeighbors ().begin ();

       it != m_state.GetTwoHopNeighbors ().end (); it++)

    {

      TwoHopNeighborTuple const &nb2hop_tuple = *it;

      if (nb2hop_tuple.neighborMainAddr == tuple.neighborMainAddr)

        {

          const NeighborTuple *nb_tuple =

            m_state.FindNeighborTuple (nb2hop_tuple.neighborMainAddr);

          if (nb_tuple == NULL)

            degree++;

        }

    }

  return degree;

}

namespace {

///

/// \brief Remove all covered 2-hop neighbors from N2 set. This is a helper function used by MprComputation algorithm.

///

void 

CoverTwoHopNeighbors (Ipv4Address neighborMainAddr, TwoHopNeighborSet & N2)

{

  // first gather all 2-hop neighbors to be removed

  std::set<Ipv4Address> toRemove;

  for (TwoHopNeighborSet::iterator twoHopNeigh = N2.begin (); twoHopNeigh != N2.end (); twoHopNeigh ++)

    {

      if (twoHopNeigh->neighborMainAddr == neighborMainAddr)

        {

          toRemove.insert (twoHopNeigh->twoHopNeighborAddr);

        }

    }

  // Now remove all matching records from N2

  for (TwoHopNeighborSet::iterator twoHopNeigh = N2.begin (); twoHopNeigh != N2.end (); )

    {

      if (toRemove.find (twoHopNeigh->twoHopNeighborAddr) != toRemove.end ())

        {

          twoHopNeigh = N2.erase (twoHopNeigh);

        }

      else

        {

          twoHopNeigh ++;

        }

    }

}

} // anonymous namespace

///

/// \brief Computates MPR set of a node following RFC 3626 hints.

///