View | Details | Raw Unified | Return to bug 667
Collapse All | Expand All

(-)a/src/routing/global-routing/candidate-queue.cc (-21 / +63 lines)
 Lines 16-21    Link Here 
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"
 Lines 25-30    Link Here 
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
{
 Lines 54-70    Link Here 
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 *
 Lines 129-146    Link Here 
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
(-)a/src/routing/global-routing/candidate-queue.h (+12 lines)
 Lines 176-184    Link Here 
176
 * properly deal with deep copies.
176
 * properly deal with deep copies.
177
 */
177
 */
178
  CandidateQueue& operator= (CandidateQueue& sr);
178
  CandidateQueue& operator= (CandidateQueue& sr);
179
/**
180
 * \brief return true if v1 < v2
181
 *
182
 * SPFVertexes are added into the queue according to the ordering
183
 * defined by this method. If v1 should be popped before v2, this 
184
 * method return true; false otherwise
185
 *
186
 * \return True if v1 should be popped before v2; false otherwise
187
 */
188
  static bool CompareSPFVertex (const SPFVertex* v1, const SPFVertex* v2);
179
189
180
  typedef std::list<SPFVertex*> CandidateList_t;
190
  typedef std::list<SPFVertex*> CandidateList_t;
181
  CandidateList_t m_candidates;
191
  CandidateList_t m_candidates;
192
193
  friend std::ostream& operator<< (std::ostream& os, const CandidateQueue& q);
182
};
194
};
183
195
184
} // namespace ns3
196
} // namespace ns3
(-)a/src/routing/global-routing/global-route-manager-impl.cc (+1 lines)
 Lines 1172-1177    Link Here 
1172
// of the routers found in the Global Router Link Records and added tehm to 
1172
// of the routers found in the Global Router Link Records and added tehm to 
1173
// the candidate list.
1173
// the candidate list.
1174
//
1174
//
1175
      NS_LOG_LOGIC (candidate);
1175
      v = candidate.Pop ();
1176
      v = candidate.Pop ();
1176
      NS_LOG_LOGIC ("Popped vertex " << v->GetVertexId ());
1177
      NS_LOG_LOGIC ("Popped vertex " << v->GetVertexId ());
1177
//
1178
//

Return to bug 667