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

/*

 * Copyright (c) 2008,2009 IITP RAS

 *

 * 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: Kirill Andreev <andreev@iitp.ru>

 */

#include "hwmp-protocol.h"

#include "hwmp-protocol-mac.h"

#include "hwmp-tag.h"

#include "hwmp-rtable.h"

#include "ns3/log.h"

#include "ns3/simulator.h"

#include "ns3/packet.h"

#include "ns3/mesh-point-device.h"

#include "ns3/wifi-net-device.h"

#include "ns3/mesh-point-device.h"

#include "ns3/mesh-wifi-interface-mac.h"

#include "ns3/random-variable.h"

#include "airtime-metric.h"

#include "ie-dot11s-preq.h"

#include "ie-dot11s-prep.h"

NS_LOG_COMPONENT_DEFINE ("HwmpProtocol");

namespace ns3 {

namespace dot11s {

NS_OBJECT_ENSURE_REGISTERED (HwmpProtocol);

TypeId

HwmpProtocol::GetTypeId ()

{

  static TypeId tid = TypeId ("ns3::dot11s::HwmpProtocol")

    .SetParent<MeshL2RoutingProtocol> ()

    .AddConstructor<HwmpProtocol> ()

    .AddAttribute ( "RandomStart",

                    "Random delay at first proactive PREQ",

                    TimeValue (Seconds (0.1)),

                    MakeTimeAccessor (

                        &HwmpProtocol::m_randomStart),

                    MakeTimeChecker ()

                   )

    .AddAttribute ( "maxQueueSize",

                    "Maximum number of packets we can store when resolving route",

                    UintegerValue (255),

                    MakeUintegerAccessor (

                        &HwmpProtocol::m_maxQueueSize),

                    MakeUintegerChecker<uint16_t> (1)

                  )

    .AddAttribute ( "dot11MeshHWMPmaxPREQretries",

                    "Maximum number of retries before we suppose the destination to be unreachable",

                    UintegerValue (3),

                    MakeUintegerAccessor (

                        &HwmpProtocol::m_dot11MeshHWMPmaxPREQretries),

                    MakeUintegerChecker<uint8_t> (1)

                   )

    .AddAttribute ( "dot11MeshHWMPnetDiameterTraversalTime",

                    "Time we suppose the packet to go from one edge of the network to another",

                    TimeValue (MicroSeconds (1024*100)),

                    MakeTimeAccessor (

                        &HwmpProtocol::m_dot11MeshHWMPnetDiameterTraversalTime),

                    MakeTimeChecker ()

                  )

    .AddAttribute ( "dot11MeshHWMPpreqMinInterval",

                    "Minimal interval between to successive PREQs",

                    TimeValue (MicroSeconds (1024*100)),

                    MakeTimeAccessor (

                        &HwmpProtocol::m_dot11MeshHWMPpreqMinInterval),

                    MakeTimeChecker ()

                  )

    .AddAttribute ( "dot11MeshHWMPperrMinInterval",

                    "Minimal interval between to successive PREQs",

                    TimeValue (MicroSeconds (1024*100)),

                    MakeTimeAccessor (&HwmpProtocol::m_dot11MeshHWMPperrMinInterval),

                    MakeTimeChecker ()

                  )

    .AddAttribute ( "dot11MeshHWMPactiveRootTimeout",

                    "Lifetime of poractive routing information",

                    TimeValue (MicroSeconds (1024*5000)),

                    MakeTimeAccessor (

                        &HwmpProtocol::m_dot11MeshHWMPactiveRootTimeout),

                    MakeTimeChecker ()

                  )

    .AddAttribute ( "dot11MeshHWMPactivePathTimeout",

                     "Lifetime of reactive routing information",

                      TimeValue (MicroSeconds (1024*5000)),

                      MakeTimeAccessor (

                          &HwmpProtocol::m_dot11MeshHWMPactivePathTimeout),

                      MakeTimeChecker ()

                  )

    .AddAttribute ( "dot11MeshHWMPpathToRootInterval",

                    "Interval between two successive proactive PREQs",

                    TimeValue (MicroSeconds (1024*2000)),

                    MakeTimeAccessor (

                        &HwmpProtocol::m_dot11MeshHWMPpathToRootInterval),

                    MakeTimeChecker ()

                  )

    .AddAttribute ( "dot11MeshHWMPrannInterval",

                    "Lifetime of poractive routing information",

                    TimeValue (MicroSeconds (1024*5000)),

                    MakeTimeAccessor (

                        &HwmpProtocol::m_dot11MeshHWMPrannInterval),

                    MakeTimeChecker ()

                  )

    .AddAttribute ( "maxTtl",

                    "Initial value of Time To Live field",

                    UintegerValue (32),

                    MakeUintegerAccessor (

                        &HwmpProtocol::m_maxTtl),

                    MakeUintegerChecker<uint8_t> (2)

                  )

    .AddAttribute ( "unicastPerrThreshold",

                    "Maximum number of PERR receivers, when we send a PERR as a chain of unicasts",

                    UintegerValue (32),

                    MakeUintegerAccessor (

                        &HwmpProtocol::m_unicastPerrThreshold),

                    MakeUintegerChecker<uint8_t> (1)

                    )

    .AddAttribute ( "unicastPreqThreshold",

                    "Maximum number of PREQ receivers, when we send a PREQ as a chain of unicasts",

                    UintegerValue (1),

                    MakeUintegerAccessor (

                        &HwmpProtocol::m_unicastPreqThreshold),

                    MakeUintegerChecker<uint8_t> (1)

                    )

    .AddAttribute ( "unicastDataThreshold",

                    "Maximum number ofbroadcast receivers, when we send a broadcast as a chain of unicasts",

                    UintegerValue (1),

                    MakeUintegerAccessor (

                        &HwmpProtocol::m_unicastDataThreshold),

                    MakeUintegerChecker<uint8_t> (1)

                  )

    .AddAttribute ( "doFlag",

                    "Destination only HWMP flag",

                    BooleanValue (false),

                    MakeBooleanAccessor (

                        &HwmpProtocol::m_doFlag),

                    MakeBooleanChecker ()

                  )

    .AddAttribute ( "rfFlag",

                    "Reply and forward flag",

                    BooleanValue (true),

                    MakeBooleanAccessor (

                        &HwmpProtocol::m_rfFlag),

                    MakeBooleanChecker ()

        );

  return tid;

}

HwmpProtocol::HwmpProtocol ():

