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 caching, internet, removal algorithms, cache replacement. J fl 3m iii S © y g Si“”W
- 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ı: 133
Ö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
- Kaynak kısıtlı proje çizelgeleme probleminde tekrarsız kromozom destekli paralel genetik algoritma uygulaması
A parallel genetic algorithm application with nonrepetitive chromosome improvement for resource constrained project scheduling problem
ŞAFAK EBESEK
- Dinamik web önbellek güncelleme algoritması ve web önbellek sunucuların en uygun şekilde yerleştirilmesi
Dynamic web cache replacement algorithm and optimal placement of web cache server
MOHAMMAD EDRİS RAJABI
Yüksek Lisans
Türkçe
2018
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKaradeniz Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. TUĞRUL ÇAVDAR
- Küresel rekabet ortamında sivil havacılık sektörünün bölgesel bazlı müşteri memnuniyet analizi
Regional based customer satisfaction analysis of the civil aviation sector in global competitive environment
FİLİZ MIZRAK
Doktora
Türkçe
2021
Sivil Havacılıkİstanbul Medipol ÜniversitesiYönetim ve Strateji Bilim Dalı
DOÇ. DR. SERHAT YÜKSEL
- Meslek liseleri için web tabanlı staj yönetim sistemi tasarım ve uygulaması
Web based internship management system design and application for vocational high schools
SULTAN YILDIZ DEMİR
Yüksek Lisans
Türkçe
2015
Eğitim ve ÖğretimDokuz Eylül ÜniversitesiYönetim Bilişim Sistemleri Ana Bilim Dalı
YRD. DOÇ. DR. ÇİĞDEM TARHAN
- Design tools for high carbon conversion, and low tar gasifier system for indigenous biomass, and coal resources
Yerli biyokütle ve kömür kaynakları için yüksek karbon dönüşümü ve düşük katranlı gazlaştırıcı sistemi tasarım araçları
NAMIK ÜNLÜ
Doktora
İngilizce
2022
Makine MühendisliğiMarmara ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
PROF. DR. ZEYNEP SİBEL ÖZDOĞAN