現今大型分散式系統中，有著百萬數量級以上的計算節點，如Google及Facebook。這些運算節點分布在世界各地，並且動態的加入或是離開系統。一般來說，大型分散式系統中的節點之間的通訊的設計是先透過疊蓋式網路再經由底層的實體網路(如，網際網路)來傳遞訊息。疊蓋式網路是一個應用層的網路，網路上任兩點的邊線代表邏輯上的鄰居關係，在疊蓋式網路上的節點是訊息傳遞上的接受者與發送者。
這類系統中通常執行著許多各式各樣的的應用程式(如資料庫，檔案系統)，這些應用程式會產生大量的查詢運算，查詢的訊息透過疊蓋式網路的傳遞來服務使用者，是系統中重要的負載。然而由於節點可以動態的進出系統，加上不同的應用在系統中執行，造成負載的不平均進而影響系統的效能。傳統的方法是用集中式的管理來最佳化這些大量的查詢，然而在這樣的大型動態的系統中是不實際的。因此，本篇論文提出具有效能保證的分散式查詢負載最佳化演算法來提升系統的效能，其中包括設計最佳化疊蓋式網路的繞路及查詢負載的平衡。
我們在這篇論文嘗試著解決因為動態環境所產生的疊蓋式網路拓譜不匹配及系統負載不平衡的問題。在解決拓樸不匹配的問題上，我們提出動態修改網路拓樸的演算法來最小化查詢的延遲。我們的方法透過在疊蓋式網路在系統中取樣來得到部份的資訊（如傳輸延遲的分佈）進而調整疊蓋式網路的拓墣結構。另一方面，我們提出負載平衡演算法來平均的分配查詢的工作量。其中，每個系統節點透過收集系統部分的資訊來估計負載的分布概況，基於這些資訊低負載的系統節點得以有效地向高負載的節點提出要求來轉移負載。
論文中所提出的演算法皆是建構在數學的理論基礎之上，在拓撲調整的問題上分析結果顯示我們的方法在兩點之間的延遲可以有效能上的保證，也就是兩個節點之間在疊蓋式網路上的延遲與兩點間在實體網路的延遲有很高的機率是相同的。在處理負載不平衡的問題方面，我們的負載平衡演算法得使得節點的負載正比於與其計算或儲存能力。我們也透過電腦模擬來與文獻中的研究比較，結果顯示我們的方法明顯優於過去的方案。

Large-scale distributed systems have been widely deployed for numerous applications, and typically used to store enormous data. In general, such systems consist of a great number of serving nodes (e.g., $>10^5$ or $>10^6$). The serving nodes are geographically distributed and can be distant. They may constantly join and leave. It is clearly not pragmatic (even impossible) to simply rely on any central entity for processing queries in such environments. Having an effective and efficient query processing in a distributed manner is thus a challenging task.

This dissertation aims at optimizing query routing and balancing query workload in dynamic and distributed large-scale systems. We address the issues of topology mismatching and load imbalance due to constantly changing system environment and query workload. To attack the topology mismatch problem, we suggest algorithms restructuring network topologies on the fly to minimize latencies of resolving queries. Our proposals demand only participating nodes to gather local knowledge while offering performance guarantees. On the other hand, to evenly balance the query workload, two algorithms are proposed to redistribute query traffic to serving nodes. As each node independently investigating the workload distribution of the system based on partial system information, the underloaded node request loads from heavy participants in a distributed manner.

Compared with prior efforts, the proposals presented in this study are effective and efficient, that are not only evaluated by rigorous mathematical analysis, but validated in extensive computer simulations.

