La tolérance aux pannes des algorithmes de partage de ressources dans les systèmes répartis et les réseaux Ad Hoc (simulation par ns-2)

CONCLUSION

La simulation de notre algorithme dans les réseaux mobile nous a permis d'identifier les paramètres ayant une influence sur la performance de notre algorithme, nous avons pu tirer les résultats suivants :

- La variation du nombre de demandeurs n'a pas une influence sur le NMM et le TAM.

- Le TAM dépends disproportionnellement de la portée de communication.

- La vitesse de mouvement n'a pas une relation claire avec le NMM et le TAM. - La variation du nombre de noeuds a une relation proportionnelle avec le TAM.

- La variation de la portée ou du nombre de noeuds n'a pas d'influence sur le NMM.

CONCLUSION ET PERSPECTIVES

À

Travers notre étude menée dans ce mémoire, qui avait pour but l'évaluation et l'amélioration des algorithmes proposés dans le cadre de la K-exclusion mutuelle dans les systèmes répartis et dans les réseaux AD HOC.

Nous avons mets l'accent sur les notions de base de ce problème, et nous avons également expliqué les algorithmes proposés ainsi que les améliorations apportées.

L'évaluation de cet algorithme a été réalisée par NS-2, l'outil de simulation qui permet de valider les algorithmes dans les conditions les plus réelles.

Ce travail nous a permis de :

- Comprendre le problème de l'exclusion mutuelle et son extension en K-ressources ainsi que la notion de la tolérance aux pannes.

- Faire une recherche bibliographique pour recenser les différentes solutions apportées à ces problèmes.

- Identifier les facteurs influant sur le comportement des algorithmes simulés.

- Comparer par simulation les performances des différentes améliorations afin de juger la meilleure d'entre elles.

- Maitriser l'outil de simulation NS-2.

Il est évident qu'il n'existe pas un travail parfait, nous pouvons penser toujours à des améliorations et des perspectives futures, nous avons pensé à :

1. Minimiser encore le nombre de messages échangés en utilisant une nouvelle structure de données pour obtenir le minimum possible.

2. Réduire en plus le temps d'attente en utilisant des nouvelles stratégies d'échanges de messages.

3. Enrichir le mécanisme de tolérance aux pannes pour pouvoir faire face à la panne de plusieurs sites.

4. Utiliser le principe de notre algorithme pour résoudre ce problème dans d'autres systèmes tels que : les réseaux de capteurs, les VANETs ... etc.

BIBLIOGRAPHIE

[Abd07] Z. Abdelhafidi. Points de reprise dans les systèmes répartis etude basée sur la simulation des protocoles cic assurant la propriété rdt. Thèse Magistère de l'université Amar Telidji-Laghouat Spécialité informatique, pages 11-27, 2007. (Cité page 27.)

[AK08] A. Alliliche and M. Kebir. Etude comparative des protocoles de points de reprise de type cic. Projet de fin d'étude, Université de Laghouat, 2008. (Cité pages 26 et 27.)

[All04] Krouba M. Allaoui, T. Etude des systèmes répartis et réalisation d'un simulateur des algorithmes répartis d'exclusion mutuelle. Projet de fin d'étude, Université de Laghouat, 2004. (Cité pages 6 et 7.)

[All07] T. Allaoui. Une nouvelle solution du problème de la k-exclusion mutuelle dans les systèmes répartis. Mémoire de Magister, Université de Laghouat, 2007. (Cité pages x, 7, 18, 19 et 31.)

[BAA89] .J Bernabéu, M. Auban, and M. Ahamad. Applying a path-compression technique to obtain an eficient distributed mutual exclusion algorithm. In Proceedings of the 3rd International Workshop on Distributed Algorithms London, UK, pages 33-44, 1989. (Cité page 23.)

[Bou07] A. Boukhalkhal. Étude par simulation des performances des protocoles de routage dans les réseaux ad hoc sans fil. Mémoire de fin d'étude, Université de Laghouat, 2007. (Cité pages x et 9.)

[CL85] K-M. Chandy and L. Lamport. Distributed snapshots : Determining global states of distributed systems. ACM Transactions on Computer Systems, pages 63-75, 1985. (Cité page 27.)

[CM84] K.M. Chandy and J. Misra. The drinking philosopher's problem. ACM Transactions on Programming Languages and Systems, pages 632-646, 1984. (Cité page 21.)

[CM92] M. Chandy and .J Misra. Synchronisation et état global dans les systèmes répartis. Eyrolles, 1992. (Cité page 22.)

[Cou94] G. Coulouris. Distributed systems. Concept and Design, 2nd Ed Addison Wesley Pubishers Ltd., 1994. (Cité page 4.)

[CR83] S.F. Carvalho and G. Roucairol. On mutual exclusion in computer networks. Communications of ACM, pages 146-147, 1983. (Cité page 21.)

[CSL91] Y. Chang, M. Singhal, and M.T Liu. A dynamic token-based distributed mutual exclusion algorithm. Computers and Communications, Conference Proceedings, Tenth Annual International Phoenix Conference, pages 240-246, 1991. (Cité page 23.)

[Dij65] W. Dijkstra. Solution of a problem in concurrent programming control. Communications of the ACM, 1965. (Cité page 20.)

[Eve04] C. Evequoz. Programmation répartie. Ecole d'ingénieur du Canton de Vaud, 2004. (Cité page 5.)

