Application service placement in stochastic grid environments using learning and ant-based methods

Abstract

Achieving acceptable application performance in a grid environment remains a difficult challenge. In particular, this is true for applications composed of services that require certain criteria regarding quality to be fulfilled in order to satisfy users' needs. The problem considered here is the partitioning of application services onto the available execution nodes of a grid environment in such a way that they satisfy certain minimum criteria regarding quality. Fundamentally, this is an NP-hard problem. We propose three algorithms based on the concepts of learning automata and the metaphor of foraging ants. The algorithms naturally follow a decentralised multi-agent method for solving the service partitioning problem. Moreover, they establish a distributed problem-solving mechanism that does not require the use of a central controller. The proposed algorithms have been rigorously tested and evaluated through extensive simulations on randomly generated application services and grid environments. The results indicate that learning is an essential component for achieving scalability and efficiency in nature-inspired systems.