Discover a topology in respect with successive routes extracted from a single source by the Dijkstra's algorithm. Nodes with a degree greater than 1 are considered as a part of the topology.
[t,tn] = NARVAL_D_RecDijkstraA(g,w)
network graph.
window index.
evolution of the quantity of the discovered nodes in the topology.
vector of discovered nodes.
NARVAL_D_RecDijkstraA discovers the network topology g in respect with the route extracted from a single source 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. 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 N3 starts the network discovery process.
N3 selects the list of destination nodes [N7,N11,N14,N15,N21].
N3 selects the list of destination nodes [N1,N2,N14,N15,N16].
N3 selects the list of destination nodes [N10,N11,N13,N16,N20].
N3 selects the list of destination nodes [N5,N10,N11,N13,N16].
In the following examples, the source node is different. The list of destination nodes is the same.
N12 selects the list of destination nodes [N5,N10,N11,N13,N16].
N9 selects the list of destination nodes [N5,N10,N11,N13,N16].
The normalized topology discovery metric rating d/D 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. tn gathers the chronological order of the nodes discovery.
Dr. Foued Melakessou
Research Associate
Interdisciplinary Centre for Security, Reliability and Trust
Room F106
University of Luxembourg
6, rue Coudenhove Kalergi
L-1359 Luxembourg-Kirchberg
E-mail: foued.melakessou@uni.lu
Tel: (+352) 46 66 44 5346