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

/*

 * Copyright 2007 University of Washington

 * Copyright (C) 1999, 2000 Kunihiro Ishiguro, Toshiaki Takada

 * 

 * 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:  Tom Henderson (tomhend@u.washington.edu)

 * 

 * Kunihiro Ishigura, Toshiaki Takada (GNU Zebra) are attributed authors

 * of the quagga 0.99.7/src/ospfd/ospf_spf.c code which was ported here

 */

#include <utility>

#include <vector>

#include <queue>

#include "ns3/assert.h"

#include "ns3/fatal-error.h"

#include "ns3/log.h"

#include "ns3/node-list.h"

#include "ns3/ipv4.h"

#include "ns3/ipv4-global-routing.h"

#include "global-router-interface.h"

#include "global-route-manager-impl.h"

#include "candidate-queue.h"

NS_LOG_COMPONENT_DEFINE ("GlobalRouteManager");

namespace ns3 {

// ---------------------------------------------------------------------------

//

// SPFVertex Implementation

//

// ---------------------------------------------------------------------------

SPFVertex::SPFVertex () : 

  m_vertexType (VertexUnknown), 

  m_vertexId ("255.255.255.255"), 

  m_lsa (0),

  m_distanceFromRoot (SPF_INFINITY), 

  m_rootOif (SPF_INFINITY),

  m_nextHop ("0.0.0.0"),

  m_parent (0),

  m_children (),

  m_vertexProcessed (false)

{

  NS_LOG_FUNCTION_NOARGS ();

}

SPFVertex::SPFVertex (GlobalRoutingLSA* lsa) : 

  m_vertexId (lsa->GetLinkStateId ()),

  m_lsa (lsa),

  m_distanceFromRoot (SPF_INFINITY), 

  m_rootOif (SPF_INFINITY),

  m_nextHop ("0.0.0.0"),

  m_parent (0),

  m_children (),

  m_vertexProcessed (false)

{

  NS_LOG_FUNCTION_NOARGS ();

  if (lsa->GetLSType () == GlobalRoutingLSA::RouterLSA) 

    {

      NS_LOG_LOGIC ("Setting m_vertexType to VertexRouter");

      m_vertexType = SPFVertex::VertexRouter;

    }

  else if (lsa->GetLSType () == GlobalRoutingLSA::NetworkLSA) 

    { 

      NS_LOG_LOGIC ("Setting m_vertexType to VertexNetwork");

      m_vertexType = SPFVertex::VertexNetwork;

    }

}

SPFVertex::~SPFVertex ()

{

  NS_LOG_FUNCTION_NOARGS ();

  for ( ListOfSPFVertex_t::iterator i = m_children.begin ();

        i != m_children.end ();

        i++)

    {

      SPFVertex *p = *i;

      delete p;

      p = 0;

      *i = 0;

    }

  m_children.clear ();

}

  void 

SPFVertex::SetVertexType (SPFVertex::VertexType type)

{

  NS_LOG_FUNCTION (type);

  m_vertexType = type;

}

  SPFVertex::VertexType 

SPFVertex::GetVertexType (void) const

{

  NS_LOG_FUNCTION_NOARGS ();

  return m_vertexType;

}

  void 

SPFVertex::SetVertexId (Ipv4Address id)

{

  NS_LOG_FUNCTION (id);

  m_vertexId = id;

}

  Ipv4Address

SPFVertex::GetVertexId (void) const

{

  NS_LOG_FUNCTION_NOARGS ();

  return m_vertexId;

}

  void 

SPFVertex::SetLSA (GlobalRoutingLSA* lsa)

{

  NS_LOG_FUNCTION (lsa);

  m_lsa = lsa;

}

  GlobalRoutingLSA* 

SPFVertex::GetLSA (void) const

{

  NS_LOG_FUNCTION_NOARGS ();

  return m_lsa;

}

  void 

SPFVertex::SetDistanceFromRoot (uint32_t distance)

{

  NS_LOG_FUNCTION (distance);

  m_distanceFromRoot = distance;

}

