View | Details | Raw Unified | Return to bug 667
Collapse All | Expand All

(-)a/CHANGES.html (-1 / +6 lines)
 Lines 55-61    Link Here 
55
55
56
<h2>New API:</h2>
56
<h2>New API:</h2>
57
<ul>
57
<ul>
58
<li></li>
58
<li>A new attribute Ipv4GlobalRouting "FlowEcmpRouting" has been added.
59
Setting this attribute to true will result in equal-cost multipath load
60
balancing across paths, with each flow resolving to the same path based
61
on its five-tuple.  This mode is in contrast to the existing 
62
"RandomEcmpRouting" mode which will randomly balance packets across paths 
63
(irrespective of their flows).  By default, FlowEcmpRouting is false.</li>
59
</ul>
64
</ul>
60
65
61
<h2>Changes to existing API:</h2>
66
<h2>Changes to existing API:</h2>
(-)043544eef3ed (+156 lines)
Added Link Here 
1
/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2
/*
3
 * This program is free software; you can redistribute it and/or modify
4
 * it under the terms of the GNU General Public License version 2 as
5
 * published by the Free Software Foundation;
6
 *
7
 * This program is distributed in the hope that it will be useful,
8
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10
 * GNU General Public License for more details.
11
 *
12
 * You should have received a copy of the GNU General Public License
13
 * along with this program; if not, write to the Free Software
14
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
15
 *
16
 */
