The Experts below are selected from a list of 111 Experts worldwide ranked by ideXlab platform
Xuanhua Shi - One of the best experts on this subject based on the ideXlab platform.
-
Scalable DHT- and ontology-based information service for large-scale grids
Future Generation Computer Systems, 2010Co-Authors: Yongcai Tao, Hai Jin, Song Wu, Xuanhua ShiAbstract:Current grid information services are centralized or hierarchical and prove inefficient as the scale of the grid rapidly increases. The introduction of the P2P DHT technique into grids brings an encouraging path. However, current applications of the P2P DHT technique to grids do not consider the Virtual Organization (VO) management mode of grid resources. Frequent joining and leaving of resources requires strong self-organization capacity of the system to maintain the rigid structure. Moreover, arranging a moderate Identifier Space for a DHT ring is knotty. A large Identifier Space will make some nodes overloaded, while a small Identifier Space will bring forth the same problem as the millennium bug. In addition, current grid services are described in XML-based standards, which only support syntactic keyword and taxonomy-based queries without reasoning ability at the semantic level, leading to poor precision and integrality. To address these issues, the paper proposes a scalable DHT- and ontology-based Information Service (DIS) for a grid system, which organizes resources into a DHT ring based on the VO mode. To save the Identifier Space, only stable VOs can join DIS via a new DHT node, whereas volatile VOs join DIS via being the sub-domain of other VOs. Furthermore, ontology-based information integration is adopted in DIS and a novel ontology for grid resources is designed, which supports semantic-based information queries. By integrating DHT- and semantic-based query techniques, DIS speeds up the information query and improves the query precision and integrality. DIS is evaluated over the ChinaGrid environment and experimental results show that DIS provides rapid resource query, high throughput and strong scalability.
-
Conf. Computing Frontiers - Scalable dht-based information service for large-scale grids
Proceedings of the 2008 conference on Computing frontiers - CF '08, 2008Co-Authors: Hai Jin, Yongcai Tao, Xuanhua ShiAbstract:Current grid information service is centralized or hierarchical and proves inefficient as grid scale rapidly increases. The introduction of P2P techniques into grids breaks an encouraging path. However, frequent join and departure of resource nodes require strong self-organization capacity of system to maintain their rigid structure. Moreover, arranging Identifier Space for P2P nodes is knotty and has great impact on system performance. If the Identifier Space is too large, some nodes will be overloaded. On the contrary, small Identifier Space will bring the same problem as millennium bug. To address the issues, this paper proposes a scalable DHT-based (Distributed Hash Table) Information Service (DIS) for grid system, which organizes grid resources into a DHT ring based on VO (Virtual Organization). To save the Identifier Space while retaining the scalability and system performance, only stable VOs can join DIS via a new DHT node, whereas volatile VOs join DIS through being the sub-domain of other VO. Experimental results show that DIS provides rapid resource query, strong scalability and high throughput, meanwhile avoiding the key node failure as well as the bottleneck problem.
Ion Stoica - One of the best experts on this subject based on the ideXlab platform.
-
load balancing in dynamic structured peer to peer systems
Performance Evaluation, 2006Co-Authors: Sonesh Surana, Karthik Lakshminarayanan, Brighten Godfrey, Richard M Karp, Ion StoicaAbstract:Most P2P systems that provide a DHT abstraction distribute objects randomly among "peer nodes" in a way that results in some nodes having Θ(log N) times as many objects as the average node. Further imbalance may result due to nonuniform distribution of objects in the Identifier Space and a high degree of heterogeneity in object loads and node capacities. Additionally, a node's load may vary greatly over time since the system can experience continuous insertions and deletions of objects, skewed object arrival patterns, and continuous arrival and departure of nodes.In this paper, we propose an algorithm for load balancing in such heterogeneous, dynamic P2P systems. Our simulation results show that in the face of rapid arrivals and departures of objects of widely varying load, our algorithm improves load balance by more than an order of magnitude for system utilizations as high as 80% while incurring an overhead of only about 6%. We also show that our distributed algorithm performs only negligibly worse than a similar centralized algorithm, and that node heterogeneity helps, not hurts, the scalability of our algorithm. Although many of these results are dependent on the workload, we believe the efficiency and performance improvement demonstrated over the case of no load balancing shows that our technique holds promise for deployed systems.
-
Load balancing in dynamic structured P2P systems
Proceedings - IEEE INFOCOM, 2004Co-Authors: Brighten Godfrey, Karthik Lakshminarayanan, Sonesh Surana, R Karp, Ion StoicaAbstract:Most P2P systems that provide a DHT abstraction distribute objects randomly among "peer nodes" in a way that results in some nodes having θ(log N) times as many objects as the average node. Further imbalance may result due to non-uniform distribution of objects in the Identifier Space and a high degree of heterogeneity in object loads and node capacities. Additionally, a node's load may vary greatly over time since the system can be expected to experience continuous insertions and deletions of objects, skewed object arrival patterns, and continuous arrival and departure of nodes. We propose an algorithm for load balancing in such heterogeneous, dynamic P2P systems. Our simulation results show that in the face of rapid arrivals and departures of objects of widely varying load, our algorithm achieves load balancing for system utilizations as high as 90% while moving only about 8% of the load that arrives into the system. Similarly, in a dynamic system where nodes arrive and depart, our algorithm moves less than 60% of the load the underlying DHT moves due to node arrivals and departures. Finally, we show that our distributed algorithm performs only negligibly worse than a similar centralized algorithm, and that node heterogeneity helps, not hurts, the scalability of our algorithm.
Pedro Szekely - One of the best experts on this subject based on the ideXlab platform.
-
MAAN: A Multi-Attribute Addressable Network for Grid Information Services
Journal of Grid Computing, 2004Co-Authors: Min Cai, M Frank, J Chen, Pedro SzekelyAbstract:Recent structured Peer-to-Peer (P2P) systems such as Distributed Hash Tables (DHTs) offer scalable key-based lookup for distributed resources. However, they cannot be simply applied to grid information services because grid resources need to be registered and searched using multiple attributes. This paper proposes a Multi-Attribute Addressable Network (MAAN) that extends Chord to support multi-attribute and range queries. MAAN addresses range queries by mapping attribute values to the Chord Identifier Space via uniform locality preserving hashing. It uses an iterative or single attribute dominated query routing algorithm to resolve multi-attribute based queries. Each node in MAAN only has O (log N ) neighbors for N nodes. The number of routing hops to resolve a multi-attribute range query is O (log N + N × s _min ), where s _min is the minimum range selectivity on all attributes. When s _min =ɛ, it is logarithmic to the number of nodes, which is scalable to a large number of nodes and attributes. We also measured the performance of our MAAN implementation and the experimental results are consistent with our theoretical analysis.
-
maan a multi attribute addressable network for grid information services
Latin American Web Congress, 2003Co-Authors: M Frank, J Chen, Pedro SzekelyAbstract:Recent structured peer-to-peer (P2P) systems such as distributed hash tables (DHTs) offer scalable key-based lookup for distributed resources. However, they cannot be simply applied to grid information services because grid resources need to be registered and searched using multiple attributes. We propose a multiattribute addressable network (MAAN) which extends chord to support multiattribute and range queries. MAAN addresses range queries by mapping attribute values to the chord Identifier Space via uniform locality preserving hashing. It uses an iterative or single attribute dominated query routing algorithm to resolve multiattribute based queries. Each node in MAAN only has O(logN) neighbors for N nodes. The number of routing hops to resolve a multiattribute range query is O(logN+N/spl times/s/sub min/), where s/sub min/ is the minimum range selectivity on all attributes. When s/sub min/=/spl epsiv/, it is logarithmic to the number of nodes, which is scalable to a large number of nodes and attributes. We also measured the performance of our MAAN implementation and the experimental results are consistent with our theoretical analysis.
Dafang Zhang - One of the best experts on this subject based on the ideXlab platform.
-
DHT-based lightweight broadcast algorithms in large-scale computing infrastructures
Future Generation Computer Systems, 2010Co-Authors: Kun Huang, Dafang ZhangAbstract:Scalable and efficient broadcast is essential to large-scale computing infrastructures such as PlanetLab and Grids. Previous broadcast algorithms exploit the greedy routing mechanisms of a Distributed Hash Table (DHT) to achieve the scalability. However, they suffer from load unbalancing and high overhead for constructing and maintaining a distributed broadcast tree (DBT). This paper presents DHT-based lightweight broadcast algorithms to overcome these limitations. Our algorithms leverage the topology and routing mechanism of Chord to select appropriate children of each node in a top-down approach. According to the node Identifier distribution of Chord, we propose two broadcast algorithms over DHT. When nodes are uniformly distributed in the Identifier Space, a token-based broadcast algorithm is proposed, where each node selects the finger nodes as its children by a token value. When nodes are arbitrarily distributed in the Identifier Space, a partition-based broadcast algorithm is proposed, where each node partitions its Identifier Space into two subSpaces and selects the agent nodes in the subSpaces as its children. We show theoretically and experimentally that both token-based and partition-based algorithms can implicitly build a balanced DBT from the novel routing paths of DHT, where the branching factor is at most two and the tree height is O(logn) in a Chord of n nodes, without extra Space for storing children and additional overhead for explicitly maintaining the parent-child membership.
-
GPC - A Partition-Based Broadcast Algorithm over DHT for Large-Scale Computing Infrastructures
Advances in Grid and Pervasive Computing, 2009Co-Authors: Kun Huang, Dafang ZhangAbstract:Scalable and efficient broadcast is essential to the large-scale computing infrastructures such as PlanetLab and Grids. Existing DHT-based broadcast algorithms suffer from the limitations of scalability and load balancing, incurring high-overhead construction and maintenance of a distributed broadcast tree (DBT). This paper proposes a partition-based broadcast algorithm over DHT for the large-scale computing infrastructures, where each node hierarchically partitions its Identifier Space into two subSpaces and selects the agent nodes in the subSpaces as its children in a top-down approach. Our theoretical analysis and experimental results demonstrate that the partition-based broadcast algorithm can construct and maintain a balanced DBT with low overhead, where the branching factors of each node are at most two, and the tree height is O (log n ) in a Chord of n nodes, without any extra storage Space for each node and explicit maintenance overhead for the parent-child membership in the DBT.
Hung Keng Pung - One of the best experts on this subject based on the ideXlab platform.
-
An Ontology-Based P2P Network for Semantic Search
Networking and Telecommunications, 2010Co-Authors: Daqing Zhang, Hung Keng PungAbstract:This article presents an ontology-based peer-to-peer network that facilitates efficient search for data in widearea networks. Data with the same semantics are grouped together into one-dimensional semantic ring Space in the upper-tier network. This is achieved by applying an ontology-based semantic clustering technique and dedicating part of node Identifiers to correspond to their data semantics. In the lower-tier network, peers in each semantic cluster are organized as Chord Identifier Space. Thus, all the nodes in the same semantic cluster know which node is responsible for storing context data triples they are looking for, and context queries can be efficiently routed to those nodes. Through the simulation studies, the authors demonstrate the effectiveness of our proposed scheme.
-
ICPADS - A two-tier semantic overlay network for P2P search
2007 International Conference on Parallel and Distributed Systems, 2007Co-Authors: Daqing Zhang, Hung Keng PungAbstract:This paper proposes a two-tier semantic peer-to-peer network that facilitates efficient search for context information in wide-area networks. Context data with the same semantics are grouped together into a one-dimensional semantic ring Space in the upper-tier network. This is achieved by applying an ontology- based semantic clustering technique and dedicating part of node Identifiers to correspond to their data semantics. In the lower-tier network, peers in each semantic cluster are organized as Chord Identifier Space. Thus, all the nodes in the same semantic cluster know which node is responsible for storing context data triples they are looking for, and context queries can be efficiently routed to those nodes. Through the simulation studies, we demonstrate the effectiveness of our proposed scheme.
