Replacement problem in web caching
Web gaçişi belleklerinde yerleştirme problemi
- Tez No: 129218
- Danışmanlar: PROF. DR. ERDAL ARIKAN
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Web'de geçici bellek, internet, geçici bellekte yeniden yerleştirme. iv, Web, Ön bellek, Web caching, internet, removal algorithms, cache replacement. J fl 3m iii S © y g Si ""W, Web, Cache, Internet
- Yıl: 2002
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Elektrik-Elektronik Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
ÖZET WEB GEÇİCİ BELLEKLERİNDE YERLEŞTİRME PROBLEMİ Seda Çakıroğlu Elektrik ve Elektronik Mühendisliği, Yüksek Lisans Tez Yöneticisi: Prof. Dr. Erdal Ankan Haziran 2002 World Wide Web, dünya çapında ağ, paylaşılmış veri nesnelerine erişim sağlayan büyük, dağıtık bir bilgi sistemidir. Web'in büyüklüğünün üstel artışı iletişim ağında tıkanıklık ve sunucularda fazla yüklenmeye sebep olur. Web'de geçici bellek kullanımı servisteki darboğazları engelleyecek ve ağ trafiğini azaltacak bir çözüm yöntemi olarak kabul edilmiştir. Bu şekilde kul lanıcıların maruz kaldığı gecikme azaltılmış olur. Bu çalışmada belleklerdeki yerleştirme prob lemi üzerinde durulmuştur. Problem, erişim maliyetini minimize etmek için sınırlı büyüklükteki belleklerde hangi sayfaların tutulması gerektiğine karar vermektir. Herbiri birbirine bağlı ve C kadar saklama alanına sahip İV tane geçici belleğin üzerinde sayfa yerleştirmenin en iyi yolu aranmıştır. Veri nesneleri uzayının P elemanlı olduğu varsayılmış ve nesneler için hem tek- tip hem değişken büyüklük modelleri kullanılmıştır. Problem, çözümü standart metodlarla İV, C ve P cinsinden üstel olan bir optimizasyon problemi olarak formüle edilmiştir. Ayrıca yaklaşık çözümler elde etmek için FIFO (ilk-gelen-ilk-atılan), LFU (en-az-sıklıkla-kullanılan), LRU (en-uzak-zamanda-kullanılmış) gibi daha az işlem gerektiren yerine yerleştirme algorit maları denedik. Bunların performanslarını belli bir olasılık dağılımına göre yarattığımız sanal istekler ve gerçek Web trafiği kayıtlarıyla test ettik. Farklı algoritmlarm elde ettiği, sayfaların geçici bellekte bulunma oranlarını ve toplam maliyetlerini karşılaştırdık. Optimum çözüme ulaştığı düşünülen çevrimdışı algoritma LFD'nin (en-uzak-zamanda-istenecek), kullanılan trafik için en iyi sonucu vermediği görülmüşür. Onun yerine kayan pencere metodu kullanılmalıdır. Elde edilen sonuçlar gösteriyor ki, istekler zamandan bağımsız bir olasılık dağılımına sahipse basit bir sabit yerleştirme algoritması sayfaların geçici bellekte bulunmasında maksimum oranı ve toplam maliyette de iyi bir seviyeyi elde elder. Eğer istekler sıklıkla değişiyorsa, çabuk uyum sağlayabilmek ve olası en kötü durumu iyileştirmek için raslantısal bir algoritma seçilmelidir. Algoritmaların sonuca ulaşma zamanlarının analizi gösteriyor ki sayfaların istenme olasılıklarını kullanan algoritmalar ancak az elemanlı uzaylarda kullanılabilir. Farklı istek dağılımlarının geçici belleğin performansına etkileri tartışılmış ve son olarak özelliğine en uygun yöntemi önermek için Web trafiğinin bir analizi yapılmıştır.
Özet (Çeviri)
ABSTRACT REPLACEMENT PROBLEM IN WEB CACHING Seda Çakıroğlu M.S. in Electrical and Electronics Engineering Supervisor: Prof. Dr. Erdal Ankan June 2002 World Wide Web is a large distributed information system that provides access to shared data objects. Exponential growth of Web's size results in network congestion and server over loading. Web caching has been recognized as an effective scheme for avoiding service bottleneck and reducing network traffic. In this way it minimizes user access latency. Our work focus on the replacement problem, that is deciding which pages to keep in a memory of limited size to minimize the retrieval cost. We seek the best configuration for a network of N caches with capacities C, where all caches are connected to each other. The universe of data objects is assumed to contain P items. Both uniform and nonuniform size models are used for data ob jects. The problem is formulated as a discrete optimization problem whose solution by standard methods is exponential in N, C and in P. We also study a number of low-complexity heuristics to obtain approximate solutions such as FIFO (first-in-first-out), LRU (least-recently-used), and LFU (least-frequently-used). We test the performances of the algorithms both by fictitious re quests generated according to a probabilistic distribution and by access logs of real Web traffic. The hit ratios and total costs of the algorithms are compared. For the traffic used, it is shown that LFD (longest-forward-distance), the classical optimal off-line paging algorithm, is not op timal. Instead a window scheme should be used. Results obtained indicate that if requests follow a stationary probabilistic distribution, a simple static placement algorithm achieves the maximum hit rates and reasonably good cost levels by using the arrival probabilities. Oth erwise, for a quick adaptation to changing requests and for better worst-case performances a randomized algorithm should be chosen. Analysis of the convergence-times shows that the algorithms using probability information have higher order run-time complexities, which limit their usage to small object space cases. The effects of the request sequence on the caches' performance are discussed. Finally, we give an analysis of Web data to propose best heuristics for its characteristics. - & $.'3 i '?'?
Benzer Tezler
- Parsiyel androjen yetersizliğinin alt üriner sistem ve erektil disfonksiyona etkisi
The effect of partial androgen deficiency on lower urinary tract and erectile function
TUNÇ OZAN
- Renk ayırım sistemlerinde PCR ve UCR tekniklerinin incelenmesi, bunların baskı kalitesine etkisi
Başlık çevirisi yok
CANDAN CENGİZ
Yüksek Lisans
Türkçe
1994
MatbaacılıkMarmara ÜniversitesiVeterinerlik Biyokimyası Ana Bilim Dalı
Y.DOÇ.DR. AŞKIN ÇELİK
- Parallel replacement problem with utilization analysis
Kullanım analizli paralel yenileme problemi
HÜSEYİN MAÇ
Yüksek Lisans
İngilizce
2004
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ.DR. DAVİD PİNHAS
- A Complex reliability model observed periodically in a random environment
Peryodik olarak gözlenen ve rastgele değişen çevre şartlarında çalışan karmaşık bir güvenirlilik modeli
BERNA YENİCE
Yüksek Lisans
İngilizce
1996
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiPROF.DR. SÜLEYMAN ÖZEKİCİ