A global router implementation. More...

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

Public Member Functions
	GlobalRouteManagerImpl ()

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

Private Member Functions
	GlobalRouteManagerImpl (GlobalRouteManagerImpl &srmi)
	GlobalRouteManagerImpl copy construction is disallowed. More...

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

GlobalRouteManagerImpl &	operator= (GlobalRouteManagerImpl &srmi)
	Global Route Manager Implementation assignment operator is disallowed. 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 712 of file global-route-manager-impl.h.

Constructor & Destructor Documentation

◆ GlobalRouteManagerImpl() [1/2]

ns3::GlobalRouteManagerImpl::GlobalRouteManagerImpl ( )

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

References m_lsdb, and NS_LOG_FUNCTION.

◆ ~GlobalRouteManagerImpl()

ns3::GlobalRouteManagerImpl::~GlobalRouteManagerImpl ( )

virtual

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

References m_lsdb, and NS_LOG_FUNCTION.

◆ GlobalRouteManagerImpl() [2/2]

ns3::GlobalRouteManagerImpl::GlobalRouteManagerImpl ( GlobalRouteManagerImpl & srmi )

private

GlobalRouteManagerImpl copy construction is disallowed.

There's no need for it and a compiler provided shallow copy would be wrong.

Parameters

srmi	object to copy from

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 613 of file global-route-manager-impl.cc.

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

◆ 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 1260 of file global-route-manager-impl.cc.

Referenced by SPFCalculate().

◆ 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 1247 of file global-route-manager-impl.cc.

References NS_LOG_FUNCTION, and SPFCalculate().

Referenced by GlobalRouteManagerImplTestCase::DoRun().

◆ DebugUseLsdb()

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

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

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

References m_lsdb, and NS_LOG_FUNCTION.

Referenced by GlobalRouteManagerImplTestCase::DoRun().

◆ 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 569 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().

◆ 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 1843 of file global-route-manager-impl.cc.

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

Referenced by CheckForStubNode(), and SPFNexthopCalculation().

◆ InitializeRoutes()

void ns3::GlobalRouteManagerImpl::InitializeRoutes ( )

virtual

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

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

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

◆ operator=()

GlobalRouteManagerImpl& ns3::GlobalRouteManagerImpl::operator= ( GlobalRouteManagerImpl & srmi )

private

Global Route Manager Implementation assignment operator is disallowed.

There's no need for it and a compiler provided shallow copy would be hopelessly wrong.

Parameters

srmi	object to copy from

Returns: the copied object

◆ 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 1508 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().

◆ 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 1542 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(), m_spfroot, NS_ASSERT, NS_ASSERT_MSG(), NS_LOG_FUNCTION, and NS_LOG_LOGIC().

Referenced by ProcessASExternals().

◆ 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 1342 of file global-route-manager-impl.cc.

References CheckForStubNode(), ns3::SPFVertex::ClearVertexProcessed(), ns3::GlobalRouteManagerLSDB::GetExtLSA(), ns3::GlobalRoutingLSA::GetLinkStateId(), ns3::GlobalRouteManagerLSDB::GetLSA(), ns3::NodeList::GetNNodes(), ns3::GlobalRouteManagerLSDB::GetNumExtLSAs(), 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::CandidateQueue::Size(), SPFIntraAddRouter(), SPFIntraAddTransit(), SPFNext(), SPFProcessStubs(), SPFVertexAddParent(), ns3::SPFVertex::VertexNetwork, and ns3::SPFVertex::VertexRouter.

Referenced by DebugSPFCalculate(), and InitializeRoutes().

◆ 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 1169 of file global-route-manager-impl.cc.

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

Referenced by SPFNexthopCalculation().

◆ 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 1930 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(), m_spfroot, NS_ASSERT, NS_ASSERT_MSG(), NS_LOG_FUNCTION, NS_LOG_LOGIC(), and ns3::GlobalRoutingLinkRecord::PointToPoint.

Referenced by SPFCalculate().

◆ 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 1703 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(), m_spfroot, NS_ASSERT, NS_ASSERT_MSG(), NS_LOG_FUNCTION, and NS_LOG_LOGIC().

Referenced by SPFProcessStubs().

◆ SPFIntraAddTransit()

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

private

Add a transit to the routing tables.

Parameters

v	the vertex

Definition at line 2075 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(), m_spfroot, NS_ASSERT, NS_ASSERT_MSG(), NS_LOG_FUNCTION, and NS_LOG_LOGIC().

Referenced by SPFCalculate().

◆ 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 747 of file global-route-manager-impl.cc.

Referenced by SPFCalculate().

◆ 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 981 of file global-route-manager-impl.cc.

Referenced by SPFNext().

◆ 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 1669 of file global-route-manager-impl.cc.

References ns3::SPFVertex::GetChild(), ns3::GlobalRoutingLSA::GetLinkRecord(), ns3::GlobalRoutingLSA::GetLinkStateId(), 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().

◆ 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