--- a/src/internet-stack/ipv4-global-routing.cc Wed Mar 25 10:40:01 2009 -0700 +++ a/src/internet-stack/ipv4-global-routing.cc Sun Mar 29 11:30:52 2009 -0700 @@ -110,7 +110,7 @@ Ipv4GlobalRouting::LookupGlobal (Ipv4Add j != m_networkRoutes.end (); j++) { - NS_ASSERT ((*j)->IsNetwork ()); + NS_ASSERT ((*j)->IsNetwork () || (*j)->IsDefault ()); Ipv4Mask mask = (*j)->GetDestNetworkMask (); Ipv4Address entry = (*j)->GetDestNetwork (); if (mask.IsMatch (dest, entry)) --- a/src/routing/global-routing/global-route-manager-impl.cc Wed Mar 25 10:40:01 2009 -0700 +++ a/src/routing/global-routing/global-route-manager-impl.cc Sun Mar 29 11:30:52 2009 -0700 @@ -1058,6 +1058,88 @@ GlobalRouteManagerImpl::DebugSPFCalculat 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 +GlobalRouteManagerImpl::CheckForStubNode (Ipv4Address root) +{ + NS_LOG_FUNCTION (root); + GlobalRoutingLSA *rlsa = m_lsdb->GetLSA (root); + Ipv4Address myRouterId = rlsa->GetLinkStateId (); + int transits = 0; + GlobalRoutingLinkRecord *transitLink; + for (uint32_t i = 0; i < rlsa->GetNLinkRecords (); i++) + { + GlobalRoutingLinkRecord *l = rlsa->GetLinkRecord (i); + if (l->GetLinkType () == GlobalRoutingLinkRecord::TransitNetwork) + { + transits++; + transitLink = l; + } + else if (l->GetLinkType () == GlobalRoutingLinkRecord::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 () == GlobalRoutingLinkRecord::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 () == GlobalRoutingLinkRecord::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 + GlobalRoutingLSA *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 + // + GlobalRoutingLinkRecord *lr = w_lsa->GetLinkRecord (j); + if (lr->GetLinkType () != GlobalRoutingLinkRecord::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 gr = GetGlobalRoutingProtocol (rlsa->GetNode ()->GetId ()); + NS_ASSERT (gr); + gr->AddNetworkRouteTo (Ipv4Address ("0.0.0.0"), Ipv4Mask ("0.0.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 GlobalRouteManagerImpl::SPFCalculate (Ipv4Address root) @@ -1090,6 +1172,20 @@ GlobalRouteManagerImpl::SPFCalculate (Ip v->SetDistanceFromRoot (0); v->GetLSA ()->SetStatus (GlobalRoutingLSA::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 (;;) { --- a/src/routing/global-routing/global-route-manager-impl.h Wed Mar 25 10:40:01 2009 -0700 +++ a/src/routing/global-routing/global-route-manager-impl.h Sun Mar 29 11:30:52 2009 -0700 @@ -788,6 +788,7 @@ private: SPFVertex* m_spfroot; GlobalRouteManagerLSDB* m_lsdb; + bool CheckForStubNode (Ipv4Address root); void SPFCalculate (Ipv4Address root); void SPFProcessStubs (SPFVertex* v); void SPFNext (SPFVertex*, CandidateQueue&); --- a/src/routing/global-routing/global-router-interface.cc Wed Mar 25 10:40:01 2009 -0700 +++ a/src/routing/global-routing/global-router-interface.cc Sun Mar 29 11:30:52 2009 -0700 @@ -24,6 +24,7 @@ #include "ns3/channel.h" #include "ns3/net-device.h" #include "ns3/node.h" +#include "ns3/node-list.h" #include "ns3/ipv4.h" #include "ns3/bridge-net-device.h" #include "ns3/net-device-container.h" @@ -140,7 +141,8 @@ GlobalRoutingLSA::GlobalRoutingLSA() m_linkRecords(), m_networkLSANetworkMask("0.0.0.0"), m_attachedRouters(), - m_status(GlobalRoutingLSA::LSA_SPF_NOT_EXPLORED) + m_status(GlobalRoutingLSA::LSA_SPF_NOT_EXPLORED), + m_node_id(0) { NS_LOG_FUNCTION_NOARGS (); } @@ -156,7 +158,8 @@ GlobalRoutingLSA::GlobalRoutingLSA ( m_linkRecords(), m_networkLSANetworkMask("0.0.0.0"), m_attachedRouters(), - m_status(status) + m_status(status), + m_node_id(0) { NS_LOG_FUNCTION (this << status << linkStateId << advertisingRtr); } @@ -165,7 +168,8 @@ GlobalRoutingLSA::GlobalRoutingLSA (Glob : 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_status(lsa.m_status), + m_node_id(lsa.m_node_id) { NS_LOG_FUNCTION_NOARGS (); NS_ASSERT_MSG(IsEmpty(), @@ -181,7 +185,8 @@ GlobalRoutingLSA::operator= (const Globa m_linkStateId = lsa.m_linkStateId; m_advertisingRtr = lsa.m_advertisingRtr; m_networkLSANetworkMask = lsa.m_networkLSANetworkMask, - m_status = lsa.m_status; + m_status = lsa.m_status, + m_node_id = lsa.m_node_id; ClearLinkRecords (); CopyLinkRecords (lsa); @@ -380,6 +385,20 @@ GlobalRoutingLSA::SetStatus (GlobalRouti m_status = status; } + Ptr +GlobalRoutingLSA::GetNode (void) const +{ + NS_LOG_FUNCTION_NOARGS (); + return NodeList::GetNode (m_node_id); +} + + void +GlobalRoutingLSA::SetNode (Ptr node) +{ + NS_LOG_FUNCTION (node); + m_node_id = node->GetId (); +} + void GlobalRoutingLSA::Print (std::ostream &os) const { @@ -570,6 +589,7 @@ GlobalRouter::DiscoverLSAs (void) pLSA->SetLinkStateId (m_routerId); pLSA->SetAdvertisingRouter (m_routerId); pLSA->SetStatus (GlobalRoutingLSA::LSA_SPF_NOT_EXPLORED); + pLSA->SetNode (node); // // Ask the node for the number of net devices attached. This isn't necessarily @@ -1087,6 +1107,7 @@ GlobalRouter::BuildNetworkLSAs (NetDevic pLSA->SetAdvertisingRouter (m_routerId); pLSA->SetNetworkLSANetworkMask (maskLocal); pLSA->SetStatus (GlobalRoutingLSA::LSA_SPF_NOT_EXPLORED); + pLSA->SetNode (node); // // Build a list of AttachedRouters by walking the devices in the channel --- a/src/routing/global-routing/global-router-interface.h Wed Mar 25 10:40:01 2009 -0700 +++ a/src/routing/global-routing/global-router-interface.h Sun Mar 29 11:30:52 2009 -0700 @@ -476,6 +476,18 @@ public: */ void SetStatus (SPFStatus status); +/** + * @brief Get the Node pointer of the node that originated this LSA + * @returns Node pointer + */ + Ptr GetNode (void) const; + +/** + * @brief Set the Node pointer of the node that originated this LSA + * @param node Node pointer + */ + void SetNode (Ptr node); + private: /** * The type of the LSA. Each LSA type has a separate advertisement @@ -544,6 +556,8 @@ private: * proper position in the tree. */ SPFStatus m_status; + + uint32_t m_node_id; }; std::ostream& operator<< (std::ostream& os, GlobalRoutingLSA& lsa);