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