延遲優(yōu)化的內(nèi)容分發(fā)技術研究.pdf

1、內(nèi)容分發(fā)網(wǎng)絡(Content Delivery Network，CDN)作為網(wǎng)絡中緩解大量并發(fā)訪問引起的擁塞問題的有效技術，得到了國內(nèi)外學術界和產(chǎn)業(yè)界的廣泛關注。在內(nèi)容分發(fā)網(wǎng)絡中，內(nèi)容被復制并存儲在多個鏡像服務器中，這使得內(nèi)容可以快速地被終端用戶訪問，大大降低了終端用戶的平均請求延遲。由于更多的鏡像服務器會帶來更大的部署和維護成本，合理地部署鏡像服務器對于內(nèi)容分發(fā)網(wǎng)絡至關重要。另外，鏡像服務器的容量是有限的，如何選擇鏡像內(nèi)容分發(fā)到各鏡像

2、服務器中，直接決定了內(nèi)容分發(fā)網(wǎng)絡的網(wǎng)絡性能。
　　基于內(nèi)容分發(fā)網(wǎng)絡中現(xiàn)有的研究成果，本文分別從鏡像服務器部署和鏡像內(nèi)容分發(fā)兩個方向研究了內(nèi)容分發(fā)網(wǎng)絡中的相關問題，以降低網(wǎng)絡中的平均請求延遲。在鏡像內(nèi)容分發(fā)問題中，從靜態(tài)內(nèi)容分發(fā)方法和動態(tài)內(nèi)容分發(fā)方法兩方面進行了研究。其中，對于動態(tài)內(nèi)容分發(fā)方法，本文結合無線Mesh網(wǎng)絡和無線融合網(wǎng)絡的特征，分別設計了相應的內(nèi)容分發(fā)機制。本文的主要研究內(nèi)容及貢獻如下四個方面。
　　一、基于網(wǎng)絡中

3、請求的統(tǒng)計特性與鏡像服務器的服務模型，研究了內(nèi)容分發(fā)網(wǎng)絡中的鏡像服務器部署方法，以降低網(wǎng)絡中的平均請求延遲，提高CDNs應用的網(wǎng)絡性能。每個的用戶請求被模擬為獨立泊松分布，而鏡像服務器被作為M/M/1排隊模型。在給定請求率、鏡像服務器的服務率、最大可部署的鏡像服務器數(shù)量和服務器的請求等待時間期望值上界的條件下，我們所研究的問題是從待選位置中選出一個子集來部署鏡像服務器，通過最小化網(wǎng)絡中正在傳輸?shù)恼埱髷?shù)與鏡像服務器隊列中等待的請求數(shù)之和，

4、達到網(wǎng)絡中平均請求延遲的最優(yōu)化。我們對該問題進行了形式化定義，并證明了其NP困難性。禁忌搜索算法和拉格朗日松弛算法被用于解決該問題，其中禁忌搜索算法引入禁忌列表來避免重復搜索，拉格朗日松弛算法可以獲得較好的近似比。實驗證明，我們所提出的算法均能獲得較低的平均網(wǎng)絡時延，并有效地用于實際CDNs的鏡像服務器部署。
　　二、內(nèi)容被劃分為多個內(nèi)容對象，對于每個內(nèi)容對象，將其熱度定義為該內(nèi)容對象的請求在所有請求中所占的百分比。根據(jù)內(nèi)容對象的

5、熱度信息，我們可以將內(nèi)容預分配到各個鏡像服務器上，用戶請求便可被定向至最近的緩存有所需內(nèi)容對象的鏡像服務器。我們既考慮了內(nèi)容的熱度，也考慮了鏡像服務器的服務能力，通過合理的模型構建，對基于內(nèi)容熱度的靜態(tài)鏡像內(nèi)容分發(fā)問題進行了形式化的定義。由于該問題的NP困難性，本文提出了兩個啟發(fā)式算法:貪心移除算法和禁忌搜索算法，用于得到可行的靜態(tài)鏡像內(nèi)容分發(fā)方案。最后，仿真實驗數(shù)據(jù)顯示，我們的方法能夠以較高的概率得到可行的鏡像內(nèi)容分發(fā)方案，且禁忌搜索

6、算法能夠大大降低CDNs中的平均請求延遲。
　　三、針對無線Mesh網(wǎng)絡中的內(nèi)容鏡像分發(fā)問題，結合內(nèi)容對象的分布密度與內(nèi)容熱度之間的最優(yōu)關系，考慮到Mesh路由器的服務模型，提出了一個全新的動態(tài)分布式四階段內(nèi)容分發(fā)算法，以適應無線Mesh網(wǎng)絡環(huán)境。首先，依據(jù)無線Mesh網(wǎng)絡的分布式特點，對網(wǎng)絡拓撲使用劃分算法進行分布化。然后，根據(jù)內(nèi)容對象的熱度信息，計算出每個內(nèi)容對象所需的鏡像數(shù)目。在網(wǎng)絡拓撲劃分的基礎上，結合網(wǎng)絡中的請求模型和服

7、務模型，使用分布式的算法生成內(nèi)容鏡像的分發(fā)策略，以降低網(wǎng)絡中的平均請求時延。最后，采用協(xié)作式的內(nèi)容分發(fā)方式，將內(nèi)容鏡像分發(fā)到各個Mesh路由器。仿真實驗證明，該算法可在不明顯增加網(wǎng)絡負載的情況下，有效地降低網(wǎng)絡中的平均請求時延。
　　四、研究了結合廣播網(wǎng)絡和4G/LTE的無線融合網(wǎng)絡中基于推送的動態(tài)內(nèi)容分發(fā)，內(nèi)容對象通過廣播和4G/LTE蜂窩網(wǎng)絡單播兩種方式推送到終端用戶。在這樣的網(wǎng)絡模型下，熱門內(nèi)容對象通過廣播的方式，推送給網(wǎng)絡

8、覆蓋范圍內(nèi)的所有終端用戶;其余的內(nèi)容對象通過4G/LTE蜂窩網(wǎng)絡，根據(jù)用戶的需求發(fā)送至終端用戶?；谶@樣的內(nèi)容分發(fā)流程，我們設計了高效的基于BCSA算法的無線融合網(wǎng)絡的內(nèi)容分發(fā)機制，摒棄了以往優(yōu)先將最熱門的內(nèi)容資源進行廣播的方案，使用了近似算法，合理地對廣播的內(nèi)容對象進行選擇，優(yōu)化廣播內(nèi)容請求的總帶寬。在蜂窩網(wǎng)絡部分，我們對緩沖隊列的長度與網(wǎng)絡延遲和丟包率的關系進行了研究。最后，通過仿真實驗對基于BCSA算法的無線融合網(wǎng)絡的效果進行了實