Graduate Exam Abstract

Shibayan Chatterjee

M.S. Final

September 19, 2016, 10:00 am - 12:00 pm

ECE conference room C101 B

Multi-Attribute Query Resolution in Structured Peer-to-Peer Networks

Abstract: Collaborative grid and cloud computing applications may be implemented by forming virtual clusters on demand. Formation of such clusters will require diverse resources with a 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 P2P 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 P2P 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 P2P 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 P2P 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 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 29% and 34% respectively. The comparison is done over the ROR architecture using Bloom-Filters.

Adviser: Anura Jayasumana
Co-Adviser: N/A
Non-ECE Member: Sangmi Pallikara, Computer Science
Member 3: Ali Pezeshki, Electrical and Computer Engineering
Addional Members: N/A


Program of Study:
ECE 567 Systems Engr. Architecture
ECE 571 VLSI System Design
ECE 658 Internet Engineering
ECE 699 Thesis
CS 545 Machine Learning
CS 557 Advanced Networking
CS 581A1 Big Data