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

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

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

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

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

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

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

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

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