{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:51:12Z","timestamp":1750308672691,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2012,6,1]],"date-time":"2012-06-01T00:00:00Z","timestamp":1338508800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61133006 and 61190110","61170284, 60903206, 91024006, and 71031007"],"award-info":[{"award-number":["61133006 and 61190110","61170284, 60903206, 91024006, and 71031007"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002858","name":"China Postdoctoral Science Foundation","doi-asserted-by":"publisher","award":["201104439"],"award-info":[{"award-number":["201104439"]}],"id":[{"id":"10.13039\/501100002858","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002855","name":"Ministry of Science and Technology of the People's Republic of China","doi-asserted-by":"publisher","award":["2011AA010100"],"award-info":[{"award-number":["2011AA010100"]}],"id":[{"id":"10.13039\/501100002855","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Research Foundation of NUDT","award":["JC10-05-01"],"award-info":[{"award-number":["JC10-05-01"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Internet Technol."],"published-print":{"date-parts":[[2012,6]]},"abstract":"<jats:p>In order to improve scalability and to reduce the maintenance overhead for structured peer-to-peer (P2P) networks, researchers have proposed architectures based on several interconnection networks with a fixed-degree and a logarithmical diameter. Among existing fixed-degree interconnection networks, the Kautz digraph has many distinctive topological properties compared to others. It, however, requires that the number of peers have the some given values, determined by peer degree and network diameter. In practice, we cannot guarantee how many peers will join a P2P network at a given time, since a P2P network is typically dynamic with peers frequently entering and leaving. To address such an issue, we propose the balanced Kautz tree and Kautz ring structures. We further design a novel structured P2P system, called BAKE, based on the two structures that has the logarithmical diameter and constant degree, even the number of peers is an arbitrary value. By keeping a total ordering of peers and employing a robust locality-preserved resource placement strategy, resources that are similar in a single or multidimensional attributes space are stored on the same peer or neighboring peers. Through analysis and simulation, we show that BAKE achieves the optimal diameter and as good a connectivity as the Kautz digraph does (almost achieves the Moore bound), and supports the exact as well as the range queries efficiently. Indeed, the structures of balanced Kautz tree and Kautz ring we propose can also be applied to other interconnection networks after minimal modifications, for example, the de Bruijn digraph.<\/jats:p>","DOI":"10.1145\/2220352.2220355","type":"journal-article","created":{"date-parts":[[2012,7,13]],"date-time":"2012-07-13T23:07:36Z","timestamp":1342220856000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Theory and network applications of balanced kautz tree structures"],"prefix":"10.1145","volume":"12","author":[{"given":"Deke","family":"Guo","sequence":"first","affiliation":[{"name":"National University of Defense Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yunhao","family":"Liu","sequence":"additional","affiliation":[{"name":"Tsinghua University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hai","family":"Jin","sequence":"additional","affiliation":[{"name":"Huazhong University of Science and Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhong","family":"Liu","sequence":"additional","affiliation":[{"name":"National University of Defense Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weiming","family":"Zhang","sequence":"additional","affiliation":[{"name":"National University of Defense Technology, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hui","family":"Liu","sequence":"additional","affiliation":[{"name":"Xidian University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,7,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0140-3664(00)00336-4"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454167"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100048015"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1294261.1294281"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.256453"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/872035.872056"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.12.006"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1018440.1021946"},{"volume-title":"Proceedings of the 27th IEEE INFOCOM. IEEE","author":"Guo D.","key":"e_1_2_1_9_1","unstructured":"Guo , D. , Liu , Y. , and Li , X . 2008. BAKE: A balanced Kautz tree structure for peer-to-peer networks . In Proceedings of the 27th IEEE INFOCOM. IEEE , Los Alamitos, CA. Guo, D., Liu, Y., and Li, X. 2008. BAKE: A balanced Kautz tree structure for peer-to-peer networks. In Proceedings of the 27th IEEE INFOCOM. IEEE, Los Alamitos, CA."},{"volume-title":"Proceedings of the 26th IEEE INFOCOM. IEEE","author":"Guo D.","key":"e_1_2_1_10_1","unstructured":"Guo , D. , Wu , J. , Chen , H. , and Luo , X . 2007. Moore: An extendable peer-to-peer network based on incomplete Kautz digraph with constant degree . In Proceedings of the 26th IEEE INFOCOM. IEEE , Los Alamitos, CA, 821. Guo, D., Wu, J., Chen, H., and Luo, X. 2007. Moore: An extendable peer-to-peer network based on incomplete Kautz digraph with constant degree. In Proceedings of the 26th IEEE INFOCOM. IEEE, Los Alamitos, CA, 821."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2010.161"},{"volume-title":"Proceedings of the. 4th USENIX Symposium on Internet Technologies and Systems.","author":"Harvey N. J. A.","key":"e_1_2_1_12_1","unstructured":"Harvey , N. J. A. , Jones , M. B. , Saroiu , S. , Theimer , M. , and Wolman , A . 2003. Skipnet: A scalable overlay network with practical locality properties . In Proceedings of the. 4th USENIX Symposium on Internet Technologies and Systems. Harvey, N. J. A., Jones, M. B., Saroiu, S., Theimer, M., and Wolman, A. 2003. Skipnet: A scalable overlay network with practical locality properties. In Proceedings of the. 4th USENIX Symposium on Internet Technologies and Systems."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1981.1675809"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1983.1676323"},{"volume-title":"Proceedings of the International Peer-to-Peer Symposium. 98--107","author":"Kaashoek F.","key":"e_1_2_1_15_1","unstructured":"Kaashoek , F. and Karger , D . 2003. Koorde: A simple degreeoptimal distributed hash table . In Proceedings of the International Peer-to-Peer Symposium. 98--107 . Kaashoek, F. and Karger, D. 2003. Koorde: A simple degreeoptimal distributed hash table. In Proceedings of the International Peer-to-Peer Symposium. 98--107."},{"volume-title":"Proceedings of the 9th USENIX OSDI. 351--364","author":"Koponen T.","key":"e_1_2_1_16_1","unstructured":"Koponen , T. , Casado , M. , Gude , N. , Stribling , J. , Poutievski , L. , Zhu , M. , Ramanathan , R. , Iwata , Y. , Inoue , H. , Hama , T. , and Shenker , S . 2010. Onix: A distributed control platform for large-scale production networks . In Proceedings of the 9th USENIX OSDI. 351--364 . Koponen, T., Casado, M., Gude, N., Stribling, J., Poutievski, L., Zhu, M., Ramanathan, R., Iwata, Y., Inoue, H., Hama, T., and Shenker, S. 2010. Onix: A distributed control platform for large-scale production networks. In Proceedings of the 9th USENIX OSDI. 351--364."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1773912.1773922"},{"volume-title":"Proceedings of the IEEE INFOCOM, IEEE","author":"Li D.","key":"e_1_2_1_18_1","unstructured":"Li , D. , Lu , X. , and Wu , J . 2005. Fissione: A scalable constant degree and low congestion dht scheme based on Kautz graphs . In Proceedings of the IEEE INFOCOM, IEEE , Los Alamitos, CA, 1677--1688. Li, D., Lu, X., and Wu, J. 2005. Fissione: A scalable constant degree and low congestion dht scheme based on Kautz graphs. In Proceedings of the IEEE INFOCOM, IEEE, Los Alamitos, CA, 1677--1688."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2005.857072"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/571825.571857"},{"volume-title":"Proceedings of the International Peer-to-Peer Symposium. 53--65","author":"Maymounkov P.","key":"e_1_2_1_21_1","unstructured":"Maymounkov , P. and Mazieres , D . 2002. Kademlia: A peer-to-peer information system based on the XOR metric . In Proceedings of the International Peer-to-Peer Symposium. 53--65 . Maymounkov, P. and Mazieres, D. 2002. Kademlia: A peer-to-peer information system based on the XOR metric. In Proceedings of the International Peer-to-Peer Symposium. 53--65."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.37236\/1888"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/777412.777421"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.805162"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/383059.383072"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/383059.383072"},{"key":"e_1_2_1_27_1","series-title":"Lecture Notes in Computer Science","volume-title":"Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems","author":"Rowstron A.","year":"2001","unstructured":"Rowstron , A. and Druschel , P . 2001 . Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems . Lecture Notes in Computer Science , Vol. 2218 , Springer , Berlin , 329--350. Rowstron, A. and Druschel, P. 2001. Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems. Lecture Notes in Computer Science, Vol. 2218, Springer, Berlin, 329--350."},{"volume-title":"Proceedings of the 1th International Workshop on Agents and Peer-to-Peer Computing. 112--124","author":"Schlosser M. T.","key":"e_1_2_1_28_1","unstructured":"Schlosser , M. T. , Sintek , M. , Decker , S. , and Nejdl , W . 2002. Hypercup - hypercubes, ontologies, and efficient search on peer-to-peer networks . In Proceedings of the 1th International Workshop on Agents and Peer-to-Peer Computing. 112--124 . Schlosser, M. T., Sintek, M., Decker, S., and Nejdl, W. 2002. Hypercup - hypercubes, ontologies, and efficient search on peer-to-peer networks. In Proceedings of the 1th International Workshop on Agents and Peer-to-Peer Computing. 112--124."},{"volume-title":"Proceedings of. the 18th International Parallel and Distributed Processing Symposium.","author":"Shen H.","key":"e_1_2_1_29_1","unstructured":"Shen , H. , Xu , C. , and Chen , G . 2004. Cycloid: A constant-degree and lookup-efficient P2P overlay network . In Proceedings of. the 18th International Parallel and Distributed Processing Symposium. Shen, H., Xu, C., and Chen, G. 2004. Cycloid: A constant-degree and lookup-efficient P2P overlay network. In Proceedings of. the 18th International Parallel and Distributed Processing Symposium."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.282610"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2002.808407"},{"volume-title":"Partial Kautz line digraphs with maximal connectivity. Tech. rep. 94-15","author":"Tvrdik P.","key":"e_1_2_1_32_1","unstructured":"Tvrdik , P. 1994. Partial Kautz line digraphs with maximal connectivity. Tech. rep. 94-15 , LIP ENSL , Lyon, France . Tvrdik, P. 1994. Partial Kautz line digraphs with maximal connectivity. Tech. rep. 94-15, LIP ENSL, Lyon, France."},{"volume-title":"Topological Structure and Analysis of Interconnection Networks","author":"Xu J.","key":"e_1_2_1_33_1","unstructured":"Xu J. 2001. Topological Structure and Analysis of Interconnection Networks . Kluwer , Amsterdam . Xu J. 2001. Topological Structure and Analysis of Interconnection Networks. Kluwer, Amsterdam."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2003.818805"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/510726.510755"}],"container-title":["ACM Transactions on Internet Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2220352.2220355","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2220352.2220355","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:00:46Z","timestamp":1750276846000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2220352.2220355"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["10.1145\/2220352.2220355"],"URL":"https:\/\/doi.org\/10.1145\/2220352.2220355","relation":{},"ISSN":["1533-5399","1557-6051"],"issn-type":[{"type":"print","value":"1533-5399"},{"type":"electronic","value":"1557-6051"}],"subject":[],"published":{"date-parts":[[2012,6]]},"assertion":[{"value":"2011-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-07-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}