隨著P2P網路的盛行，許多針對P2P網路應用的研究例如: 搜尋，整合以及路由被提出。為了使得這些應用能夠運作，網路大小是一個非常重要的總體資訊。
不像是中央管理式系統，P2P網路是個動態且規模變化大的系統；此外，在P2P網路中並沒有中央伺服器用來維護重要的資訊。這些特性使得網路大小變成不易取得的一項資訊。近年來，已經有研究提出如何取得一個估計值的解決辦法。然而，由於網路大小會不斷變動的特性，一次性的估計對於動態網路來說較不具實用價值。
因此，我們首先在三種較常見的網路拓墣上實做三個針對非結構P2P網路中估計網路大小的方法提出一份全面性的比較，並選出表現最好的一個方法作為基底提出兩個重要的改進。加入這些改進之後的方法可以準確地在這三種網路拓墣上實現大小的估計，並且在具有準確的延遲控制下能夠有效率地實現連續性網路大小的估計。最後我們呈現實驗的結果來驗證我們改進的成果。

As the applications over Peer-to-Peer (P2P) networks become more popular, lots of research has focused on the mechanisms of searching, aggregating and routing in P2P networks. To support these functions, estimating network size is vital for global information.
Unlike centralized systems, P2P networks are dynamic and scalable; besides, there is no server to maintain the information in P2P networks. These properties make the information about network size hard to obtain. In recent years, some research has addressed the mechanisms for getting the estimated size of unstructured P2P networks. However, a one-shot estimation is not practical when the network size is dynamic. As a result, we first provide
a comprehensive comparison among three related methods in three popular overlay graphs and then propose two modifications based on one of the methods. With our improvements, this modified method can function well in the three overlay graphs and continuously monitor
network size with precisely latency control. We present the experimental results to show our improvement over the one-shot estimation and the outcomes of latency control of
continuous estimation in dynamic networks.

Contents
Chinese Abstract ii
Abstract iii
Acknowledgement iv
List of Tables vii
List of Figures viii
1 Introduction 1
2 RELATEDWORK 3
3 PRELIMINARY STUDY 6
3.1 Size estimation methods overviews . . . . . . . . . . . . . . . . 7
3.2 Methods Comparison . . . . . . . . . . 8
3.2.1 Experimental environment . . . . . . 9
3.2.2 Evaluation Criteria .. . . . . . . . 10
3.2.3 Results Comparison . . .. . . . . . 10
3.2.4 Summary . . .. . . . . . . . . . . . 12
4 Methodology 16
4.1 Correct the inaccuracy problem in power-law graph . . . . . . . . . . . . . . . . . . .16
4.2 Continuous size estimation . . . . . . . . . . . . . . . . 18
4.2.1 Continuous solution . . .. . . . . . 18
5 EXPERIMENTAL EVALUATION 21
5.1 Evaluation results . . . . . . . . . . 21
5.1.1 Modified Sample&Collide . .. . . . . 22
5.1.2 Continuous estimation V.S. one-shot estimation . . . . . . . . . .. . . . . . .22
5.1.3 Latency control . . . . . . . . . . 22
6 Conclusion 26
References 27

