/* -*-  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-mac-plugin.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 "ie-dot11s-preq.h"

#include "ie-dot11s-prep.h"

#include "ie-dot11s-perr.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),

        MakeUintegerAccessor (&HwmpProtocol::m_doFlag),

        MakeUintegerChecker<bool> ()

        )

    .AddAttribute ("rfFlag",

        "Reply and forward flag",

        BooleanValue (true),

        MakeUintegerAccessor (&HwmpProtocol::m_rfFlag),

        MakeUintegerChecker<bool> ()

        );

  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;

  //TODO: clear plugins

}

bool

HwmpProtocol::RequestRoute (

  uint32_t sourceIface,

  const Mac48Address source,

  const Mac48Address destination,

  Ptr<Packet> packet,

  uint16_t protocolType, //ethrnet 'Protocol' field

  MeshL2RoutingProtocol::RouteReplyCallback routeReply

)

{

  HwmpTag tag;

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

    // packet from level 3

  {

    if(packet->PeekPacketTag(tag))

    {

      NS_ASSERT (false);

    }

    //Filling TAG:

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

    {

      tag.SetSeqno (m_dataSeqno++);

      if (m_dataSeqno == 0xffffffff)

        m_dataSeqno = 0;

    }

    tag.SetTtl (m_maxTtl+1);

  }

  else

  {

    if(!packet->RemovePacketTag(tag))

    {

      NS_ASSERT(false);

      return false;

    }

    if (tag.GetTtl () == 0)

      return false;

    tag.DecrementTtl ();

  }

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

  {

    //channel IDs where we have already sent broadcast:

    std::vector<uint16_t> channels;

    for(HwmpPluginMap::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::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);

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

      MakePathError (destinations);

    }

    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;

    for(HwmpPluginMap::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;

  return QueuePacket (pkt);

}

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

              preq.GetOriginatorAddress (),

              from,

              (uint32_t)0,

              preq.GetOriginatorSeqNumber (),

              GetNextHwmpSeqno (),

              preq.GetLifetime (),

              interface

          );

          NS_ASSERT(m_rtable->LookupReactive (preq.GetOriginatorAddress ()).retransmitter != Mac48Address::GetBroadcast ());

          preq.DelDestinationAddressElement ((*i)->GetDestinationAddress());

          continue;

        }

      //check if can answer:

      HwmpRtable::LookupResult result = m_rtable->LookupReactive ((*i)->GetDestinationAddress());

      if ((! ((*i)->IsDo())) && (result.retransmitter != Mac48Address::GetBroadcast()))

        {

          //have a valid information and can answer

          //!NB: If there is information from peer - set lifetime as

          //we have got from PREQ, and set the rest lifetime of the

          //route if the information is correct

          uint32_t lifetime = preq.GetLifetime ();

          if(result.lifetime != Seconds (0.0))

            lifetime = result.lifetime.GetMicroSeconds () / 1024;

          SendPrep (

              (*i)->GetDestinationAddress (),

              preq.GetOriginatorAddress (),

              from,

              result.metric,

              preq.GetOriginatorSeqNumber (),

              result.seqnum +1,

              lifetime,

              interface

              );

          if ((*i)->IsRf ())

            (*i)->SetFlags (true, false, (*i)->IsUsn ()); //DO = 1, RF = 0

          else

            {

              preq.DelDestinationAddressElement ((*i)->GetDestinationAddress());

              continue;

            }

        }

    }

  //chack if must retransmit:

  if (preq.GetDestCount () == 0)

    return;

  //Forward PREQ to all interfaces:

  NS_LOG_DEBUG("I am "<<GetAddress ()<<"retransmitting PREQ:"<<preq);

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

    i->second->SendPreq (preq);

}

void

HwmpProtocol::ReceivePrep (IePrep prep, Mac48Address from, uint32_t interface, Mac48Address fromMp, uint32_t metric)

{

  prep.IncrementMetric (metric);

  //acceptance cretirea:

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

  if (i == m_lastHwmpSeqno.end ())

    {

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

    }

  else

  {

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

      return;

    else

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

  }

  //update routing info