#include <LinkStateGraph.h>
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 () | |
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 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.
dtn::LinkStateGraph::LinkStateGraph | ( | ) |
Definition at line 29 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 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::Edge::cost_, 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().
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().
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().