ID Z-Ordering 4) P2P P2P 2. Peer-to-Peer(P2P) P2P Gnutella ) BitTorrent 2) P2P (DHT:Distributed Hash Table) Chord 5) CAN(Content Adressable Network) 6

Size: px

Start display at page:

Download "ID Z-Ordering 4) P2P P2P 2. Peer-to-Peer(P2P) P2P Gnutella ) BitTorrent 2) P2P (DHT:Distributed Hash Table) Chord 5) CAN(Content Adressable Network) 6"

きよあつやなぎしま
8 years ago
Views:

1 Vol.29-DPS-39 No.3 29/6/8 P2P 2 P2P P2P P2P A configuration method for structured P2P overlay network considering delay variations Tomoya Kitani and Yoshitaka Nakamura 2 P2P networks can achieve high scalability since they distribute service contents/resources to multiple nodes in the network. In a P2P network, it is necessary to search the resource location on the network when we use some contents/resources. Generally, each part of contents is labeled and dispersed in the network, and it is managed by a distributed hash table (DHT). But search efficiency becomes worse in the limited region search of such service. In this paper, we propose a new configuration method for structured P2P overlay network. In the proposed method, we set each coordinate considering delay variation and achieve the efficient search of P2P network by mapping a coordinate onto space filling curve.. Peer-to-Peer (P2P) P2P Gnutella ) BitTorrent 2) P2P GPS(Global Positioning System) P2P LL-net 3) LL-net P2P Shizuoka University 2 Nara Institute of Science and Technology c 29 Information Processing Society of Japan

2 ID Z-Ordering 4) P2P P2P 2. Peer-to-Peer(P2P) P2P Gnutella ) BitTorrent 2) P2P (DHT:Distributed Hash Table) Chord 5) CAN(Content Adressable Network) 6) Pastry 7) Tapestry 8) P2P P2P % 9) ISP ISP Laptop ) LTM ) IP Mithos 2) DHT 3) Network Coordinates (NC) DAPS 4) DHT SkipNet 5) P2P DHT ID SkipGraph 6) SkipGraph LL-net 3) 4 P2P ID Mill 7) ID O(log N) Vol.29-DPS-39 No.3 29/6/8 ID 8) Z-Ordering 4) P2P Z 2 c 29 Information Processing Society of Japan

3 ID 2 P2P Vivaldi 9) P2P ID Vivaldi 3. 2 ID P2P P2P () P2P ID (2) (3) P2P ID 2 ID Z-Ordering 2 H-indexing βω-indexing Lebesgue Curve (Z-Ordering) 2 Hilbert Curve βω-indexing ID P2P ID 2 ID HCRN Hierarchical Chordal Ring Network 2) 2 Vol.29-DPS-39 No.3 29/6/8 HCRN 2 4 ID 2 3 c 29 Information Processing Society of Japan

4 Vol.29-DPS-39 No.3 29/6/8 3 Hierarchical Chordal Ring Network (N = 62) 4 (a) 階層的なコードの設定リング上のリンクコード (b) 木構造のルーティング A cluster of HCRN n 2 b g b = g (g >> ) g = b (b >> ) (x, y), x = x n x n 2 x x, y = y n y n 2 y y 2 b xy = x n y n x n 2 y n 2 x y x y g xy 2 HCRN ID 5 Proposed curve 6 The links of the lowest level in the proposed curve ID ID 3.2 Vivaldi ID P2P LL-net P2P km km 4 c 29 Information Processing Society of Japan

ID ID 3.2. Vivaldi 9) ID 3.2.2 Vivaldi Vivaldi GPS 7 Vivaldi Vivaldi ID P2P 4.

5 ID ID 3.2. Vivaldi 9) ID Vivaldi Vivaldi GPS 7 Vivaldi Vivaldi ID P2P 4. ID N Nodes = {n i }(i = {, 2,, N}) n i x i = (x i, y i ) n i, n j d ij D = {d ij } n i p i = (p i, q i ) cost 2 E minimize Σ i,j (d ij p i p j ) 2 (a) 8 7 i F i j u(i, j) t While (cost cost prev) < ϵ foreach i Node F := ; foreach j Node e := d ij n i n j ; F := F + e u(i, j); end; p i := p i + t F end; end. Vivald Vivald (b) P2P Vol.29-DPS-39 No.3 29/6/8 P2P P2P ID 5 c 29 Information Processing Society of Japan

