Walter Scott, Jr. College of Engineering

Graduate Exam Abstract

Shibayan Chatterjee
M.S. Final
Sep 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