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

(-)a/src/routing/global-routing/global-route-manager-impl.cc (-106 / +396 lines)
 Lines 25-30    Link Here 
25
#include <utility>
25
#include <utility>
26
#include <vector>
26
#include <vector>
27
#include <queue>
27
#include <queue>
28
#include <algorithm>
29
#include <iostream>
28
#include "ns3/assert.h"
30
#include "ns3/assert.h"
29
#include "ns3/fatal-error.h"
31
#include "ns3/fatal-error.h"
30
#include "ns3/log.h"
32
#include "ns3/log.h"
 Lines 41-46    Link Here 
41
43
42
namespace ns3 {
44
namespace ns3 {
43
45
46
//std::ostream& 
47
//operator<< (std::ostream& os, const SPFVertex::ListOfIf_t& ifs)
48
//{
49
//  os << "{";
50
//  for (SPFVertex::ListOfIf_t::const_iterator iter = ifs.begin ();;)
51
//  {
52
//    os << *iter;
53
//    if (++iter != ifs.end ()) 
54
//      os << ", ";
55
//    else 
56
//      break;
57
//  }
58
//  os << "}";
59
//  return os;
60
//}
61
//
62
//std::ostream& 
63
//operator<< (std::ostream& os, const SPFVertex::ListOfAddr_t& addrs)
64
//{
65
//  os << "{";
66
//  for (SPFVertex::ListOfAddr_t::const_iterator iter = addrs.begin ();;)
67
//  {
68
//    os << *iter;
69
//    if (++iter != addrs.end ()) 
70
//      os << ", ";
71
//    else 
72
//      break;
73
//  }
74
//  os << "}";
75
//  return os;
76
//}
77
78
std::ostream& 
79
operator<< (std::ostream& os, const SPFVertex::NodeExit_t& exit)
80
{
81
  os << "(" << exit.first << " ," << exit.second << ")";
82
  return os;
83
}
84
85
std::ostream& 
86
operator<< (std::ostream& os, const SPFVertex::ListOfSPFVertex_t& vs)
87
{
88
  typedef SPFVertex::ListOfSPFVertex_t::const_iterator CIter_t;
89
  os << "{";
90
  for (CIter_t iter = vs.begin (); iter != vs.end ();)
91
  {
92
    os << (*iter)->m_vertexId;
93
    if (++iter != vs.end ()) 
94
      os << ", ";
95
    else 
96
      break;
97
  }
98
  os << "}";
99
  return os;
100
}
101
44
// ---------------------------------------------------------------------------
102
// ---------------------------------------------------------------------------
45
//
103
//
46
// SPFVertex Implementation
104
// SPFVertex Implementation
 Lines 54-60    Link Here 
54
  m_distanceFromRoot (SPF_INFINITY), 
112
  m_distanceFromRoot (SPF_INFINITY), 
55
  m_rootOif (SPF_INFINITY),
113
  m_rootOif (SPF_INFINITY),
56
  m_nextHop ("0.0.0.0"),
114
  m_nextHop ("0.0.0.0"),
57
  m_parent (0),
115
  m_parents (),
58
  m_children (),
116
  m_children (),
59
  m_vertexProcessed (false)
117
  m_vertexProcessed (false)
60
{
118
{
 Lines 67-77    Link Here 
67
  m_distanceFromRoot (SPF_INFINITY), 
125
  m_distanceFromRoot (SPF_INFINITY), 
68
  m_rootOif (SPF_INFINITY),
126
  m_rootOif (SPF_INFINITY),
69
  m_nextHop ("0.0.0.0"),
127
  m_nextHop ("0.0.0.0"),
70
  m_parent (0),
128
  m_parents (),
71
  m_children (),
129
  m_children (),
72
  m_vertexProcessed (false)
130
  m_vertexProcessed (false)
73
{
131
{
74
  NS_LOG_FUNCTION_NOARGS ();
132
  NS_LOG_FUNCTION_NOARGS ();
133
75
  if (lsa->GetLSType () == GlobalRoutingLSA::RouterLSA) 
134
  if (lsa->GetLSType () == GlobalRoutingLSA::RouterLSA) 
76
    {
135
    {
77
      NS_LOG_LOGIC ("Setting m_vertexType to VertexRouter");
136
      NS_LOG_LOGIC ("Setting m_vertexType to VertexRouter");
 Lines 86-102    Link Here 
86
145
87
SPFVertex::~SPFVertex ()
146
SPFVertex::~SPFVertex ()
88
{
147
{
89
  NS_LOG_FUNCTION_NOARGS ();
148
  NS_LOG_FUNCTION (m_vertexId);
90
  for ( ListOfSPFVertex_t::iterator i = m_children.begin ();
149
  
91
        i != m_children.end ();
150
  NS_LOG_LOGIC ("Children vertices - " << m_children);
92
        i++)
151
  NS_LOG_LOGIC ("Parent verteices - " << m_parents);
152
153
  // find this node from all its parents and remove the entry of this node
154
  // from all its parents
155
  for (ListOfSPFVertex_t::iterator piter = m_parents.begin (); 
156
    piter != m_parents.end (); 
157
    piter++)
158
  {
159
    // remove the current vertex from its parent'ss children list. Check
160
    // if the size of the list is reduced, or the child<->parent relation
161
    // is not bidirectional
162
    uint32_t orgCount = (*piter)->m_children.size ();
163
    (*piter)->m_children.remove (this);
164
    uint32_t newCount = (*piter)->m_children.size ();
165
    NS_ASSERT_MSG (orgCount > newCount, "Unable to find the current vertex from its parents --- impossible!");
166
  }
167
168
  // delete children
169
  while (m_children.size () > 0)
93
    {
170
    {
94
      SPFVertex *p = *i;
171
      // pop out children one by one. Some children may disappered 
172
      // when deleting some other children in the list. As a result,
173
      // it is necessary to use pop to walk through all children, intead
174
      // of suing iterator.
175
      //
176
      // Note that m_children.pop_front () is not necessary as this
177
      // p is removed from the children list when p is deleted
178
      SPFVertex* p = m_children.front ();
179
      // 'p' == 0, this child is already deleted by its other parent
180
      if (p == 0) continue;
181
      NS_LOG_LOGIC ("Parent vertex-" << m_vertexId << " deleting its child vertex-" << p->GetVertexId ());
95
      delete p;
182
      delete p;
96
      p = 0;
183
      p = 0;
97
      *i = 0;
98
    }
184
    }
99
  m_children.clear ();
185
  m_children.clear ();
186
  // delete parents
187
  m_parents.clear ();
188
  // delete root exit direction
189
  m_ecmpRootExits.clear ();
190
191
  NS_LOG_LOGIC ("Vertex-" << m_vertexId << " completed deleted");
100
}
192
}
101
193
102
  void 
194
  void 
 Lines 155-178    Link Here 
155
  return m_distanceFromRoot;
247
  return m_distanceFromRoot;
156
}
248
}
157
249
158
  void 
250
void 
159
SPFVertex::SetOutgoingInterfaceId (int32_t id)
251
SPFVertex::SetOutgoingInterfaceId (int32_t id)
160
{
252
{
161
  NS_LOG_FUNCTION (id);
253
  NS_LOG_FUNCTION (id);
254
255
  // always maintain only one output interface index when using setter/getter methods
162
  m_rootOif = id;
256
  m_rootOif = id;
163
}
257
}
164
258
165
  uint32_t 
259
uint32_t 
166
SPFVertex::GetOutgoingInterfaceId (void) const
260
SPFVertex::GetOutgoingInterfaceId (void) const
167
{
261
{
168
  NS_LOG_FUNCTION_NOARGS ();
262
  NS_LOG_FUNCTION_NOARGS ();
169
  return m_rootOif;
263
  return m_rootOif;
170
}
264
}
171
265
266
//void 
267
//SPFVertex::MergeOutgoingInterfaceId (const SPFVertex* v)
268
//{
269
//  NS_LOG_FUNCTION (v);
270
//
271
//  NS_LOG_LOGIC ("Before merge, list of root out-going interfaces = " << m_rootOif);
272
//  // combine the two lists first, and then remove any duplicated after
273
//  m_rootOif.insert (m_rootOif.end (), 
274
//    v->m_rootOif.begin (), v->m_rootOif.end ());
275
//  // remove duplication
276
//  m_rootOif.sort ();
277
//  m_rootOif.unique ();
278
//  NS_LOG_LOGIC ("After merge, list of root out-going interfaces = " << m_rootOif);
279
//}
280
172
  void 
281
  void 
173
SPFVertex::SetNextHop (Ipv4Address nextHop)
282
SPFVertex::SetNextHop (Ipv4Address nextHop)
174
{
283
{
175
  NS_LOG_FUNCTION (nextHop);
284
  NS_LOG_FUNCTION (nextHop);
285
286
  // always maintain only one nexthop when using setter/getter methods
176
  m_nextHop = nextHop;
287
  m_nextHop = nextHop;
177
}
288
}
178
289
 Lines 183-203    Link Here 
183
  return m_nextHop;
294
  return m_nextHop;
184
}
295
}
185
296
297
//void 
298
//SPFVertex::MergeNextHop (const SPFVertex* v)
299
//{
300
//  NS_LOG_FUNCTION (v);
301
//
302
//  NS_LOG_LOGIC ("Before merge, list of next hops = " << m_nextHop);
303
//  // combine the two lists first, and then remove any duplicated after
304
//  m_nextHop.insert (m_nextHop.end (), 
305
//    v->m_nextHop.begin (), v->m_nextHop.end ());
306
//  // remove duplication
307
//  m_nextHop.sort ();
308
//  m_nextHop.unique ();
309
//  NS_LOG_LOGIC ("After merge, list of next hops = " << m_nextHop);
310
//}
311
186
  void
312
  void
187
SPFVertex::SetParent (SPFVertex* parent)
313
SPFVertex::SetParent (SPFVertex* parent)
188
{
314
{
189
  NS_LOG_FUNCTION (parent);
315
  NS_LOG_FUNCTION (parent);
190
  m_parent = parent;
316
317
  // always maintain only one parent when using setter/getter methods
318
  m_parents.clear ();
319
  m_parents.push_back (parent);
191
}
320
}
192
321
193
  SPFVertex* 
322
  SPFVertex* 
194
SPFVertex::GetParent (void) const
323
SPFVertex::GetParent (uint32_t i) const
195
{
324
{
196
  NS_LOG_FUNCTION_NOARGS ();
325
  NS_LOG_FUNCTION_NOARGS ();
197
  return m_parent;
326
327
  // If the index i is out-of-range, return 0 and do nothing
328
  if (m_parents.size () <= i)
329
  {
330
    NS_LOG_LOGIC ("Index to SPFVertex's parent is out-of-range.");
331
    return 0;
332
  }
333
  ListOfSPFVertex_t::const_iterator iter = m_parents.begin ();
334
  while (i-- > 0) {iter++;}
335
  return *iter;
198
}
336
}
199
337
200
  uint32_t 
338
void 
339
SPFVertex::MergeParent (const SPFVertex* v)
340
{
341
  NS_LOG_FUNCTION (v);
342
343
  NS_LOG_LOGIC ("Before merge, list of parents = " << m_parents);
344
  // combine the two lists first, and then remove any duplicated after
345
  m_parents.insert (m_parents.end (), 
346
    v->m_parents.begin (), v->m_parents.end ());
347
  // remove duplication
348
  m_parents.sort ();
349
  m_parents.unique ();
350
  NS_LOG_LOGIC ("After merge, list of parents = " << m_parents);
351
}
352
353
void 
354
SPFVertex::SetRootExitDirection (Ipv4Address nextHop, int32_t id)
355
{
356
  NS_LOG_FUNCTION (nextHop << id);
357
  
358
  // always maintain only one root's exit
359
  m_ecmpRootExits.clear ();
360
  m_ecmpRootExits.push_back (NodeExit_t (nextHop, id));
361
  // update the following in order to be backward compatitable with
362
  // GetNextHop and GetOutgoingInterface methods
363
  m_nextHop = nextHop;
364
  m_rootOif = id;
365
}
366
367
void 
368
SPFVertex::SetRootExitDirection (SPFVertex::NodeExit_t exit)
369
{
370
  NS_LOG_FUNCTION (exit);
371
  SetRootExitDirection (exit.first, exit.second);
372
}
373
374
SPFVertex::NodeExit_t
375
SPFVertex::GetRootExitDirection (uint32_t i) const
376
{
377
  NS_LOG_FUNCTION (i);
378
  typedef ListOfNodeExit_t::const_iterator CIter_t;
379
380
  NS_ASSERT_MSG (i < m_ecmpRootExits.size (), "Index out-of-range when accessing SPFVertex::m_ecmpRootExits!");
381
  CIter_t iter = m_ecmpRootExits.begin ();
382
  while (i-- > 0) {iter++;}
383
384
  return *iter;
385
}
386
387
SPFVertex::NodeExit_t 
388
SPFVertex::GetRootExitDirection () const
389
{
390
  NS_LOG_FUNCTION_NOARGS ();
391
392
  NS_ASSERT_MSG (m_ecmpRootExits.size () <= 1, "Assumed there is at most one exit from the root to this vertex, but this assumption is violated!");
393
  return GetRootExitDirection (0);
394
}
395
396
void 
397
SPFVertex::MergeRootExitDirections (const SPFVertex* vertex)
398
{
399
  NS_LOG_FUNCTION (vertex);
400
401
  // obtain the external list of exit directions
402
  //
403
  // Append the external list into 'this' and remove duplication afterward
404
  const ListOfNodeExit_t& extList = vertex->m_ecmpRootExits;
405
  m_ecmpRootExits.insert (m_ecmpRootExits.end (), 
406
    extList.begin(), extList.end ());
407
  m_ecmpRootExits.sort ();
408
  m_ecmpRootExits.unique ();
409
}
410
411
void 
412
SPFVertex::InheritAllRootExitDirections (const SPFVertex* vertex)
413
{
414
  NS_LOG_FUNCTION (vertex);
415
416
  // discard all exit direction currently assoicated with this vertex,
417
  // and copy all the exit directions from the given vertex
418
  if (m_ecmpRootExits.size () > 0)
419
    NS_LOG_WARN ("x root exit directions in this vertex are going to be discarded");
420
  m_ecmpRootExits.clear ();
421
  m_ecmpRootExits.insert (m_ecmpRootExits.end (), 
422
    vertex->m_ecmpRootExits.begin (), vertex->m_ecmpRootExits.end ());
423
}
424
425
uint32_t 
426
SPFVertex::GetNRootExitDirections () const
427
{
428
  NS_LOG_FUNCTION_NOARGS ();
429
  return m_ecmpRootExits.size ();
430
}
431
432
uint32_t 
201
SPFVertex::GetNChildren (void) const
433
SPFVertex::GetNChildren (void) const
202
{
434
{
203
  NS_LOG_FUNCTION_NOARGS ();
435
  NS_LOG_FUNCTION_NOARGS ();
 Lines 341-347    Link Here 
341
573
342
GlobalRouteManagerImpl::GlobalRouteManagerImpl () 
574
GlobalRouteManagerImpl::GlobalRouteManagerImpl () 
343
: 
575
: 
344
  m_spfroot (0) 
576
  m_spfroot (0)
345
{
577
{
346
  NS_LOG_FUNCTION_NOARGS ();
578
  NS_LOG_FUNCTION_NOARGS ();
347
  m_lsdb = new GlobalRouteManagerLSDB ();
579
  m_lsdb = new GlobalRouteManagerLSDB ();
 Lines 649-663    Link Here 
649
// Is there already vertex w in candidate list?
881
// Is there already vertex w in candidate list?
650
      if (w_lsa->GetStatus () == GlobalRoutingLSA::LSA_SPF_NOT_EXPLORED)
882
      if (w_lsa->GetStatus () == GlobalRoutingLSA::LSA_SPF_NOT_EXPLORED)
651
        {
883
        {
652
653
// prepare vertex w
654
          w = new SPFVertex (w_lsa);
655
// Calculate nexthop to w
884
// Calculate nexthop to w
656
// We need to figure out how to actually get to the new router represented
885
// We need to figure out how to actually get to the new router represented
657
// by <w>.  This will (among other things) find the next hop address to send
886
// by <w>.  This will (among other things) find the next hop address to send
658
// packets destined for this network to, and also find the outbound interface
887
// packets destined for this network to, and also find the outbound interface
659
// used to forward the packets.
888
// used to forward the packets.
660
//
889
890
// prepare vertex w
891
          w = new SPFVertex (w_lsa);
661
          if (SPFNexthopCalculation (v, w, l, distance))
892
          if (SPFNexthopCalculation (v, w, l, distance))
662
            {
893
            {
663
              w_lsa->SetStatus (GlobalRoutingLSA::LSA_SPF_CANDIDATE);
894
              w_lsa->SetStatus (GlobalRoutingLSA::LSA_SPF_CANDIDATE);
 Lines 671-676    Link Here 
671
                v->GetVertexId () << ", distance: " <<
902
                v->GetVertexId () << ", distance: " <<
672
                w->GetDistanceFromRoot ());
903
                w->GetDistanceFromRoot ());
673
            }
904
            }
905
          else
906
            NS_ASSERT_MSG (0, "SPFNexthopCalculation never " 
907
              << "return false, but it does now!");
674
        }
908
        }
675
      else if (w_lsa->GetStatus () == GlobalRoutingLSA::LSA_SPF_CANDIDATE)
909
      else if (w_lsa->GetStatus () == GlobalRoutingLSA::LSA_SPF_CANDIDATE)
676
        {
910
        {
 Lines 681-702    Link Here 
681
//
915
//
682
// So, locate the vertex in the candidate queue and take a look at the 
916
// So, locate the vertex in the candidate queue and take a look at the 
683
// distance.
917
// distance.
684
          w = candidate.Find (w_lsa->GetLinkStateId ());
918
685
          if (w->GetDistanceFromRoot () < distance)
919
/* (quagga-0.98.6) W is already on the candidate list; call it cw.
920
* Compare the previously calculated cost (cw->distance)
921
* with the cost we just determined (w->distance) to see
922
* if we've found a shorter path.
923
*/
924
          SPFVertex* cw;
925
          cw = candidate.Find (w_lsa->GetLinkStateId ());
926
          if (cw->GetDistanceFromRoot () < distance)
686
            {
927
            {
687
//
928
//
688
// This is not a shorter path, so don't do anything.
929
// This is not a shorter path, so don't do anything.
689
//
930
//
690
              continue;
931
              continue;
691
            }
932
            }
692
          else if (w->GetDistanceFromRoot () == distance)
933
          else if (cw->GetDistanceFromRoot () == distance)
693
            {
934
            {
694
//
935
//
695
// This path is one with an equal cost.  Do nothing for now -- we're not doing
936
// This path is one with an equal cost.  
696
// equal-cost multipath cases yet.
697
//
937
//
938
              NS_LOG_LOGIC ("Equal cost multiple paths found.");
939
940
// At this point, there are two instances 'w' and 'cw' of the
941
// same vertex, the vertex that is currently being considered
942
// for adding into the shortest path tree. 'w' is the instance
943
// as seen from the root via vertex 'v', and 'cw' is the instance 
944
// as seen from the root via some other vertices other than 'v'.
945
// These two instances are being merged in the following codes.
946
// In particular, the parent nodes, the next hops, and the root's
947
// output interfaces of the two instances are being merged.
948
// 
949
// Note that this is functionally equivelent to calling
950
// ospf_nexthop_merge (cw->nexthop, w->nexthop) in quagga-0.98.6
951
// (ospf_spf.c::859), althrough the detail implemenation
952
// is very different from quagga (blame ns3::GlobalRouteManagerImpl)
953
954
// prepare vertex w
955
              w = new SPFVertex (w_lsa);
956
              SPFNexthopCalculation (v, w, l, distance);
957
              cw->MergeRootExitDirections (w);
958
              cw->MergeParent (w);
959
// SPFVertexAddParent (w) is necessary as the destructor of 
960
// SPFVertex checks if the vertex and its parent is linked
961
// bidirectionally
962
              SPFVertexAddParent (w);
963
              delete w;
698
            }
964
            }
699
          else
965
          else // cw->GetDistanceFromRoot () > w->GetDistanceFromRoot ()
700
            {
966
            {
701
// 
967
// 
702
// this path represents a new, lower-cost path to <w> (the vertex we found in
968
// this path represents a new, lower-cost path to <w> (the vertex we found in
 Lines 706-712    Link Here 
706
// N.B. the nexthop_calculation is conditional, if it finds a valid nexthop
972
// N.B. the nexthop_calculation is conditional, if it finds a valid nexthop
707
// it will call spf_add_parents, which will flush the old parents
973
// it will call spf_add_parents, which will flush the old parents
708
//
974
//
709
              if (SPFNexthopCalculation (v, w, l, distance))
975
              if (SPFNexthopCalculation (v, cw, l, distance))
710
                {
976
                {
711
//
977
//
712
// If we've changed the cost to get to the vertex represented by <w>, we 
978
// If we've changed the cost to get to the vertex represented by <w>, we 
 Lines 714-720    Link Here 
714
//
980
//
715
                  candidate.Reorder ();
981
                  candidate.Reorder ();
716
                }
982
                }
717
            } // new lower cost path found   
983
            } // new lower cost path found  
718
        } // end W is already on the candidate list
984
        } // end W is already on the candidate list
719
    } // end loop over the links in V's LSA
985
    } // end loop over the links in V's LSA
720
}
986
}
 Lines 808-827    Link Here 
808
// from the root node to the host represented by vertex <w>, you have to send
1074
// from the root node to the host represented by vertex <w>, you have to send
809
// the packet to the next hop address specified in w->m_nextHop.
1075
// the packet to the next hop address specified in w->m_nextHop.
810
//
1076
//
811
          w->SetNextHop (linkRemote->GetLinkData ());
1077
          Ipv4Address nextHop = linkRemote->GetLinkData ();
812
// 
1078
// 
813
// Now find the outgoing interface corresponding to the point to point link
1079
// Now find the outgoing interface corresponding to the point to point link
814
// from the perspective of <v> -- remember that <l> is the link "from"
1080
// from the perspective of <v> -- remember that <l> is the link "from"
815
// <v> "to" <w>.
1081
// <v> "to" <w>.
816
//
1082
//
817
          w->SetOutgoingInterfaceId (
1083
          uint32_t outIf = FindOutgoingInterfaceId (l->GetLinkData ());
818
            FindOutgoingInterfaceId (l->GetLinkData ()));
1084
1085
          w->SetRootExitDirection (nextHop, outIf);
819
          w->SetDistanceFromRoot (distance);
1086
          w->SetDistanceFromRoot (distance);
820
          w->SetParent (v);
1087
          w->SetParent (v);
821
          NS_LOG_LOGIC ("Next hop from " << 
1088
          NS_LOG_LOGIC ("Next hop from " << 
822
            v->GetVertexId () << " to " << w->GetVertexId () << 
1089
            v->GetVertexId () << " to " << w->GetVertexId () << 
823
            " goes through next hop " << w->GetNextHop () <<
1090
            " goes through next hop " << nextHop <<
824
            " via outgoing interface " << w->GetOutgoingInterfaceId () <<
1091
            " via outgoing interface " << outIf <<
825
            " with distance " << distance);
1092
            " with distance " << distance);
826
        }  // end W is a router vertes
1093
        }  // end W is a router vertes
