Transcript Route maintenance overheads in DHT overlays

NCCR-MICS [IP5]
Route maintenance
overheads in DHT overlays
presented by
Anwitaman Datta
Joint work with Karl Aberer and Manfred Hauswirth
{Karl.Aberer, Anwitaman.Datta, Manfred.Hauswirth}@epfl.ch
EPFL-I&C-LSIR [P-Grid.org]
Workshop on
onDistributed
Distributed Data
Dataand
andStructures’04
Structures’04
Workshop
P2P
 Central index
Content
XYZ
 Unstructured
 Flooding
Need XYZ
Network
 Super-peer
 Power-law networks …
P2P is more than just
File sharing or Pirate to Pirate!
Overheads in overlays © 2004, A. Datta, K. Aberer, M. Hauswirth @ WDAS’04
2
A Case for P2P

Goals:



Efficient, scalable and reliable resource
discovery/name resolution in a decentralized
internet scale system
Content addressable network - disentangle the
underlying network from the applications and
services
A reliable substrate for other distributed applications

Semantic Web, Grid computing, Web services, large scale
event notification, P2P web-search, …
Overheads in overlays © 2004, A. Datta, K. Aberer, M. Hauswirth @ WDAS’04
3
Challenges





Unreliability of autonomous participants (peers)
Unreliability of the communication network
Lack of global knowledge and coordination
Scalability and robustness (fault tolerance)
Performance
Overheads in overlays © 2004, A. Datta, K. Aberer, M. Hauswirth @ WDAS’04
4
Approach (& issues)

Distributed indexing and routing in an overlay
(disentangled from the underlying network)

Just like the world wide web, we can realize an overlay (but
more structured) on top of the internet infrastructure
e.g., Distributed Hash Table/Distributed Indexing


Peers (re-)joining/leaving the overlay =>
Maintenance of the overlay routes is required


P-Grid, Chord, DKS, CAN, Pastry, Kademlia, …
Self-healing while routing
Flux in overlay => system operates in dynamic
equlibrium

Two forces:


Changes in the network making routing information
unusable
Maintenance operations repairing routing information
Overheads in overlays © 2004, A. Datta, K. Aberer, M. Hauswirth @ WDAS’04
5
Prefix Routing in P-Grid
ID peer identifier
1
: 12, 13 routing table entry
0
query(101) @ 7
00
000
1
01
001
Peer 9 holds keys with
prefix 001, so we call,
its path is 001
10
010
011
100
11
101
Replicas
1
0,1
9
2,3
14
4,5
1 : 8,2
01 : 3, 10
000: 1,7
1 : 2,12
00 : 9,4
011: 3,10
7
4
5
1 : 12, 13
01 : 5,14
001: 9,4
2,3
1 : 6,13
01 :10,14
000: 1,7
4,5
1 : 8, 13
00 : 7,9
011: 3,10
3
6,7
1 : 11,12
00 : 1,9
010: 5,14
10
6,7
1 : 6,8
00 : 1,7
010: 5,14
11
8,9
13
10,11
0 : 4,7
11 : 2,12
101: 8,13
0 : 5,9
11 : 2,12
100: 6,11
6
8
8,9
0 : 1,3
11 : 2,12
101: 8,13
10,11
0 : 4,9
11 : 2,12
100: 6,11
12,13,14
0 : 1,14
10 : 11,13
12
1 : 12, 13
01 : 5, 10
001: 9,4
0,1
2
12,13,14
0 : 5,7
10 : 6,13
Self-healing, self-referential directory



Any distributed access structure (such as P-Grid) requires mapping
of a logical ID (associated data key) to physical ID (IP address)
This mapping cannot by static in the presence of dynamic IP
addresses (hence requires a directory service)
A very important problem for the implementation of any P2P
system
P-Grid
Self-referential directory
implemented by P-Grid
routing based on
lookup IP address
logical address
in case of failure
routing based on
logical address
lookup IP address
directory
(logical ID <-> IP address)
Overheads in overlays © 2004, A. Datta, K. Aberer, M. Hauswirth @ WDAS’04
7
Example
ID Presently online
query(01*) @ 7
…query(0101) @ 7 (for stale entry 5, cycle -> abort)
…query(1110) @ 7 (for stale entry 14, forward to 12 or 13)
ID Stores mappings
of peers
…query(1110) @ 12 (is offline)
…query(1110) @ 13 (for stale entry 2)
Up-to-date cache ……query(0010) @ 13 (forward to 5)
1 : 2 ,12
……query(0010) @ 5 (forward to 7)
……query(0010) @ 7 (forward to 9)
Stale cache
……query(0010) @ 9 (new entry for 2 found !)
…query(1110) @ 2 (new entry for 14 found !)
query(01*) @ 14 (finally )
ID Presently offnline
0
00
000
1
01
001
10
010
011
100
101
1
1 : 12, 13
01 : 5, 10
001: 9,4
7
1
1 : 12, 13
01 : 5,14
001: 9,4
9
2,3
1 : 8,2
01 : 3, 10
000: 1,7
4
2,3
1 : 6,13
01 :10,14
000: 1,7
14
4,5
1 : 2,12
00 : 9,4
011: 3,10
5
4,5
1 : 8, 13
00 : 7,9
011: 3,10
3
6,7
1 : 11,12
00 : 1,9
010: 5,14
10
11
2
6,7
1 : 6,8
00 : 1,7
010: 5,14
11
8,9
0 : 4,7
11 : 2,12
101: 8,13
6
8,9
0 : 1,3
11 : 2,12
101: 8,13
13
10,11
12,13,14
0 : 1,14
10 : 11,13
12
Key as 4 bits for ID (2=0010 etc.)
1
Routing
entries
repaired
12,13,14
0 : 5,7
10 : 6,13
0 : 5,9
11 : 2,12
100: 6,11
8
10,11
0 : 4,9
11 : 2,12
100: 6,11
offline
Possible strategies

