1.1 --- a/src/routing/global-routing/global-route-manager-impl.cc Sun Nov 30 21:21:23 2008 -0800
1.2 +++ b/src/routing/global-routing/global-route-manager-impl.cc Sun Nov 30 23:37:12 2008 -0800
1.3 @@ -53,7 +53,8 @@
1.4 m_rootOif (SPF_INFINITY),
1.5 m_nextHop ("0.0.0.0"),
1.6 m_parent (0),
1.7 - m_children ()
1.8 + m_children (),
1.9 + m_vertexProcessed (false)
1.10 {
1.11 NS_LOG_FUNCTION_NOARGS ();
1.12 }
1.13 @@ -65,7 +66,8 @@
1.14 m_rootOif (SPF_INFINITY),
1.15 m_nextHop ("0.0.0.0"),
1.16 m_parent (0),
1.17 - m_children ()
1.18 + m_children (),
1.19 + m_vertexProcessed (false)
1.20 {
1.21 NS_LOG_FUNCTION_NOARGS ();
1.22 if (lsa->GetLSType () == GlobalRoutingLSA::RouterLSA)
1.23 @@ -227,6 +229,19 @@
1.24 return m_children.size ();
1.25 }
1.26
1.27 +void
1.28 +SPFVertex::SetVertexProcessed (bool value)
1.29 +{
1.30 + m_vertexProcessed = value;
1.31 +}
1.32 +
1.33 +bool
1.34 +SPFVertex::IsVertexProcessed (void) const
1.35 +{
1.36 + return m_vertexProcessed;
1.37 +}
1.38 +
1.39 +
1.40 // ---------------------------------------------------------------------------
1.41 //
1.42 // GlobalRouteManagerLSDB Implementation
1.43 @@ -1174,11 +1189,11 @@
1.44 //
1.45 // Iterate the algorithm by returning to Step 2 until there are no more
1.46 // candidate vertices.
1.47 -//
1.48 - }
1.49 -//
1.50 -// Second stage of SPF calculation procedure's
1.51 -// NOTYET: ospf_spf_process_stubs (area, area->spf, new_table);
1.52 +
1.53 + } // end for loop
1.54 +
1.55 +// Second stage of SPF calculation procedure
1.56 + SPFProcessStubs (m_spfroot);
1.57 //
1.58 // We're all done setting the routing information for the node at the root of
1.59 // the SPF tree. Delete all of the vertices and corresponding resources. Go
1.60 @@ -1188,6 +1203,155 @@
1.61 m_spfroot = 0;
1.62 }
1.63
1.64 +// Processing logic from RFC 2328, page 166 and quagga ospf_spf_process_stubs ()
1.65 +// stub link records will exist for point-to-point interfaces and for
1.66 +// broadcast interfaces for which no neighboring router can be found
1.67 +void
1.68 +GlobalRouteManagerImpl::SPFProcessStubs (SPFVertex* v)
1.69 +{
1.70 + NS_LOG_FUNCTION_NOARGS ();
1.71 + NS_LOG_LOGIC ("Processing stubs for " << v->GetVertexId ());
1.72 + if (v->GetVertexType () == SPFVertex::VertexRouter)
1.73 + {
1.74 + GlobalRoutingLSA *rlsa = v->GetLSA ();
1.75 + NS_LOG_LOGIC ("Processing router LSA with id " << rlsa->GetLinkStateId ());
1.76 + for (uint32_t i = 0; i < rlsa->GetNLinkRecords (); i++)
1.77 + {
1.78 + NS_LOG_LOGIC ("Examining link " << i << " of " <<
1.79 + v->GetVertexId () << "'s " <<
1.80 + v->GetLSA ()->GetNLinkRecords () << " link records");
1.81 + GlobalRoutingLinkRecord *l = v->GetLSA ()->GetLinkRecord (i);
1.82 + if (l->GetLinkType () == GlobalRoutingLinkRecord::StubNetwork)
1.83 + {
1.84 + NS_LOG_LOGIC ("Found a Stub record to " << l->GetLinkId ());
1.85 + SPFIntraAddStub (l, v);
1.86 + continue;
1.87 + }
1.88 + }
1.89 + }
1.90 + for (uint32_t i = 0; i < v->GetNChildren (); i++)
1.91 + {
1.92 + if (!v->GetChild (i)->IsVertexProcessed ())
1.93 + {
1.94 + SPFProcessStubs (v->GetChild (i));
1.95 + v->GetChild (i)->SetVertexProcessed (true);
1.96 + }
1.97 + }
1.98 +}
1.99 +
1.100 +// RFC2328 16.1. second stage.
1.101 +void
1.102 +GlobalRouteManagerImpl::SPFIntraAddStub (GlobalRoutingLinkRecord *l, SPFVertex* v)
1.103 +{
1.104 + NS_LOG_FUNCTION_NOARGS ();
1.105 +
1.106 + NS_ASSERT_MSG (m_spfroot,
1.107 + "GlobalRouteManagerImpl::SPFIntraAddStub (): Root pointer not set");
1.108 +
1.109 + // XXX simplifed logic for the moment. There are two cases to consider:
1.110 + // 1) the stub network is on this router; do nothing for now
1.111 + // (already handled above)
1.112 + // 2) the stub network is on a remote router, so I should use the
1.113 + // same next hop that I use to get to vertex v
1.114 + if (v->GetVertexId () == m_spfroot->GetVertexId ())
1.115 + {
1.116 + NS_LOG_LOGIC ("Stub is on local host: " << v->GetVertexId () << "; returning");
1.117 + return;
1.118 + }
1.119 + NS_LOG_LOGIC ("Stub is on remote host: " << v->GetVertexId () << "; installing");
1.120 +//
1.121 +// The root of the Shortest Path First tree is the router to which we are
1.122 +// going to write the actual routing table entries. The vertex corresponding
1.123 +// to this router has a vertex ID which is the router ID of that node. We're
1.124 +// going to use this ID to discover which node it is that we're actually going
1.125 +// to update.
1.126 +//
1.127 + Ipv4Address routerId = m_spfroot->GetVertexId ();
1.128 +
1.129 + NS_LOG_LOGIC ("Vertex ID = " << routerId);
1.130 +//
1.131 +// We need to walk the list of nodes looking for the one that has the router
1.132 +// ID corresponding to the root vertex. This is the one we're going to write
1.133 +// the routing information to.
1.134 +//
1.135 + NodeList::Iterator i = NodeList::Begin ();
1.136 + for (; i != NodeList::End (); i++)
1.137 + {
1.138 + Ptr<Node> node = *i;
1.139 +//
1.140 +// The router ID is accessible through the GlobalRouter interface, so we need
1.141 +// to QI for that interface. If there's no GlobalRouter interface, the node
1.142 +// in question cannot be the router we want, so we continue.
1.143 +//
1.144 + Ptr<GlobalRouter> rtr =
1.145 + node->GetObject<GlobalRouter> ();
1.146 +
1.147 + if (rtr == 0)
1.148 + {
1.149 + NS_LOG_LOGIC ("No GlobalRouter interface on node " <<
1.150 + node->GetId ());
1.151 + continue;
1.152 + }
1.153 +//
1.154 +// If the router ID of the current node is equal to the router ID of the
1.155 +// root of the SPF tree, then this node is the one for which we need to
1.156 +// write the routing tables.
1.157 +//
1.158 + NS_LOG_LOGIC ("Considering router " << rtr->GetRouterId ());
1.159 +
1.160 + if (rtr->GetRouterId () == routerId)
1.161 + {
1.162 + NS_LOG_LOGIC ("Setting routes for node " << node->GetId ());
1.163 +//
1.164 +// Routing information is updated using the Ipv4 interface. We need to QI
1.165 +// for that interface. If the node is acting as an IP version 4 router, it
1.166 +// should absolutely have an Ipv4 interface.
1.167 +//
1.168 + Ptr<Ipv4> ipv4 = node->GetObject<Ipv4> ();
1.169 + NS_ASSERT_MSG (ipv4,
1.170 + "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
1.171 + "QI for <Ipv4> interface failed");
1.172 +//
1.173 +// Get the Global Router Link State Advertisement from the vertex we're
1.174 +// adding the routes to. The LSA will have a number of attached Global Router
1.175 +// Link Records corresponding to links off of that vertex / node. We're going
1.176 +// to be interested in the records corresponding to point-to-point links.
1.177 +//
1.178 + GlobalRoutingLSA *lsa = v->GetLSA ();
1.179 + NS_ASSERT_MSG (lsa,
1.180 + "GlobalRouteManagerImpl::SPFIntraAddRouter (): "
1.181 + "Expected valid LSA in SPFVertex* v");
1.182 + //Address tempaddr = Address (l->GetLinkData);
1.183 + Ipv4Mask tempmask ("255.255.255.0");
1.184 + Ipv4Address tempip = l->GetLinkId ();
1.185 + tempip = tempip.CombineMask (tempmask);
1.186 +
1.187 + NS_LOG_LOGIC (" Node " << node->GetId () <<
1.188 + " add route to " << tempip <<
1.189 + " with mask " << tempmask <<
1.190 + " using next hop " << v->GetNextHop () <<
1.191 + " via interface " << v->GetOutgoingTypeId ());
1.192 +//
1.193 +// Here's why we did all of that work. We're going to add a host route to the
1.194 +// host address found in the m_linkData field of the point-to-point link
1.195 +// record. In the case of a point-to-point link, this is the local IP address
1.196 +// of the node connected to the link. Each of these point-to-point links
1.197 +// will correspond to a local interface that has an IP address to which
1.198 +// the node at the root of the SPF tree can send packets. The vertex <v>
1.199 +// (corresponding to the node that has these links and interfaces) has
1.200 +// an m_nextHop address precalculated for us that is the address to which the
1.201 +// root node should send packets to be forwarded to these IP addresses.
1.202 +// Similarly, the vertex <v> has an m_rootOif (outbound interface index) to
1.203 +// which the packets should be send for forwarding.
1.204 +//
1.205 + Ptr<Ipv4GlobalRouting> gr = GetGlobalRoutingProtocol (node->GetId ());
1.206 + NS_ASSERT (gr);
1.207 + gr->AddNetworkRouteTo (tempip, tempmask, v->GetNextHop (), v->GetOutgoingTypeId ());
1.208 + return;
1.209 + } // if
1.210 + } // for
1.211 +}
1.212 +
1.213 //
1.214 // Return the interface index corresponding to a given IP address
1.215 // This is a wrapper around GetIfIndexByIpv4Address(), but we first
2.1 --- a/src/routing/global-routing/global-route-manager-impl.h Sun Nov 30 21:21:23 2008 -0800
2.2 +++ b/src/routing/global-routing/global-route-manager-impl.h Sun Nov 30 23:37:12 2008 -0800
2.3 @@ -547,6 +547,23 @@
2.4 */
2.5 uint32_t AddChild (SPFVertex* child);
2.6
2.7 + /**
2.8 + * @brief Set the value of the VertexProcessed flag
2.9 + *
2.10 + * Flag to note whether vertex has been processed in stage two of
2.11 + * SPF computation
2.12 + * @param value boolean value to set the flag
2.13 + */
2.14 + void SetVertexProcessed (bool value);
2.15 +
2.16 + /**
2.17 + * @brief Check the value of the VertexProcessed flag
2.18 + *
2.19 + * Flag to note whether vertex has been processed in stage two of
2.20 + * SPF computation
2.21 + * @returns value of underlying flag
2.22 + */
2.23 + bool IsVertexProcessed (void) const;
2.24 private:
2.25 VertexType m_vertexType;
2.26 Ipv4Address m_vertexId;
2.27 @@ -557,6 +574,7 @@
2.28 SPFVertex* m_parent;
2.29 typedef std::list<SPFVertex*> ListOfSPFVertex_t;
2.30 ListOfSPFVertex_t m_children;
2.31 + bool m_vertexProcessed;
2.32
2.33 /**
2.34 * @brief The SPFVertex copy construction is disallowed. There's no need for
2.35 @@ -771,6 +789,7 @@
2.36 SPFVertex* m_spfroot;
2.37 GlobalRouteManagerLSDB* m_lsdb;
2.38 void SPFCalculate (Ipv4Address root);
2.39 + void SPFProcessStubs (SPFVertex* v);
2.40 void SPFNext (SPFVertex*, CandidateQueue&);
2.41 int SPFNexthopCalculation (SPFVertex* v, SPFVertex* w,
2.42 GlobalRoutingLinkRecord* l, uint32_t distance);
2.43 @@ -779,6 +798,7 @@
2.44 GlobalRoutingLinkRecord* prev_link);
2.45 void SPFIntraAddRouter (SPFVertex* v);
2.46 void SPFIntraAddTransit (SPFVertex* v);
2.47 + void SPFIntraAddStub (GlobalRoutingLinkRecord *l, SPFVertex* v);
2.48 uint32_t FindOutgoingTypeId (Ipv4Address a,
2.49 Ipv4Mask amask = Ipv4Mask("255.255.255.255"));
2.50
3.1 --- a/src/routing/global-routing/global-route-manager.h Sun Nov 30 21:21:23 2008 -0800
3.2 +++ b/src/routing/global-routing/global-route-manager.h Sun Nov 30 23:37:12 2008 -0800
3.3 @@ -45,7 +45,7 @@
3.4 * the nodes in the simulation. Makes all nodes in the simulation into
3.5 * routers.
3.6 *
3.7 - * All this function does is call the three private functions
3.8 + * All this function does is call the three functions
3.9 * SelectRouterNodes (), BuildGlobalRoutingDatabase (), and
3.10 * InitializeRoutes ().
3.11 *
3.12 @@ -55,6 +55,21 @@
3.13 */
3.14 static void PopulateRoutingTables ();
3.15
3.16 +/**
3.17 + * @brief Build a routing database and initialize the routing tables of
3.18 + * the nodes in the simulation. Makes the nodes in the provided container
3.19 + * into routers.
3.20 + *
3.21 + * All this function does is call the three functions
3.22 + * SelectRouterNodes (), BuildGlobalRoutingDatabase (), and
3.23 + * InitializeRoutes ().
3.24 + *
3.25 + * @see SelectRouterNodes (Node Container c);
3.26 + * @see BuildGlobalRoutingDatabase ();
3.27 + * @see InitializeRoutes ();
3.28 + */
3.29 + static void PopulateRoutingTables (NodeContainer c);
3.30 +
3.31 /**
3.32 *@brief Remove all routes that were previously installed in a prior call
3.33 * to either PopulateRoutingTables() or RecomputeRoutingTables(), and
3.34 @@ -73,32 +88,9 @@
3.35 static void RecomputeRoutingTables ();
3.36
3.37 /**
3.38 - * @brief Build a routing database and initialize the routing tables of
3.39 - * the nodes in the simulation. Makes the nodes in the provided container
3.40 - * into routers.
3.41 - *
3.42 - * All this function does is call BuildGlobalRoutingDatabase () and
3.43 - * InitializeRoutes ().
3.44 - *
3.45 - * @see BuildGlobalRoutingDatabase ();
3.46 - * @see InitializeRoutes ();
3.47 - */
3.48 - static void PopulateRoutingTables (NodeContainer c);
3.49 -
3.50 -/**
3.51 - * @brief Allocate a 32-bit router ID from monotonically increasing counter.
3.52 - */
3.53 - static uint32_t AllocateRouterId ();
3.54 -
3.55 -private:
3.56 -
3.57 -/**
3.58 * @brief Delete all static routes on all nodes that have a
3.59 * GlobalRouterInterface
3.60 *
3.61 - * TODO: separate manually assigned static routes from static routes that
3.62 - * the global routing code injects, and only delete the latter
3.63 - * @internal
3.64 */
3.65 static void DeleteGlobalRoutes ();
3.66
3.67 @@ -119,6 +111,13 @@
3.68 static void SelectRouterNodes (NodeContainer c);
3.69
3.70 /**
3.71 + * @brief Allocate a 32-bit router ID from monotonically increasing counter.
3.72 + */
3.73 + static uint32_t AllocateRouterId ();
3.74 +
3.75 +private:
3.76 +
3.77 +/**
3.78 * @brief Build the routing database by gathering Link State Advertisements
3.79 * from each node exporting a GlobalRouter interface.
3.80 * @internal
4.1 --- a/src/routing/global-routing/global-router-interface.cc Sun Nov 30 21:21:23 2008 -0800
4.2 +++ b/src/routing/global-routing/global-router-interface.cc Sun Nov 30 23:37:12 2008 -0800
4.3 @@ -413,23 +413,30 @@
4.4
4.5 os << "---------- RouterLSA Link Record ----------" << std::endl;
4.6 os << "m_linkType = " << p->m_linkType;
4.7 - if (p->m_linkType == GlobalRoutingLinkRecord::TransitNetwork)
4.8 + if (p->m_linkType == GlobalRoutingLinkRecord::PointToPoint)
4.9 + {
4.10 + os << " (GlobalRoutingLinkRecord::PointToPoint)" << std::endl;
4.11 + os << "m_linkId = " << p->m_linkId << std::endl;
4.12 + os << "m_linkData = " << p->m_linkData << std::endl;
4.13 + os << "m_metric = " << p->m_metric << std::endl;
4.14 + }
4.15 + else if (p->m_linkType == GlobalRoutingLinkRecord::TransitNetwork)
4.16 {
4.17 os << " (GlobalRoutingLinkRecord::TransitNetwork)" << std::endl;
4.18 os << "m_linkId = " << p->m_linkId << " (Designated router for network)" << std::endl;
4.19 os << "m_linkData = " << p->m_linkData << " (This router's IP address)" << std::endl;
4.20 os << "m_metric = " << p->m_metric << std::endl;
4.21 }
4.22 - else if (p->GetLinkType () == GlobalRoutingLinkRecord::StubNetwork)
4.23 + else if (p->m_linkType == GlobalRoutingLinkRecord::StubNetwork)
4.24 {
4.25 - os << "(GlobalRoutingLinkRecord::StubNetwork)" << std::endl;
4.26 + os << " (GlobalRoutingLinkRecord::StubNetwork)" << std::endl;
4.27 os << "m_linkId = " << p->m_linkId << " (Network number of attached network)" << std::endl;
4.28 os << "m_linkData = " << p->m_linkData << " (Network mask of attached network)" << std::endl;
4.29 os << "m_metric = " << p->m_metric << std::endl;
4.30 }
4.31 else
4.32 {
4.33 - os << "(Unknown LinkType)" << std::endl;
4.34 + os << " (Unknown LinkType)" << std::endl;
4.35 os << "m_linkId = " << p->m_linkId << std::endl;
4.36 os << "m_linkData = " << p->m_linkData << std::endl;
4.37 os << "m_metric = " << p->m_metric << std::endl;
4.38 @@ -621,7 +628,7 @@
4.39 // the segment. We add the appropriate link record to the LSA.
4.40 //
4.41 // If the device is a point to point link, we treat it separately. In
4.42 - // that case, there always two link records added.
4.43 + // that case, there may be one or two link records added.
4.44 //
4.45 if (ndLocal->IsBroadcast () && !ndLocal->IsPointToPoint () )
4.46 {
4.47 @@ -1007,12 +1014,6 @@
4.48 rc = FindIfIndexForDevice(nodeRemote, ndRemote, ifIndexRemote);
4.49 NS_ABORT_MSG_IF (rc == false, "GlobalRouter::ProcessPointToPointLinks(): No interface index associated with remote device");
4.50
4.51 - if (!ipv4Remote->IsUp (ifIndexRemote))
4.52 - {
4.53 - NS_LOG_LOGIC ("Remote side interface " << ifIndexRemote << " not up");
4.54 - return;
4.55 - }
4.56 -
4.57 //
4.58 // Now that we have the Ipv4 interface, we can get the (remote) address and
4.59 // mask we need.
4.60 @@ -1026,15 +1027,22 @@
4.61 // link records; the first is a point-to-point record describing the link and
4.62 // the second is a stub network record with the network number.
4.63 //
4.64 - GlobalRoutingLinkRecord *plr = new GlobalRoutingLinkRecord;
4.65 - NS_ABORT_MSG_IF (plr == 0, "GlobalRouter::ProcessPointToPointLink(): Can't alloc link record");
4.66 - plr->SetLinkType (GlobalRoutingLinkRecord::PointToPoint);
4.67 - plr->SetLinkId (rtrIdRemote);
4.68 - plr->SetLinkData (addrLocal);
4.69 - plr->SetMetric (metricLocal);
4.70 - pLSA->AddLinkRecord (plr);
4.71 - plr = 0;
4.72 + GlobalRoutingLinkRecord *plr;
4.73 + if (ipv4Remote->IsUp (ifIndexRemote))
4.74 + {
4.75 + NS_LOG_LOGIC ("Remote side interface " << ifIndexRemote << " is up-- add a type 1 link");
4.76 +
4.77 + plr = new GlobalRoutingLinkRecord;
4.78 + NS_ABORT_MSG_IF (plr == 0, "GlobalRouter::ProcessPointToPointLink(): Can't alloc link record");
4.79 + plr->SetLinkType (GlobalRoutingLinkRecord::PointToPoint);
4.80 + plr->SetLinkId (rtrIdRemote);
4.81 + plr->SetLinkData (addrLocal);
4.82 + plr->SetMetric (metricLocal);
4.83 + pLSA->AddLinkRecord (plr);
4.84 + plr = 0;
4.85 + }
4.86
4.87 + // Regardless of state of peer, add a type 3 link (RFC 2328: 12.4.1.1)
4.88 plr = new GlobalRoutingLinkRecord;
4.89 NS_ABORT_MSG_IF (plr == 0, "GlobalRouter::ProcessPointToPointLink(): Can't alloc link record");
4.90 plr->SetLinkType (GlobalRoutingLinkRecord::StubNetwork);