Les techniques de bases vues dans les cours précédents sont employées dans des algorithmes plus complexes. C'est en particulier le cas du parcours de réseau. Par ailleurs, des problèmes particuliers nécessitent des algorithmes ayant des propriétés spécifiques, certains problèmes ne sont pas solubles avec des algorithmes déterministes, d'autres doivent fonctionner dans un environnement changeant, voire sujet à des pannes.
Dans ce cours, on étudie en première partie le problème de l'élection d'un leader dans un réseau, avec un algorithme standard et en évoquant des algorithmes plus évolués. En seconde partie, on étudie le problème du routage dans un réseau qui évolue.
L'objectif est ici de désigner, parmi les sites du réseau, un leader pour jouer ensuite un rôle particulier (par exemple contrôle d'accès à une ressource, tâche de supervision du réseau, ...). L'élection sera basée sur la comparaison de valeurs possédées par les sites. Pour simplifier, on supposera que ce sont les identités des sites qui seront comparées, l'élu (alors pré-déterminé) sera celui qui a l'identité la plus forte. ceci suppose bien entendu que les sites aient des identités deux à deux distinctes, mais ces identités ne sont pas connues a priori des différents sites.
L'algorithme doit être absolument symétrique : sinon, dans le cas où un des sites y jouerait un rôle particulier, le problème serait déjà résolu !
On utilise le parcours de réseau : chaque site peut, s'il le désire, lancer un parcours dont il est racine. Les messages relatifs à ce parcours seront estampillés par son identité. ceci permettra aux autres sites de comparer avec leur propre identité : dans le cas où la leur est plus faible, ils propageront le parcours reçu et se considéreront battus, alors que dans le cas contraire, ils ne la propageront pas et lanceront leur propre parcours, si ce n'était pas déjà fait.
Ainsi, seul le parcours du site le plus fort sera complet (i.e. parcourra tout le réseau) et, à condition de gérer les acquittements, son initiateur sera prévenu de sa terminaison donc saura qu'il est l'élu.
Afin de ne pas mélanger les différents parcours en cours, les variables nécessaires devront être indexées par les identités des sites ayant lancé les parcours.
On suppose les sites numérotés de 1 à N. L'algorithme peut sécrire ainsi
Tout site possède les variables suivantes :
Pere : tableau[1..N] d'identités de sites, chaque ligne de ce tableau initialisée à 0 (ou nil)
Acqattendus : tableau[1..N] d'entiers
parcourslance : booléen, initilisé à faux
Dejavu : tableau[1..N] de booléens, initialisés à faux
Etat : (Initial, Battu, Elu) initialisé à Initial
Lancement spontané par un site i : appeler la procédure Lancer_Parcours
Procedure Lancer_Parcours
parcourslance = vrai
Dejavu[i] = vrai
Acqattendus[i] = nombre d'éléments de voisins
Envoyer Parcours(i) à tous les voisins
Sur réception de parcours(j) venant d'un voisin k :
Si Dejavu[j]
alors envoyer acqneg[j] à k
sinon Dejavu[j] = vrai
Pere[j] = k
Si j > i alors Etat=Battu
Acqattendus[j] = nb d'elts de voisins -1
Si Acqattendus[j] = 0, alors envoyer acqpos(j) à pere(j)
sinon Envoyer Parcours[j] à tous les voisins sauf k
sinon si non(parcourslance), appeler Lancer_Parcours
Sur réception de acqneg[j] ou acqpos[j] venant de k
AcqAttendus[j] -= 1
// dans le cas d'un acqpos, on pourrait mettre à jour une variable Fils[j]
Si AcqAttendus[j] = 0,
alors si Pere[j] <> nil alors envoyer acpos[j] à Pere[j]
sinon Etat = Elu
On remarque que le site stoppe le parcours s'il se considère plus fort que le parcours reçu. Il ne renvoie même pas d'acquittement à son père, ce qui fait que les parcours ainsi stoppés ne pourront pas être acquittés : seul le parcours "gagnant" le sera, et son initiateur concluera alors qu'il est l'élu.
L'algorithme est parfaitement symétrique dans le sens où il peut être lancé par un nombre quelconque de sites (au moins un évidemment !)
N.B.: on peut optimiser en ne propageant que les parcours de poids supérieur au plus grand déjà vu : chaque site i gère une variable PGvu, initialisée à i, et on compare j à PGvu au lieu de i, et on modifie PGvu pour que cette variables mémorise toujours l'identité du plus grand parcours reçu.
L'utilisation des tableaux indexés par le nombre de sites est une simplification. On pourrait imaginer une forme différente pour les variables qui n'imposerait pas aux sites de connaître a priori le nombre de sites du réseau ni les identités (sinon, le problème peut être résolu au départ : celui qui a l'identité N a gagné !)
On peut imaginer des algorithmes pour lesquels le résultat n'est pas
pré-déterminé (cf. TD). De plus, dans le cas où
les sites n'ont pas d'identités, ni même de valeurs permettant
une fonction de comparaison, on peut envisager des algorithmes, alors nécessairement
probabilistes, c'est-à-dire avec une chance de succès inférieure
à 100%, pour résoudre le problème.
Nous ne développerons pas ici un tel algorithme, assez complexe. Cependant l'idée de base est la mâme que celle de l'algorithme déterministe que nous verrons en TD : en gros, chaque site peut essayer de se constituer un fragment du réseau dont il est "le chef", et il faut résoudre les conflits lorsque des fragments concurrents "se rencontrent". Dans le cas où les sites ou les fragments possèdent des identités ou au moins des valeurs disctinctes résolvant ce conflit, on peut construire un algorithme déterministe, sinon, il faudra opérer un tirage aléatoire et donc prendre le risque de désaccord persistant entre les deux fragments.
L'objectif est ici de maintenir sur chaque site une table de routage, laquelle indique, pour chaque destination possible de message, quel est le "meilleur voisin" auquel il faut transmettre le message afin qu'il parvienne à destination, après relais éventuels, et ceci avec le ou un plus court chemin possible.
Cette notion de plus court chemin nécessite bien entendu une notion de distance : on considérera que chaque ligne de communication est de longueur 1, et la longueur d'un chemin sera donc le nombre de lignes qui le composent.
Le réseau est susceptible d'améliorations, par exemple ajout de lignes de communications, ou d'agrandissements (ajout de sites). On va donc proposer un algorithme qui, à partir d'une situation où chaque site ne connaît que lui même, construit les tables de routage par ajout successif de lignes de communication
Afin de pouvoir comparer les distances, il faudra mémoriser au moins la meilleure d'entre elles. On aura donc pour chaque site i
Lors de l'ajout (ou la mise en service) d'une laison entre les sites i et j, on suppose que chacun d'eux reçoit un message signalant cet ajout. Le site i exécute alors le code suivant :
Distance[j] = 1; Route[j] = jLe site j fait de même, bien entendu. La réaction aux messages de mise à jour est alors la suivante :
Envoi à tous les voisins (y compris le nouveau voisin j) d'un message de MiseAJour(Distance)
Sur réception d'un message MiseAJour(D) venant d'un voisin j, le site i a le comportement suivant :
Modif = faux
Pour tout k dans 1..N faire
Si Distance[k] > 1 + D[k]
alors Distance[k] = 1 + D[k]
Route[k] = j
Modif = vrai
fait
Si Modif, alors envoyer MiseAJour(Distance) à tous les voisins
Cet algorithme peut éventuellement être optimisé, en n'envoyant pas en paramètre de MiseAJour tout le tableau Distance à chaque modification, mais seulement les triplets (i,k, Distance[k]) pours lesquels Distance[k] a changé.
Cet algorithme est actif tant qu'on ajoute des lignes de communication (ou des sites, ce qui revient à initialiser un site supplémentaire, et à ajouter toutes les lignes qui y mènent). Il ne se termine que si la topologie du réseau est elle-même figée et, dans ce cas, les tableaux Distance contiennent effectivement les distances entre i et les différents sites, et les tableaux Route contiennent les meilleurs voisins, c'est-à-dire les départs des chemins les plus courts vers les sites du réseau.
Là encore, le fait d'utiliser des tableaux permet de simplifier l'écriture. Par contre, il est nécessaire d'avoir une borne supérieure du nombre de sites du réseau, ou bien une autre méthode pour symboliser l'infini (au départ, aucune route n'est connue, donc toutes les distances sont infinies)
Cet algorithme fonctionne très bien tant qu'on AJOUTE des lignes au réseau. Par contre, il ne prévoit pas le retrait (ou la panne temporaire) de lignes du réseau. Il est tout à fait possible de le modifier pour celà : sur réception d'un message de mise à jour, au lieu de comparer, pour chaque k, la distance connue et la distance envoyée plus 1, on évalue le minimum des distances des voisins à k, et on choisit comme route vers k celui qui possède ce minimum (les distances des voisins vers les sites peuvent être mémorisées en permanence, ou demandées à l'occasion)
Mais cet algorithme présente le défaut bien connu du "comptage à l'infini" : dans le cas ou le meilleur voisin compte sur nous même pour atteindre k, on a le comportement suivant :
Certes, le phénomène s'arrête au plus tard lorsqu'on atteint N. Mais si ce nombre est grand, ça peut durer un certain temps et, pendant ce temps-là, les messages à destination de k vont être renvoyés entre i et j, encombrant inutilement le réseau surtout si, suite à une panne, k n'est plus accessible du tout. En pratique, cet algorithme n'est utilisable que pour des petits réseaux (N petit). Le protocole RIP (utilisé par le démon routed par exemple) est basé sur son principe, mais l'"infini" est égal à 16 pour ce protocole...
À titre de révison, on pourra regarder le texte de la première session 2011 par exemple.
Un exemple d'algorithme d'élection non pré-déterminée,
bien que basée sur les identités des sites. Cet algorithme est un peu
complexe, car il faut traiter différents types de messages. On peut par
contre le "faire tourner à la main" sur un exemple très simple pour
exhiber un cas où l'élu n'est pas celui dont l'identité est la plus
forte.
Un exemple d'algorithme de régénération de jeton sur un anneau, et cas de perte de ce dernier : différentes variantes avec, si le temps le permet, une généralisation à un nombre de jetons quelconque. (Voir l'essentiel de l'article dont s'inspire cet exercice, ou même l'article complet)
Retour au sommaire algorithmique répartie