10-05-2013, 03:02 PM
Self-Organization in Structured Overlay Networks (DKS)
Self-Organization.ppt (Size: 1.44 MB / Downloads: 17)
Topology maintenance
How to keep routing state correct when nodes join, leave and fail?
Periodic stabilization
Each node periodically probes all its routing entries for changes
Correction on use (lazy)
Wrong routing entries are detected and corrected during lookup operations
Correction on change (eager)
A change in topology due to join/leave/failure triggers update of erroneous routing entries
DHT Summary
Completely decentralized
Self-organizes as nodes join, leave, and fail
Maximum log2(N) number of hops to find items, where N is the number of hops
Each node only stores a small amount of items, on average D/N (D is the number of items)
Each node only maintains a small amount of routing information log2(N)
Each join/leave/failure event requires D/N items to be reshuffled
Each join/leave/failure event requires (log2(N))2 messages to restore the routing state
How to model churn?
How to generate continuous joins/failure and maintain steady state?
We found 3 schemes used in the literature:
Global joins, Global failures (Li2004, Stoica02)
Local joins, Local failures (Krishnamurthy04)
Global joins, local failures (Liben-Nowell2002)
Global: # of events is a function of initial network size
Local: # of events is a function of current network size at each time
Estimation of Global Quantities from Local Quantities
Estimation of N
Each node can get a rough estimate of N from the density of nodes in its successors list.
Estimation of of
Each node can get a rough estimate of from observing the encountered failures during an observation period
By exchanging the rough estimates between nodes during stabilization, more accuracy and agreement on the value of N could be achieved