P2P流量的精細化識別方法研究

杜錫壽 陳庶樵 張建輝 陳 偉

(國家數字交換系統工程技術研究中心 鄭州 450002)

1 引言

近年來，隨著P2P(Peer to Peer)技術的高速發展，基于P2P的視頻點播、文件共享業務大量涌現，互聯網內容得到了極大地豐富與發展，創造出可觀的商業價值。因帶寬資源寶貴，網絡運營商亟需對其鏈路上的業務進行監控、管理、分析與計費，尤其是吞噬帶寬的P2P業務。因此，對P2P流量的精細化識別具有重要現實意義。

目前，已有多種方法[1,2]可將網絡流量高效準確地二元劃分為P2P流量與非P2P流量(即P2P流量的粗識別，coarse grained identification)，它們之中性能較為突出的是基于DFI(Deep Flow Inspection)的識別方法[3]，但基于DFI對P2P流量的精細化識別研究較少，其中多數研究只針對P2P流媒體進行，不包含對P2P文件共享等其它P2P應用方式的分析。基于DPI(Deep Packet Inspection)的方法雖可用于對P2P文件共享的識別，但該方法所依賴的識別特征變化快，需維護的特征庫日益龐大，擴展性較差。因此，基于DFI方法對P2P流量的精細化識別的研究具有重要意義。總體來說，目前對P2P流量的精細化識別處于探索階段。國外方面，Finamore等人[4]在對P2P流媒體精細識別時，提出一種基于支持向量機的KISS方法，該方法雖在實驗中獲得約98%的識別準確率較高，但本質是一個基于包載荷(payload)的識別方法，無法識別加密流量。Valenti等人[5]在針對P2P-TV流量的精細識別研究中，采取了一種簡單的計數方法，即記錄某主機在一短時間內和其對等體交互的包個數，該方法雖簡單易行，但在非對稱路由(asymmetric routing)環境下對P2P-TV流量進行識別時，包個數可能無法真實反應對等體之間的交互本質。同理，Bermolen等人[6]提出的P2P流媒體的精細化識別方法Abacus和Rossi在文獻[7]中提出的基于Netflow技術Abacus方法的擴展方法也不適用于具有非對稱路由的網絡環境。文獻[8]僅使用短時間窗內的包長分布作為特征對P2P-TV應用識別，采用基于SVM的分類方法，對PPLive, PPStream, QQLive, SopCast, UUSee 5種基于P2P的流媒體應用進行識別，并在3 s內獲得了超過99%的識別準確率，但其研究對象較窄，并未包含P2P文件共享應用，且SVM本質是一種二元分類器，無法識別未知的P2P應用。國內方面，鐘以融[9]在對P2P應用的精細化識別過程中，采用SVM的方法進行分類，雖該方法在實驗中獲得90%以上的平均準確率，但SVM方法不能有效預測出新應用，同時分類使用的特征計算復雜度較高，實時性相對差。

本文在對P2P流量識別時，考慮P2P流媒體和P2P文件共享是P2P應用的兩種主要方式，本文只研究對這兩種應用方式流量的精細化識別，并且不再考慮對P2P流量的粗識別。為使方法能在非對稱路由[10]現象表現明顯的骨干鏈路上正常應用，本文將流的定義單向化(嚴格匹配五元組標識：源IP、目的IP、源端口、目的端口、協議號)，同時使用10種可快速計算獲取的網絡流特征。本文在AP算法和分層加權近鄰傳播算法(Hi-WAP, Hierarchical Weighted AP)算法的基礎上，融合半監督聚類思想提出了一種距離測度下的分層加權半監督近鄰傳播(Hierarchical Weighted Semi-supervised AP,Hi-WSAP)算法，該算法是一種層次化的半監督聚類算法，但克服了層次聚類缺乏全局目標函數的缺點，是對AP算法[11,12]和Hi-WAP算法在流量識別領域的改進。本文的結構如下：第2節描述Hi-WSAP算法的基本流程，第3節對實驗環境進行詳細說明，第4節給出并分析實驗結果，第5節對全文進行總結。

2 Hi-WSAP算法描述

