A Fast Replica Placement Methodology for Large-scale Distributed Computing Systems

Authors: Samee Ullah Khan, C. Ardil

Abstract:

Fine-grained data replication over the Internet allows duplication of frequently accessed data objects, as opposed to entire sites, to certain locations so as to improve the performance of largescale content distribution systems. In a distributed system, agents representing their sites try to maximize their own benefit since they are driven by different goals such as to minimize their communication costs, latency, etc. In this paper, we will use game theoretical techniques and in particular auctions to identify a bidding mechanism that encapsulates the selfishness of the agents, while having a controlling hand over them. In essence, the proposed game theory based mechanism is the study of what happens when independent agents act selfishly and how to control them to maximize the overall performance. A bidding mechanism asks how one can design systems so that agents- selfish behavior results in the desired system-wide goals. Experimental results reveal that this mechanism provides excellent solution quality, while maintaining fast execution time. The comparisons are recorded against some well known techniques such as greedy, branch and bound, game theoretical auctions and genetic algorithms.

Keywords: Data replication, auctions, static allocation, pricing.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1074515

References:

[1] M. Arlitt and T. Jin, "Workload characterization of the 1998 World Cup Web Site," Technical Report, Hewlett Packard Lab, Palo Alto, HPL- 1999-35(R.1), 1999.
[2] K. Calvert, M. Doar, E. Zegura, "Modeling Internet Topology," IEEE Communications, 35(6), pp. 160-163, 1997.
[3] D. Grosu and A. Chronopoulos, "Algorithmic Mechnism Design for Load Balancing in Distributed Systems," IEEE Trans. Systems, Man and Cybernatics B, 34(1), pp. 77-84, 2004.
[4] S. Jamin, C. Jin, Y. Jin, D. Riaz, Y. Shavitt and L. Zhang, "On the Placement of Internet Instrumentation," in IEEE INFOCOM, 2000.
[5] S. Khan and I. Ahmad, "Heuristic-based Replication Schemas for Fast Information Retrevial over the Internet," in 17th International Conference on Parallel and Distributed Computing Systems, San Francisco, U.S.A., 2004.
[6] S. Khan and I. Ahmad, "A Game Theoretical Solution for Web Content Replication," Technical Report, CSE-UTA, 2004.
[7] S. Khan and I. Ahmad, "A Pure Nash Equilibrium-based Game Theoretical Method for Data Replication across Multiple Servers," IEEE Transactions on Knowledge and Data Engineering, accepted to appear in 2009.
[8] B. Li, M. Golin, G. Italiano and X. Deng, "On the Optimal Placement of Web Proxies in the Internet," in IEEE INFOCOM, 2000.
[9] T. Loukopoulos, and I. Ahmad, "Static and Adaptive Distributed Data Replication using Genetic Algorithms," Journal of Parallel and Distributed Computing, 64(11), pp. 1270-1285, 2005.
[10] T. Loukopoulos, I. Ahmad, and D. Papadias, "An Overview of Data Replication on the Internet," in IEEE International Symposium on Parallel Processing and Networking, pp. 31-36, 2002.
[11] N. Nisan and A. Ronen, "Algorithimic Mechanism Design," in 31st ACM Symposium on Theory of Computing, pp. 129-140, 1999.
[12] L. Qiu, V. Padmanabhan and G. Voelker, "On the Placement of Web Server Replicas," in IEEE INFOCOM, 2001.
[13] S. Rhea, C. Wells, P. Eaton, D. Geels, B. Zhao, H. Weatherspoon, J. Kubiatowicz, "Maintenance-free Global Storage," IEEE Internet Computing, 5(5), pp. 40-49, 2001.
[14] W. Vickrey, "Counterspeculation, Auctions and Competitive Sealed Tenders," Journal of Finance, pp. 8-37, 1961.