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

/*

 * 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

 */

#include <utility>

#include <vector>

#include <queue>

#include "ns3/assert.h"

#include "ns3/fatal-error.h"

#include "ns3/debug.h"

#include "ns3/node-list.h"

#include "ns3/ipv4.h"

#include "global-router-interface.h"

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

#include "candidate-queue.h"

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

{

}

SPFVertex::SPFVertex (GlobalRouterLSA* lsa) : 

  m_vertexType (VertexRouter), 

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

{

}

SPFVertex::~SPFVertex ()

{

  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)

{

  m_vertexType = type;

}

  SPFVertex::VertexType 

SPFVertex::GetVertexType (void) const

{

  return m_vertexType;

}

  void 

SPFVertex::SetVertexId (Ipv4Address id)

{

  m_vertexId = id;

}

  Ipv4Address

SPFVertex::GetVertexId (void) const

{

  return m_vertexId;

}

  void 

SPFVertex::SetLSA (GlobalRouterLSA* lsa)

{

  m_lsa = lsa;

}

  GlobalRouterLSA* 

SPFVertex::GetLSA (void) const

{

  return m_lsa;

}

  void 

SPFVertex::SetDistanceFromRoot (uint32_t distance)

{

  m_distanceFromRoot = distance;

}

  uint32_t

SPFVertex::GetDistanceFromRoot (void) const

{

  return m_distanceFromRoot;

}

  void 

SPFVertex::SetOutgoingInterfaceId (uint32_t id)

{

  m_rootOif = id;

}

  uint32_t 

SPFVertex::GetOutgoingInterfaceId (void) const

{

  return m_rootOif;

}

  void 

SPFVertex::SetNextHop (Ipv4Address nextHop)

{

  m_nextHop = nextHop;

}

  Ipv4Address

SPFVertex::GetNextHop (void) const

{

  return m_nextHop;

}

  void

SPFVertex::SetParent (SPFVertex* parent)

{

  m_parent = parent;

}

  SPFVertex* 

SPFVertex::GetParent (void) const

{

  return m_parent;

}

  uint32_t 

SPFVertex::GetNChildren (void) const

{

  return m_children.size ();

}

  SPFVertex* 

SPFVertex::GetChild (uint32_t n) const

{

  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)

{

  m_children.push_back (child);

  return m_children.size ();

}

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

//

// GlobalRouteManagerLSDB Implementation

//

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

GlobalRouteManagerLSDB::GlobalRouteManagerLSDB ()

:

  m_database ()

{

  NS_DEBUG ("GlobalRouteManagerLSDB::GlobalRouteManagerLSDB ()");

}

GlobalRouteManagerLSDB::~GlobalRouteManagerLSDB ()

{

  NS_DEBUG ("GlobalRouteManagerLSDB::~GlobalRouteManagerLSDB ()");

  LSDBMap_t::iterator i;

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

    {

      NS_DEBUG ("GlobalRouteManagerLSDB::~GlobalRouteManagerLSDB ():free LSA");

      GlobalRouterLSA* temp = i->second;

      delete temp;

    }

  NS_DEBUG ("GlobalRouteManagerLSDB::~GlobalRouteManagerLSDB ():  clear map");

  m_database.clear ();

}

  void

GlobalRouteManagerLSDB::Initialize ()

{

  NS_DEBUG ("GlobalRouteManagerLSDB::Initialize ()");

  LSDBMap_t::iterator i;

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

    {

      GlobalRouterLSA* temp = i->second;

      temp->SetStatus (GlobalRouterLSA::LSA_SPF_NOT_EXPLORED);

    }

}

  void

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

{

  NS_DEBUG ("GlobalRouteManagerLSDB::Insert ()");

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

}

  GlobalRouterLSA*

GlobalRouteManagerLSDB::GetLSA (Ipv4Address addr) const

{

  NS_DEBUG ("GlobalRouteManagerLSDB::GetLSA ()");

//

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

}

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

//

// GlobalRouteManagerImpl Implementation

//

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

GlobalRouteManagerImpl::GlobalRouteManagerImpl () 