827
      else 
1094
      else 
 Lines 831-844    Link Here 
831
          GlobalRoutingLSA* w_lsa = w->GetLSA ();
1098
          GlobalRoutingLSA* w_lsa = w->GetLSA ();
832
          NS_ASSERT (w_lsa->GetLSType () == GlobalRoutingLSA::NetworkLSA);
1099
          NS_ASSERT (w_lsa->GetLSType () == GlobalRoutingLSA::NetworkLSA);
833
// Find outgoing interface ID for this network
1100
// Find outgoing interface ID for this network
834
          w->SetOutgoingInterfaceId (
1101
          uint32_t outIf = FindOutgoingInterfaceId (w_lsa->GetLinkStateId (), 
835
            FindOutgoingInterfaceId (w_lsa->GetLinkStateId (), 
1102
            w_lsa->GetNetworkLSANetworkMask () );
836
            w_lsa->GetNetworkLSANetworkMask () ));
1103
// Set the next hop to 0.0.0.0 meaning "not exist"
1104
          Ipv4Address nextHop = Ipv4Address::GetZero ();
1105
          w->SetRootExitDirection (nextHop, outIf);
837
          w->SetDistanceFromRoot (distance);
1106
          w->SetDistanceFromRoot (distance);
838
          w->SetParent (v);
