Automatic Clustering for Self-Organizing Grids

Computational grids have not scaled effectively due to administrative hurdles to resource and user participation. Most production grids are essentially multi-site supercomputer centers, rather than truly open and heterogeneous sets of resources that can join and leave dynamically, and that can provide support for an equally dynamic set of users. Large-scale grids containing individual resources with more autonomy about when and how they join and leave will require self-organizing grid middleware services that do not require centralized administrative control. This paper considers one such service, namely the dynamic discovery of high-performance variable-size clusters of grid nodes. A brute force approach to the problem of identifying these "ad-hoc clusters" would require excessive overhead in terms of both message exchange and computation. Therefore, we propose a scalable solution that uses a delay-based overlay structure to organize nodes based on their proximity to one another, using a small number of delay experiments. This overlay can then be used to provide a variable-size set of promising candidate nodes than can then be used as a cluster, or tested further to improve the selection. Simulation results show that this approach results in effective clustering with acceptable overhead