Les grilles de calcul représentent une infrastructure capable de fournir des capacités de calcul, de stockage et de communication d'une manière transparente à l'utilisateur. Par définition, un service de grille est un service Web particulier qui fournit des interfaces bien définies et qui suit des conventions spécifiques (Al-Ali, Rana et al.,  2004), (Foster, 2001). Un service Web est un composant logiciel caractérisé  par son identifiant, noté URI, dont les interfaces publiques sont définies et appelées dans un document XML. Il peut être découvert par d'autres systèmes logiciels, ou d'autres services Web, par l'intermédiaire d'un dépôt central (UDDI) (Benatallah, Hacid et al.,  2005), (Oberle, Lamparter et al., 2005). L'avantage principal d'un service Web est la capacité de créer des applications par l'utilisation de composants logiciels faiblement connectés et réutilisables (Chinniciet,  Moreau et al., 2006), (Tjoa, Brezany et al., 2003).

Les services Web présentent un grand intérêt dans de nombreux domaines, entre autres dans les systèmes à grande échelle. De nombreux services ont été proposés pour permettre aux utilisateurs de développer et de déployer des applications à large échelle  (Fox, Pallickaran  et al., 2003), (Oberle, Lamparter et al., 2005). Afin de permettre une découverte efficace de ces services, nous avons besoin d'une plateforme performante, facile à utiliser et ouverte pour intégrer un grand nombre de services. Une telle plateforme devrait rendre possible la gestion efficace de services et en particulier, leur recherche à travers une grille. En effet, l'opération de recherche est essentielle puisqu'elle est nécessaire dans la plupart des autres opérations appliquées sur les services comme l'ajout, la modification, la suppression, la composition, etc.

Actuellement, chaque système de grille a un répertoire central dans lequel les services sont classés manuellement dans diverses catégories. Dans le système Globus par exemple, le répertoire principal est le Metacomputing Directory Service (MDS) (Denayer, 2004). Ce répertoire fournit un accès à l'information statique et dynamique concernant les nœuds de la grille et ses ressources. Il permet aux utilisateurs et aux autres applications de découvrir les données concernant les services et de les superviser. Si un utilisateur cherche un service donné, il passe en revue manuellement ce répertoire par catégorie ou par mot-clé (Denayer, 2004), (Shi, Zhang et al., 2005). Cette recherche qui n'est pas formelle, est fondée sur des règles ou des normes fixées par les fournisseurs de services. Si le demandeur n'est pas informé de l'emplacement du service ou de ses caractéristiques, il pourra difficilement trouver le service demandé. En raison de cette limitation, l'efficacité et l'exactitude de la recherche d’un service ne peuvent pas être garanties (Potts, Sedukhin  et al.,  2003), (Wang,  Huang et al.,  2003). Une bonne solution serait d'utiliser une méthode formelle pour modéliser la représentation de services dans les répertoires (Bruno,  Canfora et al.,  2005), ce qui faciliterait leur recherche dans une grille.

Le reste de cet article est organisé comme suit. La section 2 passe en revue les travaux liés à la recherche de services. La section 3 présente un modèle formel pour la recherche de services Web. Un algorithme de recherche et un exemple d'exécution sont décrits dans la section 4. Enfin la section 5 conclut ce papier et dégage quelques perspectives de travaux futurs.

Parfois, dans les répertoires d'une grille ou de services Web, il est difficile de déterminer avec exactitude à quelle catégorie un service pourrait appartenir, particulièrement dans le cas de ceux qui exécutent plusieurs fonctionnalités (Bruno,  Canfora et al.,  2005), (Denayer, 2004). Par exemple, supposons qu'il existe dans le répertoire d'une grille trois catégories de services : Management, Reservation et Execution. Un fournisseur de services veut publier un nouveau service de grille appelé LigthExecution effectuant les trois opérations suivantes :

• SearchIfExist qui indique si un service est en exécution,

• AllocateNode qui réserve un nœud spécifique de la grille,

• UpdateInstance qui permet de mettre à jour une instance d'un service.

La question est : dans quelle catégorie ce service doit-il être classé ?

