The core motive of this research is to construct a new hierarchical non-DHT based architecture for Peer-to-Peer (P2P) networks that facilitate common interests clustering. DHT based network maintenance is on the high end and it churning management is a complex task here. Providing efficient data querying performance and ensuring minimal churn management effort has interested us to pursue non-DHT route of P2P networking. And at each level of the proposed architecture hierarchy, existing networks are all structured and each such network has the diameter of 1 overlay hop. Such low diameters have immense importance in designing very efficient data lookup algorithms. We shall use a mathematical model based on the Chinese Remainder Theorem (CRT), generally used in cryptography, to define the neighborhood relations among peers to obtain the above-mentioned diameters. To the best of our knowledge, use of CRT in P2P network design is a completely new idea; it does not exist in the literature so far. It is worth mentioning its most important advantage from the viewpoint of speed of communication, that is its diameter, which is only 3 overlay hops. The protocol is not restricted to a single data source, and it incorporates peer heterogeneity as well.

This dissertation presents algorithms for data structures called distributed hash tables (DHT) or structured overlay networks, which are used to build scalable self-managing distributed systems. The provided algorithms guarantee lookup consistency in the presence of dynamism: they guarantee consistent lookup results in the presence of nodes joining and leaving. Similarly, the algorithms guarantee that routing never fails while nodes join and leave. Previous algorithms for lookup consistency either suffer from starvation, do not work in the presence of failures, or lack proof of correctness. Several group communication algorithms for structured overlay networks are presented. We provide an overlay broadcast algorithm, which unlike previous algorithms avoids redundant messages, reaching all nodes in O(log n) time, while using O(n) messages, where n is the number of nodes in the system. The broadcast algorithm is used to build overlay multicast. We introduce bulk operation, which enables a node to efficiently make multiple lookups or send a message to all nodes in a specified set of identifiers. The algorithm ensures that all specified nodes are reached in O(log n) time, sending maximum O(log n) messages per node, regardless of the input size of the bulk operation. Moreover, the algorithm avoids sending redundant messages. Previous approaches required multiple lookups, which consume more messages and can render the initiator a bottleneck. Our algorithms are used in DHT-based storage systems, where nodes can do thousands of lookups to fetch large files. We use the bulk operation algorithm to construct a pseudo-reliable broadcast algorithm. Bulk operations can also be used to implement efficient range queries. Finally, we describe a novel way to place replicas in a DHT, called symmetric replication, that enables parallel recursive lookups. Parallel lookups are known to reduce latencies. However, costly iterative lookups have previously been used to do parallel lookups. Moreover, joins or leaves only require exchanging O(1) messages, while other schemes require at least log(f) messages for a replication degree of f. The algorithms have been implemented in a middleware called the Distributed k-ary System (DKS), which is briefly described. / QC 20100824

The Internet has evolved into a medium centered around content: people watch videos on YouTube, share their pictures via Flickr, and use Facebook to keep in touch with their friends. Yet, the only globally deployed service to discover content - i.e., Domain Name System (DNS) - does not discover content at all; it merely translates domain names into locations. The lack of persistent naming, in particular, makes content discovery, instead of domain discovery, challenging. Content Distribution Networks (CDNs), which augment DNSs with location-awareness, also suffer from the same problem of lack of persistent content names. Recently, several infrastructure- level solutions to this problem have emerged, but their fundamental limitation is that they fail to preserve the autonomy of network participants. Specifically, the storage requirements for resolution within each participant may not be proportional to their capacity. Furthermore, these solutions cannot be incrementally deployed. To the best of our knowledge, content discovery services based on peer-to-peer (P2P) networks are the only ones that support persistent content names. These services also come with the built-in advantage of scalability and deployability. However, P2P networks have been deployed in the real-world only recently, and their real-world characteristics are not well understood. It is important to understand these real-world characteristics in order to improve the performance and propose new designs by identifying the weaknesses of existing designs. In this dissertation, we first propose a novel, lightweight technique for capturing P2P traffic. Using our captured data, we characterize several aspects of P2P networks and draw conclusions about their weaknesses. Next, we create a botnet to demonstrate the lethality of the weaknesses of P2P networks. Finally, we address the weaknesses of P2P systems to design a P2P-based content discovery service, which resolves the drawbacks of existing content discovery systems and can operate at Internet-scale. This dissertation includes both previously published/unpublished and co-authored material.

<p>Structured overlay networks form a major classof peer-to-peer systems, which are touted for their abilitiesto scale, tolerate failures, and self-manage. Any long livedInternet-scale distributed system is destined to facenetwork partitions. Although the problem of network partitionsand mergers is highly related to fault-tolerance andself-management in large-scale systems, it has hardly beenstudied in the context of structured peer-to-peer systems.These systems have mainly been studied under churn (frequentjoins/failures), which as a side effect solves the problemof network partitions, as it is similar to massive nodefailures. Yet, the crucial aspect of network mergers has beenignored. In fact, it has been claimed that ring-based structuredoverlay networks, which constitute the majority of thestructured overlays, are intrinsically ill-suited for mergingrings. In this thesis, we present a number of research papers representing our work on handling network partitions and mergers in structured overlay networks. The contribution of this thesis is threefold. First, we provide a solution for merging ring-based structured overlays. Our solution is tuneable, by a {\em fanout} parameter, to achieve a trade-off between message and time complexity. Second, we provide a network size estimation algorithm for ring-based structured overlays. We believe that an estimate of the current network size can be used for tuning overlay parameters that change according to the network size, for instance the fanout parameter in our merger solution.Third, we extend our work from fixing routing anomalies to achieving data consistency. We argue that decreasing lookup inconsistencies on the routing level aids in achieving data consistency in applications built on top of overlays. We study the frequency of occurence of lookup inconsistencies and discuss solutions to decrease the affect of lookup inconsistencies.</p>

Distributed applications built on top of Structured Overlay Networks (SONs) operate based on certain self-* behaviors of the underlying Peer-to-Peer network. Among those, self-organization and self-healing are the two most prominent and assumed properties. The operating environment of distributed systems continues to be more inhospitable with the advance and demand of new technologies; for example in case of mobile and ad hoc networks Churn (node turnover) can be extremely high due to node mobility, frequent disconnects/reconnects and configuration changes. Also, in such dynamic environments, the system may face high Churn (node turnover) and Network partition in a frequent manner. The situation becomes worse if the self-healing behavior of underlying SON is not complete and well defined. This implies the following non-trivial questions: Can the maintenance mechanism of a SON heal the damage to the structure due to harshness of the operating environment and reverse it back? What are the pre-conditions; in other words, what properties the healing mechanism should possess in order to achieve reversibility against stressful environments? Existing literature lacks such assessment and verification study of the self-healing property of a SON. In this thesis, we investigate both the behavior and design of a system that operate in inhospitable environments. This work is relevant to systems with both peaks of high stress (e.g. partitions, churn, network dynamicity etc.) and continuous high stress. We evaluate existing overlay maintenance strategies, namely Correction-on-Change, Correction-on-Use, Periodic Stabilization, and Ring Merge. We define the reversibility property of a system as its ability to repair itself to its original state. We propose a new strategy, called Knowledge Base, to improve conditions for reversibility against inhospitable environments. By means of simulations, we demonstrate reversibility for overlay networks with high levels of partition and churn. We make general conclusions about the ability of the maintenance strategies to achieve reversibility. Identification of Phase Transitions in a SON can provide useful information about the properties of each state of the system. Also, this enables to find the critical points in the operating space and parameters influencing them. The applications running on top of the SON can potentially utilize this knowledge to adapt its operation accordingly in different system states. In this thesis, a representative ring-based SON, namely Beernet is chosen and extended to achieve reversibility. The resulting overlay, Beernet++ exhibits reversible phase transitions under churn. We analyze the critical points observed during such transitions. We present the behavior of Beernet++ for high level of churn and network partitioning, along with their interaction. / <p>QC 20150929</p>

Structured overlay networks form a major classof peer-to-peer systems, which are touted for their abilitiesto scale, tolerate failures, and self-manage. Any long livedInternet-scale distributed system is destined to facenetwork partitions. Although the problem of network partitionsand mergers is highly related to fault-tolerance andself-management in large-scale systems, it has hardly beenstudied in the context of structured peer-to-peer systems.These systems have mainly been studied under churn (frequentjoins/failures), which as a side effect solves the problemof network partitions, as it is similar to massive nodefailures. Yet, the crucial aspect of network mergers has beenignored. In fact, it has been claimed that ring-based structuredoverlay networks, which constitute the majority of thestructured overlays, are intrinsically ill-suited for mergingrings. In this thesis, we present a number of research papers representing our work on handling network partitions and mergers in structured overlay networks. The contribution of this thesis is threefold. First, we provide a solution for merging ring-based structured overlays. Our solution is tuneable, by a {\em fanout} parameter, to achieve a trade-off between message and time complexity. Second, we provide a network size estimation algorithm for ring-based structured overlays. We believe that an estimate of the current network size can be used for tuning overlay parameters that change according to the network size, for instance the fanout parameter in our merger solution.Third, we extend our work from fixing routing anomalies to achieving data consistency. We argue that decreasing lookup inconsistencies on the routing level aids in achieving data consistency in applications built on top of overlays. We study the frequency of occurence of lookup inconsistencies and discuss solutions to decrease the affect of lookup inconsistencies.