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

///

#include "olsr-agent-impl.h"

#include "ns3/socket-factory.h"

#include "ns3/udp.h"

#include "ns3/internet-node.h"

#include "ns3/simulator.h"

#include "ns3/debug.h"

#include "ns3/random-variable.h"

#include "ns3/inet-socket-address.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)))

/********** Intervals **********/

/// HELLO messages emission interval.

#define OLSR_HELLO_INTERVAL	Seconds (2)

/// TC messages emission interval.

#define OLSR_TC_INTERVAL	Seconds (5)

/// MID messages emission interval.

#define OLSR_MID_INTERVAL	OLSR_TC_INTERVAL

///

/// \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) * OLSR_TC_INTERVAL)

/// Dup holding time.

#define OLSR_DUP_HOLD_TIME	Seconds (30)

/// MID holding time.

#define OLSR_MID_HOLD_TIME	(Scalar (3) * OLSR_MID_INTERVAL)

/********** 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		(OLSR_HELLO_INTERVAL.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::GetSingleValue (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 {

NS_DEBUG_COMPONENT_DEFINE ("OlsrAgent");

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

OlsrAgentImpl::OlsrAgentImpl (Ptr<Node> node)

  :

  m_useL2Notifications (false),

  m_helloTimer (Timer::CANCEL_ON_DESTROY),

  m_tcTimer (Timer::CANCEL_ON_DESTROY),

  m_midTimer (Timer::CANCEL_ON_DESTROY)

{

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

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

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

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

  SetInterfaceId (OlsrAgentImpl::iid);

  // Aggregate with the Node, so that OLSR dies when the node is destroyed.

  node->AddInterface (this);

  m_packetSequenceNumber = OLSR_MAX_SEQ_NUM;

  m_messageSequenceNumber = OLSR_MAX_SEQ_NUM;

  m_ansn = OLSR_MAX_SEQ_NUM;

  m_helloInterval = OLSR_HELLO_INTERVAL;

  m_tcInterval = OLSR_TC_INTERVAL;

  m_midInterval = OLSR_MID_INTERVAL;

  m_willingness = OLSR_WILL_ALWAYS;

  m_linkTupleTimerFirstTime = true;

  m_ipv4 = node->QueryInterface<Ipv4> (Ipv4::iid);

  NS_ASSERT (m_ipv4);

  Ptr<SocketFactory> socketFactory = node->QueryInterface<SocketFactory> (Udp::iid);

  m_receiveSocket = socketFactory->CreateSocket ();

  if (m_receiveSocket->Bind (InetSocketAddress (OLSR_PORT_NUMBER)))

    NS_ASSERT_MSG (false, "Failed to bind() OLSR receive socket");

  m_sendSocket = socketFactory->CreateSocket ();

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

}

void OlsrAgentImpl::DoDispose ()

{

  m_ipv4 = 0;

  m_receiveSocket->Dispose ();

  m_receiveSocket = 0;

  m_sendSocket->Dispose ();

  m_sendSocket = 0;  

  m_routingTable->Dispose ();

  m_routingTable = 0;

  Object::DoDispose ();

}

void OlsrAgentImpl::Start ()

{

  if (m_mainAddress == Ipv4Address ())

    {

      Ipv4Address loopback ("127.0.0.1");

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

        {

          Ipv4Address addr = m_ipv4->GetAddress (i);

          if (addr != loopback)

            {

              m_mainAddress = addr;

              break;

            }

        }

      NS_ASSERT (m_mainAddress != Ipv4Address ());

    }

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

  m_routingTable = Create<RoutingTable> (m_ipv4, m_mainAddress);

  // Add OLSR as routing protocol, with slightly lower priority than

  // static routing.

  m_ipv4->AddRoutingProtocol (m_routingTable, -10);

  if (m_sendSocket->Bind (InetSocketAddress (m_mainAddress, OLSR_PORT_NUMBER)))

    NS_ASSERT_MSG (false, "Failed to bind() OLSR send socket");

  m_receiveSocket->SetRecvCallback (MakeCallback (&OlsrAgentImpl::RecvOlsr,  this));

  HelloTimerExpire ();

  TcTimerExpire ();

  MidTimerExpire ();

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

}

void OlsrAgentImpl::SetMainInterface (uint32_t interface)

{

  m_mainAddress = m_ipv4->GetAddress (interface);

}

//

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

void

OlsrAgentImpl::RecvOlsr (Ptr<Socket> socket,

                         const Packet &receivedPacket,

                         const Address &sourceAddress)

{

  NS_DEBUG ("OLSR node " << m_mainAddress << " received a OLSR packet");

  InetSocketAddress inetSourceAddr = InetSocketAddress::ConvertFrom (sourceAddress);

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

  // so we check it.

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

  Packet packet = receivedPacket;

  OlsrPacketHeader olsrPacketHeader;

  packet.RemoveHeader (olsrPacketHeader);

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

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

  while (sizeLeft)

    {

      OlsrMessageHeader messageHeader;

      if (packet.RemoveHeader (messageHeader) == 0)

        NS_ASSERT (false);

      sizeLeft -= messageHeader.GetSerializedSize ();

      NS_DEBUG ("Olsr Msg received with type "

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

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

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

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

      if (duplicated == NULL)

        {

          switch (messageHeader.GetMessageType ())

            {

            case OlsrMessageHeader::HELLO_MESSAGE:

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

              ProcessHello (messageHeader, m_mainAddress, inetSourceAddr.GetIpv4 ());

              break;

            case OlsrMessageHeader::TC_MESSAGE:

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

              ProcessTc (messageHeader, inetSourceAddr.GetIpv4 ());

              break;

            case OlsrMessageHeader::MID_MESSAGE:

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

              ProcessMid (messageHeader, inetSourceAddr.GetIpv4 ());

              break;

            default:

              NS_DEBUG ("OLSR message type " <<

                        int (messageHeader.GetMessageType ()) <<

                        " not implemented");

            }

        }

      else

        {

          NS_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 == m_mainAddress)

                {

                  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 ()  != OlsrMessageHeader::HELLO_MESSAGE)

            ForwardDefault (messageHeader, duplicated,

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

OlsrAgentImpl::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)

        {

          NeighborTuple *nb_tuple =

            m_state.FindNeighborTuple (nb2hop_tuple.neighborMainAddr);

          if (nb_tuple == NULL)

            degree++;

        }

    }

  return degree;

}

///

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

///

void

OlsrAgentImpl::MprComputation()

{

  // MPR computation should be done for each interface. See section 8.3.1

  // (RFC 3626) for details.

  m_state.ClearMprSet ();

  // N is the subset of neighbors of the node, which are

  // neighbor "of the interface I"

  NeighborSet N;

  for (NeighborSet::const_iterator it = m_state.GetNeighbors ().begin();

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

    {

      if ((*it).status == NeighborTuple::STATUS_SYM) // I think that we need this check

        N.push_back (*it);

    }

  // N2 is the set of 2-hop neighbors reachable from "the interface

  // I", excluding:

  // (i)   the nodes only reachable by members of N with willingness WILL_NEVER

  // (ii)  the node performing the computation

  // (iii) all the symmetric neighbors: the nodes for which there exists a symmetric

  //       link to this node on some interface.

  TwoHopNeighborSet N2;

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

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

    {

      TwoHopNeighborTuple const &twoHopNeigh = *it;

      bool ok = true;

      NeighborTuple *nb_tuple = m_state.FindSymNeighborTuple (twoHopNeigh.neighborMainAddr);

      if (nb_tuple == NULL)

        {

          ok = false;

        }

      else

        {

          nb_tuple = m_state.FindNeighborTuple (twoHopNeigh.neighborMainAddr, OLSR_WILL_NEVER);

          if (nb_tuple != NULL)

            {

              ok = false;

            }

          else

            {

              nb_tuple = m_state.FindSymNeighborTuple (twoHopNeigh.neighborMainAddr);

              if (nb_tuple != NULL)

                ok = false;

            }

        }

      if (ok)

        N2.push_back (twoHopNeigh);

    }

  // 1. Start with an MPR set made of all members of N with

  // N_willingness equal to WILL_ALWAYS

  for (NeighborSet::const_iterator it = N.begin (); it != N.end (); it++)

    {

      NeighborTuple const &nb_tuple = *it;

      if (nb_tuple.willingness == OLSR_WILL_ALWAYS)

        m_state.InsertMprAddress (nb_tuple.neighborMainAddr);

    }

  // 2. Calculate D(y), where y is a member of N, for all nodes in N.

  // We will do this later.

  // FIXME

  // 3. Add to the MPR set those nodes in N, which are the *only*

  // nodes to provide reachability to a node in N2. Remove the

  // nodes from N2 which are now covered by a node in the MPR set.

  MprSet foundset;

  std::set<Ipv4Address> deleted_addrs;

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

    {

      TwoHopNeighborTuple const &nb2hop_tuple1 = *it;

      MprSet::const_iterator pos = foundset.find (nb2hop_tuple1.twoHopNeighborAddr);

      if (pos != foundset.end ())

        continue;

      bool found = false;

      for (NeighborSet::const_iterator it2 = N.begin ();

           it2 != N.end (); it2++)

        {

          if ((*it2).neighborMainAddr == nb2hop_tuple1.neighborMainAddr) {

            found = true;

            break;

          }

        }

      if (!found)

        continue;

      found = false;

      for (TwoHopNeighborSet::const_iterator it2 = it + 1;

           it2 != N2.end (); it2++)

        {

          TwoHopNeighborTuple const &nb2hop_tuple2 = *it2;

          if (nb2hop_tuple1.twoHopNeighborAddr == nb2hop_tuple2.twoHopNeighborAddr)

            {

              foundset.insert (nb2hop_tuple1.twoHopNeighborAddr);

              found = true;

              break;

            }

        }

      if (!found)

        {

          m_state.InsertMprAddress (nb2hop_tuple1.neighborMainAddr);

          for (TwoHopNeighborSet::iterator it2 = it + 1; it2 != N2.end (); it2++)

            {

              TwoHopNeighborTuple const &nb2hop_tuple2 = *it2;

              if (nb2hop_tuple1.neighborMainAddr == nb2hop_tuple2.neighborMainAddr)

                {

                  deleted_addrs.insert (nb2hop_tuple2.twoHopNeighborAddr);

                  it2 = N2.erase (it2);

                  it2--;

                }

            }

          it = N2.erase (it);

          it--;

        }

      for (std::set<Ipv4Address>::iterator it2 = deleted_addrs.begin ();

           it2 != deleted_addrs.end ();

           it2++)

        {

          for (TwoHopNeighborSet::iterator it3 = N2.begin ();

               it3 != N2.end ();

               it3++)

            {

              if ((*it3).twoHopNeighborAddr == *it2)

                {

                  it3 = N2.erase (it3);

                  it3--;

                  // I have to reset the external iterator because it