Transcript Pierre Fraigniaud CNRS LRI, Univ. Paris-Sud

Optimisation des DHT
à partir des propriétés
physiques, logiques et
sociologiques des clients
Pierre Fraigniaud
CNRS
LRI, Univ. Paris-Sud
http://www.lri.fr/~pierre
Plan
•
•
•
•
Distributed Hash Table (DHT)
Structural properties
Sociological properties
Conclusion
Principles of DHTs
DHT
• File, data, etc  name
• Typically: name space = [0,1[
• h(file_name) = 0.10110001101
• User  name
• User name  [0,1[
• h(my_IP@) = 0.0011010110
Correspondence
Users = { }
user x
1 0
Data stored by x
Overlay network
1 0
y
x
x knows the
IP@ of y and z
z
Lookup
1 0
x
h(Andrei Rublev)
Node insertion
1 0
Entry point
Examples
•
•
•
•
•
CAN (D-dimensional meshes)
Chord (hypercube)
Viceroy (butterfly)
D2B, Koorde (de Bruijn)
…
Structural Properties
Desirable properties
• Small number of hops for lookup:
i.e., small diameter and efficient routing
• Quick updates:
i.e., small degree
• Small congestion:
i.e., small probability of contention
From the network point of view
Taking the inter-node distance in
Internet into account!
length(overlay route)
stretch = maxall routes
length(Internet route)
It does not mean that closely related
nodes must be close in the Overlay.
Solution
Theorem (Abraham & Malkhi)
Under some conditions on the physical
network,…
…there exists an overlay network with
strech 1+ε, degree and diameter
O(log n).
From the user point of view
Taking the user interests into account!
Closely related users aim at being close
in the Overlay.
How to measure proximity between
users?
Requests types
• Typo:
h(André Roublef) vs. h(Andrei Rublev)
• Structure:
Prefix search, interval, etc
• Data-base type requests
Sociological Properties
Connect users sharing
common interets
• Gnutella enhanced with additional
links…
• Every user keeps links only with users
sharing common interest (cf. Maay)
Structure of user connections
• Scale-free structure:
Degree distribution = power law
Prob( deg(x)=k ) ≈ k-a
• Guided walk in scale-free graphs
• Random walk
• Shortest path
• Neighbor with largest degree first
Rumors and legends
Path length
Random walk
Neighbor with
highest degree first
Shortest path
Network size
Using small world properties
• Milgram’s experiment  six degrees
of separation between indivitual
• Kleinberg’s augmented meshes
capture this phenomenon
• DHT Symphony (!)
• Why not just doing greedy routing?
Conclusion
Conclusion: users sociological properties
seem to have more impact on DHT’s
than network structural properties
Unfortunately sociological properties
are difficult to model and to measure
Warning: this conclusion might be not
true in other contexts, e.g., ad hoc,
global computing, etc.