A Discrete-Event Network Simulator
API
ns3::GlobalRouteManagerImpl Class Reference

A global router implementation. More...

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

+ Collaboration diagram for ns3::GlobalRouteManagerImpl:

Public Member Functions

 GlobalRouteManagerImpl ()
 
 GlobalRouteManagerImpl (const GlobalRouteManagerImpl &)=delete
 
virtual ~GlobalRouteManagerImpl ()
 
virtual void BuildGlobalRoutingDatabase ()
 Build the routing database by gathering Link State Advertisements from each node exporting a GlobalRouter interface. More...
 
void DebugSPFCalculate (Ipv4Address root)
 Debugging routine; call the core SPF from the unit tests. More...
 
void DebugUseLsdb (GlobalRouteManagerLSDB *lsdb)
 Debugging routine; allow client code to supply a pre-built LSDB. More...
 
virtual void DeleteGlobalRoutes ()
 Delete all static routes on all nodes that have a GlobalRouterInterface. More...
 
virtual void InitializeRoutes ()
 Compute routes using a Dijkstra SPF computation and populate per-node forwarding tables. More...
 
GlobalRouteManagerImploperator= (const GlobalRouteManagerImpl &)=delete
 

Private Member Functions

bool CheckForStubNode (Ipv4Address root)
 Test if a node is a stub, from an OSPF sense. More...
 
int32_t FindOutgoingInterfaceId (Ipv4Address a, Ipv4Mask amask=Ipv4Mask("255.255.255.255"))
 Return the interface number corresponding to a given IP address and mask. More...
 
void ProcessASExternals (SPFVertex *v, GlobalRoutingLSA *extlsa)
 Process Autonomous Systems (AS) External LSA. More...
 
void SPFAddASExternal (GlobalRoutingLSA *extlsa, SPFVertex *v)
 Add an external route to the routing tables. More...
 
void SPFCalculate (Ipv4Address root)
 Calculate the shortest path first (SPF) tree. More...
 
GlobalRoutingLinkRecordSPFGetNextLink (SPFVertex *v, SPFVertex *w, GlobalRoutingLinkRecord *prev_link)
 Search for a link between two vertices. More...
 
void SPFIntraAddRouter (SPFVertex *v)
 Add a host route to the routing tables. More...
 
void SPFIntraAddStub (GlobalRoutingLinkRecord *l, SPFVertex *v)
 Add a stub to the routing tables. More...
 
void SPFIntraAddTransit (SPFVertex *v)
 Add a transit to the routing tables. More...
 
void SPFNext (SPFVertex *v, CandidateQueue &candidate)
 Examine the links in v's LSA and update the list of candidates with any vertices not already on the list. More...
 
int SPFNexthopCalculation (SPFVertex *v, SPFVertex *w, GlobalRoutingLinkRecord *l, uint32_t distance)
 Calculate nexthop from root through V (parent) to vertex W (destination) with given distance from root->W. More...
 
void SPFProcessStubs (SPFVertex *v)
 Process Stub nodes. More...
 
void SPFVertexAddParent (SPFVertex *v)
 Adds a vertex to the list of children in each of its parents. More...
 

Private Attributes

GlobalRouteManagerLSDBm_lsdb
 the Link State DataBase (LSDB) of the Global Route Manager More...
 
SPFVertexm_spfroot
 the root node More...
 

Detailed Description

A global router implementation.

This singleton object can query interface each node in the system for a GlobalRouter interface. For those nodes, it fetches one or more Link State Advertisements and stores them in a local database. Then, it can compute shortest paths on a per-node basis to all routers, and finally configure each of the node's forwarding tables.

The design is guided by OSPFv2 RFC 2328 section 16.1.1 and quagga ospfd.

Definition at line 697 of file global-route-manager-impl.h.

Constructor & Destructor Documentation

◆ GlobalRouteManagerImpl() [1/2]

ns3::GlobalRouteManagerImpl::GlobalRouteManagerImpl ( )

Definition at line 539 of file global-route-manager-impl.cc.

References m_lsdb, and NS_LOG_FUNCTION.

◆ ~GlobalRouteManagerImpl()

ns3::GlobalRouteManagerImpl::~GlobalRouteManagerImpl ( )
virtual

Definition at line 546 of file global-route-manager-impl.cc.

References m_lsdb, and NS_LOG_FUNCTION.

◆ GlobalRouteManagerImpl() [2/2]

ns3::GlobalRouteManagerImpl::GlobalRouteManagerImpl ( const GlobalRouteManagerImpl )
delete

Member Function Documentation

◆ BuildGlobalRoutingDatabase()

void ns3::GlobalRouteManagerImpl::BuildGlobalRoutingDatabase ( )
virtual

