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