基于用戶行為特征的Ｐ２Ｐ代理緩存的研究

摘要：通過對BitTorrent用戶一段時間內的行為統計分析，把握用戶的行為特征。在此特征的基礎上，提出一種BitTorrent緩存模式，更大程度地利用緩存空間，提高緩存命中率，減輕網絡運營商的出口壓力。

關鍵詞：BitTorrent； 用戶行為； 代理緩存

中圖分類號：TP393.09文獻標志碼：A

文章編號：1001-3695(2007)11-0106-03

0引言

隨著Internet在中國的迅速發展，P2P應用正在逐漸占據互聯網業務中舉足輕重的地位。其發展經歷了從第一代的P2P應用，如Napster、Gnutella、Kazaa到第二代的BitTorrent，并逐漸成熟起來。P2P網絡是一種具有較高擴展性的分布式系統結構，其對等概念是指網絡中的物理節點在邏輯上具有相同的地位，而并非處理能力的對等。相對于傳統的集中式客戶/服務器(C/S)模型，P2P弱化了服務器的概念；系統中的各個節點不再區分服務器和客戶端的角色關系；每個節點既可請求服務，也可提供服務；節點之間可以直接交換資源和服務而不必通過服務器。

正是因為P2P應用的這些特點，使得P2P占用了大量的網絡資源。自從2002年BitTorrent技術產生以來，迅速成為了互聯網上最高效、最便捷的下載工具。目前，根據主流運營商的統計，大約50%~70％的帶寬被P2P流量所占據。據統計，到2004年底，基于BitTorrent的網絡流量占據了整個P2P流量的53%[1]。因此，本文對國內某一大城市某運營商出口進行流量分析，如圖1所示。

從以上流量分析圖中可以看到，峰值期間運營商出口流量基本飽和，達到1.7 Gbps。其中兩項主要的應用為BitTorrent和HTTP。BitTorrent流量占到37.8%；HTTP流量占到19．8%；unknown流量為21.0%。不難看出，BT流量給運營商帶來了極大的帶寬占用。

BitTorrent流量之所以占有這么大的網絡帶寬，是因為BitTorrent是為多個用戶傳輸大型文件而設計的文件傳輸協議[2]。其主體設計思想是將文件分散為多個塊，然后將分散的文件塊分發給不同的用戶，用戶之間通過tracker服務器互連。Tracker 是指運行于服務器上的一個程序，該程序能夠追蹤到底有多少人同時在下載同一個文件。搜索網絡上所有的點（peers）。其中包括種子（seeds）和下載者（leechers），并建立動態的用戶列表（list）。列表中包括其他在線用戶的IP，內容特征碼（info_hash）等信息。用戶會定時發送keepalive包，并告訴tracker其下載、上傳等狀態。客戶端連接tracker服務器，就會獲得下載人員的名單。據此，BT會自動連接別人的機器進行下載，互相交換文件塊。它改變了過去多個用戶從一臺服務器讀取文件的思想，直接在用戶之間進行文件交換，大大提高了下載傳輸的速度。另外，由于當前的BT 下載方式，對節點的請求順序主要是依據BitField 最少的部分優先請求，即最少優先。這樣就確保了每個節點都擁有其他節點最希望得到的片斷，導致了每個下載節點并不優先從本地網節點請求流量，造成了巨大的出口壓力。

面對此種情況，有些運營商采取限制用戶流量的做法來減輕網絡出口壓力，但降低了用戶體驗。本文在研究了用戶行為特征的基礎上，提出一種部分代理緩存的模式，將用戶的BT請求重定向到代理緩存服務器上，這樣既維持了用戶體驗，又節省了帶寬資源，防止網絡擁塞。

1BT代理緩存原理

代理緩存的目的就是要減少Internet網絡數據傳輸量，防止網絡擁塞，提高網絡性能。其原理就是捕獲用戶下載請求，將請求重定向到代理緩存服務器中。若請求內容不在代理服務器中，則代理轉發請求給遠程服務器，并在接收應答后緩存內容，同時由代理緩存服務器向用戶提供數據流量。起初采用全緩存模式，即在緩存容量有限的條件下，客戶端發出請求。若請求對象已經被緩存，由代理緩存提供響應；若緩存容量已滿，則根據LRU算法進行替換。其缺點是緩存內容頻繁置換，造成緩存命中率下降。改進方法就是增加緩存容量，但硬件的投入也將增大。因此在對BT用戶行為進行統計，分析了用戶行為特征的基礎上，提出一種新的緩存方式，即部分緩存。它根據下載內容的熱度，即內容的訪問頻度進行緩存，緩存那些熱度高的內容。當用戶請求下載的內容在代理緩存中，由代理服務器響應；若請求下載的內容熱度較低，不在代理緩存中，代理轉發請求給遠程服務器，并在接收到應答后不作緩存處理而直接發送給客戶。

2用戶行為分析

在國內一大城市，城域網的出口部署一套P2P流量分析系統和數據庫服務器。P2P流量分析系統負責監聽網內用戶的所有流量。其最大特點就是不僅可以對三、四層網絡數據包進行分析，而且可以分析七層網絡數據報文。由于P2P流量端口和地址不固定，對P2P流量進行分析和管理，必須要對數據包內容進行解析。對于某些沒有明顯特征的P2P流量，還需要根據特定的P2P協議對P2P整個會話過程進行監控，通過分析會話建立報文，識別出特定地址和特定端口為P2P流量。對滿足BitTorrent協議的請求，交由應用層處理，并將該請求中的信息（內容特征碼info_hash、客戶端IP地址、請求時間、tracker地址）記錄數據庫中，作為BitTorrent用戶行為分析的數據來源。