Hi-WSAP算法首先在分層劃分下的各數據子集中使用半監督近鄰傳播(Semi-supervised AP,SAP)算法，再對各數據子集的類代表點使用WAP(Weighted AP)聚類算法，最終得出聚類結果。下文結合流量識別的特定背景分別描述AP算法和Hi-WSAP算法。

2.1 AP算法

AP算法首次于2007年在《Science》中提出，它克服了部分聚類算法對初始點選擇敏感的缺點，能在短時間內處理大規模數據集。AP算法將所有樣本點都作為潛在的類代表點，通過在樣本點之間不斷傳遞及更新消息而獲得最終K個類代表點。因此，AP算法不會陷入局部最優解。

從d(i,j)的定義可看出，當兩條網絡流矢量正交時，距離最小，其相似度最小為0，必不屬于同一類。當兩條網絡流矢量方向一致時，其相似度最大為1，必屬于同一類別。s*是偏向參數(preference)，雖式(1)中沒有明確指出聚類完成后簇的個數，但是s*作為一個懲罰因子代表了一個樣本點成為類代表點的代價，s*的大小直接影響到最終聚類個數，值越大，聚類數越多。

AP算法在求解式(1)的過程中，有兩個重要參數：(1)吸引度(responsibility),r(i,j)從樣本點ei指向樣本點ej，描述ej適合作為ei的類代表的程度；(2)歸屬度(availability),a(i,j)從樣本點ej指向樣本點ei，來描述ei選擇ej作為其類代表的適合程度。算法描述如表1所示，算法迭代終止條件為達到某一最大迭代數或類中心保持不變。

從表1可以看出，在初始化相似度矩陣S=[s(i,k) ]N×N后，每次更新時，都需要對歸屬度矩陣A=[a(i,k)]N×N和吸引度矩陣R=[r(i,k)]N×N進行更新，因此AP算法的計算復雜度為O(N2)。當數據集規模增大或聚類算法的計算矩陣變得高維稀疏時，近鄰傳播算法明顯優于傳統算法[11,12]。

2.2 Hi-WSAP算法

Hi-WSAP算法首先將數據集e按等步長抽樣的方式劃分為多個數據子集，然后在單個數據子集上應用基于AP的半監督聚類算法，最后用加權AP(Weighted AP, WAP)算法將數據子集的聚類結果合并，并輸出最終的類代表點。該算法的3個重要步驟分別描述如下。

表1 AP算法描述

2.2.2基于AP的半監督聚類算法對各P2P應用，可依靠抓包通過分析端口的方法[13]獲取少量各應用的標簽數據，這些標簽數據可轉化為成對約束信息。成對約束信息分為兩部分：(1)Must-link，兩個點必須屬同一類，可用集合M= {(ei,ej)}表示；(2)Cannot-link，兩個點必屬不同類，可用集合C={(ei,ej)}表示。因此在單個數據子集上可利用這些標簽數據進行半監督聚類，聚類算法仍采用AP算法，但需首先利用成對的約束信息調整樣本點之間的相似度矩陣。下面描述標簽數據的相似度計算過程：

(1)對先驗信息中滿足Must-link約束的數據對(ei,ej)設置相似性度量值：s(i,j) = 0 &s(j,i) = 1。

(2)對先驗信息中滿足Cannot-link約束的數據對(ei,ej)設置相似性度量值：s(i,j) = 0 &s(j,i) = 0。

(3)對不包含在先驗信息中的數據對的相似度進 行 調 整 ： (ei,ej) ? {M∪C} ?s(i,j) = max(s(i,j),s(i,k) +s(k,j))。

(4)在Cannot-link集對第(3)步中的調整結果進行局部修正。當全局調整中選擇的樣本點ek與這對樣本點中的一個樣本點之間滿足Cannot-link約束，和另一個樣本點之間滿足 Must-link約束，則認為這對樣本點也滿足Cannot-link約束，樣本點的相似度 調 整 為 最 小 ： (ei,ej) ? {M∪C} &(ei,ek) ∈C&(ek,ej) ∈M?s(i,j) = 0 &s(j,i) = 0。調整后將該樣本點對加入Cannot-link集合中：C=(xi,xj)∪C。

