global-route-manager-impl.cc

Go to the documentation of this file.

/*
 * Copyright 2007 University of Washington
 * Copyright (C) 1999, 2000 Kunihiro Ishiguro, Toshiaki Takada
 *
 * SPDX-License-Identifier: GPL-2.0-only
 *
 * 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 "global-route-manager-impl.h"
 
#include "candidate-queue.h"
#include "global-router-interface.h"
#include "global-routing.h"
#include "ipv4-l3-protocol.h"
#include "ipv4.h"
#include "ipv6-l3-protocol.h"
#include "ipv6-route.h"
 
#include "ns3/assert.h"
#include "ns3/boolean.h"
#include "ns3/config.h"
#include "ns3/fatal-error.h"
#include "ns3/log.h"
#include "ns3/node-list.h"
#include "ns3/simulator.h"
 
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
 
namespace ns3
{
 
NS_LOG_COMPONENT_DEFINE("GlobalRouteManagerImpl");
 
/**
 * @brief Stream insertion operator.
 *
 * @param os the reference to the output stream
 * @param exit the exit gateway and egress interface index
 * @returns the reference to the output stream
 */
std::ostream&
operator<<(std::ostream& os, const std::pair<Ipv4Address, int>& exit)
{
    os << "(" << exit.first << ", " << exit.second << ")";
    return os;
}
 
/**
 * @brief Stream insertion operator.
 *
 * @param os the reference to the output stream
 * @param exit the exit gateway and egress interface index
 * @returns the reference to the output stream
 */
std::ostream&
operator<<(std::ostream& os, const std::pair<Ipv6Address, int>& exit)
{
    os << "(" << exit.first << ", " << exit.second << ")";
    return os;
}
 
// ---------------------------------------------------------------------------
//
// SPFVertex Implementation
//
// ---------------------------------------------------------------------------
template <typename T>
SPFVertex<T>::SPFVertex()
    : m_vertexType(VertexUnknown),
      m_vertexId("255.255.255.255"),
      m_lsa(nullptr),
      m_distanceFromRoot(SPF_INFINITY),
      m_rootOif(SPF_INFINITY),
      m_nextHop(IpAddress::GetZero()),
      m_parents(),
      m_children(),
      m_vertexProcessed(false)
{
    NS_LOG_FUNCTION(this);
}
 
template <typename T>
SPFVertex<T>::SPFVertex(GlobalRoutingLSA<IpManager>* lsa)
    : m_vertexId(lsa->GetLinkStateId()),
      m_lsa(lsa),
      m_distanceFromRoot(SPF_INFINITY),
      m_rootOif(SPF_INFINITY),
      m_nextHop(IpAddress::GetZero()),
      m_parents(),
      m_children(),
      m_vertexProcessed(false)
{
    NS_LOG_FUNCTION(this << lsa);
 
    if (lsa->GetLSType() == GlobalRoutingLSA<IpManager>::RouterLSA)
    {
        NS_LOG_LOGIC("Setting m_vertexType to VertexRouter");
        m_vertexType = SPFVertex<T>::VertexRouter;
        m_node = lsa->GetNode();
    }
    else if (lsa->GetLSType() == GlobalRoutingLSA<IpManager>::NetworkLSA)
    {
        NS_LOG_LOGIC("Setting m_vertexType to VertexNetwork");
        m_vertexType = SPFVertex<T>::VertexNetwork;
    }
}
 
template <typename T>
SPFVertex<T>::~SPFVertex()
{
    NS_LOG_FUNCTION(this);
 
    NS_LOG_LOGIC("Children vertices - " << m_children);
    NS_LOG_LOGIC("Parent vertices - " << m_parents);
 
    // find this node from all its parents and remove the entry of this node
    // from all its parents
    for (auto piter = m_parents.begin(); piter != m_parents.end(); piter++)
    {
        // remove the current vertex from its parent's children list. Check
        // if the size of the list is reduced, or the child<->parent relation
        // is not bidirectional
        uint32_t orgCount = (*piter)->m_children.size();
        (*piter)->m_children.remove(this);
        uint32_t newCount = (*piter)->m_children.size();
 
        NS_ASSERT_MSG(orgCount > newCount,
                      "Unable to find the current vertex from its parents --- impossible!");
    }
 
    // delete children
    while (!m_children.empty())
    {
        // pop out children one by one. Some children may disappear
        // when deleting some other children in the list. As a result,
        // it is necessary to use pop to walk through all children, instead
        // of using iterator.
        //
        // Note that m_children.pop_front () is not necessary as this
        // p is removed from the children list when p is deleted
        SPFVertex<T>* p = m_children.front();
        // 'p' == 0, this child is already deleted by its other parent
        if (p == nullptr)
        {
            continue;
        }
        NS_LOG_LOGIC("Parent vertex-" << m_vertexId << " deleting its child vertex-"
                                      << p->GetVertexId());
        delete p;
        p = nullptr;
    }
    m_children.clear();
    // delete parents
    m_parents.clear();
    // delete root exit direction
    m_ecmpRootExits.clear();
 
    NS_LOG_LOGIC("Vertex-" << m_vertexId << " completed deleted");
}
 
template <typename T>
void
SPFVertex<T>::SetVertexType(SPFVertex<T>::VertexType type)
{
    NS_LOG_FUNCTION(this << type);
    m_vertexType = type;
}
 
template <typename T>
SPFVertex<T>::VertexType
SPFVertex<T>::GetVertexType() const
{
    NS_LOG_FUNCTION(this);
    return m_vertexType;
}
 
template <typename T>
void
SPFVertex<T>::SetVertexId(IpAddress id)
{
    NS_LOG_FUNCTION(this << id);
    m_vertexId = id;
}
 
template <typename T>
SPFVertex<T>::IpAddress
SPFVertex<T>::GetVertexId() const
{
    NS_LOG_FUNCTION(this);
    return m_vertexId;
}
 
template <typename T>
void
SPFVertex<T>::SetLSA(GlobalRoutingLSA<IpManager>* lsa)
{
    NS_LOG_FUNCTION(this << lsa);
    m_lsa = lsa;
}
 
template <typename T>
GlobalRoutingLSA<T>*
SPFVertex<T>::GetLSA() const
{
    NS_LOG_FUNCTION(this);
    return m_lsa;
}
 
template <typename T>
void
SPFVertex<T>::SetDistanceFromRoot(uint32_t distance)
{
    NS_LOG_FUNCTION(this << distance);
    m_distanceFromRoot = distance;
}
 
template <typename T>
uint32_t
SPFVertex<T>::GetDistanceFromRoot() const
{
    NS_LOG_FUNCTION(this);
    return m_distanceFromRoot;
}
 
template <typename T>
void
SPFVertex<T>::SetParent(SPFVertex* parent)
{
    NS_LOG_FUNCTION(this << parent);
 
    // always maintain only one parent when using setter/getter methods
    m_parents.clear();
    m_parents.push_back(parent);
}
 
template <typename T>
SPFVertex<T>*
SPFVertex<T>::GetParent(uint32_t i) const
{
    NS_LOG_FUNCTION(this << i);
 
    // If the index i is out-of-range, return 0 and do nothing
    if (m_parents.size() <= i)
    {
        NS_LOG_LOGIC("Index to SPFVertex's parent is out-of-range.");
        return nullptr;
    }
    auto iter = m_parents.begin();
    while (i-- > 0)
    {
        iter++;
    }
    return *iter;
}
 
template <typename T>
void
SPFVertex<T>::MergeParent(const SPFVertex* v)
{
    NS_LOG_FUNCTION(this << v);
 
    NS_LOG_LOGIC("Before merge, list of parents = " << m_parents);
    // combine the two lists first, and then remove any duplicated after
    m_parents.insert(m_parents.end(), v->m_parents.begin(), v->m_parents.end());
    // remove duplication
    m_parents.sort();
    m_parents.unique();
    NS_LOG_LOGIC("After merge, list of parents = " << m_parents);
}
 
template <typename T>
void
SPFVertex<T>::SetRootExitDirection(IpAddress nextHop, int32_t id)
{
    NS_LOG_FUNCTION(this << nextHop << id);
 
    // always maintain only one root's exit
    m_ecmpRootExits.clear();
    m_ecmpRootExits.emplace_back(nextHop, id);
    // update the following in order to be backward compatible with
    // GetNextHop and GetOutgoingInterface methods
    m_nextHop = nextHop;
    m_rootOif = id;
}
 
template <typename T>
void
SPFVertex<T>::SetRootExitDirection(SPFVertex<T>::NodeExit_t exit)
{
    NS_LOG_FUNCTION(this << exit);
    SetRootExitDirection(exit.first, exit.second);
}
 
template <typename T>
SPFVertex<T>::NodeExit_t
SPFVertex<T>::GetRootExitDirection(uint32_t i) const
{
    NS_LOG_FUNCTION(this << i);
 
    NS_ASSERT_MSG(i < m_ecmpRootExits.size(),
                  "Index out-of-range when accessing SPFVertex::m_ecmpRootExits!");
    auto iter = m_ecmpRootExits.begin();
    while (i-- > 0)
    {
        iter++;
    }
 
    return *iter;
}
 
template <typename T>
SPFVertex<T>::NodeExit_t
SPFVertex<T>::GetRootExitDirection() const
{
    NS_LOG_FUNCTION(this);
 
    NS_ASSERT_MSG(m_ecmpRootExits.size() <= 1,
                  "Assumed there is at most one exit from the root to this vertex");
    return GetRootExitDirection(0);
}
 
template <typename T>
void
SPFVertex<T>::MergeRootExitDirections(const SPFVertex* vertex)
{
    NS_LOG_FUNCTION(this << vertex);
 
    // obtain the external list of exit directions
    //
    // Append the external list into 'this' and remove duplication afterward
    const ListOfNodeExit_t& extList = vertex->m_ecmpRootExits;
    m_ecmpRootExits.insert(m_ecmpRootExits.end(), extList.begin(), extList.end());
    m_ecmpRootExits.sort();
    m_ecmpRootExits.unique();
}
 
template <typename T>
void
SPFVertex<T>::InheritAllRootExitDirections(const SPFVertex* vertex)
{
    NS_LOG_FUNCTION(this << vertex);
 
    // discard all exit direction currently associated with this vertex,
    // and copy all the exit directions from the given vertex
    if (!m_ecmpRootExits.empty())
    {
        NS_LOG_WARN("x root exit directions in this vertex are going to be discarded");
    }
    m_ecmpRootExits.clear();
    m_ecmpRootExits.insert(m_ecmpRootExits.end(),
                           vertex->m_ecmpRootExits.begin(),
                           vertex->m_ecmpRootExits.end());
}
 
template <typename T>
uint32_t
SPFVertex<T>::GetNRootExitDirections() const
{
    NS_LOG_FUNCTION(this);
    return m_ecmpRootExits.size();
}
 
template <typename T>
uint32_t
SPFVertex<T>::GetNChildren() const
{
    NS_LOG_FUNCTION(this);
    return m_children.size();
}
 