1107
          w->SetParent (v);
839
          NS_LOG_LOGIC ("Next hop from " << 
1108
          NS_LOG_LOGIC ("Next hop from " << 
840
            v->GetVertexId () << " to network " << w->GetVertexId () << 
1109
            v->GetVertexId () << " to network " << w->GetVertexId () << 
841
            " via outgoing interface " << w->GetOutgoingInterfaceId () <<
1110
            " via outgoing interface " << outIf <<
842
            " with distance " << distance);
1111
            " with distance " << distance);
843
          return 1;
1112
          return 1;
844
        }
1113
        }
 Lines 862-879    Link Here 
862
 * use can then be derived from the next hop IP address (or 
1131
 * use can then be derived from the next hop IP address (or 
863
 * it can be inherited from the parent network).
1132
 * it can be inherited from the parent network).
864
 */
1133
 */
865
                w->SetNextHop (linkRemote->GetLinkData ());
1134
                Ipv4Address nextHop = linkRemote->GetLinkData ();
866
                w->SetOutgoingInterfaceId (v->GetOutgoingInterfaceId ());
1135
                uint32_t outIf = v->GetRootExitDirection ().second;
1136
                w->SetRootExitDirection (nextHop, outIf);
867
                NS_LOG_LOGIC ("Next hop from " << 
1137
                NS_LOG_LOGIC ("Next hop from " << 
868
                  v->GetVertexId () << " to " << w->GetVertexId () << 
1138
                  v->GetVertexId () << " to " << w->GetVertexId () << 
869
                  " goes through next hop " << w->GetNextHop () <<
1139
                  " goes through next hop " << nextHop <<
870
                  " via outgoing interface " << w->GetOutgoingInterfaceId ());
1140
                  " via outgoing interface " << outIf);
