Added more NS_LOG to debug this class * * * Enabled ECMP in the global routing class * * * Enabled ECMP in GlobalRouting class so that different routes can be returned and guide packets to go alone different ECMP * * * Changed GlobalRouteManagerImpl class to have single setter method for both next-hop-ip and out-going-interface-index. This change allows merging the list of next-hop-ip and out-going-interface-index consistance * * * Continue enabling the ECMP in global routing by treating next-hop and out-going-interface-index as one entity New methods are provided in the fix-enable-ecmp-in-global-routing.patch for using the new entity. They are - void SPFVertex::SetRootExitDirection - SPFVertex::NodeExit_t SPFVertex::GetRootExitDirection - void SPFVertex::MergeRootExitDirections * * * Continue the enable-ecmp-in-global-routing-2.patch --- allowing adding multiple routes on the root node for each destination * * * Fixed SPFVertex getter and setter method for handling multiple root exit direction todo: - add a method so that a vertex can inherit all root exit directions from its parent node * * * Fixed the global routing protocol so that it can inherit all exit directions from vertex to vertex. Moreover, fixed also the way to set the exit direction. * * * Tried fixing the bug that GlobalRouteManager:~SPFVertex() did not end correctly. It may be due to the items in m_ecmpRootExits and m_parents are not cleared when calling the destructor * * * Fixed a bug --- SPFVertex can be deleted more than once! Bug: As SPFVertex can have more than one parent when ECMP is enabled, different parent can delete the same child and leading to duplicated deletion on the child vertex. * * * Added method so that vertex can be deteched from all its parents diff -r 409388415dfc src/routing/global-routing/global-route-manager-impl.cc --- a/src/routing/global-routing/global-route-manager-impl.cc Sun Aug 23 18:25:25 2009 +0800 +++ b/src/routing/global-routing/global-route-manager-impl.cc Sun Aug 23 18:25:46 2009 +0800 @@ -25,6 +25,8 @@ #include #include #include +#include +#include #include "ns3/assert.h" #include "ns3/fatal-error.h" #include "ns3/log.h" @@ -41,6 +43,62 @@ namespace ns3 { +//std::ostream& +//operator<< (std::ostream& os, const SPFVertex::ListOfIf_t& ifs) +//{ +// os << "{"; +// for (SPFVertex::ListOfIf_t::const_iterator iter = ifs.begin ();;) +// { +// os << *iter; +// if (++iter != ifs.end ()) +// os << ", "; +// else +// break; +// } +// os << "}"; +// return os; +//} +// +//std::ostream& +//operator<< (std::ostream& os, const SPFVertex::ListOfAddr_t& addrs) +//{ +// os << "{"; +// for (SPFVertex::ListOfAddr_t::const_iterator iter = addrs.begin ();;) +// { +// os << *iter; +// if (++iter != addrs.end ()) +// os << ", "; +// else +// break; +// } +// os << "}"; +// return os; +//} + +std::ostream& +operator<< (std::ostream& os, const SPFVertex::NodeExit_t& exit) +{ + os << "(" << exit.first << " ," << exit.second << ")"; + return os; +} + +std::ostream& +operator<< (std::ostream& os, const SPFVertex::ListOfSPFVertex_t& vs) +{ + typedef SPFVertex::ListOfSPFVertex_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; +} + // --------------------------------------------------------------------------- // // SPFVertex Implementation @@ -54,7 +112,7 @@ m_distanceFromRoot (SPF_INFINITY), m_rootOif (SPF_INFINITY), m_nextHop ("0.0.0.0"), - m_parent (0), + m_parents (), m_children (), m_vertexProcessed (false) { @@ -67,11 +125,12 @@ m_distanceFromRoot (SPF_INFINITY), m_rootOif (SPF_INFINITY), m_nextHop ("0.0.0.0"), - m_parent (0), + m_parents (), m_children (), m_vertexProcessed (false) { NS_LOG_FUNCTION_NOARGS (); + if (lsa->GetLSType () == GlobalRoutingLSA::RouterLSA) { NS_LOG_LOGIC ("Setting m_vertexType to VertexRouter"); @@ -86,17 +145,50 @@ SPFVertex::~SPFVertex () { - NS_LOG_FUNCTION_NOARGS (); - for ( ListOfSPFVertex_t::iterator i = m_children.begin (); - i != m_children.end (); - i++) + 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 (ListOfSPFVertex_t::iterator piter = m_parents.begin (); + piter != m_parents.end (); + piter++) + { + // remove the current vertex from its parent'ss 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 (); + NS_ASSERT_MSG (orgCount > newCount, "Unable to find the current vertex from its parents --- impossible!"); + } + + // delete children + while (m_children.size () > 0) { - SPFVertex *p = *i; + // pop out children one by one. Some children may disappered + // when deleting some other children in the list. As a result, + // it is necessary to use pop to walk through all children, intead + // of suing iterator. + // + // Note that m_children.pop_front () is not necessary as this + // p is removed from the children list when p is deleted + SPFVertex* 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; - *i = 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 @@ -155,24 +247,43 @@ return m_distanceFromRoot; } - void +void SPFVertex::SetOutgoingInterfaceId (int32_t id) { NS_LOG_FUNCTION (id); + + // always maintain only one output interface index when using setter/getter methods m_rootOif = id; } - uint32_t +uint32_t SPFVertex::GetOutgoingInterfaceId (void) const { NS_LOG_FUNCTION_NOARGS (); return m_rootOif; } +//void +//SPFVertex::MergeOutgoingInterfaceId (const SPFVertex* v) +//{ +// NS_LOG_FUNCTION (v); +// +// NS_LOG_LOGIC ("Before merge, list of root out-going interfaces = " << m_rootOif); +// // combine the two lists first, and then remove any duplicated after +// m_rootOif.insert (m_rootOif.end (), +// v->m_rootOif.begin (), v->m_rootOif.end ()); +// // remove duplication +// m_rootOif.sort (); +// m_rootOif.unique (); +// NS_LOG_LOGIC ("After merge, list of root out-going interfaces = " << m_rootOif); +//} + void SPFVertex::SetNextHop (Ipv4Address nextHop) { NS_LOG_FUNCTION (nextHop); + + // always maintain only one nexthop when using setter/getter methods m_nextHop = nextHop; } @@ -183,21 +294,142 @@ return m_nextHop; } +//void +//SPFVertex::MergeNextHop (const SPFVertex* v) +//{ +// NS_LOG_FUNCTION (v); +// +// NS_LOG_LOGIC ("Before merge, list of next hops = " << m_nextHop); +// // combine the two lists first, and then remove any duplicated after +// m_nextHop.insert (m_nextHop.end (), +// v->m_nextHop.begin (), v->m_nextHop.end ()); +// // remove duplication +// m_nextHop.sort (); +// m_nextHop.unique (); +// NS_LOG_LOGIC ("After merge, list of next hops = " << m_nextHop); +//} + void SPFVertex::SetParent (SPFVertex* parent) { NS_LOG_FUNCTION (parent); - m_parent = parent; + + // always maintain only one parent when using setter/getter methods + m_parents.clear (); + m_parents.push_back (parent); } SPFVertex* -SPFVertex::GetParent (void) const +SPFVertex::GetParent (uint32_t i) const { NS_LOG_FUNCTION_NOARGS (); - return m_parent; + + // If the index i is out-of-range, return 0 and do nothing + if (m_parents.size () <= i) + { + NS_LOG_LOGIC ("Index to SPFVertex's parent is out-of-range."); + return 0; + } + ListOfSPFVertex_t::const_iterator iter = m_parents.begin (); + while (i-- > 0) {iter++;} + return *iter; } - uint32_t +void +SPFVertex::MergeParent (const SPFVertex* 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 +SPFVertex::SetRootExitDirection (Ipv4Address 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 +SPFVertex::SetRootExitDirection (SPFVertex::NodeExit_t exit) +{ + NS_LOG_FUNCTION (exit); + SetRootExitDirection (exit.first, exit.second); +} + +SPFVertex::NodeExit_t +SPFVertex::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 SPFVertex::m_ecmpRootExits!"); + CIter_t iter = m_ecmpRootExits.begin (); + while (i-- > 0) {iter++;} + + return *iter; +} + +SPFVertex::NodeExit_t +SPFVertex::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, but this assumption is violated!"); + return GetRootExitDirection (0); +} + +void +SPFVertex::MergeRootExitDirections (const SPFVertex* 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 +SPFVertex::InheritAllRootExitDirections (const SPFVertex* vertex) +{ + NS_LOG_FUNCTION (vertex); + + // discard all exit direction currently assoicated 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 +SPFVertex::GetNRootExitDirections () const +{ + NS_LOG_FUNCTION_NOARGS (); + return m_ecmpRootExits.size (); +} + +uint32_t SPFVertex::GetNChildren (void) const { NS_LOG_FUNCTION_NOARGS (); @@ -341,7 +573,7 @@ GlobalRouteManagerImpl::GlobalRouteManagerImpl () : - m_spfroot (0) + m_spfroot (0) { NS_LOG_FUNCTION_NOARGS (); m_lsdb = new GlobalRouteManagerLSDB (); @@ -649,15 +881,14 @@ // Is there already vertex w in candidate list? if (w_lsa->GetStatus () == GlobalRoutingLSA::LSA_SPF_NOT_EXPLORED) { - -// prepare vertex w - w = new SPFVertex (w_lsa); // Calculate nexthop to w // We need to figure out how to actually get to the new router represented // by . 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 SPFVertex (w_lsa); if (SPFNexthopCalculation (v, w, l, distance)) { w_lsa->SetStatus (GlobalRoutingLSA::LSA_SPF_CANDIDATE); @@ -671,6 +902,9 @@ v->GetVertexId () << ", distance: " << w->GetDistanceFromRoot ()); } + else + NS_ASSERT_MSG (0, "SPFNexthopCalculation never " + << "return false, but it does now!"); } else if (w_lsa->GetStatus () == GlobalRoutingLSA::LSA_SPF_CANDIDATE) { @@ -681,22 +915,54 @@ // // So, locate the vertex in the candidate queue and take a look at the // distance. - w = candidate.Find (w_lsa->GetLinkStateId ()); - if (w->GetDistanceFromRoot () < distance) + +/* (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. +*/ + SPFVertex* 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 (w->GetDistanceFromRoot () == distance) + else if (cw->GetDistanceFromRoot () == distance) { // -// This path is one with an equal cost. Do nothing for now -- we're not doing -// equal-cost multipath cases yet. +// 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 codes. +// 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 equivelent to calling +// ospf_nexthop_merge (cw->nexthop, w->nexthop) in quagga-0.98.6 +// (ospf_spf.c::859), althrough the detail implemenation +// is very different from quagga (blame ns3::GlobalRouteManagerImpl) + +// prepare vertex w + w = new SPFVertex (w_lsa); + SPFNexthopCalculation (v, w, l, distance); + cw->MergeRootExitDirections (w); + cw->MergeParent (w); +// SPFVertexAddParent (w) is necessary as the destructor of +// SPFVertex checks if the vertex and its parent is linked +// bidirectionally + SPFVertexAddParent (w); + delete w; } - else + else // cw->GetDistanceFromRoot () > w->GetDistanceFromRoot () { // // this path represents a new, lower-cost path to (the vertex we found in @@ -706,7 +972,7 @@ // N.B. the nexthop_calculation is conditional, if it finds a valid nexthop // it will call spf_add_parents, which will flush the old parents // - if (SPFNexthopCalculation (v, w, l, distance)) + if (SPFNexthopCalculation (v, cw, l, distance)) { // // If we've changed the cost to get to the vertex represented by , we @@ -714,7 +980,7 @@ // candidate.Reorder (); } - } // new lower cost path found + } // new lower cost path found } // end W is already on the candidate list } // end loop over the links in V's LSA } @@ -808,20 +1074,21 @@ // from the root node to the host represented by vertex , you have to send // the packet to the next hop address specified in w->m_nextHop. // - w->SetNextHop (linkRemote->GetLinkData ()); + Ipv4Address nextHop = linkRemote->GetLinkData (); // // Now find the outgoing interface corresponding to the point to point link // from the perspective of -- remember that is the link "from" // "to" . // - w->SetOutgoingInterfaceId ( - FindOutgoingInterfaceId (l->GetLinkData ())); + 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 " << w->GetNextHop () << - " via outgoing interface " << w->GetOutgoingInterfaceId () << + " goes through next hop " << nextHop << + " via outgoing interface " << outIf << " with distance " << distance); } // end W is a router vertes else @@ -831,14 +1098,16 @@ GlobalRoutingLSA* w_lsa = w->GetLSA (); NS_ASSERT (w_lsa->GetLSType () == GlobalRoutingLSA::NetworkLSA); // Find outgoing interface ID for this network - w->SetOutgoingInterfaceId ( - FindOutgoingInterfaceId (w_lsa->GetLinkStateId (), - w_lsa->GetNetworkLSANetworkMask () )); + uint32_t outIf = FindOutgoingInterfaceId (w_lsa->GetLinkStateId (), + w_lsa->GetNetworkLSANetworkMask () ); +// Set the next hop to 0.0.0.0 meaning "not exist" + Ipv4Address nextHop = Ipv4Address::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 " << w->GetOutgoingInterfaceId () << + " via outgoing interface " << outIf << " with distance " << distance); return 1; } @@ -862,18 +1131,18 @@ * use can then be derived from the next hop IP address (or * it can be inherited from the parent network). */ - w->SetNextHop (linkRemote->GetLinkData ()); - w->SetOutgoingInterfaceId (v->GetOutgoingInterfaceId ()); + Ipv4Address 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 " << w->GetNextHop () << - " via outgoing interface " << w->GetOutgoingInterfaceId ()); + " goes through next hop " << nextHop << + " via outgoing interface " << outIf); } } else { - w->SetNextHop (v->GetNextHop ()); - w->SetOutgoingInterfaceId (v->GetOutgoingInterfaceId ()); + w->SetRootExitDirection (v->GetRootExitDirection ()); } } else @@ -891,8 +1160,7 @@ // (shortest) paths. So the next hop and outoing interface remain the same // (are inherited). // - w->SetNextHop (v->GetNextHop ()); - w->SetOutgoingInterfaceId (v->GetOutgoingInterfaceId ()); + w->InheritAllRootExitDirections (v); } // // In all cases, we need valid values for the distance metric and a parent. @@ -1190,8 +1458,8 @@ // // Note that when there is a choice of vertices closest to the root, network // vertices must be chosen before router vertices in order to necessarily -// find all equal-cost paths. We don't do this at this moment, we should add -// the treatment above codes. -- kunihiro. +// find all equal-cost paths. This is done by using the patch +// 'change-candidate-queue-to-consider-lsa-type-when-ordering.patch' // // RFC2328 16.1. (4). // @@ -1367,12 +1635,6 @@ Ipv4Mask tempmask ("255.255.255.0"); Ipv4Address tempip = l->GetLinkId (); tempip = tempip.CombineMask (tempmask); - - NS_LOG_LOGIC (" Node " << node->GetId () << - " add route to " << tempip << - " with mask " << tempmask << - " using next hop " << v->GetNextHop () << - " via interface " << v->GetOutgoingInterfaceId ()); // // Here's why we did all of that work. We're going to add a host route to the // host address found in the m_linkData field of the point-to-point link @@ -1394,21 +1656,29 @@ } Ptr gr = router->GetRoutingProtocol (); NS_ASSERT (gr); - if (v->GetOutgoingInterfaceId () >= 0) - { - gr->AddNetworkRouteTo (tempip, tempmask, v->GetNextHop (), v->GetOutgoingInterfaceId ()); - NS_LOG_LOGIC ("Node " << node->GetId () << - " add network route to " << tempip << - " using next hop " << v->GetNextHop () << - " via interface " << v->GetOutgoingInterfaceId ()); - } - else - { - NS_LOG_LOGIC ("Node " << node->GetId () << - " NOT able to add network route to " << tempip << - " using next hop " << v->GetNextHop () << - " since outgoing interface id is negative"); - } + // 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++) + { + SPFVertex::NodeExit_t exit = v->GetRootExitDirection (i); + Ipv4Address nextHop = exit.first; + int32_t outIf = exit.second; + if (outIf >= 0) + { + gr->AddNetworkRouteTo (tempip, tempmask, nextHop, outIf); + NS_LOG_LOGIC ("(Route " <GetId () << + " add network route to " << tempip << + " using next hop " << nextHop << + " via interface " << outIf); + } + else + { + NS_LOG_LOGIC ("(Route " <GetId () << + " NOT able to add network route to " << tempip << + " using next hop " << nextHop << + " since outgoing interface id is negative"); + } + } return; } // if } // for @@ -1598,11 +1868,6 @@ { continue; } - - NS_LOG_LOGIC (" Node " << node->GetId () << - " add route to " << lr->GetLinkData () << - " using next hop " << v->GetNextHop () << - " via interface " << v->GetOutgoingInterfaceId ()); // // Here's why we did all of that work. We're going to add a host route to the // host address found in the m_linkData field of the point-to-point link @@ -1623,22 +1888,31 @@ } Ptr gr = router->GetRoutingProtocol (); NS_ASSERT (gr); - if (v->GetOutgoingInterfaceId () >= 0) - { - gr->AddHostRouteTo (lr->GetLinkData (), v->GetNextHop (), - v->GetOutgoingInterfaceId ()); - NS_LOG_LOGIC ("Node " << node->GetId () << - " adding host route to " << lr->GetLinkData () << - " using next hop " << v->GetNextHop () << - " and outgoing interface " << v->GetOutgoingInterfaceId ()); - } - else - { - NS_LOG_LOGIC ("Node " << node->GetId () << - " NOT able to add host route to " << lr->GetLinkData () << - " using next hop " << v->GetNextHop () << - " since outgoing interface id is negative"); - } + // 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++) + { + SPFVertex::NodeExit_t exit = v->GetRootExitDirection (i); + Ipv4Address nextHop = exit.first; + int32_t outIf = exit.second; + if (outIf >= 0) + { + gr->AddHostRouteTo (lr->GetLinkData (), nextHop, + outIf); + NS_LOG_LOGIC ("(Route " <GetId () << + " adding host route to " << lr->GetLinkData () << + " using next hop " << nextHop << + " and outgoing interface " << outIf); + } + else + { + NS_LOG_LOGIC ("(Route " <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. @@ -1726,21 +2000,30 @@ } Ptr gr = router->GetRoutingProtocol (); NS_ASSERT (gr); - if (v->GetOutgoingInterfaceId () >= 0) - { - gr->AddNetworkRouteTo (tempip, tempmask, v->GetNextHop (), - v->GetOutgoingInterfaceId ()); - NS_LOG_LOGIC ("Node " << node->GetId () << - " add network route to " << tempip << - " using next hop " << v->GetNextHop () << - " via interface " << v->GetOutgoingInterfaceId ()); - } - else - { - NS_LOG_LOGIC ("Node " << node->GetId () << - " NOT able to add network route to " << tempip << - " using next hop " << v->GetNextHop () << - " since outgoing interface id is negative"); + // 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++) + { + SPFVertex::NodeExit_t exit = v->GetRootExitDirection (i); + Ipv4Address nextHop = exit.first; + int32_t outIf = exit.second; + + if (outIf >= 0) + { + gr->AddNetworkRouteTo (tempip, tempmask, nextHop, outIf); + NS_LOG_LOGIC ("(Route " <GetId () << + " add network route to " << tempip << + " using next hop " << nextHop << + " via interface " << outIf); + } + else + { + NS_LOG_LOGIC ("(Route " <GetId () << + " NOT able to add network route to " << tempip << + " using next hop " << nextHop << + " since outgoing interface id is negative " << outIf); + } } } } @@ -1755,13 +2038,20 @@ // Given a pointer to a vertex, it links back to the vertex's parent that it // already has set and adds itself to that vertex's list of children. // -// For now, only one parent (not doing equal-cost multipath) -// void GlobalRouteManagerImpl::SPFVertexAddParent (SPFVertex* v) { NS_LOG_FUNCTION (v); - v->GetParent ()->AddChild (v); + + for (uint32_t i=0;;) + { + SPFVertex* parent; + // check if all parents of vertex v + if ((parent = v->GetParent (i++)) == 0) + break; + parent->AddChild (v); + } + //v->GetParent ()->AddChild (v); } } // namespace ns3 diff -r 409388415dfc src/routing/global-routing/global-route-manager-impl.h --- a/src/routing/global-routing/global-route-manager-impl.h Sun Aug 23 18:25:25 2009 +0800 +++ b/src/routing/global-routing/global-route-manager-impl.h Sun Aug 23 18:25:46 2009 +0800 @@ -255,6 +255,8 @@ void SetDistanceFromRoot (uint32_t distance); /** + * \deprecated Use GetRootExitDirection instead + * * @brief Get the interface ID that should be used to begin forwarding packets * from the root SPFVertex to "this" SPFVertex. * @internal @@ -294,9 +296,11 @@ * @returns The interface index to use when forwarding packets to the host * or network represented by "this" SPFVertex. */ - uint32_t GetOutgoingInterfaceId (void) const; + uint32_t GetOutgoingInterfaceId (void) const NS_DEPRECATED; /** + * \deprecated Use SetRootExitDirection instead + * * @brief Set the interface ID that should be used to begin forwarding packets * from the root SPFVertex to "this" SPFVertex. * @internal @@ -336,9 +340,11 @@ * @param id The interface index to use when forwarding packets to the host or * network represented by "this" SPFVertex. */ - void SetOutgoingInterfaceId (int32_t id); + void SetOutgoingInterfaceId (int32_t id) NS_DEPRECATED; /** + * \deprecated Use GetRootExitDirection instead + * * @brief Get the IP address that should be used to begin forwarding packets * from the root SPFVertex to "this" SPFVertex. * @internal @@ -379,9 +385,11 @@ * @returns The IP address to use when forwarding packets to the host * or network represented by "this" SPFVertex. */ - Ipv4Address GetNextHop (void) const; + Ipv4Address GetNextHop (void) const NS_DEPRECATED; /** + * \deprecated Use SetRootExitDirection instead + * * @brief Set the IP address that should be used to begin forwarding packets * from the root SPFVertex to "this" SPFVertex. * @internal @@ -422,7 +430,136 @@ * @param nextHop The IP address to use when forwarding packets to the host * or network represented by "this" SPFVertex. */ - void SetNextHop (Ipv4Address nextHop); + void SetNextHop (Ipv4Address nextHop) NS_DEPRECATED; +/** + * @brief Set the IP address and out-going interface index that should be used + * to begin forwarding packets from the root SPFVertex to "this" SPFVertex. + * @internal + * + * Each router node in the simulation is associated with an SPFVertex object. + * When calculating routes, each of these routers is, in turn, chosen as the + * "root" of the calculation and routes to all of the other routers are + * eventually saved in the routing tables of each of the chosen nodes. + * + * The "Root" vertex is then the SPFVertex representing the router that is + * having its routing tables set. The "this" SPFVertex is the vertex that + * represents the host or network to which a route is being calculated from + * the root. The IP address that we're asking for is the address on the + * remote side of a link off of the root node that should be used as the + * destination for packets along the path to "this" vertex. + * + * When initializing the root SPFVertex, the IP address used when forwarding + * packets is determined by examining the Global Router Link Records of the + * Link State Advertisement generated by the root node's GlobalRouter. This + * address is used to forward packets off of the root's network down those + * links. As other vertices / nodes are discovered which are further away + * from the root, they will be accessible down one of the paths via a link + * described by one of these Global Router Link Records. + * + * To forward packets to these hosts or networks, the root node must begin + * the forwarding process by sending the packets to a first hop router down + * an interface. This means that the first hop address and interface ID must + * be the same for all downstream SPFVertices. We call this "inheriting" + * the interface and next hop. + * + * In this method we are telling the root node which exit direction it should send + * should I send a packet to the network or host represented by 'this' SPFVertex. + * + * @see GlobalRouter + * @see GlobalRoutingLSA + * @see GlobalRoutingLinkRecord + * @param nextHop The IP address to use when forwarding packets to the host + * or network represented by "this" SPFVertex. + * @param id The interface index to use when forwarding packets to the host or + * network represented by "this" SPFVertex. + */ + void SetRootExitDirection (Ipv4Address nextHop, int32_t id = SPF_INFINITY); + typedef std::pair NodeExit_t; +/** + * @brief Set the IP address and out-going interface index that should be used + * to begin forwarding packets from the root SPFVertex to "this" SPFVertex. + * @internal + * + * Each router node in the simulation is associated with an SPFVertex object. + * When calculating routes, each of these routers is, in turn, chosen as the + * "root" of the calculation and routes to all of the other routers are + * eventually saved in the routing tables of each of the chosen nodes. + * + * The "Root" vertex is then the SPFVertex representing the router that is + * having its routing tables set. The "this" SPFVertex is the vertex that + * represents the host or network to which a route is being calculated from + * the root. The IP address that we're asking for is the address on the + * remote side of a link off of the root node that should be used as the + * destination for packets along the path to "this" vertex. + * + * When initializing the root SPFVertex, the IP address used when forwarding + * packets is determined by examining the Global Router Link Records of the + * Link State Advertisement generated by the root node's GlobalRouter. This + * address is used to forward packets off of the root's network down those + * links. As other vertices / nodes are discovered which are further away + * from the root, they will be accessible down one of the paths via a link + * described by one of these Global Router Link Records. + * + * To forward packets to these hosts or networks, the root node must begin + * the forwarding process by sending the packets to a first hop router down + * an interface. This means that the first hop address and interface ID must + * be the same for all downstream SPFVertices. We call this "inheriting" + * the interface and next hop. + * + * In this method we are telling the root node which exit direction it should send + * should I send a packet to the network or host represented by 'this' SPFVertex. + * + * @see GlobalRouter + * @see GlobalRoutingLSA + * @see GlobalRoutingLinkRecord + * @param nextHop The IP address to use when forwarding packets to the host + * or network represented by "this" SPFVertex. + * @param exit The pair of next-hop-IP and out-going-interface-index to use when + * forwarding packets to the host or network represented by "this" SPFVertex. + */ + void SetRootExitDirection (SPFVertex::NodeExit_t exit); + /** + * \brief Obtain a pair indicating the exit direction from the root + * + * \param i An index to a pair + * \return A pair of next-hop-IP and out-going-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 out-going-interface-index for reaching + * 'this' vertex from the root + */ + NodeExit_t GetRootExitDirection () const; + /** + * \brief Merge into 'this' vertex the list of exit directions from + * another vertex + * + * This merge is necessary when ECMP are found. + * + * \param vertex From which the list of exit directions are obtain + * and are merged into 'this' vertex + */ + void MergeRootExitDirections (const SPFVertex* vertex); + /** + * \brief Inherit all root exit directions from a given vertex to 'this' vertex + * \param vertex The vertex from which all root exit directions are to be inherrited + * + * After the call of this method, the original root exit directions + * in 'this' vertex are all lost. + */ + void InheritAllRootExitDirections (const SPFVertex* vertex); + /** + * \brief Get the number of exit directions from root for reaching 'this' vertex + * \return The number of exit directions from root + */ + uint32_t GetNRootExitDirections () const; /** * @brief Get a pointer to the SPFVector that is the parent of "this" @@ -440,10 +577,11 @@ * This method returns a pointer to the parent node of "this" SPFVertex * (both of which reside in that SPF tree). * + * @param i The index to one of the parents * @returns A pointer to the SPFVertex that is the parent of "this" SPFVertex * in the SPF tree. */ - SPFVertex* GetParent (void) const; + SPFVertex* GetParent (uint32_t i = 0) const; /** * @brief Set the pointer to the SPFVector that is the parent of "this" @@ -465,6 +603,14 @@ * SPFVertex* in the SPF tree. */ void SetParent (SPFVertex* parent); + /** + * \brief Merge the Parent list from the v into this vertex + * + * \param v The vertex from which its list of Parent is read + * and then merged into the list of Parent of *this* vertex. + * Note that the list in v remains intact + */ + void MergeParent (const SPFVertex* v); /** * @brief Get the number of children of "this" SPFVertex. @@ -570,8 +716,11 @@ uint32_t m_distanceFromRoot; int32_t m_rootOif; Ipv4Address m_nextHop; - SPFVertex* m_parent; + typedef std::list< NodeExit_t > ListOfNodeExit_t; + /// store the multiple root's exits for supporting ECMP + ListOfNodeExit_t m_ecmpRootExits; typedef std::list ListOfSPFVertex_t; + ListOfSPFVertex_t m_parents; ListOfSPFVertex_t m_children; bool m_vertexProcessed; @@ -586,6 +735,10 @@ * need for it and a compiler provided shallow copy would be wrong. */ SPFVertex& operator= (SPFVertex& 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 SPFVertex::ListOfSPFVertex_t& vs); }; /** diff -r 409388415dfc src/routing/global-routing/ipv4-global-routing.cc --- a/src/routing/global-routing/ipv4-global-routing.cc Sun Aug 23 18:25:25 2009 +0800 +++ b/src/routing/global-routing/ipv4-global-routing.cc Sun Aug 23 18:25:46 2009 +0800 @@ -22,7 +22,9 @@ #include "ns3/net-device.h" #include "ns3/ipv4-route.h" #include "ns3/ipv4-routing-table-entry.h" +#include "ns3/boolean.h" #include "ipv4-global-routing.h" +#include NS_LOG_COMPONENT_DEFINE ("Ipv4GlobalRouting"); @@ -35,11 +37,17 @@ { static TypeId tid = TypeId ("ns3::Ipv4GlobalRouting") .SetParent