Replicating Data Objects in Large-scale Distributed Computing Systems using Extended Vickrey Auction

This paper proposes a novel game theoretical technique to address the problem of data object replication in largescale distributed computing systems. The proposed technique draws inspiration from computational economic theory and employs the extended Vickrey auction. Specifically, players in a non-cooperative environment compete for server-side scarce memory space to replicate data objects so as to minimize the total network object transfer cost, while maintaining object concurrency. Optimization of such a cost in turn leads to load balancing, fault-tolerance and reduced user access time. The method is experimentally evaluated against four well-known techniques from the literature: branch and bound, greedy, bin-packing and genetic algorithms. The experimental results reveal that the proposed approach outperforms the four techniques in both the execution time and solution quality.




References:
[1] T. Loukopoulos, and I. Ahmad, "Static and adaptive distributed data
replication using genetic algorithms," J. of Parallel and Distributed
Comput., vol. 64, no. 11, pp. 1270-1285, 2004.
[2] B. Awerbuch, Y. Bartal and A. Fiat, "Competitive distributed file
allocation," in Proc. of 25th ACM Symp. on Theory Of Comput.,
Victoria, B.C., Canada, 1993, pp. 164-173.
[3] T. Abdelzaher and N. Bhatti, "Web content adaptation to improve sever
workload behavior," Comput. Networks, vol. 21, no. 11, pp. 1536-1577,
1999.
[4] A. Heddaya and S. Mirdad, "WebWave: Globally load balanced fully
distributed caching of hot published documents," in Proc. 17th Intl.
Conf. on Distributed Comput. Systems, Baltimore, Maryland, 1997, pp.
160-168.
[5] J. Kangasharju, J. Roberts and K. Ross, "Object replication strategies in
content distribution networks," in Proc. of Workshop on Content
Caching and Distribution, 2001, pp. 455-466.
[6] S. Khan and I. Ahmad, "Heuristic-based replication schemas for fast
information retrieval over the internet," in Proc. of 17th Intl. Conf. on
Parallel and Distributed Comput. Systems, 2004, pp. 278-283.
[7] S. Mahmoud and J. Riordon, "Optimal allocation of resources in
distributed information networks," ACM Trans. on Database Systems,
vol. 1, no. 1, pp. 66-78, 1976.
[8] T. Loukopoulos, D. Papadias, and I. Ahmad, "An overview of data
replication on the internet," in Proc. of IEEE Intl. Symp. on Parallel
Architectures, Algorithms and Networks, 2002, pp. 31-36.
[9] W. Vickrey, "Counterspeculations, auctions and competitive sealed-bid
tenders," J. of Finance, vol. 16, pp. 15-27, 1961.
[10] L. Qiu, V. Padmanabhan and G. Voelker, "On the placement of web
server replicas," in Proc. of the IEEE INFOCOM, 2001, pp. 1587-1596.
[11] W. Chu, "Optimal file allocation in a multiple computer system," IEEE
Trans. on Computers, vol. 18, no. 10, pp. 885-889, 1969.
[12] R. Casey, "Allocation of copies of a file in an information network," in
Proc. Spring Joint Computer Conf., IFIPS, 1972, pp. 617-625.
[13] K. Eswaran, "Placement of records in a file and file Allocation in a
computer network," in Proc. of Intl. Information Processing Conf.,
1974, pp. 304-307.
[14] L. Dowdy and D. Foster, "Comparative models of the file assignment
problem," ACM Computing Surveys, vol. 14, no. 2, pp. 287-313, 1982.
[15] K. Chandy and J. Hewes, "File allocation in distributed systems," in
Proc. of the International Symp. on Comput. Performance Modeling,
Measurement and Evaluation, 1976, pp. 10-13.
[16] S. Hakimi, "Optimum location of switching centers and the absolute
centers and medians of a graph," Operations Research, vol. 12, pp. 450-
459, 1964.
[17] 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, pp. 295-304.
[18] M. Karlsson and M. Mahalingam, "Do we need replica placement
algorithms in content delivery networks?" in Proc. of Web Caching and
Content Distribution Workshop, 2002, pp. 117-128.
[19] S. Cook, J. Pachl, and I. Pressman, "The optimal location of replicas in
a network using a READ-ONE-WRITE-ALL policy," Distributed
Computing, vol. 15, no. 1, pp. 57-66, 2002.
[20] S. Khan and I. Ahmad, "A powerful direct mechanism for optimal www
content replication," in Proc. of 19th IEEE International Parallel and
Distributed Processing Symposium, 2005, p. 86.
[21] S. Jamin, C. Jin, T. Kurc, D. Raz and Y. Shavitt, "Constrained mirror
placement on the internet," in Proc. of the IEEE INFOCOM, 2001, pp.
31-40.
[22] 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, pp.
1282-1290.
[23] K. Kalpakis, K. Dasgupta, and O. Wolfson, "Optimal placement of
replicas in trees with read, write, and storage Costs," IEEE Trans. on
Parallel and Distributed Systems, vol. 12, no. 6, pp. 628-637, 2001.
[24] I. Cidon, S. Kutten, and R. Soffer, "Optimal allocation of electronic
content," in Proc. of IEEE INFOCOM, 2001, pp. 1773-1780.
[25] P. Krishnan, D. Raz, and Y. Shavitt, "The Cache Location Problem,"
IEEE/ACM Trans. on Networking, 8(5), pp. 568-582, 2000.
[26] P. Radoslavov, R. Govindan, and D. Estrin, "Topology-informed
internet replica placement," Computer Communications, vol. 25, no. 4,
pp. 384-392, 2002.
[27] A. Venkataramanj, P. Weidmann, and M. Dahlin, "Bandwidth
constrained placement in a WAN," in Proc. ACM Symp. on Principles
of Distributed Computing, 2001, pp. 134-143.
[28] M. Korupolu and C. Plaxton, "Analysis of a local search heuristic for
facility location problems," J. of Algorithms, vol. 37, no. 1, pp. 146-
188, 2000.
[29] C. Krick, H. Racke, and M. Westermann, "Approximation algorithms
for data management in networks," in Proc. of the Symp. on Parallel
Algorithms and Architecture, 2001, pp. 237-246.
[30] B.-G. Chun, K. Chaudhuri, H. Wee, M. Barreno, C. Papadimitriou and
J. Kubiatowicz, "Selfish caching in distributed systems: A gametheoretic
analysis," in Proc. of 23rd ACM Symp. on Principles of
Distributed Computing, 2004, pp. 21-30.
[31] N. Laoutaris, O. Telelis, V. Zissimopoulos and I. Stavrakakis, "Local
utility aware content replication," in IFIP Networking Conference,
2005, pp. 455-468.
[32] B. Narebdran, S. Rangarajan and S. Yajnik, "Data distribution
algorithms for load balancing fault-tolerant web access," in Proc. of the
16th Symp. on Reliable Distributed Systems, 1997, pp. 97-106.
[33] M. Rabinovich, "Issues in web content replication," Data Engineering
Bulletin, vol. 21, no. 4, pp. 21-29, 1998.
[34] M. Arlitt and T. Jin, "Workload characterization of the 1998 World Cup
Web Site," tech. report, HP Lab, Palo Alto, HPL-1999-35(R.1), 1999.
[35] K. Calvert, M. Doar, E. Zegura, "Modeling Internet topology," IEEE
Communications, 35(6), pp. 160-163, 1997.
[36] P. Apers, "Data Allocation in Distributed Database Systems," ACM
Trans. Database Systems, 13(3), pp. 263-304, 1988.