P2P Supernodes

75 %
25 %
Information about P2P Supernodes

Published on October 9, 2009

Author: kmregan

Source: slideshare.net


Some work looking at the theoretical implications of the use of supernodes in peer-to-peer networks.

Necessity of Supernodes David Hadaller, Kevin Regan and Tyrel Russell

P2P Networks Internet application Application Layer Overlay Networks 2

Problems of P2P Networks Scalability Security Anonimity Fault Tolerant 3

P2P Structured Unstructured Networks Centralized Napster ??? Decentralized Chord/Tapestry Gnutella/Kazaa 4

The centralized and unstructured decentralized systems are not scalable in their vanilla form Structured decentralized networks are scalable But require the topology to be of a certain structure 5

Alternatives... The addition of supernodes seems to make unstructured decentralized networks scalable Why? 6

Three Directions Traditional Decentralized Unstructured (Flooding) P2P Networks Graph Theoretical Bounds Decentralized Structured P2P Networks 7

What is a Peer-to- Peer System? Most commonly used for file sharing Napster released 1999, shutdown 2001 Gnutella released 2000 Kazaa released 2001 Today: millions of users sharing petabytes of data

System Interaction User issues a keyword search Network returns list of peers contain matching files

Architecture A peer operates as both a client and a server Idea: Everyone is equal, everyone cooperates (both not true) File sharing: -FastTrack (Kazaa, Kazaa Lite) -Gnutella (Morpheus, LimeWire)

How do Unstructured Peer- to-Peer Systems Work?

Scalability Issues Gnutella not scalable

Making Gnutella Scalable Chawathe et al. obtained 3 to 5x improvement in system capacity Adding nodes of higher degree Kazaa

Host Characteristics 6% users very well connected 10% of sessions >5 hrs

Impact of File Sharing Study at the University of Washington P2P accounts for 43% Internet traffic Web accounts for 14%

Graph Theory Formulate the problem as a Graph Theory Problem Let the P2P network be a graph G where G is a set of vertices V and there exists an edge between two nodes u,v∈V when u is a neighbour of v in the overlay network 16

Some Definitions Maximum Degree We denote ∆ as the maximum over the degree of all vertices of a graph. Minimum (u,v)-path We denote the minimum path between two vertices u, v, u ≠ v, as d(u, v). Diameter We define diameter D as the length of the max d(u, v) for all u, v ∈ V 17

Moore Bound Upper bound on number of vertices in a graph with max degree Δ and diameter D D n ≤ 1 + ∆ 1 + (∆ − 1) + · · · + (∆ − 1) ∆(∆ − 1)D − 2 ≤ = n0 (D, ∆) ∆−2 n(∆−2)+2 log ∆ D≥ log(∆ − 1) 18

Moore Bound d(u,v) = D v d(u,v) = 2 v v d(u,v) = 1 v v !-1 v v !-1 v u ! v v n ≤ 1 + ∆ 1 + (∆ − 1) + · · · + (∆ − 1)D 19

Special Graphs Moore Graph Have equivilence in the Moore bound Diameter of 2: Moore graphs only exist with Δ = 3, 7, 57 Diameter more than 3: No Moore graphs exist de Bruijn Graph 8 4 Leland-Solomon Graph 6 3 9 2 7 1 5 0 20

Random Graphs We are interested in property Q, so for a graph of size n Enumerate the number of possible graphs with Q If proportion of graphs with Q → 1 as n → ∞ Then we say that almost every graph has property Q 21

Random Graphs Some properties: almost every graph has diameter 2 is k-connected for a fixed k > 2 has no complete subgraph Hk where k > 2log2n 22

Random Graphs For a fixed Δ ≥ 3 almost every Δ-regular graph has diameter 6∆ D ≥ log∆−1 n + log∆−1 logn − log∆−1 +1 ∆−2 23

Graph Theory Summary There is a theorectical limit to search in a P2P network As logn increases the time to search will increase by roughly O(logn) 24

