DHT覆盖网若干基础性问题研究
|
摘要
分布式哈希表(DHT)是一种新的P2P网络组网方式，具有高效、易扩展、低成本等优点，广泛应用于各种大规模分布式系统，如文件共享、内容分发、流媒体、VoIP等。在这些系统中，由DHT形成的覆盖网扮演着重要角色，支撑着上层各种应用。因此，它引起了研究人员的广泛关注，已成为当前的研究热点。
论文对DHT覆盖网在应用中亟待解决的一些基础性问题进行了深入的研究，从分析DHT网络的基本模型入手，研究了DHT网络的管理范围(Zone)均衡问题，深入探讨了如何在DHT网络中防御Sybil攻击，并对网络规模估计问题进行了建模分析，提出了高效的随机节点选择算法。
论文的创新点及其贡献在于：
1．研究了线段随机分割问题，得出两个基本结论：在Chord网络中，节点间距近似服从指数分布，一段地址空间上出现的节点个数近似服从泊松分布。理论分析和仿真数据表明，这两个结论的近似程度非常高，误差很小。这两个结论不仅适用于Chord网络，还适用于所有满足节点ID在网络中均匀分布假设的DHT网络。它们是全文分析与建模工作的基础。
2．提出基于静态副本Zone均衡策略，推导出Chord和Pastry网络、虚拟服务器(VS)和基于静态副本的Zone均衡策略下节点的负载分布。分析表明：Chord、Pastry和VS的Zone负载分布服从参数形式相似的伽马分布；在Chord网络中k个后继节点上放置副本，节点Zone负载服从参数为(k，n)的伽马分布。与VS和基于平衡树的Zone均衡策略相比，基于静态副本的均衡策略除了使节点Zone负载均衡外，还具有使系统更鲁棒的优势。
3．提出一种ID自检验的安全框架(ISV)，并结合洗牌策略高效抵御Sybil攻击(ICS)。ISV引入显式证书分发服务器(CD)对ID申请进行审计，分发节点签名；而身份验证工作由节点根据签名自行完成；有效降低了CD服务器的开销。ICS利用CD签发的票据记录节点加入过程，保证三轮替换规则强制实施；利用票据的替换区间和发布时戳来判定ID是否过期，防止敌手积累ID。论文对节点需要保存的票据数量进行了定量分析，得出问题的近似闭合解；理论分析表明平均每个节点上保存的票据数是O(log~2n)；仿真数据表明，该近似解具有很高的精度，说明了理论分析的正确性。
4．指出在DHT网络中估计网络规模等同于指数分布或泊松分布的参数估计问题，提出基于平均间距(AIE)和基于节点密度(NDE)两种网络规模估计算法。论文推导出AIE和NDE算法中网络规模估计值的概率分布，讨论了如何选择NDE测量范围和测量位置等问题。分析表明：AIE的测量精度只与测量间距个数相关，与网络规模本身无关，具有自适应网络规模变化的特点。仿真实验证明AIE算法的测量误差完全符合理论分析结果。
5．提出一种基于取舍原则的DHT网络随机节点抽样算法(RPS)，分析了单点启发式算法(HUR)和多点启发式算法(HURk)的抽样概率以及抽样间距的概率分布，构造了一种服从倒数分布的取舍算法(RDRP)。分析表明：RPS以等概率抽样在线节点，抽样间距服从指数分布；RPS的时间复杂度与网络规模无关，其复杂度不随网络规模的增加而增加；网络规模估计误差给RPS造成的影响与网络规模本身无关；当网络规模估计值偏小时，会在一定程度上削弱RPS的随机性。论文采用统计检验和经验检验两类方法对相关分析做出了严格检验，结果表明RPS对于网络规模估计误差具有很好的容忍性，同时也证实RPS是一种高效的随机节点抽样算法。
Distributed hash table (DHT) is a new Peer-to-Peer (P2P) networking pattern,which has many advantages, such as efficiency, scalability and low cost, and has beenwidely deployed in various large-scaled distributed systems, ranging from file sharing,contents distribution, streaming media to VoIP. In such systems, the overlay formed withDHT plays an important role in supporting the upper layer applications. As a result, ithas drawn the attention of many researchers, and becomes the current research hotspot.
This dissertation mainly focuses on some fundamental problems to be solved in theapplication of DHT. Starting from analyzing the basic model of DHT network, thedissertation investigates the zone balance in DHT overlay, explores how to resist theSybil attacks deeply, models the problem of estimating network size, and proposes anefficient random nodes sampling algorithm of DHT overlay.
The major contributions of this dissertation are as below:
1. The dissertation investigates the problem of dividing a line randomly, anddeduces two basic conclusions: in Chord network, the interval between nodes obeys theexponential distribution asymptotically, and the number of nodes appearing in a sectionof address space obeys the Poisson distribution asymptotically. The analysis andsimulation shows that the asymptotic accuracy of these two basic conclusions is veryhigh, and the error is very little. The conclusions are applicable not only to Chord, butalso to other types of DHT which satisfies the assumed condition that the identifiers aredistributed uniformly in the address space. They are the basis of analysis and modelingof the total dissertation.
2. The dissertation proposes the zone balancing scheme based on static replica, anddeduces the zone load distribution of nodes in Chord and Pastry network, the virtualservers (VS) and the static-replica-based balancing scheme. The analysis shows that thezone load distribution of Chord, Pastry and VS obeys the Gamma distribution withsimilar type of parameters, and if putting replica on k succeeding nodes in Chord, thezone load distribution obeys the Gamma distribution with parameter (k, n). Compared with VS and the trie-based zone balancing scheme, the static-replica-based scheme cannot only achieve the balance of zone load, but also make the system robuster.
3. The dissertation presents an identity self-verified secure framework (ISV), whichis combined with Cards-shuffling scheme (ICS) to resist Sybil attacks efficiently. Anexplicit certificate distributor (CD) is introduced into ISV to audit the requiring for newidentifiers, and distribute signatures to nodes, whereas the verifying of identity iscarried out by nodes themselves, which reduces the overhead of CD server greatly. ICSmakes use of the tickets signed by CD to record the joining process of nodes toguarantee the compulsive execution of k-rotation rule. To prevent the enemy fromaccumulating identifiers, ICS utilizes the substituting sections and publish timestampsto determine whether the identifier is overdue. The dissertation analyzes quantitativelythe number of tickets stored on the nodes, and gives the asymptotic closed-formsolution of the problem. The analysis shows that the average number of tickets stored oneach node is O(log~2 n), and the simulation demonstrates that the asymptotic solution isvery accurate, which illustrating the correctness of the analysis.
4. The dissertation claims that the problem to estimate the network size is identicalto the parameter estimation of the exponential or Poisson distribution in DHT, andproposes the average-interval-based estimator (AIE) and the node-density-basedestimator (NDE). The dissertation deduces the probabilistic distribution of the networksize estimation in AIE and NDE, and discusses how to select the testing scope andposition of NDE. The analysis shows that the estimating accuracy of AIE is only relatedto the number of intervals measured, and is irrelevant to the network size. This showsthat AIE can adapt the variation of network size. The simulation proves that the measureerror is in line with the theoretical analysis entirely.
5. The dissertation proposes a random node sampling scheme based on rejectionprinciple (RPS). The probabilistic distributions of the sampled probability and sampledinterval are analyzed against the single point heuristic sampling algorithm (HUR) andthe multi-points heuristic sampling algorithm (HURk). And a rejection algorithmobeying the reciprocal distribution (RDRP) is constructed. The analysis shows that RPSsamples online nodes with equal probability and the interval between nodes sampledobeys the exponential distribution; its complexity remains constant while the networksize increases; the impact of estimating error of network size on RPS is irrelevant to the network size itself; if the estimation is less than accurate network size, RPS will loserandomness to a certain degree. Finally, the dissertation utilizes the statistical testingand empirical testing methods to verify the analysis strictly. The result shows that RPSis tolerant to the estimating error of network size very much. This proves that RPS is anefficient sampling algorithm.
论文对DHT覆盖网在应用中亟待解决的一些基础性问题进行了深入的研究，从分析DHT网络的基本模型入手，研究了DHT网络的管理范围(Zone)均衡问题，深入探讨了如何在DHT网络中防御Sybil攻击，并对网络规模估计问题进行了建模分析，提出了高效的随机节点选择算法。
论文的创新点及其贡献在于：
1．研究了线段随机分割问题，得出两个基本结论：在Chord网络中，节点间距近似服从指数分布，一段地址空间上出现的节点个数近似服从泊松分布。理论分析和仿真数据表明，这两个结论的近似程度非常高，误差很小。这两个结论不仅适用于Chord网络，还适用于所有满足节点ID在网络中均匀分布假设的DHT网络。它们是全文分析与建模工作的基础。
2．提出基于静态副本Zone均衡策略，推导出Chord和Pastry网络、虚拟服务器(VS)和基于静态副本的Zone均衡策略下节点的负载分布。分析表明：Chord、Pastry和VS的Zone负载分布服从参数形式相似的伽马分布；在Chord网络中k个后继节点上放置副本，节点Zone负载服从参数为(k，n)的伽马分布。与VS和基于平衡树的Zone均衡策略相比，基于静态副本的均衡策略除了使节点Zone负载均衡外，还具有使系统更鲁棒的优势。
3．提出一种ID自检验的安全框架(ISV)，并结合洗牌策略高效抵御Sybil攻击(ICS)。ISV引入显式证书分发服务器(CD)对ID申请进行审计，分发节点签名；而身份验证工作由节点根据签名自行完成；有效降低了CD服务器的开销。ICS利用CD签发的票据记录节点加入过程，保证三轮替换规则强制实施；利用票据的替换区间和发布时戳来判定ID是否过期，防止敌手积累ID。论文对节点需要保存的票据数量进行了定量分析，得出问题的近似闭合解；理论分析表明平均每个节点上保存的票据数是O(log~2n)；仿真数据表明，该近似解具有很高的精度，说明了理论分析的正确性。
4．指出在DHT网络中估计网络规模等同于指数分布或泊松分布的参数估计问题，提出基于平均间距(AIE)和基于节点密度(NDE)两种网络规模估计算法。论文推导出AIE和NDE算法中网络规模估计值的概率分布，讨论了如何选择NDE测量范围和测量位置等问题。分析表明：AIE的测量精度只与测量间距个数相关，与网络规模本身无关，具有自适应网络规模变化的特点。仿真实验证明AIE算法的测量误差完全符合理论分析结果。
5．提出一种基于取舍原则的DHT网络随机节点抽样算法(RPS)，分析了单点启发式算法(HUR)和多点启发式算法(HURk)的抽样概率以及抽样间距的概率分布，构造了一种服从倒数分布的取舍算法(RDRP)。分析表明：RPS以等概率抽样在线节点，抽样间距服从指数分布；RPS的时间复杂度与网络规模无关，其复杂度不随网络规模的增加而增加；网络规模估计误差给RPS造成的影响与网络规模本身无关；当网络规模估计值偏小时，会在一定程度上削弱RPS的随机性。论文采用统计检验和经验检验两类方法对相关分析做出了严格检验，结果表明RPS对于网络规模估计误差具有很好的容忍性，同时也证实RPS是一种高效的随机节点抽样算法。
Distributed hash table (DHT) is a new Peer-to-Peer (P2P) networking pattern,which has many advantages, such as efficiency, scalability and low cost, and has beenwidely deployed in various large-scaled distributed systems, ranging from file sharing,contents distribution, streaming media to VoIP. In such systems, the overlay formed withDHT plays an important role in supporting the upper layer applications. As a result, ithas drawn the attention of many researchers, and becomes the current research hotspot.
This dissertation mainly focuses on some fundamental problems to be solved in theapplication of DHT. Starting from analyzing the basic model of DHT network, thedissertation investigates the zone balance in DHT overlay, explores how to resist theSybil attacks deeply, models the problem of estimating network size, and proposes anefficient random nodes sampling algorithm of DHT overlay.
The major contributions of this dissertation are as below:
1. The dissertation investigates the problem of dividing a line randomly, anddeduces two basic conclusions: in Chord network, the interval between nodes obeys theexponential distribution asymptotically, and the number of nodes appearing in a sectionof address space obeys the Poisson distribution asymptotically. The analysis andsimulation shows that the asymptotic accuracy of these two basic conclusions is veryhigh, and the error is very little. The conclusions are applicable not only to Chord, butalso to other types of DHT which satisfies the assumed condition that the identifiers aredistributed uniformly in the address space. They are the basis of analysis and modelingof the total dissertation.
2. The dissertation proposes the zone balancing scheme based on static replica, anddeduces the zone load distribution of nodes in Chord and Pastry network, the virtualservers (VS) and the static-replica-based balancing scheme. The analysis shows that thezone load distribution of Chord, Pastry and VS obeys the Gamma distribution withsimilar type of parameters, and if putting replica on k succeeding nodes in Chord, thezone load distribution obeys the Gamma distribution with parameter (k, n). Compared with VS and the trie-based zone balancing scheme, the static-replica-based scheme cannot only achieve the balance of zone load, but also make the system robuster.
3. The dissertation presents an identity self-verified secure framework (ISV), whichis combined with Cards-shuffling scheme (ICS) to resist Sybil attacks efficiently. Anexplicit certificate distributor (CD) is introduced into ISV to audit the requiring for newidentifiers, and distribute signatures to nodes, whereas the verifying of identity iscarried out by nodes themselves, which reduces the overhead of CD server greatly. ICSmakes use of the tickets signed by CD to record the joining process of nodes toguarantee the compulsive execution of k-rotation rule. To prevent the enemy fromaccumulating identifiers, ICS utilizes the substituting sections and publish timestampsto determine whether the identifier is overdue. The dissertation analyzes quantitativelythe number of tickets stored on the nodes, and gives the asymptotic closed-formsolution of the problem. The analysis shows that the average number of tickets stored oneach node is O(log~2 n), and the simulation demonstrates that the asymptotic solution isvery accurate, which illustrating the correctness of the analysis.
4. The dissertation claims that the problem to estimate the network size is identicalto the parameter estimation of the exponential or Poisson distribution in DHT, andproposes the average-interval-based estimator (AIE) and the node-density-basedestimator (NDE). The dissertation deduces the probabilistic distribution of the networksize estimation in AIE and NDE, and discusses how to select the testing scope andposition of NDE. The analysis shows that the estimating accuracy of AIE is only relatedto the number of intervals measured, and is irrelevant to the network size. This showsthat AIE can adapt the variation of network size. The simulation proves that the measureerror is in line with the theoretical analysis entirely.
5. The dissertation proposes a random node sampling scheme based on rejectionprinciple (RPS). The probabilistic distributions of the sampled probability and sampledinterval are analyzed against the single point heuristic sampling algorithm (HUR) andthe multi-points heuristic sampling algorithm (HURk). And a rejection algorithmobeying the reciprocal distribution (RDRP) is constructed. The analysis shows that RPSsamples online nodes with equal probability and the interval between nodes sampledobeys the exponential distribution; its complexity remains constant while the networksize increases; the impact of estimating error of network size on RPS is irrelevant to the network size itself; if the estimation is less than accurate network size, RPS will loserandomness to a certain degree. Finally, the dissertation utilizes the statistical testingand empirical testing methods to verify the analysis strictly. The result shows that RPSis tolerant to the estimating error of network size very much. This proves that RPS is anefficient sampling algorithm.
引文
[1] INTERNET USAGE STATISTICS, in http://www.internetworldstats.com/stats.htm: Miniwatts Marketing Group., 2008.
[2] M. Ripeanu, I. Foster, A. Iamnitchi, Mapping the Gnutella Network: Properties of Large-Scale Peer-to-Peer Systems and Implications for System Design, IEEE INTERNET COMPUTING JOURNAL, vol. 6, p. 1, 2002.
[3] http://www.clip2.com, The Gnutella Protocol Specification v0.4: http://www9.limewire.com/developer/gnutella_protocol_0.4.pdf.
[4] I. Clarke, O. Sandberg, B. Wiley, T. W. Hong, Freenet: a distributed anonymous information storage and retrieval system, in International workshop on Designing privacy enhancing technologies: design issues in anonymity and unobservability table of contents, 2001, pp.46-66.
[5] Q. Lv, P. Cao, E. Cohen, K. Li, S. Shenker, Search and replication in unstructured peer-to-peer networks, in Proceedings of the 16th international conference on Supercomputing, 2002, pp. 84-95.
[6] Q. Lv, S. Ratnasamy, S. Shenker, Can heterogeneity make gnutella scalable, in Proceedings of the 1st International Workshop on Peer-to-Peer Systems (1PTPS'02), 2002.
[7] I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger, M. F. Kaashoek, F. Dabek, H. Balakrishnan, Chord: a scalable peer-to-peer lookup protocol for Internet applications, IEEE/ACM Transactions on Networking (TON), vol. 11, pp. 17-32, 2003.
[8] S. Ratnasamy, P. Francis, M. Handley, R. Karp, S. Schenker, A scalable content-addressable network, in Proceedings of the 2001 SIGCOMM conference, 2001, pp. 161-172.
[9] A. Rowstron, P. Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, in Proceedings of the 18th IFIP/ACM International Conference on Distributed Systems Platforms (Middleware), LNCS. vol. 2218, 2001, pp. 329-350.
[10] B. Y. Zhao, L. Huang, J. Stribling, S. C. Rhea, A. D. Joseph, J. D. Kubiatowicz, Tapestry: a resilient global-scale overlay for service deployment, IEEE Journals on Selected Areas in Communications, vol. 22, pp. 41-53, 2004.
[11] P. Maymounkov, D. Mazieres, 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'02), 2002, p. 263.
[12] I. H. Witten, A. Moffat, T. C. Bell, Managing Gigabytes: Compressing and Indexing Documents and Images, 1999: Morgan Kaufmann Publishers.
[13] P. Triantafillou, T. Pitoura, Towards a Unifying Framework for Complex Query Processing over Structured Peer-to-Peer Data Networks, LECTURE NOTES IN COMPUTER SCIENCE, pp. 169-183, 2004.
[14] A. R. Bharambe, M. Agrawal, S. Seshan, Mercury: supporting scalable multi-attribute range queries, ACM SIGCOMM Computer Communication Review, vol. 34, pp. 353-366, 2004.
[15] A. Gupta, D. Agrawal, A. El Abbadi, Approximate range selection queries in peer-to-peer systems, in Proceedings of the First Biennial Conference on Innovative Data Systems Research, 2003.
[16] J. Aspnes, J. Kirsch A. Krishnamurthy, Load balancing and locality in range-queriable data structures, in Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, 2004, pp. 115-124.
[17] N. J. A. Harvey, M. B. Jones, S. Saroiu, M. Theimer, A. Wolman, SkipNet: a scalable overlay network with practical locality properties, in Proceedings of the 4th conference on USENIX Symposium on Internet Technologies and Systems-Volume 4 table of contents, 2003, pp. 9-9.
[18] K. Aberer, P. Cudr(?)-Mauroux, A. Datta, Z. Despotovic, M. Hauswirth, M. Punceva, R. Schmidt, P-Grid: a self-organizing structured P2P system, ACMSIGMOD Record, vol. 32, pp. 29-33, 2003.
[19] S. Ramabhadran, S. Ratnasamy, J. M. Hellerstein, S. Shenker, Prefix Hash Tree: An Indexing Data Structure over Distributed Hash Tables, in Proceedings of the 23rd ACM Symposium on Principles of Distributed Computing, St. John's, Newfoundland, Canada, July, 2004.
[20] M. Cai, M. Frank, J. Chen, P. Szekely, MAAN: A Multi-Attribute Addressable Network for Grid Information Services, Journal of Grid Computing, vol. 2, pp. 3-14, 2004.
[21] B.T. Loo, R. Huebsch, J. M. Hellerstein, T. Roscoe, I. Stoica, Analyzing P2P Overlays with Recursive Queries, Intel Research Technical Report IRB-TR-03-045, 2004.
[22] R. Huebsch, J. M. Hellerstein, N. Lanham, B. T. Loo, S. Shenker, I. Stoica, Querying the internet with PIER, in Proceedings of the 29th international conference on Very large data bases-Volume 29, 2003, pp. 321-332.
[23] R. Van Renesse, K. P. Birman, W. Vogels, Astrolabe: A robust and scalable technology for distributed system monitoring, management, and data mining, ACM Transactions on Computer Systems (TOCS), vol. 21, pp. 164-206, 2003.
[24] A. J. Ganesh, A. M. Kermarrec, L. Massouli(?), Peer-to-Peer Membership Management for Gossip-Based Protocols, IEEE TRANSACTIONS ON COMPUTERS, pp. 139-149, 2003.
[25] M. Jelasity, A. Montresor, O. Babaoglu, Gossip-based aggregation in large dynamic networks, ACM Transactions on Computer Systems (TOCS), vol. 23, pp. 219-252, 2005.
[26] R. van Renesse, A. Bozdog, Willow: DHT, Aggregation, and Publish/Subscribe in One Protocol, in Proceedings of lPTPS, 2004.
[27] J. Risson, T. Moors, Survey of research towards robust peer-to-peer networks: Search methods, Computer Networks, vol. 50, pp. 3485-3521, 2006.
[28] E. Sit, R. Morris, Security considerations for peer-to-peer distributed hash tables, in Proc. 1st International Workshop on Peer-to-Peer Systems (IPTPS), 2002.
[29] M. Castro, P. Druschel, A. Ganesh, A. Rowstron, D. S. Wallaeh, Secure routing for structured peer-to-peer overlay networks, ACM SIGOPS Operating Systems Review, vol. 36, pp. 299-314, 2002.
[30] D. S. Wallach, A Survey of Peer-to-Peer Security Issues, in Software Security: Theories and Systems: Mext-NSF-JSPS International Symposium, ISSS 2002, Tokyo, Japan, November 8-10, 2002: Revised Papers, 2003.
[31] S. Dahan, M. Sato, Survey of Six Myths and Oversights about Distributed Hash Tables' Security, in Distributed Computing Systems Workshops, 2007. ICDCSW'07. 27th International Conference on, 2007, pp. 26-26.
[32] K. Gummadi, R. Gummadi, S. Gribble, S. Ratnasamy, S. Shenker, I. Stoica, The Impact of DHT Routing Geometry on Resilience and Proximity, in SIGCOMM'03: Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, 2003, pp. 381-394.
[33] Y. Kulbak, D. Bickson, The eMule protocol specification, 2005.
[34] H. Yan, Z. J. F. Tom, C. Dah-Ming, C. S. L. John, H. Cheng, Challenges, design and analysis of a large-scale p2p-vod system, SIGCOMM Comput. Commun. Rev., vol. 38, pp. 375-388, 2008.
[35] J.R. Douceur, The Sybil Attack, in Peer-To-Peer Systems: First International Workshop, Iptps 2002, Cambridge, Ma, USA, March 7-8, 2002, Revised Papers, 2002.
[36] M. Steiner, T. En-Najjary, E. W. Biersack, Long Term Study of Peer Behavior in the KAD DHT, IEEE/ACM Transactions on Networking (TON), 2009.
[37] K. Sripanidkulchai, A. Ganjam, B. Maggs, H. Zhang, The feasibility of supporting large-scale live streaming applications with dynamic application end-points, ACM SIGCOMM Computer Communication Review, vol. 34, pp. 107-120, 2004.
[38] S. Q. Zhuang, D. Geels, I. Stoica, R. H. Katz, On failure detection algorithms in overlay networks, in INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE, 2005.
[39] S. Rhea, D. Geels, T. Roscoe, J. Kubiatowicz, Handling chum in a DHT, in Proceedings of the USENIX Annual Technical Conference 2004 on USENIX Annual Technical Conference table of contents, 2004, pp. 10-10.
[40] Y. Chen, R. H. Katz, J. Kubiatowicz, Dynamic Replica Placement for Scalable Content Delivery, in Proc. 1st International Workshop on Peer-to-Peer Systems, IPTPS'02, 2002, pp. 306-318.
[41] V. Ramasubramanian, E. G. Sirer, 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- Volume 1 table of contents, 2004, pp. 8-8.
[42] S. Iyer, A. Rowstron, P. Druschel, Squirrel: a decentralized peer-to-peer web cache, in Proceedings of the twenty-first annual symposium on Principles of distributed computing, 2002, pp. 213-222.
[43] H. Weatherspoon, J. Kubiatowicz, Erasure coding vs. replication: A quantitative comparison, in Proc. of IPTPS, 2002.
[44] G. Danezis, C. Lesniewski-Laas, M. F. Kaashoek, R. Anderson, Sybil-Resistant DHT Routing, LECTURE NOTES IN COMPUTER SCIENCE, vol. 3679, p. 305, 2005.
[45] M. Steiner, T. En-Najjary, E. W. Biersack, Exploiting KAD: possible uses and misuses, SIGCOMM Comput. Commun. Rev., vol. 37, pp. 65-70, 2007.
[46] A. Rowstron, P. Druschel, Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility, ACMSIGOPS Operating Systems Review, vol. 35, pp. 188-201, 2001.
[47] F. Dabek, M. F. Kaashoek, D. Karger, R. Morris, I. Stoica, Wide-area cooperative storage with CFS, ACM SIGOPS Operating Systems Review, vol. 35, pp. 202-215, 2001.
[48] A. Fiat, J. Saia, M. Young, Making Chord Robust to Byzantine Attacks, in Algorithms - ESA 2005, 2005, pp. 803-814.
[49] Z. Zhang, S. Chen, M. Yoon, MARCH: A Distributed Incentive Scheme for Peer-to-Peer Networks, in INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE, 2007, pp. 1091-1099.
[50] V. King, J. Saia, V. Sanwalani, E. Vee, Scalable leader election, in Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm Miami, Florida: ACM, 2006, pp. 990-999.
[51] L. Lamport, The part-time parliament, ACM Transactions on Computer Systems (TOCS), vol. 16, pp. 133-169, 1998.
[52] H. Johansen, A. Allavena, R. van Renesse, Fireflies: scalable support for intrusion-tolerant network overlays, in Proceedings of the 2006 EuroSys conference, 2006, pp. 3-13.
[53] C. G. Plaxton, Accessing Nearby Copies of Replicated Objects in a Distributed Environment, Theory of Computing Systems, vol. 32, pp. 241-280, 1999.
[54] F. Kaashoek, D. Karger, Koorde: A simple degree-optimal distributed hash table, in Proceedings of the 2nd International Workshop on Peer-to-Peer Systems (IPTPS '03), 2003.
[55] D. Malkhi, M. Naor, D. Ratajczak, Viceroy: a scalable and dynamic emulation of the butterfly, in Proceedings of the twenty-first annual symposium on Principles of distributed computing, 2002, pp. 183-192.
[56] 陈贵海，须成忠，沈海英，叶懋，刘之育，一种新的常数度数的P2P覆盖网络，计算机学报，vol．28，pp．1084-1095，2005．
[57] D. Guo, Y. Liu, X. Li, BAKE: A Balanced Kautz Tree Structure for Peer-to-Peer Networks, in INFOCOM 2008. The 27th Conference on Computer Communications. IEEE, 2008, pp. 2450-2457.
[58] F. Dabek, B. Zhao, P. Druschel, J. Kubiatowicz, I. Stoica, Towards a common API for structured P2P overlays, in Proc. of IPTPS, 2003.
[59] N. Leibowitz, M. Ripeanu, A. Wierzbicki, Deconstructing the Kazaa network, in Internet Applications. WIAPP 2003. Proceedings. The Third IEEE Workshop on, 2003, pp. 112-120.
[60] Y. Chawathe, S. Ratnasamy, L. Breslau, N. Lanham, S. Shenker, Making Gnutella-like P2P Systems Scalable, in Proceedings of ACM SIGCOMM, 2003.
[61] S. Rhea, B. Godfrey, B. Karp, J. Kubiatowicz, S. Ratnasamy, S. Shenker, I. Stoica, H. Yu, OpenDHT: a public DHT service and its uses, ACMSIGCOMM Computer Communication Review, vol. 35, pp. 73-84, 2005.
[62] H. Xie, Y. R. Yang, A. Krishnamurthy, Y. G. Liu, A. Silberschatz, P4p: provider portal for applications, SIGCOMM Comput. Commun. Rev., vol. 38, pp. 351-362, 2008.
[63] A. Mislove, P. Druschel, Providing Administrative Control and Autonomy in Structured Peer-to-Peer Overlays, in The 3rd International Workshop on Peer-to-Peer Systems, IPTPS'03, San Diego, CA, USA, February, 2004, pp. 26-27.
[64] M.J. Freedman, K. Lakshminarayanan, S. Rhea, I. Stoica, Non-transitive connectivity and DHTs, in Proceedings of the 2nd conference on Real, Large Distributed Systems, 2005, pp. 10-10.
[65] S.A. Baset, H. G. Schulzrinne, An Analysis of the Skype Peer-to-Peer Internet Telephony Protocol, in INFOCOM 2006. 25th IEEE International Conference on Computer Communications. Proceedings, 2006, pp. 1-11.
[66] D. Liben-Nowell, H. Balakrishnan, D. Karger, Analysis of the evolution of peer-to-peer systems, in Proceedings of the twenty-first annual symposium on Principles of distributed computing, 2002, pp. 233-242.
[67] D. Leonard, Z. Yao, X. Wang, D. Loguinov, On Static and Dynamic Partitioning Behavior of Large-Scale P2P Networks, IEEE/ACM Transactions on Networking (TON), vol. 16, pp. 1475-1488, December 2008.
[68] M. Castro, M. Costa, A. Rowstron, Performance and dependability of structured peer-to-peer overlays, in Dependable Systems and Networks, 2004 International Conference on, 2004, pp. 9-18.
[69] J. Li, J. Stribling, R. Morris, M. F. Kaashock, T. A. Gil, A performance vs. cost framework for evaluating DHT design tradeoffs under churn, in INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE, 2005.
[70] F. E. Bustamante, Y. Qiao, Friendships that last: peer lifespan and its role in P2P protocols, in Web content caching and distribution: proceedings of the 8th international workshop: Kluwer Academic Publishers, 2004, pp. 233-246.
[71] D. Stutzbach, R. Rejaie, Understanding churn in peer-to-peer networks, in Proceedings of the 6th ACM SIGCOMM conference on Internet measurement Rio de Janeriro, Brazil: ACM, 2006, pp. 189-202.
[72] Fabi, n. E. Bustamante, Y. Qiao, Designing less-structured P2P systems for the expected high churn, IEEE/ACM Transactions on Networking (TON), vol. 16, pp. 617-627, 2008.
[73] F. Wang, J. Liu, Y. Xiong, Stable Peers: Existence, Importance, and Application in Peer-to-Peer Live Video Streaming, in INFOCOM 2008. The 27th Conference on Computer Communications. IEEE, 2008, pp. 1364-1372.
[74] Z. Yao, D. Loguinov, Link Lifetimes and Randomized Neighbor Selection in DHTs, in INFOCOM 2008. The 27th Conference on Computer Communications. IEEE, 2008, pp. 146-150.
[75] D. Leonard, Z. Yao, V. Rai, D. Loguinov, On lifetime-based node failure and stochastic resilience of decentralized peer-to-peer networks, IEEE/ACM Transactions on Networking (TON), vol. 15, pp. 644-656, 2007.
[76] G. Tan, S. Jarvis, Stochastic Analysis and Improvement of the Reliability of DHT-based Multicast, in Proc. IEEE INFOCOM, 2007, pp. 2198-2206.
[77] S. Krishnamurthy, S. El-Ansary, E. Aurell, S. Haridi, An analytical study of a structured overlay in the presence of dynamic membership, IEEE/ACM Transactions on Networking (TON), vol. 16, pp. 814-825, 2008.
[78] S. Krishnamurthy, S. El-Ansary, E. Aurell, S. Haridi, Comparing Maintenance Strategies for Overlays, in Proceedings of the 16th Euromicro Conference on Parallel, Distributed and Network-Based Processing (PDP 2008) - Volume 00: IEEE Computer Society, 2008.
[79] Z. Yao, X. Wang, D. Leonard, D. Loguinov, On Node Isolation Under Churn in Unstructured P2P Networks with Heavy-Tailed Lifetimes, in INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE, 2007, pp. 2126-2134.
[80] Z. Yao, D. Loguinov, Understanding Disconnection and Stabilization of Chord, in INFOCOM 2008. The 27th Conference on Computer Communications. IEEE, 2008, pp. 1049-1057.
[81] M. Costa, M. Castro, R. Rowstron, P. Key, PIC: practical Internet coordinates for distance estimation, in Distributed Computing Systems, 2004. Proceedings. 24th International Conference on, 2004, pp. 178-187.
[82] A. Ittai, M. Dahlia, D. Oren, LAND: stretch (1+\&\#949;) locality-aware networks for DHTs, in Proceedings of the fifieenth annual ACM-SLAM symposium on Discrete algorithms New Orleans, Louisiana: Society for Industrial and Applied Mathematics, 2004, pp. 550-559.
[83] H. Kirsten, D. K. John, R. Satish, Y. Z. Ben, Distributed object location in a dynamic network, in Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures Winnipeg, Manitoba, Canada: ACM, 2002, pp. 41-52.
[84] R. K. David, R. Matthias, Finding nearest neighbors in growth-restricted metrics, in Proceedings of the thiry-fourth annual ACM symposium on Theory of computing Montreal, Quebec, Canada: ACM, 2002, pp. 741-750.
[85] J. Stribling, K. Hildrum, J. D. Kubiatowicz, Optimizations for Locality-Aware Structured Peer-to-Peer Overlays, Computer Science Division (EECS), University of California Berkeley, UCB/CSD-03-1266, 2003.
[86] S. Ratnasamy, M. Handley, R. Karp, S. Shenker, Topologically-aware overlay construction and server selection, in INFOCOM 2002. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, 2002.
[87] F. Dabek, R. Cox, F. Kaashoek, R. Morris, Vivaldi: a decentralized network coordinate system, ACMSIGCOMM Computer Communication Review, vol. 34, pp. 15-26, 2004.
[88] T. S. E. Ng, Z. Hui, Predicting Internet network distance with coordinates-based approaches, in INFOCOM 2002. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, 2002, pp. 170-179 vol.1.
[89] Z. Yong, C. Dovrolis, M. Ammar, Combining Multihoming with Overlay Routing (or, How to Be a Better ISP without Owning a Network), in INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE, 2007, pp. 839-847.
[90] A. Gupta, B. Liskov, R. Rodrigues, Efficient routing for peer-to-peer overlays, in Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation - Volume 1 San Francisco, California: USENIX Association, 2004, pp. 9-9.
[91] I. Gupta, K. Birman, P. Linga, A. Demers, R. van Renesse, Kelips: Building an Efficient and Stable P2P DHT through Increased Memory and Background Overhead, in Peer-to-peer Systems:International Workshop, IPTPS'02, 2003.
[92] B. Leong, J. Li, Achieving one-hop DHT lookup and strong stabilization by passing tokens, in Networks, 2004. (ICON 2004). Proceedings. 12th IEEE International Conference on, 2004, pp. 344-350 vol. 1.
[93] A. Gupta, B. Liskov, R. Rodrigues, One hop lookups for peer-to-peer overlays, in Proceedings of the 9th conference on Hot Topics in Operating Systems - Volume 9 Lihue, Hawaii: USENIX Association, 2003, pp. 2-2.
[94] J. Risson, A. Harwood, T. Moors, Stable High-Capacity One-Hop Distributed Hash Tables, in Computers and Communications, 2006. ISCC'06. Proceedings. 11th IEEE Symposium on, 2006, pp. 687-694.
[95] Q. Lian, W. Chen, Z. Zhang, S. Wu, B. Y. Zhao, Z-Ring: Fast Prefix Routing via a Low Maintenance Membership Protocol, in 13th IEEE International Conference on Network Protocols, ICNP'05, 2005, pp. 132-146.
[96] J. Buford, A. Brown, M. Kolberg, Analysis of an Active Maintenance Algorithm for an O(1)-Hop Overlay, in Global Telecommunications Conference, 2007. GLOBECOM '07. IEEE, 2007, pp. 81-86.
[97] C. Tang, M. J. Buco, R. N. Chang, S. Dwarkadas, L. Z. Luan, E. So, C. Ward, Low traffic overlay networks with large routing tables, ACM SIGMETRICS Performance Evaluation Review, vol. 33, pp. 14-25, 2005.
[98] K. Sripanidkulchai, The popularity of Gnutella queries and its implications on scalability: http://www.cs.cmu.edu/～kunwadee/research/p2p/gnutella.html, 2001.
[99] C. Chen, K.-C. Tsai, The Server Reassignment Problem for Load Balancing in Structured P2P Systems, IEEE Trans. Parallel Distrib. Syst., vol. 19, pp. 234-246, 2008.
[100] D. R. Karger, M. Ruhl, Simple Efficient Load-Balancing Algorithms for Peer-to-Peer Systems, Theory of Computing Systems, vol. 39, pp. 787-804, 2006.
[101] A. Rao, K. Lakshminarayanan, S. Surana, R. Karp, I. Stoica, Load Balancing in Structured P2P Systems, in Peer-to-peer Systems:International Workshop, IPTPS'02, 2002.
[102] B. Godfrey, K. Lakshminarayanan, S. Surana, R. Karp, I. Stoica, Load Balancing in Dynamic Structured P2P Systems, in Proc. IEEE INFOCOM, 2004.
[103] P. B. Godfrey, I. Stoica, Heterogeneity and load balance in distributed hash tables, in Proc. IEEE INFOCOM, 2005.
[104] X. Wang, D. Loguinov, Load-balancing performance of consistent hashing: asymptotic analysis of random node join, IEEE/ACM Transactions on Networking (TON), vol. 15, pp. 892-905, 2007.
[105] M. Naor, U. Wieder, Novel architectures for P2P applications: The continuous-discrete approach, ACM Trans. Algorithms, vol. 3, p. 34, 2007.
[106] K. Kenthapadi, G. S. Manku, Decentralized algorithms using both local and random probes for P2P load balancing, in Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, 2005, pp. 135-144.
[107] G. Giakkoupis, V. Hadzilacos, A scheme for load balancing in heterogenous distributed hash tables, in Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing Las Vegas, NV, USA: ACM, 2005, pp. 302-311.
[108] E. Adar, B. Huberman, Free riding on gnutella, First Monday, 2000.
[109] G. Hardin, The Tragedy of the Commons, Science, vol. 162, pp. 1243-1248, 1968.
[110] K. Aberer, Z. Despotovic, Managing trust in a peer-2-peer information system, in Proceedings of the tenth international conference on Information and knowledge management, 2001, pp. 310-317.
[111] F. Cornelli, E. Damiani, S. D. C. di Vimercati, S. Paraboschi, P. Samarati, Choosing reputable servents in a P2P network, in Proceedings of the 11th international conference on World Wide Web, 2002, pp. 376-386.
[112] E. Damiani, S. Paraboschi, P. Samarati, F. Violante, A reputation-based approach for choosing reliable resources in peer-to-peer networks, in Proceedings of the 9th ACM conference on Computer and communications security, 2002, pp. 207-216.
[113] D. Fahrenholtz, W. Lamersdorf, Transactional Security for a Distributed Reputation Management System, in E-Commerce and Web Technologies, 2002, pp. 259-260.
[114] C. Liau, X. Zhou, S. Bressan, K.-L. Tan, Efficient Distributed Reputation Scheme for Peer-to-Peer Systems, in Web and Communication Technologies and Internet-Related Social Issues - HSI 2003, 2003, pp. 172-172.
[115] S. D. Kamvar, M. T. Schlosser, H. Garcia-Molina, The Eigentrust algorithm for reputation management in P2P networks, in Proceedings of the 12th international conference on World Wide Web, 2003, pp. 640-651.
[116] P. Resnick, R. Zeckhauser, Trust Among Strangers in Interact Transactions: Empirical Analysis of eBay's Reputation System, The Economics of the Internet and E-Commerce, vol. 11, pp. 23-25, 2002.
[117] L. Mui, M. Mohtashemi, A. Halberstadt, A computational model of trust and reputation, in Proceedings of the 35th Hawaii International Conference on System Sciences, 2002, pp. 188-196.
[118] A. Jφsang, R. Ismail, The beta reputation system, in Proceedings of the 15th Bled Electronic Commerce Conference, 2002, pp. 324-337.
[119] A. Whitby, A. Jφsang, J. Indulska, Filtering out unfair ratings in bayesian reputation systems, The Icfain Journal of Management Research, vol. 4, pp. 48-64, 2005.
[120] R. Ismail, C. Boyd, A. Jφsang, S. Russel, Strong Privacy in Reputation Systems, in Proceedings of the 4th International Workshop on Information Security Applications (WISA), 2003.
[121] J. Sabater, C. Sierra, Reputation and social network analysis in multi-agent systems, in Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 1, 2002, pp. 475-482.
[122] E. J. Friedman, P. Resnick, The Social Cost of Cheap Pseudonyms, Journal of Economics & Management Strategy, vol. 10, pp. 173-199, 2001.
[123] M. Feldman, J. Chuang, Overcoming free-riding behavior in peer-to-peer systems, ACM SIGecom Exchanges, vol. 5, pp. 41-50, 2005.
[124] J. Andreoni, Giving with Impure Altruism: Applications to Charity and Ricardian Equivalence, The Journal of Political Economy, vol. 97, p. 1447, 1989.
[125] V. Vishnumurthy, S. Chandrakumar, E. G. Sirer, Karma: A secure economic framework for peer-to-peer resource sharing, in Workshop on Economics of Peer-to-Peer Systems, 2003.
[126] K. Walsh, E. G. Sirer, Experience with an object reputation system for peer-to-peer filesharing, in USENIX NSDI, 2006.
[127] B. Cohen, Incentives Build Robustness in BitTorrent, in Workshop on Economics of Peer-to-Peer Systems, 2003.
[128] D. Qiu, R. Srikant, Modeling and performance analysis of BitTorrent-like peer-to-peer networks, in Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, 2004, pp. 367-378.
[129] L. Guo, S. Chen, Z. Xiao, E. Tan, X. Ding, X. Zhang, Measurements, analysis, and modeling of BitTorrent-like systems, in Proceedings of the 5th ACM SIGCOMM conference on Internet measurement, 2005.
[130] M. Piatek, T. Isdal, T. Anderson, A. Krishnamurthy, A. Venkataramani, Do incentives build robustness in BitTorrent, in Proc. of NSDI, 2007.
[131] D. Levin, K. LaCurts, N. Spring, B. Bhattacharjee, Bittorrent is an auction: analyzing and improving bittorrent's incentives, SIGCOMM Comput. Commun. Rev., vol. 38, pp. 243-254, 2008.
[132] V. King, J. Saia, Choosing a random peer, in Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, 2004, pp. 125-130.
[133] V. King, S. Lewis, J. Saia, M. Young, Choosing a Random Peer in Chord, Algorithmica, vol. 49, pp. 147-169, 2007.
[134] C. Scheideler, How to spread adversarial nodes?: rotate!, in Proceedings of the thirty-seventh annual ACM symposium on Theory of computing Baltimore, MD, USA: ACM, 2005, pp. 704-713.
[135] M. Castro, P. Druschel, Y. C. Hu, A. Rowstron, Proximity neighbor selection in tree-based structured peer-to-peer overlays, Microsoft Research MSR-TR-2003-52, 2003.
[136] J. Schmidt, A. Siegel, A. Srinivasan, Chernoff-Hoeffding bounds for applications with limited independence, 1993, pp. 331-340.
[137] J. Aspnes, Z. Diamadi, G. Shah, Fault-tolerant routing in peer-to-peer systems, in Proceedings of the twenty-first annual symposium on Principles of distributed computing, 2002, pp. 223-232.
[138] J. S. Kong, J. S. A. Bridgewater, V. P. Roychowdhury, A General Framework for Scalability and Performance Analysis of DHT Routing Systems, in Proceedings of the International Conference on Dependable Systems and Networks: IEEE Computer Society, 2006.
[139] 徐全智，吕恕，概率论与数理统计，高等教育出版社，2004．
[140] 毛用才，胡奇英，随机过程，西安，西安电子科技大学出版社，1998．
[141] 盛骤，谢式千，潘承毅，概率论与数理统计，高等教育出版社，1989．
[142] 格涅坚科(苏)，概率论教程，人民教育出版社，1956．
[143] 贺德化，概率论与数理统计网络课程，高等教育出版社，2004．
[144] S. Saroiu, P. K. Gummadi, S. D. Gribble, A measurement study of peer-to-peer file sharing systems, in Proceedings of Multimedia Computing and Networking, 2002.
[145] J. Kubiatowicz, D. Bindel, Y. Chen, S. Czerwinski, P. Eaton, D. Geels, R. Gummadi, S. Rhea, H. Weatherspoon, C. Wells, OceanStore: an architecture for global-scale persistent storage, ACM SIGARCH Computer Architecture News, vol. 28, pp. 190-201, 2000.
[146] G. S. Manku, Balanced binary trees for ID management and load balance in distributed hash tables, in Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing St. John's, Newfoundland, Canada: ACM, 2004, pp. 197-205.
[147] M. Adler, E. Halperin, R. M. Karp, V. V. Vazirani, A stochastic process on the hypercube with applications to peer-to-peer networks, in Proceedings of the thirty-fifth annual ACM symposium on Theory of computing San Diego, CA, USA: ACM, 2003, pp. 575-584.
[148] R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, Lambert's W function in Maple, Maple Technical Newsletter, vol. 9, pp. 12-22, 1993.
[149] S. M. Ross, Introduction to Probability Models, 9 ed., Elsevier (Singapore) Pte Ltd., 2007.
[150] A. Ghodsi, L. O. Alima, S. Haridi, Symmetric Replication for Structured Peer-to-Peer Systems, LECTURE NOTES IN COMPUTER SCIENCE, vol. 4125, p. 74, 2007.
[151] P. Wang, J. Tyra, E. Chan-Tin, T. Malchow, D. F. Kune, N. Hopper, Y. Kim, Attacking the Kad network, in Proceedings of the 4th international conference on Security and privacy in communication netowrks, SecureComm 2008, Istanbul, Turkey: ACM, 2008, pp. 1-10.
[152] A. Singh, T. W. Ngan, P. Druschel, D. S. Wallach, Eclipse Attacks on Overlay Networks: Threats and Defenses, in INFOCOM 2006. 25th IEEE International Conference on Computer Communications. Proceedings, 2006, pp. 1-12.
[153] J. Liang, N. Naoumov, K. W. Ross, The Index Poisoning Attack in P2P File Sharing Systems, in INFOCOM 2006. 25th IEEE International Conference on Computer Communications. Proceedings, 2006, pp. 1-12.
[154] S. Ryu, K. Butler, P. Traynor, P. McDaniel, Leveraging Identity-Based Cryptography for Node ID Assignment in Structured P2P Systems, in Proceedings of the 21st International Conference on Advanced Information Networking and Applications Workshops- Volume 01, 2007, pp. 519-524.
[155] L. M. Aiello, M. Milanesio, G. Ruffo, R. Schifanella, Tempering Kademlia with a Robust Identity Based System, in Peer-to-Peer Computing, 2008. P2P'08. Eighth International Conference on, 2008, pp. 30-39.
[156] 聂晓文，卢显良，唐晖，赵志军，李玉军，基于洗牌策略的Sybil攻击防御，电子学报，Vol．36，pp．2144-2149，2008．
[157] H. Rowaihy, W. Enck, P. McDaniel, T. La Porta, Limiting sybil attacks in structured p2p networks, in 26th IEEE International Conference on Computer Communications (INFOCOM), 2007, pp. 2596-2600.
[158] R. Bazzi, G. Konjevod, On the establishment of distinct identities in overlay networks, Distributed Computing, vol. 19, pp. 267-287, 2007.
[159] H. Yu, M. Kaminsky, P. B. Gibbons, A. D. Flaxman, SybilGuard: Defending Against Sybil Attacks via Social Networks, IEEE/ACM Transactions on Networking (TON), vol. 16, pp. 576-589, 2008.
[160] T. Condie, V. Kacholia, S. Sankararaman, J. Hellerstein, P. Maniatis, Induced Churn as Shelter from Routing-Table Poisoning, in Proceedings of Network and Distributed System Security Symposium, San Diego, California, USA, 2006.
[161] B. Awerbuch, C. Scheideler, Towards a scalable and robust DHT, in Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures Cambridge, Massachusetts, USA: ACM, 2006, pp. 318-327.
[162] W. Feller, An Introduction to Probability Theory and Its Applications. Volume I, John Wiley & Sons, 1951.
[163] A. F. Siegel, L. Holst, Covering the Circle with Random Arcs of Random Sizes, Journal of Applied Probability, vol. 19, pp. 373-381, 1982.
[164] C. Domb, Covering by random intervals and one-dimensional continuum percolation, Journal of Statistical Physics, vol. 55, pp. 441-460, 1989.
[165] L. Zhou, F. B. Schneider, R. Van Renesse, COCA: A Secure Distributed Online Certification Authority, ACM Transactions on Computer Systems (TOCS), vol. 20, pp. 329-368, 2002.
[166] K. Horowitz, D. Malkhi, Estimating network size from local information, Information Processing Letters, vol. 88, pp. 237-243, 2003.
[167] M. Bawa, H. Garcia-Molina, A. Gionis, R. Motwani, Estimating aggregates on a peer-to-peer network, Technical Stanford, 2004.
[168] L. Massouli, E. L. Merrer, A.-M. Kermarrec, A. Ganesh, Peer counting and sampling in overlay networks: random walk methods, in Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing Denver, Colorado, USA: ACM, 2006, pp. 123-132.
[169] D. Kostoulas, D. Psaltoulis, I. Gupta, K. Birman, A. Demers, Decentralized Schemes for Size Estimation in Large and Dynamic Groups, in Network Computing and Applications, Fourth IEEE International Symposium on, 2005, pp. 41-48.
[170] D. Psaltoulis, D. Kostoulas, I. Gupta, K. Birman, A. Demers, Practical algorithms for Size estimation in Large and Dynamic groups, in the 26th Annual International Conference on Software Engineering (ICSE 2004), Edinburgh, Scotland.PODC'04, 2004, pp. 2-2.
[171] E. Le Merrer, A. M. Kermarrec, L. Massoulie, Peer to peer size estimation in large and dynamic networks: A comparative study, in Proceedings of the IEEE International Symposium on High Performance Distributed Computing (HPDC), 2006.
[172] S. Mane, S. Mopuru, K. Mehra, J. Srivastava, Network Size Estimation In A Peer-to-Peer Network, University of Minnesota TR 05-030, September 15 2005.
[173] G. S. Manku, Routing networks for distributed hash tables, in Proceedings of the twenty-second annual symposium on Principles of distributed computing, 2003, pp. 133-142.
[174] T. Shafaat, A. Ghodsi, S. Haridi, A Practical Approach to Network Size Estimation for Structured Overlays, in Self-Organizing Systems, 2008, pp. 71-83.
[175] C. Gkantsidis, M. Mihail, A. Saberi, Random walks in peer-to-peer networks, in INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies, 2004.
[176] P. Francis, Yoid: Extending the interact multicast architecture, White Paper, http://www.cs.wisc.edu/～suman/pubs.html, 2002.
[177] M. Faloutsos, P. Faloutsos, C. Faloutsos, On power-law relationships of the Internet topology, in Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, 1999, pp. 251-262.
[178] V. Vishnumurthy, P. Francis, On Heterogeneous Overlay Construction and Random Node Selection in Unstructured P2P Networks, in INFOCOM 2006. 25th IEEE International Conference on Computer Communications. Proceedings, 2006, pp. 1-12.
[179] V. Vishnumurthy, P. Francis, A comparison of structured and unstructured P2P approaches to heterogeneous random peer selection, in 2007 USENIX Annual Technical Conference on Proceedings of the USENIX Annual Technical Conference Santa Clam, CA: USENIX Association, 2007, pp. 1-14.
[180] G. E. Forsythe, Von Neumann's comparison method for random sampling from the normal and other distributions, Math. Comp, vol. 26, pp. 817-826, 1972.
[181] J. A. Grzesik, Von Neumann's Rejection Technique Reexamined, SlAM Review, vol. 31, p. 486, 1989.
[182] V. Neumann, Various Techniques Used in Connection with Random Digits, Applied Mathematics, vol. Series 12, pp. 36-38, 1951.
[183] P. R. Tadikamalla, Random Sampling from the Exponential Power Distribution Journal of the American Statistical Association, vol. Vol. 75, pp. 683-686 1980.
[184] P. R. Tadikamalla, Random sampling from the generalized gamma distribution Computing, vol. Volume 23, pp. 199-203, 1979.
[185] D. Knuth, Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd Edition), Addison-Wesley Professional, 1997.
[186] 吕英华，计算电磁学的数值方法，1 ed．，北京，清华大学出版社，2006．
[187] A. Rukhin, J. Soto, J. Nechvatal, M. Smid, E. barker, S. Leigh, M. Levenson, M. Vangel, D. Banks, A. Heckert, J. Dray, S. Vo, A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptgraphic Applications, NIST Special Publication May 15 2001.
[188] 何朝兵，田彦伟，顺序统计量的分布，成都大学学报(自然科学版)Vol．27，pp．116-119，2008．
[2] M. Ripeanu, I. Foster, A. Iamnitchi, Mapping the Gnutella Network: Properties of Large-Scale Peer-to-Peer Systems and Implications for System Design, IEEE INTERNET COMPUTING JOURNAL, vol. 6, p. 1, 2002.
[3] http://www.clip2.com, The Gnutella Protocol Specification v0.4: http://www9.limewire.com/developer/gnutella_protocol_0.4.pdf.
[4] I. Clarke, O. Sandberg, B. Wiley, T. W. Hong, Freenet: a distributed anonymous information storage and retrieval system, in International workshop on Designing privacy enhancing technologies: design issues in anonymity and unobservability table of contents, 2001, pp.46-66.
[5] Q. Lv, P. Cao, E. Cohen, K. Li, S. Shenker, Search and replication in unstructured peer-to-peer networks, in Proceedings of the 16th international conference on Supercomputing, 2002, pp. 84-95.
[6] Q. Lv, S. Ratnasamy, S. Shenker, Can heterogeneity make gnutella scalable, in Proceedings of the 1st International Workshop on Peer-to-Peer Systems (1PTPS'02), 2002.
[7] I. Stoica, R. Morris, D. Liben-Nowell, D. R. Karger, M. F. Kaashoek, F. Dabek, H. Balakrishnan, Chord: a scalable peer-to-peer lookup protocol for Internet applications, IEEE/ACM Transactions on Networking (TON), vol. 11, pp. 17-32, 2003.
[8] S. Ratnasamy, P. Francis, M. Handley, R. Karp, S. Schenker, A scalable content-addressable network, in Proceedings of the 2001 SIGCOMM conference, 2001, pp. 161-172.
[9] A. Rowstron, P. Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, in Proceedings of the 18th IFIP/ACM International Conference on Distributed Systems Platforms (Middleware), LNCS. vol. 2218, 2001, pp. 329-350.
[10] B. Y. Zhao, L. Huang, J. Stribling, S. C. Rhea, A. D. Joseph, J. D. Kubiatowicz, Tapestry: a resilient global-scale overlay for service deployment, IEEE Journals on Selected Areas in Communications, vol. 22, pp. 41-53, 2004.
[11] P. Maymounkov, D. Mazieres, 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'02), 2002, p. 263.
[12] I. H. Witten, A. Moffat, T. C. Bell, Managing Gigabytes: Compressing and Indexing Documents and Images, 1999: Morgan Kaufmann Publishers.
[13] P. Triantafillou, T. Pitoura, Towards a Unifying Framework for Complex Query Processing over Structured Peer-to-Peer Data Networks, LECTURE NOTES IN COMPUTER SCIENCE, pp. 169-183, 2004.
[14] A. R. Bharambe, M. Agrawal, S. Seshan, Mercury: supporting scalable multi-attribute range queries, ACM SIGCOMM Computer Communication Review, vol. 34, pp. 353-366, 2004.
[15] A. Gupta, D. Agrawal, A. El Abbadi, Approximate range selection queries in peer-to-peer systems, in Proceedings of the First Biennial Conference on Innovative Data Systems Research, 2003.
[16] J. Aspnes, J. Kirsch A. Krishnamurthy, Load balancing and locality in range-queriable data structures, in Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, 2004, pp. 115-124.
[17] N. J. A. Harvey, M. B. Jones, S. Saroiu, M. Theimer, A. Wolman, SkipNet: a scalable overlay network with practical locality properties, in Proceedings of the 4th conference on USENIX Symposium on Internet Technologies and Systems-Volume 4 table of contents, 2003, pp. 9-9.
[18] K. Aberer, P. Cudr(?)-Mauroux, A. Datta, Z. Despotovic, M. Hauswirth, M. Punceva, R. Schmidt, P-Grid: a self-organizing structured P2P system, ACMSIGMOD Record, vol. 32, pp. 29-33, 2003.
[19] S. Ramabhadran, S. Ratnasamy, J. M. Hellerstein, S. Shenker, Prefix Hash Tree: An Indexing Data Structure over Distributed Hash Tables, in Proceedings of the 23rd ACM Symposium on Principles of Distributed Computing, St. John's, Newfoundland, Canada, July, 2004.
[20] M. Cai, M. Frank, J. Chen, P. Szekely, MAAN: A Multi-Attribute Addressable Network for Grid Information Services, Journal of Grid Computing, vol. 2, pp. 3-14, 2004.
[21] B.T. Loo, R. Huebsch, J. M. Hellerstein, T. Roscoe, I. Stoica, Analyzing P2P Overlays with Recursive Queries, Intel Research Technical Report IRB-TR-03-045, 2004.
[22] R. Huebsch, J. M. Hellerstein, N. Lanham, B. T. Loo, S. Shenker, I. Stoica, Querying the internet with PIER, in Proceedings of the 29th international conference on Very large data bases-Volume 29, 2003, pp. 321-332.
[23] R. Van Renesse, K. P. Birman, W. Vogels, Astrolabe: A robust and scalable technology for distributed system monitoring, management, and data mining, ACM Transactions on Computer Systems (TOCS), vol. 21, pp. 164-206, 2003.
[24] A. J. Ganesh, A. M. Kermarrec, L. Massouli(?), Peer-to-Peer Membership Management for Gossip-Based Protocols, IEEE TRANSACTIONS ON COMPUTERS, pp. 139-149, 2003.
[25] M. Jelasity, A. Montresor, O. Babaoglu, Gossip-based aggregation in large dynamic networks, ACM Transactions on Computer Systems (TOCS), vol. 23, pp. 219-252, 2005.
[26] R. van Renesse, A. Bozdog, Willow: DHT, Aggregation, and Publish/Subscribe in One Protocol, in Proceedings of lPTPS, 2004.
[27] J. Risson, T. Moors, Survey of research towards robust peer-to-peer networks: Search methods, Computer Networks, vol. 50, pp. 3485-3521, 2006.
[28] E. Sit, R. Morris, Security considerations for peer-to-peer distributed hash tables, in Proc. 1st International Workshop on Peer-to-Peer Systems (IPTPS), 2002.
[29] M. Castro, P. Druschel, A. Ganesh, A. Rowstron, D. S. Wallaeh, Secure routing for structured peer-to-peer overlay networks, ACM SIGOPS Operating Systems Review, vol. 36, pp. 299-314, 2002.
[30] D. S. Wallach, A Survey of Peer-to-Peer Security Issues, in Software Security: Theories and Systems: Mext-NSF-JSPS International Symposium, ISSS 2002, Tokyo, Japan, November 8-10, 2002: Revised Papers, 2003.
[31] S. Dahan, M. Sato, Survey of Six Myths and Oversights about Distributed Hash Tables' Security, in Distributed Computing Systems Workshops, 2007. ICDCSW'07. 27th International Conference on, 2007, pp. 26-26.
[32] K. Gummadi, R. Gummadi, S. Gribble, S. Ratnasamy, S. Shenker, I. Stoica, The Impact of DHT Routing Geometry on Resilience and Proximity, in SIGCOMM'03: Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, 2003, pp. 381-394.
[33] Y. Kulbak, D. Bickson, The eMule protocol specification, 2005.
[34] H. Yan, Z. J. F. Tom, C. Dah-Ming, C. S. L. John, H. Cheng, Challenges, design and analysis of a large-scale p2p-vod system, SIGCOMM Comput. Commun. Rev., vol. 38, pp. 375-388, 2008.
[35] J.R. Douceur, The Sybil Attack, in Peer-To-Peer Systems: First International Workshop, Iptps 2002, Cambridge, Ma, USA, March 7-8, 2002, Revised Papers, 2002.
[36] M. Steiner, T. En-Najjary, E. W. Biersack, Long Term Study of Peer Behavior in the KAD DHT, IEEE/ACM Transactions on Networking (TON), 2009.
[37] K. Sripanidkulchai, A. Ganjam, B. Maggs, H. Zhang, The feasibility of supporting large-scale live streaming applications with dynamic application end-points, ACM SIGCOMM Computer Communication Review, vol. 34, pp. 107-120, 2004.
[38] S. Q. Zhuang, D. Geels, I. Stoica, R. H. Katz, On failure detection algorithms in overlay networks, in INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE, 2005.
[39] S. Rhea, D. Geels, T. Roscoe, J. Kubiatowicz, Handling chum in a DHT, in Proceedings of the USENIX Annual Technical Conference 2004 on USENIX Annual Technical Conference table of contents, 2004, pp. 10-10.
[40] Y. Chen, R. H. Katz, J. Kubiatowicz, Dynamic Replica Placement for Scalable Content Delivery, in Proc. 1st International Workshop on Peer-to-Peer Systems, IPTPS'02, 2002, pp. 306-318.
[41] V. Ramasubramanian, E. G. Sirer, 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- Volume 1 table of contents, 2004, pp. 8-8.
[42] S. Iyer, A. Rowstron, P. Druschel, Squirrel: a decentralized peer-to-peer web cache, in Proceedings of the twenty-first annual symposium on Principles of distributed computing, 2002, pp. 213-222.
[43] H. Weatherspoon, J. Kubiatowicz, Erasure coding vs. replication: A quantitative comparison, in Proc. of IPTPS, 2002.
[44] G. Danezis, C. Lesniewski-Laas, M. F. Kaashoek, R. Anderson, Sybil-Resistant DHT Routing, LECTURE NOTES IN COMPUTER SCIENCE, vol. 3679, p. 305, 2005.
[45] M. Steiner, T. En-Najjary, E. W. Biersack, Exploiting KAD: possible uses and misuses, SIGCOMM Comput. Commun. Rev., vol. 37, pp. 65-70, 2007.
[46] A. Rowstron, P. Druschel, Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility, ACMSIGOPS Operating Systems Review, vol. 35, pp. 188-201, 2001.
[47] F. Dabek, M. F. Kaashoek, D. Karger, R. Morris, I. Stoica, Wide-area cooperative storage with CFS, ACM SIGOPS Operating Systems Review, vol. 35, pp. 202-215, 2001.
[48] A. Fiat, J. Saia, M. Young, Making Chord Robust to Byzantine Attacks, in Algorithms - ESA 2005, 2005, pp. 803-814.
[49] Z. Zhang, S. Chen, M. Yoon, MARCH: A Distributed Incentive Scheme for Peer-to-Peer Networks, in INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE, 2007, pp. 1091-1099.
[50] V. King, J. Saia, V. Sanwalani, E. Vee, Scalable leader election, in Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm Miami, Florida: ACM, 2006, pp. 990-999.
[51] L. Lamport, The part-time parliament, ACM Transactions on Computer Systems (TOCS), vol. 16, pp. 133-169, 1998.
[52] H. Johansen, A. Allavena, R. van Renesse, Fireflies: scalable support for intrusion-tolerant network overlays, in Proceedings of the 2006 EuroSys conference, 2006, pp. 3-13.
[53] C. G. Plaxton, Accessing Nearby Copies of Replicated Objects in a Distributed Environment, Theory of Computing Systems, vol. 32, pp. 241-280, 1999.
[54] F. Kaashoek, D. Karger, Koorde: A simple degree-optimal distributed hash table, in Proceedings of the 2nd International Workshop on Peer-to-Peer Systems (IPTPS '03), 2003.
[55] D. Malkhi, M. Naor, D. Ratajczak, Viceroy: a scalable and dynamic emulation of the butterfly, in Proceedings of the twenty-first annual symposium on Principles of distributed computing, 2002, pp. 183-192.
[56] 陈贵海，须成忠，沈海英，叶懋，刘之育，一种新的常数度数的P2P覆盖网络，计算机学报，vol．28，pp．1084-1095，2005．
[57] D. Guo, Y. Liu, X. Li, BAKE: A Balanced Kautz Tree Structure for Peer-to-Peer Networks, in INFOCOM 2008. The 27th Conference on Computer Communications. IEEE, 2008, pp. 2450-2457.
[58] F. Dabek, B. Zhao, P. Druschel, J. Kubiatowicz, I. Stoica, Towards a common API for structured P2P overlays, in Proc. of IPTPS, 2003.
[59] N. Leibowitz, M. Ripeanu, A. Wierzbicki, Deconstructing the Kazaa network, in Internet Applications. WIAPP 2003. Proceedings. The Third IEEE Workshop on, 2003, pp. 112-120.
[60] Y. Chawathe, S. Ratnasamy, L. Breslau, N. Lanham, S. Shenker, Making Gnutella-like P2P Systems Scalable, in Proceedings of ACM SIGCOMM, 2003.
[61] S. Rhea, B. Godfrey, B. Karp, J. Kubiatowicz, S. Ratnasamy, S. Shenker, I. Stoica, H. Yu, OpenDHT: a public DHT service and its uses, ACMSIGCOMM Computer Communication Review, vol. 35, pp. 73-84, 2005.
[62] H. Xie, Y. R. Yang, A. Krishnamurthy, Y. G. Liu, A. Silberschatz, P4p: provider portal for applications, SIGCOMM Comput. Commun. Rev., vol. 38, pp. 351-362, 2008.
[63] A. Mislove, P. Druschel, Providing Administrative Control and Autonomy in Structured Peer-to-Peer Overlays, in The 3rd International Workshop on Peer-to-Peer Systems, IPTPS'03, San Diego, CA, USA, February, 2004, pp. 26-27.
[64] M.J. Freedman, K. Lakshminarayanan, S. Rhea, I. Stoica, Non-transitive connectivity and DHTs, in Proceedings of the 2nd conference on Real, Large Distributed Systems, 2005, pp. 10-10.
[65] S.A. Baset, H. G. Schulzrinne, An Analysis of the Skype Peer-to-Peer Internet Telephony Protocol, in INFOCOM 2006. 25th IEEE International Conference on Computer Communications. Proceedings, 2006, pp. 1-11.
[66] D. Liben-Nowell, H. Balakrishnan, D. Karger, Analysis of the evolution of peer-to-peer systems, in Proceedings of the twenty-first annual symposium on Principles of distributed computing, 2002, pp. 233-242.
[67] D. Leonard, Z. Yao, X. Wang, D. Loguinov, On Static and Dynamic Partitioning Behavior of Large-Scale P2P Networks, IEEE/ACM Transactions on Networking (TON), vol. 16, pp. 1475-1488, December 2008.
[68] M. Castro, M. Costa, A. Rowstron, Performance and dependability of structured peer-to-peer overlays, in Dependable Systems and Networks, 2004 International Conference on, 2004, pp. 9-18.
[69] J. Li, J. Stribling, R. Morris, M. F. Kaashock, T. A. Gil, A performance vs. cost framework for evaluating DHT design tradeoffs under churn, in INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE, 2005.
[70] F. E. Bustamante, Y. Qiao, Friendships that last: peer lifespan and its role in P2P protocols, in Web content caching and distribution: proceedings of the 8th international workshop: Kluwer Academic Publishers, 2004, pp. 233-246.
[71] D. Stutzbach, R. Rejaie, Understanding churn in peer-to-peer networks, in Proceedings of the 6th ACM SIGCOMM conference on Internet measurement Rio de Janeriro, Brazil: ACM, 2006, pp. 189-202.
[72] Fabi, n. E. Bustamante, Y. Qiao, Designing less-structured P2P systems for the expected high churn, IEEE/ACM Transactions on Networking (TON), vol. 16, pp. 617-627, 2008.
[73] F. Wang, J. Liu, Y. Xiong, Stable Peers: Existence, Importance, and Application in Peer-to-Peer Live Video Streaming, in INFOCOM 2008. The 27th Conference on Computer Communications. IEEE, 2008, pp. 1364-1372.
[74] Z. Yao, D. Loguinov, Link Lifetimes and Randomized Neighbor Selection in DHTs, in INFOCOM 2008. The 27th Conference on Computer Communications. IEEE, 2008, pp. 146-150.
[75] D. Leonard, Z. Yao, V. Rai, D. Loguinov, On lifetime-based node failure and stochastic resilience of decentralized peer-to-peer networks, IEEE/ACM Transactions on Networking (TON), vol. 15, pp. 644-656, 2007.
[76] G. Tan, S. Jarvis, Stochastic Analysis and Improvement of the Reliability of DHT-based Multicast, in Proc. IEEE INFOCOM, 2007, pp. 2198-2206.
[77] S. Krishnamurthy, S. El-Ansary, E. Aurell, S. Haridi, An analytical study of a structured overlay in the presence of dynamic membership, IEEE/ACM Transactions on Networking (TON), vol. 16, pp. 814-825, 2008.
[78] S. Krishnamurthy, S. El-Ansary, E. Aurell, S. Haridi, Comparing Maintenance Strategies for Overlays, in Proceedings of the 16th Euromicro Conference on Parallel, Distributed and Network-Based Processing (PDP 2008) - Volume 00: IEEE Computer Society, 2008.
[79] Z. Yao, X. Wang, D. Leonard, D. Loguinov, On Node Isolation Under Churn in Unstructured P2P Networks with Heavy-Tailed Lifetimes, in INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE, 2007, pp. 2126-2134.
[80] Z. Yao, D. Loguinov, Understanding Disconnection and Stabilization of Chord, in INFOCOM 2008. The 27th Conference on Computer Communications. IEEE, 2008, pp. 1049-1057.
[81] M. Costa, M. Castro, R. Rowstron, P. Key, PIC: practical Internet coordinates for distance estimation, in Distributed Computing Systems, 2004. Proceedings. 24th International Conference on, 2004, pp. 178-187.
[82] A. Ittai, M. Dahlia, D. Oren, LAND: stretch (1+\&\#949;) locality-aware networks for DHTs, in Proceedings of the fifieenth annual ACM-SLAM symposium on Discrete algorithms New Orleans, Louisiana: Society for Industrial and Applied Mathematics, 2004, pp. 550-559.
[83] H. Kirsten, D. K. John, R. Satish, Y. Z. Ben, Distributed object location in a dynamic network, in Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures Winnipeg, Manitoba, Canada: ACM, 2002, pp. 41-52.
[84] R. K. David, R. Matthias, Finding nearest neighbors in growth-restricted metrics, in Proceedings of the thiry-fourth annual ACM symposium on Theory of computing Montreal, Quebec, Canada: ACM, 2002, pp. 741-750.
[85] J. Stribling, K. Hildrum, J. D. Kubiatowicz, Optimizations for Locality-Aware Structured Peer-to-Peer Overlays, Computer Science Division (EECS), University of California Berkeley, UCB/CSD-03-1266, 2003.
[86] S. Ratnasamy, M. Handley, R. Karp, S. Shenker, Topologically-aware overlay construction and server selection, in INFOCOM 2002. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, 2002.
[87] F. Dabek, R. Cox, F. Kaashoek, R. Morris, Vivaldi: a decentralized network coordinate system, ACMSIGCOMM Computer Communication Review, vol. 34, pp. 15-26, 2004.
[88] T. S. E. Ng, Z. Hui, Predicting Internet network distance with coordinates-based approaches, in INFOCOM 2002. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, 2002, pp. 170-179 vol.1.
[89] Z. Yong, C. Dovrolis, M. Ammar, Combining Multihoming with Overlay Routing (or, How to Be a Better ISP without Owning a Network), in INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE, 2007, pp. 839-847.
[90] A. Gupta, B. Liskov, R. Rodrigues, Efficient routing for peer-to-peer overlays, in Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation - Volume 1 San Francisco, California: USENIX Association, 2004, pp. 9-9.
[91] I. Gupta, K. Birman, P. Linga, A. Demers, R. van Renesse, Kelips: Building an Efficient and Stable P2P DHT through Increased Memory and Background Overhead, in Peer-to-peer Systems:International Workshop, IPTPS'02, 2003.
[92] B. Leong, J. Li, Achieving one-hop DHT lookup and strong stabilization by passing tokens, in Networks, 2004. (ICON 2004). Proceedings. 12th IEEE International Conference on, 2004, pp. 344-350 vol. 1.
[93] A. Gupta, B. Liskov, R. Rodrigues, One hop lookups for peer-to-peer overlays, in Proceedings of the 9th conference on Hot Topics in Operating Systems - Volume 9 Lihue, Hawaii: USENIX Association, 2003, pp. 2-2.
[94] J. Risson, A. Harwood, T. Moors, Stable High-Capacity One-Hop Distributed Hash Tables, in Computers and Communications, 2006. ISCC'06. Proceedings. 11th IEEE Symposium on, 2006, pp. 687-694.
[95] Q. Lian, W. Chen, Z. Zhang, S. Wu, B. Y. Zhao, Z-Ring: Fast Prefix Routing via a Low Maintenance Membership Protocol, in 13th IEEE International Conference on Network Protocols, ICNP'05, 2005, pp. 132-146.
[96] J. Buford, A. Brown, M. Kolberg, Analysis of an Active Maintenance Algorithm for an O(1)-Hop Overlay, in Global Telecommunications Conference, 2007. GLOBECOM '07. IEEE, 2007, pp. 81-86.
[97] C. Tang, M. J. Buco, R. N. Chang, S. Dwarkadas, L. Z. Luan, E. So, C. Ward, Low traffic overlay networks with large routing tables, ACM SIGMETRICS Performance Evaluation Review, vol. 33, pp. 14-25, 2005.
[98] K. Sripanidkulchai, The popularity of Gnutella queries and its implications on scalability: http://www.cs.cmu.edu/～kunwadee/research/p2p/gnutella.html, 2001.
[99] C. Chen, K.-C. Tsai, The Server Reassignment Problem for Load Balancing in Structured P2P Systems, IEEE Trans. Parallel Distrib. Syst., vol. 19, pp. 234-246, 2008.
[100] D. R. Karger, M. Ruhl, Simple Efficient Load-Balancing Algorithms for Peer-to-Peer Systems, Theory of Computing Systems, vol. 39, pp. 787-804, 2006.
[101] A. Rao, K. Lakshminarayanan, S. Surana, R. Karp, I. Stoica, Load Balancing in Structured P2P Systems, in Peer-to-peer Systems:International Workshop, IPTPS'02, 2002.
[102] B. Godfrey, K. Lakshminarayanan, S. Surana, R. Karp, I. Stoica, Load Balancing in Dynamic Structured P2P Systems, in Proc. IEEE INFOCOM, 2004.
[103] P. B. Godfrey, I. Stoica, Heterogeneity and load balance in distributed hash tables, in Proc. IEEE INFOCOM, 2005.
[104] X. Wang, D. Loguinov, Load-balancing performance of consistent hashing: asymptotic analysis of random node join, IEEE/ACM Transactions on Networking (TON), vol. 15, pp. 892-905, 2007.
[105] M. Naor, U. Wieder, Novel architectures for P2P applications: The continuous-discrete approach, ACM Trans. Algorithms, vol. 3, p. 34, 2007.
[106] K. Kenthapadi, G. S. Manku, Decentralized algorithms using both local and random probes for P2P load balancing, in Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, 2005, pp. 135-144.
[107] G. Giakkoupis, V. Hadzilacos, A scheme for load balancing in heterogenous distributed hash tables, in Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing Las Vegas, NV, USA: ACM, 2005, pp. 302-311.
[108] E. Adar, B. Huberman, Free riding on gnutella, First Monday, 2000.
[109] G. Hardin, The Tragedy of the Commons, Science, vol. 162, pp. 1243-1248, 1968.
[110] K. Aberer, Z. Despotovic, Managing trust in a peer-2-peer information system, in Proceedings of the tenth international conference on Information and knowledge management, 2001, pp. 310-317.
[111] F. Cornelli, E. Damiani, S. D. C. di Vimercati, S. Paraboschi, P. Samarati, Choosing reputable servents in a P2P network, in Proceedings of the 11th international conference on World Wide Web, 2002, pp. 376-386.
[112] E. Damiani, S. Paraboschi, P. Samarati, F. Violante, A reputation-based approach for choosing reliable resources in peer-to-peer networks, in Proceedings of the 9th ACM conference on Computer and communications security, 2002, pp. 207-216.
[113] D. Fahrenholtz, W. Lamersdorf, Transactional Security for a Distributed Reputation Management System, in E-Commerce and Web Technologies, 2002, pp. 259-260.
[114] C. Liau, X. Zhou, S. Bressan, K.-L. Tan, Efficient Distributed Reputation Scheme for Peer-to-Peer Systems, in Web and Communication Technologies and Internet-Related Social Issues - HSI 2003, 2003, pp. 172-172.
[115] S. D. Kamvar, M. T. Schlosser, H. Garcia-Molina, The Eigentrust algorithm for reputation management in P2P networks, in Proceedings of the 12th international conference on World Wide Web, 2003, pp. 640-651.
[116] P. Resnick, R. Zeckhauser, Trust Among Strangers in Interact Transactions: Empirical Analysis of eBay's Reputation System, The Economics of the Internet and E-Commerce, vol. 11, pp. 23-25, 2002.
[117] L. Mui, M. Mohtashemi, A. Halberstadt, A computational model of trust and reputation, in Proceedings of the 35th Hawaii International Conference on System Sciences, 2002, pp. 188-196.
[118] A. Jφsang, R. Ismail, The beta reputation system, in Proceedings of the 15th Bled Electronic Commerce Conference, 2002, pp. 324-337.
[119] A. Whitby, A. Jφsang, J. Indulska, Filtering out unfair ratings in bayesian reputation systems, The Icfain Journal of Management Research, vol. 4, pp. 48-64, 2005.
[120] R. Ismail, C. Boyd, A. Jφsang, S. Russel, Strong Privacy in Reputation Systems, in Proceedings of the 4th International Workshop on Information Security Applications (WISA), 2003.
[121] J. Sabater, C. Sierra, Reputation and social network analysis in multi-agent systems, in Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 1, 2002, pp. 475-482.
[122] E. J. Friedman, P. Resnick, The Social Cost of Cheap Pseudonyms, Journal of Economics & Management Strategy, vol. 10, pp. 173-199, 2001.
[123] M. Feldman, J. Chuang, Overcoming free-riding behavior in peer-to-peer systems, ACM SIGecom Exchanges, vol. 5, pp. 41-50, 2005.
[124] J. Andreoni, Giving with Impure Altruism: Applications to Charity and Ricardian Equivalence, The Journal of Political Economy, vol. 97, p. 1447, 1989.
[125] V. Vishnumurthy, S. Chandrakumar, E. G. Sirer, Karma: A secure economic framework for peer-to-peer resource sharing, in Workshop on Economics of Peer-to-Peer Systems, 2003.
[126] K. Walsh, E. G. Sirer, Experience with an object reputation system for peer-to-peer filesharing, in USENIX NSDI, 2006.
[127] B. Cohen, Incentives Build Robustness in BitTorrent, in Workshop on Economics of Peer-to-Peer Systems, 2003.
[128] D. Qiu, R. Srikant, Modeling and performance analysis of BitTorrent-like peer-to-peer networks, in Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, 2004, pp. 367-378.
[129] L. Guo, S. Chen, Z. Xiao, E. Tan, X. Ding, X. Zhang, Measurements, analysis, and modeling of BitTorrent-like systems, in Proceedings of the 5th ACM SIGCOMM conference on Internet measurement, 2005.
[130] M. Piatek, T. Isdal, T. Anderson, A. Krishnamurthy, A. Venkataramani, Do incentives build robustness in BitTorrent, in Proc. of NSDI, 2007.
[131] D. Levin, K. LaCurts, N. Spring, B. Bhattacharjee, Bittorrent is an auction: analyzing and improving bittorrent's incentives, SIGCOMM Comput. Commun. Rev., vol. 38, pp. 243-254, 2008.
[132] V. King, J. Saia, Choosing a random peer, in Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, 2004, pp. 125-130.
[133] V. King, S. Lewis, J. Saia, M. Young, Choosing a Random Peer in Chord, Algorithmica, vol. 49, pp. 147-169, 2007.
[134] C. Scheideler, How to spread adversarial nodes?: rotate!, in Proceedings of the thirty-seventh annual ACM symposium on Theory of computing Baltimore, MD, USA: ACM, 2005, pp. 704-713.
[135] M. Castro, P. Druschel, Y. C. Hu, A. Rowstron, Proximity neighbor selection in tree-based structured peer-to-peer overlays, Microsoft Research MSR-TR-2003-52, 2003.
[136] J. Schmidt, A. Siegel, A. Srinivasan, Chernoff-Hoeffding bounds for applications with limited independence, 1993, pp. 331-340.
[137] J. Aspnes, Z. Diamadi, G. Shah, Fault-tolerant routing in peer-to-peer systems, in Proceedings of the twenty-first annual symposium on Principles of distributed computing, 2002, pp. 223-232.
[138] J. S. Kong, J. S. A. Bridgewater, V. P. Roychowdhury, A General Framework for Scalability and Performance Analysis of DHT Routing Systems, in Proceedings of the International Conference on Dependable Systems and Networks: IEEE Computer Society, 2006.
[139] 徐全智，吕恕，概率论与数理统计，高等教育出版社，2004．
[140] 毛用才，胡奇英，随机过程，西安，西安电子科技大学出版社，1998．
[141] 盛骤，谢式千，潘承毅，概率论与数理统计，高等教育出版社，1989．
[142] 格涅坚科(苏)，概率论教程，人民教育出版社，1956．
[143] 贺德化，概率论与数理统计网络课程，高等教育出版社，2004．
[144] S. Saroiu, P. K. Gummadi, S. D. Gribble, A measurement study of peer-to-peer file sharing systems, in Proceedings of Multimedia Computing and Networking, 2002.
[145] J. Kubiatowicz, D. Bindel, Y. Chen, S. Czerwinski, P. Eaton, D. Geels, R. Gummadi, S. Rhea, H. Weatherspoon, C. Wells, OceanStore: an architecture for global-scale persistent storage, ACM SIGARCH Computer Architecture News, vol. 28, pp. 190-201, 2000.
[146] G. S. Manku, Balanced binary trees for ID management and load balance in distributed hash tables, in Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing St. John's, Newfoundland, Canada: ACM, 2004, pp. 197-205.
[147] M. Adler, E. Halperin, R. M. Karp, V. V. Vazirani, A stochastic process on the hypercube with applications to peer-to-peer networks, in Proceedings of the thirty-fifth annual ACM symposium on Theory of computing San Diego, CA, USA: ACM, 2003, pp. 575-584.
[148] R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, Lambert's W function in Maple, Maple Technical Newsletter, vol. 9, pp. 12-22, 1993.
[149] S. M. Ross, Introduction to Probability Models, 9 ed., Elsevier (Singapore) Pte Ltd., 2007.
[150] A. Ghodsi, L. O. Alima, S. Haridi, Symmetric Replication for Structured Peer-to-Peer Systems, LECTURE NOTES IN COMPUTER SCIENCE, vol. 4125, p. 74, 2007.
[151] P. Wang, J. Tyra, E. Chan-Tin, T. Malchow, D. F. Kune, N. Hopper, Y. Kim, Attacking the Kad network, in Proceedings of the 4th international conference on Security and privacy in communication netowrks, SecureComm 2008, Istanbul, Turkey: ACM, 2008, pp. 1-10.
[152] A. Singh, T. W. Ngan, P. Druschel, D. S. Wallach, Eclipse Attacks on Overlay Networks: Threats and Defenses, in INFOCOM 2006. 25th IEEE International Conference on Computer Communications. Proceedings, 2006, pp. 1-12.
[153] J. Liang, N. Naoumov, K. W. Ross, The Index Poisoning Attack in P2P File Sharing Systems, in INFOCOM 2006. 25th IEEE International Conference on Computer Communications. Proceedings, 2006, pp. 1-12.
[154] S. Ryu, K. Butler, P. Traynor, P. McDaniel, Leveraging Identity-Based Cryptography for Node ID Assignment in Structured P2P Systems, in Proceedings of the 21st International Conference on Advanced Information Networking and Applications Workshops- Volume 01, 2007, pp. 519-524.
[155] L. M. Aiello, M. Milanesio, G. Ruffo, R. Schifanella, Tempering Kademlia with a Robust Identity Based System, in Peer-to-Peer Computing, 2008. P2P'08. Eighth International Conference on, 2008, pp. 30-39.
[156] 聂晓文，卢显良，唐晖，赵志军，李玉军，基于洗牌策略的Sybil攻击防御，电子学报，Vol．36，pp．2144-2149，2008．
[157] H. Rowaihy, W. Enck, P. McDaniel, T. La Porta, Limiting sybil attacks in structured p2p networks, in 26th IEEE International Conference on Computer Communications (INFOCOM), 2007, pp. 2596-2600.
[158] R. Bazzi, G. Konjevod, On the establishment of distinct identities in overlay networks, Distributed Computing, vol. 19, pp. 267-287, 2007.
[159] H. Yu, M. Kaminsky, P. B. Gibbons, A. D. Flaxman, SybilGuard: Defending Against Sybil Attacks via Social Networks, IEEE/ACM Transactions on Networking (TON), vol. 16, pp. 576-589, 2008.
[160] T. Condie, V. Kacholia, S. Sankararaman, J. Hellerstein, P. Maniatis, Induced Churn as Shelter from Routing-Table Poisoning, in Proceedings of Network and Distributed System Security Symposium, San Diego, California, USA, 2006.
[161] B. Awerbuch, C. Scheideler, Towards a scalable and robust DHT, in Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures Cambridge, Massachusetts, USA: ACM, 2006, pp. 318-327.
[162] W. Feller, An Introduction to Probability Theory and Its Applications. Volume I, John Wiley & Sons, 1951.
[163] A. F. Siegel, L. Holst, Covering the Circle with Random Arcs of Random Sizes, Journal of Applied Probability, vol. 19, pp. 373-381, 1982.
[164] C. Domb, Covering by random intervals and one-dimensional continuum percolation, Journal of Statistical Physics, vol. 55, pp. 441-460, 1989.
[165] L. Zhou, F. B. Schneider, R. Van Renesse, COCA: A Secure Distributed Online Certification Authority, ACM Transactions on Computer Systems (TOCS), vol. 20, pp. 329-368, 2002.
[166] K. Horowitz, D. Malkhi, Estimating network size from local information, Information Processing Letters, vol. 88, pp. 237-243, 2003.
[167] M. Bawa, H. Garcia-Molina, A. Gionis, R. Motwani, Estimating aggregates on a peer-to-peer network, Technical Stanford, 2004.
[168] L. Massouli, E. L. Merrer, A.-M. Kermarrec, A. Ganesh, Peer counting and sampling in overlay networks: random walk methods, in Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing Denver, Colorado, USA: ACM, 2006, pp. 123-132.
[169] D. Kostoulas, D. Psaltoulis, I. Gupta, K. Birman, A. Demers, Decentralized Schemes for Size Estimation in Large and Dynamic Groups, in Network Computing and Applications, Fourth IEEE International Symposium on, 2005, pp. 41-48.
[170] D. Psaltoulis, D. Kostoulas, I. Gupta, K. Birman, A. Demers, Practical algorithms for Size estimation in Large and Dynamic groups, in the 26th Annual International Conference on Software Engineering (ICSE 2004), Edinburgh, Scotland.PODC'04, 2004, pp. 2-2.
[171] E. Le Merrer, A. M. Kermarrec, L. Massoulie, Peer to peer size estimation in large and dynamic networks: A comparative study, in Proceedings of the IEEE International Symposium on High Performance Distributed Computing (HPDC), 2006.
[172] S. Mane, S. Mopuru, K. Mehra, J. Srivastava, Network Size Estimation In A Peer-to-Peer Network, University of Minnesota TR 05-030, September 15 2005.
[173] G. S. Manku, Routing networks for distributed hash tables, in Proceedings of the twenty-second annual symposium on Principles of distributed computing, 2003, pp. 133-142.
[174] T. Shafaat, A. Ghodsi, S. Haridi, A Practical Approach to Network Size Estimation for Structured Overlays, in Self-Organizing Systems, 2008, pp. 71-83.
[175] C. Gkantsidis, M. Mihail, A. Saberi, Random walks in peer-to-peer networks, in INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies, 2004.
[176] P. Francis, Yoid: Extending the interact multicast architecture, White Paper, http://www.cs.wisc.edu/～suman/pubs.html, 2002.
[177] M. Faloutsos, P. Faloutsos, C. Faloutsos, On power-law relationships of the Internet topology, in Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, 1999, pp. 251-262.
[178] V. Vishnumurthy, P. Francis, On Heterogeneous Overlay Construction and Random Node Selection in Unstructured P2P Networks, in INFOCOM 2006. 25th IEEE International Conference on Computer Communications. Proceedings, 2006, pp. 1-12.
[179] V. Vishnumurthy, P. Francis, A comparison of structured and unstructured P2P approaches to heterogeneous random peer selection, in 2007 USENIX Annual Technical Conference on Proceedings of the USENIX Annual Technical Conference Santa Clam, CA: USENIX Association, 2007, pp. 1-14.
[180] G. E. Forsythe, Von Neumann's comparison method for random sampling from the normal and other distributions, Math. Comp, vol. 26, pp. 817-826, 1972.
[181] J. A. Grzesik, Von Neumann's Rejection Technique Reexamined, SlAM Review, vol. 31, p. 486, 1989.
[182] V. Neumann, Various Techniques Used in Connection with Random Digits, Applied Mathematics, vol. Series 12, pp. 36-38, 1951.
[183] P. R. Tadikamalla, Random Sampling from the Exponential Power Distribution Journal of the American Statistical Association, vol. Vol. 75, pp. 683-686 1980.
[184] P. R. Tadikamalla, Random sampling from the generalized gamma distribution Computing, vol. Volume 23, pp. 199-203, 1979.
[185] D. Knuth, Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd Edition), Addison-Wesley Professional, 1997.
[186] 吕英华，计算电磁学的数值方法，1 ed．，北京，清华大学出版社，2006．
[187] A. Rukhin, J. Soto, J. Nechvatal, M. Smid, E. barker, S. Leigh, M. Levenson, M. Vangel, D. Banks, A. Heckert, J. Dray, S. Vo, A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptgraphic Applications, NIST Special Publication May 15 2001.
[188] 何朝兵，田彦伟，顺序统计量的分布，成都大学学报(自然科学版)Vol．27，pp．116-119，2008．