|
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 |