  m_dataSeqno (1),

  m_hwmpSeqno (1),

  m_preqId (0),

  m_rtable (CreateObject<HwmpRtable> ()),

  m_randomStart(Seconds (0.1)),

  m_maxQueueSize (255),

  m_dot11MeshHWMPmaxPREQretries (3),

  m_dot11MeshHWMPnetDiameterTraversalTime (MicroSeconds (1024*100)),

  m_dot11MeshHWMPpreqMinInterval (MicroSeconds (1024*100)),

  m_dot11MeshHWMPperrMinInterval (MicroSeconds (1024*100)),

  m_dot11MeshHWMPactiveRootTimeout (MicroSeconds (1024*5000)),

  m_dot11MeshHWMPactivePathTimeout (MicroSeconds (1024*5000)),

  m_dot11MeshHWMPpathToRootInterval (MicroSeconds (1024*2000)),

  m_dot11MeshHWMPrannInterval (MicroSeconds (1024*5000)),

  m_isRoot (false),

  m_maxTtl (32),

  m_unicastPerrThreshold (32),

  m_unicastPreqThreshold (1),

  m_unicastDataThreshold (1),

  m_doFlag (false),

  m_rfFlag (false)

{

  if (m_isRoot)

    {

      SetRoot ();

    }

}

HwmpProtocol::~HwmpProtocol ()

{

}

void

HwmpProtocol::DoDispose ()

{

  for (std::map<Mac48Address, EventId>::iterator i = m_preqTimeouts.begin (); i != m_preqTimeouts.end (); i ++)

    {

      i->second.Cancel ();

    }

  m_preqTimeouts.clear ();

  m_lastDataSeqno.clear ();

  m_lastHwmpSeqno.clear ();

  m_rqueue.clear ();

  m_rtable = 0;

}

bool

HwmpProtocol::RequestRoute (

  uint32_t sourceIface,

  const Mac48Address source,

  const Mac48Address destination,

  Ptr<const Packet> constPacket,

  uint16_t protocolType, //ethrnet 'Protocol' field

  MeshL2RoutingProtocol::RouteReplyCallback routeReply

)

{

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

  HwmpTag tag;

  if (sourceIface == GetMeshPoint ()->GetIfIndex())

    {

      // packet from level 3

      if (packet->PeekPacketTag (tag))

        {

          NS_FATAL_ERROR ("HWMP tag has come with a packet from upper layer. This must not occur...");

        }

      //Filling TAG:

      if (destination == Mac48Address::GetBroadcast ())

        {

          tag.SetSeqno (m_dataSeqno++);

        }

      tag.SetTtl (m_maxTtl);

    }

  else

    {

      if (!packet->RemovePacketTag (tag))

        {

          NS_FATAL_ERROR ("HWMP tag is supposed to be here at this point.");

        }

      tag.DecrementTtl ();

      if (tag.GetTtl () == 0)

        {

          m_stats.droppedTtl ++;

          return false;

        }

    }

  if (destination == Mac48Address::GetBroadcast ())

    {

      m_stats.txBroadcast ++;

      m_stats.txBytes += packet->GetSize ();

      //channel IDs where we have already sent broadcast:

      std::vector<uint16_t> channels;

      for (HwmpProtocolMacMap::const_iterator plugin = m_interfaces.begin (); plugin != m_interfaces.end (); plugin ++)

        {

          bool should_send = true;

          for (std::vector<uint16_t>::const_iterator chan = channels.begin (); chan != channels.end (); chan ++)

            {

              if ((*chan) == plugin->second->GetChannelId ())

                {

                  should_send = false;

                }

            }

          if (!should_send)

            {

              continue;

            }

          channels.push_back (plugin->second->GetChannelId ());

          std::vector<Mac48Address> receivers = GetBroadcastReceivers (plugin->first);

          for (std::vector<Mac48Address>::const_iterator i = receivers.begin (); i != receivers.end (); i ++)

            {

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

              tag.SetAddress (*i);

              packet_copy->AddPacketTag (tag);

              routeReply (true, packet_copy, source, destination, protocolType, plugin->first);

            }

        }

    }

  else

    {

      return ForwardUnicast (sourceIface, source, destination, packet, protocolType, routeReply, tag.GetTtl ());

    }

  return true;

}

bool

HwmpProtocol::RemoveRoutingStuff (uint32_t fromIface, const Mac48Address source,

      const Mac48Address destination, Ptr<Packet>  packet, uint16_t&  protocolType)

{

  HwmpTag tag;

  if (!packet->RemovePacketTag (tag))

    {

      NS_FATAL_ERROR ("HWMP tag must exist when packet received from the network");

    }

  return true;

}

bool

HwmpProtocol::ForwardUnicast (uint32_t  sourceIface, const Mac48Address source, const Mac48Address destination,

    Ptr<Packet>  packet, uint16_t  protocolType, RouteReplyCallback  routeReply, uint32_t ttl)

{

  NS_ASSERT(destination != Mac48Address::GetBroadcast ());

  HwmpRtable::LookupResult result = m_rtable->LookupReactive (destination);

  NS_LOG_DEBUG("Requested src = "<<source<<", dst = "<<destination<<", I am "<<GetAddress ()<<", RA = "<<result.retransmitter);

  if (result.retransmitter == Mac48Address::GetBroadcast ())

    {

      result = m_rtable->LookupProactive ();

    }

  HwmpTag tag;

  tag.SetAddress (result.retransmitter);

  tag.SetTtl (ttl);

  //seqno and metric is not used;

  packet->AddPacketTag (tag);

  if (result.retransmitter != Mac48Address::GetBroadcast ())

    {

      //reply immediately:

      routeReply (true, packet, source, destination, protocolType, result.ifIndex);

      m_stats.txUnicast ++;

      m_stats.txBytes += packet->GetSize ();

      return true;

    }

  if (sourceIface != GetMeshPoint ()->GetIfIndex ())

    {

      //Start path error procedure:

      NS_LOG_DEBUG ("Must Send PERR");

      result = m_rtable->LookupReactiveExpired (destination);

      //1.  Lookup expired reactive path. If exists - start path error

      //    procedure towards a next hop of this path

      //2.  If there was no reactive path, we lookup expired proactive

      //    path. If exist - start path error procedure towards path to

      //    root

      if (result.retransmitter == Mac48Address::GetBroadcast ())

        {

          result = m_rtable->LookupProactiveExpired ();

        }

      if (result.retransmitter != Mac48Address::GetBroadcast ())

        {

          std::vector<IePerr::FailedDestination> destinations = m_rtable->GetUnreachableDestinations (result.retransmitter);

          InitiatePathError (MakePathError (destinations));

        }

      m_stats.totalDropped ++;

      return false;

    }

  //Request a destination:

  result = m_rtable->LookupReactiveExpired (destination);

  if (ShouldSendPreq (destination))

    {

      uint32_t originator_seqno = GetNextHwmpSeqno ();

      uint32_t dst_seqno = 0;

      if (result.retransmitter != Mac48Address::GetBroadcast ())

        {

          dst_seqno = result.seqnum;

        }

      m_stats.initiatedPreq ++;

      for (HwmpProtocolMacMap::const_iterator i = m_interfaces.begin (); i != m_interfaces.end (); i ++)

        {

          i->second->RequestDestination (destination, originator_seqno, dst_seqno);

        }

    }

  QueuedPacket pkt;

  pkt.pkt = packet;

  pkt.dst = destination;

  pkt.src = source;

  pkt.protocol = protocolType;

  pkt.reply = routeReply;

  pkt.inInterface = sourceIface;

  if (QueuePacket (pkt))

    {

      m_stats.totalQueued ++;

      return true;

    }

  else

    {

      m_stats.totalDropped ++;

      return false;

    }

}

void

HwmpProtocol::ReceivePreq (IePreq preq, Mac48Address from, uint32_t interface, Mac48Address fromMp, uint32_t metric)

{

  preq.IncrementMetric (metric);

  //acceptance cretirea:

  std::map<Mac48Address, uint32_t>::const_iterator i = m_lastHwmpSeqno.find (preq.GetOriginatorAddress());

  if (i == m_lastHwmpSeqno.end ())

    {

      m_lastHwmpSeqno[preq.GetOriginatorAddress ()] = preq.GetOriginatorSeqNumber ();

      m_lastHwmpMetric[preq.GetOriginatorAddress ()] = preq.GetMetric ();

    }

  else

    {

      if (i->second > preq.GetOriginatorSeqNumber ())

        {

          return;

        }

      if (i->second == preq.GetOriginatorSeqNumber ())

        {

          //find metric

          std::map<Mac48Address, uint32_t>::const_iterator j = m_lastHwmpMetric.find (preq.GetOriginatorAddress());

          NS_ASSERT (j != m_lastHwmpSeqno.end ());

          if (j->second <= preq.GetMetric ())

            {

              return;

            }

        }

      m_lastHwmpSeqno[preq.GetOriginatorAddress ()] = preq.GetOriginatorSeqNumber ();

      m_lastHwmpMetric[preq.GetOriginatorAddress ()] = preq.GetMetric ();

    }

  NS_LOG_DEBUG("I am " << GetAddress () << "Accepted preq from address" << from << ", preq:" << preq);

  std::vector<Ptr<DestinationAddressUnit> > destinations = preq.GetDestinationList ();

  //Add reactive path to originator:

  if (

      ((m_rtable->LookupReactive (preq.GetOriginatorAddress ())).retransmitter == Mac48Address::GetBroadcast ()) ||

      ((m_rtable->LookupReactive (preq.GetOriginatorAddress ())).metric > preq.GetMetric ())

      )

    {

      m_rtable->AddReactivePath (

          preq.GetOriginatorAddress (),

          from,

          interface,

          preq.GetMetric (),

          MicroSeconds (preq.GetLifetime () * 1024),

          preq.GetOriginatorSeqNumber ()

          );

      ReactivePathResolved (preq.GetOriginatorAddress ());

    }

  //Add reactive path for precursor:

  if (

      ((m_rtable->LookupReactive (fromMp)).retransmitter == Mac48Address::GetBroadcast ()) ||

      ((m_rtable->LookupReactive (fromMp)).metric > preq.GetMetric ())

      )

    {

      m_rtable->AddReactivePath (

          fromMp,

          from,

          interface,

          metric,

          MicroSeconds (preq.GetLifetime () * 1024),

          preq.GetOriginatorSeqNumber ()

          );

      ReactivePathResolved (fromMp);

    }

  for (std::vector<Ptr<DestinationAddressUnit> >::const_iterator i = destinations.begin (); i != destinations.end (); i++)

    {

      if ((*i)->GetDestinationAddress () == Mac48Address::GetBroadcast())

        {

          //only proactive PREQ contains destination

          //address as broadcast! Proactive preq MUST

          //have destination count equal to 1 and

          //per destination flags DO and RF

          NS_ASSERT (preq.GetDestCount() == 1);

          NS_ASSERT (((*i)->IsDo ()) && ((*i)->IsRf ()));

          //Add proactive path only if it is the better then existed

          //before

          if (

              ((m_rtable->LookupProactive ()).retransmitter == Mac48Address::GetBroadcast ()) ||

              ((m_rtable->LookupProactive ()).metric > preq.GetMetric ())

            )

            {

              m_rtable->AddProactivePath (

                  preq.GetMetric (),

                  preq.GetOriginatorAddress (),

                  from,

                  interface,

                  MicroSeconds (preq.GetLifetime () * 1024),

                  preq.GetOriginatorSeqNumber ()

                  );

              ProactivePathResolved ();

            }

          if (!preq.IsNeedNotPrep ())

            {

              SendPrep (

                  GetAddress (),

                  preq.GetOriginatorAddress (),

                  from,

                  preq.GetMetric (),

                  preq.GetOriginatorSeqNumber (),

                  GetNextHwmpSeqno (),

                  preq.GetLifetime (),

                  interface

              );

            }

          break;

        }

      if ((*i)->GetDestinationAddress () == GetAddress ())

        {

          SendPrep (

              GetAddress (),