自適應聚類片選內容分發模型*

董丁維 ，王 晶 ，沈奇威

（1.北京郵電大學網絡與交換技術國家重點實驗室 北京100876；2.東信北郵信息技術有限公司 北京100191）

1 引言

隨著多媒體技術的發展和普及，網絡上信息的形式及應用的類型日益豐富，人們對于Internet內容的需求也在飛速增長。傳統的窄帶網絡及單一的Web頁面內容已經不能滿足人們的需要，網絡上用戶訪問速度慢、體驗差正逐漸成為制約信息技術發展的障礙。很多人認為網絡技術的不完善是Web性能差的主要原因，增加網絡帶寬、采用高速的路由器等方法就能加速Web訪問，但實際上帶寬不足并不是惟一原因。隨著寬帶網絡的普及，網絡的訪問速度在一定程度上得到了緩解，同時海量并發用戶密集訪問型的應用（如網絡電視點播業務）迅速發展，仍然會引起網絡擁塞，因此單純依賴網絡帶寬并不能完全解決穩定性和服務質量的問題，需要引入一種高效的內容服務網絡——內容分發網絡（content delivery network，CDN）[1]。

CDN的原理是通過在現有的Internet中加入一層新的網絡架構，將要分發的內容發布到最接近用戶的網絡邊緣節點 （edge point，EP），使用戶能就近獲得所需內容，CDN一般分為兩級結構：由中心服務器節點（center point，CP）和EP構成的第一級網絡結構，內容發布的流程在這一級上進行；第二級網絡是由EP和終端用戶之間構成的P2P分發網絡，主要用于內容向最終用戶下發[2]。

內容分發模型是指在CDN的第一級網絡中，通過構建合理的拓撲結構，采用有效的傳輸方式，同時結合聚類算法，讓EP更加合理地選擇鄰居節點，采用片選策略，使EP快速地從鄰居節點處下載適當的內容，完成內容在CP和EP之間的快速分發。不同的CDN根據其業務需求不同，往往采用不同的內容分發模型。

實踐證明，CDN的出現很大程度上改善了Internet的網絡擁塞狀況，提高了用戶訪問內容的響應速度和質量，特別是多媒體服務的質量。在以往的工程應用中，業務和內容的差異十分明顯，有的業務要求塊式內容最短時間到達，因此CDN的分發模型側重于聚類算法的有效性；有的業務注重流式內容的有序傳輸，因此要求分發模型的片選機制更加完善。隨著網絡技術的發展，兼有塊式和流式內容海量訪問的業務會日漸增多，這就對內容分發模型提出了新的要求。本文針對這一趨勢，設計了一種兼顧塊式和流式內容分發的模型。

2 研究背景

2.1 應用層組播

內容分發模型利用組播技術將內容從CP向多個EP快速高效地分發下去。組播技術是指單個信息發送者對應多個接收者的一種網絡通信，現在常見的兩種技術是IP組播和應用層組播。IP組播的主要思想是在Internet單播的框架上進行擴展，功能主要通過路由器實現，網絡資源利用率較高，但存在很多問題，主要表現在：路由器需要為所有組播保存狀態，擴展性較差；對路由器的依賴過高，并不是所有路由器都支持IP組播，可行性差；IP組播中的算法設計復雜，維護開銷大[3]。應用層組播技術，保持了互聯網原有的簡單、不可靠、單播的轉發模型，由端系統實現組播轉發功能，同時克服了IP組播需要對路由器改造的不足，可以有效節省帶寬，提高分發效率[4]。

本文設計的內容分發模型采用應用層組播技術。

2.2 傳統分發模型

（1）小規模多源組播分發模型

代表是 End System Multicast和ALMI[5]，針對小規模、多數據源的情況，典型應用是視頻會議系統。

End System Multicast首先將組播組的成員組織成一個“網”（mesh），每個成員都維護所有組成員的列表，提高了組播組的可靠性；在mesh上以每個數據源為根各構造一個生成樹（spanning tree），這樣可針對每個數據源進行性能優化。其缺點是系統開銷比較大，降低了系統的可擴展性，適合小規模組播組的情況。ALMI在組播成員之間維護一個“最小生成樹”（minimum spanning tree，MST），減小了維護開銷，但從每個源出發傳輸開銷無法單獨優化。生成樹的維護開銷限制了組播組的規模[6]。

（2）基于特定邏輯結構的分發模型

代表是 Bayeux[7]和CAN(content-addressable network)[8]，使用特殊的邏輯結構對組播節點映射或編址，組播轉發可使用簡單的規則實現，從而減少狀態維護開銷和轉發開銷，避免路由協議的使用。

