Structuring Unstructured Peer-to-Peer Networks Stefan Schmid Roger Wattenhofer D
Zeman, Alan, Host has reference to this Academic Journal, PHwiki organized this Journal Structuring Unstructured Peer-to-Peer Networks Stefan Schmid Roger Wattenhofer Distributed Computing Group HiPC 2007 Goa, India Networks DISTRIBUTED COMPUTING Internet Graph Web Graph Neuron Networks Social Graphs Public Transportation Networks Different properties: Natural vs. Man-made Robustness Diameter Routability An Interesting Network: Peer-to-Peer Network Popular Examples: File sharing: BitTorrent, eMule, Kazaa, Streaming: Zattoo, Joost, Internet telefony: Skype, etc. Important: p2p accounts as long as much Internet traffic today! (source: cachelogic.com) Network of peers, e.g., to share files Desirable properties: Scalability Low degree, low network diameter Fast routing etc.
This Particular University is Related to this Particular Journal
Some Own Applications Wuala online storage system – Student project, start-up, http://wua.la Pulsar streaming – tilllate.com, DJ events, ; pstreams.com – cheap infrastructure at content provider BitThief BitTorrent downloads Distributed Computations – BOINC client as long as ECC discrete logarithm challence Successful paradigm & technology, but still important research challenges! Structured vs. Unstructured Topologies Old p2p systems such as Napster were based on server – Server stores index: search as long as contents is simple – Problem: single point of failure – Legacy issues Unstructured systems, e.g., Gnutella, allow arbitrary topologies in addition to arbitrary data placement – Peers just connect to an arbitrary set of other peers – No single point of failure – But often inefficient: routing based on flooding or r in addition to om walk Structured systems, e.g., eMules Kad network, give guarantees – Proactive maintenance of topology – Provable network diameter in addition to peer degree – Routing possible, look up, e.g., in log(n) hops (maybe also low stretch) What is better Unstructured systems have less maintenance overhead – Peers can join in addition to leave wherever they want Unstructured systems allow as long as a richer set of queries – e.g., range queries, Boolean queries Most importantly: despite the interesting properties ( in addition to large body of research) of structured networks, todays predominant networks are still unstructured (e.g., Gnutella, BitTorrent, etc.) Really Really Flooding always possible! But unstructured systems often have scalability problems When Napster was unplugged, Gnutella went down. Discussion needs to be continued !
Routing in Arbitrary Topologies How to find a file in an arbitrary network Option 1: Flooding (up to a certain hop radius r) Robust, but does not scale. Does not find the needles, but does a good job finding popular files. Option 2: R in addition to om Walks Less messages, but no lookup per as long as mance guarantee. Potentially large delay (solution: many parallel walkers) Walkers can be lost Analysis difficult. Again: Good to find popular contents, bad to find needles. Flooding This talk considers search operations by flooding. Efficiency of flooding Very efficient on trees! Many redundant transimissions Flooding efficiency depends on network topology! Clustella We propose Clustella – a new P2P client as long as unstructured peer-to-peer systems – based on flooding, but with smart neighbor selection – allows as long as more efficient flooding!
Vision Clustella Vision: unstructured p2p network Normal client Clustella client By connecting to peers in far-away parts of the network, small cycles in the topology are avoided, in addition to flooding is more efficient. Not only Clustella clients do benefit, but also all other clients in the network. Flood Coverage Main open question: How to connect to remote peers Given a set of potential neighbors, it would be useful to know the hop distance to each of those! Then, we could connect to the one furthest away Goal: Maximize flood coverage, i.e., maximize minimum number of nodes reached by a r-hop flooding locally in addition to despite dynamics Hop-Estimation With Clustering Main idea: Use clustering! – Divide network into different clusters. – Peers in different clusters belong to different network regions in addition to can safely be connected without creating small cycles. How to achieve such a clustering Introduction of beacons! – Two parameters: radius Rd in addition to radius Rb (Rd < Rb) - If a peer has no beacon in Rd neighborhood, it becomes a beacon itself. - A peer knows all beacons in its Rb neighborhood. - Rb roughly equals the flooding radius R Clustella Mechanism (1) One beacon in radius Rd Beacon known in radius Rb Flooding radius R Beacons append their ID to all packets (piggy-back) If packet expires be as long as e, other peers (here: ) as long as ward beacon in as long as mation Entire Rb neighborhood will know beacon Peers try to connect to peers which have no beacons in common! Clustella Mechanism (2) Edges are undirected All peers have degree d or d+1 If connection is accepted if own degree is d or smaller; otherwise, a neighbor may have an open slot, or a connection is broken down Invariant quickly reestablished! Neighbors of existing neighbor are also good c in addition to idates, as they are located in the same network region. Two Challenges Evaluation of current neighbors Existing neighbors are always in the same network region Evaluating their quality in addition to comparing them to alternative neighbors is difficult Include routes in packets! Exclude beacons known from a neighbor only Dynamics Clustella must be robust to churn, i.e., frequent joins in addition to leaves E.g., node crash: Clustella peer p stores some neighbors as long as each of its neighbors q; these neighbors are good c in addition to idates as they are in the same network region as q Evaluation Simulation of three different neighbor selection strategies Gnutella-like (unfair): Peers join at some well-known entry point in addition to ask as long as their neighbors neighbors until they reach full degree R in addition to om walk (more interesting): Peers find new peers by a r in addition to om walk of length L Clustella: Peers find new neighbors by exploring the network using a walk of length L in addition to by taking beacon in as long as mation into account Results Gnutella-like topologies result in very inefficient flooding operations Clustella yields higher flood coverage than r in addition to om walk Future Work Hierarchical clustering (beacons with different radii) - Already a small hierarchy can yield better flood coverage - However, maintenance of hierarchy can be expensive under churn! - Moreover, fairness must be guaranteed: High-level beacon peers should not have more work to do! Smaller messages Reducing the message sizes as long as large radii is important! Idea: Use of Bloom filters instead of sending beacon IDs directly Conclusion We believe that structuring topologies can be benefitial to peer-to-peer systems! Clustering with beacons is simple in addition to probably also useful in other applications, e.g., in music graph Implementation must ensure fairness in addition to use small message sizes. A good choice of parameters important as long as both efficiency in addition to stability. Incorporation into Gnutella Thank you. Thank you as long as your interest.
Zeman, Alan Host
Zeman, Alan is from United States and they belong to Restaurant Corner – KJLL-AM and they are from Tucson, United States got related to this Particular Journal. and Zeman, Alan deal with the subjects like Restaurants/Dining
Journal Ratings by Catholic Theological Union
This Particular Journal got reviewed and rated by Catholic Theological Union and short form of this particular Institution is US and gave this Journal an Excellent Rating.