|
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::NodeExit_t& exit) |
48 |
{ |
49 |
os << "(" << exit.first << " ," << exit.second << ")"; |
50 |
return os; |
51 |
} |
52 |
|
53 |
std::ostream& |
54 |
operator<< (std::ostream& os, const SPFVertex::ListOfSPFVertex_t& vs) |
55 |
{ |
56 |
typedef SPFVertex::ListOfSPFVertex_t::const_iterator CIter_t; |
57 |
os << "{"; |
58 |
for (CIter_t iter = vs.begin (); iter != vs.end ();) |
59 |
{ |
60 |
os << (*iter)->m_vertexId; |
61 |
if (++iter != vs.end ()) |
62 |
{ |
63 |
os << ", "; |
64 |
} |
65 |
else |
66 |
{ |
67 |
break; |
68 |
} |
69 |
} |
70 |
os << "}"; |
71 |
return os; |
72 |
} |
73 |
|
44 |
// --------------------------------------------------------------------------- |
74 |
// --------------------------------------------------------------------------- |
45 |
// |
75 |
// |
46 |
// SPFVertex Implementation |
76 |
// SPFVertex Implementation |
|
54 |
m_distanceFromRoot (SPF_INFINITY), |
84 |
m_distanceFromRoot (SPF_INFINITY), |
55 |
m_rootOif (SPF_INFINITY), |
85 |
m_rootOif (SPF_INFINITY), |
56 |
m_nextHop ("0.0.0.0"), |
86 |
m_nextHop ("0.0.0.0"), |
57 |
m_parent (0), |
87 |
m_parents (), |
58 |
m_children (), |
88 |
m_children (), |
59 |
m_vertexProcessed (false) |
89 |
m_vertexProcessed (false) |
60 |
{ |
90 |
{ |
|
67 |
m_distanceFromRoot (SPF_INFINITY), |
97 |
m_distanceFromRoot (SPF_INFINITY), |
68 |
m_rootOif (SPF_INFINITY), |
98 |
m_rootOif (SPF_INFINITY), |
69 |
m_nextHop ("0.0.0.0"), |
99 |
m_nextHop ("0.0.0.0"), |
70 |
m_parent (0), |
100 |
m_parents (), |
71 |
m_children (), |
101 |
m_children (), |
72 |
m_vertexProcessed (false) |
102 |
m_vertexProcessed (false) |
73 |
{ |
103 |
{ |
74 |
NS_LOG_FUNCTION_NOARGS (); |
104 |
NS_LOG_FUNCTION_NOARGS (); |
|
|
105 |
|
75 |
if (lsa->GetLSType () == GlobalRoutingLSA::RouterLSA) |
106 |
if (lsa->GetLSType () == GlobalRoutingLSA::RouterLSA) |
76 |
{ |
107 |
{ |
77 |
NS_LOG_LOGIC ("Setting m_vertexType to VertexRouter"); |
108 |
NS_LOG_LOGIC ("Setting m_vertexType to VertexRouter"); |
|
86 |
|
117 |
|
87 |
SPFVertex::~SPFVertex () |
118 |
SPFVertex::~SPFVertex () |
88 |
{ |
119 |
{ |
89 |
NS_LOG_FUNCTION_NOARGS (); |
120 |
NS_LOG_FUNCTION (m_vertexId); |
90 |
for ( ListOfSPFVertex_t::iterator i = m_children.begin (); |
121 |
|
91 |
i != m_children.end (); |
122 |
NS_LOG_LOGIC ("Children vertices - " << m_children); |
92 |
i++) |
123 |
NS_LOG_LOGIC ("Parent verteices - " << m_parents); |
|
|
124 |
|
125 |
// find this node from all its parents and remove the entry of this node |
126 |
// from all its parents |
127 |
for (ListOfSPFVertex_t::iterator piter = m_parents.begin (); |
128 |
piter != m_parents.end (); |
129 |
piter++) |
93 |
{ |
130 |
{ |
94 |
SPFVertex *p = *i; |
131 |
// remove the current vertex from its parent's children list. Check |
|
|
132 |
// if the size of the list is reduced, or the child<->parent relation |
133 |
// is not bidirectional |
134 |
uint32_t orgCount = (*piter)->m_children.size (); |
135 |
(*piter)->m_children.remove (this); |
136 |
uint32_t newCount = (*piter)->m_children.size (); |
137 |
NS_ASSERT_MSG (orgCount > newCount, "Unable to find the current vertex from its parents --- impossible!"); |
138 |
} |
139 |
|
140 |
// delete children |
141 |
while (m_children.size () > 0) |
142 |
{ |
143 |
// pop out children one by one. Some children may disapper |
144 |
// when deleting some other children in the list. As a result, |
145 |
// it is necessary to use pop to walk through all children, instead |
146 |
// of using iterator. |
147 |
// |
148 |
// Note that m_children.pop_front () is not necessary as this |
149 |
// p is removed from the children list when p is deleted |
150 |
SPFVertex* p = m_children.front (); |
151 |
// 'p' == 0, this child is already deleted by its other parent |
152 |
if (p == 0) continue; |
153 |
NS_LOG_LOGIC ("Parent vertex-" << m_vertexId << " deleting its child vertex-" << p->GetVertexId ()); |
95 |
delete p; |
154 |
delete p; |
96 |
p = 0; |
155 |
p = 0; |
97 |
*i = 0; |
|
|
98 |
} |
156 |
} |
99 |
m_children.clear (); |
157 |
m_children.clear (); |
|
|
158 |
// delete parents |
159 |
m_parents.clear (); |
160 |
// delete root exit direction |
161 |
m_ecmpRootExits.clear (); |
162 |
|
163 |
NS_LOG_LOGIC ("Vertex-" << m_vertexId << " completed deleted"); |
100 |
} |
164 |
} |
101 |
|
165 |
|
102 |
void |
166 |
void |
|
155 |
return m_distanceFromRoot; |
219 |
return m_distanceFromRoot; |
156 |
} |
220 |
} |
157 |
|
221 |
|
158 |
void |
222 |
void |
159 |
SPFVertex::SetOutgoingInterfaceId (int32_t id) |
223 |
SPFVertex::SetOutgoingInterfaceId (int32_t id) |
160 |
{ |
224 |
{ |
161 |
NS_LOG_FUNCTION (id); |
225 |
NS_LOG_FUNCTION (id); |
|
|
226 |
|
227 |
// always maintain only one output interface index when using setter/getter methods |
162 |
m_rootOif = id; |
228 |
m_rootOif = id; |
163 |
} |
229 |
} |
164 |
|
230 |
|
165 |
uint32_t |
231 |
uint32_t |
166 |
SPFVertex::GetOutgoingInterfaceId (void) const |
232 |
SPFVertex::GetOutgoingInterfaceId (void) const |
167 |
{ |
233 |
{ |
168 |
NS_LOG_FUNCTION_NOARGS (); |
234 |
NS_LOG_FUNCTION_NOARGS (); |
169 |
return m_rootOif; |
235 |
return m_rootOif; |
170 |
} |
236 |
} |
171 |
|
237 |
|
|
|
238 |
//void |
239 |
//SPFVertex::MergeOutgoingInterfaceId (const SPFVertex* v) |
240 |
//{ |
241 |
// NS_LOG_FUNCTION (v); |
242 |
// |
243 |
// NS_LOG_LOGIC ("Before merge, list of root out-going interfaces = " << m_rootOif); |
244 |
// // combine the two lists first, and then remove any duplicated after |
245 |
// m_rootOif.insert (m_rootOif.end (), |
246 |
// v->m_rootOif.begin (), v->m_rootOif.end ()); |
247 |
// // remove duplication |
248 |
// m_rootOif.sort (); |
249 |
// m_rootOif.unique (); |
250 |
// NS_LOG_LOGIC ("After merge, list of root out-going interfaces = " << m_rootOif); |
251 |
//} |
252 |
|
172 |
void |
253 |
void |
173 |
SPFVertex::SetNextHop (Ipv4Address nextHop) |
254 |
SPFVertex::SetNextHop (Ipv4Address nextHop) |
174 |
{ |
255 |
{ |
175 |
NS_LOG_FUNCTION (nextHop); |
256 |
NS_LOG_FUNCTION (nextHop); |
|
|
257 |
|
258 |
// always maintain only one nexthop when using setter/getter methods |
176 |
m_nextHop = nextHop; |
259 |
m_nextHop = nextHop; |
177 |
} |
260 |
} |
178 |
|
261 |
|
|
187 |
SPFVertex::SetParent (SPFVertex* parent) |
270 |
SPFVertex::SetParent (SPFVertex* parent) |
188 |
{ |
271 |
{ |
189 |
NS_LOG_FUNCTION (parent); |
272 |
NS_LOG_FUNCTION (parent); |
190 |
m_parent = parent; |
273 |
|
|
|
274 |
// always maintain only one parent when using setter/getter methods |
275 |
m_parents.clear (); |
276 |
m_parents.push_back (parent); |
191 |
} |
277 |
} |
192 |
|
278 |
|
193 |
SPFVertex* |
279 |
SPFVertex* |
194 |
SPFVertex::GetParent (void) const |
280 |
SPFVertex::GetParent (uint32_t i) const |
195 |
{ |
281 |
{ |
196 |
NS_LOG_FUNCTION_NOARGS (); |
282 |
NS_LOG_FUNCTION_NOARGS (); |
197 |
return m_parent; |
283 |
|
|
|
284 |
// If the index i is out-of-range, return 0 and do nothing |
285 |
if (m_parents.size () <= i) |
286 |
{ |
287 |
NS_LOG_LOGIC ("Index to SPFVertex's parent is out-of-range."); |
288 |
return 0; |
289 |
} |
290 |
ListOfSPFVertex_t::const_iterator iter = m_parents.begin (); |
291 |
while (i-- > 0) |
292 |
{ |
293 |
iter++; |
294 |
} |
295 |
return *iter; |
198 |
} |
296 |
} |
199 |
|
297 |
|
200 |
uint32_t |
298 |
void |
|
|
299 |
SPFVertex::MergeParent (const SPFVertex* v) |
300 |
{ |
301 |
NS_LOG_FUNCTION (v); |
302 |
|
303 |
NS_LOG_LOGIC ("Before merge, list of parents = " << m_parents); |
304 |
// combine the two lists first, and then remove any duplicated after |
305 |
m_parents.insert (m_parents.end (), |
306 |
v->m_parents.begin (), v->m_parents.end ()); |
307 |
// remove duplication |
308 |
m_parents.sort (); |
309 |
m_parents.unique (); |
310 |
NS_LOG_LOGIC ("After merge, list of parents = " << m_parents); |
311 |
} |
312 |
|
313 |
void |
314 |
SPFVertex::SetRootExitDirection (Ipv4Address nextHop, int32_t id) |
315 |
{ |
316 |
NS_LOG_FUNCTION (nextHop << id); |
317 |
|
318 |
// always maintain only one root's exit |
319 |
m_ecmpRootExits.clear (); |
320 |
m_ecmpRootExits.push_back (NodeExit_t (nextHop, id)); |
321 |
// update the following in order to be backward compatitable with |
322 |
// GetNextHop and GetOutgoingInterface methods |
323 |
m_nextHop = nextHop; |
324 |
m_rootOif = id; |
325 |
} |
326 |
|
327 |
void |
328 |
SPFVertex::SetRootExitDirection (SPFVertex::NodeExit_t exit) |
329 |
{ |
330 |
NS_LOG_FUNCTION (exit); |
331 |
SetRootExitDirection (exit.first, exit.second); |
332 |
} |
333 |
|
334 |
SPFVertex::NodeExit_t |
335 |
SPFVertex::GetRootExitDirection (uint32_t i) const |
336 |
{ |
337 |
NS_LOG_FUNCTION (i); |
338 |
typedef ListOfNodeExit_t::const_iterator CIter_t; |
339 |
|
340 |
NS_ASSERT_MSG (i < m_ecmpRootExits.size (), "Index out-of-range when accessing SPFVertex::m_ecmpRootExits!"); |
341 |
CIter_t iter = m_ecmpRootExits.begin (); |
342 |
while (i-- > 0) {iter++;} |
343 |
|
344 |
return *iter; |
345 |
} |
346 |
|
347 |
SPFVertex::NodeExit_t |
348 |
SPFVertex::GetRootExitDirection () const |
349 |
{ |
350 |
NS_LOG_FUNCTION_NOARGS (); |
351 |
|
352 |
NS_ASSERT_MSG (m_ecmpRootExits.size () <= 1, "Assumed there is at most one exit from the root to this vertex"); |
353 |
return GetRootExitDirection (0); |
354 |
} |
355 |
|
356 |
void |
357 |
SPFVertex::MergeRootExitDirections (const SPFVertex* vertex) |
358 |
{ |
359 |
NS_LOG_FUNCTION (vertex); |
360 |
|
361 |
// obtain the external list of exit directions |
362 |
// |
363 |
// Append the external list into 'this' and remove duplication afterward |
364 |
const ListOfNodeExit_t& extList = vertex->m_ecmpRootExits; |
365 |
m_ecmpRootExits.insert (m_ecmpRootExits.end (), |
366 |
extList.begin(), extList.end ()); |
367 |
m_ecmpRootExits.sort (); |
368 |
m_ecmpRootExits.unique (); |
369 |
} |
370 |
|
371 |
void |
372 |
SPFVertex::InheritAllRootExitDirections (const SPFVertex* vertex) |
373 |
{ |
374 |
NS_LOG_FUNCTION (vertex); |
375 |
|
376 |
// discard all exit direction currently assoicated with this vertex, |
377 |
// and copy all the exit directions from the given vertex |
378 |
if (m_ecmpRootExits.size () > 0) |
379 |
{ |
380 |
NS_LOG_WARN ("x root exit directions in this vertex are going to be discarded"); |
381 |
} |
382 |
m_ecmpRootExits.clear (); |
383 |
m_ecmpRootExits.insert (m_ecmpRootExits.end (), |
384 |
vertex->m_ecmpRootExits.begin (), vertex->m_ecmpRootExits.end ()); |
385 |
} |
386 |
|
387 |
uint32_t |
388 |
SPFVertex::GetNRootExitDirections () const |
389 |
{ |
390 |
NS_LOG_FUNCTION_NOARGS (); |
391 |
return m_ecmpRootExits.size (); |
392 |
} |
393 |
|
394 |
uint32_t |
201 |
SPFVertex::GetNChildren (void) const |
395 |
SPFVertex::GetNChildren (void) const |
202 |
{ |
396 |
{ |
203 |
NS_LOG_FUNCTION_NOARGS (); |
397 |
NS_LOG_FUNCTION_NOARGS (); |
|
376 |
|
570 |
|
377 |
GlobalRouteManagerImpl::GlobalRouteManagerImpl () |
571 |
GlobalRouteManagerImpl::GlobalRouteManagerImpl () |
378 |
: |
572 |
: |
379 |
m_spfroot (0) |
573 |
m_spfroot (0) |
380 |
{ |
574 |
{ |
381 |
NS_LOG_FUNCTION_NOARGS (); |
575 |
NS_LOG_FUNCTION_NOARGS (); |
382 |
m_lsdb = new GlobalRouteManagerLSDB (); |
576 |
m_lsdb = new GlobalRouteManagerLSDB (); |
|
536 |
// |
730 |
// |
537 |
// Walk the list of nodes in the system. |
731 |
// Walk the list of nodes in the system. |
538 |
// |
732 |
// |
|
|
733 |
NS_LOG_INFO ("About to start SPF calculation"); |
539 |
NodeList::Iterator listEnd = NodeList::End (); |
734 |
NodeList::Iterator listEnd = NodeList::End (); |
540 |
for (NodeList::Iterator i = NodeList::Begin (); i != listEnd; i++) |
735 |
for (NodeList::Iterator i = NodeList::Begin (); i != listEnd; i++) |
541 |
{ |
736 |
{ |
|
555 |
SPFCalculate (rtr->GetRouterId ()); |
750 |
SPFCalculate (rtr->GetRouterId ()); |
556 |
} |
751 |
} |
557 |
} |
752 |
} |
|
|
753 |
NS_LOG_INFO ("Finished SPF calculation"); |
558 |
} |
754 |
} |
559 |
|
755 |
|
560 |
// |
756 |
// |
|
688 |
// Is there already vertex w in candidate list? |
884 |
// Is there already vertex w in candidate list? |
689 |
if (w_lsa->GetStatus () == GlobalRoutingLSA::LSA_SPF_NOT_EXPLORED) |
885 |
if (w_lsa->GetStatus () == GlobalRoutingLSA::LSA_SPF_NOT_EXPLORED) |
690 |
{ |
886 |
{ |
691 |
|
|
|
692 |
// prepare vertex w |
693 |
w = new SPFVertex (w_lsa); |
694 |
// Calculate nexthop to w |
887 |
// Calculate nexthop to w |
695 |
// We need to figure out how to actually get to the new router represented |
888 |
// We need to figure out how to actually get to the new router represented |
696 |
// by <w>. This will (among other things) find the next hop address to send |
889 |
// by <w>. This will (among other things) find the next hop address to send |
697 |
// packets destined for this network to, and also find the outbound interface |
890 |
// packets destined for this network to, and also find the outbound interface |
698 |
// used to forward the packets. |
891 |
// used to forward the packets. |
699 |
// |
892 |
|
|
|
893 |
// prepare vertex w |
894 |
w = new SPFVertex (w_lsa); |
700 |
if (SPFNexthopCalculation (v, w, l, distance)) |
895 |
if (SPFNexthopCalculation (v, w, l, distance)) |
701 |
{ |
896 |
{ |
702 |
w_lsa->SetStatus (GlobalRoutingLSA::LSA_SPF_CANDIDATE); |
897 |
w_lsa->SetStatus (GlobalRoutingLSA::LSA_SPF_CANDIDATE); |
|
710 |
v->GetVertexId () << ", distance: " << |
905 |
v->GetVertexId () << ", distance: " << |
711 |
w->GetDistanceFromRoot ()); |
906 |
w->GetDistanceFromRoot ()); |
712 |
} |
907 |
} |
|
|
908 |
else |
909 |
NS_ASSERT_MSG (0, "SPFNexthopCalculation never " |
910 |
<< "return false, but it does now!"); |
713 |
} |
911 |
} |
714 |
else if (w_lsa->GetStatus () == GlobalRoutingLSA::LSA_SPF_CANDIDATE) |
912 |
else if (w_lsa->GetStatus () == GlobalRoutingLSA::LSA_SPF_CANDIDATE) |
715 |
{ |
913 |
{ |
|
720 |
// |
918 |
// |
721 |
// So, locate the vertex in the candidate queue and take a look at the |
919 |
// So, locate the vertex in the candidate queue and take a look at the |
722 |
// distance. |
920 |
// distance. |
723 |
w = candidate.Find (w_lsa->GetLinkStateId ()); |
921 |
|
724 |
if (w->GetDistanceFromRoot () < distance) |
922 |
/* (quagga-0.98.6) W is already on the candidate list; call it cw. |
|
|
923 |
* Compare the previously calculated cost (cw->distance) |
924 |
* with the cost we just determined (w->distance) to see |
925 |
* if we've found a shorter path. |
926 |
*/ |
927 |
SPFVertex* cw; |
928 |
cw = candidate.Find (w_lsa->GetLinkStateId ()); |
929 |
if (cw->GetDistanceFromRoot () < distance) |
725 |
{ |
930 |
{ |
726 |
// |
931 |
// |
727 |
// This is not a shorter path, so don't do anything. |
932 |
// This is not a shorter path, so don't do anything. |
728 |
// |
933 |
// |
729 |
continue; |
934 |
continue; |
730 |
} |
935 |
} |
731 |
else if (w->GetDistanceFromRoot () == distance) |
936 |
else if (cw->GetDistanceFromRoot () == distance) |
732 |
{ |
937 |
{ |
733 |
// |
938 |
// |
734 |
// This path is one with an equal cost. Do nothing for now -- we're not doing |
939 |
// This path is one with an equal cost. |
735 |
// equal-cost multipath cases yet. |
|
|
736 |
// |
940 |
// |
|
|
941 |
NS_LOG_LOGIC ("Equal cost multiple paths found."); |
942 |
|
943 |
// At this point, there are two instances 'w' and 'cw' of the |
944 |
// same vertex, the vertex that is currently being considered |
945 |
// for adding into the shortest path tree. 'w' is the instance |
946 |
// as seen from the root via vertex 'v', and 'cw' is the instance |
947 |
// as seen from the root via some other vertices other than 'v'. |
948 |
// These two instances are being merged in the following code. |
949 |
// In particular, the parent nodes, the next hops, and the root's |
950 |
// output interfaces of the two instances are being merged. |
951 |
// |
952 |
// Note that this is functionally equivalent to calling |
953 |
// ospf_nexthop_merge (cw->nexthop, w->nexthop) in quagga-0.98.6 |
954 |
// (ospf_spf.c::859), although the detail implementation |
955 |
// is very different from quagga (blame ns3::GlobalRouteManagerImpl) |
956 |
|
957 |
// prepare vertex w |
958 |
w = new SPFVertex (w_lsa); |
959 |
SPFNexthopCalculation (v, w, l, distance); |
960 |
cw->MergeRootExitDirections (w); |
961 |
cw->MergeParent (w); |
962 |
// SPFVertexAddParent (w) is necessary as the destructor of |
963 |
// SPFVertex checks if the vertex and its parent is linked |
964 |
// bidirectionally |
965 |
SPFVertexAddParent (w); |
966 |
delete w; |
737 |
} |
967 |
} |
738 |
else |
968 |
else // cw->GetDistanceFromRoot () > w->GetDistanceFromRoot () |
739 |
{ |
969 |
{ |
740 |
// |
970 |
// |
741 |
// this path represents a new, lower-cost path to <w> (the vertex we found in |
971 |
// this path represents a new, lower-cost path to <w> (the vertex we found in |
|
745 |
// N.B. the nexthop_calculation is conditional, if it finds a valid nexthop |
975 |
// N.B. the nexthop_calculation is conditional, if it finds a valid nexthop |
746 |
// it will call spf_add_parents, which will flush the old parents |
976 |
// it will call spf_add_parents, which will flush the old parents |
747 |
// |
977 |
// |
748 |
if (SPFNexthopCalculation (v, w, l, distance)) |
978 |
if (SPFNexthopCalculation (v, cw, l, distance)) |
749 |
{ |
979 |
{ |
750 |
// |
980 |
// |
751 |
// If we've changed the cost to get to the vertex represented by <w>, we |
981 |
// If we've changed the cost to get to the vertex represented by <w>, we |
|
753 |
// |
983 |
// |
754 |
candidate.Reorder (); |
984 |
candidate.Reorder (); |
755 |
} |
985 |
} |
756 |
} // new lower cost path found |
986 |
} // new lower cost path found |
757 |
} // end W is already on the candidate list |
987 |
} // end W is already on the candidate list |
758 |
} // end loop over the links in V's LSA |
988 |
} // end loop over the links in V's LSA |
759 |
} |
989 |
} |
|
847 |
// from the root node to the host represented by vertex <w>, you have to send |
1077 |
// from the root node to the host represented by vertex <w>, you have to send |
848 |
// the packet to the next hop address specified in w->m_nextHop. |
1078 |
// the packet to the next hop address specified in w->m_nextHop. |
849 |
// |
1079 |
// |
850 |
w->SetNextHop (linkRemote->GetLinkData ()); |
1080 |
Ipv4Address nextHop = linkRemote->GetLinkData (); |
851 |
// |
1081 |
// |
852 |
// Now find the outgoing interface corresponding to the point to point link |
1082 |
// Now find the outgoing interface corresponding to the point to point link |
853 |
// from the perspective of <v> -- remember that <l> is the link "from" |
1083 |
// from the perspective of <v> -- remember that <l> is the link "from" |
854 |
// <v> "to" <w>. |
1084 |
// <v> "to" <w>. |
855 |
// |
1085 |
// |
856 |
w->SetOutgoingInterfaceId ( |
1086 |
uint32_t outIf = FindOutgoingInterfaceId (l->GetLinkData ()); |
857 |
FindOutgoingInterfaceId (l->GetLinkData ())); |
1087 |
|
|
|
1088 |
w->SetRootExitDirection (nextHop, outIf); |
858 |
w->SetDistanceFromRoot (distance); |
1089 |
w->SetDistanceFromRoot (distance); |
859 |
w->SetParent (v); |
1090 |
w->SetParent (v); |
860 |
NS_LOG_LOGIC ("Next hop from " << |
1091 |
NS_LOG_LOGIC ("Next hop from " << |
861 |
v->GetVertexId () << " to " << w->GetVertexId () << |
1092 |
v->GetVertexId () << " to " << w->GetVertexId () << |
862 |
" goes through next hop " << w->GetNextHop () << |
1093 |
" goes through next hop " << nextHop << |
863 |
" via outgoing interface " << w->GetOutgoingInterfaceId () << |
1094 |
" via outgoing interface " << outIf << |
864 |
" with distance " << distance); |
1095 |
" with distance " << distance); |
865 |
} // end W is a router vertes |
1096 |
} // end W is a router vertes |
866 |
else |
1097 |
else |
|
870 |
GlobalRoutingLSA* w_lsa = w->GetLSA (); |
1101 |
GlobalRoutingLSA* w_lsa = w->GetLSA (); |
871 |
NS_ASSERT (w_lsa->GetLSType () == GlobalRoutingLSA::NetworkLSA); |
1102 |
NS_ASSERT (w_lsa->GetLSType () == GlobalRoutingLSA::NetworkLSA); |
872 |
// Find outgoing interface ID for this network |
1103 |
// Find outgoing interface ID for this network |
873 |
w->SetOutgoingInterfaceId ( |
1104 |
uint32_t outIf = FindOutgoingInterfaceId (w_lsa->GetLinkStateId (), |
874 |
FindOutgoingInterfaceId (w_lsa->GetLinkStateId (), |
1105 |
w_lsa->GetNetworkLSANetworkMask () ); |
875 |
w_lsa->GetNetworkLSANetworkMask () )); |
1106 |
// Set the next hop to 0.0.0.0 meaning "not exist" |
|
|
1107 |
Ipv4Address nextHop = Ipv4Address::GetZero (); |
1108 |
w->SetRootExitDirection (nextHop, outIf); |
876 |
w->SetDistanceFromRoot (distance); |
1109 |
w->SetDistanceFromRoot (distance); |
877 |
w->SetParent (v); |
1110 |
w->SetParent (v); |
878 |
NS_LOG_LOGIC ("Next hop from " << |
1111 |
NS_LOG_LOGIC ("Next hop from " << |
879 |
v->GetVertexId () << " to network " << w->GetVertexId () << |
1112 |
v->GetVertexId () << " to network " << w->GetVertexId () << |
880 |
" via outgoing interface " << w->GetOutgoingInterfaceId () << |
1113 |
" via outgoing interface " << outIf << |
881 |
" with distance " << distance); |
1114 |
" with distance " << distance); |
882 |
return 1; |
1115 |
return 1; |
883 |
} |
1116 |
} |
|
901 |
* use can then be derived from the next hop IP address (or |
1134 |
* use can then be derived from the next hop IP address (or |
902 |
* it can be inherited from the parent network). |
1135 |
* it can be inherited from the parent network). |
903 |
*/ |
1136 |
*/ |
904 |
w->SetNextHop (linkRemote->GetLinkData ()); |
1137 |
Ipv4Address nextHop = linkRemote->GetLinkData (); |
905 |
w->SetOutgoingInterfaceId (v->GetOutgoingInterfaceId ()); |
1138 |
uint32_t outIf = v->GetRootExitDirection ().second; |
|
|
1139 |
w->SetRootExitDirection (nextHop, outIf); |
906 |
NS_LOG_LOGIC ("Next hop from " << |
1140 |
NS_LOG_LOGIC ("Next hop from " << |
907 |
v->GetVertexId () << " to " << w->GetVertexId () << |
1141 |
v->GetVertexId () << " to " << w->GetVertexId () << |
908 |
" goes through next hop " << w->GetNextHop () << |
1142 |
" goes through next hop " << nextHop << |
909 |
" via outgoing interface " << w->GetOutgoingInterfaceId ()); |
1143 |
" via outgoing interface " << outIf); |
910 |
} |
1144 |
} |
911 |
} |
1145 |
} |
912 |
else |
1146 |
else |
913 |
{ |
1147 |
{ |
914 |
w->SetNextHop (v->GetNextHop ()); |
1148 |
w->SetRootExitDirection (v->GetRootExitDirection ()); |
915 |
w->SetOutgoingInterfaceId (v->GetOutgoingInterfaceId ()); |
|
|
916 |
} |
1149 |
} |
917 |
} |
1150 |
} |
918 |
else |
1151 |
else |
|
930 |
// (shortest) paths. So the next hop and outoing interface remain the same |
1163 |
// (shortest) paths. So the next hop and outoing interface remain the same |
931 |
// (are inherited). |
1164 |
// (are inherited). |
932 |
// |
1165 |
// |
933 |
w->SetNextHop (v->GetNextHop ()); |
1166 |
w->InheritAllRootExitDirections (v); |
934 |
w->SetOutgoingInterfaceId (v->GetOutgoingInterfaceId ()); |
|
|
935 |
} |
1167 |
} |
936 |
// |
1168 |
// |
937 |
// In all cases, we need valid values for the distance metric and a parent. |
1169 |
// In all cases, we need valid values for the distance metric and a parent. |
|
1210 |
// of the routers found in the Global Router Link Records and added tehm to |
1442 |
// of the routers found in the Global Router Link Records and added tehm to |
1211 |
// the candidate list. |
1443 |
// the candidate list. |
1212 |
// |
1444 |
// |
|
|
1445 |
NS_LOG_LOGIC (candidate); |
1213 |
v = candidate.Pop (); |
1446 |
v = candidate.Pop (); |
1214 |
NS_LOG_LOGIC ("Popped vertex " << v->GetVertexId ()); |
1447 |
NS_LOG_LOGIC ("Popped vertex " << v->GetVertexId ()); |
1215 |
// |
1448 |
// |
|
1228 |
// |
1461 |
// |
1229 |
// Note that when there is a choice of vertices closest to the root, network |
1462 |
// Note that when there is a choice of vertices closest to the root, network |
1230 |
// vertices must be chosen before router vertices in order to necessarily |
1463 |
// vertices must be chosen before router vertices in order to necessarily |
1231 |
// find all equal-cost paths. We don't do this at this moment, we should add |
1464 |
// find all equal-cost paths. |
1232 |
// the treatment above codes. -- kunihiro. |
|
|
1233 |
// |
1465 |
// |
1234 |
// RFC2328 16.1. (4). |
1466 |
// RFC2328 16.1. (4). |
1235 |
// |
1467 |
// |
|
1569 |
Ipv4Mask tempmask ("255.255.255.0"); |
1801 |
Ipv4Mask tempmask ("255.255.255.0"); |
1570 |
Ipv4Address tempip = l->GetLinkId (); |
1802 |
Ipv4Address tempip = l->GetLinkId (); |
1571 |
tempip = tempip.CombineMask (tempmask); |
1803 |
tempip = tempip.CombineMask (tempmask); |
1572 |
|
|
|
1573 |
NS_LOG_LOGIC (" Node " << node->GetId () << |
1574 |
" add route to " << tempip << |
1575 |
" with mask " << tempmask << |
1576 |
" using next hop " << v->GetNextHop () << |
1577 |
" via interface " << v->GetOutgoingInterfaceId ()); |
1578 |
// |
1804 |
// |
1579 |
// Here's why we did all of that work. We're going to add a host route to the |
1805 |
// Here's why we did all of that work. We're going to add a host route to the |
1580 |
// host address found in the m_linkData field of the point-to-point link |
1806 |
// host address found in the m_linkData field of the point-to-point link |
|
1596 |
} |
1822 |
} |
1597 |
Ptr<Ipv4GlobalRouting> gr = router->GetRoutingProtocol (); |
1823 |
Ptr<Ipv4GlobalRouting> gr = router->GetRoutingProtocol (); |
1598 |
NS_ASSERT (gr); |
1824 |
NS_ASSERT (gr); |
1599 |
if (v->GetOutgoingInterfaceId () >= 0) |
1825 |
// walk through all next-hop-IPs and out-going-interfaces for reaching |
|
|
1826 |
// the stub network gateway 'v' from the root node |
1827 |
for (uint32_t i = 0; i < v->GetNRootExitDirections (); i++) |
1600 |
{ |
1828 |
{ |
1601 |
gr->AddNetworkRouteTo (tempip, tempmask, v->GetNextHop (), v->GetOutgoingInterfaceId ()); |
1829 |
SPFVertex::NodeExit_t exit = v->GetRootExitDirection (i); |
1602 |
NS_LOG_LOGIC ("Node " << node->GetId () << |
1830 |
Ipv4Address nextHop = exit.first; |
1603 |
" add network route to " << tempip << |
1831 |
int32_t outIf = exit.second; |
1604 |
" using next hop " << v->GetNextHop () << |
1832 |
if (outIf >= 0) |
1605 |
" via interface " << v->GetOutgoingInterfaceId ()); |
1833 |
{ |
1606 |
} |
1834 |
gr->AddNetworkRouteTo (tempip, tempmask, nextHop, outIf); |
1607 |
else |
1835 |
NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () << |
1608 |
{ |
1836 |
" add network route to " << tempip << |
1609 |
NS_LOG_LOGIC ("Node " << node->GetId () << |
1837 |
" using next hop " << nextHop << |
1610 |
" NOT able to add network route to " << tempip << |
1838 |
" via interface " << outIf); |
1611 |
" using next hop " << v->GetNextHop () << |
1839 |
} |
1612 |
" since outgoing interface id is negative"); |
1840 |
else |
|
|
1841 |
{ |
1842 |
NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () << |
1843 |
" NOT able to add network route to " << tempip << |
1844 |
" using next hop " << nextHop << |
1845 |
" since outgoing interface id is negative"); |
1846 |
} |
1613 |
} |
1847 |
} |
1614 |
return; |
1848 |
return; |
1615 |
} // if |
1849 |
} // if |
|
1802 |
{ |
2036 |
{ |
1803 |
continue; |
2037 |
continue; |
1804 |
} |
2038 |
} |
1805 |
|
|
|
1806 |
NS_LOG_LOGIC (" Node " << node->GetId () << |
1807 |
" add route to " << lr->GetLinkData () << |
1808 |
" using next hop " << v->GetNextHop () << |
1809 |
" via interface " << v->GetOutgoingInterfaceId ()); |
1810 |
// |
2039 |
// |
1811 |
// Here's why we did all of that work. We're going to add a host route to the |
2040 |
// Here's why we did all of that work. We're going to add a host route to the |
1812 |
// host address found in the m_linkData field of the point-to-point link |
2041 |
// host address found in the m_linkData field of the point-to-point link |
|
1827 |
} |
2056 |
} |
1828 |
Ptr<Ipv4GlobalRouting> gr = router->GetRoutingProtocol (); |
2057 |
Ptr<Ipv4GlobalRouting> gr = router->GetRoutingProtocol (); |
1829 |
NS_ASSERT (gr); |
2058 |
NS_ASSERT (gr); |
1830 |
if (v->GetOutgoingInterfaceId () >= 0) |
2059 |
// walk through all available exit directions due to ECMP, |
1831 |
{ |
2060 |
// and add host route for each of the exit direction toward |
1832 |
gr->AddHostRouteTo (lr->GetLinkData (), v->GetNextHop (), |
2061 |
// the vertex 'v' |
1833 |
v->GetOutgoingInterfaceId ()); |
2062 |
for (uint32_t i = 0; i < v->GetNRootExitDirections (); i++) |
1834 |
NS_LOG_LOGIC ("Node " << node->GetId () << |
2063 |
{ |
1835 |
" adding host route to " << lr->GetLinkData () << |
2064 |
SPFVertex::NodeExit_t exit = v->GetRootExitDirection (i); |
1836 |
" using next hop " << v->GetNextHop () << |
2065 |
Ipv4Address nextHop = exit.first; |
1837 |
" and outgoing interface " << v->GetOutgoingInterfaceId ()); |
2066 |
int32_t outIf = exit.second; |
1838 |
} |
2067 |
if (outIf >= 0) |
1839 |
else |
2068 |
{ |
1840 |
{ |
2069 |
gr->AddHostRouteTo (lr->GetLinkData (), nextHop, |
1841 |
NS_LOG_LOGIC ("Node " << node->GetId () << |
2070 |
outIf); |
1842 |
" NOT able to add host route to " << lr->GetLinkData () << |
2071 |
NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () << |
1843 |
" using next hop " << v->GetNextHop () << |
2072 |
" adding host route to " << lr->GetLinkData () << |
1844 |
" since outgoing interface id is negative"); |
2073 |
" using next hop " << nextHop << |
1845 |
} |
2074 |
" and outgoing interface " << outIf); |
|
|
2075 |
} |
2076 |
else |
2077 |
{ |
2078 |
NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () << |
2079 |
" NOT able to add host route to " << lr->GetLinkData () << |
2080 |
" using next hop " << nextHop << |
2081 |
" since outgoing interface id is negative " << outIf); |
2082 |
} |
2083 |
} // for all routes from the root the vertex 'v' |
1846 |
} |
2084 |
} |
1847 |
// |
2085 |
// |
1848 |
// Done adding the routes for the selected node. |
2086 |
// Done adding the routes for the selected node. |
|
1931 |
} |
2169 |
} |
1932 |
Ptr<Ipv4GlobalRouting> gr = router->GetRoutingProtocol (); |
2170 |
Ptr<Ipv4GlobalRouting> gr = router->GetRoutingProtocol (); |
1933 |
NS_ASSERT (gr); |
2171 |
NS_ASSERT (gr); |
1934 |
if (v->GetOutgoingInterfaceId () >= 0) |
2172 |
// walk through all available exit directions due to ECMP, |
1935 |
{ |
2173 |
// and add host route for each of the exit direction toward |
1936 |
gr->AddNetworkRouteTo (tempip, tempmask, v->GetNextHop (), |
2174 |
// the vertex 'v' |
1937 |
v->GetOutgoingInterfaceId ()); |
2175 |
for (uint32_t i = 0; i < v->GetNRootExitDirections (); i++) |
1938 |
NS_LOG_LOGIC ("Node " << node->GetId () << |
2176 |
{ |
1939 |
" add network route to " << tempip << |
2177 |
SPFVertex::NodeExit_t exit = v->GetRootExitDirection (i); |
1940 |
" using next hop " << v->GetNextHop () << |
2178 |
Ipv4Address nextHop = exit.first; |
1941 |
" via interface " << v->GetOutgoingInterfaceId ()); |
2179 |
int32_t outIf = exit.second; |
1942 |
} |
2180 |
|
1943 |
else |
2181 |
if (outIf >= 0) |
1944 |
{ |
2182 |
{ |
1945 |
NS_LOG_LOGIC ("Node " << node->GetId () << |
2183 |
gr->AddNetworkRouteTo (tempip, tempmask, nextHop, outIf); |
1946 |
" NOT able to add network route to " << tempip << |
2184 |
NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () << |
1947 |
" using next hop " << v->GetNextHop () << |
2185 |
" add network route to " << tempip << |
1948 |
" since outgoing interface id is negative"); |
2186 |
" using next hop " << nextHop << |
|
|
2187 |
" via interface " << outIf); |
2188 |
} |
2189 |
else |
2190 |
{ |
2191 |
NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () << |
2192 |
" NOT able to add network route to " << tempip << |
2193 |
" using next hop " << nextHop << |
2194 |
" since outgoing interface id is negative " << outIf); |
2195 |
} |
1949 |
} |
2196 |
} |
1950 |
} |
2197 |
} |
1951 |
} |
2198 |
} |
|
1960 |
// Given a pointer to a vertex, it links back to the vertex's parent that it |
2207 |
// Given a pointer to a vertex, it links back to the vertex's parent that it |
1961 |
// already has set and adds itself to that vertex's list of children. |
2208 |
// already has set and adds itself to that vertex's list of children. |
1962 |
// |
2209 |
// |
1963 |
// For now, only one parent (not doing equal-cost multipath) |
|
|
1964 |
// |
1965 |
void |
2210 |
void |
1966 |
GlobalRouteManagerImpl::SPFVertexAddParent (SPFVertex* v) |
2211 |
GlobalRouteManagerImpl::SPFVertexAddParent (SPFVertex* v) |
1967 |
{ |
2212 |
{ |
1968 |
NS_LOG_FUNCTION (v); |
2213 |
NS_LOG_FUNCTION (v); |
1969 |
v->GetParent ()->AddChild (v); |
2214 |
|
|
|
2215 |
for (uint32_t i=0;;) |
2216 |
{ |
2217 |
SPFVertex* parent; |
2218 |
// check if all parents of vertex v |
2219 |
if ((parent = v->GetParent (i++)) == 0) break; |
2220 |
parent->AddChild (v); |
2221 |
} |
1970 |
} |
2222 |
} |
1971 |
|
2223 |
|
1972 |
} // namespace ns3 |
2224 |
} // namespace ns3 |