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