Bayeux基于Tapestry[9]，每個節點擁有全局惟一的ID，并維護一個鄰居表，這些鄰居節點的ID和本節點的ID在一定數量的位上相同。轉發中第n跳節點ID和目的節點ID至少有n位相同。Bayeux在Tapestry的基礎上將組播樹的狀態信息保存在“中間節點”上，其主要問題是會限制算法的可擴展性。CAN組播是對CAN的擴展。CAN將一個d維坐標空間劃分成若干部分，每個節點擁有其中某部分。兩個直接相鄰部分的坐標在d-1維上相同，而在另一維上不同。轉發報文時把報文發給鄰居中和目標坐標最接近的節點。CAN組播將組播組構造為CAN，使用“洪泛”方法在CAN內轉發報文，這樣可減少節點上維護的狀態信息，提高數據傳輸的可靠性，但也會產生大量重復報文。存在的問題是，邏輯空間中節點間的關系并不能對應實際網絡中的關系，得到的報文轉發路徑很有可能在性能方面存在問題。

（3）BitTorrent分發模型

BitTorrent可以被認為是一種P2P的應用層組播技術，采用網狀拓撲，以最小化平均內容分發時間為目標，同時采用激勵機制遏制節點自私行為，以保障內容分發的效率[10]。BitTorrent一般被塊式內容分發系統所采用。

3 自適應聚類片選模型

傳統的分發模型由于采用固定的算法和結構，對特定類型（塊式或流式）的分發有較好的效果，但由于算法上的缺陷，很難同時支持塊式或者流式內容的分發。本文設計的自適應聚類片選分發模型，可以通過算法參數的動態調整，針對不同應用、不同類型的分發內容，提供分發功能，并達到良好的效果。

3.1 HTS

Hash表的鍵是一個存儲對象的標識，值則為存儲對象的屬性信息。在本模型的CP中提供的HTS（Hash table service，Hash表的維護服務），用來保存和同步EP的狀態信息，使CP與EP之間的元數據保持一致并動態更新。HTS的接口設計見表1。

3.2 CP與EP片式內容傳送

為了保證內容的傳送效率，降低丟失后的重傳損耗，內容分發時一般把內容分成許多大小相同的分片，以內容片作為傳送單位。當一個EP接收一個完整內容片之后，立即向用戶客戶端提供內容下載，也可以在鄰居EP內進行內容片互傳，充分利用有限帶寬；當傳送過程中出現某個內容片損壞或者丟失時，只需重傳單個內容片而無需重傳所有內容，節省了傳送資源，提高了效率。

表1 HTS接口

內容分片的大小會影響到整個傳送過程的效率，所以分片的大小是一個很重要的參數，有研究表明，分片大小為256 KB或者512 KB時，效率最高，BitTorrent也是采用了256 KB或者512 KB（版本不同參數不同）的分片大小。本設計采用256 KB的內容分片，既不會因為分片太小造成EP之間內容片互傳時I/O開支過大，也避免了分片過大造成分片重傳時的耗時低效[11]。

3.3 網狀拓撲結構

網狀拓撲結構有效避免了單樹和多樹結構的不足，也是分發系統中最常見的結構，既能支持塊式內容（如光盤鏡像）的分發，又能支持流式內容（如流媒體）的分發，可以針對不同的應用需求，提供不同的內容支持，并易于擴展和優化。由于每個節點在網狀拓撲結構中都有很多鄰居節點，可靠性較好，可規避節點失效的風險，保證連通性。網狀拓撲結構既支持Pull方式也支持Push方式的內容分發，但需要每個節點維護其鄰居節點的信息，有一定的系統開銷。

由于本分發模型重點在于聚類算法和動態調整片選策略，網狀結構能靈活地適應變化的網絡情況和應用需求，因此采用網狀拓撲結構。

3.4 聚類算法

內容分發模型中的聚類算法體現在如何為一個EP選擇一組其他的EP組成一個鄰居網，目的是生成一個覆蓋網絡的拓撲結構。鄰居網的形成直接影響到分發的性能和網絡結構的健壯性。

結合CP中的HTS功能，每個EP都被指定惟一的ID，某個時段內EP會有一個描述信息，稱為EP元數據，元數據中包含EP的IP地址和接收發送內容的端口號以及EP所在自治域（電信、網通）的名稱，如某臺EP的ID為“EP1號”，元數據為“IP:210.1.70.231；Port:8088;AS:EB”。每個 EP都會調用CP的HTS，將自己的ID和元數據信息在CP注冊，在聚類時再次調用HTS查詢其他EP元數據，尋找自己的鄰居節點。在開始發布流程時，CP會連接所有參與發布的EP，把其他EP的元數據信息通知EP，EP就獲得了其他參加發布的EP的地址和信息。

