Cited By
View all- Zarrin JAguiar RBarraca J(2017)HARDJournal of Network and Computer Applications10.1016/j.jnca.2017.04.01490:C(42-73)Online publication date: 15-Jul-2017
Decentralized multi-attribute range search for resource discovery and load balancing
Pages 890 - 913
Abstract
The recent trend toward heterogeneity among, and even within, computers requires new expressiveness in the way resource descriptions are created, and new sophistication in systems that attempt to match jobs with resources. In this paper, we propose a novel resource discovery and load balancing method to support multi-attribute, range-based job constraints in a peer-to-peer grid system. The common approach of using simple attribute indexes does not suffice, as range-based constraints may be satisfied by more than a single value. We show via simulation that our approach matches these new heterogeneous jobs to heterogeneous resources both effectively (good matches are found, load is balanced) and efficiently (the new functionality imposes little overhead). Our system relies on resource descriptions being aggregated and periodically disseminated. Decentralized algorithms are often sensitive to the "freshness" of this information. However, we show that our approach is not sensitive to stale data, allowing the information movement to happen rarely enough that it imposes only insignificant overhead.
References
[1]
Bharambe AR, Agrawal M, Seshan S (2004) Mercury: supporting scalable multi-attribute range queries. In: Proceedings of the ACM SIGCOMM Conference
[2]
Bloom BH (1970) Space/time trade-offs in hash coding with allowable errors. Commun ACM 13:422---426
[3]
Ganesan P, Yang B, Garcia-Molina H (2004) One torus rule them all: multi-dimensional queries in P2P systems. In: Proceedings of the 7th international workshop on web and databases
[4]
Jagadish H, Ooi BC, Vu QH, Zhang R, Zhou A (2006) Vbi-tree: a peer-to-peer framework for supporting multi-dimensional indexing schemes. In: Proceedings of the 22nd international conference on data engineering, 2006. ICDE '06, p 34.
[5]
Kim JS, Keleher P, Marsh M, Bhattacharjee B, Sussman A (2007) Using content-addressable networks for load balancing in desktop grids. In: IEEE international symposium on high performance distributed computing (HPDC)
[6]
Kim JS, Nam B, Keleher P, Marsh M, Bhattacharjee B, Sussman A (2006) Resource discovery techniques in distributed desktop grid environments. In: Proceedings of the 7th IEEE/ACM international conference on grid computing-GRID 2006
[7]
Kim JS, Nam B, Marsh M, Keleher P, Bhattacharjee B, Sussman A (2008) Integrating categorical resource types into a P2P desktop grid system. In: Proceedings of the 9th IEEE/ACM international conference on grid computing (GRID 2008)
[8]
Lawder J (2000) Calculation of mappings between one and n-dimensional values using the Hilbert space-filling curve. Tech. Rep. BBKCS-00-01, Birkbeck College
[9]
Lee J, Keleher P, Sussman A (2010) Decentralized resource management for multi-core desktop grids. In: Proceedings of the 24th IEEE international parallel & distributed processing symposium
[10]
Lee J, Keleher P, Sussman A (2011) Supporting computing element heterogeneity in p2p grids. In: 2011 IEEE international conference on cluster computing (CLUSTER), pp 150---158.
[11]
Li X, Kim YJ, Govindan R, Hong W (2003) Multi-dimensional range queries in sensor networks. In: Proceedings of the 1st international conference on embedded networked sensor systems, SenSys '03. ACM, New York, pp 63---75.
[12]
Maheswaran M, Ali S, Siegel HJ, Hensgen D, Freud RF (1999) Dynamic mapping of a class of independent tasks onto heterogeneous computing systems. J Parallel Distrib Comput 59(2)
[13]
Nam B, Sussman A (2006) DiST: fully decentralized indexing for querying distributed multidimensional datasets. In: Proceedings of IPDPS 2006
[14]
Oppenheimer D, Albrecht J, Patterson D, Vahdat A (2005) Design and implementation tradeoffs for wide-area resource discovery. In: Proceedings 14th IEEE international symposium on high performance distributed computing, HPDC-14, pp 113---124.
[15]
Ratnasamy S, Francis P, Handley M, Karp R, Shenker S (2001) A scalable content addressable network. In: Proceedings of the ACM SIGCOMM conference
[16]
Rowstran A, Druschel P (2001) Pastry: scalable, distributed object location and routing for large-scale peer-to-peer systems. In: Proceedings of the 18th IFIP/ACM international conference on distributed systems platforms (Middleware 2001)
[17]
Sahin OD, Gulbeden A, Emekci F, Agrawal D, Abbadi AE (2005) Prism: indexing multi-dimensional data in p2p networks using reference vectors. In. In MULTIMEDIA '05: Proceedings of the 13th annual ACM international conference on multimedia. ACM Press, New York, pp 946---955
[18]
Stoica I, Morris R, Karger D, Kaashoek MF, Balakrishnan H (2001) Chord: a scalable peer-to-peer lookup service for internet applications. In: Proceedings of the ACM SIGCOMM Conference
[19]
Tang Y, Xu J, Zhou S, Lee W (2009) m-light: Indexing multi-dimensional data over dhts. In: 29th IEEE international conference on distributed computing systems, 2009. ICDCS '09, pp 191---198.
[20]
Tanin E, Harwood A, Samet H (2007) Using a distributed quadtree index in peer-to-peer networks. VLDB J 16:165---178.
[21]
Vo HT, Chen C, Ooi BC (2010) Towards elastic transactional cloud storage with range query support. Proc VLDB Endow 3(1---2):506---514
[22]
Wang J, Wu S, Gao H, Li J, Ooi BC (2010) Indexing multi-dimensional data in a cloud system. In: Proceedings of the 2010 international conference on Management of data, SIGMOD '10. ACM, New York, pp 591---602.
[23]
Zhao BY, Huang L, Stribling J, Rhea SC, Joseph AD, Kubiatowicz JD (2004) Tapestry: a resilient global-scale overlay for service deployment. IEEE J Sel Areas Commun 22(1)
- Decentralized multi-attribute range search for resource discovery and load balancing
Recommendations
On the design of semi-structured multi-star hybrid-overlays for multi-attribute range queries
GPC'10: Proceedings of the 5th international conference on Advances in Grid and Pervasive ComputingIn the past few years, resource discovery is an important mechanism in P2P applications P2P networks could be categorized into structured and unstructured In general, structured P2P networks (DHTs) provide efficient keyword search, but is difficult to ...
A scalable multi-attribute range query approach on cluster-based hybrid overlays
MTPP'10: Proceedings of the Second Russia-Taiwan conference on Methods and tools of parallel programming multicomputersResource discovery in distributed computing systems is a critical issue to find and retrieve distributed resources rapidly. In general, most of previous proposed strategies focus on developing keyword searching approaches with preserving system ...
Performance Analysis of DHT Algorithms for Range-Query and Multi-Attribute Resource Discovery in Grids
ICPP '09: Proceedings of the 2009 International Conference on Parallel ProcessingResource discovery is critical to the usability and accessibility of grid computing systems. Distributed Hash Table (DHT) has been applied to grid systems as a distributed mechanism for providing scalable range-query and multiattribute resource ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Copyright © 2014 Springer Science+Business Media New York.
Publisher
Kluwer Academic Publishers
United States
Publication History
Published: 01 May 2014
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 14 Feb 2025
Other Metrics
Citations
Cited By
View all- Zarrin JAguiar RBarraca J(2017)HARDJournal of Network and Computer Applications10.1016/j.jnca.2017.04.01490:C(42-73)Online publication date: 15-Jul-2017