Build the routing database by gathering Link State Advertisements from each node exporting a GlobalRouter interface.

Definition at line 610 of file global-route-manager-impl.cc.

References ns3::NodeList::Begin(), ns3::NodeList::End(), ns3::Object::GetObject(), ns3::GlobalRouteManagerLSDB::Insert(), m_lsdb, NS_LOG_FUNCTION, and NS_LOG_LOGIC.

+ Here is the call graph for this function:

◆ CheckForStubNode()

bool ns3::GlobalRouteManagerImpl::CheckForStubNode ( Ipv4Address  root)
private

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

Parameters
rootthe root node
Returns
true if the node is a stub

Definition at line 1247 of file global-route-manager-impl.cc.

References FindOutgoingInterfaceId(), ns3::GlobalRoutingLinkRecord::GetLinkData(), ns3::GlobalRoutingLinkRecord::GetLinkId(), ns3::GlobalRoutingLSA::GetLinkRecord(), ns3::GlobalRoutingLSA::GetLinkStateId(), ns3::GlobalRoutingLinkRecord::GetLinkType(), ns3::GlobalRouteManagerLSDB::GetLSA(), ns3::GlobalRoutingLSA::GetNLinkRecords(), ns3::GlobalRoutingLSA::GetNode(), ns3::Object::GetObject(), m_lsdb, NS_ASSERT, NS_LOG_FUNCTION, NS_LOG_LOGIC, NS_LOG_WARN, ns3::GlobalRoutingLinkRecord::PointToPoint, and ns3::GlobalRoutingLinkRecord::TransitNetwork.

Referenced by SPFCalculate().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ DebugSPFCalculate()

void ns3::GlobalRouteManagerImpl::DebugSPFCalculate ( Ipv4Address  root)

Debugging routine; call the core SPF from the unit tests.

Parameters
rootthe root node to start calculations

Definition at line 1234 of file global-route-manager-impl.cc.

References NS_LOG_FUNCTION, and SPFCalculate().

+ Here is the call graph for this function:

◆ DebugUseLsdb()

void ns3::GlobalRouteManagerImpl::DebugUseLsdb ( GlobalRouteManagerLSDB lsdb)

Debugging routine; allow client code to supply a pre-built LSDB.

Parameters
lsdbthe pre-built LSDB

Definition at line 556 of file global-route-manager-impl.cc.

References m_lsdb, and NS_LOG_FUNCTION.

◆ DeleteGlobalRoutes()

void ns3::GlobalRouteManagerImpl::DeleteGlobalRoutes ( )
virtual

Delete all static routes on all nodes that have a GlobalRouterInterface.

Todo:
separate manually assigned static routes from static routes that the global routing code injects, and only delete the latter

Definition at line 567 of file global-route-manager-impl.cc.

References ns3::NodeList::Begin(), ns3::NodeList::End(), ns3::Node::GetId(), ns3::Object::GetObject(), m_lsdb, NS_LOG_FUNCTION, and NS_LOG_LOGIC.

+ Here is the call graph for this function:

◆ FindOutgoingInterfaceId()

int32_t ns3::GlobalRouteManagerImpl::FindOutgoingInterfaceId ( Ipv4Address  a,
Ipv4Mask  amask = Ipv4Mask("255.255.255.255") 
)
private

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)

Parameters
athe target IP address
amaskthe target subnet mask
Returns
the outgoing interface number

Definition at line 1822 of file global-route-manager-impl.cc.

References ns3::NodeList::Begin(), ns3::NodeList::End(), ns3::Object::GetObject(), ns3::SPFVertex::GetVertexId(), nsclick-simple-lan::ipv4, m_spfroot, NS_ASSERT_MSG, NS_FATAL_ERROR, NS_LOG_FUNCTION, and NS_LOG_LOGIC.

Referenced by CheckForStubNode(), and SPFNexthopCalculation().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ InitializeRoutes()

void ns3::GlobalRouteManagerImpl::InitializeRoutes ( )
virtual

Compute routes using a Dijkstra SPF computation and populate per-node forwarding tables.

Definition at line 692 of file global-route-manager-impl.cc.

References ns3::NodeList::Begin(), ns3::NodeList::End(), ns3::Object::GetObject(), ns3::Simulator::GetSystemId(), ns3::Node::GetSystemId(), NS_LOG_FUNCTION, NS_LOG_INFO, and SPFCalculate().

+ Here is the call graph for this function:

◆ operator=()

GlobalRouteManagerImpl& ns3::GlobalRouteManagerImpl::operator= ( const GlobalRouteManagerImpl )
delete

◆ ProcessASExternals()

