A global router implementation. More...
#include "global-route-manager-impl.h"
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. | |
void | DebugSPFCalculate (Ipv4Address root) |
Debugging routine; call the core SPF from the unit tests. | |
void | DebugUseLsdb (GlobalRouteManagerLSDB *lsdb) |
Debugging routine; allow client code to supply a pre-built LSDB. | |
virtual void | DeleteGlobalRoutes () |
Delete all static routes on all nodes that have a GlobalRouterInterface. | |
virtual void | InitializeRoutes () |
Compute routes using a Dijkstra SPF computation and populate per-node forwarding tables. | |
GlobalRouteManagerImpl & | operator= (const GlobalRouteManagerImpl &)=delete |
Private Member Functions | |
bool | CheckForStubNode (Ipv4Address root) |
Test if a node is a stub, from an OSPF sense. | |
int32_t | FindOutgoingInterfaceId (Ipv4Address a, Ipv4Mask amask=Ipv4Mask("255.255.255.255")) |
Return the interface number corresponding to a given IP address and mask. | |
void | ProcessASExternals (SPFVertex *v, GlobalRoutingLSA *extlsa) |
Process Autonomous Systems (AS) External LSA. | |
void | SPFAddASExternal (GlobalRoutingLSA *extlsa, SPFVertex *v) |
Add an external route to the routing tables. | |
void | SPFCalculate (Ipv4Address root) |
Calculate the shortest path first (SPF) tree. | |
GlobalRoutingLinkRecord * | SPFGetNextLink (SPFVertex *v, SPFVertex *w, GlobalRoutingLinkRecord *prev_link) |
Search for a link between two vertices. | |
void | SPFIntraAddRouter (SPFVertex *v) |
Add a host route to the routing tables. | |
void | SPFIntraAddStub (GlobalRoutingLinkRecord *l, SPFVertex *v) |
Add a stub to the routing tables. | |
void | SPFIntraAddTransit (SPFVertex *v) |
Add a transit to the routing tables. | |
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. | |
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. | |
void | SPFProcessStubs (SPFVertex *v) |
Process Stub nodes. | |
void | SPFVertexAddParent (SPFVertex *v) |
Adds a vertex to the list of children in each of its parents. | |
Private Attributes | |
GlobalRouteManagerLSDB * | m_lsdb |
the Link State DataBase (LSDB) of the Global Route Manager | |
SPFVertex * | m_spfroot |
the root node | |
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 686 of file global-route-manager-impl.h.
ns3::GlobalRouteManagerImpl::GlobalRouteManagerImpl | ( | ) |
Definition at line 528 of file global-route-manager-impl.cc.
References m_lsdb, and NS_LOG_FUNCTION.
|
virtual |
Definition at line 535 of file global-route-manager-impl.cc.
References m_lsdb, and NS_LOG_FUNCTION.
|
delete |
|
virtual |
Build the routing database by gathering Link State Advertisements from each node exporting a GlobalRouter interface.
Definition at line 599 of file global-route-manager-impl.cc.
References ns3::NodeList::Begin(), ns3::NodeList::End(), ns3::GlobalRouteManagerLSDB::Insert(), m_lsdb, NS_LOG_FUNCTION, and NS_LOG_LOGIC.
|
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
root | the root node |
Definition at line 1236 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().
void ns3::GlobalRouteManagerImpl::DebugSPFCalculate | ( | Ipv4Address | root | ) |
Debugging routine; call the core SPF from the unit tests.
root | the root node to start calculations |
Definition at line 1223 of file global-route-manager-impl.cc.
References NS_LOG_FUNCTION, and SPFCalculate().
void ns3::GlobalRouteManagerImpl::DebugUseLsdb | ( | GlobalRouteManagerLSDB * | lsdb | ) |
Debugging routine; allow client code to supply a pre-built LSDB.
lsdb | the pre-built LSDB |
Definition at line 545 of file global-route-manager-impl.cc.
References m_lsdb, and NS_LOG_FUNCTION.
|
virtual |
Delete all static routes on all nodes that have a GlobalRouterInterface.
Definition at line 556 of file global-route-manager-impl.cc.
References ns3::NodeList::Begin(), ns3::NodeList::End(), m_lsdb, NS_LOG_FUNCTION, and NS_LOG_LOGIC.
|
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)
a | the target IP address |
amask | the target subnet mask |
Definition at line 1809 of file global-route-manager-impl.cc.
References ns3::NodeList::Begin(), ns3::NodeList::End(), ns3::SPFVertex::GetVertexId(), m_spfroot, NS_ASSERT_MSG, NS_FATAL_ERROR, NS_LOG_FUNCTION, and NS_LOG_LOGIC.
Referenced by CheckForStubNode(), and SPFNexthopCalculation().
|
virtual |
Compute routes using a Dijkstra SPF computation and populate per-node forwarding tables.
Definition at line 681 of file global-route-manager-impl.cc.
References ns3::NodeList::Begin(), ns3::NodeList::End(), ns3::Simulator::GetSystemId(), NS_LOG_FUNCTION, NS_LOG_INFO, and SPFCalculate().
|
delete |
|
private |
Process Autonomous Systems (AS) External LSA.
v | vertex to be processed |
extlsa | external LSA |
Definition at line 1483 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, ProcessASExternals(), ns3::SPFVertex::SetVertexProcessed(), SPFAddASExternal(), and ns3::SPFVertex::VertexRouter.
Referenced by ProcessASExternals(), and SPFCalculate().
|
private |
Add an external route to the routing tables.
extlsa | the external LSA |
v | the vertex |
Definition at line 1516 of file global-route-manager-impl.cc.
References ns3::NodeList::Begin(), ns3::Ipv4Address::CombineMask(), ns3::NodeList::End(), ns3::GlobalRoutingLSA::GetAdvertisingRouter(), ns3::GlobalRoutingLSA::GetLinkStateId(), ns3::SPFVertex::GetLSA(), ns3::GlobalRoutingLSA::GetNetworkLSANetworkMask(), ns3::SPFVertex::GetNRootExitDirections(), ns3::SPFVertex::GetRootExitDirection(), ns3::SPFVertex::GetVertexId(), m_spfroot, NS_ASSERT, NS_ASSERT_MSG, NS_LOG_FUNCTION, and NS_LOG_LOGIC.
Referenced by ProcessASExternals().
|
private |
Calculate the shortest path first (SPF) tree.
Equivalent to quagga ospf_spf_calculate
root | the root node |
Definition at line 1317 of file global-route-manager-impl.cc.
References CheckForStubNode(), ns3::SPFVertex::ClearVertexProcessed(), ns3::GlobalRouteManagerLSDB::GetExtLSA(), ns3::GlobalRoutingLSA::GetLinkStateId(), ns3::GlobalRouteManagerLSDB::GetLSA(), ns3::SPFVertex::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().
|
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.
v | first vertex |
w | second vertex |
prev_link | the previous link in the list |
Definition at line 1146 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().
|
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.
v | the vertex |
Definition at line 1893 of file global-route-manager-impl.cc.
References ns3::NodeList::Begin(), ns3::NodeList::End(), ns3::GlobalRoutingLinkRecord::GetLinkData(), ns3::GlobalRoutingLSA::GetLinkRecord(), ns3::GlobalRoutingLSA::GetLinkStateId(), ns3::GlobalRoutingLinkRecord::GetLinkType(), ns3::SPFVertex::GetLSA(), ns3::GlobalRoutingLSA::GetNLinkRecords(), ns3::SPFVertex::GetNRootExitDirections(), 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().
|
private |
Add a stub to the routing tables.
l | the global routing link record |
v | the vertex |
Definition at line 1674 of file global-route-manager-impl.cc.
References ns3::NodeList::Begin(), ns3::Ipv4Address::CombineMask(), ns3::NodeList::End(), ns3::Ipv4Address::Get(), ns3::GlobalRoutingLinkRecord::GetLinkData(), ns3::GlobalRoutingLinkRecord::GetLinkId(), ns3::SPFVertex::GetLSA(), ns3::SPFVertex::GetNRootExitDirections(), ns3::SPFVertex::GetRootExitDirection(), ns3::SPFVertex::GetVertexId(), m_spfroot, NS_ASSERT, NS_ASSERT_MSG, NS_LOG_FUNCTION, and NS_LOG_LOGIC.
Referenced by SPFProcessStubs().
|
private |
Add a transit to the routing tables.
v | the vertex |
Definition at line 2036 of file global-route-manager-impl.cc.
References ns3::NodeList::Begin(), ns3::Ipv4Address::CombineMask(), ns3::NodeList::End(), ns3::GlobalRoutingLSA::GetLinkStateId(), ns3::SPFVertex::GetLSA(), ns3::GlobalRoutingLSA::GetNetworkLSANetworkMask(), ns3::SPFVertex::GetNRootExitDirections(), ns3::SPFVertex::GetRootExitDirection(), ns3::SPFVertex::GetVertexId(), m_spfroot, NS_ASSERT, NS_ASSERT_MSG, NS_LOG_FUNCTION, and NS_LOG_LOGIC.
Referenced by SPFCalculate().
|
private |
Examine the links in v's LSA and update the list of candidates with any vertices not already on the list.
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.
v | the vertex |
candidate | the SPF candidate queue |
Definition at line 730 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::GlobalRouteManagerLSDB::GetLSA(), ns3::SPFVertex::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().
|
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
v | the parent |
w | the destination |
l | the link record |
distance | the target distance |
Definition at line 962 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().
|
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
v | vertex to be processed |
Definition at line 1641 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(), SPFProcessStubs(), ns3::GlobalRoutingLinkRecord::StubNetwork, and ns3::SPFVertex::VertexRouter.
Referenced by SPFCalculate(), and SPFProcessStubs().
|
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.
v | the vertex |
Definition at line 2149 of file global-route-manager-impl.cc.
References ns3::SPFVertex::AddChild(), ns3::SPFVertex::GetParent(), and NS_LOG_FUNCTION.
Referenced by SPFCalculate(), and SPFNext().
|
private |
the Link State DataBase (LSDB) of the Global Route Manager
Definition at line 731 of file global-route-manager-impl.h.
Referenced by GlobalRouteManagerImpl(), ~GlobalRouteManagerImpl(), BuildGlobalRoutingDatabase(), CheckForStubNode(), DebugUseLsdb(), DeleteGlobalRoutes(), SPFCalculate(), and SPFNext().
|
private |
the root node
Definition at line 730 of file global-route-manager-impl.h.
Referenced by FindOutgoingInterfaceId(), SPFAddASExternal(), SPFCalculate(), SPFIntraAddRouter(), SPFIntraAddStub(), SPFIntraAddTransit(), and SPFNexthopCalculation().