|
|
|---|
| 16 |
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
16 |
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
| 17 |
*/ |
17 |
*/ |
| 18 |
|
18 |
|
|
|
19 |
#include <algorithm> |
| 20 |
#include <iostream> |
| 19 |
#include "ns3/log.h" |
21 |
#include "ns3/log.h" |
| 20 |
#include "ns3/assert.h" |
22 |
#include "ns3/assert.h" |
| 21 |
#include "candidate-queue.h" |
23 |
#include "candidate-queue.h" |
|
|
|---|
| 25 |
|
27 |
|
| 26 |
namespace ns3 { |
28 |
namespace ns3 { |
| 27 |
|
29 |
|
|
|
30 |
std::ostream& |
| 31 |
operator<< (std::ostream& os, const SPFVertex::VertexType& t) |
| 32 |
{ |
| 33 |
switch (t) |
| 34 |
{ |
| 35 |
case SPFVertex::VertexRouter: os << "router"; break; |
| 36 |
case SPFVertex::VertexNetwork: os << "network"; break; |
| 37 |
default: os << "unknown"; break; |
| 38 |
}; |
| 39 |
return os; |
| 40 |
} |
| 41 |
|
| 42 |
std::ostream& |
| 43 |
operator<< (std::ostream& os, const CandidateQueue& q) |
| 44 |
{ |
| 45 |
typedef CandidateQueue::CandidateList_t List_t; |
| 46 |
typedef List_t::const_iterator CIter_t; |
| 47 |
const CandidateQueue::CandidateList_t& list = q.m_candidates; |
| 48 |
|
| 49 |
os << "*** CandidateQueue Begin (<id, distance, LSA-type>) ***" << std::endl; |
| 50 |
for (CIter_t iter = list.begin (); iter != list.end (); iter++) |
| 51 |
{ |
| 52 |
os << "<" |
| 53 |
<< (*iter)->GetVertexId () << ", " |
| 54 |
<< (*iter)->GetDistanceFromRoot () << ", " |
| 55 |
<< (*iter)->GetVertexType () << ">" << std::endl; |
| 56 |
} |
| 57 |
os << "*** CandidateQueue End ***"; |
| 58 |
return os; |
| 59 |
} |
| 60 |
|
| 28 |
CandidateQueue::CandidateQueue() |
61 |
CandidateQueue::CandidateQueue() |
| 29 |
: m_candidates () |
62 |
: m_candidates () |
| 30 |
{ |
63 |
{ |
|
|
|---|
| 54 |
{ |
87 |
{ |
| 55 |
NS_LOG_FUNCTION (this << vNew); |
88 |
NS_LOG_FUNCTION (this << vNew); |
| 56 |
|
89 |
|
| 57 |
CandidateList_t::iterator i = m_candidates.begin (); |
90 |
CandidateList_t::iterator i = std::upper_bound ( |
| 58 |
|
91 |
m_candidates.begin (), m_candidates.end (), vNew, |
| 59 |
for (; i != m_candidates.end (); i++) |
92 |
&CandidateQueue::CompareSPFVertex |
| 60 |
{ |
93 |
); |
| 61 |
SPFVertex *v = *i; |
94 |
m_candidates.insert (i, vNew); |
| 62 |
if (vNew->GetDistanceFromRoot () < v->GetDistanceFromRoot ()) |
|
|
| 63 |
{ |
| 64 |
break; |
| 65 |
} |
| 66 |
} |
| 67 |
m_candidates.insert(i, vNew); |
| 68 |
} |
95 |
} |
| 69 |
|
96 |
|
| 70 |
SPFVertex * |
97 |
SPFVertex * |
|
|
|---|
| 129 |
CandidateQueue::Reorder (void) |
156 |
CandidateQueue::Reorder (void) |
| 130 |
{ |
157 |
{ |
| 131 |
NS_LOG_FUNCTION_NOARGS (); |
158 |
NS_LOG_FUNCTION_NOARGS (); |
| 132 |
std::list<SPFVertex*> temp; |
|
|
| 133 |
|
159 |
|
| 134 |
while (!m_candidates.empty ()) { |
160 |
m_candidates.sort (&CandidateQueue::CompareSPFVertex); |
| 135 |
SPFVertex *v = m_candidates.front (); |
161 |
NS_LOG_LOGIC ("After reordering the CandidateQueue"); |
| 136 |
m_candidates.pop_front (); |
162 |
NS_LOG_LOGIC (*this); |
| 137 |
temp.push_back(v); |
163 |
} |
| 138 |
} |
|
|
| 139 |
|
164 |
|
| 140 |
while (!temp.empty ()) { |
165 |
/* |
| 141 |
Push (temp.front ()); |
166 |
* In this implementation, SPFVertex follows the ordering where |
| 142 |
temp.pop_front (); |
167 |
* a vertex is ranked first if its GetDistanceFromRoot () is smaller; |
| 143 |
} |
168 |
* In case a tie, NetworkLSA is always ranked before RouterLSA. |
|
|
169 |
* |
| 170 |
* This ordering is necessary for implementing ECMP |
| 171 |
*/ |
| 172 |
bool |
| 173 |
CandidateQueue::CompareSPFVertex (const SPFVertex* v1, const SPFVertex* v2) |
| 174 |
{ |
| 175 |
NS_LOG_FUNCTION (&v1 << &v2); |
| 176 |
|
| 177 |
bool result = false; |
| 178 |
if (v1->GetDistanceFromRoot () < v2->GetDistanceFromRoot ()) |
| 179 |
result = true; |
| 180 |
else if (v1->GetDistanceFromRoot () == v2->GetDistanceFromRoot ()) |
| 181 |
if (v1->GetVertexType () == SPFVertex::VertexNetwork && |
| 182 |
v2->GetVertexType () == SPFVertex::VertexRouter) |
| 183 |
result = true; |
| 184 |
|
| 185 |
return result; |
| 144 |
} |
186 |
} |
| 145 |
|
187 |
|
| 146 |
} // namespace ns3 |
188 |
} // namespace ns3 |