TP Routage (Bellman-Ford/RIP)

 

Ce TP propose d'étudier l'algorithme de routage de Bellman-Ford en le simulant avec un programme C.

Etape 1

Programmez l'algorithme tel qu'il a été présenté en TD sous la forme d'une fonction C :

Algorithme de Bellman-Ford (G, s, w)

G : graphe (A, S). (A : ensemble des arcs. S : ensemble des sommets)
s : Noeud source.
w(i,j) : poids de l'arc entre les sommets i et j.
Pred(u) : prédécesseur de u sur le chemin.
L(u): poids du chemin de s à u

/* Initialisation */
Pour chaque sommet v de G faire
	L(v) := +Infini;
	Pred(v) := Nil ;
FinPour
L(s) := 0;

/* Exploration des arcs */
Pour i:=1 à Cardinal(S) - 1 faire
	Pour chaque arc ( u , v ) appartenant à A
		Si L(v) > L(u) + w(u,v) alors
			L(v) := L(u) + w(u,v);
			Pred(v) := u;
		FinSi
	FinPour
FinPour
Pour chaque arc ( u , v ) appartenant à A faire
	si L(v) > L(u) + w(u,v) alors renvoyer FAUX
FinPour
renvoyer VRAI

Programmez un ensemble de fonctions C ayant pour but de permettre à un utilisateur de créer un réseau (choix du nombre de noeuds, définition des arcs avec leur poids), de l'afficher et de le modifier.

Ecrivez un programme principal qui permet d'utiliser les fonctions précédentes, de faire fonctionner l'algorithme de routage sur ce réseau pour chaque noeud et d'afficher les résultats (chemins et longueur calculée de ces chemins).

Notes :

Etape 2

On considère maintenant que chaque noeud ne connaît initialement que les arcs directement connectés à celui-ci et leur poids.

On utilise donc l'algorithme modifié suivant :

G : graphe (A', S). (A' : ensemble des arcs connus. S : ensemble des sommets)
s : Noeud source.
w(i,j) : poids de l'arc entre les sommets i et j.
Succ(u) : Successeur de s sur le chemin de s à u.
L(u): poids du chemin de s à u

/* Initialisation */
Pour chaque sommet v de G faire
	L(v) := +Infini;
	Succ(v) := Nil ;
FinPour
L(s) := 0;

/* Exploration des arcs connus */
Pour chaque arc ( s , v ) appartenant à A'
	Si L(v) > w(s,v) alors
		L(v) := w(s,v);
		Succ(v) := v;
	FinSi
FinPour

Tantque (vrai) faire
	/* Echange avec les voisins */
	Pour chaque sommet u auquel on est connecté faire
		Envoyer les vecteurs L à u;
	Finpour
	Pour chaque sommet u auquel on est connecté faire
		Recevoir le vecteur L' venant de u;
		Pour chaque sommet v de G faire
			Si L(v) > w(s,u) + L'(v) alors
				L(v) := w(s,u) + L'(v);
				Succ(v) := u;
			Sinon Si Succ(v) = u alors
				L(v) := w(s,u) + L'(v);
			FinSi
		FinPour
	FinPour
FinTantque
Programmez trois fonctions correspondant aux trois étapes de ce nouvel algorithme.

Note : les opérations Envoyer et Recevoir ne seront pas prises en compte. On consultera directement les vecteurs des noeuds voisins.

Note : L'algorithme de la troisième étape est infini. On effectuera uniquement une itération de la boucle dans la fonction correspondante.

Ecrivez un programme principal qui permet d'utiliser les fonctions de création/édition de réseau de l'étape 1, de faire fonctionner ce nouvel algorithme de routage sur un réseau pour chaque noeud et d'afficher les résultats (chemins et longueur calculée de ces chemins) à chaque itération de l'étape 3 (échange avec les voisins).

On pourra aussi permettre la modification des poids des arcs entre deux itérations pour simuler des changements dans le réseau. En particulier en cas de perte de liaison entre deux noeuds on passera l'arc à la valeur "infini".

 

Patrice Torguet (torguet@irit.fr) – Mars 2005
Valid HTML 4.01!