一種用于提高網(wǎng)絡(luò)性能的web規(guī)則驅(qū)動代理緩存模型

一種用于提高網(wǎng)絡(luò)性能的web規(guī)則驅(qū)動代理緩存模型

1代理緩沖技術(shù)世界上互聯(lián)網(wǎng)技術(shù)的普及正在推動，越來越多的應(yīng)用已經(jīng)開始建設(shè)在國際網(wǎng)絡(luò)上，如web瀏覽和信息發(fā)布?；ヂ?lián)網(wǎng)技術(shù)與網(wǎng)絡(luò)設(shè)備本身的局限性(網(wǎng)絡(luò)的吞吐能力、服務(wù)器的負(fù)荷能力和光信號在全球性復(fù)雜光纖網(wǎng)絡(luò)上的傳輸)導(dǎo)致網(wǎng)絡(luò)延時成為一個突出問題,例如,用戶瀏覽一個網(wǎng)頁的內(nèi)容時需要等很長時間。為減少網(wǎng)絡(luò)擁塞和網(wǎng)絡(luò)延遲問題,以提高網(wǎng)絡(luò)帶寬的使用效率,人們進(jìn)行了大量相關(guān)研究。代理緩存技術(shù)被認(rèn)為是提高網(wǎng)絡(luò)性能的主要方法。傳統(tǒng)代理緩存技術(shù)存在被動和命中率低等缺點,因此,本文提出一種Web規(guī)則代理緩存模型。2多特征融合的訪問行為處理該模型將規(guī)則數(shù)據(jù)挖掘技術(shù)和代理緩存管理相結(jié)合,是一種用于管理和調(diào)度的新代理緩存模型。模型假設(shè)代理服務(wù)器位于靠近用戶處,代理服務(wù)器下的用戶群具有一定數(shù)量規(guī)模和一定穩(wěn)定性,且用戶群的Web訪問行為具有一定規(guī)律性和周期性(從長期來看)。代理服務(wù)器能準(zhǔn)確地記錄下用戶的完整訪問行為。模型描述如下:設(shè)L={l1,l2,…,ln}為一個對象組,代表用戶經(jīng)過代理緩存服務(wù)器所訪問的Web對象集。由模型假設(shè)可知,L在一段時間內(nèi)應(yīng)具有一定穩(wěn)定性,且具備變化的連續(xù)性。設(shè)M是一個用戶訪問行為的事務(wù)集{T},T為代理服務(wù)器范圍對象集L的一個子集,即T?L。圖1描述了訪問行為T。根據(jù)圖1可知,T的劃分方式如表1所示。單個用戶的訪問行為具有一定周期性和規(guī)律性,例如,在某幾段時間內(nèi)請求的對象數(shù)較多,而在其他時間內(nèi)數(shù)量較少。根據(jù)上述原則,以圖1為例,將用戶的訪問行為劃分為T1和T2兩個事務(wù)較合理,這樣可以保證對象集的規(guī)模不是很大,并體現(xiàn)用戶的訪問行為特征,但在一定程度上增加了計算量。定義規(guī)則p為:A?B,且A?L,B?L,A∩B=ξ。本文引入規(guī)則支持度S和確信度C的概念。在訪問行為事務(wù)集M中,所有含有A的事務(wù)數(shù)目被定義為A的支持?jǐn)?shù),即所有含有A∪B的事務(wù)數(shù)與事務(wù)總數(shù)的比率被定義為規(guī)則p:A?B的支持度,即所有含有A且含有B的事務(wù)集合的數(shù)目與所有含有A的事務(wù)集合數(shù)目的比率定義為規(guī)則p:A?B的確信度,即可見,若確信度和支持度一定,就能發(fā)現(xiàn)多數(shù)用戶訪問行為的規(guī)律,即規(guī)則集:多數(shù)用戶在訪問某些Web對象時,最可能與之發(fā)生聯(lián)系的其他對象有可能在不久的將來提出請求。根據(jù)發(fā)掘出的P規(guī)則,代理緩存可以較準(zhǔn)確地根據(jù)用戶當(dāng)前的訪問行為預(yù)測其下一步可能的行為。在帶寬允許的條件下,預(yù)先請求或更新緩存中的對象集,以提高緩存中對象的命中率并有效利用帶寬。由此可知,相對于其他緩存技術(shù),P規(guī)則驅(qū)動的代理緩存具有很大優(yōu)勢,其模型如圖2所示。3基于規(guī)則驅(qū)動程序的代理緩沖優(yōu)化方案的排序在P規(guī)則驅(qū)動的代理緩存模型的基礎(chǔ)上,本文提出一種緩存優(yōu)化調(diào)度算法。3.1存儲機(jī)制和存儲約束現(xiàn)有的多數(shù)Web代理緩存器基于傳統(tǒng)內(nèi)存頁調(diào)度算法來實現(xiàn)。例如,最近最少使用(LeastRecentlyUsed,LRU)算法,它在內(nèi)存緩存中是一個有效算法,但不適合Web環(huán)境。因為Web文檔大小的可變性很大(從幾百個字節(jié)到幾兆字節(jié))且必須在Internet上傳輸,會有很大延遲。而在內(nèi)存緩存中,緩存對象(頁)的大小和通信延遲都是不變的。且Web文檔的訪問來自不同用戶,而內(nèi)存中對頁的訪問來自單個程序。因此,要求有適合Web環(huán)境的新的緩存機(jī)制。本文算法綜合考慮了文檔大小、文檔的訪問頻率和規(guī)律以及緩存器里文檔的最近流逝時間和緩存文檔的價值。對于算法性能的度量,一般采用以下3種衡量標(biāo)準(zhǔn):(1)請求命中率,文檔在緩存中的百分率。(2)字節(jié)命中率,緩存器所傳送的字節(jié)百分率。(3)延遲率,下載未選中的文檔所花的時間和下載所有文檔的時間的比率。本文分析并比較了3種典型調(diào)度算法的性能,具體如下:(1)LRU算法。最先移出最近最少使用的文檔。其優(yōu)點是實現(xiàn)簡單,在內(nèi)存緩存中很有效。其缺點是沒有考慮文檔大小或延遲時間。(2)SIZE算法。先清除大文檔。其優(yōu)點是移出大文檔,可以保留更多小文檔,產(chǎn)生更高請求命中率。其缺點是可能使小文檔永遠(yuǎn)留在緩存器中,字節(jié)命中率偏低,且再次下載大文檔時,占用網(wǎng)絡(luò)資源很多。(3)GD-SIZE算法。是基于代價的貪婪算法。緩存器中的每個文檔都有相應(yīng)的價值H,當(dāng)網(wǎng)頁被帶進(jìn)緩存器時,該網(wǎng)頁的H值為文檔大小的倒數(shù)。發(fā)生置換時,H值最小的文檔(Hmin)被換出,剩下的文檔的H值變?yōu)橹脫Q前的H值減去Hmin。該算法的優(yōu)點是不再被訪問的文檔會被清除,克服了SIZE算法的缺點。其缺點是沒有考慮文檔使用率和網(wǎng)絡(luò)延遲。3.2未來的文學(xué)檢察可能現(xiàn)有算法大多根據(jù)特殊值來選擇值,有時需要很好地估計參數(shù),在對引用參數(shù)的估計上需要復(fù)雜的計算和大量模擬。一些算法在參數(shù)改變時的性能轉(zhuǎn)換方面缺乏靈活性。本文提出的代理緩存優(yōu)化算法簡單描述如下:當(dāng)緩存器滿或高負(fù)荷時,如果有新的Web文檔到達(dá),那么依次置換代價最小的文檔,直到新的文檔能被存入緩存器為止,并根據(jù)規(guī)則P,預(yù)測下一步新的用戶請求的Web文檔。該優(yōu)化算法根據(jù)模型的P規(guī)則提出一個新概念——使用率,以此來評估Web文檔的代價。用變量Pi定量反映P規(guī)則,表示使用率。Pi是一個反映文檔未來被訪問的可能性大小的量,與文檔單元價值一起形成一個公平、一致的代價。設(shè)C(i)是清除文檔i的代價,ci是文檔的價值,si是文檔大小。使用率為Pi,文檔i代價為C(i)=Pi×ci/si,其中,ci/si是文檔的單元價值。使用率Pi必須能體現(xiàn)未來文檔被訪問的可能性大小。但由于未來的訪問是未知的,因此只能采用預(yù)測的方法,能否很好地近似體現(xiàn)文檔的訪問模式是衡量算法優(yōu)劣的重要標(biāo)準(zhǔn)。對使用率Pi,本文計算方法如下:設(shè)tc是最近一次訪問文檔后經(jīng)過的時間,tk是第k次訪問文檔和第k-1次訪問文檔之間的時間間隔,設(shè)第k-1次訪問文檔后的平均訪問間隔時間為λk-1,則第k次訪問文檔后得到的平均訪問間隔時間為其中,α是大于等于1/2的參數(shù);λ反映了文檔當(dāng)前的訪問率,當(dāng)前訪問率發(fā)生變化時,能迅速靈活地反映這種變化,令λf是最后一次訪問文檔后得到的平均訪問間隔,由指數(shù)分布的定義可得因此,文檔經(jīng)過時間tc后被訪問的概率為文檔下一次被訪問的平均時間間隔為其平均使用率為P’=1/(tc+λf)。使用率體現(xiàn)了在當(dāng)前時刻,文檔下一次被調(diào)用的可能性大小。從使用率的表達(dá)式可以看出,它由文檔的訪問歷史和現(xiàn)在流逝的時間組成。在流逝時間相同的情況下,過去使用率高的文檔,未來的使用率也高,而如果流逝的時間增加,則使用率自然下降,與實際觀測結(jié)果一致。代理緩存優(yōu)化算法是一個高效的算法。與其他算法不同的是,它基于P規(guī)則驅(qū)動的緩存模型,具有LRU算法的簡潔優(yōu)點,對文檔代價的計算不需要保留以前的訪問記錄,且不需要復(fù)雜的參數(shù)估計,并能根據(jù)Pi迅速地體現(xiàn)文檔訪問率的變動情況。由于采用文檔單位價值作為權(quán),因此可以客觀地反映清除文檔所需花費的代價。對于只訪問過一次的文檔,只要簡單地選取1/tc為使用率。4與web數(shù)據(jù)的比較圖3給出了請求命中率、字節(jié)命中率的實驗結(jié)果。實驗的過程模擬實際Web緩存過程。當(dāng)有新的請求到達(dá)模擬器時,檢查緩存器的內(nèi)容。如果請求的文檔在緩存器中,則更新使用率、延遲和最后一次引用時間,否則將文檔載入緩存器,按緩存優(yōu)化調(diào)度算法清除文檔。分析使用包括訪問日志在內(nèi)的茂名學(xué)院校園網(wǎng)FreeBSD-Squid代理服務(wù)器收集的Web數(shù)據(jù)。該數(shù)據(jù)集記錄了72GB的Web數(shù)據(jù),其最高訪問率為0.497、字節(jié)訪問率為0.472,低字節(jié)訪問率的可能原因是代理服務(wù)器很少記錄大尺寸文檔的重復(fù)請求。在實驗中,對該優(yōu)化調(diào)度算法與已有的LRU,SIZE,GD-SIZE算法作比較,對Web對象的不同特征進(jìn)行處理,如對象大小、訪問頻率和新穎性等。對本文算法,使用式(7)和式(8)分別對代理緩存調(diào)度性能的2個衡量標(biāo)準(zhǔn)進(jìn)行計算統(tǒng)計。5p規(guī)則驅(qū)動的代理存儲優(yōu)化調(diào)度模型的性能指標(biāo)分析如圖3所示,本文算法比SIZE的請求命中率高16%左右,比LRU高9%左右。根據(jù)P規(guī)則優(yōu)先級較低的文檔很少被訪問、存儲在代理緩存中的可能性很小,即使被存儲,也會很快被覆蓋。由于P規(guī)則驅(qū)動保證了使用率高的內(nèi)容在代理緩存中的長時間駐存,使得使用率低的內(nèi)容不再占據(jù)代理緩存空間,因此P規(guī)則代理緩存模型保證了本文優(yōu)化調(diào)度算法有更高的請求命中率。在字節(jié)命中率方面,本文算法的性能比SIZE高19%左右,P規(guī)則驅(qū)動的緩存模型保證了指定的文檔的較高支持度,因此,獲得了很高的使用率。較高的支持度保證有價值的文檔比其他文檔優(yōu)先存儲。所以,代理緩存中的內(nèi)容總是能保持最相關(guān)、最常用和高質(zhì)量的內(nèi)容。由于在代理緩存模型中已證明本文在解決延遲問題方面的優(yōu)勢,因此實驗未考察延遲率。6web代理存儲模型Web代理緩存是網(wǎng)絡(luò)應(yīng)用的一項關(guān)鍵技術(shù),它提高了網(wǎng)絡(luò)性能,減少