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

/*

 * Copyright (c) 2011 Yufei Cheng

 *

 * 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

 *

 * Author: Yufei Cheng   <yfcheng@ittc.ku.edu>

 *              Song Luan <lsuper@mail.ustc.edu.cn> (Implemented Link Cache using Dijsktra algorithm)

 *

 * James P.G. Sterbenz <jpgs@ittc.ku.edu>, director

 * ResiliNets Research Group  http://wiki.ittc.ku.edu/resilinets

 * Information and Telecommunication Technology Center (ITTC)

 * and Department of Electrical Engineering and Computer Science

 * The University of Kansas Lawrence, KS USA.

 *

 * Work supported in part by NSF FIND (Future Internet Design) Program

 * under grant CNS-0626918 (Postmodern Internet Architecture),

 * NSF grant CNS-1050226 (Multilayer Network Resilience Analysis and Experimentation on GENI),

 * US Department of Defense (DoD), and ITTC at The University of Kansas.

 */

#include "dsr-rcache.h"

#include <map>

#include <cmath>

#include <algorithm>

#include <iostream>

#include <list>

#include <vector>

#include <functional>

#include <iomanip>

#include "ns3/simulator.h"

#include "ns3/ipv4-route.h"

#include "ns3/socket.h"

#include "ns3/log.h"

#include "ns3/address-utils.h"

#include "ns3/packet.h"

NS_LOG_COMPONENT_DEFINE ("RouteCache");

namespace ns3 {

namespace dsr {

bool CompareRoutesBoth (const RouteCacheEntry &a, const RouteCacheEntry &b)

{

  // compare based on both with hop count considered priority

}

bool CompareRoutesHops (const RouteCacheEntry &a, const RouteCacheEntry &b)

{

  // compare based on hops

  return a.GetVector ().size () < b.GetVector ().size ();

}

bool CompareRoutesExpire (const RouteCacheEntry &a, const RouteCacheEntry &b)

{

  // compare based on expire time

}

{

  NS_LOG_DEBUG (m_low << "----" << m_high);

}

NodeStab::NodeStab (Time nodeStab)

  : m_nodeStability (nodeStab + Simulator::Now ())

{

}

NodeStab::~NodeStab ()

{

}

LinkStab::LinkStab (Time linkStab)

  : m_linkStability (linkStab + Simulator::Now ())

{

}

LinkStab::~LinkStab ()

{

}

void LinkStab::Print ( ) const

{

  NS_LOG_DEBUG ("LifeTime: " << GetLinkStability ().GetSeconds ());

}

typedef std::list<RouteCacheEntry>::value_type route_pair;

RouteCacheEntry::RouteCacheEntry (IP_VECTOR const  & ip, Ipv4Address dst, Time exp)

  : m_ackTimer (Timer::CANCEL_ON_DESTROY),

    m_dst (dst),

    m_path (ip),

    m_expire (exp + Simulator::Now ()),

    m_reqCount (0),

    m_blackListState (false),

    m_blackListTimeout (Simulator::Now ())

{

}

RouteCacheEntry::~RouteCacheEntry ()

{

}

void

RouteCacheEntry::Invalidate (Time badLinkLifetime)

{

  m_reqCount = 0;

  m_expire = badLinkLifetime + Simulator::Now ();

}

void

RouteCacheEntry::Print (std::ostream & os) const

{

  os << m_dst << "\t" << (m_expire - Simulator::Now ()).GetSeconds ()

     << "\t";

}

NS_OBJECT_ENSURE_REGISTERED (RouteCache);

TypeId RouteCache::GetTypeId ()

{

  static TypeId tid = TypeId ("ns3::dsr::RouteCache")

    .SetParent<Object> ()

    .AddConstructor<RouteCache> ()

  ;

  return tid;

}

RouteCache::RouteCache ()

  : m_vector (0),

    m_maxEntriesEachDst (3),

    m_isLinkCache (false),

    m_ntimer (Timer::CANCEL_ON_DESTROY),

