Ｐ２Ｐ應用系統用戶共享行為的復雜網絡模型

摘要：分析了因特網上主流P2P應用的體系結構，構造了一個描述用戶共享行為的復雜網絡演化模型——SNET模型。在用戶共享文件持續增長的驅動下，SNET模型可以演化出與實際P2P應用相似的拓撲結構。通過分析SNET模型的仿真結果與清華校園網的實際測量數據，發現P2P應用和SNET模型中用戶的連接數量都表現出冪率分布規律。

關鍵詞：復雜網絡； 因特網測量； 對等網絡

中圖分類號：TP393

文獻標志碼：A

文章編號：1001－3695(2008)06－1853－03

0引言

復雜網絡理論[1]已經滲透到現實中諸多網絡化系統的理論研究中。因特網上存在著各式各樣的應用程序，而用戶利用這些應用程序在因特網上傳遞信息和共享資源。對于因特網上用戶行為的研究也開始借助于復雜網絡理論[2]。用戶行為的統計特征對于因特網的發展與演化和應用程序的開發與設計都具有重要的研究意義[3]。

最近，研究人員發現P2P（peer－to－peer）應用的流量和所占帶寬都迅速增長[4]，已經成為網絡流量占據50％以上的因特網的首要應用之一。P2P應用打破了因特網傳統的客戶機/服務器模式，用戶具有服務器和客戶機的雙重功能，擁有相同的責任和能力并協同完成任務。目前，P2P被廣泛應用于分布式存儲、視頻組播、文件共享及應用層組播等業務中[5]。在文件共享業務中，P2P應用充分利用用戶之間的可用資源進行數據傳遞，文件共享速率顯著增加。這使得P2P文件共享應用成為校園網以及整個因特網上最流行的應用之一。參與文件共享的所有用戶構成了一個復雜的網絡化系統。整個系統無中心控制機制，按照一種自組織方式運行[6]。網絡拓撲結構的演化完全由用戶對于文件的需求來推動。在P2P文件共享應用中，每個用戶采用的策略都會對整個系統產生影響，而大量用戶的整體行為決定了整個系統的行為。同時用戶行為的統計特征對于網絡流量造成的影響也不容忽視。因此，P2P應用中用戶行為的統計特征就成為了因特網研究中一個重要課題。

目前，對于P2P應用的理論研究工作還處于起步階段，工作主要集中在對實際系統的測量上。文獻[4，7，8]測量了因特網主干網上P2P應用的流量，提出可以通過優化P2P應用來減輕P2P流量給運營商帶來的網絡負載。Rejaie等人[9，10]測量Gnutella網絡上用戶對文件訪問的行為特征，發現P2P應用普遍存在搭便車效應(free riding effect)，即某些用戶只下載文件而拒絕共享文件。用戶對于文件的需求主要集中在少數流行文件上，而大部分文件在用戶之間流行的時間都較短。文獻[11]給出了P2P應用中用戶之間連接關系的統計特征，發現用戶網絡具有復雜的拓撲結構。本文基于上述對于實際P2P應用的測量工作，開始嘗試構建合適的復雜網絡演化模型來分析P2P應用中用戶行為的統計特征及其影響。P2P應用的復雜網絡演化模型描述P2P應用中用戶的整體行為，為研究人員提供一個平臺設計新的P2P應用和改善已有P2P應用的體系結構。

本文首先分析了流行P2P應用的體系結構，并以此為基礎構建用戶共享行為的一種復雜網絡演化模型。該模型以用戶所擁有的共享文件數量為主要參量，刻畫了P2P應用中用戶共享行為所控制的網絡演化過程。而后，結合因特網中真實數據流量的測量，分析了該網絡模型的自組織演化機制與實際P2P應用的異同。通過對實際測量數據與模型仿真結果的比較，得出了P2P應用中用戶共享行為的統計特征的一些初步結果。本文的研究對于因特網的維護和管理以及P2P應用的設計與實現都具有重要的參考價值。

1用戶共享行為復雜網絡模型

1．1P2P應用體系結構

文件共享業務是P2P主要應用之一，Napster、eDonkey、BitTorrent、Maze和迅雷(Thunder)等因特網上最流行的P2P應用都屬于此類業務。這類P2P應用普遍采用中心服務器保存所有用戶的共享文件信息以及IP地址。當用戶加入系統時，首先要連接目錄服務器并報告其IP地址及共享文件列表。用戶在需要某個文件時，向目錄服務器提交搜索請求。然后，目錄服務器返回符合搜索要求的所有文件的存儲地址，用戶根據返回的地址信息直接從提供該文件的用戶處下載文件。

