Discover a topology in respect with successive routes extracted from multiple sources by the Dijkstra's algorithm. Nodes with a degree greater than 1 are considered as a part of the topology. The node degree is used in the normalization process.
[S,T,N] = NL_R_DijkstraMapSourcesD(G,Ns,W)
Graph.
Quantity of network sources.
Window index.
Network sources.
Evolution of the quantity of the discovered nodes in the topology.
Vector of discovered nodes.
NL_R_DijkstraMapSourcesD discovers the network topology G in respect with the route extracted from randomly selected sources S by the Dijkstra's algorithm. Destination nodes are iteratively selected in a random fashion within the set of all remaining nodes. Then at each step of the discovery process, the shortest path between the source and the current destination is performed. The incremental information related to the topology knowledge for each possible source node is collected and stored. The results are plotted into the window W with a normalized scale e.g. the node degree. Nodes with a degree greater than 1 are considered as a part of the topology. The others are the basic nodes (end points). Usually, the global network topology remains unknown from an external point of view because each node is aware of its direct 1-hop neighbors. Thus multiHop communication is handled by nodes in respect with local routing tables.
In the following examples, all blue nodes and links are discovered during the research. The node starts the network discovery process.
selects the list of destination nodes
.
selects the list of destination nodes
.
selects the list of destination nodes
.
selects the list of destination nodes
.
In the following examples, the source node is different. The list of destination nodes is the same.
selects the list of destination nodes
.
selects the list of destination nodes
. The normalized topology discovery metric rating
is performed. d is the current quantity of links already discovered and D corresponds to the total amount of topology links. This function is plotted with a normalized scale e.g. the quantity of network targets divided by the network size. An interesting feature lies on the slope of the curve tangent at the origin. In fact a larger value corresponds to the ability to discover the network topology in a faster way. The line i of T represents the quantity of known topology nodes from the discovery process that started from the node i. Targets (destinations) are randomly selected inside the network. N gathers the chronological order of the nodes discovery.