: 

  m_spfroot (0) 

{

  NS_DEBUG ("GlobalRouteManagerImpl::GlobalRoutemanagerImpl ()");

  m_lsdb = new GlobalRouteManagerLSDB ();

}

GlobalRouteManagerImpl::~GlobalRouteManagerImpl ()

{

  NS_DEBUG ("GlobalRouteManagerImpl::~GlobalRouteManagerImpl ()");

  if (m_lsdb)

    {

      delete m_lsdb;

    }

}

  void

GlobalRouteManagerImpl::DebugUseLsdb (GlobalRouteManagerLSDB* lsdb)

{

  NS_DEBUG ("GlobalRouteManagerImpl::DebugUseLsdb ()");

  if (m_lsdb)

    {

      delete m_lsdb;

    }

  m_lsdb = lsdb;

}

//

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

// to participate as a router.  Eventually we expect to provide a mechanism

// for selecting a subset of the nodes to participate; for now, we just make

// 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_DEBUG ("GlobalRouteManagerImpl::SelectRouterNodes ()");

  typedef std::vector < Ptr<Node> >::iterator Iterator;

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

    {

      Ptr<Node> node = *i;

      NS_DEBUG ("GlobalRouteManagerImpl::SelectRouterNodes (): "

        "Adding GlobalRouter interface to node " <<

                node->GetId ());

      Ptr<GlobalRouter> globalRouter = Create<GlobalRouter> (node);

      node->AddInterface (globalRouter);

    }

}

//

// 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_DEBUG ("GlobalRouteManagerImpl::BuildGlobalRoutingDatabase()");

//

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

//

  typedef std::vector < Ptr<Node> >::iterator Iterator;

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

    {

      Ptr<Node> node = *i;

      Ptr<GlobalRouter> rtr = 

        node->QueryInterface<GlobalRouter> (GlobalRouter::iid);

//      

// 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_DEBUG ("Discover LSAs:  Found " << numLSAs << " LSAs");

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

        {

          GlobalRouterLSA* lsa = new GlobalRouterLSA ();

//

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

// router.

//

          rtr->GetLSA (j, *lsa);

          NS_DEBUG ("LSA " << j);

          NS_DEBUG (*lsa);

//

// Write the newly discovered link state advertisement to the database.

//

          m_lsdb->Insert (lsa->GetLinkStateId (), lsa); 

        }

    }

}

//

// For each node that is a global router (which is determined by the presence

// of an aggregated GlobalRouter interface), run the Dijkstra SPF calculation

// on the database rooted at that router, and populate the node forwarding

// tables.

//

// This function parallels RFC2328, Section 16.1.1, and quagga ospfd

//

// This calculation yields the set of intra-area routes associated

// with an area (called hereafter Area A).  A router calculates the

// shortest-path tree using itself as the root.  The formation

// of the shortest path tree is done here in two stages.  In the

// first stage, only links between routers and transit networks are

// considered.  Using the Dijkstra algorithm, a tree is formed from

// this subset of the link state database.  In the second stage,

// leaves are added to the tree by considering the links to stub

// networks.

//

// The area's link state database is represented as a directed graph.  

// The graph's vertices are routers, transit networks and stub networks.  

//

// The first stage of the procedure (i.e., the Dijkstra algorithm)

// can now be summarized as follows. At each iteration of the

// algorithm, there is a list of candidate vertices.  Paths from

// the root to these vertices have been found, but not necessarily

// the shortest ones.  However, the paths to the candidate vertex

// that is closest to the root are guaranteed to be shortest; this

// vertex is added to the shortest-path tree, removed from the

// candidate list, and its adjacent vertices are examined for

// possible addition to/modification of the candidate list.  The

// algorithm then iterates again.  It terminates when the candidate

// list becomes empty. 

//

  void

GlobalRouteManagerImpl::InitializeRoutes ()