[1] J. Chu, K. Labonte, and B. N. Levine, "Availability and Locality Measurements
of Peer-to-Peer File Systems," in Proc. SPIE|ITCom: Scalability and Tra±c
Control in IP Networks, July 2002, pp. 310{321.
[2] BitTorrent, http://www.bittorrent.org/index.html.
[3] Shareaza, http://shareaza.sourceforge.net/.
[4] iMesh, http://www.imesh.com/.
[5] Gnutella, [online] http://rfc-gnutella.sourceforge.net/.
[6] X. Liao, H. Jin, Y. Liu, and L. M. Ni, "Scalable Live Streaming Service Based
on Interoverlay Optimization," IEEE Transactions on Parallel and Distributed
Systems, vol. 18, no. 12, pp. 1663{1674, Dec. 2007.
[7] S. Xie, B. Li, G. Y. Keung, and X. Zhang, "Coolstreaming: Design, Theory, and
Practice," IEEE Transactions on Multimedia, vol. 9, no. 8, pp. 1661{1671, Dec.
2007.
[8] X. Tu, H. Jin, X. Liao, and J. Cao, "Nearcast: A Locality-Aware P2P Live Stream-
ing Approach for Distance Education," ACM Transactions on Internet Technology,
vol. 8, no. 2, pp. 1{23, Feb. 2008.
[9] PPS, http://www.pps.tv/.
[10] HBase, http://http://hbase.apache.org/.
113
[11] A. Lakshman and P. Malik, "Cassandra: A Decentralized Structured Storage
System," ACM SIGOPS Operating Systems Review, vol. 44, no. 2, pp. 35{40,
Apr. 2010.
[12] I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan, "Chord: A
Scalable Peer-to-Peer Lookup Service for Internet Applications," in Proceedings of
the 2001 Conference on Applications, Technologies, Architectures, and Protocols
for Computer Communications, Aug. 2001, pp. 149{160.
[13] D. Kempe, J. Kleinberg, and A. Demers, "Spatial Gossip and Resource Location
Protocols," Journal of the ACM, vol. 51, no. 6, pp. 943{967, Nov. 2004.
[14] R. Ranjan, A. Harwood, and R. Buyya, "Peer-to-peer-based resource discovery in
global grids: a tutorial," IEEE Communications Surveys and Tutorials, vol. 10,
no. 2, pp. 6{33, Apr. 2008.
[15] I. Chang-Yen, D. Smith, and N.-F. Tzeng, "Structured Peer-to-Peer Resource
Discovery for Computational Grids," in Proceedings of the 15th ACM Mardi Gras
conference, 2008, pp. 6:1{6:8.
[16] S. S. Lam and H. Liu, "Failure Recovery for Structured P2P Networks: Protocol
Design and Performance Evaluation," ACM SIGMETRICS Performance Evalua-
tion Review, vol. 32, no. 1, pp. 199{210, Jun. 2004.
[17] P. Roy, S. Haridi, A. Reinefeld, J.-B. Stefani, R. Yap, and T. Coupaye, "Self
Management for Large-Scale Distributed Systems: An Overview of the SELFMAN
Project," in Formal Methods for Components and Objects, F. S. Boer, M. M.
Bonsangue, S. Graf, and W.-P. Roever, Eds. Berlin, Heidelberg: Springer-Verlag,
2008, pp. 153{178.
[18] K. Aberer, P. Cudr¶e-Mauroux, A. Datta, Z. Despotovic, M. Hauswirth,
M. Punceva, and R. Schmidt, "P-Grid: A Self-organizing Structured P2P sys-
tem," SIGMOD Record, vol. 32, no. 3, pp. 29{33, Sep. 2003.
[19] S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker, "A Scalable
Content-Addressable Network," in Proceedings of the 2001 Conference on Applica-
114
tions, Technologies, Architectures, and Protocols for Computer Communications,
Aug. 2001, pp. 161{172.
[20] A. Rowstron and P. Druschel, "Pastry: Scalable, Distributed Object Location and
Routing for Large-Scale Peer-to-Peer Systems," IFIP/ACM International Confer-
ence on Distributed Systems Platforms, pp. 161{172, Nov. 2001.
[21] Y. Liu, L. Xiao, X. Liu, L. M. Ni, and X. Zhang, "Location Awareness in Un-
structured Peer-to-Peer Systems," IEEE Transactions on Parallel and Distributed
Systems, vol. 12, no. 2, pp. 163{174, Feb. 2005.
[22] Y. Liu, "A Two-Hop Solution to Solving Topology Mismatch," IEEE Transactions
on Parallel and Distributed Systems, vol. 19, no. 11, pp. 1591{1600, Nov. 2008.
[23] K.-C. Li, C.-H. Hsu, L. T. Yang, J. Dongarra, and H. Zima, Handbook of Research
on Scalable Computing Technologies. IGI Global, July 2009, ch. Load Balancing
in Peer-to-Peer Systems, pp. 163{190.
[24] H. Shen and C.-Z. Xu, "Locality-Aware and Churn-Resilient Load-balancing Al-
gorithms in Structured Peer-to-Peer Networks," IEEE Transactions on Parallel
and Distributed Systems, vol. 18, no. 6, pp. 849{862, June 2007.
[25] B. Y. Zhao, L. Huang, J. Stribling, S. C. Rhea, A. D. Joseph, and J. D. Kubi-
atowicz, "Tapestry: A Resilient Global-Scale Overlay for Service Deployment,"
IEEE Journal on Selected Areas in Communications, vol. 22, no. 1, pp. 41{53,
Jan. 2004.
[26] M. Ripeanu, L. Foster, and A. Iamnitchi, "Mapping the Gnutella Network," IEEE
Internet Computing, vol. 6, no. 1, pp. 50{57, Jan./Feb. 2002.
[27] S. Sen and J. Wang, "Analyzing Peer-to-Peer Tra±c Across Large Networks,"
IEEE/ACM Transactions on Networking, vol. 12, no. 2, pp. 219{232, Apr. 2004.
[28] H.-C. Hsiao, H. Liao, and C.-C. Huang, "Resolving the Topology Mismatch Prob-
lem in Unstructured Peer-to-Peer Networks," IEEE Transactions on Parallel and
Distributed Systems, vol. 20, pp. 1668{1681, Feb. 2009.
115
[29] H.-C. Hsiao, H. Liao, and P.-S. Yeh, "A Near-Optimal Algorithm Attacking
the Topology Mismatch Problem in Unstructured Peer-to-Peer Networks," IEEE
Transactions on Parallel and Distributed Systems, vol. 21, no. 7, pp. 983{997, Jul.
2010.
[30] C. Law and S. Kai-Yeung, "Distributed Construction of Random Expander Net-
works," in Twenty-Second Annual Joint Conference of the IEEE Computer and
Communications. IEEE Societies, Mar. 2003, pp. 2133{2143.
[31] G. Pandurangan, P. Raghavan, and E. Upfal, "Building Low-Diameter Peer-to-
Peer Networks," IEEE Journal on Selected Areas in Communications, vol. 21,
no. 6, pp. 995{1002, Aug. 2003.
[32] M. K. Reiter, A. Samar, and C. Wang, "Distributed Construction of a Fault-
Tolerant Network from a Tree," in Proceedings of the 24th IEEE Symposium on
Reliable Distributed Systems, Oct. 2005, pp. 155{165.
[33] Y. Liu, L. Xiao, and L. M. Ni, "Building a Scalable Bipartite P2P Overlay Net-
work," IEEE Transactions on Parallel and Distributed Systems, vol. 18, no. 9, pp.
1296{1306, Sept. 2007.
[34] J. M. Kleinberg, "Navigation in a Small World," Nature, vol. 406, no. 6798, p.
845, Aug. 2000.
[35] S. Milgram, "The Small-world Problem," Psychology Today, vol. 2, pp. 60{67,
1967.
[36] D. J. Watts and S. H. Strogatz, "Collective Dynamics of Small-World Networks,"
Nature, vol. 393, no. 6684, pp. 440{442, June 1998.
[37] S. Merugu, S. Srinivasan, and E. Zegura, "Adding Structure to Unstructured
Peer-to-Peer Networks: The Use of Small-World Graphs," Journal of Parallel
Distributed Computing, vol. 65, no. 2, pp. 142{153, Feb. 2005.
[38] J. Kleinberg, "The Small-World Phenomenon: An Algorithm Perspective," in Pro-
ceedings of the Thirty-second Annual ACM Symposium on Theory of Computing,
May 2000, pp. 163{170.
116
[39] V. N. Padmanabhan and L. Subramanian, "An Investigation of Geographic Map-
ping Techniques for Internet Hosts," in Proceedings of the 2001 Conference on
Applications, Technologies, Architectures, and Protocols for Computer Communi-
cations, Aug. 2001, pp. 173{185.
[40] T. S. E. Ng and H. Zhang, "Predicting Internet Network Distance with
Coordinates-Based Approaches," in Proceedings of the Twenty-First Annual Joint
Conference of the IEEE Computer and Communications Societies, June 2002, pp.
170{179.
[41] S. Ratnasamy, M. Handley, R. Karp, and S. Shenker, "Topologically-Aware Over-
lay Construction and Server Selection," in Twenty-First Annual Joint Conference
of the IEEE Computer and Communications Societies. Proceedings. IEEE, June
2002, pp. 1190{1199.
[42] Q. Tongqing, G. Chen, M. Ye, E. Chen, and B. Y. Zhao, "Towards Location-Aware
Topology in Both Unstructured and Structured P2P Systems," in Proceedings of
the 2007 International Conference on Parallel Processing, Sept. 2007, p. 30.
[43] X. Y. Zhang, Q. Zhang, Z. Zhang, G. Song, and W. Zhu, "A Construction of
Locality-Aware Overlay Network: MOverlay and Its Performance," IEEE Journal
on Selected Areas in Communications, vol. 18, no. 28, pp. 995{1002, Jan. 2004.
[44] L. Lov¶asz, "Random Walks on Graphs: A Survey," Combinatorics, Paul Erd¶'os
is Eighty, vol. 2, no. 1, pp. 1{46, 1993.
[45] M. Mitzenmacher and E. Upfal, Probability and Computing: Randomized Algo-
rithms and Probabilistic Analysis. New York, NY, USA: Cambridge University,
2005, ch. Coupling of Markov Chains, pp. 271{294.
[46] V. King and J. Saia, "Choosing a Random Peer," in Proceedings of the Twenty-
third Annual ACM Symposium on Principles of Distributed Computing, July 2004,
pp. 125{130.
[47] Z. Xu, M. Mahalingam, and M. Karlsson, "Turning Heterogeneity Into An Ad-
vantage in Overlay Routing," in Proceedings of the Twenty-Second Annual Joint
117
Conference of the IEEE Computer and Communications, Mar. 2003, pp. 1499{
1509.
[48] Y. Zhu and Y. Hu, "E±cient, Proximity-Aware Load Balancing for DHT-Based
P2P Systems," IEEE Transactions on Parallel and Distributed Systems, vol. 16,
no. 4, pp. 349{361, Apr. 2005.
[49] H. Zhang, A. Goel, and R. Govindan, "An Empirical Evaluation of Internet La-
tency Expansion," ACM SIGCOMM Computer Communication Review, vol. 35,
no. 1, pp. 93{97, Jan. 2004.
[50] D. R. Karger and M. Ruhl, "Finding Nearest Neighbors in Growth-Restricted
Metrics," in Proceedings of the Thiry-fourth Annual ACM Symposium on Theory
of Computing, May 2002, pp. 741{750.
[51] PlanetLab, http://www.planet-lab.org/.
[52] S. Saroiu, K. P. Gummadi, and S. D. Gribble, "A Measurement Study of Peer-
to-Peer File Sharing Systems," in Proceedings of Multimedia Computing and Net-
working 2002, Jan. 2002, pp. 10{10.
[53] Napster, http://www.napster.com/.
[54] K. P. Gummadi, R. J. Dunn, S. Saroiu, S. D. Gribble, H. M. Levy, and J. Zahorjan,
"Measurement, Modeling, and Analysis of a Peer-to-Peer File-sharing Workload,"
in Proceedings of the Nineteenth ACM Symposium on Operating Systems Princi-
ples, Oct. 2003, pp. 314{329.
[55] S. Jin and H. Jiang, "Novel Approaches to E±cient Flooding Search in Peer-to-
Peer Networks," Computer Networks: The International Journal of Computer and
Telecommunications Networking, vol. 51, no. 10, pp. 2818{2832, July 2007.
[56] W. Aiello, F. Chung, and L. Lu, "A Random Graph Model for Massive Graphs,"
in Proceedings of the Thirty-second Annual ACM Symposium on Theory of Com-
puting, May 2000, pp. 171{180.
118
[57] G. Phillips, S. Shenker, and H. Tangmunarunkit, "Scaling of Multicast Trees:
Comments on the Chuang-Sirbu Scaling Law," ACM SIGCOMM Computer Com-
munication Review, vol. 29, no. 4, pp. 41{51, Oct. 1999.
[58] H. Tangmunarunkit, R. Govindan, S. Jamin, S. Shenker, and W. Willinger, "Net-
work Topology Generators: Degree-Based Vs. Structural," in Proceedings of the
2002 Conference on Applications, Technologies, Architectures, and Protocols for
Computer Communications, Aug. 2002, pp. 147{159.
[59] C. G. Plaxton, R. Rajaraman, and A. W. Richa, "Accessing Nearby Copies of
Replicated Objects in a Distributed Environment," in Proceedings of the Ninth
Annual ACM Symposium on Parallel Algorithms and Architectures, June 1997,
pp. 311{320.
[60] Metropolis, Nicholas, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and
E. Teller, "Equations of State Calculations by Fast Computing Machines," Journal
of Chemical Physics, vol. 21, no. 6, pp. 1087{1092, June 1953.
[61] W. K. Hastings, "Monte Carlo Sampling Methods Using Markov Chains and Their
Applications," Biometrika, vol. 57, no. 1, pp. 97{109, Apr. 1970.
[62] S. M. Ross, Introduction to Probability Models, 9th ed. Orlando, FL, USA:
Academic Press, 2007, ch. Markov Chains, pp. 185{280.
[63] P. Diaconis and D. Stroock, "Geometric Bounds for Eigenvalues of Markov
Chains," The Annals of Applied Probability, vol. 1, no. 1, pp. 36{61, Feb. 1991.
[64] A. Sinclair, "Improved Bounds for Mixing Rates of Markov Chains and Multi-
commodity Flow," Combinatorics, Probability and Computing, vol. 1, no. 4, pp.
351{370, Dec. 1992.
[65] B. Bollob¶as, Random Graphs, 2nd ed. Cambridge University Press, 2001.
[66] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, "Optimization by Simulated An-
nealing," Science, vol. 220, no. 4598, pp. 671{680, May 1983.
119
[67] A. Medina, A. Lakhina, I. Matta, and J. Byers, "BRITE: An Approach to Univer-
sal Topology Generation," in Proceedings of the Ninth International Symposium in
Modeling, Analysis and Simulation of Computer and Telecommunication Systems,
Aug. 2001, pp. 346{353.
[68] B. Godfrey, K. Lakshminarayanan, S. Surana, R. Karq, and I. Stoica, "Load
Balancing in Dynamic Structured P2P Systems," Performance Evaluation, vol. 63,
no. 6, pp. 217{240, Mar. 2006.
[69] C. Chen and K.-C. Tsai, "The Server Reassignment Problem for Load Balanc-
ing in Structured P2P Systems," IEEE Transactions on Parallel and Distributed
Systems, vol. 12, no. 2, pp. 234{246, Feb. 2008.
[70] H.-C. Lin and C. S. Raghavendra, "A Dynamic Load-Balancing Policy with a Cen-
tral Job Dispatcher (LBC)," IEEE Transactions on Software Engineering, vol. 18,
no. 2, pp. 148{158, Feb. 1992.
[71] F. C. H. Lin and R. M. Keller, "The Gradient Model Load Balancing Method,"
IEEE Transactions on Software Engineering - Special Issue on Distributed Sys-
tems, vol. 13, no. 1, pp. 32{38, Jan. 1987.
[72] P. K. K. Loh, W. J. Hsu, C. Wentong, and N. Sriskanthan, "How Network Topol-
ogy A®ects Dynamic Load Balancing," IEEE Transactions on Software Engineer-
ing, vol. 11, no. 5, pp. 491{496, May 1985.
[73] L. M. Ni, H.-W. Xu, and T. B. Gendreau, "A Distributed Drafting Algorithm for
Load Balancing," IEEE Transactions on Software Engineering, vol. 11, no. 10, pp.
1153{1161, Oct. 1985.
[74] T. L. Casavant and J. G. Kuhl, "A Taxonomy of Scheduling in General-purpose
Distributed Computing Systems," IEEE Transactions on Software Engineering,
vol. 14, no. 2, pp. 141{154, Feb. 1988.
[75] Y. Zhu and Y. Hu, "Enhancing Search Performance on Gnutella-like P2P Sys-
tems," IEEE Transactions on Parallel and Distributed Systems, vol. 17, no. 12,
pp. 1482{1495, Dec. 2006.
120
[76] A. Bharambe, M. Agrawal, and S. Seshan, "Mercury: Supporting Scalable Multi-
Attribute Range Queries," in Proceedings of the ACM SIGCOMM, Aug. 2004, pp.
353{366.
[77] P. Ganesan, M. Bawa, and H. Garcia-Molina, "Online Balancing of Range-
Partitioned Data with Applications to Peer-to-Peer Systems," in Proceedings of
the Thirtieth International Conference on Very Large Data Bases, Sept. 2004, pp.
444{455.
[78] D. R. Karger and M. Ruhl, "Simple E±cient Load Balancing Algorithms for Peer-
to-Peer Systems," in Proceedings of the Sixteenth Annual ACM Symposium on
Parallelism in Algorithms and Architectures, June 2004, pp. 36{43.
[79] K. Kenthapadi and 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, July
2005, pp. 135{144.
[80] Q. H. Vu, B. C. Ooi, M. Rinard, and K.-L. Tan, "Histogram-Based Global Load
Balancing in Structured Peer-to-Peer Systems," IEEE Transactions on Knowledge
and Data Engineering, vol. 21, no. 4, pp. 595{608, Apr. 2009.
[81] A. Rao, K. Lakshminarayanan, S. Surana, R. Karp, and I. Stoica, "Load Balancing
in Structured P2P Systems," in Proceedings of the Second International Workshop
on Peer-to-Peer Systems, Feb. 2003, pp. 68{79.
[82] M. R. Garey and D. S. Johnson, Computers and Intractability; A Guide to the
Theory of NP-Completeness. New York, NY, USA: W.H. Freeman and Co.,
1979.
[83] N. L. Johnson and S. Kotz, Urn Models and Their Application: An Approach to
Modern Discrete Probability Theory. New York, NY, USA: John Wiley & Sons
Inc, 1977, ch. Occupancy and Related Problems, pp. 107{175.
121
[84] F. Dabek, M. F. Kaashoek, D. Karger, R. Morris, and I. Stoica, "Wide-Area
Cooperative Storage with CFS," in Proceedings of the Eighteenth ACM Symposium
on Operating Systems Principles, Oct. 2001, pp. 202{215.
[85] G. H. Gonnet, "Expected Length of the Longest Probe Sequence in Hash Code
Searching," Journal of the ACM, vol. 28, no. 2, pp. 289{304, Apr. 1981.
[86] D. Eastlake and P. Jones, "US Secure Hash Algorithm 1 (SHA1)," rFC 3174, Sept.
2001.
[87] L. Massouli¶e, E. Le Merrer, A.-M. Kermarrec, and A. Ganesh, "Peer Counting
and Sampling in Overlay Networks: Random Walk Methods," in Proceedings of
the Twenty-¯fth Annual ACM Symposium on Principles of Distributed Computing,
July 2006, pp. 123{132.
[88] M. Jelasity, A. Montresor, and O. Babaoglu, "Gossip-Based Aggregation in Large
Dynamic Networks," ACM Transactions on Computer Systems, vol. 23, no. 3, pp.
219{252, Aug. 2005.
[89] C. Gkantsidis, M. Mihail, and A. Saberi, "Random Walks in Peer-to-Peer Net-
works: Algorithms and Evaluation," Performance Evaluation - P2P Computing
Systems, vol. 63, no. 3, pp. 241{263, Mar. 2006.
[90] A. Dvoretzky, J. Kiefer, and J. Wolfowitz, "Asymptotic Minimax Character of
the Sample Distribution Function and of the Classical Multinomial Estimator,"
Annals of Mathematical Statistics, vol. 27, no. 3, pp. 642{669, 1956.
[91] M. Mitzenmacher and E. Upfal, Probability and Computing: Randomized Algo-
rithms and Probabilistic Analysis. New York, NY, USA: Cambridge, 2005.
[92] M. E. J. Newman, S. H. Strogatz, and D. J. Watts, "Random Graphs with Arbi-
trary Degree Distributions and Their Applications," Physical Review E, vol. 64,
no. 2, p. 026118, July 2001.
[93] H. Cherno®, "A Measure of Asymptotic E±ciency for Tests of a Hypothesis Based
on the Sum of Observations," Annals of Mathematical Statistics, vol. 23, no. 4,
pp. 493{507, 1952.
122
[94] H. Shen, C. Xu, and G. Chen, "Cycloid: A Scalable Constant-Degree Lookup-
E±cient P2P Overlay Network," Journal of Performance Evaluation's Special Is-
sue on Peer-to-Peer Networks, vol. 63, no. 3, pp. 195{216, Mar. 2006.
[95] L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker, "Web Caching and Zipf-
Like Distributions: Evidence and Implications," in Proceedings of the Eighteenth
Annual Joint Conference of the IEEE Computer and Communications Societies,
Mar. 1999, pp. 126-134.