[1] L. A. Adamic. The small world web. pages 443–452. Springer, 1999.
[2] L. A. Adamic, R. M. Lukose, A. R. Puniyani, and B. A. Huberman. Search in power-law
networks. Physical Review E, 64(4):046135+, Sep 2001.
[3] R. Z. Albert. Statistical mechanics of complex networks. PhD thesis, Notre Dame, IN, USA,
2001. Director-Barabasi,, Albert-Laszlo.
[4] B. Arai, G. Das, D. Gunopulos, and V. Kalogeraki. Efficient approximate query processing in
peer-to-peer networks. IEEE Transactions on Knowledge and Data Engineering, 19(7):919–
933, 2007.
[5] Bailey. Epidemic Theory of Infectious Diseases and its Applications, second ed. Hafner Press,
1975.
[6] S. P. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Gossip algorithms: design, analysis and
applications. In INFOCOM, pages 1653–1664, 2005.
[7] D. Dolev, O. Mokryn, and Y. Shavitt. On multicast trees: Structure and size estimation. In
INFOCOM, 2003.
[8] M. Faloutsos, P. Faloutsos, and C. Faloutsos. On power-law relationships of the internet
topology. In SIGCOMM ’99: Proceedings of the conference on Applications, technologies,
architectures, and protocols for computer communication, volume 29, pages 251–262, New
York, NY, USA, 1999. ACM Press.
[9] C. Gkantsidis, M. Mihail, and A. Saberi. Random walks in peer-to-peer networks. In 23rd
Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM
2004), volume 1, pages 120–130, 2004.
[10] S. A. Gupta, A. Gupta, D. Agrawal, and A. E. Abbadi. Approximate range selection queries
in peer-to-peer. In In CIDR, 2002.
[11] K. Horowitz and D. Malkhi. Estimating network size from local information. Inf. Process.
Lett., 88(5):237–243, 2003.
[12] K. Y. K. Hui, J. C. S. Lui, and D. K. Y. Yau. Small-world overlay p2p networks: Construction,
management and handling of dynamic flash crowds. Computer Networks, 50(15):2727–2746,
2006.
[13] M. Jelasity and A. Montresor. Epidemic-style proactive aggregation in large overlay networks.
pages 102–109, 2004.
[14] M. Jelasity, A. Montresor, and O. Babaoglu. Gossip-based aggregation in large dynamic
networks. ACM Trans. Comput. Syst., 23(3):219–252, 2005.
[15] M. Jelasity, A. Montresor, G. P. Jesi, and S. Voulgaris. The Peersim simulator.
http://peersim.sf.net.
[16] M. Jelasity and M. Preuß. On obtaining global information in a peer-to-peer fully distributed
environment (research note). In Euro-Par, pages 573–577, 2002.
[17] S. Kashyap, S. Deb, K. V. M. Naidu, R. Rastogi, and A. Srinivasan. Efficient gossip-based aggregate
computation. In PODS ’06: Proceedings of the twenty-fifth ACM SIGMOD-SIGACTSIGART
symposium on Principles of database systems, pages 308–317, New York, NY, USA,
2006. ACM Press.
[18] R. K. Kincaid, M. J. Holroyd, and C. Gatz. Understanding the structure of power law networks.
In SpringSim ’07: Proceedings of the 2007 spring simulation multiconference, pages
104–111, San Diego, CA, USA, 2007. Society for Computer Simulation International.
[19] D. Kostoulas, D. Psaltoulis, I. Gupta, K. P. Birman, and A. J. Demers. Active and passive
techniques for group size estimation in large-scale and dynamic distributed systems. J. Syst.
Softw., 80(10):1639–1658, 2007.
[20] L. L. Massoulie;, E. Le Merrer, A.-M. Kermarrec, and A. Ganesh. Peer counting and sampling
in overlay networks: random walk methods. In PODC ’06: Proceedings of the twenty-fifth
annual ACM symposium on Principles of distributed computing, pages 123–132, New York,
NY, USA, 2006. ACM Press.
[21] E. Le Merrer, A. M. Kermarrec, and L. Massoulie. Peer to peer size estimation in large and
dynamic networks: A comparative study. pages 7–17, 2006.
[22] A. G. M. bawa, H. Garcia-Molina and R. Motwani. Estimating aggregates on a peer-to-peer
networks. Technical report, Dept. of computer scienct, Stanford University, 2003.
[23] S. Naicken, B. Livingston, A. Basu, S. Rodhetbhai, I. Wakeman, and D. Chalmers. The state
of peer-to-peer simulators and simulations. SIGCOMM Comput. Commun. Rev., 37(2):95–98,
April 2007.
[24] K. M. J. S. S. Mane, S. Mopuru. Network size estimation in a peer-to-peer network. Technical
report, Department of Computer Science, University of Minnesota, 2005.
[25] D. Stutzbach, R. Rejaie, N. Duffield, S. Sen, and W. Willinger. On unbiased sampling for
unstructured peer-to-peer networks. In IMC ’06: Proceedings of the 6th ACM SIGCOMM
conference on Internet measurement, pages 27–40, New York, NY, USA, 2006. ACM.
[26] D. J. Watts and S. H. Strogatz. Collective dynamics of small-world networks. Nature,
393(6684):440–442, 1998.