Projet de fin d'année Logiciel < Description du logiciel < > Autres logiciels >

Algorithme de la solution reprise

Description du fonctionnement

L'algorithme de construction suppose que le réseau dont on veut déterminer la topologie ne comporte pas de boucle. Pour cela, il effectue si nécessaire une scission des équipements responsables du problème.

 

Vient ensuite la construction de l'arbre représentant le réseau à partir des informations obtenues. Il s'agit de déterminer les liaisons directes entre équipements, du type nud1-port1 vers nud2-port2. Les liaisons entre équipements ne sont normalement pas orientées et le sont juste pendant la construction de l'arbre pour les besoins de l'algorithme.

Dans un premier temps, seuls les nuds internes de l'arbre sont pris en compte pour la construction, puis les équipements de type station qui sont les feuilles de l'arbre sont finalement placées. Ceci permet de réduire, souvent de manière significative, le nombre d'équipements lors de la construction de l'arbre.

Placement des équipements réseaux

Tout les équipements manipulés ici sont des nuds internes de l'arbre, et on emploiera le terme noeud pour les désigner.

L'algorithme commence pqr positionner tous les équipements dans l'état non testé. Puis une racine est choisie pour l'arbre: il s'agit de la machine depuis laquelle est lancé le programme. C'est depuis cette racine qu'est ensuite lancée la construction.

 

D'un point de vue global, l'algorithme de construction place des équipements dans l'arbre puis s'appelle récursivement sur les fils directs du nud sur lequel il vient d'être appelé, après modification de l'arbre due aux traitements effectués.

Plus précisément, il est appelé sur un équipement donné que l'on nomme N, et procède par étapes:

1. L'algorithme récupère la liste des équipements distants, visibles par le nud N ou voyant N sur l'une de leurs interfaces, et se trouvant encore dans l'état non testé. Le nud N, ainsi que tous les nuds de la liste, sont mis dans l'état testé.

2. Pour chacun d'eux, il lance la procédure de placement dans l'arbre en cours de construction, grâce à la routine host_place_son décrite par la suite. L'arborescence est donc modifiée par l'insertion de nouveaux équipements.

3. Pour finir, l'algorithme est appelé récursivement sur les fils directs du nud N dans l'arbre actuel après modification de l'arbre due aux traitements effectués lors de l'appel sur le nud N.

 

La routine host_place_son prend en paramètre un nud N et un autre nud F et se charge de placer ce dernier dans l'arborescence enracinée en N.

1. Elle commence par récupérer la liste des fils directs de N, liés au port sur lequel est visible F si ce port est connu, sur tous les ports de N sinon. Cette liste peut éventuellement être vide.

2. Pour chacun des équipements F$_i$ de la liste, la fonction tente de déterminer qui de F$_i$ ou de F est le plus proche du nud N. Pour cela, elle fait appel à la routine essentielle more_direct_son.
   • S'il s'agit de F, on met à jour la liaison (N -> F$_i$) en la remplaçant par (F -> F$_i$) et on crée une liaison (N -> F).

   • S'il s'agit de F$_i$, alors F se trouve dans le sous-arbre enraciné en F$_i$ et on appelle donc la fonction host_place_son avec pour arguments F$_i$ et F.

     Ici, on positionne un marqueur permettant de s'assurer que l'on ne rencontre pas deux nuds F$_i$ qui sont plus proches de N que F: ceci est bien sûr impossible, car cela signifierait que F a deux pères alors que l'on s'est assuré d'avoir un arbre et non un graphe. Si malgré tout, on se retrouve dans ce cas avec le marqueur positionné, on n'effectue alors aucun traitement.

   • Si les informations dont on dispose sont insuffisantes pour déterminer les positions relatives des deux fils, on essaye résoudre le problème avec les ancêtres successifs de N. Pour finir, on effectue l'un des deux traitements précédents selon le cas, à moins que l'on n'ait toujours pas réussi à placer F par rapport à F$_i$, auquel cas on ne fait rien.

3. Finalement, si l'on n'a trouvé aucun fils F$_i$ plus proche de N que F, alors F est placé comme fils direct du nud N, en précisant les ports de la liaison s'ils sont connus. Une liaison (N -> F) est donc ajoutée à l'arbre.

 

En ce qui concerne le positionnement relatif de deux fils d'un même nud, la fonction more_direct_son regarde sur quels ports chaque fils voit son père et l'autre fils. Si pour l'un deux les ports sont différents, alors cet équipements se trouve entre les deux autres dans l'arbre.

Placement des feuilles

Ce placement est plus aisé que le précédent et nettement moins critique: en effet, une erreur dans le placement d'une feuille n'affecte que cette dernière.

 

Une fois l'ossature de l'arbre réalisée, on récupère l'ensemble des nuds internes de l'arbre, et on place les feuilles de chacun d'eux grâce à la fonction host_place_all_leaf.

Cette fonction prend pour seul paramètre le nud N pour lequel elle doit placer les feuilles.

1. Elle récupère ensuite la liste de ses ports sur lesquels il voit d'autres nuds de l'arbre, et la liste des feuilles visibles par N ou voyant N sur une de leurs interfaces.

2. Pour chacune des feuilles récupérées, on vérifie qu'elle est vue sur un port libre, et si c'est le cas on crée une liaison directe entre N et cette feuille.

Projet de fin d'année Logiciel < Description du logiciel < > Autres logiciels >