A dynamic prefix tree for service discovery within large scale grids

Eddy Caron (1) , Frédéric Desprez (1) , Cédric Tedeschi (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

Within computational grids, some services (software components, linearalgebra libraries, etc.) are made available by some servers to some clients.In spite of the growing popularity of such grids, the service discovery,although efficient in many cases, does not reach several requirements.Among them, the flexibility of the discovery and its efficiency on wide-area dynamic platforms are two major issues. Therefore, it becomescrucial to propose new tools coping with such platforms. Emerging peer-to-peer technologies provide algorithms allowing the distribution and theretrieval of data items while addressing the dynamicity of the underlyingnetwork.We study in this paper the service discovery in a pure peer-to-peer environment. We describe a new trie-based approach for the service discoverythat supports range queries and automatic completion of partial searchstrings, while providing fault-tolerance, and partially taking into accountthe topology of the underlying network. We validate this approach bothby analysis and simulation. Traditional metrics considered in peer-to-peer systems exhibits interesting complexities within our architecture.The analysis' results are confirmed by some simulation experiments runusing several grid's data sets.

Dans les grilles des serveurs offrent des services aux clients afin de réaliser des calculs. Avant de pouvoir les utiliser, les clients doivent être àmême de les retrouver. Bien que les différentes solutions proposées depuisl'émergence des grilles soient efficaces sur des plates-formes relativementstatiques et de petite échelle, elles ne sont plus en adéquation avec lanature dynamique et à large échelle des grilles futures. Pour de tels environnements de nouveaux outils doivent être proposés, notamment desmécanismes pour la découverte de services, qui devront être flexibles etpasser à l'échelle dans des environnements dynamiques. Nous étudionsdans ce papier la découverte de services pour des grilles de calcul pair-à-pair. Nous proposons une nouvelle architecture basée sur un arbre deplus long préfixes.

Mots clés: Computational grids; Peer-to-peer; Prefix trees; Service discovery

Mots clés: Arbres de préfixes; Découverte de services; Grilles de calcul; Pair-à-pair

Domaines: Informatique [cs]

Eddy Caron, Frédéric Desprez, Cédric Tedeschi. A dynamic prefix tree for service discovery within large scale grids. [Research Report] Laboratoire de l'informatique du parallélisme. 2006, 2+14p. ⟨hal-02102481⟩