Sog: a self-organized grouping infrastructure for grid resource discovery
Sukumar Ghosh, Shaowen Wang, Anand Padmanabhan · 2006
Dynamic and heterogeneous characteristics of large-scale Grids make the fundamental problem of resource discovery a great challenge. This thesis presents a self-organized grouping (SOG) infrastructure that achieves efficient Grid resource discovery by forming and maintaining autonomous resource groups. Each group dynamically aggregates a set of resources that are similar to each other in some prespecified resource characteristic. The SOG method takes advantage of the strengths of both centralized and decentralized approaches that were previously developed for Grid/P2P resource discovery. The design of the SOG method minimizes the overhead incurred in forming and maintaining groups and maximizes resource discovery performance. The way SOG method handles resource discovery queries is metaphorically similar to searching for a word in an English dictionary by identifying its alphabetical groups at the first place and then performing a lexical search within the group. The algorithms implemented in SOG method are illustrated with details. This thesis also illustrates a generalized approach using a space-filling curve on a self-organized grouping (SOG) overlay infrastructure. In particular, we focus on multi-attribute range queries through the use of Hilbert space-filling curve to preserve locality while reducing high dimension attribute space to 1-dimension. This locality preservation allows a 1-dimensional grouping attribute to be used by SOG infrastructure. Our approach combines the strength of Hilbert space-filling curve in handling multi-attribute range query, with the strength of SOG infrastructure in providing efficient Grid resource discovery. Conducting a series of computational experiments we show that the SOG method achieves more scalable, stable and efficient look up performance than other existing approaches. Experiments also show that the approach has little dependence on factors such as resource density, query type and Grid size. Theoretical analysis presented also validates some of the experimental observations.