A Frugal Bidding Procedure for Replicating WWW Content

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.





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.