|
25 |
#include <utility> |
25 |
#include <utility> |
26 |
#include <vector> |
26 |
#include <vector> |
27 |
#include <queue> |
27 |
#include <queue> |
|
|
28 |
#include <algorithm> |
29 |
#include <iostream> |
28 |
#include "ns3/assert.h" |
30 |
#include "ns3/assert.h" |
29 |
#include "ns3/fatal-error.h" |
31 |
#include "ns3/fatal-error.h" |
30 |
#include "ns3/log.h" |
32 |
#include "ns3/log.h" |
|
41 |
|
43 |
|
42 |
namespace ns3 { |
44 |
namespace ns3 { |
43 |
|
45 |
|
|
|
46 |
//std::ostream& |
47 |
//operator<< (std::ostream& os, const SPFVertex::ListOfIf_t& ifs) |
48 |
//{ |
49 |
// os << "{"; |
50 |
// for (SPFVertex::ListOfIf_t::const_iterator iter = ifs.begin ();;) |
51 |
// { |
52 |
// os << *iter; |
53 |
// if (++iter != ifs.end ()) |
54 |
// os << ", "; |
55 |
// else |
56 |
// break; |
57 |
// } |
58 |
// os << "}"; |
59 |
// return os; |
60 |
//} |
61 |
// |
62 |
//std::ostream& |
63 |
//operator<< (std::ostream& os, const SPFVertex::ListOfAddr_t& addrs) |
64 |
//{ |
65 |
// os << "{"; |
66 |
// for (SPFVertex::ListOfAddr_t::const_iterator iter = addrs.begin ();;) |
67 |
// { |
68 |
// os << *iter; |
69 |
// if (++iter != addrs.end ()) |
70 |
// os << ", "; |
71 |
// else |
72 |
// break; |
73 |
// } |
74 |
// os << "}"; |
75 |
// return os; |
76 |
//} |
77 |
|
78 |
std::ostream& |
79 |
operator<< (std::ostream& os, const SPFVertex::NodeExit_t& exit) |
80 |
{ |
81 |
os << "(" << exit.first << " ," << exit.second << ")"; |
82 |
return os; |
83 |
} |
84 |
|
85 |
std::ostream& |
86 |
operator<< (std::ostream& os, const SPFVertex::ListOfSPFVertex_t& vs) |
87 |
{ |
88 |
typedef SPFVertex::ListOfSPFVertex_t::const_iterator CIter_t; |
89 |
os << "{"; |
90 |
for (CIter_t iter = vs.begin (); iter != vs.end ();) |
91 |
{ |
92 |
os << (*iter)->m_vertexId; |
93 |
if (++iter != vs.end ()) |
94 |
os << ", "; |
95 |
else |
96 |
break; |
97 |
} |
98 |
os << "}"; |
99 |
return os; |
100 |
} |
101 |
|
44 |
// --------------------------------------------------------------------------- |
102 |
// --------------------------------------------------------------------------- |
45 |
// |
103 |
// |
46 |
// SPFVertex Implementation |
104 |
// SPFVertex Implementation |
|
54 |
m_distanceFromRoot (SPF_INFINITY), |
112 |
m_distanceFromRoot (SPF_INFINITY), |
55 |
m_rootOif (SPF_INFINITY), |
113 |
m_rootOif (SPF_INFINITY), |
56 |
m_nextHop ("0.0.0.0"), |
114 |
m_nextHop ("0.0.0.0"), |
57 |
m_parent (0), |
115 |
m_parents (), |
58 |
m_children (), |
116 |
m_children (), |
59 |
m_vertexProcessed (false) |
117 |
m_vertexProcessed (false) |
60 |
{ |
118 |
{ |
|
67 |
m_distanceFromRoot (SPF_INFINITY), |
125 |
m_distanceFromRoot (SPF_INFINITY), |
68 |
m_rootOif (SPF_INFINITY), |
126 |
m_rootOif (SPF_INFINITY), |
69 |
m_nextHop ("0.0.0.0"), |
127 |
m_nextHop ("0.0.0.0"), |
70 |
m_parent (0), |
128 |
m_parents (), |
71 |
m_children (), |
129 |
m_children (), |
72 |
m_vertexProcessed (false) |
130 |
m_vertexProcessed (false) |
73 |
{ |
131 |
{ |
74 |
NS_LOG_FUNCTION_NOARGS (); |
132 |
NS_LOG_FUNCTION_NOARGS (); |
|
|
133 |
|
75 |
if (lsa->GetLSType () == GlobalRoutingLSA::RouterLSA) |
134 |
if (lsa->GetLSType () == GlobalRoutingLSA::RouterLSA) |
76 |
{ |
135 |
{ |
77 |
NS_LOG_LOGIC ("Setting m_vertexType to VertexRouter"); |
136 |
NS_LOG_LOGIC ("Setting m_vertexType to VertexRouter"); |
|
86 |
|
145 |
|
87 |
SPFVertex::~SPFVertex () |
146 |
SPFVertex::~SPFVertex () |
88 |
{ |
147 |
{ |
89 |
NS_LOG_FUNCTION_NOARGS (); |
148 |
NS_LOG_FUNCTION (m_vertexId); |
90 |
for ( ListOfSPFVertex_t::iterator i = m_children.begin (); |
149 |
|
91 |
i != m_children.end (); |
150 |
NS_LOG_LOGIC ("Children vertices - " << m_children); |
92 |
i++) |
151 |
NS_LOG_LOGIC ("Parent verteices - " << m_parents); |
|
|
152 |
|
153 |
// find this node from all its parents and remove the entry of this node |
154 |
// from all its parents |
155 |
for (ListOfSPFVertex_t::iterator piter = m_parents.begin (); |
156 |
piter != m_parents.end (); |
157 |
piter++) |
158 |
{ |
159 |
// remove the current vertex from its parent'ss children list. Check |
160 |
// if the size of the list is reduced, or the child<->parent relation |
161 |
// is not bidirectional |
162 |
uint32_t orgCount = (*piter)->m_children.size (); |
163 |
(*piter)->m_children.remove (this); |
164 |
uint32_t newCount = (*piter)->m_children.size (); |
165 |
NS_ASSERT_MSG (orgCount > newCount, "Unable to find the current vertex from its parents --- impossible!"); |
166 |
} |
167 |
|
168 |
// delete children |
169 |
while (m_children.size () > 0) |
93 |
{ |
170 |
{ |
94 |
SPFVertex *p = *i; |
171 |
// pop out children one by one. Some children may disappered |
|
|
172 |
// when deleting some other children in the list. As a result, |
173 |
// it is necessary to use pop to walk through all children, intead |
174 |
// of suing iterator. |
175 |
// |
176 |
// Note that m_children.pop_front () is not necessary as this |
177 |
// p is removed from the children list when p is deleted |
178 |
SPFVertex* p = m_children.front (); |
179 |
// 'p' == 0, this child is already deleted by its other parent |
180 |
if (p == 0) continue; |
181 |
NS_LOG_LOGIC ("Parent vertex-" << m_vertexId << " deleting its child vertex-" << p->GetVertexId ()); |
95 |
delete p; |
182 |
delete p; |
96 |
p = 0; |
183 |
p = 0; |
97 |
*i = 0; |
|
|
98 |
} |
184 |
} |
99 |
m_children.clear (); |
185 |
m_children.clear (); |
|
|
186 |
// delete parents |
187 |
m_parents.clear (); |
188 |
// delete root exit direction |
189 |
m_ecmpRootExits.clear (); |
190 |
|
191 |
NS_LOG_LOGIC ("Vertex-" << m_vertexId << " completed deleted"); |
100 |
} |
192 |
} |
101 |
|
193 |
|
102 |
void |
194 |
void |
|
155 |
return m_distanceFromRoot; |
247 |
return m_distanceFromRoot; |
156 |
} |
248 |
} |
157 |
|
249 |
|
158 |
void |
250 |
void |
159 |
SPFVertex::SetOutgoingInterfaceId (int32_t id) |
251 |
SPFVertex::SetOutgoingInterfaceId (int32_t id) |
160 |
{ |
252 |
{ |
161 |
NS_LOG_FUNCTION (id); |
253 |
NS_LOG_FUNCTION (id); |
|
|
254 |
|
255 |
// always maintain only one output interface index when using setter/getter methods |
162 |
m_rootOif = id; |
256 |
m_rootOif = id; |
163 |
} |
257 |
} |
164 |
|
258 |
|
165 |
uint32_t |
259 |
uint32_t |
166 |
SPFVertex::GetOutgoingInterfaceId (void) const |
260 |
SPFVertex::GetOutgoingInterfaceId (void) const |
167 |
{ |
261 |
{ |
168 |
NS_LOG_FUNCTION_NOARGS (); |
262 |
NS_LOG_FUNCTION_NOARGS (); |
169 |
return m_rootOif; |
263 |
return m_rootOif; |
170 |
} |
264 |
} |
171 |
|
265 |
|
|
|
266 |
//void |
267 |
//SPFVertex::MergeOutgoingInterfaceId (const SPFVertex* v) |
268 |
//{ |
269 |
// NS_LOG_FUNCTION (v); |
270 |
// |
271 |
// NS_LOG_LOGIC ("Before merge, list of root out-going interfaces = " << m_rootOif); |
272 |
// // combine the two lists first, and then remove any duplicated after |
273 |
// m_rootOif.insert (m_rootOif.end (), |
274 |
// v->m_rootOif.begin (), v->m_rootOif.end ()); |
275 |
// // remove duplication |
276 |
// m_rootOif.sort (); |
277 |
// m_rootOif.unique (); |
278 |
// NS_LOG_LOGIC ("After merge, list of root out-going interfaces = " << m_rootOif); |
279 |
//} |
280 |
|
172 |
void |
281 |
void |
173 |
SPFVertex::SetNextHop (Ipv4Address nextHop) |
282 |
SPFVertex::SetNextHop (Ipv4Address nextHop) |
174 |
{ |
283 |
{ |
175 |
NS_LOG_FUNCTION (nextHop); |
284 |
NS_LOG_FUNCTION (nextHop); |
|
|
285 |
|
286 |
// always maintain only one nexthop when using setter/getter methods |
176 |
m_nextHop = nextHop; |
287 |
m_nextHop = nextHop; |
177 |
} |
288 |
} |
178 |
|
289 |
|
|
183 |
return m_nextHop; |
294 |
return m_nextHop; |
184 |
} |
295 |
} |
185 |
|
296 |
|
|
|
297 |
//void |
298 |
//SPFVertex::MergeNextHop (const SPFVertex* v) |
299 |
//{ |
300 |
// NS_LOG_FUNCTION (v); |
301 |
// |
302 |
// NS_LOG_LOGIC ("Before merge, list of next hops = " << m_nextHop); |
303 |
// // combine the two lists first, and then remove any duplicated after |
304 |
// m_nextHop.insert (m_nextHop.end (), |
305 |
// v->m_nextHop.begin (), v->m_nextHop.end ()); |
306 |
// // remove duplication |
307 |
// m_nextHop.sort (); |
308 |
// m_nextHop.unique (); |
309 |
// NS_LOG_LOGIC ("After merge, list of next hops = " << m_nextHop); |
310 |
//} |
311 |
|
186 |
void |
312 |
void |
187 |
SPFVertex::SetParent (SPFVertex* parent) |
313 |
SPFVertex::SetParent (SPFVertex* parent) |
188 |
{ |
314 |
{ |
189 |
NS_LOG_FUNCTION (parent); |
315 |
NS_LOG_FUNCTION (parent); |
190 |
m_parent = parent; |
316 |
|
|
|
317 |
// always maintain only one parent when using setter/getter methods |
318 |
m_parents.clear (); |
319 |
m_parents.push_back (parent); |
191 |
} |
320 |
} |
192 |
|
321 |
|
193 |
SPFVertex* |
322 |
SPFVertex* |
194 |
SPFVertex::GetParent (void) const |
323 |
SPFVertex::GetParent (uint32_t i) const |
195 |
{ |
324 |
{ |
196 |
NS_LOG_FUNCTION_NOARGS (); |
325 |
NS_LOG_FUNCTION_NOARGS (); |
197 |
return m_parent; |
326 |
|
|
|
327 |
// If the index i is out-of-range, return 0 and do nothing |
328 |
if (m_parents.size () <= i) |
329 |
{ |
330 |
NS_LOG_LOGIC ("Index to SPFVertex's parent is out-of-range."); |
331 |
return 0; |
332 |
} |
333 |
ListOfSPFVertex_t::const_iterator iter = m_parents.begin (); |
334 |
while (i-- > 0) {iter++;} |
335 |
return *iter; |
198 |
} |
336 |
} |
199 |
|
337 |
|
200 |
uint32_t |
338 |
void |
|
|
339 |
SPFVertex::MergeParent (const SPFVertex* v) |
340 |
{ |
341 |
NS_LOG_FUNCTION (v); |
342 |
|
343 |
NS_LOG_LOGIC ("Before merge, list of parents = " << m_parents); |
344 |
// combine the two lists first, and then remove any duplicated after |
345 |
m_parents.insert (m_parents.end (), |
346 |
v->m_parents.begin (), v->m_parents.end ()); |
347 |
// remove duplication |
348 |
m_parents.sort (); |
349 |
m_parents.unique (); |
350 |
NS_LOG_LOGIC ("After merge, list of parents = " << m_parents); |
351 |
} |
352 |
|
353 |
void |
354 |
SPFVertex::SetRootExitDirection (Ipv4Address nextHop, int32_t id) |
355 |
{ |
356 |
NS_LOG_FUNCTION (nextHop << id); |
357 |
|
358 |
// always maintain only one root's exit |
359 |
m_ecmpRootExits.clear (); |
360 |
m_ecmpRootExits.push_back (NodeExit_t (nextHop, id)); |
361 |
// update the following in order to be backward compatitable with |
362 |
// GetNextHop and GetOutgoingInterface methods |
363 |
m_nextHop = nextHop; |
364 |
m_rootOif = id; |
365 |
} |
366 |
|
367 |
void |
368 |
SPFVertex::SetRootExitDirection (SPFVertex::NodeExit_t exit) |
369 |
{ |
370 |
NS_LOG_FUNCTION (exit); |
371 |
SetRootExitDirection (exit.first, exit.second); |
372 |
} |
373 |
|
374 |
SPFVertex::NodeExit_t |
375 |
SPFVertex::GetRootExitDirection (uint32_t i) const |
376 |
{ |
377 |
NS_LOG_FUNCTION (i); |
378 |
typedef ListOfNodeExit_t::const_iterator CIter_t; |
379 |
|
380 |
NS_ASSERT_MSG (i < m_ecmpRootExits.size (), "Index out-of-range when accessing SPFVertex::m_ecmpRootExits!"); |
381 |
CIter_t iter = m_ecmpRootExits.begin (); |
382 |
while (i-- > 0) {iter++;} |
383 |
|
384 |
return *iter; |
385 |
} |
386 |
|
387 |
SPFVertex::NodeExit_t |
388 |
SPFVertex::GetRootExitDirection () const |
389 |
{ |
390 |
NS_LOG_FUNCTION_NOARGS (); |
391 |
|
392 |
NS_ASSERT_MSG (m_ecmpRootExits.size () <= 1, "Assumed there is at most one exit from the root to this vertex, but this assumption is violated!"); |
393 |
return GetRootExitDirection (0); |
394 |
} |
395 |
|
396 |
void |
397 |
SPFVertex::MergeRootExitDirections (const SPFVertex* vertex) |
398 |
{ |
399 |
NS_LOG_FUNCTION (vertex); |
400 |
|
401 |
// obtain the external list of exit directions |
402 |
// |
403 |
// Append the external list into 'this' and remove duplication afterward |
404 |
const ListOfNodeExit_t& extList = vertex->m_ecmpRootExits; |
405 |
m_ecmpRootExits.insert (m_ecmpRootExits.end (), |
406 |
extList.begin(), extList.end ()); |
407 |
m_ecmpRootExits.sort (); |
408 |
m_ecmpRootExits.unique (); |
409 |
} |
410 |
|
411 |
void |
412 |
SPFVertex::InheritAllRootExitDirections (const SPFVertex* vertex) |
413 |
{ |
414 |
NS_LOG_FUNCTION (vertex); |
415 |
|
416 |
// discard all exit direction currently assoicated with this vertex, |
417 |
// and copy all the exit directions from the given vertex |
418 |
if (m_ecmpRootExits.size () > 0) |
419 |
NS_LOG_WARN ("x root exit directions in this vertex are going to be discarded"); |
420 |
m_ecmpRootExits.clear (); |
421 |
m_ecmpRootExits.insert (m_ecmpRootExits.end (), |
422 |
vertex->m_ecmpRootExits.begin (), vertex->m_ecmpRootExits.end ()); |
423 |
} |
424 |
|
425 |
uint32_t |
426 |
SPFVertex::GetNRootExitDirections () const |
427 |
{ |
428 |
NS_LOG_FUNCTION_NOARGS (); |
429 |
return m_ecmpRootExits.size (); |
430 |
} |
431 |
|
432 |
uint32_t |
201 |
SPFVertex::GetNChildren (void) const |
433 |
SPFVertex::GetNChildren (void) const |
202 |
{ |
434 |
{ |
203 |
NS_LOG_FUNCTION_NOARGS (); |
435 |
NS_LOG_FUNCTION_NOARGS (); |
|
341 |
|
573 |
|
342 |
GlobalRouteManagerImpl::GlobalRouteManagerImpl () |
574 |
GlobalRouteManagerImpl::GlobalRouteManagerImpl () |
343 |
: |
575 |
: |
344 |
m_spfroot (0) |
576 |
m_spfroot (0) |
345 |
{ |
577 |
{ |
346 |
NS_LOG_FUNCTION_NOARGS (); |
578 |
NS_LOG_FUNCTION_NOARGS (); |
347 |
m_lsdb = new GlobalRouteManagerLSDB (); |
579 |
m_lsdb = new GlobalRouteManagerLSDB (); |
|
649 |
// Is there already vertex w in candidate list? |
881 |
// Is there already vertex w in candidate list? |
650 |
if (w_lsa->GetStatus () == GlobalRoutingLSA::LSA_SPF_NOT_EXPLORED) |
882 |
if (w_lsa->GetStatus () == GlobalRoutingLSA::LSA_SPF_NOT_EXPLORED) |
651 |
{ |
883 |
{ |
652 |
|
|
|
653 |
// prepare vertex w |
654 |
w = new SPFVertex (w_lsa); |
655 |
// Calculate nexthop to w |
884 |
// Calculate nexthop to w |
656 |
// We need to figure out how to actually get to the new router represented |
885 |
// We need to figure out how to actually get to the new router represented |
657 |
// by <w>. This will (among other things) find the next hop address to send |
886 |
// by <w>. This will (among other things) find the next hop address to send |
658 |
// packets destined for this network to, and also find the outbound interface |
887 |
// packets destined for this network to, and also find the outbound interface |
659 |
// used to forward the packets. |
888 |
// used to forward the packets. |
660 |
// |
889 |
|
|
|
890 |
// prepare vertex w |
891 |
w = new SPFVertex (w_lsa); |
661 |
if (SPFNexthopCalculation (v, w, l, distance)) |
892 |
if (SPFNexthopCalculation (v, w, l, distance)) |
662 |
{ |
893 |
{ |
663 |
w_lsa->SetStatus (GlobalRoutingLSA::LSA_SPF_CANDIDATE); |
894 |
w_lsa->SetStatus (GlobalRoutingLSA::LSA_SPF_CANDIDATE); |
|
671 |
v->GetVertexId () << ", distance: " << |
902 |
v->GetVertexId () << ", distance: " << |
672 |
w->GetDistanceFromRoot ()); |
903 |
w->GetDistanceFromRoot ()); |
673 |
} |
904 |
} |
|
|
905 |
else |
906 |
NS_ASSERT_MSG (0, "SPFNexthopCalculation never " |
907 |
<< "return false, but it does now!"); |
674 |
} |
908 |
} |
675 |
else if (w_lsa->GetStatus () == GlobalRoutingLSA::LSA_SPF_CANDIDATE) |
909 |
else if (w_lsa->GetStatus () == GlobalRoutingLSA::LSA_SPF_CANDIDATE) |
676 |
{ |
910 |
{ |
|
681 |
// |
915 |
// |
682 |
// So, locate the vertex in the candidate queue and take a look at the |
916 |
// So, locate the vertex in the candidate queue and take a look at the |
683 |
// distance. |
917 |
// distance. |
684 |
w = candidate.Find (w_lsa->GetLinkStateId ()); |
918 |
|
685 |
if (w->GetDistanceFromRoot () < distance) |
919 |
/* (quagga-0.98.6) W is already on the candidate list; call it cw. |
|
|
920 |
* Compare the previously calculated cost (cw->distance) |
921 |
* with the cost we just determined (w->distance) to see |
922 |
* if we've found a shorter path. |
923 |
*/ |
924 |
SPFVertex* cw; |
925 |
cw = candidate.Find (w_lsa->GetLinkStateId ()); |
926 |
if (cw->GetDistanceFromRoot () < distance) |
686 |
{ |
927 |
{ |
687 |
// |
928 |
// |
688 |
// This is not a shorter path, so don't do anything. |
929 |
// This is not a shorter path, so don't do anything. |
689 |
// |
930 |
// |
690 |
continue; |
931 |
continue; |
691 |
} |
932 |
} |
692 |
else if (w->GetDistanceFromRoot () == distance) |
933 |
else if (cw->GetDistanceFromRoot () == distance) |
693 |
{ |
934 |
{ |
694 |
// |
935 |
// |
695 |
// This path is one with an equal cost. Do nothing for now -- we're not doing |
936 |
// This path is one with an equal cost. |
696 |
// equal-cost multipath cases yet. |
|
|
697 |
// |
937 |
// |
|
|
938 |
NS_LOG_LOGIC ("Equal cost multiple paths found."); |
939 |
|
940 |
// At this point, there are two instances 'w' and 'cw' of the |
941 |
// same vertex, the vertex that is currently being considered |
942 |
// for adding into the shortest path tree. 'w' is the instance |
943 |
// as seen from the root via vertex 'v', and 'cw' is the instance |
944 |
// as seen from the root via some other vertices other than 'v'. |
945 |
// These two instances are being merged in the following codes. |
946 |
// In particular, the parent nodes, the next hops, and the root's |
947 |
// output interfaces of the two instances are being merged. |
948 |
// |
949 |
// Note that this is functionally equivelent to calling |
950 |
// ospf_nexthop_merge (cw->nexthop, w->nexthop) in quagga-0.98.6 |
951 |
// (ospf_spf.c::859), althrough the detail implemenation |
952 |
// is very different from quagga (blame ns3::GlobalRouteManagerImpl) |
953 |
|
954 |
// prepare vertex w |
955 |
w = new SPFVertex (w_lsa); |
956 |
SPFNexthopCalculation (v, w, l, distance); |
957 |
cw->MergeRootExitDirections (w); |
958 |
cw->MergeParent (w); |
959 |
// SPFVertexAddParent (w) is necessary as the destructor of |
960 |
// SPFVertex checks if the vertex and its parent is linked |
961 |
// bidirectionally |
962 |
SPFVertexAddParent (w); |
963 |
delete w; |
698 |
} |
964 |
} |
699 |
else |
965 |
else // cw->GetDistanceFromRoot () > w->GetDistanceFromRoot () |
700 |
{ |
966 |
{ |
701 |
// |
967 |
// |
702 |
// this path represents a new, lower-cost path to <w> (the vertex we found in |
968 |
// this path represents a new, lower-cost path to <w> (the vertex we found in |
|
706 |
// N.B. the nexthop_calculation is conditional, if it finds a valid nexthop |
972 |
// N.B. the nexthop_calculation is conditional, if it finds a valid nexthop |
707 |
// it will call spf_add_parents, which will flush the old parents |
973 |
// it will call spf_add_parents, which will flush the old parents |
708 |
// |
974 |
// |
709 |
if (SPFNexthopCalculation (v, w, l, distance)) |
975 |
if (SPFNexthopCalculation (v, cw, l, distance)) |
710 |
{ |
976 |
{ |
711 |
// |
977 |
// |
712 |
// If we've changed the cost to get to the vertex represented by <w>, we |
978 |
// If we've changed the cost to get to the vertex represented by <w>, we |
|
714 |
// |
980 |
// |
715 |
candidate.Reorder (); |
981 |
candidate.Reorder (); |
716 |
} |
982 |
} |
717 |
} // new lower cost path found |
983 |
} // new lower cost path found |
718 |
} // end W is already on the candidate list |
984 |
} // end W is already on the candidate list |
719 |
} // end loop over the links in V's LSA |
985 |
} // end loop over the links in V's LSA |
720 |
} |
986 |
} |
|
808 |
// from the root node to the host represented by vertex <w>, you have to send |
1074 |
// from the root node to the host represented by vertex <w>, you have to send |
809 |
// the packet to the next hop address specified in w->m_nextHop. |
1075 |
// the packet to the next hop address specified in w->m_nextHop. |
810 |
// |
1076 |
// |
811 |
w->SetNextHop (linkRemote->GetLinkData ()); |
1077 |
Ipv4Address nextHop = linkRemote->GetLinkData (); |
812 |
// |
1078 |
// |
813 |
// Now find the outgoing interface corresponding to the point to point link |
1079 |
// Now find the outgoing interface corresponding to the point to point link |
814 |
// from the perspective of <v> -- remember that <l> is the link "from" |
1080 |
// from the perspective of <v> -- remember that <l> is the link "from" |
815 |
// <v> "to" <w>. |
1081 |
// <v> "to" <w>. |
816 |
// |
1082 |
// |
817 |
w->SetOutgoingInterfaceId ( |
1083 |
uint32_t outIf = FindOutgoingInterfaceId (l->GetLinkData ()); |
818 |
FindOutgoingInterfaceId (l->GetLinkData ())); |
1084 |
|
|
|
1085 |
w->SetRootExitDirection (nextHop, outIf); |
819 |
w->SetDistanceFromRoot (distance); |
1086 |
w->SetDistanceFromRoot (distance); |
820 |
w->SetParent (v); |
1087 |
w->SetParent (v); |
821 |
NS_LOG_LOGIC ("Next hop from " << |
1088 |
NS_LOG_LOGIC ("Next hop from " << |
822 |
v->GetVertexId () << " to " << w->GetVertexId () << |
1089 |
v->GetVertexId () << " to " << w->GetVertexId () << |
823 |
" goes through next hop " << w->GetNextHop () << |
1090 |
" goes through next hop " << nextHop << |
824 |
" via outgoing interface " << w->GetOutgoingInterfaceId () << |
1091 |
" via outgoing interface " << outIf << |
825 |
" with distance " << distance); |
1092 |
" with distance " << distance); |
826 |
} // end W is a router vertes |
1093 |
} // end W is a router vertes |
827 |
else |
1094 |
else |
|
831 |
GlobalRoutingLSA* w_lsa = w->GetLSA (); |
1098 |
GlobalRoutingLSA* w_lsa = w->GetLSA (); |
832 |
NS_ASSERT (w_lsa->GetLSType () == GlobalRoutingLSA::NetworkLSA); |
1099 |
NS_ASSERT (w_lsa->GetLSType () == GlobalRoutingLSA::NetworkLSA); |
833 |
// Find outgoing interface ID for this network |
1100 |
// Find outgoing interface ID for this network |
834 |
w->SetOutgoingInterfaceId ( |
1101 |
uint32_t outIf = FindOutgoingInterfaceId (w_lsa->GetLinkStateId (), |
835 |
FindOutgoingInterfaceId (w_lsa->GetLinkStateId (), |
1102 |
w_lsa->GetNetworkLSANetworkMask () ); |
836 |
w_lsa->GetNetworkLSANetworkMask () )); |
1103 |
// Set the next hop to 0.0.0.0 meaning "not exist" |
|
|
1104 |
Ipv4Address nextHop = Ipv4Address::GetZero (); |
1105 |
w->SetRootExitDirection (nextHop, outIf); |
837 |
w->SetDistanceFromRoot (distance); |
1106 |
w->SetDistanceFromRoot (distance); |
838 |
w->SetParent (v); |
1107 |
w->SetParent (v); |
839 |
NS_LOG_LOGIC ("Next hop from " << |
1108 |
NS_LOG_LOGIC ("Next hop from " << |
840 |
v->GetVertexId () << " to network " << w->GetVertexId () << |
1109 |
v->GetVertexId () << " to network " << w->GetVertexId () << |
841 |
" via outgoing interface " << w->GetOutgoingInterfaceId () << |
1110 |
" via outgoing interface " << outIf << |
842 |
" with distance " << distance); |
1111 |
" with distance " << distance); |
843 |
return 1; |
1112 |
return 1; |
844 |
} |
1113 |
} |
|
862 |
* use can then be derived from the next hop IP address (or |
1131 |
* use can then be derived from the next hop IP address (or |
863 |
* it can be inherited from the parent network). |
1132 |
* it can be inherited from the parent network). |
864 |
*/ |
1133 |
*/ |
865 |
w->SetNextHop (linkRemote->GetLinkData ()); |
1134 |
Ipv4Address nextHop = linkRemote->GetLinkData (); |
866 |
w->SetOutgoingInterfaceId (v->GetOutgoingInterfaceId ()); |
1135 |
uint32_t outIf = v->GetRootExitDirection ().second; |
|
|
1136 |
w->SetRootExitDirection (nextHop, outIf); |
867 |
NS_LOG_LOGIC ("Next hop from " << |
1137 |
NS_LOG_LOGIC ("Next hop from " << |
868 |
v->GetVertexId () << " to " << w->GetVertexId () << |
1138 |
v->GetVertexId () << " to " << w->GetVertexId () << |
869 |
" goes through next hop " << w->GetNextHop () << |
1139 |
" goes through next hop " << nextHop << |
870 |
" via outgoing interface " << w->GetOutgoingInterfaceId ()); |
1140 |
" via outgoing interface " << outIf); |
871 |
} |
1141 |
} |
872 |
} |
1142 |
} |
873 |
else |
1143 |
else |
874 |
{ |
1144 |
{ |
875 |
w->SetNextHop (v->GetNextHop ()); |
1145 |
w->SetRootExitDirection (v->GetRootExitDirection ()); |
876 |
w->SetOutgoingInterfaceId (v->GetOutgoingInterfaceId ()); |
|
|
877 |
} |
1146 |
} |
878 |
} |
1147 |
} |
879 |
else |
1148 |
else |
|
891 |
// (shortest) paths. So the next hop and outoing interface remain the same |
1160 |
// (shortest) paths. So the next hop and outoing interface remain the same |
892 |
// (are inherited). |
1161 |
// (are inherited). |
893 |
// |
1162 |
// |
894 |
w->SetNextHop (v->GetNextHop ()); |
1163 |
w->InheritAllRootExitDirections (v); |
895 |
w->SetOutgoingInterfaceId (v->GetOutgoingInterfaceId ()); |
|
|
896 |
} |
1164 |
} |
897 |
// |
1165 |
// |
898 |
// In all cases, we need valid values for the distance metric and a parent. |
1166 |
// In all cases, we need valid values for the distance metric and a parent. |
|
1190 |
// |
1458 |
// |
1191 |
// Note that when there is a choice of vertices closest to the root, network |
1459 |
// Note that when there is a choice of vertices closest to the root, network |
1192 |
// vertices must be chosen before router vertices in order to necessarily |
1460 |
// vertices must be chosen before router vertices in order to necessarily |
1193 |
// find all equal-cost paths. We don't do this at this moment, we should add |
1461 |
// find all equal-cost paths. This is done by using the patch |
1194 |
// the treatment above codes. -- kunihiro. |
1462 |
// 'change-candidate-queue-to-consider-lsa-type-when-ordering.patch' |
1195 |
// |
1463 |
// |
1196 |
// RFC2328 16.1. (4). |
1464 |
// RFC2328 16.1. (4). |
1197 |
// |
1465 |
// |
|
1367 |
Ipv4Mask tempmask ("255.255.255.0"); |
1635 |
Ipv4Mask tempmask ("255.255.255.0"); |
1368 |
Ipv4Address tempip = l->GetLinkId (); |
1636 |
Ipv4Address tempip = l->GetLinkId (); |
1369 |
tempip = tempip.CombineMask (tempmask); |
1637 |
tempip = tempip.CombineMask (tempmask); |
1370 |
|
|
|
1371 |
NS_LOG_LOGIC (" Node " << node->GetId () << |
1372 |
" add route to " << tempip << |
1373 |
" with mask " << tempmask << |
1374 |
" using next hop " << v->GetNextHop () << |
1375 |
" via interface " << v->GetOutgoingInterfaceId ()); |
1376 |
// |
1638 |
// |
1377 |
// Here's why we did all of that work. We're going to add a host route to the |
1639 |
// Here's why we did all of that work. We're going to add a host route to the |
1378 |
// host address found in the m_linkData field of the point-to-point link |
1640 |
// host address found in the m_linkData field of the point-to-point link |
|
1394 |
} |
1656 |
} |
1395 |
Ptr<Ipv4GlobalRouting> gr = router->GetRoutingProtocol (); |
1657 |
Ptr<Ipv4GlobalRouting> gr = router->GetRoutingProtocol (); |
1396 |
NS_ASSERT (gr); |
1658 |
NS_ASSERT (gr); |
1397 |
if (v->GetOutgoingInterfaceId () >= 0) |
1659 |
// walk through all next-hop-IPs and out-going-interfaces for reaching |
1398 |
{ |
1660 |
// the stub network gateway 'v' from the root node |
1399 |
gr->AddNetworkRouteTo (tempip, tempmask, v->GetNextHop (), v->GetOutgoingInterfaceId ()); |
1661 |
for (uint32_t i = 0; i < v->GetNRootExitDirections (); i++) |
1400 |
NS_LOG_LOGIC ("Node " << node->GetId () << |
1662 |
{ |
1401 |
" add network route to " << tempip << |
1663 |
SPFVertex::NodeExit_t exit = v->GetRootExitDirection (i); |
1402 |
" using next hop " << v->GetNextHop () << |
1664 |
Ipv4Address nextHop = exit.first; |
1403 |
" via interface " << v->GetOutgoingInterfaceId ()); |
1665 |
int32_t outIf = exit.second; |
1404 |
} |
1666 |
if (outIf >= 0) |
1405 |
else |
1667 |
{ |
1406 |
{ |
1668 |
gr->AddNetworkRouteTo (tempip, tempmask, nextHop, outIf); |
1407 |
NS_LOG_LOGIC ("Node " << node->GetId () << |
1669 |
NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () << |
1408 |
" NOT able to add network route to " << tempip << |
1670 |
" add network route to " << tempip << |
1409 |
" using next hop " << v->GetNextHop () << |
1671 |
" using next hop " << nextHop << |
1410 |
" since outgoing interface id is negative"); |
1672 |
" via interface " << outIf); |
1411 |
} |
1673 |
} |
|
|
1674 |
else |
1675 |
{ |
1676 |
NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () << |
1677 |
" NOT able to add network route to " << tempip << |
1678 |
" using next hop " << nextHop << |
1679 |
" since outgoing interface id is negative"); |
1680 |
} |
1681 |
} |
1412 |
return; |
1682 |
return; |
1413 |
} // if |
1683 |
} // if |
1414 |
} // for |
1684 |
} // for |
|
1598 |
{ |
1868 |
{ |
1599 |
continue; |
1869 |
continue; |
1600 |
} |
1870 |
} |
1601 |
|
|
|
1602 |
NS_LOG_LOGIC (" Node " << node->GetId () << |
1603 |
" add route to " << lr->GetLinkData () << |
1604 |
" using next hop " << v->GetNextHop () << |
1605 |
" via interface " << v->GetOutgoingInterfaceId ()); |
1606 |
// |
1871 |
// |
1607 |
// Here's why we did all of that work. We're going to add a host route to the |
1872 |
// Here's why we did all of that work. We're going to add a host route to the |
1608 |
// host address found in the m_linkData field of the point-to-point link |
1873 |
// host address found in the m_linkData field of the point-to-point link |
|
1623 |
} |
1888 |
} |
1624 |
Ptr<Ipv4GlobalRouting> gr = router->GetRoutingProtocol (); |
1889 |
Ptr<Ipv4GlobalRouting> gr = router->GetRoutingProtocol (); |
1625 |
NS_ASSERT (gr); |
1890 |
NS_ASSERT (gr); |
1626 |
if (v->GetOutgoingInterfaceId () >= 0) |
1891 |
// walk through all available exit directions due to ECMP, |
1627 |
{ |
1892 |
// and add host route for each of the exit direction toward |
1628 |
gr->AddHostRouteTo (lr->GetLinkData (), v->GetNextHop (), |
1893 |
// the vertex 'v' |
1629 |
v->GetOutgoingInterfaceId ()); |
1894 |
for (uint32_t i = 0; i < v->GetNRootExitDirections (); i++) |
1630 |
NS_LOG_LOGIC ("Node " << node->GetId () << |
1895 |
{ |
1631 |
" adding host route to " << lr->GetLinkData () << |
1896 |
SPFVertex::NodeExit_t exit = v->GetRootExitDirection (i); |
1632 |
" using next hop " << v->GetNextHop () << |
1897 |
Ipv4Address nextHop = exit.first; |
1633 |
" and outgoing interface " << v->GetOutgoingInterfaceId ()); |
1898 |
int32_t outIf = exit.second; |
1634 |
} |
1899 |
if (outIf >= 0) |
1635 |
else |
1900 |
{ |
1636 |
{ |
1901 |
gr->AddHostRouteTo (lr->GetLinkData (), nextHop, |
1637 |
NS_LOG_LOGIC ("Node " << node->GetId () << |
1902 |
outIf); |
1638 |
" NOT able to add host route to " << lr->GetLinkData () << |
1903 |
NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () << |
1639 |
" using next hop " << v->GetNextHop () << |
1904 |
" adding host route to " << lr->GetLinkData () << |
1640 |
" since outgoing interface id is negative"); |
1905 |
" using next hop " << nextHop << |
1641 |
} |
1906 |
" and outgoing interface " << outIf); |
|
|
1907 |
} |
1908 |
else |
1909 |
{ |
1910 |
NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () << |
1911 |
" NOT able to add host route to " << lr->GetLinkData () << |
1912 |
" using next hop " << nextHop << |
1913 |
" since outgoing interface id is negative " << outIf); |
1914 |
} |
1915 |
} // for all routes from the root the vertex 'v' |
1642 |
} |
1916 |
} |
1643 |
// |
1917 |
// |
1644 |
// Done adding the routes for the selected node. |
1918 |
// Done adding the routes for the selected node. |
|
1726 |
} |
2000 |
} |
1727 |
Ptr<Ipv4GlobalRouting> gr = router->GetRoutingProtocol (); |
2001 |
Ptr<Ipv4GlobalRouting> gr = router->GetRoutingProtocol (); |
1728 |
NS_ASSERT (gr); |
2002 |
NS_ASSERT (gr); |
1729 |
if (v->GetOutgoingInterfaceId () >= 0) |
2003 |
// walk through all available exit directions due to ECMP, |
1730 |
{ |
2004 |
// and add host route for each of the exit direction toward |
1731 |
gr->AddNetworkRouteTo (tempip, tempmask, v->GetNextHop (), |
2005 |
// the vertex 'v' |
1732 |
v->GetOutgoingInterfaceId ()); |
2006 |
for (uint32_t i = 0; i < v->GetNRootExitDirections (); i++) |
1733 |
NS_LOG_LOGIC ("Node " << node->GetId () << |
2007 |
{ |
1734 |
" add network route to " << tempip << |
2008 |
SPFVertex::NodeExit_t exit = v->GetRootExitDirection (i); |
1735 |
" using next hop " << v->GetNextHop () << |
2009 |
Ipv4Address nextHop = exit.first; |
1736 |
" via interface " << v->GetOutgoingInterfaceId ()); |
2010 |
int32_t outIf = exit.second; |
1737 |
} |
2011 |
|
1738 |
else |
2012 |
if (outIf >= 0) |
1739 |
{ |
2013 |
{ |
1740 |
NS_LOG_LOGIC ("Node " << node->GetId () << |
2014 |
gr->AddNetworkRouteTo (tempip, tempmask, nextHop, outIf); |
1741 |
" NOT able to add network route to " << tempip << |
2015 |
NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () << |
1742 |
" using next hop " << v->GetNextHop () << |
2016 |
" add network route to " << tempip << |
1743 |
" since outgoing interface id is negative"); |
2017 |
" using next hop " << nextHop << |
|
|
2018 |
" via interface " << outIf); |
2019 |
} |
2020 |
else |
2021 |
{ |
2022 |
NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () << |
2023 |
" NOT able to add network route to " << tempip << |
2024 |
" using next hop " << nextHop << |
2025 |
" since outgoing interface id is negative " << outIf); |
2026 |
} |
1744 |
} |
2027 |
} |
1745 |
} |
2028 |
} |
1746 |
} |
2029 |
} |
|
1755 |
// Given a pointer to a vertex, it links back to the vertex's parent that it |
2038 |
// Given a pointer to a vertex, it links back to the vertex's parent that it |
1756 |
// already has set and adds itself to that vertex's list of children. |
2039 |
// already has set and adds itself to that vertex's list of children. |
1757 |
// |
2040 |
// |
1758 |
// For now, only one parent (not doing equal-cost multipath) |
|
|
1759 |
// |
1760 |
void |
2041 |
void |
1761 |
GlobalRouteManagerImpl::SPFVertexAddParent (SPFVertex* v) |
2042 |
GlobalRouteManagerImpl::SPFVertexAddParent (SPFVertex* v) |
1762 |
{ |
2043 |
{ |
1763 |
NS_LOG_FUNCTION (v); |
2044 |
NS_LOG_FUNCTION (v); |
1764 |
v->GetParent ()->AddChild (v); |
2045 |
|
|
|
2046 |
for (uint32_t i=0;;) |
2047 |
{ |
2048 |
SPFVertex* parent; |
2049 |
// check if all parents of vertex v |
2050 |
if ((parent = v->GetParent (i++)) == 0) |
2051 |
break; |
2052 |
parent->AddChild (v); |
2053 |
} |
2054 |
//v->GetParent ()->AddChild (v); |
1765 |
} |
2055 |
} |
1766 |
|
2056 |
|
1767 |
} // namespace ns3 |
2057 |
} // namespace ns3 |