1 DHT Fig. 1 Example of DHT 2 Successor Fig. 2 Example of Successor 2.1 Distributed Hash Table key key value O(1) DHT DHT 1 DHT 1 ID key ID IP value D

Size: px

Start display at page:

Download "1 DHT Fig. 1 Example of DHT 2 Successor Fig. 2 Example of Successor 2.1 Distributed Hash Table key key value O(1) DHT DHT 1 DHT 1 ID key ID IP value D"

しょうじのじま
6 years ago
Views:

1 P2P 1,a) 1 1 Peer-to-Peer P2P P2P P2P Chord P2P Chord Consideration for Efficient Construction of Distributed Hash Trees on P2P Systems Taihei Higuchi 1,a) Masakazu Soshi 1 Tomoyuki Asaeda 1 Abstract: Peer-to-Peer (P2P for short) systems and Distributed Hash Tables (DHTs for short), which are implementations of P2P systems, have attracted much attention in recent years because of their performance, scalability, and fault tolerance. Unfortunately, as far as we know, little is known about efficient construction of distributed hash trees on P2P systems. Therefore in this paper we propose several constructions of the hash trees on Chord, which is a most famous implementation of DHTs. Keywords: P2P, Chord, hash tree, data authentication 1. Peer-to-Peer P2P P2P P2P 1 Chord[1] Chord 1 Hiroshima City University a) mw68020@wm.hiroshima-cu.ac.jp 1 1 P2P Chord P2P Chord 2. 1

1 DHT Fig. 1 Example of DHT 2 Successor Fig. 2 Example of Successor 2.1 Distributed Hash Table key key value O(1) DHT DHT 1 DHT 1 ID key ID IP value DHT 2.2 Chord Chord 2.2.1 Chord DHT P2P SHA-1[2] 2 160 0 ID 2 160 1 ID SuccessorList FingerTable Predecessor N O(log N) 2.

2 1 DHT Fig. 1 Example of DHT 2 Successor Fig. 2 Example of Successor 2.1 Distributed Hash Table key key value O(1) DHT DHT 1 DHT 1 ID key ID IP value DHT 2.2 Chord Chord Chord DHT P2P SHA-1[2] ID ID SuccessorList FingerTable Predecessor N O(log N) SuccessorList Chord k 1 Table 1 Fig. 3 3 SuccessorList Example of SuccessorList N15 SuccessorList Example of node N15 s routing table of SuccessorList SuccessorList[i] SuccessorList[1](N15) SuccessorList[2](N15) SuccessorList[3](N15). i N20 N31 N38. k Successor 2 Successor 2 N15 N26 N15 Successor N26 Successor Chord Successor Successor Successor SuccessorList SuccessorList N r = O(log N) 3 SuccessorList 3 N15 SuccessorList FingerTable Successor Chord 2

3 5 Fig. 5 Example of hash tree 4 FingerTable Fig. 4 Example of FingerTable 2 N8 FingerTable Table 2 Example of node N8 s routing table of FingerTable FingerTable[i] i FingerTable[1](N8) N14 FingerTable[2](N8) N14 FingerTable[3](N8) N14 FingerTable[4](N8) N21 FingerTable[5](N8) N32 FingerTable[6](N8) N42 Successor N N Chord N O(N) FingerTable FingerTable n +2 0, +2 1, +2 2,, +2 n Chord 64 FingerTable N8 FingerTable 2 N8 N48 Successsor 6 FingerTable N k i d i h(m n) m n H h(= 1, 2,, H) 1 H 1 d 3 d 3 k 4, c 21, c 12 r d 3 d 3 k 3 k 4 c 22 c 21 c 22 c 11 c 11 c 12 r r r d 3 m log m 3. Chord 3.1 Chord P2P Chord 3

4 6 2 Fig. 6 Example of hash tree construction with 2-pass hash tree method 3.2 r N1 1 r Chan 2 [3] P2P s N1 N1 N2 1 N1 1 N2 N3 N3 N Chord Chord Successor Chord Successor FingerTable Fig. 7 Example of hash tree construction with Method 2 8 N1 N2 N3 N5 7 N1 N2 N3 N5 N1 ϕ N3 N5 2 7 N2 N4 N3 N4 N5 N6 N7 3 N4 N6 N7 N8 N8 N Chord Chord 4

5 Table 4 4 The number of messages in our proposed methods Fig. 8 Example of hash tree construction with Method 3 Table 5 5 The number of steps in our proposed methods Chord N1 N2 N3 N4 N8 N1 N5 N6 N7 N N Chord Chord Table 3 Evaluation of the number of messages and steps in our proposed methods 1 N 1 N N 2 log N N 2 (log N) P2P Chord 2 3 5

6 [1] Stoica, I., Morris, R., Liben-Nowell, D., Karger, D., Kaashoek, M., Dabek, F. and Balakrishnan, H.: Chord: a scalable peer-to-peer lookup protocol for internet applications, Networking, IEEE/ACM Transactions on, Vol. 11, No. 1, pp (2003). [2] Eastlake, 3rd, D. and Jones, P.: US Secure Hash Algorithm 1 (SHA1) (2001). [3] Chan, H. and Perrig, A.: Round-Efficient Broadcast Authentication Protocols for Fixed Topology Classes, Security and Privacy (SP), 2010 IEEE Symposium on, IEEE, pp (2010). 6

i

21 Fault-Toleranted Authentication Data Distribution Protocol for Autonomous Distributed Networks 1125153 2010 3 2 i Abstract Fault-Toleranted Authentication Data Distribution Protocol for Autonomous Distributed