871
            }
1141
            }
872
        }
1142
        }
873
      else 
1143
      else 
874
        {
1144
        {
875
          w->SetNextHop (v->GetNextHop ());
1145
          w->SetRootExitDirection (v->GetRootExitDirection ());
876
          w->SetOutgoingInterfaceId (v->GetOutgoingInterfaceId ());
877
        }
1146
        }
878
    }
1147
    }
879
  else 
1148
  else 
 Lines 891-898    Link Here 
891
// (shortest) paths.  So the next hop and outoing interface remain the same
1160
// (shortest) paths.  So the next hop and outoing interface remain the same
892
// (are inherited).
1161
// (are inherited).
893
//
1162
//
894
      w->SetNextHop (v->GetNextHop ());
1163
      w->InheritAllRootExitDirections (v);
895
      w->SetOutgoingInterfaceId (v->GetOutgoingInterfaceId ());
896
    }
1164
    }
897
//
1165
//
898
// In all cases, we need valid values for the distance metric and a parent.
1166
// In all cases, we need valid values for the distance metric and a parent.
 Lines 1190-1197    Link Here 
1190
//
1458
//
1191
// Note that when there is a choice of vertices closest to the root, network
1459
// Note that when there is a choice of vertices closest to the root, network
1192
// vertices must be chosen before router vertices in order to necessarily
1460
// vertices must be chosen before router vertices in order to necessarily
1193
// find all equal-cost paths. We don't do this at this moment, we should add
1461
// find all equal-cost paths. This is done by using the patch 
1194
// the treatment above codes. -- kunihiro. 
1462
// 'change-candidate-queue-to-consider-lsa-type-when-ordering.patch'
1195
//
1463
//
1196
// RFC2328 16.1. (4). 
1464
// RFC2328 16.1. (4). 
1197
//
1465
//
 Lines 1367-1378    Link Here 
1367
          Ipv4Mask tempmask ("255.255.255.0");
1635
          Ipv4Mask tempmask ("255.255.255.0");
1368
          Ipv4Address tempip = l->GetLinkId ();
1636
          Ipv4Address tempip = l->GetLinkId ();
1369
          tempip = tempip.CombineMask (tempmask);
1637
          tempip = tempip.CombineMask (tempmask);
1370
1371
          NS_LOG_LOGIC (" Node " << node->GetId () <<
1372
            " add route to " << tempip <<
1373
            " with mask " << tempmask <<
1374
            " using next hop " << v->GetNextHop () <<
1375
            " via interface " << v->GetOutgoingInterfaceId ());
