Development of an incentive and scheduling mechanism for a Peer-to-Peer computing system

Abstract

Peer-to-Peer (P2P) computing offers new research challenges in the field of distributed computing. This paradigm can take advantage of a huge number of idle CPU cycles through Internet in order to solve very complex computational problems. All these resources are provided voluntarily by millions of users spread over the world. This means the cost of allocating and maintaining the resources is split and assumed by each owner/peer. For this reason, P2P computing can be seen as a low-cost alternative to expensive super-computers. Obviously, not every kind of parallel application is suitable for a P2P computing environment. Those with high communication requirements between tasks or with high QoS needs should still be performed in a Local Area Networking (LAN) environment. Otherwise, problems with huge computational requirements that can be easily split into millions of independent tasks are suitable for P2P computing, especially as solving these problems with a supercomputer would be extremely expensive. One of the most critical aspects in the design of P2P systems is the development of incentive techniques to enforce cooperation and resource sharing among participants. Incentive policies in P2P distributed computing systems is a new research field that requires specific policies to fight against malicious and selfish behavior by peers. Encouraging peers to collaborate in file-sharing has been widely investigated but, in the P2P computing field, this issue is still at a very early stage of research. Furthermore, the dynamics of peer participation are an inherent property of P2P systems and critical for design and evaluation. This further increases the difficulty of P2P computing. Another critical aspect of P2P computing systems is the development of scheduling techniques to achieve an efficient and scalable management of the computational resources. Unlike file-sharing, based on such immutable resources as files, the mutable ones, such as CPU and Memory are the principal resources involved in P2P computing. Inside the scheduling field, P2P computing can be seen as a particular variant of Grid computing. In a similar way as with the incentive polices, an extensive list of publications can be found that study the scheduling problems for distributed computing, such as Clusters or Grid computing, but few of these focus on P2P computing. For this reason, the scheduling problem in this kind of network is a field that still requires research in depth. In this thesis we propose a Distributed Incentive and Scheduling Integrated Mechanism (DISIM) with a two-level topology and designed to work on largescale distributed computing P2P systems. The low level is formed by associations of peers controlled by super-peers with major responsibilities in managing and gathering information about the state of these groups. Scalability limitations on the first level are avoided by providing the mechanism with an upper level, made up of super-peers interconnected through a logical overlay. Regarding incentives, we propose a mechanism based on credits with a twolevel topology designed to operate on different platforms of shared computing networks. One of the main contributions is a new policy for managing the credits, called Weighted, that increases peer participation significantly. This mechanism reflects P2P user dynamics, penalizes free-riders efficiently and encourages peer participation. Moreover, the use of a popular pricing strategy, called reverse Vickrey Auction, protects the system against malicious peer behavior. Simulation results show that our policy outperforms alternative approaches, maximizing system throughput and limiting free-riding behavior by peers. From the scheduling point of view, the low-level scheduler takes user dynamism into account and is almost optimal since it holds all the status information about the workload and computational power of its constituent peers. Our main contribution at the upper level is to propose three criteria that only use local information for scheduling tasks, providing the overall system with scalability. By setting these criteria, the system can easily, dynamically and rapidly adapt its behavior to very different kinds of parallel jobs in order toachieve an efficient performance. The results obtained proved the efficiency of the overall model and the convergence with the best assignment, achieved with an ideal centralized policy with global information.