動態聚類算法的數學描述為：對某一個EP x而言，設參與發布的EP的總數為N，x的最大鄰居節點數為C，參與發布的其他EP中與x在同一個自治域的個數為M，如果用K表示鄰居節點中同一個自治域內EP的個數，則K應該滿足：

其中，a是一個系數，0.5

本文中采用的聚類算法，采用優先策略聚類和隨機鄰居選擇算法結合的方式，首先選擇和自己在同一個域的適量EP作為鄰居，同時與其他域的少量EP相連，這樣EP可以了解到其他域中內容分片的存儲情況，避免了同一個域中所有EP都缺少某些分片而從CP重傳的情況，減少了網間流量，提高了分發效率。

3.5 片選策略

確定好鄰居節點后，EP需要從鄰居節點或CP上下載內容分片，片選策略指的是EP采用何種策略從鄰居節點或CP處取得內容分片，往往與分發的內容類型有關，塊式內容和流式內容通常采用不同的分發策略。

最常用的片選策略是最少片優先策略，即EP優先選擇鄰居節點中存在副本數量最少并且自身還沒有獲得的內容片下載，使內容片均勻擴散到各個節點，避免最后一片出現問題時整個鄰居網內無法互傳的現象，緩解了CP和主干網絡的壓力，優化平均分發時間，但只適用于塊式內容。流式內容最重要的是按內容流的順序獲取分片，最少片優先并沒有考慮到內容分片的順序，因此無法滿足流式內容的分發要求。

本文采用的片選策略先將內容片設定優先級，根據優先級的高低將內容片劃分為緊急和非緊急兩個集合分別存取，將順序靠前和備份最少的內容片放入緊急集合，將其他分片放入非緊急集合，這樣既可以保證流式內容的按序分發，同時兼顧了塊式內容的備份最少片優先傳輸的要求。分發過程中內容片優先級是動態變化的，兩個集合的內容分片會不斷調整，適應實際的請求狀況和網絡情況。

假設內容分片的編號代表內容片在文件中的偏移量，由小到大排列。EP中內容片分為兩個集合存儲，一個為緊急集合，存儲當前緊急需要按序分發的流式內容，必須優先下載，否則內容流會中斷；另一個為非緊急集合，沒有時間緊迫性內容片。緊急集合中的內容片可以用數對（S，L）表示，S代表最小的內容片序號，L表示集合的大小，即內容片的數量，因此緊急集合中的內容片可表示為{S，S+1，S+2，…，S+L-1}。對于一個EP來說，緊急集合的補集即為非緊急集合。兩個集合中都含有已經被鄰居節點下載過的內容片，也有未曾下載的內容片。內容片的下載優先級用P表示，P越大，內容片越優先被下載，通常P取值為0.5～1。在分發開始之前，EP會先將內容片分成兩個集合，選定要下載的分片集合后，在兩個集合內部采用最少片優先的算法下載當前鄰居中副本數目最少的分片。傳統片選策略與自適應片選策略的比較如圖1所示。

這種片選策略是自適應的，S、L、P都是可動態調整的參數。如固定S為0，L為內容片數目，此時兩個集合合并，就變成了完全的最少片優先片選，適合非流式內容的分發；如果S隨時間的推移逐漸變大，L固定一個小于內容片總數的值，P根據內容的急迫性不斷調整，就可以支持流式內容的分發，適合流媒體業務。這樣就可以讓片選策略適應不同類型內容、不同業務的分發情況，達到良好的分發性能。

3.6 分發過程

內容分發過程是指自適應聚類片選分發模型的工作過程，包括分發模型從CP獲得分發任務到成功分發到EP的流程。假定所有參與分發的EP已經在CP注冊了HTS，分發流程如圖2所示。

在分發流程中，EP與鄰居節點交換分片信息時，用二進制的串表示內容片的下載與否[12]。如規定某位為0代表此內容片未下載，1代表已下載，這樣可用少量存儲空間表示內容分片的下載情況，當內容分片為256 KB時，1 GB的內容文件僅需要512 byte的空間。當某節點有新的內容分片加入時，EP將直接向其鄰居節點廣播新加入的內容分片序號，鄰居收到廣播信息后，更新自身中此節點的內容片位圖。當EP的鄰居節點中沒有要下載的分片的聚類時間達到閾值之后，將會重新聚類，這也是自適應的一種體現，動態地適應變化的網絡狀況，最大效率地獲取內容分片。當EP內的所有內容分片均被下載 （內容的二進制標志串各位都為1）時表示此EP已經接收完畢，向CP返回接收完畢信號，此時該EP停止聚類和片選，只向鄰居節點提供自身內容片的上傳。

