Can Unstructured P2P Protocols Survive
Dan Rubenstein, Sambit Sahu · 2005
Today's Internet periodically suffers from hot spots, a.k.a., flash crowds. A hot spot is typically triggered by an unan- ticipated news event that triggers an unanticipated surge of users that request data objects from a particular site, temporarily overwhelming the site's delivery capabilities. During this time, the large majority of users that attempt to get these objects face the frustrating experience of not being able to retrieve the content they want while still being able to communicate effectively with all other parts of the network. In this paper, we examine whether simple, undirected peer-to-peer search protocols can be used as a backup to deliver content whose popularity suddenly spikes. We model a simple, representative, undirected peer-to-peer search protocol in which clients cache only those objects they have ex- plicitly requested. Because the object that becomes hot initially has limited popularity, the number of cache points, were they to remain fixed, would be insufficient to handle the level of demand during the flash crowd. However, as searches complete, more copies of the object become available. We analyze this natural scaling phenomenon and show that during the flash crowd, copies are distributed to requesting clients at a fast enough rate such that these simple protocols can indeed be used to scalably retrieve content that suddenly becomes hot. is currently exhibiting hot spot symptoms. The object is dis- tributed to these users that seek it via end-to-end communica- tion between peers (i.e., the other users that also seek these ob- jects). The system's ability to deliver the content during the hot spot leverages off the fact that these pairwise end-to-end com- munications remain operational during the hot spot, and that a small number of users in the peer-to-peer network are still able to get through to the original server during the flash crowd. Prior to a hot spot event, users organize themselves into an overlay network: a directed graph that lies atop the underlying Internet infrastructure. The overlay enables its participants to communi- cate with one another by forwarding messages to and through other participants in the overlay. When a user (or its browser) finds a server unresponsive to its request, it can then search for the object by querying other participants within the overlay. Most studies of search in P2P systems assume that the popularity of each content item remains fixed with time. In these scenarios, search costs are reduced by replicating objects throughout the distributed (but finite) memory of the P2P system at a frequency that is correlated with the object's popu- larity (1). However, during a flash crowd, an item's popularity suddenly spikes such that most likely, an intelligent replication strategy would not have placed a sufficient number of copies of the item in the system. Search costs for the suddenly-pop- ular item would therefore be higher. Does this doom simple, undirected P2P solutions to failure? In this paper, we show that even simple P2P solutions natu- rally handle sudden spikes in demand. We develop a model of a simple yet representative, undirected search protocol similar