--- a/examples/simple-global-routing.cc Fri Aug 03 09:29:57 2007 -0700
+++ b/examples/simple-global-routing.cc Fri Aug 03 09:49:02 2007 -0700
@@ -56,14 +56,14 @@
#include "ns3/ascii-trace.h"
#include "ns3/pcap-trace.h"
#include "ns3/internet-node.h"
-#include "ns3/p2p-channel.h"
-#include "ns3/p2p-net-device.h"
+#include "ns3/point-to-point-channel.h"
+#include "ns3/point-to-point-net-device.h"
#include "ns3/mac-address.h"
#include "ns3/ipv4-address.h"
#include "ns3/ipv4.h"
#include "ns3/socket.h"
#include "ns3/ipv4-route.h"
-#include "ns3/p2p-topology.h"
+#include "ns3/point-to-point-topology.h"
#include "ns3/onoff-application.h"
#include "ns3/global-route-manager.h"
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/routing/global-routing/candidate-queue.cc Fri Aug 03 09:49:02 2007 -0700
@@ -0,0 +1,150 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * 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
+ */
+
+#include "ns3/debug.h"
+#include "ns3/assert.h"
+#include "candidate-queue.h"
+
+NS_DEBUG_COMPONENT_DEFINE ("CandidateQueue");
+
+namespace ns3 {
+
+CandidateQueue::CandidateQueue()
+ : m_candidates ()
+{
+ NS_DEBUG("CandidateQueue::CandidateQueue ()");
+}
+
+CandidateQueue::~CandidateQueue()
+{
+ NS_DEBUG("CandidateQueue::~CandidateQueue ()");
+ Clear ();
+}
+
+ void
+CandidateQueue::Clear (void)
+{
+ NS_DEBUG("CandidateQueue::Clear ()");
+
+ while (!m_candidates.empty ())
+ {
+ SPFVertex *p = Pop ();
+ delete p;
+ p = 0;
+ }
+}
+
+ void
+CandidateQueue::Push (SPFVertex *vNew)
+{
+ NS_DEBUG("CandidateQueue::Push (" << vNew << ")");
+
+ CandidateList_t::iterator i = m_candidates.begin ();
+
+ for (; i != m_candidates.end (); i++)
+ {
+ SPFVertex *v = *i;
+ if (vNew->GetDistanceFromRoot () < v->GetDistanceFromRoot ())
+ {
+ break;
+ }
+ }
+ m_candidates.insert(i, vNew);
+}
+
+ SPFVertex *
+CandidateQueue::Pop (void)
+{
+ NS_DEBUG("CandidateQueue::Pop ()");
+
+ if (m_candidates.empty ())
+ {
+ return 0;
+ }
+
+ SPFVertex *v = m_candidates.front ();
+ m_candidates.pop_front ();
+ return v;
+}
+
+ SPFVertex *
+CandidateQueue::Top (void) const
+{
+ NS_DEBUG("CandidateQueue::Top ()");
+
+ if (m_candidates.empty ())
+ {
+ return 0;
+ }
+
+ return m_candidates.front ();
+}
+
+ bool
+CandidateQueue::Empty (void) const
+{
+ NS_DEBUG("CandidateQueue::Empty ()");
+
+ return m_candidates.empty ();
+}
+
+ uint32_t
+CandidateQueue::Size (void) const
+{
+ NS_DEBUG("CandidateQueue::Size ()");
+
+ return m_candidates.size ();
+}
+
+ SPFVertex *
+CandidateQueue::Find (const Ipv4Address addr) const
+{
+ NS_DEBUG("CandidateQueue::Find ()");
+
+ CandidateList_t::const_iterator i = m_candidates.begin ();
+
+ for (; i != m_candidates.end (); i++)
+ {
+ SPFVertex *v = *i;
+ if (v->GetVertexId() == addr)
+ {
+ return v;
+ }
+ }
+
+ return 0;
+}
+
+ void
+CandidateQueue::Reorder (void)
+{
+ NS_DEBUG("CandidateQueue::Reorder ()");
+
+ std::list<SPFVertex*> temp;
+
+ while (!m_candidates.empty ()) {
+ SPFVertex *v = m_candidates.front ();
+ m_candidates.pop_front ();
+ temp.push_back(v);
+ }
+
+ while (!temp.empty ()) {
+ Push (temp.front ());
+ temp.pop_front ();
+ }
+}
+
+} // namespace ns3
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/routing/global-routing/candidate-queue.h Fri Aug 03 09:49:02 2007 -0700
@@ -0,0 +1,181 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * 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
+ */
+
+#ifndef CANDIDATE_QUEUE_H
+#define CANDIDATE_QUEUE_H
+
+#include <stdint.h>
+#include <list>
+#include "global-route-manager-impl.h"
+
+namespace ns3 {
+
+/**
+ * \brief A Candidate Queue used in static routing.
+ *
+ * The CandidateQueue is used in the OSPF shortest path computations. It
+ * is a priority queue used to store candidates for the shortest path to a
+ * given network.
+ *
+ * The queue holds Shortest Path First Vertex pointers and orders them
+ * according to the lowest value of the field m_distanceFromRoot. Remaining
+ * vertices are ordered according to increasing distance. This implements a
+ * priority queue.
+ *
+ * Although a STL priority_queue almost does what we want, the requirement
+ * for a Find () operation, the dynamic nature of the data and the derived
+ * requirement for a Reorder () operation led us to implement this simple
+ * enhanced priority queue.
+ */
+class CandidateQueue
+{
+public:
+/**
+ * @brief Create an empty SPF Candidate Queue.
+ * @internal
+ *
+ * @see SPFVertex
+ */
+ CandidateQueue ();
+
+/**
+ * @internal Destroy an SPF Candidate Queue and release any resources held
+ * by the contents.
+ * @internal
+ *
+ * @see SPFVertex
+ */
+ virtual ~CandidateQueue ();
+
+/**
+ * @brief Empty the Candidate Queue and release all of the resources
+ * associated with the Shortest Path First Vertex pointers in the queue.
+ * @internal
+ *
+ * @see SPFVertex
+ */
+ void Clear (void);
+
+/**
+ * @brief Push a Shortest Path First Vertex pointer onto the queue according
+ * to the priority scheme.
+ * @internal
+ *
+ * On completion, the top of the queue will hold the Shortest Path First
+ * Vertex pointer that points to a vertex having lowest value of the field
+ * m_distanceFromRoot. Remaining vertices are ordered according to
+ * increasing distance.
+ *
+ * @see SPFVertex
+ * @param vNew The Shortest Path First Vertex to add to the queue.
+ */
+ void Push (SPFVertex *vNew);
+
+/**
+ * @brief Pop the Shortest Path First Vertex pointer at the top of the queue.
+ * @internal
+ *
+ * The caller is given the responsiblity for releasing the resources
+ * associated with the vertex.
+ *
+ * @see SPFVertex
+ * @see Top ()
+ * @returns The Shortest Path First Vertex pointer at the top of the queue.
+ */
+ SPFVertex* Pop (void);
+
+/**
+ * @brief Return the Shortest Path First Vertex pointer at the top of the
+ * queue.
+ * @internal
+ *
+ * This method does not pop the SPFVertex* off of the queue, it simply
+ * returns the pointer.
+ *
+ * @see SPFVertex
+ * @see Pop ()
+ * @returns The Shortest Path First Vertex pointer at the top of the queue.
+ */
+ SPFVertex* Top (void) const;
+
+/**
+ * @brief Test the Candidate Queue to determine if it is empty.
+ * @internal
+ *
+ * @returns True if the queue is empty, false otherwise.
+ */
+ bool Empty (void) const;
+
+/**
+ * @brief Return the number of Shortest Path First Vertex pointers presently
+ * stored in the Candidate Queue.
+ * @internal
+ *
+ * @see SPFVertex
+ * @returns The number of SPFVertex* pointers in the Candidate Queue.
+ */
+ uint32_t Size (void) const;
+
+/**
+ * @brief Searches the Candidate Queue for a Shortest Path First Vertex
+ * pointer that points to a vertex having the given IP address.
+ * @internal
+ *
+ * @see SPFVertex
+ * @param addr The IP address to search for.
+ * @returns The SPFVertex* pointer corresponding to the given IP address.
+ */
+ SPFVertex* Find (const Ipv4Address addr) const;
+
+/**
+ * @brief Reorders the Candidate Queue according to the priority scheme.
+ * @internal
+ *
+ * On completion, the top of the queue will hold the Shortest Path First
+ * Vertex pointer that points to a vertex having lowest value of the field
+ * m_distanceFromRoot. Remaining vertices are ordered according to
+ * increasing distance.
+ *
+ * This method is provided in case the values of m_distanceFromRoot change
+ * during the routing calculations.
+ *
+ * @see SPFVertex
+ */
+ void Reorder (void);
+
+protected:
+ typedef std::list<SPFVertex*> CandidateList_t;
+ CandidateList_t m_candidates;
+
+private:
+/**
+ * Candidate Queue copy construction is disallowed (not implemented) to
+ * prevent the compiler from slipping in incorrect versions that don't
+ * properly deal with deep copies.
+ */
+ CandidateQueue (CandidateQueue& sr);
+
+/**
+ * Candidate Queue assignment operator is disallowed (not implemented) to
+ * prevent the compiler from slipping in incorrect versions that don't
+ * properly deal with deep copies.
+ */
+ CandidateQueue& operator= (CandidateQueue& sr);
+};
+
+} // namespace ns3
+
+#endif /* CANDIDATE_QUEUE_H */
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/routing/global-routing/global-route-manager-impl.cc Fri Aug 03 09:49:02 2007 -0700
@@ -0,0 +1,1408 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * 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
+ */
+
+#include <utility>
+#include <vector>
+#include <queue>
+#include "ns3/assert.h"
+#include "ns3/fatal-error.h"
+#include "ns3/debug.h"
+#include "ns3/node-list.h"
+#include "ns3/ipv4.h"
+#include "global-router-interface.h"
+#include "global-route-manager-impl.h"
+#include "candidate-queue.h"
+
+NS_DEBUG_COMPONENT_DEFINE ("GlobalRouteManager");
+
+namespace ns3 {
+
+// ---------------------------------------------------------------------------
+//
+// SPFVertex Implementation
+//
+// ---------------------------------------------------------------------------
+
+SPFVertex::SPFVertex () :
+ m_vertexType (VertexUnknown),
+ m_vertexId ("255.255.255.255"),
+ m_lsa (0),
+ m_distanceFromRoot (SPF_INFINITY),
+ m_rootOif (SPF_INFINITY),
+ m_nextHop ("0.0.0.0"),
+ m_parent (0),
+ m_children ()
+{
+}
+
+SPFVertex::SPFVertex (GlobalRouterLSA* lsa) :
+ m_vertexType (VertexRouter),
+ m_vertexId (lsa->GetLinkStateId ()),
+ m_lsa (lsa),
+ m_distanceFromRoot (SPF_INFINITY),
+ m_rootOif (SPF_INFINITY),
+ m_nextHop ("0.0.0.0"),
+ m_parent (0),
+ m_children ()
+{
+}
+
+SPFVertex::~SPFVertex ()
+{
+ for ( ListOfSPFVertex_t::iterator i = m_children.begin ();
+ i != m_children.end ();
+ i++)
+ {
+ SPFVertex *p = *i;
+ delete p;
+ p = 0;
+ *i = 0;
+ }
+ m_children.clear ();
+}
+
+ void
+SPFVertex::SetVertexType (SPFVertex::VertexType type)
+{
+ m_vertexType = type;
+}
+
+ SPFVertex::VertexType
+SPFVertex::GetVertexType (void) const
+{
+ return m_vertexType;
+}
+
+ void
+SPFVertex::SetVertexId (Ipv4Address id)
+{
+ m_vertexId = id;
+}
+
+ Ipv4Address
+SPFVertex::GetVertexId (void) const
+{
+ return m_vertexId;
+}
+
+ void
+SPFVertex::SetLSA (GlobalRouterLSA* lsa)
+{
+ m_lsa = lsa;
+}
+
+ GlobalRouterLSA*
+SPFVertex::GetLSA (void) const
+{
+ return m_lsa;
+}
+
+ void
+SPFVertex::SetDistanceFromRoot (uint32_t distance)
+{
+ m_distanceFromRoot = distance;
+}
+
+ uint32_t
+SPFVertex::GetDistanceFromRoot (void) const
+{
+ return m_distanceFromRoot;
+}
+
+ void
+SPFVertex::SetOutgoingInterfaceId (uint32_t id)
+{
+ m_rootOif = id;
+}
+
+ uint32_t
+SPFVertex::GetOutgoingInterfaceId (void) const
+{
+ return m_rootOif;
+}
+
+ void
+SPFVertex::SetNextHop (Ipv4Address nextHop)
+{
+ m_nextHop = nextHop;
+}
+
+ Ipv4Address
+SPFVertex::GetNextHop (void) const
+{
+ return m_nextHop;
+}
+
+ void
+SPFVertex::SetParent (SPFVertex* parent)
+{
+ m_parent = parent;
+}
+
+ SPFVertex*
+SPFVertex::GetParent (void) const
+{
+ return m_parent;
+}
+
+ uint32_t
+SPFVertex::GetNChildren (void) const
+{
+ return m_children.size ();
+}
+
+ SPFVertex*
+SPFVertex::GetChild (uint32_t n) const
+{
+ uint32_t j = 0;
+
+ for ( ListOfSPFVertex_t::const_iterator i = m_children.begin ();
+ i != m_children.end ();
+ i++, j++)
+ {
+ if (j == n)
+ {
+ return *i;
+ }
+ }
+ NS_ASSERT_MSG(false, "Index <n> out of range.");
+ return 0;
+}
+
+ uint32_t
+SPFVertex::AddChild (SPFVertex* child)
+{
+ m_children.push_back (child);
+ return m_children.size ();
+}
+
+// ---------------------------------------------------------------------------
+//
+// GlobalRouteManagerLSDB Implementation
+//
+// ---------------------------------------------------------------------------
+
+GlobalRouteManagerLSDB::GlobalRouteManagerLSDB ()
+:
+ m_database ()
+{
+ NS_DEBUG ("GlobalRouteManagerLSDB::GlobalRouteManagerLSDB ()");
+}
+
+GlobalRouteManagerLSDB::~GlobalRouteManagerLSDB ()
+{
+ NS_DEBUG ("GlobalRouteManagerLSDB::~GlobalRouteManagerLSDB ()");
+
+ LSDBMap_t::iterator i;
+ for (i= m_database.begin (); i!= m_database.end (); i++)
+ {
+ NS_DEBUG ("GlobalRouteManagerLSDB::~GlobalRouteManagerLSDB ():free LSA");
+ GlobalRouterLSA* temp = i->second;
+ delete temp;
+ }
+ NS_DEBUG ("GlobalRouteManagerLSDB::~GlobalRouteManagerLSDB (): clear map");
+ m_database.clear ();
+}
+
+ void
+GlobalRouteManagerLSDB::Initialize ()
+{
+ NS_DEBUG ("GlobalRouteManagerLSDB::Initialize ()");
+
+ LSDBMap_t::iterator i;
+ for (i= m_database.begin (); i!= m_database.end (); i++)
+ {
+ GlobalRouterLSA* temp = i->second;
+ temp->SetStatus (GlobalRouterLSA::LSA_SPF_NOT_EXPLORED);
+ }
+}
+
+ void
+GlobalRouteManagerLSDB::Insert (Ipv4Address addr, GlobalRouterLSA* lsa)
+{
+ NS_DEBUG ("GlobalRouteManagerLSDB::Insert ()");
+ m_database.insert (LSDBPair_t (addr, lsa));
+}
+
+ GlobalRouterLSA*
+GlobalRouteManagerLSDB::GetLSA (Ipv4Address addr) const
+{
+ NS_DEBUG ("GlobalRouteManagerLSDB::GetLSA ()");
+//
+// Look up an LSA by its address.
+//
+ LSDBMap_t::const_iterator i;
+ for (i= m_database.begin (); i!= m_database.end (); i++)
+ {
+ if (i->first == addr)
+ {
+ return i->second;
+ }
+ }
+ return 0;
+}
+
+// ---------------------------------------------------------------------------
+//
+// GlobalRouteManagerImpl Implementation
+//
+// ---------------------------------------------------------------------------
+
+GlobalRouteManagerImpl::GlobalRouteManagerImpl ()
+:
+ m_spfroot (0)
+{
+ NS_DEBUG ("GlobalRouteManagerImpl::GlobalRoutemanagerImpl ()");
+ m_lsdb = new GlobalRouteManagerLSDB ();
+}
+
+GlobalRouteManagerImpl::~GlobalRouteManagerImpl ()
+{
+ NS_DEBUG ("GlobalRouteManagerImpl::~GlobalRouteManagerImpl ()");
+
+ if (m_lsdb)
+ {
+ delete m_lsdb;
+ }
+}
+
+ void
+GlobalRouteManagerImpl::DebugUseLsdb (GlobalRouteManagerLSDB* lsdb)
+{
+ NS_DEBUG ("GlobalRouteManagerImpl::DebugUseLsdb ()");
+
+ if (m_lsdb)
+ {
+ delete m_lsdb;
+ }
+ m_lsdb = lsdb;
+}
+
+//
+// In order to build the routing database, we need at least one of the nodes
+// to participate as a router. Eventually we expect to provide a mechanism
+// for selecting a subset of the nodes to participate; for now, we just make
+// all nodes routers. We do this by walking the list of nodes in the system
+// and aggregating a Global Router Interface to each of the nodes.
+//
+ void
+GlobalRouteManagerImpl::SelectRouterNodes ()
+{
+ NS_DEBUG ("GlobalRouteManagerImpl::SelectRouterNodes ()");
+
+ typedef std::vector < Ptr<Node> >::iterator Iterator;
+ for (Iterator i = NodeList::Begin (); i != NodeList::End (); i++)
+ {
+ Ptr<Node> node = *i;
+ NS_DEBUG ("GlobalRouteManagerImpl::SelectRouterNodes (): "
+ "Adding GlobalRouter interface to node " <<
+ node->GetId ());
+
+ Ptr<GlobalRouter> globalRouter = Create<GlobalRouter> (node);
+ node->AddInterface (globalRouter);
+ }
+}
+
+//
+// In order to build the routing database, we need to walk the list of nodes
+// in the system and look for those that support the GlobalRouter interface.
+// These routers will export a number of Link State Advertisements (LSAs)
+// that describe the links and networks that are "adjacent" (i.e., that are
+// on the other side of a point-to-point link). We take these LSAs and put
+// add them to the Link State DataBase (LSDB) from which the routes will
+// ultimately be computed.
+//
+ void
+GlobalRouteManagerImpl::BuildGlobalRoutingDatabase ()
+{
+ NS_DEBUG ("GlobalRouteManagerImpl::BuildGlobalRoutingDatabase()");
+//
+// Walk the list of nodes looking for the GlobalRouter Interface.
+//
+ typedef std::vector < Ptr<Node> >::iterator Iterator;
+ for (Iterator i = NodeList::Begin (); i != NodeList::End (); i++)
+ {
+ Ptr<Node> node = *i;
+
+ Ptr<GlobalRouter> rtr =
+ node->QueryInterface<GlobalRouter> (GlobalRouter::iid);
+//
+// Ignore nodes that aren't participating in routing.
+//
+ if (!rtr)
+ {
+ continue;
+ }
+//
+// You must call DiscoverLSAs () before trying to use any routing info or to
+// update LSAs. DiscoverLSAs () drives the process of discovering routes in
+// the GlobalRouter. Afterward, you may use GetNumLSAs (), which is a very
+// computationally inexpensive call. If you call GetNumLSAs () before calling
+// DiscoverLSAs () will get zero as the number since no routes have been
+// found.
+//
+ uint32_t numLSAs = rtr->DiscoverLSAs ();
+ NS_DEBUG ("Discover LSAs: Found " << numLSAs << " LSAs");
+
+ for (uint32_t j = 0; j < numLSAs; ++j)
+ {
+ GlobalRouterLSA* lsa = new GlobalRouterLSA ();
+//
+// This is the call to actually fetch a Link State Advertisement from the
+// router.
+//
+ rtr->GetLSA (j, *lsa);
+ NS_DEBUG ("LSA " << j);
+ NS_DEBUG (*lsa);
+//
+// Write the newly discovered link state advertisement to the database.
+//
+ m_lsdb->Insert (lsa->GetLinkStateId (), lsa);
+ }
+ }
+}
+
+//
+// For each node that is a global router (which is determined by the presence
+// of an aggregated GlobalRouter interface), run the Dijkstra SPF calculation
+// on the database rooted at that router, and populate the node forwarding
+// tables.
+//
+// This function parallels RFC2328, Section 16.1.1, and quagga ospfd
+//
+// This calculation yields the set of intra-area routes associated
+// with an area (called hereafter Area A). A router calculates the
+// shortest-path tree using itself as the root. The formation
+// of the shortest path tree is done here in two stages. In the
+// first stage, only links between routers and transit networks are
+// considered. Using the Dijkstra algorithm, a tree is formed from
+// this subset of the link state database. In the second stage,
+// leaves are added to the tree by considering the links to stub
+// networks.
+//
+// The area's link state database is represented as a directed graph.
+// The graph's vertices are routers, transit networks and stub networks.
+//
+// The first stage of the procedure (i.e., the Dijkstra algorithm)
+// can now be summarized as follows. At each iteration of the
+// algorithm, there is a list of candidate vertices. Paths from
+// the root to these vertices have been found, but not necessarily
+// the shortest ones. However, the paths to the candidate vertex
+// that is closest to the root are guaranteed to be shortest; this
+// vertex is added to the shortest-path tree, removed from the
+// candidate list, and its adjacent vertices are examined for
+// possible addition to/modification of the candidate list. The
+// algorithm then iterates again. It terminates when the candidate
+// list becomes empty.
+//
+ void
+GlobalRouteManagerImpl::InitializeRoutes ()
+{
+ NS_DEBUG ("GlobalRouteManagerImpl::InitializeRoutes ()");
+//
+// Walk the list of nodes in the system.
+//
+ typedef std::vector < Ptr<Node> >::iterator Iterator;
+ for (Iterator i = NodeList::Begin (); i != NodeList::End (); i++)
+ {
+ Ptr<Node> node = *i;
+//
+// Look for the GlobalRouter interface that indicates that the node is
+// participating in routing.
+//
+ Ptr<GlobalRouter> rtr =
+ node->QueryInterface<GlobalRouter> (GlobalRouter::iid);
+//
+// if the node has a global router interface, then run the global routing
+// algorithms.
+//
+ if (rtr && rtr->GetNumLSAs () )
+ {
+ SPFCalculate (rtr->GetRouterId ());
+ }
+ }
+}
+
+//
+// This method is derived from quagga ospf_spf_next (). See RFC2328 Section
+// 16.1 (2) for further details.
+//
+// We're passed a parameter <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.
+//
+ void
+GlobalRouteManagerImpl::SPFNext (SPFVertex* v, CandidateQueue& candidate)
+{
+ SPFVertex* w = 0;
+ GlobalRouterLSA* w_lsa = 0;
+ uint32_t distance = 0;
+
+ NS_DEBUG ("GlobalRouteManagerImpl::SPFNext ()");
+//
+// Always true for now, since all our LSAs are RouterLSAs.
+//
+ if (v->GetVertexType () == SPFVertex::VertexRouter)
+ {
+ if (true)
+ {
+ NS_DEBUG ("SPFNext: Examining " << v->GetVertexId () << "'s " <<
+ v->GetLSA ()->GetNLinkRecords () << " link records");
+//
+// Walk the list of link records in the link state advertisement associated
+// with the "current" router (represented by vertex <v>).
+//
+ for (uint32_t i = 0; i < v->GetLSA ()->GetNLinkRecords (); ++i)
+ {
+//
+// (a) If this is a link to a stub network, examine the next link in V's LSA.
+// Links to stub networks will be considered in the second stage of the
+// shortest path calculation.
+//
+ GlobalRouterLinkRecord *l = v->GetLSA ()->GetLinkRecord (i);
+ if (l->GetLinkType () == GlobalRouterLinkRecord::StubNetwork)
+ {
+ NS_DEBUG ("SPFNext: Found a Stub record to " <<
+ l->GetLinkId ());
+ continue;
+ }
+//
+// (b) Otherwise, W is a transit vertex (router or transit network). Look up
+// the vertex W's LSA (router-LSA or network-LSA) in Area A's link state
+// database.
+//
+ if (l->GetLinkType () == GlobalRouterLinkRecord::PointToPoint)
+ {
+//
+// Lookup the link state advertisement of the new link -- we call it <w> in
+// the link state database.
+//
+ w_lsa = m_lsdb->GetLSA (l->GetLinkId ());
+ NS_ASSERT (w_lsa);
+ NS_DEBUG ("SPFNext: Found a P2P record from " <<
+ v->GetVertexId () << " to " << w_lsa->GetLinkStateId ());
+//
+// (c) If vertex W is already on the shortest-path tree, examine the next
+// link in the LSA.
+//
+// If the link is to a router that is already in the shortest path first tree
+// then we have it covered -- ignore it.
+//
+ if (w_lsa->GetStatus () ==
+ GlobalRouterLSA::LSA_SPF_IN_SPFTREE)
+ {
+ NS_DEBUG ("SPFNext: Skipping-> LSA "<<
+ w_lsa->GetLinkStateId () << " already in SPF tree");
+ continue;
+ }
+//
+// The link is to a router we haven't dealt with yet.
+//
+// (d) Calculate the link state cost D of the resulting path from the root to
+// vertex W. D is equal to the sum of the link state cost of the (already
+// calculated) shortest path to vertex V and the advertised cost of the link
+// between vertices V and W.
+//
+ distance = v->GetDistanceFromRoot () + l->GetMetric ();
+
+ NS_DEBUG ("SPFNext: Considering w_lsa " <<
+ w_lsa->GetLinkStateId ());
+
+ if (w_lsa->GetStatus () ==
+ GlobalRouterLSA::LSA_SPF_NOT_EXPLORED)
+ {
+//
+// If we haven't yet considered the link represented by <w> we have to create
+// a new SPFVertex to represent it.
+//
+ w = new SPFVertex (w_lsa);
+//
+// We need to figure out how to actually get to the new router represented
+// by <w>. This will (among other things) find the next hop address to send
+// packets destined for this network to, and also find the outbound interface
+// used to forward the packets.
+//
+ if (SPFNexthopCalculation (v, w, l, distance))
+ {
+ w_lsa->SetStatus (
+ GlobalRouterLSA::LSA_SPF_CANDIDATE);
+//
+// Push this new vertex onto the priority queue (ordered by distance from the
+// root node).
+//
+ candidate.Push (w);
+ NS_DEBUG ("SPFNext: Pushing " <<
+ w->GetVertexId () << ", parent vertexId: " <<
+ v->GetVertexId ());
+ }
+ }
+ } else if (w_lsa->GetStatus () ==
+ GlobalRouterLSA::LSA_SPF_CANDIDATE)
+ {
+//
+// We have already considered the link represented by <w>. What wse have to
+// do now is to decide if this new router represents a route with a shorter
+// distance metric.
+//
+// So, locate the vertex in the candidate queue and take a look at the
+// distance.
+ w = candidate.Find (w_lsa->GetLinkStateId ());
+ if (w->GetDistanceFromRoot () < distance)
+ {
+//
+// This is not a shorter path, so don't do anything.
+//
+ continue;
+ }
+ else if (w->GetDistanceFromRoot () == distance)
+ {
+//
+// This path is one with an equal cost. Do nothing for now -- we're not doing
+// equal-cost multipath cases yet.
+//
+ }
+ else
+ {
+//
+// this path represents a new, lower-cost path to <w> (the vertex we found in
+// the current link record of the link state advertisement of the current root
+// (vertex <v>)
+//
+// N.B. the nexthop_calculation is conditional, if it finds a valid nexthop
+// it will call spf_add_parents, which will flush the old parents
+//
+ if (SPFNexthopCalculation (v, w, l, distance))
+ {
+//
+// If we've changed the cost to get to the vertex represented by <w>, we
+// must reorder the priority queue keyed to that cost.
+//
+ candidate.Reorder ();
+ }
+ }
+ } // point-to-point
+ } // for loop
+ }
+ }
+}
+
+//
+// This method is derived from quagga ospf_next_hop_calculation() 16.1.1.
+//
+// Calculate the next hop IP address and the outgoing interface required to
+// get packets from the root through <v> (parent) to vertex <w> (destination),
+// over a given distance.
+//
+// For now, this is greatly simplified from the quagga code
+//
+ int
+GlobalRouteManagerImpl::SPFNexthopCalculation (
+ SPFVertex* v,
+ SPFVertex* w,
+ GlobalRouterLinkRecord* l,
+ uint32_t distance)
+{
+ NS_DEBUG ("GlobalRouteManagerImpl::SPFNexthopCalculation ()");
+//
+// The vertex m_spfroot is a distinguished vertex representing the node at
+// the root of the calculations. That is, it is the node for which we are
+// calculating the routes.
+//
+// There are two distinct cases for calculating the next hop information.
+// First, if we're considering a hop from the root to an "adjacent" network
+// (one that is on the other side of a point-to-point link connected to the
+// root), then we need to store the information needed to forward down that
+// link. The second case is if the network is not directly adjacent. In that
+// case we need to use the forwarding information from the vertex on the path
+// to the destination that is directly adjacent [node 1] in both cases of the
+// diagram below.
+//
+// (1) [root] -> [point-to-point] -> [node 1]
+// (2) [root] -> [point-to-point] -> [node 1] -> [point-to-point] -> [node 2]
+//
+// We call the propagation of next hop information down vertices of a path
+// "inheriting" the next hop information.
+//
+// The point-to-point link information is only useful in this calculation when
+// we are examining the root node.
+//
+ if (v == m_spfroot)
+ {
+//
+// In this case <v> is the root node, which means it is the starting point
+// for the packets forwarded by that node. This also means that the next hop
+// address of packets headed for some arbitrary off-network destination must
+// be the destination at the other end of one of the links off of the root
+// node if this root node is a router. We then need to see if this node <w>
+// is a router.
+//
+ if (w->GetVertexType () == SPFVertex::VertexRouter)
+ {
+//
+// In the case of point-to-point links, the link data field (m_linkData) of a
+// Global Router Link Record contains the local IP address. If we look at the
+// link record describing the link from the perspecive of <w> (the remote
+// node from the viewpoint of <v>) back to the root node, we can discover the
+// IP address of the router to which <v> is adjacent. This is a distinguished
+// address -- the next hop address to get from <v> to <w> and all networks
+// accessed through that path.
+//
+// SPFGetNextLink () is a little odd. used in this way it is just going to
+// return the link record describing the link from <w> to <v>. Think of it as
+// SPFGetLink.
+//
+ GlobalRouterLinkRecord *linkRemote = 0;
+ linkRemote = SPFGetNextLink (w, v, linkRemote);
+//
+// At this point, <l> is the Global Router Link Record describing the point-
+// to point link from <v> to <w> from the perspective of <v>; and <linkRemote>
+// is the Global Router Link Record describing that same link from the
+// perspective of <w> (back to <v>). Now we can just copy the next hop
+// address from the m_linkData member variable.
+//
+// The next hop member variable we put in <w> has the sense "in order to get
+// from the root node to the host represented by vertex <w>, you have to send
+// the packet to the next hop address specified in w->m_nextHop.
+//
+ w->SetNextHop(linkRemote->GetLinkData ());
+//
+// Now find the outgoing interface corresponding to the point to point link
+// from the perspective of <v> -- remember that <l> is the link "from"
+// <v> "to" <w>.
+//
+ w->SetOutgoingInterfaceId (
+ FindOutgoingInterfaceId (l->GetLinkData ()));
+
+ NS_DEBUG ("SPFNexthopCalculation: Next hop from " <<
+ v->GetVertexId () << " to " << w->GetVertexId () <<
+ " goes through next hop " << w->GetNextHop () <<
+ " via outgoing interface " << w->GetOutgoingInterfaceId ());
+ }
+ }
+ else
+ {
+//
+// If we're calculating the next hop information from a node (v) that is
+// *not* the root, then we need to "inherit" the information needed to
+// forward the packet from the vertex closer to the root. That is, we'll
+// still send packets to the next hop address of the router adjacent to the
+// root on the path toward <w>.
+//
+// Above, when we were considering the root node, we calculated the next hop
+// address and outgoing interface required to get off of the root network.
+// At this point, we are further away from the root network along one of the
+// (shortest) paths. So the next hop and outoing interface remain the same
+// (are inherited).
+//
+ w->SetNextHop (v->GetNextHop ());
+ w->SetOutgoingInterfaceId (v->GetOutgoingInterfaceId ());
+ }
+//
+// In all cases, we need valid values for the distance metric and a parent.
+//
+ w->SetDistanceFromRoot (distance);
+ w->SetParent (v);
+
+ return 1;
+}
+
+//
+// This method is derived from quagga ospf_get_next_link ()
+//
+// First search the Global Router Link Records of vertex <v> for one
+// representing a point-to point link to vertex <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 <v>
+// to <w>. If prev_link is not NULL, we return a Global Router Link Record
+// representing a possible *second* link from <v> to <w>.
+//
+// BUGBUG FIXME: This seems to be a bug. Shouldn't this function look for
+// any link records after pre_link and not just after the first?
+//
+ GlobalRouterLinkRecord*
+GlobalRouteManagerImpl::SPFGetNextLink (
+ SPFVertex* v,
+ SPFVertex* w,
+ GlobalRouterLinkRecord* prev_link)
+{
+ NS_DEBUG ("GlobalRouteManagerImpl::SPFGetNextLink ()");
+
+ bool skip = true;
+ GlobalRouterLinkRecord* l;
+//
+// If prev_link is 0, we are really looking for the first link, not the next
+// link.
+//
+ if (prev_link == 0)
+ {
+ skip = false;
+ }
+//
+// Iterate through the Global Router Link Records advertised by the vertex
+// <v> looking for records representing the point-to-point links off of this
+// vertex.
+//
+ for (uint32_t i = 0; i < v->GetLSA ()->GetNLinkRecords (); ++i)
+ {
+ l = v->GetLSA ()->GetLinkRecord (i);
+ if (l->GetLinkType () != GlobalRouterLinkRecord::PointToPoint)
+ {
+ continue;
+ }
+//
+// The link ID of a link record representing a point-to-point link is set to
+// the router ID of the neighboring router -- the router to which the link
+// connects from the perspective of <v> in this case. The vertex ID is also
+// set to the router ID (using the link state advertisement of a router node).
+// We're just checking to see if the link <l> is actually the link from <v> to
+// <w>.
+//
+ if (l->GetLinkId () == w->GetVertexId ()) {
+ NS_DEBUG ("SPFGetNextLink: Found matching link l: linkId = " <<
+ l->GetLinkId () << " linkData = " << l->GetLinkData ());
+//
+// If skip is false, don't (not too surprisingly) skip the link found -- it's
+// the one we're interested in. That's either because we didn't pass in a
+// previous link, and we're interested in the first one, or because we've
+// skipped a previous link and moved forward to the next (which is then the
+// one we want).
+//
+ if (skip == false)
+ {
+ NS_DEBUG ("SPFGetNextLink: Returning the found link");
+ return l;
+ }
+ else
+ {
+//
+// Skip is true and we've found a link from <v> to <w>. We want the next one.
+// Setting skip to false gets us the next point-to-point global router link
+// record in the LSA from <v>.
+//
+ NS_DEBUG ("SPFGetNextLink: Skipping the found link");
+ skip = false;
+ continue;
+ }
+ }
+ }
+ return 0;
+}
+
+//
+// Used for unit tests.
+//
+ void
+GlobalRouteManagerImpl::DebugSPFCalculate (Ipv4Address root)
+{
+ NS_DEBUG ("GlobalRouteManagerImpl::DebugSPFCalculate ()");
+ SPFCalculate (root);
+}
+
+// quagga ospf_spf_calculate
+ void
+GlobalRouteManagerImpl::SPFCalculate (Ipv4Address root)
+{
+ NS_DEBUG ("GlobalRouteManagerImpl::SPFCalculate (): "
+ "root = " << root);
+
+ SPFVertex *v;
+//
+// Initialize the Link State Database.
+//
+ m_lsdb->Initialize ();
+//
+// The candidate queue is a priority queue of SPFVertex objects, with the top
+// of the queue being the closest vertex in terms of distance from the root
+// of the tree. Initially, this queue is empty.
+//
+ CandidateQueue candidate;
+ NS_ASSERT(candidate.Size () == 0);
+//
+// Initialize the shortest-path tree to only contain the router doing the
+// calculation. Each router (and corresponding network) is a vertex in the
+// shortest path first (SPF) tree.
+//
+ v = new SPFVertex (m_lsdb->GetLSA (root));
+//
+// This vertex is the root of the SPF tree and it is distance 0 from the root.
+// We also mark this vertex as being in the SPF tree.
+//
+ m_spfroot= v;
+ v->SetDistanceFromRoot (0);
+ v->GetLSA ()->SetStatus (GlobalRouterLSA::LSA_SPF_IN_SPFTREE);
+
+ for (;;)
+ {
+//
+// The operations we need to do are given in the OSPF RFC which we reference
+// as we go along.
+//
+// RFC2328 16.1. (2).
+//
+// We examine the Global Router Link Records in the Link State
+// Advertisements of the current vertex. If there are any point-to-point
+// links to unexplored adjacent vertices we add them to the tree and update
+// the distance and next hop information on how to get there. We also add
+// the new vertices to the candidate queue (the priority queue ordered by
+// shortest path). If the new vertices represent shorter paths, we use them
+// and update the path cost.
+//
+ SPFNext (v, candidate);
+//
+// RFC2328 16.1. (3).
+//
+// If at this step the candidate list is empty, the shortest-path tree (of
+// transit vertices) has been completely built and this stage of the
+// procedure terminates.
+//
+ if (candidate.Size () == 0)
+ {
+ break;
+ }
+//
+// Choose the vertex belonging to the candidate list that is closest to the
+// root, and add it to the shortest-path tree (removing it from the candidate
+// list in the process).
+//
+// Recall that in the previous step, we created SPFVertex structures for each
+// of the routers found in the Global Router Link Records and added tehm to
+// the candidate list.
+//
+ v = candidate.Pop ();
+ NS_DEBUG ("SPFCalculate: Popped vertex " << v->GetVertexId ());
+//
+// Update the status field of the vertex to indicate that it is in the SPF
+// tree.
+//
+ v->GetLSA ()->SetStatus (GlobalRouterLSA::LSA_SPF_IN_SPFTREE);
+//
+// The current vertex has a parent pointer. By calling this rather oddly
+// named method (blame quagga) we add the current vertex to the list of
+// children of that parent vertex. In the next hop calculation called during
+// SPFNext, the parent pointer was set but the vertex has been orphaned up
+// to now.
+//
+ SPFVertexAddParent (v);
+//
+// Note that when there is a choice of vertices closest to the root, network
+// vertices must be chosen before router vertices in order to necessarily
+// find all equal-cost paths. We don't do this at this moment, we should add
+// the treatment above codes. -- kunihiro.
+//
+// RFC2328 16.1. (4).
+//
+// This is the method that actually adds the routes. It'll walk the list
+// of nodes in the system, looking for the node corresponding to the router
+// ID of the root of the tree -- that is the router we're building the routes
+// for. It looks for the Ipv4 interface of that node and remembers it. So
+// we are only actually adding routes to that one node at the root of the SPF
+// tree.
+//
+// We're going to pop of a pointer to every vertex in the tree except the
+// root in order of distance from the root. For each of the vertices, we call
+// SPFIntraAddRouter (). Down in SPFIntraAddRouter, we look at all of the
+// point-to-point Global Router Link Records (the links to nodes adjacent to
+// the node represented by the vertex). We add a route to the IP address
+// specified by the m_linkData field of each of those link records. This will
+// be the *local* IP address associated with the interface attached to the
+// link. We use the outbound interface and next hop information present in
+// the vertex <v> which have possibly been inherited from the root.
+//
+// To summarize, we're going to look at the node represented by <v> and loop
+// through its point-to-point links, adding a *host* route to the local IP
+// address (at the <v> side) for each of those links.
+//
+ SPFIntraAddRouter (v);
+//
+// RFC2328 16.1. (5).
+//
+// Iterate the algorithm by returning to Step 2 until there are no more
+// candidate vertices.
+//
+ }
+//
+// Second stage of SPF calculation procedure's
+// NOTYET: ospf_spf_process_stubs (area, area->spf, new_table);
+//
+// We're all done setting the routing information for the node at the root of
+// the SPF tree. Delete all of the vertices and corresponding resources. Go
+// possibly do it again for the next router.
+//
+ delete m_spfroot;
+ m_spfroot = 0;
+}
+
+//
+// XXX This should probably be a method on Ipv4
+//
+// Return the interface index corresponding to a given IP address
+//
+ uint32_t
+GlobalRouteManagerImpl::FindOutgoingInterfaceId (Ipv4Address a)
+{
+//
+// We have an IP address <a> and a vertex ID of the root of the SPF tree.
+// The question is what interface index does this address correspond to.
+// The answer is a little complicated since we have to find a pointer to
+// the node corresponding to the vertex ID, find the Ipv4 interface on that
+// node in order to iterate the interfaces and find the one corresponding to
+// the address in question.
+//
+ Ipv4Address routerId = m_spfroot->GetVertexId ();
+//
+// Walk the list of nodes in the system looking for the one corresponding to
+// the node at the root of the SPF tree. This is the node for which we are
+// building the routing table.
+//
+ std::vector<Ptr<Node> >::iterator i = NodeList::Begin ();
+ for (; i != NodeList::End (); i++)
+ {
+ Ptr<Node> node = *i;
+
+ Ptr<GlobalRouter> rtr =
+ node->QueryInterface<GlobalRouter> (GlobalRouter::iid);
+//
+// If the node doesn't have a GlobalRouter interface it can't be the one
+// we're interested in.
+//
+ if (rtr == 0)
+ {
+ continue;
+ }
+
+ if (rtr->GetRouterId () == routerId)
+ {
+//
+// This is the node we're building the routing table for. We're going to need
+// the Ipv4 interface to look for the ipv4 interface index. Since this node
+// is participating in routing IP version 4 packets, it certainly must have
+// an Ipv4 interface.
+//
+ Ptr<Ipv4> ipv4 = node->QueryInterface<Ipv4> (Ipv4::iid);
+ NS_ASSERT_MSG (ipv4,
+ "GlobalRouteManagerImpl::FindOutgoingInterfaceId (): "
+ "QI for <Ipv4> interface failed");
+//
+// Look through the interfaces on this node for one that has the IP address
+// we're looking for. If we find one, return the corresponding interface
+// index.
+//
+ for (uint32_t i = 0; i < ipv4->GetNInterfaces (); i++)
+ {
+ if (ipv4->GetAddress (i) == a)
+ {
+ NS_DEBUG (
+ "GlobalRouteManagerImpl::FindOutgoingInterfaceId (): "
+ "Interface match for " << a);
+ return i;
+ }
+ }
+ }
+ }
+//
+// Couldn't find it.
+//
+ return 0;
+}
+
+//
+// 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.
+//
+ void
+GlobalRouteManagerImpl::SPFIntraAddRouter (SPFVertex* v)
+{
+ NS_DEBUG ("GlobalRouteManagerImpl::SPFIntraAddRouter ()");
+
+ NS_ASSERT_MSG (m_spfroot,
+ "GlobalRouteManagerImpl::SPFIntraAddRouter (): Root pointer not set");
+//
+// The root of the Shortest Path First tree is the router to which we are
+// going to write the actual routing table entries. The vertex corresponding
+// to this router has a vertex ID which is the router ID of that node. We're
+// going to use this ID to discover which node it is that we're actually going
+// to update.
+//
+ Ipv4Address routerId = m_spfroot->GetVertexId ();
+
+ NS_DEBUG ("GlobalRouteManagerImpl::SPFIntraAddRouter (): "
+ "Vertex ID = " << routerId);
+//
+// We need to walk the list of nodes looking for the one that has the router
+// ID corresponding to the root vertex. This is the one we're going to write
+// the routing information to.
+//
+ std::vector<Ptr<Node> >::iterator i = NodeList::Begin ();
+ for (; i != NodeList::End (); i++)
+ {
+ Ptr<Node> node = *i;
+//
+// The router ID is accessible through the GlobalRouter interface, so we need
+// to QI for that interface. If there's no GlobalRouter interface, the node
+// in question cannot be the router we want, so we continue.
+//
+ Ptr<GlobalRouter> rtr =
+ node->QueryInterface<GlobalRouter> (GlobalRouter::iid);
+
+ if (rtr == 0)
+ {
+ NS_DEBUG ("GlobalRouteManagerImpl::SPFIntraAddRouter (): "
+ "No GlobalRouter interface on node " << node->GetId ());
+ continue;
+ }
+//
+// If the router ID of the current node is equal to the router ID of the
+// root of the SPF tree, then this node is the one for which we need to
+// write the routing tables.
+//
+ NS_DEBUG ("GlobalRouteManagerImpl::SPFIntraAddRouter (): "
+ "Considering router " << rtr->GetRouterId ());
+
+ if (rtr->GetRouterId () == routerId)
+ {
+ NS_DEBUG ("GlobalRouteManagerImpl::SPFIntraAddRouter (): "
+ "setting routes for node " << node->GetId ());
+//
+// Routing information is updated using the Ipv4 interface. We need to QI
+// for that interface. If the node is acting as an IP version 4 router, it
+// should absolutely have an Ipv4 interface.
+//
+ Ptr<Ipv4> ipv4 = node->QueryInterface<Ipv4> (Ipv4::iid);
+ NS_ASSERT_MSG (ipv4,
+ "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
+ "QI for <Ipv4> interface failed");
+//
+// Get the Global Router Link State Advertisement from the vertex we're
+// adding the routes to. The LSA will have a number of attached Global Router
+// Link Records corresponding to links off of that vertex / node. We're going
+// to be interested in the records corresponding to point-to-point links.
+//
+ GlobalRouterLSA *lsa = v->GetLSA ();
+ NS_ASSERT_MSG (lsa,
+ "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
+ "Expected valid LSA in SPFVertex* v");
+
+ uint32_t nLinkRecords = lsa->GetNLinkRecords ();
+//
+// Iterate through the link records on the vertex to which we're going to add
+// routes. To make sure we're being clear, we're going to add routing table
+// entries to the tables on the node corresping to the root of the SPF tree.
+// These entries will have routes to the IP addresses we find from looking at
+// the local side of the point-to-point links found on the node described by
+// the vertex <v>.
+//
+ for (uint32_t j = 0; j < nLinkRecords; j += 2)
+ {
+//
+// We are only concerned about point-to-point links
+//
+ GlobalRouterLinkRecord *lr = lsa->GetLinkRecord (j);
+ if (lr->GetLinkType () != GlobalRouterLinkRecord::PointToPoint)
+ {
+ continue;
+ }
+
+ NS_DEBUG ("GlobalRouteManagerImpl::SPFIntraAddRouter (): "
+ " Node " << node->GetId () <<
+ " add route to " << lr->GetLinkData () <<
+ " using next hop " << v->GetNextHop () <<
+ " via interface " << v->GetOutgoingInterfaceId ());
+//
+// Here's why we did all of that work. We're going to add a host route to the
+// host address found in the m_linkData field of the point-to-point link
+// record. In the case of a point-to-point link, this is the local IP address
+// of the node connected to the link. Each of these point-to-point links
+// will correspond to a local interface that has an IP address to which
+// the node at the root of the SPF tree can send packets. The vertex <v>
+// (corresponding to the node that has these links and interfaces) has
+// an m_nextHop address precalculated for us that is the address to which the
+// root node should send packets to be forwarded to these IP addresses.
+// Similarly, the vertex <v> has an m_rootOif (outbound interface index) to
+// which the packets should be send for forwarding.
+//
+ ipv4->AddHostRouteTo (lr->GetLinkData (), v->GetNextHop (),
+ v->GetOutgoingInterfaceId ());
+ }
+//
+// Done adding the routes for the selected node.
+//
+ return;
+ }
+ }
+}
+
+// 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.
+//
+// For now, only one parent (not doing equal-cost multipath)
+//
+ void
+GlobalRouteManagerImpl::SPFVertexAddParent (SPFVertex* v)
+{
+ v->GetParent ()->AddChild (v);
+}
+
+} // namespace ns3
+
+#ifdef RUN_SELF_TESTS
+
+// ---------------------------------------------------------------------------
+//
+// Unit Tests
+//
+// ---------------------------------------------------------------------------
+
+#include "ns3/test.h"
+
+namespace ns3 {
+
+class GlobalRouterTestNode : public Node
+{
+public:
+ GlobalRouterTestNode ();
+
+private:
+ virtual void DoAddDevice (Ptr<NetDevice> device) const {};
+ virtual TraceResolver *DoCreateTraceResolver (TraceContext const &context);
+};
+
+GlobalRouterTestNode::GlobalRouterTestNode ()
+{
+// Ptr<Ipv4L3Protocol> ipv4 = Create<Ipv4L3Protocol> (this);
+}
+
+ TraceResolver*
+GlobalRouterTestNode::DoCreateTraceResolver (TraceContext const &context)
+{
+ return 0;
+}
+
+class GlobalRouteManagerImplTest : public Test {
+public:
+ GlobalRouteManagerImplTest ();
+ virtual ~GlobalRouteManagerImplTest ();
+ virtual bool RunTests (void);
+};
+
+GlobalRouteManagerImplTest::GlobalRouteManagerImplTest ()
+ : Test ("GlobalRouteManagerImpl")
+{
+}
+
+GlobalRouteManagerImplTest::~GlobalRouteManagerImplTest ()
+{}
+
+ bool
+GlobalRouteManagerImplTest::RunTests (void)
+{
+ bool ok = true;
+
+ CandidateQueue candidate;
+
+ for (int i = 0; i < 100; ++i)
+ {
+ SPFVertex *v = new SPFVertex;
+ v->SetDistanceFromRoot (rand () % 100);
+ candidate.Push (v);
+ }
+
+ uint32_t lastDistance = 0;
+
+ for (int i = 0; i < 100; ++i)
+ {
+ SPFVertex *v = candidate.Pop ();
+ if (v->GetDistanceFromRoot () < lastDistance)
+ {
+ ok = false;
+ }
+ lastDistance = v->GetDistanceFromRoot ();
+ delete v;
+ v = 0;
+ }
+
+ // Build fake link state database; four routers (0-3), 3 point-to-point
+ // links
+ //
+ // n0
+ // \ link 0
+ // \ link 2
+ // n2 -------------------------n3
+ // /
+ // / link 1
+ // n1
+ //
+ // link0: 10.1.1.1/30, 10.1.1.2/30
+ // link1: 10.1.2.1/30, 10.1.2.2/30
+ // link2: 10.1.3.1/30, 10.1.3.2/30
+ //
+ // Router 0
+ GlobalRouterLinkRecord* lr0 = new GlobalRouterLinkRecord (
+ GlobalRouterLinkRecord::PointToPoint,
+ "0.0.0.2", // router ID 0.0.0.2
+ "10.1.1.1", // local ID
+ 1); // metric
+
+ GlobalRouterLinkRecord* lr1 = new GlobalRouterLinkRecord (
+ GlobalRouterLinkRecord::StubNetwork,
+ "10.1.1.1",
+ "255.255.255.252",
+ 1);
+
+ GlobalRouterLSA* lsa0 = new GlobalRouterLSA ();
+ lsa0->SetLinkStateId ("0.0.0.0");
+ lsa0->SetAdvertisingRouter ("0.0.0.0");
+ lsa0->AddLinkRecord (lr0);
+ lsa0->AddLinkRecord (lr1);
+
+ // Router 1
+ GlobalRouterLinkRecord* lr2 = new GlobalRouterLinkRecord (
+ GlobalRouterLinkRecord::PointToPoint,
+ "0.0.0.2",
+ "10.1.2.1",
+ 1);
+
+ GlobalRouterLinkRecord* lr3 = new GlobalRouterLinkRecord (
+ GlobalRouterLinkRecord::StubNetwork,
+ "10.1.2.1",
+ "255.255.255.252",
+ 1);
+
+ GlobalRouterLSA* lsa1 = new GlobalRouterLSA ();
+ lsa1->SetLinkStateId ("0.0.0.1");
+ lsa1->SetAdvertisingRouter ("0.0.0.1");
+ lsa1->AddLinkRecord (lr2);
+ lsa1->AddLinkRecord (lr3);
+
+ // Router 2
+ GlobalRouterLinkRecord* lr4 = new GlobalRouterLinkRecord (
+ GlobalRouterLinkRecord::PointToPoint,
+ "0.0.0.0",
+ "10.1.1.2",
+ 1);
+
+ GlobalRouterLinkRecord* lr5 = new GlobalRouterLinkRecord (
+ GlobalRouterLinkRecord::StubNetwork,
+ "10.1.1.2",
+ "255.255.255.252",
+ 1);
+
+ GlobalRouterLinkRecord* lr6 = new GlobalRouterLinkRecord (
+ GlobalRouterLinkRecord::PointToPoint,
+ "0.0.0.1",
+ "10.1.2.2",
+ 1);
+
+ GlobalRouterLinkRecord* lr7 = new GlobalRouterLinkRecord (
+ GlobalRouterLinkRecord::StubNetwork,
+ "10.1.2.2",
+ "255.255.255.252",
+ 1);
+
+ GlobalRouterLinkRecord* lr8 = new GlobalRouterLinkRecord (
+ GlobalRouterLinkRecord::PointToPoint,
+ "0.0.0.3",
+ "10.1.3.2",
+ 1);
+
+ GlobalRouterLinkRecord* lr9 = new GlobalRouterLinkRecord (
+ GlobalRouterLinkRecord::StubNetwork,
+ "10.1.3.2",
+ "255.255.255.252",
+ 1);
+
+ GlobalRouterLSA* lsa2 = new GlobalRouterLSA ();
+ lsa2->SetLinkStateId ("0.0.0.2");
+ lsa2->SetAdvertisingRouter ("0.0.0.2");
+ lsa2->AddLinkRecord (lr4);
+ lsa2->AddLinkRecord (lr5);
+ lsa2->AddLinkRecord (lr6);
+ lsa2->AddLinkRecord (lr7);
+ lsa2->AddLinkRecord (lr8);
+ lsa2->AddLinkRecord (lr9);
+
+ // Router 3
+ GlobalRouterLinkRecord* lr10 = new GlobalRouterLinkRecord (
+ GlobalRouterLinkRecord::PointToPoint,
+ "0.0.0.2",
+ "10.1.2.1",
+ 1);
+
+ GlobalRouterLinkRecord* lr11 = new GlobalRouterLinkRecord (
+ GlobalRouterLinkRecord::StubNetwork,
+ "10.1.2.1",
+ "255.255.255.252",
+ 1);
+
+ GlobalRouterLSA* lsa3 = new GlobalRouterLSA ();
+ lsa3->SetLinkStateId ("0.0.0.3");
+ lsa3->SetAdvertisingRouter ("0.0.0.3");
+ lsa3->AddLinkRecord (lr10);
+ lsa3->AddLinkRecord (lr11);
+
+ // Test the database
+ GlobalRouteManagerLSDB* srmlsdb = new GlobalRouteManagerLSDB ();
+ srmlsdb->Insert (lsa0->GetLinkStateId (), lsa0);
+ srmlsdb->Insert (lsa1->GetLinkStateId (), lsa1);
+ srmlsdb->Insert (lsa2->GetLinkStateId (), lsa2);
+ srmlsdb->Insert (lsa3->GetLinkStateId (), lsa3);
+ NS_ASSERT (lsa2 == srmlsdb->GetLSA (lsa2->GetLinkStateId ()));
+
+ // next, calculate routes based on the manually created LSDB
+ GlobalRouteManagerImpl* srm = new GlobalRouteManagerImpl ();
+ srm->DebugUseLsdb (srmlsdb); // manually add in an LSDB
+ // Note-- this will succeed without any nodes in the topology
+ // because the NodeList is empty
+ srm->DebugSPFCalculate (lsa0->GetLinkStateId ()); // node n0
+
+ // This delete clears the srm, which deletes the LSDB, which clears
+ // all of the LSAs, which each destroys the attached LinkRecords.
+ delete srm;
+
+ return ok;
+}
+
+// Instantiate this class for the unit tests
+// XXX here we should do some verification of the routes built
+static GlobalRouteManagerImplTest g_globalRouteManagerTest;
+
+} // namespace ns3
+
+#endif
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/routing/global-routing/global-route-manager-impl.h Fri Aug 03 09:49:02 2007 -0700
@@ -0,0 +1,747 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * 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
+ */
+
+#ifndef GLOBAL_ROUTE_MANAGER_IMPL_H
+#define GLOBAL_ROUTE_MANAGER_IMPL_H
+
+#include <stdint.h>
+#include <list>
+#include <queue>
+#include <map>
+#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;
+
+class CandidateQueue;
+
+/**
+ * @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 GlobalRouterLSA
+ * @param lsa The Link State Advertisement used for finding initial values.
+ */
+ SPFVertex(GlobalRouterLSA* 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 GlobalRouterLSA
+ * @see GlobalRouter::DiscoverLSAs ()
+ * @returns A pointer to the GlobalRouterLSA found by the router represented
+ * by this SPFVertex object.
+ */
+ GlobalRouterLSA* 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 GlobalRouterLSA
+ * @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 GlobalRouterLSA.
+ */
+ void SetLSA (GlobalRouterLSA* 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 Get the interface ID 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 outgoing interface that we're asking for is the interface
+ * index on the root node that should be used to start packets along the
+ * path to "this" vertex.
+ *
+ * When initializing the root SPFVertex, the interface ID is determined by
+ * examining the Global Router Link Records of the Link State Advertisement
+ * generated by the root node's GlobalRouter. These interfaces are used to
+ * forward packets off of the root's network down those links. As other
+ * vertices are discovered which are further away from the root, they will
+ * be accessible down one of the paths begun by a Global Router Link Record.
+ *
+ * To forward packets to these hosts or networks, the root node must begin
+ * the forwarding process by sending the packets to the interface of that
+ * first hop. 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, the root node is asking, "which of my local interfaces
+ * should I use to get a packet to the network or host represented by 'this'
+ * SPFVertex."
+ *
+ * @see GlobalRouter
+ * @see GlobalRouterLSA
+ * @see GlobalRouterLinkRecord
+ * @returns The interface index to use when forwarding packets to the host
+ * or network represented by "this" SPFVertex.
+ */
+ uint32_t GetOutgoingInterfaceId (void) const;
+
+/**
+ * @brief Set the interface ID 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 outgoing interface that we're asking for is the interface
+ * index on the root node that should be used to start packets along the
+ * path to "this" vertex.
+ *
+ * When initializing the root SPFVertex, the interface ID is determined by
+ * examining the Global Router Link Records of the Link State Advertisement
+ * generated by the root node's GlobalRouter. These interfaces are used to
+ * forward packets off of the root's network down those links. As other
+ * vertices are discovered which are further away from the root, they will
+ * be accessible down one of the paths begun by a Global Router Link Record.
+ *
+ * To forward packets to these hosts or networks, the root node must begin
+ * the forwarding process by sending the packets to the interface of that
+ * first hop. 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 letting the root node know which of its local
+ * interfaces it should use to get a packet to the network or host represented
+ * by "this" SPFVertex.
+ *
+ * @see GlobalRouter
+ * @see GlobalRouterLSA
+ * @see GlobalRouterLinkRecord
+ * @param id The interface index to use when forwarding packets to the host or
+ * network represented by "this" SPFVertex.
+ */
+ void SetOutgoingInterfaceId (uint32_t id);
+
+/**
+ * @brief Get the IP address 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, the root node is asking, "which router should I send a
+ * packet to in order to get that packet to the network or host represented
+ * by 'this' SPFVertex."
+ *
+ * @see GlobalRouter
+ * @see GlobalRouterLSA
+ * @see GlobalRouterLinkRecord
+ * @returns The IP address to use when forwarding packets to the host
+ * or network represented by "this" SPFVertex.
+ */
+ Ipv4Address GetNextHop (void) const;
+
+/**
+ * @brief Set the IP address 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 router it should send
+ * should I send a packet to in order to get that packet to the network or
+ * host represented by 'this' SPFVertex."
+ *
+ * @see GlobalRouter
+ * @see GlobalRouterLSA
+ * @see GlobalRouterLinkRecord
+ * @param nextHop The IP address to use when forwarding packets to the host
+ * or network represented by "this" SPFVertex.
+ */
+ void SetNextHop (Ipv4Address nextHop);
+
+/**
+ * @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).
+ *
+ * @returns A pointer to the SPFVertex that is the parent of "this" SPFVertex
+ * in the SPF tree.
+ */
+ SPFVertex* GetParent (void) 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 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);
+
+private:
+ VertexType m_vertexType;
+ Ipv4Address m_vertexId;
+ GlobalRouterLSA* m_lsa;
+ uint32_t m_distanceFromRoot;
+ uint32_t m_rootOif;
+ Ipv4Address m_nextHop;
+ SPFVertex* m_parent;
+ typedef std::list<SPFVertex*> ListOfSPFVertex_t;
+ ListOfSPFVertex_t m_children;
+
+/**
+ * @brief The SPFVertex copy construction is disallowed. There's no need for
+ * it and a compiler provided shallow copy would be wrong.
+ */
+ 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.
+ */
+ SPFVertex& operator= (SPFVertex& v);
+};
+
+/**
+ * @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 GlobalRouterLSA given as parameters are converted
+ * to an STL pair and are inserted into the database map.
+ *
+ * @see GlobalRouterLSA
+ * @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, GlobalRouterLSA* lsa);
+
+/**
+ * @brief Look up the Link State Advertisement associated with the given
+ * IP Address.
+ * @internal
+ *
+ * The database map is searched for the given IPV4 address and corresponding
+ * GlobalRouterLSA is returned.
+ *
+ * @see GlobalRouterLSA
+ * @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.
+ */
+ GlobalRouterLSA* GetLSA (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 GlobalRouterLSA
+ * @see SPFVertex
+ */
+ void Initialize ();
+
+private:
+ typedef std::map<Ipv4Address, GlobalRouterLSA*> LSDBMap_t;
+ typedef std::pair<Ipv4Address, GlobalRouterLSA*> LSDBPair_t;
+
+ LSDBMap_t m_database;
+/**
+ * @brief GlobalRouteManagerLSDB copy construction is disallowed. There's no
+ * need for it and a compiler provided shallow copy would be wrong.
+ */
+ 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.
+ */
+ 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 Select which nodes in the system are to be router nodes and
+ * aggregate the appropriate interfaces onto those nodes.
+ * @internal
+ *
+ */
+ virtual void SelectRouterNodes ();
+
+/**
+ * @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
+ */
+ 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.
+ */
+ 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.
+ */
+ GlobalRouteManagerImpl& operator= (GlobalRouteManagerImpl& srmi);
+
+ SPFVertex* m_spfroot;
+ GlobalRouteManagerLSDB* m_lsdb;
+ void SPFCalculate (Ipv4Address root);
+ void SPFNext (SPFVertex*, CandidateQueue&);
+ int SPFNexthopCalculation (SPFVertex* v, SPFVertex* w,
+ GlobalRouterLinkRecord* l, uint32_t distance);
+ void SPFVertexAddParent (SPFVertex* v);
+ GlobalRouterLinkRecord* SPFGetNextLink (SPFVertex* v, SPFVertex* w,
+ GlobalRouterLinkRecord* prev_link);
+ void SPFIntraAddRouter (SPFVertex* v);
+ uint32_t FindOutgoingInterfaceId (Ipv4Address a);
+};
+
+} // namespace ns3
+
+#endif /* GLOBAL_ROUTE_MANAGER_IMPL_H */
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/routing/global-routing/global-route-manager.cc Fri Aug 03 09:49:02 2007 -0700
@@ -0,0 +1,68 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * 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
+ */
+
+#include "ns3/assert.h"
+#include "ns3/debug.h"
+#include "ns3/simulation-singleton.h"
+#include "global-route-manager.h"
+#include "global-route-manager-impl.h"
+
+namespace ns3 {
+
+// ---------------------------------------------------------------------------
+//
+// GlobalRouteManager Implementation
+//
+// ---------------------------------------------------------------------------
+
+ void
+GlobalRouteManager::PopulateRoutingTables ()
+{
+ SelectRouterNodes ();
+ BuildGlobalRoutingDatabase ();
+ InitializeRoutes ();
+}
+
+ void
+GlobalRouteManager::SelectRouterNodes ()
+{
+ SimulationSingleton<GlobalRouteManagerImpl>::Get ()->
+ SelectRouterNodes ();
+}
+
+ void
+GlobalRouteManager::BuildGlobalRoutingDatabase ()
+{
+ SimulationSingleton<GlobalRouteManagerImpl>::Get ()->
+ BuildGlobalRoutingDatabase ();
+}
+
+ void
+GlobalRouteManager::InitializeRoutes ()
+{
+ SimulationSingleton<GlobalRouteManagerImpl>::Get ()->
+ InitializeRoutes ();
+}
+
+ uint32_t
+GlobalRouteManager::AllocateRouterId ()
+{
+ static uint32_t routerId = 0;
+ return routerId++;
+}
+
+
+} // namespace ns3
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/routing/global-routing/global-route-manager.h Fri Aug 03 09:49:02 2007 -0700
@@ -0,0 +1,93 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * 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
+ */
+
+#ifndef GLOBAL_ROUTE_MANAGER_H
+#define GLOBAL_ROUTE_MANAGER_H
+
+namespace ns3 {
+
+/**
+ * @brief A global global router
+ *
+ * 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 GlobalRouteManager
+{
+public:
+/**
+ * @brief Build a routing database and initialize the routing tables of
+ * the nodes in the simulation.
+ *
+ * All this function does is call BuildGlobalRoutingDatabase () and
+ * InitializeRoutes ().
+ *
+ * @see BuildGlobalRoutingDatabase ();
+ * @see InitializeRoutes ();
+ */
+ static void PopulateRoutingTables ();
+
+/**
+ * @brief Allocate a 32-bit router ID from monotonically increasing counter.
+ */
+ static uint32_t AllocateRouterId ();
+
+private:
+/**
+ * @brief Select which nodes in the system are to be router nodes and
+ * aggregate the appropriate interfaces onto those nodes.
+ * @internal
+ *
+ */
+ static void SelectRouterNodes ();
+
+/**
+ * @brief Build the routing database by gathering Link State Advertisements
+ * from each node exporting a GlobalRouter interface.
+ * @internal
+ *
+ */
+ static void BuildGlobalRoutingDatabase ();
+
+/**
+ * @brief Compute routes using a Dijkstra SPF computation and populate
+ * per-node forwarding tables
+ * @internal
+ */
+ static void InitializeRoutes ();
+
+/**
+ * @brief Global Route Manager copy construction is disallowed. There's no
+ * need for it and a compiler provided shallow copy would be wrong.
+ *
+ */
+ GlobalRouteManager (GlobalRouteManager& srm);
+
+/**
+ * @brief Global Router copy assignment operator is disallowed. There's no
+ * need for it and a compiler provided shallow copy would be wrong.
+ */
+ GlobalRouteManager& operator= (GlobalRouteManager& srm);
+};
+
+} // namespace ns3
+
+#endif /* GLOBAL_ROUTE_MANAGER_H */
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/routing/global-routing/global-router-interface.cc Fri Aug 03 09:49:02 2007 -0700
@@ -0,0 +1,588 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * 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
+ */
+
+#include "ns3/debug.h"
+#include "ns3/assert.h"
+#include "ns3/channel.h"
+#include "ns3/net-device.h"
+#include "ns3/internet-node.h"
+#include "ns3/ipv4.h"
+#include "global-router-interface.h"
+
+NS_DEBUG_COMPONENT_DEFINE ("GlobalRouter");
+
+namespace ns3 {
+
+// ---------------------------------------------------------------------------
+//
+// GlobalRouterLinkRecord Implementation
+//
+// ---------------------------------------------------------------------------
+
+GlobalRouterLinkRecord::GlobalRouterLinkRecord ()
+:
+ m_linkId ("0.0.0.0"),
+ m_linkData ("0.0.0.0"),
+ m_linkType (Unknown),
+ m_metric (0)
+{
+ NS_DEBUG("GlobalRouterLinkRecord::GlobalRouterLinkRecord ()");
+}
+
+GlobalRouterLinkRecord::GlobalRouterLinkRecord (
+ LinkType linkType,
+ Ipv4Address linkId,
+ Ipv4Address linkData,
+ uint32_t metric)
+:
+ m_linkId (linkId),
+ m_linkData (linkData),
+ m_linkType (linkType),
+ m_metric (metric)
+{
+ NS_DEBUG("GlobalRouterLinkRecord::GlobalRouterLinkRecord (" <<
+ linkType << ", " << linkId << ", " << linkData << ", " << metric << ")");
+}
+
+GlobalRouterLinkRecord::~GlobalRouterLinkRecord ()
+{
+ NS_DEBUG("GlobalRouterLinkRecord::~GlobalRouterLinkRecord ()");
+}
+
+ Ipv4Address
+GlobalRouterLinkRecord::GetLinkId (void) const
+{
+ NS_DEBUG("GlobalRouterLinkRecord::GetLinkId ()");
+ return m_linkId;
+}
+
+ void
+GlobalRouterLinkRecord::SetLinkId (Ipv4Address addr)
+{
+ NS_DEBUG("GlobalRouterLinkRecord::SetLinkId ()");
+ m_linkId = addr;
+}
+
+ Ipv4Address
+GlobalRouterLinkRecord::GetLinkData (void) const
+{
+ NS_DEBUG("GlobalRouterLinkRecord::GetLinkData ()");
+ return m_linkData;
+}
+
+ void
+GlobalRouterLinkRecord::SetLinkData (Ipv4Address addr)
+{
+ NS_DEBUG("GlobalRouterLinkRecord::SetLinkData ()");
+ m_linkData = addr;
+}
+
+ GlobalRouterLinkRecord::LinkType
+GlobalRouterLinkRecord::GetLinkType (void) const
+{
+ NS_DEBUG("GlobalRouterLinkRecord::GetLinkType ()");
+ return m_linkType;
+}
+
+ void
+GlobalRouterLinkRecord::SetLinkType (
+ GlobalRouterLinkRecord::LinkType linkType)
+{
+ NS_DEBUG("GlobalRouterLinkRecord::SetLinkType ()");
+ m_linkType = linkType;
+}
+
+ uint32_t
+GlobalRouterLinkRecord::GetMetric (void) const
+{
+ NS_DEBUG("GlobalRouterLinkRecord::GetMetric ()");
+ return m_metric;
+}
+
+ void
+GlobalRouterLinkRecord::SetMetric (uint32_t metric)
+{
+ NS_DEBUG("GlobalRouterLinkRecord::SetMetric ()");
+ m_metric = metric;
+}
+
+// ---------------------------------------------------------------------------
+//
+// GlobalRouterLSA Implementation
+//
+// ---------------------------------------------------------------------------
+
+GlobalRouterLSA::GlobalRouterLSA()
+ :
+ m_linkStateId("0.0.0.0"),
+ m_advertisingRtr("0.0.0.0"),
+ m_linkRecords(),
+ m_status(GlobalRouterLSA::LSA_SPF_NOT_EXPLORED)
+{
+ NS_DEBUG("GlobalRouterLSA::GlobalRouterLSA ()");
+}
+
+GlobalRouterLSA::GlobalRouterLSA (
+ GlobalRouterLSA::SPFStatus status,
+ Ipv4Address linkStateId,
+ Ipv4Address advertisingRtr)
+:
+ m_linkStateId(linkStateId),
+ m_advertisingRtr(advertisingRtr),
+ m_linkRecords(),
+ m_status(status)
+{
+ NS_DEBUG("GlobalRouterLSA::GlobalRouterLSA (" << status << ", " <<
+ linkStateId << ", " << advertisingRtr << ")");
+}
+
+GlobalRouterLSA::GlobalRouterLSA (GlobalRouterLSA& lsa)
+ : m_linkStateId(lsa.m_linkStateId), m_advertisingRtr(lsa.m_advertisingRtr),
+ m_status(lsa.m_status)
+{
+ NS_ASSERT_MSG(IsEmpty(),
+ "GlobalRouterLSA::GlobalRouterLSA (): Non-empty LSA in constructor");
+ CopyLinkRecords (lsa);
+}
+
+ GlobalRouterLSA&
+GlobalRouterLSA::operator= (const GlobalRouterLSA& lsa)
+{
+ m_linkStateId = lsa.m_linkStateId;
+ m_advertisingRtr = lsa.m_advertisingRtr;
+ m_status = lsa.m_status;
+
+ ClearLinkRecords ();
+ CopyLinkRecords (lsa);
+ return *this;
+}
+
+ void
+GlobalRouterLSA::CopyLinkRecords (const GlobalRouterLSA& lsa)
+{
+ for (ListOfLinkRecords_t::const_iterator i = lsa.m_linkRecords.begin ();
+ i != lsa.m_linkRecords.end ();
+ i++)
+ {
+ GlobalRouterLinkRecord *pSrc = *i;
+ GlobalRouterLinkRecord *pDst = new GlobalRouterLinkRecord;
+
+ pDst->SetLinkType (pSrc->GetLinkType ());
+ pDst->SetLinkId (pSrc->GetLinkId ());
+ pDst->SetLinkData (pSrc->GetLinkData ());
+
+ m_linkRecords.push_back(pDst);
+ pDst = 0;
+ }
+}
+
+GlobalRouterLSA::~GlobalRouterLSA()
+{
+ NS_DEBUG("GlobalRouterLSA::~GlobalRouterLSA ()");
+ ClearLinkRecords ();
+}
+
+ void
+GlobalRouterLSA::ClearLinkRecords(void)
+{
+ for ( ListOfLinkRecords_t::iterator i = m_linkRecords.begin ();
+ i != m_linkRecords.end ();
+ i++)
+ {
+ NS_DEBUG("GlobalRouterLSA::ClearLinkRecords (): free link record");
+
+ GlobalRouterLinkRecord *p = *i;
+ delete p;
+ p = 0;
+
+ *i = 0;
+ }
+ NS_DEBUG("GlobalRouterLSA::ClearLinkRecords(): clear list");
+ m_linkRecords.clear();
+}
+
+ uint32_t
+GlobalRouterLSA::AddLinkRecord (GlobalRouterLinkRecord* lr)
+{
+ m_linkRecords.push_back (lr);
+ return m_linkRecords.size ();
+}
+
+ uint32_t
+GlobalRouterLSA::GetNLinkRecords (void) const
+{
+ return m_linkRecords.size ();
+}
+
+ GlobalRouterLinkRecord *
+GlobalRouterLSA::GetLinkRecord (uint32_t n) const
+{
+ uint32_t j = 0;
+ for ( ListOfLinkRecords_t::const_iterator i = m_linkRecords.begin ();
+ i != m_linkRecords.end ();
+ i++, j++)
+ {
+ if (j == n)
+ {
+ return *i;
+ }
+ }
+ NS_ASSERT_MSG(false, "GlobalRouterLSA::GetLinkRecord (): invalid index");
+ return 0;
+}
+
+ bool
+GlobalRouterLSA::IsEmpty (void) const
+{
+ return m_linkRecords.size () == 0;
+}
+
+ Ipv4Address
+GlobalRouterLSA::GetLinkStateId (void) const
+{
+ return m_linkStateId;
+}
+
+ void
+GlobalRouterLSA::SetLinkStateId (Ipv4Address addr)
+{
+ m_linkStateId = addr;
+}
+
+ Ipv4Address
+GlobalRouterLSA::GetAdvertisingRouter (void) const
+{
+ return m_advertisingRtr;
+}
+
+ void
+GlobalRouterLSA::SetAdvertisingRouter (Ipv4Address addr)
+{
+ m_advertisingRtr = addr;
+}
+
+ GlobalRouterLSA::SPFStatus
+GlobalRouterLSA::GetStatus (void) const
+{
+ return m_status;
+}
+
+ void
+GlobalRouterLSA::SetStatus (GlobalRouterLSA::SPFStatus status)
+{
+ m_status = status;
+}
+
+ void
+GlobalRouterLSA::Print (std::ostream &os) const
+{
+ os << "m_linkStateId = " << m_linkStateId << std::endl <<
+ "m_advertisingRtr = " << m_advertisingRtr << std::endl;
+
+ for ( ListOfLinkRecords_t::const_iterator i = m_linkRecords.begin ();
+ i != m_linkRecords.end ();
+ i++)
+ {
+ GlobalRouterLinkRecord *p = *i;
+ os << "----------" << std::endl;
+ os << "m_linkId = " << p->GetLinkId () << std::endl;
+ os << "m_linkData = " << p->GetLinkData () << std::endl;
+ }
+}
+
+std::ostream& operator<< (std::ostream& os, GlobalRouterLSA& lsa)
+{
+ lsa.Print (os);
+ return os;
+}
+
+// ---------------------------------------------------------------------------
+//
+// GlobalRouter Implementation
+//
+// ---------------------------------------------------------------------------
+
+const InterfaceId GlobalRouter::iid =
+ MakeInterfaceId ("GlobalRouter", Object::iid);
+
+GlobalRouter::GlobalRouter (Ptr<Node> node)
+ : m_node(node), m_LSAs()
+{
+ NS_DEBUG("GlobalRouter::GlobalRouter ()");
+ SetInterfaceId (GlobalRouter::iid);
+ m_routerId.Set(GlobalRouteManager::AllocateRouterId ());
+}
+
+GlobalRouter::~GlobalRouter ()
+{
+ NS_DEBUG("GlobalRouter::~GlobalRouter ()");
+ ClearLSAs();
+}
+
+ void
+GlobalRouter::ClearLSAs ()
+{
+ NS_DEBUG("GlobalRouter::ClearLSAs ()");
+
+ for ( ListOfLSAs_t::iterator i = m_LSAs.begin ();
+ i != m_LSAs.end ();
+ i++)
+ {
+ NS_DEBUG("GlobalRouter::ClearLSAs (): free LSA");
+
+ GlobalRouterLSA *p = *i;
+ delete p;
+ p = 0;
+
+ *i = 0;
+ }
+ NS_DEBUG("GlobalRouter::ClearLSAs (): clear list");
+ m_LSAs.clear();
+}
+
+ Ipv4Address
+GlobalRouter::GetRouterId (void) const
+{
+ return m_routerId;
+}
+
+//
+// Go out and discover any adjacent routers and build the Link State
+// Advertisements that reflect them and their associated networks.
+//
+ uint32_t
+GlobalRouter::DiscoverLSAs (void)
+{
+ NS_DEBUG("GlobalRouter::DiscoverLSAs ()");
+ NS_ASSERT_MSG(m_node,
+ "GlobalRouter::DiscoverLSAs (): <Node> interface not set");
+
+ ClearLSAs ();
+//
+// We're aggregated to a node. We need to ask the node for a pointer to its
+// Ipv4 interface. This is where the information regarding the attached
+// interfaces lives.
+//
+ Ptr<Ipv4> ipv4Local = m_node->QueryInterface<Ipv4> (Ipv4::iid);
+ NS_ASSERT_MSG(ipv4Local,
+ "GlobalRouter::DiscoverLSAs (): QI for <Ipv4> interface failed");
+//
+// We are, for now at least, only going to report RouterLSAs in this method.
+// What this means is that there is going to be one advertisement with some
+// number of link records. This means that GetNumLSAs will actually always
+// return exactly one.
+//
+ GlobalRouterLSA *pLSA = new GlobalRouterLSA;
+ pLSA->SetLinkStateId (m_routerId);
+ pLSA->SetAdvertisingRouter (m_routerId);
+ pLSA->SetStatus (GlobalRouterLSA::LSA_SPF_NOT_EXPLORED);
+//
+// We need to ask the node for the number of net devices attached. This isn't
+// necessarily equal to the number of links to adjacent nodes (other routers)
+// as the number of devices may include those for stub networks (e.g.,
+// ethernets, etc.). So we have to walk through the list of net devices and
+// pay attention to those that are directly connected to another router through
+// a point-to-point channel.
+//
+ uint32_t numDevices = m_node->GetNDevices();
+ NS_DEBUG("GlobalRouter::DiscoverLSAs (): numDevices = " << numDevices);
+//
+// Loop through the devices looking for those connected to a point-to-point
+// channel.
+//
+ for (uint32_t i = 0; i < numDevices; ++i)
+ {
+ Ptr<NetDevice> ndLocal = m_node->GetDevice(i);
+
+ if (!ndLocal->IsPointToPoint ())
+ {
+ NS_DEBUG("GlobalRouter::DiscoverLSAs (): non-point-to-point device");
+ continue;
+ }
+
+ NS_DEBUG("GlobalRouter::DiscoverLSAs (): Point-to-point device");
+//
+// Now, we have to find the Ipv4 interface whose netdevice is the one we
+// just found. This is still the IP on the local side of the channel. There
+// is a function to do this used down in the guts of the stack, but it's not
+// exported so we had to whip up an equivalent.
+//
+ uint32_t ifIndexLocal = FindIfIndexForDevice(m_node, ndLocal);
+//
+// Now that we have the Ipv4 interface index, we can get the address and mask
+// we need.
+//
+ Ipv4Address addrLocal = ipv4Local->GetAddress(ifIndexLocal);
+ Ipv4Mask maskLocal = ipv4Local->GetNetworkMask(ifIndexLocal);
+ NS_DEBUG("Working with local address " << addrLocal);
+//
+// Now, we're going to walk over to the remote net device on the other end of
+// the point-to-point channel we now know we have. This is where our adjacent
+// router (to use OSPF lingo) is running.
+//
+ Ptr<Channel> ch = ndLocal->GetChannel();
+ Ptr<NetDevice> ndRemote = GetAdjacent(ndLocal, ch);
+//
+// The adjacent net device is aggregated to a node. We need to ask that net
+// device for its node, then ask that node for its Ipv4 interface.
+//
+ Ptr<Node> nodeRemote = ndRemote->GetNode();
+ Ptr<Ipv4> ipv4Remote = nodeRemote->QueryInterface<Ipv4> (Ipv4::iid);
+ NS_ASSERT_MSG(ipv4Remote,
+ "GlobalRouter::DiscoverLSAs (): QI for remote <Ipv4> failed");
+//
+// Per the OSPF spec, we're going to need the remote router ID, so we might as
+// well get it now.
+//
+ Ptr<GlobalRouter> srRemote =
+ nodeRemote->QueryInterface<GlobalRouter> (GlobalRouter::iid);
+ NS_ASSERT_MSG(srRemote,
+ "GlobalRouter::DiscoverLSAs (): QI for remote <GlobalRouter> failed");
+ Ipv4Address rtrIdRemote = srRemote->GetRouterId();
+ NS_DEBUG("Working with remote router " << rtrIdRemote);
+//
+// Now, just like we did above, we need to get the IP interface index for the
+// net device on the other end of the point-to-point channel.
+//
+ uint32_t ifIndexRemote = FindIfIndexForDevice(nodeRemote, ndRemote);
+//
+// Now that we have the Ipv4 interface, we can get the (remote) address and
+// mask we need.
+//
+ Ipv4Address addrRemote = ipv4Remote->GetAddress(ifIndexRemote);
+ Ipv4Mask maskRemote = ipv4Remote->GetNetworkMask(ifIndexRemote);
+ NS_DEBUG("Working with remote address " << addrRemote);
+//
+// Now we can fill out the link records for this link. There are always two
+// link records; the first is a point-to-point record describing the link and
+// the second is a stub network record with the network number.
+//
+ GlobalRouterLinkRecord *plr = new GlobalRouterLinkRecord;
+ plr->SetLinkType (GlobalRouterLinkRecord::PointToPoint);
+ plr->SetLinkId (rtrIdRemote);
+ plr->SetLinkData (addrLocal);
+ pLSA->AddLinkRecord(plr);
+ plr = 0;
+
+ plr = new GlobalRouterLinkRecord;
+ plr->SetLinkType (GlobalRouterLinkRecord::StubNetwork);
+ plr->SetLinkId (addrRemote);
+ plr->SetLinkData (Ipv4Address(maskRemote.GetHostOrder())); // Frown
+ pLSA->AddLinkRecord(plr);
+ plr = 0;
+ }
+//
+// The LSA goes on a list of LSAs in case we want to begin exporting other
+// kinds of advertisements (than Router LSAs).
+ m_LSAs.push_back (pLSA);
+ NS_DEBUG(*pLSA);
+ return m_LSAs.size ();
+}
+
+ uint32_t
+GlobalRouter::GetNumLSAs (void) const
+{
+ NS_DEBUG("GlobalRouter::GetNumLSAs ()");
+ return m_LSAs.size ();
+}
+
+//
+// Get the nth link state advertisement from this router.
+//
+ bool
+GlobalRouter::GetLSA (uint32_t n, GlobalRouterLSA &lsa) const
+{
+ NS_ASSERT_MSG(lsa.IsEmpty(), "GlobalRouter::GetLSA (): Must pass empty LSA");
+//
+// All of the work was done in GetNumLSAs. All we have to do here is to
+// walk the list of link state advertisements created there and return the
+// one the client is interested in.
+//
+ ListOfLSAs_t::const_iterator i = m_LSAs.begin ();
+ uint32_t j = 0;
+
+ for (; i != m_LSAs.end (); i++, j++)
+ {
+ if (j == n)
+ {
+ GlobalRouterLSA *p = *i;
+ lsa = *p;
+ return true;
+ }
+ }
+
+ return false;
+}
+
+//
+// Link through the given channel and find the net device that's on the
+// other end. This only makes sense with a point-to-point channel.
+//
+ Ptr<NetDevice>
+GlobalRouter::GetAdjacent(Ptr<NetDevice> nd, Ptr<Channel> ch) const
+{
+
+ uint32_t nDevices = ch->GetNDevices();
+ NS_ASSERT_MSG(nDevices == 2,
+ "GlobalRouter::GetAdjacent (): Channel with other than two devices");
+//
+// This is a point to point channel with two endpoints. Get both of them.
+//
+ Ptr<NetDevice> nd1 = ch->GetDevice(0);
+ Ptr<NetDevice> nd2 = ch->GetDevice(1);
+//
+// One of the endpoints is going to be "us" -- that is the net device attached
+// to the node on which we're running -- i.e., "nd". The other endpoint (the
+// one to which we are connected via the channel) is the adjacent router.
+//
+ if (nd1 == nd)
+ {
+ return nd2;
+ }
+ else if (nd2 == nd)
+ {
+ return nd1;
+ }
+ else
+ {
+ NS_ASSERT_MSG(false,
+ "GlobalRouter::GetAdjacent (): Wrong or confused channel?");
+ return 0;
+ }
+}
+
+//
+// Given a node and a net device, find the IPV4 interface index that
+// corresponds to that net device.
+//
+ uint32_t
+GlobalRouter::FindIfIndexForDevice(Ptr<Node> node, Ptr<NetDevice> nd) const
+{
+ Ptr<Ipv4> ipv4 = node->QueryInterface<Ipv4> (Ipv4::iid);
+ NS_ASSERT_MSG(ipv4, "QI for <Ipv4> interface failed");
+ for (uint32_t i = 0; i < ipv4->GetNInterfaces(); ++i )
+ {
+ if (ipv4->GetNetDevice(i) == nd)
+ {
+ return i;
+ }
+ }
+
+ NS_ASSERT_MSG(0, "Cannot find interface for device");
+ return 0;
+}
+
+} // namespace ns3
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/routing/global-routing/global-router-interface.h Fri Aug 03 09:49:02 2007 -0700
@@ -0,0 +1,580 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * 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
+ */
+
+#ifndef GLOBAL_ROUTER_INTERFACE_H
+#define GLOBAL_ROUTER_INTERFACE_H
+
+#include <stdint.h>
+#include <list>
+#include "ns3/object.h"
+#include "ns3/ptr.h"
+#include "ns3/node.h"
+#include "ns3/channel.h"
+#include "ns3/ipv4-address.h"
+#include "ns3/global-route-manager.h"
+
+namespace ns3 {
+
+/**
+ * @brief A single link record for a link state advertisement.
+ *
+ * The GlobalRouterLinkRecord is modeled after the OSPF link record field of
+ * a Link State Advertisement. Right now we will only see two types of link
+ * records corresponding to a stub network and a point-to-point link (channel).
+ */
+class GlobalRouterLinkRecord
+{
+public:
+/**
+ * @enum LinkType
+ * @brief Enumeration of the possible types of Global Router Link Records.
+ *
+ * These values are defined in the OSPF spec. We currently only use
+ * PointToPoint and StubNetwork types.
+ */
+ enum LinkType {
+ Unknown = 0, /**< Uninitialized Link Record */
+ PointToPoint, /**< Record representing a point to point channel */
+ TransitNetwork, /**< Unused -- for future OSPF compatibility */
+ StubNetwork, /**< Record represents a leaf node network */
+ VirtualLink /**< Unused -- for future OSPF compatibility */
+ };
+
+/**
+ * @brief Construct an empty ("uninitialized") Global Router Link Record.
+ *
+ * The Link ID and Link Data Ipv4 addresses are set to "0.0.0.0";
+ * The Link Type is set to Unknown;
+ * The metric is set to 0.
+ */
+ GlobalRouterLinkRecord ();
+
+/**
+ * Construct an initialized Global Router Link Record.
+ *
+ * @param linkType The type of link record to construct.
+ * @param linkId The link ID for the record.
+ * @param linkData The link data field for the record.
+ * @param metric The metric field for the record.
+ * @see LinkType
+ * @see SetLinkId
+ * @see SetLinkData
+ */
+ GlobalRouterLinkRecord (
+ LinkType linkType,
+ Ipv4Address linkId,
+ Ipv4Address linkData,
+ uint32_t metric);
+
+/**
+ * @brief Destroy a Global Router Link Record.
+ *
+ * Currently does nothing. Here as a placeholder only.
+ */
+ ~GlobalRouterLinkRecord ();
+
+/**
+ * Get the Link ID field of the Global Router Link Record.
+ *
+ * For an OSPF type 1 link (PointToPoint) the Link ID will be the Router ID
+ * of the neighboring router.
+ *
+ * For an OSPF type 3 link (StubNetwork), the Link ID will be the adjacent
+ * neighbor's IP address
+ *
+ * @returns The Ipv4Address corresponding to the Link ID field of the record.
+ */
+ Ipv4Address GetLinkId(void) const;
+
+/**
+ * @brief Set the Link ID field of the Global Router Link Record.
+ *
+ * For an OSPF type 1 link (PointToPoint) the Link ID must be the Router ID
+ * of the neighboring router.
+ *
+ * For an OSPF type 3 link (StubNetwork), the Link ID must be the adjacent
+ * neighbor's IP address
+ *
+ * @param addr An Ipv4Address to store in the Link ID field of the record.
+ */
+ void SetLinkId(Ipv4Address addr);
+
+/**
+ * @brief Get the Link Data field of the Global Router Link Record.
+ *
+ * For an OSPF type 1 link (PointToPoint) the Link Data will be the IP
+ * address of the node of the local side of the link.
+ *
+ * For an OSPF type 3 link (StubNetwork), the Link Data will be the
+ * network mask
+ *
+ * @returns The Ipv4Address corresponding to the Link Data field of the record.
+ */
+ Ipv4Address GetLinkData(void) const;
+
+/**
+ * @brief Set the Link Data field of the Global Router Link Record.
+ *
+ * For an OSPF type 1 link (PointToPoint) the Link Data must be the IP
+ * address of the node of the local side of the link.
+ *
+ * For an OSPF type 3 link (StubNetwork), the Link Data must be set to the
+ * network mask
+ *
+ * @param addr An Ipv4Address to store in the Link Data field of the record.
+ */
+ void SetLinkData(Ipv4Address addr);
+
+/**
+ * @brief Get the Link Type field of the Global Router Link Record.
+ *
+ * The Link Type describes the kind of link a given record represents. The
+ * values are defined by OSPF.
+ *
+ * @see LinkType
+ * @returns The LinkType of the current Global Router Link Record.
+ */
+ LinkType GetLinkType(void) const;
+
+/**
+ * @brief Set the Link Type field of the Global Router Link Record.
+ *
+ * The Link Type describes the kind of link a given record represents. The
+ * values are defined by OSPF.
+ *
+ * @see LinkType
+ * @param linkType The new LinkType for the current Global Router Link Record.
+ */
+ void SetLinkType(LinkType linkType);
+
+/**
+ * @brief Get the Metric Data field of the Global Router Link Record.
+ *
+ * The metric is an abstract cost associated with forwarding a packet across
+ * a link. A sum of metrics must have a well-defined meaning. That is, you
+ * shouldn't use bandwidth as a metric (how does the sum of the bandwidth of
+ * two hops relate to the cost of sending a packet); rather you should use
+ * something like delay.
+ *
+ * @returns The metric field of the Global Router Link Record.
+ */
+ uint32_t GetMetric(void) const;
+
+/**
+ * @brief Set the Metric Data field of the Global Router Link Record.
+ *
+ * The metric is an abstract cost associated with forwarding a packet across
+ * a link. A sum of metrics must have a well-defined meaning. That is, you
+ * shouldn't use bandwidth as a metric (how does the sum of the bandwidth of
+ * two hops relate to the cost of sending a packet); rather you should use
+ * something like delay.
+ *
+ * @param metric The new metric for the current Global Router Link Record.
+ */
+ void SetMetric(uint32_t metric);
+
+private:
+/**
+ * m_linkId and m_linkData are defined by OSPF to have different meanings
+ * depending on the type of link a given link records represents. They work
+ * together.
+ *
+ * For Type 1 link (PointToPoint), set m_linkId to Router ID of
+ * neighboring router.
+ *
+ * For Type 3 link (Stub), set m_linkId to neighbor's IP address
+ */
+ Ipv4Address m_linkId;
+
+/**
+ * m_linkId and m_linkData are defined by OSPF to have different meanings
+ * depending on the type of link a given link records represents. They work
+ * together.
+ *
+ * For Type 1 link (PointToPoint), set m_linkData to local IP address
+ *
+ * For Type 3 link (Stub), set m_linkData to mask
+ */
+ Ipv4Address m_linkData; // for links to RouterLSA,
+
+/**
+ * The type of the Global Router Link Record. Defined in the OSPF spec.
+ * We currently only use PointToPoint and StubNetwork types.
+ */
+ LinkType m_linkType;
+
+/**
+ * The metric for a given link.
+ *
+ * A metric is abstract cost associated with forwarding a packet across a
+ * link. A sum of metrics must have a well-defined meaning. That is, you
+ * shouldn't use bandwidth as a metric (how does the sum of the bandwidth
+ * of two hops relate to the cost of sending a packet); rather you should
+ * use something like delay.
+ */
+ uint32_t m_metric;
+};
+
+/**
+ * @brief a Link State Advertisement (LSA) for a router, used in global
+ * routing.
+ *
+ * Roughly equivalent to a global incarnation of the OSPF link state header
+ * combined with a list of Link Records. Since it's global, there's
+ * no need for age or sequence number. See RFC 2328, Appendix A.
+ */
+class GlobalRouterLSA
+{
+public:
+/**
+ * @enum SPFStatus
+ * @brief Enumeration of the possible values of the status flag in the Router
+ * Link State Advertisements.
+ */
+ enum SPFStatus {
+ LSA_SPF_NOT_EXPLORED = 0, /**< New vertex not yet considered */
+ LSA_SPF_CANDIDATE, /**< Vertex is in the SPF candidate queue */
+ LSA_SPF_IN_SPFTREE /**< Vertex is in the SPF tree */
+ };
+
+/**
+ * @brief Create a blank Global Router Link State Advertisement.
+ *
+ * On completion Ipv4Address variables initialized to 0.0.0.0 and the
+ * list of Link State Records is empty.
+ */
+ GlobalRouterLSA();
+
+/**
+ * @brief Create an initialized Global Router Link State Advertisement.
+ *
+ * On completion the list of Link State Records is empty.
+ *
+ * @param status The status to of the new LSA.
+ * @param linkStateId The Ipv4Address for the link state ID field.
+ * @param advertisingRtr The Ipv4Address for the advertising router field.
+ */
+ GlobalRouterLSA(SPFStatus status, Ipv4Address linkStateId,
+ Ipv4Address advertisingRtr);
+
+/**
+ * @brief Copy constructor for a Global Router Link State Advertisement.
+ *
+ * Takes a piece of memory and constructs a semantically identical copy of
+ * the given LSA.
+ *
+ * @param lsa The existing LSA to be used as the source.
+ */
+ GlobalRouterLSA (GlobalRouterLSA& lsa);
+
+/**
+ * @brief Destroy an existing Global Router Link State Advertisement.
+ *
+ * Any Global Router Link Records present in the list are freed.
+ */
+ ~GlobalRouterLSA();
+
+/**
+ * @brief Assignment operator for a Global Router Link State Advertisement.
+ *
+ * Takes an existing Global Router Link State Advertisement and overwrites
+ * it to make a semantically identical copy of a given prototype LSA.
+ *
+ * If there are any Global Router Link Records present in the existing
+ * LSA, they are freed before the assignment happens.
+ *
+ * @param lsa The existing LSA to be used as the source.
+ * @returns Reference to the overwritten LSA.
+ */
+ GlobalRouterLSA& operator= (const GlobalRouterLSA& lsa);
+
+/**
+ * @brief Copy any Global Router Link Records in a given Global Router Link
+ * State Advertisement to the current LSA.
+ *
+ * Existing Link Records are not deleted -- this is a concatenation of Link
+ * Records.
+ *
+ * @see ClearLinkRecords ()
+ * @param lsa The LSA to copy the Link Records from.
+ */
+ void CopyLinkRecords (const GlobalRouterLSA& lsa);
+
+/**
+ * @brief Add a given Global Router Link Record to the LSA.
+ *
+ * @param lr The Global Router Link Record to be added.
+ * @returns The number of link records in the list.
+ */
+ uint32_t AddLinkRecord (GlobalRouterLinkRecord* lr);
+
+/**
+ * @brief Return the number of Global Router Link Records in the LSA.
+ *
+ * @returns The number of link records in the list.
+ */
+ uint32_t GetNLinkRecords (void) const;
+
+/**
+ * @brief Return a pointer to the specified Global Router Link Record.
+ *
+ * @param n The LSA number desired.
+ * @returns The number of link records in the list.
+ */
+ GlobalRouterLinkRecord* GetLinkRecord (uint32_t n) const;
+
+/**
+ * @brief Release all of the Global Router Link Records present in the Global
+ * Router Link State Advertisement and make the list of link records empty.
+ */
+ void ClearLinkRecords(void);
+
+/**
+ * @brief Check to see if the list of Global Router Link Records present in the
+ * Global Router Link State Advertisement is empty.
+ *
+ * @returns True if the list is empty, false otherwise.
+ */
+ bool IsEmpty(void) const;
+
+/**
+ * @brief Print the contents of the Global Router Link State Advertisement and
+ * any Global Router Link Records present in the list. Quite verbose.
+ */
+ void Print (std::ostream &os) const;
+
+/**
+ * @brief Get the Link State ID as defined by the OSPF spec. We always set it
+ * to the router ID of the router making the advertisement.
+ *
+ * @see RoutingEnvironment::AllocateRouterId ()
+ * @see GlobalRouter::GetRouterId ()
+ * @returns The Ipv4Address stored as the link state ID.
+ */
+ Ipv4Address GetLinkStateId (void) const;
+
+/**
+ * @brief Set the Link State ID is defined by the OSPF spec. We always set it
+ * to the router ID of the router making the advertisement.
+ *
+ * @see RoutingEnvironment::AllocateRouterId ()
+ * @see GlobalRouter::GetRouterId ()
+ */
+ void SetLinkStateId (Ipv4Address addr);
+
+/**
+ * @brief Get the Advertising Router as defined by the OSPF spec. We always
+ * set it to the router ID of the router making the advertisement.
+ *
+ * @see RoutingEnvironment::AllocateRouterId ()
+ * @see GlobalRouter::GetRouterId ()
+ * @returns The Ipv4Address stored as the advetising router.
+ */
+ Ipv4Address GetAdvertisingRouter (void) const;
+
+/**
+ * @brief Set the Advertising Router as defined by the OSPF spec. We always
+ * set it to the router ID of the router making the advertisement.
+ *
+ * @see RoutingEnvironment::AllocateRouterId ()
+ * @see GlobalRouter::GetRouterId ()
+ */
+ void SetAdvertisingRouter (Ipv4Address rtr);
+
+/**
+ * @brief Get the SPF status of the advertisement.
+ *
+ * @see SPFStatus
+ * @returns The SPFStatus of the LSA.
+ */
+ SPFStatus GetStatus (void) const;
+
+/**
+ * @brief Set the SPF status of the advertisement
+ *
+ * @see SPFStatus
+ */
+ void SetStatus (SPFStatus status);
+
+private:
+/**
+ * The Link State ID is defined by the OSPF spec. We always set it to the
+ * router ID of the router making the advertisement.
+ *
+ * @see RoutingEnvironment::AllocateRouterId ()
+ * @see GlobalRouter::GetRouterId ()
+ */
+ Ipv4Address m_linkStateId;
+
+/**
+ * The Advertising Router is defined by the OSPF spec. We always set it to
+ * the router ID of the router making the advertisement.
+ *
+ * @see RoutingEnvironment::AllocateRouterId ()
+ * @see GlobalRouter::GetRouterId ()
+ */
+ Ipv4Address m_advertisingRtr;
+
+/**
+ * A convenience typedef to avoid too much writers cramp.
+ */
+ typedef std::list<GlobalRouterLinkRecord*> ListOfLinkRecords_t;
+
+/**
+ * Each Link State Advertisement contains a number of Link Records that
+ * describe the kinds of links that are attached to a given node. We
+ * consider PointToPoint and StubNetwork links.
+ *
+ * m_linkRecords is an STL list container to hold the Link Records that have
+ * been discovered and prepared for the advertisement.
+ *
+ * @see GlobalRouter::DiscoverLSAs ()
+ */
+ ListOfLinkRecords_t m_linkRecords;
+
+/**
+ * This is a tristate flag used internally in the SPF computation to mark
+ * if an SPFVertex (a data structure representing a vertex in the SPF tree
+ * -- a router) is new, is a candidate for a shortest path, or is in its
+ * proper position in the tree.
+ */
+ SPFStatus m_status;
+};
+
+std::ostream& operator<< (std::ostream& os, GlobalRouterLSA& lsa);
+
+/**
+ * @brief An interface aggregated to a node to provide global routing info
+ *
+ * An interface aggregated to a node that provides global routing information
+ * to a global route manager. The presence of the interface indicates that
+ * the node is a router. The interface is the mechanism by which the router
+ * advertises its connections to neighboring routers. We're basically
+ * allowing the route manager to query for link state advertisements.
+ */
+class GlobalRouter : public Object
+{
+public:
+/**
+ * @brief The Interface ID of the Global Router interface.
+ *
+ * @see Object::QueryInterface ()
+ */
+ static const InterfaceId iid;
+
+/**
+ * @brief Create a Global Router class and aggregate its interface onto the
+ * Node provided.
+ *
+ * @param node The existing Node onto which this router will be aggregated.
+ */
+ GlobalRouter (Ptr<Node> node);
+
+/**
+ * @brief Get the Router ID associated with this Global Router.
+ *
+ * The Router IDs are allocated in the RoutingEnvironment -- one per Router,
+ * starting at 0.0.0.1 and incrementing with each instantiation of a router.
+ *
+ * @see RoutingEnvironment::AllocateRouterId ()
+ * @returns The Router ID associated with the Global Router.
+ */
+ Ipv4Address GetRouterId (void) const;
+
+/**
+ * @brief Walk the connected channels, discover the adjacent routers and build
+ * the associated number of Global Router Link State Advertisements that
+ * this router can export.
+ *
+ * This is a fairly expensive operation in that every time it is called
+ * the current list of LSAs is built by walking connected point-to-point
+ * channels and peeking into adjacent IPV4 stacks to get address information.
+ * This is done to allow for limited dymanics of the Global Routing
+ * environment. By that we mean that you can discover new link state
+ * advertisements after a network topology change by calling DiscoverLSAs
+ * and then by reading those advertisements.
+ *
+ * @see GlobalRouterLSA
+ * @see GlobalRouter::GetLSA ()
+ * @returns The number of Global Router Link State Advertisements.
+ */
+ uint32_t DiscoverLSAs (void);
+
+/**
+ * @brief Get the Number of Global Router Link State Advertisements that this
+ * router can export.
+ *
+ * To get meaningful information you must have previously called DiscoverLSAs.
+ * After you know how many LSAs are present in the router, you may call
+ * GetLSA () to retrieve the actual advertisement.
+ *
+ * @see GlobalRouterLSA
+ * @see GlobalRouter::DiscoverLSAs ()
+ * @see GlobalRouter::GetLSA ()
+ * @returns The number of Global Router Link State Advertisements.
+ */
+ uint32_t GetNumLSAs (void) const;
+
+/**
+ * @brief Get a Global Router Link State Advertisements that this router has
+ * said that it can export.
+ *
+ * This is a fairly inexpensive expensive operation in that the hard work
+ * was done in GetNumLSAs. We just copy the indicated Global Router Link
+ * State Advertisement into the requested GlobalRouterLSA object.
+ *
+ * You must call GlobalRouter::GetNumLSAs before calling this method in
+ * order to discover the adjacent routers and build the advertisements.
+ * GetNumLSAs will return the number of LSAs this router advertises.
+ * The parameter n (requested LSA number) must be in the range 0 to
+ * GetNumLSAs() - 1.
+ *
+ * @see GlobalRouterLSA
+ * @see GlobalRouter::GetNumLSAs ()
+ * @param n The index number of the LSA you want to read.
+ * @param lsa The GlobalRouterLSA class to receive the LSA information.
+ * @returns The number of Global Router Link State Advertisements.
+ */
+ bool GetLSA (uint32_t n, GlobalRouterLSA &lsa) const;
+
+protected:
+ virtual ~GlobalRouter ();
+ void ClearLSAs (void);
+
+ Ptr<NetDevice> GetAdjacent(Ptr<NetDevice> nd, Ptr<Channel> ch) const;
+ uint32_t FindIfIndexForDevice(Ptr<Node> node, Ptr<NetDevice> nd) const;
+
+ Ptr<Node> m_node;
+
+ typedef std::list<GlobalRouterLSA*> ListOfLSAs_t;
+ ListOfLSAs_t m_LSAs;
+
+ Ipv4Address m_routerId;
+
+private:
+/**
+ * @brief Global Router copy construction is disallowed.
+ */
+ GlobalRouter (GlobalRouter& sr);
+/**
+ * @brief Global Router assignment operator is disallowed.
+ */
+ GlobalRouter& operator= (GlobalRouter& sr);
+};
+
+} // namespace ns3
+
+#endif /* GLOBAL_ROUTER_INTERFACE_H */
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/routing/global-routing/wscript Fri Aug 03 09:49:02 2007 -0700
@@ -0,0 +1,20 @@
+## -*- Mode: python; py-indent-offset: 4; indent-tabs-mode: nil; coding: utf-8; -*-
+
+def build(bld):
+ module = bld.create_obj('cpp', 'shlib')
+ module.name = 'ns3-global-routing'
+ module.target = module.name
+ module.uselib_local = ['ns3-node']
+ module.source = [
+ 'global-router-interface.cc',
+ 'global-route-manager.cc',
+ 'global-route-manager-impl.cc',
+ 'candidate-queue.cc',
+ ]
+ headers = bld.create_obj('ns3header')
+ headers.source = [
+ 'global-router-interface.h',
+ 'global-route-manager.h',
+ 'candidate-queue.h',
+ ]
+
--- a/src/routing/global/candidate-queue.cc Fri Aug 03 09:29:57 2007 -0700
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,150 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/*
- * 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
- */
-
-#include "ns3/debug.h"
-#include "ns3/assert.h"
-#include "candidate-queue.h"
-
-NS_DEBUG_COMPONENT_DEFINE ("CandidateQueue");
-
-namespace ns3 {
-
-CandidateQueue::CandidateQueue()
- : m_candidates ()
-{
- NS_DEBUG("CandidateQueue::CandidateQueue ()");
-}
-
-CandidateQueue::~CandidateQueue()
-{
- NS_DEBUG("CandidateQueue::~CandidateQueue ()");
- Clear ();
-}
-
- void
-CandidateQueue::Clear (void)
-{
- NS_DEBUG("CandidateQueue::Clear ()");
-
- while (!m_candidates.empty ())
- {
- SPFVertex *p = Pop ();
- delete p;
- p = 0;
- }
-}
-
- void
-CandidateQueue::Push (SPFVertex *vNew)
-{
- NS_DEBUG("CandidateQueue::Push (" << vNew << ")");
-
- CandidateList_t::iterator i = m_candidates.begin ();
-
- for (; i != m_candidates.end (); i++)
- {
- SPFVertex *v = *i;
- if (vNew->GetDistanceFromRoot () < v->GetDistanceFromRoot ())
- {
- break;
- }
- }
- m_candidates.insert(i, vNew);
-}
-
- SPFVertex *
-CandidateQueue::Pop (void)
-{
- NS_DEBUG("CandidateQueue::Pop ()");
-
- if (m_candidates.empty ())
- {
- return 0;
- }
-
- SPFVertex *v = m_candidates.front ();
- m_candidates.pop_front ();
- return v;
-}
-
- SPFVertex *
-CandidateQueue::Top (void) const
-{
- NS_DEBUG("CandidateQueue::Top ()");
-
- if (m_candidates.empty ())
- {
- return 0;
- }
-
- return m_candidates.front ();
-}
-
- bool
-CandidateQueue::Empty (void) const
-{
- NS_DEBUG("CandidateQueue::Empty ()");
-
- return m_candidates.empty ();
-}
-
- uint32_t
-CandidateQueue::Size (void) const
-{
- NS_DEBUG("CandidateQueue::Size ()");
-
- return m_candidates.size ();
-}
-
- SPFVertex *
-CandidateQueue::Find (const Ipv4Address addr) const
-{
- NS_DEBUG("CandidateQueue::Find ()");
-
- CandidateList_t::const_iterator i = m_candidates.begin ();
-
- for (; i != m_candidates.end (); i++)
- {
- SPFVertex *v = *i;
- if (v->GetVertexId() == addr)
- {
- return v;
- }
- }
-
- return 0;
-}
-
- void
-CandidateQueue::Reorder (void)
-{
- NS_DEBUG("CandidateQueue::Reorder ()");
-
- std::list<SPFVertex*> temp;
-
- while (!m_candidates.empty ()) {
- SPFVertex *v = m_candidates.front ();
- m_candidates.pop_front ();
- temp.push_back(v);
- }
-
- while (!temp.empty ()) {
- Push (temp.front ());
- temp.pop_front ();
- }
-}
-
-} // namespace ns3
--- a/src/routing/global/candidate-queue.h Fri Aug 03 09:29:57 2007 -0700
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,181 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/*
- * 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
- */
-
-#ifndef CANDIDATE_QUEUE_H
-#define CANDIDATE_QUEUE_H
-
-#include <stdint.h>
-#include <list>
-#include "global-route-manager-impl.h"
-
-namespace ns3 {
-
-/**
- * \brief A Candidate Queue used in static routing.
- *
- * The CandidateQueue is used in the OSPF shortest path computations. It
- * is a priority queue used to store candidates for the shortest path to a
- * given network.
- *
- * The queue holds Shortest Path First Vertex pointers and orders them
- * according to the lowest value of the field m_distanceFromRoot. Remaining
- * vertices are ordered according to increasing distance. This implements a
- * priority queue.
- *
- * Although a STL priority_queue almost does what we want, the requirement
- * for a Find () operation, the dynamic nature of the data and the derived
- * requirement for a Reorder () operation led us to implement this simple
- * enhanced priority queue.
- */
-class CandidateQueue
-{
-public:
-/**
- * @brief Create an empty SPF Candidate Queue.
- * @internal
- *
- * @see SPFVertex
- */
- CandidateQueue ();
-
-/**
- * @internal Destroy an SPF Candidate Queue and release any resources held
- * by the contents.
- * @internal
- *
- * @see SPFVertex
- */
- virtual ~CandidateQueue ();
-
-/**
- * @brief Empty the Candidate Queue and release all of the resources
- * associated with the Shortest Path First Vertex pointers in the queue.
- * @internal
- *
- * @see SPFVertex
- */
- void Clear (void);
-
-/**
- * @brief Push a Shortest Path First Vertex pointer onto the queue according
- * to the priority scheme.
- * @internal
- *
- * On completion, the top of the queue will hold the Shortest Path First
- * Vertex pointer that points to a vertex having lowest value of the field
- * m_distanceFromRoot. Remaining vertices are ordered according to
- * increasing distance.
- *
- * @see SPFVertex
- * @param vNew The Shortest Path First Vertex to add to the queue.
- */
- void Push (SPFVertex *vNew);
-
-/**
- * @brief Pop the Shortest Path First Vertex pointer at the top of the queue.
- * @internal
- *
- * The caller is given the responsiblity for releasing the resources
- * associated with the vertex.
- *
- * @see SPFVertex
- * @see Top ()
- * @returns The Shortest Path First Vertex pointer at the top of the queue.
- */
- SPFVertex* Pop (void);
-
-/**
- * @brief Return the Shortest Path First Vertex pointer at the top of the
- * queue.
- * @internal
- *
- * This method does not pop the SPFVertex* off of the queue, it simply
- * returns the pointer.
- *
- * @see SPFVertex
- * @see Pop ()
- * @returns The Shortest Path First Vertex pointer at the top of the queue.
- */
- SPFVertex* Top (void) const;
-
-/**
- * @brief Test the Candidate Queue to determine if it is empty.
- * @internal
- *
- * @returns True if the queue is empty, false otherwise.
- */
- bool Empty (void) const;
-
-/**
- * @brief Return the number of Shortest Path First Vertex pointers presently
- * stored in the Candidate Queue.
- * @internal
- *
- * @see SPFVertex
- * @returns The number of SPFVertex* pointers in the Candidate Queue.
- */
- uint32_t Size (void) const;
-
-/**
- * @brief Searches the Candidate Queue for a Shortest Path First Vertex
- * pointer that points to a vertex having the given IP address.
- * @internal
- *
- * @see SPFVertex
- * @param addr The IP address to search for.
- * @returns The SPFVertex* pointer corresponding to the given IP address.
- */
- SPFVertex* Find (const Ipv4Address addr) const;
-
-/**
- * @brief Reorders the Candidate Queue according to the priority scheme.
- * @internal
- *
- * On completion, the top of the queue will hold the Shortest Path First
- * Vertex pointer that points to a vertex having lowest value of the field
- * m_distanceFromRoot. Remaining vertices are ordered according to
- * increasing distance.
- *
- * This method is provided in case the values of m_distanceFromRoot change
- * during the routing calculations.
- *
- * @see SPFVertex
- */
- void Reorder (void);
-
-protected:
- typedef std::list<SPFVertex*> CandidateList_t;
- CandidateList_t m_candidates;
-
-private:
-/**
- * Candidate Queue copy construction is disallowed (not implemented) to
- * prevent the compiler from slipping in incorrect versions that don't
- * properly deal with deep copies.
- */
- CandidateQueue (CandidateQueue& sr);
-
-/**
- * Candidate Queue assignment operator is disallowed (not implemented) to
- * prevent the compiler from slipping in incorrect versions that don't
- * properly deal with deep copies.
- */
- CandidateQueue& operator= (CandidateQueue& sr);
-};
-
-} // namespace ns3
-
-#endif /* CANDIDATE_QUEUE_H */
--- a/src/routing/global/global-route-manager-impl.cc Fri Aug 03 09:29:57 2007 -0700
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,1408 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/*
- * 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
- */
-
-#include <utility>
-#include <vector>
-#include <queue>
-#include "ns3/assert.h"
-#include "ns3/fatal-error.h"
-#include "ns3/debug.h"
-#include "ns3/node-list.h"
-#include "ns3/ipv4.h"
-#include "global-router-interface.h"
-#include "global-route-manager-impl.h"
-#include "candidate-queue.h"
-
-NS_DEBUG_COMPONENT_DEFINE ("GlobalRouteManager");
-
-namespace ns3 {
-
-// ---------------------------------------------------------------------------
-//
-// SPFVertex Implementation
-//
-// ---------------------------------------------------------------------------
-
-SPFVertex::SPFVertex () :
- m_vertexType (VertexUnknown),
- m_vertexId ("255.255.255.255"),
- m_lsa (0),
- m_distanceFromRoot (SPF_INFINITY),
- m_rootOif (SPF_INFINITY),
- m_nextHop ("0.0.0.0"),
- m_parent (0),
- m_children ()
-{
-}
-
-SPFVertex::SPFVertex (GlobalRouterLSA* lsa) :
- m_vertexType (VertexRouter),
- m_vertexId (lsa->GetLinkStateId ()),
- m_lsa (lsa),
- m_distanceFromRoot (SPF_INFINITY),
- m_rootOif (SPF_INFINITY),
- m_nextHop ("0.0.0.0"),
- m_parent (0),
- m_children ()
-{
-}
-
-SPFVertex::~SPFVertex ()
-{
- for ( ListOfSPFVertex_t::iterator i = m_children.begin ();
- i != m_children.end ();
- i++)
- {
- SPFVertex *p = *i;
- delete p;
- p = 0;
- *i = 0;
- }
- m_children.clear ();
-}
-
- void
-SPFVertex::SetVertexType (SPFVertex::VertexType type)
-{
- m_vertexType = type;
-}
-
- SPFVertex::VertexType
-SPFVertex::GetVertexType (void) const
-{
- return m_vertexType;
-}
-
- void
-SPFVertex::SetVertexId (Ipv4Address id)
-{
- m_vertexId = id;
-}
-
- Ipv4Address
-SPFVertex::GetVertexId (void) const
-{
- return m_vertexId;
-}
-
- void
-SPFVertex::SetLSA (GlobalRouterLSA* lsa)
-{
- m_lsa = lsa;
-}
-
- GlobalRouterLSA*
-SPFVertex::GetLSA (void) const
-{
- return m_lsa;
-}
-
- void
-SPFVertex::SetDistanceFromRoot (uint32_t distance)
-{
- m_distanceFromRoot = distance;
-}
-
- uint32_t
-SPFVertex::GetDistanceFromRoot (void) const
-{
- return m_distanceFromRoot;
-}
-
- void
-SPFVertex::SetOutgoingInterfaceId (uint32_t id)
-{
- m_rootOif = id;
-}
-
- uint32_t
-SPFVertex::GetOutgoingInterfaceId (void) const
-{
- return m_rootOif;
-}
-
- void
-SPFVertex::SetNextHop (Ipv4Address nextHop)
-{
- m_nextHop = nextHop;
-}
-
- Ipv4Address
-SPFVertex::GetNextHop (void) const
-{
- return m_nextHop;
-}
-
- void
-SPFVertex::SetParent (SPFVertex* parent)
-{
- m_parent = parent;
-}
-
- SPFVertex*
-SPFVertex::GetParent (void) const
-{
- return m_parent;
-}
-
- uint32_t
-SPFVertex::GetNChildren (void) const
-{
- return m_children.size ();
-}
-
- SPFVertex*
-SPFVertex::GetChild (uint32_t n) const
-{
- uint32_t j = 0;
-
- for ( ListOfSPFVertex_t::const_iterator i = m_children.begin ();
- i != m_children.end ();
- i++, j++)
- {
- if (j == n)
- {
- return *i;
- }
- }
- NS_ASSERT_MSG(false, "Index <n> out of range.");
- return 0;
-}
-
- uint32_t
-SPFVertex::AddChild (SPFVertex* child)
-{
- m_children.push_back (child);
- return m_children.size ();
-}
-
-// ---------------------------------------------------------------------------
-//
-// GlobalRouteManagerLSDB Implementation
-//
-// ---------------------------------------------------------------------------
-
-GlobalRouteManagerLSDB::GlobalRouteManagerLSDB ()
-:
- m_database ()
-{
- NS_DEBUG ("GlobalRouteManagerLSDB::GlobalRouteManagerLSDB ()");
-}
-
-GlobalRouteManagerLSDB::~GlobalRouteManagerLSDB ()
-{
- NS_DEBUG ("GlobalRouteManagerLSDB::~GlobalRouteManagerLSDB ()");
-
- LSDBMap_t::iterator i;
- for (i= m_database.begin (); i!= m_database.end (); i++)
- {
- NS_DEBUG ("GlobalRouteManagerLSDB::~GlobalRouteManagerLSDB ():free LSA");
- GlobalRouterLSA* temp = i->second;
- delete temp;
- }
- NS_DEBUG ("GlobalRouteManagerLSDB::~GlobalRouteManagerLSDB (): clear map");
- m_database.clear ();
-}
-
- void
-GlobalRouteManagerLSDB::Initialize ()
-{
- NS_DEBUG ("GlobalRouteManagerLSDB::Initialize ()");
-
- LSDBMap_t::iterator i;
- for (i= m_database.begin (); i!= m_database.end (); i++)
- {
- GlobalRouterLSA* temp = i->second;
- temp->SetStatus (GlobalRouterLSA::LSA_SPF_NOT_EXPLORED);
- }
-}
-
- void
-GlobalRouteManagerLSDB::Insert (Ipv4Address addr, GlobalRouterLSA* lsa)
-{
- NS_DEBUG ("GlobalRouteManagerLSDB::Insert ()");
- m_database.insert (LSDBPair_t (addr, lsa));
-}
-
- GlobalRouterLSA*
-GlobalRouteManagerLSDB::GetLSA (Ipv4Address addr) const
-{
- NS_DEBUG ("GlobalRouteManagerLSDB::GetLSA ()");
-//
-// Look up an LSA by its address.
-//
- LSDBMap_t::const_iterator i;
- for (i= m_database.begin (); i!= m_database.end (); i++)
- {
- if (i->first == addr)
- {
- return i->second;
- }
- }
- return 0;
-}
-
-// ---------------------------------------------------------------------------
-//
-// GlobalRouteManagerImpl Implementation
-//
-// ---------------------------------------------------------------------------
-
-GlobalRouteManagerImpl::GlobalRouteManagerImpl ()
-:
- m_spfroot (0)
-{
- NS_DEBUG ("GlobalRouteManagerImpl::GlobalRoutemanagerImpl ()");
- m_lsdb = new GlobalRouteManagerLSDB ();
-}
-
-GlobalRouteManagerImpl::~GlobalRouteManagerImpl ()
-{
- NS_DEBUG ("GlobalRouteManagerImpl::~GlobalRouteManagerImpl ()");
-
- if (m_lsdb)
- {
- delete m_lsdb;
- }
-}
-
- void
-GlobalRouteManagerImpl::DebugUseLsdb (GlobalRouteManagerLSDB* lsdb)
-{
- NS_DEBUG ("GlobalRouteManagerImpl::DebugUseLsdb ()");
-
- if (m_lsdb)
- {
- delete m_lsdb;
- }
- m_lsdb = lsdb;
-}
-
-//
-// In order to build the routing database, we need at least one of the nodes
-// to participate as a router. Eventually we expect to provide a mechanism
-// for selecting a subset of the nodes to participate; for now, we just make
-// all nodes routers. We do this by walking the list of nodes in the system
-// and aggregating a Global Router Interface to each of the nodes.
-//
- void
-GlobalRouteManagerImpl::SelectRouterNodes ()
-{
- NS_DEBUG ("GlobalRouteManagerImpl::SelectRouterNodes ()");
-
- typedef std::vector < Ptr<Node> >::iterator Iterator;
- for (Iterator i = NodeList::Begin (); i != NodeList::End (); i++)
- {
- Ptr<Node> node = *i;
- NS_DEBUG ("GlobalRouteManagerImpl::SelectRouterNodes (): "
- "Adding GlobalRouter interface to node " <<
- node->GetId ());
-
- Ptr<GlobalRouter> globalRouter = Create<GlobalRouter> (node);
- node->AddInterface (globalRouter);
- }
-}
-
-//
-// In order to build the routing database, we need to walk the list of nodes
-// in the system and look for those that support the GlobalRouter interface.
-// These routers will export a number of Link State Advertisements (LSAs)
-// that describe the links and networks that are "adjacent" (i.e., that are
-// on the other side of a point-to-point link). We take these LSAs and put
-// add them to the Link State DataBase (LSDB) from which the routes will
-// ultimately be computed.
-//
- void
-GlobalRouteManagerImpl::BuildGlobalRoutingDatabase ()
-{
- NS_DEBUG ("GlobalRouteManagerImpl::BuildGlobalRoutingDatabase()");
-//
-// Walk the list of nodes looking for the GlobalRouter Interface.
-//
- typedef std::vector < Ptr<Node> >::iterator Iterator;
- for (Iterator i = NodeList::Begin (); i != NodeList::End (); i++)
- {
- Ptr<Node> node = *i;
-
- Ptr<GlobalRouter> rtr =
- node->QueryInterface<GlobalRouter> (GlobalRouter::iid);
-//
-// Ignore nodes that aren't participating in routing.
-//
- if (!rtr)
- {
- continue;
- }
-//
-// You must call DiscoverLSAs () before trying to use any routing info or to
-// update LSAs. DiscoverLSAs () drives the process of discovering routes in
-// the GlobalRouter. Afterward, you may use GetNumLSAs (), which is a very
-// computationally inexpensive call. If you call GetNumLSAs () before calling
-// DiscoverLSAs () will get zero as the number since no routes have been
-// found.
-//
- uint32_t numLSAs = rtr->DiscoverLSAs ();
- NS_DEBUG ("Discover LSAs: Found " << numLSAs << " LSAs");
-
- for (uint32_t j = 0; j < numLSAs; ++j)
- {
- GlobalRouterLSA* lsa = new GlobalRouterLSA ();
-//
-// This is the call to actually fetch a Link State Advertisement from the
-// router.
-//
- rtr->GetLSA (j, *lsa);
- NS_DEBUG ("LSA " << j);
- NS_DEBUG (*lsa);
-//
-// Write the newly discovered link state advertisement to the database.
-//
- m_lsdb->Insert (lsa->GetLinkStateId (), lsa);
- }
- }
-}
-
-//
-// For each node that is a global router (which is determined by the presence
-// of an aggregated GlobalRouter interface), run the Dijkstra SPF calculation
-// on the database rooted at that router, and populate the node forwarding
-// tables.
-//
-// This function parallels RFC2328, Section 16.1.1, and quagga ospfd
-//
-// This calculation yields the set of intra-area routes associated
-// with an area (called hereafter Area A). A router calculates the
-// shortest-path tree using itself as the root. The formation
-// of the shortest path tree is done here in two stages. In the
-// first stage, only links between routers and transit networks are
-// considered. Using the Dijkstra algorithm, a tree is formed from
-// this subset of the link state database. In the second stage,
-// leaves are added to the tree by considering the links to stub
-// networks.
-//
-// The area's link state database is represented as a directed graph.
-// The graph's vertices are routers, transit networks and stub networks.
-//
-// The first stage of the procedure (i.e., the Dijkstra algorithm)
-// can now be summarized as follows. At each iteration of the
-// algorithm, there is a list of candidate vertices. Paths from
-// the root to these vertices have been found, but not necessarily
-// the shortest ones. However, the paths to the candidate vertex
-// that is closest to the root are guaranteed to be shortest; this
-// vertex is added to the shortest-path tree, removed from the
-// candidate list, and its adjacent vertices are examined for
-// possible addition to/modification of the candidate list. The
-// algorithm then iterates again. It terminates when the candidate
-// list becomes empty.
-//
- void
-GlobalRouteManagerImpl::InitializeRoutes ()
-{
- NS_DEBUG ("GlobalRouteManagerImpl::InitializeRoutes ()");
-//
-// Walk the list of nodes in the system.
-//
- typedef std::vector < Ptr<Node> >::iterator Iterator;
- for (Iterator i = NodeList::Begin (); i != NodeList::End (); i++)
- {
- Ptr<Node> node = *i;
-//
-// Look for the GlobalRouter interface that indicates that the node is
-// participating in routing.
-//
- Ptr<GlobalRouter> rtr =
- node->QueryInterface<GlobalRouter> (GlobalRouter::iid);
-//
-// if the node has a global router interface, then run the global routing
-// algorithms.
-//
- if (rtr && rtr->GetNumLSAs () )
- {
- SPFCalculate (rtr->GetRouterId ());
- }
- }
-}
-
-//
-// This method is derived from quagga ospf_spf_next (). See RFC2328 Section
-// 16.1 (2) for further details.
-//
-// We're passed a parameter <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.
-//
- void
-GlobalRouteManagerImpl::SPFNext (SPFVertex* v, CandidateQueue& candidate)
-{
- SPFVertex* w = 0;
- GlobalRouterLSA* w_lsa = 0;
- uint32_t distance = 0;
-
- NS_DEBUG ("GlobalRouteManagerImpl::SPFNext ()");
-//
-// Always true for now, since all our LSAs are RouterLSAs.
-//
- if (v->GetVertexType () == SPFVertex::VertexRouter)
- {
- if (true)
- {
- NS_DEBUG ("SPFNext: Examining " << v->GetVertexId () << "'s " <<
- v->GetLSA ()->GetNLinkRecords () << " link records");
-//
-// Walk the list of link records in the link state advertisement associated
-// with the "current" router (represented by vertex <v>).
-//
- for (uint32_t i = 0; i < v->GetLSA ()->GetNLinkRecords (); ++i)
- {
-//
-// (a) If this is a link to a stub network, examine the next link in V's LSA.
-// Links to stub networks will be considered in the second stage of the
-// shortest path calculation.
-//
- GlobalRouterLinkRecord *l = v->GetLSA ()->GetLinkRecord (i);
- if (l->GetLinkType () == GlobalRouterLinkRecord::StubNetwork)
- {
- NS_DEBUG ("SPFNext: Found a Stub record to " <<
- l->GetLinkId ());
- continue;
- }
-//
-// (b) Otherwise, W is a transit vertex (router or transit network). Look up
-// the vertex W's LSA (router-LSA or network-LSA) in Area A's link state
-// database.
-//
- if (l->GetLinkType () == GlobalRouterLinkRecord::PointToPoint)
- {
-//
-// Lookup the link state advertisement of the new link -- we call it <w> in
-// the link state database.
-//
- w_lsa = m_lsdb->GetLSA (l->GetLinkId ());
- NS_ASSERT (w_lsa);
- NS_DEBUG ("SPFNext: Found a P2P record from " <<
- v->GetVertexId () << " to " << w_lsa->GetLinkStateId ());
-//
-// (c) If vertex W is already on the shortest-path tree, examine the next
-// link in the LSA.
-//
-// If the link is to a router that is already in the shortest path first tree
-// then we have it covered -- ignore it.
-//
- if (w_lsa->GetStatus () ==
- GlobalRouterLSA::LSA_SPF_IN_SPFTREE)
- {
- NS_DEBUG ("SPFNext: Skipping-> LSA "<<
- w_lsa->GetLinkStateId () << " already in SPF tree");
- continue;
- }
-//
-// The link is to a router we haven't dealt with yet.
-//
-// (d) Calculate the link state cost D of the resulting path from the root to
-// vertex W. D is equal to the sum of the link state cost of the (already
-// calculated) shortest path to vertex V and the advertised cost of the link
-// between vertices V and W.
-//
- distance = v->GetDistanceFromRoot () + l->GetMetric ();
-
- NS_DEBUG ("SPFNext: Considering w_lsa " <<
- w_lsa->GetLinkStateId ());
-
- if (w_lsa->GetStatus () ==
- GlobalRouterLSA::LSA_SPF_NOT_EXPLORED)
- {
-//
-// If we haven't yet considered the link represented by <w> we have to create
-// a new SPFVertex to represent it.
-//
- w = new SPFVertex (w_lsa);
-//
-// We need to figure out how to actually get to the new router represented
-// by <w>. This will (among other things) find the next hop address to send
-// packets destined for this network to, and also find the outbound interface
-// used to forward the packets.
-//
- if (SPFNexthopCalculation (v, w, l, distance))
- {
- w_lsa->SetStatus (
- GlobalRouterLSA::LSA_SPF_CANDIDATE);
-//
-// Push this new vertex onto the priority queue (ordered by distance from the
-// root node).
-//
- candidate.Push (w);
- NS_DEBUG ("SPFNext: Pushing " <<
- w->GetVertexId () << ", parent vertexId: " <<
- v->GetVertexId ());
- }
- }
- } else if (w_lsa->GetStatus () ==
- GlobalRouterLSA::LSA_SPF_CANDIDATE)
- {
-//
-// We have already considered the link represented by <w>. What wse have to
-// do now is to decide if this new router represents a route with a shorter
-// distance metric.
-//
-// So, locate the vertex in the candidate queue and take a look at the
-// distance.
- w = candidate.Find (w_lsa->GetLinkStateId ());
- if (w->GetDistanceFromRoot () < distance)
- {
-//
-// This is not a shorter path, so don't do anything.
-//
- continue;
- }
- else if (w->GetDistanceFromRoot () == distance)
- {
-//
-// This path is one with an equal cost. Do nothing for now -- we're not doing
-// equal-cost multipath cases yet.
-//
- }
- else
- {
-//
-// this path represents a new, lower-cost path to <w> (the vertex we found in
-// the current link record of the link state advertisement of the current root
-// (vertex <v>)
-//
-// N.B. the nexthop_calculation is conditional, if it finds a valid nexthop
-// it will call spf_add_parents, which will flush the old parents
-//
- if (SPFNexthopCalculation (v, w, l, distance))
- {
-//
-// If we've changed the cost to get to the vertex represented by <w>, we
-// must reorder the priority queue keyed to that cost.
-//
- candidate.Reorder ();
- }
- }
- } // point-to-point
- } // for loop
- }
- }
-}
-
-//
-// This method is derived from quagga ospf_next_hop_calculation() 16.1.1.
-//
-// Calculate the next hop IP address and the outgoing interface required to
-// get packets from the root through <v> (parent) to vertex <w> (destination),
-// over a given distance.
-//
-// For now, this is greatly simplified from the quagga code
-//
- int
-GlobalRouteManagerImpl::SPFNexthopCalculation (
- SPFVertex* v,
- SPFVertex* w,
- GlobalRouterLinkRecord* l,
- uint32_t distance)
-{
- NS_DEBUG ("GlobalRouteManagerImpl::SPFNexthopCalculation ()");
-//
-// The vertex m_spfroot is a distinguished vertex representing the node at
-// the root of the calculations. That is, it is the node for which we are
-// calculating the routes.
-//
-// There are two distinct cases for calculating the next hop information.
-// First, if we're considering a hop from the root to an "adjacent" network
-// (one that is on the other side of a point-to-point link connected to the
-// root), then we need to store the information needed to forward down that
-// link. The second case is if the network is not directly adjacent. In that
-// case we need to use the forwarding information from the vertex on the path
-// to the destination that is directly adjacent [node 1] in both cases of the
-// diagram below.
-//
-// (1) [root] -> [point-to-point] -> [node 1]
-// (2) [root] -> [point-to-point] -> [node 1] -> [point-to-point] -> [node 2]
-//
-// We call the propagation of next hop information down vertices of a path
-// "inheriting" the next hop information.
-//
-// The point-to-point link information is only useful in this calculation when
-// we are examining the root node.
-//
- if (v == m_spfroot)
- {
-//
-// In this case <v> is the root node, which means it is the starting point
-// for the packets forwarded by that node. This also means that the next hop
-// address of packets headed for some arbitrary off-network destination must
-// be the destination at the other end of one of the links off of the root
-// node if this root node is a router. We then need to see if this node <w>
-// is a router.
-//
- if (w->GetVertexType () == SPFVertex::VertexRouter)
- {
-//
-// In the case of point-to-point links, the link data field (m_linkData) of a
-// Global Router Link Record contains the local IP address. If we look at the
-// link record describing the link from the perspecive of <w> (the remote
-// node from the viewpoint of <v>) back to the root node, we can discover the
-// IP address of the router to which <v> is adjacent. This is a distinguished
-// address -- the next hop address to get from <v> to <w> and all networks
-// accessed through that path.
-//
-// SPFGetNextLink () is a little odd. used in this way it is just going to
-// return the link record describing the link from <w> to <v>. Think of it as
-// SPFGetLink.
-//
- GlobalRouterLinkRecord *linkRemote = 0;
- linkRemote = SPFGetNextLink (w, v, linkRemote);
-//
-// At this point, <l> is the Global Router Link Record describing the point-
-// to point link from <v> to <w> from the perspective of <v>; and <linkRemote>
-// is the Global Router Link Record describing that same link from the
-// perspective of <w> (back to <v>). Now we can just copy the next hop
-// address from the m_linkData member variable.
-//
-// The next hop member variable we put in <w> has the sense "in order to get
-// from the root node to the host represented by vertex <w>, you have to send
-// the packet to the next hop address specified in w->m_nextHop.
-//
- w->SetNextHop(linkRemote->GetLinkData ());
-//
-// Now find the outgoing interface corresponding to the point to point link
-// from the perspective of <v> -- remember that <l> is the link "from"
-// <v> "to" <w>.
-//
- w->SetOutgoingInterfaceId (
- FindOutgoingInterfaceId (l->GetLinkData ()));
-
- NS_DEBUG ("SPFNexthopCalculation: Next hop from " <<
- v->GetVertexId () << " to " << w->GetVertexId () <<
- " goes through next hop " << w->GetNextHop () <<
- " via outgoing interface " << w->GetOutgoingInterfaceId ());
- }
- }
- else
- {
-//
-// If we're calculating the next hop information from a node (v) that is
-// *not* the root, then we need to "inherit" the information needed to
-// forward the packet from the vertex closer to the root. That is, we'll
-// still send packets to the next hop address of the router adjacent to the
-// root on the path toward <w>.
-//
-// Above, when we were considering the root node, we calculated the next hop
-// address and outgoing interface required to get off of the root network.
-// At this point, we are further away from the root network along one of the
-// (shortest) paths. So the next hop and outoing interface remain the same
-// (are inherited).
-//
- w->SetNextHop (v->GetNextHop ());
- w->SetOutgoingInterfaceId (v->GetOutgoingInterfaceId ());
- }
-//
-// In all cases, we need valid values for the distance metric and a parent.
-//
- w->SetDistanceFromRoot (distance);
- w->SetParent (v);
-
- return 1;
-}
-
-//
-// This method is derived from quagga ospf_get_next_link ()
-//
-// First search the Global Router Link Records of vertex <v> for one
-// representing a point-to point link to vertex <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 <v>
-// to <w>. If prev_link is not NULL, we return a Global Router Link Record
-// representing a possible *second* link from <v> to <w>.
-//
-// BUGBUG FIXME: This seems to be a bug. Shouldn't this function look for
-// any link records after pre_link and not just after the first?
-//
- GlobalRouterLinkRecord*
-GlobalRouteManagerImpl::SPFGetNextLink (
- SPFVertex* v,
- SPFVertex* w,
- GlobalRouterLinkRecord* prev_link)
-{
- NS_DEBUG ("GlobalRouteManagerImpl::SPFGetNextLink ()");
-
- bool skip = true;
- GlobalRouterLinkRecord* l;
-//
-// If prev_link is 0, we are really looking for the first link, not the next
-// link.
-//
- if (prev_link == 0)
- {
- skip = false;
- }
-//
-// Iterate through the Global Router Link Records advertised by the vertex
-// <v> looking for records representing the point-to-point links off of this
-// vertex.
-//
- for (uint32_t i = 0; i < v->GetLSA ()->GetNLinkRecords (); ++i)
- {
- l = v->GetLSA ()->GetLinkRecord (i);
- if (l->GetLinkType () != GlobalRouterLinkRecord::PointToPoint)
- {
- continue;
- }
-//
-// The link ID of a link record representing a point-to-point link is set to
-// the router ID of the neighboring router -- the router to which the link
-// connects from the perspective of <v> in this case. The vertex ID is also
-// set to the router ID (using the link state advertisement of a router node).
-// We're just checking to see if the link <l> is actually the link from <v> to
-// <w>.
-//
- if (l->GetLinkId () == w->GetVertexId ()) {
- NS_DEBUG ("SPFGetNextLink: Found matching link l: linkId = " <<
- l->GetLinkId () << " linkData = " << l->GetLinkData ());
-//
-// If skip is false, don't (not too surprisingly) skip the link found -- it's
-// the one we're interested in. That's either because we didn't pass in a
-// previous link, and we're interested in the first one, or because we've
-// skipped a previous link and moved forward to the next (which is then the
-// one we want).
-//
- if (skip == false)
- {
- NS_DEBUG ("SPFGetNextLink: Returning the found link");
- return l;
- }
- else
- {
-//
-// Skip is true and we've found a link from <v> to <w>. We want the next one.
-// Setting skip to false gets us the next point-to-point global router link
-// record in the LSA from <v>.
-//
- NS_DEBUG ("SPFGetNextLink: Skipping the found link");
- skip = false;
- continue;
- }
- }
- }
- return 0;
-}
-
-//
-// Used for unit tests.
-//
- void
-GlobalRouteManagerImpl::DebugSPFCalculate (Ipv4Address root)
-{
- NS_DEBUG ("GlobalRouteManagerImpl::DebugSPFCalculate ()");
- SPFCalculate (root);
-}
-
-// quagga ospf_spf_calculate
- void
-GlobalRouteManagerImpl::SPFCalculate (Ipv4Address root)
-{
- NS_DEBUG ("GlobalRouteManagerImpl::SPFCalculate (): "
- "root = " << root);
-
- SPFVertex *v;
-//
-// Initialize the Link State Database.
-//
- m_lsdb->Initialize ();
-//
-// The candidate queue is a priority queue of SPFVertex objects, with the top
-// of the queue being the closest vertex in terms of distance from the root
-// of the tree. Initially, this queue is empty.
-//
- CandidateQueue candidate;
- NS_ASSERT(candidate.Size () == 0);
-//
-// Initialize the shortest-path tree to only contain the router doing the
-// calculation. Each router (and corresponding network) is a vertex in the
-// shortest path first (SPF) tree.
-//
- v = new SPFVertex (m_lsdb->GetLSA (root));
-//
-// This vertex is the root of the SPF tree and it is distance 0 from the root.
-// We also mark this vertex as being in the SPF tree.
-//
- m_spfroot= v;
- v->SetDistanceFromRoot (0);
- v->GetLSA ()->SetStatus (GlobalRouterLSA::LSA_SPF_IN_SPFTREE);
-
- for (;;)
- {
-//
-// The operations we need to do are given in the OSPF RFC which we reference
-// as we go along.
-//
-// RFC2328 16.1. (2).
-//
-// We examine the Global Router Link Records in the Link State
-// Advertisements of the current vertex. If there are any point-to-point
-// links to unexplored adjacent vertices we add them to the tree and update
-// the distance and next hop information on how to get there. We also add
-// the new vertices to the candidate queue (the priority queue ordered by
-// shortest path). If the new vertices represent shorter paths, we use them
-// and update the path cost.
-//
- SPFNext (v, candidate);
-//
-// RFC2328 16.1. (3).
-//
-// If at this step the candidate list is empty, the shortest-path tree (of
-// transit vertices) has been completely built and this stage of the
-// procedure terminates.
-//
- if (candidate.Size () == 0)
- {
- break;
- }
-//
-// Choose the vertex belonging to the candidate list that is closest to the
-// root, and add it to the shortest-path tree (removing it from the candidate
-// list in the process).
-//
-// Recall that in the previous step, we created SPFVertex structures for each
-// of the routers found in the Global Router Link Records and added tehm to
-// the candidate list.
-//
- v = candidate.Pop ();
- NS_DEBUG ("SPFCalculate: Popped vertex " << v->GetVertexId ());
-//
-// Update the status field of the vertex to indicate that it is in the SPF
-// tree.
-//
- v->GetLSA ()->SetStatus (GlobalRouterLSA::LSA_SPF_IN_SPFTREE);
-//
-// The current vertex has a parent pointer. By calling this rather oddly
-// named method (blame quagga) we add the current vertex to the list of
-// children of that parent vertex. In the next hop calculation called during
-// SPFNext, the parent pointer was set but the vertex has been orphaned up
-// to now.
-//
- SPFVertexAddParent (v);
-//
-// Note that when there is a choice of vertices closest to the root, network
-// vertices must be chosen before router vertices in order to necessarily
-// find all equal-cost paths. We don't do this at this moment, we should add
-// the treatment above codes. -- kunihiro.
-//
-// RFC2328 16.1. (4).
-//
-// This is the method that actually adds the routes. It'll walk the list
-// of nodes in the system, looking for the node corresponding to the router
-// ID of the root of the tree -- that is the router we're building the routes
-// for. It looks for the Ipv4 interface of that node and remembers it. So
-// we are only actually adding routes to that one node at the root of the SPF
-// tree.
-//
-// We're going to pop of a pointer to every vertex in the tree except the
-// root in order of distance from the root. For each of the vertices, we call
-// SPFIntraAddRouter (). Down in SPFIntraAddRouter, we look at all of the
-// point-to-point Global Router Link Records (the links to nodes adjacent to
-// the node represented by the vertex). We add a route to the IP address
-// specified by the m_linkData field of each of those link records. This will
-// be the *local* IP address associated with the interface attached to the
-// link. We use the outbound interface and next hop information present in
-// the vertex <v> which have possibly been inherited from the root.
-//
-// To summarize, we're going to look at the node represented by <v> and loop
-// through its point-to-point links, adding a *host* route to the local IP
-// address (at the <v> side) for each of those links.
-//
- SPFIntraAddRouter (v);
-//
-// RFC2328 16.1. (5).
-//
-// Iterate the algorithm by returning to Step 2 until there are no more
-// candidate vertices.
-//
- }
-//
-// Second stage of SPF calculation procedure's
-// NOTYET: ospf_spf_process_stubs (area, area->spf, new_table);
-//
-// We're all done setting the routing information for the node at the root of
-// the SPF tree. Delete all of the vertices and corresponding resources. Go
-// possibly do it again for the next router.
-//
- delete m_spfroot;
- m_spfroot = 0;
-}
-
-//
-// XXX This should probably be a method on Ipv4
-//
-// Return the interface index corresponding to a given IP address
-//
- uint32_t
-GlobalRouteManagerImpl::FindOutgoingInterfaceId (Ipv4Address a)
-{
-//
-// We have an IP address <a> and a vertex ID of the root of the SPF tree.
-// The question is what interface index does this address correspond to.
-// The answer is a little complicated since we have to find a pointer to
-// the node corresponding to the vertex ID, find the Ipv4 interface on that
-// node in order to iterate the interfaces and find the one corresponding to
-// the address in question.
-//
- Ipv4Address routerId = m_spfroot->GetVertexId ();
-//
-// Walk the list of nodes in the system looking for the one corresponding to
-// the node at the root of the SPF tree. This is the node for which we are
-// building the routing table.
-//
- std::vector<Ptr<Node> >::iterator i = NodeList::Begin ();
- for (; i != NodeList::End (); i++)
- {
- Ptr<Node> node = *i;
-
- Ptr<GlobalRouter> rtr =
- node->QueryInterface<GlobalRouter> (GlobalRouter::iid);
-//
-// If the node doesn't have a GlobalRouter interface it can't be the one
-// we're interested in.
-//
- if (rtr == 0)
- {
- continue;
- }
-
- if (rtr->GetRouterId () == routerId)
- {
-//
-// This is the node we're building the routing table for. We're going to need
-// the Ipv4 interface to look for the ipv4 interface index. Since this node
-// is participating in routing IP version 4 packets, it certainly must have
-// an Ipv4 interface.
-//
- Ptr<Ipv4> ipv4 = node->QueryInterface<Ipv4> (Ipv4::iid);
- NS_ASSERT_MSG (ipv4,
- "GlobalRouteManagerImpl::FindOutgoingInterfaceId (): "
- "QI for <Ipv4> interface failed");
-//
-// Look through the interfaces on this node for one that has the IP address
-// we're looking for. If we find one, return the corresponding interface
-// index.
-//
- for (uint32_t i = 0; i < ipv4->GetNInterfaces (); i++)
- {
- if (ipv4->GetAddress (i) == a)
- {
- NS_DEBUG (
- "GlobalRouteManagerImpl::FindOutgoingInterfaceId (): "
- "Interface match for " << a);
- return i;
- }
- }
- }
- }
-//
-// Couldn't find it.
-//
- return 0;
-}
-
-//
-// 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.
-//
- void
-GlobalRouteManagerImpl::SPFIntraAddRouter (SPFVertex* v)
-{
- NS_DEBUG ("GlobalRouteManagerImpl::SPFIntraAddRouter ()");
-
- NS_ASSERT_MSG (m_spfroot,
- "GlobalRouteManagerImpl::SPFIntraAddRouter (): Root pointer not set");
-//
-// The root of the Shortest Path First tree is the router to which we are
-// going to write the actual routing table entries. The vertex corresponding
-// to this router has a vertex ID which is the router ID of that node. We're
-// going to use this ID to discover which node it is that we're actually going
-// to update.
-//
- Ipv4Address routerId = m_spfroot->GetVertexId ();
-
- NS_DEBUG ("GlobalRouteManagerImpl::SPFIntraAddRouter (): "
- "Vertex ID = " << routerId);
-//
-// We need to walk the list of nodes looking for the one that has the router
-// ID corresponding to the root vertex. This is the one we're going to write
-// the routing information to.
-//
- std::vector<Ptr<Node> >::iterator i = NodeList::Begin ();
- for (; i != NodeList::End (); i++)
- {
- Ptr<Node> node = *i;
-//
-// The router ID is accessible through the GlobalRouter interface, so we need
-// to QI for that interface. If there's no GlobalRouter interface, the node
-// in question cannot be the router we want, so we continue.
-//
- Ptr<GlobalRouter> rtr =
- node->QueryInterface<GlobalRouter> (GlobalRouter::iid);
-
- if (rtr == 0)
- {
- NS_DEBUG ("GlobalRouteManagerImpl::SPFIntraAddRouter (): "
- "No GlobalRouter interface on node " << node->GetId ());
- continue;
- }
-//
-// If the router ID of the current node is equal to the router ID of the
-// root of the SPF tree, then this node is the one for which we need to
-// write the routing tables.
-//
- NS_DEBUG ("GlobalRouteManagerImpl::SPFIntraAddRouter (): "
- "Considering router " << rtr->GetRouterId ());
-
- if (rtr->GetRouterId () == routerId)
- {
- NS_DEBUG ("GlobalRouteManagerImpl::SPFIntraAddRouter (): "
- "setting routes for node " << node->GetId ());
-//
-// Routing information is updated using the Ipv4 interface. We need to QI
-// for that interface. If the node is acting as an IP version 4 router, it
-// should absolutely have an Ipv4 interface.
-//
- Ptr<Ipv4> ipv4 = node->QueryInterface<Ipv4> (Ipv4::iid);
- NS_ASSERT_MSG (ipv4,
- "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
- "QI for <Ipv4> interface failed");
-//
-// Get the Global Router Link State Advertisement from the vertex we're
-// adding the routes to. The LSA will have a number of attached Global Router
-// Link Records corresponding to links off of that vertex / node. We're going
-// to be interested in the records corresponding to point-to-point links.
-//
- GlobalRouterLSA *lsa = v->GetLSA ();
- NS_ASSERT_MSG (lsa,
- "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
- "Expected valid LSA in SPFVertex* v");
-
- uint32_t nLinkRecords = lsa->GetNLinkRecords ();
-//
-// Iterate through the link records on the vertex to which we're going to add
-// routes. To make sure we're being clear, we're going to add routing table
-// entries to the tables on the node corresping to the root of the SPF tree.
-// These entries will have routes to the IP addresses we find from looking at
-// the local side of the point-to-point links found on the node described by
-// the vertex <v>.
-//
- for (uint32_t j = 0; j < nLinkRecords; j += 2)
- {
-//
-// We are only concerned about point-to-point links
-//
- GlobalRouterLinkRecord *lr = lsa->GetLinkRecord (j);
- if (lr->GetLinkType () != GlobalRouterLinkRecord::PointToPoint)
- {
- continue;
- }
-
- NS_DEBUG ("GlobalRouteManagerImpl::SPFIntraAddRouter (): "
- " Node " << node->GetId () <<
- " add route to " << lr->GetLinkData () <<
- " using next hop " << v->GetNextHop () <<
- " via interface " << v->GetOutgoingInterfaceId ());
-//
-// Here's why we did all of that work. We're going to add a host route to the
-// host address found in the m_linkData field of the point-to-point link
-// record. In the case of a point-to-point link, this is the local IP address
-// of the node connected to the link. Each of these point-to-point links
-// will correspond to a local interface that has an IP address to which
-// the node at the root of the SPF tree can send packets. The vertex <v>
-// (corresponding to the node that has these links and interfaces) has
-// an m_nextHop address precalculated for us that is the address to which the
-// root node should send packets to be forwarded to these IP addresses.
-// Similarly, the vertex <v> has an m_rootOif (outbound interface index) to
-// which the packets should be send for forwarding.
-//
- ipv4->AddHostRouteTo (lr->GetLinkData (), v->GetNextHop (),
- v->GetOutgoingInterfaceId ());
- }
-//
-// Done adding the routes for the selected node.
-//
- return;
- }
- }
-}
-
-// 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.
-//
-// For now, only one parent (not doing equal-cost multipath)
-//
- void
-GlobalRouteManagerImpl::SPFVertexAddParent (SPFVertex* v)
-{
- v->GetParent ()->AddChild (v);
-}
-
-} // namespace ns3
-
-#ifdef RUN_SELF_TESTS
-
-// ---------------------------------------------------------------------------
-//
-// Unit Tests
-//
-// ---------------------------------------------------------------------------
-
-#include "ns3/test.h"
-
-namespace ns3 {
-
-class GlobalRouterTestNode : public Node
-{
-public:
- GlobalRouterTestNode ();
-
-private:
- virtual void DoAddDevice (Ptr<NetDevice> device) const {};
- virtual TraceResolver *DoCreateTraceResolver (TraceContext const &context);
-};
-
-GlobalRouterTestNode::GlobalRouterTestNode ()
-{
-// Ptr<Ipv4L3Protocol> ipv4 = Create<Ipv4L3Protocol> (this);
-}
-
- TraceResolver*
-GlobalRouterTestNode::DoCreateTraceResolver (TraceContext const &context)
-{
- return 0;
-}
-
-class GlobalRouteManagerImplTest : public Test {
-public:
- GlobalRouteManagerImplTest ();
- virtual ~GlobalRouteManagerImplTest ();
- virtual bool RunTests (void);
-};
-
-GlobalRouteManagerImplTest::GlobalRouteManagerImplTest ()
- : Test ("GlobalRouteManagerImpl")
-{
-}
-
-GlobalRouteManagerImplTest::~GlobalRouteManagerImplTest ()
-{}
-
- bool
-GlobalRouteManagerImplTest::RunTests (void)
-{
- bool ok = true;
-
- CandidateQueue candidate;
-
- for (int i = 0; i < 100; ++i)
- {
- SPFVertex *v = new SPFVertex;
- v->SetDistanceFromRoot (rand () % 100);
- candidate.Push (v);
- }
-
- uint32_t lastDistance = 0;
-
- for (int i = 0; i < 100; ++i)
- {
- SPFVertex *v = candidate.Pop ();
- if (v->GetDistanceFromRoot () < lastDistance)
- {
- ok = false;
- }
- lastDistance = v->GetDistanceFromRoot ();
- delete v;
- v = 0;
- }
-
- // Build fake link state database; four routers (0-3), 3 point-to-point
- // links
- //
- // n0
- // \ link 0
- // \ link 2
- // n2 -------------------------n3
- // /
- // / link 1
- // n1
- //
- // link0: 10.1.1.1/30, 10.1.1.2/30
- // link1: 10.1.2.1/30, 10.1.2.2/30
- // link2: 10.1.3.1/30, 10.1.3.2/30
- //
- // Router 0
- GlobalRouterLinkRecord* lr0 = new GlobalRouterLinkRecord (
- GlobalRouterLinkRecord::PointToPoint,
- "0.0.0.2", // router ID 0.0.0.2
- "10.1.1.1", // local ID
- 1); // metric
-
- GlobalRouterLinkRecord* lr1 = new GlobalRouterLinkRecord (
- GlobalRouterLinkRecord::StubNetwork,
- "10.1.1.1",
- "255.255.255.252",
- 1);
-
- GlobalRouterLSA* lsa0 = new GlobalRouterLSA ();
- lsa0->SetLinkStateId ("0.0.0.0");
- lsa0->SetAdvertisingRouter ("0.0.0.0");
- lsa0->AddLinkRecord (lr0);
- lsa0->AddLinkRecord (lr1);
-
- // Router 1
- GlobalRouterLinkRecord* lr2 = new GlobalRouterLinkRecord (
- GlobalRouterLinkRecord::PointToPoint,
- "0.0.0.2",
- "10.1.2.1",
- 1);
-
- GlobalRouterLinkRecord* lr3 = new GlobalRouterLinkRecord (
- GlobalRouterLinkRecord::StubNetwork,
- "10.1.2.1",
- "255.255.255.252",
- 1);
-
- GlobalRouterLSA* lsa1 = new GlobalRouterLSA ();
- lsa1->SetLinkStateId ("0.0.0.1");
- lsa1->SetAdvertisingRouter ("0.0.0.1");
- lsa1->AddLinkRecord (lr2);
- lsa1->AddLinkRecord (lr3);
-
- // Router 2
- GlobalRouterLinkRecord* lr4 = new GlobalRouterLinkRecord (
- GlobalRouterLinkRecord::PointToPoint,
- "0.0.0.0",
- "10.1.1.2",
- 1);
-
- GlobalRouterLinkRecord* lr5 = new GlobalRouterLinkRecord (
- GlobalRouterLinkRecord::StubNetwork,
- "10.1.1.2",
- "255.255.255.252",
- 1);
-
- GlobalRouterLinkRecord* lr6 = new GlobalRouterLinkRecord (
- GlobalRouterLinkRecord::PointToPoint,
- "0.0.0.1",
- "10.1.2.2",
- 1);
-
- GlobalRouterLinkRecord* lr7 = new GlobalRouterLinkRecord (
- GlobalRouterLinkRecord::StubNetwork,
- "10.1.2.2",
- "255.255.255.252",
- 1);
-
- GlobalRouterLinkRecord* lr8 = new GlobalRouterLinkRecord (
- GlobalRouterLinkRecord::PointToPoint,
- "0.0.0.3",
- "10.1.3.2",
- 1);
-
- GlobalRouterLinkRecord* lr9 = new GlobalRouterLinkRecord (
- GlobalRouterLinkRecord::StubNetwork,
- "10.1.3.2",
- "255.255.255.252",
- 1);
-
- GlobalRouterLSA* lsa2 = new GlobalRouterLSA ();
- lsa2->SetLinkStateId ("0.0.0.2");
- lsa2->SetAdvertisingRouter ("0.0.0.2");
- lsa2->AddLinkRecord (lr4);
- lsa2->AddLinkRecord (lr5);
- lsa2->AddLinkRecord (lr6);
- lsa2->AddLinkRecord (lr7);
- lsa2->AddLinkRecord (lr8);
- lsa2->AddLinkRecord (lr9);
-
- // Router 3
- GlobalRouterLinkRecord* lr10 = new GlobalRouterLinkRecord (
- GlobalRouterLinkRecord::PointToPoint,
- "0.0.0.2",
- "10.1.2.1",
- 1);
-
- GlobalRouterLinkRecord* lr11 = new GlobalRouterLinkRecord (
- GlobalRouterLinkRecord::StubNetwork,
- "10.1.2.1",
- "255.255.255.252",
- 1);
-
- GlobalRouterLSA* lsa3 = new GlobalRouterLSA ();
- lsa3->SetLinkStateId ("0.0.0.3");
- lsa3->SetAdvertisingRouter ("0.0.0.3");
- lsa3->AddLinkRecord (lr10);
- lsa3->AddLinkRecord (lr11);
-
- // Test the database
- GlobalRouteManagerLSDB* srmlsdb = new GlobalRouteManagerLSDB ();
- srmlsdb->Insert (lsa0->GetLinkStateId (), lsa0);
- srmlsdb->Insert (lsa1->GetLinkStateId (), lsa1);
- srmlsdb->Insert (lsa2->GetLinkStateId (), lsa2);
- srmlsdb->Insert (lsa3->GetLinkStateId (), lsa3);
- NS_ASSERT (lsa2 == srmlsdb->GetLSA (lsa2->GetLinkStateId ()));
-
- // next, calculate routes based on the manually created LSDB
- GlobalRouteManagerImpl* srm = new GlobalRouteManagerImpl ();
- srm->DebugUseLsdb (srmlsdb); // manually add in an LSDB
- // Note-- this will succeed without any nodes in the topology
- // because the NodeList is empty
- srm->DebugSPFCalculate (lsa0->GetLinkStateId ()); // node n0
-
- // This delete clears the srm, which deletes the LSDB, which clears
- // all of the LSAs, which each destroys the attached LinkRecords.
- delete srm;
-
- return ok;
-}
-
-// Instantiate this class for the unit tests
-// XXX here we should do some verification of the routes built
-static GlobalRouteManagerImplTest g_globalRouteManagerTest;
-
-} // namespace ns3
-
-#endif
--- a/src/routing/global/global-route-manager-impl.h Fri Aug 03 09:29:57 2007 -0700
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,747 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/*
- * 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
- */
-
-#ifndef GLOBAL_ROUTE_MANAGER_IMPL_H
-#define GLOBAL_ROUTE_MANAGER_IMPL_H
-
-#include <stdint.h>
-#include <list>
-#include <queue>
-#include <map>
-#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;
-
-class CandidateQueue;
-
-/**
- * @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 GlobalRouterLSA
- * @param lsa The Link State Advertisement used for finding initial values.
- */
- SPFVertex(GlobalRouterLSA* 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 GlobalRouterLSA
- * @see GlobalRouter::DiscoverLSAs ()
- * @returns A pointer to the GlobalRouterLSA found by the router represented
- * by this SPFVertex object.
- */
- GlobalRouterLSA* 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 GlobalRouterLSA
- * @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 GlobalRouterLSA.
- */
- void SetLSA (GlobalRouterLSA* 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 Get the interface ID 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 outgoing interface that we're asking for is the interface
- * index on the root node that should be used to start packets along the
- * path to "this" vertex.
- *
- * When initializing the root SPFVertex, the interface ID is determined by
- * examining the Global Router Link Records of the Link State Advertisement
- * generated by the root node's GlobalRouter. These interfaces are used to
- * forward packets off of the root's network down those links. As other
- * vertices are discovered which are further away from the root, they will
- * be accessible down one of the paths begun by a Global Router Link Record.
- *
- * To forward packets to these hosts or networks, the root node must begin
- * the forwarding process by sending the packets to the interface of that
- * first hop. 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, the root node is asking, "which of my local interfaces
- * should I use to get a packet to the network or host represented by 'this'
- * SPFVertex."
- *
- * @see GlobalRouter
- * @see GlobalRouterLSA
- * @see GlobalRouterLinkRecord
- * @returns The interface index to use when forwarding packets to the host
- * or network represented by "this" SPFVertex.
- */
- uint32_t GetOutgoingInterfaceId (void) const;
-
-/**
- * @brief Set the interface ID 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 outgoing interface that we're asking for is the interface
- * index on the root node that should be used to start packets along the
- * path to "this" vertex.
- *
- * When initializing the root SPFVertex, the interface ID is determined by
- * examining the Global Router Link Records of the Link State Advertisement
- * generated by the root node's GlobalRouter. These interfaces are used to
- * forward packets off of the root's network down those links. As other
- * vertices are discovered which are further away from the root, they will
- * be accessible down one of the paths begun by a Global Router Link Record.
- *
- * To forward packets to these hosts or networks, the root node must begin
- * the forwarding process by sending the packets to the interface of that
- * first hop. 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 letting the root node know which of its local
- * interfaces it should use to get a packet to the network or host represented
- * by "this" SPFVertex.
- *
- * @see GlobalRouter
- * @see GlobalRouterLSA
- * @see GlobalRouterLinkRecord
- * @param id The interface index to use when forwarding packets to the host or
- * network represented by "this" SPFVertex.
- */
- void SetOutgoingInterfaceId (uint32_t id);
-
-/**
- * @brief Get the IP address 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, the root node is asking, "which router should I send a
- * packet to in order to get that packet to the network or host represented
- * by 'this' SPFVertex."
- *
- * @see GlobalRouter
- * @see GlobalRouterLSA
- * @see GlobalRouterLinkRecord
- * @returns The IP address to use when forwarding packets to the host
- * or network represented by "this" SPFVertex.
- */
- Ipv4Address GetNextHop (void) const;
-
-/**
- * @brief Set the IP address 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 router it should send
- * should I send a packet to in order to get that packet to the network or
- * host represented by 'this' SPFVertex."
- *
- * @see GlobalRouter
- * @see GlobalRouterLSA
- * @see GlobalRouterLinkRecord
- * @param nextHop The IP address to use when forwarding packets to the host
- * or network represented by "this" SPFVertex.
- */
- void SetNextHop (Ipv4Address nextHop);
-
-/**
- * @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).
- *
- * @returns A pointer to the SPFVertex that is the parent of "this" SPFVertex
- * in the SPF tree.
- */
- SPFVertex* GetParent (void) 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 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);
-
-private:
- VertexType m_vertexType;
- Ipv4Address m_vertexId;
- GlobalRouterLSA* m_lsa;
- uint32_t m_distanceFromRoot;
- uint32_t m_rootOif;
- Ipv4Address m_nextHop;
- SPFVertex* m_parent;
- typedef std::list<SPFVertex*> ListOfSPFVertex_t;
- ListOfSPFVertex_t m_children;
-
-/**
- * @brief The SPFVertex copy construction is disallowed. There's no need for
- * it and a compiler provided shallow copy would be wrong.
- */
- 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.
- */
- SPFVertex& operator= (SPFVertex& v);
-};
-
-/**
- * @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 GlobalRouterLSA given as parameters are converted
- * to an STL pair and are inserted into the database map.
- *
- * @see GlobalRouterLSA
- * @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, GlobalRouterLSA* lsa);
-
-/**
- * @brief Look up the Link State Advertisement associated with the given
- * IP Address.
- * @internal
- *
- * The database map is searched for the given IPV4 address and corresponding
- * GlobalRouterLSA is returned.
- *
- * @see GlobalRouterLSA
- * @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.
- */
- GlobalRouterLSA* GetLSA (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 GlobalRouterLSA
- * @see SPFVertex
- */
- void Initialize ();
-
-private:
- typedef std::map<Ipv4Address, GlobalRouterLSA*> LSDBMap_t;
- typedef std::pair<Ipv4Address, GlobalRouterLSA*> LSDBPair_t;
-
- LSDBMap_t m_database;
-/**
- * @brief GlobalRouteManagerLSDB copy construction is disallowed. There's no
- * need for it and a compiler provided shallow copy would be wrong.
- */
- 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.
- */
- 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 Select which nodes in the system are to be router nodes and
- * aggregate the appropriate interfaces onto those nodes.
- * @internal
- *
- */
- virtual void SelectRouterNodes ();
-
-/**
- * @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
- */
- 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.
- */
- 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.
- */
- GlobalRouteManagerImpl& operator= (GlobalRouteManagerImpl& srmi);
-
- SPFVertex* m_spfroot;
- GlobalRouteManagerLSDB* m_lsdb;
- void SPFCalculate (Ipv4Address root);
- void SPFNext (SPFVertex*, CandidateQueue&);
- int SPFNexthopCalculation (SPFVertex* v, SPFVertex* w,
- GlobalRouterLinkRecord* l, uint32_t distance);
- void SPFVertexAddParent (SPFVertex* v);
- GlobalRouterLinkRecord* SPFGetNextLink (SPFVertex* v, SPFVertex* w,
- GlobalRouterLinkRecord* prev_link);
- void SPFIntraAddRouter (SPFVertex* v);
- uint32_t FindOutgoingInterfaceId (Ipv4Address a);
-};
-
-} // namespace ns3
-
-#endif /* GLOBAL_ROUTE_MANAGER_IMPL_H */
--- a/src/routing/global/global-route-manager.cc Fri Aug 03 09:29:57 2007 -0700
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,68 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/*
- * 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
- */
-
-#include "ns3/assert.h"
-#include "ns3/debug.h"
-#include "ns3/simulation-singleton.h"
-#include "global-route-manager.h"
-#include "global-route-manager-impl.h"
-
-namespace ns3 {
-
-// ---------------------------------------------------------------------------
-//
-// GlobalRouteManager Implementation
-//
-// ---------------------------------------------------------------------------
-
- void
-GlobalRouteManager::PopulateRoutingTables ()
-{
- SelectRouterNodes ();
- BuildGlobalRoutingDatabase ();
- InitializeRoutes ();
-}
-
- void
-GlobalRouteManager::SelectRouterNodes ()
-{
- SimulationSingleton<GlobalRouteManagerImpl>::Get ()->
- SelectRouterNodes ();
-}
-
- void
-GlobalRouteManager::BuildGlobalRoutingDatabase ()
-{
- SimulationSingleton<GlobalRouteManagerImpl>::Get ()->
- BuildGlobalRoutingDatabase ();
-}
-
- void
-GlobalRouteManager::InitializeRoutes ()
-{
- SimulationSingleton<GlobalRouteManagerImpl>::Get ()->
- InitializeRoutes ();
-}
-
- uint32_t
-GlobalRouteManager::AllocateRouterId ()
-{
- static uint32_t routerId = 0;
- return routerId++;
-}
-
-
-} // namespace ns3
--- a/src/routing/global/global-route-manager.h Fri Aug 03 09:29:57 2007 -0700
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,93 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/*
- * 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
- */
-
-#ifndef GLOBAL_ROUTE_MANAGER_H
-#define GLOBAL_ROUTE_MANAGER_H
-
-namespace ns3 {
-
-/**
- * @brief A global global router
- *
- * 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 GlobalRouteManager
-{
-public:
-/**
- * @brief Build a routing database and initialize the routing tables of
- * the nodes in the simulation.
- *
- * All this function does is call BuildGlobalRoutingDatabase () and
- * InitializeRoutes ().
- *
- * @see BuildGlobalRoutingDatabase ();
- * @see InitializeRoutes ();
- */
- static void PopulateRoutingTables ();
-
-/**
- * @brief Allocate a 32-bit router ID from monotonically increasing counter.
- */
- static uint32_t AllocateRouterId ();
-
-private:
-/**
- * @brief Select which nodes in the system are to be router nodes and
- * aggregate the appropriate interfaces onto those nodes.
- * @internal
- *
- */
- static void SelectRouterNodes ();
-
-/**
- * @brief Build the routing database by gathering Link State Advertisements
- * from each node exporting a GlobalRouter interface.
- * @internal
- *
- */
- static void BuildGlobalRoutingDatabase ();
-
-/**
- * @brief Compute routes using a Dijkstra SPF computation and populate
- * per-node forwarding tables
- * @internal
- */
- static void InitializeRoutes ();
-
-/**
- * @brief Global Route Manager copy construction is disallowed. There's no
- * need for it and a compiler provided shallow copy would be wrong.
- *
- */
- GlobalRouteManager (GlobalRouteManager& srm);
-
-/**
- * @brief Global Router copy assignment operator is disallowed. There's no
- * need for it and a compiler provided shallow copy would be wrong.
- */
- GlobalRouteManager& operator= (GlobalRouteManager& srm);
-};
-
-} // namespace ns3
-
-#endif /* GLOBAL_ROUTE_MANAGER_H */
--- a/src/routing/global/global-router-interface.cc Fri Aug 03 09:29:57 2007 -0700
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,588 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/*
- * 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
- */
-
-#include "ns3/debug.h"
-#include "ns3/assert.h"
-#include "ns3/channel.h"
-#include "ns3/net-device.h"
-#include "ns3/internet-node.h"
-#include "ns3/ipv4.h"
-#include "global-router-interface.h"
-
-NS_DEBUG_COMPONENT_DEFINE ("GlobalRouter");
-
-namespace ns3 {
-
-// ---------------------------------------------------------------------------
-//
-// GlobalRouterLinkRecord Implementation
-//
-// ---------------------------------------------------------------------------
-
-GlobalRouterLinkRecord::GlobalRouterLinkRecord ()
-:
- m_linkId ("0.0.0.0"),
- m_linkData ("0.0.0.0"),
- m_linkType (Unknown),
- m_metric (0)
-{
- NS_DEBUG("GlobalRouterLinkRecord::GlobalRouterLinkRecord ()");
-}
-
-GlobalRouterLinkRecord::GlobalRouterLinkRecord (
- LinkType linkType,
- Ipv4Address linkId,
- Ipv4Address linkData,
- uint32_t metric)
-:
- m_linkId (linkId),
- m_linkData (linkData),
- m_linkType (linkType),
- m_metric (metric)
-{
- NS_DEBUG("GlobalRouterLinkRecord::GlobalRouterLinkRecord (" <<
- linkType << ", " << linkId << ", " << linkData << ", " << metric << ")");
-}
-
-GlobalRouterLinkRecord::~GlobalRouterLinkRecord ()
-{
- NS_DEBUG("GlobalRouterLinkRecord::~GlobalRouterLinkRecord ()");
-}
-
- Ipv4Address
-GlobalRouterLinkRecord::GetLinkId (void) const
-{
- NS_DEBUG("GlobalRouterLinkRecord::GetLinkId ()");
- return m_linkId;
-}
-
- void
-GlobalRouterLinkRecord::SetLinkId (Ipv4Address addr)
-{
- NS_DEBUG("GlobalRouterLinkRecord::SetLinkId ()");
- m_linkId = addr;
-}
-
- Ipv4Address
-GlobalRouterLinkRecord::GetLinkData (void) const
-{
- NS_DEBUG("GlobalRouterLinkRecord::GetLinkData ()");
- return m_linkData;
-}
-
- void
-GlobalRouterLinkRecord::SetLinkData (Ipv4Address addr)
-{
- NS_DEBUG("GlobalRouterLinkRecord::SetLinkData ()");
- m_linkData = addr;
-}
-
- GlobalRouterLinkRecord::LinkType
-GlobalRouterLinkRecord::GetLinkType (void) const
-{
- NS_DEBUG("GlobalRouterLinkRecord::GetLinkType ()");
- return m_linkType;
-}
-
- void
-GlobalRouterLinkRecord::SetLinkType (
- GlobalRouterLinkRecord::LinkType linkType)
-{
- NS_DEBUG("GlobalRouterLinkRecord::SetLinkType ()");
- m_linkType = linkType;
-}
-
- uint32_t
-GlobalRouterLinkRecord::GetMetric (void) const
-{
- NS_DEBUG("GlobalRouterLinkRecord::GetMetric ()");
- return m_metric;
-}
-
- void
-GlobalRouterLinkRecord::SetMetric (uint32_t metric)
-{
- NS_DEBUG("GlobalRouterLinkRecord::SetMetric ()");
- m_metric = metric;
-}
-
-// ---------------------------------------------------------------------------
-//
-// GlobalRouterLSA Implementation
-//
-// ---------------------------------------------------------------------------
-
-GlobalRouterLSA::GlobalRouterLSA()
- :
- m_linkStateId("0.0.0.0"),
- m_advertisingRtr("0.0.0.0"),
- m_linkRecords(),
- m_status(GlobalRouterLSA::LSA_SPF_NOT_EXPLORED)
-{
- NS_DEBUG("GlobalRouterLSA::GlobalRouterLSA ()");
-}
-
-GlobalRouterLSA::GlobalRouterLSA (
- GlobalRouterLSA::SPFStatus status,
- Ipv4Address linkStateId,
- Ipv4Address advertisingRtr)
-:
- m_linkStateId(linkStateId),
- m_advertisingRtr(advertisingRtr),
- m_linkRecords(),
- m_status(status)
-{
- NS_DEBUG("GlobalRouterLSA::GlobalRouterLSA (" << status << ", " <<
- linkStateId << ", " << advertisingRtr << ")");
-}
-
-GlobalRouterLSA::GlobalRouterLSA (GlobalRouterLSA& lsa)
- : m_linkStateId(lsa.m_linkStateId), m_advertisingRtr(lsa.m_advertisingRtr),
- m_status(lsa.m_status)
-{
- NS_ASSERT_MSG(IsEmpty(),
- "GlobalRouterLSA::GlobalRouterLSA (): Non-empty LSA in constructor");
- CopyLinkRecords (lsa);
-}
-
- GlobalRouterLSA&
-GlobalRouterLSA::operator= (const GlobalRouterLSA& lsa)
-{
- m_linkStateId = lsa.m_linkStateId;
- m_advertisingRtr = lsa.m_advertisingRtr;
- m_status = lsa.m_status;
-
- ClearLinkRecords ();
- CopyLinkRecords (lsa);
- return *this;
-}
-
- void
-GlobalRouterLSA::CopyLinkRecords (const GlobalRouterLSA& lsa)
-{
- for (ListOfLinkRecords_t::const_iterator i = lsa.m_linkRecords.begin ();
- i != lsa.m_linkRecords.end ();
- i++)
- {
- GlobalRouterLinkRecord *pSrc = *i;
- GlobalRouterLinkRecord *pDst = new GlobalRouterLinkRecord;
-
- pDst->SetLinkType (pSrc->GetLinkType ());
- pDst->SetLinkId (pSrc->GetLinkId ());
- pDst->SetLinkData (pSrc->GetLinkData ());
-
- m_linkRecords.push_back(pDst);
- pDst = 0;
- }
-}
-
-GlobalRouterLSA::~GlobalRouterLSA()
-{
- NS_DEBUG("GlobalRouterLSA::~GlobalRouterLSA ()");
- ClearLinkRecords ();
-}
-
- void
-GlobalRouterLSA::ClearLinkRecords(void)
-{
- for ( ListOfLinkRecords_t::iterator i = m_linkRecords.begin ();
- i != m_linkRecords.end ();
- i++)
- {
- NS_DEBUG("GlobalRouterLSA::ClearLinkRecords (): free link record");
-
- GlobalRouterLinkRecord *p = *i;
- delete p;
- p = 0;
-
- *i = 0;
- }
- NS_DEBUG("GlobalRouterLSA::ClearLinkRecords(): clear list");
- m_linkRecords.clear();
-}
-
- uint32_t
-GlobalRouterLSA::AddLinkRecord (GlobalRouterLinkRecord* lr)
-{
- m_linkRecords.push_back (lr);
- return m_linkRecords.size ();
-}
-
- uint32_t
-GlobalRouterLSA::GetNLinkRecords (void) const
-{
- return m_linkRecords.size ();
-}
-
- GlobalRouterLinkRecord *
-GlobalRouterLSA::GetLinkRecord (uint32_t n) const
-{
- uint32_t j = 0;
- for ( ListOfLinkRecords_t::const_iterator i = m_linkRecords.begin ();
- i != m_linkRecords.end ();
- i++, j++)
- {
- if (j == n)
- {
- return *i;
- }
- }
- NS_ASSERT_MSG(false, "GlobalRouterLSA::GetLinkRecord (): invalid index");
- return 0;
-}
-
- bool
-GlobalRouterLSA::IsEmpty (void) const
-{
- return m_linkRecords.size () == 0;
-}
-
- Ipv4Address
-GlobalRouterLSA::GetLinkStateId (void) const
-{
- return m_linkStateId;
-}
-
- void
-GlobalRouterLSA::SetLinkStateId (Ipv4Address addr)
-{
- m_linkStateId = addr;
-}
-
- Ipv4Address
-GlobalRouterLSA::GetAdvertisingRouter (void) const
-{
- return m_advertisingRtr;
-}
-
- void
-GlobalRouterLSA::SetAdvertisingRouter (Ipv4Address addr)
-{
- m_advertisingRtr = addr;
-}
-
- GlobalRouterLSA::SPFStatus
-GlobalRouterLSA::GetStatus (void) const
-{
- return m_status;
-}
-
- void
-GlobalRouterLSA::SetStatus (GlobalRouterLSA::SPFStatus status)
-{
- m_status = status;
-}
-
- void
-GlobalRouterLSA::Print (std::ostream &os) const
-{
- os << "m_linkStateId = " << m_linkStateId << std::endl <<
- "m_advertisingRtr = " << m_advertisingRtr << std::endl;
-
- for ( ListOfLinkRecords_t::const_iterator i = m_linkRecords.begin ();
- i != m_linkRecords.end ();
- i++)
- {
- GlobalRouterLinkRecord *p = *i;
- os << "----------" << std::endl;
- os << "m_linkId = " << p->GetLinkId () << std::endl;
- os << "m_linkData = " << p->GetLinkData () << std::endl;
- }
-}
-
-std::ostream& operator<< (std::ostream& os, GlobalRouterLSA& lsa)
-{
- lsa.Print (os);
- return os;
-}
-
-// ---------------------------------------------------------------------------
-//
-// GlobalRouter Implementation
-//
-// ---------------------------------------------------------------------------
-
-const InterfaceId GlobalRouter::iid =
- MakeInterfaceId ("GlobalRouter", Object::iid);
-
-GlobalRouter::GlobalRouter (Ptr<Node> node)
- : m_node(node), m_LSAs()
-{
- NS_DEBUG("GlobalRouter::GlobalRouter ()");
- SetInterfaceId (GlobalRouter::iid);
- m_routerId.Set(GlobalRouteManager::AllocateRouterId ());
-}
-
-GlobalRouter::~GlobalRouter ()
-{
- NS_DEBUG("GlobalRouter::~GlobalRouter ()");
- ClearLSAs();
-}
-
- void
-GlobalRouter::ClearLSAs ()
-{
- NS_DEBUG("GlobalRouter::ClearLSAs ()");
-
- for ( ListOfLSAs_t::iterator i = m_LSAs.begin ();
- i != m_LSAs.end ();
- i++)
- {
- NS_DEBUG("GlobalRouter::ClearLSAs (): free LSA");
-
- GlobalRouterLSA *p = *i;
- delete p;
- p = 0;
-
- *i = 0;
- }
- NS_DEBUG("GlobalRouter::ClearLSAs (): clear list");
- m_LSAs.clear();
-}
-
- Ipv4Address
-GlobalRouter::GetRouterId (void) const
-{
- return m_routerId;
-}
-
-//
-// Go out and discover any adjacent routers and build the Link State
-// Advertisements that reflect them and their associated networks.
-//
- uint32_t
-GlobalRouter::DiscoverLSAs (void)
-{
- NS_DEBUG("GlobalRouter::DiscoverLSAs ()");
- NS_ASSERT_MSG(m_node,
- "GlobalRouter::DiscoverLSAs (): <Node> interface not set");
-
- ClearLSAs ();
-//
-// We're aggregated to a node. We need to ask the node for a pointer to its
-// Ipv4 interface. This is where the information regarding the attached
-// interfaces lives.
-//
- Ptr<Ipv4> ipv4Local = m_node->QueryInterface<Ipv4> (Ipv4::iid);
- NS_ASSERT_MSG(ipv4Local,
- "GlobalRouter::DiscoverLSAs (): QI for <Ipv4> interface failed");
-//
-// We are, for now at least, only going to report RouterLSAs in this method.
-// What this means is that there is going to be one advertisement with some
-// number of link records. This means that GetNumLSAs will actually always
-// return exactly one.
-//
- GlobalRouterLSA *pLSA = new GlobalRouterLSA;
- pLSA->SetLinkStateId (m_routerId);
- pLSA->SetAdvertisingRouter (m_routerId);
- pLSA->SetStatus (GlobalRouterLSA::LSA_SPF_NOT_EXPLORED);
-//
-// We need to ask the node for the number of net devices attached. This isn't
-// necessarily equal to the number of links to adjacent nodes (other routers)
-// as the number of devices may include those for stub networks (e.g.,
-// ethernets, etc.). So we have to walk through the list of net devices and
-// pay attention to those that are directly connected to another router through
-// a point-to-point channel.
-//
- uint32_t numDevices = m_node->GetNDevices();
- NS_DEBUG("GlobalRouter::DiscoverLSAs (): numDevices = " << numDevices);
-//
-// Loop through the devices looking for those connected to a point-to-point
-// channel.
-//
- for (uint32_t i = 0; i < numDevices; ++i)
- {
- Ptr<NetDevice> ndLocal = m_node->GetDevice(i);
-
- if (!ndLocal->IsPointToPoint ())
- {
- NS_DEBUG("GlobalRouter::DiscoverLSAs (): non-point-to-point device");
- continue;
- }
-
- NS_DEBUG("GlobalRouter::DiscoverLSAs (): Point-to-point device");
-//
-// Now, we have to find the Ipv4 interface whose netdevice is the one we
-// just found. This is still the IP on the local side of the channel. There
-// is a function to do this used down in the guts of the stack, but it's not
-// exported so we had to whip up an equivalent.
-//
- uint32_t ifIndexLocal = FindIfIndexForDevice(m_node, ndLocal);
-//
-// Now that we have the Ipv4 interface index, we can get the address and mask
-// we need.
-//
- Ipv4Address addrLocal = ipv4Local->GetAddress(ifIndexLocal);
- Ipv4Mask maskLocal = ipv4Local->GetNetworkMask(ifIndexLocal);
- NS_DEBUG("Working with local address " << addrLocal);
-//
-// Now, we're going to walk over to the remote net device on the other end of
-// the point-to-point channel we now know we have. This is where our adjacent
-// router (to use OSPF lingo) is running.
-//
- Ptr<Channel> ch = ndLocal->GetChannel();
- Ptr<NetDevice> ndRemote = GetAdjacent(ndLocal, ch);
-//
-// The adjacent net device is aggregated to a node. We need to ask that net
-// device for its node, then ask that node for its Ipv4 interface.
-//
- Ptr<Node> nodeRemote = ndRemote->GetNode();
- Ptr<Ipv4> ipv4Remote = nodeRemote->QueryInterface<Ipv4> (Ipv4::iid);
- NS_ASSERT_MSG(ipv4Remote,
- "GlobalRouter::DiscoverLSAs (): QI for remote <Ipv4> failed");
-//
-// Per the OSPF spec, we're going to need the remote router ID, so we might as
-// well get it now.
-//
- Ptr<GlobalRouter> srRemote =
- nodeRemote->QueryInterface<GlobalRouter> (GlobalRouter::iid);
- NS_ASSERT_MSG(srRemote,
- "GlobalRouter::DiscoverLSAs (): QI for remote <GlobalRouter> failed");
- Ipv4Address rtrIdRemote = srRemote->GetRouterId();
- NS_DEBUG("Working with remote router " << rtrIdRemote);
-//
-// Now, just like we did above, we need to get the IP interface index for the
-// net device on the other end of the point-to-point channel.
-//
- uint32_t ifIndexRemote = FindIfIndexForDevice(nodeRemote, ndRemote);
-//
-// Now that we have the Ipv4 interface, we can get the (remote) address and
-// mask we need.
-//
- Ipv4Address addrRemote = ipv4Remote->GetAddress(ifIndexRemote);
- Ipv4Mask maskRemote = ipv4Remote->GetNetworkMask(ifIndexRemote);
- NS_DEBUG("Working with remote address " << addrRemote);
-//
-// Now we can fill out the link records for this link. There are always two
-// link records; the first is a point-to-point record describing the link and
-// the second is a stub network record with the network number.
-//
- GlobalRouterLinkRecord *plr = new GlobalRouterLinkRecord;
- plr->SetLinkType (GlobalRouterLinkRecord::PointToPoint);
- plr->SetLinkId (rtrIdRemote);
- plr->SetLinkData (addrLocal);
- pLSA->AddLinkRecord(plr);
- plr = 0;
-
- plr = new GlobalRouterLinkRecord;
- plr->SetLinkType (GlobalRouterLinkRecord::StubNetwork);
- plr->SetLinkId (addrRemote);
- plr->SetLinkData (Ipv4Address(maskRemote.GetHostOrder())); // Frown
- pLSA->AddLinkRecord(plr);
- plr = 0;
- }
-//
-// The LSA goes on a list of LSAs in case we want to begin exporting other
-// kinds of advertisements (than Router LSAs).
- m_LSAs.push_back (pLSA);
- NS_DEBUG(*pLSA);
- return m_LSAs.size ();
-}
-
- uint32_t
-GlobalRouter::GetNumLSAs (void) const
-{
- NS_DEBUG("GlobalRouter::GetNumLSAs ()");
- return m_LSAs.size ();
-}
-
-//
-// Get the nth link state advertisement from this router.
-//
- bool
-GlobalRouter::GetLSA (uint32_t n, GlobalRouterLSA &lsa) const
-{
- NS_ASSERT_MSG(lsa.IsEmpty(), "GlobalRouter::GetLSA (): Must pass empty LSA");
-//
-// All of the work was done in GetNumLSAs. All we have to do here is to
-// walk the list of link state advertisements created there and return the
-// one the client is interested in.
-//
- ListOfLSAs_t::const_iterator i = m_LSAs.begin ();
- uint32_t j = 0;
-
- for (; i != m_LSAs.end (); i++, j++)
- {
- if (j == n)
- {
- GlobalRouterLSA *p = *i;
- lsa = *p;
- return true;
- }
- }
-
- return false;
-}
-
-//
-// Link through the given channel and find the net device that's on the
-// other end. This only makes sense with a point-to-point channel.
-//
- Ptr<NetDevice>
-GlobalRouter::GetAdjacent(Ptr<NetDevice> nd, Ptr<Channel> ch) const
-{
-
- uint32_t nDevices = ch->GetNDevices();
- NS_ASSERT_MSG(nDevices == 2,
- "GlobalRouter::GetAdjacent (): Channel with other than two devices");
-//
-// This is a point to point channel with two endpoints. Get both of them.
-//
- Ptr<NetDevice> nd1 = ch->GetDevice(0);
- Ptr<NetDevice> nd2 = ch->GetDevice(1);
-//
-// One of the endpoints is going to be "us" -- that is the net device attached
-// to the node on which we're running -- i.e., "nd". The other endpoint (the
-// one to which we are connected via the channel) is the adjacent router.
-//
- if (nd1 == nd)
- {
- return nd2;
- }
- else if (nd2 == nd)
- {
- return nd1;
- }
- else
- {
- NS_ASSERT_MSG(false,
- "GlobalRouter::GetAdjacent (): Wrong or confused channel?");
- return 0;
- }
-}
-
-//
-// Given a node and a net device, find the IPV4 interface index that
-// corresponds to that net device.
-//
- uint32_t
-GlobalRouter::FindIfIndexForDevice(Ptr<Node> node, Ptr<NetDevice> nd) const
-{
- Ptr<Ipv4> ipv4 = node->QueryInterface<Ipv4> (Ipv4::iid);
- NS_ASSERT_MSG(ipv4, "QI for <Ipv4> interface failed");
- for (uint32_t i = 0; i < ipv4->GetNInterfaces(); ++i )
- {
- if (ipv4->GetNetDevice(i) == nd)
- {
- return i;
- }
- }
-
- NS_ASSERT_MSG(0, "Cannot find interface for device");
- return 0;
-}
-
-} // namespace ns3
--- a/src/routing/global/global-router-interface.h Fri Aug 03 09:29:57 2007 -0700
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,580 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/*
- * 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
- */
-
-#ifndef GLOBAL_ROUTER_INTERFACE_H
-#define GLOBAL_ROUTER_INTERFACE_H
-
-#include <stdint.h>
-#include <list>
-#include "ns3/object.h"
-#include "ns3/ptr.h"
-#include "ns3/node.h"
-#include "ns3/channel.h"
-#include "ns3/ipv4-address.h"
-#include "ns3/global-route-manager.h"
-
-namespace ns3 {
-
-/**
- * @brief A single link record for a link state advertisement.
- *
- * The GlobalRouterLinkRecord is modeled after the OSPF link record field of
- * a Link State Advertisement. Right now we will only see two types of link
- * records corresponding to a stub network and a point-to-point link (channel).
- */
-class GlobalRouterLinkRecord
-{
-public:
-/**
- * @enum LinkType
- * @brief Enumeration of the possible types of Global Router Link Records.
- *
- * These values are defined in the OSPF spec. We currently only use
- * PointToPoint and StubNetwork types.
- */
- enum LinkType {
- Unknown = 0, /**< Uninitialized Link Record */
- PointToPoint, /**< Record representing a point to point channel */
- TransitNetwork, /**< Unused -- for future OSPF compatibility */
- StubNetwork, /**< Record represents a leaf node network */
- VirtualLink /**< Unused -- for future OSPF compatibility */
- };
-
-/**
- * @brief Construct an empty ("uninitialized") Global Router Link Record.
- *
- * The Link ID and Link Data Ipv4 addresses are set to "0.0.0.0";
- * The Link Type is set to Unknown;
- * The metric is set to 0.
- */
- GlobalRouterLinkRecord ();
-
-/**
- * Construct an initialized Global Router Link Record.
- *
- * @param linkType The type of link record to construct.
- * @param linkId The link ID for the record.
- * @param linkData The link data field for the record.
- * @param metric The metric field for the record.
- * @see LinkType
- * @see SetLinkId
- * @see SetLinkData
- */
- GlobalRouterLinkRecord (
- LinkType linkType,
- Ipv4Address linkId,
- Ipv4Address linkData,
- uint32_t metric);
-
-/**
- * @brief Destroy a Global Router Link Record.
- *
- * Currently does nothing. Here as a placeholder only.
- */
- ~GlobalRouterLinkRecord ();
-
-/**
- * Get the Link ID field of the Global Router Link Record.
- *
- * For an OSPF type 1 link (PointToPoint) the Link ID will be the Router ID
- * of the neighboring router.
- *
- * For an OSPF type 3 link (StubNetwork), the Link ID will be the adjacent
- * neighbor's IP address
- *
- * @returns The Ipv4Address corresponding to the Link ID field of the record.
- */
- Ipv4Address GetLinkId(void) const;
-
-/**
- * @brief Set the Link ID field of the Global Router Link Record.
- *
- * For an OSPF type 1 link (PointToPoint) the Link ID must be the Router ID
- * of the neighboring router.
- *
- * For an OSPF type 3 link (StubNetwork), the Link ID must be the adjacent
- * neighbor's IP address
- *
- * @param addr An Ipv4Address to store in the Link ID field of the record.
- */
- void SetLinkId(Ipv4Address addr);
-
-/**
- * @brief Get the Link Data field of the Global Router Link Record.
- *
- * For an OSPF type 1 link (PointToPoint) the Link Data will be the IP
- * address of the node of the local side of the link.
- *
- * For an OSPF type 3 link (StubNetwork), the Link Data will be the
- * network mask
- *
- * @returns The Ipv4Address corresponding to the Link Data field of the record.
- */
- Ipv4Address GetLinkData(void) const;
-
-/**
- * @brief Set the Link Data field of the Global Router Link Record.
- *
- * For an OSPF type 1 link (PointToPoint) the Link Data must be the IP
- * address of the node of the local side of the link.
- *
- * For an OSPF type 3 link (StubNetwork), the Link Data must be set to the
- * network mask
- *
- * @param addr An Ipv4Address to store in the Link Data field of the record.
- */
- void SetLinkData(Ipv4Address addr);
-
-/**
- * @brief Get the Link Type field of the Global Router Link Record.
- *
- * The Link Type describes the kind of link a given record represents. The
- * values are defined by OSPF.
- *
- * @see LinkType
- * @returns The LinkType of the current Global Router Link Record.
- */
- LinkType GetLinkType(void) const;
-
-/**
- * @brief Set the Link Type field of the Global Router Link Record.
- *
- * The Link Type describes the kind of link a given record represents. The
- * values are defined by OSPF.
- *
- * @see LinkType
- * @param linkType The new LinkType for the current Global Router Link Record.
- */
- void SetLinkType(LinkType linkType);
-
-/**
- * @brief Get the Metric Data field of the Global Router Link Record.
- *
- * The metric is an abstract cost associated with forwarding a packet across
- * a link. A sum of metrics must have a well-defined meaning. That is, you
- * shouldn't use bandwidth as a metric (how does the sum of the bandwidth of
- * two hops relate to the cost of sending a packet); rather you should use
- * something like delay.
- *
- * @returns The metric field of the Global Router Link Record.
- */
- uint32_t GetMetric(void) const;
-
-/**
- * @brief Set the Metric Data field of the Global Router Link Record.
- *
- * The metric is an abstract cost associated with forwarding a packet across
- * a link. A sum of metrics must have a well-defined meaning. That is, you
- * shouldn't use bandwidth as a metric (how does the sum of the bandwidth of
- * two hops relate to the cost of sending a packet); rather you should use
- * something like delay.
- *
- * @param metric The new metric for the current Global Router Link Record.
- */
- void SetMetric(uint32_t metric);
-
-private:
-/**
- * m_linkId and m_linkData are defined by OSPF to have different meanings
- * depending on the type of link a given link records represents. They work
- * together.
- *
- * For Type 1 link (PointToPoint), set m_linkId to Router ID of
- * neighboring router.
- *
- * For Type 3 link (Stub), set m_linkId to neighbor's IP address
- */
- Ipv4Address m_linkId;
-
-/**
- * m_linkId and m_linkData are defined by OSPF to have different meanings
- * depending on the type of link a given link records represents. They work
- * together.
- *
- * For Type 1 link (PointToPoint), set m_linkData to local IP address
- *
- * For Type 3 link (Stub), set m_linkData to mask
- */
- Ipv4Address m_linkData; // for links to RouterLSA,
-
-/**
- * The type of the Global Router Link Record. Defined in the OSPF spec.
- * We currently only use PointToPoint and StubNetwork types.
- */
- LinkType m_linkType;
-
-/**
- * The metric for a given link.
- *
- * A metric is abstract cost associated with forwarding a packet across a
- * link. A sum of metrics must have a well-defined meaning. That is, you
- * shouldn't use bandwidth as a metric (how does the sum of the bandwidth
- * of two hops relate to the cost of sending a packet); rather you should
- * use something like delay.
- */
- uint32_t m_metric;
-};
-
-/**
- * @brief a Link State Advertisement (LSA) for a router, used in global
- * routing.
- *
- * Roughly equivalent to a global incarnation of the OSPF link state header
- * combined with a list of Link Records. Since it's global, there's
- * no need for age or sequence number. See RFC 2328, Appendix A.
- */
-class GlobalRouterLSA
-{
-public:
-/**
- * @enum SPFStatus
- * @brief Enumeration of the possible values of the status flag in the Router
- * Link State Advertisements.
- */
- enum SPFStatus {
- LSA_SPF_NOT_EXPLORED = 0, /**< New vertex not yet considered */
- LSA_SPF_CANDIDATE, /**< Vertex is in the SPF candidate queue */
- LSA_SPF_IN_SPFTREE /**< Vertex is in the SPF tree */
- };
-
-/**
- * @brief Create a blank Global Router Link State Advertisement.
- *
- * On completion Ipv4Address variables initialized to 0.0.0.0 and the
- * list of Link State Records is empty.
- */
- GlobalRouterLSA();
-
-/**
- * @brief Create an initialized Global Router Link State Advertisement.
- *
- * On completion the list of Link State Records is empty.
- *
- * @param status The status to of the new LSA.
- * @param linkStateId The Ipv4Address for the link state ID field.
- * @param advertisingRtr The Ipv4Address for the advertising router field.
- */
- GlobalRouterLSA(SPFStatus status, Ipv4Address linkStateId,
- Ipv4Address advertisingRtr);
-
-/**
- * @brief Copy constructor for a Global Router Link State Advertisement.
- *
- * Takes a piece of memory and constructs a semantically identical copy of
- * the given LSA.
- *
- * @param lsa The existing LSA to be used as the source.
- */
- GlobalRouterLSA (GlobalRouterLSA& lsa);
-
-/**
- * @brief Destroy an existing Global Router Link State Advertisement.
- *
- * Any Global Router Link Records present in the list are freed.
- */
- ~GlobalRouterLSA();
-
-/**
- * @brief Assignment operator for a Global Router Link State Advertisement.
- *
- * Takes an existing Global Router Link State Advertisement and overwrites
- * it to make a semantically identical copy of a given prototype LSA.
- *
- * If there are any Global Router Link Records present in the existing
- * LSA, they are freed before the assignment happens.
- *
- * @param lsa The existing LSA to be used as the source.
- * @returns Reference to the overwritten LSA.
- */
- GlobalRouterLSA& operator= (const GlobalRouterLSA& lsa);
-
-/**
- * @brief Copy any Global Router Link Records in a given Global Router Link
- * State Advertisement to the current LSA.
- *
- * Existing Link Records are not deleted -- this is a concatenation of Link
- * Records.
- *
- * @see ClearLinkRecords ()
- * @param lsa The LSA to copy the Link Records from.
- */
- void CopyLinkRecords (const GlobalRouterLSA& lsa);
-
-/**
- * @brief Add a given Global Router Link Record to the LSA.
- *
- * @param lr The Global Router Link Record to be added.
- * @returns The number of link records in the list.
- */
- uint32_t AddLinkRecord (GlobalRouterLinkRecord* lr);
-
-/**
- * @brief Return the number of Global Router Link Records in the LSA.
- *
- * @returns The number of link records in the list.
- */
- uint32_t GetNLinkRecords (void) const;
-
-/**
- * @brief Return a pointer to the specified Global Router Link Record.
- *
- * @param n The LSA number desired.
- * @returns The number of link records in the list.
- */
- GlobalRouterLinkRecord* GetLinkRecord (uint32_t n) const;
-
-/**
- * @brief Release all of the Global Router Link Records present in the Global
- * Router Link State Advertisement and make the list of link records empty.
- */
- void ClearLinkRecords(void);
-
-/**
- * @brief Check to see if the list of Global Router Link Records present in the
- * Global Router Link State Advertisement is empty.
- *
- * @returns True if the list is empty, false otherwise.
- */
- bool IsEmpty(void) const;
-
-/**
- * @brief Print the contents of the Global Router Link State Advertisement and
- * any Global Router Link Records present in the list. Quite verbose.
- */
- void Print (std::ostream &os) const;
-
-/**
- * @brief Get the Link State ID as defined by the OSPF spec. We always set it
- * to the router ID of the router making the advertisement.
- *
- * @see RoutingEnvironment::AllocateRouterId ()
- * @see GlobalRouter::GetRouterId ()
- * @returns The Ipv4Address stored as the link state ID.
- */
- Ipv4Address GetLinkStateId (void) const;
-
-/**
- * @brief Set the Link State ID is defined by the OSPF spec. We always set it
- * to the router ID of the router making the advertisement.
- *
- * @see RoutingEnvironment::AllocateRouterId ()
- * @see GlobalRouter::GetRouterId ()
- */
- void SetLinkStateId (Ipv4Address addr);
-
-/**
- * @brief Get the Advertising Router as defined by the OSPF spec. We always
- * set it to the router ID of the router making the advertisement.
- *
- * @see RoutingEnvironment::AllocateRouterId ()
- * @see GlobalRouter::GetRouterId ()
- * @returns The Ipv4Address stored as the advetising router.
- */
- Ipv4Address GetAdvertisingRouter (void) const;
-
-/**
- * @brief Set the Advertising Router as defined by the OSPF spec. We always
- * set it to the router ID of the router making the advertisement.
- *
- * @see RoutingEnvironment::AllocateRouterId ()
- * @see GlobalRouter::GetRouterId ()
- */
- void SetAdvertisingRouter (Ipv4Address rtr);
-
-/**
- * @brief Get the SPF status of the advertisement.
- *
- * @see SPFStatus
- * @returns The SPFStatus of the LSA.
- */
- SPFStatus GetStatus (void) const;
-
-/**
- * @brief Set the SPF status of the advertisement
- *
- * @see SPFStatus
- */
- void SetStatus (SPFStatus status);
-
-private:
-/**
- * The Link State ID is defined by the OSPF spec. We always set it to the
- * router ID of the router making the advertisement.
- *
- * @see RoutingEnvironment::AllocateRouterId ()
- * @see GlobalRouter::GetRouterId ()
- */
- Ipv4Address m_linkStateId;
-
-/**
- * The Advertising Router is defined by the OSPF spec. We always set it to
- * the router ID of the router making the advertisement.
- *
- * @see RoutingEnvironment::AllocateRouterId ()
- * @see GlobalRouter::GetRouterId ()
- */
- Ipv4Address m_advertisingRtr;
-
-/**
- * A convenience typedef to avoid too much writers cramp.
- */
- typedef std::list<GlobalRouterLinkRecord*> ListOfLinkRecords_t;
-
-/**
- * Each Link State Advertisement contains a number of Link Records that
- * describe the kinds of links that are attached to a given node. We
- * consider PointToPoint and StubNetwork links.
- *
- * m_linkRecords is an STL list container to hold the Link Records that have
- * been discovered and prepared for the advertisement.
- *
- * @see GlobalRouter::DiscoverLSAs ()
- */
- ListOfLinkRecords_t m_linkRecords;
-
-/**
- * This is a tristate flag used internally in the SPF computation to mark
- * if an SPFVertex (a data structure representing a vertex in the SPF tree
- * -- a router) is new, is a candidate for a shortest path, or is in its
- * proper position in the tree.
- */
- SPFStatus m_status;
-};
-
-std::ostream& operator<< (std::ostream& os, GlobalRouterLSA& lsa);
-
-/**
- * @brief An interface aggregated to a node to provide global routing info
- *
- * An interface aggregated to a node that provides global routing information
- * to a global route manager. The presence of the interface indicates that
- * the node is a router. The interface is the mechanism by which the router
- * advertises its connections to neighboring routers. We're basically
- * allowing the route manager to query for link state advertisements.
- */
-class GlobalRouter : public Object
-{
-public:
-/**
- * @brief The Interface ID of the Global Router interface.
- *
- * @see Object::QueryInterface ()
- */
- static const InterfaceId iid;
-
-/**
- * @brief Create a Global Router class and aggregate its interface onto the
- * Node provided.
- *
- * @param node The existing Node onto which this router will be aggregated.
- */
- GlobalRouter (Ptr<Node> node);
-
-/**
- * @brief Get the Router ID associated with this Global Router.
- *
- * The Router IDs are allocated in the RoutingEnvironment -- one per Router,
- * starting at 0.0.0.1 and incrementing with each instantiation of a router.
- *
- * @see RoutingEnvironment::AllocateRouterId ()
- * @returns The Router ID associated with the Global Router.
- */
- Ipv4Address GetRouterId (void) const;
-
-/**
- * @brief Walk the connected channels, discover the adjacent routers and build
- * the associated number of Global Router Link State Advertisements that
- * this router can export.
- *
- * This is a fairly expensive operation in that every time it is called
- * the current list of LSAs is built by walking connected point-to-point
- * channels and peeking into adjacent IPV4 stacks to get address information.
- * This is done to allow for limited dymanics of the Global Routing
- * environment. By that we mean that you can discover new link state
- * advertisements after a network topology change by calling DiscoverLSAs
- * and then by reading those advertisements.
- *
- * @see GlobalRouterLSA
- * @see GlobalRouter::GetLSA ()
- * @returns The number of Global Router Link State Advertisements.
- */
- uint32_t DiscoverLSAs (void);
-
-/**
- * @brief Get the Number of Global Router Link State Advertisements that this
- * router can export.
- *
- * To get meaningful information you must have previously called DiscoverLSAs.
- * After you know how many LSAs are present in the router, you may call
- * GetLSA () to retrieve the actual advertisement.
- *
- * @see GlobalRouterLSA
- * @see GlobalRouter::DiscoverLSAs ()
- * @see GlobalRouter::GetLSA ()
- * @returns The number of Global Router Link State Advertisements.
- */
- uint32_t GetNumLSAs (void) const;
-
-/**
- * @brief Get a Global Router Link State Advertisements that this router has
- * said that it can export.
- *
- * This is a fairly inexpensive expensive operation in that the hard work
- * was done in GetNumLSAs. We just copy the indicated Global Router Link
- * State Advertisement into the requested GlobalRouterLSA object.
- *
- * You must call GlobalRouter::GetNumLSAs before calling this method in
- * order to discover the adjacent routers and build the advertisements.
- * GetNumLSAs will return the number of LSAs this router advertises.
- * The parameter n (requested LSA number) must be in the range 0 to
- * GetNumLSAs() - 1.
- *
- * @see GlobalRouterLSA
- * @see GlobalRouter::GetNumLSAs ()
- * @param n The index number of the LSA you want to read.
- * @param lsa The GlobalRouterLSA class to receive the LSA information.
- * @returns The number of Global Router Link State Advertisements.
- */
- bool GetLSA (uint32_t n, GlobalRouterLSA &lsa) const;
-
-protected:
- virtual ~GlobalRouter ();
- void ClearLSAs (void);
-
- Ptr<NetDevice> GetAdjacent(Ptr<NetDevice> nd, Ptr<Channel> ch) const;
- uint32_t FindIfIndexForDevice(Ptr<Node> node, Ptr<NetDevice> nd) const;
-
- Ptr<Node> m_node;
-
- typedef std::list<GlobalRouterLSA*> ListOfLSAs_t;
- ListOfLSAs_t m_LSAs;
-
- Ipv4Address m_routerId;
-
-private:
-/**
- * @brief Global Router copy construction is disallowed.
- */
- GlobalRouter (GlobalRouter& sr);
-/**
- * @brief Global Router assignment operator is disallowed.
- */
- GlobalRouter& operator= (GlobalRouter& sr);
-};
-
-} // namespace ns3
-
-#endif /* GLOBAL_ROUTER_INTERFACE_H */
--- a/src/routing/global/wscript Fri Aug 03 09:29:57 2007 -0700
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,20 +0,0 @@
-## -*- Mode: python; py-indent-offset: 4; indent-tabs-mode: nil; coding: utf-8; -*-
-
-def build(bld):
- module = bld.create_obj('cpp', 'shlib')
- module.name = 'ns3-global-routing'
- module.target = module.name
- module.uselib_local = ['ns3-node']
- module.source = [
- 'global-router-interface.cc',
- 'global-route-manager.cc',
- 'global-route-manager-impl.cc',
- 'candidate-queue.cc',
- ]
- headers = bld.create_obj('ns3header')
- headers.source = [
- 'global-router-interface.h',
- 'global-route-manager.h',
- 'candidate-queue.h',
- ]
-