Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

Published in: Peer-to-Peer Networking and Applications 1/2015

01-01-2015

Improving lookup reliability in Kad

Authors: Bingshuang Liu, Tao Wei, Chao Zhang, Jun Li, Jianyu Zhang

Published in: Peer-to-Peer Networking and Applications | Issue 1/2015

Login to get access
share
SHARE

Abstract

Kad is one of the most popular peer-to-peer (P2P) networks deployed on today’s Internet. It provides support for file-sharing applications such as eMule and aMule and serves millions of users. Its reliability impacts not only the availability of file-sharing services, but also the capability of supporting other Internet services. However, in today’s Kad network, its lookup operation’s success ratio is lower than 91 % and not suitable for critical applications. In this paper, we investigate why Kad lookup fails and propose several new solutions. We build a measurement system called Anthill to analyze Kad’s communication process quantitatively, and figure out that the causes of Kad’s lookup failures can be classified into four categories: packet loss, selective Denial of Service nodes, search sequence miss, and publish/search space miss. The first two are due to the environment changes, the third is caused by the detachment of routing operations and content operations in Kad, and the last one shows the limitations of the Kademlia DHT algorithm under Kad’s current configuration. Based on the analysis, we propose corresponding approaches for Kad, including packet-retransmission, neighborhood lookup, and β-adjusting. We have systematically measured the effectiveness and efficiency of these approaches, and then give several recommendations for adoption in different situations. The improved version of Kad can achieve a success ratio of 99.8 % for lookup operations, with only a moderate communication overhead, while its average lookup latency is reduced significantly to only about 1 second. Our work shows that, with proper configurations and improvements, Kad can work much better and is capable of supporting more Internet services.
Literature
4.
go back to reference Bryan DA, Lowekamp BB, Jennings C (2005) Sosimple: a serverless, standards-based, p2p sip communication system. In: Proceedings of the 1st international workshop on advanced architectures and algorithms for internet delivery and applications (AAA-IDEA). IEEE Computer Society, Washington, pp 42–49 Bryan DA, Lowekamp BB, Jennings C (2005) Sosimple: a serverless, standards-based, p2p sip communication system. In: Proceedings of the 1st international workshop on advanced architectures and algorithms for internet delivery and applications (AAA-IDEA). IEEE Computer Society, Washington, pp 42–49
5.
go back to reference Carra D, Biersack EW (2007) Building a reliable p2p system out of unreliable p2p clients: the case of kad. In: Proceedings of the 2007 ACM CoNEXT conference. ACM, New York, pp 28:1–28:12 Carra D, Biersack EW (2007) Building a reliable p2p system out of unreliable p2p clients: the case of kad. In: Proceedings of the 2007 ACM CoNEXT conference. ACM, New York, pp 28:1–28:12
6.
go back to reference Cholez T, Henard C, Chrisment I, Festor O, Doyen G, Khatoun R (2011) A first approach to detect suspicious peers in the kad p2p network. In: 2011 Conference on network and information systems security (SAR-SSI), pp 1–8 Cholez T, Henard C, Chrisment I, Festor O, Doyen G, Khatoun R (2011) A first approach to detect suspicious peers in the kad p2p network. In: 2011 Conference on network and information systems security (SAR-SSI), pp 1–8
7.
go back to reference Cohen B (2003) Incentives build robustness in bittorrent. In: First workshop on economics of peer-to-peer systems. Berkeley Cohen B (2003) Incentives build robustness in bittorrent. In: First workshop on economics of peer-to-peer systems. Berkeley
8.
go back to reference Dabek F, Li J, Sit E, Robertson J, Kaashoek MF, Morris R (2004) Designing a dht for low latency and high throughput. In: Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation (NSDI). USENIX Association, Berkeley, pp 1–14 Dabek F, Li J, Sit E, Robertson J, Kaashoek MF, Morris R (2004) Designing a dht for low latency and high throughput. In: Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation (NSDI). USENIX Association, Berkeley, pp 1–14
9.
go back to reference Freedman MJ, Freudenthal E, Mazières D (2004) Democratizing content publication with coral. In: Proceedings of the 1st conference on symposium on networked systems design and implementation (NSDI). USENIX Association, Berkeley, pp 18–18 Freedman MJ, Freudenthal E, Mazières D (2004) Democratizing content publication with coral. In: Proceedings of the 1st conference on symposium on networked systems design and implementation (NSDI). USENIX Association, Berkeley, pp 18–18
10.
go back to reference Kang H, Chan-Tin E, Hopper N, Kim Y (2009) Why kad lookup fails. In: Proceedings of IEEE 9th international conference on peer-to-peer computing (P2P). IEEE, pp 121–130 Kang H, Chan-Tin E, Hopper N, Kim Y (2009) Why kad lookup fails. In: Proceedings of IEEE 9th international conference on peer-to-peer computing (P2P). IEEE, pp 121–130
11.
go back to reference Li J, Stribling J, Morris R, Kaashoek M, Gil T (2005) A performance vs. cost framework for evaluating dht design tradeoffs under churn. In: Proceedings of IEEE 24th annual joint conference of the ieee computer and communications societies (INFOCOM), vol 1, pp 225–236 Li J, Stribling J, Morris R, Kaashoek M, Gil T (2005) A performance vs. cost framework for evaluating dht design tradeoffs under churn. In: Proceedings of IEEE 24th annual joint conference of the ieee computer and communications societies (INFOCOM), vol 1, pp 225–236
12.
go back to reference Liu B, Wei T, Zhang J, Li J, Zou W, Zhou M (2012) Revisiting why kad lookup fails. In: Proceedings of IEEE 12th international conference on peer-to-peer computing (P2P). IEEE, pp 37–42 Liu B, Wei T, Zhang J, Li J, Zou W, Zhou M (2012) Revisiting why kad lookup fails. In: Proceedings of IEEE 12th international conference on peer-to-peer computing (P2P). IEEE, pp 37–42
13.
go back to reference Lopez PG, Artigas MS, Ahull JP (2007) The p2pweb model: A glue for the web. In: Proceedings of the 16th IEEE international workshops on enabling technologies: infrastructure for collaborative enterprises (WETICE). IEEE Computer Society, Washington, pp 153–158 Lopez PG, Artigas MS, Ahull JP (2007) The p2pweb model: A glue for the web. In: Proceedings of the 16th IEEE international workshops on enabling technologies: infrastructure for collaborative enterprises (WETICE). IEEE Computer Society, Washington, pp 153–158
14.
go back to reference Maymounkov P, Mazières D (2002) Kademlia: a peer-to-peer information system based on the xor metric. In: Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS). Springer-Verlag, London, pp 53–65 CrossRef Maymounkov P, Mazières D (2002) Kademlia: a peer-to-peer information system based on the xor metric. In: Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS). Springer-Verlag, London, pp 53–65 CrossRef
15.
go back to reference Mol JJD, Pouwelse JA, Epema DHJ, Sips HJ (2008) Free-riding, fairness, and firewalls in p2p file-sharing. In: Proceedings of the 8th International conference on peer-to-peer computing (P2P). IEEE Computer Society, Washington, pp 301–310 Mol JJD, Pouwelse JA, Epema DHJ, Sips HJ (2008) Free-riding, fairness, and firewalls in p2p file-sharing. In: Proceedings of the 8th International conference on peer-to-peer computing (P2P). IEEE Computer Society, Washington, pp 301–310
16.
go back to reference Nakamoto S (2008) Bitcoin: A peer-to-peer electronic cash system Nakamoto S (2008) Bitcoin: A peer-to-peer electronic cash system
17.
go back to reference Ramasubramanian V, Sirer EG (2004) Beehive: O(1)lookup performance for power-law query distributions in peer-to-peer overlays. In: Proceedings of the 1st conference on symposium on networked systems design and implementation (NSDI). USENIX Association, Berkeley, pp 1–14 Ramasubramanian V, Sirer EG (2004) Beehive: O(1)lookup performance for power-law query distributions in peer-to-peer overlays. In: Proceedings of the 1st conference on symposium on networked systems design and implementation (NSDI). USENIX Association, Berkeley, pp 1–14
18.
go back to reference Ramasubramanian V, Sirer EG (2004) The design and implementation of a next generation name service for the internet. SIGCOMM Comput Commun Rev 34(4):331–342 CrossRef Ramasubramanian V, Sirer EG (2004) The design and implementation of a next generation name service for the internet. SIGCOMM Comput Commun Rev 34(4):331–342 CrossRef
19.
go back to reference Ratnasamy S, Stoica I, Shenker S (2002) Routing algorithms for dhts: some open questions. In: Proceedings of the 1st international workshop on peer-to-peer systems (IPTPS), IPTPS ’01. Springer-Verlag, London, pp 45–52 Ratnasamy S, Stoica I, Shenker S (2002) Routing algorithms for dhts: some open questions. In: Proceedings of the 1st international workshop on peer-to-peer systems (IPTPS), IPTPS ’01. Springer-Verlag, London, pp 45–52
20.
go back to reference Rhea S, Geels D, Roscoe T, Kubiatowicz J (2004) Handling churn in a dht. In: Proceedings of the annual conference on USENIX annual technical conference (ATEC), ATEC ’04. USENIX Association, Berkeley, pp 1–14 Rhea S, Geels D, Roscoe T, Kubiatowicz J (2004) Handling churn in a dht. In: Proceedings of the annual conference on USENIX annual technical conference (ATEC), ATEC ’04. USENIX Association, Berkeley, pp 1–14
21.
go back to reference Risson J, Moors T (2006) Survey of research towards robust peer-to-peer networks: search methods. Comput Netw 50(17):3485–3521 CrossRefMATH Risson J, Moors T (2006) Survey of research towards robust peer-to-peer networks: search methods. Comput Netw 50(17):3485–3521 CrossRefMATH
22.
go back to reference Steiner M, Biersack EW, Ennajjary T (2007) Actively monitoring peers in kad. In: Proceedings of the 6th international workshop on peer-to-peer systems (IPTPS). Bellevue Steiner M, Biersack EW, Ennajjary T (2007) Actively monitoring peers in kad. In: Proceedings of the 6th international workshop on peer-to-peer systems (IPTPS). Bellevue
23.
go back to reference Steiner M, Carra D, Biersack EW (2008) Faster content access in kad. In: Proceedings of the 8th international conference on peer-to-peer computing (P2P), P2P ’08. IEEE Computer Society, Washington, pp 195–204 Steiner M, Carra D, Biersack EW (2008) Faster content access in kad. In: Proceedings of the 8th international conference on peer-to-peer computing (P2P), P2P ’08. IEEE Computer Society, Washington, pp 195–204
24.
go back to reference Steiner M, En-Najjary T, Biersack EW (2007) A global view of kad. In: Proceedings of the 7th ACM SIGCOMM conference on internet measurement (IMC). ACM, New York, pp 117–122 Steiner M, En-Najjary T, Biersack EW (2007) A global view of kad. In: Proceedings of the 7th ACM SIGCOMM conference on internet measurement (IMC). ACM, New York, pp 117–122
25.
go back to reference Steiner M, En-Najjary T, Biersack EW (2009) Long term study of peer behavior in the kad dht. IEEE/ACM Trans Netw 17(5):1371–1384 CrossRef Steiner M, En-Najjary T, Biersack EW (2009) Long term study of peer behavior in the kad dht. IEEE/ACM Trans Netw 17(5):1371–1384 CrossRef
26.
go back to reference Stutzbach D, Rejaie R (2006) Improving lookup performance over a widely-deployed dht. In: Proceedings of the 25th IEEE international conference on computer communications (INFOCOM), pp. 1–12 Stutzbach D, Rejaie R (2006) Improving lookup performance over a widely-deployed dht. In: Proceedings of the 25th IEEE international conference on computer communications (INFOCOM), pp. 1–12
27.
go back to reference Stutzbach D, Rejaie R (2006) Understanding churn in peer-to-peer networks. In: Proceedings of the 6th ACM SIGCOMM conference on Internet measurement (IMC). ACM, New York, pp 189–202 Stutzbach D, Rejaie R (2006) Understanding churn in peer-to-peer networks. In: Proceedings of the 6th ACM SIGCOMM conference on Internet measurement (IMC). ACM, New York, pp 189–202
30.
go back to reference Yu J, Li Z (2009) Active measurement of routing table in kad. In: Proceedings of the 6th IEEE conference on consumer communications and networking conference (CCNC). IEEE Press, Piscataway, pp 1252–1256 Yu J, Li Z (2009) Active measurement of routing table in kad. In: Proceedings of the 6th IEEE conference on consumer communications and networking conference (CCNC). IEEE Press, Piscataway, pp 1252–1256
Metadata
Title
Improving lookup reliability in Kad
Authors
Bingshuang Liu
Tao Wei
Chao Zhang
Jun Li
Jianyu Zhang
Publication date
01-01-2015
Publisher
Springer US
Published in
Peer-to-Peer Networking and Applications / Issue 1/2015
Print ISSN: 1936-6442
Electronic ISSN: 1936-6450
DOI
https://doi.org/10.1007/s12083-013-0240-4

Other articles of this Issue 1/2015

Peer-to-Peer Networking and Applications 1/2015 Go to the issue

Premium Partner