bug 521. Ipv4 global routing inefficient. Updated Tom's patch
authorCraig Dowell <craigdo@ee.washington.edu>
Tue, 30 Jun 2009 23:15:04 -0700
changeset 4628 a5a8c44e4240
parent 4627 d132345b3e10
child 4629 2dddadf4248c
child 4630 b72cd6ed9862
bug 521. Ipv4 global routing inefficient. Updated Tom's patch
src/routing/global-routing/global-route-manager-impl.cc
src/routing/global-routing/global-route-manager-impl.h
src/routing/global-routing/global-router-interface.cc
src/routing/global-routing/global-router-interface.h
src/routing/global-routing/ipv4-global-routing.cc
--- 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))