Eager - Correction on Use (CoU)

While using a routing table, try correcting stale
entries even if the present query can be routed using
alternate routes (available locally).


Some entries of a particular level of routing table are
unusable, but other entries of the same level are still usable.
Lazy - Correction on Failure (CoF)

While using a routing table, try correcting stale
entries only if no alternate routes for the present
query is available locally.

All entries of a particular level of routing table are unusable,
but other levels may still be usable.
Overheads in overlays © 2004, A. Datta, K. Aberer, M. Hauswirth @ WDAS’04
9
Performance of overlays in flux

Static resilience

Given a state of the network, and no more changes,
how does the network perform?


Dealing with network churn

Given flux in the network, what maintenance cost is
required to maintain a certain state.



P-Grid, Chord, various topologies …
e.g., Lower bound (MIT/Chord)
Simulations … (many groups)
Dynamic equilibrium

Given any flux in the network, and any maintenance
strategy, what equilibrium state will the network
operate in, and what will the maintenance cost and
performance in the equilibrium state be?
Overheads in overlays © 2004, A. Datta, K. Aberer, M. Hauswirth @ WDAS’04
10
Eager recursion a.k.a. Correction on Use ‘CoU’
Dynamic equilibrium equation

LHS

Rate at which repair of stale routing entries occur





rup changes per 1-rup queries
Nrec – 1 additional recursive queries
Repair makes sense only if the routing entry to be repaired
corresponds to an online peer
A repair is possible only if recursive query succeeds
RHS




Rate of entries turning stale
rup changes
1-pdyn probability of non-stale references (only these can turn stale)
r references at each peer for each of log2n levels
Overheads in overlays © 2004, A. Datta, K. Aberer, M. Hauswirth @ WDAS’04
11
Lazy Repair Strategy (Correction on Failure ‘CoF’ )

Try to rectify stale references only when none of the references in
a given level are usable




Not all routing entries are treated uniformly (unlike in CoU).
The number of stale entries for each routing level at each peer
defines the state of that level.
Markovian model.
Dynamic equilibrium equation determined by equating inflow and
outflow for each state

At dynamic equilibrium, the number of routing levels with given
number of stale entries over the whole system should not change
0 ref
stale
ID
change
1 ref
stale
ID
change
2 ref
stale
ID
change
…
ID
change
r ref
stale
repairs
N.B. We distinguish stale entries from offline peers
Overheads in overlays © 2004, A. Datta, K. Aberer, M. Hauswirth @ WDAS’04
12
Analysis vs. Simulations (Lazy recursion)
Overheads in overlays © 2004, A. Datta, K. Aberer, M. Hauswirth @ WDAS’04
13
Overhead with varying pon
Overheads in overlays © 2004, A. Datta, K. Aberer, M. Hauswirth @ WDAS’04
14
Contour: Zone of operation for a maximum cost (Lazy)
Overheads in overlays © 2004, A. Datta, K. Aberer, M. Hauswirth @ WDAS’04
15
CoU (eager) vs. CoF (lazy)
Overheads in overlays © 2004, A. Datta, K. Aberer, M. Hauswirth @ WDAS’04
16
Our approaches
Taxonomy of route maintenance mechanisms
Reactive
strategies
Summary



Self-referential decentralized directory with self-healing
routing
Dynamic equilibrium of overlay network in flux (model
& analysis)
Route maintenance mechanisms



Correction on Use
Correction on Failure
Taxonomy of maintenance mechanisms
Overheads in overlays © 2004, A. Datta, K. Aberer, M. Hauswirth @ WDAS’04
18
Other/open issues

Security/DDoS/…







Identity/Authentication
Authorization/Privacy
Reputation/Trust
Quorums/Web-of-trust
Garbage collection of
references
Generic analysis (for
various DHTs)
Sensor networks or
MANETs and overlays
Overheads in overlays © 2004, A. Datta, K. Aberer, M. Hauswirth @ WDAS’04
19
References

Efficient, self-contained handling of identity in Peer-to-Peer
systems,
Karl Aberer, Anwitaman Datta, Manfred Hauswirth; IEEE
Transactions on Knowledge and Data Engineering 16(7), July
2004
& other papers @ http://www.p-grid.org
Questions?
Overheads in overlays © 2004, A. Datta, K. Aberer, M. Hauswirth @ WDAS’04
20