Routage et transfert d’informations dans GRAPP&S

GRAPP&S, une solution totalement répartie pour le stockage de données & Services

Définitions et Modélisation 

Il existe de nombreuses définitions des systèmes distribués. Dans [Tel94] l’auteur définit un système distribué comme un ensemble d’entités autonomes, ou unité de calcul, reliées par des canaux de communication. Par ces canaux ils échangent des messages dans le but d’avoir des puissances de traitement ou de stockage, des disponibilités de services, un temps de réponse rapide etc. Ces entités peuvent être des processus ou des machines physiques (ordinateur par exemple). Cette définition très large se doit d’être précisée et formalisée. 

 Graphe et système de communication 

Un système distribué est modélisé par un graphe G = (V, E), les ensembles V et E correspondent respectivement aux sommets (ou nœuds) et aux arêtes ou arcs du graphe. Le graphe G peut être orienté ou non-orienté. Les nœuds du graphe représentent les unités de calcul du système, les arcs, ou arêtes du graphe représentent les liens de communication. Comme dans le cadre des graphes les liens de communication peuvent être orientés ou non orientés, fixant ainsi le « sens » des communications et des échanges. Définition 1.2. Un graphe G est dit connexe si pour deux sommets quelconques u et v du graphe, on peut trouver un chemin constitué d’arêtes consécutives qui relie u à v. Définition 1.3. Un graphe G est dit simple si quels que soient u et v deux sommets, u est relié à v par au plus une arête. Définition 1.4. Un graphe G est dit sans boucle si quel que soit u un sommet, il n’existe aucune arête (u, u). Les graphes que nous considèrerons dans la suite sont connexe, simple et sans boucles. Définition 1.5. Chaque sommet ou nœud est une entité autonome de calcul, de stockage, avec des moyens et des canaux de communications. Un sommet peut être, par exemple : un ordinateur, un équipement réseau (routeur, switch …), un capteur, un objet communiquant … Les sommets peuvent ne posséder aucun identifiant, dans ce cas on parlera de système anonyme. Nous supposons que chaque sommet du graphe possède une identité unique. Cette hypothèse est tout à fait réaliste, dans un réseau classique, chaque interface de communication étant doté d’un identifiant physique unique : l’adresse MAC ; et chaque interface active est dotée d’un identifiant logique unique au sein du réseau dans lequel il se trouve : l’adresse IP. L’activité d’un sommet, c’est-à-dire, celle qui correspond à l’exécution d’un algorithme, consiste en trois opérations élémentaires : 1. Envoyer des messages aux voisins Send(message) ; 2. Recevoir des messages Receive(message) ; 3. Effectuer des calculs locaux, permettant l’évaluation de toutes les opérations algorithmiques classiques Compute() Définition 1.6. Une arête du graphe correspond à un canal de communication bidirectionnel entre deux entités de calcul voisines. Une arête e= (u, v) ∈ E correspond alors à une paire ((u, i),(v, j)) comme le montre la figure1.2. Figure 1.2 – une arête e=(u, v) L’envoi d’un message de u vers v(resp. de v vers u) s’effectue alors en transmettant le message sur le port i(resp. sur le port j). Le sommet v(resp. u) reçoit le message en le récupérant sur le port j (resp. sur le port i). Nous supposons que les ports d’un même sommet ont des numéros distincts et qu’un sommet peut distinguer le port sur lequel il a reçu un message donné. L’échange d’informations entre u et v peut se faire, comme nous le verrons dans la suite, selon deux principaux modèles : par lecture / écriture de mémoire partagée, ou par échange de messages explicites. Définition 1.7. Le voisinage d’un sommet u donné, est l’ensemble des sommets v ∈ E auxquels ce dernier est connecté par une arête (u, v) ∈ E. Autrement dit, le voisinage correspond à l’ensemble des nœuds avec lesquels il est possible de communiquer directement. Deux sommets u et v reliés par une arête dans le graphe G sont dit adjacents. L’ensemble des sommets adjacents à u définit aussi le voisinage de u ; il est noté par N(u). Le degré de u, noté deg(u), désigne le nombre de voisins de u. 

 Topologies particulières

 Plusieurs types de graphes sont rencontrés dans les systèmes distribués. Le choix des graphes utilisés est fortement tributaire de leur caractère très hétérogène, leur besoin de passage à l’échelle, et de leur structuration. Le choix d’une topologie particulière a un impact non négligeable sur les facilités de programmation et sur les performances des algorithmes et des programmes qui sont développés et implantés. Une topologie particulière permet d’exploiter des propriétés spécifiques comme l’orientation, la régularité du voisinage … Ces propriétés simplifient grandement certaines étapes ou services liés à la conception d’algorithmes.Topologie en Chaîne On définit une chaîne de taille n comme un graphe connexe dont 2 nœuds sont de degré 1 et n − 2 nœuds de degré 2. Une illustration d’une topologie en chaîne d’un système distribué est donnée dans la figure 1.3. La topologie en chaîne est largement exploitée, on la retrouve notamment dans le cadre des architectures de type bus de communication, mais aussi des bus logiciels comme dans le cas de Corba [?, GGM00] Elle permet des diffusions simples, ainsi qu’une grande simplicité des moyens utilisés pour le routage. Par contre, elle n’est pas tolérante aux fautes : une panne d’un nœud interne provoque la perte de la connexité du système. Topologie en Anneau Un anneau est une chaîne reliée par ses extrémités. Il peut être orienté ou non. L’orientation peut se faire soit dans le cadre des liens de communications, soit de manière interne aux nœuds de communication en associant des identifiants de type next et previous aux deux voisins d’un nœud, c’est à dire aux ports de communication associés. Naturellement, dans ce cas le port next d’un nœud est relié au port previous de son voisin et inversement. Une illustration d’une topologie en chaîne d’un système distribué est donnée dans la figure 1.4.