在P2P應用中，用戶之間相互傳遞文件的共享行為構成了一個位于因特網物理網絡之上的虛擬動態網絡系統[12]。在該網絡系統中，每一個節點表示一個用戶，既是服務器又是客戶機；用戶之間用于下載文件的TCP連接被抽象為邊，節點通過這些邊相互連接構成整個網絡。網絡中不存在任何中心控制機制，用戶可以隨時加入或離開網絡，節點與節點之間是否建立連接也完全受其自身控制。網絡的演化規律完全由用戶之間自組織的文件共享行為決定。根據上述特點，本文提出了P2P用戶共享行為的復雜網絡演化模型——sharing network (SNET)模型。

1．2SNET模型

在SNET模型中，用戶i的共享文件數量ωi(t)的增長推動網絡拓撲結構的演化。假設在單位時間內，任意用戶i可以從其相連的每個用戶處下載單位數量的文件，也就是

ωi(t)=ωi(t-1)+ki(t-1)

（1）

其中：ki(t-1)表示用戶i在t-1時刻的邊數。如果用戶在網絡中存在的時間越長，相連的用戶數量越多，那么其共享文件數量的增長也越快。SNET模型按照如下過程演化：

a)新用戶加入。網絡中隨時都會有新用戶加入；新用戶共享文件的初始數量設為1，即ωi(ti)=1（其中：ti表示用戶i加入網絡的時刻）；新用戶按照策略gi∈G選擇m(m≥1)個用戶發送連接請求（G為節點i可選的所有策略hi構成的集合）。

b)連接請求接收。用戶j在收到連接請求后，會按照策略hj∈H來決定是否接收此請求（H為節點j可選的所有策略hj構成的集合）。

c)共享文件數量增長。任意用戶都會從其相連的每個用戶處下載單位數量的文件，共享文件數量的增長如式（1）所示。

d)用戶退出。用戶可以隨時退出，將用戶退出策略qi構成的集合記為Q；在用戶推出網絡后，所有與退出用戶相連的鄰居用戶都按照策略gi∈G重新選擇一個用戶發出連接請求，以此來維持其下載能力。

隨著用戶不斷地加入和退出，網絡的拓撲結構也不斷變化，由G、H和Q等策略共同決定的網絡演化規律使得網絡生成復雜的拓撲結構。

1．3網絡演化規律

1)網絡的初始狀態

假設在初始時刻，網絡中有N個用戶，且每一個用戶的初始狀態都相同。

（2）

即所有用戶都只含有單位數量的共享文件，且用戶之間不存在任何連接。而后，在網絡的演化過程中，每單位時間內網絡中都有一個用戶退出，同時也有一個新用戶加入。也就是說，用戶加入和退出的速率基本相同。此外，假設網絡中所有的連接均為雙向，在連接建立之后兩個用戶都可從對方下載文件。

2)連接請求發送策略G

考慮到如果一個用戶擁有共享文件數量越多，那么該用戶越有可能擁有符合其他用戶搜索要求的文件。因此，假設所有用戶都采用相同的線性傾向策略，即任意一個用戶選擇用戶i發送連接請求的概率G(ωi)正比于用戶i共享文件的數量ωi

G(ωi)=ωi/(∑jωj)

（3）

3)連接管理策略H

假設每一個用戶都具有足夠的能力來接收所有連接請求，并且采用一種最簡單的隨機策略來決定是否接收某個連接請求，即每個用戶均以概率p來隨機接收其他用戶的連接請求。

4)用戶退出策略Q

用戶選擇退出網絡的決定相對來說比較復雜，一般地，有兩種選擇退出的方式：a)在用戶已經完成所需文件的下載時，用戶可能選擇退出網絡而不再與其他用戶共享文件（在這種情況下，用戶選擇退出網絡的概率將正比于用戶的共享文件數量）；b)一個用戶的共享文件數量越多，能夠說明該用戶越愿意與其他用戶共享文件，此時，該用戶在網絡中的存在時間也會相應較長（在這種情況下，用戶退出網絡的概率將反比于用戶共享文件的數量）。在任何時刻t，用戶i退出網絡的概率設為

Q(ωi)=ωγi/(∑jωγj)

（4）

其中：γ取值為+1或-1，分別對應于上述兩種情況中a)或b)在網絡中占主導地位。

2數據測量與模型驗證

2．1數據測量與分析

清華大學校園網（TUNET）是全國最大的校園網之一，其拓撲結構大致可以分為核心網（core layer）、邊緣網（distribution layer）和接入網（access layer）三層。TUNET通過兩條1 Gbps鏈路（in－going和out－going）與中國教育和科研計算機網（CERNET）相連；CERNET則為校園網提供因特網接入服務，如圖1所示。

