# HG changeset patch
# User Tom Henderson <tomh@tomh.org>
# Date 1356904421 28800
# Node ID c20b5b6de0a1fceb40f7b57ed9a305cf0603da06
# Parent  043544eef3ed4b73924e3f61025b8849fd9b750d
New Ipv4GlobalRouting option for ECMP to split load per-path

diff -r 043544eef3ed -r c20b5b6de0a1 CHANGES.html
--- a/CHANGES.html	Fri Dec 28 04:22:19 2012 +0100
+++ b/CHANGES.html	Sun Dec 30 13:53:41 2012 -0800
@@ -55,7 +55,12 @@
 
 <h2>New API:</h2>
 <ul>
-<li></li>
+<li>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.</li>
 </ul>
 
 <h2>Changes to existing API:</h2>
diff -r 043544eef3ed -r c20b5b6de0a1 src/internet/examples/ecmp-global-routing.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/internet/examples/ecmp-global-routing.cc	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 <iostream>
+#include <fstream>
+#include <string>
+#include <cassert>
+
+#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 ();
+}
diff -r 043544eef3ed -r c20b5b6de0a1 src/internet/examples/wscript
--- a/src/internet/examples/wscript	Fri Dec 28 04:22:19 2012 +0100
+++ b/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'
+
+
diff -r 043544eef3ed -r c20b5b6de0a1 src/internet/model/ipv4-global-routing.cc
--- a/src/internet/model/ipv4-global-routing.cc	Fri Dec 28 04:22:19 2012 +0100
+++ b/src/internet/model/ipv4-global-routing.cc	Sun Dec 30 13:53:41 2012 -0800
@@ -20,6 +20,7 @@
 #include <iomanip>
 #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<const Packet> 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<Ipv4Route>
-Ipv4GlobalRouting::LookupGlobal (Ipv4Address dest, Ptr<NetDevice> oif)
+Ipv4GlobalRouting::LookupGlobal (const Ipv4Header &header, Ptr<const Packet> ipPayload, Ptr<NetDevice> 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<Ipv4Route> rtentry = 0;
   // store all available routes that bring packets to their destination
   typedef std::vector<Ipv4RoutingTableEntry*> 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<Ipv4Route> rtentry = LookupGlobal (header.GetDestination (), oif);
+  Ptr<Ipv4Route> 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<Ipv4Route> rtentry = LookupGlobal (header.GetDestination ());
+  Ptr<Ipv4Route> rtentry = LookupGlobal (header, p);
   if (rtentry != 0)
     {
       NS_LOG_LOGIC ("Found unicast destination- calling unicast callback");
diff -r 043544eef3ed -r c20b5b6de0a1 src/internet/model/ipv4-global-routing.h
--- a/src/internet/model/ipv4-global-routing.h	Fri Dec 28 04:22:19 2012 +0100
+++ b/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<Ipv4RoutingTableEntry *>::const_iterator ASExternalRoutesCI;
   typedef std::list<Ipv4RoutingTableEntry *>::iterator ASExternalRoutesI;
 
-  Ptr<Ipv4Route> LookupGlobal (Ipv4Address dest, Ptr<NetDevice> oif = 0);
+  uint32_t GetTupleValue (const Ipv4Header &header, Ptr<const Packet> ipPayload);
+
+  Ptr<Ipv4Route> LookupGlobal (const Ipv4Header &header, Ptr<const Packet> ipPayload, Ptr<NetDevice> oif = 0);
 
   HostRoutes m_hostRoutes;
   NetworkRoutes m_networkRoutes;