Design and Evaluation of KTree for Reliable Routing in Peer-to-Peer Systems
2
조회
0
다운로드
4
인용
0
참고문헌
키워드
초록
This paper discusses the design and evaluation of KTree, a reliable constant degree distributed hash table (DHT) for distributed data storage and retrieval for peer-to-peer systems. KTree’s ability to route efficiently even when a large number of nodes are joining and/or leaving the system makes it an ideal choice for different sort of applications including data sharing. Each node in KTree has a unique node identifier belonging to an identifier space. In KTree, we partition the identifier space into levels and segments and fix the manager of every segment. A node in KTree maintains links with a constant number of nodes at the next level to forward queries. A node also creates a link with a node at the top level to get the global view of the system. This way KTree traverses a logarithmic number of nodes to route a query to its destination. An insert operation stores a key on a number of diverse nodes. The lookup operation, on the other hand, retrieves the stored data efficiently and reliably. A prototype implementation of KTree on PeerSim proves its reliability and efficiency. The experimental results achieved with a network of 50,000 nodes confirm its self-configurability and ability to route messages even under a high rate of churn.
Abstract
This paper discusses the design and evaluation of KTree, a reliable constant degree distributed hash table (DHT) for distributed data storage and retrieval for peer-to-peer systems. KTree’s ability to route efficiently even when a large number of nodes are joining and/or leaving the system makes it an ideal choice for different sort of applications including data sharing. Each node in KTree has a unique node identifier belonging to an identifier space. In KTree, we partition the identifier space into levels and segments and fix the manager of every segment. A node in KTree maintains links with a constant number of nodes at the next level to forward queries. A node also creates a link with a node at the top level to get the global view of the system. This way KTree traverses a logarithmic number of nodes to route a query to its destination. An insert operation stores a key on a number of diverse nodes. The lookup operation, on the other hand, retrieves the stored data efficiently and reliably. A prototype implementation of KTree on PeerSim proves its reliability and efficiency. The experimental results achieved with a network of 50,000 nodes confirm its self-configurability and ability to route messages even under a high rate of churn.
참고문헌 (16)
- A. Rowstron, "Pastry: scalable, decentralized object location and routing for large-scale peer-to-peer systems", Lecture Notes in Computer Science, 2218, pp.329~350 (2001)
- I. Stoica, "Chord: a scalable peerto- peer lookup service for internet applications", Computer Communication Review, 31(4), pp.149~160 (2001)
- S. Ratnasamy, "A scalable content addressable network", Computer Communication Review, 31(4), pp.161~172 (2001)
- F. Kaasheok, "Koorde: a simple degree-optimal distributed hash tables", Lecture Notes in Computer Science, 2735, pp.98~107 (2003)
- The content addressable network D2B, "P. Fraigniaud", Univ. Paris-Sud, ~, pp.Technical Report LRI 1349 (2003)
- A. Montresor, "PeerSim: a scalable P2P simulator", Proc. of the 9th Int. Conference on Peer-to-Peer (P2P’09), pp.99~100 (2009)
- A. Datta, "On de Bruijn routing in distributed hash tables: There and back again", proc. of 4th Int’l Conference on Peer-to-Peer Computing, pp.159~166 (2004)
- D. Malkhi, "Viceroy: a scalable and dynamic emulation of the butterfly", Proc. of the annual ACM Symposium on Principles of Distributed Computing, 21, pp.183~192 (2002)
- M.J. Freedman, "Efficient peer-to-peer lookup based on a distributed trie", Lecture Notes in Computer Science, 2429, pp.66~75 (2002)
- "On the fundamental tradeoffs between routing table size and network diameter in peer-topeer networks", IEEE journal on Selected Areas in Communication, 22(1), pp.151~163 (2004)
- M. Naor, "Novel architectures for P2P applications: the continuous-discrete approach", Proceedings of Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 2003, pp.50~59 (2003)
- D. Loguinov, "Graphtheoretic analysis of structured peer-to-peer systems: routing distances and fault resilience", Proceedings of 2003 Conference on Applications, Technologies, Architectures and Protocols for Computer Communications, pp.395~406 (2003)
- Maymounkov, P., "A Peer-to-Peer Information Systems Based on the XOR Metric", Proceedings of IPTPS 2002 (2002)
- 유정현, "Network Address Translator 모델들의 Hole punching 기술 지원에 관한 성능분석", 한국차세대컴퓨팅학회 논문지, 8(5), pp.40~49 (2012), 한국차세대컴퓨팅학회
- 송규원, "Classifying Behavior Patterns of User Nodes", 한국차세대컴퓨팅학회 논문지, 8(3), pp.15~26 (2012), 한국차세대컴퓨팅학회[DOI]
- 김하영, "TCP Overlay를 이용한 Throughput 향상", 한국차세대컴퓨팅학회 논문지, 5(2), pp.28~33 (2009), 한국차세대컴퓨팅학회