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