  uint32_t

SPFVertex::GetDistanceFromRoot (void) const

{

  NS_LOG_FUNCTION_NOARGS ();

  return m_distanceFromRoot;

}

  void 

{

  NS_LOG_FUNCTION (id);

  m_rootOif = id;

}

  uint32_t 

{

  NS_LOG_FUNCTION_NOARGS ();

  return m_rootOif;

}

  void 

SPFVertex::SetNextHop (Ipv4Address nextHop)

{

  NS_LOG_FUNCTION (nextHop);

  m_nextHop = nextHop;

}

  Ipv4Address

SPFVertex::GetNextHop (void) const

{

  NS_LOG_FUNCTION_NOARGS ();

  return m_nextHop;

}

  void

SPFVertex::SetParent (SPFVertex* parent)

{

  NS_LOG_FUNCTION (parent);

  m_parent = parent;

}

  SPFVertex* 

SPFVertex::GetParent (void) const

{

  NS_LOG_FUNCTION_NOARGS ();

  return m_parent;

}

  uint32_t 

SPFVertex::GetNChildren (void) const

{

  NS_LOG_FUNCTION_NOARGS ();

  return m_children.size ();

}

  SPFVertex* 

SPFVertex::GetChild (uint32_t n) const

{

  NS_LOG_FUNCTION (n);

  uint32_t j = 0;

  for ( ListOfSPFVertex_t::const_iterator i = m_children.begin ();

        i != m_children.end ();

        i++, j++)

    {

      if (j == n)

        {

          return *i;

        }

    }

  NS_ASSERT_MSG (false, "Index <n> out of range.");

  return 0;

}

  uint32_t 

SPFVertex::AddChild (SPFVertex* child)

{

  NS_LOG_FUNCTION (child);

  m_children.push_back (child);

  return m_children.size ();

}

void 

SPFVertex::SetVertexProcessed (bool value)

{

  m_vertexProcessed = value;

}

bool 

SPFVertex::IsVertexProcessed (void) const

{

  return m_vertexProcessed;

}

// ---------------------------------------------------------------------------

//

// GlobalRouteManagerLSDB Implementation

//

// ---------------------------------------------------------------------------

GlobalRouteManagerLSDB::GlobalRouteManagerLSDB ()

:

  m_database ()

{

  NS_LOG_FUNCTION_NOARGS ();

}

GlobalRouteManagerLSDB::~GlobalRouteManagerLSDB ()

{

  NS_LOG_FUNCTION_NOARGS ();

  LSDBMap_t::iterator i;

  for (i= m_database.begin (); i!= m_database.end (); i++)

    {

      NS_LOG_LOGIC ("free LSA");

      GlobalRoutingLSA* temp = i->second;

      delete temp;

    }

  NS_LOG_LOGIC ("clear map");

  m_database.clear ();

}

  void

GlobalRouteManagerLSDB::Initialize ()

{

  NS_LOG_FUNCTION_NOARGS ();

  LSDBMap_t::iterator i;

  for (i= m_database.begin (); i!= m_database.end (); i++)

    {

      GlobalRoutingLSA* temp = i->second;

      temp->SetStatus (GlobalRoutingLSA::LSA_SPF_NOT_EXPLORED);

    }

}

  void

GlobalRouteManagerLSDB::Insert (Ipv4Address addr, GlobalRoutingLSA* lsa)

{

  NS_LOG_FUNCTION (addr << lsa);

  m_database.insert (LSDBPair_t (addr, lsa));

}

  GlobalRoutingLSA*

GlobalRouteManagerLSDB::GetLSA (Ipv4Address addr) const

{

  NS_LOG_FUNCTION (addr);

//

// Look up an LSA by its address.

//

  LSDBMap_t::const_iterator i;

  for (i= m_database.begin (); i!= m_database.end (); i++)

  {

    if (i->first == addr)

    {

      return i->second;

    }

  }

  return 0;

}

