Distributed System Laboratory (DSL)

Challenges for content-based publish/subscribe systems include efficient subscription management and event matching, load balancing, and efficient and scalable event delivery. We investigate novel subscription intallation and management algorithms based on distributed hash tables (DHTs). We explores different technqiues to address the load balancing issues caused by skewed distribution of subscriptions and events in real applications. We proposes an efficient, virtually maintenance-free event delivery algorithm that exploits DHT overlay links. By exploiting DHT links in the design, our solutions have numerous advantages: (1) The fault-tolerance and self-organizing nature of DHT links makes Ferry resilient to node failures. (2) Ferry does not construct or maintain multicast trees for event delivery, and it is virtually maintenance-free. (3) Grouping subscriptions along DHT links in subscription management facilitates message aggregation during event delivery, thus minimizing the number of messages across the system. (4) The proximity neighbor selection (PNS) property of DHT links naturally enables proximity-aware event delivery along the DHT links, yielding good delivery performance. (5) The DHT routing table maintenance messages (sent periodically by the underlying DHT) could be piggybacked onto the event delivery messages to reduce the DHT maintenance cost that is nontrivial in terms of bandwidth.

Relevant Publications:

Resilient P2P Anonymous Routing

One hurdle to using peer-to-peer networks as anonymizing networks is churn. Node churn makes anonymous paths fragile and short-lived: failures of a relay node disrupt the path, resulting in message loss and communication failures. To make anonymous routing resilient to node failures, we proposed two solutions. One is to use a group of peer nodes to act as a mix, masking single mix failures. The other is to use redundancy based on erasure coding to achieve resilient anonymous routing. We also explore the impact of node session time distributions on routing resilience and propose a biased mix selection policy to improve path durability.

Relevant Publications:

Enhancing Search Performance in Peer-To-Peer Networks

In the past years, P2P computing has attracted tremendous attention from both user and research communities. A large body of research work has been focusing on P2P search. There are two important factors driving research interests into P2P search. First, the trend of information proliferation eagerly calls for a scalable information infrastructure capable of indexing and searching rich content such as HTML, music and image files. A recent study has shown that 93% of information produced worldwide is in digital form. The volume of data added each year is over one terabytes and is expected to grow exponentially. Such huge amount of information poses many challenges for existing search systems. Second, compared to centralized search systems, P2P search systems are particularly attractive and promising due to their scalability, availability, low cost, easy of deployment, and data freshness. We combine techniques from information retrieval (IR) and P2P computing to tackle the issue of how to improve P2P search performance in terms of search efficiency and quality of search results. We have designed and experimentally evaluated two P2P search frameworks on distributed hash tables (DHTs) and unstructured P2P networks such as Gnutella. The results have shown that our proposed solutions can make search very efficient and improve quality of search results.

Relevant Publications:

Load Balancing in Distributed Hash Tables

Many solutions have been proposed to tackle the load balancing issue in DHT-based P2P systems. However, all these solutions either ignore the heterogeneity nature of the system, or reassign loads among nodes without considering proximity relationships, or both. In this paper, we present an efficient, proximity-aware load balancing scheme by using the concept of virtual servers. To the best of our knowledge, this is the first work to use proximity information in load balancing. In particular, our main contributions are: 1) Relying on a self-organized, fully distributed k-ary tree structure constructed on top of a DHT, load balance is achieved by aligning those two skews in load distribution and node capacity inherent in P2P systems --- that is, have higher capacity nodes carry more loads; 2) proximity information is used to guide virtual server reassignments such that virtual servers are reassigned and transferred between physically close heavily loaded nodes and lightly loaded nodes, thereby minimizing the load movement cost and allowing load balancing to perform efficiently; and 3) our simulations show that our proximity-aware load balancing scheme reduces the load movement cost by 11-65 percent for all the combinations of two representative network topologies, two node capacity profiles, and two load distributions of virtual servers. Moreover, we achieve virtual server reassignments in O(logN) time.