First approach for a decentralized resource allocation in ad hoc grids

Abstract

As more people and organizations use computers, the demands on computer systems have changed. Therefore, with increasing the number of participants, the scalability has become an important issue for managing resource allocation. A centralized system relies on one computer node that processes the whole application. In such systems, a small number of nodes provide the resources that can only serve a limited number of clients. On one hand, if the centralized system becomes large enough, load balancing will create too much overhead. On the other hand, limitation on the network bandwidth increases the network bottleneck which affects the system performance. Decenralizing control, distributing processing loads and network bandwidth among all participating nodes will reduce the overhead in very large systems. In this light, Peer-To-Peer(P2P) systems offer an alternative solution to old server-based approach. Generally, a P2P system must have three essential properties. First, the system needs to be scalable. That is, it does not rely on single points of failures and bottlenecks. Second, the P2P system needs to be self-organized when peers arbitrarily join and leave the system. Third, the system needs to be fault-tolerant. In other words, the system must be robust when subjected to faults. In this thesis, we propose a dynamic decentralized P2P resource allocation method having as many resource allocators as required given the number of nodes, tasks and resources. In spite of the capability of the proposed resource allocation scheme for implementing on any structured overlay system, we implemented our application on Pastry as the underlying structured overlay system. We investigated the matchmaking process in the fully populated system when all resource allocators are active as well as the non-fully populated system when only some resource allocators perform resource allocation process. As we wanted to have a self-organized system in terms of resource allocators, we defined a mechanism that dynamically segment/desegment the ad hoc grid by promoting/demoting resource allocator(s) according to the workload of the existing resource allocator(s). This mechanism enables the ad hoc grid to adapt itself to the changing environment from a centralized to a decentralized form and back to the centralized form.