P2P網絡的邏輯結構與物理結構匹配性研究

P2P網絡的邏輯結構和物理結構匹配，主要是指對節點的物理網絡位置的知曉(比如距離的遠近)，以及邏輯層與物理層之間的拓撲網絡結構的匹配。資源搜索是P2P網絡中非常重要的構成部分，但是同時也帶來了很大的網絡開銷，此外，資源搜索過程中查詢消息需要在邏輯層的網絡拓撲網絡中傳輸，這就引出了邏輯層與物理網絡層之間的匹配問題。

一、P2P網絡的邏輯結構與物理結構不匹配。

由于邏輯層和物理網絡的不匹配的原因，很容易出現同一消息重復穿越相同的物理鏈接的現象，帶來大量多余流量。

根據文獻的敘述，Gnutella網絡是應用最廣的典型的分布式P2P系統。而只有50000個節點的Gnutella網絡，就會產生了330TB/月的流量。文獻[2]指出:Gnutella網絡中只有2%—5%的節點位于同一自治系統(AS)中，而超過40%的節點都位于前10大AS。這表明大部分的P2P網絡流量都要跨越AS邊界，增加了網間流量。

二、改進邏輯結構和物理結構不匹配的現有的辦法。

現有，對P2P系統搜索效率的改進方法可以分為4類:基于轉發機制、基于集群化、基于邏輯層拓撲優化及基于緩存。這四種方法可以一起使用，相互補充。目前已有的研究的相關工作，如下所述。

1.基于轉發機制

基于轉發機制的改進方法原理，對于分布式P2P網絡系統來說就是，節點根據物理網絡信息選擇一部分鄰居節點而不是所有的邏輯鄰居節點來轉發查詢消息。文獻[4]提出的有向BFS方法中，每個節點維護一個基于一些量化值的信息，比如從鄰居節點獲得的查詢結果walker數量、與該鄰居節點的鏈接時延。節點選擇返回最多查詢結果的鄰居節點或者最近的鄰居節點來轉發查詢消息。文獻[5]提出的K-walker查詢方法，源節點會發送若干個不同的行走者(轉發鄰居節點)。行走者到達的節點，隨機只選擇一個鄰居節點來轉發該查詢。而對于每個行走者來說，查詢過程是順序處理的。

2.基于集群化

限制節點的交互信息的往來是嚴格控制資源搜索流量的關鍵問題。而將節點集群分組是一個很有效的方法。首先，先對集群化進行理論描述文獻[6]。通過估算互聯網上任意兩臺主機間的近似距離(采用IP網絡的時延來代表距離)，生成加權圖，加權值就是主機間的距離。這樣，網絡的集群化問題就被定義為圖的最優化劃分。用圖論公式描述為:給定加權圖、直徑，將整個圖劃分為最少的N個集群，集群的總和覆蓋全圖。任意一個集群中，兩個節點的間距小于K。這樣形成的理想邏輯網絡和物理網絡結構的關系是，大部分邏輯層邏輯連接位于同一集群的各主機之間，而集群之間只通過少數邏輯連接來連通。

3.基于邏輯層拓撲優化的方法

目前，有很多工作都是通過使用小范圍的測量消息，來獲知該范圍內的拓撲信息，然后進行邏輯層的拓撲優化的。文獻提出了LMT算法，是在Gnetella0.6P2P網絡協議基礎上，設計了叫做TTL2的探測消息類型。

4.基于緩存的方法

基于緩存的，包括數據索引緩存和內容緩存。集中式P2P系統提供集中索引服務器，保存所有節點的共享文件索引。KaZaA使用合作式的超級節點，每個超級節點保存一部分節點的文件索引。有些系統將保存索引這一功能分發到所有的節點。

三、基于聚類思想解決P2P網絡的邏輯結構與物理結構匹配性的新方法。

正如前文所說，P2P網絡的位置知曉性的問題，研究者提出了很多的解決方法，這些方法也確實都在一定程度上解決了P2P網絡的位置知曉性的問題，但是這些方法也存在這樣或者那樣的問題，比如基于緩存的方法必然對設備的性能有更高的要求，要有更大的存儲空間才有可能保持的性能;基于轉發機制的方法也存在著在某些情況下容易引發消息洪泛的可能。所以，基于這些情況，本文提出了基于聚類思想的P2P網絡的位置知曉性的問題的解決方案。

聚類方法是數據挖掘技術中的一種重要的方法。我們可以將解決P2P網絡的位置知曉性的問題的方法中的基于集群化思想的地標方法與數據挖掘中的聚類思想相結合，從而得到新的解決P2P網絡的位置知曉性的問題的方法。

本文討論P2P網絡的邏輯結構和物理結構匹配問題，分析造成底層網絡重復消息的理論原因，研究對等網絡(P2P)的邏輯結構和物理結構匹配問題。雖然對于P2P網絡的邏輯結構和物理結構匹配問題很多研究者提出了很多的研究方法，但是總有這樣那樣的缺陷，本文根據網絡環境的實際情況，提出了基于聚類的P2P網絡知曉性的新算法。

參考文獻:

[1]K.Sripanidkulchai.The Popularity of Gnutella Queries and Its Implications on Scalability.http://www2.cs.cmu.edu/ kunwadee/research/p2p/gnutella.html，2001.

[2]M.Ripeanu，A.Iamnitchi，and I.Foster.Mapping the Gnutella Network.IEEE Internet Computing，2002.

[3]Yunhao Liu，Li Xiao，Xiaomei Liu，Lionel M. Ni，Xiaodong Zhang.Location Awareness in unstructured Peer-to-Peer systems.IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS，VOL.16，NO.2，FEBRUARY 2005

[4]B.Yang and H.Garcia-Molina.Efficient Search in Peer-to-Peer Networks.Proc.22nd Int’l Conf.Distributed Computing Systems(ICDCS)，2002.

[5]Q.Lv，P.Cao，E.Cohen，K.Li，and S.Shenker.Search and Replication in Unstructured Peer-to-Peer Networks.Proc.16th ACM Int’l Conf.Supercomputing，2002.

[6]NG，T.E.，AND ZHANG，H.Predicting Internet Network Distance with Coordinates-based Approaches.In Proceedings of IEEE INFOCOM’02，New York，June 2002.

[7]Yunhao Liu，Li Xiao，Xiaomei Liu，Lionel M.Ni，Xiaodong Zhang.Location-Aware Topology Matching in P2P Systems.IEEE INFOCOM 2004，Hong Kong，China，March 2004.