基于最小緩存替換算法的流媒體文件lru-lfi方法

基于最小緩存替換算法的流媒體文件lru-lfi方法

internet的快速發(fā)展使它成為基于社會(huì)信息的承載者。網(wǎng)絡(luò)上的文本和圖片等靜態(tài)信息已經(jīng)不能充分滿足人們的需要。日益成熟的數(shù)字多媒體技術(shù)使得在Internet上開(kāi)展各種流媒體應(yīng)用如VoD(VideoonDemand)、IPTV(InternetProtocolTelevision)、遠(yuǎn)程教育、視頻會(huì)議等已逐步成為現(xiàn)實(shí)。然而,由于現(xiàn)有的互聯(lián)網(wǎng)絡(luò)是建立在傳輸非實(shí)時(shí)數(shù)據(jù)的基礎(chǔ)上的,缺乏對(duì)延遲、抖動(dòng)、包丟失率等敏感的實(shí)時(shí)通信的良好支持,影響了流媒體傳輸?shù)男阅?造成用戶可感知質(zhì)量的降低。流媒體代理緩存技術(shù)通過(guò)在骨干網(wǎng)絡(luò)的邊緣靠近用戶的地方部署代理服務(wù)器來(lái)緩存熱門視頻節(jié)目的部分或全部數(shù)據(jù),為后來(lái)的用戶請(qǐng)求提供服務(wù),減少了啟動(dòng)延遲,降低了骨干網(wǎng)絡(luò)和流媒體服務(wù)器負(fù)載,而成為了近年來(lái)網(wǎng)絡(luò)應(yīng)用的研究熱點(diǎn)。1流媒體代理存儲(chǔ)模式單一，過(guò)于單一流媒體代理緩存的系統(tǒng)結(jié)構(gòu)如圖1所示,其相對(duì)于現(xiàn)在已廣泛使用于Web對(duì)象的代理緩存技術(shù)有如下特點(diǎn):1)流媒體對(duì)象的大小通常比傳統(tǒng)Web對(duì)象要大幾個(gè)數(shù)量級(jí)。因此,完全緩存對(duì)象的實(shí)現(xiàn)方式在流媒體代理緩存中會(huì)大大降低緩存空間利用率和命中率,并不現(xiàn)實(shí)。2)流媒體對(duì)象通常都具有一次寫(xiě)多次讀的性質(zhì),很少進(jìn)行改變,因此在流媒體緩存中,緩存的一致性并不是非常重要的問(wèn)題。3)用戶通常只瀏覽流媒體文件的起初部分以決定是否繼續(xù)觀看,因此在設(shè)計(jì)流媒體代理緩存系統(tǒng)時(shí)必須考慮如何適應(yīng)該情況。4)流媒體傳輸對(duì)網(wǎng)絡(luò)帶寬、時(shí)延、丟包率等有較高的要求,這些因素都會(huì)直接影響到用戶觀看節(jié)目的質(zhì)量。這些特性的存在,使得不能直接照搬傳統(tǒng)的Web緩存技術(shù),而必須開(kāi)發(fā)一種適用于流媒體的代理緩存技術(shù)。2自適應(yīng)和延遲策略在流媒體代理緩存的設(shè)計(jì)中,現(xiàn)有的緩存算法研究幾乎都是基于部分緩存進(jìn)行的,主要差別體現(xiàn)在分段策略和性能影響因素上。分段策略方面,Sen等人提出前綴緩存算法以減少流媒體的延遲和抖動(dòng)。Lim等人提出SCU算法,旨在提高緩存的前綴字節(jié)命中率,減少訪問(wèn)延遲,降低流媒體播放時(shí)的網(wǎng)絡(luò)傳輸成本。Wu等人提出指數(shù)增長(zhǎng)的分段策略能夠快速替換片段來(lái)適應(yīng)緩存對(duì)象的訪問(wèn)模式的變化。Chen等提出一種基于自適應(yīng)和延遲的分段方法。在緩存性能影響因素方面,最有影響的當(dāng)數(shù)資源訪問(wèn)的局部性原理和資源的訪問(wèn)頻率。LRU和LFU算法就是分別考慮訪問(wèn)近期性和訪問(wèn)頻率的實(shí)現(xiàn)方式,但LFU存在緩存污染問(wèn)題,LRU存在長(zhǎng)環(huán)模式問(wèn)題。同時(shí),這兩種算法還容易出現(xiàn)持續(xù)替換同一媒體對(duì)象的問(wèn)題,導(dǎo)致文件緩存內(nèi)容被完全釋放的概率增大,請(qǐng)求命中率下降和響應(yīng)延遲增加。鑒于此,EELRU通過(guò)偵測(cè)循環(huán)訪問(wèn)模式的長(zhǎng)度,以自適應(yīng)選擇替換出的對(duì)象。文獻(xiàn)將前綴和后綴分開(kāi)緩存并采用不同替換策略的方式,但這樣增加了替換算法開(kāi)銷及存儲(chǔ)空間管理的復(fù)雜程度。LRU-K和LCB-K考慮了對(duì)象最近K次被引用的信息,將訪問(wèn)頻率和訪問(wèn)的最近性綜合到價(jià)值函數(shù)的設(shè)計(jì)之中,具有較好的性能。RBC算法考慮了文件大小和所需的發(fā)送帶寬因素,ATCB-SCU算法則重點(diǎn)考慮傳輸代價(jià)。IntervalCaching策略通過(guò)結(jié)合磁盤緩存和內(nèi)存緩存技術(shù)提高了性能,但它的有效性隨著訪問(wèn)間隔的增加而失效。LRFU統(tǒng)一考慮訪問(wèn)頻率和近期性,在兩者之間進(jìn)行折中?，F(xiàn)有的緩存替換算法在建立緩存價(jià)值函數(shù)時(shí),幾乎沒(méi)有考慮緩存的字節(jié)有效性,而緩存字節(jié)有效性對(duì)提高緩存空間利用率和字節(jié)命中率具有重要的影響,但文獻(xiàn)中的算法采用的是整體緩存的思想,具有一定的局限性。3算法的設(shè)計(jì)3.1文件存儲(chǔ)文件的信息調(diào)整與存儲(chǔ)在保證緩存內(nèi)容能有效屏蔽代理服務(wù)器獲取媒體剩余部分內(nèi)容延遲的情況下,將媒體文件等分成若干段,正在對(duì)請(qǐng)求進(jìn)行服務(wù)的流媒體文件緩存內(nèi)容不允許被替換。設(shè)緩存替代請(qǐng)求時(shí)刻為t,記此時(shí)緩存中的流媒體文件集合為FileSet(t)={1,2,…,n},文件i在代理服務(wù)器中緩存部分的大小為Sizei(i∈FileSet(t));估計(jì)文件i以后會(huì)被使用的概率為Pi(t),緩存容量上限為B。為了最大化緩存空間的利用率和字節(jié)命中率,t時(shí)刻執(zhí)行緩存替代策略后應(yīng)使得:Μaximaize∑i∈FileSet(t)Ρi(t)×δi(t)(1)同時(shí)滿足約束條件:∑i∈FileSet(t)Sizei≤B(2)其中,δi(t)表示媒體文件的字節(jié)有用性,由于用戶在請(qǐng)求某個(gè)媒體文件服務(wù)時(shí),可能在任意播放位置停止。因此,媒體文件對(duì)于用戶來(lái)說(shuō),并不一定是整體有用,而是部分地有用,應(yīng)該對(duì)文件i中具有使用價(jià)值的部分進(jìn)行評(píng)估,即考慮媒體文件的字節(jié)有用性。設(shè)文件i大小為si,共播放m次,第j次播放時(shí)間為tj(0<j≤m),平均播放速率為ri,則對(duì)δi(t)的計(jì)算如下:δi(t)=m∑j=1ri×tjsi(3)對(duì)于(2)式,假定每個(gè)文件的緩存大小遠(yuǎn)小于總的緩存空間大小,因此緩存文件占用的空間達(dá)到最大時(shí),可以忽略剩下的部分空間,則(2)式可近似為:∑i∈FileSet(t)Sizei=B(4)該問(wèn)題實(shí)際上是一個(gè)背包問(wèn)題,求解該問(wèn)題是NP難的。因此,采用近似最優(yōu)化算法,對(duì)每個(gè)文件i,在時(shí)刻t建立緩存效用函數(shù):φi(t)=Ρi(t)×δi(t)Sizei(5)在算法執(zhí)行時(shí),計(jì)算每個(gè)媒體文件的緩存效用值,每次替換出效用值最小的文件的最后一段。在效用函數(shù)中,綜合考慮媒體文件最近K次訪問(wèn)的情況和在緩存中的緩存大小,結(jié)合媒體文件的字節(jié)有用性,動(dòng)態(tài)地改變文件的緩存效用。隨著文件緩存部分的減小,其緩存效用會(huì)逐漸變大,使得同一文件中越靠近起始部分的段擁有相對(duì)越高的緩存效用,從而避免了在LRU和LFU替換算法中出現(xiàn)文件被連續(xù)替換,導(dǎo)致文件緩存內(nèi)容被完全釋放,緩存空間利用率下降和播放啟動(dòng)延遲增大等問(wèn)題。同時(shí),算法考慮了文件的字節(jié)有用性對(duì)緩存空間利用率的影響。3.2文件有效估計(jì)在式(5)建立的緩存效用函數(shù)中,參數(shù)δi(t)和Sizei都比較容易計(jì)算,關(guān)鍵是對(duì)參數(shù)Pi(t)的估算。由于對(duì)任意文件i的訪問(wèn)假定獨(dú)立且服從參數(shù)為λi(t)的泊松過(guò)程通常是有效的,所以可以通過(guò)式(6)估算Pi(t):Ρi(t)=λi(t)n∑j=1λj(t)(6)因?yàn)槲覀兊奶鎿Q是通過(guò)對(duì)文件的效用值排序來(lái)決定的,因此將(6)式帶入(5)中,可簡(jiǎn)化為:φi(t)=λi(t)×δi(t)Sizei(7)對(duì)于λi(t)的估算,參照文獻(xiàn)的估算方法,記文件被評(píng)估的最近訪問(wèn)次數(shù)為ki(t),其最大值為K,tki為文件倒數(shù)第ki次訪問(wèn)的時(shí)間,則:λi(t)=ki(t)t-tki(8)將(8)式帶入(7)中,得到效用函數(shù)為:φi(t)=ki(t)t-tki×δi(t)Sizei(9)3.3文件被請(qǐng)求概率SCU-K算法考慮了文件最近K次訪問(wèn)情況,使文件的緩存長(zhǎng)度隨文件被請(qǐng)求概率的變化和文件在多次播放中體現(xiàn)出的字節(jié)有用性而動(dòng)態(tài)變化,同時(shí)使文件的前綴部分擁有更高的緩存價(jià)值,降低文件被連續(xù)替換而最終被完全替換出緩存的概率。在算法的描述中,作如下約定:4測(cè)試與分析4.1系統(tǒng)運(yùn)行過(guò)程我們?cè)O(shè)計(jì)了一個(gè)離散事件仿真器,用以模擬代理服務(wù)器對(duì)緩存的操作行為,模擬器由用戶的請(qǐng)求驅(qū)動(dòng)運(yùn)行。當(dāng)有新的請(qǐng)求到達(dá)仿真器時(shí),檢查緩存是否命中,同時(shí),仿真器按照緩存替換算法決定是否增加緩存和進(jìn)行緩存替換。模擬器設(shè)計(jì)和運(yùn)行參數(shù)如表1。4.2不同存儲(chǔ)空間下的編碼算法在缺乏樣品個(gè)數(shù)和sd我們對(duì)SCU-K與LRU,LFU,LRU-K算法在緩存字節(jié)命中率和平均啟動(dòng)延遲方面進(jìn)行了對(duì)比模擬實(shí)驗(yàn)。對(duì)于LRU-K算法,因?yàn)槠湔w性能在K=2時(shí)最好,所以選擇與LRU-2進(jìn)行對(duì)比實(shí)驗(yàn)。首先,比較SCU-K算法在K取不同值時(shí)的性能,結(jié)果如圖2(a)所示,隨著K值的增大,SCU-K算法在字節(jié)命中率指標(biāo)上都呈上升趨勢(shì),尤其是當(dāng)K=2時(shí),性能增幅最明顯(增幅最大約為14.1%),因此對(duì)比實(shí)驗(yàn)時(shí)SCU-K中取K=2。圖2(b)顯示了緩存字節(jié)命中率相對(duì)于不同緩存大小的變化情況,隨著緩存空間的增大,四種算法在字節(jié)命中率上呈上升趨勢(shì),LRU字節(jié)命中率最低,LFU優(yōu)于LRU,LRU-2比LFU的字節(jié)命中率增加約0.7%到6.3%,SCU-2除了考慮文件的訪問(wèn)頻率和訪問(wèn)近期性以外,還體現(xiàn)了文件的字節(jié)有用性對(duì)緩存的影響,增大了緩存空間利用率,在緩存字節(jié)命中率方面性能最好,相對(duì)于LRU-2平均增幅約為3.9%。圖2(b)顯示了平均啟動(dòng)延遲相對(duì)于不同緩存大小的變化情況,隨著緩存空間的增大,四種算法的啟動(dòng)延遲都成下降趨勢(shì),LFU和LRU算法性能明顯不如LRU-2和SCU-2,其主要原因是存在連續(xù)替換而導(dǎo)致文件最終被全部替換出緩存的問(wèn)題。SCU-K通過(guò)將媒體文件緩存大小作為緩存效用的變量,使媒體段越靠近起始部分具有相對(duì)越高的緩存效用來(lái)解決這一問(wèn)題,降低了文件前綴部分被替換的概率,因此在降低啟動(dòng)延遲方面具有更高的優(yōu)勢(shì)。5采用scu-k算法進(jìn)行文件存儲(chǔ)和替換綜上所述,流媒體緩存技術(shù)是提高流媒體傳輸系統(tǒng)效率,降低骨干網(wǎng)絡(luò)帶寬消耗,服務(wù)器負(fù)載和播放啟動(dòng)延遲的重要手段。文中提出的SCU-K算法綜合考慮了流媒體文件字節(jié)有用性對(duì)提高緩存空間利用率的影響和前綴緩存對(duì)降低啟動(dòng)延遲的影響,以文件最近K次訪問(wèn)情況為基礎(chǔ)建立緩存效用作為替換依據(jù),每次替換緩存效用最小的文件的媒體段。SCU-K算