1376
//
1638
//
1377
// Here's why we did all of that work.  We're going to add a host route to the
1639
// Here's why we did all of that work.  We're going to add a host route to the
1378
// host address found in the m_linkData field of the point-to-point link
1640
// host address found in the m_linkData field of the point-to-point link
 Lines 1394-1414    Link Here 
1394
            }
1656
            }
1395
          Ptr<Ipv4GlobalRouting> gr = router->GetRoutingProtocol ();
1657
          Ptr<Ipv4GlobalRouting> gr = router->GetRoutingProtocol ();
1396
          NS_ASSERT (gr);
1658
          NS_ASSERT (gr);
1397
          if (v->GetOutgoingInterfaceId () >= 0)
1659
          // walk through all next-hop-IPs and out-going-interfaces for reaching
1398
            {
1660
          // the stub network gateway 'v' from the root node
1399
              gr->AddNetworkRouteTo (tempip, tempmask, v->GetNextHop (), v->GetOutgoingInterfaceId ());
1661
          for (uint32_t i = 0; i < v->GetNRootExitDirections (); i++)
1400
              NS_LOG_LOGIC ("Node " << node->GetId () <<
1662
          {
1401
                " add network route to " << tempip <<
1663
            SPFVertex::NodeExit_t exit = v->GetRootExitDirection (i);
1402
                " using next hop " << v->GetNextHop () <<
1664
            Ipv4Address nextHop = exit.first;
1403
                " via interface " << v->GetOutgoingInterfaceId ());
1665
            int32_t outIf = exit.second;
1404
            }
1666
            if (outIf >= 0)
1405
          else
1667
              {
1406
            {
1668
                gr->AddNetworkRouteTo (tempip, tempmask, nextHop, outIf);
1407
              NS_LOG_LOGIC ("Node " << node->GetId () <<
1669
                NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () <<
1408
                " NOT able to add network route to " << tempip <<
1670
                  " add network route to " << tempip <<
1409
                " using next hop " << v->GetNextHop () <<
1671
                  " using next hop " << nextHop <<
1410
                " since outgoing interface id is negative");
1672
                  " via interface " << outIf);
1411
            }
1673
              }
1674
            else
1675
              {
1676
                NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () <<
1677
                  " NOT able to add network route to " << tempip <<
1678
                  " using next hop " << nextHop <<
1679
                  " since outgoing interface id is negative");
1680
              }
1681
          }
1412
          return;
1682
          return;
1413
        } // if
1683
        } // if
1414
    } // for
1684
    } // for
 Lines 1598-1608    Link Here 
1598
                {
1868
                {
1599
                  continue;
1869
                  continue;
1600
                }
1870
                }
1601
1602
              NS_LOG_LOGIC (" Node " << node->GetId () <<
1603
                " add route to " << lr->GetLinkData () <<
1604
                " using next hop " << v->GetNextHop () <<
1605
                " via interface " << v->GetOutgoingInterfaceId ());
1606
//
1871
//
1607
// Here's why we did all of that work.  We're going to add a host route to the
1872
// Here's why we did all of that work.  We're going to add a host route to the
1608
// host address found in the m_linkData field of the point-to-point link
1873
// host address found in the m_linkData field of the point-to-point link
 Lines 1623-1644    Link Here 
1623
                }
1888
                }
1624
              Ptr<Ipv4GlobalRouting> gr = router->GetRoutingProtocol ();
1889
              Ptr<Ipv4GlobalRouting> gr = router->GetRoutingProtocol ();
1625
              NS_ASSERT (gr);
1890
              NS_ASSERT (gr);
1626
              if (v->GetOutgoingInterfaceId () >= 0)
1891
              // walk through all available exit directions due to ECMP,
1627
                {
1892
              // and add host route for each of the exit direction toward
1628
                  gr->AddHostRouteTo (lr->GetLinkData (), v->GetNextHop (),
1893
              // the vertex 'v'
1629
                    v->GetOutgoingInterfaceId ());
1894
              for (uint32_t i = 0; i < v->GetNRootExitDirections (); i++)
1630
                  NS_LOG_LOGIC ("Node " << node->GetId () <<
1895
              {
1631
                    " adding host route to " << lr->GetLinkData () <<
1896
                SPFVertex::NodeExit_t exit = v->GetRootExitDirection (i);
1632
                    " using next hop " << v->GetNextHop () <<
1897
                Ipv4Address nextHop = exit.first;
1633
                    " and outgoing interface " << v->GetOutgoingInterfaceId ());
1898
                int32_t outIf = exit.second;
1634
                }
1899
                if (outIf >= 0)
1635
              else
1900
                  {
1636
                {
1901
                    gr->AddHostRouteTo (lr->GetLinkData (), nextHop,
1637
                  NS_LOG_LOGIC ("Node " << node->GetId () <<
1902
                      outIf);
1638
                    " NOT able to add host route to " << lr->GetLinkData () <<
1903
                    NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () <<
1639
                    " using next hop " << v->GetNextHop () <<
1904
                      " adding host route to " << lr->GetLinkData () <<
1640
                    " since outgoing interface id is negative");
1905
                      " using next hop " << nextHop <<
1641
                }
1906
                      " and outgoing interface " << outIf);
1907
                  }
1908
                else
1909
                  {
1910
                    NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () <<
1911
                      " NOT able to add host route to " << lr->GetLinkData () <<
1912
                      " using next hop " << nextHop <<
1913
                      " since outgoing interface id is negative " << outIf);
1914
                  }
1915
              } // for all routes from the root the vertex 'v'
1642
            }
1916
            }
1643
//
1917
//
1644
// Done adding the routes for the selected node.
1918
// Done adding the routes for the selected node.
 Lines 1726-1746    Link Here 
1726
            }
2000
            }
1727
          Ptr<Ipv4GlobalRouting> gr = router->GetRoutingProtocol ();
2001
          Ptr<Ipv4GlobalRouting> gr = router->GetRoutingProtocol ();
1728
          NS_ASSERT (gr);
2002
          NS_ASSERT (gr);
1729
          if (v->GetOutgoingInterfaceId () >= 0)
2003
          // walk through all available exit directions due to ECMP,
1730
            {
2004
          // and add host route for each of the exit direction toward
1731
              gr->AddNetworkRouteTo (tempip, tempmask, v->GetNextHop (),
2005
          // the vertex 'v'
1732
                v->GetOutgoingInterfaceId ());
2006
          for (uint32_t i = 0; i < v->GetNRootExitDirections (); i++)
1733
              NS_LOG_LOGIC ("Node " << node->GetId () <<
2007
          {
1734
                " add network route to " << tempip <<
2008
            SPFVertex::NodeExit_t exit = v->GetRootExitDirection (i);
1735
                " using next hop " << v->GetNextHop () <<
2009
            Ipv4Address nextHop = exit.first;
1736
                " via interface " << v->GetOutgoingInterfaceId ());
2010
            int32_t outIf = exit.second;
1737
            }
2011
1738
          else
2012
            if (outIf >= 0)
1739
            {
2013
              {
1740
              NS_LOG_LOGIC ("Node " << node->GetId () <<
2014
                gr->AddNetworkRouteTo (tempip, tempmask, nextHop, outIf);
1741
                " NOT able to add network route to " << tempip <<
2015
                NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () <<
1742
                " using next hop " << v->GetNextHop () <<
2016
                  " add network route to " << tempip <<
1743
                " since outgoing interface id is negative");
2017
                  " using next hop " << nextHop <<
2018
                  " via interface " << outIf);
2019
              }
2020
            else
2021
              {
2022
                NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () <<
2023
                  " NOT able to add network route to " << tempip <<
2024
                  " using next hop " << nextHop <<
2025
                  " since outgoing interface id is negative " << outIf);
2026
              }