  GlobalRoutingLSA*

GlobalRouteManagerLSDB::GetLSAByLinkData (Ipv4Address addr) const

{

  NS_LOG_FUNCTION (addr);

//

// Look up an LSA by its address.

//

  LSDBMap_t::const_iterator i;

  for (i= m_database.begin (); i!= m_database.end (); i++)

    {

      GlobalRoutingLSA* temp = i->second;

// Iterate among temp's Link Records

      for (uint32_t j = 0; j < temp->GetNLinkRecords (); j++)

        {

          GlobalRoutingLinkRecord *lr = temp->GetLinkRecord (j);

          if ( lr->GetLinkType () == GlobalRoutingLinkRecord::TransitNetwork &&

               lr->GetLinkData () == addr)

            {

              return temp;

            }

        }

    }

  return 0;

}

// ---------------------------------------------------------------------------

//

// GlobalRouteManagerImpl Implementation

//

// ---------------------------------------------------------------------------

GlobalRouteManagerImpl::GlobalRouteManagerImpl () 

: 

  m_spfroot (0) 

{

  NS_LOG_FUNCTION_NOARGS ();

  m_lsdb = new GlobalRouteManagerLSDB ();

}

GlobalRouteManagerImpl::~GlobalRouteManagerImpl ()

{

  NS_LOG_FUNCTION_NOARGS ();

  if (m_lsdb)

    {

      delete m_lsdb;

    }

}

  void

GlobalRouteManagerImpl::DebugUseLsdb (GlobalRouteManagerLSDB* lsdb)

{

  NS_LOG_FUNCTION (lsdb);

  if (m_lsdb)

    {

      delete m_lsdb;

    }

  m_lsdb = lsdb;

}

  void

GlobalRouteManagerImpl::DeleteGlobalRoutes ()

{

  NS_LOG_FUNCTION_NOARGS ();

  for (NodeList::Iterator i = NodeList::Begin (); i != NodeList::End (); i++)

    {

      Ptr<Node> node = *i;

      Ptr<Ipv4GlobalRouting> gr = GetGlobalRoutingProtocol (node->GetId ());

      uint32_t j = 0;

      uint32_t nRoutes = gr->GetNRoutes ();

      NS_LOG_LOGIC ("Deleting " << gr->GetNRoutes ()<< " routes from node " << node->GetId ());

      // Each time we delete route 0, the route index shifts downward

      // We can delete all routes if we delete the route numbered 0

      // nRoutes times

      for (j = 0; j < nRoutes; j++)

        {

          NS_LOG_LOGIC ("Deleting global route " << j << " from node " << node->GetId ());

          gr->RemoveRoute (0);        

        }

      NS_LOG_LOGIC ("Deleted " << j << " global routes from node "<< node->GetId ());

    }

  if (m_lsdb)

    {

      NS_LOG_LOGIC ("Deleting LSDB, creating new one");

      delete m_lsdb;

      m_lsdb = new GlobalRouteManagerLSDB ();

    }

}

//

// In order to build the routing database, we need at least one of the nodes

// to participate as a router.  This is a convenience function that makes

// all nodes routers.  We do this by walking the list of nodes in the system

// and aggregating a Global Router Interface to each of the nodes.

//

  void

GlobalRouteManagerImpl::SelectRouterNodes () 

{

  NS_LOG_FUNCTION_NOARGS ();

  for (NodeList::Iterator i = NodeList::Begin (); i != NodeList::End (); i++)

    {

      Ptr<Node> node = *i;

      NS_LOG_LOGIC ("Adding GlobalRouter interface to node " << node->GetId ());

      Ptr<GlobalRouter> globalRouter = CreateObject<GlobalRouter> ();

      node->AggregateObject (globalRouter);

      NS_LOG_LOGIC ("Adding GlobalRouting Protocol to node " << node->GetId ());

      Ptr<Ipv4GlobalRouting> globalRouting = CreateObject<Ipv4GlobalRouting> ();

      // This is the object that will keep the global routes.  We insert it

      // at slightly higher priority than static routing (which is at zero).

      // This means that global routes (e.g. host routes) will be consulted

      // before static routes

      Ptr<Ipv4> ipv4 = node->GetObject<Ipv4> ();

      NS_ASSERT_MSG (ipv4, "GlobalRouteManagerImpl::SelectRouterNodes (): "

        "GetObject for <Ipv4> interface failed");

      // XXX make the below  priority value an attribute

      ipv4->AddRoutingProtocol (globalRouting, 3);  

      // Locally cache the globalRouting pointer; we'll need it later

      // when we add routes

      AddGlobalRoutingProtocol (node->GetId (), globalRouting);

    }

}

