Ministere de l’enseignement superieur et de la recherche scientifique

8.6.1 Algorithmes de reprise dans les réseaux mobiles 

D’après notre étude, nous concluons que certains algorithmes ne peuvent pas être portés en environnement mobile, en raison de leur éloignement des objectifs attendus par ces derniers. Car en plus des objectifs déjà cités dans la deuxième partie de cette étude, ces algorithmes doivent respecter les contraintes imposées par le réseau sans fils.

L’idée de porter l’étude du fixe vers le mobile a surgit en 1993 dans [74], et avait pour but le traitement de la mobilité, en sauvegardant en plus des points de reprise l’itinéraire emprunté par le site.

8.6.1.1 Points de reprise indépendants 

Les algorithmes d’établissement de point de reprise non coordonnés, ont été les premiers algorithmes proprement dits proposés pour le mobile. Comme déjà évoqué dans le cadre des systèmes répartis fixes, cette méthode consiste à faire prendre aux différents processus du système des points de reprise de manière totalement indépendante [73], [80], [81]. Cela implique la sauvegarde de plusieurs points de reprise. Si ces points devaient être transférés sur un support de stockage stable, le coût en messages de transfert serait très élevé. Le calcul d’une ligne de recouvrement, via un graphe de dépendance entre les points de reprise locaux, n’est fait que pendant le recouvrement, ce qui peut s’avérer très coûteux en énergie. Le ramassage des points, est compliqué. Mais l’inconvénient majeur de cette technique est l’effet Domino, ce qui rend cette technique peu tentante, nous verrons par la suite que la méthode non coordonnée est combinée avec d’autres méthodes pour faire face à certaines contraintes du mobile.

8.6.1.2 Points de reprise coordonnés

8.6.1.2.1 Coordination explicite

C’est la technique vers laquelle beaucoup de chercheurs se sont penchés, sans doute parce qu’elle garantie la cohérence de la ligne de reprise.

Cette approche repose sur une coordination et une synchronisation globale des processus de l’application. Un coordinateur sauvegarde son point de reprise et diffuse une requête aux autres processus de l’application pour établir leur point de reprise, ce qui implique une latence importante et un coût considérable en messages de synchronisation.

La nouvelle idée est de construire des algorithmes utilisant la coordination, mais en minimisant le nombre de processus participant à la reprise, par conséquent minimiser le coût de la synchronisation, et visant la transparence de la procédure de checkpointing par rapport à l’exécution de l’application.

La technique de sauvegarde coordonnée de points de reprise est classée dans deux catégories : les algorithmes bloquants [84] et les algorithmes non bloquants [76], [83], [84], [85]. Les premiers forcent les processus à geler leur travail courant lors de l’algorithme, l’autre permet aux processus de continuer leur tache courante en parallèle avec l’algorithme, en attribuant des numéros de séquence aux messages, pour éviter les messages orphelins.

Le checkpointing coordonné, ne génère pas d’effet domino, stocke un nombre minimum de checkpoints (2 au maximum) en contre partie il utilise un surplus de messages de synchronisation et peut bloquer l ‘application pendant une période de temps qui peut avoir un impacte néfaste sur son rendement. Sinon elle utiliserait des structures de données énormes pour éviter le blocage. Le recouvrement est très simple.

8.6.1.2.2 Coordination réalisée par des horloges (time based)

Dans cette approche, on utilise les horloges synchronisées ou des temporisateurs pour coordonner l’établissement des points de reprise [51], [55], [86]. On remarque que la notion de coordinateur n’a pas totalement disparue, mais est incluse implicitement dans le protocole. On remarque une moindre utilisation de toutes les ressources, mais le problème est la déviation temporelle entre les horloges qui pourrait être très grande.

8.6.1.3 Points de reprise induits par les communications

Cette technique utilise les biens faits des deux techniques citées auparavant : coordonné et indépendant. La synchronisation est assurée par les messages de l’application, on appelle cela la phase “paresseuse” [33], [56], [89]. Chaque processus prend régulièrement des points de reprise de manière indépendante. On distingue deux familles de protocole :

8.6.1.3.1 Les protocoles model-based

Ces protocoles sont basés sur les notions de chemins et de cycles en “zig-zag” pour déterminer les états globaux cohérents. Les communications et les prises de checkpoints doivent respecter un certain motif.

3.6.1.3.2 les protocoles index-based

Ce type de protocole utilise une méthode basée sur la suppression des dépendances causales entre les checkpoints. Chaque message porte l’index du dernier point de reprise de l’émetteur.

Aucun message spécifique de coordination n’est envoyé, mais les points de reprise sont réalisés lors d’évènements particuliers, donc nous sommes sûr de former un état global cohérent.

8.6.1.4 Journalisation pessimiste

Tous les messages (journal) émis doivent être conservés de façon synchrone et sur un support stable [87], [88], au cas où il serait nécessaire de les rejouer. Cette méthode garantie une reprise très sûre après une panne et n ‘implique aucune autre station MH car il faut tout simplement rejouer les

messages sauvegardés. Aussi on a besoin d’aucune coordination, mais elle est très coûteuse en espace mémoire et en message de sauvegarde sur le support stable.

8.6.1.5 Journalisation optimiste 

À la différence de la journalisation pessimiste [80], le journal n’est pas écrit directement en mémoire stable mais est d’abord écrit en mémoire volatile pour être vidé périodiquement vers la mémoire stable. Donc la fréquence de l’accès à la mémoire est limitée mais peut conduire à impliquer d’autres MH lors de la reprise en cas de journalisation en retard et donc beaucoup de nœuds vont faire un retour arrière.

8.6.1.6 Journalisation causale 

Cette technique combine les avantages de la journalisation optimiste et de la journalisation pessimiste [65].

Le journal est sauvegardé en mémoire volatile mais la décision de l’écrire en mémoire stable est prise à partir des dépendances causales entre les évènements. Ceci implique l’ajout d’informations additionnelles aux messages (dépendances causales) et par conséquent l’augmentation de la taille du message à sauvegarder et à transmettre vue la largeur de la bande passante limitée.

8.6.1.7 Les techniques hybrides

Ces techniques combinent entre deux ou plusieurs méthodes entre celles citées auparavant. Comme par exemple la L’algorithme de Prakach-Singhal [75], qui a combiné les deux techniques : bloquante et non bloquante, l ‘algorithme de Hirogak-Takiwaza [92] qui combine entre les algorithmes synchrones et indépendants, ou encore celle de Lin et dow [93] qui combine entre l’approche coordonnée et celle induite par les communications. Leur but est de faire bon usage des avantages de chaque méthode qu’elle combine