{

  NS_DEBUG ("GlobalRouteManagerImpl::InitializeRoutes ()");

//

// Walk the list of nodes in the system.

//

  typedef std::vector < Ptr<Node> >::iterator Iterator;

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

    {

      Ptr<Node> node = *i;

//

// Look for the GlobalRouter interface that indicates that the node is

// participating in routing.

//

      Ptr<GlobalRouter> rtr = 

        node->QueryInterface<GlobalRouter> (GlobalRouter::iid);

//

// if the node has a global router interface, then run the global routing

// algorithms.

//

      if (rtr && rtr->GetNumLSAs () )

        {

          SPFCalculate (rtr->GetRouterId ());

        }

    }

}

//

// This method is derived from quagga ospf_spf_next ().  See RFC2328 Section 

// 16.1 (2) for further details.

//

// We're passed a parameter <v> that is a vertex which is already in the SPF

// tree.  A vertex represents a router node.  We also get a reference to the

// SPF candidate queue, which is a priority queue containing the shortest paths

// to the networks we know about.

//

// We examine the links in v's LSA and update the list of candidates with any

// vertices not already on the list.  If a lower-cost path is found to a

// vertex already on the candidate list, store the new (lower) cost.

//

  void

GlobalRouteManagerImpl::SPFNext (SPFVertex* v, CandidateQueue& candidate)

{

  SPFVertex* w = 0;

  GlobalRouterLSA* w_lsa = 0;

  uint32_t distance = 0;

  NS_DEBUG ("GlobalRouteManagerImpl::SPFNext ()");

//

// Always true for now, since all our LSAs are RouterLSAs.

//

  if (v->GetVertexType () == SPFVertex::VertexRouter) 

    {

      if (true)

        {

          NS_DEBUG ("SPFNext: Examining " << v->GetVertexId () << "'s " <<

            v->GetLSA ()->GetNLinkRecords () << " link records");

//

// Walk the list of link records in the link state advertisement associated 

// with the "current" router (represented by vertex <v>).

//

          for (uint32_t i = 0; i < v->GetLSA ()->GetNLinkRecords (); ++i)

            {

//

// (a) If this is a link to a stub network, examine the next link in V's LSA.

// Links to stub networks will be considered in the second stage of the

// shortest path calculation.

//

              GlobalRouterLinkRecord *l = v->GetLSA ()->GetLinkRecord (i);

              if (l->GetLinkType () == GlobalRouterLinkRecord::StubNetwork)

                {

                  NS_DEBUG ("SPFNext: Found a Stub record to " << 

                    l->GetLinkId ());

                  continue;

                }

//

// (b) Otherwise, W is a transit vertex (router or transit network).  Look up

// the vertex W's LSA (router-LSA or network-LSA) in Area A's link state

// database. 

//

              if (l->GetLinkType () == GlobalRouterLinkRecord::PointToPoint)

                {

//

// Lookup the link state advertisement of the new link -- we call it <w> in

// the link state database.

//

                  w_lsa = m_lsdb->GetLSA (l->GetLinkId ());

                  NS_ASSERT (w_lsa);

                  NS_DEBUG ("SPFNext:  Found a P2P record from " << 

                    v->GetVertexId () << " to " << w_lsa->GetLinkStateId ());

//

// (c) If vertex W is already on the shortest-path tree, examine the next

// link in the LSA.

//

// If the link is to a router that is already in the shortest path first tree

// then we have it covered -- ignore it.

//

                  if (w_lsa->GetStatus () == 

                      GlobalRouterLSA::LSA_SPF_IN_SPFTREE) 

                    {

                      NS_DEBUG ("SPFNext: Skipping->  LSA "<< 

                        w_lsa->GetLinkStateId () << " already in SPF tree");

                      continue;

                    }

//

// The link is to a router we haven't dealt with yet.

//

// (d) Calculate the link state cost D of the resulting path from the root to 

// vertex W.  D is equal to the sum of the link state cost of the (already 

// calculated) shortest path to vertex V and the advertised cost of the link

// between vertices V and W.  

//

                  distance = v->GetDistanceFromRoot () + l->GetMetric ();

                  NS_DEBUG ("SPFNext: Considering w_lsa " << 

                    w_lsa->GetLinkStateId ());