    m_delay (MilliSeconds (100))

{

  /*

   * The timer to set layer 2 notification, not fully supported by ns3 yet

   */

  m_ntimer.SetDelay (m_delay);

  m_ntimer.SetFunction (&RouteCache::PurgeMac, this);

  m_txErrorCallback = MakeCallback (&RouteCache::ProcessTxError, this);

}

RouteCache::~RouteCache ()

{

  NS_LOG_FUNCTION_NOARGS ();

  // clear the route cache when done

  m_sortedRoutes.clear ();

}

void

RouteCache::RemoveLastEntry (std::list<RouteCacheEntry> & rtVector)

{

  NS_LOG_FUNCTION (this);

  // release the last entry of route list

  rtVector.pop_back ();

}

bool

RouteCache::UpdateRouteEntry (Ipv4Address dst)

{

  NS_LOG_FUNCTION (this << dst);

  std::map<Ipv4Address, std::list<RouteCacheEntry> >::const_iterator i =

    m_sortedRoutes.find (dst);

  if (i == m_sortedRoutes.end ())

    {

      NS_LOG_DEBUG ("Failed to find the route entry for the destination " << dst);

      return false;

    }

  else

    {

      std::list<RouteCacheEntry> rtVector = i->second;

      RouteCacheEntry successEntry = rtVector.front ();

      successEntry.SetExpireTime (RouteCacheTimeout);

      rtVector.pop_front ();

      rtVector.push_back (successEntry);

      rtVector.sort (CompareRoutesExpire);  // sort the route vector first

      m_sortedRoutes.erase (dst);  // erase the entry first

      /*

       * Save the new route cache along with the destination address in map

       */

      std::pair<std::map<Ipv4Address, std::list<RouteCacheEntry> >::iterator, bool> result =

        m_sortedRoutes.insert (std::make_pair (dst, rtVector));

      return result.second;

    }

  return false;

}

bool

RouteCache::LookupRoute (Ipv4Address id, RouteCacheEntry & rt)

{

  NS_LOG_FUNCTION (this << id);

    {

      return LookupRoute_Link (id, rt);

    }

  else

    {

      Purge ();  // Purge first to remove expired entries

      if (m_sortedRoutes.empty ())

        {

          NS_LOG_LOGIC ("Route to " << id << " not found; m_sortedRoutes is empty");

          return false;

        }

      std::map<Ipv4Address, std::list<RouteCacheEntry> >::const_iterator i = m_sortedRoutes.find (id);

      if (i == m_sortedRoutes.end ())

        {

          NS_LOG_LOGIC ("No Direct Route to " << id << " found");

          for (std::map<Ipv4Address, std::list<RouteCacheEntry> >::const_iterator j =

                 m_sortedRoutes.begin (); j != m_sortedRoutes.end (); ++j)

            {

              std::list<RouteCacheEntry> rtVector = j->second; // The route cache vector linked with destination address

              /*

               * Loop through the possibly multiple routes within the route vector

               */

              for (std::list<RouteCacheEntry>::const_iterator k = rtVector.begin (); k != rtVector.end (); ++k)

                {

                  // return the first route in the route vector

                  RouteCacheEntry::IP_VECTOR routeVector = k->GetVector ();

                  RouteCacheEntry::IP_VECTOR changeVector;

                  for (RouteCacheEntry::IP_VECTOR::iterator l = routeVector.begin (); l != routeVector.end (); ++l)

                    {

                      if (*l != id)

                        {

                          changeVector.push_back (*l);

                        }

                      else

                        {

                          changeVector.push_back (*l);

                          break;

                        }

                    }

                  /*

                   * When the changed vector is smaller in size and larger than 1, which means we have found a route with the destination

                   * address we are looking for

                   */

                  if ((changeVector.size () < routeVector.size ())  && (changeVector.size () > 1))

                    {

                      RouteCacheEntry changeEntry; // Create the route entry

                      changeEntry.SetVector (changeVector);

                      changeEntry.SetDestination (id);

                      // Use the expire time from original route entry

                      changeEntry.SetExpireTime (k->GetExpireTime ());

                      // We need to add new route entry here

                      std::list<RouteCacheEntry> newVector;

                      newVector.push_back (changeEntry);

                      newVector.sort (CompareRoutesExpire);  // sort the route vector first

                      m_sortedRoutes[id] = newVector;   // Only get the first sub route and add it in route cache

                      NS_LOG_INFO ("We have a sub-route to " << id << " add it in route cache");

                    }

                }

            }

        }

      NS_LOG_INFO ("Here we check the route cache again after updated the sub routes");

      std::map<Ipv4Address, std::list<RouteCacheEntry> >::const_iterator m = m_sortedRoutes.find (id);

      if (m == m_sortedRoutes.end ())

        {

          NS_LOG_DEBUG ("No updated route till last time");

          return false;

        }

      /*

       * We have a direct route to the destination address

       */

      std::list<RouteCacheEntry> rtVector = m->second;

      rt = rtVector.front ();  // use the first entry in the route vector

      return true;

    }

}

void

RouteCache::SetCacheType (std::string type)

{

  NS_LOG_FUNCTION (this << type);

  if (type == std::string ("LinkCache"))

  else if (type == std::string ("PathCache"))

  else

    {

      m_isLinkCache = false;             // use path cache as default

      NS_LOG_INFO ("Error Cache Type");

    }

}

bool

RouteCache::IsLinkCache ()

{

  NS_LOG_FUNCTION (this);

  return m_isLinkCache;

}

void

RouteCache::RebuildBestRouteTable (Ipv4Address source)

{

  NS_LOG_FUNCTION (this << source);

  /**

   * \brief The followings are initialize-single-source

   */

  // @d shortest-path estimate

  std::map<Ipv4Address, uint32_t> d;

  // @pre preceeding node

  std::map<Ipv4Address, Ipv4Address> pre;

  for (std::map<Ipv4Address, std::map<Ipv4Address, uint32_t> >::iterator i = m_netGraph.begin (); i != m_netGraph.end (); ++i)

    {

      if (i->second.find (source) != i->second.end ())

        {

          d[i->first] = i->second[source];

          pre[i->first] = source;

        }

      else

        {

          d[i->first] = MAXWEIGHT;

          pre[i->first] = Ipv4Address ("255.255.255.255");

        }

    }

  d[source] = 0;

  /**

   * \brief The followings are core of dijskra algorithm

   */

  // the node set which shortest distance has been calculated, if true calculated

  std::map<Ipv4Address, bool> s;

  double temp = MAXWEIGHT;

  Ipv4Address tempip = Ipv4Address ("255.255.255.255");

  for (uint32_t i = 0; i < m_netGraph.size (); i++)

    {

        {

            {

                {

                  d[k->first] = d[tempip] + k->second;

                  pre[k->first] = tempip;

                }

            }

        }

    }

  // clean the best route table

  m_bestRoutesTable_link.clear ();

    {

      // loop for all vertexes

      RouteCacheEntry::IP_VECTOR route;

      Ipv4Address iptemp = i->first;

      if (!i->second.IsBroadcast () && iptemp != source)

        {

          while (iptemp != source)

            {

              route.push_back (iptemp);

              iptemp = pre[iptemp];

            }

          route.push_back (source);

          /**

           * \brief Reverse the route

           */

          RouteCacheEntry::IP_VECTOR reverseroute;

            {

              reverseroute.push_back (*j);

            }

          NS_LOG_DEBUG ("Add Route: ");

          PrintVector (reverseroute);

          m_bestRoutesTable_link[i->first] = reverseroute;

        }

    }

}

bool

RouteCache::LookupRoute_Link (Ipv4Address id, RouteCacheEntry & rt)

{

  NS_LOG_FUNCTION (this << id);

  std::map<Ipv4Address, RouteCacheEntry::IP_VECTOR>::const_iterator i = m_bestRoutesTable_link.find (id);

  if (i == m_bestRoutesTable_link.end ())

    {

      return false;

    }

  else

    {

      if (i->second.size () < 2)

        {

          NS_LOG_DEBUG ("Route To " << id << " error");

          return false;

        }

      RouteCacheEntry newEntry; // Create the route entry

      newEntry.SetVector (i->second);

      newEntry.SetDestination (id);

      newEntry.SetExpireTime (RouteCacheTimeout);

      NS_LOG_INFO ("Route to " << id << " found with the route length " << i->second.size ());

      rt = newEntry;

      std::vector<Ipv4Address> path = rt.GetVector ();

      PrintVector (path);

      return true;

    }

}

void

RouteCache::PurgeLinkNode ()

{

  NS_LOG_FUNCTION (this);

    {

      std::map<Link, LinkStab>::iterator itmp = i;

      if (i->second.GetLinkStability () <= Seconds (0))

        {

          ++i;

          m_linkCache.erase (itmp);

        }

      else

        {

          ++i;

        }

    }

    {

      NS_LOG_DEBUG ("The node stability " << i->second.GetNodeStability ());

      std::map<Ipv4Address, NodeStab>::iterator itmp = i;

      if (i->second.GetNodeStability () <= Seconds (0))

        {

          ++i;

          m_nodeCache.erase (itmp);

        }

      else

        {

          ++i;

        }

    }

}

void

RouteCache::UpdateNetGraph ()

{

  NS_LOG_FUNCTION (this);

  m_netGraph.clear ();

    {

      // Here the weight is set as 1

      uint32_t weight = 1;

      m_netGraph[i->first.m_low][i->first.m_high] = weight;

      m_netGraph[i->first.m_high][i->first.m_low] = weight;

    }

}

bool

RouteCache::IncStability (Ipv4Address node)

{

  NS_LOG_FUNCTION (this << node);