/* -*-  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-agent-impl.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/boolean.h"

#include "ns3/uinteger.h"

#include "ns3/enum.h"

#include "ns3/trace-source-accessor.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::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 {

namespace olsr {

NS_LOG_COMPONENT_DEFINE ("OlsrAgent");

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

NS_OBJECT_ENSURE_REGISTERED (AgentImpl);

TypeId 

AgentImpl::GetTypeId (void)

{

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

    .SetParent<Agent> ()

    .AddConstructor<AgentImpl> ()

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

                   TimeValue (Seconds (2)),

                   MakeTimeAccessor (&AgentImpl::m_helloInterval),

                   MakeTimeChecker ())

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

                   TimeValue (Seconds (5)),

                   MakeTimeAccessor (&AgentImpl::m_tcInterval),

                   MakeTimeChecker ())

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

                   TimeValue (Seconds (5)),

                   MakeTimeAccessor (&AgentImpl::m_midInterval),

                   MakeTimeChecker ())

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

                   EnumValue (OLSR_WILL_DEFAULT),

                   MakeEnumAccessor (&AgentImpl::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 (&AgentImpl::m_rxPacketTrace))

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

                     MakeTraceSourceAccessor (&AgentImpl::m_txPacketTrace))

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

		     MakeTraceSourceAccessor (&AgentImpl::m_routingTableChanged))

    ;

  return tid;

}

AgentImpl::AgentImpl ()

  :

  m_helloTimer (Timer::CANCEL_ON_DESTROY),

  m_tcTimer (Timer::CANCEL_ON_DESTROY),

  m_midTimer (Timer::CANCEL_ON_DESTROY)

{}

AgentImpl::~AgentImpl ()

{}

void

AgentImpl::SetNode (Ptr<Node> node)

{

  NS_LOG_DEBUG ("Created olsr::AgentImpl");

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

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

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

  m_queuedMessagesTimer.SetFunction (&AgentImpl::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 = node->GetObject<Ipv4> ();

  NS_ASSERT (m_ipv4);

}

void AgentImpl::DoDispose ()

{

  m_ipv4 = 0;

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

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

    {

      iter->first->Dispose ();

    }

  m_socketAddresses.clear ();

  if (m_routingTable)

    {

      m_routingTable->Dispose ();

      m_routingTable = 0;

    }

  Object::DoDispose ();

}

void AgentImpl::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_LOG_DEBUG ("Starting OLSR on node " << m_mainAddress);

  m_routingTable = CreateObject<RoutingTable> ();

  m_routingTable->SetIpv4 (m_ipv4);

  m_routingTable->SetMainAddress (m_mainAddress);

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

  // static routing.

  m_ipv4->AddRoutingProtocol (m_routingTable, 10);

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

      socket->SetRecvCallback (MakeCallback (&AgentImpl::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] = addr;

    }

  HelloTimerExpire ();

  TcTimerExpire ();

  MidTimerExpire ();

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

}

void AgentImpl::SetMainInterface (uint32_t interface)

{

  m_mainAddress = m_ipv4->GetAddress (interface);

}

//

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

void

AgentImpl::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];

  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

AgentImpl::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;

}

///

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

///

void

AgentImpl::MprComputation()

{

  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;

        }

      //  excluding:

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

      bool ok = false;

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

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

        {

          if (neigh->neighborMainAddr == twoHopNeigh->neighborMainAddr)

            {

              if (neigh->willingness == OLSR_WILL_NEVER)

                {

                  ok = false;

                  break;

                }

              else

                {

                  ok = true;

                  break;

                }

            }

        }

      if (!ok)

        {

          continue;

        }

      // excluding:

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

      //       link to this node on some interface.

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

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

        {

          if (neigh->neighborMainAddr == twoHopNeigh->twoHopNeighborAddr)

            {

              ok = false;

              break;

            }

        }

      if (ok)

        {

          N2.push_back (*twoHopNeigh);

        }

    }

  NS_LOG_DEBUG ("Size of N2: " << N2.size ());  

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

  // N_willingness equal to WILL_ALWAYS

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

    {

      if (neighbor->willingness == OLSR_WILL_ALWAYS)

        {

          mprSet.insert (neighbor->neighborMainAddr);

          // (not in RFC but I think is needed: remove the 2-hop

          // neighbors reachable by the MPR from N2)

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

               twoHopNeigh != N2.end (); )

            {

              if (twoHopNeigh->neighborMainAddr == neighbor->neighborMainAddr)

                {

                  twoHopNeigh = N2.erase (twoHopNeigh);

                }

              else

                {

                  twoHopNeigh++;

                }

            }

        }

    }

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

  // (we do this later)

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

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

  std::set<Ipv4Address> coveredTwoHopNeighbors;

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

    {

      NeighborSet::const_iterator onlyNeighbor = N.end ();

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

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

        {

          if (neighbor->neighborMainAddr == twoHopNeigh->neighborMainAddr)

            {

              if (onlyNeighbor == N.end ())

                {

                  onlyNeighbor = neighbor;

                }

              else

                {

                  onlyNeighbor = N.end ();

                  break;

                }

            }

        }

      if (onlyNeighbor != N.end ())

        {

          mprSet.insert (onlyNeighbor->neighborMainAddr);

          coveredTwoHopNeighbors.insert (twoHopNeigh->twoHopNeighborAddr);

        }

    }

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

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

       twoHopNeigh != N2.end (); )

    {

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

        {

          twoHopNeigh = N2.erase (twoHopNeigh);

        }

      else

        {

          twoHopNeigh++;

        }

    }

  // 4. While there exist nodes in N2 which are not covered by at

  // least one node in the MPR set:

  while (N2.begin () != N2.end ())

    {

      // 4.1. For each node in N, calculate the reachability, i.e., the

      // number of nodes in N2 which are not yet covered by at

      // least one node in the MPR set, and which are reachable

      // through this 1-hop neighbor

      std::map<int, std::vector<const NeighborTuple *> > reachability;

      std::set<int> rs;

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

        {

          NeighborTuple const &nb_tuple = *it;

          int r = 0;

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

            {

              TwoHopNeighborTuple const &nb2hop_tuple = *it2;

              if (nb_tuple.neighborMainAddr == nb2hop_tuple.neighborMainAddr)

                r++;

            }

          rs.insert (r);

          reachability[r].push_back (&nb_tuple);

        }

      // 4.2. Select as a MPR the node with highest N_willingness among

      // the nodes in N with non-zero reachability. In case of

      // multiple choice select the node which provides

      // reachability to the maximum number of nodes in N2. In

      // case of multiple nodes providing the same amount of

      // reachability, select the node as MPR whose D(y) is

      // greater. Remove the nodes from N2 which are now covered

      // by a node in the MPR set.

      NeighborTuple const *max = NULL;

      int max_r = 0;

      for (std::set<int>::iterator it = rs.begin (); it != rs.end (); it++)

        {

          int r = *it;

          if (r == 0)

            {

              continue;

            }

          for (std::vector<const NeighborTuple *>::iterator it2 = reachability[r].begin ();

               it2 != reachability[r].end (); it2++)

            {

              const NeighborTuple *nb_tuple = *it2;

              if (max == NULL || nb_tuple->willingness > max->willingness)

                {

                  max = nb_tuple;

                  max_r = r;

                }

              else if (nb_tuple->willingness == max->willingness)

                {

                  if (r > max_r)

                    {

                      max = nb_tuple;

                      max_r = r;

                    }

                  else if (r == max_r)

                    {

                      if (Degree (*nb_tuple) > Degree (*max))

                        {

                          max = nb_tuple;

                          max_r = r;

                        }

                    }

                }

            }

        }

      if (max != NULL)

        {

          mprSet.insert (max->neighborMainAddr);

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

               twoHopNeigh != N2.end (); )

            {

              if (twoHopNeigh->neighborMainAddr == max->neighborMainAddr)

                {

                  twoHopNeigh = N2.erase (twoHopNeigh);

                }

              else

                {

                  twoHopNeigh++;

                }

            }

        }

    }

#ifdef NS3_LOG_ENABLE

  {

    std::ostringstream os;

    os << "[";

    for (MprSet::const_iterator iter = mprSet.begin ();

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

      {

        MprSet::const_iterator next = iter;

        next++;

        os << *iter;

        if (next != mprSet.end ())

          os << ", ";

      }

    os << "]";

    NS_LOG_DEBUG ("Computed MPR set for node " << m_mainAddress << ": " << os.str ());

  }

#endif

  m_state.SetMprSet (mprSet);

}

///

/// \brief Gets the main address associated with a given interface address.

///

/// \param iface_addr the interface address.

/// \return the corresponding main address.

///

Ipv4Address

AgentImpl::GetMainAddress (Ipv4Address iface_addr) const

{

  const IfaceAssocTuple *tuple =

    m_state.FindIfaceAssocTuple (iface_addr);

  if (tuple != NULL)

    return tuple->mainAddr;

  else

    return iface_addr;

}

///

/// \brief Creates the routing table of the node following RFC 3626 hints.

///

void

AgentImpl::RoutingTableComputation ()

{

  NS_LOG_DEBUG (Simulator::Now ().GetSeconds () << " s: Node " << m_mainAddress

                << ": RoutingTableComputation begin...");

  // 1. All the entries from the routing table are removed.

  m_routingTable->Clear ();

  // 2. The new routing entries are added starting with the

  // symmetric neighbors (h=1) as the destination nodes.

  const NeighborSet &neighborSet = m_state.GetNeighbors ();

  for (NeighborSet::const_iterator it = neighborSet.begin ();

       it != neighborSet.end(); it++)

    {

      NeighborTuple const &nb_tuple = *it;

      NS_LOG_DEBUG ("Looking at neighbor tuple: " << nb_tuple);

      if (nb_tuple.status == NeighborTuple::STATUS_SYM)

        {

          bool nb_main_addr = false;

          const LinkTuple *lt = NULL;

          const LinkSet &linkSet = m_state.GetLinks ();

          for (LinkSet::const_iterator it2 = linkSet.begin();

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

            {

              LinkTuple const &link_tuple = *it2;

              NS_LOG_DEBUG ("Looking at link tuple: " << link_tuple

                            << (link_tuple.time >= Simulator::Now ()? "" : " (expired)"));

              if ((GetMainAddress (link_tuple.neighborIfaceAddr) == nb_tuple.neighborMainAddr)

                  && link_tuple.time >= Simulator::Now ())

                {

                  NS_LOG_LOGIC ("Link tuple matches neighbor " << nb_tuple.neighborMainAddr

                                << " => adding routing table entry to neighbor");

                  lt = &link_tuple;

                  m_routingTable->AddEntry (link_tuple.neighborIfaceAddr,

                                            link_tuple.neighborIfaceAddr,

                                            link_tuple.localIfaceAddr,

                                            1);

                  if (link_tuple.neighborIfaceAddr == nb_tuple.neighborMainAddr)

                    {

                      nb_main_addr = true;

                    }

                }

              else

                {

                  NS_LOG_LOGIC ("Link tuple: linkMainAddress= " << GetMainAddress (link_tuple.neighborIfaceAddr)

                                << "; neighborMainAddr =  " << nb_tuple.neighborMainAddr

                                << "; expired=" << int (link_tuple.time < Simulator::Now ())

                                << " => IGNORE");

                }

            }

          // If, in the above, no R_dest_addr is equal to the main

          // address of the neighbor, then another new routing entry

          // with MUST be added, with:

          //      R_dest_addr  = main address of the neighbor;

          //      R_next_addr  = L_neighbor_iface_addr of one of the

          //                     associated link tuple with L_time >= current time;

          //      R_dist       = 1;

          //      R_iface_addr = L_local_iface_addr of the

          //                     associated link tuple.

          if (!nb_main_addr && lt != NULL)

            {

              NS_LOG_LOGIC ("no R_dest_addr is equal to the main address of the neighbor "

                            "=> adding additional routing entry");

              m_routingTable->AddEntry(nb_tuple.neighborMainAddr,

                                       lt->neighborIfaceAddr,

                                       lt->localIfaceAddr,

                                       1);

            }

        }

    }

  //  3. for each node in N2, i.e., a 2-hop neighbor which is not a

  //  neighbor node or the node itself, and such that there exist at

  //  least one entry in the 2-hop neighbor set where

  //  N_neighbor_main_addr correspond to a neighbor node with

  //  willingness different of WILL_NEVER,

  const TwoHopNeighborSet &twoHopNeighbors = m_state.GetTwoHopNeighbors ();

  for (TwoHopNeighborSet::const_iterator it = twoHopNeighbors.begin ();

       it != twoHopNeighbors.end (); it++)

    {

      TwoHopNeighborTuple const &nb2hop_tuple = *it;

      NS_LOG_LOGIC ("Looking at two-hop neighbor tuple: " << nb2hop_tuple);

      // a 2-hop neighbor which is not a neighbor node or the node itself

      if (m_state.FindNeighborTuple (nb2hop_tuple.twoHopNeighborAddr))

        {

          NS_LOG_LOGIC ("Two-hop neighbor tuple is also neighbor; skipped.");

          continue;

        }

      if (nb2hop_tuple.twoHopNeighborAddr == m_mainAddress)

        {

          NS_LOG_LOGIC ("Two-hop neighbor is self; skipped.");

          continue;

        }

      // ...and such that there exist at least one entry in the 2-hop

      // neighbor set where N_neighbor_main_addr correspond to a

      // neighbor node with willingness different of WILL_NEVER...

      bool nb2hopOk = false;

      for (NeighborSet::const_iterator neighbor = neighborSet.begin ();

           neighbor != neighborSet.end(); neighbor++)

        {

          if (neighbor->neighborMainAddr == nb2hop_tuple.neighborMainAddr

              && neighbor->willingness != OLSR_WILL_NEVER)

            {

              nb2hopOk = true;

              break;

            }

        }

      if (!nb2hopOk)

        {

          NS_LOG_LOGIC ("Two-hop neighbor tuple skipped: 2-hop neighbor "

                        << nb2hop_tuple.twoHopNeighborAddr

                        << " is attached to neighbor " << nb2hop_tuple.neighborMainAddr

                        << ", which was not found in the Neighbor Set.");

          continue;

        }

      // one selects one 2-hop tuple and creates one entry in the routing table with:

      //                R_dest_addr  =  the main address of the 2-hop neighbor;

      //                R_next_addr  = the R_next_addr of the entry in the

      //                               routing table with:

      //                                   R_dest_addr == N_neighbor_main_addr

      //                                                  of the 2-hop tuple;

      //                R_dist       = 2;

      //                R_iface_addr = the R_iface_addr of the entry in the

      //                               routing table with:

      //                                   R_dest_addr == N_neighbor_main_addr

      //                                                  of the 2-hop tuple;

      RoutingTableEntry entry;

      bool foundEntry = m_routingTable->Lookup (nb2hop_tuple.neighborMainAddr, entry);

      if (foundEntry)

        {

          NS_LOG_LOGIC ("Adding routing entry for two-hop neighbor.");

          m_routingTable->AddEntry (nb2hop_tuple.twoHopNeighborAddr,

                                    entry.nextAddr,

                                    entry.interface,

                                    2);

        }

      else

        {

          NS_LOG_LOGIC ("NOT adding routing entry for two-hop neighbor ("

                        << nb2hop_tuple.twoHopNeighborAddr

                        << " not found in the routing table)");

        }

    }

  for (uint32_t h = 2; ; h++)

    {

      bool added = false;

      // 3.1. For each topology entry in the topology table, if its

      // T_dest_addr does not correspond to R_dest_addr of any

      // route entry in the routing table AND its T_last_addr

      // corresponds to R_dest_addr of a route entry whose R_dist

      // is equal to h, then a new route entry MUST be recorded in

      // the routing table (if it does not already exist)

      const TopologySet &topology = m_state.GetTopologySet ();

      for (TopologySet::const_iterator it = topology.begin ();

           it != topology.end (); it++)

        {

          const TopologyTuple &topology_tuple = *it;

          NS_LOG_LOGIC ("Looking at topology tuple: " << topology_tuple);

          RoutingTableEntry destAddrEntry, lastAddrEntry;

          bool have_destAddrEntry = m_routingTable->Lookup (topology_tuple.destAddr, destAddrEntry);

          bool have_lastAddrEntry = m_routingTable->Lookup (topology_tuple.lastAddr, lastAddrEntry);

          if (!have_destAddrEntry && have_lastAddrEntry && lastAddrEntry.distance == h)

            {

              NS_LOG_LOGIC ("Adding routing table entry based on the topology tuple.");

              // then a new route entry MUST be recorded in

              //                the routing table (if it does not already exist) where:

              //                     R_dest_addr  = T_dest_addr;

              //                     R_next_addr  = R_next_addr of the recorded

              //                                    route entry where:

              //                                    R_dest_addr == T_last_addr

              //                     R_dist       = h+1; and

              //                     R_iface_addr = R_iface_addr of the recorded

              //                                    route entry where:

              //                                       R_dest_addr == T_last_addr.

              m_routingTable->AddEntry (topology_tuple.destAddr,

                                        lastAddrEntry.nextAddr,

                                        lastAddrEntry.interface,

                                        h + 1);

              added = true;

            }

          else

            {

              NS_LOG_LOGIC ("NOT adding routing table entry based on the topology tuple: "

                            "have_destAddrEntry=" << have_destAddrEntry

                            << " have_lastAddrEntry=" << have_lastAddrEntry

                            << " lastAddrEntry.distance=" << (int) lastAddrEntry.distance

                            << " (h=" << h << ")");

            }

        }

      if (!added)

        break;

    }

  // 4. For each entry in the multiple interface association base

  // where there exists a routing entry such that:

  //	R_dest_addr  == I_main_addr  (of the multiple interface association entry)

  // AND there is no routing entry such that:

  //	R_dest_addr  == I_iface_addr

  const IfaceAssocSet &ifaceAssocSet = m_state.GetIfaceAssocSet ();

  for (IfaceAssocSet::const_iterator it = ifaceAssocSet.begin ();

       it != ifaceAssocSet.end (); it++)

    {

      IfaceAssocTuple const &tuple = *it;

      RoutingTableEntry entry1, entry2;

      bool have_entry1 = m_routingTable->Lookup (tuple.mainAddr, entry1);

      bool have_entry2 = m_routingTable->Lookup (tuple.ifaceAddr, entry2);

      if (have_entry1 && !have_entry2)

        {

          // then a route entry is created in the routing table with:

          //       R_dest_addr  =  I_iface_addr (of the multiple interface

          //                                     association entry)

          //       R_next_addr  =  R_next_addr  (of the recorded route entry)

          //       R_dist       =  R_dist       (of the recorded route entry)

          //       R_iface_addr =  R_iface_addr (of the recorded route entry).

          m_routingTable->AddEntry (tuple.ifaceAddr,

                                    entry1.nextAddr,

                                    entry1.interface,

                                    entry1.distance);

        }

    }

  NS_LOG_DEBUG ("Node " << m_mainAddress << ": RoutingTableComputation end.");