Design and analysis of an adaptive object replication algorithm in distributed network systems

Abstract

In this paper, we propose an adaptive object replication algorithm for distributed network systems, analyze its performance from both theoretical and experimental standpoints. We first present a mathematical cost model that considers all the costs associated with servicing a request, i.e., I/O cost, control-message transferring cost, and data-message transferring cost. Using this cost model, we develop an adaptive object replication algorithm, referred to as Adaptive Distributed Request Window (ADRW) algorithm. Our objective is to dynamically adjust the allocation schemes of objects based on the decision of ADRW algorithm, i.e., whether the system is read-intensive or write-intensive, so as to minimize the total servicing cost of the arriving requests. Competitive analysis is carried out to study the performance of ADRW algorithm theoretically. We then implement our proposed algorithm in a PC based network system. The experimental results convincingly demonstrate that ADRW algorithm is adaptive and is superior to several related algorithms in the literature in terms of the average request servicing cost. © 2008 Elsevier B.V. All rights reserved.