Node:Topology algorithm, Next:Interface specification, Previous:Database, Up:Top
This algorithm which builds the topology suppose there is no loop
in the network, and
cut the equipement which create the loop
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.
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
will do the following operation:
Nand which are in the
The equipments in these lists and
N are put in
host\_place\_sonwe'll describe after.
The arguments of
host\_place\_son are 2 nodes,
F; this function try to place
F in the part of the tree
(which represents the building in progress) where the root is
Non the port where
Fis seen if this port is known, otherwise on all the ports. This list can be empty.
Fi) of this list,
host\_place\_sontry to know the closest equipment (
F, the link N~->~Fi is update to F~->~Fi and we create the link N~->~F
Fiand we apply
Fas arguments. We use a flag to be sure not to find two node
Fhas two father), because we work with trees and this case is impossible. Otherwise we do nothing.
N. At last, we do nothing.
Fis placed as a direct son of
N, and we give the port of this link if it's known.
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.
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.