在上述4個調整步驟完成后，可知部分樣本點之間的相似度值，由這些相似度值可簡化迭代步驟，提高聚類效率。在每個樣本子集的聚類算法同表 1所示。

2.2.3 加權近鄰傳播聚類WAP算法是一種針對有權值的類代表點聚類的算法，WAP算法與AP算法極為相似，其相似度定義為

其中ni表示選擇ei作為其類代表點的樣本點總數，bi為一常數，該值與ei所代表的樣本點之間的平均相似度有關。因此，根據新定義的相似度S'(ei,ej),WAP算法要解決K個中心點的選擇問題可描述為，尋找一個映射s，使得

取最大值。解決該問題的算法與AP算法一致，不同之處僅在于WAP使用新定義的相似度。

從 Hi-WSAP算法的計算流程可以看出，Hi-WSAP算法的最壞時間復雜度[14]為O(N3/2)，該復雜度隨著N的大規模擴張要遠低于AP算法的時間復雜度O(N2)，因此，Hi-WSAP算法的性能在數據集規模較大時會明顯優于 SAP算法，更適用于對P2P流量的精細化識別。

3 實驗環境

3.1 實驗數據

為便于對比和分析，本文使用兩組數據集。第1組為Auckland Set，可通過官方網站[15]下載，該數據集已多次用于網絡流量識別領域。第2組為自采集數據集NDSC Set。

為評價P2P流量精細化識別方法性能優劣，對兩組數據集都需預處理：首先將海量的WWW,POP3等非P2P應用濾除，在剩余的P2P流量中，將流的定義嚴格單向化，直接刪除單向流中包個數小于3的流，并規定一條流的生存時間為30 s。

Auckland Set中，因沒有應用層數據，在建立數據集時，利用基于端口的識別方法[13]對預處理后的P2P應用流進行標簽化，同時，由于數據量巨大，本文采用按類別比例取出20000條單向網絡流作為實驗使用，這20000條單向網絡流的詳細分析如表2所示。

表2 Auckland Set統計信息

NDSC Set中，初始流量來源于某校園網出口，該校園網有近百臺主機通過1條千兆全雙工以太網鏈路連接到互聯網，采集時間為2011年10月18日從0點開始每隔兩小時采集一次，共12次，每次持續時間為半小時。在處理時，使用基于載荷的分析方法[2]進行標簽化，并按類別比例取出50000條單向網絡流作為實驗使用，這50000條單向網絡流的詳細分析如表3所示。

表3 NDSC Set統計信息

3.2 對比算法

由于Hi-WSAP算法為一種基于距離測度的半監督聚類方法，因此本文在相同的實驗條件下，選擇兩種基于距離測度的半監督聚類算法作為對比算法。一種是文獻[16]提出的SAP算法，該算法在聚類時不對數據集做分層處理，直接利用約束信息對相似度矩陣進行簡化后聚類。并將SAP算法應用于UCI數據庫中的數據集，實驗效果較好，性能優于原始AP算法。另一種是文獻[17]提出的，將約束信息應用于K-means算法的Constrainted K-means(約束K均值)算法，該算法通過將Must-link和Cannot- link兩種形式的約束條件添加到K-means的目標函數中，使識別準確率大大提高，是一種經典的半監督聚類算法。

3.3 特征選擇

本文通過對真實網絡數據進行大量實驗分析，在DFI方法中采用的統計特征為網絡流的前若干個報文長度。這些統計特征在一個流的前若干包內可通過字節定位快速獲取，在計算過程中可大大降低時間開銷。最終選取的流統計特征如表4所示。

表4 特征縮寫及描述

3.4.1 準確性指標本文使用的準確性指標為F度量和整體準確率(OA)。F度量由召回率和精度聯合定義，對于類別i關于聚類結果簇j的召回率和精度分別定義為r(i,j) =mij/mi和p(i,j) =mij/mj,mij為屬于類別i但被聚類到簇j的樣本點數目，mi為類別i的樣本點數，mj為聚類結果簇j的樣本點個數。則類別i關于聚類結果簇j的F度量為

整個聚類結果的F度量計算公式為

3.4 評價指標

