[發明專利]CDN預先主動選擇優質節點開展優化內容分發服務的方法

有效

• 申請號: 201210549447.5
• 申請日: 2012-12-17
• 公開（公告）號: CN102984279A
• 公開（公告）日: 2013-03-20
• 發明（設計）人: 呂智慧;吳杰;黃翼
• 申請（專利權）人: 復旦大學
• 主分類號: H04L29/08
• 分類號: H04L29/08;H04L29/06
• 代理公司: 上海正旦專利代理有限公司 31200
• 代理人: 陸飛;盛志范

1.一種CDN預先主動選擇優質節點開展優化內容分發服務的方法，其特征在于具體步驟為：

第一步:?定義和構建放大層

把一個邊緣CDN服務器以及它所領導的一批對等節點看作是一個自治區，把整個系統分為多個不同的自治區，每個自治區有一個CDN節點；在每個自治區內部，CDN節點通過從其所管理的對等節點獲得的信息來決定系統的問題和瓶頸，從而選出需要媒體內容數據并能力強的節點進入放大層，并為之提供服務；CDN節點使用輕量級的方法收集P2P節點的統計信息；每個對等節點不需要定期向其自治區的CDN節點匯報所有自己的信息，只要在向CDN節點請求緊急數據塊的情況下匯報這些信息；

每個匯報信息中都必須包括節點ID和時間戳；對于請求緊急數據的對等節點來說，提供：（1）請求塊列表，（2）篩選后的鄰居列表；如果一個節點被選為中介放大節點而接受CDN服務器的服務，它提供的信息有：（1）播放緩沖區情況，（2）播放點；當CDN服務器決定是否繼續服務一個中介放大節點時，CDN讓該對等節點提供：（1）流量上傳速度，（2）播放緩沖區情況，（3）上傳帶寬使用率，（4）播放點；

?(1)?建立放大層節點的基本架構

是從原有的P2P網狀結構中選拔節點形成一個擴展和放大層，即有若干節點直接從服務器獲取數據，獲取數據的方式采用的是CDN直接Push模式；假設CDN允許直接服務N個節點，會有N個節點與CDN做鄰居，其它節點均不能與CDN做鄰居；

(2)?放大層的初始建立機制

在開始階段，CDN節點開放N個直連通道，但沒有節點與其連接，之后隨著Peer節點的陸續加入，CDN開放的N個直連通道會依據某種算法被使用；

所謂放大層的含義是，在放大層的節點的上傳帶寬必須大于支持播放的最小碼流；設觀看所需的最小碼流大小為a，放大層中節點的最小上傳帶寬為b，則必須滿足條件a<b，這樣在它服務其他普通節點時才能起到放大傳播的作用；

設StreamingRate是流媒體直播中正常觀看所需要的碼流大小，N為放大層中節點的個數，則服務器在放大層中所消耗的流量總和為：

U_direct=StreamingRate?*?N????????????（公式1）

設為放大層中節點i，i∈[1,N]，的上傳帶寬，則放大層節點在上傳帶寬充分利用的情況下提供的流量是：

Umagnification=Σi=1NUpeeri]]>????（公式2）

顯然有U_{magnification}≥U_direct；

第二步:選擇和確定進入放大層的節點

每個向CDN服務器請求緊急數據塊即快要播放的數據塊的消息中，同時附上節點本身的一些信息,這些信息如第一步所述；CDN通過定期統計分析這些信息，找到進入放大層的節點并對其予以幫助，來提高CDN分發效率和系統總體性能；

在系統中，節點向CDN請求緊急的數據塊，做法是節點向CDN節點發送塊請求包，請求包內包括該節點所要請求的塊和該節點的鄰居中能力比較強的鄰居節點ID，這里，所謂能力比較強的節點指的是鄰居節點中上傳帶寬處在前50%的節點，請求包格式如下：

節點ID時間戳請求塊列表篩選后的鄰居列表

每隔一段時間，CDN節點對收集到的數據進行分析，統計每個請求節點的鄰居列表中的節點出現次數，并從中找出出現次數最多的若干個節點作為中介放大層節點；

最終CDN邊緣服務器選出k個節點作為中介放大節點，k的計算方法如下：

k=min(UCDN-Uoutgoing_rateSTRM_RATE*α*β,NUMonline_nodes10)]]>????（公式3）

β=e(NUMreqNUMonline_nodes-1)]]>????（公式4）

在公式中，α是常數，分子是CDN服務器的剩余帶寬乘以β，STRM_RATE*α是對CDN服務一個瓶頸節點每秒所需流量的期望值，是預估CDN剩下的流量最多能服務多少個中介放大節點；其中NUM_req是在該時間段內向CDN服務器發出請求的節點個數，NUM_{online_nodes}是該邊緣CDN服務器所管的節點總數；

第三步:給放大層節點直接提供內容分發服務

當CDN服務器從統計信息中找出k個中介放大節點，同時向這些節點發送服務啟動消息，這些中介放大節點在收到服務啟動消息后，返回自己的BufferMap給CDN服務器，CDN服務器根據每個節點的BufferMap情況進行相應的服務；

CDN服務器服務中介放大節點采用推送的方式，推送區域是Peer節點緩存區中的整個普通區，選擇該區域為服務對象的主要原因是為了降低冗余塊的個數，即節點自身拉到的塊與CDN服務器推來的塊相互重疊；因此CDN服務器首先查看中介放大層節點的緩沖區，找出在該服務區域內的所有缺失塊，并以一定碼流大小將其推送至對等節點；

CDN服務器根據如下公式決定在多少時間內把所有數據全部推送給對等節點：

Tfast=NUMlackSTRM_RATE/STRM_PACK_SIZE]]>????（公式5）

T_slow=T_fast×2????（公式4-8）

T=Tslow-(Tslow-Tfast)×NUMreq_nbrNUMmax_nbr]]>????（公式6）

NUM_lack指的是該服務區內缺失塊的個數，Tfast是把這些缺失塊以播放碼流的速度送出時所需要的時間，Tslow是把這些缺失塊以播放碼流速度的一半輸出所需要的時間；NUM_{req_nbr}表示該節點有多少鄰居向CDN服務器請求緊急塊，NUM_{max_nbr}表示每個節點的最大鄰居數，最終的時間T介于T_fast和T_slow兩個值之間，相應的傳輸速度介于播放碼流的一半和播放碼流之間；

第四步:?判斷對放大層節點的服務是否延續

當CDN節點服務了一個中介放大層節點一段時間T后，根據該節點的表現決定是否繼續服務該節點，判斷是否繼續服務的公式如下：

Uaverage=∫t=start_servicet=current_timeUoutgoing_rate(t)dtTcurrent_time-Tstart_service>Uoutgoing_rate(start_service)]]>????（公式7）

其中U_{outgoing_rate}(t)表示時刻t時，節點的上傳速度大小，表示從CDN服務節點開始到現在，該節點上傳的流量總數，U_average表示服務期間瓶頸節點的平均上傳流量；U_{outgoing_rate}(start_service)表示被服務前中介放大節點的上傳速度；滿足以上不等式，CDN即可繼續服務該對等節點；繼續服務的緩沖區區間不變，CDN服務器會根據如下公式決定在多少時間內把所有數據全部推送給對等節點：

T=Tslow-(Tslow-Tfast)×Uploadpeer-UcurrentUploadpeer]]>????（公式8）

T_fast和T_slow的意義與上節相同，Upload_peer表示中介放大節點的上傳帶寬；

第五步:?放大層節點的更換

放大層節點需要不斷更新和替換，每隔一段時間，放大層直連節點對自己的鄰居進行一次掃描，找出那些能力即上傳帶寬比自己強，且不是直連節點的鄰居節點；找到以后，該直連接節點利用一定策略，把該節點置換到放大層，而自己重新變為普通節點從放大層退出；

每個節點定時觸發一次該算法，只有放大層的節點才執行該算法流程；在找出的優質鄰居節點符合交換條件的時候，首先判斷該鄰居節點的鄰居數是否達到了上限，如果沒有，只讓該鄰居與CDN節點建立連接，本節點與CDN斷開連接，這樣該鄰居節點的鄰居數增加一；否則，解除本節點與該鄰居節點的鄰居關系，用以騰出該鄰居節點的可用鄰居連接讓給CDN服務器；

當一個放大層節點離開系統時，它選出自己最強的鄰居節點來替換自己，以保證放大層節點的擴展性和穩定性；

第六步:?定時監控放大層節點

為了避免放大層的節點在找鄰居時會與同樣在放大層的節點建立鄰居關系,我們需要定時監控放大層節點的算法，對于節點來說也是間隔一段時間執行一次，即首先判斷自己是不是放大層節點，不是的話直接退出操作；否則，檢查自己所有的鄰居，如果發現沒有一個鄰居是放大層節點的話就退出，否則將解除自己與該節點的鄰居關系，由于解除鄰居關系后本節點的鄰居節點個數減少，因此要重新執行鄰居查找算法對自己的鄰居數進行補充；

第七步:?動態調整放大層節點的數量

在一段時間內有大量節點陸陸續續的加入時，需要增加放大層中的節點數目來提高系統的服務質量；具體是通過利用CDN服務器在運行時收集到的信息來動態調整放大層中的節點數量，該動態調整算法如下：

其中，用node_num?表示放大層中允許的最大節點數量，urgent_outgoing表示CDN服務器用于服務peer節點緊急請求的平均上傳流量，?direct_outgoing表示服務放大層的平均上傳流量，這兩個平均上傳流量定時統計一次；該算法的公式表示如下，

node_num=node_num*θ,ifurgent_outgoingdirect_outgoing≥0.4node_numλ,ifurgent_outgoingdirect_outgoing≤0.15]]>????（公式9）

其中θ是1.3，λ是1.2。

2.根據權利要求1所述的方法，其特征在于，第五步中，所述當一個放大層節點離開系統時，它選出自己最強的鄰居節點來替換自己，以保證放大層節點的擴展性和穩定性，

具體算法流程如下：

（1）向自己的所有鄰居發送斷開連接請求；

（2）如果是非放大層節點，則轉第（5）步，否則轉到第（3）步；

（3）遍歷自己的鄰居列表，找出能力最強的節點，對該最強節點發出消息包，使其在鄰居列表加入CDN邊緣服務器的信息并把退出節點的信息從鄰居列表中刪除；

（4）向CDN服務器發出消息包，使其在鄰居列表加入新節點的信息并把該退出節點的信息從鄰居列表中刪除；

（5）刪除本機鄰居列表中的所有信息并退出系統。