20#include "ns3/assert.h"
21#include "ns3/fatal-error.h"
23#include "ns3/node-list.h"
24#include "ns3/simulator.h"
47 os <<
"(" << exit.first <<
" ," << exit.second <<
")";
55 for (
auto iter = vs.begin(); iter != vs.end();)
57 os << (*iter)->m_vertexId;
58 if (++iter != vs.end())
78 : m_vertexType(VertexUnknown),
79 m_vertexId(
"255.255.255.255"),
86 m_vertexProcessed(false)
92 : m_vertexId(lsa->GetLinkStateId()),
99 m_vertexProcessed(false)
129 uint32_t orgCount = (*piter)->m_children.size();
130 (*piter)->m_children.remove(
this);
131 uint32_t newCount = (*piter)->m_children.size();
132 if (orgCount > newCount)
135 "Unable to find the current vertex from its parents --- impossible!");
243 NS_LOG_LOGIC(
"Index to SPFVertex's parent is out-of-range.");
295 "Index out-of-range when accessing SPFVertex::m_ecmpRootExits!");
311 "Assumed there is at most one exit from the root to this vertex");
338 NS_LOG_WARN(
"x root exit directions in this vertex are going to be discarded");
490 if (i->first == addr)
569 uint32_t nRoutes = gr->GetNRoutes();
570 NS_LOG_LOGIC(
"Deleting " << gr->GetNRoutes() <<
" routes from node " << node->GetId());
574 for (j = 0; j < nRoutes; j++)
576 NS_LOG_LOGIC(
"Deleting global route " << j <<
" from node " << node->GetId());
579 NS_LOG_LOGIC(
"Deleted " << j <<
" global routes from node " << node->GetId());
627 uint32_t numLSAs = rtr->DiscoverLSAs();
630 for (
uint32_t j = 0; j < numLSAs; ++j)
637 rtr->GetLSA(j, *lsa);
699 if (node->GetSystemId() != systemId)
708 if (rtr && rtr->GetNumLSAs())
752 for (
uint32_t i = 0; i < numRecordsInVertex; i++)
868 "SPFNexthopCalculation never "
869 <<
"return false, but it does now!");
1051 <<
" goes through next hop " << nextHop
1052 <<
" via outgoing interface " << outIf
1053 <<
" with distance " << distance);
1070 <<
" via outgoing interface " << outIf
1071 <<
" with distance " << distance);
1098 <<
" goes through next hop " << nextHop
1099 <<
" via outgoing interface " << outIf);
1153 bool found_prev_link =
false;
1159 if (prev_link ==
nullptr)
1162 found_prev_link =
true;
1182 if (!found_prev_link)
1185 found_prev_link =
true;
1258 NS_LOG_WARN(
"all nodes should have at least one transit link:" << root);
1271 NS_LOG_LOGIC(
"TBD: Would have inserted default for transit");
1281 for (
uint32_t j = 0; j < nLinkRecords; ++j)
1304 << myRouterId <<
" to next hop " << lr->
GetLinkData()
1305 <<
" via interface "
1346 NS_LOG_LOGIC(
"Starting SPFCalculate for node " << root);
1357 NS_LOG_LOGIC(
"SPFCalculate truncated for stub node " << root);
1386 if (candidate.
Size() == 0)
1400 v = candidate.
Pop();
1495 NS_LOG_LOGIC(
"Found advertising router to destination");
1503 NS_LOG_LOGIC(
"Vertex's child " << i <<
" not yet processed, processing...");
1552 NS_LOG_LOGIC(
"No GlobalRouter interface on node " << node->GetId());
1560 NS_LOG_LOGIC(
"Considering router " << rtr->GetRouterId());
1562 if (rtr->GetRouterId() == routerId)
1564 NS_LOG_LOGIC(
"Setting routes for node " << node->GetId());
1572 "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
1573 "QI for <Ipv4> interface failed");
1581 "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
1582 "Expected valid LSA in SPFVertex* v");
1616 gr->AddASExternalRouteTo(tempip, tempmask, nextHop, outIf);
1617 NS_LOG_LOGIC(
"(Route " << i <<
") Node " << node->GetId()
1618 <<
" add external network route to " << tempip
1619 <<
" using next hop " << nextHop <<
" via interface "
1624 NS_LOG_LOGIC(
"(Route " << i <<
") Node " << node->GetId()
1625 <<
" NOT able to add network route to " << tempip
1626 <<
" using next hop " << nextHop
1627 <<
" since outgoing interface id is negative");
1716 NS_LOG_LOGIC(
"No GlobalRouter interface on node " << node->GetId());
1724 NS_LOG_LOGIC(
"Considering router " << rtr->GetRouterId());
1726 if (rtr->GetRouterId() == routerId)
1728 NS_LOG_LOGIC(
"Setting routes for node " << node->GetId());
1736 "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
1737 "QI for <Ipv4> interface failed");
1745 "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
1746 "Expected valid LSA in SPFVertex* v");
1780 gr->AddNetworkRouteTo(tempip, tempmask, nextHop, outIf);
1781 NS_LOG_LOGIC(
"(Route " << i <<
") Node " << node->GetId()
1782 <<
" add network route to " << tempip
1783 <<
" using next hop " << nextHop <<
" via interface "
1788 NS_LOG_LOGIC(
"(Route " << i <<
") Node " << node->GetId()
1789 <<
" NOT able to add network route to " << tempip
1790 <<
" using next hop " << nextHop
1791 <<
" since outgoing interface id is negative");
1838 if (rtr->GetRouterId() == routerId)
1848 "GlobalRouteManagerImpl::FindOutgoingInterfaceId (): "
1849 "GetObject for <Ipv4> interface failed");
1855 int32_t interface = ipv4->GetInterfaceForPrefix(a, amask);
1860 NS_FATAL_ERROR (
"GlobalRouteManagerImpl::FindOutgoingInterfaceId(): "
1861 "Expected an interface associated with address a:" << a);
1870 NS_LOG_LOGIC(
"FindOutgoingInterfaceId():Can't find root node " << routerId);
1923 NS_LOG_LOGIC(
"No GlobalRouter interface on node " << node->GetId());
1931 NS_LOG_LOGIC(
"Considering router " << rtr->GetRouterId());
1933 if (rtr->GetRouterId() == routerId)
1935 NS_LOG_LOGIC(
"Setting routes for node " << node->GetId());
1943 "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
1944 "GetObject for <Ipv4> interface failed");
1953 "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
1954 "Expected valid LSA in SPFVertex* v");
1965 NS_LOG_LOGIC(
" Node " << node->GetId() <<
" found " << nLinkRecords
1966 <<
" link records in LSA " << lsa <<
"with LinkStateId "
1968 for (
uint32_t j = 0; j < nLinkRecords; ++j)
2008 gr->AddHostRouteTo(lr->
GetLinkData(), nextHop, outIf);
2009 NS_LOG_LOGIC(
"(Route " << i <<
") Node " << node->GetId()
2011 <<
" using next hop " << nextHop
2012 <<
" and outgoing interface " << outIf);
2016 NS_LOG_LOGIC(
"(Route " << i <<
") Node " << node->GetId()
2017 <<
" NOT able to add host route to "
2018 << lr->
GetLinkData() <<
" using next hop " << nextHop
2019 <<
" since outgoing interface id is negative "
2065 NS_LOG_LOGIC(
"No GlobalRouter interface on node " << node->GetId());
2073 NS_LOG_LOGIC(
"Considering router " << rtr->GetRouterId());
2075 if (rtr->GetRouterId() == routerId)
2077 NS_LOG_LOGIC(
"setting routes for node " << node->GetId());
2085 "GlobalRouteManagerImpl::SPFIntraAddTransit (): "
2086 "GetObject for <Ipv4> interface failed");
2095 "GlobalRouteManagerImpl::SPFIntraAddTransit (): "
2096 "Expected valid LSA in SPFVertex* v");
2118 gr->AddNetworkRouteTo(tempip, tempmask, nextHop, outIf);
2119 NS_LOG_LOGIC(
"(Route " << i <<
") Node " << node->GetId()
2120 <<
" add network route to " << tempip
2121 <<
" using next hop " << nextHop <<
" via interface "
2126 NS_LOG_LOGIC(
"(Route " << i <<
") Node " << node->GetId()
2127 <<
" NOT able to add network route to " << tempip
2128 <<
" using next hop " << nextHop
2129 <<
" since outgoing interface id is negative " << outIf);
2154 if ((parent = v->
GetParent(i++)) ==
nullptr)
A Candidate Queue used in routing calculations.
SPFVertex * Pop()
Pop the Shortest Path First Vertex pointer at the top of the queue.
uint32_t Size() const
Return the number of Shortest Path First Vertex pointers presently stored in the Candidate Queue.
void Push(SPFVertex *vNew)
Push a Shortest Path First Vertex pointer onto the queue according to the priority scheme.
void Reorder()
Reorders the Candidate Queue according to the priority scheme.
SPFVertex * Find(const Ipv4Address addr) const
Searches the Candidate Queue for a Shortest Path First Vertex pointer that points to a vertex having ...
void SPFCalculate(Ipv4Address root)
Calculate the shortest path first (SPF) tree.
void SPFAddASExternal(GlobalRoutingLSA *extlsa, SPFVertex *v)
Add an external route to the routing tables.
virtual ~GlobalRouteManagerImpl()
void ProcessASExternals(SPFVertex *v, GlobalRoutingLSA *extlsa)
Process Autonomous Systems (AS) External LSA.
virtual void InitializeRoutes()
Compute routes using a Dijkstra SPF computation and populate per-node forwarding tables.
void SPFProcessStubs(SPFVertex *v)
Process Stub nodes.
virtual void BuildGlobalRoutingDatabase()
Build the routing database by gathering Link State Advertisements from each node exporting a GlobalRo...
GlobalRoutingLinkRecord * SPFGetNextLink(SPFVertex *v, SPFVertex *w, GlobalRoutingLinkRecord *prev_link)
Search for a link between two vertices.
int32_t FindOutgoingInterfaceId(Ipv4Address a, Ipv4Mask amask=Ipv4Mask("255.255.255.255"))
Return the interface number corresponding to a given IP address and mask.
virtual void DeleteGlobalRoutes()
Delete all static routes on all nodes that have a GlobalRouterInterface.
GlobalRouteManagerLSDB * m_lsdb
the Link State DataBase (LSDB) of the Global Route Manager
bool CheckForStubNode(Ipv4Address root)
Test if a node is a stub, from an OSPF sense.
void DebugUseLsdb(GlobalRouteManagerLSDB *lsdb)
Debugging routine; allow client code to supply a pre-built LSDB.
SPFVertex * m_spfroot
the root node
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 l...
void DebugSPFCalculate(Ipv4Address root)
Debugging routine; call the core SPF from the unit tests.
void SPFIntraAddTransit(SPFVertex *v)
Add a transit to the routing tables.
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 roo...
void SPFIntraAddStub(GlobalRoutingLinkRecord *l, SPFVertex *v)
Add a stub to the routing tables.
void SPFIntraAddRouter(SPFVertex *v)
Add a host route to the routing tables.
void SPFVertexAddParent(SPFVertex *v)
Adds a vertex to the list of children in each of its parents.
The Link State DataBase (LSDB) of the Global Route Manager.
void Initialize()
Set all LSA flags to an initialized state, for SPF computation.
std::pair< Ipv4Address, GlobalRoutingLSA * > LSDBPair_t
pair of IPv4 addresses / Link State Advertisements
~GlobalRouteManagerLSDB()
Destroy an empty Global Router Manager Link State Database.
uint32_t GetNumExtLSAs() const
Get the number of External Link State Advertisements.
GlobalRoutingLSA * GetLSA(Ipv4Address addr) const
Look up the Link State Advertisement associated with the given link state ID (address).
std::vector< GlobalRoutingLSA * > m_extdatabase
database of External Link State Advertisements
void Insert(Ipv4Address addr, GlobalRoutingLSA *lsa)
Insert an IP address / Link State Advertisement pair into the Link State Database.
LSDBMap_t m_database
database of IPv4 addresses / Link State Advertisements
GlobalRoutingLSA * GetExtLSA(uint32_t index) const
Look up the External Link State Advertisement associated with the given index.
GlobalRouteManagerLSDB()
Construct an empty Global Router Manager Link State Database.
GlobalRoutingLSA * GetLSAByLinkData(Ipv4Address addr) const
Look up the Link State Advertisement associated with the given link state ID (address).
An interface aggregated to a node to provide global routing info.
a Link State Advertisement (LSA) for a router, used in global routing.
Ipv4Address GetAdvertisingRouter() const
Get the Advertising Router as defined by the OSPF spec.
void SetStatus(SPFStatus status)
Set the SPF status of the advertisement.
@ LSA_SPF_NOT_EXPLORED
New vertex not yet considered.
@ LSA_SPF_IN_SPFTREE
Vertex is in the SPF tree.
@ LSA_SPF_CANDIDATE
Vertex is in the SPF candidate queue.
uint32_t GetNAttachedRouters() const
Return the number of attached routers listed in the NetworkLSA.
Ptr< Node > GetNode() const
Get the Node pointer of the node that originated this LSA.
SPFStatus GetStatus() const
Get the SPF status of the advertisement.
Ipv4Mask GetNetworkLSANetworkMask() const
For a Network LSA, get the Network Mask field that precedes the list of attached routers.
Ipv4Address GetAttachedRouter(uint32_t n) const
Return an Ipv4Address corresponding to the specified attached router.
LSType GetLSType() const
Return the LSType field of the LSA.
uint32_t GetNLinkRecords() const
Return the number of Global Routing Link Records in the LSA.
GlobalRoutingLinkRecord * GetLinkRecord(uint32_t n) const
Return a pointer to the specified Global Routing Link Record.
Ipv4Address GetLinkStateId() const
Get the Link State ID as defined by the OSPF spec.
A single link record for a link state advertisement.
LinkType GetLinkType() const
Get the Link Type field of the Global Routing Link Record.
Ipv4Address GetLinkId() const
Get the Link ID field of the Global Routing Link Record.
uint16_t GetMetric() const
Get the Metric Data field of the Global Routing Link Record.
Ipv4Address GetLinkData() const
Get the Link Data field of the Global Routing Link Record.
@ StubNetwork
Record represents a leaf node network.
@ PointToPoint
Record representing a point to point channel.
@ TransitNetwork
Unused – for future OSPF compatibility
Ipv4 addresses are stored in host order in this class.
static Ipv4Address GetZero()
Ipv4Address CombineMask(const Ipv4Mask &mask) const
Combine this address with a network mask.
uint32_t Get() const
Get the host-order 32-bit IP address.
Access to the IPv4 forwarding table, interfaces, and configuration.
a class to represent an Ipv4 address mask
static uint32_t GetNNodes()
Ptr< T > GetObject() const
Get a pointer to the requested aggregated Object.
Smart pointer class similar to boost::intrusive_ptr.
Vertex used in shortest path first (SPF) computations.
Ipv4Address GetVertexId() const
Get the Vertex ID field of a SPFVertex object.
NodeExit_t GetRootExitDirection(uint32_t i) const
Obtain a pair indicating the exit direction from the root.
std::pair< Ipv4Address, int32_t > NodeExit_t
IPv4 / interface container for exit nodes.
GlobalRoutingLSA * GetLSA() const
Get the Global Router Link State Advertisement returned by the Global Router represented by this SPFV...
Ipv4Address m_nextHop
next hop
void SetVertexId(Ipv4Address id)
Set the Vertex ID field of a SPFVertex object.
void MergeParent(const SPFVertex *v)
Merge the Parent list from the v into this vertex.
VertexType
Enumeration of the possible types of SPFVertex objects.
@ VertexNetwork
Vertex representing a network in the topology.
@ VertexRouter
Vertex representing a router in the topology.
void InheritAllRootExitDirections(const SPFVertex *vertex)
Inherit all root exit directions from a given vertex to 'this' vertex.
void SetDistanceFromRoot(uint32_t distance)
Set the distance from the root vertex to "this" SPFVertex object.
SPFVertex * GetChild(uint32_t n) const
Get a borrowed SPFVertex pointer to the specified child of "this" SPFVertex.
VertexType GetVertexType() const
Get the Vertex Type field of a SPFVertex object.
bool IsVertexProcessed() const
Check the value of the VertexProcessed flag.
void SetParent(SPFVertex *parent)
Set the pointer to the SPFVector that is the parent of "this" SPFVertex.
void MergeRootExitDirections(const SPFVertex *vertex)
Merge into 'this' vertex the list of exit directions from another vertex.
std::list< SPFVertex * > ListOfSPFVertex_t
container of SPFVertex items
uint32_t GetDistanceFromRoot() const
Get the distance from the root vertex to "this" SPFVertex object.
GlobalRoutingLSA * m_lsa
Link State Advertisement.
~SPFVertex()
Destroy an SPFVertex (Shortest Path First Vertex).
void SetRootExitDirection(Ipv4Address nextHop, int32_t id=SPF_INFINITY)
Set the IP address and outgoing interface index that should be used to begin forwarding packets from ...
void SetVertexProcessed(bool value)
Set the value of the VertexProcessed flag.
std::list< NodeExit_t > ListOfNodeExit_t
container of Exit nodes
void SetVertexType(VertexType type)
Set the Vertex Type field of a SPFVertex object.
void SetLSA(GlobalRoutingLSA *lsa)
Set the Global Router Link State Advertisement returned by the Global Router represented by this SPFV...
uint32_t GetNRootExitDirections() const
Get the number of exit directions from root for reaching 'this' vertex.
int32_t m_rootOif
root Output Interface
uint32_t m_distanceFromRoot
Distance from root node.
void ClearVertexProcessed()
Clear the value of the VertexProcessed flag.
bool m_vertexProcessed
Flag to note whether vertex has been processed in stage two of SPF computation.
uint32_t GetNChildren() const
Get the number of children of "this" SPFVertex.
Ipv4Address m_vertexId
Vertex ID.
uint32_t AddChild(SPFVertex *child)
Get a borrowed SPFVertex pointer to the specified child of "this" SPFVertex.
NodeExit_t GetRootExitDirection() const
Obtain a pair indicating the exit direction from the root.
ListOfNodeExit_t m_ecmpRootExits
store the multiple root's exits for supporting ECMP
SPFVertex * GetParent(uint32_t i=0) const
Get a pointer to the SPFVector that is the parent of "this" SPFVertex.
ListOfSPFVertex_t m_children
Children list.
VertexType m_vertexType
Vertex type.
ListOfSPFVertex_t m_parents
parent list
SPFVertex()
Construct an empty ("uninitialized") SPFVertex (Shortest Path First Vertex).
static uint32_t GetSystemId()
Get the system id of this simulator.
#define NS_ASSERT(condition)
At runtime, in debugging builds, if this condition is not true, the program prints the source file,...
#define NS_ASSERT_MSG(condition, message)
At runtime, in debugging builds, if this condition is not true, the program prints the message to out...
#define NS_FATAL_ERROR(msg)
Report a fatal error with a message and terminate.
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
#define NS_LOG_LOGIC(msg)
Use NS_LOG to output a message of level LOG_LOGIC.
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by ",...
#define NS_LOG_WARN(msg)
Use NS_LOG to output a message of level LOG_WARN.
#define NS_LOG_INFO(msg)
Use NS_LOG to output a message of level LOG_INFO.
Every class exported by the ns3 library is enclosed in the ns3 namespace.
std::ostream & operator<<(std::ostream &os, const Angles &a)
const uint32_t SPF_INFINITY
"infinite" distance between nodes