Distributed Hash Tables Distributed Hash Tables (DHTs) are an implementation of a decentralized, structured peer-to-peer network The diameter of the network scales logarithmically with the size of the network Node degree varies from O(1) to O(log n) 25

Implementations Tapestry - Plaxton Mesh CAN - d-dimensional Torus Pastry - Logical Ring Chord - Logical Ring with Chords Koorde - Logical Ring with deBruijn Graphs HyperCuP - Hypercube 26

Number of Name Degree Diameter Nodes Tapestry N O(log N) O(log N) CAN N O(d) O(n1/d) Pastry N O(log N) O(log N) Chord N O(log N) O(log N) Koorde N O(1) O(log N) HyperCuP N O((b-1)l) O(log N)

Conclusion Graph theory gives us a way to bound almost any random graph with a given number of nodes and a maximum degree Flooding P2P networks have looked at scalability from an empirical perspective Distributed Hash Tables provide a scalable method for P2P at the cost of 28

Questions? 29

Add a comment

Related presentations

Presentación que realice en el Evento Nacional de Gobierno Abierto, realizado los ...

In this presentation we will describe our experience developing with a highly dyna...

Presentation to the LITA Forum 7th November 2014 Albuquerque, NM

Un recorrido por los cambios que nos generará el wearabletech en el futuro

Um paralelo entre as novidades & mercado em Wearable Computing e Tecnologias Assis...

Microsoft finally joins the smartwatch and fitness tracker game by introducing the...

Related pages

P2P - Peer to Peer - wwwdh.cs.fau.de

P2P - Peer to Peer Henry Sch¨afer WebSite Engineering Seminar 24. ... mehrere SuperNodes pro Cluster bilden, deren Indexdaten redundant gehalten werden
Read more

Skype replaces P2P supernodes with Linux boxes hosted by ...

Ministry of Innovation — Skype replaces P2P supernodes with Linux boxes hosted by Microsoft (updated) Microsoft has replaced P2P Skype supernodes with ...
Read more

Peer-to-Peer — e-teaching.org

Reines P2P-Netz mit gleichberechtigten Teilnehmern. ... Andere Formen hybrider Peer-to-Peer-Systeme machen vom Prinzip so genannter Supernodes Gebrauch.
Read more

Peer-to-Peer - Willkommen auf e-teaching.org

Reines P2P-Netz mit gleichberechtigten Teilnehmern. ... Andere Formen hybrider Peer-to-Peer-Systeme machen vom Prinzip so genannter Supernodes Gebrauch.
Read more

Schwachstelle im P2P-Netzwerk FastTrack bedroht Supernodes ...

Durch einen Fehler im P2P-Protokoll sollen Angreifer die im FT-Netzwerk verwendeten Supernodes manipulieren können.
Read more

Peer-to-Peer-Architekturen - www-vs.informatik.uni-ulm.de

Peer-to-Peer-Architekturen C. Architekturen 2) Super P2P Ausbau von Hybride P2P: Tausch der zentralen Verwaltungsinstanz mit P2P-Netzwerk Bsp.:
Read more

Peer-to-Peer - 4FriendsOnly.com Internet Technologies AG

Gliederung Entstehung von P2P Client-Server vs. Peer-to-Peer Modelle Anwendungsbereiche ... Suchanfragen erstrecken sich nur auf Supernodes Ist die ...
Read more

How Does Kazaa Work? - How Kazaa Works | HowStuffWorks

How Kazaa Works. by ... Kazaa uses peer-to-peer (P2P) file sharing ... The approximately 30,000 supernodes on Kazaa act a lot like traffic hubs, ...
Read more

Skype: Linux als Supernode - Golem.de

Skype hat in seinem Netzwerk zahlreiche Linux-Server eingerichtet, die als Supernodes dienen. ... hat Microsoft im P2P-Netzwerk Supernodes eingerichtet.
Read more

P2P: Telefonieren mit KaZaA - SPIEGEL ONLINE

P2P: Telefonieren mit KaZaA. Telefongespräche über das Internet gibt es seit Jahren, im Kundenmarkt konnten sie sich bisher nicht durchsetzen ...
Read more