1744
            }
2027
            }
1745
        }
2028
        }
1746
    } 
2029
    } 
 Lines 1755-1767    Link Here 
1755
// Given a pointer to a vertex, it links back to the vertex's parent that it
2038
// Given a pointer to a vertex, it links back to the vertex's parent that it
1756
// already has set and adds itself to that vertex's list of children.
2039
// already has set and adds itself to that vertex's list of children.
1757
//
2040
//
1758
// For now, only one parent (not doing equal-cost multipath)
1759
//
1760
  void
2041
  void
1761
GlobalRouteManagerImpl::SPFVertexAddParent (SPFVertex* v)
2042
GlobalRouteManagerImpl::SPFVertexAddParent (SPFVertex* v)
1762
{
2043
{
1763
  NS_LOG_FUNCTION (v);
2044
  NS_LOG_FUNCTION (v);
1764
  v->GetParent ()->AddChild (v);
2045
2046
  for (uint32_t i=0;;)
2047
  {
2048
    SPFVertex* parent;
2049
    // check if all parents of vertex v
2050
    if ((parent = v->GetParent (i++)) == 0)
2051
      break;
2052
    parent->AddChild (v);
2053
  }
2054
  //v->GetParent ()->AddChild (v);
1765
}
2055
}
1766
2056
1767
} // namespace ns3
2057
} // namespace ns3
(-)a/src/routing/global-routing/global-route-manager-impl.h (-6 / +159 lines)
 Lines 255-260    Link Here 
255
  void SetDistanceFromRoot (uint32_t distance);
255
  void SetDistanceFromRoot (uint32_t distance);
256
256
257
/**
257
/**
258
 * \deprecated Use GetRootExitDirection instead
259
 *
258
 * @brief Get the interface ID that should be used to begin forwarding packets
260
 * @brief Get the interface ID that should be used to begin forwarding packets
259
 * from the root SPFVertex to "this" SPFVertex.
261
 * from the root SPFVertex to "this" SPFVertex.
260
 * @internal
262
 * @internal
 Lines 294-302    Link Here 
294
 * @returns The interface index to use when forwarding packets to the host
296
 * @returns The interface index to use when forwarding packets to the host
295
 * or network represented by "this" SPFVertex.
297
 * or network represented by "this" SPFVertex.
296
 */
298
 */
297
  uint32_t GetOutgoingInterfaceId (void) const;
299
  uint32_t GetOutgoingInterfaceId (void) const NS_DEPRECATED;
298
300
299
/**
301
/**
302
 * \deprecated Use SetRootExitDirection instead
303
 *
300
 * @brief Set the interface ID that should be used to begin forwarding packets
304
 * @brief Set the interface ID that should be used to begin forwarding packets
301
 * from the root SPFVertex to "this" SPFVertex.
305
 * from the root SPFVertex to "this" SPFVertex.
302
 * @internal
306
 * @internal
 Lines 336-344    Link Here 
336
 * @param id The interface index to use when forwarding packets to the host or
340
 * @param id The interface index to use when forwarding packets to the host or
337
 * network represented by "this" SPFVertex.
341
 * network represented by "this" SPFVertex.
338
 */
342
 */
339
  void SetOutgoingInterfaceId (int32_t id);
343
  void SetOutgoingInterfaceId (int32_t id) NS_DEPRECATED;
340
344
341
/**
345
/**
346
 * \deprecated Use GetRootExitDirection instead
347
 *
342
 * @brief Get the IP address that should be used to begin forwarding packets 
348
 * @brief Get the IP address that should be used to begin forwarding packets 
343
 * from the root SPFVertex to "this" SPFVertex.
349
 * from the root SPFVertex to "this" SPFVertex.
344
 * @internal
350
 * @internal
 Lines 379-387    Link Here 
379
 * @returns The IP address to use when forwarding packets to the host
385
 * @returns The IP address to use when forwarding packets to the host
380
 * or network represented by "this" SPFVertex.
386
 * or network represented by "this" SPFVertex.
381
 */
387
 */
382
  Ipv4Address GetNextHop (void) const;
388
  Ipv4Address GetNextHop (void) const NS_DEPRECATED;
383
389
384
/**
390
/**
391
 * \deprecated Use SetRootExitDirection instead
392
 *
385
 * @brief Set the IP address that should be used to begin forwarding packets 
393
 * @brief Set the IP address that should be used to begin forwarding packets 
386
 * from the root SPFVertex to "this" SPFVertex.
394
 * from the root SPFVertex to "this" SPFVertex.
387
 * @internal
395
 * @internal
 Lines 422-428    Link Here 
422
 * @param nextHop The IP address to use when forwarding packets to the host
430
 * @param nextHop The IP address to use when forwarding packets to the host
423
 * or network represented by "this" SPFVertex.
431
 * or network represented by "this" SPFVertex.
424
 */
432
 */
425
  void SetNextHop (Ipv4Address nextHop);
433
  void SetNextHop (Ipv4Address nextHop) NS_DEPRECATED;
434
/**
435
 * @brief Set the IP address and out-going interface index that should be used 
436
 * to begin forwarding packets from the root SPFVertex to "this" SPFVertex.
437
 * @internal
438
 *
439
 * Each router node in the simulation is associated with an SPFVertex object.
440
 * When calculating routes, each of these routers is, in turn, chosen as the 
441
 * "root" of the calculation and routes to all of the other routers are
442
 * eventually saved in the routing tables of each of the chosen nodes.
443
 *
444
 * The "Root" vertex is then the SPFVertex representing the router that is
445
 * having its routing tables set.  The "this" SPFVertex is the vertex that
446
 * represents the host or network to which a route is being calculated from 
447
 * the root.  The IP address that we're asking for is the address on the 
448
 * remote side of a link off of the root node that should be used as the
449
 * destination for packets along the path to "this" vertex.
450
 *
451
 * When initializing the root SPFVertex, the IP address used when forwarding
452
 * packets is determined by examining the Global Router Link Records of the
453
 * Link State Advertisement generated by the root node's GlobalRouter.  This
454
 * address is used to forward packets off of the root's network down those
455
 * links.  As other vertices / nodes are discovered which are further away
456
 * from the root, they will be accessible down one of the paths via a link
457
 * described by one of these Global Router Link Records.
458
 * 
459
 * To forward packets to these hosts or networks, the root node must begin
460
 * the forwarding process by sending the packets to a first hop router down
461
 * an interface.  This means that the first hop address and interface ID must
462
 * be the same for all downstream SPFVertices.  We call this "inheriting"
463
 * the interface and next hop.
464
 *
465
 * In this method we are telling the root node which exit direction it should send
466
 * should I send a packet to the network or host represented by 'this' SPFVertex.
467
 *
468
 * @see GlobalRouter
469
 * @see GlobalRoutingLSA
470
 * @see GlobalRoutingLinkRecord
471
 * @param nextHop The IP address to use when forwarding packets to the host
472
 * or network represented by "this" SPFVertex.
473
 * @param id The interface index to use when forwarding packets to the host or
474
 * network represented by "this" SPFVertex.
475
 */
