Implementation of Ipv4GlobalRoutingUnroderedNexthops to manage multiple
independent sets of routing tables (e.g., for Path Splicing)
diff --git a/examples/ccnx-grid.cc b/examples/ccnx-grid.cc
index d9fbe76..0427ae2 100644
--- a/examples/ccnx-grid.cc
+++ b/examples/ccnx-grid.cc
@@ -28,7 +28,7 @@
#include <iostream>
#include <sstream>
-#include "ns3/visualizer-module.h"
+// #include "ns3/visualizer-module.h"
#include "ns3/ccnx.h"
using namespace ns3;
@@ -38,8 +38,8 @@
int
main (int argc, char *argv[])
{
- GlobalValue::Bind ("SimulatorImplementationType", StringValue
- ("ns3::VisualSimulatorImpl"));
+ // GlobalValue::Bind ("SimulatorImplementationType", StringValue
+ // ("ns3::VisualSimulatorImpl"));
uint32_t n = 3;
@@ -151,4 +151,4 @@
return 0;
-}
\ No newline at end of file
+}
diff --git a/examples/ccnx-routing-simple.cc b/examples/ccnx-routing-simple.cc
index 1172376..e277cfe 100644
--- a/examples/ccnx-routing-simple.cc
+++ b/examples/ccnx-routing-simple.cc
@@ -55,7 +55,8 @@
PointToPointHelper p2p;
InternetStackHelper stack;
- Ipv4GlobalRoutingHelper ipv4RoutingHelper ("ns3::Ipv4GlobalRoutingOrderedNexthops");
+ // Ipv4GlobalRoutingHelper ipv4RoutingHelper ("ns3::Ipv4GlobalRoutingOrderedNexthops");
+ Ipv4GlobalRoutingHelper ipv4RoutingHelper ("ns3::Ipv4GlobalRoutingUnorderedNexthops");
stack.SetRoutingHelper (ipv4RoutingHelper);
PointToPointGridHelper grid (nNodes, nNodes, p2p);
@@ -75,8 +76,9 @@
// // Create router nodes, initialize routing database and set up the routing
// // tables in the nodes.
// Ipv4GlobalRoutingHelper::PopulateRoutingTables ();
- Ipv4GlobalRoutingHelper::PopulateAllPossibleRoutingTables ();
-
+ // Ipv4GlobalRoutingHelper::PopulateAllPossibleRoutingTables ();
+ Ipv4GlobalRoutingHelper::PopulateRandomRoutingTables (5);
+
// testing ip routing
UdpEchoClientHelper client (Ipv4Address ("10.2.1.1"), 1029);
client.SetAttribute ("MaxPackets", UintegerValue (1));
diff --git a/model/ipv4-global-routing-unordered-nexthops.cc b/model/ipv4-global-routing-unordered-nexthops.cc
new file mode 100644
index 0000000..720be8d
--- /dev/null
+++ b/model/ipv4-global-routing-unordered-nexthops.cc
@@ -0,0 +1,311 @@
+// -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*-
+//
+// Copyright (c) 2008 University of Washington
+//
+// This program is free software; you can redistribute it and/or modify
+// it under the terms of the GNU General Public License version 2 as
+// published by the Free Software Foundation;
+//
+// This program is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public License
+// along with this program; if not, write to the Free Software
+// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+//
+
+#include "ns3/names.h"
+#include "ns3/node.h"
+#include "ns3/log.h"
+#include "ns3/simulator.h"
+#include "ns3/object.h"
+#include "ns3/packet.h"
+#include "ns3/net-device.h"
+#include "ns3/ipv4-route.h"
+#include "ipv4-global-routing-unordered-nexthops.h"
+
+#include <iomanip>
+
+NS_LOG_COMPONENT_DEFINE ("Ipv4GlobalRoutingUnorderedNexthops");
+
+namespace ns3 {
+
+NS_OBJECT_ENSURE_REGISTERED (Ipv4GlobalRoutingUnorderedNexthops);
+
+TypeId
+Ipv4GlobalRoutingUnorderedNexthops::GetTypeId (void)
+{
+ static TypeId tid = TypeId ("ns3::Ipv4GlobalRoutingUnorderedNexthops")
+ .SetParent<Ipv4GlobalRouting> ()
+ .AddConstructor<Ipv4GlobalRoutingUnorderedNexthops> ()
+ ;
+ return tid;
+}
+
+Ipv4GlobalRoutingUnorderedNexthops::Ipv4GlobalRoutingUnorderedNexthops ()
+: m_numLogicalEntries (1)
+{
+}
+
+void
+Ipv4GlobalRoutingUnorderedNexthops::FixRoutes ()
+{
+ for (Ipv4AddressTrieMap::iterator route = m_routes.begin ();
+ route != m_routes.end ();
+ route ++)
+ {
+ if (route->second->size () < m_numLogicalEntries)
+ {
+ NS_LOG_WARN ("Not all entries got a new routing entry. Making one based on previous set");
+ route->second->push_back (route->second->back ());
+ route->second->back ().SetMetric (UINT32_MAX); // just to ensure we have consistency across the sets
+ }
+ }
+ m_numLogicalEntries ++;
+}
+
+void
+Ipv4GlobalRoutingUnorderedNexthops::AddRouteTo (Ipv4Address dest,
+ Ipv4Mask destMask,
+ Ipv4Address nextHop,
+ uint32_t interface,
+ uint32_t metric/*=0*/)
+{
+ NS_LOG_FUNCTION (dest << destMask << nextHop << interface << metric);
+
+ // First, make sure we don't try to add route to ourselves
+ int32_t iface = m_ipv4->GetInterfaceForPrefix (dest, destMask);
+ NS_LOG_LOGIC ("Iface " << iface << " for " << dest);
+ if (destMask != Ipv4Mask::GetZero () && iface >= 0)
+ {
+ NS_LOG_LOGIC ("Do not add route to ourselves");
+ return;
+ }
+
+ // Second, there is no reason to add p2p route that equals to the next hop
+ if (destMask == Ipv4Mask::GetOnes () && dest == nextHop)
+ {
+ NS_LOG_LOGIC ("Ignore route to nexthop via nexhop");
+ return;
+ }
+
+ Ptr<EntryContainer> nextHops = 0;
+
+ Ipv4AddressTrieMap::iterator route =
+ m_routes.find (dest.CombineMask (destMask));
+ if (route == m_routes.end ())
+ {
+ nextHops = Create<EntryContainer> ();
+ m_routes[dest.CombineMask (destMask)] = nextHops;
+ }
+ else
+ {
+ nextHops = route->second;
+ }
+
+ // NS_LOG_ERROR ("numLogicalEntries: " << m_numLogicalEntries << ", nextHops->size: " << nextHops->size ());
+ NS_ASSERT_MSG (nextHops->size ()==m_numLogicalEntries ||
+ nextHops->size ()==m_numLogicalEntries-1,
+ "Number of entries in nextHops should be either equal to number of logical entries, or one smaller");
+
+ if (nextHops->size ()==m_numLogicalEntries-1)
+ {
+ // new entry
+ nextHops->push_back (Ipv4RoutingTableEntry::CreateNetworkRouteTo (dest, destMask, nextHop, interface, metric));
+ }
+ else
+ {
+ if (nextHops->back ().GetMetric () > metric)
+ {
+ // update entry if new metric is smaller
+ nextHops->back () = Ipv4RoutingTableEntry::CreateNetworkRouteTo (dest, destMask, nextHop, interface, metric);
+ }
+ }
+}
+
+Ptr<Ipv4Route>
+Ipv4GlobalRoutingUnorderedNexthops::LookupGlobal (uint32_t entryNum, Ipv4Address dest, Ptr<NetDevice> oif)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ NS_LOG_LOGIC ("Looking for route for destination " << dest);
+
+ NS_ASSERT_MSG (m_numLogicalEntries > 0,
+ "Number of logical entries should be at least one");
+
+ NS_ASSERT_MSG (entryNum < m_numLogicalEntries,
+ "Number of requested logical entry should be smaller than total number of logical entries");
+
+ Ipv4AddressTrieMap::const_iterator longest_prefix_map = m_routes.longest_prefix_match (dest);
+ if (longest_prefix_map == m_routes.end ())
+ {
+ return 0;
+ }
+
+ const Ipv4RoutingTableEntry & entry = (*longest_prefix_map->second)[entryNum];
+
+ if (oif != 0 && oif == m_ipv4->GetNetDevice (entry.GetInterface ()))
+ {
+ NS_LOG_LOGIC ("Route points to the incoming interface. Return empty route");
+ return 0;
+ }
+
+ // create a Ipv4Route object from the selected routing table entry
+ Ptr<Ipv4Route> rtentry = Create<Ipv4Route> ();
+ rtentry->SetDestination (entry.GetDest ());
+ rtentry->SetSource (m_ipv4->GetAddress (entry.GetInterface (), 0).GetLocal ());
+ rtentry->SetGateway (entry.GetGateway ());
+ rtentry->SetOutputDevice (m_ipv4->GetNetDevice (entry.GetInterface ()));
+ return rtentry;
+}
+
+void
+Ipv4GlobalRoutingUnorderedNexthops::DeleteRoutes ()
+{
+ m_routes.clear ();
+}
+
+void
+Ipv4GlobalRoutingUnorderedNexthops::PrintRoutingTable (Ptr<OutputStreamWrapper> stream) const
+{
+ std::ostream* os = stream->GetStream ();
+ if (m_routes.size () > 0)
+ {
+ *os << "Destination Iface(Metric),...,Iface(Metric)" << std::endl;
+ for (Ipv4AddressTrieMap::const_iterator i=m_routes.begin (); i != m_routes.end (); i++)
+ {
+ if (i->second->size ()==0) continue;
+ const Ipv4RoutingTableEntry &route = i->second->front ();
+
+ std::ostringstream dest;
+ dest << route.GetDest () << "/" << route.GetDestNetworkMask().GetPrefixLength ();
+ *os << std::setiosflags (std::ios::left) << std::setw (15) << dest.str ();
+
+ for (EntryContainer::iterator entry = i->second->begin ();
+ entry != i->second->end ();
+ entry ++)
+ {
+ if (entry != i->second->begin ())
+ *os << ",";
+ *os << entry->GetInterface () << "(" << entry->GetMetric () << ")";
+ }
+
+ *os << std::endl;
+ }
+ }
+}
+
+Ptr<Ipv4Route>
+Ipv4GlobalRoutingUnorderedNexthops::RouteOutput (Ptr<Packet> p, const Ipv4Header &header,
+ Ptr<NetDevice> oif, Socket::SocketErrno &sockerr)
+{
+//
+// First, see if this is a multicast packet we have a route for. If we
+// have a route, then send the packet down each of the specified interfaces.
+//
+ if (header.GetDestination ().IsMulticast ())
+ {
+ NS_LOG_LOGIC ("Multicast destination-- returning false");
+ return 0; // Let other routing protocols try to handle this
+ }
+//
+// See if this is a unicast packet we have a route for.
+//
+ NS_LOG_LOGIC ("Unicast destination- looking up");
+ Ptr<Ipv4Route> rtentry = LookupGlobal (0, header.GetDestination (), oif);
+ if (rtentry)
+ {
+ sockerr = Socket::ERROR_NOTERROR;
+ }
+ else
+ {
+ sockerr = Socket::ERROR_NOROUTETOHOST;
+ }
+ return rtentry;
+}
+
+bool
+Ipv4GlobalRoutingUnorderedNexthops::RouteInput (Ptr<const Packet> p, const Ipv4Header &header,
+ Ptr<const NetDevice> idev,
+ UnicastForwardCallback ucb, MulticastForwardCallback mcb,
+ LocalDeliverCallback lcb, ErrorCallback ecb)
+{
+
+ NS_LOG_FUNCTION (this << p << header << header.GetSource () << header.GetDestination () << idev);
+ // Check if input device supports IP
+ NS_ASSERT (m_ipv4->GetInterfaceForDevice (idev) >= 0);
+ uint32_t iif = m_ipv4->GetInterfaceForDevice (idev);
+
+ if (header.GetDestination ().IsMulticast ())
+ {
+ NS_LOG_LOGIC ("Multicast destination-- returning false");
+ return false; // Let other routing protocols try to handle this
+ }
+
+ if (header.GetDestination ().IsBroadcast ())
+ {
+ NS_LOG_LOGIC ("For me (Ipv4Addr broadcast address)");
+ // TODO: Local Deliver for broadcast
+ // TODO: Forward broadcast
+ }
+
+ // TODO: Configurable option to enable RFC 1222 Strong End System Model
+ // Right now, we will be permissive and allow a source to send us
+ // a packet to one of our other interface addresses; that is, the
+ // destination unicast address does not match one of the iif addresses,
+ // but we check our other interfaces. This could be an option
+ // (to remove the outer loop immediately below and just check iif).
+ for (uint32_t j = 0; j < m_ipv4->GetNInterfaces (); j++)
+ {
+ for (uint32_t i = 0; i < m_ipv4->GetNAddresses (j); i++)
+ {
+ Ipv4InterfaceAddress iaddr = m_ipv4->GetAddress (j, i);
+ Ipv4Address addr = iaddr.GetLocal ();
+ if (addr.IsEqual (header.GetDestination ()))
+ {
+ if (j == iif)
+ {
+ NS_LOG_LOGIC ("For me (destination " << addr << " match)");
+ }
+ else
+ {
+ NS_LOG_LOGIC ("For me (destination " << addr << " match) on another interface " << header.GetDestination ());
+ }
+ lcb (p, header, iif);
+ return true;
+ }
+ if (header.GetDestination ().IsEqual (iaddr.GetBroadcast ()))
+ {
+ NS_LOG_LOGIC ("For me (interface broadcast address)");
+ lcb (p, header, iif);
+ return true;
+ }
+ NS_LOG_LOGIC ("Address "<< addr << " not a match");
+ }
+ }
+ // Check if input device supports IP forwarding
+ if (m_ipv4->IsForwarding (iif) == false)
+ {
+ NS_LOG_LOGIC ("Forwarding disabled for this interface");
+ ecb (p, header, Socket::ERROR_NOROUTETOHOST);
+ return false;
+ }
+ // Next, try to find a route
+ NS_LOG_LOGIC ("Unicast destination- looking up global route");
+ Ptr<Ipv4Route> rtentry = LookupGlobal (0, header.GetDestination ());
+ if (rtentry != 0)
+ {
+ NS_LOG_LOGIC ("Found unicast destination- calling unicast callback");
+ ucb (rtentry, p, header);
+ return true;
+ }
+ else
+ {
+ NS_LOG_LOGIC ("Did not find unicast destination- returning false");
+ return false; // Let other routing protocols try to handle this
+ // route request.
+ }
+}
+
+} // namespace ns3
diff --git a/model/ipv4-global-routing-unordered-nexthops.h b/model/ipv4-global-routing-unordered-nexthops.h
new file mode 100644
index 0000000..bb137b2
--- /dev/null
+++ b/model/ipv4-global-routing-unordered-nexthops.h
@@ -0,0 +1,97 @@
+// -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*-
+//
+// Copyright (c) 2008 University of Washington
+//
+// This program is free software; you can redistribute it and/or modify
+// it under the terms of the GNU General Public License version 2 as
+// published by the Free Software Foundation;
+//
+// This program is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public License
+// along with this program; if not, write to the Free Software
+// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+//
+//
+
+#ifndef IPV4_GLOBAL_ROUTING_UNORDERED_NEXTHOPS_H
+#define IPV4_GLOBAL_ROUTING_UNORDERED_NEXTHOPS_H
+
+#include "ns3/ipv4-global-routing.h"
+#include "ns3/trie.h"
+#include "ns3/ipv4-routing-table-entry.h"
+#include "ns3/simple-ref-count.h"
+
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/tag.hpp>
+#include <boost/multi_index/ordered_index.hpp>
+#include <boost/multi_index/mem_fun.hpp>
+#include <boost/multi_index/random_access_index.hpp>
+#include <boost/multi_index/sequenced_index.hpp>
+
+namespace ns3 {
+
+/**
+ * \brief Global routing protocol for IP version 4 stacks.
+ *
+ * Each prefix entry stores a list of ordered by metric next-hops
+ *
+ * This class deals with Ipv4 unicast routes only.
+ *
+ * \see Ipv4GlobalRouting
+ * \see Ipv4RoutingProtocol
+ * \see GlobalRouteManager
+ */
+class Ipv4GlobalRoutingUnorderedNexthops : public Ipv4GlobalRouting
+{
+private:
+ class EntryContainer
+ : public SimpleRefCount<EntryContainer>
+ , public
+ std::vector<Ipv4RoutingTableEntry>
+ {
+ };
+
+public:
+ static TypeId GetTypeId (void);
+
+ Ipv4GlobalRoutingUnorderedNexthops ();
+
+ // These methods inherited from base class
+ // from Ipv4RoutingProtocol
+ virtual Ptr<Ipv4Route> RouteOutput (Ptr<Packet> p, const Ipv4Header &header,
+ Ptr<NetDevice> oif, Socket::SocketErrno &sockerr);
+
+ virtual bool RouteInput (Ptr<const Packet> p, const Ipv4Header &header, Ptr<const NetDevice> idev,
+ UnicastForwardCallback ucb, MulticastForwardCallback mcb,
+ LocalDeliverCallback lcb, ErrorCallback ecb);
+
+ virtual void PrintRoutingTable (Ptr<OutputStreamWrapper> stream) const;
+
+ // from Ipv4GlobalRouting
+ virtual void AddRouteTo (Ipv4Address dest,
+ Ipv4Mask destMask,
+ Ipv4Address nextHop,
+ uint32_t interface,
+ uint32_t metric=0);
+
+ virtual void DeleteRoutes ();
+
+ virtual void FixRoutes ();
+
+protected:
+ virtual Ptr<Ipv4Route> LookupGlobal (uint32_t entryNum, Ipv4Address dest, Ptr<NetDevice> oif = 0);
+
+private:
+ typedef Ipv4AddressTrie<Ptr<EntryContainer> > Ipv4AddressTrieMap;
+ Ipv4AddressTrieMap m_routes;
+
+ uint32_t m_numLogicalEntries;
+};
+
+} // Namespace ns3
+
+#endif /* IPV4_GLOBAL_ROUTING_UNORDERED_NEXTHOPS_H */