17
18
// This script illustrates the behavior of equal-cost multipath routing 
19
// (ECMP) with Ipv4 global routing, across three equal-cost paths
20
//
21
// Network topology:
22
//
23
//           n2
24
//          /  \ all links 
25
//         /    \  point-to-point
26
//  n0---n1--n3--n5----n6
27
//         \    /
28
//          \  /
29
//           n4
30
//
31
// - multiple UDP flows from n0 to n6
32
// - Tracing of queues and packet receptions to file "ecmp-global-routing.tr"
33
// - pcap traces on nodes n2, n3, and n4
34
35
#include <iostream>
36
#include <fstream>
37
#include <string>
38
#include <cassert>
39
40
#include "ns3/core-module.h"
41
#include "ns3/network-module.h"
42
#include "ns3/applications-module.h"
43
#include "ns3/point-to-point-module.h"
44
#include "ns3/internet-module.h"
45
46
using namespace ns3;
47
48
NS_LOG_COMPONENT_DEFINE ("EcmpGlobalRoutingExample");
49
50
int 
51
main (int argc, char *argv[])
52
{
53
  uint32_t ecmpMode = 1;
54
55
  // Allow the user to override any of the defaults and the above
56
  // Bind ()s at run-time, via command-line arguments
57
  CommandLine cmd;
58
  cmd.AddValue ("EcmpMode", "Ecmp Mode: (0 none, 1 random, 2 flow)", ecmpMode);
59
  cmd.Parse (argc, argv);
60
61
  switch (ecmpMode)
62
    {
63
      case 0:
64
        break;  //no ECMP
65
      case 1:
66
        Config::SetDefault ("ns3::Ipv4GlobalRouting::RandomEcmpRouting", BooleanValue (true));
67
        break;
68
      case 2:
69
        Config::SetDefault ("ns3::Ipv4GlobalRouting::FlowEcmpRouting", BooleanValue (true));
70
        break;  
71
      default:
72
        NS_FATAL_ERROR ("Illegal command value for EcmpMode: " << ecmpMode);
73
        break;
74
    }
75
76
  // Allow the user to override any of the defaults and the above
77
78
  NS_LOG_INFO ("Create nodes.");
79
  NodeContainer c;
80
  c.Create (7);
81
  NodeContainer n0n1 = NodeContainer (c.Get (0), c.Get (1));
82
  NodeContainer n1n2 = NodeContainer (c.Get (1), c.Get (2));
83
  NodeContainer n1n3 = NodeContainer (c.Get (1), c.Get (3));
84
  NodeContainer n1n4 = NodeContainer (c.Get (1), c.Get (4));
85
  NodeContainer n2n5 = NodeContainer (c.Get (2), c.Get (5));
86
  NodeContainer n3n5 = NodeContainer (c.Get (3), c.Get (5));
87
  NodeContainer n4n5 = NodeContainer (c.Get (4), c.Get (5));
88
  NodeContainer n5n6 = NodeContainer (c.Get (5), c.Get (6));
89
90
  InternetStackHelper internet;
91
  internet.Install (c);
92
93
  NS_LOG_INFO ("Create channels.");
94
  PointToPointHelper p2p;
95
  p2p.SetDeviceAttribute ("DataRate", StringValue ("10Mbps"));
96
  p2p.SetChannelAttribute ("Delay", StringValue ("1ms"));
97
  NetDeviceContainer d0d1 = p2p.Install (n0n1);
98
  NetDeviceContainer d1d2 = p2p.Install (n1n2);
99
  NetDeviceContainer d1d3 = p2p.Install (n1n3);
100
  NetDeviceContainer d1d4 = p2p.Install (n1n4);
101
  NetDeviceContainer d2d5 = p2p.Install (n2n5);
102
  NetDeviceContainer d3d5 = p2p.Install (n3n5);
103
  NetDeviceContainer d4d5 = p2p.Install (n4n5);
104
  NetDeviceContainer d5d6 = p2p.Install (n5n6);
105
106
  NS_LOG_INFO ("Assign IP Addresses.");
107
  Ipv4AddressHelper ipv4;
108
  ipv4.SetBase ("10.0.1.0", "255.255.255.0");
109
  ipv4.Assign (d0d1);
110
  ipv4.SetBase ("10.1.2.0", "255.255.255.0");
111
  ipv4.Assign (d1d2);
112
  ipv4.SetBase ("10.1.3.0", "255.255.255.0");
113
  ipv4.Assign (d1d3);
114
  ipv4.SetBase ("10.1.4.0", "255.255.255.0");
115
  ipv4.Assign (d1d4);
116
  ipv4.SetBase ("10.2.5.0", "255.255.255.0");
117
  ipv4.Assign (d2d5);
118
  ipv4.SetBase ("10.3.5.0", "255.255.255.0");
119
  ipv4.Assign (d3d5);
120
  ipv4.SetBase ("10.4.5.0", "255.255.255.0");
121
  ipv4.Assign (d4d5);
122
  ipv4.SetBase ("10.5.6.0", "255.255.255.0");
123
  ipv4.Assign (d5d6);
124
125
  NS_LOG_INFO ("Populate routing tables.");
126
  Ipv4GlobalRoutingHelper::PopulateRoutingTables ();
127
128
  NS_LOG_INFO ("Create Applications.");
129
  uint16_t port = 9;   // Discard port (RFC 863)
130
  OnOffHelper onoff ("ns3::UdpSocketFactory",
131
                     InetSocketAddress (Ipv4Address ("10.5.6.2"), port));
132
  onoff.SetConstantRate (DataRate ("100kbps"));
133
  onoff.SetAttribute ("PacketSize", UintegerValue (500));
134
135
  ApplicationContainer apps;
136
  for (uint32_t i = 0; i < 10; i++)
137
    {
138
      apps.Add (onoff.Install (c.Get (0)));
139
    }
140
  apps.Add (onoff.Install (c.Get (1)));
141
  apps.Start (Seconds (1.0));
142
  apps.Stop (Seconds (5.0));
143
144
  PacketSinkHelper sink ("ns3::UdpSocketFactory",
145
                         Address (InetSocketAddress (Ipv4Address::GetAny (), port)));
146
  sink.Install (c.Get (6));
147
148
  // Trace the right-most (second) interface on nodes 2, 3, and 4
149
  p2p.EnablePcap ("ecmp-global-routing", 2, 2);
150
  p2p.EnablePcap ("ecmp-global-routing", 3, 2);
151
  p2p.EnablePcap ("ecmp-global-routing", 4, 2);
152
153
  NS_LOG_INFO ("Run Simulation.");
154
  Simulator::Run ();
155
  Simulator::Destroy ();
156
}
(-)a/src/internet/examples/wscript (+6 lines)
 Lines 7-9    Link Here 
7
    obj = bld.create_ns3_program('main-simple',
7
    obj = bld.create_ns3_program('main-simple',
8
                                 ['network', 'internet', 'applications'])
8
                                 ['network', 'internet', 'applications'])
9
    obj.source = 'main-simple.cc'
9
    obj.source = 'main-simple.cc'
10
11
    obj = bld.create_ns3_program( 'ecmp-global-routing',
12
                                  ['applications', 'point-to-point', 'internet', 'network', 'core'])
13
    obj.source = 'ecmp-global-routing.cc'
14
15
(-)a/src/internet/model/ipv4-global-routing.cc (-11 / +75 lines)
 Lines 20-25    Link Here 