圖1 片選示意

圖2 分發流程

在分發過程中CP會不斷向參與分發的EP發送輪詢消息，直到接收到EP的接收完畢的反饋信息，記錄當前分發進度。若此過程中某EP有失敗消息返回，CP將立即對該EP啟動重傳，并記錄錯誤信息，若依舊收到失敗返回消息，則調用HTS對此EP的屬性情況進行更新，然后放棄此EP，重新選擇替代EP加入分發流程。當所有EP都接收完畢之后，CP收到EP的成功接收信號，分發流程完成。

4 性能分析

當前的工程應用中，分發服務多采用BitTorrent模型，這種模型對于塊式內容的分發能達到比較好的效果，并且支持流式內容分發。為了驗證本文設計的分發模型的性能，在實驗室環境下設計實現了一個簡單分發模擬器，用于模擬自適應聚類片選模型和BitTorrent模型的分發過程，并且比較其性能。設計一個分發模擬器，其固定的聚類算法標準參數a為0.75，最少片優先最佳概率P為0.8，采用平均分發時間作為衡量塊式內容的性能標準，采用連續索引比（continuity index，CI）作為衡量流式內容性能標準，CI是指播放期限內下載的內容片與全部內容片的比值，比值越大，下載越流暢。塊式內容分發性能對比如圖3所示。流式內容分發性能見表2。

圖3 塊式內容分發性能對比

表2 流式內容分發性能記錄

從圖3和表2可以看出，在多域的流式塊式混合分發的應用場景中，采用參數集為{C=50，a=0.75，K=35，P=0.8}，本文所采用的分發模型的性能明顯優于傳統的BitTorrent模型。

5 結束語

本文采用的自適應聚類片選內容分發模型，采用網狀拓撲結構和自治域優先+隨機選擇的聚類算法，結合緊急內容最少片優先的動態片選策略，通過算法參數的調整，自適應地完成流式內容和塊式內容的快速分發，從而適應不同業務的分發需求，彌補了其他分發模型在支持內容類型上的不足，具有良好的擴展性。由于分發模型中網狀結構和鄰居節點的設置，分發過程中CP需要不斷調整EP的狀態，EP需要隨時維護自己的鄰居節點的內容信息，增加了開銷，一定程度上影響了分發性能，還有進一步改進的空間。

1 廖建新.移動智能網技術的研發現狀及未來發展.電子學報,2003(11)

2 程久軍,李玉宏,程時端等.移動P2P體系結構與關鍵技術的研究.北京郵電大學學報,2006,29(4):86～89

3 Francis P.Yoid:extending the multicast Internet architecture.http://www.aciri.org/yoid,1999

4 Pendakaris D,ShiS.ALMI:an application levelmulticast intfrastructure.In:The 3rd USENIX Symposium on Internet Techonlogies and Systemes,San Francisco,CA,USA,2001

5 Chu Y H,Rao S G,Seshan S,et al.A case for end system multicast.ACM SIGMETRICS Performance Evaluation Review,2000,28(1):1～12

6 Chu Y H,Rao S G,Seshan S,et al.Enabling conferencing applications on the Internet using an overlay multicast architecture.ACM SIGCOMM Computer Communication Review 2001,31(4):55～67

7 Zhuang S Q,Zhao B Y,Joseph A D.Bayeux:an architecture for scalable and fault-tolerant wide-area data dissemination.In:the Eleventh InternationalWorshop on Network and Operating System Support for Digital Audio and Video,New York,2001

8 RatnasamyS,Handleym,Kapp R,etal.Application-level multicast using content-addressable networks.In:Networked Group Communication,Third International COST264 Workshop,London,UK,2001

9 ZhaoB Y,KubiatowiczJD,Joseph A D.Tapestry:an infrastructure for fault-tolerant wide-are location and routing.USA:University of California,Computer Science Division,2001

10 BitTorrent Webside.http://www.bittorrent.com/,2007

11 天瑞雄.自組織覆蓋網絡建模與優化.清華大學碩士學位論文,2005

12 楊妙,王晶.IDP中消息分發模塊的改進.電信工程技術與標準化,2009,22(6)