476
  void SetRootExitDirection (Ipv4Address nextHop, int32_t id = SPF_INFINITY);
477
  typedef std::pair<Ipv4Address, int32_t> NodeExit_t;
478
/**
479
 * @brief Set the IP address and out-going interface index that should be used 
480
 * to begin forwarding packets from the root SPFVertex to "this" SPFVertex.
481
 * @internal
482
 *
483
 * Each router node in the simulation is associated with an SPFVertex object.
484
 * When calculating routes, each of these routers is, in turn, chosen as the 
485
 * "root" of the calculation and routes to all of the other routers are
486
 * eventually saved in the routing tables of each of the chosen nodes.
487
 *
488
 * The "Root" vertex is then the SPFVertex representing the router that is
489
 * having its routing tables set.  The "this" SPFVertex is the vertex that
490
 * represents the host or network to which a route is being calculated from 
491
 * the root.  The IP address that we're asking for is the address on the 
492
 * remote side of a link off of the root node that should be used as the
493
 * destination for packets along the path to "this" vertex.
494
 *
495
 * When initializing the root SPFVertex, the IP address used when forwarding
496
 * packets is determined by examining the Global Router Link Records of the
497
 * Link State Advertisement generated by the root node's GlobalRouter.  This
498
 * address is used to forward packets off of the root's network down those
499
 * links.  As other vertices / nodes are discovered which are further away
500
 * from the root, they will be accessible down one of the paths via a link
501
 * described by one of these Global Router Link Records.
502
 * 
503
 * To forward packets to these hosts or networks, the root node must begin
504
 * the forwarding process by sending the packets to a first hop router down
505
 * an interface.  This means that the first hop address and interface ID must
506
 * be the same for all downstream SPFVertices.  We call this "inheriting"
507
 * the interface and next hop.
508
 *
509
 * In this method we are telling the root node which exit direction it should send
510
 * should I send a packet to the network or host represented by 'this' SPFVertex.
511
 *
512
 * @see GlobalRouter
513
 * @see GlobalRoutingLSA
514
 * @see GlobalRoutingLinkRecord
515
 * @param nextHop The IP address to use when forwarding packets to the host
516
 * or network represented by "this" SPFVertex.
517
 * @param exit The pair of next-hop-IP and out-going-interface-index to use when 
518
 * forwarding packets to the host or network represented by "this" SPFVertex.
519
 */
520
  void SetRootExitDirection (SPFVertex::NodeExit_t exit);
521
 /**
522
  * \brief Obtain a pair indicating the exit direction from the root
523
  *
524
  * \param i An index to a pair
525
  * \return A pair of next-hop-IP and out-going-interface-index for 
526
  * indicating an exit direction from the root. It is 0 if the index 'i'
527
  * is out-of-range
528
  */
529
  NodeExit_t GetRootExitDirection (uint32_t i) const;
530
  /**
531
   * \brief Obtain a pair indicating the exit direction from the root
532
   *
533
   * This method assumes there is only a single exit direction from the root.
534
   * Error occur if this assumption is invalid.
535
   *
536
   * \return The pair of next-hop-IP and out-going-interface-index for reaching
537
   * 'this' vertex from the root
538
   */
539
  NodeExit_t GetRootExitDirection () const;
540
  /**
541
   * \brief Merge into 'this' vertex the list of exit directions from
542
   * another vertex
543
   *
544
   * This merge is necessary when ECMP are found. 
545
   *
546
   * \param vertex From which the list of exit directions are obtain
547
   * and are merged into 'this' vertex
548
   */
549
  void MergeRootExitDirections (const SPFVertex* vertex);
550
  /**
551
   * \brief Inherit all root exit directions from a given vertex to 'this' vertex
552
   * \param vertex The vertex from which all root exit directions are to be inherrited
553
   *
554
   * After the call of this method, the original root exit directions
555
   * in 'this' vertex are all lost.
556
   */
557
  void InheritAllRootExitDirections (const SPFVertex* vertex);
558
  /**
559
   * \brief Get the number of exit directions from root for reaching 'this' vertex
560
   * \return The number of exit directions from root
561
   */
562
  uint32_t GetNRootExitDirections () const;
426
563
427
/**
564
/**
428
 * @brief Get a pointer to the SPFVector that is the parent of "this" 
565
 * @brief Get a pointer to the SPFVector that is the parent of "this" 
 Lines 440-449    Link Here 
440
 * This method returns a pointer to the parent node of "this" SPFVertex
577
 * This method returns a pointer to the parent node of "this" SPFVertex
441
 * (both of which reside in that SPF tree).
578
 * (both of which reside in that SPF tree).
442
 *
579
 *
580
 * @param i The index to one of the parents
443
 * @returns A pointer to the SPFVertex that is the parent of "this" SPFVertex
581
 * @returns A pointer to the SPFVertex that is the parent of "this" SPFVertex
444
 * in the SPF tree.
582
 * in the SPF tree.
445
 */
583
 */
446
  SPFVertex* GetParent (void) const;
584
  SPFVertex* GetParent (uint32_t i = 0) const;
447
585
448
/**
586
/**
449
 * @brief Set the pointer to the SPFVector that is the parent of "this" 
587
 * @brief Set the pointer to the SPFVector that is the parent of "this" 
 Lines 465-470    Link Here 
465
 * SPFVertex* in the SPF tree.
603
 * SPFVertex* in the SPF tree.
466
 */
604
 */
467
  void SetParent (SPFVertex* parent);
605
  void SetParent (SPFVertex* parent);
606
  /**
607
   * \brief Merge the Parent list from the v into this vertex
608
   *
609
   * \param v The vertex from which its list of Parent is read
610
   * and then merged into the list of Parent of *this* vertex.
611
   * Note that the list in v remains intact
612
   */
613
  void MergeParent (const SPFVertex* v);
468
614
469
/**
615
/**
470
 * @brief Get the number of children of "this" SPFVertex.
616
 * @brief Get the number of children of "this" SPFVertex.
 Lines 570-577    Link Here 
570
  uint32_t m_distanceFromRoot;
716
  uint32_t m_distanceFromRoot;
571
  int32_t m_rootOif;
717
  int32_t m_rootOif;
572
  Ipv4Address m_nextHop;
718
  Ipv4Address m_nextHop;
573
  SPFVertex* m_parent;
719
  typedef std::list< NodeExit_t > ListOfNodeExit_t;
720
  /// store the multiple root's exits for supporting ECMP
721
  ListOfNodeExit_t m_ecmpRootExits;
574
  typedef std::list<SPFVertex*> ListOfSPFVertex_t;
722
  typedef std::list<SPFVertex*> ListOfSPFVertex_t;
723
  ListOfSPFVertex_t m_parents;
575
  ListOfSPFVertex_t m_children;
724
  ListOfSPFVertex_t m_children;
576
  bool m_vertexProcessed; 
725
  bool m_vertexProcessed; 
577
726
 Lines 586-591    Link Here 
586
 * need for it and a compiler provided shallow copy would be wrong.
735
 * need for it and a compiler provided shallow copy would be wrong.
587
 */
736
 */
588
  SPFVertex& operator= (SPFVertex& v);
737
  SPFVertex& operator= (SPFVertex& v);
738
739
  //friend std::ostream& operator<< (std::ostream& os, const ListOfIf_t& ifs);
740
  //friend std::ostream& operator<< (std::ostream& os, const ListOfAddr_t& addrs);
