Psu: a novel low-latency constant-degree overlay network

Abstract

Many structured peer-to-peer (P2P) systems supported by distributed hash table (DHT) schemas have been proposed recently to improve the scalability of distributed virtual application systems. By organizing the peers based on interconnection topologies, existing proposed schemas are purely based on the logical relationship without knowledge of the physical networks. In this paper, we propose a new structured DHT schema, which receives routing information not just from virtual neighbors in P2P overlay network, but also from nearby physical neighbors. The average degree of our model is 5, the diameter is logarithmic. The simulation shows that our model achieves shorter query path length, higher clustering, and better robustness than other overlay networks which have the same level of degree and diameter.

Keywords

overlay network / Cayley graph / physical approximation / semi-direct product / peer server

References

[1] Stoica I, Morris R, Karger D, Kaashoek M F, Balakrishnan H. Chord: a scalable peer-to-peer lookup service for internet applications. In: Proceedings of 2001 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication. 2001, 149–160

[2] Kumar A, Merugu S, Xu J, Zegura E W, Yu X. Ulysses: a robust, low-diameter, low-latency peer-topeer network. European Transactions on Telecommunications, 2004, 15(6): 571–587

[3] Ratnasamy S, Francis P, Handley M, Karp R, Schenker S. A scalable content-addressable network. In: Proceedings of 2001 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications. 2001, 161–172

[4] Li D, Lu X, Wu J. FISSIONE: a scalable constant degree and low congestion DHT scheme based on Kautz graphs. In: Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communications Societies. 2005

[5] Xiao W, Parhami B. Cayley graphs as models of deterministic small-world networks. Information Processing Letters, 2006, 97(3): 115–117

[6] Naor M, Malkhi D, Ratajczak D. Viceroy: a scalable and dynamic emulation of the butterfly. In: Proceedings of 21st Annual Symposium on Principles of Distributed Computing. 2002, 183–192

[7] Shen H, Xu C Z, Chen G. Cycloid: a constant-degree and lookup-efficient P2P overlay network. Performance Evaluation, 2006, 63(3): 195–216

[8] Kaashoek M F, Karger D R. Koorde: a simple degree-optimal distributed hash table. In: Proceedings of 2nd International Workshop on Peer-to-Peer Systems. 2003, 98–107

[9] Fraigniaud P, Gauron P. D2b: a de bruijn based content-addressable network. Theoretical Computer Science, 2006, 355(1): 65–79

[10] Naor M, Wieder U. Novel architectures for P2P applications: the continuous-discrete approach. ACM Transactions on Algorithms, 2007, 3(3): 50–59

[11] Xiao W, He M, Wei W, Cayleychord: a novel P2P overlay network. In: Proceedings of 2008 IEEE/IPIP International Conference on Embedded and Ubiquitous Computing. 2008, 501–506

[12] Xiao W, Wei W. Ebu: a novel P2P overlay network. In: Proceedings of 1st International Conference on Intelligent Networks and Intelligent Systems. 2008, 178–182

[13] Sun Z, Xiao W. Comnet: a P2P community network. In: Proceedings of 7th International Symposium on Advanced Parallel Processing Technologies. 2007, 271–281

[14] Biggs N. Algebraic Graph Theory. New York: Cambridge University Press, 1993

[15] Wu C H, Hu S Y, Tseng L M. Discovery of physical neighbors for P2P 3D streaming. In: Proceedings of 2009 International Conference on Ultra Modern Telecommunications. 2009

[16] Hsieh M Y, Yang H C, Tseng L M. Finding nearest neighbors in replication-aware CDN-P2P architecture. Journal of Internet Technology, 2005, 6(2): 133–142

[17] Miura H, Yamamoto M. Content routing with network support using passive measurement in content distribution networks. IEICE Transactions on Communications, 2003, E86-B (6): 1805–1811

Acknowledgements

We would like to thank the reviewers for the corrections and suggestions presented in their comments. This Work was supported by the National Natural Science Foundation of China (Grant No. 60973150) and Guangdong Laboratory of Software and Applied Technology (2006B80407001).

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg