#include <LinkStateGraph.h>
Inheritance diagram for dtn::LinkStateGraph:
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 85 of file LinkStateGraph.h.
Public Types | |
typedef int | cost_t |
typedef std::set< Vertex * > | VertexSet |
typedef std::set< Edge * > | EdgeSet |
Public Member Functions | |
LinkStateGraph () | |
Edge * | addEdge (Vertex *from, Vertex *to, cost_t cost) |
Adds an edge to the link state graph. | |
Edge * | getEdge (Vertex *from, Vertex *to) |
void | removeEdge (Edge *to) |
Removes an edge from the link state graph. | |
Vertex * | getVertex (const char *eid) |
Finds the Vertex with the given eid, or creates a new one if none is found. | |
Vertex * | getMatchingVertex (const char *eid) |
Run the dijkstra algorithm, and then return the best next hop. | |
Vertex * | findNextHop (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 |
typedef int dtn::LinkStateGraph::cost_t |
Definition at line 90 of file LinkStateGraph.h.
typedef std::set<Vertex*> dtn::LinkStateGraph::VertexSet |
Definition at line 93 of file LinkStateGraph.h.
typedef std::set<Edge*> dtn::LinkStateGraph::EdgeSet |
Definition at line 94 of file LinkStateGraph.h.
dtn::LinkStateGraph::LinkStateGraph | ( | ) |
Definition at line 50 of file LinkStateGraph.cc.
LinkStateGraph::Edge * dtn::LinkStateGraph::addEdge | ( | Vertex * | from, | |
Vertex * | to, | |||
cost_t | cost | |||
) |
Adds an edge to the link state graph.
Definition at line 125 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 138 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 145 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 193 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 160 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 56 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 209 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 217 of file LinkStateGraph.cc.
References edges_.
Referenced by dtn::LinkStateRouter::handle_contact_up().
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 101 of file LinkStateGraph.h.
Referenced by findNextHop(), getMatchingVertex(), and getVertex().
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 109 of file LinkStateGraph.h.
Referenced by dumpGraph(), and edges().