/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/*
* Copyright 2007 University of Washington
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License version 2 as
* published by the Free Software Foundation;
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*
* Authors: Craig Dowell (craigdo@ee.washington.edu)
* Tom Henderson (tomhend@u.washington.edu)
*/
#ifndef GLOBAL_ROUTE_MANAGER_IMPL_H
#define GLOBAL_ROUTE_MANAGER_IMPL_H
#include <stdint.h>
#include <list>
#include <queue>
#include <map>
#include <vector>
#include "ns3/object.h"
#include "ns3/ptr.h"
#include "ns3/ipv4-address.h"
#include "global-router-interface.h"
namespace ns3 {
const uint32_t SPF_INFINITY = 0xffffffff; //!< "infinite" distance between nodes
class CandidateQueue;
class Ipv4GlobalRouting;
/**
* @brief Vertex used in shortest path first (SPF) computations. See \RFC{2328},
* Section 16.
*
* Each router in the simulation is associated with an SPFVertex object. When
* calculating routes, each of these routers is, in turn, chosen as the "root"
* of the calculation and routes to all of the other routers are eventually
* saved in the routing tables of each of the chosen nodes. Each of these
* routers in the calculation has an associated SPFVertex.
*
* The "Root" vertex is the SPFVertex representing the router that is having
* its routing tables set. The SPFVertex objects representing other routers
* or networks in the simulation are arranged in the SPF tree. It is this
* tree that represents the Shortest Paths to the other networks.
*
* Each SPFVertex has a pointer to the Global Router Link State Advertisement
* (LSA) that its underlying router has exported. Within these LSAs are
* Global Router Link Records that describe the point to point links from the
* underlying router to other nodes (represented by other SPFVertex objects)
* in the simulation topology. The combination of the arrangement of the
* SPFVertex objects in the SPF tree, along with the details of the link
* records that connect them provide the information required to construct the
* required routes.
*/
class SPFVertex
{
public:
/**
* @brief Enumeration of the possible types of SPFVertex objects.
* @internal
*
* Currently we use VertexRouter to identify objects that represent a router
* in the simulation topology, and VertexNetwork to identify objects that
* represent a network.
*/
enum VertexType {
VertexUnknown = 0, /**< Uninitialized Link Record */
VertexRouter, /**< Vertex representing a router in the topology */
VertexNetwork /**< Vertex representing a network in the topology */
};
/**
* @brief Construct an empty ("uninitialized") SPFVertex (Shortest Path First
* Vertex).
* @internal
*
* The Vertex Type is set to VertexUnknown, the Vertex ID is set to
* 255.255.255.255, and the distance from root is set to infinity
* (UINT32_MAX). The referenced Link State Advertisement (LSA) is set to
* null as is the parent SPFVertex. The outgoing interface index is set to
* infinity, the next hop address is set to 0.0.0.0 and the list of children
* of the SPFVertex is initialized to empty.
*
* @see VertexType
*/
SPFVertex();
/**
* @brief Construct an initialized SPFVertex (Shortest Path First Vertex).
* @internal
*
* The Vertex Type is initialized to VertexRouter and the Vertex ID is found
* from the Link State ID of the Link State Advertisement (LSA) passed as a
* parameter. The Link State ID is set to the Router ID of the advertising
* router. The referenced LSA (m_lsa) is set to the given LSA. Other than
* these members, initialization is as in the default constructor.
* of the SPFVertex is initialized to empty.
*
* @see SPFVertex::SPFVertex ()
* @see VertexType
* @see GlobalRoutingLSA
* @param lsa The Link State Advertisement used for finding initial values.
*/
SPFVertex(GlobalRoutingLSA* lsa);
/**
* @brief Destroy an SPFVertex (Shortest Path First Vertex).
* @internal
*
* The children vertices of the SPFVertex are recursively deleted.
*
* @see SPFVertex::SPFVertex ()
*/
~SPFVertex();
/**
* @brief Get the Vertex Type field of a SPFVertex object.
* @internal
*
* The Vertex Type describes the kind of simulation object a given SPFVertex
* represents.
*
* @see VertexType
* @returns The VertexType of the current SPFVertex object.
*/
VertexType GetVertexType (void) const;
/**
* @brief Set the Vertex Type field of a SPFVertex object.
* @internal
*
* The Vertex Type describes the kind of simulation object a given SPFVertex
* represents.
*
* @see VertexType
* @param type The new VertexType for the current SPFVertex object.
*/
void SetVertexType (VertexType type);
/**
* @brief Get the Vertex ID field of a SPFVertex object.
* @internal
*
* The Vertex ID uniquely identifies the simulation object a given SPFVertex
* represents. Typically, this is the Router ID for SPFVertex objects
* representing routers, and comes from the Link State Advertisement of a
* router aggregated to a node in the simulation. These IDs are allocated
* automatically by the routing environment and look like IP addresses
* beginning at 0.0.0.0 and monotonically increasing as new routers are
* instantiated.
*
* @returns The Ipv4Address Vertex ID of the current SPFVertex object.
*/
Ipv4Address GetVertexId (void) const;
/**
* @brief Set the Vertex ID field of a SPFVertex object.
* @internal
*
* The Vertex ID uniquely identifies the simulation object a given SPFVertex
* represents. Typically, this is the Router ID for SPFVertex objects
* representing routers, and comes from the Link State Advertisement of a
* router aggregated to a node in the simulation. These IDs are allocated
* automatically by the routing environment and look like IP addresses
* beginning at 0.0.0.0 and monotonically increase as new routers are
* instantiated. This method is an explicit override of the automatically
* generated value.
*
* @param id The new Ipv4Address Vertex ID for the current SPFVertex object.
*/
void SetVertexId (Ipv4Address id);
/**
* @brief Get the Global Router Link State Advertisement returned by the
* Global Router represented by this SPFVertex during the route discovery
* process.
* @internal
*
* @see GlobalRouter
* @see GlobalRoutingLSA
* @see GlobalRouter::DiscoverLSAs ()
* @returns A pointer to the GlobalRoutingLSA found by the router represented
* by this SPFVertex object.
*/
GlobalRoutingLSA* GetLSA (void) const;
/**
* @brief Set the Global Router Link State Advertisement returned by the
* Global Router represented by this SPFVertex during the route discovery
* process.
* @internal
*
* @see SPFVertex::GetLSA ()
* @see GlobalRouter
* @see GlobalRoutingLSA
* @see GlobalRouter::DiscoverLSAs ()
* @warning Ownership of the LSA is transferred to the "this" SPFVertex. You
* must not delete the LSA after calling this method.
* @param lsa A pointer to the GlobalRoutingLSA.
*/
void SetLSA (GlobalRoutingLSA* lsa);
/**
* @brief Get the distance from the root vertex to "this" SPFVertex object.
* @internal
*
* Each router in the simulation is associated with an SPFVertex object. When
* calculating routes, each of these routers is, in turn, chosen as the "root"
* of the calculation and routes to all of the other routers are eventually
* saved in the routing tables of each of the chosen nodes. Each of these
* routers in the calculation has an associated SPFVertex.
*
* The "Root" vertex is then the SPFVertex representing the router that is
* having its routing tables set. The "this" SPFVertex is the vertex to which
* a route is being calculated from the root. The distance from the root that
* we're asking for is the number of hops from the root vertex to the vertex
* in question.
*
* The distance is calculated during route discovery and is stored in a
* member variable. This method simply fetches that value.
*
* @returns The distance, in hops, from the root SPFVertex to "this" SPFVertex.
*/
uint32_t GetDistanceFromRoot (void) const;
/**
* @brief Set the distance from the root vertex to "this" SPFVertex object.
* @internal
*
* Each router in the simulation is associated with an SPFVertex object. When
* calculating routes, each of these routers is, in turn, chosen as the "root"
* of the calculation and routes to all of the other routers are eventually
* saved in the routing tables of each of the chosen nodes. Each of these
* routers in the calculation has an associated SPFVertex.
*
* The "Root" vertex is then the SPFVertex representing the router that is
* having its routing tables set. The "this" SPFVertex is the vertex to which
* a route is being calculated from the root. The distance from the root that
* we're asking for is the number of hops from the root vertex to the vertex
* in question.
*
* @param distance The distance, in hops, from the root SPFVertex to "this"
* SPFVertex.
*/
void SetDistanceFromRoot (uint32_t distance);
/**
* @brief Set the IP address and outgoing interface index that should be used
* to begin forwarding packets from the root SPFVertex to "this" SPFVertex.
* @internal
*
* Each router node in the simulation is associated with an SPFVertex object.
* When calculating routes, each of these routers is, in turn, chosen as the
* "root" of the calculation and routes to all of the other routers are
* eventually saved in the routing tables of each of the chosen nodes.
*
* The "Root" vertex is then the SPFVertex representing the router that is
* having its routing tables set. The "this" SPFVertex is the vertex that
* represents the host or network to which a route is being calculated from
* the root. The IP address that we're asking for is the address on the
* remote side of a link off of the root node that should be used as the
* destination for packets along the path to "this" vertex.
*
* When initializing the root SPFVertex, the IP address used when forwarding
* packets is determined by examining the Global Router Link Records of the
* Link State Advertisement generated by the root node's GlobalRouter. This
* address is used to forward packets off of the root's network down those
* links. As other vertices / nodes are discovered which are further away
* from the root, they will be accessible down one of the paths via a link
* described by one of these Global Router Link Records.
*
* To forward packets to these hosts or networks, the root node must begin
* the forwarding process by sending the packets to a first hop router down
* an interface. This means that the first hop address and interface ID must
* be the same for all downstream SPFVertices. We call this "inheriting"
* the interface and next hop.
*
* In this method we are telling the root node which exit direction it should send
* should I send a packet to the network or host represented by 'this' SPFVertex.
*
* @see GlobalRouter
* @see GlobalRoutingLSA
* @see GlobalRoutingLinkRecord
* @param nextHop The IP address to use when forwarding packets to the host
* or network represented by "this" SPFVertex.
* @param id The interface index to use when forwarding packets to the host or
* network represented by "this" SPFVertex.
*/
void SetRootExitDirection (Ipv4Address nextHop, int32_t id = SPF_INFINITY);
typedef std::pair<Ipv4Address, int32_t> NodeExit_t; //!< IPv4 / interface container for exit nodes.
/**
* @brief Set the IP address and outgoing interface index that should be used
* to begin forwarding packets from the root SPFVertex to "this" SPFVertex.
* @internal
*
* Each router node in the simulation is associated with an SPFVertex object.
* When calculating routes, each of these routers is, in turn, chosen as the
* "root" of the calculation and routes to all of the other routers are
* eventually saved in the routing tables of each of the chosen nodes.
*
* The "Root" vertex is then the SPFVertex representing the router that is
* having its routing tables set. The "this" SPFVertex is the vertex that
* represents the host or network to which a route is being calculated from
* the root. The IP address that we're asking for is the address on the
* remote side of a link off of the root node that should be used as the
* destination for packets along the path to "this" vertex.
*
* When initializing the root SPFVertex, the IP address used when forwarding
* packets is determined by examining the Global Router Link Records of the
* Link State Advertisement generated by the root node's GlobalRouter. This
* address is used to forward packets off of the root's network down those
* links. As other vertices / nodes are discovered which are further away
* from the root, they will be accessible down one of the paths via a link
* described by one of these Global Router Link Records.
*
* To forward packets to these hosts or networks, the root node must begin
* the forwarding process by sending the packets to a first hop router down
* an interface. This means that the first hop address and interface ID must
* be the same for all downstream SPFVertices. We call this "inheriting"
* the interface and next hop.
*
* In this method we are telling the root node which exit direction it should send
* should I send a packet to the network or host represented by 'this' SPFVertex.
*
* @see GlobalRouter
* @see GlobalRoutingLSA
* @see GlobalRoutingLinkRecord
* @param exit The pair of next-hop-IP and outgoing-interface-index to use when
* forwarding packets to the host or network represented by "this" SPFVertex.
*/
void SetRootExitDirection (SPFVertex::NodeExit_t exit);
/**
* \brief Obtain a pair indicating the exit direction from the root
*
* \param i An index to a pair
* \return A pair of next-hop-IP and outgoing-interface-index for
* indicating an exit direction from the root. It is 0 if the index 'i'
* is out-of-range
*/
NodeExit_t GetRootExitDirection (uint32_t i) const;
/**
* \brief Obtain a pair indicating the exit direction from the root
*
* This method assumes there is only a single exit direction from the root.
* Error occur if this assumption is invalid.
*
* \return The pair of next-hop-IP and outgoing-interface-index for reaching
* 'this' vertex from the root
*/
NodeExit_t GetRootExitDirection () const;
/**
* \brief Merge into 'this' vertex the list of exit directions from
* another vertex
*
* This merge is necessary when ECMP are found.
*
* \param vertex From which the list of exit directions are obtain
* and are merged into 'this' vertex
*/
void MergeRootExitDirections (const SPFVertex* vertex);
/**
* \brief Inherit all root exit directions from a given vertex to 'this' vertex
* \param vertex The vertex from which all root exit directions are to be inherited
*
* After the call of this method, the original root exit directions
* in 'this' vertex are all lost.
*/
void InheritAllRootExitDirections (const SPFVertex* vertex);
/**
* \brief Get the number of exit directions from root for reaching 'this' vertex
* \return The number of exit directions from root
*/
uint32_t GetNRootExitDirections () const;
/**
* @brief Get a pointer to the SPFVector that is the parent of "this"
* SPFVertex.
* @internal
*
* Each router node in the simulation is associated with an SPFVertex object.
* When calculating routes, each of these routers is, in turn, chosen as the
* "root" of the calculation and routes to all of the other routers are
* eventually saved in the routing tables of each of the chosen nodes.
*
* The "Root" vertex is then the SPFVertex representing the router that is
* having its routing tables set and is the root of the SPF tree.
*
* This method returns a pointer to the parent node of "this" SPFVertex
* (both of which reside in that SPF tree).
*
* @param i The index to one of the parents
* @returns A pointer to the SPFVertex that is the parent of "this" SPFVertex
* in the SPF tree.
*/
SPFVertex* GetParent (uint32_t i = 0) const;
/**
* @brief Set the pointer to the SPFVector that is the parent of "this"
* SPFVertex.
* @internal
*
* Each router node in the simulation is associated with an SPFVertex object.
* When calculating routes, each of these routers is, in turn, chosen as the
* "root" of the calculation and routes to all of the other routers are
* eventually saved in the routing tables of each of the chosen nodes.
*
* The "Root" vertex is then the SPFVertex representing the router that is
* having its routing tables set and is the root of the SPF tree.
*
* This method sets the parent pointer of "this" SPFVertex (both of which
* reside in that SPF tree).
*
* @param parent A pointer to the SPFVertex that is the parent of "this"
* SPFVertex* in the SPF tree.
*/
void SetParent (SPFVertex* parent);
/**
* \brief Merge the Parent list from the v into this vertex
*
* \param v The vertex from which its list of Parent is read
* and then merged into the list of Parent of *this* vertex.
* Note that the list in v remains intact
*/
void MergeParent (const SPFVertex* v);
/**
* @brief Get the number of children of "this" SPFVertex.
* @internal
*
* Each router node in the simulation is associated with an SPFVertex object.
* When calculating routes, each of these routers is, in turn, chosen as the
* "root" of the calculation and routes to all of the other routers are
* eventually saved in the routing tables of each of the chosen nodes.
*
* The "Root" vertex is then the SPFVertex representing the router that is
* having its routing tables set and is the root of the SPF tree. Each vertex
* in the SPF tree can have a number of children that represent host or
* network routes available via that vertex.
*
* This method returns the number of children of "this" SPFVertex (which
* reside in the SPF tree).
*
* @returns The number of children of "this" SPFVertex (which reside in the
* SPF tree).
*/
uint32_t GetNChildren (void) const;
/**
* @brief Get a borrowed SPFVertex pointer to the specified child of "this"
* SPFVertex.
* @internal
*
* Each router node in the simulation is associated with an SPFVertex object.
* When calculating routes, each of these routers is, in turn, chosen as the
* "root" of the calculation and routes to all of the other routers are
* eventually saved in the routing tables of each of the chosen nodes.
*
* The "Root" vertex is then the SPFVertex representing the router that is
* having its routing tables set and is the root of the SPF tree. Each vertex
* in the SPF tree can have a number of children that represent host or
* network routes available via that vertex.
*
* This method the number of children of "this" SPFVertex (which reside in
* the SPF tree.
*
* @see SPFVertex::GetNChildren
* @param n The index (from 0 to the number of children minus 1) of the
* child SPFVertex to return.
* @warning The pointer returned by GetChild () is a borrowed pointer. You
* do not have any ownership of the underlying object and must not delete
* that object.
* @returns A pointer to the specified child SPFVertex (which resides in the
* SPF tree).
*/
SPFVertex* GetChild (uint32_t n) const;
/**
* @brief Get a borrowed SPFVertex pointer to the specified child of "this"
* SPFVertex.
* @internal
*
* Each router node in the simulation is associated with an SPFVertex object.
* When calculating routes, each of these routers is, in turn, chosen as the
* "root" of the calculation and routes to all of the other routers are
* eventually saved in the routing tables of each of the chosen nodes.
*
* The "Root" vertex is then the SPFVertex representing the router that is
* having its routing tables set and is the root of the SPF tree. Each vertex
* in the SPF tree can have a number of children that represent host or
* network routes available via that vertex.
*
* This method the number of children of "this" SPFVertex (which reside in
* the SPF tree.
*
* @see SPFVertex::GetNChildren
* @warning Ownership of the pointer added to the children of "this"
* SPFVertex is transferred to the "this" SPFVertex. You must not delete the
* (now) child SPFVertex after calling this method.
* @param child A pointer to the SPFVertex (which resides in the SPF tree) to
* be added to the list of children of "this" SPFVertex.
* @returns The number of children of "this" SPFVertex after the addition of
* the new child.
*/
uint32_t AddChild (SPFVertex* child);
/**
* @brief Set the value of the VertexProcessed flag
*
* Flag to note whether vertex has been processed in stage two of
* SPF computation
* @param value boolean value to set the flag
*/
void SetVertexProcessed (bool value);
/**
* @brief Check the value of the VertexProcessed flag
*
* Flag to note whether vertex has been processed in stage two of
* SPF computation
* @returns value of underlying flag
*/
bool IsVertexProcessed (void) const;
/**
* @brief Clear the value of the VertexProcessed flag
*
* Flag to note whether vertex has been processed in stage two of
* SPF computation
*/
void ClearVertexProcessed (void);
private:
VertexType m_vertexType; //!< Vertex type
Ipv4Address m_vertexId; //!< Vertex ID
GlobalRoutingLSA* m_lsa; //!< Link State Advertisement
uint32_t m_distanceFromRoot; //!< Distance from root node
int32_t m_rootOif; //!< root Output Interface
Ipv4Address m_nextHop; //!< next hop
typedef std::list< NodeExit_t > ListOfNodeExit_t; //!< container of Exit nodes
ListOfNodeExit_t m_ecmpRootExits; //!< store the multiple root's exits for supporting ECMP
typedef std::list<SPFVertex*> ListOfSPFVertex_t; //!< container of SPFVertexes
ListOfSPFVertex_t m_parents; //!< parent list
ListOfSPFVertex_t m_children; //!< Children list
bool m_vertexProcessed; //!< Flag to note whether vertex has been processed in stage two of SPF computation
/**
* @brief The SPFVertex copy construction is disallowed. There's no need for
* it and a compiler provided shallow copy would be wrong.
* @param v object to copy from
*/
SPFVertex (SPFVertex& v);
/**
* @brief The SPFVertex copy assignment operator is disallowed. There's no
* need for it and a compiler provided shallow copy would be wrong.
* @param v object to copy from
* @returns the copied object
*/
SPFVertex& operator= (SPFVertex& v);
/**
* \brief Stream insertion operator.
*
* \param os the reference to the output stream
* \param vs a list of SPFVertexes
* \returns the reference to the output stream
*/
friend std::ostream& operator<< (std::ostream& os, const SPFVertex::ListOfSPFVertex_t& vs);
};
/**
* @brief The Link State DataBase (LSDB) of the Global Route Manager.
*
* Each node in the simulation participating in global routing has a
* GlobalRouter interface. The primary job of this interface is to export
* Global Router Link State Advertisements (LSAs). These advertisements in
* turn contain a number of Global Router Link Records that describe the
* point to point links from the underlying node to other nodes (that will
* also export their own LSAs.
*
* This class implements a searchable database of LSAs gathered from every
* router in the simulation.
*/
class GlobalRouteManagerLSDB
{
public:
/**
* @brief Construct an empty Global Router Manager Link State Database.
* @internal
*
* The database map composing the Link State Database is initialized in
* this constructor.
*/
GlobalRouteManagerLSDB ();
/**
* @brief Destroy an empty Global Router Manager Link State Database.
* @internal
*
* The database map is walked and all of the Link State Advertisements stored
* in the database are freed; then the database map itself is clear ()ed to
* release any remaining resources.
*/
~GlobalRouteManagerLSDB ();
/**
* @brief Insert an IP address / Link State Advertisement pair into the Link
* State Database.
* @internal
*
* The IPV4 address and the GlobalRoutingLSA given as parameters are converted
* to an STL pair and are inserted into the database map.
*
* @see GlobalRoutingLSA
* @see Ipv4Address
* @param addr The IP address associated with the LSA. Typically the Router
* ID.
* @param lsa A pointer to the Link State Advertisement for the router.
*/
void Insert (Ipv4Address addr, GlobalRoutingLSA* lsa);
/**
* @brief Look up the Link State Advertisement associated with the given
* link state ID (address).
* @internal
*
* The database map is searched for the given IPV4 address and corresponding
* GlobalRoutingLSA is returned.
*
* @see GlobalRoutingLSA
* @see Ipv4Address
* @param addr The IP address associated with the LSA. Typically the Router
* ID.
* @returns A pointer to the Link State Advertisement for the router specified
* by the IP address addr.
*/
GlobalRoutingLSA* GetLSA (Ipv4Address addr) const;
/**
* @brief Look up the Link State Advertisement associated with the given
* link state ID (address). This is a variation of the GetLSA call
* to allow the LSA to be found by matching addr with the LinkData field
* of the TransitNetwork link record.
* @internal
*
* @see GetLSA
* @param addr The IP address associated with the LSA. Typically the Router
* @returns A pointer to the Link State Advertisement for the router specified
* by the IP address addr.
* ID.
*/
GlobalRoutingLSA* GetLSAByLinkData (Ipv4Address addr) const;
/**
* @brief Set all LSA flags to an initialized state, for SPF computation
* @internal
*
* This function walks the database and resets the status flags of all of the
* contained Link State Advertisements to LSA_SPF_NOT_EXPLORED. This is done
* prior to each SPF calculation to reset the state of the SPFVertex structures
* that will reference the LSAs during the calculation.
*
* @see GlobalRoutingLSA
* @see SPFVertex
*/
void Initialize ();
/**
* @brief Look up the External Link State Advertisement associated with the given
* index.
* @internal
*
* The external database map is searched for the given index and corresponding
* GlobalRoutingLSA is returned.
*
* @see GlobalRoutingLSA
* @param index the index associated with the LSA.
* @returns A pointer to the Link State Advertisement.
*/
GlobalRoutingLSA* GetExtLSA (uint32_t index) const;
/**
* @brief Get the number of External Link State Advertisements.
* @internal
*
* @see GlobalRoutingLSA
* @returns the number of External Link State Advertisements.
*/
uint32_t GetNumExtLSAs () const;
private:
typedef std::map<Ipv4Address, GlobalRoutingLSA*> LSDBMap_t; //!< container of IPv4 addresses / Link State Advertisements
typedef std::pair<Ipv4Address, GlobalRoutingLSA*> LSDBPair_t; //!< pair of IPv4 addresses / Link State Advertisements
LSDBMap_t m_database; //!< database of IPv4 addresses / Link State Advertisements
std::vector<GlobalRoutingLSA*> m_extdatabase; //!< database of External Link State Advertisements
/**
* @brief GlobalRouteManagerLSDB copy construction is disallowed. There's no
* need for it and a compiler provided shallow copy would be wrong.
* @param lsdb object to copy from
*/
GlobalRouteManagerLSDB (GlobalRouteManagerLSDB& lsdb);
/**
* @brief The SPFVertex copy assignment operator is disallowed. There's no
* need for it and a compiler provided shallow copy would be wrong.
* @param lsdb object to copy from
* @returns the copied object
*/
GlobalRouteManagerLSDB& operator= (GlobalRouteManagerLSDB& lsdb);
};
/**
* @brief A global router implementation.
*
* This singleton object can query interface each node in the system
* for a GlobalRouter interface. For those nodes, it fetches one or
* more Link State Advertisements and stores them in a local database.
* Then, it can compute shortest paths on a per-node basis to all routers,
* and finally configure each of the node's forwarding tables.
*
* The design is guided by OSPFv2 \RFC{2328} section 16.1.1 and quagga ospfd.
*/
class GlobalRouteManagerImpl
{
public:
GlobalRouteManagerImpl ();
virtual ~GlobalRouteManagerImpl ();
/**
* @brief Delete all static routes on all nodes that have a
* GlobalRouterInterface
*
* \todo separate manually assigned static routes from static routes that
* the global routing code injects, and only delete the latter
* @internal
*
*/
virtual void DeleteGlobalRoutes ();
/**
* @brief Build the routing database by gathering Link State Advertisements
* from each node exporting a GlobalRouter interface.
* @internal
*/
virtual void BuildGlobalRoutingDatabase ();
/**
* @brief Compute routes using a Dijkstra SPF computation and populate
* per-node forwarding tables
* @internal
*/
virtual void InitializeRoutes ();
/**
* @brief Debugging routine; allow client code to supply a pre-built LSDB
* @internal
*/
void DebugUseLsdb (GlobalRouteManagerLSDB*);
/**
* @brief Debugging routine; call the core SPF from the unit tests
* @internal
* @param root the root node to start calculations
*/
void DebugSPFCalculate (Ipv4Address root);
private:
/**
* @brief GlobalRouteManagerImpl copy construction is disallowed.
* There's no need for it and a compiler provided shallow copy would be
* wrong.
*
* @param srmi object to copy from
*/
GlobalRouteManagerImpl (GlobalRouteManagerImpl& srmi);
/**
* @brief Global Route Manager Implementation assignment operator is
* disallowed. There's no need for it and a compiler provided shallow copy
* would be hopelessly wrong.
*
* @param srmi object to copy from
* @returns the copied object
*/
GlobalRouteManagerImpl& operator= (GlobalRouteManagerImpl& srmi);
SPFVertex* m_spfroot; //!< the root node
GlobalRouteManagerLSDB* m_lsdb; //!< the Link State DataBase (LSDB) of the Global Route Manager
/**
* \brief Test if a node is a stub, from an OSPF sense.
*
* If there is only one link of type 1 or 2, then a default route
* can safely be added to the next-hop router and SPF does not need
* to be run
*
* \param root the root node
* \returns true if the node is a stub
*/
bool CheckForStubNode (Ipv4Address root);
/**
* \brief Calculate the shortest path first (SPF) tree
*
* Equivalent to quagga ospf_spf_calculate
* \param root the root node
*/
void SPFCalculate (Ipv4Address root);
/**
* \brief Process Stub nodes
*
* Processing logic from RFC 2328, page 166 and quagga ospf_spf_process_stubs ()
* stub link records will exist for point-to-point interfaces and for
* broadcast interfaces for which no neighboring router can be found
*
* \param v vertex to be processed
*/
void SPFProcessStubs (SPFVertex* v);
/**
* \brief Process Autonomous Systems (AS) External LSA
*
* \param v vertex to be processed
* \param extlsa external LSA
*/
void ProcessASExternals (SPFVertex* v, GlobalRoutingLSA* extlsa);
/**
* \brief Examine the links in v's LSA and update the list of candidates with any
* vertices not already on the list
*
* \internal
*
* This method is derived from quagga ospf_spf_next (). See RFC2328 Section
* 16.1 (2) for further details.
*
* We're passed a parameter \a v that is a vertex which is already in the SPF
* tree. A vertex represents a router node. We also get a reference to the
* SPF candidate queue, which is a priority queue containing the shortest paths
* to the networks we know about.
*
* We examine the links in v's LSA and update the list of candidates with any
* vertices not already on the list. If a lower-cost path is found to a
* vertex already on the candidate list, store the new (lower) cost.
*
* \param v the vertex
* \param candidate the SPF candidate queue
*/
void SPFNext (SPFVertex* v, CandidateQueue& candidate);
/**
* \brief Calculate nexthop from root through V (parent) to vertex W (destination)
* with given distance from root->W.
*
* This method is derived from quagga ospf_nexthop_calculation() 16.1.1.
* For now, this is greatly simplified from the quagga code
*
* \param v the parent
* \param w the destination
* \param l the link record
* \param distance the target distance
* \returns 1 on success
*/
int SPFNexthopCalculation (SPFVertex* v, SPFVertex* w,
GlobalRoutingLinkRecord* l, uint32_t distance);
/**
* \brief Adds a vertex to the list of children *in* each of its parents
*
* Derived from quagga ospf_vertex_add_parents ()
*
* This is a somewhat oddly named method (blame quagga). Although you might
* expect it to add a parent *to* something, it actually adds a vertex
* to the list of children *in* each of its parents.
*
* Given a pointer to a vertex, it links back to the vertex's parent that it
* already has set and adds itself to that vertex's list of children.
*
* \param v the vertex
*/
void SPFVertexAddParent (SPFVertex* v);
/**
* \brief Search for a link between two vertexes.
*
* This method is derived from quagga ospf_get_next_link ()
*
* First search the Global Router Link Records of vertex \a v for one
* representing a point-to point link to vertex \a w.
*
* What is done depends on prev_link. Contrary to appearances, prev_link just
* acts as a flag here. If prev_link is NULL, we return the first Global
* Router Link Record we find that describes a point-to-point link from \a v
* to \a w. If prev_link is not NULL, we return a Global Router Link Record
* representing a possible *second* link from \a v to \a w.
*
* \param v first vertex
* \param w second vertex
* \param prev_link the previous link in the list
* \returns the link's record
*/
GlobalRoutingLinkRecord* SPFGetNextLink (SPFVertex* v, SPFVertex* w,
GlobalRoutingLinkRecord* prev_link);
/**
* \brief Add a host route to the routing tables
*
*
* This method is derived from quagga ospf_intra_add_router ()
*
* This is where we are actually going to add the host routes to the routing
* tables of the individual nodes.
*
* The vertex passed as a parameter has just been added to the SPF tree.
* This vertex must have a valid m_root_oid, corresponding to the outgoing
* interface on the root router of the tree that is the first hop on the path
* to the vertex. The vertex must also have a next hop address, corresponding
* to the next hop on the path to the vertex. The vertex has an m_lsa field
* that has some number of link records. For each point to point link record,
* the m_linkData is the local IP address of the link. This corresponds to
* a destination IP address, reachable from the root, to which we add a host
* route.
*
* \param v the vertex
*
*/
void SPFIntraAddRouter (SPFVertex* v);
/**
* \brief Add a transit to the routing tables
*
* \param v the vertex
*/
void SPFIntraAddTransit (SPFVertex* v);
/**
* \brief Add a stub to the routing tables
*
* \param l the global routing link record
* \param v the vertex
*/
void SPFIntraAddStub (GlobalRoutingLinkRecord *l, SPFVertex* v);
/**
* \brief Add an external route to the routing tables
*
* \param extlsa the external LSA
* \param v the vertex
*/
void SPFAddASExternal (GlobalRoutingLSA *extlsa, SPFVertex *v);
/**
* \brief Return the interface number corresponding to a given IP address and mask
*
* This is a wrapper around GetInterfaceForPrefix(), but we first
* have to find the right node pointer to pass to that function.
* If no such interface is found, return -1 (note: unit test framework
* for routing assumes -1 to be a legal return value)
*
* \param a the target IP address
* \param amask the target subnet mask
* \return the outgoing interface number
*/
int32_t FindOutgoingInterfaceId (Ipv4Address a,
Ipv4Mask amask = Ipv4Mask ("255.255.255.255"));
};
} // namespace ns3
#endif /* GLOBAL_ROUTE_MANAGER_IMPL_H */