# HG changeset patch # User Wilson Thong # Date 1260862094 28800 # Node ID 7bf468a1e874ac39fc3d675949bb5f1312900784 # Parent 316957e1932f931230c7617955908a609d6f2aca bug 667: Add equal-cost multipath routing (ECMP) to IPv4 global routing diff -r 316957e1932f -r 7bf468a1e874 src/routing/global-routing/candidate-queue.cc --- a/src/routing/global-routing/candidate-queue.cc Sun Dec 13 22:11:05 2009 -0800 +++ b/src/routing/global-routing/candidate-queue.cc Mon Dec 14 23:28:14 2009 -0800 @@ -16,6 +16,8 @@ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ +#include +#include #include "ns3/log.h" #include "ns3/assert.h" #include "candidate-queue.h" @@ -25,6 +27,37 @@ namespace ns3 { +std::ostream& +operator<< (std::ostream& os, const SPFVertex::VertexType& t) +{ + switch (t) + { + case SPFVertex::VertexRouter: os << "router"; break; + case SPFVertex::VertexNetwork: os << "network"; break; + default: os << "unknown"; break; + }; + return os; +} + +std::ostream& +operator<< (std::ostream& os, const CandidateQueue& q) +{ + typedef CandidateQueue::CandidateList_t List_t; + typedef List_t::const_iterator CIter_t; + const CandidateQueue::CandidateList_t& list = q.m_candidates; + + os << "*** CandidateQueue Begin () ***" << std::endl; + for (CIter_t iter = list.begin (); iter != list.end (); iter++) + { + os << "<" + << (*iter)->GetVertexId () << ", " + << (*iter)->GetDistanceFromRoot () << ", " + << (*iter)->GetVertexType () << ">" << std::endl; + } + os << "*** CandidateQueue End ***"; + return os; +} + CandidateQueue::CandidateQueue() : m_candidates () { @@ -54,17 +87,11 @@ { NS_LOG_FUNCTION (this << vNew); - CandidateList_t::iterator i = m_candidates.begin (); - - for (; i != m_candidates.end (); i++) - { - SPFVertex *v = *i; - if (vNew->GetDistanceFromRoot () < v->GetDistanceFromRoot ()) - { - break; - } - } - m_candidates.insert(i, vNew); + CandidateList_t::iterator i = std::upper_bound ( + m_candidates.begin (), m_candidates.end (), vNew, + &CandidateQueue::CompareSPFVertex + ); + m_candidates.insert (i, vNew); } SPFVertex * @@ -129,18 +156,38 @@ CandidateQueue::Reorder (void) { NS_LOG_FUNCTION_NOARGS (); - std::list temp; - while (!m_candidates.empty ()) { - SPFVertex *v = m_candidates.front (); - m_candidates.pop_front (); - temp.push_back(v); - } + m_candidates.sort (&CandidateQueue::CompareSPFVertex); + NS_LOG_LOGIC ("After reordering the CandidateQueue"); + NS_LOG_LOGIC (*this); +} - while (!temp.empty ()) { - Push (temp.front ()); - temp.pop_front (); - } +/* + * In this implementation, SPFVertex 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 +CandidateQueue::CompareSPFVertex (const SPFVertex* v1, const SPFVertex* 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 () == SPFVertex::VertexNetwork + && v2->GetVertexType () == SPFVertex::VertexRouter) + { + result = true; + } + } + return result; } } // namespace ns3 diff -r 316957e1932f -r 7bf468a1e874 src/routing/global-routing/candidate-queue.h --- a/src/routing/global-routing/candidate-queue.h Sun Dec 13 22:11:05 2009 -0800 +++ b/src/routing/global-routing/candidate-queue.h Mon Dec 14 23:28:14 2009 -0800 @@ -178,9 +178,21 @@ * \param sr object to assign */ CandidateQueue& operator= (CandidateQueue& sr); +/** + * \brief return true if v1 < v2 + * + * SPFVertexes 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 CompareSPFVertex (const SPFVertex* v1, const SPFVertex* v2); typedef std::list CandidateList_t; CandidateList_t m_candidates; + + friend std::ostream& operator<< (std::ostream& os, const CandidateQueue& q); }; } // namespace ns3 diff -r 316957e1932f -r 7bf468a1e874 src/routing/global-routing/global-route-manager-impl.cc --- a/src/routing/global-routing/global-route-manager-impl.cc Sun Dec 13 22:11:05 2009 -0800 +++ b/src/routing/global-routing/global-route-manager-impl.cc Mon Dec 14 23:28:14 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,34 @@ namespace ns3 { +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 +84,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 +97,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 +117,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++) { - SPFVertex *p = *i; + // 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 (); + 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 + 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 +219,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; } @@ -187,17 +270,128 @@ 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"); + 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 (); @@ -376,7 +570,7 @@ GlobalRouteManagerImpl::GlobalRouteManagerImpl () : - m_spfroot (0) + m_spfroot (0) { NS_LOG_FUNCTION_NOARGS (); m_lsdb = new GlobalRouteManagerLSDB (); @@ -536,6 +730,7 @@ // // Walk the list of nodes in the system. // + NS_LOG_INFO ("About to start SPF calculation"); NodeList::Iterator listEnd = NodeList::End (); for (NodeList::Iterator i = NodeList::Begin (); i != listEnd; i++) { @@ -555,6 +750,7 @@ SPFCalculate (rtr->GetRouterId ()); } } + NS_LOG_INFO ("Finished SPF calculation"); } // @@ -688,15 +884,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); @@ -710,6 +905,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) { @@ -720,22 +918,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 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::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 @@ -745,7 +975,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 @@ -753,7 +983,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 } @@ -847,20 +1077,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 @@ -870,14 +1101,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; } @@ -901,18 +1134,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 @@ -930,8 +1163,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. @@ -1210,6 +1442,7 @@ // 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 ()); // @@ -1228,8 +1461,7 @@ // // 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. // // RFC2328 16.1. (4). // @@ -1569,12 +1801,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 @@ -1596,20 +1822,28 @@ } Ptr gr = router->GetRoutingProtocol (); NS_ASSERT (gr); - if (v->GetOutgoingInterfaceId () >= 0) + // 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++) { - 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"); + 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 @@ -1802,11 +2036,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 @@ -1827,22 +2056,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. @@ -1931,21 +2169,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); + } } } } @@ -1960,13 +2207,18 @@ // 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); + } } } // namespace ns3 diff -r 316957e1932f -r 7bf468a1e874 src/routing/global-routing/global-route-manager-impl.h --- a/src/routing/global-routing/global-route-manager-impl.h Sun Dec 13 22:11:05 2009 -0800 +++ b/src/routing/global-routing/global-route-manager-impl.h Mon Dec 14 23:28:14 2009 -0800 @@ -256,6 +256,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 @@ -295,9 +297,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 @@ -337,9 +341,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 @@ -380,9 +386,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 @@ -423,7 +431,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 outgoing 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 outgoing 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 outgoing-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 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 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" @@ -441,10 +578,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" @@ -466,6 +604,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. @@ -574,8 +720,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; @@ -590,6 +739,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 316957e1932f -r 7bf468a1e874 src/routing/global-routing/ipv4-global-routing.cc --- a/src/routing/global-routing/ipv4-global-routing.cc Sun Dec 13 22:11:05 2009 -0800 +++ b/src/routing/global-routing/ipv4-global-routing.cc Mon Dec 14 23:28:14 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