CONFIIT[FKS10]

 La topologie en anneau permet une grande simplicité des opérations de routage de l’information, ainsi que de diffusion. Comme dans le cas de la chaîne, elle se montre non tolérante aux fautes, une seule panne d’un sommet transformant l’anneau en chaîne, deux pannes pouvant provoquer la perte de la propriété de connexité. Topologie en Arbre Un arbre est un graphe connexe sans cycle. Un arbre peut aussi être défini comme un graphe connexe tel que pour tout couple de sommets (u, v), il existe une unique chaîne entre u et v. Les sommets d’un arbre sont appelés nœuds de l’arbre. L’un des nœuds est appelé la racine. On dit que l’arbre est enraciné (il est aussi appelé arborescence, la racine constitue le sommet le plus haut). La figure 1.5 illustre un système distribué sous forme d’un arbre. On dit que v est un descendant d’un nœud u, si le nœud u est sur le chemin entre v et la racine de l’arbre. Si u et v sont reliés par une arête alors on dit que u est le père de v. Tout nœud qui ne possède pas d’enfant est une feuille.On trouve de nombreux systèmes organisés selon un arbre, on pourra citer pour les systèmes pair-à-pair Napster [FP99a], Bittorrent [Coh08a] et les nouvelles versions de Gnutella [KM02a]. La topologie en arbre est aussi largement utilisée dans le cadre des grilles de calcul comme dans les cas de DIET[CD06] et Globus [Fos05] qui ont une organisation hiérarchique, sous la forme d’un arbre. La structure en arbre offre des propriétés intéressantes, notamment dans les cas de recherche et de diffusion. Elle permet notamment d’offrir des communications efficaces entre différents nœuds. Cette topologie se montre aussi peu tolérante face aux pannes qui peuvent impacter le système : la panne d’un nœud autre qu’un feuille implique la perte de la connexité du système. Topologie en Grille Une grille KpXq est un graphe composé de pXq sommets vi,j avec 1 ≤ i ≤ p, 1 ≤ j ≤ q, dans lequel deux sommets( ou nœuds) vi,j et vk,l sont adjacents si |i − k| + |j − l| = 1. Où p représente le nombre de lignes et q le nombre de colonnes. La figure 1.6 illustre un système distribué sous la forme d’une grille. Figure 1.6 – Une grille 3 x 4 L’exploitation d’un grille permet de simplifier toutes les opérations de routage. En effet, comme dans le cas de l’anneau, il est possible d’orienter les liens de communication et de nommer les nœuds afin de rendre le routage implicite. Par contre la moindre panne d’un site détruit la structure, cette topologie est donc difficilement adaptable face aux changements topologiques. Topologie Graphe complet Un graphe est dit complet, aussi appelé clique si pour toute paire {u, v} de sommets, il existe une arête dont les extrémités sont u et v. Un graphe complet à n sommets est noté Kn. La figure1.7 illustre un graphe complet à 5 sommets. Figure 1.7 – Un graphe complet à 5 sommets. la clique se montre particulièrememnt efficace face aux changements topologiques et aux pannes. Les communications sont efficaces car elles ne nécessitent que d’un seul échange de message pour tout échange ente deux sommets. Par contre, cette topologie implique une explosion du nombre de liens de communications, et de ports de communication en chaque nœud. 

Topologie physique et topologie logique 

L’ensemble des topologies présentées peuvent être physiques ou logiques. Dans le cas d’une topologie physique, le graphe de communication est organisé selon la topologie régulière définie. Les propriétés liées aux topologies peuvent donc être exploitées « directement » : dans le cas d’un anneau, chaque neud n’aura que 2 voisins … Il est aussi possible de construire une topologie virtuelle sur une topologie physique. dans ce cas, on parle de topologie logique. Une topologie logique est un donc sous-graphe G0 = {V 0 , E0} de G = {V, E} pour lequel V = V 0 et E 0 ⊆ E, G0 présente une topologie régulière. Il est donc possible de plonger un anneau sur un graphe quelconque, et ainsi, de bénéficier des propriétés des anneaux, alors que le graphe G d’origine ne présente aucun propriété particulière. La figure 1.8 montre le plongement d’un anneau virtuel sur un graphe quelconque. Figure 1.8 – Un graphe complet à 5 sommets et un anneau logique L’utilisation des arbres comme structure logique est courante, avec le calcul de structures couvrantes des systèmes distribués. La figure 1.9 montre le plongement d’un arbre virtuel sur un graphe quelconque.