Evaluate the performance of some distributed hash table algorithms DHT and propose solutions to improve the performance of the CHORD algorithm

MINISTRY OF EDUCATION AND TRAINING HANOI UNIVERSITY OF SCIENCE AND TECHNOLOGY

---------------------------------------

MASTER OF SCIENCE THESIS

INDUSTRY: INFORMATION TECHNOLOGY

PERFORMANCE EVALUATION OF SOME DISTRIBUTED HASH TABLES DHT AND PROVIDE SOLUTIONS

PERFORMANCE IMPROVEMENT METHODS OF CHORD ALGORITHM

NGO HOANG GIANG

Scientific supervisor: Dr. NGUYEN CHAN HUNG

HANOI 2008

MINISTRY OF EDUCATION AND TRAINING HANOI UNIVERSITY OF SCIENCE AND TECHNOLOGY

***

Socialist Republic of Vietnam

Independence – Freedom – Happiness

COMMITMENT

This master's thesis was researched and carried out by me under the guidance of Professor Dr. Nguyen Chan Hung. To complete this thesis, in addition to the listed references, I guarantee not to copy other people's graduation works or designs.

Hanoi, October 28, 2008 (Signed and full name)

Ngo Hoang Giang

ACKNOWLEDGEMENTS

First of all, I am extremely grateful to Professor Dr. Nguyen Chan Hung - who directly spent a lot of time to guide and provide valuable information to help me complete this thesis.

I would like to sincerely thank the Board of Directors of the Information Network Center - Hanoi University of Science and Technology, where I am working, for creating many conditions to encourage and motivate me to complete this thesis.

Finally, I would like to express my gratitude to my relatives, friends and colleagues who have always encouraged me to complete this thesis.

Hanoi, October 28, 2008

Ngo Hoang Giang

Index

U COMMITMENT U 1

U THANK YOU 2

U Table of Contents U 3

U Glossary U 5

U Drawing Catalog U 6

U Algorithm Catalog U 8

U Table Category U 9

U Foreword U 10

U Chapter 1. UU General Theory U 11

U 1.1. UU General theory of P2P networks U 11

U 1.1.1. UU P2P Network Concept U 11

U 1.1.2. UU The evolution of P2P systems U 12

1 U .1.3. UU U 16 p2p application

U 1.1.4. UU Problems with current p2p networks U 16

U 1.2. UU Theory of Distributed Hash Table (DHT) U 18

U 1.2.1. UU Hash Table U 18

U 1.2.2. UU Distributed Hash Table U 18

U 1.3. UU Introduces some DHT U 20

U 1.3.1. UU Chord U 21

U 1.3.2. UU Kademlia U 30

U 1.3.3. UU Tapestry U 33

U 1.3.4. UU Kelips U 38

U 1.4. UU Methods for evaluating and testing P2P networks U 40

U 1.4.1. UU Survey of overlay network simulation simulators U 41

U 1.4.2. UU P2PSim U 42

U Chapter 2. UU Performance evaluation of some DHTs U 43

U 2.1. UU Practical Problem U 43

U 2.2. UU Performance evaluation of some DHTs U 44

U 2.2.1. UU Objectives and theoretical basis U 44

U 2.2.2. UU Experimental process and performance evaluation method U 45

U 2.2.3. UU Determine the churn rate threshold for DHTs to work well U 47

U 2.2.4. UU Performance comparison of DHTs U 53

U 2.2.5. UU Evaluation of the influence of design parameters on the performance of DHTs U ..63

U Chapter 3. UU Performance Improvements of Chord U 68

U 3.1. UU Limitations of the Chord U 68 protocol

U 3.2. UU Chord U 68 Protocol Improvement Solution

U 3.3. UU Loop maintenance solution using lock mechanism U 69

U 3.3.1. UU Goal U 69

3 U .3.2. UU Working mechanism U 69

U 3.4. UU Proxy Caching Solution U 79

U 3.4.1. UU Target U 79

U 3.4.2. UU Working mechanism U 79