[HM94] J.M. Hélary and M. Mostefaoui. fault-tolerant distributed mutual exclusion algorithm based on open-cube structure. 14th International Conference on Distributed Computing Systems (ICDCS), pages 89-96, 1994. (Cité page 23.)

[HPR88] J-M. Hélary, N. Plouzeau, and M. Raynal. A distributed algorithm for mutual exclusion in an arbitrary network. Computer journal, pages 289-295, 1988. (Cité page 23.)

[Lai02] T.H. Lai. On distributed dynamic channel allocation in mobile cellular networks. IEEE Transactions on Parallel and Distributed Systems, pages 1024-1037, 2002. (Cité page 40.)

[Lam78] L. Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of ACM, pages 558-565, 1978. (Cité pages 20 et 21.)

[Lan77] G. Lann. Distributed systems - towards a formal approach. International Federation for Information Processing(IFIP)Congress, pages 155-160, 1977. (Cité page 20.)

[Lan78] G. Lann. Algorithms for distributed data-sharing systems which use tickets. Proceedings of the Third Berkeley Workshop on Distributed Data Management and Computer Networks, pages 259-272, 1978. (Cité page 23.)

[Lem00] T. Lemlouma. Le routage dans les réseaux mobiles ad hoc. Mini projet, Université d'Alger USTHB, 2000. (Cité pages 8, 14 et 15.)

[LK09] A. Lahag and Kouidri. Etude des performances des algorithmes de l'exclusion mutuelle dans les réseaux ad hoc {Simulation par NS2}. Projet de fin d'étude, Université de Laghouat, 2009. (Cité pages 9 et 20.)

[Mae85] M. Maekawa. A square root n algorithm for mutual exclusion in decentralized systems. ACM Transactions on Computer Systems(TOCS), 1985. (Cité page 22.)

[Man07] N. Mansouri. Protocole de routage multi chemin avec équilibrage de charge dans les réseaux mobiles ad hoc. Projet de fin d'étude, Ecole supérieur des communications de Tunis, Tunisie, 2007. (Cité pages 11 et 12.)

[Mar85] A.J. Martin. Distributed mutual exclusion on a ring of processes. Science of Computer Programming, pages 265-276, 1985. (Cité page 23.)

[Mes98] P. Meskauskas. Mobile ad hoc networking. Seminar on Telecommunications Technology, Helsinki, 1998. (Cité pages 11 et 12.)

[NM91] M.L. Neilsen and M. Mizuno. A dag-based algorithm for distributed mutual exclusion. In International Conference on Distributed Computing Systems (ICDCS), pages 354-360, 1991. (Cité page 23.)

[NT87] N. Naimi and M. Trehel. An improvement of the log(n) distributed algorithm for mutual exclusion. IEEE 7th international Conf. On Distributed Systems, Berlin, Germany, 1987. (Cité page 23.)

[RA81] G. Ricart and K. Agrawala. An optimal algorithm for mutual exclusion in computer networks. Communications of ACM, pages 9-17, 1981. (Cité page 21.)

[Ray88] K. Raymond. A distributed algorithm for multiple entries to a critical section. Information Processing Letters 30, pages 189-193, 1988. (Cité page 25.)

[Ray89] K. Raymond. A tree-based algorithm for distributed mutual exclusion. ACM Transactions on Computer Systems, pages 61-77, 1989. (Cité page 23.)

[Ray91] M. Raynal. A simple taxonomy for distributed mutual exclusion algorithms. Operating Systems Review, 1991. (Cité page 21.)

[Sin89] M. Singhal. A heuristically-aided algorithm for mutual exclusion in distributed systems. IEEE Transactions on Computers, pages 651-662, 1989. (Cité page 23.)

[Sin91] M. Singhal. A class of deadlock-free meakawa-type algorithms for mutual exclusion in distributed systems. Distributed Computing, pages 131-138, 1991. (Cité page 22.)

[SK85] I. Suzuki and T. Kasami. A distributed mutual exclusion algorithm. ACM Trans.Computer Systems, pages 344-349, 1985. (Cité page 23.)

[Sop08] J. Sopena. Algorithmes d'exclusion mutuelle : tolérance aux fautes et adaptation aux grilles. Thèse de doctorat de l'Université Pierre et Marie Curie-Paris VI, 2008. (Cité pages 21 et 22.)

[Sri89] P.K. Srimani. Another distributed algorithm for multiple entries to a critical sec-
tion. Information Processing Letters 41, pages 51-57, 1989. (Cité page 25.)

[Tan94] S. Tanenbum. Distributed operating systems. Prentice Hall, 1994. (Cité page 4.)

[vdS87] J.L.A. van de Snepscheut. Fair mutual exclusion on a graph of processes. Distributed Computing, pages 113-115, 1987. (Cité page 23.)

[Wei08] W. Weigang. A fault tolerant mutual exclusion algorithm for mobile ad hoc networks. Department of Computing, The Hong Kong Polytechnic University, 2008. (Cité page 25.)

[WK97] J.E. Walter and S. Kini. Mutual exclusion on multihop, mobile wireless networks. Texas A and M University College Station, 1997. (Cité page 26.)

[WW01] J. WALTER and L. WELCH. A mutual exclusion algorithm for ad hoc mobile
networks. Department of Computer Science,Texas USA, 2001. (Cité page 25.)