void ns3::GlobalRouteManagerImpl::ProcessASExternals ( SPFVertex v,
GlobalRoutingLSA extlsa 
)
private

◆ SPFAddASExternal()

void ns3::GlobalRouteManagerImpl::SPFAddASExternal ( GlobalRoutingLSA extlsa,
SPFVertex v 
)
private

◆ SPFCalculate()

◆ SPFGetNextLink()

GlobalRoutingLinkRecord * ns3::GlobalRouteManagerImpl::SPFGetNextLink ( SPFVertex v,
SPFVertex w,
GlobalRoutingLinkRecord prev_link 
)
private

Search for a link between two vertices.

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.

Parameters
vfirst vertex
wsecond vertex
prev_linkthe previous link in the list
Returns
the link's record

Definition at line 1157 of file global-route-manager-impl.cc.

References ns3::GlobalRoutingLinkRecord::GetLinkData(), ns3::GlobalRoutingLinkRecord::GetLinkId(), ns3::GlobalRoutingLSA::GetLinkRecord(), ns3::SPFVertex::GetLSA(), ns3::SPFVertex::GetVertexId(), NS_LOG_FUNCTION, and NS_LOG_LOGIC.

Referenced by SPFNexthopCalculation().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ SPFIntraAddRouter()

void ns3::GlobalRouteManagerImpl::SPFIntraAddRouter ( SPFVertex v)
private

Add a host route to the routing tables.

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.

Parameters
vthe vertex

Definition at line 1906 of file global-route-manager-impl.cc.

References ns3::NodeList::Begin(), ns3::NodeList::End(), ns3::Node::GetId(), ns3::GlobalRoutingLinkRecord::GetLinkData(), ns3::GlobalRoutingLSA::GetLinkRecord(), ns3::GlobalRoutingLSA::GetLinkStateId(), ns3::GlobalRoutingLinkRecord::GetLinkType(), ns3::SPFVertex::GetLSA(), ns3::GlobalRoutingLSA::GetNLinkRecords(), ns3::SPFVertex::GetNRootExitDirections(), ns3::Object::GetObject(), ns3::SPFVertex::GetRootExitDirection(), ns3::SPFVertex::GetVertexId(), nsclick-simple-lan::ipv4, m_spfroot, NS_ASSERT, NS_ASSERT_MSG, NS_LOG_FUNCTION, NS_LOG_LOGIC, and ns3::GlobalRoutingLinkRecord::PointToPoint.

Referenced by SPFCalculate().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ SPFIntraAddStub()

void ns3::GlobalRouteManagerImpl::SPFIntraAddStub ( GlobalRoutingLinkRecord l,
SPFVertex v 
)
private

◆ SPFIntraAddTransit()

◆ SPFNext()

void ns3::GlobalRouteManagerImpl::SPFNext ( SPFVertex v,
CandidateQueue candidate 
)
private

Examine the links in v's LSA and update the list of candidates with any vertices not already on the list.

Internal:

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.

Parameters
vthe vertex
candidatethe SPF candidate queue

Definition at line 741 of file global-route-manager-impl.cc.

References ns3::CandidateQueue::Find(), ns3::GlobalRoutingLSA::GetAttachedRouter(), ns3::SPFVertex::GetDistanceFromRoot(), ns3::GlobalRoutingLinkRecord::GetLinkId(), ns3::GlobalRoutingLSA::GetLinkRecord(), ns3::GlobalRoutingLSA::GetLinkStateId(), ns3::GlobalRoutingLinkRecord::GetLinkType(), ns3::SPFVertex::GetLSA(), ns3::GlobalRouteManagerLSDB::GetLSA(), ns3::GlobalRouteManagerLSDB::GetLSAByLinkData(), ns3::GlobalRoutingLSA::GetLSType(), ns3::GlobalRoutingLinkRecord::GetMetric(), ns3::GlobalRoutingLSA::GetNAttachedRouters(), ns3::GlobalRoutingLSA::GetNLinkRecords(), ns3::GlobalRoutingLSA::GetStatus(), ns3::SPFVertex::GetVertexId(), ns3::SPFVertex::GetVertexType(), ns3::GlobalRoutingLSA::LSA_SPF_CANDIDATE, ns3::GlobalRoutingLSA::LSA_SPF_IN_SPFTREE, ns3::GlobalRoutingLSA::LSA_SPF_NOT_EXPLORED, m_lsdb, ns3::SPFVertex::MergeParent(), ns3::SPFVertex::MergeRootExitDirections(), NS_ASSERT, NS_ASSERT_MSG, NS_LOG_FUNCTION, NS_LOG_LOGIC, ns3::GlobalRoutingLinkRecord::PointToPoint, ns3::CandidateQueue::Push(), ns3::CandidateQueue::Reorder(), ns3::GlobalRoutingLSA::RouterLSA, ns3::GlobalRoutingLSA::SetStatus(), SPFNexthopCalculation(), SPFVertexAddParent(), ns3::GlobalRoutingLinkRecord::StubNetwork, ns3::GlobalRoutingLinkRecord::TransitNetwork, ns3::SPFVertex::VertexNetwork, and ns3::SPFVertex::VertexRouter.

