12:45 PM, Thursday, January 31st
Room 104, Gates Computer Science Building

Search and Replication in Unstructured Peer-to-Peer Networks

Pei Cao
Cisco Systems

About the talk:

File sharing in Peer-to-Peer(P2P) networks are popular applications on the Internet today. In this talk, we briefly survey architectures of existing P2P systems, then focus on decentralized and unstructured networks such as Gnutella. We study two aspects of the system: file search efficiency and replication strategies. We show that simple flooding-based search algorithm scales poorly, especially for power-law random graphs. A multiple-walker random-walk search algorithm can improve upon the simple flooding by two orders of magnitude. We also show that, in unstructured networks, an object's replication ratio should be proportional to the square root of its popularity in order to minimize overall network search traffic. With simulations, we show that the path replication strategy, such as the one used in FreeNet, leads to the close-to-optimal replication ratios.

This project is joint work with Christine Lv, Edith Cohen, Kai Li and Scott Shenker.

About the speaker:

Pei Cao is currently a system architect at Cisco systems. Prior to that she is an assistant professor at the CS Dept. at Univ. Wisconsin-Madison. Her research interests include operating systems, Web caching and content delivery, and storage systems.