1. P2P Systems Flashcards
What are P2P Systems?
P2P is a class of applications that takes advantage of resources –
storage, cycles, content, human presence – available at the edge of
the Internet.
Because accessing these decentralized resources means operating in
an environment of unstable connectivity and unpredictable IP
addresses, P2P nodes must operate outside the DNS system and
have significant or total autonomy from central servers.
What are the characteristics of P2P systems?
- Direct interaction of systems (peers)
- Equal and autonomous participants
- Joint usage of resources
- No central control / usage of central services
- Self-organization of the system
What are the 1st generation p2p systems?
- Centralized P2P (Napster)
- Pure P2P (Gnutella 0.4)
Describe the characteristics of Napster
- Central Directory Server stores all information
- One-hop lookup
- Then direct p2p communicatoin
Disadvantages: - SPOF, bottleneck
Describe the characteristics of Gnutella 0.4
- Message flooding on query
- Then p2p communication
Disadvantages: - Lots of overhead
- Possible false negatives due to maximum hop distance of query
What is the 2nd generation p2p system and what are its charactesristics?
Hybrid P2P (Gnutella 0.6):
- Hierarchical network (superpeers and leafnodes)
- Election process to determine superpeers
- Reduces traffic at leaf nodes but not at superpeers
- Creates asymmetric load
- Still false positives
Give the definition for the clustering coefficient
C(v) = (2*e(v)) / (deg(v) * (deg(v) -1))
e(v) denotes the number of connections of v’s neighbors that are
connected with each other
Give the definition for the path length |P(v,w)|, the distance d(v,w) and the diameter of g.
- The path length is defined by the number of edges in path P
- The distance is the minimal path length of any path between point v and w
- The diameter of g is the largest distance between two nodes (v,w) in g.
What is a small world network?
A small world network is a network with a dense local structure and a
diameter comparable to a random graph with same numbers of nodes
and edges
Name models that create random, small-world and power-law networks.
Random: Gilbert Random Graph
- n vertices. Connect two vertices with the probability p
Small world: Watts-Strogatz model
- Create a ring of n vertices and connect them to the next k neighbours clockwise.
- Generate a random number for each edge between 0 and 1.
- Set threshold p and rewire edges with a number below p. Keep source vertex and choose a random destination node
Power law networks: Barábasi-Albert model
- Start with a small network
- Every time step, add a new vertex x. Add m edges from x to the
vertices v that are already there, where the target of the edges is
drawn with the probability given by the preferential attachment
What are three measures for networks?
- Average path length
- Clustering coefficient
- Node degree distribution
How does a new node join the chord ring?
- Generate node id (e.g. hash(ip + port))
- Contact entry node ( known via e.g. reverse dns, public list)
- Copy data for give chord range
- Update finger tables
What are applications for i3?
- Mobility support
- Multicast
- Anycast
How does i3 work?
- Based on DHT
- Content identifier (ID) is a hash
- Sender sends (ID, data) to responsible i3 node
- Receiver subscribes to data with a trigger (ID, R) at i3 node
- i3 nodes forwards data (R, data)
How is multicast realized in i3?
- Multiple triggers at i3 node: (ID, R1), (ID, R2), …
