internet: (fixes #2102) Make global routing robust to bridged links
authorChip Webb <ns3@chipwebb.com>
Thu, 10 Mar 2016 16:06:22 -0800
changeset 12017 8495f6496ae2
parent 12016 ebf575fd18e5
child 12018 1fd617b55ca1
internet: (fixes #2102) Make global routing robust to bridged links
src/internet/model/global-router-interface.cc
src/internet/model/global-router-interface.h
--- a/src/internet/model/global-router-interface.cc	Thu Mar 10 14:16:31 2016 -0800
+++ b/src/internet/model/global-router-interface.cc	Thu Mar 10 16:06:22 2016 -0800
@@ -791,7 +791,8 @@
   // this is a stub network.  If we find another router, then what we have here
   // is a transit network.
   //
-  if (AnotherRouterOnLink (nd, true) == false)
+  ClearBridgesVisited ();
+  if (AnotherRouterOnLink (nd) == false)
     {
       //
       // This is a net device connected to a stub network
@@ -830,7 +831,8 @@
       // gets the IP interface address of the designated router in this 
       // case.
       //
-      Ipv4Address desigRtr = FindDesignatedRouterForLink (nd, true);
+      ClearBridgesVisited ();
+      Ipv4Address desigRtr = FindDesignatedRouterForLink (nd);
 
       //
       // Let's double-check that any designated router we find out on our
@@ -926,7 +928,8 @@
       // by the presence of another router on the network segment.  If we find
       // another router on any of our bridged links, we are a transit network.
       //
-      if (AnotherRouterOnLink (ndTemp, true))
+      ClearBridgesVisited ();
+      if (AnotherRouterOnLink (ndTemp))
         {
           areTransitNetwork = true;
 
@@ -937,7 +940,8 @@
           // for the lowest address on each segment and pick the lowest of them
           // all.
           //
-          Ipv4Address desigRtrTemp = FindDesignatedRouterForLink (ndTemp, true);
+          ClearBridgesVisited ();
+          Ipv4Address desigRtrTemp = FindDesignatedRouterForLink (ndTemp);
 
           //
           // Let's double-check that any designated router we find out on our
@@ -1243,9 +1247,9 @@
 // connecting to the channel becomes the designated router for the link.
 //
 Ipv4Address
-GlobalRouter::FindDesignatedRouterForLink (Ptr<NetDevice> ndLocal, bool allowRecursion) const
+GlobalRouter::FindDesignatedRouterForLink (Ptr<NetDevice> ndLocal) const
 {
-  NS_LOG_FUNCTION (this << ndLocal << allowRecursion);
+  NS_LOG_FUNCTION (this << ndLocal);
 
   Ptr<Channel> ch = ndLocal->GetChannel ();
   uint32_t nDevices = ch->GetNDevices ();
@@ -1282,6 +1286,15 @@
           NS_LOG_LOGIC ("Device is bridged by BridgeNetDevice " << bnd);
 
           //
+          // When enumerating a bridge, don't count the netdevice we came in on
+          //
+          if (ndLocal == ndOther)
+            {
+              NS_LOG_LOGIC ("Skip -- it is where we came from.");
+              continue;
+            }
+
+          //
           // It is possible that the bridge net device is sitting under a
           // router, so we have to check for the presence of that router
           // before we run off and follow all the links
@@ -1315,6 +1328,19 @@
                 }
             }
 
+          // 
+          // Check if we have seen this bridge net device already while
+          // recursively enumerating an L2 broadcast domain. If it is new 
+          // to us, go ahead and process it. If we have already processed it,
+          // move to the next
+          // 
+          if(BridgeHasAlreadyBeenVisited(bnd))
+            {
+              NS_ABORT_MSG ("ERROR: L2 forwarding loop detected!");
+            }
+
+          MarkBridgeAsVisited(bnd);
+
           NS_LOG_LOGIC ("Looking through bridge ports of bridge net device " << bnd);
           for (uint32_t j = 0; j < bnd->GetNBridgePorts (); ++j)
             {
@@ -1326,13 +1352,10 @@
                   continue;
                 }
 
-              if (allowRecursion)
-                {
-                  NS_LOG_LOGIC ("Recursively looking for routers down bridge port " << ndBridged);
-                  Ipv4Address addrOther = FindDesignatedRouterForLink (ndBridged, false);
-                  desigRtr = addrOther < desigRtr ? addrOther : desigRtr;
-                  NS_LOG_LOGIC ("designated router now " << desigRtr);
-                }
+              NS_LOG_LOGIC ("Recursively looking for routers down bridge port " << ndBridged);
+              Ipv4Address addrOther = FindDesignatedRouterForLink (ndBridged);
+              desigRtr = addrOther < desigRtr ? addrOther : desigRtr;
+              NS_LOG_LOGIC ("designated router now " << desigRtr);
             }
         }
       else
@@ -1380,9 +1403,9 @@
 // when there is a bridged net device on the other side.
 //
 bool
-GlobalRouter::AnotherRouterOnLink (Ptr<NetDevice> nd, bool allowRecursion) const
+GlobalRouter::AnotherRouterOnLink (Ptr<NetDevice> nd) const
 {
-  NS_LOG_FUNCTION (this << nd << allowRecursion);
+  NS_LOG_FUNCTION (this << nd);
 
   Ptr<Channel> ch = nd->GetChannel ();
   if (!ch)
@@ -1426,6 +1449,20 @@
       if (bnd)
         {
           NS_LOG_LOGIC ("Device is bridged by net device " << bnd);
+
+          // 
+          // Check if we have seen this bridge net device already while
+          // recursively enumerating an L2 broadcast domain. If it is new 
+          // to us, go ahead and process it. If we have already processed it,
+          // move to the next
+          // 
+          if(BridgeHasAlreadyBeenVisited(bnd))
+            {
+              NS_ABORT_MSG ("ERROR: L2 forwarding loop detected!");
+            }
+
+          MarkBridgeAsVisited(bnd);
+
           NS_LOG_LOGIC ("Looking through bridge ports of bridge net device " << bnd);
           for (uint32_t j = 0; j < bnd->GetNBridgePorts (); ++j)
             {
@@ -1437,14 +1474,11 @@
                   continue;
                 }
 
-              if (allowRecursion)
+              NS_LOG_LOGIC ("Recursively looking for routers on bridge port " << ndBridged);
+              if (AnotherRouterOnLink (ndBridged))
                 {
-                  NS_LOG_LOGIC ("Recursively looking for routers on bridge port " << ndBridged);
-                  if (AnotherRouterOnLink (ndBridged, false))
-                    {
-                      NS_LOG_LOGIC ("Found routers on bridge port, return true");
-                      return true;
-                    }
+                  NS_LOG_LOGIC ("Found routers on bridge port, return true");
+                  return true;
                 }
             }
           NS_LOG_LOGIC ("No routers on bridged net device, return false");
@@ -1699,4 +1733,40 @@
   return 0;
 }
 
+//
+// Start a new enumeration of an L2 broadcast domain by clearing m_bridgesVisited
+//
+void 
+GlobalRouter::ClearBridgesVisited (void) const
+{
+  m_bridgesVisited.clear();
+}
+
+//
+// Check if we have already visited a given bridge net device by searching m_bridgesVisited
+//
+bool
+GlobalRouter::BridgeHasAlreadyBeenVisited (Ptr<BridgeNetDevice> bridgeNetDevice) const
+{
+  std::vector<Ptr<BridgeNetDevice> >::iterator iter;
+  for (iter = m_bridgesVisited.begin (); iter != m_bridgesVisited.end (); ++iter)
+    {
+      if (bridgeNetDevice == *iter)
+        {
+          return true;
+        }
+    }
+  return false;
+}
+
+//
+// Remember that we visited a bridge net device by adding it to m_bridgesVisited
+//
+void 
+GlobalRouter::MarkBridgeAsVisited (Ptr<BridgeNetDevice> bridgeNetDevice) const
+{
+  m_bridgesVisited.push_back (bridgeNetDevice);
+}
+
+
 } // namespace ns3
