Fully Decentralized Information System

P2P file sharing

• Global scale application.

Example: Gnutella.

• 40.000 nodes, 3 Mio files.

• 3M nodes (Jan 2006).

Strengths

• Good response time, scalable.

• No infrastructure, no administration.

• No single point of failure.

Weaknesses

• High network traffic.

• No structured search.

• Free-riding.

Gnutella

Meeting Peers (Ping/Pong)

Protocol Message Types

Type	Description	Contained Information
Ping	Announce availability and probe for other servents.	None.
Pong	Response to a ping.	IP address and port# of responding servent; number and total kb of files shared.
Query	Search request	Minimum network bandwidth of responding servent; search criteria.
QueryHit	Returned by servents that have the requested file	IP address, port# and network bandwidth of responding servent; number of results and result set.
Push	File download requests for servents behind a firewall	Servent identifier; index of requested file; IP address and port to send file to.

Searching

(Query/QueryHit/GET)

Structureless

Queries are flooded to neighbors, have a TTL, and are forwarded only once.

A query may obtain several responses indicating which peers provide the requested file. Among those, it selects one and is directly contacted in order to download the file.

• Can we search using fewer packets?

Improvements in Message Flooding

Expanding Ring.

• Start the search with small TTL (e.g. TTL = 1).

• If no success iteratively increases TTL (e.g. TTL = TTL +2).

k-Random Walkers.

• Forward the query to one randomly chosen neighbor only, with large TTL.

• Start k random walkers.

• Random walker periodically checks with the requester whether to continue.

Hybrid Gnutella: “Ultrapeers”

Ultrapeers can be installed (KaZaA) or self-promoted (Gnutella v.2).

Real Gnutella Network

Popular open-source file-sharing network.

• ~450,000 users as of 2003.

• ~2,000,000 today.

Ultrapeer-based Topology.

• Queries flooded among ultrapeers.

• Leaf nodes are shielded from query traffic.

• Based on multiple crawlers.