20
#include <iomanip>
20
#include <iomanip>
21
#include "ns3/names.h"
21
#include "ns3/names.h"
22
#include "ns3/log.h"
22
#include "ns3/log.h"
23
#include "ns3/abort.h"
23
#include "ns3/simulator.h"
24
#include "ns3/simulator.h"
24
#include "ns3/object.h"
25
#include "ns3/object.h"
25
#include "ns3/packet.h"
26
#include "ns3/packet.h"
 Lines 27-32    Link Here 
27
#include "ns3/ipv4-route.h"
28
#include "ns3/ipv4-route.h"
28
#include "ns3/ipv4-routing-table-entry.h"
29
#include "ns3/ipv4-routing-table-entry.h"
29
#include "ns3/boolean.h"
30
#include "ns3/boolean.h"
31
#include "udp-header.h"
32
#include "tcp-header.h"
30
#include "ipv4-global-routing.h"
33
#include "ipv4-global-routing.h"
31
#include "global-route-manager.h"
34
#include "global-route-manager.h"
32
35
 Lines 36-41    Link Here 
36
39
37
NS_OBJECT_ENSURE_REGISTERED (Ipv4GlobalRouting);
40
NS_OBJECT_ENSURE_REGISTERED (Ipv4GlobalRouting);
38
41
42
/* see http://www.iana.org/assignments/protocol-numbers */
43
const uint8_t TCP_PROT_NUMBER = 6;
44
const uint8_t UDP_PROT_NUMBER = 17;
45
39
TypeId 
46
TypeId 
40
Ipv4GlobalRouting::GetTypeId (void)
47
Ipv4GlobalRouting::GetTypeId (void)
41
{ 
48
{ 
 Lines 46-51    Link Here 
46
                   BooleanValue (false),
53
                   BooleanValue (false),
47
                   MakeBooleanAccessor (&Ipv4GlobalRouting::m_randomEcmpRouting),
54
                   MakeBooleanAccessor (&Ipv4GlobalRouting::m_randomEcmpRouting),
48
                   MakeBooleanChecker ())
55
                   MakeBooleanChecker ())
56
    .AddAttribute ("FlowEcmpRouting",
57
                   "Set to true if flows are randomly routed among ECMP; set to false for using only one route consistently",
58
                   BooleanValue (false),
59
                   MakeBooleanAccessor (&Ipv4GlobalRouting::m_flowEcmpRouting),
60
                   MakeBooleanChecker ())
