Peer-to-Peer Networking (P2P)

Niels Olof Bouvin

Introduction to the Peer-to-Peer Networking Course

Overview

Course Overview
What is P2P?
Client/Server vs. P2P
P2P Characteristics
Typical P2P Applications
Example: Gnutella (and what's wrong with it)
Teasers for the rest of the course
Exercise 1

Course Overview

news://daimi.p2p: Announcements, questions, discussions, ...
http://wiki.daimi.au.dk/p2p-2006: Course plan, literature, ... (much more will be added over the course)
Course material: Papers, technical reports, and Web pages; A compendium is in production
Groups: exercises should ideally be done by groups (2-4 people)
Exam: Oral, 12 minutes, known questions, 13-scale

Purpose of course

To familiarize you with the gamut of P2P systems
To introduce a number of design criteria for P2P networks
To learn you to assess the strengths and weaknesses of a given system, based on these criteria
To establish practical knowledge of P2P networking by constructing a basic P2P system from scratch

Course Plan

Lectures

Introduction to P2P (30/8)
Unstructured P2P systems (6/9)
Structured P2P systems (13/9)
P2P applications (20/9)
Security & reputation (27/9)
P2P in a mobile context & Mobile Ad Hoc Networks (4/10)
Grid computing (11/10)

Practical aspects

Over the course (mandatory) assignments will let you create your own basic P2P system from scratch:

discovery of peers
establishing overlay network
searching
file transfers

Administratrivia – the creation of groups

Divide yourselves into groups – preferably 2-4 persons
Send me <n.o.bouvin@daimi.au.dk> a list of your group members, including Name, User name, and Student-ID, when you turn in your first assignment

Overview

Course overview
What is P2P?
Client/Server vs. P2P
P2P Characteristics
Typical P2P Applications
Example: Gnutella (and what's wrong with it)
Teasers for the rest of the course
Exercise 1

What are P2P Networking Systems?

There are a fair number of different opinions:

“A server-less networking technology that allows several network devices to share resources and communicate directly with each another”
“Deployable in an ad-hoc fashion, without requiring centralized management or control”
“Peer-to-peer is a class of applications that take advantage of resources—storage, cycles, content, human presence—available at the edges of the Internet”
“Peer-to-peer systems are distributed systems consisting of interconnected nodes able to self organize into network topologies with the purpose of sharing resources such as content, CPU cycles, storage and bandwidth, capable of adapting to failures and accommodating transient populations of nodes while maintaining acceptable connectivity and performance, without requiring the intermediation or support of a global centralized server or authority”

A Brief History of P2P Computing

1969-1995: The original Peer-to-Peer Internet

No firewalls, computers connected directly to the 'net, most services widely available
Usenet: based on Unix-to-Unix-CoPy (UUCP) originally, decentralized model of control
DNS: hosts are clients and servers, cache replies

1995-2001: The Internet explosion (and implosion)

Movement away from peer-to-peer to client-server models
Web, firewalls, ADSL, asymmetric connections, NAT, ...

2001-...: New wave of peer-to-peer(?)

separating authoring from publishing
(Web) service oriented Internet

Overview

Course overview
What is P2P?
Client/Server vs. P2P
Typical P2P Applications
Example: Gnutella (and what's wrong with it)
Teasers for the rest of the course
Exercise 1

Client/Server – Advantages

Centralized
Increased security
Control
Easy to control/maintain
Simple
Static topology

State kept one place
Simple architecture
Scalable (only few resources on the client)
well known and well supported
(RPC, RMI, J2EE, Corba, .NET)
loose coupling between client/client and server/client

Client/Server – Disadvantages

Single point of failure
Scalability
Requires large bandwidth for the server
State kept one place
Central control
Does not take advantage of the resources of the client
Does not support collaboration between clients

Peer to Peer – Advantages

Robust
Scalability
More clients = more resources
Dynamic (self configuring)
Replication
Decentralized (autonomy)
Peers can collaborate directly

Peer to Peer – Disadvantages

Architectural complexity
Resources are distributed and not always available
More demanding of peers
New technology: abstractions, techniques, etc., are not mature or fully understood

Overview

Course overview
What is P2P?
Client/Server vs. P2P
P2P Characteristics
Typical P2P Applications
Example: Gnutella (and what's wrong with it)
Teasers for the rest of the course
Exercise 1

Terms in P2P

Overlay network: The arrangement of peers on top of an existing “real” network. The organization of the overlay network is essential for a good performing P2P system
Servent: Server and client
Churn: The (often high) rate of peers entering and leaving a P2P network
Power-law distribution: Distribution, where few peers are very well-connected, and the rest less so

Peer to Peer – Challenges

Peer discovery
Resource discovery (searching/routing)
Performance
Consistency
Reliability
Fairness
Security

Classes of P2P Architectures

Purely decentralized architectures: All peers have the same basic capabilities and offer similar services
Partially centralized architectures: Some, usually more powerful, peers will accept more demanding roles on an ad hoc basis
Hybrid decentralized architectures: Some central servers facilitate coordination

Degrees of P2P Structure

Unstructured networks: Peers connect in a more or less haphazardly way – resulting in a network graph either power-law or random. Routing/searching is ad-hoc or heuristic
Semi-structured networks: While the network is still relatively random, resources are placed so that greedy routing works
Structured networks: Peers and resources are placed according to a rigidly defined schema, which is maintained over the lifetime of the network

P2P Characteristics (1)

Scalability

The ability of a system to support an increasing use

Pro: Network, storage, computational power of peers may be leveraged

Con: Routing, location, synchronizing may not scale; “fat” clients needed

Performance

The time it takes for a system to react to a stimulus

Pro: Data and computation may be close to peers, high degree of distribution

Con: Replicated, distributed state and computation; complex architectures

P2P Characteristics (2)

Availability

The part of the deployment period during which a system can deliver the services it implements

Pro: No single point of failure/robustness; system may be self-configuring, replicated, autonomous

Con: Ensuring consistent availability; having knowledge of network state

Fairness

Distributing work equally across the peers according to their needs and abilities

Pro: Necessary in order to maintain the good performance of P2P

Con: Difficult to ensure

P2P Characteristics (3)

Integrity and authenticity

The ability of a system to maintain correct state

Pro: Replication, no Single Point of Failure

Con: Cryptographic security difficult to establish without central authority

Security

The degree to which a system can withstand attacks

Pro: Robustness against Denial of Service attacks; anonymity

Con: Complex, decentralized security architecture

P2P Characteristics (4)

Anonymity, deniability, censorship resistance

Being able to retrieve or publish information without risk of discovery

Pro: Adds security, difficult to suppress information

Con: Not easy to ensure, what if running the system becomes a crime? Should all information be available?

Overview

Course overview
What is P2P?
Client/Server vs. P2P
P2P Characteristics
Typical P2P Applications
Example: Gnutella (and what's wrong with it)
Teasers for the rest of the course
Exercise 1

Typical P2P Applications

Content sharing and distribution
Communication
Collaboration
Distributed computation

P2P Content Sharing

Rationale

Users want to share information. The bandwidth/storage of users' computers are often partly unused

Examples

Napster

MP3 file sharing and searching service
Started in 1999, bankrupt June 2002, later restarted with revised business model
Hybrid P2P solution: Files on peers, metadata on server

Gnutella

The original “proper” P2P application for file sharing

Napster...

P2P Content Distribution

Rationale

A secure way of distributing content – focus on creating a “fabric” for distribution

Examples

Freenet

Goal: Anonymous information distribution, censor resistance
Completely decentralized P2P solution
Routing based on key “closeness” to target; routing replicates data

PAST

Goal: A large scale storage system based on a structured P2P network
High degree of availability and security

P2P Communication

Rationale

Communication is essential in collaboration and communication need only be between peers

Examples

ICQ (and many others)

Pioneered instant messages in 1996
ICQ server maps from ICQ-specific addresses to IP addresses; communication is peer-to-peer

Skype

Voice over IP based on P2P routing
Instant messaging

P2P Collaboration

Rationale

Human collaboration is intrinsically peer-to-peer, reflect this in software architectures

Examples

Groove

Commercial peer platform for hosting peer-to-peer applications and business solutions
Very elaborate security model
Based on publish/subscribe in which events can be cached

Distributed Knight

Peer-to-peer collaboration on Unified Modeling Language (UML) diagrams
Tight integration with context-aware instant messaging system

P2P for Distributed Computation

Rationale

Powerful desktop machines most often underutilized

Typical model:

central server divides “embarrassingly parallelisable” problem into manageable chunks and distributes these to clients which perform computations and return results
in principle similar to clusters, such as Beowulf

True P2P?

sort of... most projects are strictly hierarchical in architecture
certainly fits “deployable in an ad-hoc fashion, without requiring centralised management or control”

P2P for Distributed Computation (2)

Advantages

scales well for the right kind of problem
supercomputing for a low, low price
as peers need not communicate with each other, peers only need to be online when receiving work or sending results - thus even modem users can participate

Disadvantages

far from all computational problems can be parallelised to the necessary degree
project must generate sufficient “buzz” in order to get people to donate clock cycles

SETI@Home – looking for little green men

Largest (distributed) computation project ever

Problem: To identify radio signals from alien civilisations

this requires extensive filtering of radio signals, which is very computational expensive due to the large amount of data

Solution

Get people to donate their spare clock cycles to the project by running screen savers and background processes

Some statistics: (from 2004)

current #users: 4.670.336
current performance: 104.73 TeraFLOPS (NEC Earth-Simulator peak performance: 40.96 TeraFLOPS)

SETI@Home – experiences

A huge success!

the very success of the system has led to problems coping with the large number of clients
still no alien civilisations...

Problems

the prestige of having a high ranking makes it attractive to cheat the system by faking results. Others deliberately corrupt results to mislead the system.
SETI@Home uses cryptographic methods (and closed source) to combat this behaviour. To ensure data integrity, all work units are processed repeatedly by different clients

Some other distributed computation projects

distributed.net: has led a number of projects to break various encryption methods by brute force and solving mathematical problems
Folding@Home: simulates protein folding (a hard problem) using distributed computation
BOINC – Berkeley Open Infrastructure for Network Computing: next generation system for SETI@Home and other distributed computation problems
The Grid: Middleware infrastructure, tools, and applications concerned with integrating geographically distributed computational resources

Overview

Course overview
What is P2P?
Client/Server vs. P2P
P2P Characteristics
Typical P2P Applications
Example: Gnutella (and what's wrong with it)
Teasers for the rest of the course
Exercise 1

Gnutella

The first major truly distributed P2P file sharing system.
Napster demonstrated the problem of a single point of failure
Gnutella is fully distributed and cannot be easily be taken out by an attack (legal or otherwise)
Invented by Justin Frankel & Tom Pepper of Nullsoft and Winamp fame
Very quickly pulled by AOL/Time Warner (the owners of Nullsoft)
At that point the source was “in the wild”, and a number of Gnutella variants have since developed
Quite primitive system, but hugely successful nonetheless

Gnutella protocol – 5 commands are all you need

Ping: used for discovery
Pong: the response to a Ping
Query: used for searching
QueryHit: the response to a successful query
Push: used to get firewalled servents to reach outside the firewall

How does it work?

A Gnutella peer starts out with a number of peers from “somewhere”
It can ping these peers to receive information about them, and thus build a list of potential peers to contact in the future
Pings and queries are sent to all known peers who in turn call all their peers and so on (flooding)
Queries has a unique ID (128 bit) and a TTL (Time To Live). This ensures that peers do not retransmit the same query twice and that queries eventually die out
Peers remembers received and transmitted queries and whence they came
If a query match is found, the response (containing the query and the host address) is returned following the query route back to the originator
The originator receives (presumably) a number of hits and can then contact a host directly for downloading (usually through http)

How does it work?

A Gnutella Network Graph

Ranking of Gnutella peers

Peers report

amount of shared data
available bandwidth

Self-reporting is problematic

claim your bandwidth is low, and you will be left alone

Gnutella is inefficient

Flooding ensures that all peers within TTL horizon are contacted
However, flooding generates a tremendous amount of network traffic
Gnutella is so inefficient, that swamping the network becomes quite likely, even without any data traffic

Calculating Gnutella

Reachable Users
	T=1	T=2	T=3	T=4	T=5	T=6	T=7	T=8
N=2	2	4	6	8	10	12	14	16
N=3	3	9	21	45	93	189	381	765
N=4	4	16	52	160	484	1,456	4,372	13,120
N=5	5	25	105	425	1,705	6,825	27,305	109,225
N=6	6	36	186	936	4,686	23,436	117,186	585,936
N=7	7	49	301	1,813	10,885	65,317	391,909	2,351,461
N=8	8	64	456	3,200	22,408	156,864	1,098,056	7,686,400

Raising N (number of connections open) and T (number of hops) extend the number of reachable users geometrically.

Assuming balanced & equally distributed network graph

From Ritter 2001

Calculating Gnutella

Bandwidth Generated in Bytes (S=83)
	T=1	T=2	T=3	T=4	T=5	T=6	T=7	T=8
N=2	166	332	498	664	830	996	1,162	1,328
N=3	249	747	1,743	3,735	7,719	15,687	31,623	63,495
N=4	332	1,328	4,316	13,280	40,172	120,848	362,876	1,088,960
N=5	415	2,075	8,715	35,275	141,515	566,475	2,266,315	9,065,675
N=6	498	2,988	15,438	77,688	388,938	1,945,188	9,726,438	48,632,688
N=7	581	4,067	24,983	150,479	903,455	5,421,311	32,528,447	195,171,263
N=8	664	5,312	37,848	265,600	1,859,864	13,019,712	91,138,648	637,971,200

Assuming balanced & equally distributed network graph

From Ritter 2001

Calculating Gnutella

Bandwidth Incurred in Bytes (S=83)
	T=1	T=2	T=3	T=4	T=5	T=6	T=7	T=8
N=2	332	664	996	1,328	1,660	1,992	2,324	2,656
N=3	498	1,494	3,486	7,470	15,438	31,374	63,246	126,990
N=4	664	2,656	8,632	26,560	80,344	241,696	725,752	2,177,920
N=5	830	4,150	17,430	70,550	283,030	1,132,950	4,532,630	18,131,350
N=6	996	5,976	30,876	155,376	777,876	3,890,376	19,452,876	97,265,376
N=7	1,162	8,134	49,966	300,958	1,806,910	10,842,622	65,056,894	390,342,526
N=8	1,328	10,624	75,696	531,200	3,719,728	26,039,424	182,277,296	1,275,942,400

Searching for 'grateful dead live' generates a lot of traffic, when N and T grows. These calculations only consider search – not the cost of actual file transfers.

Assuming balanced & equally distributed network graph

From Ritter 2001

Experiences

Flooding hardly the most efficient use of network resources
Downloads the whole file from a single peers
- So if that peer goes missing in the middle of your download... so does your data
Advantage of Gnutella: So abysmal performance, it spurred the development of a lot of improvements – more about this next time!

Overview

Course overview
What is P2P?
Client/Server vs. P2P
P2P Characteristics
Typical P2P Applications
Example: Gnutella (and what's wrong with it)
Teasers for the rest of the course
Exercise 1

Week 2: Unstructured P2P Networks

The most common (and simplest) architecture for P2P networks
Peers come and leave as they please
Peers attach themselves to the network in an (more or less) ad hoc fashion
Search and routing become difficult – no precise knowledge of data and peer availability or location
Most primitive version: Gnutella
Pretty robust with regards to churn
Much cleverer approaches possible:
- Random Walkers
- Probabilistic Walkers
- Caching and replication

Week 3: Structured P2P Networks

Peers are added to the network at a precise location
Peers handle content specific to their place in the network
Most structured P2P networks locate content according to its key, therefore often known as Distributed Hash Tables (DHT)
DHTs can have very good performance – routing in O(log n)
DHTs are usually sensitive to high churn rates (costly to reestablish structured overlay network)

Week 4: P2P Applications

P2P can be used for other purposes than warez distribution (it's true!)
We look at some applications, such as PAST, YouServ, Skype, and BitTorrent, and some P2P frameworks

Week 5: Security and Reputation

Without a central authority (such as a central server) maintaining security and fairness becomes a challenge
Who can you trust?
How can identity be (reasonably) established?
How can we ensure good behaviour (ie. defeat “free-riding“)?

Week 6: Mobile P2P – Mobile Ad Hoc Networks

P2P on the Internet have a fair number of challenges, but that is all simple stuff compared to MANETs
Routing: You can only see your neighbours (some of the time)
Transience: You (and everybody else) may be moving about
Limited resources: You are using a radio and operating on a battery
We look at some of the challenges, especially with regards to routing

Week 7: The Grid

The Big Boys' P2P network
The Grid is used for the purpose of massively large scientific computations
This requires a high degree of
- Dependability
- Security
- Awareness
We look at the IBM Globus system

Summary

The strength of P2P is in numbers

Great number of unused processors
Great number of unused bandwidth

By leveraging these strengths, P2P systems can be built to increase

Computing power
Data availability
Free speech

This involves significant challenges

Routing
Churn
Security

Overview

Course overview
What is P2P?
Client/Server vs. P2P
P2P Characteristics
Typical P2P Applications
Example: Gnutella (and what's wrong with it)
Teasers for the rest of the course
Exercise 1

Exercise 1 – Basic discovery

Construct a peer, that can discover and list other peers. In essence, implement functionality similar to 'ping' and 'pong' from Gnutella. However, you are free/encouraged to create your own (extensible) protocol.

Each peer should publish a “quality value”, adjustable upon launch, signifying its strength.

The program must be interactive (though a GUI is certainly not necessary), and should run on Linux. You are free to use any programming language available. However, your program must require no more setup than “untar; make; make test” or similar.

Accompany the prototype with source and a short report (2-3 pages) detailing your assumptions (e.g. does your system work across subnets/firewall etc), protocol, design choices, and usage instructions.

Include information about all group members: Full name, user name, and student ID.

The exercise is mandatory and on a group basis.

Due 18:00 6/9/2006 by email to <n.o.bouvin@daimi.au.dk>