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

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

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

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

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

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

6、算法能夠大大降低CDNs中的平均請(qǐng)求延遲。
　　三、針對(duì)無(wú)線Mesh網(wǎng)絡(luò)中的內(nèi)容鏡像分發(fā)問(wèn)題，結(jié)合內(nèi)容對(duì)象的分布密度與內(nèi)容熱度之間的最優(yōu)關(guān)系，考慮到Mesh路由器的服務(wù)模型，提出了一個(gè)全新的動(dòng)態(tài)分布式四階段內(nèi)容分發(fā)算法，以適應(yīng)無(wú)線Mesh網(wǎng)絡(luò)環(huán)境。首先，依據(jù)無(wú)線Mesh網(wǎng)絡(luò)的分布式特點(diǎn)，對(duì)網(wǎng)絡(luò)拓?fù)涫褂脛澐炙惴ㄟM(jìn)行分布化。然后，根據(jù)內(nèi)容對(duì)象的熱度信息，計(jì)算出每個(gè)內(nèi)容對(duì)象所需的鏡像數(shù)目。在網(wǎng)絡(luò)拓?fù)鋭澐值幕A(chǔ)上，結(jié)合網(wǎng)絡(luò)中的請(qǐng)求模型和服

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

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