741
  friend std::ostream& operator<< (std::ostream& os, const SPFVertex::ListOfSPFVertex_t& vs);
589
};
742
};
590
743
591
/**
744
/**
(-)a/src/routing/global-routing/ipv4-global-routing.cc (-11 / +29 lines)
 Lines 22-28    Link Here 
22
#include "ns3/net-device.h"
22
#include "ns3/net-device.h"
23
#include "ns3/ipv4-route.h"
23
#include "ns3/ipv4-route.h"
24
#include "ns3/ipv4-routing-table-entry.h"
24
#include "ns3/ipv4-routing-table-entry.h"
25
#include "ns3/boolean.h"
25
#include "ipv4-global-routing.h"
26
#include "ipv4-global-routing.h"
27
#include <vector>
26
28
27
NS_LOG_COMPONENT_DEFINE ("Ipv4GlobalRouting");
29
NS_LOG_COMPONENT_DEFINE ("Ipv4GlobalRouting");
28
30
 Lines 35-45    Link Here 
35
{ 
37
{ 
36
  static TypeId tid = TypeId ("ns3::Ipv4GlobalRouting")
38
  static TypeId tid = TypeId ("ns3::Ipv4GlobalRouting")
37
    .SetParent<Object> ()
39
    .SetParent<Object> ()
40
    .AddAttribute ("RandomEcmpRouting",
41
                   "Set to true if packets are randomly routed among ECMP; set to false for using only one route consistently",
42
                   BooleanValue(false),
43
                   MakeBooleanAccessor (&Ipv4GlobalRouting::m_randomEcmpRouting),
44
                   MakeBooleanChecker ())
38
    ;
45
    ;
39
  return tid;
46
  return tid;
40
}
47
}
41
48
42
Ipv4GlobalRouting::Ipv4GlobalRouting () 
49
Ipv4GlobalRouting::Ipv4GlobalRouting () 
50
: m_randomEcmpRouting (false) 
43
{
51
{
44
  NS_LOG_FUNCTION_NOARGS ();
52
  NS_LOG_FUNCTION_NOARGS ();
45
}
53
}
 Lines 103-111    Link Here 
103
{
111
{
104
  NS_LOG_FUNCTION_NOARGS ();
112
  NS_LOG_FUNCTION_NOARGS ();
105
  Ptr<Ipv4Route> rtentry = 0;
113
  Ptr<Ipv4Route> rtentry = 0;
106
  bool found = false;
107
  Ipv4RoutingTableEntry* route = 0;
114
  Ipv4RoutingTableEntry* route = 0;
115
  // store all available routes that bring packets to their destination
116
  typedef std::vector<Ipv4RoutingTableEntry*> RouteVec_t;
117
  RouteVec_t allRoutes;
108
118
119
  NS_LOG_LOGIC ("Number of m_hostRoutes = " << m_hostRoutes.size ());
109
  for (HostRoutesCI i = m_hostRoutes.begin (); 
120
  for (HostRoutesCI i = m_hostRoutes.begin (); 
110
       i != m_hostRoutes.end (); 
121
       i != m_hostRoutes.end (); 
111
       i++) 
122
       i++) 
 Lines 113-126    Link Here 
113
      NS_ASSERT ((*i)->IsHost ());
124
      NS_ASSERT ((*i)->IsHost ());
114
      if ((*i)->GetDest ().IsEqual (dest)) 
125
      if ((*i)->GetDest ().IsEqual (dest)) 
115
        {
126
        {
116
          NS_LOG_LOGIC ("Found global host route" << *i); 
127
          allRoutes.push_back (*i);
117
          route = (*i);
128
          NS_LOG_LOGIC (allRoutes.size () << "Found global host route" << *i);           
118
          found = true; 
119
          break;
120
        }
129
        }
121
    }
130
    }
122
  if (found == false)
131
  if (allRoutes.size () == 0) // if no host route is found
123
    {
132
    {
133
      NS_LOG_LOGIC ("Number of m_networkRoutes" << m_networkRoutes.size ());
124
      for (NetworkRoutesI j = m_networkRoutes.begin (); 
134
      for (NetworkRoutesI j = m_networkRoutes.begin (); 
125
           j != m_networkRoutes.end (); 
135
           j != m_networkRoutes.end (); 
126
           j++) 
136
           j++) 
 Lines 130-144    Link Here 
130
          Ipv4Address entry = (*j)->GetDestNetwork ();
140
          Ipv4Address entry = (*j)->GetDestNetwork ();
131
          if (mask.IsMatch (dest, entry)) 
141
          if (mask.IsMatch (dest, entry)) 
132
            {
142
            {
133
              NS_LOG_LOGIC ("Found global network route" << *j); 
143
              allRoutes.push_back (*j);
134
              route = (*j);
144
              NS_LOG_LOGIC (allRoutes.size () << "Found global network route" << *j); 
135
              found = true;
136
              break;
137
            }
145
            }
138
        }
146
        }
139
    }
147
    }
140
  if (found == true)
148
  if (allRoutes.size () > 0) // if route(s) is found
141
    {
149
    {
150
      // pick up one of the routes uniformly at random if random
151
      // ECMP routing is enabled, or always select the first route
152
      // consistently if random ECMP routing is disabled
153
      uint32_t selectIndex;
154
      if (m_randomEcmpRouting)
155
        selectIndex = m_rand.GetInteger (0, allRoutes.size ()-1);
156
      else 
157
        selectIndex = 0;
158
      route = allRoutes.at (selectIndex);
159
      // crete a Ipv4Route object from the selected routing table entry
142
      rtentry = Create<Ipv4Route> ();
160
      rtentry = Create<Ipv4Route> ();
143
      rtentry->SetDestination (route->GetDest ());
161
      rtentry->SetDestination (route->GetDest ());
144
      // XXX handle multi-address case
162
      // XXX handle multi-address case
(-)a/src/routing/global-routing/ipv4-global-routing.h (+6 lines)
 Lines 27-32    Link Here 
27
#include "ns3/ptr.h"
27
#include "ns3/ptr.h"
28
#include "ns3/ipv4.h"
28
#include "ns3/ipv4.h"
29
#include "ns3/ipv4-routing-protocol.h"
29
#include "ns3/ipv4-routing-protocol.h"
30
#include "ns3/random-variable.h"
30
31
31
namespace ns3 {
32
namespace ns3 {
32
33
 Lines 198-203    Link Here 
198
  void DoDispose (void);
199
  void DoDispose (void);
199
200
200
private:
201
private:
202
  /// Set to true if packets are randomly routed among ECMP; set to false for using only one route consistently
203
  bool m_randomEcmpRouting;
204
  /// A uniform random number generator for randomly routing packets among ECMP 
205
  UniformVariable m_rand;
206
201
  typedef std::list<Ipv4RoutingTableEntry *> HostRoutes;
207
  typedef std::list<Ipv4RoutingTableEntry *> HostRoutes;
202
  typedef std::list<Ipv4RoutingTableEntry *>::const_iterator HostRoutesCI;
208
  typedef std::list<Ipv4RoutingTableEntry *>::const_iterator HostRoutesCI;
203
  typedef std::list<Ipv4RoutingTableEntry *>::iterator HostRoutesI;
209
  typedef std::list<Ipv4RoutingTableEntry *>::iterator HostRoutesI;

Return to bug 667