A Discrete-Event Network Simulator
API
global-route-manager-impl.h
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright 2007 University of Washington
4  *
5  * This program is free software; you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License version 2 as
7  * published by the Free Software Foundation;
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software
16  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17  *
18  * Authors: Craig Dowell (craigdo@ee.washington.edu)
19  * Tom Henderson (tomhend@u.washington.edu)
20  */
21 
22 #ifndef GLOBAL_ROUTE_MANAGER_IMPL_H
23 #define GLOBAL_ROUTE_MANAGER_IMPL_H
24 
25 #include <stdint.h>
26 #include <list>
27 #include <queue>
28 #include <map>
29 #include <vector>
30 #include "ns3/object.h"
31 #include "ns3/ptr.h"
32 #include "ns3/ipv4-address.h"
34 
35 namespace ns3 {
36 
37 const uint32_t SPF_INFINITY = 0xffffffff;
38 
39 class CandidateQueue;
40 class Ipv4GlobalRouting;
41 
68 class SPFVertex
69 {
70 public:
78  enum VertexType {
82  };
83 
97  SPFVertex();
98 
115 
123  ~SPFVertex();
124 
134  VertexType GetVertexType (void) const;
135 
145  void SetVertexType (VertexType type);
146 
160  Ipv4Address GetVertexId (void) const;
161 
176  void SetVertexId (Ipv4Address id);
177 
189  GlobalRoutingLSA* GetLSA (void) const;
190 
204  void SetLSA (GlobalRoutingLSA* lsa);
205 
226  uint32_t GetDistanceFromRoot (void) const;
227 
246  void SetDistanceFromRoot (uint32_t distance);
247 
289  void SetRootExitDirection (Ipv4Address nextHop, int32_t id = SPF_INFINITY);
290 
291  typedef std::pair<Ipv4Address, int32_t> NodeExit_t;
292 
341  NodeExit_t GetRootExitDirection (uint32_t i) const;
361  void MergeRootExitDirections (const SPFVertex* vertex);
369  void InheritAllRootExitDirections (const SPFVertex* vertex);
374  uint32_t GetNRootExitDirections () const;
375 
395  SPFVertex* GetParent (uint32_t i = 0) const;
396 
415  void SetParent (SPFVertex* parent);
423  void MergeParent (const SPFVertex* v);
424 
444  uint32_t GetNChildren (void) const;
445 
472  SPFVertex* GetChild (uint32_t n) const;
473 
500  uint32_t AddChild (SPFVertex* child);
501 
509  void SetVertexProcessed (bool value);
510 
518  bool IsVertexProcessed (void) const;
519 
526  void ClearVertexProcessed (void);
527 
528 private:
533  int32_t m_rootOif;
535  typedef std::list< NodeExit_t > ListOfNodeExit_t;
537  typedef std::list<SPFVertex*> ListOfSPFVertex_t;
541 
547  SPFVertex (SPFVertex& v);
548 
556 
564  friend std::ostream& operator<< (std::ostream& os, const SPFVertex::ListOfSPFVertex_t& vs);
565 };
566 
581 {
582 public:
590 
599 
613  void Insert (Ipv4Address addr, GlobalRoutingLSA* lsa);
614 
629  GlobalRoutingLSA* GetLSA (Ipv4Address addr) const;
643 
655  void Initialize ();
656 
668  GlobalRoutingLSA* GetExtLSA (uint32_t index) const;
675  uint32_t GetNumExtLSAs () const;
676 
677 
678 private:
679  typedef std::map<Ipv4Address, GlobalRoutingLSA*> LSDBMap_t;
680  typedef std::pair<Ipv4Address, GlobalRoutingLSA*> LSDBPair_t;
681 
683  std::vector<GlobalRoutingLSA*> m_extdatabase;
684 
691 
699 };
700 
713 {
714 public:
716  virtual ~GlobalRouteManagerImpl ();
724  virtual void DeleteGlobalRoutes ();
725 
730  virtual void BuildGlobalRoutingDatabase ();
731 
736  virtual void InitializeRoutes ();
737 
742 
747  void DebugSPFCalculate (Ipv4Address root);
748 
749 private:
758 
768 
771 
782  bool CheckForStubNode (Ipv4Address root);
783 
790  void SPFCalculate (Ipv4Address root);
791 
801  void SPFProcessStubs (SPFVertex* v);
802 
809  void ProcessASExternals (SPFVertex* v, GlobalRoutingLSA* extlsa);
810 
832  void SPFNext (SPFVertex* v, CandidateQueue& candidate);
833 
848  GlobalRoutingLinkRecord* l, uint32_t distance);
849 
864  void SPFVertexAddParent (SPFVertex* v);
865 
886  GlobalRoutingLinkRecord* prev_link);
887 
910  void SPFIntraAddRouter (SPFVertex* v);
911 
917  void SPFIntraAddTransit (SPFVertex* v);
918 
926 
933  void SPFAddASExternal (GlobalRoutingLSA *extlsa, SPFVertex *v);
934 
948  Ipv4Mask amask = Ipv4Mask ("255.255.255.255"));
949 };
950 
951 } // namespace ns3
952 
953 #endif /* GLOBAL_ROUTE_MANAGER_IMPL_H */
int32_t FindOutgoingInterfaceId(Ipv4Address a, Ipv4Mask amask=Ipv4Mask("255.255.255.255"))
Return the interface number corresponding to a given IP address and mask.
GlobalRoutingLSA * GetLSA(Ipv4Address addr) const
Look up the Link State Advertisement associated with the given link state ID (address).
ListOfSPFVertex_t m_parents
parent list
void SPFAddASExternal(GlobalRoutingLSA *extlsa, SPFVertex *v)
Add an external route to the routing tables.
uint32_t m_distanceFromRoot
Distance from root node.
virtual void DeleteGlobalRoutes()
Delete all static routes on all nodes that have a GlobalRouterInterface.
const uint32_t SPF_INFINITY
"infinite" distance between nodes
uint32_t GetNChildren(void) const
Get the number of children of "this" SPFVertex.
void SetParent(SPFVertex *parent)
Set the pointer to the SPFVector that is the parent of "this" SPFVertex.
a class to represent an Ipv4 address mask
Definition: ipv4-address.h:269
~SPFVertex()
Destroy an SPFVertex (Shortest Path First Vertex).
void SPFIntraAddRouter(SPFVertex *v)
Add a host route to the routing tables.
GlobalRouteManagerLSDB * m_lsdb
the Link State DataBase (LSDB) of the Global Route Manager
void ProcessASExternals(SPFVertex *v, GlobalRoutingLSA *extlsa)
Process Autonomous Systems (AS) External LSA.
NodeExit_t GetRootExitDirection() const
Obtain a pair indicating the exit direction from the root.
std::list< SPFVertex * > ListOfSPFVertex_t
container of SPFVertexes
void SPFIntraAddStub(GlobalRoutingLinkRecord *l, SPFVertex *v)
Add a stub to the routing tables.
uint32_t GetDistanceFromRoot(void) const
Get the distance from the root vertex to "this" SPFVertex object.
VertexType m_vertexType
Vertex type.
void InheritAllRootExitDirections(const SPFVertex *vertex)
Inherit all root exit directions from a given vertex to &#39;this&#39; vertex.
void SPFProcessStubs(SPFVertex *v)
Process Stub nodes.
void MergeParent(const SPFVertex *v)
Merge the Parent list from the v into this vertex.
std::vector< GlobalRoutingLSA * > m_extdatabase
database of External Link State Advertisements
LSDBMap_t m_database
database of IPv4 addresses / Link State Advertisements
Vertex used in shortest path first (SPF) computations.
GlobalRoutingLinkRecord * SPFGetNextLink(SPFVertex *v, SPFVertex *w, GlobalRoutingLinkRecord *prev_link)
Search for a link between two vertices.
SPFVertex()
Construct an empty ("uninitialized") SPFVertex (Shortest Path First Vertex).
friend std::ostream & operator<<(std::ostream &os, const SPFVertex::ListOfSPFVertex_t &vs)
Stream insertion operator.
GlobalRoutingLSA * m_lsa
Link State Advertisement.
void SetDistanceFromRoot(uint32_t distance)
Set the distance from the root vertex to "this" SPFVertex object.
A global router implementation.
void SPFNext(SPFVertex *v, CandidateQueue &candidate)
Examine the links in v&#39;s LSA and update the list of candidates with any vertices not already on the l...
ListOfNodeExit_t m_ecmpRootExits
store the multiple root&#39;s exits for supporting ECMP
uint32_t GetNRootExitDirections() const
Get the number of exit directions from root for reaching &#39;this&#39; vertex.
A Candidate Queue used in routing calculations.
a Link State Advertisement (LSA) for a router, used in global routing.
ListOfSPFVertex_t m_children
Children list.
uint32_t GetNumExtLSAs() const
Get the number of External Link State Advertisements.
std::pair< Ipv4Address, int32_t > NodeExit_t
IPv4 / interface container for exit nodes.
std::pair< Ipv4Address, GlobalRoutingLSA * > LSDBPair_t
pair of IPv4 addresses / Link State Advertisements
void Initialize()
Set all LSA flags to an initialized state, for SPF computation.
~GlobalRouteManagerLSDB()
Destroy an empty Global Router Manager Link State Database.
Global routing protocol for IPv4 stacks.
GlobalRouteManagerLSDB & operator=(GlobalRouteManagerLSDB &lsdb)
The SPFVertex copy assignment operator is disallowed.
void DebugSPFCalculate(Ipv4Address root)
Debugging routine; call the core SPF from the unit tests.
std::list< NodeExit_t > ListOfNodeExit_t
container of Exit nodes
void SPFIntraAddTransit(SPFVertex *v)
Add a transit to the routing tables.
SPFVertex & operator=(SPFVertex &v)
The SPFVertex copy assignment operator is disallowed.
Ipv4Address GetVertexId(void) const
Get the Vertex ID field of a SPFVertex object.
virtual void InitializeRoutes()
Compute routes using a Dijkstra SPF computation and populate per-node forwarding tables.
int32_t m_rootOif
root Output Interface
void SetVertexType(VertexType type)
Set the Vertex Type field of a SPFVertex object.
Ipv4Address m_vertexId
Vertex ID.
Every class exported by the ns3 library is enclosed in the ns3 namespace.
void DebugUseLsdb(GlobalRouteManagerLSDB *)
Debugging routine; allow client code to supply a pre-built LSDB.
int SPFNexthopCalculation(SPFVertex *v, SPFVertex *w, GlobalRoutingLinkRecord *l, uint32_t distance)
Calculate nexthop from root through V (parent) to vertex W (destination) with given distance from roo...
void SetLSA(GlobalRoutingLSA *lsa)
Set the Global Router Link State Advertisement returned by the Global Router represented by this SPFV...
void SetRootExitDirection(Ipv4Address nextHop, int32_t id=SPF_INFINITY)
Set the IP address and outgoing interface index that should be used to begin forwarding packets from ...
GlobalRoutingLSA * GetLSA(void) const
Get the Global Router Link State Advertisement returned by the Global Router represented by this SPFV...
void SetVertexId(Ipv4Address id)
Set the Vertex ID field of a SPFVertex object.
void Insert(Ipv4Address addr, GlobalRoutingLSA *lsa)
Insert an IP address / Link State Advertisement pair into the Link State Database.
bool CheckForStubNode(Ipv4Address root)
Test if a node is a stub, from an OSPF sense.
void MergeRootExitDirections(const SPFVertex *vertex)
Merge into &#39;this&#39; vertex the list of exit directions from another vertex.
Vertex representing a router in the topology.
bool IsVertexProcessed(void) const
Check the value of the VertexProcessed flag.
Ipv4 addresses are stored in host order in this class.
Definition: ipv4-address.h:41
GlobalRoutingLSA * GetLSAByLinkData(Ipv4Address addr) const
Look up the Link State Advertisement associated with the given link state ID (address).
Ipv4Address m_nextHop
next hop
std::map< Ipv4Address, GlobalRoutingLSA * > LSDBMap_t
container of IPv4 addresses / Link State Advertisements
SPFVertex * GetChild(uint32_t n) const
Get a borrowed SPFVertex pointer to the specified child of "this" SPFVertex.
void ClearVertexProcessed(void)
Clear the value of the VertexProcessed flag.
void SPFCalculate(Ipv4Address root)
Calculate the shortest path first (SPF) tree.
bool m_vertexProcessed
Flag to note whether vertex has been processed in stage two of SPF computation.
The Link State DataBase (LSDB) of the Global Route Manager.
void SetVertexProcessed(bool value)
Set the value of the VertexProcessed flag.
VertexType
Enumeration of the possible types of SPFVertex objects.
virtual void BuildGlobalRoutingDatabase()
Build the routing database by gathering Link State Advertisements from each node exporting a GlobalRo...
SPFVertex * m_spfroot
the root node
SPFVertex * GetParent(uint32_t i=0) const
Get a pointer to the SPFVector that is the parent of "this" SPFVertex.
GlobalRouteManagerLSDB()
Construct an empty Global Router Manager Link State Database.
GlobalRoutingLSA * GetExtLSA(uint32_t index) const
Look up the External Link State Advertisement associated with the given index.
Vertex representing a network in the topology.
GlobalRouteManagerImpl & operator=(GlobalRouteManagerImpl &srmi)
Global Route Manager Implementation assignment operator is disallowed.
VertexType GetVertexType(void) const
Get the Vertex Type field of a SPFVertex object.
void SPFVertexAddParent(SPFVertex *v)
Adds a vertex to the list of children in each of its parents.
uint32_t AddChild(SPFVertex *child)
Get a borrowed SPFVertex pointer to the specified child of "this" SPFVertex.