template <typename T>
SPFVertex<T>*
SPFVertex<T>::GetChild(uint32_t n) const
{
    NS_LOG_FUNCTION(this << n);
    uint32_t j = 0;
 
    for (auto 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 nullptr;
}
 
template <typename T>
uint32_t
SPFVertex<T>::AddChild(SPFVertex* child)
{
    NS_LOG_FUNCTION(this << child);
    m_children.push_back(child);
    return m_children.size();
}
 
template <typename T>
void
SPFVertex<T>::SetVertexProcessed(bool value)
{
    NS_LOG_FUNCTION(this << value);
    m_vertexProcessed = value;
}
 
template <typename T>
bool
SPFVertex<T>::IsVertexProcessed() const
{
    NS_LOG_FUNCTION(this);
    return m_vertexProcessed;
}
 
template <typename T>
void
SPFVertex<T>::ClearVertexProcessed()
{
    NS_LOG_FUNCTION(this);
    for (uint32_t i = 0; i < this->GetNChildren(); i++)
    {
        this->GetChild(i)->ClearVertexProcessed();
    }
    this->SetVertexProcessed(false);
}
 
template <typename T>
Ptr<Node>
SPFVertex<T>::GetNode() const
{
    return m_node;
}
 
// ---------------------------------------------------------------------------
//
// GlobalRouteManagerLSDB Implementation
//
// ---------------------------------------------------------------------------
template <typename T>
GlobalRouteManagerLSDB<T>::GlobalRouteManagerLSDB()
    : m_database(),
      m_extdatabase()
{
    NS_LOG_FUNCTION(this);
}
 
template <typename T>
GlobalRouteManagerLSDB<T>::~GlobalRouteManagerLSDB()
{
    NS_LOG_FUNCTION(this);
    for (auto i = m_database.begin(); i != m_database.end(); i++)
    {
        NS_LOG_LOGIC("free LSA");
        GlobalRoutingLSA<IpManager>* temp = i->second;
        delete temp;
    }
    for (uint32_t j = 0; j < m_extdatabase.size(); j++)
    {
        NS_LOG_LOGIC("free ASexternalLSA");
        GlobalRoutingLSA<IpManager>* temp = m_extdatabase.at(j);
        delete temp;
    }
    NS_LOG_LOGIC("clear map");
    m_database.clear();
}
 
template <typename T>
void
GlobalRouteManagerLSDB<T>::Initialize()
{
    NS_LOG_FUNCTION(this);
    for (auto i = m_database.begin(); i != m_database.end(); i++)
    {
        GlobalRoutingLSA<IpManager>* temp = i->second;
        temp->SetStatus(GlobalRoutingLSA<IpManager>::LSA_SPF_NOT_EXPLORED);
    }
}
 
template <typename T>
void
GlobalRouteManagerLSDB<T>::Insert(IpAddress addr, GlobalRoutingLSA<IpManager>* lsa)
{
    NS_LOG_FUNCTION(this << addr << lsa);
    if (lsa->GetLSType() == GlobalRoutingLSA<IpManager>::ASExternalLSAs)
    {
        m_extdatabase.push_back(lsa);
    }
    else
    {
        m_database.insert(LSDBPair_t(addr, lsa));
    }
}
 
template <typename T>
GlobalRoutingLSA<typename GlobalRouteManagerLSDB<T>::IpManager>*
GlobalRouteManagerLSDB<T>::GetExtLSA(uint32_t index) const
{
    NS_LOG_FUNCTION(this << index);
    return m_extdatabase.at(index);
}
 
template <typename T>
uint32_t
GlobalRouteManagerLSDB<T>::GetNumExtLSAs() const
{
    NS_LOG_FUNCTION(this);
    return m_extdatabase.size();
}
 
template <typename T>
GlobalRoutingLSA<typename GlobalRouteManagerLSDB<T>::IpManager>*
GlobalRouteManagerLSDB<T>::GetLSA(IpAddress addr) const
{
    NS_LOG_FUNCTION(this << addr);
    //
    // Look up an LSA by its address.
    //
    for (auto i = m_database.begin(); i != m_database.end(); i++)
    {
        if (i->first == addr)
        {
            return i->second;
        }
    }
    return nullptr;
}
 
template <typename T>
GlobalRoutingLSA<typename GlobalRouteManagerLSDB<T>::IpManager>*
GlobalRouteManagerLSDB<T>::GetLSAByLinkData(IpAddress addr) const
{
    NS_LOG_FUNCTION(this << addr);
    //
    // Look up an LSA by its address.
    //
    for (auto i = m_database.begin(); i != m_database.end(); i++)
    {
        GlobalRoutingLSA<IpManager>* temp = i->second;
        // Iterate among temp's Link Records
        for (uint32_t j = 0; j < temp->GetNLinkRecords(); j++)
        {
            GlobalRoutingLinkRecord<IpManager>* lr = temp->GetLinkRecord(j);
            if (lr->GetLinkType() == GlobalRoutingLinkRecord<IpManager>::TransitNetwork &&
                lr->GetLinkData() == addr)
            {
                return temp;
            }
        }
    }
    return nullptr;
}
 
// ---------------------------------------------------------------------------
//
// GlobalRouteManagerImpl Implementation
//
// ---------------------------------------------------------------------------
 
template <typename T>
GlobalRouteManagerImpl<T>::GlobalRouteManagerImpl()
    : m_spfroot(nullptr)
{
    NS_LOG_FUNCTION(this);
    m_lsdb = new GlobalRouteManagerLSDB<IpManager>();
}
 
template <typename T>
GlobalRouteManagerImpl<T>::~GlobalRouteManagerImpl()
{
    NS_LOG_FUNCTION(this);
    if (m_lsdb)
    {
        delete m_lsdb;
    }
}
 
template <typename T>
void
GlobalRouteManagerImpl<T>::DebugUseLsdb(GlobalRouteManagerLSDB<T>* lsdb)
{
    NS_LOG_FUNCTION(this << lsdb);
    if (m_lsdb)
    {
        delete m_lsdb;
    }
    m_lsdb = lsdb;
}
 
template <typename T>
void
GlobalRouteManagerImpl<T>::DeleteGlobalRoutes()
{
    NS_LOG_FUNCTION(this);
    for (auto i = NodeList::Begin(); i != NodeList::End(); i++)
    {
        Ptr<Node> node = *i;
        Ptr<GlobalRouter<IpManager>> router = node->GetObject<GlobalRouter<IpManager>>();
        if (!router)
        {
            continue;
        }
        Ptr<GlobalRouting<IpRoutingProtocol>> gr = router->GetRoutingProtocol();
        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<IpManager>();
    }
}
 
//
// 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.
//
 
template <typename T>
void
GlobalRouteManagerImpl<T>::BuildGlobalRoutingDatabase()
{
    NS_LOG_FUNCTION(this);
    //
    // Walk the list of nodes looking for the GlobalRouter Interface.  Nodes with
    // global router interfaces are, not too surprisingly, our routers.
    //
    for (auto i = NodeList::Begin(); i != NodeList::End(); i++)
    {
        Ptr<Node> node = *i;
 
        Ptr<GlobalRouter<IpManager>> rtr = node->GetObject<GlobalRouter<IpManager>>();
        //
        // 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.
        //
        Ptr<GlobalRouting<IpRoutingProtocol>> grouting = rtr->GetRoutingProtocol();
        uint32_t numLSAs = rtr->DiscoverLSAs();
        NS_LOG_LOGIC("Found " << numLSAs << " LSAs");
 
        for (uint32_t j = 0; j < numLSAs; ++j)
        {
            auto lsa = new GlobalRoutingLSA<IpManager>();
            //
            // This is the call to actually fetch a Link State Advertisement from the
            // router.
            //
            rtr->GetLSA(j, *lsa);
            NS_LOG_LOGIC(*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.
//
 
template <typename T>
void
GlobalRouteManagerImpl<T>::InitializeRoutes()
{
    NS_LOG_FUNCTION(this);
    //
    // Walk the list of nodes in the system.
    //
    NS_LOG_INFO("About to start SPF calculation");
    for (auto 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<IpManager>> rtr = node->GetObject<GlobalRouter<IpManager>>();
 
        uint32_t systemId = Simulator::GetSystemId();
        // Ignore nodes that are not assigned to our systemId (distributed sim)
        if (node->GetSystemId() != systemId)
        {
            continue;
        }
 
        //
        // if the node has a global router interface, then run the global routing
        // algorithms.
        //
        if (rtr && rtr->GetNumLSAs())
        {
            SPFCalculate(rtr->GetRouterId());
        }
    }
    NS_LOG_INFO("Finished SPF calculation");
}
 
//
// 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.
//
 
template <typename T>
void
GlobalRouteManagerImpl<T>::SPFNext(SPFVertex<T>* v, CandidateQueue<T>& candidate)
{
    NS_LOG_FUNCTION(this << v << &candidate);
 
    SPFVertex<T>* w = nullptr;
    GlobalRoutingLSA<IpManager>* w_lsa = nullptr;
    GlobalRoutingLinkRecord<IpManager>* l = nullptr;
    uint32_t distance = 0;
    uint32_t numRecordsInVertex = 0;
    //
    // V points to a Router-LSA or Network-LSA
    // Loop over the links in router LSA or attached routers in Network LSA
    //
    if (v->GetVertexType() == SPFVertex<T>::VertexRouter)
    {
        numRecordsInVertex = v->GetLSA()->GetNLinkRecords();
    }
    if (v->GetVertexType() == SPFVertex<T>::VertexNetwork)
    {
        numRecordsInVertex = v->GetLSA()->GetNAttachedRouters();
    }
 
    // Loop over the links in V's LSA
    for (uint32_t i = 0; i < numRecordsInVertex; i++)
    {
        // Get w_lsa:  In case of V is Router-LSA
        if (v->GetVertexType() == SPFVertex<T>::VertexRouter)
        {
            NS_LOG_LOGIC("Examining link " << i << " of " << v->GetVertexId() << "'s "
                                           << v->GetLSA()->GetNLinkRecords() << " link records");
            //
            // (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.
            //
            l = v->GetLSA()->GetLinkRecord(i);
            NS_ASSERT(l != nullptr);
            if (l->GetLinkType() == GlobalRoutingLinkRecord<IpManager>::StubNetwork)
            {
                NS_LOG_LOGIC("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() == GlobalRoutingLinkRecord<IpManager>::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_LOG_LOGIC("Found a P2P record from " << v->GetVertexId() << " to "
                                                        << w_lsa->GetLinkStateId());
            }
            else if (l->GetLinkType() == GlobalRoutingLinkRecord<IpManager>::TransitNetwork)
            {
                w_lsa = m_lsdb->GetLSA(l->GetLinkId());
                NS_ASSERT(w_lsa);
                NS_LOG_LOGIC("Found a Transit record from " << v->GetVertexId() << " to "
                                                            << w_lsa->GetLinkStateId());
            }
            else
            {
                NS_ASSERT_MSG(0, "illegal Link Type");
            }
        }
        // Get w_lsa:  In case of V is Network-LSA
        if (v->GetVertexType() == SPFVertex<T>::VertexNetwork)
        {
            w_lsa = m_lsdb->GetLSAByLinkData(v->GetLSA()->GetAttachedRouter(i));
            if (!w_lsa)
            {
                continue;
            }
            NS_LOG_LOGIC("Found a Network LSA from " << v->GetVertexId() << " to "
                                                     << w_lsa->GetLinkStateId());
        }
 
        // Note:  w_lsa at this point may be either RouterLSA or NetworkLSA
        //
        // (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() == GlobalRoutingLSA<IpManager>::LSA_SPF_IN_SPFTREE)
        {
            NS_LOG_LOGIC("Skipping ->  LSA " << w_lsa->GetLinkStateId() << " already in SPF tree");
            continue;
        }
        //
        // (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.
        //
        if (v->GetLSA()->GetLSType() == GlobalRoutingLSA<IpManager>::RouterLSA)
        {
            NS_ASSERT(l != nullptr);
            distance = v->GetDistanceFromRoot() + l->GetMetric();
        }
        else
        {
            distance = v->GetDistanceFromRoot();
        }
 
        NS_LOG_LOGIC("Considering w_lsa " << w_lsa->GetLinkStateId());
 
        // Is there already vertex w in candidate list?
        if (w_lsa->GetStatus() == GlobalRoutingLSA<IpManager>::LSA_SPF_NOT_EXPLORED)
        {
            // Calculate nexthop to w
            // We need to figure out how to actually get to the new router represented
            // by <w>.  This will (among other things) find the next hop address to send
            // packets destined for this network to, and also find the outbound interface
            // used to forward the packets.
 
            // prepare vertex w
            w = new SPFVertex<T>(w_lsa);
            if (SPFNexthopCalculation(v, w, l, distance))
            {
                w_lsa->SetStatus(GlobalRoutingLSA<IpManager>::LSA_SPF_CANDIDATE);
                //
                // Push this new vertex onto the priority queue (ordered by distance from the
                // root node).
                //
                candidate.Push(w);
                NS_LOG_LOGIC("Pushing " << w->GetVertexId()
                                        << ", parent vertexId: " << v->GetVertexId()
                                        << ", distance: " << w->GetDistanceFromRoot());
            }
            else
            {
                NS_ASSERT_MSG(0, "SPFNexthopCalculation never return false, but it does now!");
            }
        }
        else if (w_lsa->GetStatus() == GlobalRoutingLSA<IpManager>::LSA_SPF_CANDIDATE)
        {
            //
            // We have already considered the link represented by <w>.  What wse have to
            // do now is to decide if this new router represents a route with a shorter
            // distance metric.
            //
            // So, locate the vertex in the candidate queue and take a look at the
            // distance.
 
            /* (quagga-0.98.6) W is already on the candidate list; call it cw.
             * Compare the previously calculated cost (cw->distance)
             * with the cost we just determined (w->distance) to see
             * if we've found a shorter path.
             */
            SPFVertex<T>* cw;
            cw = candidate.Find(w_lsa->GetLinkStateId());
            if (cw->GetDistanceFromRoot() < distance)
            {
                //
                // This is not a shorter path, so don't do anything.
                //
                continue;
            }
            else if (cw->GetDistanceFromRoot() == distance)
            {
                //
                // This path is one with an equal cost.
                //
                NS_LOG_LOGIC("Equal cost multiple paths found.");
 
                // At this point, there are two instances 'w' and 'cw' of the
                // same vertex, the vertex that is currently being considered
                // for adding into the shortest path tree. 'w' is the instance
                // as seen from the root via vertex 'v', and 'cw' is the instance
                // as seen from the root via some other vertices other than 'v'.
                // These two instances are being merged in the following code.
                // In particular, the parent nodes, the next hops, and the root's
                // output interfaces of the two instances are being merged.
                //
                // Note that this is functionally equivalent to calling
                // ospf_nexthop_merge (cw->nexthop, w->nexthop) in quagga-0.98.6
                // (ospf_spf.c::859), although the detail implementation
                // is very different from quagga (blame ns3::GlobalRouteManagerImpl)
 
                // prepare vertex w
                w = new SPFVertex<T>(w_lsa);
                SPFNexthopCalculation(v, w, l, distance);
                cw->MergeRootExitDirections(w);
                cw->MergeParent(w);
                // SPFVertexAddParent (w) is necessary as the destructor of
                // SPFVertex checks if the vertex and its parent is linked
                // bidirectionally
                SPFVertexAddParent(w);
                delete w;
            }
            else // cw->GetDistanceFromRoot () > w->GetDistanceFromRoot ()
            {
                //
                // this path represents a new, lower-cost path to <w> (the vertex we found in
                // the current link record of the link state advertisement of the current root
                // (vertex <v>)
                //
                // N.B. the nexthop_calculation is conditional, if it finds a valid nexthop
                // it will call spf_add_parents, which will flush the old parents
                //
                if (SPFNexthopCalculation(v, cw, l, distance))
                {
                    //
                    // If we've changed the cost to get to the vertex represented by <w>, we
                    // must reorder the priority queue keyed to that cost.
                    //
                    candidate.Reorder();
                }
            }
        }
    }
}
 
//
// This method is derived from quagga ospf_nexthop_calculation() 16.1.1.
//
// Calculate nexthop from root through V (parent) to vertex W (destination)
// with given distance from root->W.
//
// As appropriate, set w's parent, distance, and nexthop information
//
// For now, this is greatly simplified from the quagga code
//
 
template <typename T>
int
GlobalRouteManagerImpl<T>::SPFNexthopCalculation(SPFVertex<T>* v,
                                                 SPFVertex<T>* w,
                                                 GlobalRoutingLinkRecord<IpManager>* l,
                                                 uint32_t distance)
{
    NS_LOG_FUNCTION(this << v << w << l << distance);
    //
    // If w is a NetworkVertex, l should be null
    /*
      if (w->GetVertexType () == SPFVertex::VertexNetwork && l)
        {
            NS_ASSERT_MSG (0, "Error:  SPFNexthopCalculation parameter problem");
        }
    */
 
    //
    // The vertex m_spfroot is a distinguished vertex representing the node at
    // the root of the calculations.  That is, it is the node for which we are
    // calculating the routes.
    //
    // There are two distinct cases for calculating the next hop information.
    // First, if we're considering a hop from the root to an "adjacent" network
    // (one that is on the other side of a point-to-point link connected to the
    // root), then we need to store the information needed to forward down that
    // link.  The second case is if the network is not directly adjacent.  In that
    // case we need to use the forwarding information from the vertex on the path
    // to the destination that is directly adjacent [node 1] in both cases of the
    // diagram below.
    //
    // (1) [root] -> [point-to-point] -> [node 1]
    // (2) [root] -> [point-to-point] -> [node 1] -> [point-to-point] -> [node 2]
    //
    // We call the propagation of next hop information down vertices of a path
    // "inheriting" the next hop information.
    //
    // The point-to-point link information is only useful in this calculation when
    // we are examining the root node.
    //
    if (v == m_spfroot)
    {
        //
        // In this case <v> is the root node, which means it is the starting point
        // for the packets forwarded by that node.  This also means that the next hop
        // address of packets headed for some arbitrary off-network destination must
        // be the destination at the other end of one of the links off of the root
        // node if this root node is a router.  We then need to see if this node <w>
        // is a router.
        //
        if (w->GetVertexType() == SPFVertex<T>::VertexRouter)
        {
            //
            // In the case of point-to-point links, the link data field (m_linkData) of a
            // Global Router Link Record contains the local IP address.  If we look at the
            // link record describing the link from the perspective of <w> (the remote
            // node from the viewpoint of <v>) back to the root node, we can discover the
            // IP address of the router to which <v> is adjacent.  This is a distinguished
            // address -- the next hop address to get from <v> to <w> and all networks
            // accessed through that path.
            //
            // SPFGetNextLink () is a little odd.  used in this way it is just going to
            // return the link record describing the link from <w> to <v>.  Think of it as
            // SPFGetLink.
            //
            NS_ASSERT(l);
            GlobalRoutingLinkRecord<IpManager>* linkRemote = nullptr;
            linkRemote = SPFGetNextLink(w, v, linkRemote);
            //
            // At this point, <l> is the Global Router Link Record describing the point-
            // to point link from <v> to <w> from the perspective of <v>; and <linkRemote>
            // is the Global Router Link Record describing that same link from the
            // perspective of <w> (back to <v>).  Now we can just copy the next hop
            // address from the m_linkData member variable.
            //
            // The next hop member variable we put in <w> has the sense "in order to get
            // from the root node to the host represented by vertex <w>, you have to send
            // the packet to the next hop address specified in w->m_nextHop.
            //
            IpAddress nextHop;
            if constexpr (IsIpv4)
            {
                nextHop = linkRemote->GetLinkData();
            }
            else
            {
                nextHop = linkRemote->GetLinkLocData();
            }
            //
            // Now find the outgoing interface corresponding to the point to point link
            // from the perspective of <v> -- remember that <l> is the link "from"
            // <v> "to" <w>.
            //
            uint32_t outIf;
            if constexpr (IsIpv4)
            {
                outIf = FindOutgoingInterfaceId(l->GetLinkData());
            }
            else
            {
                outIf = FindOutgoingInterfaceId(l->GetLinkLocData());
            }
 
            w->SetRootExitDirection(nextHop, outIf);
            w->SetDistanceFromRoot(distance);
            w->SetParent(v);
            NS_LOG_LOGIC("Next hop from " << v->GetVertexId() << " to " << w->GetVertexId()
                                          << " goes through next hop " << nextHop
                                          << " via outgoing interface " << outIf
                                          << " with distance " << distance);
        }
        else
        {
            NS_ASSERT(w->GetVertexType() == SPFVertex<T>::VertexNetwork);
            // W is a directly connected network; no next hop is required
            GlobalRoutingLSA<IpManager>* w_lsa = w->GetLSA();
            NS_ASSERT(w_lsa->GetLSType() == GlobalRoutingLSA<IpManager>::NetworkLSA);
            // Find outgoing interface ID for this network
            uint32_t outIf =
                FindOutgoingInterfaceId(w_lsa->GetLinkStateId(), w_lsa->GetNetworkLSANetworkMask());
            // Set the next hop to 0.0.0.0 meaning "not exist"
            IpAddress nextHop = IpAddress::GetZero();
            w->SetRootExitDirection(nextHop, outIf);
            w->SetDistanceFromRoot(distance);
            w->SetParent(v);
            NS_LOG_LOGIC("Next hop from " << v->GetVertexId() << " to network " << w->GetVertexId()
                                          << " via outgoing interface " << outIf
                                          << " with distance " << distance);
            return 1;
        }
    }
    else if (v->GetVertexType() == SPFVertex<T>::VertexNetwork)
    {
        // See if any of v's parents are the root
        if (v->GetParent() == m_spfroot)
        {
            // 16.1.1 para 5. ...the parent vertex is a network that
            // directly connects the calculating router to the destination
            // router.  The list of next hops is then determined by
            // examining the destination's router-LSA...
            NS_ASSERT(w->GetVertexType() == SPFVertex<T>::VertexRouter);
            GlobalRoutingLinkRecord<IpManager>* linkRemote = nullptr;
            while ((linkRemote = SPFGetNextLink(w, v, linkRemote)))
            {
                /* ...For each link in the router-LSA that points back to the
                 * parent network, the link's Link Data field provides the IP
                 * address of a next hop router.  The outgoing interface to
                 * use can then be derived from the next hop IP address (or
                 * it can be inherited from the parent network).
                 */
                IpAddress nextHop;
                if constexpr (IsIpv4)
                {
                    nextHop = linkRemote->GetLinkData();
                }
                else
                {
                    nextHop = linkRemote->GetLinkLocData();
                }
                uint32_t outIf = v->GetRootExitDirection().second;
                w->SetRootExitDirection(nextHop, outIf);
                NS_LOG_LOGIC("Next hop from " << v->GetVertexId() << " to " << w->GetVertexId()
                                              << " goes through next hop " << nextHop
                                              << " via outgoing interface " << outIf);
            }
        }
        else
        {
            w->InheritAllRootExitDirections(v);
        }
    }
    else
    {
        //
        // If we're calculating the next hop information from a node (v) that is
        // *not* the root, then we need to "inherit" the information needed to
        // forward the packet from the vertex closer to the root.  That is, we'll
        // still send packets to the next hop address of the router adjacent to the
        // root on the path toward <w>.
        //
        // Above, when we were considering the root node, we calculated the next hop
        // address and outgoing interface required to get off of the root network.
        // At this point, we are further away from the root network along one of the
        // (shortest) paths.  So the next hop and outgoing interface remain the same
        // (are inherited).
        //
        w->InheritAllRootExitDirections(v);
    }
    //
    // In all cases, we need valid values for the distance metric and a parent.
    //
    w->SetDistanceFromRoot(distance);
    w->SetParent(v);
 
    return 1;
}
 
//
// This method is derived from quagga ospf_get_next_link ()
//
// First search the Global Router Link Records of vertex <v> for one
// representing a point-to point link to vertex <w>.
//
// What is done depends on prev_link.  Contrary to appearances, prev_link just
// acts as a flag here.  If prev_link is NULL, we return the first Global
// Router Link Record we find that describes a point-to-point link from <v>
// to <w>.  If prev_link is not NULL, we return a Global Router Link Record
// representing a possible *second* link from <v> to <w>.
//
 
template <typename T>
 
GlobalRoutingLinkRecord<typename GlobalRouteManagerImpl<T>::IpManager>*
GlobalRouteManagerImpl<T>::SPFGetNextLink(SPFVertex<T>* v,
                                          SPFVertex<T>* w,
                                          GlobalRoutingLinkRecord<IpManager>* prev_link)
{
    NS_LOG_FUNCTION(this << v << w << prev_link);
 
    bool skip = true;
    bool found_prev_link = false;
    GlobalRoutingLinkRecord<IpManager>* l;
    //
    // If prev_link is 0, we are really looking for the first link, not the next
    // link.
    //
    if (prev_link == nullptr)
    {
        skip = false;
        found_prev_link = true;
    }
    //
    // Iterate through the Global Router Link Records advertised by the vertex
    // <v> looking for records representing the point-to-point links off of this
    // vertex.
    //
    for (uint32_t i = 0; i < v->GetLSA()->GetNLinkRecords(); ++i)
    {
        l = v->GetLSA()->GetLinkRecord(i);
        //
        // The link ID of a link record representing a point-to-point link is set to
        // the router ID of the neighboring router -- the router to which the link
        // connects from the perspective of <v> in this case.  The vertex ID is also
        // set to the router ID (using the link state advertisement of a router node).
        // We're just checking to see if the link <l> is actually the link from <v> to
        // <w>.
        //
        if (l->GetLinkId() == w->GetVertexId())
        {
            if (!found_prev_link)
            {
                NS_LOG_LOGIC("Skipping links before prev_link found");
                found_prev_link = true;
                continue;
            }
 
            NS_LOG_LOGIC("Found matching link l:  linkId = " << l->GetLinkId()
                                                             << " linkData = " << l->GetLinkData());
            //
            // If skip is false, don't (not too surprisingly) skip the link found -- it's
            // the one we're interested in.  That's either because we didn't pass in a
            // previous link, and we're interested in the first one, or because we've
            // skipped a previous link and moved forward to the next (which is then the
            // one we want).
            //
            if (!skip)
            {
                NS_LOG_LOGIC("Returning the found link");
                return l;
            }
            else
            {
                //
                // Skip is true and we've found a link from <v> to <w>.  We want the next one.
                // Setting skip to false gets us the next point-to-point global router link
                // record in the LSA from <v>.
                //
                NS_LOG_LOGIC("Skipping the found link");
                skip = false;
                continue;
            }
        }
    }
    return nullptr;
}
 
//
// Used for unit tests.
//
 
template <typename T>
void
GlobalRouteManagerImpl<T>::DebugSPFCalculate(IpAddress root)
{
    NS_LOG_FUNCTION(this << root);
    SPFCalculate(root);
}
 
//
// Used to test if a node is a stub, from an OSPF sense.
// If there is only one link of type 1 or 2, then a default route
// can safely be added to the next-hop router and SPF does not need
// to be run
//
 
template <typename T>
bool
GlobalRouteManagerImpl<T>::CheckForStubNode(IpAddress root)
{
    NS_LOG_FUNCTION(this << root);
    GlobalRoutingLSA<IpManager>* rlsa = m_lsdb->GetLSA(root);
    IpAddress myRouterId = rlsa->GetLinkStateId();
    int transits = 0;
    GlobalRoutingLinkRecord<IpManager>* transitLink = nullptr;
    for (uint32_t i = 0; i < rlsa->GetNLinkRecords(); i++)
    {
        GlobalRoutingLinkRecord<IpManager>* l = rlsa->GetLinkRecord(i);
        if (l->GetLinkType() == GlobalRoutingLinkRecord<IpManager>::TransitNetwork ||
            l->GetLinkType() == GlobalRoutingLinkRecord<IpManager>::PointToPoint)
        {
            transits++;
            transitLink = l;
        }
    }
    if (transits == 0)
    {
        // This router is not connected to any router.  Probably, global
        // routing should not be called for this node, but we can just raise
        // a warning here and return true.
        NS_LOG_WARN("all nodes should have at least one transit link:" << root);
        return true;
    }
    if (transits == 1)
    {
        if (transitLink->GetLinkType() == GlobalRoutingLinkRecord<IpManager>::TransitNetwork)
        {
            // Install default route to next hop router
            // What is the next hop?  We need to check all neighbors on the link.
            // If there is a single router that has two transit links, then
            // that is the default next hop.  If there are more than one
            // routers on link with multiple transit links, return false.
            // Not yet implemented, so simply return false
            NS_LOG_LOGIC("TBD: Would have inserted default for transit");
            return false;
        }
        else if (transitLink->GetLinkType() == GlobalRoutingLinkRecord<IpManager>::PointToPoint)
        {
            // Install default route to next hop
            // The link record LinkID is the router ID of the peer.
            // The Link Data is the local IP interface address
            GlobalRoutingLSA<IpManager>* w_lsa = m_lsdb->GetLSA(transitLink->GetLinkId());
            uint32_t nLinkRecords = w_lsa->GetNLinkRecords();
            for (uint32_t j = 0; j < nLinkRecords; ++j)
            {
                //
                // We are only concerned about point-to-point links
                //
                GlobalRoutingLinkRecord<IpManager>* lr = w_lsa->GetLinkRecord(j);
                if (lr->GetLinkType() != GlobalRoutingLinkRecord<IpManager>::PointToPoint)
                {
                    continue;
                }
                // Find the link record that corresponds to our routerId
                if (lr->GetLinkId() == myRouterId)
                {
                    // Next hop is stored in the LinkID field of lr
                    Ptr<GlobalRouter<IpManager>> router =
                        rlsa->GetNode()->template GetObject<GlobalRouter<IpManager>>();
                    NS_ASSERT(router);
                    Ptr<GlobalRouting<IpRoutingProtocol>> gr = router->GetRoutingProtocol();
                    NS_ASSERT(gr);
                    if constexpr (IsIpv4)
                    {
                        gr->AddNetworkRouteTo(IpAddress::GetZero(),
                                              IpMaskOrPrefix::GetZero(),
                                              lr->GetLinkData(),
                                              FindOutgoingInterfaceId(transitLink->GetLinkData()));
                        NS_LOG_LOGIC("Inserting default route for node "
                                     << myRouterId << " to next hop " << lr->GetLinkData()
                                     << " via interface "
                                     << FindOutgoingInterfaceId(transitLink->GetLinkData()));
                    }
                    else
                    {
                        gr->AddNetworkRouteTo(
                            IpAddress::GetZero(),
                            IpMaskOrPrefix::GetZero(),
                            lr->GetLinkLocData(),
                            FindOutgoingInterfaceId(transitLink->GetLinkLocData()));
                        NS_LOG_LOGIC("Inserting default route for node "
                                     << myRouterId << " to next hop " << lr->GetLinkLocData()
                                     << " via interface "
                                     << FindOutgoingInterfaceId(transitLink->GetLinkLocData()));
                    }
                    return true;
                }
            }
        }
    }
    return false;
}
 
// quagga ospf_spf_calculate
 
template <typename T>
void
GlobalRouteManagerImpl<T>::SPFCalculate(IpAddress root)
{
    NS_LOG_FUNCTION(this << root);
 
    SPFVertex<T>* v;
    //
    // Initialize the Link State Database.
    //
    m_lsdb->Initialize();
    //
    // The candidate queue is a priority queue of SPFVertex objects, with the top
    // of the queue being the closest vertex in terms of distance from the root
    // of the tree.  Initially, this queue is empty.
    //
    CandidateQueue<T> candidate;
    NS_ASSERT(candidate.Size() == 0);
    //
    // Initialize the shortest-path tree to only contain the router doing the
    // calculation.  Each router (and corresponding network) is a vertex in the
    // shortest path first (SPF) tree.
    //
    v = new SPFVertex<T>(m_lsdb->GetLSA(root));
    //
    // This vertex is the root of the SPF tree and it is distance 0 from the root.
    // We also mark this vertex as being in the SPF tree.
    //
    m_spfroot = v;
    v->SetDistanceFromRoot(0);
    v->GetLSA()->SetStatus(GlobalRoutingLSA<IpManager>::LSA_SPF_IN_SPFTREE);
    NS_LOG_LOGIC("Starting SPFCalculate for node " << root);
 
    //
    // Optimize SPF calculation, for ns-3.
    // We do not need to calculate SPF for every node in the network if this
    // node has only one interface through which another router can be
    // reached.  Instead, short-circuit this computation and just install
    // a default route in the CheckForStubNode() method.
    //
    if (NodeList::GetNNodes() > 0 && CheckForStubNode(root))
    {
        NS_LOG_LOGIC("SPFCalculate truncated for stub node " << root);
        delete m_spfroot;
        return;
    }
 
    for (;;)
    {
        //
        // The operations we need to do are given in the OSPF RFC which we reference
        // as we go along.
        //
        // RFC2328 16.1. (2).
        //
        // We examine the Global Router Link Records in the Link State
        // Advertisements of the current vertex.  If there are any point-to-point
        // links to unexplored adjacent vertices we add them to the tree and update
        // the distance and next hop information on how to get there.  We also add
        // the new vertices to the candidate queue (the priority queue ordered by
        // shortest path).  If the new vertices represent shorter paths, we use them
        // and update the path cost.
        //
        SPFNext(v, candidate);
        //
        // RFC2328 16.1. (3).
        //
        // If at this step the candidate list is empty, the shortest-path tree (of
        // transit vertices) has been completely built and this stage of the
        // procedure terminates.
        //
        if (candidate.Size() == 0)
        {
            break;
        }
        //
        // Choose the vertex belonging to the candidate list that is closest to the
        // root, and add it to the shortest-path tree (removing it from the candidate
        // list in the process).
        //
        // Recall that in the previous step, we created SPFVertex structures for each
        // of the routers found in the Global Router Link Records and added tehm to
        // the candidate list.
        //
        NS_LOG_LOGIC(candidate);
        v = candidate.Pop();
        NS_LOG_LOGIC("Popped vertex " << v->GetVertexId());
        //
        // Update the status field of the vertex to indicate that it is in the SPF
        // tree.
        //
        v->GetLSA()->SetStatus(GlobalRoutingLSA<IpManager>::LSA_SPF_IN_SPFTREE);
        //
        // The current vertex has a parent pointer.  By calling this rather oddly
        // named method (blame quagga) we add the current vertex to the list of
        // children of that parent vertex.  In the next hop calculation called during
        // SPFNext, the parent pointer was set but the vertex has been orphaned up
        // to now.
        //
        SPFVertexAddParent(v);
        //
        // Note that when there is a choice of vertices closest to the root, network
        // vertices must be chosen before router vertices in order to necessarily
        // find all equal-cost paths.
        //
        // RFC2328 16.1. (4).
        //
        // This is the method that actually adds the routes.  It'll walk the list
        // of nodes in the system, looking for the node corresponding to the router
        // ID of the root of the tree -- that is the router we're building the routes
        // for.  It looks for the Ipv4 interface of that node and remembers it.  So
        // we are only actually adding routes to that one node at the root of the SPF
        // tree.
        //
        // We're going to pop of a pointer to every vertex in the tree except the
        // root in order of distance from the root.  For each of the vertices, we call
        // SPFIntraAddRouter ().  Down in SPFIntraAddRouter, we look at all of the
        // point-to-point Global Router Link Records (the links to nodes adjacent to
        // the node represented by the vertex).  We add a route to the IP address
        // specified by the m_linkData field of each of those link records.  This will
        // be the *local* IP address associated with the interface attached to the
        // link.  We use the outbound interface and next hop information present in
        // the vertex <v> which have possibly been inherited from the root.
        //
        // To summarize, we're going to look at the node represented by <v> and loop
        // through its point-to-point links, adding a *host* route to the local IP
        // address (at the <v> side) for each of those links.
        //
        if (v->GetVertexType() == SPFVertex<T>::VertexRouter)
        {
            SPFIntraAddRouter(v);
        }
        else if (v->GetVertexType() == SPFVertex<T>::VertexNetwork)
        {
            SPFIntraAddTransit(v);
        }
        else
        {
            NS_ASSERT_MSG(0, "illegal SPFVertex type");
        }
        //
        // RFC2328 16.1. (5).
        //
        // Iterate the algorithm by returning to Step 2 until there are no more
        // candidate vertices.
    }
 
    // Second stage of SPF calculation procedure
    SPFProcessStubs(m_spfroot);
    for (uint32_t i = 0; i < m_lsdb->GetNumExtLSAs(); i++)
    {
        m_spfroot->ClearVertexProcessed();
        GlobalRoutingLSA<IpManager>* extlsa = m_lsdb->GetExtLSA(i);
        NS_LOG_LOGIC("Processing External LSA with id " << extlsa->GetLinkStateId());
        ProcessASExternals(m_spfroot, extlsa);
    }
 
    //
    // We're all done setting the routing information for the node at the root of
    // the SPF tree.  Delete all of the vertices and corresponding resources.  Go
    // possibly do it again for the next router.
    //
    delete m_spfroot;
    m_spfroot = nullptr;
}
 
template <typename T>
void
GlobalRouteManagerImpl<T>::ProcessASExternals(SPFVertex<T>* v, GlobalRoutingLSA<IpManager>* extlsa)
{
    NS_LOG_FUNCTION(this << v << extlsa);
    NS_LOG_LOGIC("Processing external for destination "
                 << extlsa->GetLinkStateId() << ", for router " << v->GetVertexId()
                 << ", advertised by " << extlsa->GetAdvertisingRouter());
    if (v->GetVertexType() == SPFVertex<T>::VertexRouter)
    {
        GlobalRoutingLSA<IpManager>* rlsa = v->GetLSA();
        NS_LOG_LOGIC("Processing router LSA with id " << rlsa->GetLinkStateId());
        if ((rlsa->GetLinkStateId()) == (extlsa->GetAdvertisingRouter()))
        {
            NS_LOG_LOGIC("Found advertising router to destination");
            SPFAddASExternal(extlsa, v);
        }
    }
    for (uint32_t i = 0; i < v->GetNChildren(); i++)
    {
        if (!v->GetChild(i)->IsVertexProcessed())
        {
            NS_LOG_LOGIC("Vertex's child " << i << " not yet processed, processing...");
            ProcessASExternals(v->GetChild(i), extlsa);
            v->GetChild(i)->SetVertexProcessed(true);
        }
    }
}
 
//
// Adding external routes to routing table - modeled after
// SPFAddIntraAddStub()
//
 
template <typename T>
void
GlobalRouteManagerImpl<T>::SPFAddASExternal(GlobalRoutingLSA<IpManager>* extlsa, SPFVertex<T>* v)
{
    NS_LOG_FUNCTION(this << extlsa << v);
 
    NS_ASSERT_MSG(m_spfroot, "GlobalRouteManagerImpl::SPFAddASExternal (): Root pointer not set");
    // Two cases to consider: We are advertising the external ourselves
    // => No need to add anything
    // OR find best path to the advertising router
    if (v->GetVertexId() == m_spfroot->GetVertexId())
    {
        NS_LOG_LOGIC("External is on local host: " << v->GetVertexId() << "; returning");
        return;
    }
    NS_LOG_LOGIC("External is on remote host: " << extlsa->GetAdvertisingRouter()
                                                << "; installing");
 
    IpAddress routerId = m_spfroot->GetVertexId();
 
    NS_LOG_LOGIC("Vertex ID = " << routerId);
    //
    // The node we need to add routes to is the node corresponding to the root vertex.
    // This is the node for which we are building the routing table.
    //
    Ptr<Node> node = m_spfroot->GetNode();
 
    if (!node)
    {
        NS_FATAL_ERROR("SPFAddASExternal():Can't find root node " << routerId);
        return;
    }
    //
    // The router ID is accessible through the GlobalRouter interface, so we need
    // to QI for that interface.  If there's no GlobalRouter interface, the node
    // in question cannot be the router we want, so we continue.
    //
    Ptr<GlobalRouter<T>> router = node->GetObject<GlobalRouter<T>>();
    NS_ASSERT_MSG(router, "No GlobalRouter interface on SPF root node " << node->GetId());
    //
    // If the router ID of the current node is equal to the router ID of the
    // root of the SPF tree, then this node is the one for which we need to
    // write the routing tables.
    //
    if (router->GetRouterId() == routerId)
    {
        NS_LOG_LOGIC("Setting routes for node " << node->GetId());
        //
        // Routing information is updated using the Ipv4 interface.  We need to QI
        // for that interface.  If the node is acting as an IP version 4 router, it
        // should absolutely have an Ipv4 interface.
        //
        Ptr<Ip> ipv4 = node->GetObject<Ip>();
        NS_ASSERT_MSG(ipv4,
                      "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
                      "QI for <Ipv4> interface failed");
        //
        // Get the Global Router Link State Advertisement from the vertex we're
        // adding the routes to.  The LSA will have a number of attached Global Router
        // Link Records corresponding to links off of that vertex / node.  We're going
        // to be interested in the records corresponding to point-to-point links.
        //
        NS_ASSERT_MSG(v->GetLSA(),
                      "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
                      "Expected valid LSA in SPFVertex* v");
        IpMaskOrPrefix tempmask = extlsa->GetNetworkLSANetworkMask();
        IpAddress tempip = extlsa->GetLinkStateId();
 
        if constexpr (IsIpv4)
        {
            tempip = tempip.CombineMask(tempmask);
        }
        else
        {
            tempip = tempip.CombinePrefix(tempmask);
        }
 
        //
        // Here's why we did all of that work.  We're going to add a host route to the
        // host address found in the m_linkData field of the point-to-point link
        // record.  In the case of a point-to-point link, this is the local IP address
        // of the node connected to the link.  Each of these point-to-point links
        // will correspond to a local interface that has an IP address to which
        // the node at the root of the SPF tree can send packets.  The vertex <v>
        // (corresponding to the node that has these links and interfaces) has
        // an m_nextHop address precalculated for us that is the address to which the
        // root node should send packets to be forwarded to these IP addresses.
        // Similarly, the vertex <v> has an m_rootOif (outbound interface index) to
        // which the packets should be send for forwarding.
        //
        Ptr<GlobalRouter<IpManager>> router = node->GetObject<GlobalRouter<IpManager>>();
 
        NS_ASSERT_MSG(router, "No GlobalRouter interface on node " << node->GetId());
 
        Ptr<GlobalRouting<IpRoutingProtocol>> gr = router->GetRoutingProtocol();
        NS_ASSERT(gr);
        // walk through all next-hop-IPs and out-going-interfaces for reaching
        // the stub network gateway 'v' from the root node
        for (uint32_t i = 0; i < v->GetNRootExitDirections(); i++)
        {
            typename SPFVertex<T>::NodeExit_t exit = v->GetRootExitDirection(i);
            IpAddress nextHop = exit.first;
            int32_t outIf = exit.second;
            if (outIf >= 0)
            {
                gr->AddASExternalRouteTo(tempip, tempmask, nextHop, outIf);
                NS_LOG_LOGIC("(Route " << i << ") Node " << node->GetId()
                                       << " add external network route to " << tempip
                                       << " using next hop " << nextHop << " via interface "
                                       << outIf);
            }
            else
            {
                NS_LOG_LOGIC("(Route " << i << ") Node " << node->GetId()
                                       << " NOT able to add network route to " << tempip
                                       << " using next hop " << nextHop
                                       << " since outgoing interface id is negative");
            }
        }
        return;
    }
    // This should never happen. The RouterId and vertexId should match
    NS_FATAL_ERROR("SPFIntraAddRouter(): routerId and vertex ID do not match");
}
 
// Processing logic from RFC 2328, page 166 and quagga ospf_spf_process_stubs ()
// stub link records will exist for point-to-point interfaces and for
// broadcast interfaces for which no neighboring router can be found
 
template <typename T>
void
GlobalRouteManagerImpl<T>::SPFProcessStubs(SPFVertex<T>* v)
{
    NS_LOG_FUNCTION(this << v);
    NS_LOG_LOGIC("Processing stubs for " << v->GetVertexId());
    if (v->GetVertexType() == SPFVertex<T>::VertexRouter)
    {
        GlobalRoutingLSA<IpManager>* rlsa = v->GetLSA();
        NS_LOG_LOGIC("Processing router LSA with id " << rlsa->GetLinkStateId());
        for (uint32_t i = 0; i < rlsa->GetNLinkRecords(); i++)
        {
            NS_LOG_LOGIC("Examining link " << i << " of " << v->GetVertexId() << "'s "
                                           << v->GetLSA()->GetNLinkRecords() << " link records");
            GlobalRoutingLinkRecord<IpManager>* l = v->GetLSA()->GetLinkRecord(i);
            if (l->GetLinkType() == GlobalRoutingLinkRecord<IpManager>::StubNetwork)
            {
                NS_LOG_LOGIC("Found a Stub record to " << l->GetLinkId());
                SPFIntraAddStub(l, v);
                continue;
            }
        }
    }
    for (uint32_t i = 0; i < v->GetNChildren(); i++)
    {
        if (!v->GetChild(i)->IsVertexProcessed())
        {
            SPFProcessStubs(v->GetChild(i));
            v->GetChild(i)->SetVertexProcessed(true);
        }
    }
}
 
// RFC2328 16.1. second stage.
 
template <typename T>
void
GlobalRouteManagerImpl<T>::SPFIntraAddStub(GlobalRoutingLinkRecord<IpManager>* l, SPFVertex<T>* v)
{
    NS_LOG_FUNCTION(this << l << v);
 
    NS_ASSERT_MSG(m_spfroot, "GlobalRouteManagerImpl::SPFIntraAddStub (): Root pointer not set");
 
    // XXX simplified logic for the moment.  There are two cases to consider:
    // 1) the stub network is on this router; do nothing for now
    //    (already handled above)
    // 2) the stub network is on a remote router, so I should use the
    // same next hop that I use to get to vertex v
    if (v->GetVertexId() == m_spfroot->GetVertexId())
    {
        NS_LOG_LOGIC("Stub is on local host: " << v->GetVertexId() << "; returning");
        return;
    }
    NS_LOG_LOGIC("Stub is on remote host: " << v->GetVertexId() << "; installing");
    //
    // The root of the Shortest Path First tree is the router to which we are
    // going to write the actual routing table entries.  The vertex corresponding
    // to this router has a vertex ID which is the router ID of that node.  We're
    // going to use this ID to discover which node it is that we're actually going
    // to update.
    //
    IpAddress routerId = m_spfroot->GetVertexId();
 
    NS_LOG_LOGIC("Vertex ID = " << routerId);
    //
    // The node we need to add routes to is the node corresponding to the root vertex.
    // This is the node for which we are building the routing table.
    //
    Ptr<Node> node = m_spfroot->GetNode();
    if (!node)
    {
        NS_LOG_ERROR("SPFIntraAddStub():Can't find root node " << routerId);
        return;
    }
    //
    // The router ID is accessible through the GlobalRouter interface, so we need
    // to QI for that interface.  If there's no GlobalRouter interface, the node
    // in question cannot be the router we want, so we continue.
    //
    Ptr<GlobalRouter<T>> router = node->GetObject<GlobalRouter<T>>();
    NS_ASSERT_MSG(router, "No GlobalRouter interface on node " << node->GetId());
    //
    // If the router ID of the current node is equal to the router ID of the
    // root of the SPF tree, then this node is the one for which we need to
    // write the routing tables.
    //
    if (routerId == router->GetRouterId())
    {
        NS_LOG_LOGIC("Setting routes for node " << node->GetId());
        //
        // Routing information is updated using the Ipv4 interface.  We need to QI
        // for that interface.  If the node is acting as an IP version 4 router, it
        // should absolutely have an Ipv4 interface.
        //
        Ptr<Ip> ip = node->GetObject<Ip>();
        NS_ASSERT_MSG(ip,
                      "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
                      "QI for <Ipv4> interface failed");
        //
        // Get the Global Router Link State Advertisement from the vertex we're
        // adding the routes to.  The LSA will have a number of attached Global Router
        // Link Records corresponding to links off of that vertex / node.  We're going
        // to be interested in the records corresponding to point-to-point links.
        //
        NS_ASSERT_MSG(v->GetLSA(),
                      "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
                      "Expected valid LSA in SPFVertex* v");
        IpMaskOrPrefix tempmask;
        if constexpr (IsIpv4)
        {
            tempmask = Ipv4Mask(l->GetLinkData().Get());
        }
        else
        {
            // to get the Prefix from the Ipv6Address
            uint8_t buf[16];
            l->GetLinkData().GetBytes(buf);
            tempmask = Ipv6Prefix(buf);
        }
 
        IpAddress tempip = l->GetLinkId();
        if constexpr (IsIpv4)
        {
            tempip = tempip.CombineMask(tempmask);
        }
        else
        {
            tempip = tempip.CombinePrefix(tempmask);
        }
        //
        // Here's why we did all of that work.  We're going to add a host route to the
        // host address found in the m_linkData field of the point-to-point link
        // record.  In the case of a point-to-point link, this is the local IP address
        // of the node connected to the link.  Each of these point-to-point links
        // will correspond to a local interface that has an IP address to which
        // the node at the root of the SPF tree can send packets.  The vertex <v>
        // (corresponding to the node that has these links and interfaces) has
        // an m_nextHop address precalculated for us that is the address to which the
        // root node should send packets to be forwarded to these IP addresses.
        // Similarly, the vertex <v> has an m_rootOif (outbound interface index) to
        // which the packets should be send for forwarding.
        //
 
        Ptr<GlobalRouter<T>> router = node->GetObject<GlobalRouter<T>>();
 
        Ptr<GlobalRouting<IpRoutingProtocol>> gr = router->GetRoutingProtocol();
        NS_ASSERT(gr);
        // walk through all next-hop-IPs and out-going-interfaces for reaching
        // the stub network gateway 'v' from the root node
        for (uint32_t i = 0; i < v->GetNRootExitDirections(); i++)
        {
            typename SPFVertex<T>::NodeExit_t exit = v->GetRootExitDirection(i);
            IpAddress nextHop = exit.first;
            int32_t outIf = exit.second;
            if (outIf >= 0)
            {
                gr->AddNetworkRouteTo(tempip, tempmask, nextHop, outIf);
                NS_LOG_LOGIC("(Route " << i << ") Node " << node->GetId()
                                       << " add network route to " << tempip << " using next hop "
                                       << nextHop << " via interface " << outIf);
            }
            else
            {
                NS_LOG_LOGIC("(Route " << i << ") Node " << node->GetId()
                                       << " NOT able to add network route to " << tempip
                                       << " using next hop " << nextHop
                                       << " since outgoing interface id is negative");
            }
        }
        return;
    }
    // This should never happen. The RouterId and vertex Id should match
    NS_LOG_ERROR("SPFIntraAddStub(): routerId and vertex ID do not match");
}
 
//
// Return the interface number corresponding to a given IP address and mask
// This is a wrapper around GetInterfaceForPrefix(), but we first
// have to find the right node pointer to pass to that function.
// If no such interface is found, return -1 (note:  unit test framework
// for routing assumes -1 to be a legal return value)
//
 
template <typename T>
int32_t
GlobalRouteManagerImpl<T>::FindOutgoingInterfaceId(IpAddress a, IpMaskOrPrefix amask)
{
    NS_LOG_FUNCTION(this << a << amask);
    //
    // We have an IP address <a> and a vertex ID of the root of the SPF tree.
    // The question is what interface index does this address correspond to.
    // The answer is a little complicated since we have to find a pointer to
    // the node corresponding to the vertex ID, find the Ipv4 interface on that
    // node in order to iterate the interfaces and find the one corresponding to
    // the address in question.
    //
    IpAddress routerId = m_spfroot->GetVertexId();
    //
    // The node we need to add routes to is the node corresponding to the root vertex.
    // This is the node for which we are building the routing table.
    //
    Ptr<Node> node = m_spfroot->GetNode();
    if (!node)
    {
        //
        // Couldn't find it.
        //
        NS_LOG_LOGIC("FindOutgoingInterfaceId():Can't find root node " << routerId);
        return -1;
    }
 
    Ptr<GlobalRouter<IpManager>> rtr = node->GetObject<GlobalRouter<IpManager>>();
    NS_ASSERT_MSG(rtr, "No GlobalRouter interface on node " << node->GetId());
    //
    // If the node doesn't have a GlobalRouter interface it can't be the one
    // we're interested in.
    //
 
    if (rtr->GetRouterId() == routerId)
    {
        //
        // This is the node we're building the routing table for.  We're going to need
        // the Ipv4 interface to look for the ipv4 interface index.  Since this node
        // is participating in routing IP version 4 packets, it certainly must have
        // an Ipv4 interface.
        //
        Ptr<Ip> ip = node->GetObject<Ip>();
        NS_ASSERT_MSG(ip,
                      "GlobalRouteManagerImpl::FindOutgoingInterfaceId (): "
                      "GetObject for <Ipv4> interface failed");
        //
        // Look through the interfaces on this node for one that has the IP address
        // we're looking for.  If we find one, return the corresponding interface
        // index, or -1 if not found.
        //
        int32_t interface = ip->GetInterfaceForPrefix(a, amask);
 
#if 0
          if (interface < 0)
            {
              NS_FATAL_ERROR ("GlobalRouteManagerImpl::FindOutgoingInterfaceId(): "
                              "Expected an interface associated with address a:" << a);
            }
#endif
        return interface;
    }
    // This should never happen. The RouterId and vertex Id should match
    NS_FATAL_ERROR("SPFIntraAddRouter(): routerId and vertex ID do not match");
    return -1;
}
 
//
// This method is derived from quagga ospf_intra_add_router ()
//
// This is where we are actually going to add the host routes to the routing
// tables of the individual nodes.
//
// The vertex passed as a parameter has just been added to the SPF tree.
// This vertex must have a valid m_root_oid, corresponding to the outgoing
// interface on the root router of the tree that is the first hop on the path
// to the vertex.  The vertex must also have a next hop address, corresponding
// to the next hop on the path to the vertex.  The vertex has an m_lsa field
// that has some number of link records.  For each point to point link record,
// the m_linkData is the local IP address of the link.  This corresponds to
// a destination IP address, reachable from the root, to which we add a host
// route.
//
 
template <typename T>
void
GlobalRouteManagerImpl<T>::SPFIntraAddRouter(SPFVertex<T>* v)
{
    NS_LOG_FUNCTION(this << v);
 
    NS_ASSERT_MSG(m_spfroot, "GlobalRouteManagerImpl::SPFIntraAddRouter (): Root pointer not set");
    //
    // The root of the Shortest Path First tree is the router to which we are
    // going to write the actual routing table entries.  The vertex corresponding
    // to this router has a vertex ID which is the router ID of that node.  We're
    // going to use this ID to discover which node it is that we're actually going
    // to update.
    //
    IpAddress routerId = m_spfroot->GetVertexId();
 
    NS_LOG_LOGIC("Vertex ID = " << routerId);
    //
    // The node we need to add routes to is the node corresponding to the root vertex.
    // This is the node for which we are building the routing table.
    //
    Ptr<Node> node = m_spfroot->GetNode();
    if (!node)
    {
        NS_LOG_ERROR("SPFIntraAddRouter():Can't find root node " << routerId);
        return;
    }
 
    //
    // The router ID is accessible through the GlobalRouter interface, so we need
    // to GetObject for that interface.  If there's no GlobalRouter interface,
    // the node in question cannot be the router we want, so we continue.
    //
    Ptr<GlobalRouter<T>> rtr = node->GetObject<GlobalRouter<T>>();
    NS_ASSERT_MSG(rtr, "No GlobalRouter interface on node " << node->GetId());
    //
    // If the router ID of the current node is equal to the router ID of the
    // root of the SPF tree, then this node is the one for which we need to
    // write the routing tables.
    //
 
    if (rtr->GetRouterId() == routerId)
    {
        NS_LOG_LOGIC("Setting routes for node " << node->GetId());
        //
        // Routing information is updated using the Ipv4 interface.  We need to
        // GetObject for that interface.  If the node is acting as an IP version 4
        // router, it should absolutely have an Ipv4 interface.
        //
        Ptr<Ip> ip = node->GetObject<Ip>();
        NS_ASSERT_MSG(ip,
                      "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
                      "GetObject for <Ipv4> interface failed");
        //
        // Get the Global Router Link State Advertisement from the vertex we're
        // adding the routes to.  The LSA will have a number of attached Global Router
        // Link Records corresponding to links off of that vertex / node.  We're going
        // to be interested in the records corresponding to point-to-point links.
        //
        GlobalRoutingLSA<IpManager>* lsa = v->GetLSA();
        NS_ASSERT_MSG(lsa,
                      "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
                      "Expected valid LSA in SPFVertex* v");
 
        uint32_t nLinkRecords = lsa->GetNLinkRecords();
        //
        // Iterate through the link records on the vertex to which we're going to add
        // routes.  To make sure we're being clear, we're going to add routing table
        // entries to the tables on the node corresponding to the root of the SPF tree.
        // These entries will have routes to the IP addresses we find from looking at
        // the local side of the point-to-point links found on the node described by
        // the vertex <v>.
        //
        NS_LOG_LOGIC(" Node " << node->GetId() << " found " << nLinkRecords
                              << " link records in LSA " << lsa << "with LinkStateId "
                              << lsa->GetLinkStateId());
        for (uint32_t j = 0; j < nLinkRecords; ++j)
        {
            //
            // We are only concerned about point-to-point links
            //
            GlobalRoutingLinkRecord<IpManager>* lr = lsa->GetLinkRecord(j);
            if (lr->GetLinkType() != GlobalRoutingLinkRecord<IpManager>::PointToPoint)
            {
                continue;
            }
            //
            // Here's why we did all of that work.  We're going to add a host route to the
            // host address found in the m_linkData field of the point-to-point link
            // record.  In the case of a point-to-point link, this is the local IP address
            // of the node connected to the link.  Each of these point-to-point links
            // will correspond to a local interface that has an IP address to which
            // the node at the root of the SPF tree can send packets.  The vertex <v>
            // (corresponding to the node that has these links and interfaces) has
            // an m_nextHop address precalculated for us that is the address to which the
            // root node should send packets to be forwarded to these IP addresses.
            // Similarly, the vertex <v> has an m_rootOif (outbound interface index) to
            // which the packets should be send for forwarding.
            //
            Ptr<GlobalRouter<IpManager>> router = node->GetObject<GlobalRouter<IpManager>>();
            if (!router)
            {
                continue;
            }
            Ptr<GlobalRouting<IpRoutingProtocol>> gr = router->GetRoutingProtocol();
            NS_ASSERT(gr);
            // walk through all available exit directions due to ECMP,
            // and add host route for each of the exit direction toward
            // the vertex 'v'
            for (uint32_t i = 0; i < v->GetNRootExitDirections(); i++)
            {
                typename SPFVertex<T>::NodeExit_t exit = v->GetRootExitDirection(i);
                IpAddress nextHop = exit.first;
                int32_t outIf = exit.second;
                if (outIf >= 0)
                {
                    if (lr->GetLinkData() != IpAddress::GetZero())
                    {
                        gr->AddHostRouteTo(lr->GetLinkData(), nextHop, outIf);
                        NS_LOG_LOGIC("(Route " << i << ") Node " << node->GetId()
                                               << " adding host route to " << lr->GetLinkData()
                                               << " using next hop " << nextHop
                                               << " and outgoing interface " << outIf);
                    }
                    else
                    {
                        NS_LOG_LOGIC("The Link Data field of the link record is zero, This link "
                                     "Record is for an interface with no globalUnicast address,  "
                                     "not adding a hostroute to it");
                        continue;
                    }
                }
                else
                {
                    NS_LOG_LOGIC("(Route " << i << ") Node " << node->GetId()
                                           << " NOT able to add host route to " << lr->GetLinkData()
                                           << " using next hop " << nextHop
                                           << " since outgoing interface id is negative " << outIf);
                }
            }
        }
        //
        // Done adding the routes for the selected node.
        //
        return;
    }
    // This should never happen. The RouterId and vertex Id should match
    NS_FATAL_ERROR("SPFIntraAddRouter(): routerId and vertex ID do not match");
}
 
template <typename T>
void
GlobalRouteManagerImpl<T>::SPFIntraAddTransit(SPFVertex<T>* v)
{
    NS_LOG_FUNCTION(this << v);
 
    NS_ASSERT_MSG(m_spfroot, "GlobalRouteManagerImpl::SPFIntraAddTransit (): Root pointer not set");
    //
    // The root of the Shortest Path First tree is the router to which we are
    // going to write the actual routing table entries.  The vertex corresponding
    // to this router has a vertex ID which is the router ID of that node.  We're
    // going to use this ID to discover which node it is that we're actually going
    // to update.
    //
    IpAddress routerId = m_spfroot->GetVertexId();
 
    NS_LOG_LOGIC("Vertex ID = " << routerId);
    //
    // The node we need to add routes to is the node corresponding to the root vertex.
    // This is the node for which we are building the routing table.
    //
    Ptr<Node> node = m_spfroot->GetNode();
    if (!node)
    {
        NS_LOG_ERROR("SPFIntraAddTransit():Can't find root node " << routerId);
        return;
    }
 
    //
    // The router ID is accessible through the GlobalRouter interface, so we need
    // to GetObject for that interface.  If there's no GlobalRouter interface,
    // the node in question cannot be the router we want, so we continue.
    //
    Ptr<GlobalRouter<T>> rtr = node->GetObject<GlobalRouter<T>>();
    NS_ASSERT_MSG(rtr, "No GlobalRouter interface on node " << node->GetId());
    //
    // If the router ID of the current node is equal to the router ID of the
    // root of the SPF tree, then this node is the one for which we need to
    // write the routing tables.
    //
 
    if (rtr->GetRouterId() == routerId)
    {
        NS_LOG_LOGIC("setting routes for node " << node->GetId());
        //
        // Routing information is updated using the Ipv4 interface.  We need to
        // GetObject for that interface.  If the node is acting as an IP version 4
        // router, it should absolutely have an Ipv4 interface.
        //
        Ptr<Ipv4> ipv4 = node->GetObject<Ipv4>();
        NS_ASSERT_MSG(ipv4,
                      "GlobalRouteManagerImpl::SPFIntraAddTransit (): "
                      "GetObject for <Ipv4> interface failed");
        //
        // Get the Global Router Link State Advertisement from the vertex we're
        // adding the routes to.  The LSA will have a number of attached Global Router
        // Link Records corresponding to links off of that vertex / node.  We're going
        // to be interested in the records corresponding to point-to-point links.
        //
        GlobalRoutingLSA<T>* lsa = v->GetLSA();
        NS_ASSERT_MSG(lsa,
                      "GlobalRouteManagerImpl::SPFIntraAddTransit (): "
                      "Expected valid LSA in SPFVertex* v");
        IpMaskOrPrefix tempmask = lsa->GetNetworkLSANetworkMask();
        IpAddress tempip = lsa->GetLinkStateId();
        if constexpr (IsIpv4)
        {
            tempip = tempip.CombineMask(tempmask);
        }
        else
        {
            tempip = tempip.CombinePrefix(tempmask);
        }
        Ptr<GlobalRouter<T>> router = node->GetObject<GlobalRouter<T>>();
        Ptr<GlobalRouting<IpRoutingProtocol>> gr = router->GetRoutingProtocol();
        NS_ASSERT(gr);
        // walk through all available exit directions due to ECMP,
        // and add host route for each of the exit direction toward
        // the vertex 'v'
        for (uint32_t i = 0; i < v->GetNRootExitDirections(); i++)
        {
            typename SPFVertex<T>::NodeExit_t exit = v->GetRootExitDirection(i);
            IpAddress nextHop = exit.first;
            int32_t outIf = exit.second;
 
            if (outIf >= 0)
            {
                gr->AddNetworkRouteTo(tempip, tempmask, nextHop, outIf);
                NS_LOG_LOGIC("(Route " << i << ") Node " << node->GetId()
                                       << " add network route to " << tempip << " using next hop "
                                       << nextHop << " via interface " << outIf);
            }
            else
            {
                NS_LOG_LOGIC("(Route " << i << ") Node " << node->GetId()
                                       << " NOT able to add network route to " << tempip
                                       << " using next hop " << nextHop
                                       << " since outgoing interface id is negative " << outIf);
            }
        }
        //
        // done adding routes for the root node.
        //
        return;
    }
    // This should never happen. The RouterId and vertex Id should match
    NS_FATAL_ERROR("SPFIntraAddTransit(): routerId and vertex ID do not match");
}
 
// Derived from quagga ospf_vertex_add_parents ()
//
// This is a somewhat oddly named method (blame quagga).  Although you might
// expect it to add a parent *to* something, it actually adds a vertex
// to the list of children *in* each of its parents.
//
// Given a pointer to a vertex, it links back to the vertex's parent that it
// already has set and adds itself to that vertex's list of children.
//
 
template <typename T>
void
GlobalRouteManagerImpl<T>::SPFVertexAddParent(SPFVertex<T>* v)
{
    NS_LOG_FUNCTION(this << v);
 
    for (uint32_t i = 0;;)
    {
        SPFVertex<T>* parent;
        // check if all parents of vertex v
        if ((parent = v->GetParent(i++)) == nullptr)
        {
            break;
        }
        parent->AddChild(v);
    }
}
 
template <typename T>
Ptr<Node>
GlobalRouteManagerImpl<T>::GetNodeByIp(const IpAddress& address)
{
    // iterate through the list of nodes
    for (auto i = NodeList::Begin(); i != NodeList::End(); ++i)
    {
        Ptr<Node> node = *i;
        Ptr<Ip> ip = node->GetObject<Ip>();
 
        if (!ip)
        {
            continue;
        }
 
        int32_t interface = ip->GetInterfaceForAddress(address);
        if (interface >= 0) // Address found on this node
        {
            return node;
        }
    }
    return nullptr; // If no node with the given IP address was found
}
 
template <typename T>
void
GlobalRouteManagerImpl<T>::PrintRoute(Ptr<Node> sourceNode,
                                      Ptr<Node> dest,
                                      Ptr<OutputStreamWrapper> stream,
                                      bool nodeIdLookup,
                                      Time::Unit unit)
{
    // Get any Ip of destination other than the loopbackIp
    Ptr<Ip> ip = dest->GetObject<Ip>();
    NS_ASSERT_MSG(ip, "Ip not found on destination node " << dest->GetId());
 
    uint32_t numInterfaces = ip->GetNInterfaces();
 
    for (uint32_t i = 0; i < numInterfaces; i++)
    {
        uint32_t numAddresses = ip->GetNAddresses(i);
        for (uint32_t j = 0; j < numAddresses; j++)
        {
            IpInterfaceAddress addr = ip->GetAddress(i, j);
            IpAddress localAddr;
            if constexpr (IsIpv4)
            {
                localAddr = addr.GetLocal();
            }
            else
            {
                localAddr = addr.GetAddress();
            }
            if (localAddr != IpAddress::GetLoopback())
            {
                PrintRoute(sourceNode, localAddr, stream, nodeIdLookup, unit);
                return;
            }
        }
    }
    // If no IP address is associated with the destination node, abort the program
    NS_ABORT_MSG("No IP address associated with destination Node");
}
 
template <typename T>
Ptr<typename GlobalRouteManagerImpl<T>::IpGlobalRouting>
GlobalRouteManagerImpl<T>::GetGlobalRoutingForNode(Ptr<Node> node)
{
    Ptr<Ip> ip = node->GetObject<Ip>();
    auto globalRouting = DynamicCast<IpGlobalRouting>(ip->GetRoutingProtocol());
 
    if (globalRouting)
    {
        return globalRouting;
    }
 
    auto list = DynamicCast<IpListRouting>(ip->GetRoutingProtocol());
    if (!list)
    {
        return nullptr;
    }
 
    for (uint32_t i = 0; i < list->GetNRoutingProtocols(); i++)
    {
        int16_t priority = 0;
        globalRouting = DynamicCast<IpGlobalRouting>(list->GetRoutingProtocol(i, priority));
        if (globalRouting)
        {
            return globalRouting;
        }
    }
 
    return nullptr;
}
 
template <typename T>
bool
GlobalRouteManagerImpl<T>::IsLocalDelivery(Ptr<Ip> ip, IpAddress dest)
{
    for (uint32_t i = 0; i < ip->GetNInterfaces(); i++)
    {
        for (uint32_t j = 0; j < ip->GetNAddresses(i); j++)
        {
            auto addr = ip->GetAddress(i, j);
            IpAddress localAddr;
            if constexpr (IsIpv4)
            {
                localAddr = addr.GetLocal();
            }
            else
            {
                localAddr = addr.GetAddress();
            }
            if (dest == localAddr)
            {
                return true;
            }
        }
    }
 
    return false;
}
 
template <typename T>
bool
GlobalRouteManagerImpl<T>::ValidateSourceNodeHasIpAddress(Ptr<Ip> ip)
{
    uint32_t numInter = ip->GetNInterfaces();
    if (numInter == 0)
    {
        NS_ABORT_MSG("No interfaces associated with source Node");
        return false;
    }
 
    for (uint32_t i = 0; i < numInter; i++)
    {
        if (ip->GetNAddresses(i) > 0)
        {
            return true;
        }
    }
 
    NS_ABORT_MSG("No IP address associated with source Node");
    return false;
}
 
template <typename T>
bool
GlobalRouteManagerImpl<T>::IsOnSameSubnet(Ptr<Ip> ipCurrentNode, IpAddress dest)
{
    bool found = false;
    uint32_t numInterfaces = ipCurrentNode->GetNInterfaces();
    for (uint32_t i = 0; i < numInterfaces; i++)
    {
        uint32_t numAddresses = ipCurrentNode->GetNAddresses(i);
        for (uint32_t j = 0; j < numAddresses; j++)
        {
            IpInterfaceAddress senderAddr = ipCurrentNode->GetAddress(i, j);
            // Check if the destination is within the same subnet
            if constexpr (IsIpv4)
            {
                IpMaskOrPrefix mask = senderAddr.GetMask();
                if (mask.IsMatch(dest, senderAddr.GetLocal()))
                {
                    // next hop will be the destNode
                    return true;
                }
            }
            else
            {
                IpMaskOrPrefix prefix = senderAddr.GetPrefix();
                if (prefix.IsMatch(dest, senderAddr.GetAddress()))
                {
                    // next hop will be the destNode
                    return true;
                }
            }
        }
    }
    return found;
}
 
template <typename T>
void
GlobalRouteManagerImpl<T>::PrintRoute(Ptr<Node> sourceNode,
                                      IpAddress dest,
                                      Ptr<OutputStreamWrapper> stream,
                                      bool nodeIdLookup,
                                      Time::Unit unit)
{
    NS_LOG_FUNCTION(this << sourceNode << dest);
 
    Ptr<Node> destNode = GetNodeByIp(dest);
    // check that given ip address exists
    if (!destNode)
    {
        NS_ABORT_MSG("Destination node not found for IP address: " << dest);
        return;
    }
 
    NS_ABORT_MSG_IF(!sourceNode, "No Source Node Provided");
    Ptr<Ip> ip = sourceNode->GetObject<Ip>();
    // check for ip stack
    NS_ABORT_MSG_IF(!ip, "No Ip object found on source node " << sourceNode->GetId());
 
    // check if source has ip address assigned to it
    if (!ValidateSourceNodeHasIpAddress(ip))
    {
        NS_ABORT_MSG("No IP address associated with source Node");
        return;
    }
 
    auto globalRouting = GetGlobalRoutingForNode(sourceNode);
 
    // Final check: If still nullptr, GlobalRouting wasn't found anywhere
    if (!globalRouting)
    {
        NS_ABORT_MSG("No global routing protocol found on source node " << sourceNode->GetId());
        return;
    }
 
    // Set up the output stream
    std::ostream* os = stream->GetStream();
    uint32_t hopsRemaining = 64;
    uint32_t currHop = 1;
    // Print the maxHop. This is similar to TraceRoute
    *os << ", " << hopsRemaining << " hops Max." << std::endl;
 
    // first check if it is local delivery to one of the nodes on the source node itself
    if (IsLocalDelivery(ip, dest))
    {
        NS_LOG_DEBUG("PrintRoute: Source and Destination are on the same Node "
                     << sourceNode->GetId());
        *os << "Source and Destination are on the same Node";
        *os << std::endl << std::endl;
        return;
    }
 
    // check if routes exist
    if (!globalRouting->LookupGlobal(dest))
    {
        *os << "There is no path from Node " << sourceNode->GetId() << " to Node "
            << destNode->GetId() << "." << std::endl
            << std::endl;
        return;
    }
 
    // we start searching for gateways
    Ptr<Node> currentNode = sourceNode;
    IpAddress currentNodeIp;
    std::list<Ptr<Node>> visitedNodes;
    visitedNodes.push_back(currentNode);
    while (currentNode != destNode)
    {
        if (!hopsRemaining)
        {
            NS_LOG_WARN("Max Hop Limit reached");
            return;
        }
 
        Ptr<Ip> ipCurrentNode = currentNode->GetObject<Ip>();
        auto router = GetGlobalRoutingForNode(currentNode);
 
        Ptr<IpRoute> gateway = router->LookupGlobal(dest);
        // check if the gateway exists
        if (!gateway)
        {
            NS_LOG_WARN("No next hop found");
            return;
        }
 
        IpAddress gatewayAddress = gateway->GetGateway();
 
        // check if the currentNode and the destination belong to the same network. Routing tables
        // will have a routing table entry with 0.0.0.0 (or ::) as Gateway
        if (gatewayAddress == IpAddress::GetZero())
        {
            // check if gateway is on the same subnet as the destination if it is not and still null
            // then there is no next jump
            bool found = IsOnSameSubnet(ipCurrentNode, dest);
            if (!found)
            {
                *os << "Error: Did not find any addresses for  " << dest << " From "
                    << currentNode->GetId() << std::endl;
                return;
            }
            else
            {
                currentNode = destNode;
                break;
            }
        }
 
        Ptr<Node> nextNode = GetNodeByIp(gatewayAddress);
 
        if (nextNode == currentNode)
        {
            *os << "Invalid route: Next hop points back to the current node (Node "
                << currentNode->GetId() << ").\n";
            NS_LOG_WARN("Invalid route: Next hop points back to the current node.");
            return;
        }
 
        // check for loops
        if (std::find(visitedNodes.begin(), visitedNodes.end(), nextNode) != visitedNodes.end())
        {
            *os << "Loop detected! Node " << nextNode->GetId() << " revisited.\n\n";
            NS_LOG_WARN("Routing Loop detected");
            return;
        }
        visitedNodes.push_back(nextNode);
 
        Ptr<NetDevice> outdevice = gateway->GetOutputDevice();
        Ptr<IpL3Protocol> ipL3 = currentNode->GetObject<IpL3Protocol>();
        uint32_t interfaceIndex = ipCurrentNode->GetInterfaceForDevice(outdevice);
        currentNodeIp = ipL3->SourceAddressSelection(interfaceIndex, gatewayAddress);
 
        // print this iteration
        std::ostringstream addr;
        std::ostringstream node;
        if (nextNode != destNode)
        {
            node << "(Node " << nextNode->GetId() << ")";
            addr << gatewayAddress;
            *os << std::right << std::setw(2) << currHop++ << "  " << addr.str();
            if (nodeIdLookup)
            {
                *os << " " << node.str();
            }
            *os << std::endl;
        }
        // if the next node is the destination node, then print the Destination IP instead of the
        // ingress IP of the destination.
        else
        {
            node << "(Node " << destNode->GetId() << ")";
            addr << dest;
            *os << std::right << std::setw(2) << currHop++ << "  " << addr.str();
            if (nodeIdLookup)
            {
                *os << " " << node.str();
            }
            *os << std::endl;
        }
        currentNode = nextNode;
        currentNodeIp = gatewayAddress;
        hopsRemaining--;
    }
    *os << std::endl;
}
 
template <typename T>
void
GlobalRouteManagerImpl<T>::InitializeRouters()
{
    NS_LOG_FUNCTION_NOARGS();
    for (auto i = NodeList::Begin(); i != NodeList::End(); i++)
    {
        Ptr<Node> node = *i;
        Ptr<Ip> ip = node->GetObject<Ip>();
        if (!ip)
        {
            continue;
        }
        if constexpr (!IsIpv4)
        {
            ip->SetAttribute("StrongEndSystemModel", BooleanValue(false));
        }
 
        for (uint32_t i = 0; i < ip->GetNInterfaces(); i++)
        {
            ip->SetForwarding(i, true);
        }
    }
}
 
template class SPFVertex<Ipv4Manager>;
template class GlobalRouteManagerLSDB<Ipv4Manager>;
template class ns3::GlobalRouteManagerImpl<ns3::Ipv4Manager>;
template class SPFVertex<Ipv6Manager>;
template class GlobalRouteManagerLSDB<Ipv6Manager>;
template class ns3::GlobalRouteManagerImpl<ns3::Ipv6Manager>;
 
} // namespace ns3