在2006年12月流量高峰時段，采集了TUNET與CERNET之間的兩條1 Gbps鏈路的數據流量。因為兩條鏈路上的流量都很大，所以在測量過程中，只記錄了數據的報頭信息，它包括源地址、目的地址、源端口和目的端口等信息。在P2P應用中，Maze和迅雷都是采用固定的TCP端口通信。對于此類應用，直接根據端口就可以識別出全部流量。其中，Maze采用30601和30701端口進行通信；迅雷則采用3076、3077和3078端口作為通信端口。在數據分析中，首先將上述端口的數據包分離出來，并對其進行TCP流歸并，將屬于同一個TCP連接的多個數據包融合到一起；然后根據不同IP地址之間的TCP連接數量，計算出每一個用戶的連接數量。在測量數據中，Maze中大約包含了 1 000個在線用戶，而迅雷中在線用戶有6 000個左右。

2．2SNET模型仿真與驗證

在SNET模型中，設在線用戶數量N＝4 000，新用戶發送連接請求的數目m=2，而用戶接收連接請求的概率p=0．5。網絡從初始狀態開始演化，在10 000步后，將所得的拓撲結構與實際測量的P2P應用拓撲結構進行比較。圖2顯示了網絡中用戶連接數量k的概率密度函數P(k)。

從圖2可以看出，Maze和迅雷具有相似的拓撲結構性質：兩種P2P應用中用戶連接數量的分布均滿足冪率分布規律，大部分用戶只有少量連接，而少數用戶擁有非常大的連接數量。此外，當γ取值為-1時，由SNET模型生成的拓撲結構顯示出與實際P2P應用相似的拓撲結構特征，網絡中同樣存在少量連接數量很大的用戶。但是當γ取值為+1時，SNET模型中連接數量大的用戶消失了，用戶的連接數量普遍較小。此時，因為用戶下載到需要的文件后就立即退出網絡，所以用戶的連接數量難以增長到很大的數量。這說明在實際P2P應用中，用戶在網絡中的在線時間與其共享文件的數量正相關，擁有較多連接的用戶也是共享文件的主要提供者，而大部分用戶屬于搭便車的用戶，下載少量文件后便會退出網絡。

3結束語

本文構建了P2P應用的用戶共享行為的復雜網絡演化模型——SNET模型。SNET模型主要用來研究文件共享業務中用戶行為的統計特征。本文測量了清華大學校園網與因特網之間的數據流量，統計了其中P2P應用中用戶連接數量的分布特征。通過比較實際數據與SNET模型，發現P2P應用中用戶在文件共享方面存在極大差異：少數用戶提供了大部分文件而大部分用戶往往只是下載少量文件后便會退出。用戶共享行為構建的虛擬網絡也因此表現出冪率分布特征。SNET模型揭示了用戶頻繁加入和退出網絡的整體行為對于網絡拓撲結構的影響，簡化了用戶對于連接的管理策略。SNET模型為進一步研究P2P應用中用戶行為的統計特征提供了一個平臺，尤其是對于其中連接管理策略還存在很多問題值得探討，對于設計和改善新的P2P應用也具有重要的參考價值。

參考文獻:

[1]BOCCALETTIA S， LATORAB V， MORENOD Y， et al. Complex networks: structure and dynamics[J]. Physics Reports， 2006， 424(4－5):175－308.

[2]姚園園， 張志鴻. 從復雜網絡角度對即時消息網絡進行拓撲建模[J]. 微計算機信息， 2006， 24(3):207－209.

[3]WELLMAN B. Computer networks as social networks[J]. Science， 2001， 293(14):2031－2034.

[4]SEN S， WANG Jia. Analyzing peer－to－peer traffic across large networks[J]. ACM/IEEE Trans on Networking， 2004，12(2):219－232.

[5]湯晟，吳朝暉.P2P—對等網絡的未來[J]. 計算機應用研究，2004， 21(1):13－16， 22.

[6]PREHOFER C， BETTSTETTER C. Self－organization in communication networks:principles and design paradigms[J]. IEEE Communications Magazine， 2005， 43(7):78－85.

[7]POUWELSE J. A， GARBACKI P， EPEMA D H J， et al. The bittorrent P2P file－sharing system:measurements and analysis[C] //Lecture Notes in Computer Science. 2005: 205－216.

[8]YANG Mao， DAI Ya－fei， TIAN Jing. Analyzing peer－to－peer ttraffic's impact on large scale networks[C] //Lecture Notes in Computer Science. 2006: 412－419.

[9]ZHAO Shan－yu， STUTZBACH D， REJAIE R. Characterizing files in the modern Gnutella network a measurement study[C] //Proc of SPIE/ACM Multimedia Computing and Networking. New York:ACM Press， 2006:189－202.

[10]STUTZBACH D， REJAIE R. Understanding churn in peer－to－peer networks[C] //Proc of the 6th ACM SIGCOMM on Internet measurement. New York: ACM Press， 2006: 189－202.

[11]WANG Fang， MORENO Y， SUN Yao－ru. Structure of peer－to－peer social networks[J]. Physical Review E，2002，58(4):630.

[12]王磊，周淑華，袁堅，等. 虛擬網絡行為對互聯網整體特性的影響[J]. 物理學報，2007， 56(1):36－42.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文