此前已經有文章對BitTorrent的通信量進行分析[3]，在這里不再陳述。這個部分主要講述對國內一大城市BitTorrent用戶的數據統計，以及筆者對這些數據進行分析得出的結論。

本文記錄了2006年4月11日~5月31日的數據。據統計，在這段時間內，共有140 922個IP地址通過BT客戶端下載文件，平均每天請求下載的內容個數為23 619， 最高為25 772（5月27日）， 最低為18 041（5月30日）。若把這些下載內容全部緩存，采用全緩存模式，會頻繁置換緩存內容，使緩存利用率下降，命中率下降。如果只緩存一部分，并且緩存的這部分內容占據了BT流量的絕大部分，那么緩存效果將會大大增強。因此對某天請求下載的info_hash進行統計分析。

圖2向人們展示了一天當中共25 571個info_hash內容被請求下載及每個info_hash內容被請求的次數分布情況。從圖中可以看出，用戶的請求大多集中在那些訪問量較高的內容上，其中最高請求達到4 856次。對這些info_hash按照訪問次數進行排序。其中訪問量居前2 000名的info_hash的訪問次數總共達到392 895次，占全天訪問總量920 795的42.7%，BT流量占全部BT流量的62.5%；訪問量居前4 000名的info_hash的訪問次數為515 697次，占56%，BT流量占68．1%。由此可見，若將這2 000或是4 000個info_hash內容緩存，用戶的請求被重定向到代理服務器上，使得絕大部分的網絡數據在網內流動，大大減輕了運營商的出口壓力，節省了網絡帶寬，提高了系統效率。

3部分代理緩存的實現

3．1部分緩存的用戶請求處理過程

當用戶發送對象的請求時，該請求將被代理服務器獲得并處理。根據用戶所請求操作的內容和所請求對象是否已被緩存，緩存系統將進行不同的處理。如果請求內容不可緩存，則代理轉發請求給遠程服務器，并在接收到應答后不作緩存處理而直接發送到客戶；否則，將用戶請求重定向到代理服務器，由代理服務器響應，并作相應的處理。用戶請求處理過程如下：

a)接收到客戶的請求；

b)對請求進行分析，并根據請求類型和請求情況進行處理；

c)若所請求對象不允許緩存，則轉發該請求到遠程服務器，并在收到應答信息或請求數據后將其轉發給發出請求的客戶；

d)若所請求對象允許緩存但尚未被緩存，在收到應答信息或請求數據后，將其獲得的內容緩存的同時，轉發給發出請求的客戶；

e)若所請求對象允許緩存且已被緩存，則由緩存直接對請求進行響應。

3．2代理緩存的置換策略

由于緩存容量大小有限，當緩存已滿又有新的內容需要緩存時，就必須將熱度低的內容換出，這就出現了緩存置換問題。全緩存模式采用了LRU算法進行置換，這樣會造成頻繁的置換緩存內容，命中率下降。因此在部分緩存模式中，采用改進的LRU算法，即考慮到熱度變化是個動態的過程，在不同時間段的起伏變化。

現在按照熱度對下載內容info_hash進行排名。對5月2日的前2 000個info_hash在2~31日的走勢情況進行分析。假設這2 000個info_hash中，有info_hash在第N（1≤N≤29)d后跌出前2 000名，時隔Md后又返回到前2 000名的info_hash的數目為C。C的數據如圖3所示。

從圖3可以看出，當某個info_hash被置換出去以后，在12 d之內又重新回到2 000名之內的幾率比較大。如果將這些置換出去的內容再保留12 d，將會減少由于熱度波動造成的頻繁緩存置換，也提高了緩存命中率，極大地利用了緩存空間。同樣經過統計，當緩存info_hash數目為3 000、4 000時，保留12 d也是最佳時間。因而在計算緩存容量時，要考慮到這種情況。

4性能分析

4．1出口流量比較

在運營商的出口部署代理緩存系統后，對其流量、命中率和緩存容量進行比較。

圖4展示了在出口處部署代理緩存系統后的流量情況。

對比圖1可以明顯地看出，峰值期間出口流量壓力得到緩解，從1.7降到1.48 Gbps；BT流量從641.1降到185.3 Mbps；所占出口流量比例從37.8%，下降到13.3%。

4．2命中率比較

命中率包括請求命中率和緩存命中率。

請求命中率是指緩存中命中次數與用戶請求次數之比。假設用戶請求次數為Mq，緩存中命中次數為Nq，請求命中率α=Nq/Mq。

5結束語

對BitTorrent代理緩存的研究是近幾年較新的研究領域。通過將經常被訪問的內容緩存到代理服務器上，使得客戶的請求能從本地得到響應，從而減少網絡通信量，節省帶寬資源。但也有需要改進的地方。由于緩存文件是按照內容的特征值info_hash來區分，對于相同的內容，可能有多個info_hash，那么必然會有多個副本對應相同的內容，造成了空間的浪費。若考慮到內容解析，就會避免這種情況發生，這也是今后的研究方向。

參考文獻：

[1]Cachelogic. The true picture of peertopeer file sharing[EB/OL]. [2005-05].http://www.cachelogic.com/research/slide9.php.

[2]COHEN B. Bittorrent protocol specification[EB/OL].[2005-02]. http://www.bitconjurer.org/BitTorrent/protocol.html.

[3]SEN S， WANG J. Analyzing peertopeer traffic across large networks[J].IEEE/ACM Transactions on Networking， 2004，12(2):219-232.

[4]GUMMADI K P， DUNN R J， SAROIU S. Measurement，modeling，and analysis of a peertopeer file sharing workload[C]//Proc of the 19th ACM Symposium on Operating System Principles.2003: 314-329.

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