A new and effective hierarchical overlay structure for Peer-to-Peer networks

The tremendous growth of public interest in Peer-to-Peer (P2P) networks in recent years has initiated a lot of research work on how to design efficient overlay structures for P2P systems. Scalable overlay networks such as Chord, CAN, Pastry, and Tapestry provide no control over where data is stored and the location of the peers and resources is determined by the hash values of their identifiers and keys respectively. As a result, these overlays cannot support range queries and other proximity-aware complex queries directly.In this paper, we present a hierarchical P2P overlay network called SkipCluster, which is capable of supporting both exact-match and multi-dimensional range queries efficiently without consumption of extra memory space. SkipCluster is derived from skip graphs and SkipNet, but it has a two-tier hierarchical architecture.In both tiers, peers are connected in sequence according to the order of their peer IDs, and related resources are stored near each other without hashing of their resource keys. We design a novel data structure called Triple Linked List (TLL) to store each super-peer’s pointers in the higher tier, which can be used to find the longest prefix and speed up query routing of inter-cluster. In the lower tier, each intra-cluster peer’s routing table contains pointers with exponentially incremental distance. Experimental results show that SkipCluster can speed up both exact-match and range queries in different network sizes.     

Ambient contracts: verifying and enforcing ambient object compositions à la carte

Current programming languages do not offer adequate abstractions to discover and compose heterogenous objects over unreliable networks. This forces programmers to discover objects one by one, compose them manually, and keep track of their individual connectivity state at all times. In this paper we propose Ambient Contracts, a novel programming abstraction to deal with the difficulties of composing objects connected over unreliable networks. Ambient Contracts provide declarative heterogenous group discovery and composition while dealing with the unreliability of the network. An ambient contract allows runtime verification and enforcement of the messages sent between the participants in the contract. The use of our abstraction significantly reduces the code base and allows programmers to focus on the core functionality of their application. Our claims are reinforced by comparing the implementation of an example scenario in our contracts with a Java implementation using M2MI.     

T-Man: Gossip-based fast overlay topology construction

Large-scale overlay networks have become crucial ingredients of fully-decentralized applications and peer-to-peer systems. Depending on the task at hand, overlay networks are organized into different topologies, such as rings, trees, semantic and geographic proximity networks. We argue that the central role overlay networks play in decentralized application development requires a more systematic study and effort towards understanding the possibilities and limits of overlay network construction in its generality. Our contribution in this paper is a gossip protocol called T-Man that can build a wide range of overlay networks from scratch, relying only on minimal assumptions. The protocol is fast, robust, and very simple. It is also highly configurable as the desired topology itself is a parameter in the form of a ranking method that orders nodes according to preference for a base node to select them as neighbors. The paper presents extensive empirical analysis of the protocol along with theoretical analysis of certain aspects of its behavior. We also describe a practical application of T-Man for building Chord distributed hash table overlays efficiently from scratch.     

Game-theoretic model of asymmetrical multipath selection in pervasive computing environment

In order to transfer the ever increasing multimedia data we need to make use of multiple paths to realize the bandwidth aggregating. In pervasive computing environment, the combination of ubiquitous overlay networks and the capacity of multihoming can provide the possibility of exploiting plentiful available paths. Thus, we introduce a Pervasive Multipath Architecture (PEMA), in which we use the game theory to investigate the selfish strategic collaboration of multiple heterogeneous overlays when they are allowed to use the massively-multipath transfer. Overlay networks are modeled as “players” in this multipath selection game, and we study the asymmetric case where all overlays have different Round Trip Times (RTT) and different degrees of waste. We demonstrate the existence and uniqueness of Nash equilibrium (NE). In addition, we find that overlays differing only in their RTTs still receive proportional throughput shares and utilities at the NE. However, if overlays differ only in their degrees of waste, a more wasteful overlay has a larger utility and a larger throughput (bandwidth) share than a less wasteful overlay. Since maintaining connected paths consumes resource, we further consider a more generalized cost function where an overlay’s total resource consumption includes both transferring data packets and maintaining path connections. In this general game, we find that the overlay is more conservative, which opens smaller number of paths and obtains smaller efficiency loss at the NE than in other simplified games. Our simulations confirm the effectiveness and friendliness of multipath transfer for a range of path numbers and in the presence of multi-overlay traffic.     

