<< NL_R_DijkstraHTWeight NL_R: Routing NL_R_DijkstraMapNoLeaf >>

NARVAL >> NL_R: Routing > NL_R_DijkstraMap

NL_R_DijkstraMap

Discover a topology in respect with successive routes extracted from a single source by the Dijkstra's algorithm.

Calling Sequence

[T,N] = NL_R_DijkstraMap(G,W)

Arguments

G :

Graph.

W :

Window index.

T :

Evolution of the quantity of the discovered nodes in the topology.

N :

Vector of discovered nodes.

Description

NL_R_DijkstraMap discovers the network topology G in respect with the routes 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. 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.

Examples

n=100;//network size
l=1000;//network squared area side
d=100;//Locality radius
[g]=NL_T_LocalityConnex(n,l,d);//generation of a topology
ind=1;//window index for the graph topology
[f]=NL_G_ShowGraph(g,ind);//topology visualization
w=2;//window index for the results
[t,tn]=NL_R_DijkstraMap(g,w)//application of NL_R_DijkstraMap

Dependency

NL_F_RandVectorNoRepl, NL_R_DijkstraNiNj

Report an issue
<< NL_R_DijkstraHTWeight NL_R: Routing NL_R_DijkstraMapNoLeaf >>