Ce choix dépend du fournisseur de service. Mais, quelque soit l'endroit où le service sera placé, ceci ne garantit pas la localisation de ce service lors d'une recherche. Par exemple, si le service est classé dans la catégorie Reservation (puisqu'il offre une opération de réservation), un utilisateur qui cherche un service fournissant une opération de gestion d'un nœud, ne pourra pas le trouver. Au contraire, si le service est affecté à la catégorie Management, l'utilisateur qui cherche un service ayant la capacité de réservation, ne pourra pas également le trouver. Une méthode intuitive est d'enregistrer ce service dans toutes les catégories, ce qui peut générer de la redondance dans le répertoire.

Notre modèle est fondé sur une recherche orientée opération qui permet à un utilisateur de chercher un service (ou un ensemble de services) exécutant un ensemble d'opérations.

La recherche d'un service est une action importante dans la gestion de services. En effet, toute utilisation d'un service nécessite d'abord sa recherche. Par exemple, pour la suppression d'un service, nous devons d'abord le rechercher avant de le supprimer.

Dans le cas général, un mécanisme de recherche doit avoir les propriétés suivantes (Denayer, 2004) :

• Précis i.e. les résultats retournés doivent correspondre aux  critères de recherche.

• Rapide i.e.  le temps de réponse doit être le plus court possible.

• Efficace i.e. la totalité des résultats ne devrait pas être trop grande. Le fait de donner un résultat ayant une cardinalité faible et un degré de correspondance élevé est plus intéressant que de produire des résultats importants avec des degrés de correspondance faibles.

La particularité de l'opération de recherche dans le domaine des services réside dans la notion même de service. En effet, la réponse à la requête d'un utilisateur n'est pas booléenne. Dans le cas de recherche d'un service, plusieurs réponses sont possibles :

• aucun service ne couvre les opérations demandées ;

• un ou plusieurs services couvrent exactement les opérations demandées ;

• un ou plusieurs services couvrent totalement les opérations demandées mais offrent d'autres opérations ;

• aucun service ne couvre totalement les opérations demandées et l'union des services trouvés ne couvre pas les opérations demandées ;

• aucun service ne couvre totalement les opérations demandées mais l'union des services trouvés couvre les opérations demandées.

Benatallah, Hacid et al. (2005) utilisent  les logiques de description (DL's) comme cadre formel pour la gestion automatique de services. Les DL's sont une famille de logiques qui ont été développées pour modéliser les structures hiérarchiques complexes et les doter d’un moteur de raisonnement spécialisé (Benatallah, Hacid et al., 2005).

D'autres travaux présentant la notion de service Web sémantique ont été proposés dans (Fox, Pallickaran  et al., 2003), (Merwe, Obiedkov et al., 2004). Ces travaux s'orientent vers la création de normes sémantiques pour permettre l'automatisation complète de la gestion (et la recherche) de services Web. Ils ne sont pas fondés simplement sur la syntaxe du service, mais également sur sa sémantique. (Fox, Pallickaran  et al., 2003) et utilisent la notion de similitude pour rechercher des services. Cependant, il peut être peu convenable de chercher un service selon l'approche de similarité, parce que deux services peuvent ne pas être semblables globalement mais ils peuvent l'être au niveau des opérations.

D'autres travaux utilisent l'ontologie de service dont les instances représentent les services Web (Kovacs, 2003). L'idée est de pouvoir faire la recherche sur le contenu du service plutôt que sur la base de mots-clés. L'ontologie est utile dans le contexte des services de grille car elle permet d'unifier ou de normaliser les caractéristiques des services demandés et fournis.

L'ensemble de ces travaux ne satisfait pas, dans tous les cas, les exigences des utilisateurs. En effet, les utilisateurs recherchent un service doté d’opérations spécifiques car, pour un utilisateur, les opérations exécutées par un service sont plus importantes que les autres facteurs tels que son nom, sa localisation, sa catégorie, etc.

Notre approche privilégie une recherche fondée sur les opérations exécutées par un service. En fait, quand un service est publié, son fournisseur précise dans un fichier WSDL  (Web Service Description Language), la description de ce service (Chinniciet,  Moreau et al., 2006). Ce fichier décrit le type du service Web (opérations réalisées et types des paramètres) et les aspects techniques d'implantation du service. Notre travail exploite ce fichier qui contient plusieurs parties. La partie appelée PortType décrit les opérations offertes par ce service. Dans la suite, nous désignons par opération d'un service, une opération décrite dans la partie PortType.

Dans cette section, nous introduisons les treillis de Galois que nous utiliserons pour la définition de notre approche.

Un contexte formel est un riplet   où S est un ensemble de services, O un ensemble d'opérations, et R  une relation binaire . Soit et , la notation sRo indique que le service s exécute l'opération o. Cette relation peut être représentée par une table T, appelée table de contexte, où T[i,j]=1 si S_iRo_j et 0 sinon (voir Table 1) (Berry, McConnell et al., 2006), (Bruno, Canfora et al.,  2005), (Hao et YoungQiang, 2004).

Un service exécute au moins une opération et n'importe quelle opération est exécutée, au moins, par un service.

Ayant un sous-ensemble d'opérations O = {op₁,op₂,...,op_k} et un sous-ensemble de services S={s₁,s₂,...,s_l}, un concept est un couple (S,O) où f(S)=O, et g(O)=S (Berry, McConnell et al., 2006), (Hao et YoungQiang, 2004), (Ludwig et Santen, 2002).

S est appelé intend de O et représente le sous-ensemble des services qui réalisent toutes les opérations de O. O est appelée l'extend de S et contient toutes les opérations communes à tous les services de l'ensemble S.

L'ensemble des concepts peut être représenté par un graphe dont les nœuds sont les concepts et les arcs sont les relations entre concepts. Ce graphe (ou diagramme) peut être classé par niveaux. Au niveau le plus haut (niveau 0), nous trouvons le concept dont l'extend contient toutes les opérations et l’intend est l'ensemble vide. Le niveau 1 représente les concepts ayant en commun une seule opération. Au niveau i, figurent tous les concepts dont le nombre d'opérations communes est égal à i. Le dernier niveau rassemble tous les services en intend et l'ensemble vide en extend.

En parcourant ce diagramme de haut en bas, nous avons de plus en plus d'opérations communes dans les concepts (plus spécifiques), et des intend (services) plus généraux. Nous proposons d'utiliser cette hiérarchie (opération, service) pour la recherche de services fondée sur les opérations. Ainsi, est-il important de classer les concepts avec le minimum  d'opérations communes au niveau le plus haut du graphe.

L'exemple de la table 1 comprend cinq services et cinq opérations. Le diagramme qui lui est associé est illustré par la figure 1. Ce diagramme contient plusieurs concepts : quatre d’entre eux relèvent du niveau 1 avec une seule opération dans l'extend tandis que quatre du niveau 2 ont chacun deux opérations dans l'extend, etc.

Nous supposons qu'un utilisateur recherche un service qui exécute des opérations formulées dans une requête.

Notre algorithme de recherche parcourt les concepts de haut en bas (selon le graphe) pour tenter de répondre à la requête de l'utilisateur. Ainsi, si l'algorithme trouve un service qui peut satisfaire la demande de l'utilisateur, il s'arrête. Le comportement de l'algorithme proposé peut se définir comme suit :

• l’étape 1 calcule les niveaux et affecte des concepts à ces niveaux (lignes 1-6) ;

• l’étape 2 initialise les variables (lignes 7-9) ;

• l’étape 3 parcourt un seul niveau pour chercher les opérations de la requête utilisateur (lignes 11-16) ;

• l’ étape 4 parcourt tous les niveaux (lignes 10-18).

Algorithme

Input :

C = (W, O, R) un contexte.

Req = {Op₁,Op₂,...,Op_k} une requête.

Output :

Un ensemble de services qui réalisent les opérations de la requête.

GraphLevel = CalculateLevels()

Level[][] =

For i = 1 to ConceptsNum Do

j = Level(Concept(W,O))

Level[j][] = Level[j][] + Concept(W,O)

End For

Res =

Found = False

i = SizeOf(Req)

Repeat  

For j=1 to Levelsize[i] do

The current concept is (W,O)  /* W set of services

If Req O Then       /* O set of operations

Res = Res {W-Res}

Found =True

End For

i=i+1

Until i>=GraphLevel or Found = True

Return Res

Dans la première partie de l'algorithme, nous commençons par le calcul du niveau du graphe et le niveau de chaque concept (lignes 1-6) et nous stockons chaque concept dans son niveau. Le niveau d'un concept est le nombre d'opérations dans l'extend du concept. La valeur initiale du résultat est l'ensemble vide noté (ligne 7). Nous commençons le parcours par le

 niveau qui est égal au nombre d'opérations dans la requête (lignes 9-10). Pour chaque niveau, l'algorithme passe en revue les concepts un par un (ligne 11) et teste si la requête est égale ou est  incluse dans le sous-ensemble O, l'extend du concept (lignes 12-13). Si le test est concluant, alors il faut ajouter l’intend du concept, i.e. les services Web, au résultat (ligne 14). Pour éviter la répétition d'un service dans le résultat, nous vérifions s'il est déjà apparu dans ce résultat (ligne 14). Si nous trouvons un résultat pour le niveau actuel, l'algorithme s'arrête et nous retournons le résultat. Dans l'autre cas, nous irons au niveau suivant (ligne 17) et répéterons le même travail au niveau suivant (ligne 18). Cette répétition se termine si nous trouvons un résultat ou si tous les niveaux sont parcourus sans résultat (ligne 18). Il est important de noter que la première partie de l'algorithme (lignes 1-6) sera exécutée une seule fois. Nous ne devons pas recalculer les niveaux pour chaque opération de recherche, à moins que le graphe ait subi des modifications (nouveau service, suppression ou modification d'un service, etc.).

Soit H le nombre de niveaux dans un graphe et L le nombre maximum de nœuds d'un niveau. Les complexités minimales et maximales de notre algorithme sont respectivement de O(L) et O(H*L). Dans le premier cas ceci veut dire que nous avons trouvé le service au premier niveau parcouru. Dans le second cas, l'algorithme parcourt tous les niveaux sans succès. Dans les deux cas la complexité est linéaire.

Dans cette section, nous présenterons deux exemples d'application de l'algorithme proposé. Considérons le contexte donné par la table 2. Ce contexte contient huit opérations et dix services. Dans le premier exemple, nous considérons la requête Req1 = {Op1, Op3, Op7} alors que dans le second, il s’agit de la requête Req2 = {Op1, Op6}.

La recherche de concepts et la création des niveaux du contexte de l’exemple permet de dégager les concepts classés par niveaux, comme indiqué dans la table 3.

Dans la table 2, nous remarquons que les seuls services qui fournissent les opérations {Op1, Op3, Op7} sont S1 et S6. On voudrait vérifier si notre algorithme permet d'obtenir ce résultat.

La table 4 montre le déroulement de notre algorithme pour le premier exemple et confirme le résultat attendu, à savoir les services S1 et S6.

Considérons maintenant la deuxième requête Req2={Op1, Op6}. L'algorithme commence avec le niveau 2 qui correspond au nombre d'opérations dans la requête. Ce niveau ne contient aucun concept dont l'extend est égal à la requête. Ensuite, l'algorithme parcourt les niveaux suivants sans succès. Les détails de l'exécution de l'algorithme pour cet exemple sont représentés par la Table 5. Nous remarquons que l'algorithme donne le résultat escompté, à savoir aucun service relatif à la requête.

Dans cet article, nous avons proposé une nouvelle méthode pour la recherche de services dans une grille. C’est une méthode formelle de recherche de services basée sur les treillis de Galois. Partant de cette méthode, nous avons développé un algorithme de recherche que nous avons illustré à travers deux exemples.

Comme perspective à court terme, nous pensons définir la notion de similarité entre services pour répondre aux requêtes utilisateurs. Par ailleurs, nous envisageons d'exploiter les potentialités des ontologies dans la recherche de services similaires dans les grilles.