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

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

TypeId 

{

    .SetParent<Ipv4RoutingProtocol> ()

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

                   TimeValue (Seconds (2)),

                   MakeTimeChecker ())

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

                   TimeValue (Seconds (5)),

                   MakeTimeChecker ())

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

                   TimeValue (Seconds (5)),

                   MakeTimeChecker ())

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

                   EnumValue (OLSR_WILL_DEFAULT),

                   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.",

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

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

    ;

  return tid;

}

  :

  m_helloTimer (Timer::CANCEL_ON_DESTROY),

  m_tcTimer (Timer::CANCEL_ON_DESTROY),

  m_midTimer (Timer::CANCEL_ON_DESTROY)

{}

{}

void

{

  m_packetSequenceNumber = OLSR_MAX_SEQ_NUM;

  m_messageSequenceNumber = OLSR_MAX_SEQ_NUM;

  m_ansn = OLSR_MAX_SEQ_NUM;

  m_linkTupleTimerFirstTime = true;

  m_ipv4 = node->GetObject<Ipv4> ();

  NS_ASSERT (m_ipv4);

}

{

  m_ipv4 = 0;

  for (std::map< Ptr<Socket>, Ipv4Address >::iterator iter = m_socketAddresses.begin ();

       iter != m_socketAddresses.end (); iter++)

    {

      iter->first->Close ();

    }

  m_socketAddresses.clear ();

  Ipv4RoutingProtocol::DoDispose ();

}

{

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

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

      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] = addr;

    }

  HelloTimerExpire ();

  TcTimerExpire ();

  MidTimerExpire ();

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

}

{

  m_mainAddress = m_ipv4->GetAddress (interface);

}

//

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

void

{

  Ptr<Packet> receivedPacket;

  Address sourceAddress;

  receivedPacket = socket->RecvFrom (sourceAddress);

  InetSocketAddress inetSourceAddr = InetSocketAddress::ConvertFrom (sourceAddress);

  Ipv4Address senderIfaceAddr = inetSourceAddr.GetIpv4 ();

  Ipv4Address receiverIfaceAddr = m_socketAddresses[socket];

  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

{

  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;

}

///

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

///

void

{

  NS_LOG_FUNCTION (this);

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

  // (RFC 3626) for details.

  MprSet mprSet;

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

  // neighbor "of the interface I"

  NeighborSet N;

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

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

    {

      if (neighbor->status == NeighborTuple::STATUS_SYM) // I think that we need this check

        {

          N.push_back (*neighbor);

        }

    }

  // 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 twoHopNeigh = m_state.GetTwoHopNeighbors ().begin ();

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

    {

      // excluding:

      // (ii)  the node performing the computation

      if (twoHopNeigh->twoHopNeighborAddr == m_mainAddress)

        {

          continue;

        }