Node:Topology algorithm, Next:, Previous:Database, Up:Top

Topology algorithm


This algorithm which builds the topology suppose there is no loop in the network, and cut the equipement which create the loop if necessary.

After collecting datas, the main operation is the determination of direct link between equipments. The link are non-oriented.

First we just look at internal nodes in order to build the tree, and after that we'll consider and place leaves such as terminal and computer. This allow us to reduce drastically the number of equipments during the building.

Placing internal nodes

We are talking about internal nodes which we are trying to place.

First, each equipment is on status non-tested, and a temporary root is choosen (this is the location on which the software is running).

This algorithm place some equipment, and call itself recursively on each direct son of the node on which it has work after changes it has to do on the tree.

In fact, for a node called N, a call of the algorithm on N will do the following operation:

The arguments of host\_place\_son are 2 nodes, N and F; this function try to place F in the part of the tree (which represents the building in progress) where the root is N.

When we want to know how to place two sons of a node, we compare on which ports each son see his father and the other son.

Placing leaves

For each node we place its leaves seen on free ports (i.e. all the ports where this node don't see another node of the builded tree). We create a link for each leaf.