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"
57 os <<
"(" << exit.first <<
" ," << exit.second <<
")";
64 typedef SPFVertex::ListOfSPFVertex_t::const_iterator CIter_t;
66 for (CIter_t iter = vs.begin (); iter != vs.end ();)
68 os << (*iter)->m_vertexId;
69 if (++iter != vs.end ())
89 m_vertexType (VertexUnknown),
90 m_vertexId (
"255.255.255.255"),
94 m_nextHop (
"0.0.0.0"),
97 m_vertexProcessed (false)
103 m_vertexId (lsa->GetLinkStateId ()),
107 m_nextHop (
"0.0.0.0"),
110 m_vertexProcessed (false)
135 for (ListOfSPFVertex_t::iterator piter =
m_parents.begin ();
142 uint32_t orgCount = (*piter)->m_children.size ();
143 (*piter)->m_children.remove (
this);
144 uint32_t newCount = (*piter)->m_children.size ();
145 if (orgCount > newCount)
147 NS_ASSERT_MSG (orgCount > newCount,
"Unable to find the current vertex from its parents --- impossible!");
163 if (p == 0)
continue;
251 NS_LOG_LOGIC (
"Index to SPFVertex's parent is out-of-range.");
254 ListOfSPFVertex_t::const_iterator iter =
m_parents.begin ();
302 typedef ListOfNodeExit_t::const_iterator CIter_t;
306 while (i-- > 0) { iter++; }
330 extList.begin (), extList.end ());
344 NS_LOG_WARN (
"x root exit directions in this vertex are going to be discarded");
371 for ( ListOfSPFVertex_t::const_iterator i =
m_children.begin ();
434 LSDBMap_t::iterator i;
455 LSDBMap_t::iterator i;
498 LSDBMap_t::const_iterator i;
501 if (i->first == addr)
516 LSDBMap_t::const_iterator i;
583 uint32_t nRoutes = gr->GetNRoutes ();
584 NS_LOG_LOGIC (
"Deleting " << gr->GetNRoutes ()<<
" routes from node " << node->
GetId ());
588 for (j = 0; j < nRoutes; j++)
642 uint32_t numLSAs = rtr->DiscoverLSAs ();
645 for (uint32_t j = 0; j < numLSAs; ++j)
652 rtr->GetLSA (j, *lsa);
725 if (rtr && rtr->GetNumLSAs () )
754 uint32_t distance = 0;
755 uint32_t numRecordsInVertex = 0;
769 for (uint32_t i = 0; i < numRecordsInVertex; i++)
786 NS_LOG_LOGIC (
"Found a Stub record to " << l->GetLinkId ());
805 else if (l->GetLinkType () ==
889 <<
"return false, but it does now!");
1072 " goes through next hop " << nextHop <<
1073 " via outgoing interface " << outIf <<
1074 " with distance " << distance);
1084 w_lsa->GetNetworkLSANetworkMask () );
1092 " via outgoing interface " << outIf <<
1093 " with distance " << distance);
1121 " goes through next hop " << nextHop <<
1122 " via outgoing interface " << outIf);
1177 bool found_prev_link =
false;
1186 found_prev_link =
true;
1206 if (!found_prev_link)
1208 NS_LOG_LOGIC (
"Skipping links before prev_link found");
1209 found_prev_link =
true;
1286 NS_LOG_WARN (
"all nodes should have at least one transit link:" << root );
1299 NS_LOG_LOGIC (
"TBD: Would have inserted default for transit");
1309 for (uint32_t j = 0; j < nLinkRecords; ++j)
1329 NS_LOG_LOGIC (
"Inserting default route for node " << myRouterId <<
" to next hop " <<
1371 NS_LOG_LOGIC (
"Starting SPFCalculate for node " << root);
1382 NS_LOG_LOGIC (
"SPFCalculate truncated for stub node " << root);
1411 if (candidate.
Size () == 0)
1425 v = candidate.
Pop ();
1511 NS_LOG_LOGIC (
"Processing external for destination " <<
1521 NS_LOG_LOGIC (
"Found advertising router to destination");
1529 NS_LOG_LOGIC (
"Vertex's child " << i <<
" not yet processed, processing...");
1569 for (; i != listEnd; i++)
1589 NS_LOG_LOGIC (
"Considering router " << rtr->GetRouterId ());
1591 if (rtr->GetRouterId () == routerId)
1601 "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
1602 "QI for <Ipv4> interface failed");
1610 "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
1611 "Expected valid LSA in SPFVertex* v");
1642 int32_t outIf = exit.second;
1645 gr->AddASExternalRouteTo (tempip, tempmask, nextHop, outIf);
1647 " add external network route to " << tempip <<
1648 " using next hop " << nextHop <<
1649 " via interface " << outIf);
1654 " NOT able to add network route to " << tempip <<
1655 " using next hop " << nextHop <<
1656 " since outgoing interface id is negative");
1685 NS_LOG_LOGIC (
"Found a Stub record to " << l->GetLinkId ());
1708 "GlobalRouteManagerImpl::SPFIntraAddStub (): Root pointer not set");
1738 for (; i != listEnd; i++)
1760 NS_LOG_LOGIC (
"Considering router " << rtr->GetRouterId ());
1762 if (rtr->GetRouterId () == routerId)
1772 "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
1773 "QI for <Ipv4> interface failed");
1781 "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
1782 "Expected valid LSA in SPFVertex* v");
1813 int32_t outIf = exit.second;
1816 gr->AddNetworkRouteTo (tempip, tempmask, nextHop, outIf);
1818 " add network route to " << tempip <<
1819 " using next hop " << nextHop <<
1820 " via interface " << outIf);
1825 " NOT able to add network route to " << tempip <<
1826 " using next hop " << nextHop <<
1827 " since outgoing interface id is negative");
1862 for (; i != listEnd; i++)
1877 if (rtr->GetRouterId () == routerId)
1887 "GlobalRouteManagerImpl::FindOutgoingInterfaceId (): "
1888 "GetObject for <Ipv4> interface failed");
1894 int32_t
interface = ipv4->GetInterfaceForPrefix (a, amask);
1899 NS_FATAL_ERROR (
"GlobalRouteManagerImpl::FindOutgoingInterfaceId(): "
1900 "Expected an interface associated with address a:" << a);
1909 NS_LOG_LOGIC (
"FindOutgoingInterfaceId():Can't find root node " << routerId);
1935 "GlobalRouteManagerImpl::SPFIntraAddRouter (): Root pointer not set");
1953 for (; i != listEnd; i++)
1975 NS_LOG_LOGIC (
"Considering router " << rtr->GetRouterId ());
1977 if (rtr->GetRouterId () == routerId)
1987 "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
1988 "GetObject for <Ipv4> interface failed");
1997 "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
1998 "Expected valid LSA in SPFVertex* v");
2010 " found " << nLinkRecords <<
" link records in LSA " << lsa <<
"with LinkStateId "<< lsa->
GetLinkStateId ());
2011 for (uint32_t j = 0; j < nLinkRecords; ++j)
2048 int32_t outIf = exit.second;
2055 " using next hop " << nextHop <<
2056 " and outgoing interface " << outIf);
2061 " NOT able to add host route to " << lr->
GetLinkData () <<
2062 " using next hop " << nextHop <<
2063 " since outgoing interface id is negative " << outIf);
2080 "GlobalRouteManagerImpl::SPFIntraAddTransit (): Root pointer not set");
2098 for (; i != listEnd; i++)
2120 NS_LOG_LOGIC (
"Considering router " << rtr->GetRouterId ());
2122 if (rtr->GetRouterId () == routerId)
2132 "GlobalRouteManagerImpl::SPFIntraAddTransit (): "
2133 "GetObject for <Ipv4> interface failed");
2142 "GlobalRouteManagerImpl::SPFIntraAddTransit (): "
2143 "Expected valid LSA in SPFVertex* v");
2161 int32_t outIf = exit.second;
2165 gr->AddNetworkRouteTo (tempip, tempmask, nextHop, outIf);
2167 " add network route to " << tempip <<
2168 " using next hop " << nextHop <<
2169 " via interface " << outIf);
2174 " NOT able to add network route to " << tempip <<
2175 " using next hop " << nextHop <<
2176 " since outgoing interface id is negative " << outIf);
2197 for (uint32_t i=0;;)
2201 if ((parent = v->
GetParent (i++)) == 0)
break;
Ipv4Address GetLinkId(void) const
Get the Link ID field of the Global Routing Link Record.
Unused – for future OSPF compatibility.
LSType GetLSType(void) const
Return the LSType field of the LSA.
int32_t FindOutgoingInterfaceId(Ipv4Address a, Ipv4Mask amask=Ipv4Mask("255.255.255.255"))
Return the interface number corresponding to a given IP address and mask.
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).
ListOfSPFVertex_t m_parents
parent list
static uint32_t GetNNodes(void)
void SPFAddASExternal(GlobalRoutingLSA *extlsa, SPFVertex *v)
Add an external route to the routing tables.
uint32_t m_distanceFromRoot
Distance from root node.
virtual void DeleteGlobalRoutes()
Delete all static routes on all nodes that have a GlobalRouterInterface.
const uint32_t SPF_INFINITY
"infinite" distance between nodes
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)
Add a host route to the routing tables.
GlobalRouteManagerLSDB * m_lsdb
the Link State DataBase (LSDB) of the Global Route Manager
#define NS_ASSERT(condition)
void ProcessASExternals(SPFVertex *v, GlobalRoutingLSA *extlsa)
Process Autonomous Systems (AS) External LSA.
uint32_t GetNumExtLSAs() const
Get the number of External Link State Advertisements.
std::list< SPFVertex * > ListOfSPFVertex_t
container of SPFVertexes
void SPFIntraAddStub(GlobalRoutingLinkRecord *l, SPFVertex *v)
Add a stub to the routing tables.
VertexType m_vertexType
Vertex type.
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)
Process Stub nodes.
void MergeParent(const SPFVertex *v)
Merge the Parent list from the v into this vertex.
std::vector< GlobalRoutingLSA * > m_extdatabase
database of External Link State Advertisements
LSDBMap_t m_database
database of IPv4 addresses / Link State Advertisements
Vertex used in shortest path first (SPF) computations.
GlobalRoutingLinkRecord * SPFGetNextLink(SPFVertex *v, SPFVertex *w, GlobalRoutingLinkRecord *prev_link)
Search for a link between two vertexes.
SPFVertex()
Construct an empty ("uninitialized") SPFVertex (Shortest Path First Vertex).
GlobalRoutingLSA * m_lsa
Link State Advertisement.
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.
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...
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.
ListOfNodeExit_t m_ecmpRootExits
store the multiple root's exits for supporting ECMP
Record represents a leaf node network.
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
Children list.
uint32_t GetNChildren(void) const
Get the number of children of "this" SPFVertex.
std::pair< Ipv4Address, int32_t > NodeExit_t
IPv4 / interface container for exit nodes.
std::pair< Ipv4Address, GlobalRoutingLSA * > LSDBPair_t
pair of IPv4 addresses / Link State Advertisements
GlobalRoutingLSA * GetExtLSA(uint32_t index) const
Look up the External Link State Advertisement associated with the given index.
New vertex not yet considered.
void Initialize()
Set all LSA flags to an initialized state, for SPF computation.
uint32_t Get(void) const
Get the host-order 32-bit IP address.
~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
container of Exit nodes
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)
Add a transit to the routing tables.
#define NS_LOG_LOGIC(msg)
virtual void InitializeRoutes()
Compute routes using a Dijkstra SPF computation and populate per-node forwarding tables.
int32_t m_rootOif
root Output Interface
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.
Vertex is in the SPF candidate queue.
std::ostream & operator<<(std::ostream &os, const Angles &a)
print a struct Angles to output
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.
Ipv4Address m_vertexId
Vertex ID.
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)
Calculate nexthop from root through V (parent) to vertex W (destination) with given distance from roo...
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)
NS_LOG_COMPONENT_DEFINE("GlobalRouteManagerImpl")
bool CheckForStubNode(Ipv4Address root)
Test if a node is a stub, from an OSPF sense.
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.
Vertex representing a router in the topology.
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
Record representing a point to point channel.
static uint32_t GetSystemId()
static Iterator Begin(void)
Ipv4Address m_nextHop
next hop
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)
Clear the value of the VertexProcessed flag.
VertexType GetVertexType(void) const
Get the Vertex Type field of a SPFVertex object.
void SPFCalculate(Ipv4Address root)
Calculate the shortest path first (SPF) tree.
bool m_vertexProcessed
Flag to note whether vertex has been processed in stage two of SPF computation.
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.
SPFVertex * m_spfroot
the root node
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
Vertex representing a network in the topology.
Vertex is in the SPF tree.
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.
void SPFVertexAddParent(SPFVertex *v)
Adds a vertex to the list of children in each of its parents.
uint32_t AddChild(SPFVertex *child)
Get a borrowed SPFVertex pointer to the specified child of "this" SPFVertex.