--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/internet/helper/ipv6-global-routing-helper.cc Tue Aug 30 02:11:57 2011 +0530
@@ -0,0 +1,74 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2008 INRIA
+ *
+ * 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
+ *
+ * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
+ */
+#include "ipv6-global-routing-helper.h"
+#include "ns3/ipv6-global-router-interface.h"
+#include "ns3/ipv6-global-routing.h"
+#include "ns3/ipv6-list-routing.h"
+#include "ns3/log.h"
+
+NS_LOG_COMPONENT_DEFINE("GlobalRouting6Helper");
+
+namespace ns3 {
+
+Ipv6GlobalRoutingHelper::Ipv6GlobalRoutingHelper ()
+{}
+
+Ipv6GlobalRoutingHelper::Ipv6GlobalRoutingHelper (const Ipv6GlobalRoutingHelper &o)
+{
+}
+
+Ipv6GlobalRoutingHelper*
+Ipv6GlobalRoutingHelper::Copy (void) const
+{
+ return new Ipv6GlobalRoutingHelper (*this);
+}
+
+Ptr<Ipv6RoutingProtocol>
+Ipv6GlobalRoutingHelper::Create (Ptr<Node> node) const
+{
+ NS_LOG_LOGIC ("Adding GlobalRouter interface to node " <<
+ node->GetId ());
+
+ Ptr<Global6Router> globalRouter = CreateObject<Global6Router> ();
+ node->AggregateObject (globalRouter);
+
+ NS_LOG_LOGIC ("Adding GlobalRouting Protocol to node " << node->GetId ());
+ Ptr<Ipv6GlobalRouting> globalRouting = CreateObject<Ipv6GlobalRouting> ();
+ globalRouter->SetRoutingProtocol (globalRouting);
+
+ return globalRouting;
+}
+
+void
+Ipv6GlobalRoutingHelper::PopulateRoutingTables (void)
+{
+ GlobalRoute6Manager::BuildGlobalRoutingDatabase ();
+ GlobalRoute6Manager::InitializeRoutes ();
+}
+void
+Ipv6GlobalRoutingHelper::RecomputeRoutingTables (void)
+{
+ GlobalRoute6Manager::DeleteGlobalRoutes ();
+ GlobalRoute6Manager::BuildGlobalRoutingDatabase ();
+ GlobalRoute6Manager::InitializeRoutes ();
+}
+
+
+} // namespace ns3
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/internet/helper/ipv6-global-routing-helper.h Tue Aug 30 02:11:57 2011 +0530
@@ -0,0 +1,97 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2008 INRIA
+ *
+ * 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
+ *
+ * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
+ */
+#ifndef IPV6_GLOBAL_ROUTING_HELPER_H
+#define IPV6_GLOBAL_ROUTING_HELPER_H
+
+#include "ns3/node-container.h"
+#include "ns3/ipv6-routing-helper.h"
+
+namespace ns3 {
+
+/**
+ * \brief Helper class that adds ns3::Ipv4GlobalRouting objects
+ */
+class Ipv6GlobalRoutingHelper : public Ipv6RoutingHelper
+{
+public:
+ /**
+ * \brief Construct a GlobalRoutingHelper to make life easier for managing
+ * global routing tasks.
+ */
+ Ipv6GlobalRoutingHelper ();
+
+ /**
+ * \brief Construct a GlobalRoutingHelper from another previously initialized
+ * instance (Copy Constructor).
+ */
+ Ipv6GlobalRoutingHelper (const Ipv6GlobalRoutingHelper &);
+
+ /**
+ * \internal
+ * \returns pointer to clone of this Ipv4GlobalRoutingHelper
+ *
+ * This method is mainly for internal use by the other helpers;
+ * clients are expected to free the dynamic memory allocated by this method
+ */
+ Ipv6GlobalRoutingHelper* Copy (void) const;
+
+ /**
+ * \param node the node on which the routing protocol will run
+ * \returns a newly-created routing protocol
+ *
+ * This method will be called by ns3::InternetStackHelper::Install
+ */
+ virtual Ptr<Ipv6RoutingProtocol> Create (Ptr<Node> node) const;
+
+ /**
+ * \brief Build a routing database and initialize the routing tables of
+ * the nodes in the simulation. Makes all nodes in the simulation into
+ * routers.
+ *
+ * All this function does is call the functions
+ * BuildGlobalRoutingDatabase () and InitializeRoutes ().
+ *
+ */
+ static void PopulateRoutingTables (void);
+ /**
+ * \brief Remove all routes that were previously installed in a prior call
+ * to either PopulateRoutingTables() or RecomputeRoutingTables(), and
+ * add a new set of routes.
+ *
+ * This method does not change the set of nodes
+ * over which GlobalRouting is being used, but it will dynamically update
+ * its representation of the global topology before recomputing routes.
+ * Users must first call PopulateRoutingTables() and then may subsequently
+ * call RecomputeRoutingTables() at any later time in the simulation.
+ *
+ */
+ static void RecomputeRoutingTables (void);
+private:
+ /**
+ * \internal
+ * \brief Assignment operator declared private and not implemented to disallow
+ * assignment and prevent the compiler from happily inserting its own.
+ */
+ Ipv6GlobalRoutingHelper &operator = (const Ipv6GlobalRoutingHelper &o);
+};
+
+} // namespace ns3
+
+#endif /* IPV6_GLOBAL_ROUTING_HELPER_H */
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/internet/model/ipv6-candidate-queue.cc Tue Aug 30 02:11:57 2011 +0530
@@ -0,0 +1,193 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright 2007 University of Washington
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#include <algorithm>
+#include <iostream>
+#include "ns3/log.h"
+#include "ns3/assert.h"
+#include "ipv6-candidate-queue.h"
+#include "ipv6-global-route-manager-impl.h"
+
+NS_LOG_COMPONENT_DEFINE ("Candidate6Queue");
+
+namespace ns3 {
+
+std::ostream&
+operator<< (std::ostream& os, const SPF6Vertex::VertexType& t)
+{
+ switch (t)
+ {
+ case SPF6Vertex::VertexRouter: os << "router"; break;
+ case SPF6Vertex::VertexNetwork: os << "network"; break;
+ default: os << "unknown"; break;
+ };
+ return os;
+}
+
+std::ostream&
+operator<< (std::ostream& os, const Candidate6Queue& q)
+{
+ typedef Candidate6Queue::CandidateList_t List_t;
+ typedef List_t::const_iterator CIter_t;
+ const Candidate6Queue::CandidateList_t& list = q.m_candidates;
+
+ os << "*** Candidate6Queue Begin (<id, distance, LSA-type>) ***" << std::endl;
+ for (CIter_t iter = list.begin (); iter != list.end (); iter++)
+ {
+ os << "<"
+ << (*iter)->GetVertexId () << ", "
+ << (*iter)->GetDistanceFromRoot () << ", "
+ << (*iter)->GetVertexType () << ">" << std::endl;
+ }
+ os << "*** Candidate6Queue End ***";
+ return os;
+}
+
+Candidate6Queue::Candidate6Queue()
+ : m_candidates ()
+{
+ NS_LOG_FUNCTION_NOARGS ();
+}
+
+Candidate6Queue::~Candidate6Queue()
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ Clear ();
+}
+
+ void
+Candidate6Queue::Clear (void)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ while (!m_candidates.empty ())
+ {
+ SPF6Vertex *p = Pop ();
+ delete p;
+ p = 0;
+ }
+}
+
+ void
+Candidate6Queue::Push (SPF6Vertex *vNew)
+{
+ NS_LOG_FUNCTION (this << vNew);
+
+ CandidateList_t::iterator i = std::upper_bound (
+ m_candidates.begin (), m_candidates.end (), vNew,
+ &Candidate6Queue::CompareSPF6Vertex
+ );
+ m_candidates.insert (i, vNew);
+}
+
+ SPF6Vertex *
+Candidate6Queue::Pop (void)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ if (m_candidates.empty ())
+ {
+ return 0;
+ }
+
+ SPF6Vertex *v = m_candidates.front ();
+ m_candidates.pop_front ();
+ return v;
+}
+
+ SPF6Vertex *
+Candidate6Queue::Top (void) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ if (m_candidates.empty ())
+ {
+ return 0;
+ }
+
+ return m_candidates.front ();
+}
+
+ bool
+Candidate6Queue::Empty (void) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ return m_candidates.empty ();
+}
+
+ uint32_t
+Candidate6Queue::Size (void) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ return m_candidates.size ();
+}
+
+ SPF6Vertex *
+Candidate6Queue::Find (const Ipv6Address addr) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ CandidateList_t::const_iterator i = m_candidates.begin ();
+
+ for (; i != m_candidates.end (); i++)
+ {
+ SPF6Vertex *v = *i;
+ if (v->GetVertexId() == addr)
+ {
+ return v;
+ }
+ }
+
+ return 0;
+}
+
+ void
+Candidate6Queue::Reorder (void)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+
+ m_candidates.sort (&Candidate6Queue::CompareSPF6Vertex);
+ NS_LOG_LOGIC ("After reordering the Candidate6Queue");
+ NS_LOG_LOGIC (*this);
+}
+
+/*
+ * In this implementation, SPF6Vertex follows the ordering where
+ * a vertex is ranked first if its GetDistanceFromRoot () is smaller;
+ * In case of a tie, NetworkLSA is always ranked before RouterLSA.
+ *
+ * This ordering is necessary for implementing ECMP
+ */
+bool
+Candidate6Queue::CompareSPF6Vertex (const SPF6Vertex* v1, const SPF6Vertex* v2)
+{
+ NS_LOG_FUNCTION (&v1 << &v2);
+
+ bool result = false;
+ if (v1->GetDistanceFromRoot () < v2->GetDistanceFromRoot ())
+ {
+ result = true;
+ }
+ else if (v1->GetDistanceFromRoot () == v2->GetDistanceFromRoot ())
+ {
+ if (v1->GetVertexType () == SPF6Vertex::VertexNetwork
+ && v2->GetVertexType () == SPF6Vertex::VertexRouter)
+ {
+ result = true;
+ }
+ }
+ return result;
+}
+
+} // namespace ns3
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/internet/model/ipv6-candidate-queue.h Tue Aug 30 02:11:57 2011 +0530
@@ -0,0 +1,200 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright 2007 University of Washington
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Craig Dowell (craigdo@ee.washington.edu)
+ */
+
+#ifndef CANDIDATE_QUEUE_6_H
+#define CANDIDATE_QUEUE_6_H
+
+#include <stdint.h>
+#include <list>
+#include "ns3/ipv6-address.h"
+
+namespace ns3 {
+
+class SPF6Vertex;
+
+/**
+ * \brief A Candidate Queue used in static routing.
+ *
+ * The Candidate6Queue 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 Candidate6Queue
+{
+public:
+/**
+ * @brief Create an empty SPF Candidate Queue.
+ * @internal
+ *
+ * @see SPF6Vertex
+ */
+ Candidate6Queue ();
+
+/**
+ * @internal Destroy an SPF Candidate Queue and release any resources held
+ * by the contents.
+ * @internal
+ *
+ * @see SPF6Vertex
+ */
+ virtual ~Candidate6Queue ();
+
+/**
+ * @brief Empty the Candidate Queue and release all of the resources
+ * associated with the Shortest Path First Vertex pointers in the queue.
+ * @internal
+ *
+ * @see SPF6Vertex
+ */
+ 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 SPF6Vertex
+ * @param vNew The Shortest Path First Vertex to add to the queue.
+ */
+ void Push (SPF6Vertex *vNew);
+
+/**
+ * @brief Pop the Shortest Path First Vertex pointer at the top of the queue.
+ * @internal
+ *
+ * The caller is given the responsibility for releasing the resources
+ * associated with the vertex.
+ *
+ * @see SPF6Vertex
+ * @see Top ()
+ * @returns The Shortest Path First Vertex pointer at the top of the queue.
+ */
+ SPF6Vertex* Pop (void);
+
+/**
+ * @brief Return the Shortest Path First Vertex pointer at the top of the
+ * queue.
+ * @internal
+ *
+ * This method does not pop the SPF6Vertex* off of the queue, it simply
+ * returns the pointer.
+ *
+ * @see SPF6Vertex
+ * @see Pop ()
+ * @returns The Shortest Path First Vertex pointer at the top of the queue.
+ */
+ SPF6Vertex* 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 SPF6Vertex
+ * @returns The number of SPF6Vertex* 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 SPF6Vertex
+ * @param addr The IP address to search for.
+ * @returns The SPF6Vertex* pointer corresponding to the given IP address.
+ */
+ SPF6Vertex* Find (const Ipv6Address 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 SPF6Vertex
+ */
+ void Reorder (void);
+
+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.
+ * \param sr object to copy
+ */
+ Candidate6Queue (Candidate6Queue& 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.
+ * \param sr object to assign
+ */
+ Candidate6Queue& operator= (Candidate6Queue& sr);
+/**
+ * \brief return true if v1 < v2
+ *
+ * SPF6Vertexes are added into the queue according to the ordering
+ * defined by this method. If v1 should be popped before v2, this
+ * method return true; false otherwise
+ *
+ * \return True if v1 should be popped before v2; false otherwise
+ */
+ static bool CompareSPF6Vertex (const SPF6Vertex* v1, const SPF6Vertex* v2);
+
+ typedef std::list<SPF6Vertex*> CandidateList_t;
+ CandidateList_t m_candidates;
+
+ friend std::ostream& operator<< (std::ostream& os, const Candidate6Queue& q);
+};
+
+} // namespace ns3
+
+#endif /* CANDIDATE_QUEUE_6_H */
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/internet/model/ipv6-global-route-manager-impl.cc Tue Aug 30 02:11:57 2011 +0530
@@ -0,0 +1,2408 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright 2007 University of Washington
+ * Copyright (C) 1999, 2000 Kunihiro Ishiguro, Toshiaki Takada
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Authors: Tom Henderson (tomhend@u.washington.edu)
+ *
+ * Kunihiro Ishigura, Toshiaki Takada (GNU Zebra) are attributed authors
+ * of the quagga 0.99.7/src/ospfd/ospf_spf.c code which was ported here
+ */
+
+#include <utility>
+#include <vector>
+#include <queue>
+#include <algorithm>
+#include <iostream>
+#include "ns3/assert.h"
+#include "ns3/fatal-error.h"
+#include "ns3/log.h"
+#include "ns3/node-list.h"
+#include "ns3/ipv6.h"
+#include "ns3/ipv6-routing-protocol.h"
+#include "ns3/ipv6-list-routing.h"
+#include "ns3/mpi-interface.h"
+#include "ipv6-global-router-interface.h"
+#include "ipv6-global-route-manager-impl.h"
+#include "ipv6-candidate-queue.h"
+#include "ipv6-global-routing.h"
+
+NS_LOG_COMPONENT_DEFINE ("GlobalRoute6Manager");
+
+namespace ns3 {
+
+std::ostream&
+operator<< (std::ostream& os, const SPF6Vertex::NodeExit_t& exit)
+{
+ os << "(" << exit.first << " ," << exit.second << ")";
+ return os;
+}
+
+std::ostream&
+operator<< (std::ostream& os, const SPF6Vertex::ListOfSPF6Vertex_t& vs)
+{
+ typedef SPF6Vertex::ListOfSPF6Vertex_t::const_iterator CIter_t;
+ os << "{";
+ for (CIter_t iter = vs.begin (); iter != vs.end ();)
+ {
+ os << (*iter)->m_vertexId;
+ if (++iter != vs.end ())
+ {
+ os << ", ";
+ }
+ else
+ {
+ break;
+ }
+ }
+ os << "}";
+ return os;
+}
+
+// ---------------------------------------------------------------------------
+//
+// SPF6Vertex Implementation
+//
+// ---------------------------------------------------------------------------
+
+SPF6Vertex::SPF6Vertex () :
+ m_vertexType (VertexUnknown),
+ m_vertexId ("FFFF:FFFF:FFFF:FFFF:FFFF:FFFF:FFFF:FFFF"),
+ m_lsa (0),
+ m_distanceFromRoot (SPF_INFINITY),
+ m_rootOif (SPF_INFINITY),
+ m_nextHop ("0::0"),
+ m_parents (),
+ m_children (),
+ m_vertexProcessed (false)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+}
+
+SPF6Vertex::SPF6Vertex (GlobalRouting6LSA* lsa) :
+ m_vertexId (lsa->GetLinkStateId ()),
+ m_lsa (lsa),
+ m_distanceFromRoot (SPF_INFINITY),
+ m_rootOif (SPF_INFINITY),
+ m_nextHop ("0::0"),
+ m_parents (),
+ m_children (),
+ m_vertexProcessed (false)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+
+ if (lsa->GetLSType () == GlobalRouting6LSA::RouterLSA)
+ {
+ NS_LOG_LOGIC ("Setting m_vertexType to VertexRouter");
+ m_vertexType = SPF6Vertex::VertexRouter;
+ }
+ else if (lsa->GetLSType () == GlobalRouting6LSA::NetworkLSA)
+ {
+ NS_LOG_LOGIC ("Setting m_vertexType to VertexNetwork");
+ m_vertexType = SPF6Vertex::VertexNetwork;
+ }
+}
+
+SPF6Vertex::~SPF6Vertex ()
+{
+ NS_LOG_FUNCTION (m_vertexId);
+
+ NS_LOG_LOGIC ("Children vertices - " << m_children);
+ NS_LOG_LOGIC ("Parent verteices - " << m_parents);
+
+ // find this node from all its parents and remove the entry of this node
+ // from all its parents
+ for (ListOfSPF6Vertex_t::iterator piter = m_parents.begin ();
+ piter != m_parents.end ();
+ piter++)
+ {
+ // remove the current vertex from its parent's children list. Check
+ // if the size of the list is reduced, or the child<->parent relation
+ // is not bidirectional
+ uint32_t orgCount = (*piter)->m_children.size ();
+ (*piter)->m_children.remove (this);
+ uint32_t newCount = (*piter)->m_children.size ();
+ if (orgCount > newCount)
+ {
+ NS_ASSERT_MSG (orgCount > newCount, "Unable to find the current vertex from its parents --- impossible!");
+ }
+ }
+
+ // delete children
+ while (m_children.size () > 0)
+ {
+ // pop out children one by one. Some children may disapper
+ // when deleting some other children in the list. As a result,
+ // it is necessary to use pop to walk through all children, instead
+ // of using iterator.
+ //
+ // Note that m_children.pop_front () is not necessary as this
+ // p is removed from the children list when p is deleted
+ SPF6Vertex* p = m_children.front ();
+ // 'p' == 0, this child is already deleted by its other parent
+ if (p == 0) continue;
+ NS_LOG_LOGIC ("Parent vertex-" << m_vertexId << " deleting its child vertex-" << p->GetVertexId ());
+ delete p;
+ p = 0;
+ }
+ m_children.clear ();
+ // delete parents
+ m_parents.clear ();
+ // delete root exit direction
+ m_ecmpRootExits.clear ();
+
+ NS_LOG_LOGIC ("Vertex-" << m_vertexId << " completed deleted");
+}
+
+ void
+SPF6Vertex::SetVertexType (SPF6Vertex::VertexType type)
+{
+ NS_LOG_FUNCTION (type);
+ m_vertexType = type;
+}
+
+ SPF6Vertex::VertexType
+SPF6Vertex::GetVertexType (void) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ return m_vertexType;
+}
+
+ void
+SPF6Vertex::SetVertexId (Ipv6Address id)
+{
+ NS_LOG_FUNCTION (id);
+ m_vertexId = id;
+}
+
+ Ipv6Address
+SPF6Vertex::GetVertexId (void) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ return m_vertexId;
+}
+
+ void
+SPF6Vertex::SetLSA (GlobalRouting6LSA* lsa)
+{
+ NS_LOG_FUNCTION (lsa);
+ m_lsa = lsa;
+}
+
+ GlobalRouting6LSA*
+SPF6Vertex::GetLSA (void) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ return m_lsa;
+}
+
+ void
+SPF6Vertex::SetDistanceFromRoot (uint32_t distance)
+{
+ NS_LOG_FUNCTION (distance);
+ m_distanceFromRoot = distance;
+}
+
+ uint32_t
+SPF6Vertex::GetDistanceFromRoot (void) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ return m_distanceFromRoot;
+}
+
+ void
+SPF6Vertex::SetParent (SPF6Vertex* parent)
+{
+ NS_LOG_FUNCTION (parent);
+
+ // always maintain only one parent when using setter/getter methods
+ m_parents.clear ();
+ m_parents.push_back (parent);
+}
+
+ SPF6Vertex*
+SPF6Vertex::GetParent (uint32_t i) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+
+ // If the index i is out-of-range, return 0 and do nothing
+ if (m_parents.size () <= i)
+ {
+ NS_LOG_LOGIC ("Index to SPF6Vertex's parent is out-of-range.");
+ return 0;
+ }
+ ListOfSPF6Vertex_t::const_iterator iter = m_parents.begin ();
+ while (i-- > 0)
+ {
+ iter++;
+ }
+ return *iter;
+}
+
+void
+SPF6Vertex::MergeParent (const SPF6Vertex* v)
+{
+ NS_LOG_FUNCTION (v);
+
+ NS_LOG_LOGIC ("Before merge, list of parents = " << m_parents);
+ // combine the two lists first, and then remove any duplicated after
+ m_parents.insert (m_parents.end (),
+ v->m_parents.begin (), v->m_parents.end ());
+ // remove duplication
+ m_parents.sort ();
+ m_parents.unique ();
+ NS_LOG_LOGIC ("After merge, list of parents = " << m_parents);
+}
+
+void
+SPF6Vertex::SetRootExitDirection (Ipv6Address nextHop, int32_t id)
+{
+ NS_LOG_FUNCTION (nextHop << id);
+
+ // always maintain only one root's exit
+ m_ecmpRootExits.clear ();
+ m_ecmpRootExits.push_back (NodeExit_t (nextHop, id));
+ // update the following in order to be backward compatitable with
+ // GetNextHop and GetOutgoingInterface methods
+ m_nextHop = nextHop;
+ m_rootOif = id;
+}
+
+void
+SPF6Vertex::SetRootExitDirection (SPF6Vertex::NodeExit_t exit)
+{
+ NS_LOG_FUNCTION (exit);
+ SetRootExitDirection (exit.first, exit.second);
+}
+
+SPF6Vertex::NodeExit_t
+SPF6Vertex::GetRootExitDirection (uint32_t i) const
+{
+ NS_LOG_FUNCTION (i);
+ typedef ListOfNodeExit_t::const_iterator CIter_t;
+
+ NS_ASSERT_MSG (i < m_ecmpRootExits.size (), "Index out-of-range when accessing SPF6Vertex::m_ecmpRootExits!");
+ CIter_t iter = m_ecmpRootExits.begin ();
+ while (i-- > 0) {iter++;}
+
+ return *iter;
+}
+
+SPF6Vertex::NodeExit_t
+SPF6Vertex::GetRootExitDirection () const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+
+ NS_ASSERT_MSG (m_ecmpRootExits.size () <= 1, "Assumed there is at most one exit from the root to this vertex");
+ return GetRootExitDirection (0);
+}
+
+void
+SPF6Vertex::MergeRootExitDirections (const SPF6Vertex* vertex)
+{
+ NS_LOG_FUNCTION (vertex);
+
+ // obtain the external list of exit directions
+ //
+ // Append the external list into 'this' and remove duplication afterward
+ const ListOfNodeExit_t& extList = vertex->m_ecmpRootExits;
+ m_ecmpRootExits.insert (m_ecmpRootExits.end (),
+ extList.begin(), extList.end ());
+ m_ecmpRootExits.sort ();
+ m_ecmpRootExits.unique ();
+}
+
+void
+SPF6Vertex::InheritAllRootExitDirections (const SPF6Vertex* vertex)
+{
+ NS_LOG_FUNCTION (vertex);
+
+ // discard all exit direction currently associated with this vertex,
+ // and copy all the exit directions from the given vertex
+ if (m_ecmpRootExits.size () > 0)
+ {
+ NS_LOG_WARN ("x root exit directions in this vertex are going to be discarded");
+ }
+ m_ecmpRootExits.clear ();
+ m_ecmpRootExits.insert (m_ecmpRootExits.end (),
+ vertex->m_ecmpRootExits.begin (), vertex->m_ecmpRootExits.end ());
+}
+
+uint32_t
+SPF6Vertex::GetNRootExitDirections () const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ return m_ecmpRootExits.size ();
+}
+
+uint32_t
+SPF6Vertex::GetNChildren (void) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ return m_children.size ();
+}
+
+ SPF6Vertex*
+SPF6Vertex::GetChild (uint32_t n) const
+{
+ NS_LOG_FUNCTION (n);
+ uint32_t j = 0;
+
+ for ( ListOfSPF6Vertex_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
+SPF6Vertex::AddChild (SPF6Vertex* child)
+{
+ NS_LOG_FUNCTION (child);
+ m_children.push_back (child);
+ return m_children.size ();
+}
+
+void
+SPF6Vertex::SetVertexProcessed (bool value)
+{
+ m_vertexProcessed = value;
+}
+
+bool
+SPF6Vertex::IsVertexProcessed (void) const
+{
+ return m_vertexProcessed;
+}
+
+void
+SPF6Vertex::ClearVertexProcessed (void)
+{
+ for (uint32_t i = 0; i < this->GetNChildren (); i++)
+ {
+ this->GetChild (i)->ClearVertexProcessed ();
+ }
+ this->SetVertexProcessed (false);
+}
+
+// ---------------------------------------------------------------------------
+//
+// GlobalRouteManager6LSDB Implementation
+//
+// ---------------------------------------------------------------------------
+
+GlobalRouteManager6LSDB::GlobalRouteManager6LSDB ()
+:
+ m_database (),
+ m_extdatabase ()
+{
+ NS_LOG_FUNCTION_NOARGS ();
+}
+
+GlobalRouteManager6LSDB::~GlobalRouteManager6LSDB ()
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ LSDBMap_t::iterator i;
+ for (i= m_database.begin (); i!= m_database.end (); i++)
+ {
+ NS_LOG_LOGIC ("free LSA");
+ GlobalRouting6LSA* temp = i->second;
+ delete temp;
+ }
+ for (uint32_t j = 0; j < m_extdatabase.size (); j++)
+ {
+ NS_LOG_LOGIC ("free ASexternalLSA");
+ GlobalRouting6LSA* temp = m_extdatabase.at (j);
+ delete temp;
+ }
+ NS_LOG_LOGIC ("clear map");
+ m_database.clear ();
+}
+
+ void
+GlobalRouteManager6LSDB::Initialize ()
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ LSDBMap_t::iterator i;
+ for (i= m_database.begin (); i!= m_database.end (); i++)
+ {
+ GlobalRouting6LSA* temp = i->second;
+ temp->SetStatus (GlobalRouting6LSA::LSA_SPF_NOT_EXPLORED);
+ }
+}
+
+ void
+GlobalRouteManager6LSDB::Insert (Ipv6Address addr, GlobalRouting6LSA* lsa)
+{
+ NS_LOG_FUNCTION (addr << lsa);
+ if (lsa->GetLSType () == GlobalRouting6LSA::ASExternalLSAs)
+ {
+ m_extdatabase.push_back (lsa);
+ }
+ else
+ {
+ m_database.insert (LSDBPair_t (addr, lsa));
+ }
+}
+
+ GlobalRouting6LSA*
+GlobalRouteManager6LSDB::GetExtLSA (uint32_t index) const
+{
+ return m_extdatabase.at (index);
+}
+
+ uint32_t
+GlobalRouteManager6LSDB::GetNumExtLSAs () const
+{
+ return m_extdatabase.size ();
+}
+
+ GlobalRouting6LSA*
+GlobalRouteManager6LSDB::GetLSA (Ipv6Address addr) const
+{
+ NS_LOG_FUNCTION (addr);
+//
+// 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;
+}
+
+ GlobalRouting6LSA*
+GlobalRouteManager6LSDB::GetLSAByLinkData (Ipv6Address addr) const
+{
+ NS_LOG_FUNCTION (addr);
+//
+// Look up an LSA by its address.
+//
+ LSDBMap_t::const_iterator i;
+ for (i= m_database.begin (); i!= m_database.end (); i++)
+ {
+ GlobalRouting6LSA* temp = i->second;
+// Iterate among temp's Link Records
+ for (uint32_t j = 0; j < temp->GetNLinkRecords (); j++)
+ {
+ GlobalRouting6LinkRecord *lr = temp->GetLinkRecord (j);
+ if ( lr->GetLinkType () == GlobalRouting6LinkRecord::TransitNetwork &&
+ lr->GetLinkData () == addr)
+ {
+ return temp;
+ }
+ }
+ }
+ return 0;
+}
+
+// ---------------------------------------------------------------------------
+//
+// GlobalRouteManager6Impl Implementation
+//
+// ---------------------------------------------------------------------------
+
+GlobalRouteManager6Impl::GlobalRouteManager6Impl ()
+:
+ m_spfroot (0)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ m_lsdb = new GlobalRouteManager6LSDB ();
+}
+
+GlobalRouteManager6Impl::~GlobalRouteManager6Impl ()
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ if (m_lsdb)
+ {
+ delete m_lsdb;
+ }
+}
+
+ void
+GlobalRouteManager6Impl::DebugUseLsdb (GlobalRouteManager6LSDB* lsdb)
+{
+ NS_LOG_FUNCTION (lsdb);
+ if (m_lsdb)
+ {
+ delete m_lsdb;
+ }
+ m_lsdb = lsdb;
+}
+
+ void
+GlobalRouteManager6Impl::DeleteGlobalRoutes ()
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ NodeList::Iterator listEnd = NodeList::End ();
+ for (NodeList::Iterator i = NodeList::Begin (); i != listEnd; i++)
+ {
+ Ptr<Node> node = *i;
+ Ptr<Global6Router> router = node->GetObject<Global6Router> ();
+ if (router == 0)
+ {
+ continue;
+ }
+ Ptr<Ipv6GlobalRouting> gr = router->GetRoutingProtocol ();
+ uint32_t j = 0;
+ uint32_t nRoutes = gr->GetNRoutes ();
+ NS_LOG_LOGIC ("Deleting " << gr->GetNRoutes ()<< " routes from node " << node->GetId ());
+ // Each time we delete route 0, the route index shifts downward
+ // We can delete all routes if we delete the route numbered 0
+ // nRoutes times
+ for (j = 0; j < nRoutes; j++)
+ {
+ NS_LOG_LOGIC ("Deleting global route " << j << " from node " << node->GetId ());
+ gr->RemoveRoute (0);
+ }
+ NS_LOG_LOGIC ("Deleted " << j << " global routes from node "<< node->GetId ());
+ }
+ if (m_lsdb)
+ {
+ NS_LOG_LOGIC ("Deleting LSDB, creating new one");
+ delete m_lsdb;
+ m_lsdb = new GlobalRouteManager6LSDB ();
+ }
+}
+
+//
+// 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 Global6Router 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
+GlobalRouteManager6Impl::BuildGlobalRoutingDatabase ()
+{
+ NS_LOG_FUNCTION_NOARGS ();
+//
+// Walk the list of nodes looking for the Global6Router Interface. Nodes with
+// global router interfaces are, not too surprisingly, our routers.
+//
+ NodeList::Iterator listEnd = NodeList::End ();
+ for (NodeList::Iterator i = NodeList::Begin (); i != listEnd; i++)
+ {
+ Ptr<Node> node = *i;
+
+ Ptr<Global6Router> rtr = node->GetObject<Global6Router> ();
+//
+// 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 Global6Router. 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.
+//
+ Ptr<Ipv6GlobalRouting> grouting = rtr->GetRoutingProtocol ();
+ uint32_t numLSAs = rtr->DiscoverLSAs ();
+ NS_LOG_LOGIC ("Found " << numLSAs << " LSAs");
+
+ for (uint32_t j = 0; j < numLSAs; ++j)
+ {
+ GlobalRouting6LSA* lsa = new GlobalRouting6LSA ();
+//
+// This is the call to actually fetch a Link State Advertisement from the
+// router.
+//
+ rtr->GetLSA (j, *lsa);
+ NS_LOG_LOGIC (*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 Global6Router 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
+GlobalRouteManager6Impl::InitializeRoutes ()
+{
+ NS_LOG_FUNCTION_NOARGS ();
+//
+// Walk the list of nodes in the system.
+//
+ NS_LOG_INFO ("About to start SPF calculation");
+ NS_LOG_INFO(NodeList::GetNNodes());
+ NodeList::Iterator listEnd = NodeList::End ();
+ for (NodeList::Iterator i = NodeList::Begin (); i != listEnd; i++)
+ {
+ Ptr<Node> node = *i;
+//
+// Look for the Global6Router interface that indicates that the node is
+// participating in routing.
+//
+ Ptr<Global6Router> rtr =
+ node->GetObject<Global6Router> ();
+
+ // Ignore nodes that are not assigned to our systemId (distributed sim)
+ if (node->GetSystemId () != MpiInterface::GetSystemId ())
+ {
+ continue;
+ }
+
+//
+// if the node has a global router interface, then run the global routing
+// algorithms.
+//
+ if (rtr && rtr->GetNumLSAs () )
+ {
+ NS_LOG_INFO(rtr->GetRouterId());
+ SPFCalculate (rtr->GetRouterId ());
+ }
+ else if(rtr)
+ NS_LOG_INFO("only rtr");
+ }
+ NS_LOG_INFO ("Finished SPF calculation");
+}
+
+//
+// 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
+GlobalRouteManager6Impl::SPFNext (SPF6Vertex* v, Candidate6Queue& candidate)
+{
+ NS_LOG_FUNCTION (v << &candidate);
+
+ SPF6Vertex* w = 0;
+ GlobalRouting6LSA* w_lsa = 0;
+ GlobalRouting6LinkRecord *l = 0;
+ uint32_t distance = 0;
+ uint32_t numRecordsInVertex = 0;
+//
+// V points to a Router-LSA or Network-LSA
+// Loop over the links in router LSA or attached routers in Network LSA
+//
+ if (v->GetVertexType () == SPF6Vertex::VertexRouter)
+ {
+ numRecordsInVertex = v->GetLSA ()->GetNLinkRecords ();
+ }
+ if (v->GetVertexType () == SPF6Vertex::VertexNetwork)
+ {
+ numRecordsInVertex = v->GetLSA ()->GetNAttachedRouters ();
+ }
+
+ for (uint32_t i = 0; i < numRecordsInVertex; i++)
+ {
+// Get w_lsa: In case of V is Router-LSA
+ if (v->GetVertexType () == SPF6Vertex::VertexRouter)
+ {
+ NS_LOG_LOGIC ("Examining link " << i << " of " <<
+ v->GetVertexId () << "'s " <<
+ v->GetLSA ()->GetNLinkRecords () << " link records");
+//
+// (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.
+//
+ l = v->GetLSA ()->GetLinkRecord (i);
+ if (l->GetLinkType () == GlobalRouting6LinkRecord::StubNetwork)
+ {
+ NS_LOG_LOGIC ("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 () == GlobalRouting6LinkRecord::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_LOG_LOGIC ("Found a P2P record from " <<
+ v->GetVertexId () << " to " << w_lsa->GetLinkStateId ());
+ }
+ else if (l->GetLinkType () ==
+ GlobalRouting6LinkRecord::TransitNetwork)
+ {
+ w_lsa = m_lsdb->GetLSA (l->GetLinkId ());
+ NS_ASSERT (w_lsa);
+ NS_LOG_LOGIC ("Found a Transit record from " <<
+ v->GetVertexId () << " to " << w_lsa->GetLinkStateId ());
+ }
+ else
+ {
+ NS_ASSERT_MSG (0, "illegal Link Type");
+ }
+ }
+// Get w_lsa: In case of V is Network-LSA
+ if (v->GetVertexType () == SPF6Vertex::VertexNetwork)
+ {
+ w_lsa = m_lsdb->GetLSAByLinkData
+ (v->GetLSA ()->GetAttachedRouter (i));
+ if (!w_lsa)
+ {
+ continue;
+ }
+ NS_LOG_LOGIC ("Found a Network LSA from " <<
+ v->GetVertexId () << " to " << w_lsa->GetLinkStateId ());
+ }
+
+// Note: w_lsa at this point may be either RouterLSA or NetworkLSA
+//
+// (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 () == GlobalRouting6LSA::LSA_SPF_IN_SPFTREE)
+ {
+ NS_LOG_LOGIC ("Skipping -> LSA "<<
+ w_lsa->GetLinkStateId () << " already in SPF tree");
+ continue;
+ }
+//
+// (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.
+//
+ if (v->GetLSA ()->GetLSType () == GlobalRouting6LSA::RouterLSA)
+ {
+ distance = v->GetDistanceFromRoot () + l->GetMetric ();
+ }
+ else
+ {
+ distance = v->GetDistanceFromRoot ();
+ }
+
+ NS_LOG_LOGIC ("Considering w_lsa " << w_lsa->GetLinkStateId ());
+
+// Is there already vertex w in candidate list?
+ if (w_lsa->GetStatus () == GlobalRouting6LSA::LSA_SPF_NOT_EXPLORED)
+ {
+// Calculate nexthop to w
+// 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.
+
+// prepare vertex w
+ w = new SPF6Vertex (w_lsa);
+ if (SPFNexthopCalculation (v, w, l, distance))
+ {
+ w_lsa->SetStatus (GlobalRouting6LSA::LSA_SPF_CANDIDATE);
+//
+// Push this new vertex onto the priority queue (ordered by distance from the
+// root node).
+//
+ candidate.Push (w);
+ NS_LOG_LOGIC ("Pushing " <<
+ w->GetVertexId () << ", parent vertexId: " <<
+ v->GetVertexId () << ", distance: " <<
+ w->GetDistanceFromRoot ());
+ }
+ else
+ NS_ASSERT_MSG (0, "SPFNexthopCalculation never "
+ << "return false, but it does now!");
+ }
+ else if (w_lsa->GetStatus () == GlobalRouting6LSA::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.
+
+/* (quagga-0.98.6) W is already on the candidate list; call it cw.
+* Compare the previously calculated cost (cw->distance)
+* with the cost we just determined (w->distance) to see
+* if we've found a shorter path.
+*/
+ SPF6Vertex* cw;
+ cw = candidate.Find (w_lsa->GetLinkStateId ());
+ if (cw->GetDistanceFromRoot () < distance)
+ {
+//
+// This is not a shorter path, so don't do anything.
+//
+ continue;
+ }
+ else if (cw->GetDistanceFromRoot () == distance)
+ {
+//
+// This path is one with an equal cost.
+//
+ NS_LOG_LOGIC ("Equal cost multiple paths found.");
+
+// At this point, there are two instances 'w' and 'cw' of the
+// same vertex, the vertex that is currently being considered
+// for adding into the shortest path tree. 'w' is the instance
+// as seen from the root via vertex 'v', and 'cw' is the instance
+// as seen from the root via some other vertices other than 'v'.
+// These two instances are being merged in the following code.
+// In particular, the parent nodes, the next hops, and the root's
+// output interfaces of the two instances are being merged.
+//
+// Note that this is functionally equivalent to calling
+// ospf_nexthop_merge (cw->nexthop, w->nexthop) in quagga-0.98.6
+// (ospf_spf.c::859), although the detail implementation
+// is very different from quagga (blame ns3::GlobalRouteManager6Impl)
+
+// prepare vertex w
+ w = new SPF6Vertex (w_lsa);
+ SPFNexthopCalculation (v, w, l, distance);
+ cw->MergeRootExitDirections (w);
+ cw->MergeParent (w);
+// SPF6VertexAddParent (w) is necessary as the destructor of
+// SPF6Vertex checks if the vertex and its parent is linked
+// bidirectionally
+ SPF6VertexAddParent (w);
+ delete w;
+ }
+ else // cw->GetDistanceFromRoot () > w->GetDistanceFromRoot ()
+ {
+//
+// 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, cw, 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 ();
+ }
+ } // new lower cost path found
+ } // end W is already on the candidate list
+ } // end loop over the links in V's LSA
+}
+
+//
+// This method is derived from quagga ospf_nexthop_calculation() 16.1.1.
+//
+// Calculate nexthop from root through V (parent) to vertex W (destination)
+// with given distance from root->W.
+//
+// As appropriate, set w's parent, distance, and nexthop information
+//
+// For now, this is greatly simplified from the quagga code
+//
+ int
+GlobalRouteManager6Impl::SPFNexthopCalculation (
+ SPF6Vertex* v,
+ SPF6Vertex* w,
+ GlobalRouting6LinkRecord* l,
+ uint32_t distance)
+{
+ NS_LOG_FUNCTION (v << w << l << distance);
+//
+// If w is a NetworkVertex, l should be null
+/*
+ if (w->GetVertexType () == SPF6Vertex::VertexNetwork && l)
+ {
+ NS_ASSERT_MSG (0, "Error: SPFNexthopCalculation parameter problem");
+ }
+*/
+
+//
+// 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 () == SPF6Vertex::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.
+//
+ NS_ASSERT (l);
+ GlobalRouting6LinkRecord *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.
+//
+ Ipv6Address nextHop = 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>.
+//
+ uint32_t outIf = FindOutgoingInterfaceId (l->GetLinkData ());
+
+ w->SetRootExitDirection (nextHop, outIf);
+ w->SetDistanceFromRoot (distance);
+ w->SetParent (v);
+ NS_LOG_LOGIC ("Next hop from " <<
+ v->GetVertexId () << " to " << w->GetVertexId () <<
+ " goes through next hop " << nextHop <<
+ " via outgoing interface " << outIf <<
+ " with distance " << distance);
+ } // end W is a router vertes
+ else
+ {
+ NS_ASSERT (w->GetVertexType () == SPF6Vertex::VertexNetwork);
+// W is a directly connected network; no next hop is required
+ GlobalRouting6LSA* w_lsa = w->GetLSA ();
+ NS_ASSERT (w_lsa->GetLSType () == GlobalRouting6LSA::NetworkLSA);
+// Find outgoing interface ID for this network
+ uint32_t outIf = FindOutgoingInterfaceId (w_lsa->GetLinkStateId (),
+ w_lsa->GetNetworkLSANetworkMask () );
+// Set the next hop to 0.0.0.0 meaning "not exist"
+ Ipv6Address nextHop = Ipv6Address::GetZero ();
+ w->SetRootExitDirection (nextHop, outIf);
+ w->SetDistanceFromRoot (distance);
+ w->SetParent (v);
+ NS_LOG_LOGIC ("Next hop from " <<
+ v->GetVertexId () << " to network " << w->GetVertexId () <<
+ " via outgoing interface " << outIf <<
+ " with distance " << distance);
+ return 1;
+ }
+ } // end v is the root
+ else if (v->GetVertexType () == SPF6Vertex::VertexNetwork)
+ {
+// See if any of v's parents are the root
+ if (v->GetParent () == m_spfroot)
+ {
+// 16.1.1 para 5. ...the parent vertex is a network that
+// directly connects the calculating router to the destination
+// router. The list of next hops is then determined by
+// examining the destination's router-LSA...
+ NS_ASSERT (w->GetVertexType () == SPF6Vertex::VertexRouter);
+ GlobalRouting6LinkRecord *linkRemote = 0;
+ while ((linkRemote = SPFGetNextLink (w, v, linkRemote)))
+ {
+/* ...For each link in the router-LSA that points back to the
+ * parent network, the link's Link Data field provides the IP
+ * address of a next hop router. The outgoing interface to
+ * use can then be derived from the next hop IP address (or
+ * it can be inherited from the parent network).
+ */
+ Ipv6Address nextHop = linkRemote->GetLinkData ();
+ uint32_t outIf = v->GetRootExitDirection ().second;
+ w->SetRootExitDirection (nextHop, outIf);
+ NS_LOG_LOGIC ("Next hop from " <<
+ v->GetVertexId () << " to " << w->GetVertexId () <<
+ " goes through next hop " << nextHop <<
+ " via outgoing interface " << outIf);
+ }
+ }
+ else
+ {
+ w->SetRootExitDirection (v->GetRootExitDirection ());
+ }
+ }
+ 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->InheritAllRootExitDirections (v);
+ }
+//
+// 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>.
+//
+ GlobalRouting6LinkRecord*
+GlobalRouteManager6Impl::SPFGetNextLink (
+ SPF6Vertex* v,
+ SPF6Vertex* w,
+ GlobalRouting6LinkRecord* prev_link)
+{
+ NS_LOG_FUNCTION (v << w << prev_link);
+
+ bool skip = true;
+ bool found_prev_link = false;
+ GlobalRouting6LinkRecord* l;
+//
+// If prev_link is 0, we are really looking for the first link, not the next
+// link.
+//
+ if (prev_link == 0)
+ {
+ skip = false;
+ found_prev_link = true;
+ }
+//
+// 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);
+//
+// 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 ())
+ {
+ if (!found_prev_link)
+ {
+ NS_LOG_LOGIC ("Skipping links before prev_link found");
+ found_prev_link = true;
+ continue;
+ }
+
+ NS_LOG_LOGIC ("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_LOG_LOGIC ("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_LOG_LOGIC ("Skipping the found link");
+ skip = false;
+ continue;
+ }
+ }
+ }
+ return 0;
+}
+
+//
+// Used for unit tests.
+//
+ void
+GlobalRouteManager6Impl::DebugSPFCalculate (Ipv6Address root)
+{
+ NS_LOG_FUNCTION (root);
+ SPFCalculate (root);
+}
+
+//
+// Used to test if a node is a stub, from an OSPF sense.
+// If there is only one link of type 1 or 2, then a default route
+// can safely be added to the next-hop router and SPF does not need
+// to be run
+//
+bool
+GlobalRouteManager6Impl::CheckForStubNode (Ipv6Address root)
+{
+ NS_LOG_FUNCTION (root);
+ GlobalRouting6LSA *rlsa = m_lsdb->GetLSA (root);
+ Ipv6Address myRouterId = rlsa->GetLinkStateId ();
+ int transits = 0;
+ GlobalRouting6LinkRecord *transitLink = 0;
+ for (uint32_t i = 0; i < rlsa->GetNLinkRecords (); i++)
+ {
+ GlobalRouting6LinkRecord *l = rlsa->GetLinkRecord (i);
+ if (l->GetLinkType () == GlobalRouting6LinkRecord::TransitNetwork)
+ {
+ transits++;
+ transitLink = l;
+ }
+ else if (l->GetLinkType () == GlobalRouting6LinkRecord::PointToPoint)
+ {
+ transits++;
+ transitLink = l;
+ }
+ }
+ if (transits == 0)
+ {
+ // This router is not connected to any router. Probably, global
+ // routing should not be called for this node, but we can just raise
+ // a warning here and return true.
+ NS_LOG_WARN ("all nodes should have at least one transit link:" << root );
+ return true;
+ }
+ if (transits == 1)
+ {
+ if (transitLink->GetLinkType () == GlobalRouting6LinkRecord::TransitNetwork)
+ {
+ // Install default route to next hop router
+ // What is the next hop? We need to check all neighbors on the link.
+ // If there is a single router that has two transit links, then
+ // that is the default next hop. If there are more than one
+ // routers on link with multiple transit links, return false.
+ // Not yet implemented, so simply return false
+ NS_LOG_LOGIC ("TBD: Would have inserted default for transit");
+ return false;
+ }
+ else if (transitLink->GetLinkType () == GlobalRouting6LinkRecord::PointToPoint)
+ {
+ // Install default route to next hop
+ // The link record LinkID is the router ID of the peer.
+ // The Link Data is the local IP interface address
+ GlobalRouting6LSA *w_lsa = m_lsdb->GetLSA (transitLink->GetLinkId ());
+ uint32_t nLinkRecords = w_lsa->GetNLinkRecords ();
+ for (uint32_t j = 0; j < nLinkRecords; ++j)
+ {
+ //
+ // We are only concerned about point-to-point links
+ //
+ GlobalRouting6LinkRecord *lr = w_lsa->GetLinkRecord (j);
+ if (lr->GetLinkType () != GlobalRouting6LinkRecord::PointToPoint)
+ {
+ continue;
+ }
+ // Find the link record that corresponds to our routerId
+ if (lr->GetLinkId () == myRouterId)
+ {
+ // Next hop is stored in the LinkID field of lr
+ Ptr<Global6Router> router = rlsa->GetNode ()->GetObject<Global6Router> ();
+ NS_ASSERT (router);
+ Ptr<Ipv6GlobalRouting> gr = router->GetRoutingProtocol ();
+ NS_ASSERT (gr);
+ gr->AddNetworkRouteTo (Ipv6Address ("0::0"), Ipv6Prefix ("0::0"), lr->GetLinkData (),
+ FindOutgoingInterfaceId (transitLink->GetLinkData ()));
+ NS_LOG_LOGIC ("Inserting default route for node " << myRouterId << " to next hop " <<
+ lr->GetLinkData () << " via interface " <<
+ FindOutgoingInterfaceId(transitLink->GetLinkData()));
+ return true;
+ }
+ }
+ }
+ }
+ return false;
+}
+
+// quagga ospf_spf_calculate
+ void
+GlobalRouteManager6Impl::SPFCalculate (Ipv6Address root)
+{
+ NS_LOG_FUNCTION (this << root);
+
+ SPF6Vertex *v;
+//
+// Initialize the Link State Database.
+//
+ m_lsdb->Initialize ();
+//
+// The candidate queue is a priority queue of SPF6Vertex 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.
+//
+ Candidate6Queue 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 SPF6Vertex (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 (GlobalRouting6LSA::LSA_SPF_IN_SPFTREE);
+ NS_LOG_LOGIC ("Starting SPFCalculate for node " << root);
+
+//
+// Optimize SPF calculation, for ns-3.
+// We do not need to calculate SPF for every node in the network if this
+// node has only one interface through which another router can be
+// reached. Instead, short-circuit this computation and just install
+// a default route in the CheckForStubNode() method.
+//
+ if (NodeList::GetNNodes () > 0 && CheckForStubNode (root))
+ {
+ NS_LOG_LOGIC ("SPFCalculate truncated for stub node " << root);
+ delete m_spfroot;
+ return;
+ }
+
+ 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 SPF6Vertex structures for each
+// of the routers found in the Global Router Link Records and added tehm to
+// the candidate list.
+//
+ NS_LOG_LOGIC (candidate);
+ v = candidate.Pop ();
+ NS_LOG_LOGIC ("Popped vertex " << v->GetVertexId ());
+//
+// Update the status field of the vertex to indicate that it is in the SPF
+// tree.
+//
+ v->GetLSA ()->SetStatus (GlobalRouting6LSA::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.
+//
+ SPF6VertexAddParent (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.
+//
+// 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.
+//
+ if (v->GetVertexType () == SPF6Vertex::VertexRouter)
+ {
+ SPFIntraAddRouter (v);
+ }
+ else if (v->GetVertexType () == SPF6Vertex::VertexNetwork)
+ {
+ SPFIntraAddTransit (v);
+ }
+ else
+ {
+ NS_ASSERT_MSG (0, "illegal SPF6Vertex type");
+ }
+//
+// RFC2328 16.1. (5).
+//
+// Iterate the algorithm by returning to Step 2 until there are no more
+// candidate vertices.
+
+ } // end for loop
+
+// Second stage of SPF calculation procedure
+ SPFProcessStubs (m_spfroot);
+ for (uint32_t i = 0; i < m_lsdb->GetNumExtLSAs (); i++)
+ {
+ m_spfroot->ClearVertexProcessed ();
+ GlobalRouting6LSA *extlsa = m_lsdb->GetExtLSA (i);
+ NS_LOG_LOGIC ("Processing External LSA with id " << extlsa->GetLinkStateId ());
+ ProcessASExternals (m_spfroot, extlsa);
+ }
+
+//
+// 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;
+}
+
+void
+GlobalRouteManager6Impl::ProcessASExternals (SPF6Vertex* v, GlobalRouting6LSA* extlsa)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ NS_LOG_LOGIC ("Processing external for destination " <<
+ extlsa->GetLinkStateId () <<
+ ", for router " << v->GetVertexId () <<
+ ", advertised by " << extlsa->GetAdvertisingRouter ());
+ if (v->GetVertexType () == SPF6Vertex::VertexRouter)
+ {
+ GlobalRouting6LSA *rlsa = v->GetLSA ();
+ NS_LOG_LOGIC ("Processing router LSA with id " << rlsa->GetLinkStateId ());
+ if ((rlsa->GetLinkStateId ()) == (extlsa->GetAdvertisingRouter ()))
+ {
+ NS_LOG_LOGIC ("Found advertising router to destination");
+ SPFAddASExternal(extlsa,v);
+ }
+ }
+ for (uint32_t i = 0; i < v->GetNChildren (); i++)
+ {
+ if (!v->GetChild (i)->IsVertexProcessed ())
+ {
+ NS_LOG_LOGIC ("Vertex's child " << i << " not yet processed, processing...");
+ ProcessASExternals (v->GetChild (i), extlsa);
+ v->GetChild (i)->SetVertexProcessed (true);
+ }
+ }
+}
+
+//
+// Adding external routes to routing table - modeled after
+// SPFAddIntraAddStub()
+//
+
+void
+GlobalRouteManager6Impl::SPFAddASExternal (GlobalRouting6LSA *extlsa, SPF6Vertex *v)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+
+ NS_ASSERT_MSG (m_spfroot, "GlobalRouteManager6Impl::SPFAddASExternal (): Root pointer not set");
+// Two cases to consider: We are advertising the external ourselves
+// => No need to add anything
+// OR find best path to the advertising router
+ if (v->GetVertexId () == m_spfroot->GetVertexId ())
+ {
+ NS_LOG_LOGIC ("External is on local host: "
+ << v->GetVertexId () << "; returning");
+ return;
+ }
+ NS_LOG_LOGIC ("External is on remote host: "
+ << extlsa->GetAdvertisingRouter () << "; installing");
+
+ Ipv6Address routerId = m_spfroot->GetVertexId ();
+
+ NS_LOG_LOGIC ("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.
+//
+ NodeList::Iterator i = NodeList::Begin ();
+ NodeList::Iterator listEnd = NodeList::End ();
+ for (; i != listEnd; i++)
+ {
+ Ptr<Node> node = *i;
+//
+// The router ID is accessible through the Global6Router interface, so we need
+// to QI for that interface. If there's no Global6Router interface, the node
+// in question cannot be the router we want, so we continue.
+//
+ Ptr<Global6Router> rtr = node->GetObject<Global6Router> ();
+
+ if (rtr == 0)
+ {
+ NS_LOG_LOGIC ("No Global6Router 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_LOG_LOGIC ("Considering router " << rtr->GetRouterId ());
+
+ if (rtr->GetRouterId () == routerId)
+ {
+ NS_LOG_LOGIC ("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<Ipv6> ipv6 = node->GetObject<Ipv6> ();
+ NS_ASSERT_MSG (ipv6,
+ "GlobalRouteManager6Impl::SPFIntraAddRouter (): "
+ "QI for <Ipv6> 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.
+//
+ NS_ASSERT_MSG (v->GetLSA (),
+ "GlobalRouteManager6Impl::SPFIntraAddRouter (): "
+ "Expected valid LSA in SPF6Vertex* v");
+ Ipv6Prefix tempmask = extlsa->GetNetworkLSANetworkMask ();
+ Ipv6Address tempip = extlsa->GetLinkStateId ();
+ tempip = tempip.CombinePrefix (tempmask);
+
+//
+// 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.
+//
+ Ptr<Global6Router> router = node->GetObject<Global6Router> ();
+ if (router == 0)
+ {
+ continue;
+ }
+ Ptr<Ipv6GlobalRouting> gr = router->GetRoutingProtocol ();
+ NS_ASSERT (gr);
+ // walk through all next-hop-IPs and out-going-interfaces for reaching
+ // the stub network gateway 'v' from the root node
+ for (uint32_t i = 0; i < v->GetNRootExitDirections (); i++)
+ {
+ SPF6Vertex::NodeExit_t exit = v->GetRootExitDirection (i);
+ Ipv6Address nextHop = exit.first;
+ int32_t outIf = exit.second;
+ if (outIf >= 0)
+ {
+ gr->AddASExternalRouteTo (tempip, tempmask, nextHop, outIf);
+ NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () <<
+ " add external network route to " << tempip <<
+ " using next hop " << nextHop <<
+ " via interface " << outIf);
+ }
+ else
+ {
+ NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () <<
+ " NOT able to add network route to " << tempip <<
+ " using next hop " << nextHop <<
+ " since outgoing interface id is negative");
+ }
+ }
+ return;
+ } // if
+ } // for
+}
+
+
+// Processing logic from RFC 2328, page 166 and quagga ospf_spf_process_stubs ()
+// stub link records will exist for point-to-point interfaces and for
+// broadcast interfaces for which no neighboring router can be found
+void
+GlobalRouteManager6Impl::SPFProcessStubs (SPF6Vertex* v)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ NS_LOG_LOGIC ("Processing stubs for " << v->GetVertexId ());
+ if (v->GetVertexType () == SPF6Vertex::VertexRouter)
+ {
+ GlobalRouting6LSA *rlsa = v->GetLSA ();
+ NS_LOG_LOGIC ("Processing router LSA with id " << rlsa->GetLinkStateId ());
+ for (uint32_t i = 0; i < rlsa->GetNLinkRecords (); i++)
+ {
+ NS_LOG_LOGIC ("Examining link " << i << " of " <<
+ v->GetVertexId () << "'s " <<
+ v->GetLSA ()->GetNLinkRecords () << " link records");
+ GlobalRouting6LinkRecord *l = v->GetLSA ()->GetLinkRecord (i);
+ if (l->GetLinkType () == GlobalRouting6LinkRecord::StubNetwork)
+ {
+ NS_LOG_LOGIC ("Found a Stub record to " << l->GetLinkId ());
+ SPFIntraAddStub (l, v);
+ continue;
+ }
+ }
+ }
+ for (uint32_t i = 0; i < v->GetNChildren (); i++)
+ {
+ if (!v->GetChild (i)->IsVertexProcessed ())
+ {
+ SPFProcessStubs (v->GetChild (i));
+ v->GetChild (i)->SetVertexProcessed (true);
+ }
+ }
+}
+
+// RFC2328 16.1. second stage.
+void
+GlobalRouteManager6Impl::SPFIntraAddStub (GlobalRouting6LinkRecord *l, SPF6Vertex* v)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+
+ NS_ASSERT_MSG (m_spfroot,
+ "GlobalRouteManager6Impl::SPFIntraAddStub (): Root pointer not set");
+
+ // XXX simplifed logic for the moment. There are two cases to consider:
+ // 1) the stub network is on this router; do nothing for now
+ // (already handled above)
+ // 2) the stub network is on a remote router, so I should use the
+ // same next hop that I use to get to vertex v
+ if (v->GetVertexId () == m_spfroot->GetVertexId ())
+ {
+ NS_LOG_LOGIC ("Stub is on local host: " << v->GetVertexId () << "; returning");
+ return;
+ }
+ NS_LOG_LOGIC ("Stub is on remote host: " << v->GetVertexId () << "; installing");
+//
+// 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.
+//
+ Ipv6Address routerId = m_spfroot->GetVertexId ();
+
+ NS_LOG_LOGIC ("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.
+//
+ NodeList::Iterator i = NodeList::Begin ();
+ NodeList::Iterator listEnd = NodeList::End ();
+ for (; i != listEnd; i++)
+ {
+ Ptr<Node> node = *i;
+//
+// The router ID is accessible through the Global6Router interface, so we need
+// to QI for that interface. If there's no Global6Router interface, the node
+// in question cannot be the router we want, so we continue.
+//
+ Ptr<Global6Router> rtr =
+ node->GetObject<Global6Router> ();
+
+ if (rtr == 0)
+ {
+ NS_LOG_LOGIC ("No Global6Router 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_LOG_LOGIC ("Considering router " << rtr->GetRouterId ());
+
+ if (rtr->GetRouterId () == routerId)
+ {
+ NS_LOG_LOGIC ("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<Ipv6> ipv6 = node->GetObject<Ipv6> ();
+ NS_ASSERT_MSG (ipv6,
+ "GlobalRouteManager6Impl::SPFIntraAddRouter (): "
+ "QI for <Ipv6> 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.
+//
+ NS_ASSERT_MSG (v->GetLSA (),
+ "GlobalRouteManager6Impl::SPFIntraAddRouter (): "
+ "Expected valid LSA in SPF6Vertex* v");
+ uint8_t addr[16];
+ l->GetLinkData().GetBytes(addr);
+ Ipv6Prefix tempmask (addr);
+ Ipv6Address tempip = l->GetLinkId ();
+ tempip = tempip.CombinePrefix (tempmask);
+//
+// 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.
+//
+
+ Ptr<Global6Router> router = node->GetObject<Global6Router> ();
+ if (router == 0)
+ {
+ continue;
+ }
+ Ptr<Ipv6GlobalRouting> gr = router->GetRoutingProtocol ();
+ NS_ASSERT (gr);
+ // walk through all next-hop-IPs and out-going-interfaces for reaching
+ // the stub network gateway 'v' from the root node
+ for (uint32_t i = 0; i < v->GetNRootExitDirections (); i++)
+ {
+ SPF6Vertex::NodeExit_t exit = v->GetRootExitDirection (i);
+ Ipv6Address nextHop = exit.first;
+ int32_t outIf = exit.second;
+ if (outIf >= 0)
+ {
+ gr->AddNetworkRouteTo (tempip, tempmask, nextHop, outIf);
+ NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () <<
+ " add network route to " << tempip <<
+ " using next hop " << nextHop <<
+ " via interface " << outIf);
+ }
+ else
+ {
+ NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () <<
+ " NOT able to add network route to " << tempip <<
+ " using next hop " << nextHop <<
+ " since outgoing interface id is negative");
+ }
+ }
+ return;
+ } // if
+ } // for
+}
+
+//
+// Return the interface number corresponding to a given IP address and mask
+// This is a wrapper around GetInterfaceForPrefix(), but we first
+// have to find the right node pointer to pass to that function.
+// If no such interface is found, return -1 (note: unit test framework
+// for routing assumes -1 to be a legal return value)
+//
+int32_t
+GlobalRouteManager6Impl::FindOutgoingInterfaceId (Ipv6Address a, Ipv6Prefix amask)
+{
+ NS_LOG_FUNCTION (a << amask);
+//
+// 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.
+//
+ Ipv6Address 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.
+//
+ NodeList::Iterator i = NodeList::Begin ();
+ NodeList::Iterator listEnd = NodeList::End ();
+ for (; i != listEnd; i++)
+ {
+ Ptr<Node> node = *i;
+
+ Ptr<Global6Router> rtr =
+ node->GetObject<Global6Router> ();
+//
+// If the node doesn't have a Global6Router 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<Ipv6> ipv6 = node->GetObject<Ipv6> ();
+ NS_ASSERT_MSG (ipv6,
+ "GlobalRouteManager6Impl::FindOutgoingInterfaceId (): "
+ "GetObject for <Ipv6> 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, or -1 if not found.
+//
+ int32_t interface = ipv6->GetInterfaceForPrefix (a, amask);
+
+#if 0
+ if (interface < 0)
+ {
+ NS_FATAL_ERROR ("GlobalRouteManager6Impl::FindOutgoingInterfaceId(): "
+ "Expected an interface associated with address a:" << a);
+ }
+#endif
+ return interface;
+ }
+ }
+//
+// Couldn't find it.
+//
+ NS_LOG_LOGIC ("FindOutgoingInterfaceId():Can't find root node " << routerId);
+ return -1;
+}
+
+//
+// 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
+GlobalRouteManager6Impl::SPFIntraAddRouter (SPF6Vertex* v)
+{
+ NS_LOG_FUNCTION (v);
+
+ NS_ASSERT_MSG (m_spfroot,
+ "GlobalRouteManager6Impl::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.
+//
+ Ipv6Address routerId = m_spfroot->GetVertexId ();
+
+ NS_LOG_LOGIC ("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.
+//
+ NodeList::Iterator i = NodeList::Begin ();
+ NodeList::Iterator listEnd = NodeList::End ();
+ for (; i != listEnd; i++)
+ {
+ Ptr<Node> node = *i;
+//
+// The router ID is accessible through the Global6Router interface, so we need
+// to GetObject for that interface. If there's no Global6Router interface,
+// the node in question cannot be the router we want, so we continue.
+//
+ Ptr<Global6Router> rtr =
+ node->GetObject<Global6Router> ();
+
+ if (rtr == 0)
+ {
+ NS_LOG_LOGIC ("No Global6Router 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_LOG_LOGIC ("Considering router " << rtr->GetRouterId ());
+
+ if (rtr->GetRouterId () == routerId)
+ {
+ NS_LOG_LOGIC ("Setting routes for node " << node->GetId ());
+//
+// Routing information is updated using the Ipv4 interface. We need to
+// GetObject for that interface. If the node is acting as an IP version 4
+// router, it should absolutely have an Ipv4 interface.
+//
+ Ptr<Ipv6> ipv6 = node->GetObject<Ipv6> ();
+ NS_ASSERT_MSG (ipv6,
+ "GlobalRouteManager6Impl::SPFIntraAddRouter (): "
+ "GetObject for <Ipv6> 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.
+//
+ GlobalRouting6LSA *lsa = v->GetLSA ();
+ NS_ASSERT_MSG (lsa,
+ "GlobalRouteManager6Impl::SPFIntraAddRouter (): "
+ "Expected valid LSA in SPF6Vertex* 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>.
+//
+ NS_LOG_LOGIC (" Node " << node->GetId () <<
+ " found " << nLinkRecords << " link records in LSA " << lsa << "with LinkStateId "<< lsa->GetLinkStateId ());
+ for (uint32_t j = 0; j < nLinkRecords; ++j)
+ {
+//
+// We are only concerned about point-to-point links
+//
+ GlobalRouting6LinkRecord *lr = lsa->GetLinkRecord (j);
+ if (lr->GetLinkType () != GlobalRouting6LinkRecord::PointToPoint)
+ {
+ continue;
+ }
+//
+// 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.
+//
+ Ptr<Global6Router> router = node->GetObject<Global6Router> ();
+ if (router == 0)
+ {
+ continue;
+ }
+ Ptr<Ipv6GlobalRouting> gr = router->GetRoutingProtocol ();
+ NS_ASSERT (gr);
+ // walk through all available exit directions due to ECMP,
+ // and add host route for each of the exit direction toward
+ // the vertex 'v'
+ for (uint32_t i = 0; i < v->GetNRootExitDirections (); i++)
+ {
+ SPF6Vertex::NodeExit_t exit = v->GetRootExitDirection (i);
+ Ipv6Address nextHop = exit.first;
+ int32_t outIf = exit.second;
+ if (outIf >= 0)
+ {
+ gr->AddHostRouteTo (lr->GetLinkData (), nextHop,
+ outIf);
+ NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () <<
+ " adding host route to " << lr->GetLinkData () <<
+ " using next hop " << nextHop <<
+ " and outgoing interface " << outIf);
+ }
+ else
+ {
+ NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () <<
+ " NOT able to add host route to " << lr->GetLinkData () <<
+ " using next hop " << nextHop <<
+ " since outgoing interface id is negative " << outIf);
+ }
+ } // for all routes from the root the vertex 'v'
+ }
+//
+// Done adding the routes for the selected node.
+//
+ return;
+ }
+ }
+}
+ void
+GlobalRouteManager6Impl::SPFIntraAddTransit (SPF6Vertex* v)
+{
+ NS_LOG_FUNCTION (v);
+
+ NS_ASSERT_MSG (m_spfroot,
+ "GlobalRouteManager6Impl::SPFIntraAddTransit (): 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.
+//
+ Ipv6Address routerId = m_spfroot->GetVertexId ();
+
+ NS_LOG_LOGIC ("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.
+//
+ NodeList::Iterator i = NodeList::Begin ();
+ NodeList::Iterator listEnd = NodeList::End ();
+ for (; i != listEnd; i++)
+ {
+ Ptr<Node> node = *i;
+//
+// The router ID is accessible through the Global6Router interface, so we need
+// to GetObject for that interface. If there's no Global6Router interface,
+// the node in question cannot be the router we want, so we continue.
+//
+ Ptr<Global6Router> rtr =
+ node->GetObject<Global6Router> ();
+
+ if (rtr == 0)
+ {
+ NS_LOG_LOGIC ("No Global6Router 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_LOG_LOGIC ("Considering router " << rtr->GetRouterId ());
+
+ if (rtr->GetRouterId () == routerId)
+ {
+ NS_LOG_LOGIC ("setting routes for node " << node->GetId ());
+//
+// Routing information is updated using the Ipv4 interface. We need to
+// GetObject for that interface. If the node is acting as an IP version 4
+// router, it should absolutely have an Ipv4 interface.
+//
+ Ptr<Ipv6> ipv6 = node->GetObject<Ipv6> ();
+ NS_ASSERT_MSG (ipv6,
+ "GlobalRouteManager6Impl::SPFIntraAddTransit (): "
+ "GetObject for <Ipv6> 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.
+//
+ GlobalRouting6LSA *lsa = v->GetLSA ();
+ NS_ASSERT_MSG (lsa,
+ "GlobalRouteManager6Impl::SPFIntraAddTransit (): "
+ "Expected valid LSA in SPF6Vertex* v");
+ Ipv6Prefix tempmask = lsa->GetNetworkLSANetworkMask ();
+ Ipv6Address tempip = lsa->GetLinkStateId ();
+ tempip = tempip.CombinePrefix (tempmask);
+ Ptr<Global6Router> router = node->GetObject<Global6Router> ();
+ if (router == 0)
+ {
+ continue;
+ }
+ Ptr<Ipv6GlobalRouting> gr = router->GetRoutingProtocol ();
+ NS_ASSERT (gr);
+ // walk through all available exit directions due to ECMP,
+ // and add host route for each of the exit direction toward
+ // the vertex 'v'
+ for (uint32_t i = 0; i < v->GetNRootExitDirections (); i++)
+ {
+ SPF6Vertex::NodeExit_t exit = v->GetRootExitDirection (i);
+ Ipv6Address nextHop = exit.first;
+ int32_t outIf = exit.second;
+
+ if (outIf >= 0)
+ {
+ gr->AddNetworkRouteTo (tempip, tempmask, nextHop, outIf);
+ NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () <<
+ " add network route to " << tempip <<
+ " using next hop " << nextHop <<
+ " via interface " << outIf);
+ }
+ else
+ {
+ NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () <<
+ " NOT able to add network route to " << tempip <<
+ " using next hop " << nextHop <<
+ " since outgoing interface id is negative " << outIf);
+ }
+ }
+ }
+ }
+}
+
+// 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.
+//
+ void
+GlobalRouteManager6Impl::SPF6VertexAddParent (SPF6Vertex* v)
+{
+ NS_LOG_FUNCTION (v);
+
+ for (uint32_t i=0;;)
+ {
+ SPF6Vertex* parent;
+ // check if all parents of vertex v
+ if ((parent = v->GetParent (i++)) == 0) break;
+ parent->AddChild (v);
+ }
+}
+
+} // namespace ns3
+
+
+#include "ns3/test.h"
+#include "ns3/simulator.h"
+#include <stdlib.h> // for rand()
+
+namespace ns3 {
+
+class GlobalRouteManager6ImplTestCase : public TestCase
+{
+public:
+ GlobalRouteManager6ImplTestCase();
+ virtual void DoRun(void);
+};
+
+GlobalRouteManager6ImplTestCase::GlobalRouteManager6ImplTestCase()
+ : TestCase("GlobalRouteManager6ImplTestCase")
+{}
+void
+GlobalRouteManager6ImplTestCase::DoRun(void)
+{
+ Candidate6Queue candidate;
+
+ for (int i = 0; i < 100; ++i)
+ {
+ SPF6Vertex *v = new SPF6Vertex;
+ v->SetDistanceFromRoot (rand () % 100);
+ candidate.Push (v);
+ }
+
+ uint32_t lastDistance = 0;
+
+ for (int i = 0; i < 100; ++i)
+ {
+ SPF6Vertex *v = candidate.Pop ();
+ if (v->GetDistanceFromRoot () < lastDistance)
+ {
+ // XXX does nothing.
+ UpdateErrorStatus (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
+ GlobalRouting6LinkRecord* lr0 = new GlobalRouting6LinkRecord (
+ GlobalRouting6LinkRecord::PointToPoint,
+ "0000:0000:0000:0000:0000:0000:0000:0002", // router ID 0.0.0.2
+ "0000:0000:0000:0000:000A:0001:0001:0001", // local ID
+ 1); // metric
+
+ GlobalRouting6LinkRecord* lr1 = new GlobalRouting6LinkRecord (
+ GlobalRouting6LinkRecord::StubNetwork,
+ "0000:0000:0000:0000:000A:0001:0001:0001",
+ "0000:0000:0000:0000:00FF:00FF:00FF:00FB",
+ 1);
+
+ GlobalRouting6LSA* lsa0 = new GlobalRouting6LSA ();
+ lsa0->SetLSType (GlobalRouting6LSA::RouterLSA);
+ lsa0->SetLinkStateId ("0::0");
+ lsa0->SetAdvertisingRouter ("0::0");
+ lsa0->AddLinkRecord (lr0);
+ lsa0->AddLinkRecord (lr1);
+
+ // Router 1
+ GlobalRouting6LinkRecord* lr2 = new GlobalRouting6LinkRecord (
+ GlobalRouting6LinkRecord::PointToPoint,
+ "0000:0000:0000:0000:0000:0000:0000:0002",
+ "0000:0000:0000:0000:000A:0001:0002:0001",
+ 1);
+
+ GlobalRouting6LinkRecord* lr3 = new GlobalRouting6LinkRecord (
+ GlobalRouting6LinkRecord::StubNetwork,
+ "0000:0000:0000:0000:000A:0001:0002:0001",
+ "0000:0000:0000:0000:00FF:00FF:00FF:00FB",
+ 1);
+
+ GlobalRouting6LSA* lsa1 = new GlobalRouting6LSA ();
+ lsa1->SetLSType (GlobalRouting6LSA::RouterLSA);
+ lsa1->SetLinkStateId ("0::0:0001");
+ lsa1->SetAdvertisingRouter ("0::0:0001");
+ lsa1->AddLinkRecord (lr2);
+ lsa1->AddLinkRecord (lr3);
+
+ // Router 2
+ GlobalRouting6LinkRecord* lr4 = new GlobalRouting6LinkRecord (
+ GlobalRouting6LinkRecord::PointToPoint,
+ "0::0",
+ "0000:0000:0000:0000:000A:0001:0001:0002",
+ 1);
+
+ GlobalRouting6LinkRecord* lr5 = new GlobalRouting6LinkRecord (
+ GlobalRouting6LinkRecord::StubNetwork,
+ "0000:0000:0000:0000:000A:0001:0002:0001",
+ "0000:0000:0000:0000:00FF:00FF:00FF:00FB",
+ 1);
+
+ GlobalRouting6LinkRecord* lr6 = new GlobalRouting6LinkRecord (
+ GlobalRouting6LinkRecord::PointToPoint,
+ "0::0:0001",
+ "0000:0000:0000:0000:000A:0001:0002:0002",
+ 1);
+
+ GlobalRouting6LinkRecord* lr7 = new GlobalRouting6LinkRecord (
+ GlobalRouting6LinkRecord::StubNetwork,
+ "0000:0000:0000:0000:000A:0001:0002:0001",
+ "0000:0000:0000:0000:00FF:00FF:00FF:00FB",
+ 1);
+
+ GlobalRouting6LinkRecord* lr8 = new GlobalRouting6LinkRecord (
+ GlobalRouting6LinkRecord::PointToPoint,
+ "0::0:0003",
+ "0000:0000:0000:0000:000A:0001:0003:0002",
+ 1);
+
+ GlobalRouting6LinkRecord* lr9 = new GlobalRouting6LinkRecord (
+ GlobalRouting6LinkRecord::StubNetwork,
+ "0000:0000:0000:0000:000A:0001:0003:0002",
+ "0000:0000:0000:0000:00FF:00FF:00FF:00FB",
+ 1);
+
+ GlobalRouting6LSA* lsa2 = new GlobalRouting6LSA ();
+ lsa2->SetLSType (GlobalRouting6LSA::RouterLSA);
+ lsa2->SetLinkStateId ("0::0:0002");
+ lsa2->SetAdvertisingRouter ("0::0:0002");
+ lsa2->AddLinkRecord (lr4);
+ lsa2->AddLinkRecord (lr5);
+ lsa2->AddLinkRecord (lr6);
+ lsa2->AddLinkRecord (lr7);
+ lsa2->AddLinkRecord (lr8);
+ lsa2->AddLinkRecord (lr9);
+
+ // Router 3
+ GlobalRouting6LinkRecord* lr10 = new GlobalRouting6LinkRecord (
+ GlobalRouting6LinkRecord::PointToPoint,
+ "0::0:0002",
+ "0000:0000:0000:0000:000A:0001:0002:0001",
+ 1);
+
+ GlobalRouting6LinkRecord* lr11 = new GlobalRouting6LinkRecord (
+ GlobalRouting6LinkRecord::StubNetwork,
+ "0000:0000:0000:0000:000A:0001:0003:0002",
+ "0000:0000:0000:0000:00FF:00FF:00FF:00FB",
+ 1);
+
+ GlobalRouting6LSA* lsa3 = new GlobalRouting6LSA ();
+ lsa3->SetLSType (GlobalRouting6LSA::RouterLSA);
+ lsa3->SetLinkStateId ("0::0:0003");
+ lsa3->SetAdvertisingRouter ("0::0:0003");
+ lsa3->AddLinkRecord (lr10);
+ lsa3->AddLinkRecord (lr11);
+
+ // Test the database
+ GlobalRouteManager6LSDB* srmlsdb = new GlobalRouteManager6LSDB ();
+ 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
+ GlobalRouteManager6Impl* srm = new GlobalRouteManager6Impl ();
+ 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
+
+ Simulator::Run ();
+
+// XXX here we should do some verification of the routes built
+
+ Simulator::Destroy ();
+
+ // This delete clears the srm, which deletes the LSDB, which clears
+ // all of the LSAs, which each destroys the attached LinkRecords.
+ delete srm;
+
+ // XXX
+ // No testing has actually been done other than making sure that this code
+ // does not crash
+ //return GetErrorStatus ();
+}
+
+
+static class GlobalRouteManager6ImplTestSuite : public TestSuite
+{
+public:
+ GlobalRouteManager6ImplTestSuite()
+ : TestSuite("global-route-manager-impl", UNIT)
+ {
+ AddTestCase(new GlobalRouteManager6ImplTestCase());
+ }
+} g_globalRoutingManagerImplTestSuite;
+
+} // namespace ns3
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/internet/model/ipv6-global-route-manager-impl.h Tue Aug 30 02:11:57 2011 +0530
@@ -0,0 +1,782 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright 2007 University of Washington
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Authors: Craig Dowell (craigdo@ee.washington.edu)
+ * Tom Henderson (tomhend@u.washington.edu)
+ */
+
+#ifndef GLOBAL_ROUTE_MANAGER_6_IMPL_H
+#define GLOBAL_ROUTE_MANAGER_6_IMPL_H
+
+#include <stdint.h>
+#include <list>
+#include <queue>
+#include <map>
+#include <vector>
+#include "ns3/object.h"
+#include "ns3/ptr.h"
+#include "ns3/ipv6-address.h"
+#include "ipv6-global-router-interface.h"
+#include "global-route-manager-impl.h"
+
+namespace ns3 {
+
+//const uint32_t SPF_INFINITY = 0xffffffff;
+
+class Candidate6Queue;
+class Ipv6GlobalRouting;
+
+/**
+ * @brief Vertex used in shortest path first (SPF) computations. See RFC 2328,
+ * Section 16.
+ *
+ * Each router in the simulation is associated with an SPF6Vertex 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 SPF6Vertex.
+ *
+ * The "Root" vertex is the SPF6Vertex representing the router that is having
+ * its routing tables set. The SPF6Vertex 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 SPF6Vertex 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 SPF6Vertex objects)
+ * in the simulation topology. The combination of the arrangement of the
+ * SPF6Vertex 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 SPF6Vertex
+{
+public:
+/**
+ * @brief Enumeration of the possible types of SPF6Vertex 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") SPF6Vertex (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 SPF6Vertex. 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 SPF6Vertex is initialized to empty.
+ *
+ * @see VertexType
+ */
+ SPF6Vertex();
+
+/**
+ * @brief Construct an initialized SPF6Vertex (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 SPF6Vertex is initialized to empty.
+ *
+ * @see SPF6Vertex::SPF6Vertex ()
+ * @see VertexType
+ * @see GlobalRoutingLSA
+ * @param lsa The Link State Advertisement used for finding initial values.
+ */
+ SPF6Vertex(GlobalRouting6LSA* lsa);
+
+/**
+ * @brief Destroy an SPF6Vertex (Shortest Path First Vertex).
+ * @internal
+ *
+ * The children vertices of the SPF6Vertex are recursively deleted.
+ *
+ * @see SPF6Vertex::SPF6Vertex ()
+ */
+ ~SPF6Vertex();
+
+/**
+ * @brief Get the Vertex Type field of a SPF6Vertex object.
+ * @internal
+ *
+ * The Vertex Type describes the kind of simulation object a given SPF6Vertex
+ * represents.
+ *
+ * @see VertexType
+ * @returns The VertexType of the current SPF6Vertex object.
+ */
+ VertexType GetVertexType (void) const;
+
+/**
+ * @brief Set the Vertex Type field of a SPF6Vertex object.
+ * @internal
+ *
+ * The Vertex Type describes the kind of simulation object a given SPF6Vertex
+ * represents.
+ *
+ * @see VertexType
+ * @param type The new VertexType for the current SPF6Vertex object.
+ */
+ void SetVertexType (VertexType type);
+
+/**
+ * @brief Get the Vertex ID field of a SPF6Vertex object.
+ * @internal
+ *
+ * The Vertex ID uniquely identifies the simulation object a given SPF6Vertex
+ * represents. Typically, this is the Router ID for SPF6Vertex 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 SPF6Vertex object.
+ */
+ Ipv6Address GetVertexId (void) const;
+
+/**
+ * @brief Set the Vertex ID field of a SPF6Vertex object.
+ * @internal
+ *
+ * The Vertex ID uniquely identifies the simulation object a given SPF6Vertex
+ * represents. Typically, this is the Router ID for SPF6Vertex 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 SPF6Vertex object.
+ */
+ void SetVertexId (Ipv6Address id);
+
+/**
+ * @brief Get the Global Router Link State Advertisement returned by the
+ * Global Router represented by this SPF6Vertex during the route discovery
+ * process.
+ * @internal
+ *
+ * @see Global6Router
+ * @see GlobalRoutingLSA
+ * @see Global6Router::DiscoverLSAs ()
+ * @returns A pointer to the GlobalRoutingLSA found by the router represented
+ * by this SPF6Vertex object.
+ */
+ GlobalRouting6LSA* GetLSA (void) const;
+
+/**
+ * @brief Set the Global Router Link State Advertisement returned by the
+ * Global Router represented by this SPF6Vertex during the route discovery
+ * process.
+ * @internal
+ *
+ * @see SPF6Vertex::GetLSA ()
+ * @see Global6Router
+ * @see GlobalRoutingLSA
+ * @see Global6Router::DiscoverLSAs ()
+ * @warning Ownership of the LSA is transferred to the "this" SPF6Vertex. You
+ * must not delete the LSA after calling this method.
+ * @param lsa A pointer to the GlobalRoutingLSA.
+ */
+ void SetLSA (GlobalRouting6LSA* lsa);
+
+/**
+ * @brief Get the distance from the root vertex to "this" SPF6Vertex object.
+ * @internal
+ *
+ * Each router in the simulation is associated with an SPF6Vertex 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 SPF6Vertex.
+ *
+ * The "Root" vertex is then the SPF6Vertex representing the router that is
+ * having its routing tables set. The "this" SPF6Vertex 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 SPF6Vertex to "this" SPF6Vertex.
+ */
+ uint32_t GetDistanceFromRoot (void) const;
+
+/**
+ * @brief Set the distance from the root vertex to "this" SPF6Vertex object.
+ * @internal
+ *
+ * Each router in the simulation is associated with an SPF6Vertex 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 SPF6Vertex.
+ *
+ * The "Root" vertex is then the SPF6Vertex representing the router that is
+ * having its routing tables set. The "this" SPF6Vertex 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 SPF6Vertex to "this"
+ * SPF6Vertex.
+ */
+ void SetDistanceFromRoot (uint32_t distance);
+
+/**
+ * @brief Set the IP address and outgoing interface index that should be used
+ * to begin forwarding packets from the root SPF6Vertex to "this" SPF6Vertex.
+ * @internal
+ *
+ * Each router node in the simulation is associated with an SPF6Vertex 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 SPF6Vertex representing the router that is
+ * having its routing tables set. The "this" SPF6Vertex 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 SPF6Vertex, 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 Global6Router. This
+ * address is used to forward packets off of the root's network down those
+ * links. As other vertices / nodes are discovered which are further away
+ * from the root, they will be accessible down one of the paths via a link
+ * described by one of these Global Router Link Records.
+ *
+ * To forward packets to these hosts or networks, the root node must begin
+ * the forwarding process by sending the packets to a first hop router down
+ * an interface. This means that the first hop address and interface ID must
+ * be the same for all downstream SPFVertices. We call this "inheriting"
+ * the interface and next hop.
+ *
+ * In this method we are telling the root node which exit direction it should send
+ * should I send a packet to the network or host represented by 'this' SPF6Vertex.
+ *
+ * @see Global6Router
+ * @see GlobalRoutingLSA
+ * @see GlobalRouting6LinkRecord
+ * @param nextHop The IP address to use when forwarding packets to the host
+ * or network represented by "this" SPF6Vertex.
+ * @param id The interface index to use when forwarding packets to the host or
+ * network represented by "this" SPF6Vertex.
+ */
+ void SetRootExitDirection (Ipv6Address nextHop, int32_t id = SPF_INFINITY);
+ typedef std::pair<Ipv6Address, int32_t> NodeExit_t;
+/**
+ * @brief Set the IP address and outgoing interface index that should be used
+ * to begin forwarding packets from the root SPF6Vertex to "this" SPF6Vertex.
+ * @internal
+ *
+ * Each router node in the simulation is associated with an SPF6Vertex 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 SPF6Vertex representing the router that is
+ * having its routing tables set. The "this" SPF6Vertex 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 SPF6Vertex, 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 Global6Router. This
+ * address is used to forward packets off of the root's network down those
+ * links. As other vertices / nodes are discovered which are further away
+ * from the root, they will be accessible down one of the paths via a link
+ * described by one of these Global Router Link Records.
+ *
+ * To forward packets to these hosts or networks, the root node must begin
+ * the forwarding process by sending the packets to a first hop router down
+ * an interface. This means that the first hop address and interface ID must
+ * be the same for all downstream SPFVertices. We call this "inheriting"
+ * the interface and next hop.
+ *
+ * In this method we are telling the root node which exit direction it should send
+ * should I send a packet to the network or host represented by 'this' SPF6Vertex.
+ *
+ * @see Global6Router
+ * @see GlobalRoutingLSA
+ * @see GlobalRouting6LinkRecord
+ * @param nextHop The IP address to use when forwarding packets to the host
+ * or network represented by "this" SPF6Vertex.
+ * @param exit The pair of next-hop-IP and outgoing-interface-index to use when
+ * forwarding packets to the host or network represented by "this" SPF6Vertex.
+ */
+ void SetRootExitDirection (SPF6Vertex::NodeExit_t exit);
+ /**
+ * \brief Obtain a pair indicating the exit direction from the root
+ *
+ * \param i An index to a pair
+ * \return A pair of next-hop-IP and outgoing-interface-index for
+ * indicating an exit direction from the root. It is 0 if the index 'i'
+ * is out-of-range
+ */
+ NodeExit_t GetRootExitDirection (uint32_t i) const;
+ /**
+ * \brief Obtain a pair indicating the exit direction from the root
+ *
+ * This method assumes there is only a single exit direction from the root.
+ * Error occur if this assumption is invalid.
+ *
+ * \return The pair of next-hop-IP and outgoing-interface-index for reaching
+ * 'this' vertex from the root
+ */
+ NodeExit_t GetRootExitDirection () const;
+ /**
+ * \brief Merge into 'this' vertex the list of exit directions from
+ * another vertex
+ *
+ * This merge is necessary when ECMP are found.
+ *
+ * \param vertex From which the list of exit directions are obtain
+ * and are merged into 'this' vertex
+ */
+ void MergeRootExitDirections (const SPF6Vertex* vertex);
+ /**
+ * \brief Inherit all root exit directions from a given vertex to 'this' vertex
+ * \param vertex The vertex from which all root exit directions are to be inherited
+ *
+ * After the call of this method, the original root exit directions
+ * in 'this' vertex are all lost.
+ */
+ void InheritAllRootExitDirections (const SPF6Vertex* vertex);
+ /**
+ * \brief Get the number of exit directions from root for reaching 'this' vertex
+ * \return The number of exit directions from root
+ */
+ uint32_t GetNRootExitDirections () const;
+
+/**
+ * @brief Get a pointer to the SPFVector that is the parent of "this"
+ * SPF6Vertex.
+ * @internal
+ *
+ * Each router node in the simulation is associated with an SPF6Vertex 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 SPF6Vertex 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" SPF6Vertex
+ * (both of which reside in that SPF tree).
+ *
+ * @param i The index to one of the parents
+ * @returns A pointer to the SPF6Vertex that is the parent of "this" SPF6Vertex
+ * in the SPF tree.
+ */
+ SPF6Vertex* GetParent (uint32_t i = 0) const;
+
+/**
+ * @brief Set the pointer to the SPFVector that is the parent of "this"
+ * SPF6Vertex.
+ * @internal
+ *
+ * Each router node in the simulation is associated with an SPF6Vertex 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 SPF6Vertex 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" SPF6Vertex (both of which
+ * reside in that SPF tree).
+ *
+ * @param parent A pointer to the SPF6Vertex that is the parent of "this"
+ * SPF6Vertex* in the SPF tree.
+ */
+ void SetParent (SPF6Vertex* parent);
+ /**
+ * \brief Merge the Parent list from the v into this vertex
+ *
+ * \param v The vertex from which its list of Parent is read
+ * and then merged into the list of Parent of *this* vertex.
+ * Note that the list in v remains intact
+ */
+ void MergeParent (const SPF6Vertex* v);
+
+/**
+ * @brief Get the number of children of "this" SPF6Vertex.
+ * @internal
+ *
+ * Each router node in the simulation is associated with an SPF6Vertex 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 SPF6Vertex 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" SPF6Vertex (which
+ * reside in the SPF tree).
+ *
+ * @returns The number of children of "this" SPF6Vertex (which reside in the
+ * SPF tree).
+ */
+ uint32_t GetNChildren (void) const;
+
+/**
+ * @brief Get a borrowed SPF6Vertex pointer to the specified child of "this"
+ * SPF6Vertex.
+ * @internal
+ *
+ * Each router node in the simulation is associated with an SPF6Vertex 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 SPF6Vertex 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" SPF6Vertex (which reside in
+ * the SPF tree.
+ *
+ * @see SPF6Vertex::GetNChildren
+ * @param n The index (from 0 to the number of children minus 1) of the
+ * child SPF6Vertex 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 SPF6Vertex (which resides in the
+ * SPF tree).
+ */
+ SPF6Vertex* GetChild (uint32_t n) const;
+
+/**
+ * @brief Get a borrowed SPF6Vertex pointer to the specified child of "this"
+ * SPF6Vertex.
+ * @internal
+ *
+ * Each router node in the simulation is associated with an SPF6Vertex 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 SPF6Vertex 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" SPF6Vertex (which reside in
+ * the SPF tree.
+ *
+ * @see SPF6Vertex::GetNChildren
+ * @warning Ownership of the pointer added to the children of "this"
+ * SPF6Vertex is transferred to the "this" SPF6Vertex. You must not delete the
+ * (now) child SPF6Vertex after calling this method.
+ * @param child A pointer to the SPF6Vertex (which resides in the SPF tree) to
+ * be added to the list of children of "this" SPF6Vertex.
+ * @returns The number of children of "this" SPF6Vertex after the addition of
+ * the new child.
+ */
+ uint32_t AddChild (SPF6Vertex* child);
+
+ /**
+ * @brief Set the value of the VertexProcessed flag
+ *
+ * Flag to note whether vertex has been processed in stage two of
+ * SPF computation
+ * @param value boolean value to set the flag
+ */
+ void SetVertexProcessed (bool value);
+
+ /**
+ * @brief Check the value of the VertexProcessed flag
+ *
+ * Flag to note whether vertex has been processed in stage two of
+ * SPF computation
+ * @returns value of underlying flag
+ */
+ bool IsVertexProcessed (void) const;
+
+ void ClearVertexProcessed (void);
+
+private:
+ VertexType m_vertexType;
+ Ipv6Address m_vertexId;
+ GlobalRouting6LSA* m_lsa;
+ uint32_t m_distanceFromRoot;
+ int32_t m_rootOif;
+ Ipv6Address m_nextHop;
+ typedef std::list< NodeExit_t > ListOfNodeExit_t;
+ /// store the multiple root's exits for supporting ECMP
+ ListOfNodeExit_t m_ecmpRootExits;
+ typedef std::list<SPF6Vertex*> ListOfSPF6Vertex_t;
+ ListOfSPF6Vertex_t m_parents;
+ ListOfSPF6Vertex_t m_children;
+ bool m_vertexProcessed;
+
+/**
+ * @brief The SPF6Vertex copy construction is disallowed. There's no need for
+ * it and a compiler provided shallow copy would be wrong.
+ */
+ SPF6Vertex (SPF6Vertex& v);
+
+/**
+ * @brief The SPF6Vertex copy assignment operator is disallowed. There's no
+ * need for it and a compiler provided shallow copy would be wrong.
+ */
+ SPF6Vertex& operator= (SPF6Vertex& v);
+
+ //friend std::ostream& operator<< (std::ostream& os, const ListOfIf_t& ifs);
+ //friend std::ostream& operator<< (std::ostream& os, const ListOfAddr_t& addrs);
+ friend std::ostream& operator<< (std::ostream& os, const SPF6Vertex::ListOfSPF6Vertex_t& vs);
+};
+
+/**
+ * @brief The Link State DataBase (LSDB) of the Global Route Manager.
+ *
+ * Each node in the simulation participating in global routing has a
+ * Global6Router 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 GlobalRouteManager6LSDB
+{
+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.
+ */
+ GlobalRouteManager6LSDB ();
+
+/**
+ * @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.
+ */
+ ~GlobalRouteManager6LSDB ();
+
+/**
+ * @brief Insert an IP address / Link State Advertisement pair into the Link
+ * State Database.
+ * @internal
+ *
+ * The IPV4 address and the GlobalRoutingLSA given as parameters are converted
+ * to an STL pair and are inserted into the database map.
+ *
+ * @see GlobalRoutingLSA
+ * @see Ipv4Address
+ * @param addr The IP address associated with the LSA. Typically the Router
+ * ID.
+ * @param lsa A pointer to the Link State Advertisement for the router.
+ */
+ void Insert(Ipv6Address addr, GlobalRouting6LSA* lsa);
+
+/**
+ * @brief Look up the Link State Advertisement associated with the given
+ * link state ID (address).
+ * @internal
+ *
+ * The database map is searched for the given IPV4 address and corresponding
+ * GlobalRoutingLSA is returned.
+ *
+ * @see GlobalRoutingLSA
+ * @see Ipv4Address
+ * @param addr The IP address associated with the LSA. Typically the Router
+ * ID.
+ * @returns A pointer to the Link State Advertisement for the router specified
+ * by the IP address addr.
+ */
+ GlobalRouting6LSA* GetLSA (Ipv6Address addr) const;
+/**
+ * @brief Look up the Link State Advertisement associated with the given
+ * link state ID (address). This is a variation of the GetLSA call
+ * to allow the LSA to be found by matching addr with the LinkData field
+ * of the TransitNetwork link record.
+ * @internal
+ *
+ * @see GetLSA
+ * @param addr The IP address associated with the LSA. Typically the Router
+ * @returns A pointer to the Link State Advertisement for the router specified
+ * by the IP address addr.
+ * ID.
+ */
+ GlobalRouting6LSA* GetLSAByLinkData (Ipv6Address 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 SPF6Vertex structures
+ * that will reference the LSAs during the calculation.
+ *
+ * @see GlobalRoutingLSA
+ * @see SPF6Vertex
+ */
+ void Initialize ();
+
+ GlobalRouting6LSA* GetExtLSA (uint32_t index) const;
+ uint32_t GetNumExtLSAs () const;
+
+
+private:
+ typedef std::map<Ipv6Address, GlobalRouting6LSA*> LSDBMap_t;
+ typedef std::pair<Ipv6Address, GlobalRouting6LSA*> LSDBPair_t;
+
+ LSDBMap_t m_database;
+ std::vector<GlobalRouting6LSA*> m_extdatabase;
+
+/**
+ * @brief GlobalRouteManagerLSDB copy construction is disallowed. There's no
+ * need for it and a compiler provided shallow copy would be wrong.
+ */
+ GlobalRouteManager6LSDB (GlobalRouteManager6LSDB& lsdb);
+
+/**
+ * @brief The SPF6Vertex copy assignment operator is disallowed. There's no
+ * need for it and a compiler provided shallow copy would be wrong.
+ */
+ GlobalRouteManager6LSDB& operator= (GlobalRouteManager6LSDB& lsdb);
+};
+
+/**
+ * @brief A global router implementation.
+ *
+ * This singleton object can query interface each node in the system
+ * for a Global6Router 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 GlobalRouteManager6Impl
+{
+public:
+ GlobalRouteManager6Impl ();
+ virtual ~GlobalRouteManager6Impl ();
+/**
+ * @brief Delete all static routes on all nodes that have a
+ * Global6RouterInterface
+ *
+ * TODO: separate manually assigned static routes from static routes that
+ * the global routing code injects, and only delete the latter
+ * @internal
+ *
+ */
+ virtual void DeleteGlobalRoutes ();
+
+/**
+ * @brief Build the routing database by gathering Link State Advertisements
+ * from each node exporting a Global6Router 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 (GlobalRouteManager6LSDB*);
+
+/**
+ * @brief Debugging routine; call the core SPF from the unit tests
+ * @internal
+ */
+ void DebugSPFCalculate (Ipv6Address root);
+
+private:
+/**
+ * @brief GlobalRouteManager6Impl copy construction is disallowed.
+ * There's no need for it and a compiler provided shallow copy would be
+ * wrong.
+ */
+ GlobalRouteManager6Impl (GlobalRouteManager6Impl& 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.
+ */
+ GlobalRouteManager6Impl& operator= (GlobalRouteManager6Impl& srmi);
+
+ SPF6Vertex* m_spfroot;
+ GlobalRouteManager6LSDB* m_lsdb;
+ bool CheckForStubNode (Ipv6Address root);
+ void SPFCalculate (Ipv6Address root);
+ void SPFProcessStubs (SPF6Vertex* v);
+ void ProcessASExternals (SPF6Vertex* v, GlobalRouting6LSA* extlsa);
+ void SPFNext (SPF6Vertex*, Candidate6Queue&);
+ int SPFNexthopCalculation (SPF6Vertex* v, SPF6Vertex* w,
+ GlobalRouting6LinkRecord* l, uint32_t distance);
+ void SPF6VertexAddParent (SPF6Vertex* v);
+ GlobalRouting6LinkRecord* SPFGetNextLink (SPF6Vertex* v, SPF6Vertex* w,
+ GlobalRouting6LinkRecord* prev_link);
+ void SPFIntraAddRouter (SPF6Vertex* v);
+ void SPFIntraAddTransit (SPF6Vertex* v);
+ void SPFIntraAddStub (GlobalRouting6LinkRecord *l, SPF6Vertex* v);
+ void SPFAddASExternal (GlobalRouting6LSA *extlsa, SPF6Vertex *v);
+ int32_t FindOutgoingInterfaceId (Ipv6Address a,
+ Ipv6Prefix amask = Ipv6Prefix("FFFF:FFFF:FFFF:FFFF:FFFF:FFFF:FFFF:FFFF"));
+};
+
+} // namespace ns3
+
+#endif /* GLOBAL_ROUTE_MANAGER_6_IMPL_H */
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/internet/model/ipv6-global-route-manager.cc Tue Aug 30 02:11:57 2011 +0530
@@ -0,0 +1,64 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright 2007 University of Washington
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Author: Tom Henderson (tomhend@u.washington.edu)
+ */
+
+#include "ns3/assert.h"
+#include "ns3/log.h"
+#include "ns3/simulation-singleton.h"
+#include "ipv6-global-route-manager.h"
+#include "ipv6-global-route-manager-impl.h"
+
+namespace ns3 {
+
+// ---------------------------------------------------------------------------
+//
+// GlobalRoute6Manager Implementation
+//
+// ---------------------------------------------------------------------------
+
+ void
+GlobalRoute6Manager::DeleteGlobalRoutes ()
+{
+ SimulationSingleton<GlobalRouteManager6Impl>::Get ()->
+ DeleteGlobalRoutes ();
+}
+
+ void
+GlobalRoute6Manager::BuildGlobalRoutingDatabase (void)
+{
+ SimulationSingleton<GlobalRouteManager6Impl>::Get ()->
+ BuildGlobalRoutingDatabase ();
+}
+
+ void
+GlobalRoute6Manager::InitializeRoutes (void)
+{
+ SimulationSingleton<GlobalRouteManager6Impl>::Get ()->
+ InitializeRoutes ();
+}
+
+ uint32_t
+GlobalRoute6Manager::AllocateRouterId (void)
+{
+ static uint32_t routerId = 0;
+ return routerId++;
+}
+
+
+} // namespace ns3
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/internet/model/ipv6-global-route-manager.h Tue Aug 30 02:11:57 2011 +0530
@@ -0,0 +1,87 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright 2007 University of Washington
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Authors: Craig Dowell (craigdo@ee.washington.edu)
+ * Tom Henderson (tomhend@u.washington.edu)
+ */
+
+#ifndef GLOBAL_ROUTE_6_MANAGER_H
+#define GLOBAL_ROUTE_6_MANAGER_H
+
+#include "ns3/deprecated.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 GlobalRoute6Manager
+{
+public:
+/**
+ * @brief Allocate a 32-bit router ID from monotonically increasing counter.
+ */
+ static uint32_t AllocateRouterId ();
+
+/**
+ * @brief Delete all static routes on all nodes that have a
+ * GlobalRouterInterface
+ *
+ */
+ static void DeleteGlobalRoutes ();
+
+/**
+ * @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 ();
+
+private:
+/**
+ * @brief Global Route Manager copy construction is disallowed. There's no
+ * need for it and a compiler provided shallow copy would be wrong.
+ *
+ */
+ GlobalRoute6Manager (GlobalRoute6Manager& srm);
+
+/**
+ * @brief Global Router copy assignment operator is disallowed. There's no
+ * need for it and a compiler provided shallow copy would be wrong.
+ */
+ GlobalRoute6Manager& operator= (GlobalRoute6Manager& srm);
+};
+
+} // namespace ns3
+
+#endif /* GLOBAL_ROUTE_6_MANAGER_H */
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/internet/model/ipv6-global-router-interface.cc Tue Aug 30 02:11:57 2011 +0530
@@ -0,0 +1,1759 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright 2007 University of Washington
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Authors: Tom Henderson (tomhend@u.washington.edu)
+ */
+
+#include "ns3/log.h"
+#include "ns3/assert.h"
+#include "ns3/abort.h"
+#include "ns3/channel.h"
+#include "ns3/net-device.h"
+#include "ns3/node.h"
+#include "ns3/node-list.h"
+#include "ns3/ipv4.h"
+#include "ns3/ipv6.h"
+#include "ns3/bridge-net-device.h"
+#include "ipv6-global-routing.h"
+#include "ipv6-global-router-interface.h"
+#include <vector>
+
+NS_LOG_COMPONENT_DEFINE ("Global6Router");
+
+namespace ns3 {
+
+// ---------------------------------------------------------------------------
+//
+// GlobalRouting6LinkRecord Implementation
+//
+// ---------------------------------------------------------------------------
+
+GlobalRouting6LinkRecord::GlobalRouting6LinkRecord ()
+:
+ m_linkId ("0::0"),
+ m_linkData ("0::0"),
+ m_linkType (Unknown),
+ m_metric (0)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+}
+
+GlobalRouting6LinkRecord::GlobalRouting6LinkRecord (
+ LinkType linkType,
+ Ipv6Address linkId,
+ Ipv6Address linkData,
+ uint16_t metric)
+:
+ m_linkId (linkId),
+ m_linkData (linkData),
+ m_linkType (linkType),
+ m_metric (metric)
+{
+ NS_LOG_FUNCTION (this << linkType << linkId << linkData << metric);
+}
+
+GlobalRouting6LinkRecord::~GlobalRouting6LinkRecord ()
+{
+ NS_LOG_FUNCTION_NOARGS ();
+}
+
+ Ipv6Address
+GlobalRouting6LinkRecord::GetLinkId (void) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ return m_linkId;
+}
+
+ void
+GlobalRouting6LinkRecord::SetLinkId (Ipv6Address addr)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ m_linkId = addr;
+}
+
+ Ipv6Address
+GlobalRouting6LinkRecord::GetLinkData (void) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ return m_linkData;
+}
+
+ void
+GlobalRouting6LinkRecord::SetLinkData (Ipv6Address addr)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ m_linkData = addr;
+}
+
+ GlobalRouting6LinkRecord::LinkType
+GlobalRouting6LinkRecord::GetLinkType (void) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ return m_linkType;
+}
+
+ void
+GlobalRouting6LinkRecord::SetLinkType (
+ GlobalRouting6LinkRecord::LinkType linkType)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ m_linkType = linkType;
+}
+
+ uint16_t
+GlobalRouting6LinkRecord::GetMetric (void) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ return m_metric;
+}
+
+ void
+GlobalRouting6LinkRecord::SetMetric (uint16_t metric)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ m_metric = metric;
+}
+
+// ---------------------------------------------------------------------------
+//
+// GlobalRouting6LSA Implementation
+//
+// ---------------------------------------------------------------------------
+
+GlobalRouting6LSA::GlobalRouting6LSA()
+ :
+ m_lsHandling(GlobalRouting6LSA::LinkLocalFloodingScope),
+ m_floodingScope(GlobalRouting6LSA::LinkLocalScoping),
+ m_lsType (GlobalRouting6LSA::Unknown),
+ m_linkStateId("0::0"),
+ m_advertisingRtr("0::0"),
+ m_linkRecords(),
+ m_networkLSANetworkMask("0::0"),
+ m_attachedRouters(),
+ m_status(GlobalRouting6LSA::LSA_SPF_NOT_EXPLORED),
+ m_node_id(0)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+}
+
+GlobalRouting6LSA::GlobalRouting6LSA (
+ GlobalRouting6LSA::SPFStatus status,
+ Ipv6Address linkStateId,
+ Ipv6Address advertisingRtr)
+:
+ m_lsHandling(GlobalRouting6LSA::LinkLocalFloodingScope),
+ m_floodingScope(GlobalRouting6LSA::LinkLocalScoping),
+ m_lsType (GlobalRouting6LSA::Unknown),
+ m_linkStateId(linkStateId),
+ m_advertisingRtr(advertisingRtr),
+ m_linkRecords(),
+ m_networkLSANetworkMask("0::0"),
+ m_attachedRouters(),
+ m_status(status),
+ m_node_id(0)
+{
+ NS_LOG_FUNCTION (this << status << linkStateId << advertisingRtr);
+}
+
+GlobalRouting6LSA::GlobalRouting6LSA (GlobalRouting6LSA& lsa)
+ : m_lsHandling(lsa.m_lsHandling), m_floodingScope(lsa.m_floodingScope),
+ m_lsType(lsa.m_lsType), m_linkStateId(lsa.m_linkStateId),
+ m_advertisingRtr(lsa.m_advertisingRtr),
+ m_networkLSANetworkMask(lsa.m_networkLSANetworkMask),
+ m_status(lsa.m_status),
+ m_node_id(lsa.m_node_id)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ NS_ASSERT_MSG(IsEmpty(),
+ "GlobalRouting6LSA::GlobalRouting6LSA (): Non-empty LSA in constructor");
+ CopyLinkRecords (lsa);
+}
+
+ GlobalRouting6LSA&
+GlobalRouting6LSA::operator= (const GlobalRouting6LSA& lsa)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ m_lsHandling=lsa.m_lsHandling;
+ m_floodingScope=lsa.m_floodingScope;
+ m_lsType = lsa.m_lsType;
+ m_linkStateId = lsa.m_linkStateId;
+ m_advertisingRtr = lsa.m_advertisingRtr;
+ m_networkLSANetworkMask = lsa.m_networkLSANetworkMask,
+ m_status = lsa.m_status;
+ m_node_id = lsa.m_node_id;
+
+ ClearLinkRecords ();
+ CopyLinkRecords (lsa);
+ return *this;
+}
+
+ void
+GlobalRouting6LSA::CopyLinkRecords (const GlobalRouting6LSA& lsa)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ for (ListOfLinkRecords_t::const_iterator i = lsa.m_linkRecords.begin ();
+ i != lsa.m_linkRecords.end ();
+ i++)
+ {
+ GlobalRouting6LinkRecord *pSrc = *i;
+ GlobalRouting6LinkRecord *pDst = new GlobalRouting6LinkRecord;
+
+ pDst->SetLinkType (pSrc->GetLinkType ());
+ pDst->SetLinkId (pSrc->GetLinkId ());
+ pDst->SetLinkData (pSrc->GetLinkData ());
+ pDst->SetMetric (pSrc->GetMetric ());
+
+ m_linkRecords.push_back(pDst);
+ pDst = 0;
+ }
+
+ m_attachedRouters = lsa.m_attachedRouters;
+}
+
+GlobalRouting6LSA::~GlobalRouting6LSA()
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ ClearLinkRecords ();
+}
+
+ void
+GlobalRouting6LSA::ClearLinkRecords(void)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ for ( ListOfLinkRecords_t::iterator i = m_linkRecords.begin ();
+ i != m_linkRecords.end ();
+ i++)
+ {
+ NS_LOG_LOGIC ("Free link record");
+
+ GlobalRouting6LinkRecord *p = *i;
+ delete p;
+ p = 0;
+
+ *i = 0;
+ }
+ NS_LOG_LOGIC ("Clear list");
+ m_linkRecords.clear();
+}
+
+ uint32_t
+GlobalRouting6LSA::AddLinkRecord (GlobalRouting6LinkRecord* lr)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ m_linkRecords.push_back (lr);
+ return m_linkRecords.size ();
+}
+
+ uint32_t
+GlobalRouting6LSA::GetNLinkRecords (void) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ return m_linkRecords.size ();
+}
+
+ GlobalRouting6LinkRecord *
+GlobalRouting6LSA::GetLinkRecord (uint32_t n) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ 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, "GlobalRouting6LSA::GetLinkRecord (): invalid index");
+ return 0;
+}
+
+ bool
+GlobalRouting6LSA::IsEmpty (void) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ return m_linkRecords.size () == 0;
+}
+
+GlobalRouting6LSA::LSHandling
+GlobalRouting6LSA::GetLSHandling(void) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ return m_lsHandling;
+}
+
+void
+GlobalRouting6LSA::SetLSHandling(GlobalRouting6LSA::LSHandling handle)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ m_lsHandling=handle;
+}
+
+GlobalRouting6LSA::FloodingScope
+GlobalRouting6LSA::GetFloodingScope(void) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ return m_floodingScope;
+}
+
+void
+GlobalRouting6LSA::SetFloodingScope(GlobalRouting6LSA::FloodingScope scope)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ m_floodingScope=scope;
+}
+
+
+ GlobalRouting6LSA::LSType
+GlobalRouting6LSA::GetLSType (void) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ return m_lsType;
+}
+
+ void
+GlobalRouting6LSA::SetLSType (GlobalRouting6LSA::LSType typ)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ m_lsType = typ;
+}
+
+ Ipv6Address
+GlobalRouting6LSA::GetLinkStateId (void) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ return m_linkStateId;
+}
+
+ void
+GlobalRouting6LSA::SetLinkStateId (Ipv6Address addr)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ m_linkStateId = addr;
+}
+
+ Ipv6Address
+GlobalRouting6LSA::GetAdvertisingRouter (void) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ return m_advertisingRtr;
+}
+
+ void
+GlobalRouting6LSA::SetAdvertisingRouter (Ipv6Address addr)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ m_advertisingRtr = addr;
+}
+
+ void
+GlobalRouting6LSA::SetNetworkLSANetworkMask (Ipv6Prefix prefix)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ m_networkLSANetworkMask = prefix;
+}
+
+ Ipv6Prefix
+GlobalRouting6LSA::GetNetworkLSANetworkMask (void) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ return m_networkLSANetworkMask;
+}
+
+ GlobalRouting6LSA::SPFStatus
+GlobalRouting6LSA::GetStatus (void) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ return m_status;
+}
+
+ uint32_t
+GlobalRouting6LSA::AddAttachedRouter (Ipv6Address addr)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ m_attachedRouters.push_back (addr);
+ return m_attachedRouters.size ();
+}
+
+ uint32_t
+GlobalRouting6LSA::GetNAttachedRouters (void) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ return m_attachedRouters.size ();
+}
+
+ Ipv6Address
+GlobalRouting6LSA::GetAttachedRouter (uint32_t n) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ uint32_t j = 0;
+ for ( ListOfAttachedRouters_t::const_iterator i = m_attachedRouters.begin ();
+ i != m_attachedRouters.end ();
+ i++, j++)
+ {
+ if (j == n)
+ {
+ return *i;
+ }
+ }
+ NS_ASSERT_MSG(false, "GlobalRouting6LSA::GetAttachedRouter (): invalid index");
+ return Ipv6Address("0::0");
+}
+
+ void
+GlobalRouting6LSA::SetStatus (GlobalRouting6LSA::SPFStatus status)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ m_status = status;
+}
+
+ Ptr<Node>
+GlobalRouting6LSA::GetNode (void) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ return NodeList::GetNode (m_node_id);
+}
+
+ void
+GlobalRouting6LSA::SetNode (Ptr<Node> node)
+{
+ NS_LOG_FUNCTION (node);
+ m_node_id = node->GetId ();
+}
+
+ void
+GlobalRouting6LSA::Print (std::ostream &os) const
+{
+ os << std::endl;
+ os << "========== Global Routing LSA ==========" << std::endl;
+ os << "m_lsType = " << m_lsType;
+ if (m_lsType == GlobalRouting6LSA::RouterLSA)
+ {
+ os << " (GlobalRouting6LSA::RouterLSA)";
+ }
+ else if (m_lsType == GlobalRouting6LSA::NetworkLSA)
+ {
+ os << " (GlobalRouting6LSA::NetworkLSA)";
+ }
+ else if (m_lsType == GlobalRouting6LSA::InterAreaPrefixLSA)
+ {
+ os << " (GlobalRouting6LSA::InterAreaPrefixLSA)";
+ }
+ else if (m_lsType == GlobalRouting6LSA::InterAreaRouterLSA)
+ {
+ os << " (GlobalRouting6LSA::InterAreaRouterLSA)";
+ }
+ else if (m_lsType == GlobalRouting6LSA::ASExternalLSAs)
+ {
+ os << " (GlobalRouting6LSA::ASExternalLSAs)";
+ }
+ else if (m_lsType == GlobalRouting6LSA::GroupmembershipLSA)
+ {
+ os << " (GlobalRouting6LSA::GroupmembershipLSA)";
+ }
+ else if (m_lsType == GlobalRouting6LSA::Type7LSA)
+ {
+ os << " (GlobalRouting6LSA::Type7LSA)";
+ }
+ else if (m_lsType == GlobalRouting6LSA::LinkLSA)
+ {
+ os << " (GlobalRouting6LSA::LinkLSA)";
+ }
+ else if (m_lsType == GlobalRouting6LSA::IntraAreaPrefixLSA)
+ {
+ os << " (GlobalRouting6LSA::IntraAreaPrefixLSA)";
+ }
+ else
+ {
+ os << "(Unknown LSType)";
+ }
+ os << std::endl;
+
+ os << "m_linkStateId = " << m_linkStateId << " (Router ID)" << std::endl;
+ os << "m_advertisingRtr = " << m_advertisingRtr << " (Router ID)" << std::endl;
+
+ if (m_lsType == GlobalRouting6LSA::RouterLSA)
+ {
+ for ( ListOfLinkRecords_t::const_iterator i = m_linkRecords.begin ();
+ i != m_linkRecords.end ();
+ i++)
+ {
+ GlobalRouting6LinkRecord *p = *i;
+
+ os << "---------- RouterLSA Link Record ----------" << std::endl;
+ os << "m_linkType = " << p->m_linkType;
+ if (p->m_linkType == GlobalRouting6LinkRecord::PointToPoint)
+ {
+ os << " (GlobalRouting6LinkRecord::PointToPoint)" << std::endl;
+ os << "m_linkId = " << p->m_linkId << std::endl;
+ os << "m_linkData = " << p->m_linkData << std::endl;
+ os << "m_metric = " << p->m_metric << std::endl;
+ }
+ else if (p->m_linkType == GlobalRouting6LinkRecord::TransitNetwork)
+ {
+ os << " (GlobalRouting6LinkRecord::TransitNetwork)" << std::endl;
+ os << "m_linkId = " << p->m_linkId << " (Designated router for network)" << std::endl;
+ os << "m_linkData = " << p->m_linkData << " (This router's IP address)" << std::endl;
+ os << "m_metric = " << p->m_metric << std::endl;
+ }
+ else if (p->m_linkType == GlobalRouting6LinkRecord::StubNetwork)
+ {
+ os << " (GlobalRouting6LinkRecord::StubNetwork)" << std::endl;
+ os << "m_linkId = " << p->m_linkId << " (Network number of attached network)" << std::endl;
+ os << "m_linkData = " << p->m_linkData << " (Network mask of attached network)" << std::endl;
+ os << "m_metric = " << p->m_metric << std::endl;
+ }
+ else
+ {
+ os << " (Unknown LinkType)" << std::endl;
+ os << "m_linkId = " << p->m_linkId << std::endl;
+ os << "m_linkData = " << p->m_linkData << std::endl;
+ os << "m_metric = " << p->m_metric << std::endl;
+ }
+ os << "---------- End RouterLSA Link Record ----------" << std::endl;
+ }
+ }
+ else if (m_lsType == GlobalRouting6LSA::NetworkLSA)
+ {
+ os << "---------- NetworkLSA Link Record ----------" << std::endl;
+ os << "m_networkLSANetworkMask = " << m_networkLSANetworkMask << std::endl;
+ for ( ListOfAttachedRouters_t::const_iterator i = m_attachedRouters.begin (); i != m_attachedRouters.end (); i++)
+ {
+ Ipv6Address p = *i;
+ os << "attachedRouter = " << p << std::endl;
+ }
+ os << "---------- End NetworkLSA Link Record ----------" << std::endl;
+ }
+ else if (m_lsType == GlobalRouting6LSA::ASExternalLSAs)
+ {
+ os << "---------- ASExternalLSA Link Record --------" << std::endl;
+ os << "m_linkStateId = " << m_linkStateId << std::endl;
+ os << "m_networkLSANetworkMask = " << m_networkLSANetworkMask << std::endl;
+ }
+ else
+ {
+ NS_ASSERT_MSG(0, "Illegal LSA LSType: " << m_lsType);
+ }
+ os << "========== End Global Routing LSA ==========" << std::endl;
+}
+
+std::ostream& operator<< (std::ostream& os, GlobalRouting6LSA& lsa)
+{
+ lsa.Print (os);
+ return os;
+}
+
+// ---------------------------------------------------------------------------
+//
+// Global6Router Implementation
+//
+// ---------------------------------------------------------------------------
+
+NS_OBJECT_ENSURE_REGISTERED (Global6Router);
+
+TypeId
+Global6Router::GetTypeId (void)
+{
+ static TypeId tid = TypeId ("ns3::Global6Router")
+ .SetParent<Object> ();
+ return tid;
+}
+
+Global6Router::Global6Router ()
+ : m_LSAs()
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ m_routerId.Set((uint8_t *)GlobalRoute6Manager::AllocateRouterId ());
+}
+
+Global6Router::~Global6Router ()
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ ClearLSAs();
+}
+
+void
+Global6Router::SetRoutingProtocol (Ptr<Ipv6GlobalRouting> routing)
+{
+ m_routingProtocol = routing;
+}
+Ptr<Ipv6GlobalRouting>
+Global6Router::GetRoutingProtocol (void)
+{
+ return m_routingProtocol;
+}
+
+void
+Global6Router::DoDispose ()
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ m_routingProtocol = 0;
+ for (InjectedRoutesI k = m_injectedRoutes.begin ();
+ k != m_injectedRoutes.end ();
+ k = m_injectedRoutes.erase (k))
+ {
+ delete (*k);
+ }
+ Object::DoDispose ();
+}
+
+ void
+Global6Router::ClearLSAs ()
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ for ( ListOfLSAs_t::iterator i = m_LSAs.begin ();
+ i != m_LSAs.end ();
+ i++)
+ {
+ NS_LOG_LOGIC ("Free LSA");
+
+ GlobalRouting6LSA *p = *i;
+ delete p;
+ p = 0;
+
+ *i = 0;
+ }
+ NS_LOG_LOGIC ("Clear list of LSAs");
+ m_LSAs.clear();
+}
+
+ Ipv6Address
+Global6Router::GetRouterId (void) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ return m_routerId;
+}
+
+//
+// DiscoverLSAs is called on all nodes in the system that have a Global6Router
+// interface aggregated. We need to go out and discover any adjacent routers
+// and build the Link State Advertisements that reflect them and their associated
+// networks.
+//
+uint32_t
+Global6Router::DiscoverLSAs ()
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ Ptr<Node> node = GetObject<Node> ();
+ NS_ABORT_MSG_UNLESS (node, "Global6Router::DiscoverLSAs (): GetObject for <Node> interface failed");
+ NS_LOG_LOGIC ("For node " << node->GetId () );
+
+ ClearLSAs ();
+
+ //
+ // While building the Router-LSA, keep a list of those NetDevices for
+ // which the current node is the designated router and we will later build
+ // a NetworkLSA for.
+ //
+ NetDeviceContainer c;
+
+ //
+ // 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. If we're a router, we had better have an Ipv4 interface.
+ //
+ Ptr<Ipv6> ipv6Local = node->GetObject<Ipv6> ();
+ NS_ABORT_MSG_UNLESS (ipv6Local, "Global6Router::DiscoverLSAs (): GetObject for <Ipv6> interface failed");
+
+ //
+ // Every router node originates a Router-LSA
+ //
+ GlobalRouting6LSA *pLSA = new GlobalRouting6LSA;
+ pLSA->SetLSType (GlobalRouting6LSA::RouterLSA);
+ pLSA->SetLinkStateId (m_routerId);
+ pLSA->SetAdvertisingRouter (m_routerId);
+ pLSA->SetStatus (GlobalRouting6LSA::LSA_SPF_NOT_EXPLORED);
+ pLSA->SetNode (node);
+
+ //
+ // 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.) and
+ // bridge devices also take up an "extra" net device.
+ //
+ uint32_t numDevices = node->GetNDevices();
+
+ //
+ // Iterate through the devices on the node and walk the channel to see what's
+ // on the other side of the standalone devices..
+ //
+ for (uint32_t i = 0; i < numDevices; ++i)
+ {
+ Ptr<NetDevice> ndLocal = node->GetDevice(i);
+
+ //
+ // There is an assumption that bridge ports must never have an IP address
+ // associated with them. This turns out to be a very convenient place to
+ // check and make sure that this is the case.
+ //
+ if (NetDeviceIsBridged (ndLocal))
+ {
+ uint32_t interfaceBridge;
+ bool rc = FindInterfaceForDevice(node, ndLocal, interfaceBridge);
+ NS_ABORT_MSG_IF (rc, "Global6Router::DiscoverLSAs(): Bridge ports must not have an IPv6 interface index");
+ }
+
+ //
+ // Check to see if the net device we just got has a corresponding IP
+ // interface (could be a pure L2 NetDevice) -- for example a net device
+ // associated with a bridge. We are only going to involve devices with
+ // IP addresses in routing.
+ //
+ bool isForwarding = false;
+ for (uint32_t j = 0; j < ipv6Local->GetNInterfaces (); ++j )
+ {
+ if (ipv6Local->GetNetDevice (j) == ndLocal && ipv6Local->IsUp (j) &&
+ ipv6Local->IsForwarding (j))
+ {
+ isForwarding = true;
+ break;
+ }
+ }
+
+ if (!isForwarding)
+ {
+ NS_LOG_LOGIC ("Net device " << ndLocal << "has no IP interface or is not enabled for forwarding, skipping");
+ continue;
+ }
+
+ //
+ // We have a net device that we need to check out. If it suports
+ // broadcast and is not a point-point link, then it will be either a stub
+ // network or a transit network depending on the number of routers on
+ // the segment. We add the appropriate link record to the LSA.
+ //
+ // If the device is a point to point link, we treat it separately. In
+ // that case, there may be zero, one, or two link records added.
+ //
+
+ if (ndLocal->IsBroadcast () && !ndLocal->IsPointToPoint () )
+ {
+ NS_LOG_LOGIC ("Broadcast link");
+ ProcessBroadcastLink (ndLocal, pLSA, c);
+ }
+ else if (ndLocal->IsPointToPoint () )
+ {
+ NS_LOG_LOGIC ("Point=to-point link");
+ ProcessPointToPointLink (ndLocal, pLSA);
+ }
+ else
+ {
+ NS_ASSERT_MSG(0, "Global6Router::DiscoverLSAs (): unknown link type");
+ }
+ }
+
+ NS_LOG_LOGIC ("========== LSA for node " << node->GetId () << " ==========");
+ NS_LOG_LOGIC (*pLSA);
+ m_LSAs.push_back (pLSA);
+ pLSA = 0;
+
+ //
+ // Now, determine whether we need to build a NetworkLSA. This is the case if
+ // we found at least one designated router.
+ //
+ uint32_t nDesignatedRouters = c.GetN ();
+ if (nDesignatedRouters > 0)
+ {
+ NS_LOG_LOGIC ("Build Network LSAs");
+ BuildNetworkLSAs (c);
+ }
+
+ //
+ // Build injected route LSAs as external routes
+ // RFC 2328, section 12.4.4
+ //
+ for (InjectedRoutesCI i = m_injectedRoutes.begin();
+ i != m_injectedRoutes.end();
+ i++)
+ {
+ GlobalRouting6LSA *pLSA = new GlobalRouting6LSA;
+ pLSA->SetLSType (GlobalRouting6LSA::ASExternalLSAs);
+ pLSA->SetLinkStateId ((*i)->GetDestNetwork ());
+ pLSA->SetAdvertisingRouter (m_routerId);
+ pLSA->SetNetworkLSANetworkMask ((*i)->GetDestNetworkPrefix ());
+ pLSA->SetStatus (GlobalRouting6LSA::LSA_SPF_NOT_EXPLORED);
+ m_LSAs.push_back (pLSA);
+ }
+ return m_LSAs.size ();
+}
+
+ void
+Global6Router::ProcessBroadcastLink (Ptr<NetDevice> nd, GlobalRouting6LSA *pLSA, NetDeviceContainer &c)
+{
+ NS_LOG_FUNCTION (nd << pLSA << &c);
+
+ if (nd->IsBridge ())
+ {
+ ProcessBridgedBroadcastLink (nd, pLSA, c);
+ }
+ else
+ {
+ ProcessSingleBroadcastLink (nd, pLSA, c);
+ }
+}
+
+ void
+Global6Router::ProcessSingleBroadcastLink (Ptr<NetDevice> nd, GlobalRouting6LSA *pLSA, NetDeviceContainer &c)
+{
+ NS_LOG_FUNCTION (nd << pLSA << &c);
+
+ GlobalRouting6LinkRecord *plr = new GlobalRouting6LinkRecord;
+ NS_ABORT_MSG_IF (plr == 0, "Global6Router::ProcessSingleBroadcastLink(): Can't alloc link record");
+
+ //
+ // We have some preliminaries to do to get enough information to proceed.
+ // This information we need comes from the internet stack, so notice that
+ // there is an implied assumption that global routing is only going to
+ // work with devices attached to the internet stack (have an ipv4 interface
+ // associated to them.
+ //
+ Ptr<Node> node = nd->GetNode ();
+
+ uint32_t interfaceLocal;
+ bool rc = FindInterfaceForDevice(node, nd, interfaceLocal);
+ NS_ABORT_MSG_IF (rc == false, "Global6Router::ProcessSingleBroadcastLink(): No interface index associated with device");
+
+ Ptr<Ipv6> ipv6Local = node->GetObject<Ipv6> ();
+ NS_ABORT_MSG_UNLESS (ipv6Local, "Global6Router::ProcessSingleBroadcastLink (): GetObject for <Ipv4> interface failed");
+
+ if (ipv6Local->GetNAddresses (interfaceLocal) > 1)
+ {
+ NS_LOG_WARN ("Warning, interface has multiple IP addresses; using only the primary one");
+ }
+ Ipv6Address addrLocal = ipv6Local->GetAddress (interfaceLocal, 0).GetAddress ();
+ Ipv6Prefix maskLocal = ipv6Local->GetAddress (interfaceLocal, 0).GetPrefix ();
+ NS_LOG_LOGIC ("Working with local address " << addrLocal);
+ uint16_t metricLocal = ipv6Local->GetMetric (interfaceLocal);
+
+ //
+ // Check to see if the net device is connected to a channel/network that has
+ // another router on it. If there is no other router on the link (but us) then
+ // this is a stub network. If we find another router, then what we have here
+ // is a transit network.
+ //
+ if (AnotherRouterOnLink (nd, true) == false)
+ {
+ //
+ // This is a net device connected to a stub network
+ //
+ NS_LOG_LOGIC("Router-LSA Stub Network");
+ plr->SetLinkType (GlobalRouting6LinkRecord::StubNetwork);
+
+ //
+ // According to OSPF, the Link ID is the IP network number of
+ // the attached network.
+ //
+ plr->SetLinkId (addrLocal.CombinePrefix(maskLocal));
+
+ //
+ // and the Link Data is the network mask; converted to Ipv4Address
+ //
+ Ipv6Address maskLocalAddr;
+ uint8_t addr[16];
+ maskLocal.GetBytes(addr);
+ maskLocalAddr.Set(addr);
+ plr->SetLinkData (maskLocalAddr);
+ plr->SetMetric (metricLocal);
+ pLSA->AddLinkRecord(plr);
+ plr = 0;
+ }
+ else
+ {
+ //
+ // We have multiple routers on a broadcast interface, so this is
+ // a transit network.
+ //
+ NS_LOG_LOGIC ("Router-LSA Transit Network");
+ plr->SetLinkType (GlobalRouting6LinkRecord::TransitNetwork);
+
+ //
+ // By definition, the router with the lowest IP address is the
+ // designated router for the network. OSPF says that the Link ID
+ // gets the IP interface address of the designated router in this
+ // case.
+ //
+ Ipv6Address desigRtr = FindDesignatedRouterForLink (nd, true);
+
+ //
+ // Let's double-check that any designated router we find out on our
+ // network is really on our network.
+ //
+ if (desigRtr != "FFFF:FFFF:FFFF:FFFF:FFFF:FFFF:FFFF:FFFF")
+ {
+ Ipv6Address networkHere = addrLocal.CombinePrefix (maskLocal);
+ Ipv6Address networkThere = desigRtr.CombinePrefix (maskLocal);
+ NS_ABORT_MSG_UNLESS (networkHere == networkThere,
+ "Global6Router::ProcessSingleBroadcastLink(): Network number confusion");
+ }
+ if (desigRtr == addrLocal)
+ {
+ c.Add (nd);
+ NS_LOG_LOGIC ("Node " << node->GetId () << " elected a designated router");
+ }
+ plr->SetLinkId (desigRtr);
+
+ //
+ // OSPF says that the Link Data is this router's own IP address.
+ //
+ plr->SetLinkData (addrLocal);
+ plr->SetMetric (metricLocal);
+ pLSA->AddLinkRecord (plr);
+ plr = 0;
+ }
+}
+
+ void
+Global6Router::ProcessBridgedBroadcastLink (Ptr<NetDevice> nd, GlobalRouting6LSA *pLSA, NetDeviceContainer &c)
+{
+ NS_LOG_FUNCTION (nd << pLSA << &c);
+ NS_ASSERT_MSG (nd->IsBridge (), "Global6Router::ProcessBridgedBroadcastLink(): Called with non-bridge net device");
+
+#if 0
+ //
+ // It is possible to admit the possibility that a bridge device on a node
+ // can also participate in routing. This would surprise people who don't
+ // come from Microsoft-land where they do use such a construct. Based on
+ // the principle of least-surprise, we will leave the relatively simple
+ // code in place to do this, but not enable it until someone really wants
+ // the capability. Even then, we will not enable this code as a default
+ // but rather something you will have to go and turn on.
+ //
+
+ Ptr<BridgeNetDevice> bnd = nd->GetObject<BridgeNetDevice> ();
+ NS_ABORT_MSG_UNLESS (bnd, "Global6Router::DiscoverLSAs (): GetObject for <BridgeNetDevice> failed");
+
+ //
+ // We have some preliminaries to do to get enough information to proceed.
+ // This information we need comes from the internet stack, so notice that
+ // there is an implied assumption that global routing is only going to
+ // work with devices attached to the internet stack (have an ipv4 interface
+ // associated to them.
+ //
+ Ptr<Node> node = nd->GetNode ();
+
+ uint32_t interfaceLocal;
+ bool rc = FindInterfaceForDevice(node, nd, interfaceLocal);
+ NS_ABORT_MSG_IF (rc == false, "Global6Router::ProcessBridgedBroadcastLink(): No interface index associated with device");
+
+ Ptr<Ipv4> ipv4Local = node->GetObject<Ipv4> ();
+ NS_ABORT_MSG_UNLESS (ipv4Local, "Global6Router::ProcessBridgedBroadcastLink (): GetObject for <Ipv4> interface failed");
+
+ if (ipv4Local->GetNAddresses (interfaceLocal) > 1)
+ {
+ NS_LOG_WARN ("Warning, interface has multiple IP addresses; using only the primary one");
+ }
+ Ipv4Address addrLocal = ipv4Local->GetAddress (interfaceLocal, 0).GetLocal ();
+ Ipv4Mask maskLocal = ipv4Local->GetAddress (interfaceLocal, 0).GetMask ();;
+ NS_LOG_LOGIC ("Working with local address " << addrLocal);
+ uint16_t metricLocal = ipv4Local->GetMetric (interfaceLocal);
+
+ //
+ // We need to handle a bridge on the router. This means that we have been
+ // given a net device that is a BridgeNetDevice. It has an associated Ipv4
+ // interface index and address. Some number of other net devices live "under"
+ // the bridge device as so-called bridge ports. In a nutshell, what we have
+ // to do is to repeat what is done for a single broadcast link on all of
+ // those net devices living under the bridge (trolls?)
+ //
+
+ bool areTransitNetwork = false;
+ Ipv4Address desigRtr ("255.255.255.255");
+
+ for (uint32_t i = 0; i < bnd->GetNBridgePorts (); ++i)
+ {
+ Ptr<NetDevice> ndTemp = bnd->GetBridgePort (i);
+
+ //
+ // We have to decide if we are a transit network. This is characterized
+ // by the presence of another router on the network segment. If we find
+ // another router on any of our bridged links, we are a transit network.
+ //
+ if (AnotherRouterOnLink (ndTemp, true))
+ {
+ areTransitNetwork = true;
+
+ //
+ // If we're going to be a transit network, then we have got to elect
+ // a designated router for the whole bridge. This means finding the
+ // router with the lowest IP address on the whole bridge. We ask
+ // for the lowest address on each segment and pick the lowest of them
+ // all.
+ //
+ Ipv4Address desigRtrTemp = FindDesignatedRouterForLink (ndTemp, true);
+
+ //
+ // Let's double-check that any designated router we find out on our
+ // network is really on our network.
+ //
+ if (desigRtrTemp != "255.255.255.255")
+ {
+ Ipv4Address networkHere = addrLocal.CombineMask (maskLocal);
+ Ipv4Address networkThere = desigRtrTemp.CombineMask (maskLocal);
+ NS_ABORT_MSG_UNLESS (networkHere == networkThere,
+ "Global6Router::ProcessSingleBroadcastLink(): Network number confusion");
+ }
+ if (desigRtrTemp < desigRtr)
+ {
+ desigRtr = desigRtrTemp;
+ }
+ }
+ }
+ //
+ // That's all the information we need to put it all together, just like we did
+ // in the case of a single broadcast link.
+ //
+
+ GlobalRouting6LinkRecord *plr = new GlobalRouting6LinkRecord;
+ NS_ABORT_MSG_IF (plr == 0, "Global6Router::ProcessBridgedBroadcastLink(): Can't alloc link record");
+
+ if (areTransitNetwork == false)
+ {
+ //
+ // This is a net device connected to a bridge of stub networks
+ //
+ NS_LOG_LOGIC("Router-LSA Stub Network");
+ plr->SetLinkType (GlobalRouting6LinkRecord::StubNetwork);
+
+ //
+ // According to OSPF, the Link ID is the IP network number of
+ // the attached network.
+ //
+ plr->SetLinkId (addrLocal.CombineMask(maskLocal));
+
+ //
+ // and the Link Data is the network mask; converted to Ipv4Address
+ //
+ Ipv4Address maskLocalAddr;
+ maskLocalAddr.Set(maskLocal.Get ());
+ plr->SetLinkData (maskLocalAddr);
+ plr->SetMetric (metricLocal);
+ pLSA->AddLinkRecord(plr);
+ plr = 0;
+ }
+ else
+ {
+ //
+ // We have multiple routers on a bridged broadcast interface, so this is
+ // a transit network.
+ //
+ NS_LOG_LOGIC ("Router-LSA Transit Network");
+ plr->SetLinkType (GlobalRouting6LinkRecord::TransitNetwork);
+
+ //
+ // By definition, the router with the lowest IP address is the
+ // designated router for the network. OSPF says that the Link ID
+ // gets the IP interface address of the designated router in this
+ // case.
+ //
+ if (desigRtr == addrLocal)
+ {
+ c.Add (nd);
+ NS_LOG_LOGIC ("Node " << node->GetId () << " elected a designated router");
+ }
+ plr->SetLinkId (desigRtr);
+
+ //
+ // OSPF says that the Link Data is this router's own IP address.
+ //
+ plr->SetLinkData (addrLocal);
+ plr->SetMetric (metricLocal);
+ pLSA->AddLinkRecord (plr);
+ plr = 0;
+ }
+#endif
+}
+
+ void
+Global6Router::ProcessPointToPointLink (Ptr<NetDevice> ndLocal, GlobalRouting6LSA *pLSA)
+{
+ NS_LOG_FUNCTION (ndLocal << pLSA);
+
+ //
+ // We have some preliminaries to do to get enough information to proceed.
+ // This information we need comes from the internet stack, so notice that
+ // there is an implied assumption that global routing is only going to
+ // work with devices attached to the internet stack (have an ipv4 interface
+ // associated to them.
+ //
+ Ptr<Node> nodeLocal = ndLocal->GetNode ();
+
+ uint32_t interfaceLocal;
+ bool rc = FindInterfaceForDevice(nodeLocal, ndLocal, interfaceLocal);
+ NS_ABORT_MSG_IF (rc == false, "Global6Router::ProcessPointToPointLink (): No interface index associated with device");
+
+ Ptr<Ipv6> ipv6Local = nodeLocal->GetObject<Ipv6> ();
+ NS_ABORT_MSG_UNLESS (ipv6Local, "Global6Router::ProcessPointToPointLink (): GetObject for <Ipv6> interface failed");
+
+ if (ipv6Local->GetNAddresses (interfaceLocal) > 1)
+ {
+ NS_LOG_WARN ("Warning, interface has multiple IP addresses; using only the primary one");
+ }
+ Ipv6Address addrLocal = ipv6Local->GetAddress (interfaceLocal, 0).GetAddress ();
+ Ipv6Prefix maskLocal = ipv6Local->GetAddress (interfaceLocal, 0).GetPrefix ();
+ NS_LOG_LOGIC ("Working with local address " << addrLocal);
+ uint16_t metricLocal = ipv6Local->GetMetric (interfaceLocal);
+
+ //
+ // Now, we're going to walk over to the remote net device on the other end of
+ // the point-to-point channel we know we have. This is where our adjacent
+ // router (to use OSPF lingo) is running.
+ //
+ Ptr<Channel> ch = ndLocal->GetChannel();
+
+ //
+ // Get the net device on the other side of the point-to-point channel.
+ //
+ 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. Note a
+ // requirement that nodes on either side of a point-to-point link must have
+ // internet stacks; and an assumption that point-to-point links are incompatible
+ // with bridging.
+ //
+ Ptr<Node> nodeRemote = ndRemote->GetNode();
+ Ptr<Ipv6> ipv6Remote = nodeRemote->GetObject<Ipv6> ();
+ NS_ABORT_MSG_UNLESS (ipv6Remote,
+ "Global6Router::ProcessPointToPointLink(): GetObject for remote <Ipv6> failed");
+
+ //
+ // Further note the requirement that nodes on either side of a point-to-point
+ // link must participate in global routing and therefore have a Global6Router
+ // interface aggregated.
+ //
+ Ptr<Global6Router> rtrRemote = nodeRemote->GetObject<Global6Router> ();
+ if (rtrRemote == 0)
+ {
+ // This case is possible if the remote does not participate in global routing
+ return;
+ }
+ //
+ // We're going to need the remote router ID, so we might as well get it now.
+ //
+ Ipv6Address rtrIdRemote = rtrRemote->GetRouterId();
+ NS_LOG_LOGIC ("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 interfaceRemote;
+ rc = FindInterfaceForDevice(nodeRemote, ndRemote, interfaceRemote);
+ NS_ABORT_MSG_IF (rc == false, "Global6Router::ProcessPointToPointLinks(): No interface index associated with remote device");
+
+ //
+ // Now that we have the Ipv4 interface, we can get the (remote) address and
+ // mask we need.
+ //
+ if (ipv6Remote->GetNAddresses (interfaceRemote) > 1)
+ {
+ NS_LOG_WARN ("Warning, interface has multiple IP addresses; using only the primary one");
+ }
+ Ipv6Address addrRemote = ipv6Remote->GetAddress (interfaceRemote, 0).GetAddress ();
+ Ipv6Prefix maskRemote = ipv6Remote->GetAddress (interfaceRemote, 0).GetPrefix ();
+ NS_LOG_LOGIC ("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.
+ //
+ GlobalRouting6LinkRecord *plr;
+ if (ipv6Remote->IsUp (interfaceRemote))
+ {
+ NS_LOG_LOGIC ("Remote side interface " << interfaceRemote << " is up-- add a type 1 link");
+
+ plr = new GlobalRouting6LinkRecord;
+ NS_ABORT_MSG_IF (plr == 0, "Global6Router::ProcessPointToPointLink(): Can't alloc link record");
+ plr->SetLinkType (GlobalRouting6LinkRecord::PointToPoint);
+ plr->SetLinkId (rtrIdRemote);
+ plr->SetLinkData (addrLocal);
+ plr->SetMetric (metricLocal);
+ pLSA->AddLinkRecord (plr);
+ plr = 0;
+ }
+
+ // Regardless of state of peer, add a type 3 link (RFC 2328: 12.4.1.1)
+ plr = new GlobalRouting6LinkRecord;
+ NS_ABORT_MSG_IF (plr == 0, "Global6Router::ProcessPointToPointLink(): Can't alloc link record");
+ plr->SetLinkType (GlobalRouting6LinkRecord::StubNetwork);
+ plr->SetLinkId (addrRemote);
+ uint8_t addr[16];
+ maskRemote.GetBytes(addr);
+ plr->SetLinkData (Ipv6Address(addr)); // Frown
+ plr->SetMetric (metricLocal);
+ pLSA->AddLinkRecord (plr);
+ plr = 0;
+}
+
+ void
+Global6Router::BuildNetworkLSAs (NetDeviceContainer c)
+{
+ NS_LOG_FUNCTION (&c);
+
+ uint32_t nDesignatedRouters = c.GetN ();
+
+ for (uint32_t i = 0; i < nDesignatedRouters; ++i)
+ {
+ //
+ // Build one NetworkLSA for each net device talking to a network that we are the
+ // designated router for. These devices are in the provided container.
+ //
+ Ptr<NetDevice> ndLocal = c.Get (i);
+ Ptr<Node> node = ndLocal->GetNode ();
+
+ uint32_t interfaceLocal;
+ bool rc = FindInterfaceForDevice(node, ndLocal, interfaceLocal);
+ NS_ABORT_MSG_IF (rc == false, "Global6Router::BuildNetworkLSAs (): No interface index associated with device");
+
+ Ptr<Ipv6> ipv6Local = node->GetObject<Ipv6> ();
+ NS_ABORT_MSG_UNLESS (ipv6Local, "Global6Router::ProcessPointToPointLink (): GetObject for <Ipv6> interface failed");
+
+ if (ipv6Local->GetNAddresses (interfaceLocal) > 1)
+ {
+ NS_LOG_WARN ("Warning, interface has multiple IP addresses; using only the primary one");
+ }
+ Ipv6Address addrLocal = ipv6Local->GetAddress (interfaceLocal, 0).GetAddress ();
+ Ipv6Prefix maskLocal = ipv6Local->GetAddress (interfaceLocal, 0).GetPrefix ();
+
+ GlobalRouting6LSA *pLSA = new GlobalRouting6LSA;
+ NS_ABORT_MSG_IF (pLSA == 0, "Global6Router::BuildNetworkLSAs(): Can't alloc link record");
+
+ pLSA->SetLSType (GlobalRouting6LSA::NetworkLSA);
+ pLSA->SetLinkStateId (addrLocal);
+ pLSA->SetAdvertisingRouter (m_routerId);
+ pLSA->SetNetworkLSANetworkMask (maskLocal);
+ pLSA->SetStatus (GlobalRouting6LSA::LSA_SPF_NOT_EXPLORED);
+ pLSA->SetNode (node);
+
+ //
+ // Build a list of AttachedRouters by walking the devices in the channel
+ // and, if we find a node with a Global6Router interface and an IPv4
+ // interface associated with that device, we call it an attached router.
+ //
+ Ptr<Channel> ch = ndLocal->GetChannel();
+ uint32_t nDevices = ch->GetNDevices();
+ NS_ASSERT (nDevices);
+
+ for (uint32_t i = 0; i < nDevices; i++)
+ {
+ Ptr<NetDevice> tempNd = ch->GetDevice (i);
+ NS_ASSERT (tempNd);
+ Ptr<Node> tempNode = tempNd->GetNode ();
+
+ //
+ // Does the node in question have a Global6Router interface? If not it can
+ // hardly be considered an attached router.
+ //
+ Ptr<Global6Router> rtr = tempNode->GetObject<Global6Router> ();
+ if (rtr == 0)
+ {
+ continue;
+ }
+
+ //
+ // Does the attached node have an ipv4 interface for the device we're probing?
+ // If not, it can't play router.
+ //
+ uint32_t tempInterface;
+ if (FindInterfaceForDevice (tempNode, tempNd, tempInterface))
+ {
+ Ptr<Ipv6> tempIpv6 = tempNode->GetObject<Ipv6> ();
+ NS_ASSERT (tempIpv6);
+ if (!tempIpv6->IsUp (tempInterface))
+ {
+ NS_LOG_LOGIC ("Remote side interface " << tempInterface << " not up");
+ }
+ else
+ {
+ if (tempIpv6->GetNAddresses (tempInterface) > 1)
+ {
+ NS_LOG_WARN ("Warning, interface has multiple IP addresses; using only the primary one");
+ }
+ Ipv6Address tempAddr = tempIpv6->GetAddress(tempInterface, 0).GetAddress ();
+ pLSA->AddAttachedRouter (tempAddr);
+ }
+ }
+ }
+ m_LSAs.push_back (pLSA);
+ pLSA = 0;
+ }
+}
+
+//
+// Given a local net device, we need to walk the channel to which the net device is
+// attached and look for nodes with Global6Router interfaces on them (one of them
+// will be us). Of these, the router with the lowest IP address on the net device
+// connecting to the channel becomes the designated router for the link.
+//
+ Ipv6Address
+Global6Router::FindDesignatedRouterForLink (Ptr<NetDevice> ndLocal, bool allowRecursion) const
+{
+ NS_LOG_FUNCTION (ndLocal << allowRecursion);
+
+ Ptr<Channel> ch = ndLocal->GetChannel();
+ uint32_t nDevices = ch->GetNDevices();
+ NS_ASSERT (nDevices);
+
+ NS_LOG_LOGIC ("Looking for designated router off of net device " << ndLocal << " on node " <<
+ ndLocal->GetNode ()->GetId ());
+
+ Ipv6Address desigRtr ("FFFF:FFFF:FFFF:FFFF:FFFF:FFFF:FFFF:FFFF");
+
+ //
+ // Look through all of the devices on the channel to which the net device
+ // in question is attached.
+ //
+ for (uint32_t i = 0; i < nDevices; i++)
+ {
+ Ptr<NetDevice> ndOther = ch->GetDevice (i);
+ NS_ASSERT (ndOther);
+
+ Ptr<Node> nodeOther = ndOther->GetNode ();
+
+ NS_LOG_LOGIC ("Examine channel device " << i << " on node " << nodeOther->GetId ());
+
+ //
+ // For all other net devices, we need to check and see if a router
+ // is present. If the net device on the other side is a bridged
+ // device, we need to consider all of the other devices on the
+ // bridge as well (all of the bridge ports.
+ //
+ NS_LOG_LOGIC ("checking to see if the device is bridged");
+ Ptr<BridgeNetDevice> bnd = NetDeviceIsBridged (ndOther);
+ if (bnd)
+ {
+ NS_LOG_LOGIC ("Device is bridged by BridgeNetDevice " << bnd);
+
+ //
+ // It is possible that the bridge net device is sitting under a
+ // router, so we have to check for the presence of that router
+ // before we run off and follow all the links
+ //
+ // We require a designated router to have a Global6Router interface and
+ // an internet stack that includes the Ipv4 interface. If it doesn't
+ // it can't play router.
+ //
+ NS_LOG_LOGIC ("Checking for router on bridge net device " << bnd);
+ Ptr<Global6Router> rtr = nodeOther->GetObject<Global6Router> ();
+ Ptr<Ipv6> ipv6 = nodeOther->GetObject<Ipv6> ();
+ if (rtr && ipv6)
+ {
+ uint32_t interfaceOther;
+ if (FindInterfaceForDevice(nodeOther, bnd, interfaceOther))
+ {
+ NS_LOG_LOGIC ("Found router on bridge net device " << bnd);
+ if (!ipv6->IsUp (interfaceOther))
+ {
+ NS_LOG_LOGIC ("Remote side interface " << interfaceOther << " not up");
+ continue;
+ }
+ if (ipv6->GetNAddresses (interfaceOther) > 1)
+ {
+ NS_LOG_WARN ("Warning, interface has multiple IP addresses; using only the primary one");
+ }
+ Ipv6Address addrOther = ipv6->GetAddress (interfaceOther, 0).GetAddress ();
+ desigRtr = addrOther < desigRtr ? addrOther : desigRtr;
+ NS_LOG_LOGIC ("designated router now " << desigRtr);
+ }
+ }
+
+ NS_LOG_LOGIC ("Looking through bridge ports of bridge net device " << bnd);
+ for (uint32_t j = 0; j < bnd->GetNBridgePorts (); ++j)
+ {
+ Ptr<NetDevice> ndBridged = bnd->GetBridgePort (j);
+ NS_LOG_LOGIC ("Examining bridge port " << j << " device " << ndBridged);
+ if (ndBridged == ndOther)
+ {
+ NS_LOG_LOGIC ("That bridge port is me, don't walk backward");
+ continue;
+ }
+
+ if (allowRecursion)
+ {
+ NS_LOG_LOGIC ("Recursively looking for routers down bridge port " << ndBridged);
+ Ipv6Address addrOther = FindDesignatedRouterForLink (ndBridged, false);
+ desigRtr = addrOther < desigRtr ? addrOther : desigRtr;
+ NS_LOG_LOGIC ("designated router now " << desigRtr);
+ }
+ }
+ }
+ else
+ {
+ NS_LOG_LOGIC ("This device is not bridged");
+ Ptr<Node> nodeOther = ndOther->GetNode ();
+ NS_ASSERT (nodeOther);
+
+ //
+ // We require a designated router to have a Global6Router interface and
+ // an internet stack that includes the Ipv4 interface. If it doesn't
+ //
+ Ptr<Global6Router> rtr = nodeOther->GetObject<Global6Router> ();
+ Ptr<Ipv6> ipv6 = nodeOther->GetObject<Ipv6> ();
+ if (rtr && ipv6)
+ {
+ uint32_t interfaceOther;
+ if (FindInterfaceForDevice(nodeOther, ndOther, interfaceOther))
+ {
+ if (!ipv6->IsUp (interfaceOther))
+ {
+ NS_LOG_LOGIC ("Remote side interface " << interfaceOther << " not up");
+ continue;
+ }
+ NS_LOG_LOGIC ("Found router on net device " << ndOther);
+ if (ipv6->GetNAddresses (interfaceOther) > 1)
+ {
+ NS_LOG_WARN ("Warning, interface has multiple IP addresses; using only the primary one");
+ }
+ Ipv6Address addrOther = ipv6->GetAddress (interfaceOther, 0).GetAddress ();
+ desigRtr = addrOther < desigRtr ? addrOther : desigRtr;
+ NS_LOG_LOGIC ("designated router now " << desigRtr);
+ }
+ }
+ }
+ }
+ return desigRtr;
+}
+
+//
+// Given a node and an attached net device, take a look off in the channel to
+// which the net device is attached and look for a node on the other side
+// that has a Global6Router interface aggregated. Life gets more complicated
+// when there is a bridged net device on the other side.
+//
+ bool
+Global6Router::AnotherRouterOnLink (Ptr<NetDevice> nd, bool allowRecursion) const
+{
+ NS_LOG_FUNCTION (nd << allowRecursion);
+
+ Ptr<Channel> ch = nd->GetChannel();
+ if (!ch)
+ {
+ // It may be that this net device is a stub device, without a channel
+ return false;
+ }
+ uint32_t nDevices = ch->GetNDevices();
+ NS_ASSERT (nDevices);
+
+ NS_LOG_LOGIC ("Looking for routers off of net device " << nd << " on node " << nd->GetNode ()->GetId ());
+
+ //
+ // Look through all of the devices on the channel to which the net device
+ // in question is attached.
+ //
+ for (uint32_t i = 0; i < nDevices; i++)
+ {
+ Ptr<NetDevice> ndOther = ch->GetDevice (i);
+ NS_ASSERT (ndOther);
+
+ NS_LOG_LOGIC ("Examine channel device " << i << " on node " << ndOther->GetNode ()->GetId ());
+
+ //
+ // Ignore the net device itself.
+ //
+ if (ndOther == nd)
+ {
+ NS_LOG_LOGIC ("Myself, skip");
+ continue;
+ }
+
+ //
+ // For all other net devices, we need to check and see if a router
+ // is present. If the net device on the other side is a bridged
+ // device, we need to consider all of the other devices on the
+ // bridge.
+ //
+ NS_LOG_LOGIC ("checking to see if device is bridged");
+ Ptr<BridgeNetDevice> bnd = NetDeviceIsBridged (ndOther);
+ if (bnd)
+ {
+ NS_LOG_LOGIC ("Device is bridged by net device " << bnd);
+ NS_LOG_LOGIC ("Looking through bridge ports of bridge net device " << bnd);
+ for (uint32_t j = 0; j < bnd->GetNBridgePorts (); ++j)
+ {
+ Ptr<NetDevice> ndBridged = bnd->GetBridgePort (j);
+ NS_LOG_LOGIC ("Examining bridge port " << j << " device " << ndBridged);
+ if (ndBridged == ndOther)
+ {
+ NS_LOG_LOGIC ("That bridge port is me, skip");
+ continue;
+ }
+
+ if (allowRecursion)
+ {
+ NS_LOG_LOGIC ("Recursively looking for routers on bridge port " << ndBridged);
+ if (AnotherRouterOnLink (ndBridged, false))
+ {
+ NS_LOG_LOGIC ("Found routers on bridge port, return true");
+ return true;
+ }
+ }
+ }
+ NS_LOG_LOGIC ("No routers on bridged net device, return false");
+ return false;
+ }
+
+ NS_LOG_LOGIC ("This device is not bridged");
+ Ptr<Node> nodeTemp = ndOther->GetNode ();
+ NS_ASSERT (nodeTemp);
+
+ Ptr<Global6Router> rtr = nodeTemp->GetObject<Global6Router> ();
+ if (rtr)
+ {
+ NS_LOG_LOGIC ("Found Global6Router interface, return true");
+ return true;
+ }
+ else
+ {
+ NS_LOG_LOGIC ("No Global6Router interface on device, continue search");
+ }
+ }
+ NS_LOG_LOGIC ("No routers found, return false");
+ return false;
+}
+
+ uint32_t
+Global6Router::GetNumLSAs (void) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ return m_LSAs.size ();
+}
+
+//
+// Get the nth link state advertisement from this router.
+//
+ bool
+Global6Router::GetLSA (uint32_t n, GlobalRouting6LSA &lsa) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ NS_ASSERT_MSG(lsa.IsEmpty(), "Global6Router::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)
+ {
+ GlobalRouting6LSA *p = *i;
+ lsa = *p;
+ return true;
+ }
+ }
+
+ return false;
+}
+
+void
+Global6Router::InjectRoute (Ipv6Address network, Ipv6Prefix networkPrefix)
+{
+ NS_LOG_FUNCTION (network << networkPrefix);
+ Ipv6RoutingTableEntry *route = new Ipv6RoutingTableEntry ();
+//
+// Interface number does not matter here, using 1.
+//
+ *route = Ipv6RoutingTableEntry::CreateNetworkRouteTo (network,
+ networkPrefix,
+ 1);
+ m_injectedRoutes.push_back (route);
+}
+
+Ipv6RoutingTableEntry *
+Global6Router::GetInjectedRoute (uint32_t index)
+{
+ NS_LOG_FUNCTION (index);
+ if (index < m_injectedRoutes.size ())
+ {
+ uint32_t tmp = 0;
+ for (InjectedRoutesCI i = m_injectedRoutes.begin ();
+ i != m_injectedRoutes.end ();
+ i++)
+ {
+ if (tmp == index)
+ {
+ return *i;
+ }
+ tmp++;
+ }
+ }
+ NS_ASSERT (false);
+ // quiet compiler.
+ return 0;
+}
+
+uint32_t
+Global6Router::GetNInjectedRoutes ()
+{
+ return m_injectedRoutes.size ();
+}
+
+void
+Global6Router::RemoveInjectedRoute (uint32_t index)
+{
+ NS_LOG_FUNCTION (index);
+ NS_ASSERT (index < m_injectedRoutes.size ());
+ uint32_t tmp = 0;
+ for (InjectedRoutesI i = m_injectedRoutes.begin (); i != m_injectedRoutes.end (); i++)
+ {
+ if (tmp == index)
+ {
+ NS_LOG_LOGIC ("Removing route " << index << "; size = " << m_injectedRoutes.size());
+ delete *i;
+ m_injectedRoutes.erase (i);
+ return;
+ }
+ tmp++;
+ }
+}
+
+bool
+Global6Router::WithdrawRoute (Ipv6Address network, Ipv6Prefix networkPrefix)
+{
+ NS_LOG_FUNCTION (network << networkPrefix);
+ for (InjectedRoutesI i = m_injectedRoutes.begin (); i != m_injectedRoutes.end (); i++)
+ {
+ if ((*i)->GetDestNetwork () == network && (*i)->GetDestNetworkPrefix () == networkPrefix)
+ {
+ NS_LOG_LOGIC ("Withdrawing route to network/prefix " << network << "/" << networkPrefix);
+ delete *i;
+ m_injectedRoutes.erase (i);
+ 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>
+Global6Router::GetAdjacent (Ptr<NetDevice> nd, Ptr<Channel> ch) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ NS_ASSERT_MSG(ch->GetNDevices() == 2, "Global6Router::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,
+ "Global6Router::GetAdjacent (): Wrong or confused channel?");
+ return 0;
+ }
+}
+
+//
+// Given a node and a net device, find an IPV4 interface index that corresponds
+// to that net device. This function may fail for various reasons. If a node
+// does not have an internet stack (for example if it is a bridge) we won't have
+// an IPv4 at all. If the node does have a stack, but the net device in question
+// is bridged, there will not be an interface associated directly with the device.
+//
+ bool
+Global6Router::FindInterfaceForDevice (Ptr<Node> node, Ptr<NetDevice> nd, uint32_t &index) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ NS_LOG_LOGIC("For node " << node->GetId () << " for net device " << nd );
+
+ Ptr<Ipv6> ipv6 = node->GetObject<Ipv6> ();
+ if (ipv6 == 0)
+ {
+ NS_LOG_LOGIC ("No Ipv6 interface on node " << node->GetId ());
+ return false;
+ }
+
+ for (uint32_t i = 0; i < ipv6->GetNInterfaces(); ++i )
+ {
+ if (ipv6->GetNetDevice(i) == nd)
+ {
+ NS_LOG_LOGIC ("Device " << nd << " has associated ipv6 index " << i);
+ index = i;
+ return true;
+ }
+ }
+
+ NS_LOG_LOGIC ("Device " << nd << " has no associated ipv6 index");
+ return false;
+}
+
+//
+// Decide whether or not a given net device is being bridged by a BridgeNetDevice.
+//
+ Ptr<BridgeNetDevice>
+Global6Router::NetDeviceIsBridged (Ptr<NetDevice> nd) const
+{
+ NS_LOG_FUNCTION (nd);
+
+ Ptr<Node> node = nd->GetNode ();
+ uint32_t nDevices = node->GetNDevices();
+
+ //
+ // There is no bit on a net device that says it is being bridged, so we have
+ // to look for bridges on the node to which the device is attached. If we
+ // find a bridge, we need to look through its bridge ports (the devices it
+ // bridges) to see if we find the device in question.
+ //
+ for (uint32_t i = 0; i < nDevices; ++i)
+ {
+ Ptr<NetDevice> ndTest = node->GetDevice(i);
+ NS_LOG_LOGIC ("Examine device " << i << " " << ndTest);
+
+ if (ndTest->IsBridge ())
+ {
+ NS_LOG_LOGIC ("device " << i << " is a bridge net device");
+ Ptr<BridgeNetDevice> bnd = ndTest->GetObject<BridgeNetDevice> ();
+ NS_ABORT_MSG_UNLESS (bnd, "Global6Router::DiscoverLSAs (): GetObject for <BridgeNetDevice> failed");
+
+ for (uint32_t j = 0; j < bnd->GetNBridgePorts (); ++j)
+ {
+ NS_LOG_LOGIC ("Examine bridge port " << j << " " << bnd->GetBridgePort (j));
+ if (bnd->GetBridgePort (j) == nd)
+ {
+ NS_LOG_LOGIC ("Net device " << nd << " is bridged by " << bnd);
+ return bnd;
+ }
+ }
+ }
+ }
+ NS_LOG_LOGIC ("Net device " << nd << " is not bridged");
+ return 0;
+}
+
+} // namespace ns3
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/internet/model/ipv6-global-router-interface.h Tue Aug 30 02:11:57 2011 +0530
@@ -0,0 +1,805 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright 2007 University of Washington
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Authors: Craig Dowell (craigdo@ee.washington.edu)
+ * Tom Henderson (tomhend@u.washington.edu)
+ */
+
+#ifndef GLOBAL_ROUTER_6_INTERFACE_H
+#define GLOBAL_ROUTER_6_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/ipv6-address.h"
+#include "ns3/net-device-container.h"
+#include "ns3/bridge-net-device.h"
+#include "ns3/ipv6-global-route-manager.h"
+#include "ns3/ipv6-routing-table-entry.h"
+
+namespace ns3 {
+
+class Global6Router;
+class Ipv6GlobalRouting;
+
+/**
+ * @brief A single link record for a link state advertisement.
+ *
+ * The GlobalRouting6LinkRecord 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 GlobalRouting6LinkRecord
+{
+public:
+ friend class GlobalRouting6LSA;
+/**
+ * @enum LinkType
+ * @brief Enumeration of the possible types of Global Routing 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 Routing 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.
+ */
+ GlobalRouting6LinkRecord ();
+
+/**
+ * Construct an initialized Global Routing 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
+ */
+ GlobalRouting6LinkRecord (
+ LinkType linkType,
+ Ipv6Address linkId,
+ Ipv6Address linkData,
+ uint16_t metric);
+
+/**
+ * @brief Destroy a Global Routing Link Record.
+ *
+ * Currently does nothing. Here as a placeholder only.
+ */
+ ~GlobalRouting6LinkRecord ();
+
+/**
+ * Get the Link ID field of the Global Routing 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.
+ */
+ Ipv6Address GetLinkId(void) const;
+
+/**
+ * @brief Set the Link ID field of the Global Routing 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(Ipv6Address addr);
+
+/**
+ * @brief Get the Link Data field of the Global Routing 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.
+ */
+ Ipv6Address GetLinkData(void) const;
+
+/**
+ * @brief Set the Link Data field of the Global Routing 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(Ipv6Address addr);
+
+/**
+ * @brief Get the Link Type field of the Global Routing 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 Routing Link Record.
+ */
+ LinkType GetLinkType(void) const;
+
+/**
+ * @brief Set the Link Type field of the Global Routing 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 Routing Link Record.
+ */
+ void SetLinkType(LinkType linkType);
+
+/**
+ * @brief Get the Metric Data field of the Global Routing 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 Routing Link Record.
+ */
+ uint16_t GetMetric(void) const;
+
+/**
+ * @brief Set the Metric Data field of the Global Routing 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 Routing Link Record.
+ */
+ void SetMetric(uint16_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
+ */
+ Ipv6Address 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
+ */
+ Ipv6Address m_linkData; // for links to RouterLSA,
+
+/**
+ * The type of the Global Routing 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.
+ */
+ uint16_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 GlobalRouting6LSA
+{
+public:
+/**
+ * @enum LSHandling
+ * @brief corresponds to LS handling bit of the LS type or LSA header
+ */
+ enum LSHandling {
+ LinkLocalFloodingScope=0,
+ StoreandFlood
+ };
+/**
+ * @enum FloodingScope
+ * @brief corresponds to Flooding Scope of the LSA
+ */
+ enum FloodingScope {
+ LinkLocalScoping=0,
+ AreaScoping,
+ ASScoping,
+ Reserved
+ };
+/**
+ * @enum LSType
+ * @brief corresponds to LS type field of RFC 2328 OSPF LSA header
+ */
+ enum LSType {
+ Unknown = 0, /**< Uninitialized Type */
+ RouterLSA,
+ NetworkLSA,
+ InterAreaPrefixLSA,
+ InterAreaRouterLSA,
+ ASExternalLSAs,
+ GroupmembershipLSA,
+ Type7LSA,
+ LinkLSA,
+ IntraAreaPrefixLSA
+ };
+/**
+ * @enum SPFStatus
+ * @brief Enumeration of the possible values of the status flag in the Routing
+ * 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 Routing Link State Advertisement.
+ *
+ * On completion Ipv4Address variables initialized to 0.0.0.0 and the
+ * list of Link State Records is empty.
+ */
+ GlobalRouting6LSA();
+
+/**
+ * @brief Create an initialized Global Routing 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.
+ */
+ GlobalRouting6LSA(SPFStatus status, Ipv6Address linkStateId,
+ Ipv6Address advertisingRtr);
+
+/**
+ * @brief Copy constructor for a Global Routing 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.
+ */
+ GlobalRouting6LSA (GlobalRouting6LSA& lsa);
+
+/**
+ * @brief Destroy an existing Global Routing Link State Advertisement.
+ *
+ * Any Global Routing Link Records present in the list are freed.
+ */
+ ~GlobalRouting6LSA();
+
+/**
+ * @brief Assignment operator for a Global Routing Link State Advertisement.
+ *
+ * Takes an existing Global Routing Link State Advertisement and overwrites
+ * it to make a semantically identical copy of a given prototype LSA.
+ *
+ * If there are any Global Routing 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.
+ */
+ GlobalRouting6LSA& operator= (const GlobalRouting6LSA& lsa);
+
+/**
+ * @brief Copy any Global Routing Link Records in a given Global Routing 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 GlobalRouting6LSA& lsa);
+
+/**
+ * @brief Add a given Global Routing Link Record to the LSA.
+ *
+ * @param lr The Global Routing Link Record to be added.
+ * @returns The number of link records in the list.
+ */
+ uint32_t AddLinkRecord (GlobalRouting6LinkRecord* lr);
+
+/**
+ * @brief Return the number of Global Routing 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 Routing Link Record.
+ *
+ * @param n The LSA number desired.
+ * @returns The number of link records in the list.
+ */
+ GlobalRouting6LinkRecord* GetLinkRecord (uint32_t n) const;
+
+/**
+ * @brief Release all of the Global Routing Link Records present in the Global
+ * Routing Link State Advertisement and make the list of link records empty.
+ */
+ void ClearLinkRecords(void);
+
+/**
+ * @brief Check to see if the list of Global Routing Link Records present in the
+ * Global Routing 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 Routing Link State Advertisement and
+ * any Global Routing Link Records present in the list. Quite verbose.
+ */
+ void Print (std::ostream &os) const;
+
+/**
+ * @brief Return the LSHandling field of the LSA
+ */
+ LSHandling GetLSHandling(void) const;
+/**
+ * @brief Set the LSHandling field of the LSA
+ */
+ void SetLSHandling(LSHandling handle);
+
+/**
+ * @brief Return the FloodingScope field of the LSA
+ */
+ FloodingScope GetFloodingScope(void) const;
+/**
+ * @brief Set the FloodingScope field of the LSA
+ */
+ void SetFloodingScope(FloodingScope scope);
+
+/**
+ * @brief Return the LSType field of the LSA
+ */
+ LSType GetLSType (void) const;
+/**
+ * @brief Set the LS type field of the LSA
+ */
+ void SetLSType (LSType typ);
+
+/**
+ * @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 GlobalRouting::GetRouterId ()
+ * @returns The Ipv4Address stored as the link state ID.
+ */
+ Ipv6Address 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.
+ * @param addr IPv4 address which will act as ID
+ * @see RoutingEnvironment::AllocateRouterId ()
+ * @see GlobalRouting::GetRouterId ()
+ */
+ void SetLinkStateId (Ipv6Address 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 GlobalRouting::GetRouterId ()
+ * @returns The Ipv4Address stored as the advertising router.
+ */
+ Ipv6Address 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.
+ *
+ * @param rtr ID of the router making advertisement
+ * @see RoutingEnvironment::AllocateRouterId ()
+ * @see GlobalRouting::GetRouterId ()
+ */
+ void SetAdvertisingRouter (Ipv6Address rtr);
+
+/**
+ * @brief For a Network LSA, set the Network Mask field that precedes
+ * the list of attached routers.
+ */
+ void SetNetworkLSANetworkMask (Ipv6Prefix prefix);
+
+/**
+ * @brief For a Network LSA, get the Network Mask field that precedes
+ * the list of attached routers.
+ *
+ * @returns the NetworkLSANetworkMask
+ */
+ Ipv6Prefix GetNetworkLSANetworkMask (void) const;
+
+/**
+ * @brief Add an attached router to the list in the NetworkLSA
+ *
+ * @param addr The Ipv4Address of the interface on the network link
+ * @returns The number of addresses in the list.
+ */
+ uint32_t AddAttachedRouter (Ipv6Address addr);
+
+/**
+ * @brief Return the number of attached routers listed in the NetworkLSA
+ *
+ * @returns The number of attached routers.
+ */
+ uint32_t GetNAttachedRouters (void) const;
+
+/**
+ * @brief Return an Ipv4Address corresponding to the specified attached router
+ *
+ * @param n The attached router number desired (number in the list).
+ * @returns The Ipv4Address of the requested router
+ */
+ Ipv6Address GetAttachedRouter (uint32_t n) const;
+
+/**
+ * @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
+ * @param status SPF status to set
+ * @see SPFStatus
+ */
+ void SetStatus (SPFStatus status);
+
+/**
+ * @brief Get the Node pointer of the node that originated this LSA
+ * @returns Node pointer
+ */
+ Ptr<Node> GetNode (void) const;
+
+/**
+ * @brief Set the Node pointer of the node that originated this LSA
+ * @param node Node pointer
+ */
+ void SetNode (Ptr<Node> node);
+
+private:
+/**
+ * LSA Handling.How the LSA should be handled by a router that
+ *does not recognize the LSA’s function code
+ */
+ LSHandling m_lsHandling;
+
+/**
+ * The flooding scope of the LSA
+ */
+ FloodingScope m_floodingScope;
+
+/**
+ * The type of the LSA. Each LSA type has a separate advertisement
+ * format.
+ */
+ LSType m_lsType;
+/**
+ * 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 GlobalRouting::GetRouterId ()
+ */
+ Ipv6Address 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 GlobalRouting::GetRouterId ()
+ */
+ Ipv6Address m_advertisingRtr;
+
+/**
+ * A convenience typedef to avoid too much writers cramp.
+ */
+ typedef std::list<GlobalRouting6LinkRecord*> 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 GlobalRouting::DiscoverLSAs ()
+ */
+ ListOfLinkRecords_t m_linkRecords;
+
+/**
+ * Each Network LSA contains the network mask of the attached network
+ */
+ Ipv6Prefix m_networkLSANetworkMask;
+
+/**
+ * A convenience typedef to avoid too much writers cramp.
+ */
+ typedef std::list<Ipv6Address> ListOfAttachedRouters_t;
+
+/**
+ * Each Network LSA contains a list of attached routers
+ *
+ * m_attachedRouters is an STL list container to hold the addresses that have
+ * been discovered and prepared for the advertisement.
+ *
+ * @see GlobalRouting::DiscoverLSAs ()
+ */
+ ListOfAttachedRouters_t m_attachedRouters;
+
+/**
+ * This is a tristate flag used internally in the SPF computation to mark
+ * if an SPF6Vertex (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;
+ uint32_t m_node_id;
+};
+
+std::ostream& operator<< (std::ostream& os, GlobalRouting6LSA& 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 Global6Router : public Object
+{
+public:
+/**
+ * @brief The Interface ID of the Global Router interface.
+ *
+ * @see Object::GetObject ()
+ */
+ static TypeId GetTypeId (void);
+
+/**
+ * @brief Create a Global Router class
+ */
+ Global6Router ();
+
+
+ void SetRoutingProtocol (Ptr<Ipv6GlobalRouting> routing);
+ Ptr<Ipv6GlobalRouting> GetRoutingProtocol (void);
+
+/**
+ * @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.
+ */
+ Ipv6Address GetRouterId (void) const;
+
+/**
+ * @brief Walk the connected channels, discover the adjacent routers and build
+ * the associated number of Global Routing 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 dynamics 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 GlobalRouting6LSA
+ * @see Global6Router::GetLSA ()
+ * @returns The number of Global Routing Link State Advertisements.
+ */
+ uint32_t DiscoverLSAs (void);
+
+/**
+ * @brief Get the Number of Global Routing 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 Global6RouterLSA
+ * @see GlobalRouting::DiscoverLSAs ()
+ * @see GlobalRouting::GetLSA ()
+ * @returns The number of Global Routing Link State Advertisements.
+ */
+ uint32_t GetNumLSAs (void) const;
+
+/**
+ * @brief Get a Global Routing 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 Routing Link
+ * State Advertisement into the requested GlobalRouting6LSA object.
+ *
+ * You must call Global6Router::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 GlobalRouting6LSA
+ * @see GlobalRouting::GetNumLSAs ()
+ * @param n The index number of the LSA you want to read.
+ * @param lsa The GlobalRouting6LSA class to receive the LSA information.
+ * @returns The number of Global Router Link State Advertisements.
+ */
+ bool GetLSA (uint32_t n, GlobalRouting6LSA &lsa) const;
+
+/**
+ * @brief Inject a route to be circulated to other routers as an external
+ * route
+ *
+ * @param network The Network to inject
+ * @param networkMask The Network Mask to inject
+ */
+ void InjectRoute (Ipv6Address network, Ipv6Prefix networkPrefix);
+
+/**
+ * @brief Get the number of injected routes that have been added
+ * to the routing table.
+ * @return number of injected routes
+ */
+ uint32_t GetNInjectedRoutes (void);
+
+/**
+ * @brief Return the injected route indexed by i
+ * @param i the index of the route
+ * @return a pointer to that Ipv4RoutingTableEntry is returned
+ *
+ */
+ Ipv6RoutingTableEntry *GetInjectedRoute (uint32_t i);
+
+/**
+ * @brief Withdraw a route from the global unicast routing table.
+ *
+ * Calling this function will cause all indexed routes numbered above
+ * index i to have their index decremented. For instance, it is possible to
+ * remove N injected routes by calling RemoveInjectedRoute (0) N times.
+ *
+ * @param i The index (into the injected routing list) of the route to remove.
+ *
+ * @see Global6Router::WithdrawRoute ()
+ */
+ void RemoveInjectedRoute (uint32_t i);
+
+/**
+ * @brief Withdraw a route from the global unicast routing table.
+ *
+ * @param network The Network to withdraw
+ * @param networkMask The Network Mask to withdraw
+ * @return whether the operation succeeded (will return false if no such route)
+ *
+ * @see Global6Router::RemoveInjectedRoute ()
+ */
+ bool WithdrawRoute (Ipv6Address network, Ipv6Prefix networkPrefix);
+
+private:
+ virtual ~Global6Router ();
+ void ClearLSAs (void);
+
+ Ptr<NetDevice> GetAdjacent(Ptr<NetDevice> nd, Ptr<Channel> ch) const;
+ bool FindInterfaceForDevice(Ptr<Node> node, Ptr<NetDevice> nd, uint32_t &index) const;
+ Ipv6Address FindDesignatedRouterForLink (Ptr<NetDevice> ndLocal, bool allowRecursion) const;
+ bool AnotherRouterOnLink (Ptr<NetDevice> nd, bool allowRecursion) const;
+ void ProcessBroadcastLink (Ptr<NetDevice> nd, GlobalRouting6LSA *pLSA, NetDeviceContainer &c);
+ void ProcessSingleBroadcastLink (Ptr<NetDevice> nd, GlobalRouting6LSA *pLSA, NetDeviceContainer &c);
+ void ProcessBridgedBroadcastLink (Ptr<NetDevice> nd, GlobalRouting6LSA *pLSA, NetDeviceContainer &c);
+
+ void ProcessPointToPointLink (Ptr<NetDevice> ndLocal, GlobalRouting6LSA *pLSA);
+ void BuildNetworkLSAs (NetDeviceContainer c);
+ Ptr<BridgeNetDevice> NetDeviceIsBridged (Ptr<NetDevice> nd) const;
+
+
+ typedef std::list<GlobalRouting6LSA*> ListOfLSAs_t;
+ ListOfLSAs_t m_LSAs;
+
+ Ipv6Address m_routerId;
+ Ptr<Ipv6GlobalRouting> m_routingProtocol;
+
+ typedef std::list<Ipv6RoutingTableEntry *> InjectedRoutes;
+ typedef std::list<Ipv6RoutingTableEntry *>::const_iterator InjectedRoutesCI;
+ typedef std::list<Ipv6RoutingTableEntry *>::iterator InjectedRoutesI;
+ InjectedRoutes m_injectedRoutes; // Routes we are exporting
+
+ // inherited from Object
+ virtual void DoDispose (void);
+
+/**
+ * @brief Global Router copy construction is disallowed.
+ */
+ Global6Router (Global6Router& sr);
+
+/**
+ * @brief Global Router assignment operator is disallowed.
+ */
+ Global6Router& operator= (Global6Router& sr);
+};
+
+} // namespace ns3
+
+#endif /* GLOBAL_ROUTER_6_INTERFACE_H */
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/internet/model/ipv6-global-routing.cc Tue Aug 30 02:11:57 2011 +0530
@@ -0,0 +1,651 @@
+// -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil; -*-
+//
+// Copyright (c) 2008 University of Washington
+//
+// This program is free software; you can redistribute it and/or modify
+// it under the terms of the GNU General Public License version 2 as
+// published by the Free Software Foundation;
+//
+// This program is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public License
+// along with this program; if not, write to the Free Software
+// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+//
+
+#include <vector>
+#include <iomanip>
+#include "ns3/names.h"
+#include "ns3/log.h"
+#include "ns3/simulator.h"
+#include "ns3/object.h"
+#include "ns3/packet.h"
+#include "ns3/net-device.h"
+#include "ns3/ipv6-route.h"
+#include "ns3/ipv6-routing-table-entry.h"
+#include "ns3/boolean.h"
+#include "ipv6-global-routing.h"
+#include "ipv6-global-route-manager.h"
+
+NS_LOG_COMPONENT_DEFINE ("Ipv6GlobalRouting");
+
+namespace ns3 {
+
+NS_OBJECT_ENSURE_REGISTERED (Ipv6GlobalRouting);
+
+TypeId
+Ipv6GlobalRouting::GetTypeId (void)
+{
+ static TypeId tid = TypeId ("ns3::Ipv6GlobalRouting")
+ .SetParent<Object> ()
+ .AddAttribute ("RandomEcmpRouting",
+ "Set to true if packets are randomly routed among ECMP; set to false for using only one route consistently",
+ BooleanValue(false),
+ MakeBooleanAccessor (&Ipv6GlobalRouting::m_randomEcmpRouting),
+ MakeBooleanChecker ())
+ .AddAttribute ("RespondToInterfaceEvents",
+ "Set to true if you want to dynamically recompute the global routes upon Interface notification events (up/down, or add/remove address)",
+ BooleanValue(false),
+ MakeBooleanAccessor (&Ipv6GlobalRouting::m_respondToInterfaceEvents),
+ MakeBooleanChecker ())
+ ;
+ return tid;
+}
+
+Ipv6GlobalRouting::Ipv6GlobalRouting ()
+: m_randomEcmpRouting (false),
+ m_respondToInterfaceEvents (false)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+}
+
+Ipv6GlobalRouting::~Ipv6GlobalRouting ()
+{
+ NS_LOG_FUNCTION_NOARGS ();
+}
+
+void
+Ipv6GlobalRouting::AddHostRouteTo (Ipv6Address dest,
+ Ipv6Address nextHop,
+ uint32_t interface)
+{
+ NS_LOG_FUNCTION (dest << nextHop << interface);
+ Ipv6RoutingTableEntry *route = new Ipv6RoutingTableEntry ();
+ *route = Ipv6RoutingTableEntry::CreateHostRouteTo (dest, nextHop, interface);
+ m_hostRoutes.push_back (route);
+}
+
+void
+Ipv6GlobalRouting::AddHostRouteTo (Ipv6Address dest,
+ uint32_t interface)
+{
+ NS_LOG_FUNCTION (dest << interface);
+ Ipv6RoutingTableEntry *route = new Ipv6RoutingTableEntry ();
+ *route = Ipv6RoutingTableEntry::CreateHostRouteTo (dest, interface);
+ m_hostRoutes.push_back (route);
+}
+
+void
+Ipv6GlobalRouting::AddNetworkRouteTo (Ipv6Address network,
+ Ipv6Prefix networkPrefix,
+ Ipv6Address nextHop,
+ uint32_t interface)
+{
+ NS_LOG_FUNCTION (network << networkPrefix << nextHop << interface);
+ Ipv6RoutingTableEntry *route = new Ipv6RoutingTableEntry ();
+ *route = Ipv6RoutingTableEntry::CreateNetworkRouteTo (network,
+ networkPrefix,
+ nextHop,
+ interface);
+ m_networkRoutes.push_back (route);
+}
+
+void
+Ipv6GlobalRouting::AddNetworkRouteTo (Ipv6Address network,
+ Ipv6Prefix networkPrefix,
+ uint32_t interface)
+{
+ NS_LOG_FUNCTION (network << networkPrefix << interface);
+ Ipv6RoutingTableEntry *route = new Ipv6RoutingTableEntry ();
+ *route = Ipv6RoutingTableEntry::CreateNetworkRouteTo (network,
+ networkPrefix,
+ interface);
+ m_networkRoutes.push_back (route);
+}
+
+void
+Ipv6GlobalRouting::AddASExternalRouteTo (Ipv6Address network,
+ Ipv6Prefix networkPrefix,
+ Ipv6Address nextHop,
+ uint32_t interface)
+{
+ NS_LOG_FUNCTION (network << networkPrefix << nextHop);
+ Ipv6RoutingTableEntry *route = new Ipv6RoutingTableEntry ();
+ *route = Ipv6RoutingTableEntry::CreateNetworkRouteTo (network,
+ networkPrefix,
+ nextHop,
+ interface);
+ m_ASexternalRoutes.push_back (route);
+}
+
+
+Ptr<Ipv6Route>
+Ipv6GlobalRouting::LookupGlobal (Ipv6Address dest, Ptr<NetDevice> interface)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ NS_LOG_LOGIC ("Looking for route for destination " << dest);
+ Ptr<Ipv6Route> rtentry = 0;
+ // store all available routes that bring packets to their destination
+ typedef std::vector<Ipv6RoutingTableEntry*> RouteVec_t;
+ RouteVec_t allRoutes;
+
+ NS_LOG_LOGIC ("Number of m_hostRoutes = " << m_hostRoutes.size ());
+ for (HostRoutesCI i = m_hostRoutes.begin ();
+ i != m_hostRoutes.end ();
+ i++)
+ {
+ NS_ASSERT ((*i)->IsHost ());
+ if ((*i)->GetDest ().IsEqual (dest))
+ {
+ if (interface != 0)
+ {
+ if (interface != m_ipv6->GetNetDevice((*i)->GetInterface ()))
+ {
+ NS_LOG_LOGIC ("Not on requested interface, skipping");
+ continue;
+ }
+ }
+ allRoutes.push_back (*i);
+ NS_LOG_LOGIC (allRoutes.size () << "Found global host route" << *i);
+ }
+ }
+ if (allRoutes.size () == 0) // if no host route is found
+ {
+ NS_LOG_LOGIC ("Number of m_networkRoutes" << m_networkRoutes.size ());
+ for (NetworkRoutesI j = m_networkRoutes.begin ();
+ j != m_networkRoutes.end ();
+ j++)
+ {
+ Ipv6Prefix mask = (*j)->GetDestNetworkPrefix ();
+ Ipv6Address entry = (*j)->GetDestNetwork ();
+ if (mask.IsMatch (dest, entry))
+ {
+ if (interface != 0)
+ {
+ if (interface != m_ipv6->GetNetDevice((*j)->GetInterface ()))
+ {
+ NS_LOG_LOGIC ("Not on requested interface, skipping");
+ continue;
+ }
+ }
+ allRoutes.push_back (*j);
+ NS_LOG_LOGIC (allRoutes.size () << "Found global network route" << *j);
+ }
+ }
+ }
+ if (allRoutes.size () == 0) // consider external if no host/network found
+ {
+ for (ASExternalRoutesI k = m_ASexternalRoutes.begin ();
+ k != m_ASexternalRoutes.end ();
+ k++)
+ {
+ Ipv6Prefix mask = (*k)->GetDestNetworkPrefix ();
+ Ipv6Address entry = (*k)->GetDestNetwork ();
+ if (mask.IsMatch (dest, entry))
+ {
+ NS_LOG_LOGIC ("Found external route" << *k);
+ if (interface != 0)
+ {
+ if (interface != m_ipv6->GetNetDevice((*k)->GetInterface ()))
+ {
+ NS_LOG_LOGIC ("Not on requested interface, skipping");
+ continue;
+ }
+ }
+ allRoutes.push_back (*k);
+ break;
+ }
+ }
+ }
+ if (allRoutes.size () > 0 ) // if route(s) is found
+ {
+ // pick up one of the routes uniformly at random if random
+ // ECMP routing is enabled, or always select the first route
+ // consistently if random ECMP routing is disabled
+ uint32_t selectIndex;
+ if (m_randomEcmpRouting)
+ {
+ selectIndex = m_rand.GetInteger (0, allRoutes.size ()-1);
+ }
+ else
+ {
+ selectIndex = 0;
+ }
+ Ipv6RoutingTableEntry* route = allRoutes.at (selectIndex);
+ // create a Ipv6Route object from the selected routing table entry
+ rtentry = Create<Ipv6Route> ();
+ rtentry->SetDestination (route->GetDest ());
+ // XXX handle multi-address case
+ rtentry->SetSource (SourceAddressSelection (m_ipv6->GetInterfaceForDevice (interface), dest)); //????
+ rtentry->SetGateway (route->GetGateway ());
+ uint32_t interfaceIdx = route->GetInterface ();
+ rtentry->SetOutputDevice (m_ipv6->GetNetDevice (interfaceIdx));
+ return rtentry;
+ }
+ else
+ {
+ return 0;
+ }
+}
+
+uint32_t
+Ipv6GlobalRouting::GetNRoutes (void) const
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ uint32_t n = 0;
+ n += m_hostRoutes.size ();
+ n += m_networkRoutes.size ();
+ n += m_ASexternalRoutes.size ();
+ return n;
+}
+
+Ipv6RoutingTableEntry *
+Ipv6GlobalRouting::GetRoute (uint32_t index) const
+{
+ NS_LOG_FUNCTION (index);
+ if (index < m_hostRoutes.size ())
+ {
+ uint32_t tmp = 0;
+ for (HostRoutesCI i = m_hostRoutes.begin ();
+ i != m_hostRoutes.end ();
+ i++)
+ {
+ if (tmp == index)
+ {
+ return *i;
+ }
+ tmp++;
+ }
+ }
+ index -= m_hostRoutes.size ();
+ uint32_t tmp = 0;
+ if (index < m_networkRoutes.size())
+ {
+ for (NetworkRoutesCI j = m_networkRoutes.begin ();
+ j != m_networkRoutes.end ();
+ j++)
+ {
+ if (tmp == index)
+ {
+ return *j;
+ }
+ tmp++;
+ }
+ }
+ index -= m_networkRoutes.size();
+ tmp = 0;
+ for (ASExternalRoutesCI k = m_ASexternalRoutes.begin ();
+ k != m_ASexternalRoutes.end ();
+ k++)
+ {
+ if (tmp == index)
+ {
+ return *k;
+ }
+ tmp++;
+ }
+ NS_ASSERT (false);
+ // quiet compiler.
+ return 0;
+}
+void
+Ipv6GlobalRouting::RemoveRoute (uint32_t index)
+{
+ NS_LOG_FUNCTION (index);
+ if (index < m_hostRoutes.size ())
+ {
+ uint32_t tmp = 0;
+ for (HostRoutesI i = m_hostRoutes.begin ();
+ i != m_hostRoutes.end ();
+ i++)
+ {
+ if (tmp == index)
+ {
+ NS_LOG_LOGIC ("Removing route " << index << "; size = " << m_hostRoutes.size());
+ delete *i;
+ m_hostRoutes.erase (i);
+ NS_LOG_LOGIC ("Done removing host route " << index << "; host route remaining size = " << m_hostRoutes.size());
+ return;
+ }
+ tmp++;
+ }
+ }
+ index -= m_hostRoutes.size ();
+ uint32_t tmp = 0;
+ for (NetworkRoutesI j = m_networkRoutes.begin ();
+ j != m_networkRoutes.end ();
+ j++)
+ {
+ if (tmp == index)
+ {
+ NS_LOG_LOGIC ("Removing route " << index << "; size = " << m_networkRoutes.size());
+ delete *j;
+ m_networkRoutes.erase (j);
+ NS_LOG_LOGIC ("Done removing network route " << index << "; network route remaining size = " << m_networkRoutes.size());
+ return;
+ }
+ tmp++;
+ }
+ index -= m_networkRoutes.size ();
+ tmp = 0;
+ for (ASExternalRoutesI k = m_ASexternalRoutes.begin ();
+ k != m_ASexternalRoutes.end ();
+ k++)
+ {
+ if (tmp == index)
+ {
+ NS_LOG_LOGIC ("Removing route " << index << "; size = " << m_ASexternalRoutes.size());
+ delete *k;
+ m_ASexternalRoutes.erase (k);
+ NS_LOG_LOGIC ("Done removing network route " << index << "; network route remaining size = " << m_networkRoutes.size());
+ return;
+ }
+ tmp++;
+ }
+ NS_ASSERT (false);
+}
+
+void
+Ipv6GlobalRouting::DoDispose (void)
+{
+ NS_LOG_FUNCTION_NOARGS ();
+ for (HostRoutesI i = m_hostRoutes.begin ();
+ i != m_hostRoutes.end ();
+ i = m_hostRoutes.erase (i))
+ {
+ delete (*i);
+ }
+ for (NetworkRoutesI j = m_networkRoutes.begin ();
+ j != m_networkRoutes.end ();
+ j = m_networkRoutes.erase (j))
+ {
+ delete (*j);
+ }
+ for (ASExternalRoutesI l = m_ASexternalRoutes.begin ();
+ l != m_ASexternalRoutes.end ();
+ l = m_ASexternalRoutes.erase (l))
+ {
+ delete (*l);
+ }
+
+ Ipv6RoutingProtocol::DoDispose ();
+}
+
+// Formatted like output of "route -n" command
+ void
+Ipv6GlobalRouting::PrintRoutingTable(Ptr<OutputStreamWrapper> stream) const
+{
+ std::ostream* os = stream->GetStream();
+ *os<<GetNRoutes();
+ if (GetNRoutes () > 0)
+ {
+ *os << "Destination Gateway Genmask Flags Metric Ref Use Iface" << std::endl;
+ for (uint32_t j = 0; j < GetNRoutes (); j++)
+ {
+ std::ostringstream dest, gw, mask, flags;
+ Ipv6RoutingTableEntry route = GetRoute (j);
+ dest << route.GetDest ();
+ *os << std::setiosflags (std::ios::left) << std::setw (16) << dest.str();
+ gw << route.GetGateway ();
+ *os << std::setiosflags (std::ios::left) << std::setw (16) << gw.str();
+ mask << route.GetDestNetworkPrefix ();
+ *os << std::setiosflags (std::ios::left) << std::setw (16) << mask.str();
+ flags << "U";
+ if (route.IsHost ())
+ {
+ flags << "H";
+ }
+ else if (route.IsGateway ())
+ {
+ flags << "G";
+ }
+ *os << std::setiosflags (std::ios::left) << std::setw (6) << flags.str();
+ // Metric not implemented
+ *os << "-" << " ";
+ // Ref ct not implemented
+ *os << "-" << " ";
+ // Use not implemented
+ *os << "-" << " ";
+ if (Names::FindName (m_ipv6->GetNetDevice (route.GetInterface ())) != "")
+ {
+ *os << Names::FindName (m_ipv6->GetNetDevice (route.GetInterface ()));
+ }
+ else
+ {
+ *os << route.GetInterface();
+ }
+ *os << std::endl;
+ }
+ }
+}
+///*/
+
+Ptr<Ipv6Route>
+Ipv6GlobalRouting::RouteOutput (Ptr<Packet> p, const Ipv6Header &header, Ptr<NetDevice> oif, Socket::SocketErrno &sockerr)
+{
+
+//
+// First, see if this is a multicast packet we have a route for. If we
+// have a route, then send the packet down each of the specified interfaces.
+//
+ if (header.GetDestinationAddress().IsMulticast ())
+ {
+ NS_LOG_LOGIC ("Multicast destination-- returning false");
+ return 0; // Let other routing protocols try to handle this
+ }
+//
+// See if this is a unicast packet we have a route for.
+//
+ NS_LOG_LOGIC ("Unicast destination- looking up");
+ Ptr<Ipv6Route> rtentry = LookupGlobal (header.GetDestinationAddress (), oif);
+ if (rtentry)
+ {
+ sockerr = Socket::ERROR_NOTERROR;
+ }
+ else
+ {
+ sockerr = Socket::ERROR_NOROUTETOHOST;
+ }
+ return rtentry;
+}
+
+bool
+Ipv6GlobalRouting::RouteInput (Ptr<const Packet> p, const Ipv6Header &header, Ptr<const NetDevice> idev, UnicastForwardCallback ucb, MulticastForwardCallback mcb,
+ LocalDeliverCallback lcb, ErrorCallback ecb)
+{
+
+ NS_LOG_FUNCTION (this << p << header << header.GetSourceAddress () << header.GetDestinationAddress () << idev);
+ // Check if input device supports IP
+ NS_ASSERT (m_ipv6->GetInterfaceForDevice (idev) >= 0);
+ uint32_t iif = m_ipv6->GetInterfaceForDevice (idev);
+
+ if (header.GetDestinationAddress ().IsMulticast ())
+ {
+ NS_LOG_LOGIC ("Multicast destination-- returning false");
+ return false; // Let other routing protocols try to handle this
+ }
+/*
+ if (header.GetDestinationAddress ().IsBroadcast ())
+ {
+ NS_LOG_LOGIC ("For me (Ipv6Addr broadcast address)");
+ // TODO: Local Deliver for broadcast
+ // TODO: Forward broadcast
+ }
+
+ // TODO: Configurable option to enable RFC 1222 Strong End System Model
+ // Right now, we will be permissive and allow a source to send us
+ // a packet to one of our other interface addresses; that is, the
+ // destination unicast address does not match one of the iif addresses,
+ // but we check our other interfaces. This could be an option
+ // (to remove the outer loop immediately below and just check iif).
+ for (uint32_t j = 0; j < m_ipv6->GetNInterfaces (); j++)
+ {
+ for (uint32_t i = 0; i < m_ipv6->GetNAddresses (j); i++)
+ {
+ Ipv6InterfaceAddress iaddr = m_ipv6->GetAddress (j, i);
+ Ipv6Address addr = iaddr.GetLocal ();
+ if (addr.IsEqual (header.GetDestinationAddress ()))
+ {
+ if (j == iif)
+ {
+ NS_LOG_LOGIC ("For me (destination " << addr << " match)");
+ }
+ else
+ {
+ NS_LOG_LOGIC ("For me (destination " << addr << " match) on another interface " << header.GetDestinationAddress ());
+ }
+ lcb (p, header, iif);
+ return true;
+ }
+ if (header.GetDestinationAddress ().IsEqual (iaddr.GetBroadcast ()))
+ {
+ NS_LOG_LOGIC ("For me (interface broadcast address)");
+ lcb (p, header, iif);
+ return true;
+ }
+ NS_LOG_LOGIC ("Address "<< addr << " not a match");
+ }
+ }*/
+ // Check if input device supports IP forwarding
+ if (m_ipv6->IsForwarding (iif) == false)
+ {
+ NS_LOG_LOGIC ("Forwarding disabled for this interface");
+ ecb (p, header, Socket::ERROR_NOROUTETOHOST);
+ return false;
+ }
+ // Next, try to find a route
+ NS_LOG_LOGIC ("Unicast destination- looking up global route");
+ Ptr<Ipv6Route> rtentry = LookupGlobal (header.GetDestinationAddress ());
+ if (rtentry != 0)
+ {
+ NS_LOG_LOGIC ("Found unicast destination- calling unicast callback");
+ ucb (rtentry, p, header);
+ return true;
+ }
+ else
+ {
+ NS_LOG_LOGIC ("Did not find unicast destination- returning false");
+ return false; // Let other routing protocols try to handle this
+ // route request.
+ }
+}
+void
+Ipv6GlobalRouting::NotifyInterfaceUp (uint32_t i)
+{
+ NS_LOG_FUNCTION (this << i);
+ if (m_respondToInterfaceEvents && Simulator::Now ().GetSeconds () > 0) // avoid startup events
+ {
+ GlobalRoute6Manager::DeleteGlobalRoutes ();
+ GlobalRoute6Manager::BuildGlobalRoutingDatabase ();
+ GlobalRoute6Manager::InitializeRoutes ();
+ }
+}
+
+void
+Ipv6GlobalRouting::NotifyInterfaceDown (uint32_t i)
+{
+ NS_LOG_FUNCTION (this << i);
+ if (m_respondToInterfaceEvents && Simulator::Now ().GetSeconds () > 0) // avoid startup events
+ {
+ GlobalRoute6Manager::DeleteGlobalRoutes ();
+ GlobalRoute6Manager::BuildGlobalRoutingDatabase ();
+ GlobalRoute6Manager::InitializeRoutes ();
+ }
+}
+
+void
+Ipv6GlobalRouting::NotifyAddAddress (uint32_t interface, Ipv6InterfaceAddress address)
+{
+ NS_LOG_FUNCTION (this << interface << address);
+ if (m_respondToInterfaceEvents && Simulator::Now ().GetSeconds () > 0) // avoid startup events
+ {
+ GlobalRoute6Manager::DeleteGlobalRoutes ();
+ GlobalRoute6Manager::BuildGlobalRoutingDatabase ();
+ GlobalRoute6Manager::InitializeRoutes ();
+ }
+}
+
+void
+Ipv6GlobalRouting::NotifyRemoveAddress (uint32_t interface, Ipv6InterfaceAddress address)
+{
+ NS_LOG_FUNCTION (this << interface << address);
+ if (m_respondToInterfaceEvents && Simulator::Now ().GetSeconds () > 0) // avoid startup events
+ {
+ GlobalRoute6Manager::DeleteGlobalRoutes ();
+ GlobalRoute6Manager::BuildGlobalRoutingDatabase ();
+ GlobalRoute6Manager::InitializeRoutes ();
+ }
+}
+
+void Ipv6GlobalRouting::NotifyAddRoute (Ipv6Address dst, Ipv6Prefix mask, Ipv6Address nextHop, uint32_t interface, Ipv6Address prefixToUse)
+{
+ NS_LOG_FUNCTION (this << dst << mask << nextHop << interface);
+ for (Ipv6RoutingProtocolList::const_iterator rprotoIter =
+ m_routingProtocols.begin ();
+ rprotoIter != m_routingProtocols.end ();
+ rprotoIter++)
+ {
+ (*rprotoIter).second->NotifyAddRoute (dst, mask, nextHop, interface, prefixToUse);
+ }
+}
+
+void Ipv6GlobalRouting::NotifyRemoveRoute (Ipv6Address dst, Ipv6Prefix mask, Ipv6Address nextHop, uint32_t interface, Ipv6Address prefixToUse)
+{
+ NS_LOG_FUNCTION (this << dst << mask << nextHop << interface);
+ for (Ipv6RoutingProtocolList::const_iterator rprotoIter =
+ m_routingProtocols.begin ();
+ rprotoIter != m_routingProtocols.end ();
+ rprotoIter++)
+ {
+ (*rprotoIter).second->NotifyRemoveRoute (dst, mask, nextHop, interface, prefixToUse);
+ }
+}
+void
+Ipv6GlobalRouting::SetIpv6 (Ptr<Ipv6> ipv6)
+{
+ NS_LOG_FUNCTION(this << ipv6);
+ NS_ASSERT (m_ipv6 == 0 && ipv6 != 0);
+ m_ipv6 = ipv6;
+}
+
+Ipv6Address Ipv6GlobalRouting::SourceAddressSelection (uint32_t interface, Ipv6Address dest)
+{
+ NS_LOG_FUNCTION (this << interface << dest);
+ Ipv6Address ret;
+
+ /* first address of an IPv6 interface is link-local ones */
+ ret = m_ipv6->GetAddress (interface, 0).GetAddress ();
+
+ if (dest == Ipv6Address::GetAllNodesMulticast () || dest == Ipv6Address::GetAllRoutersMulticast () || dest == Ipv6Address::GetAllHostsMulticast ())
+ {
+ return ret;
+ }
+
+ /* useally IPv6 interfaces have one link-local address and one global address */
+
+ for (uint32_t i = 1 ; i < m_ipv6->GetNAddresses (interface) ; i++)
+ {
+ Ipv6InterfaceAddress test = m_ipv6->GetAddress (interface, i);
+
+ if (test.GetAddress ().CombinePrefix (test.GetPrefix ()) == dest.CombinePrefix (test.GetPrefix ()))
+ {
+ return test.GetAddress ();
+ }
+ }
+
+ return ret;
+}
+}//namespace ns3
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/internet/model/ipv6-global-routing.h Tue Aug 30 02:11:57 2011 +0530
@@ -0,0 +1,260 @@
+// -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil; -*-
+//
+// Copyright (c) 2008 University of Washington
+//
+// This program is free software; you can redistribute it and/or modify
+// it under the terms of the GNU General Public License version 2 as
+// published by the Free Software Foundation;
+//
+// This program is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public License
+// along with this program; if not, write to the Free Software
+// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+//
+//
+
+#ifndef IPV6_GLOBAL_ROUTING_H
+#define IPV6_GLOBAL_ROUTING_H
+
+#include <list>
+#include <stdint.h>
+#include "ns3/ipv6-address.h"
+#include "ns3/ipv6-header.h"
+#include "ns3/ptr.h"
+#include "ns3/ipv6.h"
+#include "ns3/ipv6-routing-protocol.h"
+#include "ns3/random-variable.h"
+#include "ns3/output-stream-wrapper.h"
+
+namespace ns3 {
+
+class Packet;
+class NetDevice;
+class Ipv6Interface;
+class Ipv6Address;
+class Ipv6Header;
+class Ipv6RoutingTableEntry;
+class Ipv6MulticastRoutingTableEntry;
+class Node;
+
+
+/**
+ * \brief Global routing protocol for IP version 6 stacks.
+ *
+ * In ns-3 we have the concept of a pluggable routing protocol. Routing
+ * protocols are added to a list maintained by the Ipv6L3Protocol. Every
+ * stack gets one routing protocol for free -- the Ipv6StaticRouting routing
+ * protocol is added in the constructor of the Ipv6L3Protocol (this is the
+ * piece of code that implements the functionality of the IP layer).
+ *
+ * As an option to running a dynamic routing protocol, a GlobalRouteManager
+ * object has been created to allow users to build routes for all participating
+ * nodes. One can think of this object as a "routing oracle"; it has
+ * an omniscient view of the topology, and can construct shortest path
+ * routes between all pairs of nodes. These routes must be stored
+ * somewhere in the node, so therefore this class Ipv6GlobalRouting
+ * is used as one of the pluggable routing protocols. It is kept distinct
+ * from Ipv6StaticRouting because these routes may be dynamically cleared
+ * and rebuilt in the middle of the simulation, while manually entered
+ * routes into the Ipv6StaticRouting may need to be kept distinct.
+ *
+ * This class deals with Ipv6 unicast routes only.
+ *
+ * \see Ipv6RoutingProtocol
+ * \see GlobalRouteManager
+ */
+class Ipv6GlobalRouting : public Ipv6RoutingProtocol
+{
+public:
+ static TypeId GetTypeId (void);
+/**
+ * \brief Construct an empty Ipv6GlobalRouting routing protocol,
+ *
+ * The Ipv6GlobalRouting class supports host and network unicast routes.
+ * This method initializes the lists containing these routes to empty.
+ *
+ * \see Ipv6GlobalRouting
+ */
+ Ipv6GlobalRouting ();
+ virtual ~Ipv6GlobalRouting ();
+
+ // These methods inherited from base class
+ virtual Ptr<Ipv6Route> RouteOutput (Ptr<Packet> p, const Ipv6Header &header, Ptr<NetDevice> oif, Socket::SocketErrno &sockerr);
+
+ virtual bool RouteInput (Ptr<const Packet> p, const Ipv6Header &header, Ptr<const NetDevice> idev,
+ UnicastForwardCallback ucb, MulticastForwardCallback mcb,
+ LocalDeliverCallback lcb, ErrorCallback ecb);
+ virtual void NotifyInterfaceUp (uint32_t interface);
+ virtual void NotifyInterfaceDown (uint32_t interface);
+ virtual void NotifyAddAddress (uint32_t interface, Ipv6InterfaceAddress address);
+ virtual void NotifyRemoveAddress (uint32_t interface, Ipv6InterfaceAddress address);
+virtual void NotifyAddRoute (Ipv6Address dst, Ipv6Prefix mask, Ipv6Address nextHop, uint32_t interface, Ipv6Address prefixToUse = Ipv6Address::GetZero ());
+ virtual void NotifyRemoveRoute (Ipv6Address dst, Ipv6Prefix mask, Ipv6Address nextHop, uint32_t interface, Ipv6Address prefixToUse = Ipv6Address::GetZero ());
+ virtual void SetIpv6 (Ptr<Ipv6> ipv6);
+ virtual void PrintRoutingTable (Ptr<OutputStreamWrapper> stream) const;
+
+/**
+ * \brief Add a host route to the global routing table.
+ *
+ * \param dest The Ipv6Address destination for this route.
+ * \param nextHop The Ipv6Address of the next hop in the route.
+ * \param interface The network interface index used to send packets to the
+ * destination.
+ *
+ * \see Ipv6Address
+ */
+ void AddHostRouteTo (Ipv6Address dest,
+ Ipv6Address nextHop,
+ uint32_t interface);
+/**
+ * \brief Add a host route to the global routing table.
+ *
+ * \param dest The Ipv6Address destination for this route.
+ * \param interface The network interface index used to send packets to the
+ * destination.
+ *
+ * \see Ipv6Address
+ */
+ void AddHostRouteTo (Ipv6Address dest,
+ uint32_t interface);
+
+/**
+ * \brief Add a network route to the global routing table.
+ *
+ * \param network The Ipv6Address network for this route.
+ * \param networkMask The Ipv6Mask to extract the network.
+ * \param nextHop The next hop in the route to the destination network.
+ * \param interface The network interface index used to send packets to the
+ * destination.
+ *
+ * \see Ipv6Address
+ */
+ void AddNetworkRouteTo (Ipv6Address network,
+ Ipv6Prefix networkPrefix,
+ Ipv6Address nextHop,
+ uint32_t interface);
+
+/**
+ * \brief Add a network route to the global routing table.
+ *
+ * \param network The Ipv6Address network for this route.
+ * \param networkMask The Ipv4Mask to extract the network.
+ * \param interface The network interface index used to send packets to the
+ * destination.
+ *
+ * \see Ipv6Address
+ */
+ void AddNetworkRouteTo (Ipv6Address network,
+ Ipv6Prefix networkPrefix,
+ uint32_t interface);
+
+/**
+ * \brief Add an external route to the global routing table.
+ *
+ * \param network The Ipv6Address network for this route.
+ * \param networkMask The Ipv6Mask to extract the network.
+ * \param nextHop The next hop Ipv6Address
+ * \param interface The network interface index used to send packets to the
+ * destination.
+ */
+ void AddASExternalRouteTo (Ipv6Address network,
+ Ipv6Prefix networkPrefix,
+ Ipv6Address nextHop,
+ uint32_t interface);
+
+/**
+ * \brief Get the number of individual unicast routes that have been added
+ * to the routing table.
+ *
+ * \warning The default route counts as one of the routes.
+ */
+ uint32_t GetNRoutes (void) const;
+
+/**
+ * \brief Get a route from the global unicast routing table.
+ *
+ * Externally, the unicast global routing table appears simply as a table with
+ * n entries. The one subtlety of note is that if a default route has been set
+ * it will appear as the zeroth entry in the table. This means that if you
+ * add only a default route, the table will have one entry that can be accessed
+ * either by explicitly calling GetDefaultRoute () or by calling GetRoute (0).
+ *
+ * Similarly, if the default route has been set, calling RemoveRoute (0) will
+ * remove the default route.
+ *
+ * \param i The index (into the routing table) of the route to retrieve. If
+ * the default route has been set, it will occupy index zero.
+ * \return If route is set, a pointer to that Ipv6RoutingTableEntry is returned, otherwise
+ * a zero pointer is returned.
+ *
+ * \see Ipv6RoutingTableEntry
+ * \see Ipv6GlobalRouting::RemoveRoute
+ */
+ Ipv6RoutingTableEntry *GetRoute (uint32_t i) const;
+
+/**
+ * \brief Remove a route from the global unicast routing table.
+ *
+ * Externally, the unicast global routing table appears simply as a table with
+ * n entries. The one subtlety of note is that if a default route has been set
+ * it will appear as the zeroth entry in the table. This means that if the
+ * default route has been set, calling RemoveRoute (0) will remove the
+ * default route.
+ *
+ * \param i The index (into the routing table) of the route to remove. If
+ * the default route has been set, it will occupy index zero.
+ *
+ * \see Ipv6RoutingTableEntry
+ * \see Ipv6GlobalRouting::GetRoute
+ * \see Ipv6GlobalRouting::AddRoute
+ */
+ void RemoveRoute (uint32_t i);
+
+protected:
+ void DoDispose (void);
+
+private:
+ /// Set to true if packets are randomly routed among ECMP; set to false for using only one route consistently
+ bool m_randomEcmpRouting;
+ /// Set to true if this interface should respond to interface events by globallly recomputing routes
+ bool m_respondToInterfaceEvents;
+ /// A uniform random number generator for randomly routing packets among ECMP
+ UniformVariable m_rand;
+
+ typedef std::list<Ipv6RoutingTableEntry *> HostRoutes;
+ typedef std::list<Ipv6RoutingTableEntry *>::const_iterator HostRoutesCI;
+ typedef std::list<Ipv6RoutingTableEntry *>::iterator HostRoutesI;
+ typedef std::list<Ipv6RoutingTableEntry *> NetworkRoutes;
+ typedef std::list<Ipv6RoutingTableEntry *>::const_iterator NetworkRoutesCI;
+ typedef std::list<Ipv6RoutingTableEntry *>::iterator NetworkRoutesI;
+ typedef std::list<Ipv6RoutingTableEntry *> ASExternalRoutes;
+ typedef std::list<Ipv6RoutingTableEntry *>::const_iterator ASExternalRoutesCI;
+ typedef std::list<Ipv6RoutingTableEntry *>::iterator ASExternalRoutesI;
+ typedef std::pair<int16_t, Ptr<Ipv6RoutingProtocol> > Ipv6RoutingProtocolEntry;
+ typedef std::list<Ipv6RoutingProtocolEntry> Ipv6RoutingProtocolList;
+
+ Ptr<Ipv6Route> LookupGlobal (Ipv6Address dest, Ptr<NetDevice> oif = 0);
+ /**
+ * \brief Choose the source address to use with destination address.
+ * \param interface interface index
+ * \param dest IPv6 destination address
+ * \return IPv6 source address to use
+ */
+ Ipv6Address SourceAddressSelection (uint32_t interface, Ipv6Address dest);
+
+ Ipv6RoutingProtocolList m_routingProtocols;
+
+ HostRoutes m_hostRoutes;
+ NetworkRoutes m_networkRoutes;
+ ASExternalRoutes m_ASexternalRoutes; // External routes imported
+
+ Ptr<Ipv6> m_ipv6;
+};
+
+} // Namespace ns3
+
+#endif /* IPV6_GLOBAL_ROUTING_H */
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/internet/test/ipv6-global-route-manager-impl-test-suite.cc Tue Aug 30 02:11:57 2011 +0530
@@ -0,0 +1,234 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright 2007 University of Washington
+ * Copyright (C) 1999, 2000 Kunihiro Ishiguro, Toshiaki Takada
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ *
+ * Authors: Tom Henderson (tomhend@u.washington.edu)
+ *
+ * Kunihiro Ishigura, Toshiaki Takada (GNU Zebra) are attributed authors
+ * of the quagga 0.99.7/src/ospfd/ospf_spf.c code which was ported here
+ */
+
+#include "ns3/test.h"
+#include "ns3/ipv6-global-route-manager-impl.h"
+#include "ns3/ipv6-candidate-queue.h"
+#include "ns3/simulator.h"
+#include <stdlib.h> // for rand()
+
+namespace ns3 {
+
+class GlobalRouteManager6ImplTestCase : public TestCase
+{
+public:
+ GlobalRouteManager6ImplTestCase();
+ virtual void DoRun(void);
+};
+
+GlobalRouteManager6ImplTestCase::GlobalRouteManager6ImplTestCase()
+ : TestCase("GlobalRouteManager6ImplTestCase")
+{}
+void
+GlobalRouteManager6ImplTestCase::DoRun(void)
+{
+ Candidate6Queue candidate;
+
+ for (int i = 0; i < 100; ++i)
+ {
+ SPF6Vertex *v = new SPF6Vertex;
+ v->SetDistanceFromRoot (rand () % 100);
+ candidate.Push (v);
+ }
+
+ uint32_t lastDistance = 0;
+
+ for (int i = 0; i < 100; ++i)
+ {
+ SPF6Vertex *v = candidate.Pop ();
+ if (v->GetDistanceFromRoot () < lastDistance)
+ {
+ // XXX does nothing.
+ UpdateErrorStatus (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
+ GlobalRouting6LinkRecord* lr0 = new GlobalRouting6LinkRecord (
+ GlobalRouting6LinkRecord::PointToPoint,
+ "0.0.0.2", // router ID 0.0.0.2
+ "10.1.1.1", // local ID
+ 1); // metric
+
+ GlobalRouting6LinkRecord* lr1 = new GlobalRouting6LinkRecord (
+ GlobalRouting6LinkRecord::StubNetwork,
+ "10.1.1.1",
+ "255.255.255.252",
+ 1);
+
+ GlobalRouting6LSA* lsa0 = new GlobalRouting6LSA ();
+ lsa0->SetLSType (GlobalRouting6LSA::RouterLSA);
+ lsa0->SetLinkStateId ("0.0.0.0");
+ lsa0->SetAdvertisingRouter ("0.0.0.0");
+ lsa0->AddLinkRecord (lr0);
+ lsa0->AddLinkRecord (lr1);
+
+ // Router 1
+ GlobalRouting6LinkRecord* lr2 = new GlobalRouting6LinkRecord (
+ GlobalRouting6LinkRecord::PointToPoint,
+ "0.0.0.2",
+ "10.1.2.1",
+ 1);
+
+ GlobalRouting6LinkRecord* lr3 = new GlobalRouting6LinkRecord (
+ GlobalRouting6LinkRecord::StubNetwork,
+ "10.1.2.1",
+ "255.255.255.252",
+ 1);
+
+ GlobalRouting6LSA* lsa1 = new GlobalRouting6LSA ();
+ lsa1->SetLSType (GlobalRouting6LSA::RouterLSA);
+ lsa1->SetLinkStateId ("0.0.0.1");
+ lsa1->SetAdvertisingRouter ("0.0.0.1");
+ lsa1->AddLinkRecord (lr2);
+ lsa1->AddLinkRecord (lr3);
+
+ // Router 2
+ GlobalRouting6LinkRecord* lr4 = new GlobalRouting6LinkRecord (
+ GlobalRouting6LinkRecord::PointToPoint,
+ "0.0.0.0",
+ "10.1.1.2",
+ 1);
+
+ GlobalRouting6LinkRecord* lr5 = new GlobalRouting6LinkRecord (
+ GlobalRouting6LinkRecord::StubNetwork,
+ "10.1.1.2",
+ "255.255.255.252",
+ 1);
+
+ GlobalRouting6LinkRecord* lr6 = new GlobalRouting6LinkRecord (
+ GlobalRouting6LinkRecord::PointToPoint,
+ "0.0.0.1",
+ "10.1.2.2",
+ 1);
+
+ GlobalRouting6LinkRecord* lr7 = new GlobalRouting6LinkRecord (
+ GlobalRouting6LinkRecord::StubNetwork,
+ "10.1.2.2",
+ "255.255.255.252",
+ 1);
+
+ GlobalRouting6LinkRecord* lr8 = new GlobalRouting6LinkRecord (
+ GlobalRouting6LinkRecord::PointToPoint,
+ "0.0.0.3",
+ "10.1.3.2",
+ 1);
+
+ GlobalRouting6LinkRecord* lr9 = new GlobalRouting6LinkRecord (
+ GlobalRouting6LinkRecord::StubNetwork,
+ "10.1.3.2",
+ "255.255.255.252",
+ 1);
+
+ GlobalRouting6LSA* lsa2 = new GlobalRouting6LSA ();
+ lsa2->SetLSType (GlobalRouting6LSA::RouterLSA);
+ 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
+ GlobalRouting6LinkRecord* lr10 = new GlobalRouting6LinkRecord (
+ GlobalRouting6LinkRecord::PointToPoint,
+ "0.0.0.2",
+ "10.1.2.1",
+ 1);
+
+ GlobalRouting6LinkRecord* lr11 = new GlobalRouting6LinkRecord (
+ GlobalRouting6LinkRecord::StubNetwork,
+ "10.1.2.1",
+ "255.255.255.252",
+ 1);
+
+ GlobalRouting6LSA* lsa3 = new GlobalRouting6LSA ();
+ lsa3->SetLSType (GlobalRouting6LSA::RouterLSA);
+ 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
+ GlobalRouteManager6Impl* srm = new GlobalRouteManager6Impl ();
+ 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
+
+ Simulator::Run ();
+
+// XXX here we should do some verification of the routes built
+
+ Simulator::Destroy ();
+
+ // This delete clears the srm, which deletes the LSDB, which clears
+ // all of the LSAs, which each destroys the attached LinkRecords.
+ delete srm;
+
+ // XXX
+ // No testing has actually been done other than making sure that this code
+ // does not crash
+}
+
+
+static class GlobalRouteManager6ImplTestSuite : public TestSuite
+{
+public:
+ GlobalRouteManager6ImplTestSuite()
+ : TestSuite("global-route-manager-impl", UNIT)
+ {
+ AddTestCase(new GlobalRouteManager6ImplTestCase());
+ }
+} g_globalRoutingManagerImplTestSuite;
+
+} // namespace ns3
--- a/src/internet/wscript Mon Aug 29 20:31:03 2011 +0530
+++ b/src/internet/wscript Tue Aug 30 02:11:57 2011 +0530
@@ -184,6 +184,12 @@
'helper/ipv6-interface-container.cc',
'helper/ipv6-routing-helper.cc',
'model/ipv6-address-generator.cc',
+ 'model/ipv6-global-routing.cc',
+ 'model/ipv6-global-route-manager-impl.cc',
+ 'model/ipv6-global-router-interface.cc',
+ 'model/ipv6-candidate-queue.cc',
+ 'model/ipv6-global-route-manager.cc',
+ 'helper/ipv6-global-routing-helper.cc',
]
internet_test = bld.create_ns3_module_test_library('internet')
@@ -275,6 +281,12 @@
'helper/ipv6-interface-container.h',
'helper/ipv6-routing-helper.h',
'model/ipv6-address-generator.h',
+ 'model/ipv6-global-routing.h',
+ 'model/ipv6-global-route-manager.h',
+ 'model/ipv6-global-router-interface.h',
+ 'model/ipv6-global-route-manager-impl.h',
+ 'model/ipv6-candidate-queue.h',
+ 'helper/ipv6-global-routing-helper.h',
]
if bld.env['NSC_ENABLED']: