LEFT | RIGHT |
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */ | 1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */ |
2 /* | 2 /* |
3 * Copyright 2007 University of Washington | 3 * Copyright 2007 University of Washington |
4 * Copyright (C) 1999, 2000 Kunihiro Ishiguro, Toshiaki Takada | 4 * Copyright (C) 1999, 2000 Kunihiro Ishiguro, Toshiaki Takada |
5 *· | 5 *· |
6 * This program is free software; you can redistribute it and/or modify | 6 * This program is free software; you can redistribute it and/or modify |
7 * it under the terms of the GNU General Public License version 2 as | 7 * it under the terms of the GNU General Public License version 2 as |
8 * published by the Free Software Foundation; | 8 * published by the Free Software Foundation; |
9 * | 9 * |
10 * This program is distributed in the hope that it will be useful, | 10 * This program is distributed in the hope that it will be useful, |
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of | 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of |
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
13 * GNU General Public License for more details. | 13 * GNU General Public License for more details. |
14 * | 14 * |
15 * You should have received a copy of the GNU General Public License | 15 * You should have received a copy of the GNU General Public License |
16 * along with this program; if not, write to the Free Software | 16 * along with this program; if not, write to the Free Software |
17 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | 17 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
18 * | 18 * |
19 * Authors: Tom Henderson (tomhend@u.washington.edu) | 19 * Authors: Tom Henderson (tomhend@u.washington.edu) |
20 *· | 20 *· |
21 * Kunihiro Ishigura, Toshiaki Takada (GNU Zebra) are attributed authors | 21 * Kunihiro Ishigura, Toshiaki Takada (GNU Zebra) are attributed authors |
22 * of the quagga 0.99.7/src/ospfd/ospf_spf.c code which was ported here | 22 * of the quagga 0.99.7/src/ospfd/ospf_spf.c code which was ported here |
23 */ | 23 */ |
24 | 24 |
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" |
31 #include "ns3/node-list.h" | 33 #include "ns3/node-list.h" |
32 #include "ns3/ipv4.h" | 34 #include "ns3/ipv4.h" |
33 #include "ns3/ipv4-routing-protocol.h" | 35 #include "ns3/ipv4-routing-protocol.h" |
34 #include "ns3/ipv4-list-routing.h" | 36 #include "ns3/ipv4-list-routing.h" |
35 #include "ns3/mpi-interface.h" | 37 #include "ns3/mpi-interface.h" |
36 #include "global-router-interface.h" | 38 #include "global-router-interface.h" |
37 #include "global-route-manager-impl.h" | 39 #include "global-route-manager-impl.h" |
38 #include "candidate-queue.h" | 40 #include "candidate-queue.h" |
39 #include "ipv4-global-routing.h" | 41 #include "ipv4-global-routing.h" |
40 | 42 |
41 NS_LOG_COMPONENT_DEFINE ("GlobalRouteManager"); | 43 NS_LOG_COMPONENT_DEFINE ("GlobalRouteManager"); |
42 | 44 |
43 namespace ns3 { | 45 namespace ns3 { |
44 | 46 |
| 47 std::ostream&· |
| 48 operator<< (std::ostream& os, const SPFVertex::NodeExit_t& exit) |
| 49 { |
| 50 os << "(" << exit.first << " ," << exit.second << ")"; |
| 51 return os; |
| 52 } |
| 53 |
| 54 std::ostream&· |
| 55 operator<< (std::ostream& os, const SPFVertex::ListOfSPFVertex_t& vs) |
| 56 { |
| 57 typedef SPFVertex::ListOfSPFVertex_t::const_iterator CIter_t; |
| 58 os << "{"; |
| 59 for (CIter_t iter = vs.begin (); iter != vs.end ();) |
| 60 { |
| 61 os << (*iter)->m_vertexId; |
| 62 if (++iter != vs.end ())· |
| 63 { |
| 64 os << ", "; |
| 65 } |
| 66 else· |
| 67 {· |
| 68 break; |
| 69 } |
| 70 } |
| 71 os << "}"; |
| 72 return os; |
| 73 } |
| 74 |
45 // --------------------------------------------------------------------------- | 75 // --------------------------------------------------------------------------- |
46 // | 76 // |
47 // SPFVertex Implementation | 77 // SPFVertex Implementation |
48 // | 78 // |
49 // --------------------------------------------------------------------------- | 79 // --------------------------------------------------------------------------- |
50 | 80 |
51 SPFVertex::SPFVertex () :· | 81 SPFVertex::SPFVertex () :· |
52 m_vertexType (VertexUnknown),· | 82 m_vertexType (VertexUnknown),· |
53 m_vertexId ("255.255.255.255"),· | 83 m_vertexId ("255.255.255.255"),· |
54 m_lsa (0), | 84 m_lsa (0), |
55 m_distanceFromRoot (SPF_INFINITY),· | 85 m_distanceFromRoot (SPF_INFINITY),· |
56 m_rootOif (SPF_INFINITY), | 86 m_rootOif (SPF_INFINITY), |
57 m_nextHop ("0.0.0.0"), | 87 m_nextHop ("0.0.0.0"), |
58 m_parent (0), | 88 m_parents (), |
59 m_children (), | 89 m_children (), |
60 m_vertexProcessed (false) | 90 m_vertexProcessed (false) |
61 { | 91 { |
62 NS_LOG_FUNCTION_NOARGS (); | 92 NS_LOG_FUNCTION_NOARGS (); |
63 } | 93 } |
64 | 94 |
65 SPFVertex::SPFVertex (GlobalRoutingLSA* lsa) :· | 95 SPFVertex::SPFVertex (GlobalRoutingLSA* lsa) :· |
66 m_vertexId (lsa->GetLinkStateId ()), | 96 m_vertexId (lsa->GetLinkStateId ()), |
67 m_lsa (lsa), | 97 m_lsa (lsa), |
68 m_distanceFromRoot (SPF_INFINITY),· | 98 m_distanceFromRoot (SPF_INFINITY),· |
69 m_rootOif (SPF_INFINITY), | 99 m_rootOif (SPF_INFINITY), |
70 m_nextHop ("0.0.0.0"), | 100 m_nextHop ("0.0.0.0"), |
71 m_parent (0), | 101 m_parents (), |
72 m_children (), | 102 m_children (), |
73 m_vertexProcessed (false) | 103 m_vertexProcessed (false) |
74 { | 104 { |
75 NS_LOG_FUNCTION_NOARGS (); | 105 NS_LOG_FUNCTION_NOARGS (); |
| 106 |
76 if (lsa->GetLSType () == GlobalRoutingLSA::RouterLSA)· | 107 if (lsa->GetLSType () == GlobalRoutingLSA::RouterLSA)· |
77 { | 108 { |
78 NS_LOG_LOGIC ("Setting m_vertexType to VertexRouter"); | 109 NS_LOG_LOGIC ("Setting m_vertexType to VertexRouter"); |
79 m_vertexType = SPFVertex::VertexRouter; | 110 m_vertexType = SPFVertex::VertexRouter; |
80 } | 111 } |
81 else if (lsa->GetLSType () == GlobalRoutingLSA::NetworkLSA)· | 112 else if (lsa->GetLSType () == GlobalRoutingLSA::NetworkLSA)· |
82 {· | 113 {· |
83 NS_LOG_LOGIC ("Setting m_vertexType to VertexNetwork"); | 114 NS_LOG_LOGIC ("Setting m_vertexType to VertexNetwork"); |
84 m_vertexType = SPFVertex::VertexNetwork; | 115 m_vertexType = SPFVertex::VertexNetwork; |
85 } | 116 } |
86 } | 117 } |
87 | 118 |
88 SPFVertex::~SPFVertex () | 119 SPFVertex::~SPFVertex () |
89 { | 120 { |
90 NS_LOG_FUNCTION_NOARGS (); | 121 NS_LOG_FUNCTION (m_vertexId); |
91 for ( ListOfSPFVertex_t::iterator i = m_children.begin (); | 122 ·· |
92 i != m_children.end (); | 123 NS_LOG_LOGIC ("Children vertices - " << m_children); |
93 i++) | 124 NS_LOG_LOGIC ("Parent verteices - " << m_parents); |
94 { | 125 |
95 SPFVertex *p = *i; | 126 // find this node from all its parents and remove the entry of this node |
| 127 // from all its parents |
| 128 for (ListOfSPFVertex_t::iterator piter = m_parents.begin ();· |
| 129 piter != m_parents.end ();· |
| 130 piter++) |
| 131 { |
| 132 // remove the current vertex from its parent's children list. Check |
| 133 // if the size of the list is reduced, or the child<->parent relation |
| 134 // is not bidirectional |
| 135 uint32_t orgCount = (*piter)->m_children.size (); |
| 136 (*piter)->m_children.remove (this); |
| 137 uint32_t newCount = (*piter)->m_children.size (); |
| 138 if (orgCount > newCount) |
| 139 { |
| 140 NS_ASSERT_MSG (orgCount > newCount, "Unable to find the current vertex
from its parents --- impossible!"); |
| 141 } |
| 142 } |
| 143 |
| 144 // delete children |
| 145 while (m_children.size () > 0) |
| 146 { |
| 147 // pop out children one by one. Some children may disapper· |
| 148 // when deleting some other children in the list. As a result, |
| 149 // it is necessary to use pop to walk through all children, instead |
| 150 // of using iterator. |
| 151 // |
| 152 // Note that m_children.pop_front () is not necessary as this |
| 153 // p is removed from the children list when p is deleted |
| 154 SPFVertex* p = m_children.front (); |
| 155 // 'p' == 0, this child is already deleted by its other parent |
| 156 if (p == 0) continue; |
| 157 NS_LOG_LOGIC ("Parent vertex-" << m_vertexId << " deleting its child verte
x-" << p->GetVertexId ()); |
96 delete p; | 158 delete p; |
97 p = 0; | 159 p = 0; |
98 *i = 0; | |
99 } | 160 } |
100 m_children.clear (); | 161 m_children.clear (); |
| 162 // delete parents |
| 163 m_parents.clear (); |
| 164 // delete root exit direction |
| 165 m_ecmpRootExits.clear (); |
| 166 |
| 167 NS_LOG_LOGIC ("Vertex-" << m_vertexId << " completed deleted"); |
101 } | 168 } |
102 | 169 |
103 void· | 170 void· |
104 SPFVertex::SetVertexType (SPFVertex::VertexType type) | 171 SPFVertex::SetVertexType (SPFVertex::VertexType type) |
105 { | 172 { |
106 NS_LOG_FUNCTION (type); | 173 NS_LOG_FUNCTION (type); |
107 m_vertexType = type; | 174 m_vertexType = type; |
108 } | 175 } |
109 | 176 |
110 SPFVertex::VertexType· | 177 SPFVertex::VertexType· |
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
149 m_distanceFromRoot = distance; | 216 m_distanceFromRoot = distance; |
150 } | 217 } |
151 | 218 |
152 uint32_t | 219 uint32_t |
153 SPFVertex::GetDistanceFromRoot (void) const | 220 SPFVertex::GetDistanceFromRoot (void) const |
154 { | 221 { |
155 NS_LOG_FUNCTION_NOARGS (); | 222 NS_LOG_FUNCTION_NOARGS (); |
156 return m_distanceFromRoot; | 223 return m_distanceFromRoot; |
157 } | 224 } |
158 | 225 |
159 void· | |
160 SPFVertex::SetOutgoingInterfaceId (int32_t id) | |
161 { | |
162 NS_LOG_FUNCTION (id); | |
163 m_rootOif = id; | |
164 } | |
165 | |
166 uint32_t· | |
167 SPFVertex::GetOutgoingInterfaceId (void) const | |
168 { | |
169 NS_LOG_FUNCTION_NOARGS (); | |
170 return m_rootOif; | |
171 } | |
172 | |
173 void· | |
174 SPFVertex::SetNextHop (Ipv4Address nextHop) | |
175 { | |
176 NS_LOG_FUNCTION (nextHop); | |
177 m_nextHop = nextHop; | |
178 } | |
179 | |
180 Ipv4Address | |
181 SPFVertex::GetNextHop (void) const | |
182 { | |
183 NS_LOG_FUNCTION_NOARGS (); | |
184 return m_nextHop; | |
185 } | |
186 | |
187 void | 226 void |
188 SPFVertex::SetParent (SPFVertex* parent) | 227 SPFVertex::SetParent (SPFVertex* parent) |
189 { | 228 { |
190 NS_LOG_FUNCTION (parent); | 229 NS_LOG_FUNCTION (parent); |
191 m_parent = parent; | 230 |
| 231 // always maintain only one parent when using setter/getter methods |
| 232 m_parents.clear (); |
| 233 m_parents.push_back (parent); |
192 } | 234 } |
193 | 235 |
194 SPFVertex*· | 236 SPFVertex*· |
195 SPFVertex::GetParent (void) const | 237 SPFVertex::GetParent (uint32_t i) const |
196 { | 238 { |
197 NS_LOG_FUNCTION_NOARGS (); | 239 NS_LOG_FUNCTION_NOARGS (); |
198 return m_parent; | 240 |
199 } | 241 // If the index i is out-of-range, return 0 and do nothing |
200 | 242 if (m_parents.size () <= i) |
201 uint32_t· | 243 { |
| 244 NS_LOG_LOGIC ("Index to SPFVertex's parent is out-of-range."); |
| 245 return 0; |
| 246 } |
| 247 ListOfSPFVertex_t::const_iterator iter = m_parents.begin (); |
| 248 while (i-- > 0)· |
| 249 { |
| 250 iter++; |
| 251 } |
| 252 return *iter; |
| 253 } |
| 254 |
| 255 void· |
| 256 SPFVertex::MergeParent (const SPFVertex* v) |
| 257 { |
| 258 NS_LOG_FUNCTION (v); |
| 259 |
| 260 NS_LOG_LOGIC ("Before merge, list of parents = " << m_parents); |
| 261 // combine the two lists first, and then remove any duplicated after |
| 262 m_parents.insert (m_parents.end (),· |
| 263 v->m_parents.begin (), v->m_parents.end ()); |
| 264 // remove duplication |
| 265 m_parents.sort (); |
| 266 m_parents.unique (); |
| 267 NS_LOG_LOGIC ("After merge, list of parents = " << m_parents); |
| 268 } |
| 269 |
| 270 void· |
| 271 SPFVertex::SetRootExitDirection (Ipv4Address nextHop, int32_t id) |
| 272 { |
| 273 NS_LOG_FUNCTION (nextHop << id); |
| 274 ·· |
| 275 // always maintain only one root's exit |
| 276 m_ecmpRootExits.clear (); |
| 277 m_ecmpRootExits.push_back (NodeExit_t (nextHop, id)); |
| 278 // update the following in order to be backward compatitable with |
| 279 // GetNextHop and GetOutgoingInterface methods |
| 280 m_nextHop = nextHop; |
| 281 m_rootOif = id; |
| 282 } |
| 283 |
| 284 void· |
| 285 SPFVertex::SetRootExitDirection (SPFVertex::NodeExit_t exit) |
| 286 { |
| 287 NS_LOG_FUNCTION (exit); |
| 288 SetRootExitDirection (exit.first, exit.second); |
| 289 } |
| 290 |
| 291 SPFVertex::NodeExit_t |
| 292 SPFVertex::GetRootExitDirection (uint32_t i) const |
| 293 { |
| 294 NS_LOG_FUNCTION (i); |
| 295 typedef ListOfNodeExit_t::const_iterator CIter_t; |
| 296 |
| 297 NS_ASSERT_MSG (i < m_ecmpRootExits.size (), "Index out-of-range when accessing
SPFVertex::m_ecmpRootExits!"); |
| 298 CIter_t iter = m_ecmpRootExits.begin (); |
| 299 while (i-- > 0) {iter++;} |
| 300 |
| 301 return *iter; |
| 302 } |
| 303 |
| 304 SPFVertex::NodeExit_t· |
| 305 SPFVertex::GetRootExitDirection () const |
| 306 { |
| 307 NS_LOG_FUNCTION_NOARGS (); |
| 308 |
| 309 NS_ASSERT_MSG (m_ecmpRootExits.size () <= 1, "Assumed there is at most one exi
t from the root to this vertex"); |
| 310 return GetRootExitDirection (0); |
| 311 } |
| 312 |
| 313 void· |
| 314 SPFVertex::MergeRootExitDirections (const SPFVertex* vertex) |
| 315 { |
| 316 NS_LOG_FUNCTION (vertex); |
| 317 |
| 318 // obtain the external list of exit directions |
| 319 // |
| 320 // Append the external list into 'this' and remove duplication afterward |
| 321 const ListOfNodeExit_t& extList = vertex->m_ecmpRootExits; |
| 322 m_ecmpRootExits.insert (m_ecmpRootExits.end (),· |
| 323 extList.begin(), extList.end ()); |
| 324 m_ecmpRootExits.sort (); |
| 325 m_ecmpRootExits.unique (); |
| 326 } |
| 327 |
| 328 void· |
| 329 SPFVertex::InheritAllRootExitDirections (const SPFVertex* vertex) |
| 330 { |
| 331 NS_LOG_FUNCTION (vertex); |
| 332 |
| 333 // discard all exit direction currently assoicated with this vertex, |
| 334 // and copy all the exit directions from the given vertex |
| 335 if (m_ecmpRootExits.size () > 0) |
| 336 { |
| 337 NS_LOG_WARN ("x root exit directions in this vertex are going to be discar
ded"); |
| 338 } |
| 339 m_ecmpRootExits.clear (); |
| 340 m_ecmpRootExits.insert (m_ecmpRootExits.end (),· |
| 341 vertex->m_ecmpRootExits.begin (), vertex->m_ecmpRootExits.end ()); |
| 342 } |
| 343 |
| 344 uint32_t· |
| 345 SPFVertex::GetNRootExitDirections () const |
| 346 { |
| 347 NS_LOG_FUNCTION_NOARGS (); |
| 348 return m_ecmpRootExits.size (); |
| 349 } |
| 350 |
| 351 uint32_t· |
202 SPFVertex::GetNChildren (void) const | 352 SPFVertex::GetNChildren (void) const |
203 { | 353 { |
204 NS_LOG_FUNCTION_NOARGS (); | 354 NS_LOG_FUNCTION_NOARGS (); |
205 return m_children.size (); | 355 return m_children.size (); |
206 } | 356 } |
207 | 357 |
208 SPFVertex*· | 358 SPFVertex*· |
209 SPFVertex::GetChild (uint32_t n) const | 359 SPFVertex::GetChild (uint32_t n) const |
210 { | 360 { |
211 NS_LOG_FUNCTION (n); | 361 NS_LOG_FUNCTION (n); |
(...skipping 158 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
370 } | 520 } |
371 | 521 |
372 // --------------------------------------------------------------------------- | 522 // --------------------------------------------------------------------------- |
373 // | 523 // |
374 // GlobalRouteManagerImpl Implementation | 524 // GlobalRouteManagerImpl Implementation |
375 // | 525 // |
376 // --------------------------------------------------------------------------- | 526 // --------------------------------------------------------------------------- |
377 | 527 |
378 GlobalRouteManagerImpl::GlobalRouteManagerImpl ()· | 528 GlobalRouteManagerImpl::GlobalRouteManagerImpl ()· |
379 :· | 529 :· |
380 m_spfroot (0) | 530 m_spfroot (0) |
381 { | 531 { |
382 NS_LOG_FUNCTION_NOARGS (); | 532 NS_LOG_FUNCTION_NOARGS (); |
383 m_lsdb = new GlobalRouteManagerLSDB (); | 533 m_lsdb = new GlobalRouteManagerLSDB (); |
384 } | 534 } |
385 | 535 |
386 GlobalRouteManagerImpl::~GlobalRouteManagerImpl () | 536 GlobalRouteManagerImpl::~GlobalRouteManagerImpl () |
387 { | 537 { |
388 NS_LOG_FUNCTION_NOARGS (); | 538 NS_LOG_FUNCTION_NOARGS (); |
389 if (m_lsdb) | 539 if (m_lsdb) |
390 { | 540 { |
(...skipping 139 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
530 // algorithm then iterates again. It terminates when the candidate | 680 // algorithm then iterates again. It terminates when the candidate |
531 // list becomes empty.· | 681 // list becomes empty.· |
532 // | 682 // |
533 void | 683 void |
534 GlobalRouteManagerImpl::InitializeRoutes () | 684 GlobalRouteManagerImpl::InitializeRoutes () |
535 { | 685 { |
536 NS_LOG_FUNCTION_NOARGS (); | 686 NS_LOG_FUNCTION_NOARGS (); |
537 // | 687 // |
538 // Walk the list of nodes in the system. | 688 // Walk the list of nodes in the system. |
539 // | 689 // |
| 690 NS_LOG_INFO ("About to start SPF calculation"); |
540 NodeList::Iterator listEnd = NodeList::End (); | 691 NodeList::Iterator listEnd = NodeList::End (); |
541 for (NodeList::Iterator i = NodeList::Begin (); i != listEnd; i++) | 692 for (NodeList::Iterator i = NodeList::Begin (); i != listEnd; i++) |
542 { | 693 { |
543 Ptr<Node> node = *i; | 694 Ptr<Node> node = *i; |
544 // | 695 // |
545 // Look for the GlobalRouter interface that indicates that the node is | 696 // Look for the GlobalRouter interface that indicates that the node is |
546 // participating in routing. | 697 // participating in routing. |
547 // | 698 // |
548 Ptr<GlobalRouter> rtr =· | 699 Ptr<GlobalRouter> rtr =· |
549 node->GetObject<GlobalRouter> (); | 700 node->GetObject<GlobalRouter> (); |
550 | 701 |
551 // Ignore nodes that are not assigned to our systemId (distributed sim) | 702 // Ignore nodes that are not assigned to our systemId (distributed sim) |
552 if (node->GetSystemId () != MPIInterface::Rank ()) continue; | 703 if (node->GetSystemId () != MpiInterface::GetSystemId ()) |
| 704 { |
| 705 continue; |
| 706 } |
553 ······ | 707 ······ |
554 // | 708 // |
555 // if the node has a global router interface, then run the global routing | 709 // if the node has a global router interface, then run the global routing |
556 // algorithms. | 710 // algorithms. |
557 // | 711 // |
558 if (rtr && rtr->GetNumLSAs () ) | 712 if (rtr && rtr->GetNumLSAs () ) |
559 { | 713 { |
560 SPFCalculate (rtr->GetRouterId ()); | 714 SPFCalculate (rtr->GetRouterId ()); |
561 } | 715 } |
562 } | 716 } |
| 717 NS_LOG_INFO ("Finished SPF calculation"); |
563 } | 718 } |
564 | 719 |
565 // | 720 // |
566 // This method is derived from quagga ospf_spf_next (). See RFC2328 Section· | 721 // This method is derived from quagga ospf_spf_next (). See RFC2328 Section· |
567 // 16.1 (2) for further details. | 722 // 16.1 (2) for further details. |
568 // | 723 // |
569 // We're passed a parameter <v> that is a vertex which is already in the SPF | 724 // We're passed a parameter <v> that is a vertex which is already in the SPF |
570 // tree. A vertex represents a router node. We also get a reference to the | 725 // tree. A vertex represents a router node. We also get a reference to the |
571 // SPF candidate queue, which is a priority queue containing the shortest paths | 726 // SPF candidate queue, which is a priority queue containing the shortest paths |
572 // to the networks we know about. | 727 // to the networks we know about. |
(...skipping 113 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
686 else | 841 else |
687 { | 842 { |
688 distance = v->GetDistanceFromRoot (); | 843 distance = v->GetDistanceFromRoot (); |
689 } | 844 } |
690 | 845 |
691 NS_LOG_LOGIC ("Considering w_lsa " << w_lsa->GetLinkStateId ()); | 846 NS_LOG_LOGIC ("Considering w_lsa " << w_lsa->GetLinkStateId ()); |
692 | 847 |
693 // Is there already vertex w in candidate list? | 848 // Is there already vertex w in candidate list? |
694 if (w_lsa->GetStatus () == GlobalRoutingLSA::LSA_SPF_NOT_EXPLORED) | 849 if (w_lsa->GetStatus () == GlobalRoutingLSA::LSA_SPF_NOT_EXPLORED) |
695 { | 850 { |
696 | |
697 // prepare vertex w | |
698 w = new SPFVertex (w_lsa); | |
699 // Calculate nexthop to w | 851 // Calculate nexthop to w |
700 // We need to figure out how to actually get to the new router represented | 852 // We need to figure out how to actually get to the new router represented |
701 // by <w>. This will (among other things) find the next hop address to send | 853 // by <w>. This will (among other things) find the next hop address to send |
702 // packets destined for this network to, and also find the outbound interface | 854 // packets destined for this network to, and also find the outbound interface |
703 // used to forward the packets. | 855 // used to forward the packets. |
704 // | 856 |
| 857 // prepare vertex w |
| 858 w = new SPFVertex (w_lsa); |
705 if (SPFNexthopCalculation (v, w, l, distance)) | 859 if (SPFNexthopCalculation (v, w, l, distance)) |
706 { | 860 { |
707 w_lsa->SetStatus (GlobalRoutingLSA::LSA_SPF_CANDIDATE); | 861 w_lsa->SetStatus (GlobalRoutingLSA::LSA_SPF_CANDIDATE); |
708 // | 862 // |
709 // Push this new vertex onto the priority queue (ordered by distance from the | 863 // Push this new vertex onto the priority queue (ordered by distance from the |
710 // root node). | 864 // root node). |
711 // | 865 // |
712 candidate.Push (w); | 866 candidate.Push (w); |
713 NS_LOG_LOGIC ("Pushing " <<· | 867 NS_LOG_LOGIC ("Pushing " <<· |
714 w->GetVertexId () << ", parent vertexId: " <<· | 868 w->GetVertexId () << ", parent vertexId: " <<· |
715 v->GetVertexId () << ", distance: " << | 869 v->GetVertexId () << ", distance: " << |
716 w->GetDistanceFromRoot ()); | 870 w->GetDistanceFromRoot ()); |
717 } | 871 } |
| 872 else |
| 873 NS_ASSERT_MSG (0, "SPFNexthopCalculation never "· |
| 874 << "return false, but it does now!"); |
718 } | 875 } |
719 else if (w_lsa->GetStatus () == GlobalRoutingLSA::LSA_SPF_CANDIDATE) | 876 else if (w_lsa->GetStatus () == GlobalRoutingLSA::LSA_SPF_CANDIDATE) |
720 { | 877 { |
721 // | 878 // |
722 // We have already considered the link represented by <w>. What wse have to | 879 // We have already considered the link represented by <w>. What wse have to |
723 // do now is to decide if this new router represents a route with a shorter | 880 // do now is to decide if this new router represents a route with a shorter |
724 // distance metric. | 881 // distance metric. |
725 // | 882 // |
726 // So, locate the vertex in the candidate queue and take a look at the· | 883 // So, locate the vertex in the candidate queue and take a look at the· |
727 // distance. | 884 // distance. |
728 w = candidate.Find (w_lsa->GetLinkStateId ()); | 885 |
729 if (w->GetDistanceFromRoot () < distance) | 886 /* (quagga-0.98.6) W is already on the candidate list; call it cw. |
| 887 * Compare the previously calculated cost (cw->distance) |
| 888 * with the cost we just determined (w->distance) to see |
| 889 * if we've found a shorter path. |
| 890 */ |
| 891 SPFVertex* cw; |
| 892 cw = candidate.Find (w_lsa->GetLinkStateId ()); |
| 893 if (cw->GetDistanceFromRoot () < distance) |
730 { | 894 { |
731 // | 895 // |
732 // This is not a shorter path, so don't do anything. | 896 // This is not a shorter path, so don't do anything. |
733 // | 897 // |
734 continue; | 898 continue; |
735 } | 899 } |
736 else if (w->GetDistanceFromRoot () == distance) | 900 else if (cw->GetDistanceFromRoot () == distance) |
737 { | 901 { |
738 // | 902 // |
739 // This path is one with an equal cost. Do nothing for now -- we're not doing | 903 // This path is one with an equal cost.·· |
740 // equal-cost multipath cases yet. | 904 // |
741 // | 905 NS_LOG_LOGIC ("Equal cost multiple paths found."); |
| 906 |
| 907 // At this point, there are two instances 'w' and 'cw' of the |
| 908 // same vertex, the vertex that is currently being considered |
| 909 // for adding into the shortest path tree. 'w' is the instance |
| 910 // as seen from the root via vertex 'v', and 'cw' is the instance· |
| 911 // as seen from the root via some other vertices other than 'v'. |
| 912 // These two instances are being merged in the following code. |
| 913 // In particular, the parent nodes, the next hops, and the root's |
| 914 // output interfaces of the two instances are being merged. |
| 915 //· |
| 916 // Note that this is functionally equivalent to calling |
| 917 // ospf_nexthop_merge (cw->nexthop, w->nexthop) in quagga-0.98.6 |
| 918 // (ospf_spf.c::859), although the detail implementation |
| 919 // is very different from quagga (blame ns3::GlobalRouteManagerImpl) |
| 920 |
| 921 // prepare vertex w |
| 922 w = new SPFVertex (w_lsa); |
| 923 SPFNexthopCalculation (v, w, l, distance); |
| 924 cw->MergeRootExitDirections (w); |
| 925 cw->MergeParent (w); |
| 926 // SPFVertexAddParent (w) is necessary as the destructor of· |
| 927 // SPFVertex checks if the vertex and its parent is linked |
| 928 // bidirectionally |
| 929 SPFVertexAddParent (w); |
| 930 delete w; |
742 } | 931 } |
743 else | 932 else // cw->GetDistanceFromRoot () > w->GetDistanceFromRoot () |
744 { | 933 { |
745 //· | 934 //· |
746 // this path represents a new, lower-cost path to <w> (the vertex we found in | 935 // this path represents a new, lower-cost path to <w> (the vertex we found in |
747 // the current link record of the link state advertisement of the current root | 936 // the current link record of the link state advertisement of the current root |
748 // (vertex <v>) | 937 // (vertex <v>) |
749 // | 938 // |
750 // N.B. the nexthop_calculation is conditional, if it finds a valid nexthop | 939 // N.B. the nexthop_calculation is conditional, if it finds a valid nexthop |
751 // it will call spf_add_parents, which will flush the old parents | 940 // it will call spf_add_parents, which will flush the old parents |
752 // | 941 // |
753 if (SPFNexthopCalculation (v, w, l, distance)) | 942 if (SPFNexthopCalculation (v, cw, l, distance)) |
754 { | 943 { |
755 // | 944 // |
756 // If we've changed the cost to get to the vertex represented by <w>, we· | 945 // If we've changed the cost to get to the vertex represented by <w>, we· |
757 // must reorder the priority queue keyed to that cost. | 946 // must reorder the priority queue keyed to that cost. |
758 // | 947 // |
759 candidate.Reorder (); | 948 candidate.Reorder (); |
760 } | 949 } |
761 } // new lower cost path found | 950 } // new lower cost path found·· |
762 } // end W is already on the candidate list | 951 } // end W is already on the candidate list |
763 } // end loop over the links in V's LSA | 952 } // end loop over the links in V's LSA |
764 } | 953 } |
765 | 954 |
766 // | 955 // |
767 // This method is derived from quagga ospf_nexthop_calculation() 16.1.1.·· | 956 // This method is derived from quagga ospf_nexthop_calculation() 16.1.1.·· |
768 // | 957 // |
769 // Calculate nexthop from root through V (parent) to vertex W (destination) | 958 // Calculate nexthop from root through V (parent) to vertex W (destination) |
770 // with given distance from root->W. | 959 // with given distance from root->W. |
771 // | 960 // |
(...skipping 73 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
845 // At this point, <l> is the Global Router Link Record describing the point- | 1034 // At this point, <l> is the Global Router Link Record describing the point- |
846 // to point link from <v> to <w> from the perspective of <v>; and <linkRemote> | 1035 // to point link from <v> to <w> from the perspective of <v>; and <linkRemote> |
847 // is the Global Router Link Record describing that same link from the· | 1036 // is the Global Router Link Record describing that same link from the· |
848 // perspective of <w> (back to <v>). Now we can just copy the next hop· | 1037 // perspective of <w> (back to <v>). Now we can just copy the next hop· |
849 // address from the m_linkData member variable. | 1038 // address from the m_linkData member variable. |
850 //· | 1039 //· |
851 // The next hop member variable we put in <w> has the sense "in order to get | 1040 // The next hop member variable we put in <w> has the sense "in order to get |
852 // from the root node to the host represented by vertex <w>, you have to send | 1041 // from the root node to the host represented by vertex <w>, you have to send |
853 // the packet to the next hop address specified in w->m_nextHop. | 1042 // the packet to the next hop address specified in w->m_nextHop. |
854 // | 1043 // |
855 w->SetNextHop (linkRemote->GetLinkData ()); | 1044 Ipv4Address nextHop = linkRemote->GetLinkData (); |
856 //· | 1045 //· |
857 // Now find the outgoing interface corresponding to the point to point link | 1046 // Now find the outgoing interface corresponding to the point to point link |
858 // from the perspective of <v> -- remember that <l> is the link "from" | 1047 // from the perspective of <v> -- remember that <l> is the link "from" |
859 // <v> "to" <w>. | 1048 // <v> "to" <w>. |
860 // | 1049 // |
861 w->SetOutgoingInterfaceId ( | 1050 uint32_t outIf = FindOutgoingInterfaceId (l->GetLinkData ()); |
862 FindOutgoingInterfaceId (l->GetLinkData ())); | 1051 |
| 1052 w->SetRootExitDirection (nextHop, outIf); |
863 w->SetDistanceFromRoot (distance); | 1053 w->SetDistanceFromRoot (distance); |
864 w->SetParent (v); | 1054 w->SetParent (v); |
865 NS_LOG_LOGIC ("Next hop from " <<· | 1055 NS_LOG_LOGIC ("Next hop from " <<· |
866 v->GetVertexId () << " to " << w->GetVertexId () <<· | 1056 v->GetVertexId () << " to " << w->GetVertexId () <<· |
867 " goes through next hop " << w->GetNextHop () << | 1057 " goes through next hop " << nextHop << |
868 " via outgoing interface " << w->GetOutgoingInterfaceId () << | 1058 " via outgoing interface " << outIf << |
869 " with distance " << distance); | 1059 " with distance " << distance); |
870 } // end W is a router vertes | 1060 } // end W is a router vertes |
871 else· | 1061 else· |
872 { | 1062 { |
873 NS_ASSERT (w->GetVertexType () == SPFVertex::VertexNetwork); | 1063 NS_ASSERT (w->GetVertexType () == SPFVertex::VertexNetwork); |
874 // W is a directly connected network; no next hop is required | 1064 // W is a directly connected network; no next hop is required |
875 GlobalRoutingLSA* w_lsa = w->GetLSA (); | 1065 GlobalRoutingLSA* w_lsa = w->GetLSA (); |
876 NS_ASSERT (w_lsa->GetLSType () == GlobalRoutingLSA::NetworkLSA); | 1066 NS_ASSERT (w_lsa->GetLSType () == GlobalRoutingLSA::NetworkLSA); |
877 // Find outgoing interface ID for this network | 1067 // Find outgoing interface ID for this network |
878 w->SetOutgoingInterfaceId ( | 1068 uint32_t outIf = FindOutgoingInterfaceId (w_lsa->GetLinkStateId (),· |
879 FindOutgoingInterfaceId (w_lsa->GetLinkStateId (),· | 1069 w_lsa->GetNetworkLSANetworkMask () ); |
880 w_lsa->GetNetworkLSANetworkMask () )); | 1070 // Set the next hop to 0.0.0.0 meaning "not exist" |
| 1071 Ipv4Address nextHop = Ipv4Address::GetZero (); |
| 1072 w->SetRootExitDirection (nextHop, outIf); |
881 w->SetDistanceFromRoot (distance); | 1073 w->SetDistanceFromRoot (distance); |
882 w->SetParent (v); | 1074 w->SetParent (v); |
883 NS_LOG_LOGIC ("Next hop from " <<· | 1075 NS_LOG_LOGIC ("Next hop from " <<· |
884 v->GetVertexId () << " to network " << w->GetVertexId () <<· | 1076 v->GetVertexId () << " to network " << w->GetVertexId () <<· |
885 " via outgoing interface " << w->GetOutgoingInterfaceId () << | 1077 " via outgoing interface " << outIf << |
886 " with distance " << distance); | 1078 " with distance " << distance); |
887 return 1; | 1079 return 1; |
888 } | 1080 } |
889 } // end v is the root | 1081 } // end v is the root |
890 else if (v->GetVertexType () == SPFVertex::VertexNetwork)· | 1082 else if (v->GetVertexType () == SPFVertex::VertexNetwork)· |
891 { | 1083 { |
892 // See if any of v's parents are the root | 1084 // See if any of v's parents are the root |
893 if (v->GetParent () == m_spfroot) | 1085 if (v->GetParent () == m_spfroot) |
894 { | 1086 { |
895 // 16.1.1 para 5. ...the parent vertex is a network that | 1087 // 16.1.1 para 5. ...the parent vertex is a network that |
896 // directly connects the calculating router to the destination | 1088 // directly connects the calculating router to the destination |
897 // router. The list of next hops is then determined by | 1089 // router. The list of next hops is then determined by |
898 // examining the destination's router-LSA... | 1090 // examining the destination's router-LSA... |
899 NS_ASSERT (w->GetVertexType () == SPFVertex::VertexRouter); | 1091 NS_ASSERT (w->GetVertexType () == SPFVertex::VertexRouter); |
900 GlobalRoutingLinkRecord *linkRemote = 0; | 1092 GlobalRoutingLinkRecord *linkRemote = 0; |
901 while ((linkRemote = SPFGetNextLink (w, v, linkRemote))) | 1093 while ((linkRemote = SPFGetNextLink (w, v, linkRemote))) |
902 { | 1094 { |
903 /* ...For each link in the router-LSA that points back to the | 1095 /* ...For each link in the router-LSA that points back to the |
904 * parent network, the link's Link Data field provides the IP | 1096 * parent network, the link's Link Data field provides the IP |
905 * address of a next hop router. The outgoing interface to | 1097 * address of a next hop router. The outgoing interface to |
906 * use can then be derived from the next hop IP address (or· | 1098 * use can then be derived from the next hop IP address (or· |
907 * it can be inherited from the parent network). | 1099 * it can be inherited from the parent network). |
908 */ | 1100 */ |
909 w->SetNextHop (linkRemote->GetLinkData ()); | 1101 Ipv4Address nextHop = linkRemote->GetLinkData (); |
910 w->SetOutgoingInterfaceId (v->GetOutgoingInterfaceId ()); | 1102 uint32_t outIf = v->GetRootExitDirection ().second; |
| 1103 w->SetRootExitDirection (nextHop, outIf); |
911 NS_LOG_LOGIC ("Next hop from " <<· | 1104 NS_LOG_LOGIC ("Next hop from " <<· |
912 v->GetVertexId () << " to " << w->GetVertexId () <<· | 1105 v->GetVertexId () << " to " << w->GetVertexId () <<· |
913 " goes through next hop " << w->GetNextHop () << | 1106 " goes through next hop " << nextHop << |
914 " via outgoing interface " << w->GetOutgoingInterfaceId ()); | 1107 " via outgoing interface " << outIf); |
915 } | 1108 } |
916 } | 1109 } |
917 else· | 1110 else· |
918 { | 1111 { |
919 w->SetNextHop (v->GetNextHop ()); | 1112 w->SetRootExitDirection (v->GetRootExitDirection ()); |
920 w->SetOutgoingInterfaceId (v->GetOutgoingInterfaceId ()); | |
921 } | 1113 } |
922 } | 1114 } |
923 else· | 1115 else· |
924 { | 1116 { |
925 // | 1117 // |
926 // If we're calculating the next hop information from a node (v) that is· | 1118 // If we're calculating the next hop information from a node (v) that is· |
927 // *not* the root, then we need to "inherit" the information needed to | 1119 // *not* the root, then we need to "inherit" the information needed to |
928 // forward the packet from the vertex closer to the root. That is, we'll | 1120 // forward the packet from the vertex closer to the root. That is, we'll |
929 // still send packets to the next hop address of the router adjacent to the | 1121 // still send packets to the next hop address of the router adjacent to the |
930 // root on the path toward <w>. | 1122 // root on the path toward <w>. |
931 // | 1123 // |
932 // Above, when we were considering the root node, we calculated the next hop | 1124 // Above, when we were considering the root node, we calculated the next hop |
933 // address and outgoing interface required to get off of the root network.·· | 1125 // address and outgoing interface required to get off of the root network.·· |
934 // At this point, we are further away from the root network along one of the | 1126 // At this point, we are further away from the root network along one of the |
935 // (shortest) paths. So the next hop and outoing interface remain the same | 1127 // (shortest) paths. So the next hop and outoing interface remain the same |
936 // (are inherited). | 1128 // (are inherited). |
937 // | 1129 // |
938 w->SetNextHop (v->GetNextHop ()); | 1130 w->InheritAllRootExitDirections (v); |
939 w->SetOutgoingInterfaceId (v->GetOutgoingInterfaceId ()); | |
940 } | 1131 } |
941 // | 1132 // |
942 // In all cases, we need valid values for the distance metric and a parent. | 1133 // In all cases, we need valid values for the distance metric and a parent. |
943 // | 1134 // |
944 w->SetDistanceFromRoot (distance); | 1135 w->SetDistanceFromRoot (distance); |
945 w->SetParent (v); | 1136 w->SetParent (v); |
946 | 1137 |
947 return 1; | 1138 return 1; |
948 } | 1139 } |
949 | 1140 |
(...skipping 258 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1208 } | 1399 } |
1209 // | 1400 // |
1210 // Choose the vertex belonging to the candidate list that is closest to the | 1401 // Choose the vertex belonging to the candidate list that is closest to the |
1211 // root, and add it to the shortest-path tree (removing it from the candidate | 1402 // root, and add it to the shortest-path tree (removing it from the candidate |
1212 // list in the process). | 1403 // list in the process). |
1213 // | 1404 // |
1214 // Recall that in the previous step, we created SPFVertex structures for each | 1405 // Recall that in the previous step, we created SPFVertex structures for each |
1215 // of the routers found in the Global Router Link Records and added tehm to· | 1406 // of the routers found in the Global Router Link Records and added tehm to· |
1216 // the candidate list. | 1407 // the candidate list. |
1217 // | 1408 // |
| 1409 NS_LOG_LOGIC (candidate); |
1218 v = candidate.Pop (); | 1410 v = candidate.Pop (); |
1219 NS_LOG_LOGIC ("Popped vertex " << v->GetVertexId ()); | 1411 NS_LOG_LOGIC ("Popped vertex " << v->GetVertexId ()); |
1220 // | 1412 // |
1221 // Update the status field of the vertex to indicate that it is in the SPF | 1413 // Update the status field of the vertex to indicate that it is in the SPF |
1222 // tree. | 1414 // tree. |
1223 // | 1415 // |
1224 v->GetLSA ()->SetStatus (GlobalRoutingLSA::LSA_SPF_IN_SPFTREE); | 1416 v->GetLSA ()->SetStatus (GlobalRoutingLSA::LSA_SPF_IN_SPFTREE); |
1225 // | 1417 // |
1226 // The current vertex has a parent pointer. By calling this rather oddly· | 1418 // The current vertex has a parent pointer. By calling this rather oddly· |
1227 // named method (blame quagga) we add the current vertex to the list of· | 1419 // named method (blame quagga) we add the current vertex to the list of· |
1228 // children of that parent vertex. In the next hop calculation called during | 1420 // children of that parent vertex. In the next hop calculation called during |
1229 // SPFNext, the parent pointer was set but the vertex has been orphaned up | 1421 // SPFNext, the parent pointer was set but the vertex has been orphaned up |
1230 // to now. | 1422 // to now. |
1231 // | 1423 // |
1232 SPFVertexAddParent (v); | 1424 SPFVertexAddParent (v); |
1233 // | 1425 // |
1234 // Note that when there is a choice of vertices closest to the root, network | 1426 // Note that when there is a choice of vertices closest to the root, network |
1235 // vertices must be chosen before router vertices in order to necessarily | 1427 // vertices must be chosen before router vertices in order to necessarily |
1236 // find all equal-cost paths. We don't do this at this moment, we should add | 1428 // find all equal-cost paths.· |
1237 // the treatment above codes. -- kunihiro.· | |
1238 // | 1429 // |
1239 // RFC2328 16.1. (4).· | 1430 // RFC2328 16.1. (4).· |
1240 // | 1431 // |
1241 // This is the method that actually adds the routes. It'll walk the list | 1432 // This is the method that actually adds the routes. It'll walk the list |
1242 // of nodes in the system, looking for the node corresponding to the router | 1433 // of nodes in the system, looking for the node corresponding to the router |
1243 // ID of the root of the tree -- that is the router we're building the routes | 1434 // ID of the root of the tree -- that is the router we're building the routes |
1244 // for. It looks for the Ipv4 interface of that node and remembers it. So | 1435 // for. It looks for the Ipv4 interface of that node and remembers it. So |
1245 // we are only actually adding routes to that one node at the root of the SPF· | 1436 // we are only actually adding routes to that one node at the root of the SPF· |
1246 // tree. | 1437 // tree. |
1247 // | 1438 // |
(...skipping 152 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1400 // Link Records corresponding to links off of that vertex / node. We're going | 1591 // Link Records corresponding to links off of that vertex / node. We're going |
1401 // to be interested in the records corresponding to point-to-point links. | 1592 // to be interested in the records corresponding to point-to-point links. |
1402 // | 1593 // |
1403 NS_ASSERT_MSG (v->GetLSA (),· | 1594 NS_ASSERT_MSG (v->GetLSA (),· |
1404 "GlobalRouteManagerImpl::SPFIntraAddRouter (): " | 1595 "GlobalRouteManagerImpl::SPFIntraAddRouter (): " |
1405 "Expected valid LSA in SPFVertex* v"); | 1596 "Expected valid LSA in SPFVertex* v"); |
1406 Ipv4Mask tempmask = extlsa->GetNetworkLSANetworkMask (); | 1597 Ipv4Mask tempmask = extlsa->GetNetworkLSANetworkMask (); |
1407 Ipv4Address tempip = extlsa->GetLinkStateId (); | 1598 Ipv4Address tempip = extlsa->GetLinkStateId (); |
1408 tempip = tempip.CombineMask (tempmask); | 1599 tempip = tempip.CombineMask (tempmask); |
1409 | 1600 |
1410 NS_LOG_LOGIC (" Node " << node->GetId () << | |
1411 " add route to " << tempip << | |
1412 " with mask " << tempmask << | |
1413 " using next hop " << v->GetNextHop () << | |
1414 " via interface " << v->GetOutgoingInterfaceId ()); | |
1415 // | 1601 // |
1416 // Here's why we did all of that work. We're going to add a host route to the | 1602 // Here's why we did all of that work. We're going to add a host route to the |
1417 // host address found in the m_linkData field of the point-to-point link | 1603 // host address found in the m_linkData field of the point-to-point link |
1418 // record. In the case of a point-to-point link, this is the local IP address | 1604 // record. In the case of a point-to-point link, this is the local IP address |
1419 // of the node connected to the link. Each of these point-to-point links | 1605 // of the node connected to the link. Each of these point-to-point links |
1420 // will correspond to a local interface that has an IP address to which | 1606 // will correspond to a local interface that has an IP address to which |
1421 // the node at the root of the SPF tree can send packets. The vertex <v>· | 1607 // the node at the root of the SPF tree can send packets. The vertex <v>· |
1422 // (corresponding to the node that has these links and interfaces) has· | 1608 // (corresponding to the node that has these links and interfaces) has· |
1423 // an m_nextHop address precalculated for us that is the address to which the | 1609 // an m_nextHop address precalculated for us that is the address to which the |
1424 // root node should send packets to be forwarded to these IP addresses. | 1610 // root node should send packets to be forwarded to these IP addresses. |
1425 // Similarly, the vertex <v> has an m_rootOif (outbound interface index) to | 1611 // Similarly, the vertex <v> has an m_rootOif (outbound interface index) to |
1426 // which the packets should be send for forwarding. | 1612 // which the packets should be send for forwarding. |
1427 // | 1613 // |
1428 Ptr<GlobalRouter> router = node->GetObject<GlobalRouter> (); | 1614 Ptr<GlobalRouter> router = node->GetObject<GlobalRouter> (); |
1429 if (router == 0) | 1615 if (router == 0) |
1430 { | 1616 { |
1431 continue; | 1617 continue; |
1432 } | 1618 } |
1433 Ptr<Ipv4GlobalRouting> gr = router->GetRoutingProtocol (); | 1619 Ptr<Ipv4GlobalRouting> gr = router->GetRoutingProtocol (); |
1434 NS_ASSERT (gr); | 1620 NS_ASSERT (gr); |
1435 if (v->GetOutgoingInterfaceId () >= 0) | 1621 // walk through all next-hop-IPs and out-going-interfaces for reaching |
| 1622 // the stub network gateway 'v' from the root node |
| 1623 for (uint32_t i = 0; i < v->GetNRootExitDirections (); i++) |
1436 { | 1624 { |
1437 gr->AddASExternalRouteTo (tempip, tempmask, v->GetNextHop (), v->G
etOutgoingInterfaceId ()); | 1625 SPFVertex::NodeExit_t exit = v->GetRootExitDirection (i); |
1438 NS_LOG_LOGIC ("Node " << node->GetId () << | 1626 Ipv4Address nextHop = exit.first; |
1439 " add network route to " << tempip << | 1627 int32_t outIf = exit.second; |
1440 " using next hop " << v->GetNextHop () << | 1628 if (outIf >= 0) |
1441 " via interface " << v->GetOutgoingInterfaceId ()); | 1629 { |
1442 } | 1630 gr->AddASExternalRouteTo (tempip, tempmask, nextHop, outIf); |
1443 else | 1631 NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () << |
1444 { | 1632 " add external network route to " << tempip << |
1445 NS_LOG_LOGIC ("Node " << node->GetId () << | 1633 " using next hop " << nextHop << |
1446 " NOT able to add network route to " << tempip << | 1634 " via interface " << outIf); |
1447 " using next hop " << v->GetNextHop () << | 1635 } |
1448 " since outgoing interface id is negative"); | 1636 else |
| 1637 { |
| 1638 NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () << |
| 1639 " NOT able to add network route to " << tempip << |
| 1640 " using next hop " << nextHop << |
| 1641 " since outgoing interface id is negative"); |
| 1642 } |
1449 } | 1643 } |
1450 return; | 1644 return; |
1451 } // if | 1645 } // if |
1452 } // for | 1646 } // for |
1453 } | 1647 } |
1454 | 1648 |
1455 | 1649 |
1456 // Processing logic from RFC 2328, page 166 and quagga ospf_spf_process_stubs () | 1650 // Processing logic from RFC 2328, page 166 and quagga ospf_spf_process_stubs () |
1457 // stub link records will exist for point-to-point interfaces and for | 1651 // stub link records will exist for point-to-point interfaces and for |
1458 // broadcast interfaces for which no neighboring router can be found | 1652 // broadcast interfaces for which no neighboring router can be found |
(...skipping 108 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1567 // adding the routes to. The LSA will have a number of attached Global Router | 1761 // adding the routes to. The LSA will have a number of attached Global Router |
1568 // Link Records corresponding to links off of that vertex / node. We're going | 1762 // Link Records corresponding to links off of that vertex / node. We're going |
1569 // to be interested in the records corresponding to point-to-point links. | 1763 // to be interested in the records corresponding to point-to-point links. |
1570 // | 1764 // |
1571 NS_ASSERT_MSG (v->GetLSA (),· | 1765 NS_ASSERT_MSG (v->GetLSA (),· |
1572 "GlobalRouteManagerImpl::SPFIntraAddRouter (): " | 1766 "GlobalRouteManagerImpl::SPFIntraAddRouter (): " |
1573 "Expected valid LSA in SPFVertex* v"); | 1767 "Expected valid LSA in SPFVertex* v"); |
1574 Ipv4Mask tempmask ("255.255.255.0"); | 1768 Ipv4Mask tempmask ("255.255.255.0"); |
1575 Ipv4Address tempip = l->GetLinkId (); | 1769 Ipv4Address tempip = l->GetLinkId (); |
1576 tempip = tempip.CombineMask (tempmask); | 1770 tempip = tempip.CombineMask (tempmask); |
1577 | |
1578 NS_LOG_LOGIC (" Node " << node->GetId () << | |
1579 " add route to " << tempip << | |
1580 " with mask " << tempmask << | |
1581 " using next hop " << v->GetNextHop () << | |
1582 " via interface " << v->GetOutgoingInterfaceId ()); | |
1583 // | 1771 // |
1584 // Here's why we did all of that work. We're going to add a host route to the | 1772 // Here's why we did all of that work. We're going to add a host route to the |
1585 // host address found in the m_linkData field of the point-to-point link | 1773 // host address found in the m_linkData field of the point-to-point link |
1586 // record. In the case of a point-to-point link, this is the local IP address | 1774 // record. In the case of a point-to-point link, this is the local IP address |
1587 // of the node connected to the link. Each of these point-to-point links | 1775 // of the node connected to the link. Each of these point-to-point links |
1588 // will correspond to a local interface that has an IP address to which | 1776 // will correspond to a local interface that has an IP address to which |
1589 // the node at the root of the SPF tree can send packets. The vertex <v>· | 1777 // the node at the root of the SPF tree can send packets. The vertex <v>· |
1590 // (corresponding to the node that has these links and interfaces) has· | 1778 // (corresponding to the node that has these links and interfaces) has· |
1591 // an m_nextHop address precalculated for us that is the address to which the | 1779 // an m_nextHop address precalculated for us that is the address to which the |
1592 // root node should send packets to be forwarded to these IP addresses. | 1780 // root node should send packets to be forwarded to these IP addresses. |
1593 // Similarly, the vertex <v> has an m_rootOif (outbound interface index) to | 1781 // Similarly, the vertex <v> has an m_rootOif (outbound interface index) to |
1594 // which the packets should be send for forwarding. | 1782 // which the packets should be send for forwarding. |
1595 // | 1783 // |
1596 ·········· | 1784 ·········· |
1597 Ptr<GlobalRouter> router = node->GetObject<GlobalRouter> (); | 1785 Ptr<GlobalRouter> router = node->GetObject<GlobalRouter> (); |
1598 if (router == 0) | 1786 if (router == 0) |
1599 { | 1787 { |
1600 continue; | 1788 continue; |
1601 } | 1789 } |
1602 Ptr<Ipv4GlobalRouting> gr = router->GetRoutingProtocol (); | 1790 Ptr<Ipv4GlobalRouting> gr = router->GetRoutingProtocol (); |
1603 NS_ASSERT (gr); | 1791 NS_ASSERT (gr); |
1604 if (v->GetOutgoingInterfaceId () >= 0) | 1792 // walk through all next-hop-IPs and out-going-interfaces for reaching |
| 1793 // the stub network gateway 'v' from the root node |
| 1794 for (uint32_t i = 0; i < v->GetNRootExitDirections (); i++) |
1605 { | 1795 { |
1606 gr->AddNetworkRouteTo (tempip, tempmask, v->GetNextHop (), v->GetO
utgoingInterfaceId ()); | 1796 SPFVertex::NodeExit_t exit = v->GetRootExitDirection (i); |
1607 NS_LOG_LOGIC ("Node " << node->GetId () << | 1797 Ipv4Address nextHop = exit.first; |
1608 " add network route to " << tempip << | 1798 int32_t outIf = exit.second; |
1609 " using next hop " << v->GetNextHop () << | 1799 if (outIf >= 0) |
1610 " via interface " << v->GetOutgoingInterfaceId ()); | 1800 { |
1611 } | 1801 gr->AddNetworkRouteTo (tempip, tempmask, nextHop, outIf); |
1612 else | 1802 NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () << |
1613 { | 1803 " add network route to " << tempip << |
1614 NS_LOG_LOGIC ("Node " << node->GetId () << | 1804 " using next hop " << nextHop << |
1615 " NOT able to add network route to " << tempip << | 1805 " via interface " << outIf); |
1616 " using next hop " << v->GetNextHop () << | 1806 } |
1617 " since outgoing interface id is negative"); | 1807 else |
| 1808 { |
| 1809 NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () << |
| 1810 " NOT able to add network route to " << tempip << |
| 1811 " using next hop " << nextHop << |
| 1812 " since outgoing interface id is negative"); |
| 1813 } |
1618 } | 1814 } |
1619 return; | 1815 return; |
1620 } // if | 1816 } // if |
1621 } // for | 1817 } // for |
1622 } | 1818 } |
1623 | 1819 |
1624 // | 1820 // |
1625 // Return the interface number corresponding to a given IP address and mask | 1821 // Return the interface number corresponding to a given IP address and mask |
1626 // This is a wrapper around GetInterfaceForPrefix(), but we first | 1822 // This is a wrapper around GetInterfaceForPrefix(), but we first |
1627 // have to find the right node pointer to pass to that function. | 1823 // have to find the right node pointer to pass to that function. |
(...skipping 172 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1800 for (uint32_t j = 0; j < nLinkRecords; ++j) | 1996 for (uint32_t j = 0; j < nLinkRecords; ++j) |
1801 { | 1997 { |
1802 // | 1998 // |
1803 // We are only concerned about point-to-point links | 1999 // We are only concerned about point-to-point links |
1804 // | 2000 // |
1805 GlobalRoutingLinkRecord *lr = lsa->GetLinkRecord (j); | 2001 GlobalRoutingLinkRecord *lr = lsa->GetLinkRecord (j); |
1806 if (lr->GetLinkType () != GlobalRoutingLinkRecord::PointToPoint) | 2002 if (lr->GetLinkType () != GlobalRoutingLinkRecord::PointToPoint) |
1807 { | 2003 { |
1808 continue; | 2004 continue; |
1809 } | 2005 } |
1810 | |
1811 NS_LOG_LOGIC (" Node " << node->GetId () << | |
1812 " add route to " << lr->GetLinkData () << | |
1813 " using next hop " << v->GetNextHop () << | |
1814 " via interface " << v->GetOutgoingInterfaceId ()); | |
1815 // | 2006 // |
1816 // Here's why we did all of that work. We're going to add a host route to the | 2007 // Here's why we did all of that work. We're going to add a host route to the |
1817 // host address found in the m_linkData field of the point-to-point link | 2008 // host address found in the m_linkData field of the point-to-point link |
1818 // record. In the case of a point-to-point link, this is the local IP address | 2009 // record. In the case of a point-to-point link, this is the local IP address |
1819 // of the node connected to the link. Each of these point-to-point links | 2010 // of the node connected to the link. Each of these point-to-point links |
1820 // will correspond to a local interface that has an IP address to which | 2011 // will correspond to a local interface that has an IP address to which |
1821 // the node at the root of the SPF tree can send packets. The vertex <v>· | 2012 // the node at the root of the SPF tree can send packets. The vertex <v>· |
1822 // (corresponding to the node that has these links and interfaces) has· | 2013 // (corresponding to the node that has these links and interfaces) has· |
1823 // an m_nextHop address precalculated for us that is the address to which the | 2014 // an m_nextHop address precalculated for us that is the address to which the |
1824 // root node should send packets to be forwarded to these IP addresses. | 2015 // root node should send packets to be forwarded to these IP addresses. |
1825 // Similarly, the vertex <v> has an m_rootOif (outbound interface index) to | 2016 // Similarly, the vertex <v> has an m_rootOif (outbound interface index) to |
1826 // which the packets should be send for forwarding. | 2017 // which the packets should be send for forwarding. |
1827 // | 2018 // |
1828 Ptr<GlobalRouter> router = node->GetObject<GlobalRouter> (); | 2019 Ptr<GlobalRouter> router = node->GetObject<GlobalRouter> (); |
1829 if (router == 0) | 2020 if (router == 0) |
1830 { | 2021 { |
1831 continue; | 2022 continue; |
1832 } | 2023 } |
1833 Ptr<Ipv4GlobalRouting> gr = router->GetRoutingProtocol (); | 2024 Ptr<Ipv4GlobalRouting> gr = router->GetRoutingProtocol (); |
1834 NS_ASSERT (gr); | 2025 NS_ASSERT (gr); |
1835 if (v->GetOutgoingInterfaceId () >= 0) | 2026 // walk through all available exit directions due to ECMP, |
1836 { | 2027 // and add host route for each of the exit direction toward |
1837 gr->AddHostRouteTo (lr->GetLinkData (), v->GetNextHop (), | 2028 // the vertex 'v' |
1838 v->GetOutgoingInterfaceId ()); | 2029 for (uint32_t i = 0; i < v->GetNRootExitDirections (); i++) |
1839 NS_LOG_LOGIC ("Node " << node->GetId () << | 2030 { |
1840 " adding host route to " << lr->GetLinkData () << | 2031 SPFVertex::NodeExit_t exit = v->GetRootExitDirection (i); |
1841 " using next hop " << v->GetNextHop () << | 2032 Ipv4Address nextHop = exit.first; |
1842 " and outgoing interface " << v->GetOutgoingInterfaceId ()); | 2033 int32_t outIf = exit.second; |
1843 } | 2034 if (outIf >= 0) |
1844 else | 2035 { |
1845 { | 2036 gr->AddHostRouteTo (lr->GetLinkData (), nextHop, |
1846 NS_LOG_LOGIC ("Node " << node->GetId () << | 2037 outIf); |
1847 " NOT able to add host route to " << lr->GetLinkData () << | 2038 NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId ()
<< |
1848 " using next hop " << v->GetNextHop () << | 2039 " adding host route to " << lr->GetLinkData () << |
1849 " since outgoing interface id is negative"); | 2040 " using next hop " << nextHop << |
1850 } | 2041 " and outgoing interface " << outIf); |
| 2042 } |
| 2043 else |
| 2044 { |
| 2045 NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId ()
<< |
| 2046 " NOT able to add host route to " << lr->GetLinkData () << |
| 2047 " using next hop " << nextHop << |
| 2048 " since outgoing interface id is negative " << outIf); |
| 2049 } |
| 2050 } // for all routes from the root the vertex 'v' |
1851 } | 2051 } |
1852 // | 2052 // |
1853 // Done adding the routes for the selected node. | 2053 // Done adding the routes for the selected node. |
1854 // | 2054 // |
1855 return; | 2055 return; |
1856 } | 2056 } |
1857 } | 2057 } |
1858 } | 2058 } |
1859 void | 2059 void |
1860 GlobalRouteManagerImpl::SPFIntraAddTransit (SPFVertex* v) | 2060 GlobalRouteManagerImpl::SPFIntraAddTransit (SPFVertex* v) |
(...skipping 68 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1929 Ipv4Mask tempmask = lsa->GetNetworkLSANetworkMask (); | 2129 Ipv4Mask tempmask = lsa->GetNetworkLSANetworkMask (); |
1930 Ipv4Address tempip = lsa->GetLinkStateId (); | 2130 Ipv4Address tempip = lsa->GetLinkStateId (); |
1931 tempip = tempip.CombineMask (tempmask); | 2131 tempip = tempip.CombineMask (tempmask); |
1932 Ptr<GlobalRouter> router = node->GetObject<GlobalRouter> (); | 2132 Ptr<GlobalRouter> router = node->GetObject<GlobalRouter> (); |
1933 if (router == 0) | 2133 if (router == 0) |
1934 { | 2134 { |
1935 continue; | 2135 continue; |
1936 } | 2136 } |
1937 Ptr<Ipv4GlobalRouting> gr = router->GetRoutingProtocol (); | 2137 Ptr<Ipv4GlobalRouting> gr = router->GetRoutingProtocol (); |
1938 NS_ASSERT (gr); | 2138 NS_ASSERT (gr); |
1939 if (v->GetOutgoingInterfaceId () >= 0) | 2139 // walk through all available exit directions due to ECMP, |
1940 { | 2140 // and add host route for each of the exit direction toward |
1941 gr->AddNetworkRouteTo (tempip, tempmask, v->GetNextHop (), | 2141 // the vertex 'v' |
1942 v->GetOutgoingInterfaceId ()); | 2142 for (uint32_t i = 0; i < v->GetNRootExitDirections (); i++) |
1943 NS_LOG_LOGIC ("Node " << node->GetId () << | 2143 { |
1944 " add network route to " << tempip << | 2144 SPFVertex::NodeExit_t exit = v->GetRootExitDirection (i); |
1945 " using next hop " << v->GetNextHop () << | 2145 Ipv4Address nextHop = exit.first; |
1946 " via interface " << v->GetOutgoingInterfaceId ()); | 2146 int32_t outIf = exit.second; |
1947 } | 2147 |
1948 else | 2148 if (outIf >= 0) |
1949 { | 2149 { |
1950 NS_LOG_LOGIC ("Node " << node->GetId () << | 2150 gr->AddNetworkRouteTo (tempip, tempmask, nextHop, outIf); |
1951 " NOT able to add network route to " << tempip << | 2151 NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () << |
1952 " using next hop " << v->GetNextHop () << | 2152 " add network route to " << tempip << |
1953 " since outgoing interface id is negative"); | 2153 " using next hop " << nextHop << |
| 2154 " via interface " << outIf); |
| 2155 } |
| 2156 else |
| 2157 { |
| 2158 NS_LOG_LOGIC ("(Route " << i << ") Node " << node->GetId () << |
| 2159 " NOT able to add network route to " << tempip << |
| 2160 " using next hop " << nextHop << |
| 2161 " since outgoing interface id is negative " << outIf); |
| 2162 } |
1954 } | 2163 } |
1955 } | 2164 } |
1956 }· | 2165 }· |
1957 } | 2166 } |
1958 | 2167 |
1959 // Derived from quagga ospf_vertex_add_parents () | 2168 // Derived from quagga ospf_vertex_add_parents () |
1960 // | 2169 // |
1961 // This is a somewhat oddly named method (blame quagga). Although you might | 2170 // This is a somewhat oddly named method (blame quagga). Although you might |
1962 // expect it to add a parent *to* something, it actually adds a vertex | 2171 // expect it to add a parent *to* something, it actually adds a vertex |
1963 // to the list of children *in* each of its parents.· | 2172 // to the list of children *in* each of its parents.· |
1964 // | 2173 // |
1965 // Given a pointer to a vertex, it links back to the vertex's parent that it | 2174 // Given a pointer to a vertex, it links back to the vertex's parent that it |
1966 // already has set and adds itself to that vertex's list of children. | 2175 // already has set and adds itself to that vertex's list of children. |
1967 // | 2176 // |
1968 // For now, only one parent (not doing equal-cost multipath) | |
1969 // | |
1970 void | 2177 void |
1971 GlobalRouteManagerImpl::SPFVertexAddParent (SPFVertex* v) | 2178 GlobalRouteManagerImpl::SPFVertexAddParent (SPFVertex* v) |
1972 { | 2179 { |
1973 NS_LOG_FUNCTION (v); | 2180 NS_LOG_FUNCTION (v); |
1974 v->GetParent ()->AddChild (v); | 2181 |
| 2182 for (uint32_t i=0;;) |
| 2183 { |
| 2184 SPFVertex* parent; |
| 2185 // check if all parents of vertex v |
| 2186 if ((parent = v->GetParent (i++)) == 0) break; |
| 2187 parent->AddChild (v); |
| 2188 } |
1975 } | 2189 } |
1976 | 2190 |
1977 } // namespace ns3 | 2191 } // namespace ns3 |
1978 | 2192 |
1979 | 2193 |
1980 #include "ns3/test.h" | 2194 #include "ns3/test.h" |
1981 #include "ns3/simulator.h" | 2195 #include "ns3/simulator.h" |
1982 #include <stdlib.h> // for rand() | 2196 #include <stdlib.h> // for rand() |
1983 | 2197 |
1984 namespace ns3 { | 2198 namespace ns3 { |
(...skipping 194 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2179 { | 2393 { |
2180 public: | 2394 public: |
2181 GlobalRouteManagerImplTestSuite() | 2395 GlobalRouteManagerImplTestSuite() |
2182 : TestSuite("global-route-manager-impl", UNIT) | 2396 : TestSuite("global-route-manager-impl", UNIT) |
2183 { | 2397 { |
2184 AddTestCase(new GlobalRouteManagerImplTestCase()); | 2398 AddTestCase(new GlobalRouteManagerImplTestCase()); |
2185 } | 2399 } |
2186 } g_globalRoutingManagerImplTestSuite; | 2400 } g_globalRoutingManagerImplTestSuite; |
2187 | 2401 |
2188 } // namespace ns3 | 2402 } // namespace ns3 |
LEFT | RIGHT |