Referenced by SPFCalculate().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ SPFNexthopCalculation()

int ns3::GlobalRouteManagerImpl::SPFNexthopCalculation ( SPFVertex v,
SPFVertex w,
GlobalRoutingLinkRecord l,
uint32_t  distance 
)
private

Calculate nexthop from root through V (parent) to vertex W (destination) with given distance from root->W.

This method is derived from quagga ospf_nexthop_calculation() 16.1.1. For now, this is greatly simplified from the quagga code

Parameters
vthe parent
wthe destination
lthe link record
distancethe target distance
Returns
1 on success

Definition at line 973 of file global-route-manager-impl.cc.

References FindOutgoingInterfaceId(), ns3::GlobalRoutingLinkRecord::GetLinkData(), ns3::GlobalRoutingLSA::GetLinkStateId(), ns3::SPFVertex::GetLSA(), ns3::GlobalRoutingLSA::GetLSType(), ns3::GlobalRoutingLSA::GetNetworkLSANetworkMask(), ns3::SPFVertex::GetParent(), ns3::SPFVertex::GetRootExitDirection(), ns3::SPFVertex::GetVertexId(), ns3::SPFVertex::GetVertexType(), ns3::Ipv4Address::GetZero(), ns3::SPFVertex::InheritAllRootExitDirections(), m_spfroot, ns3::GlobalRoutingLSA::NetworkLSA, NS_ASSERT, NS_LOG_FUNCTION, NS_LOG_LOGIC, ns3::SPFVertex::SetDistanceFromRoot(), ns3::SPFVertex::SetParent(), ns3::SPFVertex::SetRootExitDirection(), SPFGetNextLink(), ns3::SPFVertex::VertexNetwork, and ns3::SPFVertex::VertexRouter.

Referenced by SPFNext().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ SPFProcessStubs()

void ns3::GlobalRouteManagerImpl::SPFProcessStubs ( SPFVertex v)
private

Process Stub nodes.

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

Parameters
vvertex to be processed

Definition at line 1654 of file global-route-manager-impl.cc.

References ns3::SPFVertex::GetChild(), ns3::GlobalRoutingLinkRecord::GetLinkId(), ns3::GlobalRoutingLSA::GetLinkRecord(), ns3::GlobalRoutingLSA::GetLinkStateId(), ns3::GlobalRoutingLinkRecord::GetLinkType(), ns3::SPFVertex::GetLSA(), ns3::SPFVertex::GetNChildren(), ns3::GlobalRoutingLSA::GetNLinkRecords(), ns3::SPFVertex::GetVertexId(), ns3::SPFVertex::GetVertexType(), ns3::SPFVertex::IsVertexProcessed(), NS_LOG_FUNCTION, NS_LOG_LOGIC, ns3::SPFVertex::SetVertexProcessed(), SPFIntraAddStub(), ns3::GlobalRoutingLinkRecord::StubNetwork, and ns3::SPFVertex::VertexRouter.

Referenced by SPFCalculate().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ SPFVertexAddParent()

void ns3::GlobalRouteManagerImpl::SPFVertexAddParent ( SPFVertex v)
private

Adds a vertex to the list of children in each of its parents.

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.

Parameters
vthe vertex

Definition at line 2161 of file global-route-manager-impl.cc.

References ns3::SPFVertex::AddChild(), ns3::SPFVertex::GetParent(), and NS_LOG_FUNCTION.

Referenced by SPFCalculate(), and SPFNext().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

Member Data Documentation

◆ m_lsdb

GlobalRouteManagerLSDB* ns3::GlobalRouteManagerImpl::m_lsdb
private

the Link State DataBase (LSDB) of the Global Route Manager

Definition at line 742 of file global-route-manager-impl.h.

Referenced by GlobalRouteManagerImpl(), ~GlobalRouteManagerImpl(), BuildGlobalRoutingDatabase(), CheckForStubNode(), DebugUseLsdb(), DeleteGlobalRoutes(), SPFCalculate(), and SPFNext().

◆ m_spfroot

SPFVertex* ns3::GlobalRouteManagerImpl::m_spfroot
private

The documentation for this class was generated from the following files: