dtn::LinkStateGraph Class Reference

#include <LinkStateGraph.h>

Inheritance diagram for dtn::LinkStateGraph:

oasys::Logger List of all members.

Detailed Description

Encapsulates link state graphs and the operations upon them.

A link state graph consists of Vertices and Edges. A Vertex represents a single endpoint identifier (EID). Every pair of Vertices may have at most one Edge between them, and are associated with an edge cost. Edges represent a connection between two EIDs, usually a physical link, but this is by no means guaranteed.

The use of the names Edge and Vertex is intentional to avoid any confusion between physical nodes, and the Vertices in the graph, as well as physical links and edges in the graph (which may not represent actual links, but rather "virtual" links within the machine).

Example: A network of two machines, uid://1, uid://2. Machines are connected via Ethernet interfaces, eth://00:01, eth://00:02.

Vertices = { uid://1, uid://2, eth://00:01, eth://00:02 }; Edges = { ( uid://1, eth://00:01, 0 ), ( uid://2, eth://00:02, 0 ), ( eth://00:01, eth://00:02, 1 ) }

We use the abstraction of multiple Vertices per Node to make for cleaner routing algorithms.

Note: later on, edges will also have connectivity characteristics, such as priority criteria, a "calendar", and potentially others.

XXX/jakob - is there a case for allowing multiple edges between vertices? is it strong enough to allow the ugliness it causes?

Definition at line 64 of file LinkStateGraph.h.

Public Types

typedef int cost_t
typedef std::set< Vertex * > VertexSet
typedef std::set< Edge * > EdgeSet

Public Member Functions

 LinkStateGraph ()
EdgeaddEdge (Vertex *from, Vertex *to, cost_t cost)
 Adds an edge to the link state graph.
EdgegetEdge (Vertex *from, Vertex *to)
void removeEdge (Edge *to)
 Removes an edge from the link state graph.
VertexgetVertex (const char *eid)
 Finds the Vertex with the given eid, or creates a new one if none is found.
VertexgetMatchingVertex (const char *eid)
 Run the dijkstra algorithm, and then return the best next hop.
VertexfindNextHop (Vertex *from, Vertex *to)
 Run the dijkstra algorithm, and then return the best next hop.
void dumpGraph (oasys::StringBuffer *buf)
 Dump a debug version of the graph to buf.
EdgeSet edges ()

Public Attributes

VertexSet vertices_
 Every eid is represented by its own vertice.
EdgeSet edges_
 There is at most one edge between any pair of vertices.

Classes

class  Edge
class  Vertex


Member Typedef Documentation

typedef int dtn::LinkStateGraph::cost_t

Definition at line 69 of file LinkStateGraph.h.

typedef std::set<Vertex*> dtn::LinkStateGraph::VertexSet

Definition at line 72 of file LinkStateGraph.h.

typedef std::set<Edge*> dtn::LinkStateGraph::EdgeSet

Definition at line 73 of file LinkStateGraph.h.


Constructor & Destructor Documentation

dtn::LinkStateGraph::LinkStateGraph (  ) 

Definition at line 29 of file LinkStateGraph.cc.


Member Function Documentation

LinkStateGraph::Edge * dtn::LinkStateGraph::addEdge ( Vertex from,
Vertex to,
cost_t  cost 
)

Adds an edge to the link state graph.

Definition at line 104 of file LinkStateGraph.cc.

References dtn::LinkStateGraph::Vertex::incoming_edges_, and dtn::LinkStateGraph::Vertex::outgoing_edges_.

Referenced by dtn::LinkStateRouter::LSRegistration::deliver_bundle(), and dtn::LinkStateRouter::handle_contact_up().

LinkStateGraph::Edge * dtn::LinkStateGraph::getEdge ( Vertex from,
Vertex to 
)

Definition at line 117 of file LinkStateGraph.cc.

References dtn::LinkStateGraph::Vertex::outgoing_edges_.

Referenced by dtn::LinkStateRouter::handle_contact_up().

void dtn::LinkStateGraph::removeEdge ( Edge to  ) 

Removes an edge from the link state graph.

Definition at line 124 of file LinkStateGraph.cc.

References ASSERT, dtn::LinkStateGraph::Edge::from_, dtn::LinkStateGraph::Vertex::outgoing_edges_, and dtn::LinkStateGraph::Edge::to_.

Referenced by dtn::LinkStateRouter::LSRegistration::deliver_bundle(), and dtn::LinkStateRouter::handle_contact_down().

LinkStateGraph::Vertex * dtn::LinkStateGraph::getVertex ( const char *  eid  ) 

Finds the Vertex with the given eid, or creates a new one if none is found.

New Vertices are automatically added to the lsg.

Definition at line 172 of file LinkStateGraph.cc.

References log_debug, and vertices_.

Referenced by dtn::LinkStateRouter::LSRegistration::deliver_bundle(), dtn::LinkStateRouter::handle_bundle_received(), dtn::LinkStateRouter::handle_contact_down(), and dtn::LinkStateRouter::handle_contact_up().

LinkStateGraph::Vertex * dtn::LinkStateGraph::getMatchingVertex ( const char *  eid  ) 

Run the dijkstra algorithm, and then return the best next hop.

This is very naive, but at least less bug prone.

Definition at line 139 of file LinkStateGraph.cc.

References log_debug, log_info, pattern(), and vertices_.

Referenced by dtn::LinkStateRouter::handle_bundle_received().

LinkStateGraph::Vertex * dtn::LinkStateGraph::findNextHop ( Vertex from,
Vertex to 
)

Run the dijkstra algorithm, and then return the best next hop.

This is very naive, but at least less bug prone.

Definition at line 35 of file LinkStateGraph.cc.

References ASSERT, dtn::LinkStateGraph::Vertex::dijkstra_distance_, dtn::LinkStateGraph::Vertex::eid_, dtn::LinkStateGraph::Vertex::incoming_edges_, log_debug, log_info, dtn::LinkStateGraph::Vertex::outgoing_edges_, and vertices_.

Referenced by dtn::LinkStateRouter::handle_bundle_received().

void dtn::LinkStateGraph::dumpGraph ( oasys::StringBuffer buf  ) 

Dump a debug version of the graph to buf.

Definition at line 188 of file LinkStateGraph.cc.

References oasys::StringBuffer::appendf(), and edges_.

Referenced by dtn::LinkStateRouter::get_routing_state().

std::set< LinkStateGraph::Edge * > dtn::LinkStateGraph::edges (  ) 

Definition at line 196 of file LinkStateGraph.cc.

References edges_.

Referenced by dtn::LinkStateRouter::handle_contact_up().


Member Data Documentation

VertexSet dtn::LinkStateGraph::vertices_

Every eid is represented by its own vertice.

This means a single machine could potentially be represented by a large number of vertices in the graph.

Definition at line 80 of file LinkStateGraph.h.

Referenced by findNextHop(), getMatchingVertex(), and getVertex().

EdgeSet dtn::LinkStateGraph::edges_

There is at most one edge between any pair of vertices.

Note: machines may have more than one edge between them, but that's because they have several interfaces.

Definition at line 88 of file LinkStateGraph.h.

Referenced by dumpGraph(), and edges().


The documentation for this class was generated from the following files:
Generated on Thu Jun 7 12:54:33 2007 for DTN Reference Implementation by  doxygen 1.5.1