A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
global-route-manager-impl.h
Go to the documentation of this file.
1/*
2 * Copyright 2007 University of Washington
3 *
4 * SPDX-License-Identifier: GPL-2.0-only
5 *
6 * Authors: Craig Dowell (craigdo@ee.washington.edu)
7 * Tom Henderson (tomhend@u.washington.edu)
8 */
9
10#ifndef GLOBAL_ROUTE_MANAGER_IMPL_H
11#define GLOBAL_ROUTE_MANAGER_IMPL_H
12
14
15#include "ns3/ipv4-address.h"
16#include "ns3/object.h"
17#include "ns3/ptr.h"
18
19#include <list>
20#include <map>
21#include <queue>
22#include <stdint.h>
23#include <vector>
24
25namespace ns3
26{
27
28const uint32_t SPF_INFINITY = 0xffffffff; //!< "infinite" distance between nodes
29
30class CandidateQueue;
32
33/**
34 * \ingroup globalrouting
35 *
36 * @brief Vertex used in shortest path first (SPF) computations. See \RFC{2328},
37 * Section 16.
38 *
39 * Each router in the simulation is associated with an SPFVertex object. When
40 * calculating routes, each of these routers is, in turn, chosen as the "root"
41 * of the calculation and routes to all of the other routers are eventually
42 * saved in the routing tables of each of the chosen nodes. Each of these
43 * routers in the calculation has an associated SPFVertex.
44 *
45 * The "Root" vertex is the SPFVertex representing the router that is having
46 * its routing tables set. The SPFVertex objects representing other routers
47 * or networks in the simulation are arranged in the SPF tree. It is this
48 * tree that represents the Shortest Paths to the other networks.
49 *
50 * Each SPFVertex has a pointer to the Global Router Link State Advertisement
51 * (LSA) that its underlying router has exported. Within these LSAs are
52 * Global Router Link Records that describe the point to point links from the
53 * underlying router to other nodes (represented by other SPFVertex objects)
54 * in the simulation topology. The combination of the arrangement of the
55 * SPFVertex objects in the SPF tree, along with the details of the link
56 * records that connect them provide the information required to construct the
57 * required routes.
58 */
60{
61 public:
62 /**
63 * @brief Enumeration of the possible types of SPFVertex objects.
64 *
65 * Currently we use VertexRouter to identify objects that represent a router
66 * in the simulation topology, and VertexNetwork to identify objects that
67 * represent a network.
68 */
70 {
71 VertexUnknown = 0, /**< Uninitialized Link Record */
72 VertexRouter, /**< Vertex representing a router in the topology */
73 VertexNetwork /**< Vertex representing a network in the topology */
74 };
75
76 /**
77 * @brief Construct an empty ("uninitialized") SPFVertex (Shortest Path First
78 * Vertex).
79 *
80 * The Vertex Type is set to VertexUnknown, the Vertex ID is set to
81 * 255.255.255.255, and the distance from root is set to infinity
82 * (UINT32_MAX). The referenced Link State Advertisement (LSA) is set to
83 * null as is the parent SPFVertex. The outgoing interface index is set to
84 * infinity, the next hop address is set to 0.0.0.0 and the list of children
85 * of the SPFVertex is initialized to empty.
86 *
87 * @see VertexType
88 */
89 SPFVertex();
90
91 /**
92 * @brief Construct an initialized SPFVertex (Shortest Path First Vertex).
93 *
94 * The Vertex Type is initialized to VertexRouter and the Vertex ID is found
95 * from the Link State ID of the Link State Advertisement (LSA) passed as a
96 * parameter. The Link State ID is set to the Router ID of the advertising
97 * router. The referenced LSA (m_lsa) is set to the given LSA. Other than
98 * these members, initialization is as in the default constructor.
99 * of the SPFVertex is initialized to empty.
100 *
101 * @see SPFVertex::SPFVertex ()
102 * @see VertexType
103 * @see GlobalRoutingLSA
104 * @param lsa The Link State Advertisement used for finding initial values.
105 */
107
108 /**
109 * @brief Destroy an SPFVertex (Shortest Path First Vertex).
110 *
111 * The children vertices of the SPFVertex are recursively deleted.
112 *
113 * @see SPFVertex::SPFVertex ()
114 */
115 ~SPFVertex();
116
117 // Delete copy constructor and assignment operator to avoid misuse
118 SPFVertex(const SPFVertex&) = delete;
119 SPFVertex& operator=(const SPFVertex&) = delete;
120
121 /**
122 * @brief Get the Vertex Type field of a SPFVertex object.
123 *
124 * The Vertex Type describes the kind of simulation object a given SPFVertex
125 * represents.
126 *
127 * @see VertexType
128 * @returns The VertexType of the current SPFVertex object.
129 */
131
132 /**
133 * @brief Set the Vertex Type field of a SPFVertex object.
134 *
135 * The Vertex Type describes the kind of simulation object a given SPFVertex
136 * represents.
137 *
138 * @see VertexType
139 * @param type The new VertexType for the current SPFVertex object.
140 */
141 void SetVertexType(VertexType type);
142
143 /**
144 * @brief Get the Vertex ID field of a SPFVertex object.
145 *
146 * The Vertex ID uniquely identifies the simulation object a given SPFVertex
147 * represents. Typically, this is the Router ID for SPFVertex objects
148 * representing routers, and comes from the Link State Advertisement of a
149 * router aggregated to a node in the simulation. These IDs are allocated
150 * automatically by the routing environment and look like IP addresses
151 * beginning at 0.0.0.0 and monotonically increasing as new routers are
152 * instantiated.
153 *
154 * @returns The Ipv4Address Vertex ID of the current SPFVertex object.
155 */
156 Ipv4Address GetVertexId() const;
157
158 /**
159 * @brief Set the Vertex ID field of a SPFVertex object.
160 *
161 * The Vertex ID uniquely identifies the simulation object a given SPFVertex
162 * represents. Typically, this is the Router ID for SPFVertex objects
163 * representing routers, and comes from the Link State Advertisement of a
164 * router aggregated to a node in the simulation. These IDs are allocated
165 * automatically by the routing environment and look like IP addresses
166 * beginning at 0.0.0.0 and monotonically increase as new routers are
167 * instantiated. This method is an explicit override of the automatically
168 * generated value.
169 *
170 * @param id The new Ipv4Address Vertex ID for the current SPFVertex object.
171 */
172 void SetVertexId(Ipv4Address id);
173
174 /**
175 * @brief Get the Global Router Link State Advertisement returned by the
176 * Global Router represented by this SPFVertex during the route discovery
177 * process.
178 *
179 * @see GlobalRouter
180 * @see GlobalRoutingLSA
181 * @see GlobalRouter::DiscoverLSAs ()
182 * @returns A pointer to the GlobalRoutingLSA found by the router represented
183 * by this SPFVertex object.
184 */
185 GlobalRoutingLSA* GetLSA() const;
186
187 /**
188 * @brief Set the Global Router Link State Advertisement returned by the
189 * Global Router represented by this SPFVertex during the route discovery
190 * process.
191 *
192 * @see SPFVertex::GetLSA ()
193 * @see GlobalRouter
194 * @see GlobalRoutingLSA
195 * @see GlobalRouter::DiscoverLSAs ()
196 * @warning Ownership of the LSA is transferred to the "this" SPFVertex. You
197 * must not delete the LSA after calling this method.
198 * @param lsa A pointer to the GlobalRoutingLSA.
199 */
200 void SetLSA(GlobalRoutingLSA* lsa);
201
202 /**
203 * @brief Get the distance from the root vertex to "this" SPFVertex object.
204 *
205 * Each router in the simulation is associated with an SPFVertex object. When
206 * calculating routes, each of these routers is, in turn, chosen as the "root"
207 * of the calculation and routes to all of the other routers are eventually
208 * saved in the routing tables of each of the chosen nodes. Each of these
209 * routers in the calculation has an associated SPFVertex.
210 *
211 * The "Root" vertex is then the SPFVertex representing the router that is
212 * having its routing tables set. The "this" SPFVertex is the vertex to which
213 * a route is being calculated from the root. The distance from the root that
214 * we're asking for is the number of hops from the root vertex to the vertex
215 * in question.
216 *
217 * The distance is calculated during route discovery and is stored in a
218 * member variable. This method simply fetches that value.
219 *
220 * @returns The distance, in hops, from the root SPFVertex to "this" SPFVertex.
221 */
223
224 /**
225 * @brief Set the distance from the root vertex to "this" SPFVertex object.
226 *
227 * Each router in the simulation is associated with an SPFVertex object. When
228 * calculating routes, each of these routers is, in turn, chosen as the "root"
229 * of the calculation and routes to all of the other routers are eventually
230 * saved in the routing tables of each of the chosen nodes. Each of these
231 * routers in the calculation has an associated SPFVertex.
232 *
233 * The "Root" vertex is then the SPFVertex representing the router that is
234 * having its routing tables set. The "this" SPFVertex is the vertex to which
235 * a route is being calculated from the root. The distance from the root that
236 * we're asking for is the number of hops from the root vertex to the vertex
237 * in question.
238 *
239 * @param distance The distance, in hops, from the root SPFVertex to "this"
240 * SPFVertex.
241 */
242 void SetDistanceFromRoot(uint32_t distance);
243
244 /**
245 * @brief Set the IP address and outgoing interface index that should be used
246 * to begin forwarding packets from the root SPFVertex to "this" SPFVertex.
247 *
248 * Each router node in the simulation is associated with an SPFVertex object.
249 * When calculating routes, each of these routers is, in turn, chosen as the
250 * "root" of the calculation and routes to all of the other routers are
251 * eventually saved in the routing tables of each of the chosen nodes.
252 *
253 * The "Root" vertex is then the SPFVertex representing the router that is
254 * having its routing tables set. The "this" SPFVertex is the vertex that
255 * represents the host or network to which a route is being calculated from
256 * the root. The IP address that we're asking for is the address on the
257 * remote side of a link off of the root node that should be used as the
258 * destination for packets along the path to "this" vertex.
259 *
260 * When initializing the root SPFVertex, the IP address used when forwarding
261 * packets is determined by examining the Global Router Link Records of the
262 * Link State Advertisement generated by the root node's GlobalRouter. This
263 * address is used to forward packets off of the root's network down those
264 * links. As other vertices / nodes are discovered which are further away
265 * from the root, they will be accessible down one of the paths via a link
266 * described by one of these Global Router Link Records.
267 *
268 * To forward packets to these hosts or networks, the root node must begin
269 * the forwarding process by sending the packets to a first hop router down
270 * an interface. This means that the first hop address and interface ID must
271 * be the same for all downstream SPFVertices. We call this "inheriting"
272 * the interface and next hop.
273 *
274 * In this method we are telling the root node which exit direction it should send
275 * should I send a packet to the network or host represented by 'this' SPFVertex.
276 *
277 * @see GlobalRouter
278 * @see GlobalRoutingLSA
279 * @see GlobalRoutingLinkRecord
280 * @param nextHop The IP address to use when forwarding packets to the host
281 * or network represented by "this" SPFVertex.
282 * @param id The interface index to use when forwarding packets to the host or
283 * network represented by "this" SPFVertex.
284 */
286
287 typedef std::pair<Ipv4Address, int32_t>
288 NodeExit_t; //!< IPv4 / interface container for exit nodes.
289
290 /**
291 * @brief Set the IP address and outgoing interface index that should be used
292 * to begin forwarding packets from the root SPFVertex to "this" SPFVertex.
293 *
294 * Each router node in the simulation is associated with an SPFVertex object.
295 * When calculating routes, each of these routers is, in turn, chosen as the
296 * "root" of the calculation and routes to all of the other routers are
297 * eventually saved in the routing tables of each of the chosen nodes.
298 *
299 * The "Root" vertex is then the SPFVertex representing the router that is
300 * having its routing tables set. The "this" SPFVertex is the vertex that
301 * represents the host or network to which a route is being calculated from
302 * the root. The IP address that we're asking for is the address on the
303 * remote side of a link off of the root node that should be used as the
304 * destination for packets along the path to "this" vertex.
305 *
306 * When initializing the root SPFVertex, the IP address used when forwarding
307 * packets is determined by examining the Global Router Link Records of the
308 * Link State Advertisement generated by the root node's GlobalRouter. This
309 * address is used to forward packets off of the root's network down those
310 * links. As other vertices / nodes are discovered which are further away
311 * from the root, they will be accessible down one of the paths via a link
312 * described by one of these Global Router Link Records.
313 *
314 * To forward packets to these hosts or networks, the root node must begin
315 * the forwarding process by sending the packets to a first hop router down
316 * an interface. This means that the first hop address and interface ID must
317 * be the same for all downstream SPFVertices. We call this "inheriting"
318 * the interface and next hop.
319 *
320 * In this method we are telling the root node which exit direction it should send
321 * should I send a packet to the network or host represented by 'this' SPFVertex.
322 *
323 * @see GlobalRouter
324 * @see GlobalRoutingLSA
325 * @see GlobalRoutingLinkRecord
326 * @param exit The pair of next-hop-IP and outgoing-interface-index to use when
327 * forwarding packets to the host or network represented by "this" SPFVertex.
328 */
330 /**
331 * \brief Obtain a pair indicating the exit direction from the root
332 *
333 * \param i An index to a pair
334 * \return A pair of next-hop-IP and outgoing-interface-index for
335 * indicating an exit direction from the root. It is 0 if the index 'i'
336 * is out-of-range
337 */
339 /**
340 * \brief Obtain a pair indicating the exit direction from the root
341 *
342 * This method assumes there is only a single exit direction from the root.
343 * Error occur if this assumption is invalid.
344 *
345 * \return The pair of next-hop-IP and outgoing-interface-index for reaching
346 * 'this' vertex from the root
347 */
349 /**
350 * \brief Merge into 'this' vertex the list of exit directions from
351 * another vertex
352 *
353 * This merge is necessary when ECMP are found.
354 *
355 * \param vertex From which the list of exit directions are obtain
356 * and are merged into 'this' vertex
357 */
358 void MergeRootExitDirections(const SPFVertex* vertex);
359 /**
360 * \brief Inherit all root exit directions from a given vertex to 'this' vertex
361 * \param vertex The vertex from which all root exit directions are to be inherited
362 *
363 * After the call of this method, the original root exit directions
364 * in 'this' vertex are all lost.
365 */
366 void InheritAllRootExitDirections(const SPFVertex* vertex);
367 /**
368 * \brief Get the number of exit directions from root for reaching 'this' vertex
369 * \return The number of exit directions from root
370 */
372
373 /**
374 * @brief Get a pointer to the SPFVector that is the parent of "this"
375 * SPFVertex.
376 *
377 * Each router node in the simulation is associated with an SPFVertex object.
378 * When calculating routes, each of these routers is, in turn, chosen as the
379 * "root" of the calculation and routes to all of the other routers are
380 * eventually saved in the routing tables of each of the chosen nodes.
381 *
382 * The "Root" vertex is then the SPFVertex representing the router that is
383 * having its routing tables set and is the root of the SPF tree.
384 *
385 * This method returns a pointer to the parent node of "this" SPFVertex
386 * (both of which reside in that SPF tree).
387 *
388 * @param i The index to one of the parents
389 * @returns A pointer to the SPFVertex that is the parent of "this" SPFVertex
390 * in the SPF tree.
391 */
392 SPFVertex* GetParent(uint32_t i = 0) const;
393
394 /**
395 * @brief Set the pointer to the SPFVector that is the parent of "this"
396 * SPFVertex.
397 *
398 * Each router node in the simulation is associated with an SPFVertex object.
399 * When calculating routes, each of these routers is, in turn, chosen as the
400 * "root" of the calculation and routes to all of the other routers are
401 * eventually saved in the routing tables of each of the chosen nodes.
402 *
403 * The "Root" vertex is then the SPFVertex representing the router that is
404 * having its routing tables set and is the root of the SPF tree.
405 *
406 * This method sets the parent pointer of "this" SPFVertex (both of which
407 * reside in that SPF tree).
408 *
409 * @param parent A pointer to the SPFVertex that is the parent of "this"
410 * SPFVertex* in the SPF tree.
411 */
412 void SetParent(SPFVertex* parent);
413 /**
414 * \brief Merge the Parent list from the v into this vertex
415 *
416 * \param v The vertex from which its list of Parent is read
417 * and then merged into the list of Parent of *this* vertex.
418 * Note that the list in v remains intact
419 */
420 void MergeParent(const SPFVertex* v);
421
422 /**
423 * @brief Get the number of children of "this" SPFVertex.
424 *
425 * Each router node in the simulation is associated with an SPFVertex object.
426 * When calculating routes, each of these routers is, in turn, chosen as the
427 * "root" of the calculation and routes to all of the other routers are
428 * eventually saved in the routing tables of each of the chosen nodes.
429 *
430 * The "Root" vertex is then the SPFVertex representing the router that is
431 * having its routing tables set and is the root of the SPF tree. Each vertex
432 * in the SPF tree can have a number of children that represent host or
433 * network routes available via that vertex.
434 *
435 * This method returns the number of children of "this" SPFVertex (which
436 * reside in the SPF tree).
437 *
438 * @returns The number of children of "this" SPFVertex (which reside in the
439 * SPF tree).
440 */
441 uint32_t GetNChildren() const;
442
443 /**
444 * @brief Get a borrowed SPFVertex pointer to the specified child of "this"
445 * SPFVertex.
446 *
447 * Each router node in the simulation is associated with an SPFVertex object.
448 * When calculating routes, each of these routers is, in turn, chosen as the
449 * "root" of the calculation and routes to all of the other routers are
450 * eventually saved in the routing tables of each of the chosen nodes.
451 *
452 * The "Root" vertex is then the SPFVertex representing the router that is
453 * having its routing tables set and is the root of the SPF tree. Each vertex
454 * in the SPF tree can have a number of children that represent host or
455 * network routes available via that vertex.
456 *
457 * This method the number of children of "this" SPFVertex (which reside in
458 * the SPF tree.
459 *
460 * @see SPFVertex::GetNChildren
461 * @param n The index (from 0 to the number of children minus 1) of the
462 * child SPFVertex to return.
463 * @warning The pointer returned by GetChild () is a borrowed pointer. You
464 * do not have any ownership of the underlying object and must not delete
465 * that object.
466 * @returns A pointer to the specified child SPFVertex (which resides in the
467 * SPF tree).
468 */
469 SPFVertex* GetChild(uint32_t n) const;
470
471 /**
472 * @brief Get a borrowed SPFVertex pointer to the specified child of "this"
473 * SPFVertex.
474 *
475 * Each router node in the simulation is associated with an SPFVertex object.
476 * When calculating routes, each of these routers is, in turn, chosen as the
477 * "root" of the calculation and routes to all of the other routers are
478 * eventually saved in the routing tables of each of the chosen nodes.
479 *
480 * The "Root" vertex is then the SPFVertex representing the router that is
481 * having its routing tables set and is the root of the SPF tree. Each vertex
482 * in the SPF tree can have a number of children that represent host or
483 * network routes available via that vertex.
484 *
485 * This method the number of children of "this" SPFVertex (which reside in
486 * the SPF tree.
487 *
488 * @see SPFVertex::GetNChildren
489 * @warning Ownership of the pointer added to the children of "this"
490 * SPFVertex is transferred to the "this" SPFVertex. You must not delete the
491 * (now) child SPFVertex after calling this method.
492 * @param child A pointer to the SPFVertex (which resides in the SPF tree) to
493 * be added to the list of children of "this" SPFVertex.
494 * @returns The number of children of "this" SPFVertex after the addition of
495 * the new child.
496 */
498
499 /**
500 * @brief Set the value of the VertexProcessed flag
501 *
502 * Flag to note whether vertex has been processed in stage two of
503 * SPF computation
504 * @param value boolean value to set the flag
505 */
506 void SetVertexProcessed(bool value);
507
508 /**
509 * @brief Check the value of the VertexProcessed flag
510 *
511 * Flag to note whether vertex has been processed in stage two of
512 * SPF computation
513 * @returns value of underlying flag
514 */
515 bool IsVertexProcessed() const;
516
517 /**
518 * @brief Clear the value of the VertexProcessed flag
519 *
520 * Flag to note whether vertex has been processed in stage two of
521 * SPF computation
522 */
524
525 private:
526 VertexType m_vertexType; //!< Vertex type
527 Ipv4Address m_vertexId; //!< Vertex ID
528 GlobalRoutingLSA* m_lsa; //!< Link State Advertisement
529 uint32_t m_distanceFromRoot; //!< Distance from root node
530 int32_t m_rootOif; //!< root Output Interface
531 Ipv4Address m_nextHop; //!< next hop
532 typedef std::list<NodeExit_t> ListOfNodeExit_t; //!< container of Exit nodes
533 ListOfNodeExit_t m_ecmpRootExits; //!< store the multiple root's exits for supporting ECMP
534 typedef std::list<SPFVertex*> ListOfSPFVertex_t; //!< container of SPFVertex items
535 ListOfSPFVertex_t m_parents; //!< parent list
536 ListOfSPFVertex_t m_children; //!< Children list
537 bool m_vertexProcessed; //!< Flag to note whether vertex has been processed in stage two of SPF
538 //!< computation
539
540 /**
541 * \brief Stream insertion operator.
542 *
543 * \param os the reference to the output stream
544 * \param vs a list of SPFVertex items
545 * \returns the reference to the output stream
546 */
547 friend std::ostream& operator<<(std::ostream& os, const SPFVertex::ListOfSPFVertex_t& vs);
548};
549
550/**
551 * @brief The Link State DataBase (LSDB) of the Global Route Manager.
552 *
553 * Each node in the simulation participating in global routing has a
554 * GlobalRouter interface. The primary job of this interface is to export
555 * Global Router Link State Advertisements (LSAs). These advertisements in
556 * turn contain a number of Global Router Link Records that describe the
557 * point to point links from the underlying node to other nodes (that will
558 * also export their own LSAs.
559 *
560 * This class implements a searchable database of LSAs gathered from every
561 * router in the simulation.
562 */
564{
565 public:
566 /**
567 * @brief Construct an empty Global Router Manager Link State Database.
568 *
569 * The database map composing the Link State Database is initialized in
570 * this constructor.
571 */
573
574 /**
575 * @brief Destroy an empty Global Router Manager Link State Database.
576 *
577 * The database map is walked and all of the Link State Advertisements stored
578 * in the database are freed; then the database map itself is clear ()ed to
579 * release any remaining resources.
580 */
582
583 // Delete copy constructor and assignment operator to avoid misuse
586
587 /**
588 * @brief Insert an IP address / Link State Advertisement pair into the Link
589 * State Database.
590 *
591 * The IPV4 address and the GlobalRoutingLSA given as parameters are converted
592 * to an STL pair and are inserted into the database map.
593 *
594 * @see GlobalRoutingLSA
595 * @see Ipv4Address
596 * @param addr The IP address associated with the LSA. Typically the Router
597 * ID.
598 * @param lsa A pointer to the Link State Advertisement for the router.
599 */
600 void Insert(Ipv4Address addr, GlobalRoutingLSA* lsa);
601
602 /**
603 * @brief Look up the Link State Advertisement associated with the given
604 * link state ID (address).
605 *
606 * The database map is searched for the given IPV4 address and corresponding
607 * GlobalRoutingLSA is returned.
608 *
609 * @see GlobalRoutingLSA
610 * @see Ipv4Address
611 * @param addr The IP address associated with the LSA. Typically the Router
612 * ID.
613 * @returns A pointer to the Link State Advertisement for the router specified
614 * by the IP address addr.
615 */
617 /**
618 * @brief Look up the Link State Advertisement associated with the given
619 * link state ID (address). This is a variation of the GetLSA call
620 * to allow the LSA to be found by matching addr with the LinkData field
621 * of the TransitNetwork link record.
622 *
623 * @see GetLSA
624 * @param addr The IP address associated with the LSA. Typically the Router
625 * @returns A pointer to the Link State Advertisement for the router specified
626 * by the IP address addr.
627 * ID.
628 */
630
631 /**
632 * @brief Set all LSA flags to an initialized state, for SPF computation
633 *
634 * This function walks the database and resets the status flags of all of the
635 * contained Link State Advertisements to LSA_SPF_NOT_EXPLORED. This is done
636 * prior to each SPF calculation to reset the state of the SPFVertex structures
637 * that will reference the LSAs during the calculation.
638 *
639 * @see GlobalRoutingLSA
640 * @see SPFVertex
641 */
642 void Initialize();
643
644 /**
645 * @brief Look up the External Link State Advertisement associated with the given
646 * index.
647 *
648 * The external database map is searched for the given index and corresponding
649 * GlobalRoutingLSA is returned.
650 *
651 * @see GlobalRoutingLSA
652 * @param index the index associated with the LSA.
653 * @returns A pointer to the Link State Advertisement.
654 */
655 GlobalRoutingLSA* GetExtLSA(uint32_t index) const;
656 /**
657 * @brief Get the number of External Link State Advertisements.
658 *
659 * @see GlobalRoutingLSA
660 * @returns the number of External Link State Advertisements.
661 */
662 uint32_t GetNumExtLSAs() const;
663
664 private:
665 typedef std::map<Ipv4Address, GlobalRoutingLSA*>
666 LSDBMap_t; //!< container of IPv4 addresses / Link State Advertisements
667 typedef std::pair<Ipv4Address, GlobalRoutingLSA*>
668 LSDBPair_t; //!< pair of IPv4 addresses / Link State Advertisements
669
670 LSDBMap_t m_database; //!< database of IPv4 addresses / Link State Advertisements
671 std::vector<GlobalRoutingLSA*>
672 m_extdatabase; //!< database of External Link State Advertisements
673};
674
675/**
676 * @brief A global router implementation.
677 *
678 * This singleton object can query interface each node in the system
679 * for a GlobalRouter interface. For those nodes, it fetches one or
680 * more Link State Advertisements and stores them in a local database.
681 * Then, it can compute shortest paths on a per-node basis to all routers,
682 * and finally configure each of the node's forwarding tables.
683 *
684 * The design is guided by OSPFv2 \RFC{2328} section 16.1.1 and quagga ospfd.
685 */
687{
688 public:
690 virtual ~GlobalRouteManagerImpl();
691
692 // Delete copy constructor and assignment operator to avoid misuse
695
696 /**
697 * @brief Delete all static routes on all nodes that have a
698 * GlobalRouterInterface
699 *
700 * \todo separate manually assigned static routes from static routes that
701 * the global routing code injects, and only delete the latter
702 */
703 virtual void DeleteGlobalRoutes();
704
705 /**
706 * @brief Build the routing database by gathering Link State Advertisements
707 * from each node exporting a GlobalRouter interface.
708 */
709 virtual void BuildGlobalRoutingDatabase();
710
711 /**
712 * @brief Compute routes using a Dijkstra SPF computation and populate
713 * per-node forwarding tables
714 */
715 virtual void InitializeRoutes();
716
717 /**
718 * @brief Debugging routine; allow client code to supply a pre-built LSDB
719 * @param lsdb the pre-built LSDB
720 */
722
723 /**
724 * @brief Debugging routine; call the core SPF from the unit tests
725 * @param root the root node to start calculations
726 */
728
729 private:
730 SPFVertex* m_spfroot; //!< the root node
731 GlobalRouteManagerLSDB* m_lsdb; //!< the Link State DataBase (LSDB) of the Global Route Manager
732
733 /**
734 * \brief Test if a node is a stub, from an OSPF sense.
735 *
736 * If there is only one link of type 1 or 2, then a default route
737 * can safely be added to the next-hop router and SPF does not need
738 * to be run
739 *
740 * \param root the root node
741 * \returns true if the node is a stub
742 */
743 bool CheckForStubNode(Ipv4Address root);
744
745 /**
746 * \brief Calculate the shortest path first (SPF) tree
747 *
748 * Equivalent to quagga ospf_spf_calculate
749 * \param root the root node
750 */
751 void SPFCalculate(Ipv4Address root);
752
753 /**
754 * \brief Process Stub nodes
755 *
756 * Processing logic from RFC 2328, page 166 and quagga ospf_spf_process_stubs ()
757 * stub link records will exist for point-to-point interfaces and for
758 * broadcast interfaces for which no neighboring router can be found
759 *
760 * \param v vertex to be processed
761 */
762 void SPFProcessStubs(SPFVertex* v);
763
764 /**
765 * \brief Process Autonomous Systems (AS) External LSA
766 *
767 * \param v vertex to be processed
768 * \param extlsa external LSA
769 */
771
772 /**
773 * \brief Examine the links in v's LSA and update the list of candidates with any
774 * vertices not already on the list
775 *
776 * \internal
777 *
778 * This method is derived from quagga ospf_spf_next (). See RFC2328 Section
779 * 16.1 (2) for further details.
780 *
781 * We're passed a parameter \a v that is a vertex which is already in the SPF
782 * tree. A vertex represents a router node. We also get a reference to the
783 * SPF candidate queue, which is a priority queue containing the shortest paths
784 * to the networks we know about.
785 *
786 * We examine the links in v's LSA and update the list of candidates with any
787 * vertices not already on the list. If a lower-cost path is found to a
788 * vertex already on the candidate list, store the new (lower) cost.
789 *
790 * \param v the vertex
791 * \param candidate the SPF candidate queue
792 */
793 void SPFNext(SPFVertex* v, CandidateQueue& candidate);
794
795 /**
796 * \brief Calculate nexthop from root through V (parent) to vertex W (destination)
797 * with given distance from root->W.
798 *
799 * This method is derived from quagga ospf_nexthop_calculation() 16.1.1.
800 * For now, this is greatly simplified from the quagga code
801 *
802 * \param v the parent
803 * \param w the destination
804 * \param l the link record
805 * \param distance the target distance
806 * \returns 1 on success
807 */
809 SPFVertex* w,
811 uint32_t distance);
812
813 /**
814 * \brief Adds a vertex to the list of children *in* each of its parents
815 *
816 * Derived from quagga ospf_vertex_add_parents ()
817 *
818 * This is a somewhat oddly named method (blame quagga). Although you might
819 * expect it to add a parent *to* something, it actually adds a vertex
820 * to the list of children *in* each of its parents.
821 *
822 * Given a pointer to a vertex, it links back to the vertex's parent that it
823 * already has set and adds itself to that vertex's list of children.
824 *
825 * \param v the vertex
826 */
828
829 /**
830 * \brief Search for a link between two vertices.
831 *
832 * This method is derived from quagga ospf_get_next_link ()
833 *
834 * First search the Global Router Link Records of vertex \a v for one
835 * representing a point-to point link to vertex \a w.
836 *
837 * What is done depends on prev_link. Contrary to appearances, prev_link just
838 * acts as a flag here. If prev_link is NULL, we return the first Global
839 * Router Link Record we find that describes a point-to-point link from \a v
840 * to \a w. If prev_link is not NULL, we return a Global Router Link Record
841 * representing a possible *second* link from \a v to \a w.
842 *
843 * \param v first vertex
844 * \param w second vertex
845 * \param prev_link the previous link in the list
846 * \returns the link's record
847 */
849 SPFVertex* w,
850 GlobalRoutingLinkRecord* prev_link);
851
852 /**
853 * \brief Add a host route to the routing tables
854 *
855 *
856 * This method is derived from quagga ospf_intra_add_router ()
857 *
858 * This is where we are actually going to add the host routes to the routing
859 * tables of the individual nodes.
860 *
861 * The vertex passed as a parameter has just been added to the SPF tree.
862 * This vertex must have a valid m_root_oid, corresponding to the outgoing
863 * interface on the root router of the tree that is the first hop on the path
864 * to the vertex. The vertex must also have a next hop address, corresponding
865 * to the next hop on the path to the vertex. The vertex has an m_lsa field
866 * that has some number of link records. For each point to point link record,
867 * the m_linkData is the local IP address of the link. This corresponds to
868 * a destination IP address, reachable from the root, to which we add a host
869 * route.
870 *
871 * \param v the vertex
872 *
873 */
875
876 /**
877 * \brief Add a transit to the routing tables
878 *
879 * \param v the vertex
880 */
882
883 /**
884 * \brief Add a stub to the routing tables
885 *
886 * \param l the global routing link record
887 * \param v the vertex
888 */
890
891 /**
892 * \brief Add an external route to the routing tables
893 *
894 * \param extlsa the external LSA
895 * \param v the vertex
896 */
898
899 /**
900 * \brief Return the interface number corresponding to a given IP address and mask
901 *
902 * This is a wrapper around GetInterfaceForPrefix(), but we first
903 * have to find the right node pointer to pass to that function.
904 * If no such interface is found, return -1 (note: unit test framework
905 * for routing assumes -1 to be a legal return value)
906 *
907 * \param a the target IP address
908 * \param amask the target subnet mask
909 * \return the outgoing interface number
910 */
911 int32_t FindOutgoingInterfaceId(Ipv4Address a, Ipv4Mask amask = Ipv4Mask("255.255.255.255"));
912};
913
914} // namespace ns3
915
916#endif /* GLOBAL_ROUTE_MANAGER_IMPL_H */
A Candidate Queue used in routing calculations.
A global router implementation.
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.
GlobalRouteManagerImpl & operator=(const GlobalRouteManagerImpl &)=delete
GlobalRouteManagerLSDB * m_lsdb
the Link State DataBase (LSDB) of the Global Route Manager
bool CheckForStubNode(Ipv4Address root)
Test if a node is a stub, from an OSPF sense.
void DebugUseLsdb(GlobalRouteManagerLSDB *lsdb)
Debugging routine; allow client code to supply a pre-built LSDB.
void SPFNext(SPFVertex *v, CandidateQueue &candidate)
Examine the links in v's LSA and update the list of candidates with any vertices not already on the l...
void DebugSPFCalculate(Ipv4Address root)
Debugging routine; call the core SPF from the unit tests.
void SPFIntraAddTransit(SPFVertex *v)
Add a transit to the routing tables.
int SPFNexthopCalculation(SPFVertex *v, SPFVertex *w, GlobalRoutingLinkRecord *l, uint32_t distance)
Calculate nexthop from root through V (parent) to vertex W (destination) with given distance from roo...
void SPFIntraAddStub(GlobalRoutingLinkRecord *l, SPFVertex *v)
Add a stub to the routing tables.
GlobalRouteManagerImpl(const GlobalRouteManagerImpl &)=delete
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.
GlobalRouteManagerLSDB & operator=(const GlobalRouteManagerLSDB &)=delete
std::map< Ipv4Address, GlobalRoutingLSA * > LSDBMap_t
container of IPv4 addresses / Link State Advertisements
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
GlobalRouteManagerLSDB(const GlobalRouteManagerLSDB &)=delete
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).
a Link State Advertisement (LSA) for a router, used in global routing.
Ipv4 addresses are stored in host order in this class.
Global routing protocol for IPv4 stacks.
a class to represent an Ipv4 address mask
Vertex used in shortest path first (SPF) computations.
Ipv4Address GetVertexId() const
Get the Vertex ID field of a SPFVertex object.
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.
@ VertexUnknown
Uninitialized Link Record.
void InheritAllRootExitDirections(const SPFVertex *vertex)
Inherit all root exit directions from a given vertex to 'this' vertex.
void SetDistanceFromRoot(uint32_t distance)
Set the distance from the root vertex to "this" SPFVertex object.
SPFVertex * GetChild(uint32_t n) const
Get a borrowed SPFVertex pointer to the specified child of "this" SPFVertex.
VertexType GetVertexType() const
Get the Vertex Type field of a SPFVertex object.
bool IsVertexProcessed() const
Check the value of the VertexProcessed flag.
void SetParent(SPFVertex *parent)
Set the pointer to the SPFVector that is the parent of "this" SPFVertex.
void MergeRootExitDirections(const SPFVertex *vertex)
Merge into 'this' vertex the list of exit directions from another vertex.
std::list< SPFVertex * > ListOfSPFVertex_t
container of SPFVertex items
uint32_t GetDistanceFromRoot() const
Get the distance from the root vertex to "this" SPFVertex object.
GlobalRoutingLSA * m_lsa
Link State Advertisement.
~SPFVertex()
Destroy an SPFVertex (Shortest Path First Vertex).
SPFVertex & operator=(const SPFVertex &)=delete
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.
friend std::ostream & operator<<(std::ostream &os, const SPFVertex::ListOfSPFVertex_t &vs)
Stream insertion operator.
SPFVertex(const SPFVertex &)=delete
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).
Every class exported by the ns3 library is enclosed in the ns3 namespace.
const uint32_t SPF_INFINITY
"infinite" distance between nodes