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...

GlobalRouteManagerImpl &	operator= (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...

GlobalRoutingLinkRecord *	SPFGetNextLink (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
GlobalRouteManagerLSDB *	m_lsdb
	the Link State DataBase (LSDB) of the Global Route Manager More...

SPFVertex *	m_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

root	the root node

Returns: true if the node is a stub

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

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

root	the 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

lsdb	the 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

a	the target IP address
amask	the 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

Process Autonomous Systems (AS) External LSA.

Parameters

v	vertex to be processed
extlsa	external LSA

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

References ns3::GlobalRoutingLSA::GetAdvertisingRouter(), ns3::SPFVertex::GetChild(), ns3::GlobalRoutingLSA::GetLinkStateId(), ns3::SPFVertex::GetLSA(), ns3::SPFVertex::GetNChildren(), ns3::SPFVertex::GetVertexId(), ns3::SPFVertex::GetVertexType(), ns3::SPFVertex::IsVertexProcessed(), NS_LOG_FUNCTION, NS_LOG_LOGIC, ns3::SPFVertex::SetVertexProcessed(), SPFAddASExternal(), and ns3::SPFVertex::VertexRouter.

Referenced by SPFCalculate().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ SPFAddASExternal()

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

private

Add an external route to the routing tables.

Parameters

extlsa	the external LSA
v	the vertex

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

References ns3::NodeList::Begin(), ns3::Ipv4Address::CombineMask(), ns3::NodeList::End(), ns3::GlobalRoutingLSA::GetAdvertisingRouter(), ns3::Node::GetId(), ns3::GlobalRoutingLSA::GetLinkStateId(), ns3::SPFVertex::GetLSA(), ns3::GlobalRoutingLSA::GetNetworkLSANetworkMask(), 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, and NS_LOG_LOGIC.

Referenced by ProcessASExternals().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ SPFCalculate()

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

private

Calculate the shortest path first (SPF) tree.

Equivalent to quagga ospf_spf_calculate

Parameters

root	the root node

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

References CheckForStubNode(), ns3::SPFVertex::ClearVertexProcessed(), ns3::GlobalRouteManagerLSDB::GetExtLSA(), ns3::GlobalRoutingLSA::GetLinkStateId(), ns3::SPFVertex::GetLSA(), ns3::GlobalRouteManagerLSDB::GetLSA(), ns3::NodeList::GetNNodes(), ns3::GlobalRouteManagerLSDB::GetNumExtLSAs(), ns3::SPFVertex::GetVertexId(), ns3::SPFVertex::GetVertexType(), ns3::GlobalRouteManagerLSDB::Initialize(), ns3::GlobalRoutingLSA::LSA_SPF_IN_SPFTREE, m_lsdb, m_spfroot, NS_ASSERT, NS_ASSERT_MSG, NS_LOG_FUNCTION, NS_LOG_LOGIC, ns3::CandidateQueue::Pop(), ProcessASExternals(), ns3::SPFVertex::SetDistanceFromRoot(), ns3::GlobalRoutingLSA::SetStatus(), ns3::CandidateQueue::Size(), SPFIntraAddRouter(), SPFIntraAddTransit(), SPFNext(), SPFProcessStubs(), SPFVertexAddParent(), ns3::SPFVertex::VertexNetwork, and ns3::SPFVertex::VertexRouter.

Referenced by DebugSPFCalculate(), and InitializeRoutes().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ 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

v	first vertex
w	second vertex
prev_link	the 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

v	the 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

Add a stub to the routing tables.

Parameters

l	the global routing link record
v	the vertex

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

References ns3::NodeList::Begin(), ns3::Ipv4Address::CombineMask(), ns3::NodeList::End(), ns3::Ipv4Address::Get(), ns3::Node::GetId(), ns3::GlobalRoutingLinkRecord::GetLinkData(), ns3::GlobalRoutingLinkRecord::GetLinkId(), ns3::SPFVertex::GetLSA(), 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, and NS_LOG_LOGIC.

Referenced by SPFProcessStubs().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ SPFIntraAddTransit()

void ns3::GlobalRouteManagerImpl::SPFIntraAddTransit ( SPFVertex * v )

private

Add a transit to the routing tables.

Parameters

v	the vertex

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

References ns3::NodeList::Begin(), ns3::Ipv4Address::CombineMask(), ns3::NodeList::End(), ns3::Node::GetId(), ns3::GlobalRoutingLSA::GetLinkStateId(), ns3::SPFVertex::GetLSA(), ns3::GlobalRoutingLSA::GetNetworkLSANetworkMask(), 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, and NS_LOG_LOGIC.

Referenced by SPFCalculate().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ 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

v	the vertex
candidate	the SPF candidate queue

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

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

v	the parent
w	the destination
l	the link record
distance	the target distance

Returns: 1 on success

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

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

v	vertex 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