A Discrete-Event Network Simulator
API
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Groups Pages
global-route-manager-impl.cc
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright 2007 University of Washington
4  * Copyright (C) 1999, 2000 Kunihiro Ishiguro, Toshiaki Takada
5  *
6  * This program is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License version 2 as
8  * published by the Free Software Foundation;
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program; if not, write to the Free Software
17  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18  *
19  * Authors: Tom Henderson (tomhend@u.washington.edu)
20  *
21  * Kunihiro Ishigura, Toshiaki Takada (GNU Zebra) are attributed authors
22  * of the quagga 0.99.7/src/ospfd/ospf_spf.c code which was ported here
23  */
24 
25 #include <utility>
26 #include <vector>
27 #include <queue>
28 #include <algorithm>
29 #include <iostream>
30 #include "ns3/assert.h"
31 #include "ns3/fatal-error.h"
32 #include "ns3/log.h"
33 #include "ns3/node-list.h"
34 #include "ns3/ipv4.h"
35 #include "ns3/ipv4-routing-protocol.h"
36 #include "ns3/ipv4-list-routing.h"
37 #include "ns3/mpi-interface.h"
40 #include "candidate-queue.h"
41 #include "ipv4-global-routing.h"
42 
43 NS_LOG_COMPONENT_DEFINE ("GlobalRouteManagerImpl");
44 
45 namespace ns3 {
46 
47 std::ostream&
48 operator<< (std::ostream& os, const SPFVertex::NodeExit_t& exit)
49 {
50  os << "(" << exit.first << " ," << exit.second << ")";
51  return os;
52 }
53 
54 std::ostream&
55 operator<< (std::ostream& os, const SPFVertex::ListOfSPFVertex_t& vs)
56 {
57  typedef SPFVertex::ListOfSPFVertex_t::const_iterator CIter_t;
58  os << "{";
59  for (CIter_t iter = vs.begin (); iter != vs.end ();)
60  {
61  os << (*iter)->m_vertexId;
62  if (++iter != vs.end ())
63  {
64  os << ", ";
65  }
66  else
67  {
68  break;
69  }
70  }
71  os << "}";
72  return os;
73 }
74 
75 // ---------------------------------------------------------------------------
76 //
77 // SPFVertex Implementation
78 //
79 // ---------------------------------------------------------------------------
80 
82  m_vertexType (VertexUnknown),
83  m_vertexId ("255.255.255.255"),
84  m_lsa (0),
85  m_distanceFromRoot (SPF_INFINITY),
86  m_rootOif (SPF_INFINITY),
87  m_nextHop ("0.0.0.0"),
88  m_parents (),
89  m_children (),
90  m_vertexProcessed (false)
91 {
92  NS_LOG_FUNCTION (this);
93 }
94 
96  m_vertexId (lsa->GetLinkStateId ()),
97  m_lsa (lsa),
98  m_distanceFromRoot (SPF_INFINITY),
99  m_rootOif (SPF_INFINITY),
100  m_nextHop ("0.0.0.0"),
101  m_parents (),
102  m_children (),
103  m_vertexProcessed (false)
104 {
105  NS_LOG_FUNCTION (this << lsa);
106 
107  if (lsa->GetLSType () == GlobalRoutingLSA::RouterLSA)
108  {
109  NS_LOG_LOGIC ("Setting m_vertexType to VertexRouter");
111  }
112  else if (lsa->GetLSType () == GlobalRoutingLSA::NetworkLSA)
113  {
114  NS_LOG_LOGIC ("Setting m_vertexType to VertexNetwork");
116  }
117 }
118 
120 {
121  NS_LOG_FUNCTION (this);
122 
123  NS_LOG_LOGIC ("Children vertices - " << m_children);
124  NS_LOG_LOGIC ("Parent verteices - " << m_parents);
125 
126  // find this node from all its parents and remove the entry of this node
127  // from all its parents
128  for (ListOfSPFVertex_t::iterator piter = m_parents.begin ();
129  piter != m_parents.end ();
130  piter++)
131  {
132  // remove the current vertex from its parent's children list. Check
133  // if the size of the list is reduced, or the child<->parent relation
134  // is not bidirectional
135  uint32_t orgCount = (*piter)->m_children.size ();
136  (*piter)->m_children.remove (this);
137  uint32_t newCount = (*piter)->m_children.size ();
138  if (orgCount > newCount)
139  {
140  NS_ASSERT_MSG (orgCount > newCount, "Unable to find the current vertex from its parents --- impossible!");
141  }
142  }
143 
144  // delete children
145  while (m_children.size () > 0)
146  {
147  // pop out children one by one. Some children may disapper
148  // when deleting some other children in the list. As a result,
149  // it is necessary to use pop to walk through all children, instead
150  // of using iterator.
151  //
152  // Note that m_children.pop_front () is not necessary as this
153  // p is removed from the children list when p is deleted
154  SPFVertex* p = m_children.front ();
155  // 'p' == 0, this child is already deleted by its other parent
156  if (p == 0) continue;
157  NS_LOG_LOGIC ("Parent vertex-" << m_vertexId << " deleting its child vertex-" << p->GetVertexId ());
158  delete p;
159  p = 0;
160  }
161  m_children.clear ();
162  // delete parents
163  m_parents.clear ();
164  // delete root exit direction
165  m_ecmpRootExits.clear ();
166 
167  NS_LOG_LOGIC ("Vertex-" << m_vertexId << " completed deleted");
168 }
169 
170 void
172 {
173  NS_LOG_FUNCTION (this << type);
174  m_vertexType = type;
175 }
176 
179 {
180  NS_LOG_FUNCTION (this);
181  return m_vertexType;
182 }
183 
184 void
186 {
187  NS_LOG_FUNCTION (this << id);
188  m_vertexId = id;
189 }
190 
193 {
194  NS_LOG_FUNCTION (this);
195  return m_vertexId;
196 }
197 
198 void
200 {
201  NS_LOG_FUNCTION (this << lsa);
202  m_lsa = lsa;
203 }
204 
206 SPFVertex::GetLSA (void) const
207 {
208  NS_LOG_FUNCTION (this);
209  return m_lsa;
210 }
211 
212 void
214 {
215  NS_LOG_FUNCTION (this << distance);
216  m_distanceFromRoot = distance;
217 }
218 
219 uint32_t
221 {
222  NS_LOG_FUNCTION (this);
223  return m_distanceFromRoot;
224 }
225 
226 void
228 {
229  NS_LOG_FUNCTION (this << parent);
230 
231  // always maintain only one parent when using setter/getter methods
232  m_parents.clear ();
233  m_parents.push_back (parent);
234 }
235 
236 SPFVertex*
237 SPFVertex::GetParent (uint32_t i) const
238 {
239  NS_LOG_FUNCTION (this << i);
240 
241  // If the index i is out-of-range, return 0 and do nothing
242  if (m_parents.size () <= i)
243  {
244  NS_LOG_LOGIC ("Index to SPFVertex's parent is out-of-range.");
245  return 0;
246  }
247  ListOfSPFVertex_t::const_iterator iter = m_parents.begin ();
248  while (i-- > 0)
249  {
250  iter++;
251  }
252  return *iter;
253 }
254 
255 void
257 {
258  NS_LOG_FUNCTION (this << v);
259 
260  NS_LOG_LOGIC ("Before merge, list of parents = " << m_parents);
261  // combine the two lists first, and then remove any duplicated after
262  m_parents.insert (m_parents.end (),
263  v->m_parents.begin (), v->m_parents.end ());
264  // remove duplication
265  m_parents.sort ();
266  m_parents.unique ();
267  NS_LOG_LOGIC ("After merge, list of parents = " << m_parents);
268 }
269 
270 void
272 {
273  NS_LOG_FUNCTION (this << nextHop << id);
274 
275  // always maintain only one root's exit
276  m_ecmpRootExits.clear ();
277  m_ecmpRootExits.push_back (NodeExit_t (nextHop, id));
278  // update the following in order to be backward compatitable with
279  // GetNextHop and GetOutgoingInterface methods
280  m_nextHop = nextHop;
281  m_rootOif = id;
282 }
283 
284 void
286 {
287  NS_LOG_FUNCTION (this << exit);
288  SetRootExitDirection (exit.first, exit.second);
289 }
290 
293 {
294  NS_LOG_FUNCTION (this << i);
295  typedef ListOfNodeExit_t::const_iterator CIter_t;
296 
297  NS_ASSERT_MSG (i < m_ecmpRootExits.size (), "Index out-of-range when accessing SPFVertex::m_ecmpRootExits!");
298  CIter_t iter = m_ecmpRootExits.begin ();
299  while (i-- > 0) { iter++; }
300 
301  return *iter;
302 }
303 
306 {
307  NS_LOG_FUNCTION (this);
308 
309  NS_ASSERT_MSG (m_ecmpRootExits.size () <= 1, "Assumed there is at most one exit from the root to this vertex");
310  return GetRootExitDirection (0);
311 }
312 
313 void
315 {
316  NS_LOG_FUNCTION (this << vertex);
317 
318  // obtain the external list of exit directions
319  //
320  // Append the external list into 'this' and remove duplication afterward
321  const ListOfNodeExit_t& extList = vertex->m_ecmpRootExits;
322  m_ecmpRootExits.insert (m_ecmpRootExits.end (),
323  extList.begin (), extList.end ());
324  m_ecmpRootExits.sort ();
325  m_ecmpRootExits.unique ();
326 }
327 
328 void
330 {
331  NS_LOG_FUNCTION (this << vertex);
332 
333  // discard all exit direction currently associated with this vertex,
334  // and copy all the exit directions from the given vertex
335  if (m_ecmpRootExits.size () > 0)
336  {
337  NS_LOG_WARN ("x root exit directions in this vertex are going to be discarded");
338  }
339  m_ecmpRootExits.clear ();
340  m_ecmpRootExits.insert (m_ecmpRootExits.end (),
341  vertex->m_ecmpRootExits.begin (), vertex->m_ecmpRootExits.end ());
342 }
343 
344 uint32_t
346 {
347  NS_LOG_FUNCTION (this);
348  return m_ecmpRootExits.size ();
349 }
350 
351 uint32_t
353 {
354  NS_LOG_FUNCTION (this);
355  return m_children.size ();
356 }
357 
358 SPFVertex*
359 SPFVertex::GetChild (uint32_t n) const
360 {
361  NS_LOG_FUNCTION (this << n);
362  uint32_t j = 0;
363 
364  for ( ListOfSPFVertex_t::const_iterator i = m_children.begin ();
365  i != m_children.end ();
366  i++, j++)
367  {
368  if (j == n)
369  {
370  return *i;
371  }
372  }
373  NS_ASSERT_MSG (false, "Index <n> out of range.");
374  return 0;
375 }
376 
377 uint32_t
379 {
380  NS_LOG_FUNCTION (this << child);
381  m_children.push_back (child);
382  return m_children.size ();
383 }
384 
385 void
387 {
388  NS_LOG_FUNCTION (this << value);
389  m_vertexProcessed = value;
390 }
391 
392 bool
394 {
395  NS_LOG_FUNCTION (this);
396  return m_vertexProcessed;
397 }
398 
399 void
401 {
402  NS_LOG_FUNCTION (this);
403  for (uint32_t i = 0; i < this->GetNChildren (); i++)
404  {
405  this->GetChild (i)->ClearVertexProcessed ();
406  }
407  this->SetVertexProcessed (false);
408 }
409 
410 // ---------------------------------------------------------------------------
411 //
412 // GlobalRouteManagerLSDB Implementation
413 //
414 // ---------------------------------------------------------------------------
415 
417  :
418  m_database (),
419  m_extdatabase ()
420 {
421  NS_LOG_FUNCTION (this);
422 }
423 
425 {
426  NS_LOG_FUNCTION (this);
427  LSDBMap_t::iterator i;
428  for (i= m_database.begin (); i!= m_database.end (); i++)
429  {
430  NS_LOG_LOGIC ("free LSA");
431  GlobalRoutingLSA* temp = i->second;
432  delete temp;
433  }
434  for (uint32_t j = 0; j < m_extdatabase.size (); j++)
435  {
436  NS_LOG_LOGIC ("free ASexternalLSA");
437  GlobalRoutingLSA* temp = m_extdatabase.at (j);
438  delete temp;
439  }
440  NS_LOG_LOGIC ("clear map");
441  m_database.clear ();
442 }
443 
444 void
446 {
447  NS_LOG_FUNCTION (this);
448  LSDBMap_t::iterator i;
449  for (i= m_database.begin (); i!= m_database.end (); i++)
450  {
451  GlobalRoutingLSA* temp = i->second;
453  }
454 }
455 
456 void
458 {
459  NS_LOG_FUNCTION (this << addr << lsa);
461  {
462  m_extdatabase.push_back (lsa);
463  }
464  else
465  {
466  m_database.insert (LSDBPair_t (addr, lsa));
467  }
468 }
469 
471 GlobalRouteManagerLSDB::GetExtLSA (uint32_t index) const
472 {
473  NS_LOG_FUNCTION (this << index);
474  return m_extdatabase.at (index);
475 }
476 
477 uint32_t
479 {
480  NS_LOG_FUNCTION (this);
481  return m_extdatabase.size ();
482 }
483 
486 {
487  NS_LOG_FUNCTION (this << addr);
488 //
489 // Look up an LSA by its address.
490 //
491  LSDBMap_t::const_iterator i;
492  for (i= m_database.begin (); i!= m_database.end (); i++)
493  {
494  if (i->first == addr)
495  {
496  return i->second;
497  }
498  }
499  return 0;
500 }
501 
504 {
505  NS_LOG_FUNCTION (this << addr);
506 //
507 // Look up an LSA by its address.
508 //
509  LSDBMap_t::const_iterator i;
510  for (i= m_database.begin (); i!= m_database.end (); i++)
511  {
512  GlobalRoutingLSA* temp = i->second;
513 // Iterate among temp's Link Records
514  for (uint32_t j = 0; j < temp->GetNLinkRecords (); j++)
515  {
516  GlobalRoutingLinkRecord *lr = temp->GetLinkRecord (j);
518  lr->GetLinkData () == addr)
519  {
520  return temp;
521  }
522  }
523  }
524  return 0;
525 }
526 
527 // ---------------------------------------------------------------------------
528 //
529 // GlobalRouteManagerImpl Implementation
530 //
531 // ---------------------------------------------------------------------------
532 
534  :
535  m_spfroot (0)
536 {
537  NS_LOG_FUNCTION (this);
539 }
540 
542 {
543  NS_LOG_FUNCTION (this);
544  if (m_lsdb)
545  {
546  delete m_lsdb;
547  }
548 }
549 
550 void
552 {
553  NS_LOG_FUNCTION (this << lsdb);
554  if (m_lsdb)
555  {
556  delete m_lsdb;
557  }
558  m_lsdb = lsdb;
559 }
560 
561 void
563 {
564  NS_LOG_FUNCTION (this);
565  NodeList::Iterator listEnd = NodeList::End ();
566  for (NodeList::Iterator i = NodeList::Begin (); i != listEnd; i++)
567  {
568  Ptr<Node> node = *i;
569  Ptr<GlobalRouter> router = node->GetObject<GlobalRouter> ();
570  if (router == 0)
571  {
572  continue;
573  }
574  Ptr<Ipv4GlobalRouting> gr = router->GetRoutingProtocol ();
575  uint32_t j = 0;
576  uint32_t nRoutes = gr->GetNRoutes ();
577  NS_LOG_LOGIC ("Deleting " << gr->GetNRoutes ()<< " routes from node " << node->GetId ());
578  // Each time we delete route 0, the route index shifts downward
579  // We can delete all routes if we delete the route numbered 0
580  // nRoutes times
581  for (j = 0; j < nRoutes; j++)
582  {
583  NS_LOG_LOGIC ("Deleting global route " << j << " from node " << node->GetId ());
584  gr->RemoveRoute (0);
585  }
586  NS_LOG_LOGIC ("Deleted " << j << " global routes from node "<< node->GetId ());
587  }
588  if (m_lsdb)
589  {
590  NS_LOG_LOGIC ("Deleting LSDB, creating new one");
591  delete m_lsdb;
593  }
594 }
595 
596 //
597 // In order to build the routing database, we need to walk the list of nodes
598 // in the system and look for those that support the GlobalRouter interface.
599 // These routers will export a number of Link State Advertisements (LSAs)
600 // that describe the links and networks that are "adjacent" (i.e., that are
601 // on the other side of a point-to-point link). We take these LSAs and put
602 // add them to the Link State DataBase (LSDB) from which the routes will
603 // ultimately be computed.
604 //
605 void
607 {
608  NS_LOG_FUNCTION (this);
609 //
610 // Walk the list of nodes looking for the GlobalRouter Interface. Nodes with
611 // global router interfaces are, not too surprisingly, our routers.
612 //
613  NodeList::Iterator listEnd = NodeList::End ();
614  for (NodeList::Iterator i = NodeList::Begin (); i != listEnd; i++)
615  {
616  Ptr<Node> node = *i;
617 
618  Ptr<GlobalRouter> rtr = node->GetObject<GlobalRouter> ();
619 //
620 // Ignore nodes that aren't participating in routing.
621 //
622  if (!rtr)
623  {
624  continue;
625  }
626 //
627 // You must call DiscoverLSAs () before trying to use any routing info or to
628 // update LSAs. DiscoverLSAs () drives the process of discovering routes in
629 // the GlobalRouter. Afterward, you may use GetNumLSAs (), which is a very
630 // computationally inexpensive call. If you call GetNumLSAs () before calling
631 // DiscoverLSAs () will get zero as the number since no routes have been
632 // found.
633 //
634  Ptr<Ipv4GlobalRouting> grouting = rtr->GetRoutingProtocol ();
635  uint32_t numLSAs = rtr->DiscoverLSAs ();
636  NS_LOG_LOGIC ("Found " << numLSAs << " LSAs");
637 
638  for (uint32_t j = 0; j < numLSAs; ++j)
639  {
640  GlobalRoutingLSA* lsa = new GlobalRoutingLSA ();
641 //
642 // This is the call to actually fetch a Link State Advertisement from the
643 // router.
644 //
645  rtr->GetLSA (j, *lsa);
646  NS_LOG_LOGIC (*lsa);
647 //
648 // Write the newly discovered link state advertisement to the database.
649 //
650  m_lsdb->Insert (lsa->GetLinkStateId (), lsa);
651  }
652  }
653 }
654 
655 //
656 // For each node that is a global router (which is determined by the presence
657 // of an aggregated GlobalRouter interface), run the Dijkstra SPF calculation
658 // on the database rooted at that router, and populate the node forwarding
659 // tables.
660 //
661 // This function parallels RFC2328, Section 16.1.1, and quagga ospfd
662 //
663 // This calculation yields the set of intra-area routes associated
664 // with an area (called hereafter Area A). A router calculates the
665 // shortest-path tree using itself as the root. The formation
666 // of the shortest path tree is done here in two stages. In the
667 // first stage, only links between routers and transit networks are
668 // considered. Using the Dijkstra algorithm, a tree is formed from
669 // this subset of the link state database. In the second stage,
670 // leaves are added to the tree by considering the links to stub
671 // networks.
672 //
673 // The area's link state database is represented as a directed graph.
674 // The graph's vertices are routers, transit networks and stub networks.
675 //
676 // The first stage of the procedure (i.e., the Dijkstra algorithm)
677 // can now be summarized as follows. At each iteration of the
678 // algorithm, there is a list of candidate vertices. Paths from
679 // the root to these vertices have been found, but not necessarily
680 // the shortest ones. However, the paths to the candidate vertex
681 // that is closest to the root are guaranteed to be shortest; this
682 // vertex is added to the shortest-path tree, removed from the
683 // candidate list, and its adjacent vertices are examined for
684 // possible addition to/modification of the candidate list. The
685 // algorithm then iterates again. It terminates when the candidate
686 // list becomes empty.
687 //
688 void
690 {
691  NS_LOG_FUNCTION (this);
692 //
693 // Walk the list of nodes in the system.
694 //
695  NS_LOG_INFO ("About to start SPF calculation");
696  NodeList::Iterator listEnd = NodeList::End ();
697  for (NodeList::Iterator i = NodeList::Begin (); i != listEnd; i++)
698  {
699  Ptr<Node> node = *i;
700 //
701 // Look for the GlobalRouter interface that indicates that the node is
702 // participating in routing.
703 //
704  Ptr<GlobalRouter> rtr =
705  node->GetObject<GlobalRouter> ();
706 
707  // Ignore nodes that are not assigned to our systemId (distributed sim)
708  if (node->GetSystemId () != MpiInterface::GetSystemId ())
709  {
710  continue;
711  }
712 
713 //
714 // if the node has a global router interface, then run the global routing
715 // algorithms.
716 //
717  if (rtr && rtr->GetNumLSAs () )
718  {
719  SPFCalculate (rtr->GetRouterId ());
720  }
721  }
722  NS_LOG_INFO ("Finished SPF calculation");
723 }
724 
725 //
726 // This method is derived from quagga ospf_spf_next (). See RFC2328 Section
727 // 16.1 (2) for further details.
728 //
729 // We're passed a parameter <v> that is a vertex which is already in the SPF
730 // tree. A vertex represents a router node. We also get a reference to the
731 // SPF candidate queue, which is a priority queue containing the shortest paths
732 // to the networks we know about.
733 //
734 // We examine the links in v's LSA and update the list of candidates with any
735 // vertices not already on the list. If a lower-cost path is found to a
736 // vertex already on the candidate list, store the new (lower) cost.
737 //
738 void
740 {
741  NS_LOG_FUNCTION (this << v << &candidate);
742 
743  SPFVertex* w = 0;
744  GlobalRoutingLSA* w_lsa = 0;
746  uint32_t distance = 0;
747  uint32_t numRecordsInVertex = 0;
748 //
749 // V points to a Router-LSA or Network-LSA
750 // Loop over the links in router LSA or attached routers in Network LSA
751 //
753  {
754  numRecordsInVertex = v->GetLSA ()->GetNLinkRecords ();
755  }
757  {
758  numRecordsInVertex = v->GetLSA ()->GetNAttachedRouters ();
759  }
760 
761  for (uint32_t i = 0; i < numRecordsInVertex; i++)
762  {
763 // Get w_lsa: In case of V is Router-LSA
765  {
766  NS_LOG_LOGIC ("Examining link " << i << " of " <<
767  v->GetVertexId () << "'s " <<
768  v->GetLSA ()->GetNLinkRecords () << " link records");
769 //
770 // (a) If this is a link to a stub network, examine the next link in V's LSA.
771 // Links to stub networks will be considered in the second stage of the
772 // shortest path calculation.
773 //
774  l = v->GetLSA ()->GetLinkRecord (i);
775  NS_ASSERT (l != 0);
776  if (l->GetLinkType () == GlobalRoutingLinkRecord::StubNetwork)
777  {
778  NS_LOG_LOGIC ("Found a Stub record to " << l->GetLinkId ());
779  continue;
780  }
781 //
782 // (b) Otherwise, W is a transit vertex (router or transit network). Look up
783 // the vertex W's LSA (router-LSA or network-LSA) in Area A's link state
784 // database.
785 //
786  if (l->GetLinkType () == GlobalRoutingLinkRecord::PointToPoint)
787  {
788 //
789 // Lookup the link state advertisement of the new link -- we call it <w> in
790 // the link state database.
791 //
792  w_lsa = m_lsdb->GetLSA (l->GetLinkId ());
793  NS_ASSERT (w_lsa);
794  NS_LOG_LOGIC ("Found a P2P record from " <<
795  v->GetVertexId () << " to " << w_lsa->GetLinkStateId ());
796  }
797  else if (l->GetLinkType () ==
799  {
800  w_lsa = m_lsdb->GetLSA (l->GetLinkId ());
801  NS_ASSERT (w_lsa);
802  NS_LOG_LOGIC ("Found a Transit record from " <<
803  v->GetVertexId () << " to " << w_lsa->GetLinkStateId ());
804  }
805  else
806  {
807  NS_ASSERT_MSG (0, "illegal Link Type");
808  }
809  }
810 // Get w_lsa: In case of V is Network-LSA
812  {
813  w_lsa = m_lsdb->GetLSAByLinkData
814  (v->GetLSA ()->GetAttachedRouter (i));
815  if (!w_lsa)
816  {
817  continue;
818  }
819  NS_LOG_LOGIC ("Found a Network LSA from " <<
820  v->GetVertexId () << " to " << w_lsa->GetLinkStateId ());
821  }
822 
823 // Note: w_lsa at this point may be either RouterLSA or NetworkLSA
824 //
825 // (c) If vertex W is already on the shortest-path tree, examine the next
826 // link in the LSA.
827 //
828 // If the link is to a router that is already in the shortest path first tree
829 // then we have it covered -- ignore it.
830 //
832  {
833  NS_LOG_LOGIC ("Skipping -> LSA "<<
834  w_lsa->GetLinkStateId () << " already in SPF tree");
835  continue;
836  }
837 //
838 // (d) Calculate the link state cost D of the resulting path from the root to
839 // vertex W. D is equal to the sum of the link state cost of the (already
840 // calculated) shortest path to vertex V and the advertised cost of the link
841 // between vertices V and W.
842 //
844  {
845  NS_ASSERT (l != 0);
846  distance = v->GetDistanceFromRoot () + l->GetMetric ();
847  }
848  else
849  {
850  distance = v->GetDistanceFromRoot ();
851  }
852 
853  NS_LOG_LOGIC ("Considering w_lsa " << w_lsa->GetLinkStateId ());
854 
855 // Is there already vertex w in candidate list?
857  {
858 // Calculate nexthop to w
859 // We need to figure out how to actually get to the new router represented
860 // by <w>. This will (among other things) find the next hop address to send
861 // packets destined for this network to, and also find the outbound interface
862 // used to forward the packets.
863 
864 // prepare vertex w
865  w = new SPFVertex (w_lsa);
866  if (SPFNexthopCalculation (v, w, l, distance))
867  {
869 //
870 // Push this new vertex onto the priority queue (ordered by distance from the
871 // root node).
872 //
873  candidate.Push (w);
874  NS_LOG_LOGIC ("Pushing " <<
875  w->GetVertexId () << ", parent vertexId: " <<
876  v->GetVertexId () << ", distance: " <<
877  w->GetDistanceFromRoot ());
878  }
879  else
880  NS_ASSERT_MSG (0, "SPFNexthopCalculation never "
881  << "return false, but it does now!");
882  }
883  else if (w_lsa->GetStatus () == GlobalRoutingLSA::LSA_SPF_CANDIDATE)
884  {
885 //
886 // We have already considered the link represented by <w>. What wse have to
887 // do now is to decide if this new router represents a route with a shorter
888 // distance metric.
889 //
890 // So, locate the vertex in the candidate queue and take a look at the
891 // distance.
892 
893 /* (quagga-0.98.6) W is already on the candidate list; call it cw.
894 * Compare the previously calculated cost (cw->distance)
895 * with the cost we just determined (w->distance) to see
896 * if we've found a shorter path.
897 */
898  SPFVertex* cw;
899  cw = candidate.Find (w_lsa->GetLinkStateId ());
900  if (cw->GetDistanceFromRoot () < distance)
901  {
902 //
903 // This is not a shorter path, so don't do anything.
904 //
905  continue;
906  }
907  else if (cw->GetDistanceFromRoot () == distance)
908  {
909 //
910 // This path is one with an equal cost.
911 //
912  NS_LOG_LOGIC ("Equal cost multiple paths found.");
913 
914 // At this point, there are two instances 'w' and 'cw' of the
915 // same vertex, the vertex that is currently being considered
916 // for adding into the shortest path tree. 'w' is the instance
917 // as seen from the root via vertex 'v', and 'cw' is the instance
918 // as seen from the root via some other vertices other than 'v'.
919 // These two instances are being merged in the following code.
920 // In particular, the parent nodes, the next hops, and the root's
921 // output interfaces of the two instances are being merged.
922 //
923 // Note that this is functionally equivalent to calling
924 // ospf_nexthop_merge (cw->nexthop, w->nexthop) in quagga-0.98.6
925 // (ospf_spf.c::859), although the detail implementation
926 // is very different from quagga (blame ns3::GlobalRouteManagerImpl)
927 
928 // prepare vertex w
929  w = new SPFVertex (w_lsa);
930  SPFNexthopCalculation (v, w, l, distance);
931  cw->MergeRootExitDirections (w);
932  cw->MergeParent (w);
933 // SPFVertexAddParent (w) is necessary as the destructor of
934 // SPFVertex checks if the vertex and its parent is linked
935 // bidirectionally
936  SPFVertexAddParent (w);
937  delete w;
938  }
939  else // cw->GetDistanceFromRoot () > w->GetDistanceFromRoot ()
940  {
941 //
942 // this path represents a new, lower-cost path to <w> (the vertex we found in
943 // the current link record of the link state advertisement of the current root
944 // (vertex <v>)
945 //
946 // N.B. the nexthop_calculation is conditional, if it finds a valid nexthop
947 // it will call spf_add_parents, which will flush the old parents
948 //
949  if (SPFNexthopCalculation (v, cw, l, distance))
950  {
951 //
952 // If we've changed the cost to get to the vertex represented by <w>, we
953 // must reorder the priority queue keyed to that cost.
954 //
955  candidate.Reorder ();
956  }
957  } // new lower cost path found
958  } // end W is already on the candidate list
959  } // end loop over the links in V's LSA
960 }
961 
962 //
963 // This method is derived from quagga ospf_nexthop_calculation() 16.1.1.
964 //
965 // Calculate nexthop from root through V (parent) to vertex W (destination)
966 // with given distance from root->W.
967 //
968 // As appropriate, set w's parent, distance, and nexthop information
969 //
970 // For now, this is greatly simplified from the quagga code
971 //
972 int
974  SPFVertex* v,
975  SPFVertex* w,
977  uint32_t distance)
978 {
979  NS_LOG_FUNCTION (this << v << w << l << distance);
980 //
981 // If w is a NetworkVertex, l should be null
982 /*
983  if (w->GetVertexType () == SPFVertex::VertexNetwork && l)
984  {
985  NS_ASSERT_MSG (0, "Error: SPFNexthopCalculation parameter problem");
986  }
987 */
988 
989 //
990 // The vertex m_spfroot is a distinguished vertex representing the node at
991 // the root of the calculations. That is, it is the node for which we are
992 // calculating the routes.
993 //
994 // There are two distinct cases for calculating the next hop information.
995 // First, if we're considering a hop from the root to an "adjacent" network
996 // (one that is on the other side of a point-to-point link connected to the
997 // root), then we need to store the information needed to forward down that
998 // link. The second case is if the network is not directly adjacent. In that
999 // case we need to use the forwarding information from the vertex on the path
1000 // to the destination that is directly adjacent [node 1] in both cases of the
1001 // diagram below.
1002 //
1003 // (1) [root] -> [point-to-point] -> [node 1]
1004 // (2) [root] -> [point-to-point] -> [node 1] -> [point-to-point] -> [node 2]
1005 //
1006 // We call the propagation of next hop information down vertices of a path
1007 // "inheriting" the next hop information.
1008 //
1009 // The point-to-point link information is only useful in this calculation when
1010 // we are examining the root node.
1011 //
1012  if (v == m_spfroot)
1013  {
1014 //
1015 // In this case <v> is the root node, which means it is the starting point
1016 // for the packets forwarded by that node. This also means that the next hop
1017 // address of packets headed for some arbitrary off-network destination must
1018 // be the destination at the other end of one of the links off of the root
1019 // node if this root node is a router. We then need to see if this node <w>
1020 // is a router.
1021 //
1022  if (w->GetVertexType () == SPFVertex::VertexRouter)
1023  {
1024 //
1025 // In the case of point-to-point links, the link data field (m_linkData) of a
1026 // Global Router Link Record contains the local IP address. If we look at the
1027 // link record describing the link from the perspecive of <w> (the remote
1028 // node from the viewpoint of <v>) back to the root node, we can discover the
1029 // IP address of the router to which <v> is adjacent. This is a distinguished
1030 // address -- the next hop address to get from <v> to <w> and all networks
1031 // accessed through that path.
1032 //
1033 // SPFGetNextLink () is a little odd. used in this way it is just going to
1034 // return the link record describing the link from <w> to <v>. Think of it as
1035 // SPFGetLink.
1036 //
1037  NS_ASSERT (l);
1038  GlobalRoutingLinkRecord *linkRemote = 0;
1039  linkRemote = SPFGetNextLink (w, v, linkRemote);
1040 //
1041 // At this point, <l> is the Global Router Link Record describing the point-
1042 // to point link from <v> to <w> from the perspective of <v>; and <linkRemote>
1043 // is the Global Router Link Record describing that same link from the
1044 // perspective of <w> (back to <v>). Now we can just copy the next hop
1045 // address from the m_linkData member variable.
1046 //
1047 // The next hop member variable we put in <w> has the sense "in order to get
1048 // from the root node to the host represented by vertex <w>, you have to send
1049 // the packet to the next hop address specified in w->m_nextHop.
1050 //
1051  Ipv4Address nextHop = linkRemote->GetLinkData ();
1052 //
1053 // Now find the outgoing interface corresponding to the point to point link
1054 // from the perspective of <v> -- remember that <l> is the link "from"
1055 // <v> "to" <w>.
1056 //
1057  uint32_t outIf = FindOutgoingInterfaceId (l->GetLinkData ());
1058 
1059  w->SetRootExitDirection (nextHop, outIf);
1060  w->SetDistanceFromRoot (distance);
1061  w->SetParent (v);
1062  NS_LOG_LOGIC ("Next hop from " <<
1063  v->GetVertexId () << " to " << w->GetVertexId () <<
1064  " goes through next hop " << nextHop <<
1065  " via outgoing interface " << outIf <<
1066  " with distance " << distance);
1067  } // end W is a router vertes
1068  else
1069  {
1071 // W is a directly connected network; no next hop is required
1072  GlobalRoutingLSA* w_lsa = w->GetLSA ();
1073  NS_ASSERT (w_lsa->GetLSType () == GlobalRoutingLSA::NetworkLSA);
1074 // Find outgoing interface ID for this network
1075  uint32_t outIf = FindOutgoingInterfaceId (w_lsa->GetLinkStateId (),
1076  w_lsa->GetNetworkLSANetworkMask () );
1077 // Set the next hop to 0.0.0.0 meaning "not exist"
1078  Ipv4Address nextHop = Ipv4Address::GetZero ();
1079  w->SetRootExitDirection (nextHop, outIf);
1080  w->SetDistanceFromRoot (distance);
1081  w->SetParent (v);
1082  NS_LOG_LOGIC ("Next hop from " <<
1083  v->GetVertexId () << " to network " << w->GetVertexId () <<
1084  " via outgoing interface " << outIf <<
1085  " with distance " << distance);
1086  return 1;
1087  }
1088  } // end v is the root
1089  else if (v->GetVertexType () == SPFVertex::VertexNetwork)
1090  {
1091 // See if any of v's parents are the root
1092  if (v->GetParent () == m_spfroot)
1093  {
1094 // 16.1.1 para 5. ...the parent vertex is a network that
1095 // directly connects the calculating router to the destination
1096 // router. The list of next hops is then determined by
1097 // examining the destination's router-LSA...
1099  GlobalRoutingLinkRecord *linkRemote = 0;
1100  while ((linkRemote = SPFGetNextLink (w, v, linkRemote)))
1101  {
1102 /* ...For each link in the router-LSA that points back to the
1103  * parent network, the link's Link Data field provides the IP
1104  * address of a next hop router. The outgoing interface to
1105  * use can then be derived from the next hop IP address (or
1106  * it can be inherited from the parent network).
1107  */
1108  Ipv4Address nextHop = linkRemote->GetLinkData ();
1109  uint32_t outIf = v->GetRootExitDirection ().second;
1110  w->SetRootExitDirection (nextHop, outIf);
1111  NS_LOG_LOGIC ("Next hop from " <<
1112  v->GetVertexId () << " to " << w->GetVertexId () <<
1113  " goes through next hop " << nextHop <<
1114  " via outgoing interface " << outIf);
1115  }
1116  }
1117  else
1118  {
1120  }
1121  }
1122  else
1123  {
1124 //
1125 // If we're calculating the next hop information from a node (v) that is
1126 // *not* the root, then we need to "inherit" the information needed to
1127 // forward the packet from the vertex closer to the root. That is, we'll
1128 // still send packets to the next hop address of the router adjacent to the
1129 // root on the path toward <w>.
1130 //
1131 // Above, when we were considering the root node, we calculated the next hop
1132 // address and outgoing interface required to get off of the root network.
1133 // At this point, we are further away from the root network along one of the
1134 // (shortest) paths. So the next hop and outoing interface remain the same
1135 // (are inherited).
1136 //
1138  }
1139 //
1140 // In all cases, we need valid values for the distance metric and a parent.
1141 //
1142  w->SetDistanceFromRoot (distance);
1143  w->SetParent (v);
1144 
1145  return 1;
1146 }
1147 
1148 //
1149 // This method is derived from quagga ospf_get_next_link ()
1150 //
1151 // First search the Global Router Link Records of vertex <v> for one
1152 // representing a point-to point link to vertex <w>.
1153 //
1154 // What is done depends on prev_link. Contrary to appearances, prev_link just
1155 // acts as a flag here. If prev_link is NULL, we return the first Global
1156 // Router Link Record we find that describes a point-to-point link from <v>
1157 // to <w>. If prev_link is not NULL, we return a Global Router Link Record
1158 // representing a possible *second* link from <v> to <w>.
1159 //
1162  SPFVertex* v,
1163  SPFVertex* w,
1164  GlobalRoutingLinkRecord* prev_link)
1165 {
1166  NS_LOG_FUNCTION (this << v << w << prev_link);
1167 
1168  bool skip = true;
1169  bool found_prev_link = false;
1171 //
1172 // If prev_link is 0, we are really looking for the first link, not the next
1173 // link.
1174 //
1175  if (prev_link == 0)
1176  {
1177  skip = false;
1178  found_prev_link = true;
1179  }
1180 //
1181 // Iterate through the Global Router Link Records advertised by the vertex
1182 // <v> looking for records representing the point-to-point links off of this
1183 // vertex.
1184 //
1185  for (uint32_t i = 0; i < v->GetLSA ()->GetNLinkRecords (); ++i)
1186  {
1187  l = v->GetLSA ()->GetLinkRecord (i);
1188 //
1189 // The link ID of a link record representing a point-to-point link is set to
1190 // the router ID of the neighboring router -- the router to which the link
1191 // connects from the perspective of <v> in this case. The vertex ID is also
1192 // set to the router ID (using the link state advertisement of a router node).
1193 // We're just checking to see if the link <l> is actually the link from <v> to
1194 // <w>.
1195 //
1196  if (l->GetLinkId () == w->GetVertexId ())
1197  {
1198  if (!found_prev_link)
1199  {
1200  NS_LOG_LOGIC ("Skipping links before prev_link found");
1201  found_prev_link = true;
1202  continue;
1203  }
1204 
1205  NS_LOG_LOGIC ("Found matching link l: linkId = " <<
1206  l->GetLinkId () << " linkData = " << l->GetLinkData ());
1207 //
1208 // If skip is false, don't (not too surprisingly) skip the link found -- it's
1209 // the one we're interested in. That's either because we didn't pass in a
1210 // previous link, and we're interested in the first one, or because we've
1211 // skipped a previous link and moved forward to the next (which is then the
1212 // one we want).
1213 //
1214  if (skip == false)
1215  {
1216  NS_LOG_LOGIC ("Returning the found link");
1217  return l;
1218  }
1219  else
1220  {
1221 //
1222 // Skip is true and we've found a link from <v> to <w>. We want the next one.
1223 // Setting skip to false gets us the next point-to-point global router link
1224 // record in the LSA from <v>.
1225 //
1226  NS_LOG_LOGIC ("Skipping the found link");
1227  skip = false;
1228  continue;
1229  }
1230  }
1231  }
1232  return 0;
1233 }
1234 
1235 //
1236 // Used for unit tests.
1237 //
1238 void
1240 {
1241  NS_LOG_FUNCTION (this << root);
1242  SPFCalculate (root);
1243 }
1244 
1245 //
1246 // Used to test if a node is a stub, from an OSPF sense.
1247 // If there is only one link of type 1 or 2, then a default route
1248 // can safely be added to the next-hop router and SPF does not need
1249 // to be run
1250 //
1251 bool
1253 {
1254  NS_LOG_FUNCTION (this << root);
1255  GlobalRoutingLSA *rlsa = m_lsdb->GetLSA (root);
1256  Ipv4Address myRouterId = rlsa->GetLinkStateId ();
1257  int transits = 0;
1258  GlobalRoutingLinkRecord *transitLink = 0;
1259  for (uint32_t i = 0; i < rlsa->GetNLinkRecords (); i++)
1260  {
1261  GlobalRoutingLinkRecord *l = rlsa->GetLinkRecord (i);
1263  {
1264  transits++;
1265  transitLink = l;
1266  }
1268  {
1269  transits++;
1270  transitLink = l;
1271  }
1272  }
1273  if (transits == 0)
1274  {
1275  // This router is not connected to any router. Probably, global
1276  // routing should not be called for this node, but we can just raise
1277  // a warning here and return true.
1278  NS_LOG_WARN ("all nodes should have at least one transit link:" << root );
1279  return true;
1280  }
1281  if (transits == 1)
1282  {
1284  {
1285  // Install default route to next hop router
1286  // What is the next hop? We need to check all neighbors on the link.
1287  // If there is a single router that has two transit links, then
1288  // that is the default next hop. If there are more than one
1289  // routers on link with multiple transit links, return false.
1290  // Not yet implemented, so simply return false
1291  NS_LOG_LOGIC ("TBD: Would have inserted default for transit");
1292  return false;
1293  }
1294  else if (transitLink->GetLinkType () == GlobalRoutingLinkRecord::PointToPoint)
1295  {
1296  // Install default route to next hop
1297  // The link record LinkID is the router ID of the peer.
1298  // The Link Data is the local IP interface address
1299  GlobalRoutingLSA *w_lsa = m_lsdb->GetLSA (transitLink->GetLinkId ());
1300  uint32_t nLinkRecords = w_lsa->GetNLinkRecords ();
1301  for (uint32_t j = 0; j < nLinkRecords; ++j)
1302  {
1303  //
1304  // We are only concerned about point-to-point links
1305  //
1306  GlobalRoutingLinkRecord *lr = w_lsa->GetLinkRecord (j);
1308  {
1309  continue;
1310  }
1311  // Find the link record that corresponds to our routerId
1312  if (lr->GetLinkId () == myRouterId)
1313  {
1314  // Next hop is stored in the LinkID field of lr
1315  Ptr<GlobalRouter> router = rlsa->GetNode ()->GetObject<GlobalRouter> ();
1316  NS_ASSERT (router);
1317  Ptr<Ipv4GlobalRouting> gr = router->GetRoutingProtocol ();
1318  NS_ASSERT (gr);
1319  gr->AddNetworkRouteTo (Ipv4Address ("0.0.0.0"), Ipv4Mask ("0.0.0.0"), lr->GetLinkData (),
1320  FindOutgoingInterfaceId (transitLink->GetLinkData ()));
1321  NS_LOG_LOGIC ("Inserting default route for node " << myRouterId << " to next hop " <<
1322  lr->GetLinkData () << " via interface " <<
1323  FindOutgoingInterfaceId (transitLink->GetLinkData ()));
1324  return true;
1325  }
1326  }
1327  }
1328  }
1329  return false;
1330 }
1331 
1332 // quagga ospf_spf_calculate
1333 void
1335 {
1336  NS_LOG_FUNCTION (this << root);
1337 
1338  SPFVertex *v;
1339 //
1340 // Initialize the Link State Database.
1341 //
1342  m_lsdb->Initialize ();
1343 //
1344 // The candidate queue is a priority queue of SPFVertex objects, with the top
1345 // of the queue being the closest vertex in terms of distance from the root
1346 // of the tree. Initially, this queue is empty.
1347 //
1348  CandidateQueue candidate;
1349  NS_ASSERT (candidate.Size () == 0);
1350 //
1351 // Initialize the shortest-path tree to only contain the router doing the
1352 // calculation. Each router (and corresponding network) is a vertex in the
1353 // shortest path first (SPF) tree.
1354 //
1355  v = new SPFVertex (m_lsdb->GetLSA (root));
1356 //
1357 // This vertex is the root of the SPF tree and it is distance 0 from the root.
1358 // We also mark this vertex as being in the SPF tree.
1359 //
1360  m_spfroot= v;
1361  v->SetDistanceFromRoot (0);
1362  v->GetLSA ()->SetStatus (GlobalRoutingLSA::LSA_SPF_IN_SPFTREE);
1363  NS_LOG_LOGIC ("Starting SPFCalculate for node " << root);
1364 
1365 //
1366 // Optimize SPF calculation, for ns-3.
1367 // We do not need to calculate SPF for every node in the network if this
1368 // node has only one interface through which another router can be
1369 // reached. Instead, short-circuit this computation and just install
1370 // a default route in the CheckForStubNode() method.
1371 //
1372  if (NodeList::GetNNodes () > 0 && CheckForStubNode (root))
1373  {
1374  NS_LOG_LOGIC ("SPFCalculate truncated for stub node " << root);
1375  delete m_spfroot;
1376  return;
1377  }
1378 
1379  for (;;)
1380  {
1381 //
1382 // The operations we need to do are given in the OSPF RFC which we reference
1383 // as we go along.
1384 //
1385 // RFC2328 16.1. (2).
1386 //
1387 // We examine the Global Router Link Records in the Link State
1388 // Advertisements of the current vertex. If there are any point-to-point
1389 // links to unexplored adjacent vertices we add them to the tree and update
1390 // the distance and next hop information on how to get there. We also add
1391 // the new vertices to the candidate queue (the priority queue ordered by
1392 // shortest path). If the new vertices represent shorter paths, we use them
1393 // and update the path cost.
1394 //
1395  SPFNext (v, candidate);
1396 //
1397 // RFC2328 16.1. (3).
1398 //
1399 // If at this step the candidate list is empty, the shortest-path tree (of
1400 // transit vertices) has been completely built and this stage of the
1401 // procedure terminates.
1402 //
1403  if (candidate.Size () == 0)
1404  {
1405  break;
1406  }
1407 //
1408 // Choose the vertex belonging to the candidate list that is closest to the
1409 // root, and add it to the shortest-path tree (removing it from the candidate
1410 // list in the process).
1411 //
1412 // Recall that in the previous step, we created SPFVertex structures for each
1413 // of the routers found in the Global Router Link Records and added tehm to
1414 // the candidate list.
1415 //
1416  NS_LOG_LOGIC (candidate);
1417  v = candidate.Pop ();
1418  NS_LOG_LOGIC ("Popped vertex " << v->GetVertexId ());
1419 //
1420 // Update the status field of the vertex to indicate that it is in the SPF
1421 // tree.
1422 //
1423  v->GetLSA ()->SetStatus (GlobalRoutingLSA::LSA_SPF_IN_SPFTREE);
1424 //
1425 // The current vertex has a parent pointer. By calling this rather oddly
1426 // named method (blame quagga) we add the current vertex to the list of
1427 // children of that parent vertex. In the next hop calculation called during
1428 // SPFNext, the parent pointer was set but the vertex has been orphaned up
1429 // to now.
1430 //
1431  SPFVertexAddParent (v);
1432 //
1433 // Note that when there is a choice of vertices closest to the root, network
1434 // vertices must be chosen before router vertices in order to necessarily
1435 // find all equal-cost paths.
1436 //
1437 // RFC2328 16.1. (4).
1438 //
1439 // This is the method that actually adds the routes. It'll walk the list
1440 // of nodes in the system, looking for the node corresponding to the router
1441 // ID of the root of the tree -- that is the router we're building the routes
1442 // for. It looks for the Ipv4 interface of that node and remembers it. So
1443 // we are only actually adding routes to that one node at the root of the SPF
1444 // tree.
1445 //
1446 // We're going to pop of a pointer to every vertex in the tree except the
1447 // root in order of distance from the root. For each of the vertices, we call
1448 // SPFIntraAddRouter (). Down in SPFIntraAddRouter, we look at all of the
1449 // point-to-point Global Router Link Records (the links to nodes adjacent to
1450 // the node represented by the vertex). We add a route to the IP address
1451 // specified by the m_linkData field of each of those link records. This will
1452 // be the *local* IP address associated with the interface attached to the
1453 // link. We use the outbound interface and next hop information present in
1454 // the vertex <v> which have possibly been inherited from the root.
1455 //
1456 // To summarize, we're going to look at the node represented by <v> and loop
1457 // through its point-to-point links, adding a *host* route to the local IP
1458 // address (at the <v> side) for each of those links.
1459 //
1460  if (v->GetVertexType () == SPFVertex::VertexRouter)
1461  {
1462  SPFIntraAddRouter (v);
1463  }
1464  else if (v->GetVertexType () == SPFVertex::VertexNetwork)
1465  {
1466  SPFIntraAddTransit (v);
1467  }
1468  else
1469  {
1470  NS_ASSERT_MSG (0, "illegal SPFVertex type");
1471  }
1472 //
1473 // RFC2328 16.1. (5).
1474 //
1475 // Iterate the algorithm by returning to Step 2 until there are no more
1476 // candidate vertices.
1477 
1478  } // end for loop
1479 
1480 // Second stage of SPF calculation procedure
1481  SPFProcessStubs (m_spfroot);
1482  for (uint32_t i = 0; i < m_lsdb->GetNumExtLSAs (); i++)
1483  {
1484  m_spfroot->ClearVertexProcessed ();
1485  GlobalRoutingLSA *extlsa = m_lsdb->GetExtLSA (i);
1486  NS_LOG_LOGIC ("Processing External LSA with id " << extlsa->GetLinkStateId ());
1487  ProcessASExternals (m_spfroot, extlsa);
1488  }
1489 
1490 //
1491 // We're all done setting the routing information for the node at the root of
1492 // the SPF tree. Delete all of the vertices and corresponding resources. Go
1493 // possibly do it again for the next router.
1494 //
1495  delete m_spfroot;
1496  m_spfroot = 0;
1497 }
1498 
1499 void
1501 {
1502  NS_LOG_FUNCTION (this << v << extlsa);
1503  NS_LOG_LOGIC ("Processing external for destination " <<
1504  extlsa->GetLinkStateId () <<
1505  ", for router " << v->GetVertexId () <<
1506  ", advertised by " << extlsa->GetAdvertisingRouter ());
1508  {
1509  GlobalRoutingLSA *rlsa = v->GetLSA ();
1510  NS_LOG_LOGIC ("Processing router LSA with id " << rlsa->GetLinkStateId ());
1511  if ((rlsa->GetLinkStateId ()) == (extlsa->GetAdvertisingRouter ()))
1512  {
1513  NS_LOG_LOGIC ("Found advertising router to destination");
1514  SPFAddASExternal (extlsa,v);
1515  }
1516  }
1517  for (uint32_t i = 0; i < v->GetNChildren (); i++)
1518  {
1519  if (!v->GetChild (i)->IsVertexProcessed ())
1520  {
1521  NS_LOG_LOGIC ("Vertex's child " << i << " not yet processed, processing...");
1522  ProcessASExternals (v->GetChild (i), extlsa);
1523  v->GetChild (i)->SetVertexProcessed (true);
1524  }
1525  }
1526 }
1527 
1528 //
1529 // Adding external routes to routing table - modeled after
1530 // SPFAddIntraAddStub()
1531 //
1532 
1533 void
1535 {
1536  NS_LOG_FUNCTION (this << extlsa << v);
1537 
1538  NS_ASSERT_MSG (m_spfroot, "GlobalRouteManagerImpl::SPFAddASExternal (): Root pointer not set");
1539 // Two cases to consider: We are advertising the external ourselves
1540 // => No need to add anything
1541 // OR find best path to the advertising router
1542  if (v->GetVertexId () == m_spfroot->GetVertexId ())
1543  {
1544  NS_LOG_LOGIC ("External is on local host: "
1545  << v->GetVertexId () << "; returning");
1546  return;
1547  }
1548  NS_LOG_LOGIC ("External is on remote host: "
1549  << extlsa->GetAdvertisingRouter () << "; installing");
1550 
1551  Ipv4Address routerId = m_spfroot->GetVertexId ();
1552 
1553  NS_LOG_LOGIC ("Vertex ID = " << routerId);
1554 //
1555 // We need to walk the list of nodes looking for the one that has the router
1556 // ID corresponding to the root vertex. This is the one we're going to write
1557 // the routing information to.
1558 //
1560  NodeList::Iterator listEnd = NodeList::End ();
1561  for (; i != listEnd; i++)
1562  {
1563  Ptr<Node> node = *i;
1564 //
1565 // The router ID is accessible through the GlobalRouter interface, so we need
1566 // to QI for that interface. If there's no GlobalRouter interface, the node
1567 // in question cannot be the router we want, so we continue.
1568 //
1569  Ptr<GlobalRouter> rtr = node->GetObject<GlobalRouter> ();
1570 
1571  if (rtr == 0)
1572  {
1573  NS_LOG_LOGIC ("No GlobalRouter interface on node " << node->GetId ());
1574  continue;
1575  }
1576 //
1577 // If the router ID of the current node is equal to the router ID of the
1578 // root of the SPF tree, then this node is the one for which we need to
1579 // write the routing tables.
1580 //
1581  NS_LOG_LOGIC ("Considering router " << rtr->GetRouterId ());
1582 
1583  if (rtr->GetRouterId () == routerId)
1584  {
1585  NS_LOG_LOGIC ("Setting routes for node " << node->GetId ());
1586 //
1587 // Routing information is updated using the Ipv4 interface. We need to QI
1588 // for that interface. If the node is acting as an IP version 4 router, it
1589 // should absolutely have an Ipv4 interface.
1590 //
1591  Ptr<Ipv4> ipv4 = node->GetObject<Ipv4> ();
1592  NS_ASSERT_MSG (ipv4,
1593  "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
1594  "QI for <Ipv4> interface failed");
1595 //
1596 // Get the Global Router Link State Advertisement from the vertex we're
1597 // adding the routes to. The LSA will have a number of attached Global Router
1598 // Link Records corresponding to links off of that vertex / node. We're going
1599 // to be interested in the records corresponding to point-to-point links.
1600 //
1601  NS_ASSERT_MSG (v->GetLSA (),
1602  "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
1603  "Expected valid LSA in SPFVertex* v");
1604  Ipv4Mask tempmask = extlsa->GetNetworkLSANetworkMask ();
1605  Ipv4Address tempip = extlsa->GetLinkStateId ();
1606  tempip = tempip.CombineMask (tempmask);
1607 
1608 //
1609 // Here's why we did all of that work. We're going to add a host route to the
1610 // host address found in the m_linkData field of the point-to-point link
1611 // record. In the case of a point-to-point link, this is the local IP address
1612 // of the node connected to the link. Each of these point-to-point links
1613 // will correspond to a local interface that has an IP address to which
1614 // the node at the root of the SPF tree can send packets. The vertex <v>
1615 // (corresponding to the node that has these links and interfaces) has
1616 // an m_nextHop address precalculated for us that is the address to which the
1617 // root node should send packets to be forwarded to these IP addresses.
1618 // Similarly, the vertex <v> has an m_rootOif (outbound interface index) to
1619 // which the packets should be send for forwarding.
1620 //
1621  Ptr<GlobalRouter> router = node->GetObject<GlobalRouter> ();
1622  if (router == 0)
1623  {
1624  continue;
1625  }
1626  Ptr<Ipv4GlobalRouting> gr = router->GetRoutingProtocol ();
1627  NS_ASSERT (gr);
1628  // walk through all next-hop-IPs and out-going-interfaces for reaching
1629  // the stub network gateway 'v' from the root node
1630  for (uint32_t i = 0; i < v->GetNRootExitDirections (); i++)
1631  {
1633  Ipv4Address nextHop = exit.first;
1634  int32_t outIf = exit.second;
1635  if (outIf >= 0)
1636  {
1637  gr->AddASExternalRouteTo (tempip, tempmask, nextHop, outIf);
1638  NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () <<
1639  " add external network route to " << tempip <<
1640  " using next hop " << nextHop <<
1641  " via interface " << outIf);
1642  }
1643  else
1644  {
1645  NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () <<
1646  " NOT able to add network route to " << tempip <<
1647  " using next hop " << nextHop <<
1648  " since outgoing interface id is negative");
1649  }
1650  }
1651  return;
1652  } // if
1653  } // for
1654 }
1655 
1656 
1657 // Processing logic from RFC 2328, page 166 and quagga ospf_spf_process_stubs ()
1658 // stub link records will exist for point-to-point interfaces and for
1659 // broadcast interfaces for which no neighboring router can be found
1660 void
1662 {
1663  NS_LOG_FUNCTION (this << v);
1664  NS_LOG_LOGIC ("Processing stubs for " << v->GetVertexId ());
1666  {
1667  GlobalRoutingLSA *rlsa = v->GetLSA ();
1668  NS_LOG_LOGIC ("Processing router LSA with id " << rlsa->GetLinkStateId ());
1669  for (uint32_t i = 0; i < rlsa->GetNLinkRecords (); i++)
1670  {
1671  NS_LOG_LOGIC ("Examining link " << i << " of " <<
1672  v->GetVertexId () << "'s " <<
1673  v->GetLSA ()->GetNLinkRecords () << " link records");
1675  if (l->GetLinkType () == GlobalRoutingLinkRecord::StubNetwork)
1676  {
1677  NS_LOG_LOGIC ("Found a Stub record to " << l->GetLinkId ());
1678  SPFIntraAddStub (l, v);
1679  continue;
1680  }
1681  }
1682  }
1683  for (uint32_t i = 0; i < v->GetNChildren (); i++)
1684  {
1685  if (!v->GetChild (i)->IsVertexProcessed ())
1686  {
1687  SPFProcessStubs (v->GetChild (i));
1688  v->GetChild (i)->SetVertexProcessed (true);
1689  }
1690  }
1691 }
1692 
1693 // RFC2328 16.1. second stage.
1694 void
1696 {
1697  NS_LOG_FUNCTION (this << l << v);
1698 
1700  "GlobalRouteManagerImpl::SPFIntraAddStub (): Root pointer not set");
1701 
1702  // XXX simplifed logic for the moment. There are two cases to consider:
1703  // 1) the stub network is on this router; do nothing for now
1704  // (already handled above)
1705  // 2) the stub network is on a remote router, so I should use the
1706  // same next hop that I use to get to vertex v
1707  if (v->GetVertexId () == m_spfroot->GetVertexId ())
1708  {
1709  NS_LOG_LOGIC ("Stub is on local host: " << v->GetVertexId () << "; returning");
1710  return;
1711  }
1712  NS_LOG_LOGIC ("Stub is on remote host: " << v->GetVertexId () << "; installing");
1713 //
1714 // The root of the Shortest Path First tree is the router to which we are
1715 // going to write the actual routing table entries. The vertex corresponding
1716 // to this router has a vertex ID which is the router ID of that node. We're
1717 // going to use this ID to discover which node it is that we're actually going
1718 // to update.
1719 //
1720  Ipv4Address routerId = m_spfroot->GetVertexId ();
1721 
1722  NS_LOG_LOGIC ("Vertex ID = " << routerId);
1723 //
1724 // We need to walk the list of nodes looking for the one that has the router
1725 // ID corresponding to the root vertex. This is the one we're going to write
1726 // the routing information to.
1727 //
1729  NodeList::Iterator listEnd = NodeList::End ();
1730  for (; i != listEnd; i++)
1731  {
1732  Ptr<Node> node = *i;
1733 //
1734 // The router ID is accessible through the GlobalRouter interface, so we need
1735 // to QI for that interface. If there's no GlobalRouter interface, the node
1736 // in question cannot be the router we want, so we continue.
1737 //
1738  Ptr<GlobalRouter> rtr =
1739  node->GetObject<GlobalRouter> ();
1740 
1741  if (rtr == 0)
1742  {
1743  NS_LOG_LOGIC ("No GlobalRouter interface on node " <<
1744  node->GetId ());
1745  continue;
1746  }
1747 //
1748 // If the router ID of the current node is equal to the router ID of the
1749 // root of the SPF tree, then this node is the one for which we need to
1750 // write the routing tables.
1751 //
1752  NS_LOG_LOGIC ("Considering router " << rtr->GetRouterId ());
1753 
1754  if (rtr->GetRouterId () == routerId)
1755  {
1756  NS_LOG_LOGIC ("Setting routes for node " << node->GetId ());
1757 //
1758 // Routing information is updated using the Ipv4 interface. We need to QI
1759 // for that interface. If the node is acting as an IP version 4 router, it
1760 // should absolutely have an Ipv4 interface.
1761 //
1762  Ptr<Ipv4> ipv4 = node->GetObject<Ipv4> ();
1763  NS_ASSERT_MSG (ipv4,
1764  "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
1765  "QI for <Ipv4> interface failed");
1766 //
1767 // Get the Global Router Link State Advertisement from the vertex we're
1768 // adding the routes to. The LSA will have a number of attached Global Router
1769 // Link Records corresponding to links off of that vertex / node. We're going
1770 // to be interested in the records corresponding to point-to-point links.
1771 //
1772  NS_ASSERT_MSG (v->GetLSA (),
1773  "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
1774  "Expected valid LSA in SPFVertex* v");
1775  Ipv4Mask tempmask (l->GetLinkData ().Get ());
1776  Ipv4Address tempip = l->GetLinkId ();
1777  tempip = tempip.CombineMask (tempmask);
1778 //
1779 // Here's why we did all of that work. We're going to add a host route to the
1780 // host address found in the m_linkData field of the point-to-point link
1781 // record. In the case of a point-to-point link, this is the local IP address
1782 // of the node connected to the link. Each of these point-to-point links
1783 // will correspond to a local interface that has an IP address to which
1784 // the node at the root of the SPF tree can send packets. The vertex <v>
1785 // (corresponding to the node that has these links and interfaces) has
1786 // an m_nextHop address precalculated for us that is the address to which the
1787 // root node should send packets to be forwarded to these IP addresses.
1788 // Similarly, the vertex <v> has an m_rootOif (outbound interface index) to
1789 // which the packets should be send for forwarding.
1790 //
1791 
1792  Ptr<GlobalRouter> router = node->GetObject<GlobalRouter> ();
1793  if (router == 0)
1794  {
1795  continue;
1796  }
1797  Ptr<Ipv4GlobalRouting> gr = router->GetRoutingProtocol ();
1798  NS_ASSERT (gr);
1799  // walk through all next-hop-IPs and out-going-interfaces for reaching
1800  // the stub network gateway 'v' from the root node
1801  for (uint32_t i = 0; i < v->GetNRootExitDirections (); i++)
1802  {
1804  Ipv4Address nextHop = exit.first;
1805  int32_t outIf = exit.second;
1806  if (outIf >= 0)
1807  {
1808  gr->AddNetworkRouteTo (tempip, tempmask, nextHop, outIf);
1809  NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () <<
1810  " add network route to " << tempip <<
1811  " using next hop " << nextHop <<
1812  " via interface " << outIf);
1813  }
1814  else
1815  {
1816  NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () <<
1817  " NOT able to add network route to " << tempip <<
1818  " using next hop " << nextHop <<
1819  " since outgoing interface id is negative");
1820  }
1821  }
1822  return;
1823  } // if
1824  } // for
1825 }
1826 
1827 //
1828 // Return the interface number corresponding to a given IP address and mask
1829 // This is a wrapper around GetInterfaceForPrefix(), but we first
1830 // have to find the right node pointer to pass to that function.
1831 // If no such interface is found, return -1 (note: unit test framework
1832 // for routing assumes -1 to be a legal return value)
1833 //
1834 int32_t
1836 {
1837  NS_LOG_FUNCTION (this << a << amask);
1838 //
1839 // We have an IP address <a> and a vertex ID of the root of the SPF tree.
1840 // The question is what interface index does this address correspond to.
1841 // The answer is a little complicated since we have to find a pointer to
1842 // the node corresponding to the vertex ID, find the Ipv4 interface on that
1843 // node in order to iterate the interfaces and find the one corresponding to
1844 // the address in question.
1845 //
1846  Ipv4Address routerId = m_spfroot->GetVertexId ();
1847 //
1848 // Walk the list of nodes in the system looking for the one corresponding to
1849 // the node at the root of the SPF tree. This is the node for which we are
1850 // building the routing table.
1851 //
1853  NodeList::Iterator listEnd = NodeList::End ();
1854  for (; i != listEnd; i++)
1855  {
1856  Ptr<Node> node = *i;
1857 
1858  Ptr<GlobalRouter> rtr =
1859  node->GetObject<GlobalRouter> ();
1860 //
1861 // If the node doesn't have a GlobalRouter interface it can't be the one
1862 // we're interested in.
1863 //
1864  if (rtr == 0)
1865  {
1866  continue;
1867  }
1868 
1869  if (rtr->GetRouterId () == routerId)
1870  {
1871 //
1872 // This is the node we're building the routing table for. We're going to need
1873 // the Ipv4 interface to look for the ipv4 interface index. Since this node
1874 // is participating in routing IP version 4 packets, it certainly must have
1875 // an Ipv4 interface.
1876 //
1877  Ptr<Ipv4> ipv4 = node->GetObject<Ipv4> ();
1878  NS_ASSERT_MSG (ipv4,
1879  "GlobalRouteManagerImpl::FindOutgoingInterfaceId (): "
1880  "GetObject for <Ipv4> interface failed");
1881 //
1882 // Look through the interfaces on this node for one that has the IP address
1883 // we're looking for. If we find one, return the corresponding interface
1884 // index, or -1 if not found.
1885 //
1886  int32_t interface = ipv4->GetInterfaceForPrefix (a, amask);
1887 
1888 #if 0
1889  if (interface < 0)
1890  {
1891  NS_FATAL_ERROR ("GlobalRouteManagerImpl::FindOutgoingInterfaceId(): "
1892  "Expected an interface associated with address a:" << a);
1893  }
1894 #endif
1895  return interface;
1896  }
1897  }
1898 //
1899 // Couldn't find it.
1900 //
1901  NS_LOG_LOGIC ("FindOutgoingInterfaceId():Can't find root node " << routerId);
1902  return -1;
1903 }
1904 
1905 //
1906 // This method is derived from quagga ospf_intra_add_router ()
1907 //
1908 // This is where we are actually going to add the host routes to the routing
1909 // tables of the individual nodes.
1910 //
1911 // The vertex passed as a parameter has just been added to the SPF tree.
1912 // This vertex must have a valid m_root_oid, corresponding to the outgoing
1913 // interface on the root router of the tree that is the first hop on the path
1914 // to the vertex. The vertex must also have a next hop address, corresponding
1915 // to the next hop on the path to the vertex. The vertex has an m_lsa field
1916 // that has some number of link records. For each point to point link record,
1917 // the m_linkData is the local IP address of the link. This corresponds to
1918 // a destination IP address, reachable from the root, to which we add a host
1919 // route.
1920 //
1921 void
1923 {
1924  NS_LOG_FUNCTION (this << v);
1925 
1927  "GlobalRouteManagerImpl::SPFIntraAddRouter (): Root pointer not set");
1928 //
1929 // The root of the Shortest Path First tree is the router to which we are
1930 // going to write the actual routing table entries. The vertex corresponding
1931 // to this router has a vertex ID which is the router ID of that node. We're
1932 // going to use this ID to discover which node it is that we're actually going
1933 // to update.
1934 //
1935  Ipv4Address routerId = m_spfroot->GetVertexId ();
1936 
1937  NS_LOG_LOGIC ("Vertex ID = " << routerId);
1938 //
1939 // We need to walk the list of nodes looking for the one that has the router
1940 // ID corresponding to the root vertex. This is the one we're going to write
1941 // the routing information to.
1942 //
1944  NodeList::Iterator listEnd = NodeList::End ();
1945  for (; i != listEnd; i++)
1946  {
1947  Ptr<Node> node = *i;
1948 //
1949 // The router ID is accessible through the GlobalRouter interface, so we need
1950 // to GetObject for that interface. If there's no GlobalRouter interface,
1951 // the node in question cannot be the router we want, so we continue.
1952 //
1953  Ptr<GlobalRouter> rtr =
1954  node->GetObject<GlobalRouter> ();
1955 
1956  if (rtr == 0)
1957  {
1958  NS_LOG_LOGIC ("No GlobalRouter interface on node " <<
1959  node->GetId ());
1960  continue;
1961  }
1962 //
1963 // If the router ID of the current node is equal to the router ID of the
1964 // root of the SPF tree, then this node is the one for which we need to
1965 // write the routing tables.
1966 //
1967  NS_LOG_LOGIC ("Considering router " << rtr->GetRouterId ());
1968 
1969  if (rtr->GetRouterId () == routerId)
1970  {
1971  NS_LOG_LOGIC ("Setting routes for node " << node->GetId ());
1972 //
1973 // Routing information is updated using the Ipv4 interface. We need to
1974 // GetObject for that interface. If the node is acting as an IP version 4
1975 // router, it should absolutely have an Ipv4 interface.
1976 //
1977  Ptr<Ipv4> ipv4 = node->GetObject<Ipv4> ();
1978  NS_ASSERT_MSG (ipv4,
1979  "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
1980  "GetObject for <Ipv4> interface failed");
1981 //
1982 // Get the Global Router Link State Advertisement from the vertex we're
1983 // adding the routes to. The LSA will have a number of attached Global Router
1984 // Link Records corresponding to links off of that vertex / node. We're going
1985 // to be interested in the records corresponding to point-to-point links.
1986 //
1987  GlobalRoutingLSA *lsa = v->GetLSA ();
1988  NS_ASSERT_MSG (lsa,
1989  "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
1990  "Expected valid LSA in SPFVertex* v");
1991 
1992  uint32_t nLinkRecords = lsa->GetNLinkRecords ();
1993 //
1994 // Iterate through the link records on the vertex to which we're going to add
1995 // routes. To make sure we're being clear, we're going to add routing table
1996 // entries to the tables on the node corresping to the root of the SPF tree.
1997 // These entries will have routes to the IP addresses we find from looking at
1998 // the local side of the point-to-point links found on the node described by
1999 // the vertex <v>.
2000 //
2001  NS_LOG_LOGIC (" Node " << node->GetId () <<
2002  " found " << nLinkRecords << " link records in LSA " << lsa << "with LinkStateId "<< lsa->GetLinkStateId ());
2003  for (uint32_t j = 0; j < nLinkRecords; ++j)
2004  {
2005 //
2006 // We are only concerned about point-to-point links
2007 //
2008  GlobalRoutingLinkRecord *lr = lsa->GetLinkRecord (j);
2010  {
2011  continue;
2012  }
2013 //
2014 // Here's why we did all of that work. We're going to add a host route to the
2015 // host address found in the m_linkData field of the point-to-point link
2016 // record. In the case of a point-to-point link, this is the local IP address
2017 // of the node connected to the link. Each of these point-to-point links
2018 // will correspond to a local interface that has an IP address to which
2019 // the node at the root of the SPF tree can send packets. The vertex <v>
2020 // (corresponding to the node that has these links and interfaces) has
2021 // an m_nextHop address precalculated for us that is the address to which the
2022 // root node should send packets to be forwarded to these IP addresses.
2023 // Similarly, the vertex <v> has an m_rootOif (outbound interface index) to
2024 // which the packets should be send for forwarding.
2025 //
2026  Ptr<GlobalRouter> router = node->GetObject<GlobalRouter> ();
2027  if (router == 0)
2028  {
2029  continue;
2030  }
2031  Ptr<Ipv4GlobalRouting> gr = router->GetRoutingProtocol ();
2032  NS_ASSERT (gr);
2033  // walk through all available exit directions due to ECMP,
2034  // and add host route for each of the exit direction toward
2035  // the vertex 'v'
2036  for (uint32_t i = 0; i < v->GetNRootExitDirections (); i++)
2037  {
2039  Ipv4Address nextHop = exit.first;
2040  int32_t outIf = exit.second;
2041  if (outIf >= 0)
2042  {
2043  gr->AddHostRouteTo (lr->GetLinkData (), nextHop,
2044  outIf);
2045  NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () <<
2046  " adding host route to " << lr->GetLinkData () <<
2047  " using next hop " << nextHop <<
2048  " and outgoing interface " << outIf);
2049  }
2050  else
2051  {
2052  NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () <<
2053  " NOT able to add host route to " << lr->GetLinkData () <<
2054  " using next hop " << nextHop <<
2055  " since outgoing interface id is negative " << outIf);
2056  }
2057  } // for all routes from the root the vertex 'v'
2058  }
2059 //
2060 // Done adding the routes for the selected node.
2061 //
2062  return;
2063  }
2064  }
2065 }
2066 void
2068 {
2069  NS_LOG_FUNCTION (this << v);
2070 
2072  "GlobalRouteManagerImpl::SPFIntraAddTransit (): Root pointer not set");
2073 //
2074 // The root of the Shortest Path First tree is the router to which we are
2075 // going to write the actual routing table entries. The vertex corresponding
2076 // to this router has a vertex ID which is the router ID of that node. We're
2077 // going to use this ID to discover which node it is that we're actually going
2078 // to update.
2079 //
2080  Ipv4Address routerId = m_spfroot->GetVertexId ();
2081 
2082  NS_LOG_LOGIC ("Vertex ID = " << routerId);
2083 //
2084 // We need to walk the list of nodes looking for the one that has the router
2085 // ID corresponding to the root vertex. This is the one we're going to write
2086 // the routing information to.
2087 //
2089  NodeList::Iterator listEnd = NodeList::End ();
2090  for (; i != listEnd; i++)
2091  {
2092  Ptr<Node> node = *i;
2093 //
2094 // The router ID is accessible through the GlobalRouter interface, so we need
2095 // to GetObject for that interface. If there's no GlobalRouter interface,
2096 // the node in question cannot be the router we want, so we continue.
2097 //
2098  Ptr<GlobalRouter> rtr =
2099  node->GetObject<GlobalRouter> ();
2100 
2101  if (rtr == 0)
2102  {
2103  NS_LOG_LOGIC ("No GlobalRouter interface on node " <<
2104  node->GetId ());
2105  continue;
2106  }
2107 //
2108 // If the router ID of the current node is equal to the router ID of the
2109 // root of the SPF tree, then this node is the one for which we need to
2110 // write the routing tables.
2111 //
2112  NS_LOG_LOGIC ("Considering router " << rtr->GetRouterId ());
2113 
2114  if (rtr->GetRouterId () == routerId)
2115  {
2116  NS_LOG_LOGIC ("setting routes for node " << node->GetId ());
2117 //
2118 // Routing information is updated using the Ipv4 interface. We need to
2119 // GetObject for that interface. If the node is acting as an IP version 4
2120 // router, it should absolutely have an Ipv4 interface.
2121 //
2122  Ptr<Ipv4> ipv4 = node->GetObject<Ipv4> ();
2123  NS_ASSERT_MSG (ipv4,
2124  "GlobalRouteManagerImpl::SPFIntraAddTransit (): "
2125  "GetObject for <Ipv4> interface failed");
2126 //
2127 // Get the Global Router Link State Advertisement from the vertex we're
2128 // adding the routes to. The LSA will have a number of attached Global Router
2129 // Link Records corresponding to links off of that vertex / node. We're going
2130 // to be interested in the records corresponding to point-to-point links.
2131 //
2132  GlobalRoutingLSA *lsa = v->GetLSA ();
2133  NS_ASSERT_MSG (lsa,
2134  "GlobalRouteManagerImpl::SPFIntraAddTransit (): "
2135  "Expected valid LSA in SPFVertex* v");
2136  Ipv4Mask tempmask = lsa->GetNetworkLSANetworkMask ();
2137  Ipv4Address tempip = lsa->GetLinkStateId ();
2138  tempip = tempip.CombineMask (tempmask);
2139  Ptr<GlobalRouter> router = node->GetObject<GlobalRouter> ();
2140  if (router == 0)
2141  {
2142  continue;
2143  }
2144  Ptr<Ipv4GlobalRouting> gr = router->GetRoutingProtocol ();
2145  NS_ASSERT (gr);
2146  // walk through all available exit directions due to ECMP,
2147  // and add host route for each of the exit direction toward
2148  // the vertex 'v'
2149  for (uint32_t i = 0; i < v->GetNRootExitDirections (); i++)
2150  {
2152  Ipv4Address nextHop = exit.first;
2153  int32_t outIf = exit.second;
2154 
2155  if (outIf >= 0)
2156  {
2157  gr->AddNetworkRouteTo (tempip, tempmask, nextHop, outIf);
2158  NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () <<
2159  " add network route to " << tempip <<
2160  " using next hop " << nextHop <<
2161  " via interface " << outIf);
2162  }
2163  else
2164  {
2165  NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () <<
2166  " NOT able to add network route to " << tempip <<
2167  " using next hop " << nextHop <<
2168  " since outgoing interface id is negative " << outIf);
2169  }
2170  }
2171  }
2172  }
2173 }
2174 
2175 // Derived from quagga ospf_vertex_add_parents ()
2176 //
2177 // This is a somewhat oddly named method (blame quagga). Although you might
2178 // expect it to add a parent *to* something, it actually adds a vertex
2179 // to the list of children *in* each of its parents.
2180 //
2181 // Given a pointer to a vertex, it links back to the vertex's parent that it
2182 // already has set and adds itself to that vertex's list of children.
2183 //
2184 void
2186 {
2187  NS_LOG_FUNCTION (this << v);
2188 
2189  for (uint32_t i=0;;)
2190  {
2191  SPFVertex* parent;
2192  // check if all parents of vertex v
2193  if ((parent = v->GetParent (i++)) == 0) break;
2194  parent->AddChild (v);
2195  }
2196 }
2197 
2198 } // namespace ns3
2199 
2200