Repository logo
 

Multi-attribute query resolution in structured peer-to-peer networks

Simple item page
dc.contributor.authorChatterjee, Shibayan, author
dc.contributor.authorJayasumana, Anura, advisor
dc.contributor.authorPezeshki, Ali, committee member
dc.contributor.authorPallickara, Sangmi Lee, committee member
dc.date.accessioned2017-01-04T22:59:06Z
dc.date.available2017-01-04T22:59:06Z
dc.date.issued2016
dc.description.abstractCollaborative grid and cloud computing applications may be implemented by forming virtual clusters on demand. Formation of such clusters will require diverse resources with specific attributes to execute and support the specific application and its performance requirements. This thesis focuses on formation of such systems by looking up resources over a distributed peer-to-peer system. Discovery of appropriate resources from an enormous distributed pool of resources becomes tedious, but it should be resolved with minimum cost and latency. There can be a number of attributes characterizing each resource, and these attributes may have ranges of values depending upon the characteristics of the resources. Thus, when performing a look-up for appropriate resources with a peer-to-peer approach, the objective moves from a single-dimensional look-up problem to a multi-dimensional look-up problem. The look-up operation has to be optimized in terms of delay in resolution, hop-count, communication cost, and overhead cost. This thesis develops and evaluates an architecture aimed at resolving this n-dimensional peer-to-peer look-up problem. The optimality of the proposed solution is evaluated in terms of communication overhead, delay, and hop count for look up. The complexity of n-dimensional look-up problem is further reduced in terms of dimensionality by utilizing the correlation between different attribute characteristics. The proposed architecture uses a structured peer-to-peer network in the form of multiple rings, grouped together on the basis of individual attributes thus forming a Ring of Rings (ROR). Chord protocol is used to maintain the scalability and for having communication cost for lookup within logarithmic time complexity. Communication within the network is done using Bloom filters as a data structure, which represents the resources satisfying different attribute values. The novelty of the architecture and the communication methodology lies in the fact that architecture facilitates any number of attributes having any range of values. Furthermore, use of Bloom-filters for communication reduces the overhead normally required to carry around long lists of resources to perform the final intersection that resolves the query. Using Bloom-filters greatly reduces the communication overhead and the cost of communication. The ROR architecture coupled with Bloom-filter messages reduces the message sizes considerably, but it introduces a certain amount of false positives. The findings indicate that with the optimum number of hash-functions and the optimum sized Bloom-filter, a ROR peer-to-peer architecture to search for multi-attribute queries can be much more efficient than the conventional systems used for the resolution of same type of queries. Queries associated with many systems request attributes which are correlated to each other. The research also addresses the identification of such resources more efficiently based on correlation of the attributes. The ROR architecture can be tuned for resolving these kinds of queries. The new architectures proposed are localized caching and overlapped ring architecture. The network configuration responsible for resolving the query is the same structured peer-to-peer network, where caching and overlapped ring strategies fit in to resolve multiple correlated attributes. These architectures also use Bloom-filter as a data structure to resolve the queries with minimum communication cost and overhead. Performance of proposed architectures is evaluated using simulations, with the resource traces for simulation generated using the ResQue resource generation tool. The results obtained for a simulation environment consisting of 700 resources, each with 12 different types of attributes, and the number of nodes from 24 to 84 indicates a 30% reduction in communication overhead, 7% reduction in delay in response, and 10% reduction in average load per node. The optimum number of hash functions for the Bloom-filter is 6, and the m/n ratio is kept 10 where m is the size of Bloom-filter and n is the resource count. The optimum number of nodes responsible for each attribute is found to be 5. In case of correlated attributes, for the same set of resource count and number of nodes the caching and overlapped ring architecture (using Bloom-filters), provides 58.5% and 57.3% reductions in hop-count, 56.63% and 52.06% reductions in delay in response, message sizes gets reduced by 10% and the average load per node gets reduced by 9% and 34% respectively. The comparison is done over the ROR architecture using Bloom-filters. The number of hash functions for Bloom-filters is considered 4, m/n ratio to be 10 and with 4 nodes per attribute in case of co-related attribute resolution.
dc.format.mediumborn digital
dc.format.mediummasters theses
dc.identifierChatterjee_colostate_0053N_13882.pdf
dc.identifier.urihttp://hdl.handle.net/10217/178845
dc.languageEnglish
dc.language.isoeng
dc.publisherColorado State University. Libraries
dc.relation.ispartof2000-2019
dc.rightsCopyright and other restrictions may apply. User is responsible for compliance with all applicable laws. For information about copyright law, please see https://libguides.colostate.edu/copyright.
dc.subjectcaching
dc.subjectoverlapped rings
dc.subjectrange queries
dc.subjectmulti-attribute resources
dc.subjectbloom-filters
dc.subjectpeer-to-peer networks (P2P)
dc.titleMulti-attribute query resolution in structured peer-to-peer networks
dc.typeText
dcterms.rights.dplaThis Item is protected by copyright and/or related rights (https://rightsstatements.org/vocab/InC/1.0/). You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).
thesis.degree.disciplineElectrical and Computer Engineering
thesis.degree.grantorColorado State University
thesis.degree.levelMasters
thesis.degree.nameMaster of Science (M.S.)

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Chatterjee_colostate_0053N_13882.pdf
Size:
6.81 MB
Format:
Adobe Portable Document Format
Download

Collections

2000-2019
Theses and Dissertations