# HG changeset patch # User Craig Dowell # Date 1184910530 25200 # Node ID 6a34eab865da5156930be83d74555e8ccfc1e837 # Parent 4aeb2eaa21a7fd8c79cbf3328430086914cb2840 last parts of general cleaup and commenting diff -r 4aeb2eaa21a7 -r 6a34eab865da src/routing/candidate-queue.h --- a/src/routing/candidate-queue.h Wed Jul 18 16:57:54 2007 -0700 +++ b/src/routing/candidate-queue.h Thu Jul 19 22:48:50 2007 -0700 @@ -24,7 +24,7 @@ namespace ns3 { /** - * \brief a Candidate Queue used in static routing. + * \brief A Candidate Queue used in static routing. * * The CandidateQueue is used in the OSPF shortest path computations. It * is a priority queue used to store candidates for the shortest path to a @@ -62,7 +62,7 @@ * * @see SPFVertex */ - void Clear (void); + void Clear (void); /** * Push a Shortest Path First Vertex pointer onto the queue according to the * priority scheme. @@ -75,7 +75,7 @@ * @see SPFVertex * @param vNew The Shortest Path First Vertex to add to the queue. */ - void Push (SPFVertex *vNew); + void Push (SPFVertex *vNew); /** * Pop the Shortest Path First Vertex pointer at the top of the queue. * The caller is given the responsiblity for releasing the resources @@ -85,7 +85,7 @@ * @see Top () * @returns The Shortest Path First Vertex pointer at the top of the queue. */ - SPFVertex* Pop (void); + SPFVertex* Pop (void); /** * Return the Shortest Path First Vertex pointer at the top of the queue. * This method does not pop the SPFVertex* off of the queue, it simply @@ -95,13 +95,13 @@ * @see Pop () * @returns The Shortest Path First Vertex pointer at the top of the queue. */ - SPFVertex* Top (void) const; + SPFVertex* Top (void) const; /** * Test the Candidate Queue to determine if it is empty. * * @returns True if the queue is empty, false otherwise. */ - bool Empty (void) const; + bool Empty (void) const; /** * Return the number of Shortest Path First Vertex pointers presently * stored in the Candidate Queue. @@ -109,7 +109,7 @@ * @see SPFVertex * @returns The number of SPFVertex* pointers in the Candidate Queue. */ - uint32_t Size (void) const; + uint32_t Size (void) const; /** * Searches the Candidate Queue for a Shortest Path First Vertex pointer * that points to a vertex having the given IP address. @@ -118,7 +118,7 @@ * @param addr The IP address to search for. * @returns The SPFVertex* pointer corresponding to the given IP address. */ - SPFVertex* Find (const Ipv4Address addr) const; + SPFVertex* Find (const Ipv4Address addr) const; /** * Reorders the Candidate Queue according to the priority scheme. On * completion, the top of the queue will hold the Shortest Path First @@ -131,7 +131,7 @@ * * @see SPFVertex */ - void Reorder (void); + void Reorder (void); protected: typedef std::list CandidateList_t; diff -r 4aeb2eaa21a7 -r 6a34eab865da src/routing/static-route-manager.cc --- a/src/routing/static-route-manager.cc Wed Jul 18 16:57:54 2007 -0700 +++ b/src/routing/static-route-manager.cc Thu Jul 19 22:48:50 2007 -0700 @@ -30,6 +30,12 @@ namespace ns3 { +// --------------------------------------------------------------------------- +// +// SPFVertex Implementation +// +// --------------------------------------------------------------------------- + SPFVertex::SPFVertex () : m_vertexType (VertexUnknown), m_vertexId ("255.255.255.255"), @@ -183,6 +189,12 @@ return m_children.size (); } +// --------------------------------------------------------------------------- +// +// StaticRouteManagerLSDB Implementation +// +// --------------------------------------------------------------------------- + StaticRouteManagerLSDB::StaticRouteManagerLSDB () : m_database () @@ -205,7 +217,7 @@ m_database.clear (); } -void + void StaticRouteManagerLSDB::Initialize () { NS_DEBUG ("StaticRouteManagerLSDB::Initialize ()"); @@ -218,19 +230,21 @@ } } -void + void StaticRouteManagerLSDB::Insert (Ipv4Address addr, StaticRouterLSA* lsa) { NS_DEBUG ("StaticRouteManagerLSDB::Insert ()"); m_database.insert (LSDBPair_t (addr, lsa)); } -StaticRouterLSA* -StaticRouteManagerLSDB::GetLSA (Ipv4Address addr) + StaticRouterLSA* +StaticRouteManagerLSDB::GetLSA (Ipv4Address addr) const { NS_DEBUG ("StaticRouteManagerLSDB::GetLSA ()"); - // Look up an LSA by its address - LSDBMap_t::iterator i; +// +// Look up an LSA by its address. +// + LSDBMap_t::const_iterator i; for (i= m_database.begin (); i!= m_database.end (); i++) { if (i->first == addr) @@ -241,7 +255,15 @@ return 0; } -StaticRouteManager::StaticRouteManager () : m_spfroot (0) +// --------------------------------------------------------------------------- +// +// StaticRouteManager Implementation +// +// --------------------------------------------------------------------------- + +StaticRouteManager::StaticRouteManager () +: + m_spfroot (0) { m_lsdb = new StaticRouteManagerLSDB (); } @@ -256,7 +278,7 @@ } } -void + void StaticRouteManager::DebugUseLsdb (StaticRouteManagerLSDB* lsdb) { if (m_lsdb) @@ -273,7 +295,7 @@ // add them to the Link State DataBase (LSDB) from which the routes will // ultimately be computed. // -void + void StaticRouteManager::BuildStaticRoutingDatabase () { NS_DEBUG ("StaticRouteManager::BuildStaticRoutingDatabase()"); @@ -356,7 +378,7 @@ // algorithm then iterates again. It terminates when the candidate // list becomes empty. // -void + void StaticRouteManager::InitializeRoutes () { NS_DEBUG ("StaticRouteManager::InitializeRoutes ()"); @@ -397,7 +419,7 @@ // vertices not already on the list. If a lower-cost path is found to a // vertex already on the candidate list, store the new (lower) cost. // -void + void StaticRouteManager::SPFNext (SPFVertex* v, CandidateQueue& candidate) { SPFVertex* w = 0; @@ -561,7 +583,7 @@ // // For now, this is greatly simplified from the quagga code // -int + int StaticRouteManager::SPFNexthopCalculation ( SPFVertex* v, SPFVertex* w, @@ -684,15 +706,14 @@ // to . If prev_link is not NULL, we return a Static Router Link Record // representing a possible *second* link from to . // -// BUGBUG This seems to be a bug? Shouldn't this function look for any link -// records after pre_link and not just after the first? +// BUGBUG FIXME: This seems to be a bug. Shouldn't this function look for +// any link records after pre_link and not just after the first? // -StaticRouterLinkRecord* + StaticRouterLinkRecord* StaticRouteManager::SPFGetNextLink ( SPFVertex* v, SPFVertex* w, - StaticRouterLinkRecord* prev_link - ) + StaticRouterLinkRecord* prev_link) { NS_DEBUG ("StaticRouteManager::SPFGetNextLink ()"); @@ -760,14 +781,14 @@ // // Used for unit tests. // -void + void StaticRouteManager::DebugSPFCalculate (Ipv4Address root) { SPFCalculate (root); } // quagga ospf_spf_calculate -void + void StaticRouteManager::SPFCalculate (Ipv4Address root) { NS_DEBUG ("StaticRouteManager::SPFCalculate (): " @@ -870,11 +891,11 @@ // root in order of distance from the root. For each of the vertices, we call // SPFIntraAddRouter (). Down in SPFIntraAddRouter, we look at all of the // point-to-point Static Router Link Records (the links to nodes adjacent to -// the node represented by the vertex). We add a link to the IP address +// the node represented by the vertex). We add a route to the IP address // specified by the m_linkData field of each of those link records. This will // be the *local* IP address associated with the interface attached to the // link. We use the outbound interface and next hop information present in -// the vertex . +// the vertex which have possibly been inherited from the root. // // To summarize, we're going to look at the node represented by and loop // through its point-to-point links, adding a *host* route to the local IP @@ -901,11 +922,11 @@ } // -// XXX this should probably be a method on Ipv4 +// BUGBUG FIXME: This should probably be a method on Ipv4 // // Return the interface index corresponding to a given IP address // -uint32_t + uint32_t StaticRouteManager::FindOutgoingInterfaceId (Ipv4Address a) { // @@ -988,7 +1009,7 @@ // a destination IP address, reachable from the root, to which we add a host // route. // -void + void StaticRouteManager::SPFIntraAddRouter (SPFVertex* v) { NS_DEBUG ("StaticRouteManager::SPFIntraAddRouter ()"); @@ -1115,12 +1136,11 @@ // Given a pointer to a vertex, it links back to the vertex's parent that it // already has set and adds itself to that vertex's list of children. // -void +// For now, only one parent (not doing equal-cost multipath) +// + void StaticRouteManager::SPFVertexAddParent (SPFVertex* v) { -// -// For now, only one parent (not doing equal-cost multipath) -// v->GetParent ()->AddChild (v); } @@ -1128,6 +1148,12 @@ #ifdef RUN_SELF_TESTS +// --------------------------------------------------------------------------- +// +// Unit Tests +// +// --------------------------------------------------------------------------- + #include "ns3/test.h" namespace ns3 { @@ -1147,7 +1173,7 @@ // Ptr ipv4 = Create (this); } -TraceResolver* + TraceResolver* StaticRouterTestNode::DoCreateTraceResolver (TraceContext const &context) { return 0; @@ -1168,7 +1194,7 @@ StaticRouteManagerTest::~StaticRouteManagerTest () {} -bool + bool StaticRouteManagerTest::RunTests (void) { bool ok = true; diff -r 4aeb2eaa21a7 -r 6a34eab865da src/routing/static-route-manager.h --- a/src/routing/static-route-manager.h Wed Jul 18 16:57:54 2007 -0700 +++ b/src/routing/static-route-manager.h Thu Jul 19 22:48:50 2007 -0700 @@ -32,140 +32,618 @@ class CandidateQueue; /** - * \brief Vertex used in shortest path first (SPF) computations + * @brief Vertex used in shortest path first (SPF) computations. See RFC 2328, + * Section 16. + * + * Each router in the simulation is associated with an SPFVertex object. When + * calculating routes, each of these routers is, in turn, chosen as the "root" + * of the calculation and routes to all of the other routers are eventually + * saved in the routing tables of each of the chosen nodes. Each of these + * routers in the calculation has an associated SPFVertex. * - * See RFC 2328, Section 16. + * The "Root" vertex is the SPFVertex representing the router that is having + * its routing tables set. The SPFVertex objects representing other routers + * or networks in the simulation are arranged in the SPF tree. It is this + * tree that represents the Shortest Paths to the other networks. + * + * Each SPFVertex has a pointer to the Static Router Link State Advertisement + * (LSA) that its underlying router has exported. Within these LSAs are + * Static Router Link Records that describe the point to point links from the + * underlying router to other nodes (represented by other SPFVertex objects) + * in the simulation topology. The combination of the arrangement of the + * SPFVertex objects in the SPF tree, along with the details of the link + * records that connect them provide the information required to construct the + * required routes. */ class SPFVertex { public: - SPFVertex(); - SPFVertex(StaticRouterLSA*); - ~SPFVertex(); - +/** + * @enum Enumeration of the possible types of SPFVertex objects. Currently + * we use VertexRouter to identify objects that represent a router in the + * simulation topology, and VertexNetwork to identify objects that represent + * a network. + */ enum VertexType { - VertexUnknown = 0, - VertexRouter, - VertexNetwork + VertexUnknown = 0, /**< Uninitialized Link Record */ + VertexRouter, /**< Vertex representing a router in the topology */ + VertexNetwork /**< Vertex representing a network in the topology */ }; - +/** + * @brief Construct an empty ("uninitialized") SPFVertex (Shortest Path First + * Vertex). + * + * The Vertex Type is set to VertexUnknown, the Vertex ID is set to + * 255.255.255.255, and the distance from root is set to infinity + * (UINT32_MAX). The referenced Link State Advertisement (LSA) is set to + * null as is the parent SPFVertex. The outgoing interface index is set to + * infinity, the next hop address is set to 0.0.0.0 and the list of children + * of the SPFVertex is initialized to empty. + * + * @see VertexType + */ + SPFVertex(); +/** + * @brief Construct an initialized SPFVertex (Shortest Path First Vertex). + * + * The Vertex Type is initialized to VertexRouter and the Vertex ID is found + * from the Link State ID of the Link State Advertisement (LSA) passed as a + * parameter. The Link State ID is set to the Router ID of the advertising + * router. The referenced LSA (m_lsa) is set to the given LSA. Other than + * these members, initialization is as in the default constructor. + * of the SPFVertex is initialized to empty. + * + * @see SPFVertex::SPFVertex () + * @see VertexType + * @see StaticRouterLSA + * @param lsa The Link State Advertisement used for finding initial values. + */ + SPFVertex(StaticRouterLSA* lsa); +/** + * @brief Destroy an SPFVertex (Shortest Path First Vertex). + * + * The children vertices of the SPFVertex are recursively deleted. + * + * @see SPFVertex::SPFVertex () + */ + ~SPFVertex(); +/** + * @brief Get the Vertex Type field of a SPFVertex object. + * + * The Vertex Type describes the kind of simulation object a given SPFVertex + * represents. + * + * @see VertexType + * @returns The VertexType of the current SPFVertex object. + */ + VertexType GetVertexType (void) const; +/** + * @brief Set the Vertex Type field of a SPFVertex object. + * + * The Vertex Type describes the kind of simulation object a given SPFVertex + * represents. + * + * @see VertexType + * @param The new VertexType for the current SPFVertex object. + */ void SetVertexType (VertexType type); - VertexType GetVertexType (void) const; - - void SetVertexId (Ipv4Address idV); +/** + * @brief Get the Vertex ID field of a SPFVertex object. + * + * The Vertex ID uniquely identifies the simulation object a given SPFVertex + * represents. Typically, this is the Router ID for SPFVertex objects + * representing routers, and comes from the Link State Advertisement of a + * router aggregated to a node in the simulation. These IDs are allocated + * automatically by the routing environment and look like IP addresses + * beginning at 0.0.0.0 and monotonically increasing as new routers are + * instantiated. + * + * @returns The Ipv4Address Vertex ID of the current SPFVertex object. + */ Ipv4Address GetVertexId (void) const; - +/** + * @brief Set the Vertex ID field of a SPFVertex object. + * + * The Vertex ID uniquely identifies the simulation object a given SPFVertex + * represents. Typically, this is the Router ID for SPFVertex objects + * representing routers, and comes from the Link State Advertisement of a + * router aggregated to a node in the simulation. These IDs are allocated + * automatically by the routing environment and look like IP addresses + * beginning at 0.0.0.0 and monotonically increasing as new routers are + * instantiated. + * + * @param id The new Ipv4Address Vertex ID for the current SPFVertex object. + */ + void SetVertexId (Ipv4Address id); +/** + * @brief Get the Static Router Link State Advertisement returned by the + * Static Router represented by this SPFVertex during the route discovery + * process. + * + * @see StaticRouter + * @see StaticRouterLSA + * @see StaticRouter::DiscoverLSAs () + * @returns A pointer to the StaticRouterLSA found by the router represented + * by this SPFVertex object. + */ + StaticRouterLSA* GetLSA (void) const; +/** + * @brief Set the Static Router Link State Advertisement returned by the + * Static Router represented by this SPFVertex during the route discovery + * process. + * + * @see SPFVertex::GetLSA () + * @see StaticRouter + * @see StaticRouterLSA + * @see StaticRouter::DiscoverLSAs () + * @warning Ownership of the LSA is transferred to the "this" SPFVertex. You + * must not delete the LSA after calling this method. + * @param A pointer to the StaticRouterLSA. + */ void SetLSA (StaticRouterLSA* lsa); - StaticRouterLSA* GetLSA (void) const; - - void SetDistanceFromRoot (uint32_t distance); +/** + * @brief Get the distance from the root vertex to "this" SPFVertex object. + * + * Each router in the simulation is associated with an SPFVertex object. When + * calculating routes, each of these routers is, in turn, chosen as the "root" + * of the calculation and routes to all of the other routers are eventually + * saved in the routing tables of each of the chosen nodes. Each of these + * routers in the calculation has an associated SPFVertex. + * + * The "Root" vertex is then the SPFVertex representing the router that is + * having its routing tables set. The "this" SPFVertex is the vertex to which + * a route is being calculated from the root. The distance from the root that + * we're asking for is the number of hops from the root vertex to the vertex + * in question. + * + * The distance is calculated during route discovery and is stored in a + * member variable. This method simply fetches that value. + * + * @returns The distance, in hops, from the root SPFVertex to "this" SPFVertex. + */ uint32_t GetDistanceFromRoot (void) const; - +/** + * @brief Set the distance from the root vertex to "this" SPFVertex object. + * + * Each router in the simulation is associated with an SPFVertex object. When + * calculating routes, each of these routers is, in turn, chosen as the "root" + * of the calculation and routes to all of the other routers are eventually + * saved in the routing tables of each of the chosen nodes. Each of these + * routers in the calculation has an associated SPFVertex. + * + * The "Root" vertex is then the SPFVertex representing the router that is + * having its routing tables set. The "this" SPFVertex is the vertex to which + * a route is being calculated from the root. The distance from the root that + * we're asking for is the number of hops from the root vertex to the vertex + * in question. + * + * @param distance The distance, in hops, from the root SPFVertex to "this" + * SPFVertex. + */ + void SetDistanceFromRoot (uint32_t distance); +/** + * @brief Get the interface ID that should be used to begin forwarding packets + * from the root SPFVertex to "this" SPFVertex. + * + * Each router node in the simulation is associated with an SPFVertex object. + * When calculating routes, each of these routers is, in turn, chosen as the + * "root" of the calculation and routes to all of the other routers are + * eventually saved in the routing tables of each of the chosen nodes. + * + * The "Root" vertex is then the SPFVertex representing the router that is + * having its routing tables set. The "this" SPFVertex is the vertex that + * represents the host or network to which a route is being calculated from + * the root. The outgoing interface that we're asking for is the interface + * index on the root node that should be used to start packets along the + * path to "this" vertex. + * + * When initializing the root SPFVertex, the interface ID is determined by + * examining the Static Router Link Records of the Link State Advertisement + * generated by the root node's StaticRouter. These interfaces are used to + * forward packets off of the root's network down those links. As other + * vertices are discovered which are further away from the root, they will + * be accessible down one of the paths begun by a Static Router Link Record. + * + * To forward packets to these hosts or networks, the root node must begin + * the forwarding process by sending the packets to the interface of that + * first hop. This means that the first hop address and interface ID must + * be the same for all downstream SPFVertices. We call this "inheriting" + * the interface and next hop. + * + * In this method, the root node is asking, "which of my local interfaces + * should I use to get a packet to the network or host represented by 'this' + * SPFVertex." + * + * @see StaticRouter + * @see StaticRouterLSA + * @see StaticRouterLinkRecord + * @returns The interface index to use when forwarding packets to the host + * or network represented by "this" SPFVertex. + */ + uint32_t GetOutgoingInterfaceId (void) const; +/** + * @brief Set the interface ID that should be used to begin forwarding packets + * from the root SPFVertex to "this" SPFVertex. + * + * Each router node in the simulation is associated with an SPFVertex object. + * When calculating routes, each of these routers is, in turn, chosen as the + * "root" of the calculation and routes to all of the other routers are + * eventually saved in the routing tables of each of the chosen nodes. + * + * The "Root" vertex is then the SPFVertex representing the router that is + * having its routing tables set. The "this" SPFVertex is the vertex that + * represents the host or network to which a route is being calculated from + * the root. The outgoing interface that we're asking for is the interface + * index on the root node that should be used to start packets along the + * path to "this" vertex. + * + * When initializing the root SPFVertex, the interface ID is determined by + * examining the Static Router Link Records of the Link State Advertisement + * generated by the root node's StaticRouter. These interfaces are used to + * forward packets off of the root's network down those links. As other + * vertices are discovered which are further away from the root, they will + * be accessible down one of the paths begun by a Static Router Link Record. + * + * To forward packets to these hosts or networks, the root node must begin + * the forwarding process by sending the packets to the interface of that + * first hop. This means that the first hop address and interface ID must + * be the same for all downstream SPFVertices. We call this "inheriting" + * the interface and next hop. + * + * In this method, we are letting the root node know which of its local + * interfaces it should use to get a packet to the network or host represented + * by "this" SPFVertex. + * + * @see StaticRouter + * @see StaticRouterLSA + * @see StaticRouterLinkRecord + * @param id The interface index to use when forwarding packets to the host or + * network represented by "this" SPFVertex. + */ void SetOutgoingInterfaceId (uint32_t id); - uint32_t GetOutgoingInterfaceId (void) const; - +/** + * @brief Get the IP address that should be used to begin forwarding packets + * from the root SPFVertex to "this" SPFVertex. + * + * Each router node in the simulation is associated with an SPFVertex object. + * When calculating routes, each of these routers is, in turn, chosen as the + * "root" of the calculation and routes to all of the other routers are + * eventually saved in the routing tables of each of the chosen nodes. + * + * The "Root" vertex is then the SPFVertex representing the router that is + * having its routing tables set. The "this" SPFVertex is the vertex that + * represents the host or network to which a route is being calculated from + * the root. The IP address that we're asking for is the address on the + * remote side of a link off of the root node that should be used as the + * destination for packets along the path to "this" vertex. + * + * When initializing the root SPFVertex, the IP address used when forwarding + * packets is determined by examining the Static Router Link Records of the + * Link State Advertisement generated by the root node's StaticRouter. This + * address is used to forward packets off of the root's network down those + * links. As other vertices / nodes are discovered which are further away + * from the root, they will be accessible down one of the paths via a link + * described by one of these Static Router Link Records. + * + * To forward packets to these hosts or networks, the root node must begin + * the forwarding process by sending the packets to a first hop router down + * an interface. This means that the first hop address and interface ID must + * be the same for all downstream SPFVertices. We call this "inheriting" + * the interface and next hop. + * + * In this method, the root node is asking, "which router should I send a + * packet to in order to get that packet to the network or host represented + * by 'this' SPFVertex." + * + * @see StaticRouter + * @see StaticRouterLSA + * @see StaticRouterLinkRecord + * @returns The IP address to use when forwarding packets to the host + * or network represented by "this" SPFVertex. + */ + Ipv4Address GetNextHop (void) const; +/** + * @brief Set the IP address that should be used to begin forwarding packets + * from the root SPFVertex to "this" SPFVertex. + * + * Each router node in the simulation is associated with an SPFVertex object. + * When calculating routes, each of these routers is, in turn, chosen as the + * "root" of the calculation and routes to all of the other routers are + * eventually saved in the routing tables of each of the chosen nodes. + * + * The "Root" vertex is then the SPFVertex representing the router that is + * having its routing tables set. The "this" SPFVertex is the vertex that + * represents the host or network to which a route is being calculated from + * the root. The IP address that we're asking for is the address on the + * remote side of a link off of the root node that should be used as the + * destination for packets along the path to "this" vertex. + * + * When initializing the root SPFVertex, the IP address used when forwarding + * packets is determined by examining the Static Router Link Records of the + * Link State Advertisement generated by the root node's StaticRouter. This + * address is used to forward packets off of the root's network down those + * links. As other vertices / nodes are discovered which are further away + * from the root, they will be accessible down one of the paths via a link + * described by one of these Static Router Link Records. + * + * To forward packets to these hosts or networks, the root node must begin + * the forwarding process by sending the packets to a first hop router down + * an interface. This means that the first hop address and interface ID must + * be the same for all downstream SPFVertices. We call this "inheriting" + * the interface and next hop. + * + * In this method we are telling the root node which router it should send + * should I send a packet to in order to get that packet to the network or + * host represented by 'this' SPFVertex." + * + * @see StaticRouter + * @see StaticRouterLSA + * @see StaticRouterLinkRecord + * @param nextHop The IP address to use when forwarding packets to the host + * or network represented by "this" SPFVertex. + */ void SetNextHop (Ipv4Address nextHop); - Ipv4Address GetNextHop (void) const; - - void SetParent (SPFVertex* parent); +/** + * @brief Get a pointer to the SPFVector that is the parent of "this" + * SPFVertex. + * + * Each router node in the simulation is associated with an SPFVertex object. + * When calculating routes, each of these routers is, in turn, chosen as the + * "root" of the calculation and routes to all of the other routers are + * eventually saved in the routing tables of each of the chosen nodes. + * + * The "Root" vertex is then the SPFVertex representing the router that is + * having its routing tables set and is the root of the SPF tree. + * + * This method returns a pointer to the parent node of "this" SPFVertex + * (both of which reside in that SPF tree). + * + * @returns A pointer to the SPFVertex that is the parent of "this" SPFVertex + * in the SPF tree. + */ SPFVertex* GetParent (void) const; - +/** + * @brief Set the pointer to the SPFVector that is the parent of "this" + * SPFVertex. + * + * Each router node in the simulation is associated with an SPFVertex object. + * When calculating routes, each of these routers is, in turn, chosen as the + * "root" of the calculation and routes to all of the other routers are + * eventually saved in the routing tables of each of the chosen nodes. + * + * The "Root" vertex is then the SPFVertex representing the router that is + * having its routing tables set and is the root of the SPF tree. + * + * This method sets the parent pointer of "this" SPFVertex (both of which + * reside in that SPF tree). + * + * @param parent A pointer to the SPFVertex that is the parent of "this" + * SPFVertex* in the SPF tree. + */ + void SetParent (SPFVertex* parent); +/** + * @brief Get the number of children of "this" SPFVertex. + * + * Each router node in the simulation is associated with an SPFVertex object. + * When calculating routes, each of these routers is, in turn, chosen as the + * "root" of the calculation and routes to all of the other routers are + * eventually saved in the routing tables of each of the chosen nodes. + * + * The "Root" vertex is then the SPFVertex representing the router that is + * having its routing tables set and is the root of the SPF tree. Each vertex + * in the SPF tree can have a number of children that represent host or + * network routes available via that vertex. + * + * This method returns the number of children of "this" SPFVertex (which + * reside in the SPF tree). + * + * @returns The number of children of "this" SPFVertex (which reside in the + * SPF tree). + */ uint32_t GetNChildren (void) const; +/** + * @brief Get a borrowed SPFVertex pointer to the specified child of "this" + * SPFVertex. + * + * Each router node in the simulation is associated with an SPFVertex object. + * When calculating routes, each of these routers is, in turn, chosen as the + * "root" of the calculation and routes to all of the other routers are + * eventually saved in the routing tables of each of the chosen nodes. + * + * The "Root" vertex is then the SPFVertex representing the router that is + * having its routing tables set and is the root of the SPF tree. Each vertex + * in the SPF tree can have a number of children that represent host or + * network routes available via that vertex. + * + * This method the number of children of "this" SPFVertex (which reside in + * the SPF tree. + * + * @see SPFVertex::GetNChildren + * @param n The index (from 0 to the number of children minus 1) of the + * child SPFVertex to return. + * @warning The pointer returned by GetChild () is a borrowed pointer. You + * do not have any ownership of the underlying object and must not delete + * that object. + * @returns A pointer to the specified child SPFVertex (which resides in the + * SPF tree). + */ SPFVertex* GetChild (uint32_t n) const; - +/** + * @brief Get a borrowed SPFVertex pointer to the specified child of "this" + * SPFVertex. + * + * Each router node in the simulation is associated with an SPFVertex object. + * When calculating routes, each of these routers is, in turn, chosen as the + * "root" of the calculation and routes to all of the other routers are + * eventually saved in the routing tables of each of the chosen nodes. + * + * The "Root" vertex is then the SPFVertex representing the router that is + * having its routing tables set and is the root of the SPF tree. Each vertex + * in the SPF tree can have a number of children that represent host or + * network routes available via that vertex. + * + * This method the number of children of "this" SPFVertex (which reside in + * the SPF tree. + * + * @see SPFVertex::GetNChildren + * @param n The index (from 0 to the number of children minus 1) of the + * child SPFVertex to return. + * @warning Ownership of the pointer added to the children of "this" + * SPFVertex is transferred to the "this" SPFVertex. You must not delete the + * (now) child SPFVertex after calling this method. + * @param child A pointer to the SPFVertex (which resides in the SPF tree) to + * be added to the list of children of "this" SPFVertex. + * @returns The number of children of "this" SPFVertex after the addition of + * the new child. + */ uint32_t AddChild (SPFVertex* child); private: VertexType m_vertexType; - Ipv4Address m_vertexId; // router id - StaticRouterLSA* m_lsa; // This pointer owns LSA for mem. mgmt purposes + Ipv4Address m_vertexId; + StaticRouterLSA* m_lsa; uint32_t m_distanceFromRoot; uint32_t m_rootOif; Ipv4Address m_nextHop; - - // need to keep track of current parent vertex SPFVertex* m_parent; - - // m_children lists the leaves from your SPF tree typedef std::list ListOfSPFVertex_t; ListOfSPFVertex_t m_children; /** - * The SPFVertex copy construction is disallowed. There's no need for + * @brief The SPFVertex copy construction is disallowed. There's no need for * it and a compiler provided shallow copy would be wrong. */ SPFVertex (SPFVertex& v); /** - * The SPFVertex copy assignment operator is disallowed. There's no need for - * it and a compiler provided shallow copy would be wrong. + * @brief The SPFVertex copy assignment operator is disallowed. There's no + * need for it and a compiler provided shallow copy would be wrong. */ SPFVertex& operator= (SPFVertex& v); }; /** - * \brief The Link State DataBase (LSDB) of a static router + * @brief The Link State DataBase (LSDB) of the Static Route Manager. + * + * Each node in the simulation participating in static routing has a + * StaticRouter interface. The primary job of this interface is to export + * Static Router Link State Advertisements (LSAs). These advertisements in + * turn contain a number of Static Router Link Records that describe the + * point to point links from the underlying node to other nodes (that will + * also export their own LSAs. + * + * This class implements a searchable database of LSAs gathered from every + * router in the simulation. */ class StaticRouteManagerLSDB { public: +/** + * @brief Construct an empty Static Router Manager Link State Database. + * + * The database map composing the Link State Database is initialized in + * this constructor. + */ StaticRouteManagerLSDB (); +/** + * @brief Destroy an empty Static Router Manager Link State Database. + * + * The database map is walked and all of the Link State Advertisements stored + * in the database are freed; then the database map itself is clear ()ed to + * release any remaining resources. + */ ~StaticRouteManagerLSDB (); +/** + * @brief Insert an IP address / Link State Advertisement pair into the Link + * State Database. + * + * The IPV4 address and the StaticRouterLSA given as parameters are converted + * to an STL pair and are inserted into the database map. + * + * @see StaticRouterLSA + * @see Ipv4Address + * @param addr The IP address associated with the LSA. Typically the Router + * ID. + * @param lsa A pointer to the Link State Advertisement for the router. + */ void Insert(Ipv4Address addr, StaticRouterLSA* lsa); - StaticRouterLSA* GetLSA (Ipv4Address addr); - /** - * \brief Set all LSA flags to an initialized state, for SPF computation - */ +/** + * @brief Look up the Link State Advertisement associated with the given + * IP Address. + * + * The database map is searched for the given IPV4 address and corresponding + * StaticRouterLSA is returned. + * + * @see StaticRouterLSA + * @see Ipv4Address + * @param addr The IP address associated with the LSA. Typically the Router + * ID. + * @returns A pointer to the Link State Advertisement for the router specified + * by the IP address addr. + */ + StaticRouterLSA* GetLSA (Ipv4Address addr) const; +/** + * @brief Set all LSA flags to an initialized state, for SPF computation + * + * This function walks the database and resets the status flags of all of the + * contained Link State Advertisements to LSA_SPF_NOT_EXPLORED. This is done + * prior to each SPF calculation to reset the state of the SPFVertex structures + * that will reference the LSAs during the calculation. + * + * @see StaticRouterLSA + * @see SPFVertex + */ void Initialize (); +private: typedef std::map LSDBMap_t; typedef std::pair LSDBPair_t; + LSDBMap_t m_database; -private: /** - * StaticRouteManagerLSDB copy construction is disallowed. There's no + * @brief StaticRouteManagerLSDB copy construction is disallowed. There's no * need for it and a compiler provided shallow copy would be hopelessly wrong. */ StaticRouteManagerLSDB (StaticRouteManagerLSDB& lsdb); /** - * The SPFVertex copy assignment operator is disallowed. There's no need for - * it and a compiler provided shallow copy would be wrong. + * @brief The SPFVertex copy assignment operator is disallowed. There's no + * need for it and a compiler provided shallow copy would be wrong. */ StaticRouteManagerLSDB& operator= (StaticRouteManagerLSDB& lsdb); }; /** - * \brief A global static router + * @brief A global static router * * This singleton object can query interface each node in the system * for a StaticRouter interface. For those nodes, it fetches one or - * more LSAs and stores them in a local database. Then, it - * can compute shortest paths on a per-node basis to all routers, and - * finally configure each of the node's forwarding tables. + * more Link State Advertisements and stores them in a local database. + * Then, it can compute shortest paths on a per-node basis to all routers, + * and finally configure each of the node's forwarding tables. * - * The design is guided by OSPFv2 RFC 2328 section 16.1.1 - * and quagga ospfd + * The design is guided by OSPFv2 RFC 2328 section 16.1.1 and quagga ospfd. */ class StaticRouteManager : public Object { public: static const InterfaceId iid; StaticRouteManager (); - /** - * \brief Build routing database by gathering LSA from each routing node - */ +/** + * @brief Build the routing database by gathering Link State Advertisements + * from each node exporting a StaticRouter interface. + * + */ virtual void BuildStaticRoutingDatabase(); - /** - * \brief Compute routes using Dijkstra SPF computation, and populate - * per-node forwarding tables - */ +/** + * @brief Compute routes using a Dijkstra SPF computation and populate + * per-node forwarding tables + */ virtual void InitializeRoutes(); - - /** - * \brief Debugging routine; allow client code to supply a pre-built LSDB - */ +/** + * @brief Debugging routine; allow client code to supply a pre-built LSDB + */ void DebugUseLsdb (StaticRouteManagerLSDB*); - /** - * \brief Debugging routine; call the core SPF from the unit tests - */ +/** + * @brief Debugging routine; call the core SPF from the unit tests + */ void DebugSPFCalculate (Ipv4Address root); virtual ~StaticRouteManager (); @@ -174,14 +652,14 @@ private: /** - * Static Route Manager copy construction is disallowed. There's no need for - * it and a compiler provided shallow copy would be hopelessly wrong. + * @brief Static Route Manager copy construction is disallowed. There's no + * need for it and a compiler provided shallow copy would be hopelessly wrong. * */ StaticRouteManager (StaticRouteManager& srm); /** - * Static Router copy assignment operator is disallowed. There's no need for - * it and a compiler provided shallow copy would be hopelessly wrong. + * @brief Static Router copy assignment operator is disallowed. There's no + * need for it and a compiler provided shallow copy would be hopelessly wrong. */ StaticRouteManager& operator= (StaticRouteManager& srm); @@ -196,7 +674,6 @@ StaticRouterLinkRecord* prev_link); void SPFIntraAddRouter(SPFVertex* v); uint32_t FindOutgoingInterfaceId(Ipv4Address a); - }; } // namespace ns3 diff -r 4aeb2eaa21a7 -r 6a34eab865da src/routing/static-router.cc --- a/src/routing/static-router.cc Wed Jul 18 16:57:54 2007 -0700 +++ b/src/routing/static-router.cc Thu Jul 19 22:48:50 2007 -0700 @@ -26,6 +26,12 @@ namespace ns3 { +// --------------------------------------------------------------------------- +// +// StaticRouterLinkRecord Implementation +// +// --------------------------------------------------------------------------- + StaticRouterLinkRecord::StaticRouterLinkRecord () : m_linkId ("0.0.0.0"), @@ -113,6 +119,12 @@ m_metric = metric; } +// --------------------------------------------------------------------------- +// +// StaticRouterLSA Implementation +// +// --------------------------------------------------------------------------- + StaticRouterLSA::StaticRouterLSA() : m_linkStateId("0.0.0.0"), @@ -297,6 +309,12 @@ return os; } +// --------------------------------------------------------------------------- +// +// StaticRouter Implementation +// +// --------------------------------------------------------------------------- + const InterfaceId StaticRouter::iid = MakeInterfaceId ("StaticRouter", Object::iid); diff -r 4aeb2eaa21a7 -r 6a34eab865da src/routing/static-router.h --- a/src/routing/static-router.h Wed Jul 18 16:57:54 2007 -0700 +++ b/src/routing/static-router.h Thu Jul 19 22:48:50 2007 -0700 @@ -60,7 +60,7 @@ */ StaticRouterLinkRecord (); /** - * Construct a fully uninitialized Static Router Link Record. + * Construct an initialized Static Router Link Record. * * @param linkType The type of link record to construct. * @param linkId The link ID for the record. @@ -89,6 +89,8 @@ * * For an OSPF type 3 link (StubNetwork), the Link ID will be the adjacent * neighbor's IP address + * + * @returns The Ipv4Address corresponding to the Link ID field of the record. */ Ipv4Address GetLinkId(void) const; /** @@ -99,6 +101,8 @@ * * For an OSPF type 3 link (StubNetwork), the Link ID must be the adjacent * neighbor's IP address + * + * @param An Ipv4Address to store in the Link ID field of the record. */ void SetLinkId(Ipv4Address addr); /** @@ -109,6 +113,8 @@ * * For an OSPF type 3 link (StubNetwork), the Link Data will be the * network mask + * + * @returns The Ipv4Address corresponding to the Link Data field of the record. */ Ipv4Address GetLinkData(void) const; /** @@ -119,6 +125,8 @@ * * For an OSPF type 3 link (StubNetwork), the Link Data must be set to the * network mask + * + * @param An Ipv4Address to store in the Link Data field of the record. */ void SetLinkData(Ipv4Address addr); /** @@ -128,6 +136,7 @@ * values are defined by OSPF. * * @see LinkType + * @returns The LinkType of the current Static Router Link Record. */ LinkType GetLinkType(void) const; /** @@ -137,6 +146,7 @@ * values are defined by OSPF. * * @see LinkType + * @param linkType The new LinkType for the current Static Router Link Record. */ void SetLinkType(LinkType linkType); /** @@ -147,6 +157,8 @@ * shouldn't use bandwidth as a metric (how does the sum of the bandwidth of * two hops relate to the cost of sending a packet); rather you should use * something like delay. + * + * @returns The metric field of the Static Router Link Record. */ uint32_t GetMetric(void) const; /** @@ -157,6 +169,8 @@ * shouldn't use bandwidth as a metric (how does the sum of the bandwidth of * two hops relate to the cost of sending a packet); rather you should use * something like delay. + * + * @param metric The new metric for the current Static Router Link Record. */ void SetMetric(uint32_t metric);