Fuzzynet: Ringless routing in a ring-like structured overlay

Many structured overlay networks rely on a ring invariant as a core network connectivity element. The responsibility ranges of the participating peers and navigability principles (greedy routing) heavily depend on the ring structure. For correctness guarantees, each node needs to eagerly maintain its immediate neighboring links - the ring invariant. However, the ring maintenance is an expensive task and it may not even be possible to maintain the ring invariant continuously under high churn, particularly as the network size grows. Furthermore, routing anomalies in the network, peers behind firewalls and Network Address Translators (NATs) create non-transitivity effects, which inevitably lead to the violation of the ring invariant. We argue that reliance on the ring structure is a serious impediment for real life deployment and scalability of structured overlays. In this paper we propose an overlay called Fuzzynet, which does not rely on the ring invariant, yet has all the functionalities of structured overlays. Fuzzynet takes the idea of lazy overlay maintenance further by dropping any explicit connectivity and data maintenance requirement, relying merely on the actions performed when new Fuzzynet peers join the network. We show that with sufficient amount of neighbors (O(log N), comparable to traditional structured over-lays), even under high churn, data can be retrieved in Fuzzynet w.h.p. We validate our novel design principles by simulations as well as PlanetLab experiments and compare them with ring based overlays.     

Dynamic overlay multicast for live multimedia streaming in urban VANETs

Infotainment service has been a foreseeing trend in VANETs (Vehicular Ad Hoc Networks), and multimedia streaming has a high potential in VANET infotainment service. This paper considers the scenario of live multimedia streaming multicast to vehicles of the same group using a dynamic application layer overlay. Due to the willingness for cooperation of non-group nodes, application layer overlay multicast is more feasible than other kinds of multicast such as network-coding-based multicast and network-layer multicast. To adapt to high mobility and full of obstacles in urban VANETs, we propose an effective dynamic overlay multicast scheme for multimedia streaming, called OMV (Overlay Multicast in VANETs). The proposed OMV enhances an overlay’s stability with two strategies: (1) QoS-satisfied dynamic overlay and (2) mesh-structure overlay. The QoS-satisfied strategy to adjust the overlay selects potential new parents based on their streams’ packet loss rates and end-to-end delays. The mesh-structure strategy allows a child to have multiple parents. We evaluate the proposed OMV in urban VANETs with obstacles using two real video clips to demonstrate the feasibility of the OMV for real videos. Evaluation results show that comparing the proposed OMV to Qadri et al.’s work, which is a static mesh overlay and is the best method available in VANETs, the packet loss rate is reduced by 27.1% and the end-to-end delay is decreased by 11.7%, with a small control overhead of 2.1%, on average. Comparing the proposed OMV for tree overlays to ALMA, which is for dynamic tree multicast overlays and is also the best method available in MANETs, the packet loss rate is reduced by 7.1% and the end-to-end delay is decreased by 13.1%. In addition, to address the problem of obstacle-prone urban VANETs, we also derive feasible stream rates and overlay sizes for city maps with different road section sizes. To the best of our knowledge, how to organize and dynamically adjust an application layer multicast overlay for live multimedia streaming have not been studied in existing VANET literatures. In summary, to deal with highly dynamic topologies in urban VANETs, we propose a QoS-satisfied strategy for group nodes to switch to new parents that can offer better QoS. The proposed OMV is feasible for live multimedia streaming applications, such as emergency live video transmission and live video tour guides for passengers in different vehicles that belong to the same multicast group.     

