A novel robust on-line protocol for load-balancing in structured peer-to-peer systems
详细信息 查看全文
- 作者：George Tsatsanifos (1)
Vasilis Samoladas (2) - 关键词：Load ; balancing ; Structured peer ; to ; peer systems ; Distributed hash ; tables ; Multiple realities ; Virtual nodes ; Replication ; Range queries ; 68M10 ; 68M12 ; 68M14
- 刊名：Computing
- 出版年：2012
- 出版时间：10 - September 2012
- 年：2012
- 卷：94
- 期：8
- 页码：731-762
- 全文大小：910KB
- 参考文献：1. The dblp data-set. http://dblp.uni-trier.de/xml
2. The r-tree portal. http://www.rtreeportal.org
3. W3c rdfs rules of entailment. http://www.w3.org/TR/rdf-mt/#rules
4. Aberer K (2001) P-grid: a self-organizing access structure for p2p information systems. In: CoopIS, pp 179鈥?94
5. Aberer K (2002) Scalable data access in peer-to-peer systems using unbalanced search trees. In: WDAS, pp 107鈥?20
6. Aberer K, Datta A, Hauswirth M (2004) Efficient, self-contained handling of identity in peer-to-peer systems. IEEE TKDE, 16
7. Aberer K, Datta A, Hauswirth M (2005) Multifaceted simultaneous load balancing in DHT-based p2p systems: a new game with old balls and bins. In: Babaoglu 脰, Jelasity M, Montresor A, Fetzer C, Leonardi S, van Moorsel APA, van Steen M (eds) Self-star properties in complex information systems, pp 373鈥?91
8. Aberer K, Datta A, Hauswirth M (2005) P-grid: dynamics of self-organizing processes in structured peer-to-peer systems. In: Steinmetz R, Wehrle K (eds) Peer-to-peer systems and applications, pp 137鈥?53
9. Aspnes J, Kirsch J, Krishnamurthy A (2004) Load balancing and locality in range-queriable data structures. In: PODC, pp 115鈥?24
10. Avidor A, Azar Y, Sgall J (2001) Ancient and new algorithms for load balancing in the lp norm. Algorithmica 29(3): 422鈥?41 CrossRef
11. Azar Y, Broder AZ, Karlin AR, Upfal E (1994) Balanced allocations. SIAM J Comp 29(1): 180鈥?00 CrossRef
12. Bharambe AR, Agrawal M, Seshan S (2004) Mercury: supporting scalable multi-attribute range queries. In: SIGCOMM, pp 353鈥?66
13. Bienkowski M, Korzeniowski M, auf der Heide FM (2005) Dynamic load balancing in distributed hash tables. In: IPTPS, pp 217鈥?25
14. Blanas S, Samoladas V (2009) Contention-based performance evaluation of multidimensional range search in peer-to-peer networks. Future Gener Comp Syst 25(1): 100鈥?08 CrossRef
15. Byers JW, Considine J, Mitzenmacher M (2003) Simple load balancing for distributed hash tables. In: IPTPS, pp 80鈥?7
16. Cai M, Frank MR, Chen J, Szekely PA (2004) Maan: a multi-attribute addressable network for grid information services. J Grid Comp 2(1): 3鈥?4 CrossRef
17. Datta A, Hauswirth M, John R, Schmidt R, Aberer K (2005) Range queries in trie-structured overlays. In: P2P computing, pp 57鈥?6
18. Datta A, Nejdl W, Aberer K (2006) Optimal caching for first-order query load-balancing in decentralized index structures. In: DBISP2P, pp 331鈥?42
19. Datta A, Schmidt R, Aberer K (2007) Query-load balancing in structured overlays. In: CCGRID, pp 453鈥?60
20. Ganesan P, Bawa M, Garcia-molina H (2004) Online balancing of range-partitioned data with applications to peer-to-peer systems. In: VLDB, pp 444鈥?55
21. Ganesan P, Yang B, Garcia-Molina H (2004) One torus to rule them all: Multidimensional queries in p2p systems. In: WebDB, pp 19鈥?4
22. Godfrey B, Lakshminarayanan K, Surana S, Karp RM, Stoica I (2004) Load balancing in dynamic structured p2p systems. In: INFOCOM
23. Godfrey PB (2008) Balls and bins with structure: balanced allocations on hypergraphs. In: SODA 鈥?8, pp 511鈥?17
24. Gopalakrishnan V, Silaghi BD, Bhattacharjee B, Keleher PJ (2004) Adaptive replication in peer-to-peer systems. In: ICDCS, pp 360鈥?69
25. Graham RL (1969) Bounds on multiprocessing timing anomalies. SIAM J Appl Math 17(2): 416鈥?29 CrossRef
26. Jagadish HV, Ooi BC, Vu QH (2005) Baton: a balanced tree structure for peer-to-peer networks. In: VLDB, pp 661鈥?72
27. Jagadish HV, Ooi BC, Vu QH, Zhang R, Zhou A (2006) Vbi-tree: a peer-to-peer framework for supporting multi-dimensional indexing schemes. In: ICDE, p 34
28. Jain R, Chiu D, Hawe W (1984) A quantitative measure of fairness and discrimination for resource allocation in shared computer systems. In: DEC research report TR-301
29. Karger D, Lehman E, Leighton T, Panigrahy R, Levine M, Lewin D (1997) Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the world wide web. In: ACM symposium on theory of computers, pp 654鈥?63
30. Karger DR (2004) Simple efficient load balancing algorithms for peer-to-peer systems. In: ACM SPAA, pp 36鈥?3
31. Kenthapadi K, Panigrahy R (2006) Balanced allocation on graphs. In: SODA 鈥?6, pp 434鈥?43
32. Konstantinou I, Tsoumakos D, Koziris N (2011) Fast and cost-effective online load-balancing in distributed range-queriable systems. IEEE Trans Parallel Distrib Syst 22(8): 1350鈥?364 CrossRef
33. Maymounkov P, Mazi猫res D (2002) Kademlia: a peer-to-peer information system based on the xor metric. In: IPTPS, pp 53鈥?5
34. Mitzenmacher M (2001) The power of two choices in randomized load balancing. IEEE Trans Parallel Distrib Syst 12(10): 1094鈥?104 CrossRef
35. Mondal A, Goda K, Kitsuregawa M (2003) Effective load-balancing via migration and replication in spatial grids. In: DEXA, pp 202鈥?11
36. Pitoura T, Ntarmos N, Triantafillou P (2006) Replication, load balancing and efficient range query processing in dhts. In: EDBT, pp 131鈥?48
37. Raab M, Steger A (1998) Balls into bin鈥攁 simple and tight analysis. In: RANDOM, pp 159鈥?70
38. Ramabhadran S, Ratnasamy S, Hellerstein JM, Shenker S (2004) Brief announcement: prefix hash tree. In: PODC, p 368
39. Rao A, Lakshminarayanan K, Surana S, Karp RM, Stoica I (2003) Load balancing in structured p2p systems. In: IPTPS, pp 68鈥?9
40. Ratnasamy S, Francis P, Handley M, Karp R, Schenker S (2001) A scalable content-addressable network. In: SIGCOMM 鈥?1, pp 161鈥?72
41. Rowstron AIT, Druschel P (2001) Pastry: scalable, decentralized object location, and routing for large-scale peer-to-peer systems. In: Middleware, pp 329鈥?50
42. Stoica I, Morris R, Liben-Nowell D, Karger D, Kaashoek F, Dabek F, Balakrishnan H (2003) Chord a scalable p2p lookup protocol for internet applications. IEEE/ACM Trans Netw 11(1): 17鈥?2 CrossRef
43. Tsatsanifos G, Sacharidis D, Sellis TK (2011) Midas: multi-attribute indexing for distributed architecture systems. In: SSTD, pp 168鈥?85
44. Tsatsanifos G, Sacharidis D, Sellis TK (2011) On enhancing scalability for distributed rdf/s stores. In: EDBT, pp 141鈥?52
45. Wang X, Loguinov D (2007) Load-balancing performance of consistent hashing: asymptotic analysis of random node join. IEEE/ACM Trans Netw 15(4): 892鈥?05 CrossRef
46. Wu K-L, Yu PS (2003) Replication for load balancing and hot-spot relief on proxy web caches with hash routing. Distrib Parallel Databases 13(2): 203鈥?20 CrossRef
47. Zhao B, Kubiatowicz J, Joseph AD (2004) Tapestry: a resilient global-scale overlay for service deployment. IEEE J Sel Areas Comm 22(1): 41鈥?3 CrossRef - 作者单位：George Tsatsanifos (1)
Vasilis Samoladas (2)
1. Knowledge and Database Systems Laboratory, School of Electrical and Computer Engineering, National Technical University of Athens, Athens, Greece
2. Software Technology and Network Applications Laboratory, Electronic and Computer Engineering Department, Technical University of Crete, Chania, Greece - ISSN：1436-5057
文摘
In this paper, we revisit the problem of load-balancing structured peer-to-peer systems with on-line protocols. Load-balancing is of major significance for large-scale decentralized networks in terms of enhanced scalability and performance. The main incentives behind balancing schemes are under-utilization of bandwidth and computer resources. Therefore, our methods focus mainly on task-skew. Specifically, we address the problem with on-line protocols on the basis of migration and enhanced availability. In particular, the cornerstones of our methods are the notions of virtual nodes, replication and Multiple realities, combined altogether with allocation techniques based on balls-in-bins games. The rationale of our dynamic protocol to depend exclusively on peer load distribution preserves intact the structural properties and search efficiency of the overlay used as an indexing infrastructure, while preserving the semantic information of the data (e.g., range partitioned network). We also propose an effective load-aware mechanism to facilitate robust operations that counteract against contingent churn failures. Finally, our work is complemented with extensive experiments using both real and synthetic data sets.