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