網路大小連續估計法在非結構P2P網路之應用

Continuous Network Size Estimation in Unstructured Peer-to-Peer Networks

許至輝(Chih-Hui Hsu)

指導教授 ： 陳宜欣

國立清華大學/電機資訊學院/資訊系統與應用研究所/碩士(2009年)

摘要

隨著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.

並列關鍵字

P2P ； network size ； peer ； continuous ； estimation

參考文獻

[1] L. A. Adamic. The small world web. pages 443–452. Springer, 1999.

[3] R. Z. Albert. Statistical mechanics of complex networks. PhD thesis, Notre Dame, IN, USA,

[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.