A Frugal Bidding Procedure for Replicating WWW Content

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: Internet, data content replication, static allocation, mechanism design, equilibrium.

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

References:

[1] P. Apers, "Data Allocation in Distributed Database Systems," ACM Transactions on Database Systems, 13(3), pp. 263-304, 1988.
[2] A. Archer and E. Tardos, "Truthful Mechanism for One-parameter Agents," in Proc. Of 42nd IEEE FOCS, pp. 482-491, 2001.
[3] M. Arlitt and T. Jin, "Workload characterization of the 1998 World Cup Web Site," Tech. report, Hewlett Packard Lab, Palo Alto, HPL-1999- 35(R.1), 1999.
[4] K. Calvert, M. Doar, E. Zegura, "Modeling Internet Topology," IEEE Communications, 35(6), pp. 160-163, 1997.
[5] C. Ceri, G. Pelagatti, and G. Martella, "Optimal File Allocation in a Computer Network: A Solution based on Knapsack Problem," Computer Networks, vol. 6, pp. 345-357, 1982.
[6] M. Charikar, S. Guha, E. Tardos and D. Shmoys, "A Constant-Factor Approximation Algorithm for the K-Median Problem," in ACM STOC, pp. 1-10, 1999.
[7] B. Davison, "A Survey of Proxy Cache Evaluation Techniques," in Proc. of the 4th International Web Caching Workshop, 1999.
[8] A. Fiat, R. Karp, M. Luby, L. McGeoch, D. Sleator and N. Young, "Competitive Paging Algorithms," Journal of Algorithms, 12(4), pp. 685- 699, 1991.
[9] S. Floyd and V. Paxson, "Difficulties in Simulating the Internet," IEEE/ACM Trans. Networking, 9(4), pp. 253-285, 2001.
[10] M. Garey and D. Johnson, Computers and Intractability, W.H. Freeman and Co., 1979.
[11] J. Green and J. Laffont, "Characterization of Satisfactory Mechnisms for the revelation of Preferences for Public Goods," Econometrica, pp. 427- 438, 1977.
[12] T. Groves, "Incentives in Teams," Econometrica, pp. 617-631, 1973.
[13] 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.
[14] S. Jamin, C. Jin, Y. Jin, D. Riaz, Y. Shavitt and L. Zhang, "On the Placement of Internet Instrumentation," in Proc. of the IEEE INFOCOM, 2000.
[15] S. Jamin, C. Jin, T. Kurc, D. Raz and Y. Shavitt, "Constrained Mirror Placement on the Internet," in Proc. of the IEEE INFOCOM, 2001.
[16] J. Kangasharju, J. Roberts and K. Ross, "Object Replication Strategies in Content Distribution Networks," in Proc. of Web Caching and Content Distribution Workshop, pp. 455-456, 2001.
[17] S. U. Khan and I. Ahmad, "Heuristics-based Replication Schemas for Fast Information Retrieval over the Internet," in 17th International Conference on Parallel and Distributed Computing Systems (PDCS), San Francisco, CA, USA, September 2004, pp. 278-283.
[18] S. U. Khan and I. Ahmad, "A Powerful Direct Mechanism for Optimal WWW Content Replication," in 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS), Denver, CO, USA, April 2005.
[19] S. U. Khan and I. Ahmad, "A Game Theoretical Extended Vickery Auction Mechanism for Replicating Data in Large-scale Distributed Computing Systems," in International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA), Las Vegas, NV, USA, June 2005, pp. 904-910.
[20] S. U. Khan and I. Ahmad, "RAMM: A Game Theoretical Replica Allocation and Management Mechanism," in 8th International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN), Las Vegas, NV, USA, December 2005, pp. 160-165.
[21] S. U. Khan and I. Ahmad, "A Powerful Direct Mechanism for Optimal WWW Content Replication," in 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS), Denver, CO, USA, April 2005.
[22] S. U. Khan and I. Ahmad, "A Game Theoretical Extended Vickery Auction Mechanism for Replicating Data in Large-scale Distributed Computing Systems," in International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA), Las Vegas, NV, USA, June 2005, pp. 904-910.
[23] S. U. Khan and I. Ahmad, "RAMM: A Game Theoretical Replica Allocation and Management Mechanism," in 8th International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN), Las Vegas, NV, USA, December 2005, pp. 160-165.
[24] S. U. Khan and I. Ahmad, "Discriminatory Algorithmic Mechanism Design Based WWW Content Replication," Informatica, vol. 31, no. 1, pp. 105-119, 2007.
[25] S. U. Khan and I. Ahmad, "Game Theoretical Solutions for Data Replication in Distributed Computing Systems," in Handbook of Parallel Computing: Models, Algorithms, and Applications, S. Rajasekaran and J. Reif, Eds., Chapman & Hall/CRC Press, Boca Raton, FL, USA, 2007, ISBN 1-584-88623-4, Chapter 45.
[26] S. U. Khan and I. Ahmad, "A Semi-Distributed Axiomatic Game Theoretical Mechanism for Replicating Data Objects in Large Distributed Computing Systems," in 21st IEEE International Parallel and Distributed Processing Symposium (IPDPS), Long Beach, CA, USA, March 2007.
[27] B. Khargharia, S. Hariri, F. Szidarovszky, M. Houri, H. El-Rewini, S. U. Khan, I. Ahmad, and M. S. Yousif, "Autonomic Power and Performance Management for Large-Scale Data Centers," in 21st IEEE International Parallel and Distributed Processing Symposium (IPDPS), Long Beach, CA, USA, March 2007.
[28] S. U. Khan, "Game Theoretical Techniques for Designing Counter- Terrorism Systems," in 5th International Symposium on Defense and Security, vol. 6560 of SPIE (Society of Photo-Optical Instrumentation Engineers), Orlando, FL, USA, April 2007, pp. 74-82.
[29] S. U. Khan and I. Ahmad, "A Cooperative Game Theoretical Replica Placement Technique," in 13th International Conference on Parallel and Distributed Systems (ICPADS), Hsinchu, Taiwan, December 2007.
[30] S. U. Khan and I. Ahmad, "Comparison and Analysis of Ten Static Heuristics-based Internet Data Replication Techniques," Journal of Parallel and Distributed Computing, vol. 68, no. 2, pp. 113-136, 2008.
[31] S. U. Khan, A. A. Maciejewski, H. J. Siegel, and I. Ahmad, "A Game Theoretical Data Replication Technique for Mobile Ad Hoc Networks," in 22nd IEEE International Parallel and Distributed Processing Symposium (IPDPS), Miami, FL, USA, April 2008.
[32] I. Ahmad, S. Ranka, and S. U. Khan, "Using Game Theory for Scheduling Tasks on Multi-core Processors for Simultaneous Optimization of Performance and Energy," in 22nd IEEE International Parallel and Distributed Processing Symposium (IPDPS), Miami, FL, USA, April 2008.
[33] S. U. 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, vol. 20, no. 3, pp. 346- 360, 2009.
[34] S. U. Khan and I. Ahmad, " Cooperative Game Theoretical Technique for Joint Optimization of Energy Consumption and Response Time in Computational Grids," IEEE Transactions on Parallel and Distributed Systems, vol. 21, no. 4, pp. 537-553, 2009.
[35] S. U. Khan and C. Ardil, "A Weighted Sum Technique for the Joint Optimization of Performance and Power Consumption in Data Centers," International Journal of Electrical, Computer, and Systems Engineering, vol. 3, no. 1, pp. 35-40, 2009.
[36] V. Krishna, Auction Theory, Academic Press, 2002.
[37] Y. Kwok, K. Karlapalem, I. Ahmad and N. Pun, "Design and Evaluation of Data Allocation Algorithms for Distributed Database Systems," IEEE Journal on Selected areas in Communication, 14(7), pp. 1332-1348, 1996.
[38] B. Lee and J. Weissman, "Dynamic Replica Management in the Service Grid," in Proc. of IEEE International Symposium on High Performance Distributed Computing, 2001.
[39] B. Li, M. Golin, G. Italiano and X. Deng, "On the Optimal Placement of Web Proxies in the Internet," in Proc. of the IEEE INFOCOM, 2000.
[40] T. Loukopoulos, and I. Ahmad, "Static and Adaptive Distributed Data Replication using Genetic Algorithms," Accepted to appear in Journal of Parallel and Distributed Computing.
[41] T. Loukopoulos, I. Ahmad, and D. Papadias, "An Overview of Data Replication on the Internet," in Proc. of ISPAN, pp. 31-36, 2002.
[42] S. March and S. Rho, "Allocating Data and Operations to Nodes in Distributed Database Design," IEEE Trans. Knowledge and Data Engineering, 7(2), pp.305-317, 1995.
[43] S. Martello and P. Toth, Knapsack Problems: Algorithms and Computer Implementations, John Wiley & Sons, 1990.
[44] A. Mas-Collel, W. Whinston and J. Green, Microeconomic Theory, Oxford University Press, 1995.
[45] B. Narebdran, S. Rangarajan and S. Yajnik, "Data Distribution Algorithms for Load Balancing Fault-Tolerant Web Access," in Proc. of the 16th Symposium on Reliable Distributed Systems, 1997.
[46] N. Nisan and A. Ronen, "Algorithimic Mechanism Design," in Proc. of 31st ACM STOC, pp. 129-140, 1999.
[47] L. Qiu, V. Padmanabhan and G. Voelker, "On the Placement of Web Server Replicas," in Proc. of the IEEE INFOCOM, 2001.
[48] M. Rabinovich, "Issues in Web Content Replication," Data Engineering Bulletin, 21(4), 1998.
[49] M. Rabanovich and O. Spatscheck, Web Caching and Replication, Addison-Wesley, 2002.
[50] 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.
[51] S. Saurabh and D. Parkes, "Hard-to-Manupilate VCG-Based Auctions," Avaialable at: http://www.eecs.harvard.edu/econcs/pubs/hard_to_manipulate.pdf
[52] M. Sayal, Y. Breitbart, P. Scheuermann and R. Vingralek, "Selection Algorithms for Replicated Web Servers," in Proc. of the Workshop on Internet Server Performance, 1998.
[53] S. So, I. Ahmad and K. Karlapalem, "Response Time Driven Multimedia Data Objects Allocation for Browsing Documents in Distributed Environments," IEEE Transactions on Knowledge and Data Engineering, 11(3), pp. 386-405, 1999.
[54] W. Vickrey, "Counterspeculation, Auctions and Competitive Sealed Tenders," Journal of Finance, pp. 8-37, 1961.
[55] A. Vigneron, L. Gao, M. Golin, G. Italiano and B. Li, "An Algorithm for Finding a K-Median in a Directed Tree," Information Processing Letters, vol. 74, pp. 81-88, 2000.
[56] G. Zipf, Human Behavior and the Principle of Least-Effort, Addison- Wesley, 1949.