Peer-to-Peer Computing and Structured Overlay Network

Introduction to Peer-to-Peer Networks

Overview of Peer-to-Peer Networks

• Peer-to-peer (P2P) networks allow flexible sharing of resources like files and multimedia across a network of computers.

• In P2P networks, all nodes, referred to as peers, function equally as clients and servers, enabling direct communication without the need for DNS.

• The concept of "churn" refers to the dynamic insertion and deletion of nodes in a P2P network, which helps maintain resource availability at low costs.

Characteristics of Peer-to-Peer Networks

• P2P networks are self-organizing and provide combined storage and CPU power while maintaining distributed control among nodes.

• Key features include anonymity, efficient management of churn, and a naming mechanism that selects geographically close servers for improved performance.

Data Searching Mechanisms in P2P Networks

Search Algorithms

• The core mechanism in P2P networks is data searching; this relies on how data is organized within the network.

• Unlike host-centric algorithms used on the Internet, P2P search mechanisms are data-centric, allowing queries directly related to specific objects or files.

Overlay Network Structure

• P2P overlay networks can be classified into structured and unstructured types based on their organization principles.

• Structured overlays use fixed topologies like distributed hash tables (DHT), while unstructured overlays do not follow any rigid structure.

Differences Between Structured and Unstructured Overlays

Structured Overlays

• In structured overlays, file placement is deterministic with fast lookup capabilities using hash mapping based on file names.

Unstructured Overlays

• Unstructured overlays lack a defined structure for object storage; they often rely on ad hoc search mechanisms such as flooding or random walks.

Indexing Methods in Peer-to-Peer Networks

Types of Indexing

• Three main indexing methods exist: centralized indexing (e.g., Napster), distributed indexing (using DHT), and local indexing where each peer indexes only local objects.

Semantic vs. Semantic-Free Indexing

• Semantic indexing supports human-readable keywords for searches while semantic-free indexing uses hash functions for structured overlays.

Distributed Hash Tables (DHT)

Overview of DHT Functionality

• DHT maps node address space to object space using consistent hashing functions that ensure efficient file lookups despite node changes.

Chord Protocol Example

• The Chord protocol utilizes a flat key space to map network nodes with data objects efficiently through consistent hashing techniques.

Managing Node Joins and Departures

Node Management Strategies

• When nodes join or leave the network, consistent hashing minimizes overhead by redistributing keys uniformly across remaining nodes.

Lookup Operations in Chord Protocol

• A simple lookup operation involves tracking successors along a logical ring until reaching the appropriate node storing the desired key.

Scalable Lookup Enhancements

Improving Lookup Efficiency

• Scalable lookup enhances efficiency by increasing routing table size from order one to order log n entries while reducing hops needed during searches.

Finger Table Utilization

• Each node maintains a finger table containing multiple entries that help locate successor nodes more quickly than simple lookups.

Node Insertion in a Distributed Hash Table

Understanding Node Joining Process

• When a new node (I) joins the network, it locates its successor (J), which will be responsible for managing I's data.

• The predecessor of J (K) must update its successor to point to I, ensuring that the logical ring remains consistent.

• The insertion process involves changing the predecessor and successor pointers accordingly, maintaining the integrity of the network structure.

Finger Table Creation and Stabilization

• After joining, node I must create its own finger table while existing tables are updated; this is crucial for efficient lookups.

• Until I's finger table is fully populated, lookups may require more hops than optimal, resulting in linear rather than logarithmic search times.

Managing Node Failures

• Periodic checks (check predecessor function) help identify failed nodes and allow for updates to successor and predecessor pointers.

• If a node fails, notifications trigger adjustments in the network to ensure continuity by finding new functional successors.

Complexity Analysis of DHT Networks

Key Metrics in Network Performance

• Each node manages approximately 1 + epsilon K/n keys with high probability; K represents total keys and n denotes nodes.

• Time complexity for locating successors is logarithmic (O(log n)), while average lookup time can be optimized further through structured peer-to-peer networks.

Comparison with Other Protocol Structures

• Various protocols like CAD, Mela, Pastry, Tapestry, and Viceroy exhibit different structural designs impacting routing efficiency within peer-to-peer networks.