--- a/src/internet/model/global-router-interface.h	Thu Mar 10 14:16:31 2016 -0800
+++ b/src/internet/model/global-router-interface.h	Thu Mar 10 16:06:22 2016 -0800
@@ -766,24 +766,21 @@
    * connecting to the channel becomes the designated router for the link.
    *
    * \param ndLocal local NetDevice to scan
-   * \param allowRecursion Recursively look for routers down bridge port
    * \returns the IP address of the designated router
    */
-  Ipv4Address FindDesignatedRouterForLink (Ptr<NetDevice> ndLocal, bool allowRecursion) const;
+  Ipv4Address FindDesignatedRouterForLink (Ptr<NetDevice> ndLocal) const;
 
   /**
    * \brief Checks for the presence of another router on the NetDevice
    *
    * Given a node and an attached net device, take a look off in the channel to
    * which the net device is attached and look for a node on the other side
-   * that has a GlobalRouter interface aggregated.  Life gets more complicated
-   * when there is a bridged net device on the other side.
+   * that has a GlobalRouter interface aggregated.  
    *
    * \param nd NetDevice to scan
-   * \param allowRecursion Recursively look for routers down bridge port
    * \returns true if a router is found
    */
-  bool AnotherRouterOnLink (Ptr<NetDevice> nd, bool allowRecursion) const;
+  bool AnotherRouterOnLink (Ptr<NetDevice> nd) const;
 
   /**
    * \brief Process a generic broadcast link
@@ -848,6 +845,29 @@
   typedef std::list<Ipv4RoutingTableEntry *>::iterator InjectedRoutesI; //!< Iterator to container of Ipv4RoutingTableEntry
   InjectedRoutes m_injectedRoutes; //!< Routes we are exporting
 
+  // Declared mutable so that const member functions can clear it
+  // (supporting the logical constness of the search methods of this class) 
+  mutable std::vector<Ptr<BridgeNetDevice> > m_bridgesVisited;
+  /**
+   * Clear the list of bridges visited on the link 
+   */
+  void ClearBridgesVisited (void) const;
+  /**
+   * When recursively checking for devices on the link, check whether a
+   * given device has already been visited.
+   *
+   * \param device the bridge device to check
+   * \return true if bridge has already been visited 
+   */
+  bool BridgeHasAlreadyBeenVisited (Ptr<BridgeNetDevice> device) const;
+  /**
+   * When recursively checking for devices on the link, mark a given device 
+   * as having been visited.
+   *
+   * \param device the bridge device to mark
+   */
+  void MarkBridgeAsVisited (Ptr<BridgeNetDevice> device) const;
+
   // inherited from Object
   virtual void DoDispose (void);