A key-order preserving structured overlay network is a class of structured overlay network that preserves, in its structure, the order of keys to support efficient range queries. This paper presents a novel key-order preserving structured overlay network “Suzaku”. Similar to the conventional Chord#, Suzaku uses a periodically updated finger table as a routing table, but extends its uni-directional finger table to bi-directional, which achieves ⌈log2 n⌉-1 maximum lookup hops in the converged state. Suzaku introduces active and passive bi-directional finger table update algorithms for node insertion and deletion. This method maintains good lookup performance (lookup hops increase nearly logarithmically against n) even in churn situations. As well as its good performance, the algorithms of Suzaku are simple and easy to implement. This paper describes the principles of Suzaku, followed by simulation evaluations, in which it showed better performance than the conventional networks, Chord# and Skip Graph.

In this paper, we propose a method to construct a scalable sensor data stream delivery system that guarantees the specified delivery quality of service (i.e., total reachability to destinations), even when delivery server resources (nodes) are in a heterogeneous churn situation. A number of P2P-based methods have been proposed for constructing a scalable and efficient sensor data stream system that accommodates different delivery cycles by distributing communication loads of the nodes. However, no existing method can guarantee delivery quality of service when the nodes on the system have a heterogeneous churn rate. As an extension of existing methods, which assign relay nodes based on the distributed hashing of the time-to-deliver, our method specifies the number of replication nodes, based on the churn rate of each node and on the relevant delivery paths. Through simulations, we confirmed that our proposed method can guarantee the required reachability, while avoiding any increase in unnecessary resource assignment costs.

The routing efficiency of structured overlay networks depends on the consistency of pointers between nodes, where a pointer maps a node identifier to the corresponding address. This consistency can, however, break temporarily when some overlay nodes fail, since it takes time to repair the broken pointers in a distributed manner. Conventional solutions utilize “backpointers” to quickly discover any failure among the pointing nodes, which allow them to fix the pointers in a short time. Overlay nodes are, however, required to maintain backpointers for every pointing node, which incurs significant memory and consistency check overhead. This paper proposes a novel light-weight protocol; an overlay node gives a “living will” containing its acquaintances (backpointers) only to its successor, thus other nodes are freed from the need to maintain it. Our carefully-designed protocol guarantees that all acquaintances are registered via the living will, even in the presence of churn, and the successor notifies the acquaintances for the deceased. Even if the successor passes away and the living will is lost, the successor to the successor can identify the acquaintances with a high success ratio. Simulations show that our protocol greatly reduces memory overhead as well as the detection time for node failure with the cost being a slight increase in messaging load.

A key issue in Peer-to-Peer (P2P) live streaming systems is that several participant peers tend to leave within a short time period. For example, such a phenomenon is common at the half time of football games and at the end of the performance of famous artists. Such selfish behavior of the participants causes several problems in P2P networks such as the disconnection of the overlay, the departure of backup peers and the occurrence of cyclic reference to backup peers. In this paper, we propose several techniques for tree-structured P2P live streaming systems to enhance their resilience to the simultaneous departure of some participants. As the baseline of the discussion, we will focus on mTreebone which is a typical churn-resilient P2P live streaming system based on the notion of peer stability. The performance of the proposed techniques is evaluated by simulation. The simulation result indicates that even under high churn rates, the proposed techniques significantly reduce the number of attempts needed to connect to backup peers and the recovery time after a fail.

Distributed systems desire to construct a random overlay graph for robustness, efficient information dissemination and load balancing. A random walk-based overlay construction is a promising alternative to generate an ideal random scale free overlay in distributed systems. However, a simple random walk-based overlay construction can be affected by node churn. Especially, the number of edges increases and the degree distribution is skewed. This inappropriate distortion can be exploited by malicious nodes. In this paper, we propose a modified random walk-based overlay construction supported by a logistic/trial based decision function to compensate the impact of node churn. Through event-driven simulations, we show that the decision function helps an overlay maintain the proper degree distribution, low diameter and low clustering coefficient with shorter random walks.