30 #include "ns3/assert.h"
31 #include "ns3/fatal-error.h"
33 #include "ns3/node-list.h"
35 #include "ns3/ipv4-routing-protocol.h"
36 #include "ns3/ipv4-list-routing.h"
37 #include "ns3/mpi-interface.h"
50 os <<
"(" << exit.first <<
" ," << exit.second <<
")";
57 typedef SPFVertex::ListOfSPFVertex_t::const_iterator CIter_t;
59 for (CIter_t iter = vs.begin (); iter != vs.end ();)
61 os << (*iter)->m_vertexId;
62 if (++iter != vs.end ())
82 m_vertexType (VertexUnknown),
83 m_vertexId (
"255.255.255.255"),
87 m_nextHop (
"0.0.0.0"),
90 m_vertexProcessed (false)
96 m_vertexId (lsa->GetLinkStateId ()),
100 m_nextHop (
"0.0.0.0"),
103 m_vertexProcessed (false)
128 for (ListOfSPFVertex_t::iterator piter =
m_parents.begin ();
135 uint32_t orgCount = (*piter)->m_children.size ();
136 (*piter)->m_children.remove (
this);
137 uint32_t newCount = (*piter)->m_children.size ();
138 if (orgCount > newCount)
140 NS_ASSERT_MSG (orgCount > newCount,
"Unable to find the current vertex from its parents --- impossible!");
156 if (p == 0)
continue;
244 NS_LOG_LOGIC (
"Index to SPFVertex's parent is out-of-range.");
247 ListOfSPFVertex_t::const_iterator iter =
m_parents.begin ();
295 typedef ListOfNodeExit_t::const_iterator CIter_t;
299 while (i-- > 0) { iter++; }
323 extList.begin (), extList.end ());
337 NS_LOG_WARN (
"x root exit directions in this vertex are going to be discarded");
364 for ( ListOfSPFVertex_t::const_iterator i =
m_children.begin ();
427 LSDBMap_t::iterator i;
448 LSDBMap_t::iterator i;
491 LSDBMap_t::const_iterator i;
494 if (i->first == addr)
509 LSDBMap_t::const_iterator i;
576 uint32_t nRoutes = gr->GetNRoutes ();
577 NS_LOG_LOGIC (
"Deleting " << gr->GetNRoutes ()<<
" routes from node " << node->
GetId ());
581 for (j = 0; j < nRoutes; j++)
635 uint32_t numLSAs = rtr->DiscoverLSAs ();
638 for (uint32_t j = 0; j < numLSAs; ++j)
645 rtr->GetLSA (j, *lsa);
717 if (rtr && rtr->GetNumLSAs () )
746 uint32_t distance = 0;
747 uint32_t numRecordsInVertex = 0;
761 for (uint32_t i = 0; i < numRecordsInVertex; i++)
778 NS_LOG_LOGIC (
"Found a Stub record to " << l->GetLinkId ());
797 else if (l->GetLinkType () ==
881 <<
"return false, but it does now!");
1064 " goes through next hop " << nextHop <<
1065 " via outgoing interface " << outIf <<
1066 " with distance " << distance);
1076 w_lsa->GetNetworkLSANetworkMask () );
1084 " via outgoing interface " << outIf <<
1085 " with distance " << distance);
1113 " goes through next hop " << nextHop <<
1114 " via outgoing interface " << outIf);
1169 bool found_prev_link =
false;
1178 found_prev_link =
true;
1198 if (!found_prev_link)
1200 NS_LOG_LOGIC (
"Skipping links before prev_link found");
1201 found_prev_link =
true;
1278 NS_LOG_WARN (
"all nodes should have at least one transit link:" << root );
1291 NS_LOG_LOGIC (
"TBD: Would have inserted default for transit");
1301 for (uint32_t j = 0; j < nLinkRecords; ++j)
1321 NS_LOG_LOGIC (
"Inserting default route for node " << myRouterId <<
" to next hop " <<
1363 NS_LOG_LOGIC (
"Starting SPFCalculate for node " << root);
1374 NS_LOG_LOGIC (
"SPFCalculate truncated for stub node " << root);
1403 if (candidate.
Size () == 0)
1417 v = candidate.
Pop ();
1503 NS_LOG_LOGIC (
"Processing external for destination " <<
1513 NS_LOG_LOGIC (
"Found advertising router to destination");
1521 NS_LOG_LOGIC (
"Vertex's child " << i <<
" not yet processed, processing...");
1561 for (; i != listEnd; i++)
1581 NS_LOG_LOGIC (
"Considering router " << rtr->GetRouterId ());
1583 if (rtr->GetRouterId () == routerId)
1593 "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
1594 "QI for <Ipv4> interface failed");
1602 "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
1603 "Expected valid LSA in SPFVertex* v");
1634 int32_t outIf = exit.second;
1637 gr->AddASExternalRouteTo (tempip, tempmask, nextHop, outIf);
1639 " add external network route to " << tempip <<
1640 " using next hop " << nextHop <<
1641 " via interface " << outIf);
1646 " NOT able to add network route to " << tempip <<
1647 " using next hop " << nextHop <<
1648 " since outgoing interface id is negative");
1677 NS_LOG_LOGIC (
"Found a Stub record to " << l->GetLinkId ());
1700 "GlobalRouteManagerImpl::SPFIntraAddStub (): Root pointer not set");
1730 for (; i != listEnd; i++)
1752 NS_LOG_LOGIC (
"Considering router " << rtr->GetRouterId ());
1754 if (rtr->GetRouterId () == routerId)
1764 "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
1765 "QI for <Ipv4> interface failed");
1773 "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
1774 "Expected valid LSA in SPFVertex* v");
1805 int32_t outIf = exit.second;
1808 gr->AddNetworkRouteTo (tempip, tempmask, nextHop, outIf);
1810 " add network route to " << tempip <<
1811 " using next hop " << nextHop <<
1812 " via interface " << outIf);
1817 " NOT able to add network route to " << tempip <<
1818 " using next hop " << nextHop <<
1819 " since outgoing interface id is negative");
1854 for (; i != listEnd; i++)
1869 if (rtr->GetRouterId () == routerId)
1879 "GlobalRouteManagerImpl::FindOutgoingInterfaceId (): "
1880 "GetObject for <Ipv4> interface failed");
1886 int32_t
interface = ipv4->GetInterfaceForPrefix (a, amask);
1891 NS_FATAL_ERROR (
"GlobalRouteManagerImpl::FindOutgoingInterfaceId(): "
1892 "Expected an interface associated with address a:" << a);
1901 NS_LOG_LOGIC (
"FindOutgoingInterfaceId():Can't find root node " << routerId);
1927 "GlobalRouteManagerImpl::SPFIntraAddRouter (): Root pointer not set");
1945 for (; i != listEnd; i++)
1967 NS_LOG_LOGIC (
"Considering router " << rtr->GetRouterId ());
1969 if (rtr->GetRouterId () == routerId)
1979 "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
1980 "GetObject for <Ipv4> interface failed");
1989 "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
1990 "Expected valid LSA in SPFVertex* v");
2002 " found " << nLinkRecords <<
" link records in LSA " << lsa <<
"with LinkStateId "<< lsa->
GetLinkStateId ());
2003 for (uint32_t j = 0; j < nLinkRecords; ++j)
2040 int32_t outIf = exit.second;
2047 " using next hop " << nextHop <<
2048 " and outgoing interface " << outIf);
2053 " NOT able to add host route to " << lr->
GetLinkData () <<
2054 " using next hop " << nextHop <<
2055 " since outgoing interface id is negative " << outIf);
2072 "GlobalRouteManagerImpl::SPFIntraAddTransit (): Root pointer not set");
2090 for (; i != listEnd; i++)
2112 NS_LOG_LOGIC (
"Considering router " << rtr->GetRouterId ());
2114 if (rtr->GetRouterId () == routerId)
2124 "GlobalRouteManagerImpl::SPFIntraAddTransit (): "
2125 "GetObject for <Ipv4> interface failed");
2134 "GlobalRouteManagerImpl::SPFIntraAddTransit (): "
2135 "Expected valid LSA in SPFVertex* v");
2153 int32_t outIf = exit.second;
2157 gr->AddNetworkRouteTo (tempip, tempmask, nextHop, outIf);
2159 " add network route to " << tempip <<
2160 " using next hop " << nextHop <<
2161 " via interface " << outIf);
2166 " NOT able to add network route to " << tempip <<
2167 " using next hop " << nextHop <<
2168 " since outgoing interface id is negative " << outIf);
2189 for (uint32_t i=0;;)
2193 if ((parent = v->
GetParent (i++)) == 0)
break;
Ipv4Address GetLinkId(void) const
LSType GetLSType(void) const
Return the LSType field of the LSA.
int32_t FindOutgoingInterfaceId(Ipv4Address a, Ipv4Mask amask=Ipv4Mask("255.255.255.255"))
GlobalRoutingLinkRecord * GetLinkRecord(uint32_t n) const
Return a pointer to the specified Global Routing Link Record.
#define NS_LOG_FUNCTION(parameters)
GlobalRoutingLSA * GetLSAByLinkData(Ipv4Address addr) const
Look up the Link State Advertisement associated with the given link state ID (address). This is a variation of the GetLSA call to allow the LSA to be found by matching addr with the LinkData field of the TransitNetwork link record.
ListOfSPFVertex_t m_parents
static uint32_t GetNNodes(void)
void SPFAddASExternal(GlobalRoutingLSA *extlsa, SPFVertex *v)
uint32_t m_distanceFromRoot
virtual void DeleteGlobalRoutes()
Delete all static routes on all nodes that have a GlobalRouterInterface.
const uint32_t SPF_INFINITY
void SetParent(SPFVertex *parent)
Set the pointer to the SPFVector that is the parent of "this" SPFVertex.
SPFVertex * Pop(void)
Pop the Shortest Path First Vertex pointer at the top of the queue.
a class to represent an Ipv4 address mask
~SPFVertex()
Destroy an SPFVertex (Shortest Path First Vertex).
void SPFIntraAddRouter(SPFVertex *v)
GlobalRouteManagerLSDB * m_lsdb
#define NS_ASSERT(condition)
void ProcessASExternals(SPFVertex *v, GlobalRoutingLSA *extlsa)
uint32_t GetNumExtLSAs() const
#define NS_LOG_COMPONENT_DEFINE(name)
std::list< SPFVertex * > ListOfSPFVertex_t
void SPFIntraAddStub(GlobalRoutingLinkRecord *l, SPFVertex *v)
Ipv4Address CombineMask(Ipv4Mask const &mask) const
Combine this address with a network mask.
void InheritAllRootExitDirections(const SPFVertex *vertex)
Inherit all root exit directions from a given vertex to 'this' vertex.
void SPFProcessStubs(SPFVertex *v)
void MergeParent(const SPFVertex *v)
Merge the Parent list from the v into this vertex.
std::vector< GlobalRoutingLSA * > m_extdatabase
Vertex used in shortest path first (SPF) computations. See RFC 2328, Section 16.
GlobalRoutingLinkRecord * SPFGetNextLink(SPFVertex *v, SPFVertex *w, GlobalRoutingLinkRecord *prev_link)
SPFVertex()
Construct an empty ("uninitialized") SPFVertex (Shortest Path First Vertex).
void SetDistanceFromRoot(uint32_t distance)
Set the distance from the root vertex to "this" SPFVertex object.
Ipv4Mask GetNetworkLSANetworkMask(void) const
For a Network LSA, get the Network Mask field that precedes the list of attached routers.
uint32_t GetSystemId(void) const
uint32_t Size(void) const
Return the number of Shortest Path First Vertex pointers presently stored in the Candidate Queue...
#define NS_FATAL_ERROR(msg)
fatal error handling
Ipv4Address GetAdvertisingRouter(void) const
Get the Advertising Router as defined by the OSPF spec. We always set it to the router ID of the rout...
ListOfNodeExit_t m_ecmpRootExits
store the multiple root's exits for supporting ECMP
A single link record for a link state advertisement.
A Candidate Queue used in static routing.
a Link State Advertisement (LSA) for a router, used in global routing.
ListOfSPFVertex_t m_children
uint32_t GetNChildren(void) const
Get the number of children of "this" SPFVertex.
std::pair< Ipv4Address, int32_t > NodeExit_t
std::pair< Ipv4Address, GlobalRoutingLSA * > LSDBPair_t
GlobalRoutingLSA * GetExtLSA(uint32_t index) const
void Initialize()
Set all LSA flags to an initialized state, for SPF computation.
~GlobalRouteManagerLSDB()
Destroy an empty Global Router Manager Link State Database.
static Iterator End(void)
void DebugSPFCalculate(Ipv4Address root)
Debugging routine; call the core SPF from the unit tests.
std::list< NodeExit_t > ListOfNodeExit_t
uint32_t GetDistanceFromRoot(void) const
Get the distance from the root vertex to "this" SPFVertex object.
SPFStatus GetStatus(void) const
Get the SPF status of the advertisement.
void SPFIntraAddTransit(SPFVertex *v)
#define NS_LOG_LOGIC(msg)
virtual void InitializeRoutes()
Compute routes using a Dijkstra SPF computation and populate per-node forwarding tables.
GlobalRoutingLSA * GetLSA(void) const
Get the Global Router Link State Advertisement returned by the Global Router represented by this SPFV...
Access to the Ipv4 forwarding table, interfaces, and configuration.
std::ostream & operator<<(std::ostream &os, const Angles &a)
void Push(SPFVertex *vNew)
Push a Shortest Path First Vertex pointer onto the queue according to the priority scheme...
void SetVertexType(VertexType type)
Set the Vertex Type field of a SPFVertex object.
void SetStatus(SPFStatus status)
Set the SPF status of the advertisement.
std::vector< Ptr< Node > >::const_iterator Iterator
void DebugUseLsdb(GlobalRouteManagerLSDB *)
Debugging routine; allow client code to supply a pre-built LSDB.
int SPFNexthopCalculation(SPFVertex *v, SPFVertex *w, GlobalRoutingLinkRecord *l, uint32_t distance)
void SetLSA(GlobalRoutingLSA *lsa)
Set the Global Router Link State Advertisement returned by the Global Router represented by this SPFV...
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 SetVertexId(Ipv4Address id)
Set the Vertex ID field of a SPFVertex object.
uint32_t GetNAttachedRouters(void) const
Return the number of attached routers listed in the NetworkLSA.
uint32_t GetNLinkRecords(void) const
Return the number of Global Routing Link Records in the LSA.
GlobalRoutingLSA * GetLSA(Ipv4Address addr) const
Look up the Link State Advertisement associated with the given link state ID (address).
void Insert(Ipv4Address addr, GlobalRoutingLSA *lsa)
Insert an IP address / Link State Advertisement pair into the Link State Database.
static Ipv4Address GetZero(void)
bool CheckForStubNode(Ipv4Address root)
An interface aggregated to a node to provide global routing info.
void MergeRootExitDirections(const SPFVertex *vertex)
Merge into 'this' vertex the list of exit directions from another vertex.
Ipv4Address GetLinkData(void) const
Get the Link Data field of the Global Routing Link Record.
#define NS_ASSERT_MSG(condition, message)
uint32_t GetNRootExitDirections() const
Get the number of exit directions from root for reaching 'this' vertex.
virtual ~GlobalRouteManagerImpl()
Ipv4 addresses are stored in host order in this class.
SPFVertex * Find(const Ipv4Address addr) const
Searches the Candidate Queue for a Shortest Path First Vertex pointer that points to a vertex having ...
uint32_t GetId(void) const
static uint32_t GetSystemId()
void SPFNext(SPFVertex *, CandidateQueue &)
static Iterator Begin(void)
SPFVertex * GetParent(uint32_t i=0) const
Get a pointer to the SPFVector that is the parent of "this" SPFVertex.
NodeExit_t GetRootExitDirection() const
Obtain a pair indicating the exit direction from the root.
void ClearVertexProcessed(void)
VertexType GetVertexType(void) const
Get the Vertex Type field of a SPFVertex object.
void SPFCalculate(Ipv4Address root)
The Link State DataBase (LSDB) of the Global Route Manager.
void SetVertexProcessed(bool value)
Set the value of the VertexProcessed flag.
VertexType
Enumeration of the possible types of SPFVertex objects.
Ipv4Address GetAttachedRouter(uint32_t n) const
Return an Ipv4Address corresponding to the specified attached router.
virtual void BuildGlobalRoutingDatabase()
Build the routing database by gathering Link State Advertisements from each node exporting a GlobalRo...
Ptr< Node > GetNode(void) const
Get the Node pointer of the node that originated this LSA.
void Reorder(void)
Reorders the Candidate Queue according to the priority scheme.
LinkType GetLinkType(void) const
Get the Link Type field of the Global Routing Link Record.
GlobalRouteManagerLSDB()
Construct an empty Global Router Manager Link State Database.
NodeExit_t GetRootExitDirection(uint32_t i) const
Obtain a pair indicating the exit direction from the root.
bool IsVertexProcessed(void) const
Check the value of the VertexProcessed flag.
Ptr< T > GetObject(void) const
uint16_t GetMetric(void) const
Get the Metric Data field of the Global Routing Link Record.
Ipv4Address GetVertexId(void) const
Get the Vertex ID field of a SPFVertex object.
SPFVertex * GetChild(uint32_t n) const
Get a borrowed SPFVertex pointer to the specified child of "this" SPFVertex.
Ipv4Address GetLinkStateId(void) const
Get the Link State ID as defined by the OSPF spec. We always set it to the router ID of the router ma...
void SPFVertexAddParent(SPFVertex *v)
uint32_t AddChild(SPFVertex *child)
Get a borrowed SPFVertex pointer to the specified child of "this" SPFVertex.