6 Vivaldi P2P ) : Gnutella. 2) : BitTorrent. 3) P2P : Vol.46, No.SIG8 (TOD28), pp. 5 (25). 4) Orenstein, J. and Merrett, T.: A class of data structures for associative searching, Proceedings of the 3rd ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, pp.8 9 (984). 5) Stoica, I., Morris, R., Karger, D., Kaashoek, M.F. and Balakrishnan, H.: Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications, Proceedings of the ACM SIGCOMM 2, pp.49 6 (2). 6) Ratnasamy, S., Francis, P., Handley, M., Karp, R. and Schenker, S.: A scalable content-addressable network, Proceedings of the ACM SIGCOMM 2, pp.6 72 (2). 7) Rowstron, A. I.T. and Druschel, P.: Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg (Middleware 2), Springer-Verlag LNCS 228, pp (2). 8) Zhao, B.Y., Kubiatowicz, J. and Joseph, A.D.: Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and Routing, Technical report, Computer Science Division, University of California at Berkeley (2). 9) Han, J., Watson, D. and Jahanian, F.: Topology Aware Overlay Networks, Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE INFOCOM 25), Vol.4, pp (25). ) Wu, C.-J., Liu, D.-K. and Hwang, R.-H.: A location-aware peer-to-peer overlay network, International Journal of Communication Systems, Vol.2, No., pp.83 2 (27). Vol.29-DPS-39 No.3 29/6/8 ) Liu, Y., Liu, X., Xiao, L., Ni, L. M. and Zhang, X.: Location-Aware Topology Matching in P2P Systems, Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies(IEEE INFOCOM 24), Vol.4, pp (24). 2) Waldvogel, M. and Rinaldi, R.: Efficient Topology-Aware Overlay Network, ACM SIGCOMM Computer Communication Review, Vol.33, No., pp. 6 (23). 3) Pietzuch, P., Ledlie, J., Mitzenmacher, M. and Seltzer, M.: Network-Aware Overlays with Network Coordinates, Proceedings of the 26th IEEE International Conference on Distributed Computing Systems (ICDCS 26), p.2 (26). 4) Zhang, D. and Lin, C.: Efficient Delay Aware Peer-to-Peer Overlay Network, Proceedings of the 6th International Conference on Web-Age Information Management (WAIM 25), Springer-Verlag LNCS 3739, pp (25). 5) Harvey, N. J.A., Jones, M.B., Saroiu, S., Theimer, M. and Wolman, A.: SkipNet: A Scalable Overlay Network with Practical Locality Properties, Proceedings of the 4th USENIX Symposium on Internet Technologies and Systems (USITS 3), pp (23). 6) Aspnes, J. and Shah, G.: Skip graphs, Proceedings of the 4th annual ACM-SIAM Symposium on Discrete Algorithms (SODA 3), pp (23). 7) Matsuura, S., Fujikawa, K. and Sunahara, H.: Mill: A Geographical Location Oriented Overlay Network Managing data of Ubiquitous Sensors, IEICE TRANSAC- TIONS on Communications, Vol.E9-B, No., pp (27). 8) Wierum, J.-M.: Logarithmic Path-Length in Space-Filling Curves, Proceedings of the 4th Canadian Conference on Computational Geometry, pp (22). 9) Dabek, F., Cox, R. and Morris, R.: Vivaldi: A Decentralized Network Coordinate System, Proceedings of the ACM SIGCOMM 24, pp.5 26 (24). 2) Kitani, T., Funabiki, N., Yamaguchi, H. and Higashino, T.: Hierarchical Logical Topology in WDM Ring Networks with Limited ADM, Proceedings of the IFIP Networking 28 (Networking 28), Springer-Verlag LNCS 4982, pp (28). 6 c 29 Information Processing Society of Japan

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

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 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: