--- a/CHANGES.html Fri Dec 28 04:22:19 2012 +0100
+++ a/CHANGES.html Sun Dec 30 13:53:41 2012 -0800
@@ -55,7 +55,12 @@
New API:
-
+- A new attribute Ipv4GlobalRouting "FlowEcmpRouting" has been added.
+Setting this attribute to true will result in equal-cost multipath load
+balancing across paths, with each flow resolving to the same path based
+on its five-tuple. This mode is in contrast to the existing
+"RandomEcmpRouting" mode which will randomly balance packets across paths
+(irrespective of their flows). By default, FlowEcmpRouting is false.
Changes to existing API:
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ 043544eef3ed Sun Dec 30 13:53:41 2012 -0800
@@ -0,0 +1,156 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * 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
+ *
+ */
+
+// This script illustrates the behavior of equal-cost multipath routing
+// (ECMP) with Ipv4 global routing, across three equal-cost paths
+//
+// Network topology:
+//
+// n2
+// / \ all links
+// / \ point-to-point
+// n0---n1--n3--n5----n6
+// \ /
+// \ /
+// n4
+//
+// - multiple UDP flows from n0 to n6
+// - Tracing of queues and packet receptions to file "ecmp-global-routing.tr"
+// - pcap traces on nodes n2, n3, and n4
+
+#include
+#include
+#include
+#include
+
+#include "ns3/core-module.h"
+#include "ns3/network-module.h"
+#include "ns3/applications-module.h"
+#include "ns3/point-to-point-module.h"
+#include "ns3/internet-module.h"
+
+using namespace ns3;
+
+NS_LOG_COMPONENT_DEFINE ("EcmpGlobalRoutingExample");
+
+int
+main (int argc, char *argv[])
+{
+ uint32_t ecmpMode = 1;
+
+ // Allow the user to override any of the defaults and the above
+ // Bind ()s at run-time, via command-line arguments
+ CommandLine cmd;
+ cmd.AddValue ("EcmpMode", "Ecmp Mode: (0 none, 1 random, 2 flow)", ecmpMode);
+ cmd.Parse (argc, argv);
+
+ switch (ecmpMode)
+ {
+ case 0:
+ break; //no ECMP
+ case 1:
+ Config::SetDefault ("ns3::Ipv4GlobalRouting::RandomEcmpRouting", BooleanValue (true));
+ break;
+ case 2:
+ Config::SetDefault ("ns3::Ipv4GlobalRouting::FlowEcmpRouting", BooleanValue (true));
+ break;
+ default:
+ NS_FATAL_ERROR ("Illegal command value for EcmpMode: " << ecmpMode);
+ break;
+ }
+
+ // Allow the user to override any of the defaults and the above
+
+ NS_LOG_INFO ("Create nodes.");
+ NodeContainer c;
+ c.Create (7);
+ NodeContainer n0n1 = NodeContainer (c.Get (0), c.Get (1));
+ NodeContainer n1n2 = NodeContainer (c.Get (1), c.Get (2));
+ NodeContainer n1n3 = NodeContainer (c.Get (1), c.Get (3));
+ NodeContainer n1n4 = NodeContainer (c.Get (1), c.Get (4));
+ NodeContainer n2n5 = NodeContainer (c.Get (2), c.Get (5));
+ NodeContainer n3n5 = NodeContainer (c.Get (3), c.Get (5));
+ NodeContainer n4n5 = NodeContainer (c.Get (4), c.Get (5));
+ NodeContainer n5n6 = NodeContainer (c.Get (5), c.Get (6));
+
+ InternetStackHelper internet;
+ internet.Install (c);
+
+ NS_LOG_INFO ("Create channels.");
+ PointToPointHelper p2p;
+ p2p.SetDeviceAttribute ("DataRate", StringValue ("10Mbps"));
+ p2p.SetChannelAttribute ("Delay", StringValue ("1ms"));
+ NetDeviceContainer d0d1 = p2p.Install (n0n1);
+ NetDeviceContainer d1d2 = p2p.Install (n1n2);
+ NetDeviceContainer d1d3 = p2p.Install (n1n3);
+ NetDeviceContainer d1d4 = p2p.Install (n1n4);
+ NetDeviceContainer d2d5 = p2p.Install (n2n5);
+ NetDeviceContainer d3d5 = p2p.Install (n3n5);
+ NetDeviceContainer d4d5 = p2p.Install (n4n5);
+ NetDeviceContainer d5d6 = p2p.Install (n5n6);
+
+ NS_LOG_INFO ("Assign IP Addresses.");
+ Ipv4AddressHelper ipv4;
+ ipv4.SetBase ("10.0.1.0", "255.255.255.0");
+ ipv4.Assign (d0d1);
+ ipv4.SetBase ("10.1.2.0", "255.255.255.0");
+ ipv4.Assign (d1d2);
+ ipv4.SetBase ("10.1.3.0", "255.255.255.0");
+ ipv4.Assign (d1d3);
+ ipv4.SetBase ("10.1.4.0", "255.255.255.0");
+ ipv4.Assign (d1d4);
+ ipv4.SetBase ("10.2.5.0", "255.255.255.0");
+ ipv4.Assign (d2d5);
+ ipv4.SetBase ("10.3.5.0", "255.255.255.0");
+ ipv4.Assign (d3d5);
+ ipv4.SetBase ("10.4.5.0", "255.255.255.0");
+ ipv4.Assign (d4d5);
+ ipv4.SetBase ("10.5.6.0", "255.255.255.0");
+ ipv4.Assign (d5d6);
+
+ NS_LOG_INFO ("Populate routing tables.");
+ Ipv4GlobalRoutingHelper::PopulateRoutingTables ();
+
+ NS_LOG_INFO ("Create Applications.");
+ uint16_t port = 9; // Discard port (RFC 863)
+ OnOffHelper onoff ("ns3::UdpSocketFactory",
+ InetSocketAddress (Ipv4Address ("10.5.6.2"), port));
+ onoff.SetConstantRate (DataRate ("100kbps"));
+ onoff.SetAttribute ("PacketSize", UintegerValue (500));
+
+ ApplicationContainer apps;
+ for (uint32_t i = 0; i < 10; i++)
+ {
+ apps.Add (onoff.Install (c.Get (0)));
+ }
+ apps.Add (onoff.Install (c.Get (1)));
+ apps.Start (Seconds (1.0));
+ apps.Stop (Seconds (5.0));
+
+ PacketSinkHelper sink ("ns3::UdpSocketFactory",
+ Address (InetSocketAddress (Ipv4Address::GetAny (), port)));
+ sink.Install (c.Get (6));
+
+ // Trace the right-most (second) interface on nodes 2, 3, and 4
+ p2p.EnablePcap ("ecmp-global-routing", 2, 2);
+ p2p.EnablePcap ("ecmp-global-routing", 3, 2);
+ p2p.EnablePcap ("ecmp-global-routing", 4, 2);
+
+ NS_LOG_INFO ("Run Simulation.");
+ Simulator::Run ();
+ Simulator::Destroy ();
+}
--- a/src/internet/examples/wscript Fri Dec 28 04:22:19 2012 +0100
+++ a/src/internet/examples/wscript Sun Dec 30 13:53:41 2012 -0800
@@ -7,3 +7,9 @@
obj = bld.create_ns3_program('main-simple',
['network', 'internet', 'applications'])
obj.source = 'main-simple.cc'
+
+ obj = bld.create_ns3_program( 'ecmp-global-routing',
+ ['applications', 'point-to-point', 'internet', 'network', 'core'])
+ obj.source = 'ecmp-global-routing.cc'
+
+
--- a/src/internet/model/ipv4-global-routing.cc Fri Dec 28 04:22:19 2012 +0100
+++ a/src/internet/model/ipv4-global-routing.cc Sun Dec 30 13:53:41 2012 -0800
@@ -20,6 +20,7 @@
#include
#include "ns3/names.h"
#include "ns3/log.h"
+#include "ns3/abort.h"
#include "ns3/simulator.h"
#include "ns3/object.h"
#include "ns3/packet.h"
@@ -27,6 +28,8 @@
#include "ns3/ipv4-route.h"
#include "ns3/ipv4-routing-table-entry.h"
#include "ns3/boolean.h"
+#include "udp-header.h"
+#include "tcp-header.h"
#include "ipv4-global-routing.h"
#include "global-route-manager.h"
@@ -36,6 +39,10 @@
NS_OBJECT_ENSURE_REGISTERED (Ipv4GlobalRouting);
+/* see http://www.iana.org/assignments/protocol-numbers */
+const uint8_t TCP_PROT_NUMBER = 6;
+const uint8_t UDP_PROT_NUMBER = 17;
+
TypeId
Ipv4GlobalRouting::GetTypeId (void)
{
@@ -46,6 +53,11 @@
BooleanValue (false),
MakeBooleanAccessor (&Ipv4GlobalRouting::m_randomEcmpRouting),
MakeBooleanChecker ())
+ .AddAttribute ("FlowEcmpRouting",
+ "Set to true if flows are randomly routed among ECMP; set to false for using only one route consistently",
+ BooleanValue (false),
+ MakeBooleanAccessor (&Ipv4GlobalRouting::m_flowEcmpRouting),
+ MakeBooleanChecker ())
.AddAttribute ("RespondToInterfaceEvents",
"Set to true if you want to dynamically recompute the global routes upon Interface notification events (up/down, or add/remove address)",
BooleanValue (false),
@@ -57,6 +69,7 @@
Ipv4GlobalRouting::Ipv4GlobalRouting ()
: m_randomEcmpRouting (false),
+ m_flowEcmpRouting (false),
m_respondToInterfaceEvents (false)
{
NS_LOG_FUNCTION_NOARGS ();
@@ -133,12 +146,58 @@
m_ASexternalRoutes.push_back (route);
}
+// This function is used to spread the routing of flows across equal
+// cost paths, by calculating an integer based on the five-tuple in the headers
+//
+// It assumes that if a transport protocol value is specified in the header,
+// that a transport header with port numbers is prepended to the ipPayload
+//
+uint32_t
+Ipv4GlobalRouting::GetTupleValue (const Ipv4Header &header, Ptr ipPayload)
+{
+ // We do not care if this value rolls over
+ uint32_t tupleValue = header.GetSource ().Get () +
+ header.GetDestination ().Get () +
+ header.GetProtocol ();
+ switch (header.GetProtocol ())
+ {
+ case UDP_PROT_NUMBER:
+ {
+ UdpHeader udpHeader;
+ ipPayload->PeekHeader (udpHeader);
+ NS_LOG_DEBUG ("Found UDP proto and header: " <<
+ udpHeader.GetSourcePort () << ":" <<
+ udpHeader.GetDestinationPort ());
+ tupleValue += udpHeader.GetSourcePort ();
+ tupleValue += udpHeader.GetDestinationPort ();
+ break;
+ }
+ case TCP_PROT_NUMBER:
+ {
+ TcpHeader tcpHeader;
+ ipPayload->PeekHeader (tcpHeader);
+ NS_LOG_DEBUG ("Found TCP proto and header: " <<
+ tcpHeader.GetSourcePort () << ":" <<
+ tcpHeader.GetDestinationPort ());
+ tupleValue += tcpHeader.GetSourcePort ();
+ tupleValue += tcpHeader.GetDestinationPort ();
+ break;
+ }
+ default:
+ {
+ NS_LOG_DEBUG ("Udp or Tcp header not found");
+ break;
+ }
+ }
+ return tupleValue;
+}
Ptr
-Ipv4GlobalRouting::LookupGlobal (Ipv4Address dest, Ptr oif)
+Ipv4GlobalRouting::LookupGlobal (const Ipv4Header &header, Ptr ipPayload, Ptr oif)
{
NS_LOG_FUNCTION_NOARGS ();
- NS_LOG_LOGIC ("Looking for route for destination " << dest);
+ NS_ABORT_MSG_IF (m_randomEcmpRouting && m_flowEcmpRouting, "Ecmp mode selection");
+ NS_LOG_LOGIC ("Looking for route for destination " << header.GetDestination());
Ptr rtentry = 0;
// store all available routes that bring packets to their destination
typedef std::vector RouteVec_t;
@@ -150,7 +209,7 @@
i++)
{
NS_ASSERT ((*i)->IsHost ());
- if ((*i)->GetDest ().IsEqual (dest))
+ if ((*i)->GetDest ().IsEqual (header.GetDestination ()))
{
if (oif != 0)
{
@@ -173,7 +232,7 @@
{
Ipv4Mask mask = (*j)->GetDestNetworkMask ();
Ipv4Address entry = (*j)->GetDestNetwork ();
- if (mask.IsMatch (dest, entry))
+ if (mask.IsMatch (header.GetDestination (), entry))
{
if (oif != 0)
{
@@ -196,7 +255,7 @@
{
Ipv4Mask mask = (*k)->GetDestNetworkMask ();
Ipv4Address entry = (*k)->GetDestNetwork ();
- if (mask.IsMatch (dest, entry))
+ if (mask.IsMatch (header.GetDestination (), entry))
{
NS_LOG_LOGIC ("Found external route" << *k);
if (oif != 0)
@@ -214,15 +273,20 @@
}
if (allRoutes.size () > 0 ) // if route(s) is found
{
- // pick up one of the routes uniformly at random if random
- // ECMP routing is enabled, or always select the first route
- // consistently if random ECMP routing is disabled
+ // select one of the routes uniformly at random if random
+ // ECMP routing is enabled, or map a flow consistently to a route
+ // if flow ECMP routing is enabled, or otherwise always select the
+ // first route
uint32_t selectIndex;
if (m_randomEcmpRouting)
{
selectIndex = m_rand->GetInteger (0, allRoutes.size ()-1);
}
- else
+ else if (m_flowEcmpRouting && (allRoutes.size () > 1))
+ {
+ selectIndex = GetTupleValue (header, ipPayload) % allRoutes.size ();
+ }
+ else
{
selectIndex = 0;
}
@@ -458,7 +522,7 @@
// See if this is a unicast packet we have a route for.
//
NS_LOG_LOGIC ("Unicast destination- looking up");
- Ptr rtentry = LookupGlobal (header.GetDestination (), oif);
+ Ptr rtentry = LookupGlobal (header, p, oif);
if (rtentry)
{
sockerr = Socket::ERROR_NOTERROR;
@@ -536,7 +600,7 @@
}
// Next, try to find a route
NS_LOG_LOGIC ("Unicast destination- looking up global route");
- Ptr rtentry = LookupGlobal (header.GetDestination ());
+ Ptr rtentry = LookupGlobal (header, p);
if (rtentry != 0)
{
NS_LOG_LOGIC ("Found unicast destination- calling unicast callback");
--- a/src/internet/model/ipv4-global-routing.h Fri Dec 28 04:22:19 2012 +0100
+++ a/src/internet/model/ipv4-global-routing.h Sun Dec 30 13:53:41 2012 -0800
@@ -227,6 +227,8 @@
private:
/// Set to true if packets are randomly routed among ECMP; set to false for using only one route consistently
bool m_randomEcmpRouting;
+ /// Set to true if flows are randomly routed among ECMP; set to false for using only one route consistently
+ bool m_flowEcmpRouting;
/// Set to true if this interface should respond to interface events by globallly recomputing routes
bool m_respondToInterfaceEvents;
/// A uniform random number generator for randomly routing packets among ECMP
@@ -242,7 +244,9 @@
typedef std::list::const_iterator ASExternalRoutesCI;
typedef std::list::iterator ASExternalRoutesI;
- Ptr LookupGlobal (Ipv4Address dest, Ptr oif = 0);
+ uint32_t GetTupleValue (const Ipv4Header &header, Ptr ipPayload);
+
+ Ptr LookupGlobal (const Ipv4Header &header, Ptr ipPayload, Ptr oif = 0);
HostRoutes m_hostRoutes;
NetworkRoutes m_networkRoutes;