兰斯香槟-阿登大学科学技术健康博士学院合作博士论文

0                             兰斯香槟-阿登大学0科学技术健康博士学院（547）0合作博士论文0获得学位：0达喀尔谢赫∙安塔∙迪奥普大学博士学位0学科：计算机科学0和0兰斯香槟-阿登大学博士学位0学科：计算机科学0公开展示和答辩人：0Bassirou GUEYE02016年5月26日0自适应自组织网格服务0论文指导：Ibrahima NIANG先生，迪奥普谢赫∙安塔大学副教授0以及Olivier FLAUZAC先生，兰斯香槟-阿登大学教授0评审委员会0克莱蒙费朗第二布莱兹∙帕斯大学的Michel MISSON先生，教授，主席0Eddy CARON先生，ENS里昂科学学院副教授，评阅人0圣路易斯加斯顿∙贝尔格大学的Ousmane THIARE先生，教授，评阅人0Olivier FLAUZAC先生，兰斯香槟-阿登大学教授，考官0塞内加尔谢赫∙安塔∙迪奥普大学的Ibrahima NIANG先生，副教授，考官0Cyril RABAT先生，兰斯香槟-阿登大学副教授，考官0献给我父亲和母亲的回忆。愿全能的真主怜悯你们！0致我的妻子0致我所有的家人0致谢0我感谢至高无上的真主安拉，他照亮了我的道路，引导我走到了这一步。0我要向我的导师Olivier Flauzac和IbrahimaNiang表示最衷心的感谢和感激之情，他们是兰斯香槟-阿登大学和达喀尔谢赫∙安塔∙迪奥普大学的教授，他们对我充满信任，给予我完成博士论文的机会。我还要感谢他们在整个工作过程中的支持、建议，尤其是在保证质量的同时给予我独立完成这个项目的机会。最后，我再次感谢他们的人道主义精神和给予我的所有帮助。愿他们在这篇论文中感受到我无尽的感激之情。0我向法语国际大学机构（AUF）表示衷心的感谢，他们提供资金支持，使得这篇论文得以实现。0我要衷心感谢我的导师CyrilRabat，他是兰斯香槟-阿登大学的副教授，他在论文的撰写过程中给予了我很大的帮助。非常感谢他提出的建设性意见、深入的建议、有趣的讨论和仔细的校对。0我向Eddy Caron和OusmaneThiaré表示衷心的感谢，他们是里昂高等师范学校和圣路易斯加斯顿∙贝尔格大学的教授，他们荣幸地同意评审这篇论文，并提出了有建设性的意见和建议，以改善论文的质量。我还要感谢米歇尔∙米松教授，他同意参加评审委员会。0我感谢UCAD计算机科学部门的所有工作人员，以及UCAD计算中心的所有工作人员。我将这些感谢与LID实验室的所有成员联系在一起。我感谢BambaGueye在繁忙的日程中阅读和校对论文。我还要特别感谢MandicouBˆa的各种交流。感谢博士生Abel Diatta、Malick Gaye，特别感谢Papa Dame Bˆa。0i0我还要感谢CReSTIC实验室的所有成员。感谢Florian Legendre和LuizSteffenel的建议和友善。感谢博士生Mahamat Charfadine，Carlos Gonzalez和ThiernoDiallo的帮助。还要感谢CReSTIC的秘书们的可用性和友善。0朋友们的鼓励是我在困难时刻的一股氧气，给予我精神上的支持。特别是...，我不会提及他们的名字，他们会认出自己。0我要深深地感谢我的父亲和母亲。我为你们感到非常自豪，我将不断感谢你们并为你们祈祷。愿全能的上帝怜悯你们！0感谢我家人的所有成员，无论是近亲还是远亲，感谢我的姐妹，感谢我的弟弟，感谢CheikhGueye，感谢他们的祈祷和鼓励。0最后，我要真诚地感谢我的妻子Soda，感谢她的爱、温柔、耐心和鼓励，感谢她在困难时刻一直陪伴在我身边，并容忍我经常离开她去实现这个项目。0谢谢...0ii0摘要0在全球范围内管理分布式资源涉及许多挑战。在这篇论文中，我们提出了一种在大规模点对点网格环境中动态管理服务的模型。这个名为P2P4GS的模型具有将点对点基础设施与服务执行平台解耦的独特性。此外，这个中间件是通用的，适用于任何点对点架构。为了确保这个特性，由于大规模分布式系统在资源、实体和用户方面的发展趋势，我们提出了将点对点网格系统结构化为虚拟社区（簇）的方法。这种结构化方法完全分布式，并且仅需要关于节点邻域的本地知识来选举簇管理器（ISP，信息系统代理）。另一方面，在各个虚拟社区内协调通信并实现高效的服务发现，结构化过程中维护了一个仅由ISP组成的生成树。因此，搜索查询将沿着这棵生成树进行路由。除了服务发现，我们还提出了服务部署、发布和调用机制。最后，我们实现并分析了P2P4GS的性能。为了说明其通用性，我们将其实现在完全不同的协议上，包括Gia、Pastry和Kademlia。性能测试表明，P2P4GS在容错性和集群分布以及通信成本方面具有良好的可扩展性。0关键词：点对点系统，服务网格，资源管理，建模，结构化，容错性。0iiiKeywords : Peer-to-peer Systems, Grid services, resources management, modelisation,clustering, Fault tolerance.v0摘要0资源管理是网格系统的一个关键问题，该系统由多个地理分布的虚拟组织组成。在这篇论文中，我们提出了一种在大规模点对点网格环境中动态管理服务的模型。这个名为P2P4GS的模型具有将点对点基础设施与执行服务平台解耦的独特性。此外，这个中间件是通用的，适用于任何点对点架构。与此同时，大规模分布式系统中资源和用户数量的增加导致了可扩展性问题。为了确保可扩展性，我们提出将点对点网格节点组织成所谓的虚拟社区（簇）。这种结构化方法完全分布式，只需要关于节点邻域的本地知识来选举簇管理器（ISP，信息系统代理）。另一方面，在各个虚拟社区内协调通信并实现高效的服务发现，结构化过程中维护了一个仅由ISP组成的生成树。因此，搜索查询将沿着这棵生成树进行路由。除了服务发现，我们还提出了服务部署、发布和调用机制。最后，我们实现并分析了P2P4GS的性能。为了说明其通用性，我们将其实现在完全不同的协议上。这些协议包括Gia、Pastry和Kademlia。性能测试表明，P2P4GS在容错性和集群分布以及通信成本方面具有良好的可扩展性。Table des mati`eresRemerciementsiR´esum´eiiiAbstractvTable des mati`eresviiListe des figuresxListe des algorithmesxiListe des tableauxxiiIntroduction11Etat de l’art sur les syst`emes distribu´es71.1G´en´eralit´es sur les syst`emes distribu´es. . . . . . . . . . . . . . . . . . . .81.1.1D´efinitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .81.1.2Mod´elisation d’un syst`eme distribu´e . . . . . . . . . . . . . . . . . .81.1.3Mod`eles de communication . . . . . . . . . . . . . . . . . . . . . . .111.1.4Algorithmes distribu´es . . . . . . . . . . . . . . . . . . . . . . . . .131.1.5Notions de panne et de tol´erance aux pannes . . . . . . . . . . . . .141.1.6Les mod`eles d’architecture . . . . . . . . . . . . . . . . . . . . . . .171.2Les syst`emes pair-`a-pair. . . . . . . . . . . . . . . . . . . . . . . . . . . .191.2.1D´efinition et terminologies . . . . . . . . . . . . . . . . . . . . . . .191.2.2Caract´eristiques du pair-`a-pair . . . . . . . . . . . . . . . . . . . . .201.2.3Architectures de r´eseaux pair-`a-pair . . . . . . . . . . . . . . . . . .221.3Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .28viiTable des mati`eres2Les services dans les syst`emes distribu´es312.1G´en´eralit´es sur les services . . . . . . . . . . . . . . . . . . . . . . . . . . .322.1.1Notion de service . . . . . . . . . . . . . . . . . . . . . . . . . . . .322.1.2Approche conceptuelle orient´ee service (SOA). . . . . . . . . . . .332.2Services Web. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .362.2.1Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .362.2.2D´efinitions de la notion de Service Web . . . . . . . . . . . . . . . .372.2.3Les technologies des Services Web . . . . . . . . . . . . . . . . . . .382.3Services de grilles informatiques . . . . . . . . . . . . . . . . . . . . . . . .442.3.1Concept de grille informatique . . . . . . . . . . . . . . . . . . . . .442.3.2Architecture d’une grille . . . . . . . . . . . . . . . . . . . . . . . .472.3.3Topologies de grilles. . . . . . . . . . . . . . . . . . . . . . . . . .492.3.4Les services de grille. . . . . . . . . . . . . . . . . . . . . . . . . .502.4Gestion de services dans un environnement de grille informatique `a large´echelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .522.4.1Objectifs et motivations. . . . . . . . . . . . . . . . . . . . . . . .532.4.2M´ecanismes de d´ecouverte de services dans les grilles . . . . . . . .542.5Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .613Sp´ecifications de services dans un environnement de grille P2P `a large´echelle633.1Motivations et objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . .643.2Sp´ecifications de P2P4GS. . . . . . . . . . . . . . . . . . . . . . . . . . .653.2.1Concepts de bases . . . . . . . . . . . . . . . . . . . . . . . . . . . .653.2.2Mod`ele d’architecture . . . . . . . . . . . . . . . . . . . . . . . . . .683.3Approche de structuration du syst`eme en communaut´es . . . . . . . . . . .723.3.1Pr´esentation de la solution de structuration. . . . . . . . . . . . .723.3.2Algorithme de structuration . . . . . . . . . . . . . . . . . . . . . .753.3.3M´ecanismes d’adaptation `a la dynamique du syst`eme . . . . . . . .783.4Synth`ese . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8004 P2P4GS中的服务管理.......................................83 4.1 动机......................................................84 4.2服务管理原语..............................................85 4.2.1 符号表示法............................................85 4.2.2部署服务：deploy......................................86 4.2.3 注册服务：save........................................904.2.4 服务发现：lookup......................................910第八页0目录04.2.5 服务调用和执行：invoke和exec.............................94 4.3总结......................................................9505 P2P4GS规范的实验和评估.................................97 5.1 模拟环境..................................................985.2 实现的覆盖层描述..........................................99 5.2.1 Gia协议................................................1005.2.2 Pastry协议.............................................101 5.2.3 Kademlia协议...........................................1025.3 性能测量..................................................104 5.3.1性能指标和模拟参数......................................104 5.3.2第一种结构化方法的性能..................................105 5.3.3最小度要求对系统性能的影响..............................106 5.3.4故障对服务发现的影响..................................114 5.4 总结......................................................1150结论1170参考文献1210第九页5.1Structure des modules du simulateur OMNeT++. . . . . . . . . . . . . .995.2Pourcentage de PSI en fonction du protocole P2P et de la taille du r´eseau . 106x0图表目录01.1 无向图和有向图..........................................9 1.2分布式系统的一些经典拓扑结构..............................11 1.3图的生成树示例(a)......................................12 1.4 阻碍链的基本链..........................................151.5 客户端-服务器模型和对等模型..............................17 1.6P2P架构分类............................................22 1.7 去中心化结构化对等架构示例[SMK +01].....................26 1.8 混合对等架构............................................2802.1 SOA交互模型..................................................35 2.2WSDL文档结构................................................40 2.3UDDI目录结构................................................41 2.4SOAP消息结构................................................42 2.5世界上一些流行的网格........................................45 2.6网格计算架构..................................................47 2.7网格与Web服务的融合..........................................52 2.8网格环境中的服务发现机制......................................54 2.9DIET架构......................................................5603.1 覆盖网络的架构..........................................66 3.2P2P4GS系统架构..........................................68 3.3 节点连接系统............................................733.4 结构化演化和网关PSI的选择...............................7404.1 S6服务执行场景.............................................95 4.2S10服务执行场景...........................................96Table des figures5.3Protocole Gia : Pourcentage de PSI form´es en fonction du degr´e minimalrequis (∆RequiredMinDegree) et de la taille du r´eseau . . . . . . . . . . . . . . 1075.4Protocole Pastry : Pourcentage de PSI form´es en fonction du degr´e minimalrequis (∆RequiredMinDegree) et de la taille du r´eseau . . . . . . . . . . . . . . 1085.5Protocole Kademlia : Pourcentage de PSI form´es en fonction du degr´e mi-nimal requis (∆RequiredMinDegree) et de la taille du r´eseau. . . . . . . . . . 1085.6Protocole Gia : Diam`etre de l’arbre couvrant en fonction du degr´e minimalrequis (∆RequiredMinDegree) et de la taille du r´eseau . . . . . . . . . . . . . . 1105.7Protocole Pastry : Diam`etre de l’arbre couvrant en fonction du degr´e mi-nimal requis (∆RequiredMinDegree) et de la taille du r´eseau. . . . . . . . . . 1105.8Protocole Kademlia : Diam`etre de l’arbre couvrant en fonction du degr´eminimal requis (∆RequiredMinDegree) et de la taille du r´eseau . . . . . . . . . 1115.9Nombre total de messages ´echang´es en fonction du ∆RequiredMinDegree id´ealdu protocole P2P sous-jacent et de la taille du r´eseau . . . . . . . . . . . . 1125.10 Diam`etre de l’arbre couvrant, en fonction du ∆RequiredMinDegree id´eal duprotocole P2P sous-jacent et de la taille du r´eseau . . . . . . . . . . . . . . 1135.11 Taux de succ`es d’une recherche de service en fonction du pourcentage denœuds en panne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114xiListe des Algorithmes1`A la r´eception d’un message responseStatus(idv, statusv) du nœud v . . . . . . .762`A la r´eception d’un message updateStatus(idv, statusv) du nœud v. . . . . . .773`A la r´eception d’un clusterManagement(serviceListv, neighListv) ou `a l’expira-timeout. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .806`A la r´eception de la description des contraintes de d´eploiement depuis le nœudnodeRequester . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .887`A la r´eception d’un message serviceDiscovery(keyReq, constraints, entryPoint,TTL) depuis le nœud v . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .898`A la r´eception d’une requˆete de recherche serviceQuery depuis le nœud nodeRequester 929`A la r´eception d’un message discoveryRequest(keyReq, serviceQuery, entryPoint,distance) depuis le nœud v. . . . . . . . . . . . . . . . . . . . . . . . . . . .9310`A la r´eception d’un message discoveryResponse(keyQuery, serviceFindList, distance)ou `a l’expiration du temps de recherche . . . . . . . . . . . . . . . . . . . . . .94xii0tion de  T timeout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 4 `A la r´eception d’un messagemasterRouteManagement( id v ) du nœud  v  . . . . . 78 5 `A la r´eception d’un messageresponseElection( id v ,  degree v ) ou `a l’expiration duListe des tableaux2.1Synth`ese des diff´erentes approches de d´ecouverte de services dans un envi-ronnement de grille . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .603.1Param`etres, variables et structure des messages de P2P4GS . . . . . . . . .754.1Param`etres, variables et structure des messages de gestion de P2P4GS . . .865.1Table de routage d’un pair d’identifiant 10233102 (extrait de Pastry [RD01])1025.2Param`etres de simulation pour l’´evaluation de la sp´ecification P2P4GS. . 105xiiiIntroductionContexte et motivations10Depuis son avènement, l’Internet a accéléré le développement d’applications danstous les domaines. L’évolution des systèmes informatiques a pour effet ledéveloppement de nombreuses ressources informationnelles, matérielles et logiciellesdistribuées, telles que les ressources de calcul et de stockage, les bases de données,les divers types d’applications et d’utilitaires, etc. Parallèlement à cedéveloppement, les besoins en termes de puissance de calcul, de capacité destockage, etc. sont de plus en plus grands. Face à cette demande croissante depuissance, la communauté informatique s’est intéressée aux architecturesdistribuées à large échelle de type grilles, afin d’offrir des solutions pour le stockagede données et le calcul réparti à un plus grand nombre d’applications etd’utilisateurs. Le principe des grilles est de mettre en commun des ressourcespartagées, distribuées et hétérogènes [FKT01]. Par le biais des grilles, les utilisateursont la possibilité d’accéder à des ressources distantes de calcul et de stockage, delancer des applications qui demandent des ressources inexistantes ou non disponibleslocalement.0D’autre part, cette évolution des systèmes informatiques a apporté une modificationprofonde dans la manière d’utiliser les ressources informatiques. En effet, avecl’émergence de l’architecture orientée service pour répondre aux problèmesd’interopérabilité, les ressources informatiques sont de plus en plus exposées sous laforme de services. Cette tendance de l’orientée service s’est manifestée dans lecadre du Web avec notamment les Services Web [CDK + 02] mais aussi dans le cadredes grilles informatiques avec les grilles de services. Ces grilles de services visent ainsià définir des mécanismes pour virtualiser les ressources et les restituer sous forme deservices, afin de pouvoir les assembler et les désassembler en fonction des besoinsdes utilisateurs [FKNT02a].0Dès lors, avec cette démocratisation des grilles, la gestion de ressources géographiquementdispersées et disponibles dans plusieurs organisations virtuelles (Universités, insti-Introduction20tuts, entreprises, etc.) implique de nombreux défis. En effet, les ressources sont denature très hétérogènes et dynamiques. Une gestion intégrale et transparente desressources est donc nécessaire pour conserver la consistance d’un tel système. Deplus, les demandes en puissance de calcul et en capacité de stockage sont de plus enplus énormes. Le système doit ainsi être en mesure de passer à l’échelle tout enlimitant les coûts de gestion et de communication. Pour répondre à ces exigences, lesgrilles n’ont pas cessé d’évoluer en termes d’architectures qui guident ledéveloppement de tous les composants d’une application. En effet, les systèmes degrilles traditionnelles présentent des architectures centralisées ou hiérarchiques. Detelles architectures sont sensib