Computer Networking Lecture Notes

2013 November 21 • Peer-to-Peer Architectures

---

Outline

Architectures

• The architecture relates the pieces to the whole.
  • The purpose of each piece.
  • The relation among pieces.
• Apart from organization, architectures allow
  • Comparison among similar systems.
  • A hook for analysis.
  • Navigation through the design space.

Centralized Architectures

Centralized Architectures

• A distributed architecture with distinguished pieces
  • The pieces are usually called servers.
• Servers off-load specific functions from other nodes.
  • Routing servers, storage servers, indexing servers, …
• Nodes needing a function contact the appropriate server.

Example

Centralized Systems

• An inheritance from client-server systems.
  • The servers are “thinner” in peer-to-peer systems.
• Peer-server contact tends to be brief and to establish or re-establish, relations in the system.
  • Directory servers for example.

SETI@home

• Search for Extra-Terrestrial Intelligence, SETI@home.
• A massive distributed computing success.
• Distributed computing exploiting idle CPUs.
• SETI servers maintain small, well-defined computation chunks (code + data).
• Peers query servers for work, reply servers with results.
• Other services: peer sign-up, results checking, credit management, team organization, …

SETI Characteristics

• Unscalable and unreliable.
  • Servers can be a bottleneck under load.
  • Work storage is part of the problem.
• Efficient and effective.
  • Distributed computation, effectively unlimited at an excellent price/performance ratio.
• Privacy, anonymity, and security.
  • Peers are in the dark, servers aren’t.

Napster

• Napster was one of the first successful (semi) peer-to-peer systems.
• A system devoted to file sharing.
• Each Napster peer offered files for sharing.
• Peers registered file lists with the Napster server.
• A server query was a list of file names, the response was a list of hosting peers.
• The querying peer directly contacted hosting peers.

Example

Napster Characteristics

• Unscalable and unreliable.
  • The server is a bottleneck under load.
  • Copyright holds had an obvious take-down target.
• Efficient and effective.
  • Storage was distributed, effectively unlimited.
  • Performing search was easy and fast (modulo scalability).
  • The free-rider problem.

Centralized Analysis

• Servers in a system
  • Increase efficiency by reducing search.
  • Focus and amortize build and run costs.
  • Make network management easier.
• Unfortunately, they’re also
  • Unscalable with respect to peer count.
  • A single failure point.
• However, servers can peer and be distributed.

Dentralized Architectures

Decentralized Architectures

• A distributed architecture with uniform nodes.
• Each node provides system services.
  • Usually with help from other nodes.
  • Distributed service delivery.
• Navigation (as opposed to location) becomes important.
  • A single node will be most ways unsatisfactory.

Structure and Topology

• Decentralized structure measures hierarchy.
  • Hierarchical structures are organized into tiers or levels.
  • Flat structures are without levels.
• Decentralized topology characterizes logical relations among nodes.
  • Structured topologies impose definite node relations.
  • Unstructured topologies result in random (or undefined) relations.

Gnutella

• Original Gnutella was the first fully decentralized peer-to-peer system.
• Exploratory, mainly for resource sharing.
• Each Gnutella peer was fully autonomous: entry, exit and resources.
• The ping-pong protocol let peers connect to other peers.
  • A new peer pings old peers.
  • Old peers pong with a neighbor list.

Gnutella Characteristics

• Search and navigation by modified flooding.
• Peer scalable, system unscalable and expensive.
  • Easy and autonomous peer entry and exit.
  • Modified flooding doesn’t scale under load.
• Uncertain and unstable.
  • No indexing into stored resources.
  • Performing search was easy and fast (modulo scalability).

Decentralized Topology

Decentralized Topology

• Decentralized topology characterizes logical relations among nodes.
  • Structured topologies impose definite node relations.
  • Unstructured topologies result in random (or undefined) relations.
• Topology trades off between
  • search and navigation and
  • dynamism and resilience.

Unstructured Topology

Unstructured Topology

• An unstructured topology leaves everything up to the nodes to discover.
• The most important discovery are one-hop neighbors.
  • Other important topological attributes follow.
• Configuration discoveries can be
  • statically determined, almost a priori, or
  • reconfigurable, in response to changing conditions.

Structured Topology

Structured Topology

• A structured topology defines levels into which nodes are slotted.
• The placement of nodes into levels can be
  • precise, always guaranteed to hold for particular nodes, or
  • probabilistic, holding in general for nodes collectively.
• Structured topologies can be thought of as mappings between important system features.

Decentralized Structure

Decentralized Structure

• Decentralized structure measures hierarchy.
  • Hierarchical structures are organized into tiers or levels.
  • Flat structures are without levels.
• Structure trades off between
  • autonomy and reliability and
  • management and costs.

Chord

• Chord is a flat, structured peer-to-peer network.
• Based on a distributed hash table.
• Each Chord peers are autonomously members.
• The Chord protocols maintain routing tables at each node for fast search and navigation.

Chord Characteristics

• Per-node routing tables.
• Peers and system scalable; routing table maintenance is expensive.
  • Chord protocols for peer entry and exit.
  • A periodic clean-up protocol fixes uncoordinated exits.
• Search is fast and certain.
  • Logarithmic in the number of peers.
  • Uncoordinated exits may lose resources.

Summary

• Peer-to-peer network architecture can be unstructured, structured, or hybrid.
  • Unstructured: arbitrary nodes and links.
  • Structured: constrained links, arbitrary nodes.
  • Hybrid: constrained links and nodes.
• Choices weigh between efficiency and reliability, adaptability and overhead, and others.

References

• Architecture of Peer-to-Peer Systems (Chapter 2) in Peer-to-Peer Computing by Quang Hieu Vu, Mihai Lupu, Beng Chin Ooi from Springer, 2010.
• A Survey and Comparison of Peer-to-Peer Overlay Network Schemes by Eng Keong Lua, Jon Crowcroft, Marcelo Pias, Ravi Sharma and Steven Lim in IEEE Communications Surveys and Tutorials, v. 7, n. 2, 2005.

---

This page last modified on 2013 April 22.