Graph Properties

Graph theory provides a variety of methods to characterize the way vertices (peers) are connected, as static connectivity properties. While structured P2P systems (such as DHTs) have well-defined topologies based on maintaining certain mathematical properties, the properties of unstructured P2P systems arise from a complex interaction of peer churn, peer discovery, and neighbor selection. Therefore, we have conducted a measurement study of a deployed P2P system to study and characterize its graph properties.

Despite the fact that the overlay topology is such a fundamental property, there have been few studies of the topologies of deployed P2P systems. These studies are all at least three years old, characterizing the Gnutella topology when it was just 3% of its current size. Additionally, these studies do not capture significant new topological features that have been introduced over the last few year.

In [1], [2], we examine static and dynamic properties of two-tier overlays (e.g., Gnutella, eDonkey, FastTrack) using snapshots captured by Cruiser, using Gnutella as an example. Our key results include:

• The peer degree is not power-law contrary to the result reported in previous studies. In fact, we show how a power-law degree can be the result of measurement error due to slow crawling.
• While not power-law, Gnutella is still a small world network. It has short path lengths and more clustering than a comparably-sized random graph.
• Long-lived ultrapeers form their own fairly well connected small world graph, with increased clustering.
• The longer peers remain in the overlay, the greater the chance they will be connected to other long-lived peers. There is an onion-like biasing where peers are more likely to be connected to older peers.

In [3], we extend our work by examining the geographic distribution of peers and exploring long-term trends.

We have made some of topology snapshots available for the user of other researchers here.

[1]	Daniel Stutzbach and Reza Rejaie, "Characterizing the Two-Tier Gnutella Topology", ACM SIGMETRICS, Extended Abstract, June, 2005.

[2]	Daniel Stutzbach, Reza Rejaie, and Subhabrata Sen. "Characterizing Unstructured Overlay Topologies in Modern P2P File-Sharing Systems", Internet Measurement Conference, October, 2005. (24% acceptance)

[3]	Amir Rasti, Daniel Stutzbach, and Reza Rejaie, "On the Long-term Evolution of the Two-Tier Gnutella Overlay", Global Internet Symposium, April 2006.