49
    .AddAttribute ("RespondToInterfaceEvents",
61
    .AddAttribute ("RespondToInterfaceEvents",
50
                   "Set to true if you want to dynamically recompute the global routes upon Interface notification events (up/down, or add/remove address)",
62
                   "Set to true if you want to dynamically recompute the global routes upon Interface notification events (up/down, or add/remove address)",
51
                   BooleanValue (false),
63
                   BooleanValue (false),
 Lines 57-62    Link Here 
57
69
58
Ipv4GlobalRouting::Ipv4GlobalRouting () 
70
Ipv4GlobalRouting::Ipv4GlobalRouting () 
59
  : m_randomEcmpRouting (false),
71
  : m_randomEcmpRouting (false),
72
    m_flowEcmpRouting (false),
60
    m_respondToInterfaceEvents (false)
73
    m_respondToInterfaceEvents (false)
61
{
74
{
62
  NS_LOG_FUNCTION_NOARGS ();
75
  NS_LOG_FUNCTION_NOARGS ();
 Lines 133-144    Link Here 
133
  m_ASexternalRoutes.push_back (route);
146
  m_ASexternalRoutes.push_back (route);
134
}
147
}
135
148
149
// This function is used to spread the routing of flows across equal
150
// cost paths, by calculating an integer based on the five-tuple in the headers
151
//
152
// It assumes that if a transport protocol value is specified in the header, 
153
// that a transport header with port numbers is prepended to the ipPayload 
154
//
155
uint32_t
156
Ipv4GlobalRouting::GetTupleValue (const Ipv4Header &header, Ptr<const Packet> ipPayload)
157
{
158
  // We do not care if this value rolls over
159
  uint32_t tupleValue = header.GetSource ().Get () + 
160
                        header.GetDestination ().Get () + 
161
                        header.GetProtocol ();
162
  switch (header.GetProtocol ())
163
    {
164
    case UDP_PROT_NUMBER:
165
      {
166
        UdpHeader udpHeader;
167
        ipPayload->PeekHeader (udpHeader);
168
        NS_LOG_DEBUG ("Found UDP proto and header: " << 
169
                       udpHeader.GetSourcePort () << ":" <<  
170
                       udpHeader.GetDestinationPort ());
171
        tupleValue += udpHeader.GetSourcePort ();
172
        tupleValue += udpHeader.GetDestinationPort ();
173
        break;
174
      }
175
    case TCP_PROT_NUMBER:
176
      {
177
        TcpHeader tcpHeader;
178
        ipPayload->PeekHeader (tcpHeader);
179
        NS_LOG_DEBUG ("Found TCP proto and header: " << 
180
                       tcpHeader.GetSourcePort () << ":" <<  
181
                       tcpHeader.GetDestinationPort ());
182
        tupleValue += tcpHeader.GetSourcePort ();
183
        tupleValue += tcpHeader.GetDestinationPort ();
184
        break;
185
      }
186
    default:
187
      {
188
        NS_LOG_DEBUG ("Udp or Tcp header not found");
189
        break;
190
      }
191
    }
192
  return tupleValue;
193
}
136
194
137
Ptr<Ipv4Route>
195
Ptr<Ipv4Route>
138
Ipv4GlobalRouting::LookupGlobal (Ipv4Address dest, Ptr<NetDevice> oif)
196
Ipv4GlobalRouting::LookupGlobal (const Ipv4Header &header, Ptr<const Packet> ipPayload, Ptr<NetDevice> oif)
139
{
197
{
140
  NS_LOG_FUNCTION_NOARGS ();
198
  NS_LOG_FUNCTION_NOARGS ();
141
  NS_LOG_LOGIC ("Looking for route for destination " << dest);
199
  NS_ABORT_MSG_IF (m_randomEcmpRouting && m_flowEcmpRouting, "Ecmp mode selection");
200
  NS_LOG_LOGIC ("Looking for route for destination " << header.GetDestination());
142
  Ptr<Ipv4Route> rtentry = 0;
201
  Ptr<Ipv4Route> rtentry = 0;
143
  // store all available routes that bring packets to their destination
202
  // store all available routes that bring packets to their destination
144
  typedef std::vector<Ipv4RoutingTableEntry*> RouteVec_t;
203
  typedef std::vector<Ipv4RoutingTableEntry*> RouteVec_t;
 Lines 150-156    Link Here 
150
       i++) 
209
       i++) 
151
    {
210
    {
152
      NS_ASSERT ((*i)->IsHost ());
211
      NS_ASSERT ((*i)->IsHost ());
153
      if ((*i)->GetDest ().IsEqual (dest)) 
212
      if ((*i)->GetDest ().IsEqual (header.GetDestination ())) 
154
        {
213
        {
155
          if (oif != 0)
214
          if (oif != 0)
156
            {
215
            {
 Lines 173-179    Link Here 
173
        {
232
        {
174
          Ipv4Mask mask = (*j)->GetDestNetworkMask ();
233
          Ipv4Mask mask = (*j)->GetDestNetworkMask ();
175
          Ipv4Address entry = (*j)->GetDestNetwork ();
234
          Ipv4Address entry = (*j)->GetDestNetwork ();
176
          if (mask.IsMatch (dest, entry)) 
235
          if (mask.IsMatch (header.GetDestination (), entry)) 
177
            {
236
            {
178
              if (oif != 0)
237
              if (oif != 0)
179
                {
238
                {
 Lines 196-202    Link Here 
196
        {
255
        {
197
          Ipv4Mask mask = (*k)->GetDestNetworkMask ();
256
          Ipv4Mask mask = (*k)->GetDestNetworkMask ();
198
          Ipv4Address entry = (*k)->GetDestNetwork ();
257
          Ipv4Address entry = (*k)->GetDestNetwork ();
199
          if (mask.IsMatch (dest, entry))
258
          if (mask.IsMatch (header.GetDestination (), entry))
200
            {
259
            {
201
              NS_LOG_LOGIC ("Found external route" << *k);
260
              NS_LOG_LOGIC ("Found external route" << *k);
202
              if (oif != 0)
261
              if (oif != 0)
 Lines 214-228    Link Here 
214
    }
273
    }
215
  if (allRoutes.size () > 0 ) // if route(s) is found
274
  if (allRoutes.size () > 0 ) // if route(s) is found
216
    {
275
    {
217
      // pick up one of the routes uniformly at random if random
276
      // select one of the routes uniformly at random if random
218
      // ECMP routing is enabled, or always select the first route
277
      // ECMP routing is enabled, or map a flow consistently to a route
219
      // consistently if random ECMP routing is disabled
278
      // if flow ECMP routing is enabled, or otherwise always select the 
279
      // first route
220
      uint32_t selectIndex;
280
      uint32_t selectIndex;
221
      if (m_randomEcmpRouting)
281
      if (m_randomEcmpRouting)
222
        {
282
        {
223
          selectIndex = m_rand->GetInteger (0, allRoutes.size ()-1);
283
          selectIndex = m_rand->GetInteger (0, allRoutes.size ()-1);
224
        }
284
        }
225
      else 
285
      else  if (m_flowEcmpRouting && (allRoutes.size () > 1))
286
        {
287
          selectIndex = GetTupleValue (header, ipPayload) % allRoutes.size ();
288
        }
289
      else
226
        {
290
        {
227
          selectIndex = 0;
291
          selectIndex = 0;
228
        }
292
        }
 Lines 458-464    Link Here 
458
// See if this is a unicast packet we have a route for.
522
// See if this is a unicast packet we have a route for.
459
//
523
//
460
  NS_LOG_LOGIC ("Unicast destination- looking up");
524
  NS_LOG_LOGIC ("Unicast destination- looking up");
461
  Ptr<Ipv4Route> rtentry = LookupGlobal (header.GetDestination (), oif);
525
  Ptr<Ipv4Route> rtentry = LookupGlobal (header, p, oif);
462
  if (rtentry)
526
  if (rtentry)
463
    {
527
    {
464
      sockerr = Socket::ERROR_NOTERROR;
528
      sockerr = Socket::ERROR_NOTERROR;
 Lines 536-542    Link Here 
536
    }
600
    }
537
  // Next, try to find a route
601
  // Next, try to find a route
538
  NS_LOG_LOGIC ("Unicast destination- looking up global route");
602
  NS_LOG_LOGIC ("Unicast destination- looking up global route");
539
  Ptr<Ipv4Route> rtentry = LookupGlobal (header.GetDestination ());
603
  Ptr<Ipv4Route> rtentry = LookupGlobal (header, p);
540
  if (rtentry != 0)
604
  if (rtentry != 0)
541
    {
605
    {
542
      NS_LOG_LOGIC ("Found unicast destination- calling unicast callback");
606
      NS_LOG_LOGIC ("Found unicast destination- calling unicast callback");
(-)a/src/internet/model/ipv4-global-routing.h (-1 / +5 lines)
 Lines 227-232    Link Here 
227
private:
227
private:
228
  /// Set to true if packets are randomly routed among ECMP; set to false for using only one route consistently
228
  /// Set to true if packets are randomly routed among ECMP; set to false for using only one route consistently
229
  bool m_randomEcmpRouting;
229
  bool m_randomEcmpRouting;
230
  /// Set to true if flows are randomly routed among ECMP; set to false for using only one route consistently
231
  bool m_flowEcmpRouting;
230
  /// Set to true if this interface should respond to interface events by globallly recomputing routes 
232
  /// Set to true if this interface should respond to interface events by globallly recomputing routes 
231
  bool m_respondToInterfaceEvents;
233
  bool m_respondToInterfaceEvents;
232
  /// A uniform random number generator for randomly routing packets among ECMP 
234
  /// A uniform random number generator for randomly routing packets among ECMP 
 Lines 242-248    Link Here 
242
  typedef std::list<Ipv4RoutingTableEntry *>::const_iterator ASExternalRoutesCI;
244
  typedef std::list<Ipv4RoutingTableEntry *>::const_iterator ASExternalRoutesCI;
243
  typedef std::list<Ipv4RoutingTableEntry *>::iterator ASExternalRoutesI;
245
  typedef std::list<Ipv4RoutingTableEntry *>::iterator ASExternalRoutesI;
244
246
245
  Ptr<Ipv4Route> LookupGlobal (Ipv4Address dest, Ptr<NetDevice> oif = 0);
247
  uint32_t GetTupleValue (const Ipv4Header &header, Ptr<const Packet> ipPayload);
248
249
  Ptr<Ipv4Route> LookupGlobal (const Ipv4Header &header, Ptr<const Packet> ipPayload, Ptr<NetDevice> oif = 0);
246
250
247
  HostRoutes m_hostRoutes;
251
  HostRoutes m_hostRoutes;
248
  NetworkRoutes m_networkRoutes;
252
  NetworkRoutes m_networkRoutes;

Return to bug 667