3.4.2 時間復雜度指標為評價各半監督聚類算法的時間效率，本文以秒為單位分別衡量 Hi-WSAP算法，SAP算法，約束K均值算法得到最終的聚類結果所消耗的時間，在這個階段中，算法越復雜，其消耗時間越長，實時性越差，越不適用于對P2P流量的精細化識別。

4 實驗結果

4.1 準確性指標

本文以F度量評價Hi-WSAP算法、SAP算法、約束K均值算法在P2P流量精細化識別中的準確性。在單次實驗中，獲取標簽點有兩種方式。第1種為分層抽樣，即在各類內隨機抽取相同比例的樣本作為標簽數據，各類標簽總和從0開始以500為單位不斷增加，直到各類標簽數的總和到5000為止。記錄每次實驗的F度量，重復上述單次實驗10次，得到的F度量結果如圖1，圖2所示。第2種為均勻抽樣，即在各類內指定隨機抽取相同的樣本數作為標簽數據，各類標簽總和從0開始以500為單位不斷增加，直到各類標簽數的和到5000為止。記錄每次實驗的F度量，重復上述單次實驗10次，得到的結果如圖3，圖4所示。

圖1 分層抽樣下Auckland Set的準確性結果

圖2 分層抽樣下NDSC Set的準確性結果

圖3 均勻抽樣下Auckland Set的準確性結果

圖4 均勻抽樣下NDSC Set的準確性結果

圖1，圖2中，隨著標簽數據的增加，3種算法的F.度量都有不同程度的增長，Hi-WSAP算法在兩種數據集下上升趨勢穩定，SAP算法上升曲線有小范圍波動，但最終趨于平穩，約束K均值算法在兩種數據集下F度量值波動都較大。從F.度量看，SAP算法和Hi-WSAP算法基本一致，當標簽數據總數為500時SAP算法的F度量大于Hi-WSAP算法，但隨著標簽數據的增大，Hi-WSAP算法的F度量略高于SAP算法。約束K均值算法的F.度量最低。

圖3，圖4中，Hi-WSAP算法和SAP算法在F度量的上升過程中基本一致，上升曲線較為平穩，但隨著標簽數據的增加，Hi-WSAP算法的F.度量略大于SAP算法。約束K均值算法的F度量最小，但在Auckland數據集上發現，約束K均值算法在F度量上升過程中，在標簽化數據點數為3000之前，都表現出較好的平穩性。

為評價3種算法的整體準確率，本文在標簽數據點總數為5000時記錄3種算法在Auckland Set和NDSC Set下的兩種抽樣方式的整體準確率，結果如表5，表6所示。

表5 分層抽樣下整體準確率實驗結果(%)

表6 均勻抽樣下整體準確率實驗結果(%)

從表5，表6中可得，在整體準確率上，Hi-WSAP算法略高于SAP算法，而Hi-WSAP算法和SAP算法的整體準確率高于約束K均值。Hi-WSAP算法在分層抽樣和均勻抽樣下的整體準確率都超過92%，準確率較高。綜合圖1，圖2，圖3，圖4和表5，表6知，Hi-WSAP算法相對于其它兩種算法在準確率的指標上更適用于對P2P流量的精細化識別。

4.2 時間復雜度指標

本文每單次實驗中，指定標簽數據為數據集總數10%，但在獲取標簽數據時采用兩種抽樣方法。第1種方法為分層抽樣，第2種方法為均勻抽樣，兩種方法的處理手段分別與準確性指標實驗中一致。每種抽樣方法重復實驗10次，以10次結果的時間平均值為最終指標。3種算法的時間復雜度實驗結果如表7，表8所示。

由表7、表8中知，Hi-WSAP算法在兩種抽樣方式下的算法收斂時間明顯小于SAP算法和約束K均值算法，該算法在時間性能上相對于SAP算法和約束K均值算法具有顯著優勢。這是由于Hi-WSAP算法對數據集的分層處理大大降低了算法的迭代次數，而SAP算法和約束K.均值算法在處理時是在整個數據集上進行迭代，計算中迭代次數較多。因此，Hi-WSAP算法相對于其他兩種算法在時間復雜度指標上更適用于對P2P流量的識別。

表7 分層抽樣下時間復雜度的實驗結果(s)

表8 均勻抽樣下時間復雜度上的實驗結果(s)