Dynamic Web Service discovery architecture based on a novel peer based overlay network

Service Oriented Computing and its most famous implementation technology Web Services (WS) are becoming an important enabler of networked business models. Discovery mechanisms are a critical factor to the overall utility of Web Services. So far, discovery mechanisms based on the UDDI standard rely on many centralized and area-specific directories, which poses information stress problems such as performance bottlenecks and fault tolerance. In this context, decentralized approaches based on Peer to Peer overlay networks have been proposed by many researchers as a solution. In this paper, we propose a new structured P2P overlay network infrastructure designed for Web Services Discovery. We present theoretical analysis backed up by experimental results, showing that the proposed solution outperforms popular decentralized infrastructures for web discovery, Chord (and some of its successors), BATON (and it’s successor) and Skip-Graphs.     

Declarative secure distributed information systems

We present a unified declarative platform for specifying, implementing, and analyzing secure networked information systems. Our work builds upon techniques from logic-based trust management systems and declarative networking. We make the following contributions. First, we propose the Secure Network Datalog (SeNDlog) language that unifies Binder, a logic-based language for access control in distributed systems, and Network Datalog, a distributed recursive query language for declarative networks. SeNDlog enables network routing, information systems, and their security policies to be specified and implemented within a common declarative framework. Second, we extend existing distributed recursive query processing techniques to execute SeNDlogprograms that incorporate secure communication via authentication and encryption among untrusted nodes. Third, we demonstrate the use of user-defined cryptographic functions for customizing the authentication and encryption mechanisms used for securing protocols. Finally, using a local cluster and the PlanetLab testbed, we perform a detailed performance study of a variety of secure networked systems implemented using our platform.     

Analyzing locality over a P2P computing architecture

A characteristic of Peer-to-Peer (P2P) computing networks is their huge number of different computational resources scattered across the Internet. Gathering peers into markets according to their multi-attribute computational resources makes it easier to manage these environments. This solution is known as market overlay. In this context, the closeness of the markets with similar resources, known as locality, is a key feature for ensuring good P2P resource management. Thus, the locality feature over a market overlay allows a lack of resources in a given market to be compensated quickly by any other market with similar resources, whenever these are close to each other. Consequently, locality becomes an essential challenge.This paper addresses the analysis of the locality of P2P market over-lays. According to this, a new procedure for measuring locality is applied together with an extensive analysis of some well-known structured P2P overlays. Based on this analysis, a new P2P computing architecture, named DisCoP, oriented towards optimizing locality is proposed. Our proposal gathers the peers into markets according to their computational resources. A Hilbert function is used to arrange multi-attribute markets in an ordered and mono-dimensional space and the markets are linked by means of a Bruijn graph. In order to maintain the DisCoP locality whenever the overlay is not completed, a solution based on the virtualization of markets is also proposed. Finally, the DisCoP locality is tested together with the proposed virtualization method for approximate searches over uncompleted overlays. The simulation results show that approximate searches exploit the DisCoP locality efficiently.     

Enabling Dynamic Querying over Distributed Hash Tables

Dynamic querying (DQ) is a search technique used in unstructured peer-to-peer (P2P) networks to minimize the number of nodes that is necessary to visit to reach the desired number of results. In this paper, we introduce the use of the DQ technique in structured P2P networks. In particular, we present a P2P search algorithm, named DQ-DHT (Dynamic Querying over a Distributed Hash Table), to perform DQ-like searches over DHT-based overlays. The aim of DQ-DHT is twofold: allowing arbitrary queries to be performed in structured P2P networks and providing dynamic adaptation of the search according to the popularity of the resources to be located. DQ-DHT has been particularly designed for use in those distributed environments, like computational grids, where it is necessary to support arbitrary queries for searching resources on the basis of complex criteria or semantic features. This paper describes the DQ-DHT algorithm using Chord as basic overlay and analyzes its performance in comparison with DQ in unstructured networks.