- 學位論文
無線設備之瀏覽器快取演算法
Browser Cche Management Algorithms for Wireless Devices
若您是本文的作者，可授權文章由華藝線上圖書館中協助推廣。
摘要
隨著無線網路的普及，在移動式設備上瀏覽網頁將是一項重要的網路服務。 然而移動式設備有兩大特性，造成瀏覽網頁的效率差。 第一，無線網路的低資料傳輸速率，造成移動式設備擷取網頁的效率差。 第二，移動式設備只有少量的瀏覽器快取記憶體，無法將很多的網頁物件存在記憶體中，來減少網頁的存取時間。 瀏覽器快取置換演算法可以改善網頁瀏覽的效率，將有用的網頁物件存在瀏覽器快取記憶體中，剔除沒有用的物件。 使用者可以避免等待到遠端網頁伺服器擷取網頁的時間，只需使用快取記憶體中的網頁即可。 本論文針對移動式設備的特性，設計新的瀏覽器快取置換策略SAVUT，其中包含了三個部分，第一是物件價值計算函數的設計，第二是部分擷取策略，第三是部分置換策略。 SAVUT可以細分為部分置換SAVUT (PR-SAVUT)、部分擷取SAVUT (PC-SAVUT)、部分擷取置換SAVUT (PCR-SAVUT)等三種不同的演算法。 目的在於提高byte hit rate和reduced latency rate，來減少移動式設備需要從遠端網頁伺服器擷取的位元組數目，同時減少使用者等待網頁的時間。 經由模擬實驗得知以下的結果。 第一，在SAVUT細分出來的三種演算法當中，PR-SAVUT在byte hit rate和reduced latency rate方面的效能比PC-SAVUT和PCR-SVUT要好。 同樣的效能表現，部分置換LRU (PR-LRU)的效能也比部分擷取LRU (PC-LRU)和部分擷取置換LRU (PCR-LRU)的效能要好。 第二，和其他現存的置換演算法比較的話，在byte hit rate和reduced latency rate方面，PR-SAVUT比GDS(packet)和Min-SAUD的效能都要好。 PR-SAVUT在reduced latency rate方面，比PR-LRU要好。 在byte hit rate方面，當記憶體容量比16MB要大的時候，PR-SAVUT的效能比PR-LRU要好。 綜合以上所述，在byte hit rate和reduced latency rate方面，PR-SAVUT可以比GDS(packet)和Min-SUD的效能要好。 跟另一個同樣都是利用部分置換策略的演算法PR-LRU比的話，除了當記憶體大小為8MB時，PR-SAVUT無法表現的比PR-LRU好之外，當記憶體容量大於16MB時，PR-SAVUT的效能就比PR-LRU要好。
並列摘要
As the wireless network becomes popular, the Web surfing on mobile devices will be a popular Internet service. Mobile devices have two characteristics, which cause the inefficient wireless Web object dissemination. First, the low data transfer rate in the wireless network causes inefficient Web object dissemination. Second, there are only limited browser cache spaces in a mobile device. A mobile device can not save many Web objects in the browser cache to reduce the retrieval latency of Web objects. The browser cache replacement algorithm can improve the efficiency of the Web surfing by caching objects, which will be accessed again in the future. Instead of retrieving the Web objects from remote Web servers, the browser in the mobile device only needs to present the Web objects in the browser cache. In this thesis, we propose a new browser cache replacement algorithm, SAVUT. SAVUT is designed based on the characteristics of mobile devices. SAVUT has three major characteristics, which are the gain function, the partial caching mechanism, and the partial replacement mechanism. SAVUT separates into three different replacement algorithms, which are partial replacement SAVUT (PR-SAVUT), partial caching SAVUT (PC-SAVUT), and partial caching replacement SAVUT (PCR-SAVUT). These three replacement algorithms are the SAVUT-based replacement algorithms. The goals of the SAVUT-based replacement algorithms are to achieve the high byte hit rate and to reduce the perceivable latency time. The results of the simulation are in the following. First, the performance of PR-SAVUT outperforms PC-SAVUT and PCR-SAVUT. The performance of partial replacement LRU (PR-LRU) also outperforms partial caching LRU (PC-LRU) and partial caching replacement LRU (PCR-LRU). Second, compare with the performances of GDS(packet) and Min-SAUD in the byte hit rate and the reduced latency rate, PR-SAVUT outperforms GDS(packet) and Min-SAUD. PR-SAVUT outperforms PR-LRU in the reduced latency rate; PR-SAVUT also outperforms PR-LRU in the byte hit rate as the browser cache size is larger than 16MB.
參考文獻
[2] Joel F. Bartlett. Experience with a Wireless World Wide Web Client. In
[3] Timothy W. Bickmore and Bill N. Schilit. Digestor: Device-independent access
to the World Wide Web. Computer Networks and ISDN Systems, 29(8—
13):1075—1082, 1997.
Proceedings of the USENIX Symposium on Internet Technologies and Systems,