U 3.5. UU Improved Symmetric Cloning Solution U 87

U 3.5.1. UU Target U 87

U 3.5.2. UU Working mechanism U 87

U Conclusion U 92

U References U 93

Glossary

English

Vietnamese
Peer-to-peer	Peer-to-peer network
Peer	Peers in a peer-to-peer network
Node	A network device (a peer)
Item	A unit of data
Structured	Structured
Overlay	Networks built on other networks
Hash table	Hash table
Distributed hash table	Distributed hash table
Join	Join (peer-to-peer)
Leave	Leave (peer-to-peer)
Failure	Error
Churn rate	Number of peers leaving/joining the network in a period of time

Maybe you are interested!

List of drawings

U Figure 1.1. Centralized directory model U 13

U Figure 1.2. Flooding request model U 14

U Figure 1.3. Distributed Hash Table U 20

U Figure 1.4. (a) A Chord network with 6 nodes, 5 items and N=16. (b) General principle of the routing table. (c) Routing table of node 3 and node 11 U 23

U Figure 1.5. The process of a node joining the network U 28

U Figure 1.6. (a) Finger table and key position after node 6 joins. (b) Finger table and key position after node 3 leaves. U 29

U Figure 1.7.Pointer of node 3 (0011) in Kademlia U 31

U Figure 1.8. Illustration of how to select the routing table of a Tapestry node U 34

U Figure 1.9. Message path from node 5230 to node 42AD U 36

U Figure 1.10. Example of Tapestry node publish item U 37

U Figure 1.11. Example of Tapestry node searching for item U 37

U Figure 1.12. Kelips network in which nodes are distributed in 10 affinity groups and states

status at a particular node U 39

U Figure 2.1. Node join/leave with interval=600 s in 100 node Chord network U 46

U Figure 2.2. Algorithm flow chart of churn rate determination process U 48

U Figure 2.3. Graph showing the fraction of successful lookups versus the average live bandwidth used by a node in a 100-node (left) and 1000-node (right) Kademlia network. U 49

U Figure 2.4. Graph showing the search success rate versus the average bandwidth used by a node in a 100-node (left) and 1000-node (right) Chord network. U 50

U Figure 2.5. Graph showing the search success rate versus the average bandwidth used by a node in the 100-node (left) and 1000-node (right) Kelips networks. U 51

U Figure 2.6. Graph showing the search success rate versus the average bandwidth used by a node in a Tapestry network of 100 nodes (left) and 1000 nodes (right). U 52

U Figure 2.7. Graph showing the search success rate according to the average bandwidth used by a node in the Chord network with interval=5s (left) and interval=10s (right). U 55

U Figure 2.8. Graph showing the search success rate according to the average bandwidth used by a node of Kelisp and Tapestry with RTT=1s, 10s and node join/leave with interval=5s (left) and 10s (right). U 56

U Figure 2.9. Graph showing the search success rate according to the average bandwidth used by a node in a 1000-node Chord network with interval=120s (left) and interval=600s (right). U 59

U Figure 2.10. Impact of churn rate on search failure rate (top) and average search delay (bottom) in networks of different sizes. U 60

U Figure 2.11. Graph showing the search success rate (top) and average search delay (bottom) against the average bandwidth used by a node in networks of different sizes with nodes joining/leaving with interval=600s U 62

U Figure 2.12. The effect of the “base” parameter on the performance of Tapestry (left) and the “gossip interval” parameter on the performance of the Kelips network in a 1000-node network when nodes join/leave with interval=600s U 65

U Figure 2.13. Convex hull representation of successor stabilization interval (left) and finger stabilization interval (right) in a 1000-node Chord network when nodes join/leave with interval=600s U 66

U Figure 3.1. State transition diagram of Chord U 70 node

U Figure 3.2. Time diagram showing the process of a node successfully entering the network U ...71

U Figure 3.3. Time diagram showing the process of a node leaving the network U 74

U Figure 3.4. Architecture of proxy caching solution U 80

U Figure 3.5. Timeline diagram showing successful caching process U 81