  void

GlobalRouteManagerImpl::SelectRouterNodes (NodeContainer c) 

{

  NS_LOG_FUNCTION (&c);

  for (NodeContainer::Iterator i = c.Begin (); i != c.End (); i++)

    {

      Ptr<Node> node = *i;

      NS_LOG_LOGIC ("Adding GlobalRouter interface to node " << 

        node->GetId ());

      Ptr<GlobalRouter> globalRouter = CreateObject<GlobalRouter> ();

      node->AggregateObject (globalRouter);

      NS_LOG_LOGIC ("Adding GlobalRouting Protocol to node " << node->GetId ());

      Ptr<Ipv4GlobalRouting> globalRouting = CreateObject<Ipv4GlobalRouting> ();

      // This is the object that will keep the global routes.  We insert it

      // at slightly higher priority than static routing (which is at zero).

      // This means that global routes (e.g. host routes) will be consulted

      // before static routes

      Ptr<Ipv4> ipv4 = node->GetObject<Ipv4> ();

      NS_ASSERT_MSG (ipv4, "GlobalRouteManagerImpl::SelectRouterNodes (): "

        "GetObject for <Ipv4> interface failed");

      // XXX make the below  priority value an attribute

      ipv4->AddRoutingProtocol (globalRouting, 3);  

      // Locally cache the globalRouting pointer; we'll need it later

      // when we add routes

      AddGlobalRoutingProtocol (node->GetId (), globalRouting);

    }

}

//

// In order to build the routing database, we need to walk the list of nodes

// in the system and look for those that support the GlobalRouter interface.

// These routers will export a number of Link State Advertisements (LSAs)

// that describe the links and networks that are "adjacent" (i.e., that are

// on the other side of a point-to-point link).  We take these LSAs and put

// add them to the Link State DataBase (LSDB) from which the routes will 

// ultimately be computed.

//

  void

GlobalRouteManagerImpl::BuildGlobalRoutingDatabase () 

{

  NS_LOG_FUNCTION_NOARGS ();

//

// Walk the list of nodes looking for the GlobalRouter Interface.  Nodes with

// global router interfaces are, not too surprisingly, our routers.

//

  for (NodeList::Iterator i = NodeList::Begin (); i != NodeList::End (); i++)

    {

      Ptr<Node> node = *i;

      Ptr<GlobalRouter> rtr = node->GetObject<GlobalRouter> ();

//      

// Ignore nodes that aren't participating in routing.

//

      if (!rtr)

        {

          continue;

        }

//

// You must call DiscoverLSAs () before trying to use any routing info or to

// update LSAs.  DiscoverLSAs () drives the process of discovering routes in

// the GlobalRouter.  Afterward, you may use GetNumLSAs (), which is a very

// computationally inexpensive call.  If you call GetNumLSAs () before calling 

// DiscoverLSAs () will get zero as the number since no routes have been 

// found.

//

      uint32_t numLSAs = rtr->DiscoverLSAs ();

      NS_LOG_LOGIC ("Found " << numLSAs << " LSAs");

      for (uint32_t j = 0; j < numLSAs; ++j)

        {

          GlobalRoutingLSA* lsa = new GlobalRoutingLSA ();

//

// This is the call to actually fetch a Link State Advertisement from the