Changed CandidateQueue class so that NetworkLSA is always ordered in front of RouterLSA. Besides, some manuipliation on std::list objects are replaced using STL diff -r 0950db321270 src/routing/global-routing/candidate-queue.cc --- a/src/routing/global-routing/candidate-queue.cc Sat Aug 08 11:41:38 2009 +0800 +++ b/src/routing/global-routing/candidate-queue.cc Sat Aug 08 20:34:51 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,33 @@ 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 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 0950db321270 src/routing/global-routing/candidate-queue.h --- a/src/routing/global-routing/candidate-queue.h Sat Aug 08 11:41:38 2009 +0800 +++ b/src/routing/global-routing/candidate-queue.h Sat Aug 08 20:34:51 2009 +0800 @@ -176,9 +176,21 @@ * properly deal with deep copies. */ 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 0950db321270 src/routing/global-routing/global-route-manager-impl.cc --- a/src/routing/global-routing/global-route-manager-impl.cc Sat Aug 08 11:41:38 2009 +0800 +++ b/src/routing/global-routing/global-route-manager-impl.cc Sat Aug 08 20:34:51 2009 +0800 @@ -1172,6 +1172,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 ()); //