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

Topology algorithm

Description

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:

• it collects
  • the list of the equipments that N see,
  • and the list of the equipments which see N and which are in the non-tested status.

  The equipments in these lists and N are put in tested status.

• Then it try to place each of them, with the function host\_place\_son we'll describe after.
• At last, we apply the algorithm on each direct son.

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.

• It collects the direct son list of N on the port where F is seen if this port is known, otherwise on all the ports. This list can be empty.
• For each of the elements (called Fi) of this list, host\_place\_son try to know the closest equipment (F or Fi) to N:
  • If it's F, the link N~->~Fi is update to F~->~Fi and we create the link N~->~F
  • If it's Fi, then F is under Fi and we apply host\_place\_son with Fi and F as arguments. We use a flag to be sure not to find two node Fi closer to N than F (i.e. F has two father), because we work with trees and this case is impossible. Otherwise we do nothing.
  • Else, we try to solve this problem with ancestors of N. At last, we do nothing.
• If there is no son closer to N than F, then F is 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.

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.