bug 521. Ipv4 global routing inefficient. Updated Tom's patch
--- a/src/routing/global-routing/global-route-manager-impl.cc Tue Jun 30 10:31:11 2009 -0700
+++ b/src/routing/global-routing/global-route-manager-impl.cc Tue Jun 30 23:15:04 2009 -0700
@@ -1000,6 +1000,93 @@
SPFCalculate (root);
}
+//
+// Used to 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
+//
+bool
+GlobalRouteManagerImpl::CheckForStubNode (Ipv4Address root)
+{
+ NS_LOG_FUNCTION (root);
+ GlobalRoutingLSA *rlsa = m_lsdb->GetLSA (root);
+ Ipv4Address myRouterId = rlsa->GetLinkStateId ();
+ int transits = 0;
+ GlobalRoutingLinkRecord *transitLink;
+ for (uint32_t i = 0; i < rlsa->GetNLinkRecords (); i++)
+ {
+ GlobalRoutingLinkRecord *l = rlsa->GetLinkRecord (i);
+ if (l->GetLinkType () == GlobalRoutingLinkRecord::TransitNetwork)
+ {
+ transits++;
+ transitLink = l;
+ }
+ else if (l->GetLinkType () == GlobalRoutingLinkRecord::PointToPoint)
+ {
+ transits++;
+ transitLink = l;
+ }
+ }
+ if (transits == 0)
+ {
+ // This router is not connected to any router. Probably, global
+ // routing should not be called for this node, but we can just raise
+ // a warning here and return true.
+ NS_LOG_WARN ("all nodes should have at least one transit link:" << root );
+ return true;
+ }
+ if (transits == 1)
+ {
+ if (transitLink->GetLinkType () == GlobalRoutingLinkRecord::TransitNetwork)
+ {
+ // Install default route to next hop router
+ // What is the next hop? We need to check all neighbors on the link.
+ // If there is a single router that has two transit links, then
+ // that is the default next hop. If there are more than one
+ // routers on link with multiple transit links, return false.
+ // Not yet implemented, so simply return false
+ NS_LOG_LOGIC ("TBD: Would have inserted default for transit");
+ return false;
+ }
+ else if (transitLink->GetLinkType () == GlobalRoutingLinkRecord::PointToPoint)
+ {
+ // Install default route to next hop
+ // The link record LinkID is the router ID of the peer.
+ // The Link Data is the local IP interface address
+ GlobalRoutingLSA *w_lsa = m_lsdb->GetLSA (transitLink->GetLinkId ());
+ uint32_t nLinkRecords = w_lsa->GetNLinkRecords ();
+ for (uint32_t j = 0; j < nLinkRecords; ++j)
+ {
+ //
+ // We are only concerned about point-to-point links
+ //
+ GlobalRoutingLinkRecord *lr = w_lsa->GetLinkRecord (j);
+ if (lr->GetLinkType () != GlobalRoutingLinkRecord::PointToPoint)
+ {
+ continue;
+ }
+ // Find the link record that corresponds to our routerId
+ if (lr->GetLinkId () == myRouterId)
+ {
+ // Next hop is stored in the LinkID field of lr
+ Ptr<GlobalRouter> router = rlsa->GetNode ()->GetObject<GlobalRouter> ();
+ NS_ASSERT (router);
+ Ptr<Ipv4GlobalRouting> gr = router->GetRoutingProtocol ();
+ NS_ASSERT (gr);
+ gr->AddNetworkRouteTo (Ipv4Address ("0.0.0.0"), Ipv4Mask ("0.0.0.0"), lr->GetLinkData (),
+ FindOutgoingInterfaceId (transitLink->GetLinkData ()));
+ NS_LOG_LOGIC ("Inserting default route for node " << myRouterId << " to next hop " <<
+ lr->GetLinkData () << " via interface " <<
+ FindOutgoingInterfaceId(transitLink->GetLinkData()));
+ return true;
+ }
+ }
+ }
+ }
+ return false;
+}
+
// quagga ospf_spf_calculate
void
GlobalRouteManagerImpl::SPFCalculate (Ipv4Address root)
@@ -1033,6 +1120,20 @@
v->GetLSA ()->SetStatus (GlobalRoutingLSA::LSA_SPF_IN_SPFTREE);
NS_LOG_LOGIC ("Starting SPFCalculate for node " << root);
+//
+// Optimize SPF calculation, for ns-3.
+// We do not need to calculate SPF for every node in the network if this
+// node has only one interface through which another router can be
+// reached. Instead, short-circuit this computation and just install
+// a default route in the CheckForStubNode() method.
+//
+ if (NodeList::GetNNodes () > 0 && CheckForStubNode (root))
+ {
+ NS_LOG_LOGIC ("SPFCalculate truncated for stub node " << root);
+ delete m_spfroot;
+ return;
+ }
+
for (;;)
{
//
--- a/src/routing/global-routing/global-route-manager-impl.h Tue Jun 30 10:31:11 2009 -0700
+++ b/src/routing/global-routing/global-route-manager-impl.h Tue Jun 30 23:15:04 2009 -0700
@@ -772,6 +772,7 @@
SPFVertex* m_spfroot;
GlobalRouteManagerLSDB* m_lsdb;
+ bool CheckForStubNode (Ipv4Address root);
void SPFCalculate (Ipv4Address root);
void SPFProcessStubs (SPFVertex* v);
void SPFNext (SPFVertex*, CandidateQueue&);
--- a/src/routing/global-routing/global-router-interface.cc Tue Jun 30 10:31:11 2009 -0700
+++ b/src/routing/global-routing/global-router-interface.cc Tue Jun 30 23:15:04 2009 -0700
@@ -24,6 +24,7 @@
#include "ns3/channel.h"
#include "ns3/net-device.h"
#include "ns3/node.h"
+#include "ns3/node-list.h"
#include "ns3/ipv4.h"
#include "ns3/bridge-net-device.h"
#include "ipv4-global-routing.h"
@@ -140,7 +141,8 @@
m_linkRecords(),
m_networkLSANetworkMask("0.0.0.0"),
m_attachedRouters(),
- m_status(GlobalRoutingLSA::LSA_SPF_NOT_EXPLORED)
+ m_status(GlobalRoutingLSA::LSA_SPF_NOT_EXPLORED),
+ m_node_id(0)
{
NS_LOG_FUNCTION_NOARGS ();
}
@@ -156,7 +158,8 @@
m_linkRecords(),
m_networkLSANetworkMask("0.0.0.0"),
m_attachedRouters(),
- m_status(status)
+ m_status(status),
+ m_node_id(0)
{
NS_LOG_FUNCTION (this << status << linkStateId << advertisingRtr);
}
@@ -165,7 +168,8 @@
: m_lsType(lsa.m_lsType), m_linkStateId(lsa.m_linkStateId),
m_advertisingRtr(lsa.m_advertisingRtr),
m_networkLSANetworkMask(lsa.m_networkLSANetworkMask),
- m_status(lsa.m_status)
+ m_status(lsa.m_status),
+ m_node_id(lsa.m_node_id)
{
NS_LOG_FUNCTION_NOARGS ();
NS_ASSERT_MSG(IsEmpty(),
@@ -182,6 +186,7 @@
m_advertisingRtr = lsa.m_advertisingRtr;
m_networkLSANetworkMask = lsa.m_networkLSANetworkMask,
m_status = lsa.m_status;
+ m_node_id = lsa.m_node_id;
ClearLinkRecords ();
CopyLinkRecords (lsa);
@@ -380,6 +385,20 @@
m_status = status;
}
+ Ptr<Node>
+GlobalRoutingLSA::GetNode (void) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ return NodeList::GetNode (m_node_id);
+}
+
+ void
+GlobalRoutingLSA::SetNode (Ptr<Node> node)
+{
+ NS_LOG_FUNCTION (node);
+ m_node_id = node->GetId ();
+}
+
void
GlobalRoutingLSA::Print (std::ostream &os) const
{
@@ -582,6 +601,7 @@
pLSA->SetLinkStateId (m_routerId);
pLSA->SetAdvertisingRouter (m_routerId);
pLSA->SetStatus (GlobalRoutingLSA::LSA_SPF_NOT_EXPLORED);
+ pLSA->SetNode (node);
//
// Ask the node for the number of net devices attached. This isn't necessarily
@@ -1123,6 +1143,7 @@
pLSA->SetAdvertisingRouter (m_routerId);
pLSA->SetNetworkLSANetworkMask (maskLocal);
pLSA->SetStatus (GlobalRoutingLSA::LSA_SPF_NOT_EXPLORED);
+ pLSA->SetNode (node);
//
// Build a list of AttachedRouters by walking the devices in the channel
--- a/src/routing/global-routing/global-router-interface.h Tue Jun 30 10:31:11 2009 -0700
+++ b/src/routing/global-routing/global-router-interface.h Tue Jun 30 23:15:04 2009 -0700
@@ -477,6 +477,18 @@
*/
void SetStatus (SPFStatus status);
+/**
+ * @brief Get the Node pointer of the node that originated this LSA
+ * @returns Node pointer
+ */
+ Ptr<Node> GetNode (void) const;
+
+/**
+ * @brief Set the Node pointer of the node that originated this LSA
+ * @param node Node pointer
+ */
+ void SetNode (Ptr<Node> node);
+
private:
/**
* The type of the LSA. Each LSA type has a separate advertisement
@@ -545,6 +557,7 @@
* proper position in the tree.
*/
SPFStatus m_status;
+ uint32_t m_node_id;
};
std::ostream& operator<< (std::ostream& os, GlobalRoutingLSA& lsa);
--- a/src/routing/global-routing/ipv4-global-routing.cc Tue Jun 30 10:31:11 2009 -0700
+++ b/src/routing/global-routing/ipv4-global-routing.cc Tue Jun 30 23:15:04 2009 -0700
@@ -125,7 +125,7 @@
j != m_networkRoutes.end ();
j++)
{
- NS_ASSERT ((*j)->IsNetwork ());
+ NS_ASSERT ((*j)->IsNetwork () || (*j)->IsDefault ());
Ipv4Mask mask = (*j)->GetDestNetworkMask ();
Ipv4Address entry = (*j)->GetDestNetwork ();
if (mask.IsMatch (dest, entry))