--- a/CHANGES.html Mon Aug 31 23:11:29 2009 -0700
+++ b/CHANGES.html Mon Aug 31 23:35:16 2009 -0700
@@ -52,6 +52,15 @@
<h2>New API:</h2>
<ul>
+<li><b>Longest prefix match, support for metrics, for Ipv4StaticRouting</b>
+<p>When performing route lookup, first match for longest prefix, and then
+based on metrics (default metric = 0). If metrics are equal, most recent
+addition is picked. Extends API for support of metrics but preserves
+backward compatibility. One small change is that the default route
+is no longer stored as index 0 route in the host route table so
+GetDefaultRoute () must be used.
+</p>
+</li>
<li><b>Route injection for global routing</b>
<p>Add ability to inject and withdraw routes to Ipv4GlobalRouting. This
allows a user to insert a route and have it redistributed like an OSPF
--- a/src/routing/static-routing/ipv4-routing-table-entry.cc Mon Aug 31 23:11:29 2009 -0700
+++ b/src/routing/static-routing/ipv4-routing-table-entry.cc Mon Aug 31 23:35:16 2009 -0700
@@ -48,14 +48,14 @@
Ipv4Address gateway,
uint32_t interface)
: m_dest (dest),
- m_destNetworkMask (Ipv4Mask::GetZero ()),
+ m_destNetworkMask (Ipv4Mask::GetOnes ()),
m_gateway (gateway),
m_interface (interface)
{}
Ipv4RoutingTableEntry::Ipv4RoutingTableEntry (Ipv4Address dest,
uint32_t interface)
: m_dest (dest),
- m_destNetworkMask (Ipv4Mask::GetZero ()),
+ m_destNetworkMask (Ipv4Mask::GetOnes ()),
m_gateway (Ipv4Address::GetZero ()),
m_interface (interface)
{}
@@ -80,7 +80,7 @@
bool
Ipv4RoutingTableEntry::IsHost (void) const
{
- if (m_destNetworkMask.IsEqual (Ipv4Mask::GetZero ()))
+ if (m_destNetworkMask.IsEqual (Ipv4Mask::GetOnes ()))
{
return true;
}
--- a/src/routing/static-routing/ipv4-static-routing.cc Mon Aug 31 23:11:29 2009 -0700
+++ b/src/routing/static-routing/ipv4-static-routing.cc Mon Aug 31 23:35:16 2009 -0700
@@ -27,6 +27,8 @@
NS_LOG_COMPONENT_DEFINE ("Ipv4StaticRouting");
+using std::make_pair;
+
namespace ns3 {
NS_OBJECT_ENSURE_REGISTERED (Ipv4StaticRouting);
@@ -42,37 +44,17 @@
}
Ipv4StaticRouting::Ipv4StaticRouting ()
-: m_defaultRoute (0), m_ipv4 (0)
-{
- NS_LOG_FUNCTION_NOARGS ();
-}
-
-void
-Ipv4StaticRouting::AddHostRouteTo (Ipv4Address dest,
- Ipv4Address nextHop,
- uint32_t interface)
+: m_ipv4 (0)
{
NS_LOG_FUNCTION_NOARGS ();
- Ipv4RoutingTableEntry *route = new Ipv4RoutingTableEntry ();
- *route = Ipv4RoutingTableEntry::CreateHostRouteTo (dest, nextHop, interface);
- m_hostRoutes.push_back (route);
-}
-
-void
-Ipv4StaticRouting::AddHostRouteTo (Ipv4Address dest,
- uint32_t interface)
-{
- NS_LOG_FUNCTION_NOARGS ();
- Ipv4RoutingTableEntry *route = new Ipv4RoutingTableEntry ();
- *route = Ipv4RoutingTableEntry::CreateHostRouteTo (dest, interface);
- m_hostRoutes.push_back (route);
}
void
Ipv4StaticRouting::AddNetworkRouteTo (Ipv4Address network,
Ipv4Mask networkMask,
Ipv4Address nextHop,
- uint32_t interface)
+ uint32_t interface,
+ uint32_t metric)
{
NS_LOG_FUNCTION_NOARGS ();
Ipv4RoutingTableEntry *route = new Ipv4RoutingTableEntry ();
@@ -80,31 +62,49 @@
networkMask,
nextHop,
interface);
- m_networkRoutes.push_back (route);
+ m_networkRoutes.push_back (make_pair(route,metric));
}
void
Ipv4StaticRouting::AddNetworkRouteTo (Ipv4Address network,
Ipv4Mask networkMask,
- uint32_t interface)
+ uint32_t interface,
+ uint32_t metric)
{
NS_LOG_FUNCTION_NOARGS ();
Ipv4RoutingTableEntry *route = new Ipv4RoutingTableEntry ();
*route = Ipv4RoutingTableEntry::CreateNetworkRouteTo (network,
networkMask,
interface);
- m_networkRoutes.push_back (route);
+ m_networkRoutes.push_back (make_pair (route,metric));
+}
+
+void
+Ipv4StaticRouting::AddHostRouteTo (Ipv4Address dest,
+ Ipv4Address nextHop,
+ uint32_t interface,
+ uint32_t metric)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ AddNetworkRouteTo (dest, Ipv4Mask::GetOnes (), nextHop, interface, metric);
+}
+
+void
+Ipv4StaticRouting::AddHostRouteTo (Ipv4Address dest,
+ uint32_t interface,
+ uint32_t metric)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ AddNetworkRouteTo (dest, Ipv4Mask::GetOnes (), interface, metric);
}
void
Ipv4StaticRouting::SetDefaultRoute (Ipv4Address nextHop,
- uint32_t interface)
+ uint32_t interface,
+ uint32_t metric)
{
NS_LOG_FUNCTION_NOARGS ();
- Ipv4RoutingTableEntry *route = new Ipv4RoutingTableEntry ();
- *route = Ipv4RoutingTableEntry::CreateDefaultRoute (nextHop, interface);
- delete m_defaultRoute;
- m_defaultRoute = route;
+ AddNetworkRouteTo (Ipv4Address ("0.0.0.0"), Ipv4Mask::GetZero (), nextHop, interface, metric);
}
void
@@ -133,7 +133,7 @@
*route = Ipv4RoutingTableEntry::CreateNetworkRouteTo (network,
networkMask,
outputInterface);
- m_networkRoutes.push_back (route);
+ m_networkRoutes.push_back (make_pair(route,0));
}
uint32_t
@@ -214,58 +214,48 @@
{
NS_LOG_FUNCTION_NOARGS ();
Ptr<Ipv4Route> rtentry = 0;
- for (HostRoutesCI i = m_hostRoutes.begin ();
- i != m_hostRoutes.end ();
+ uint16_t longest_mask = 0;
+ uint32_t shortest_metric = 0xffffffff;
+ for (NetworkRoutesI i = m_networkRoutes.begin ();
+ i != m_networkRoutes.end ();
i++)
{
- NS_ASSERT ((*i)->IsHost ());
- if ((*i)->GetDest ().IsEqual (dest))
+ Ipv4RoutingTableEntry *j=i->first;
+ uint32_t metric =i->second;
+ Ipv4Mask mask = (j)->GetDestNetworkMask ();
+ uint16_t masklen = mask.GetPrefixLength ();
+ Ipv4Address entry = (j)->GetDestNetwork ();
+ NS_LOG_LOGIC ("Searching for route to " << dest << ", checking against route to " << entry << "/" << masklen);
+ if (mask.IsMatch (dest, entry))
{
- NS_LOG_LOGIC ("Found global host route" << *i);
- Ipv4RoutingTableEntry* route = (*i);
+ NS_LOG_LOGIC ("Found global network route " << j << ", mask length " << masklen << ", metric " << metric);
+ if (masklen < longest_mask) // Not interested if got shorter mask
+ {
+ NS_LOG_LOGIC ("Previous match longer, skipping");
+ continue;
+ }
+ if (masklen > longest_mask) // Reset metric if longer masklen
+ {
+ shortest_metric = 0xffffffff;
+ }
+ longest_mask = masklen;
+ if (metric > shortest_metric)
+ {
+ NS_LOG_LOGIC ("Equal mask length, but previous metric shorter, skipping");
+ continue;
+ }
+ shortest_metric = metric;
+ Ipv4RoutingTableEntry* route = (j);
+ uint32_t interfaceIdx = route->GetInterface ();
rtentry = Create<Ipv4Route> ();
- uint32_t interfaceIdx = route->GetInterface ();
rtentry->SetDestination (route->GetDest ());
rtentry->SetSource (SourceAddressSelection (interfaceIdx, route->GetDest ()));
rtentry->SetGateway (route->GetGateway ());
rtentry->SetOutputDevice (m_ipv4->GetNetDevice (interfaceIdx));
- return rtentry;
}
}
- for (NetworkRoutesI j = m_networkRoutes.begin ();
- j != m_networkRoutes.end ();
- j++)
- {
- NS_ASSERT ((*j)->IsNetwork ());
- Ipv4Mask mask = (*j)->GetDestNetworkMask ();
- Ipv4Address entry = (*j)->GetDestNetwork ();
- if (mask.IsMatch (dest, entry))
- {
- NS_LOG_LOGIC ("Found global network route" << *j);
- Ipv4RoutingTableEntry* route = (*j);
- rtentry = Create<Ipv4Route> ();
- uint32_t interfaceIdx = route->GetInterface ();
- rtentry->SetDestination (route->GetDest ());
- rtentry->SetSource (SourceAddressSelection (interfaceIdx, route->GetDest ()));
- rtentry->SetGateway (route->GetGateway ());
- rtentry->SetOutputDevice (m_ipv4->GetNetDevice (interfaceIdx));
- return rtentry;
- }
- }
- if (m_defaultRoute != 0)
- {
- NS_ASSERT (m_defaultRoute->IsDefault ());
- NS_LOG_LOGIC ("Found global network route" << m_defaultRoute);
- Ipv4RoutingTableEntry* route = m_defaultRoute;
- rtentry = Create<Ipv4Route> ();
- uint32_t interfaceIdx = route->GetInterface ();
- rtentry->SetDestination (route->GetDest ());
- rtentry->SetSource (SourceAddressSelection (interfaceIdx, route->GetDest ()));
- rtentry->SetGateway (route->GetGateway ());
- rtentry->SetOutputDevice (m_ipv4->GetNetDevice (interfaceIdx));
- return rtentry;
- }
- return 0;
+ NS_LOG_LOGIC ("Matching route via " << rtentry << " at the end");
+ return rtentry;
}
Ptr<Ipv4MulticastRoute>
@@ -324,23 +314,40 @@
Ipv4StaticRouting::GetNRoutes (void)
{
NS_LOG_FUNCTION_NOARGS ();
- uint32_t n = 0;
- if (m_defaultRoute != 0)
- {
- n++;
- }
- n += m_hostRoutes.size ();
- n += m_networkRoutes.size ();
- return n;
+ return m_networkRoutes.size ();;
}
Ipv4RoutingTableEntry
Ipv4StaticRouting::GetDefaultRoute ()
{
NS_LOG_FUNCTION_NOARGS ();
- if (m_defaultRoute != 0)
+ // Basically a repeat of LookupStatic, retained for backward compatibility
+ Ipv4Address dest ("0.0.0.0");
+ uint32_t shortest_metric = 0xffffffff;
+ Ipv4RoutingTableEntry *result = 0;
+ for (NetworkRoutesI i = m_networkRoutes.begin ();
+ i != m_networkRoutes.end ();
+ i++)
{
- return *m_defaultRoute;
+ Ipv4RoutingTableEntry *j = i->first;
+ uint32_t metric = i->second;
+ Ipv4Mask mask = (j)->GetDestNetworkMask ();
+ uint16_t masklen = mask.GetPrefixLength ();
+ Ipv4Address entry = (j)->GetDestNetwork ();
+ if (masklen != 0)
+ {
+ continue;
+ }
+ if (metric > shortest_metric)
+ {
+ continue;
+ }
+ shortest_metric = metric;
+ result = j;
+ }
+ if (result)
+ {
+ return result;
}
else
{
@@ -352,29 +359,26 @@
Ipv4StaticRouting::GetRoute (uint32_t index)
{
NS_LOG_FUNCTION_NOARGS ();
- if (index == 0 && m_defaultRoute != 0)
- {
- return *m_defaultRoute;
- }
- if (index > 0 && m_defaultRoute != 0)
- {
- index--;
- }
- if (index < m_hostRoutes.size ())
- {
uint32_t tmp = 0;
- for (HostRoutesCI i = m_hostRoutes.begin ();
- i != m_hostRoutes.end ();
- i++)
+ for (NetworkRoutesI j = m_networkRoutes.begin ();
+ j != m_networkRoutes.end ();
+ j++)
{
if (tmp == index)
{
- return *i;
+ return j->first;
}
tmp++;
}
- }
- index -= m_hostRoutes.size ();
+ NS_ASSERT (false);
+ // quiet compiler.
+ return 0;
+}
+
+uint32_t
+Ipv4StaticRouting::GetMetric (uint32_t index)
+{
+ NS_LOG_FUNCTION_NOARGS ();
uint32_t tmp = 0;
for (NetworkRoutesI j = m_networkRoutes.begin ();
j != m_networkRoutes.end ();
@@ -382,7 +386,7 @@
{
if (tmp == index)
{
- return *j;
+ return j->second;
}
tmp++;
}
@@ -394,32 +398,6 @@
Ipv4StaticRouting::RemoveRoute (uint32_t index)
{
NS_LOG_FUNCTION_NOARGS ();
- if (index == 0 && m_defaultRoute != 0)
- {
- delete m_defaultRoute;
- m_defaultRoute = 0;
- }
- if (index > 0 && m_defaultRoute != 0)
- {
- index--;
- }
- if (index < m_hostRoutes.size ())
- {
- uint32_t tmp = 0;
- for (HostRoutesI i = m_hostRoutes.begin ();
- i != m_hostRoutes.end ();
- i++)
- {
- if (tmp == index)
- {
- delete *i;
- m_hostRoutes.erase (i);
- return;
- }
- tmp++;
- }
- }
- index -= m_hostRoutes.size ();
uint32_t tmp = 0;
for (NetworkRoutesI j = m_networkRoutes.begin ();
j != m_networkRoutes.end ();
@@ -427,7 +405,7 @@
{
if (tmp == index)
{
- delete *j;
+ delete j->first;
m_networkRoutes.erase (j);
return;
}
@@ -520,22 +498,11 @@
Ipv4StaticRouting::DoDispose (void)
{
NS_LOG_FUNCTION_NOARGS ();
- for (HostRoutesI i = m_hostRoutes.begin ();
- i != m_hostRoutes.end ();
- i = m_hostRoutes.erase (i))
- {
- delete (*i);
- }
for (NetworkRoutesI j = m_networkRoutes.begin ();
j != m_networkRoutes.end ();
j = m_networkRoutes.erase (j))
{
- delete (*j);
- }
- if (m_defaultRoute != 0)
- {
- delete m_defaultRoute;
- m_defaultRoute = 0;
+ delete (j->first);
}
for (MulticastRoutesI i = m_multicastRoutes.begin ();
i != m_multicastRoutes.end ();
@@ -568,13 +535,18 @@
Ipv4StaticRouting::NotifyInterfaceDown (uint32_t i)
{
// Remove all static routes that are going through this interface
- for (uint32_t j = 0; j < GetNRoutes (); j++)
+ uint32_t j = 0;
+ while (j < GetNRoutes())
{
Ipv4RoutingTableEntry route = GetRoute (j);
if (route.GetInterface () == i)
{
RemoveRoute (j);
}
+ else
+ {
+ j++;
+ }
}
}
--- a/src/routing/static-routing/ipv4-static-routing.h Mon Aug 31 23:11:29 2009 -0700
+++ b/src/routing/static-routing/ipv4-static-routing.h Mon Aug 31 23:35:16 2009 -0700
@@ -23,6 +23,7 @@
#define IPV4_STATIC_ROUTING_H
#include <list>
+#include <utility>
#include <stdint.h>
#include "ns3/ipv4-address.h"
#include "ns3/ipv4-header.h"
@@ -87,31 +88,6 @@
virtual void SetIpv4 (Ptr<Ipv4> ipv4);
/**
- * \brief Add a host route to the static routing table.
- *
- * \param dest The Ipv4Address destination for this route.
- * \param nextHop The Ipv4Address of the next hop in the route.
- * \param interface The network interface index used to send packets to the
- * destination.
- *
- * \see Ipv4Address
- */
- void AddHostRouteTo (Ipv4Address dest,
- Ipv4Address nextHop,
- uint32_t interface);
-/**
- * \brief Add a host route to the static routing table.
- *
- * \param dest The Ipv4Address destination for this route.
- * \param interface The network interface index used to send packets to the
- * destination.
- *
- * \see Ipv4Address
- */
- void AddHostRouteTo (Ipv4Address dest,
- uint32_t interface);
-
-/**
* \brief Add a network route to the static routing table.
*
* \param network The Ipv4Address network for this route.
@@ -119,13 +95,15 @@
* \param nextHop The next hop in the route to the destination network.
* \param interface The network interface index used to send packets to the
* destination.
+ * \param metric Metric of route in case of multiple routes to same destination
*
* \see Ipv4Address
*/
void AddNetworkRouteTo (Ipv4Address network,
Ipv4Mask networkMask,
Ipv4Address nextHop,
- uint32_t interface);
+ uint32_t interface,
+ uint32_t metric = 0);
/**
* \brief Add a network route to the static routing table.
@@ -134,14 +112,44 @@
* \param networkMask The Ipv4Mask to extract the network.
* \param interface The network interface index used to send packets to the
* destination.
+ * \param metric Metric of route in case of multiple routes to same destination
*
* \see Ipv4Address
*/
void AddNetworkRouteTo (Ipv4Address network,
Ipv4Mask networkMask,
- uint32_t interface);
+ uint32_t interface,
+ uint32_t metric = 0);
/**
+ * \brief Add a host route to the static routing table.
+ *
+ * \param dest The Ipv4Address destination for this route.
+ * \param nextHop The Ipv4Address of the next hop in the route.
+ * \param interface The network interface index used to send packets to the
+ * destination.
+ * \param metric Metric of route in case of multiple routes to same destination
+ *
+ * \see Ipv4Address
+ */
+ void AddHostRouteTo (Ipv4Address dest,
+ Ipv4Address nextHop,
+ uint32_t interface,
+ uint32_t metric = 0);
+/**
+ * \brief Add a host route to the static routing table.
+ *
+ * \param dest The Ipv4Address destination for this route.
+ * \param interface The network interface index used to send packets to the
+ * destination.
+ * \param metric Metric of route in case of multiple routes to same destination
+ *
+ * \see Ipv4Address
+ */
+ void AddHostRouteTo (Ipv4Address dest,
+ uint32_t interface,
+ uint32_t metric = 0);
+/**
* \brief Add a default route to the static routing table.
*
* This method tells the routing system what to do in the case where a specific
@@ -155,12 +163,14 @@
* \param nextHop The Ipv4Address to send packets to in the hope that they
* will be forwarded correctly.
* \param interface The network interface index used to send packets.
+ * \param metric Metric of route in case of multiple routes to same destination
*
* \see Ipv4Address
* \see Ipv4StaticRouting::Lookup
*/
void SetDefaultRoute (Ipv4Address nextHop,
- uint32_t interface);
+ uint32_t interface,
+ uint32_t metric = 0);
/**
* \brief Get the number of individual unicast routes that have been added
@@ -171,10 +181,11 @@
uint32_t GetNRoutes (void);
/**
- * \brief Get the default route from the static routing table.
+ * \brief Get the default route with lowest metric from the static routing table.
*
* \return If the default route is set, a pointer to that Ipv4RoutingTableEntry is
- * returned, otherwise a zero pointer is returned.
+ * returned, otherwise an empty routing table entry is returned.
+* If multiple default routes exist, the one with lowest metric is returned.
*
* \see Ipv4RoutingTableEntry
*/
@@ -184,16 +195,9 @@
* \brief Get a route from the static unicast routing table.
*
* Externally, the unicast static routing table appears simply as a table with
- * n entries. The one sublety of note is that if a default route has been set
- * it will appear as the zeroth entry in the table. This means that if you
- * add only a default route, the table will have one entry that can be accessed
- * either by explicity calling GetDefaultRoute () or by calling GetRoute (0).
- *
- * Similarly, if the default route has been set, calling RemoveRoute (0) will
- * remove the default route.
+ * n entries.
*
- * \param i The index (into the routing table) of the route to retrieve. If
- * the default route has been set, it will occupy index zero.
+ * \param i The index (into the routing table) of the route to retrieve.
* \return If route is set, a pointer to that Ipv4RoutingTableEntry is returned, otherwise
* a zero pointer is returned.
*
@@ -203,16 +207,21 @@
Ipv4RoutingTableEntry GetRoute (uint32_t i);
/**
+ * \brief Get a metric for route from the static unicast routing table.
+ *
+ * \param i The index (into the routing table) of the route to retrieve.
+ * \return If route is set, the metric is returned. If not, an infinity metric (0xffffffff) is returned
+ *
+ */
+ uint32_t GetMetric (uint32_t index);
+
+/**
* \brief Remove a route from the static unicast routing table.
*
* Externally, the unicast static routing table appears simply as a table with
- * n entries. The one sublety of note is that if a default route has been set
- * it will appear as the zeroth entry in the table. This means that if the
- * default route has been set, calling RemoveRoute (0) will remove the
- * default route.
+ * n entries.
*
- * \param i The index (into the routing table) of the route to remove. If
- * the default route has been set, it will occupy index zero.
+ * \param i The index (into the routing table) of the route to remove.
*
* \see Ipv4RoutingTableEntry
* \see Ipv4StaticRouting::GetRoute
@@ -366,12 +375,9 @@
virtual void DoDispose (void);
private:
- typedef std::list<Ipv4RoutingTableEntry *> HostRoutes;
- typedef std::list<Ipv4RoutingTableEntry *>::const_iterator HostRoutesCI;
- typedef std::list<Ipv4RoutingTableEntry *>::iterator HostRoutesI;
- typedef std::list<Ipv4RoutingTableEntry *> NetworkRoutes;
- typedef std::list<Ipv4RoutingTableEntry *>::const_iterator NetworkRoutesCI;
- typedef std::list<Ipv4RoutingTableEntry *>::iterator NetworkRoutesI;
+ typedef std::list<std::pair <Ipv4RoutingTableEntry *, uint32_t> > NetworkRoutes;
+ typedef std::list<std::pair <Ipv4RoutingTableEntry *, uint32_t> >::const_iterator NetworkRoutesCI;
+ typedef std::list<std::pair <Ipv4RoutingTableEntry *, uint32_t> >::iterator NetworkRoutesI;
typedef std::list<Ipv4MulticastRoutingTableEntry *> MulticastRoutes;
typedef std::list<Ipv4MulticastRoutingTableEntry *>::const_iterator MulticastRoutesCI;
@@ -383,9 +389,7 @@
Ipv4Address SourceAddressSelection (uint32_t interface, Ipv4Address dest);
- HostRoutes m_hostRoutes;
NetworkRoutes m_networkRoutes;
- Ipv4RoutingTableEntry *m_defaultRoute;
MulticastRoutes m_multicastRoutes;
Ptr<Ipv4> m_ipv4;