5 結束語

對P2P流量的精細化識別是網絡測量領域的一個重要方面。本文基于DFI的方法對P2P流量的精細化識別進行研究。在識別算法上，提出并使用一種能適應大規模數據集的Hi-WSAP算法；在統計特征上，選取了10種可在網絡流的前幾個數據包內快速計算的特征。在數據集Auckland Set和NDSC Set上進行的對比實驗可以看出：(1)Hi-WSAP的準確率較高，能夠在兩種抽樣方式下保持較為平穩的增長。(2)Hi-WSAP算法收斂時間短，在兩種數據集上表現出較快的處理速度。

由于本文使用的兩種實驗數據集數據量小，雖經單向化處理，仍不能完全描述骨干鏈路環境下的流量特征。Hi-WSAP算法能否在骨干鏈路環境下對P2P流量進行實時識別處理仍需分析驗證，這也是本文下一步主要的研究方向。

[1]Lim Y, Kim H, Jeong J,et al.. Internet traffic classification demystified: on the sources of the discriminative power[C].Proceedings of ACM CoNEXT, Philadelphia, USA,December 2010: 9-21.

[2]Kim H, Claffy K, Fomenkov M,et al.. Internet traffic classification demystified: myths, caveats, and the best practices[C]. Proceedings of ACM CoNEXT, Madrid, Spain,2008: 1-12.

[3]Zhou X. A P2P traffic classification method based on SVM[C]. Proceedings of the International Symposium Computer Science and Computational Technology, Shanghai,China, 2008: 53-57.

[4]Finamore A, Mellia M, Meo M,et al.. KISS: stocastic packet inspection[J].Lecture Notes in Computer Science, 2010, 6003:115-126.

[5]Valenti S, Rossi D, Meo M,et al.. Accurate, fine-grained classification of P2P-TV applications by simply counting packets[J].Lecture Notes in Computer Science, 2009, 5537:84-92.

[6]Bermolen P, Mellia M, Meo M,et al.. Abacus: accurate behavioral classification of P2P-TV traffic[J].Computer Networks, 2011, 55(6): 1394-1411.

[7]Rossi D and Valenti S. Fine-grained traffic classification with Netflow data[C]. TRaffic Analysis and Classification (TRAC)Workshop at IWCMC 2010, Caen, France, 2010: 479-483.

[8]Li J, Zhang X, Zuo X L,et al.. Using packet size distribution to identify P2P-TV traffic[C]. 2010 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery, Huangshan, China, 2010: 150-155.

[9]鐘以融. P2P流量識別方法研究[D]. [碩士論文], 東北財經大學, 2010.

Zhong Yi-rong. Study on P2P traffic identification method[D].[Master dissertation], Dongbei Cai Jing University, 2010.

[10]John W, Dusi M, and Claffy K. Estimating routing symmetry on single links by passive flow measurements[C]. Proceedings of the Wireless Communications and Mobile Computing Conference, Caen, France, 2010: 473-478.

[11]Frey B J and Dueck D. Clustering by passing messages between data points[J].Science, 2007, 315(5814): 972-976.

[12]Mézard M. Where are the exemplars?[J].Science, 2007,315(5814): 949-951.

[13]Madhukar A and Williamson C. A longitudinal study of P2P traffic classification[C]. 14th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, Monterey, USA, 2006: 179-188.

[14]Fu C, Wang J, Chen X G,et al.. Flow transformation of anonymous communication based on hierarchical weighted affinity propagation clustering[J].Journal of Computational Information Systems, 2011, 7(1): 319-326.

[15]Auckland. http://wand.net.nz/wits/index.php, 2011-11-2.

[16]肖宇, 于劍. 基于近鄰傳播算法的半監督聚類[J]. 軟件學報,2008, 19(11): 2803-2813.

Xiao Y and Yu J. Semi-supervised clustering based on affinity propagation algorithm[J].Journal of Software, 2008, 19(11):2803-2813.

[17]Wagstaff K, Cardie C, Rogers S,et al.. Constrained K-means clustering with background knowledge[C]. Proceedings of the Eighteenth International Conference on Machine Learning,Williamstown, Morgan Kaufmann Publishers, 2001: 577-584.