Geri Dön

Replacement problem in web caching

Web gaçişi belleklerinde yerleştirme problemi

  1. Tez No: 129218
  2. Yazar: SEDA ÇAKIROĞLU
  3. Danışmanlar: PROF. DR. ERDAL ARIKAN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. 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
  7. Yıl: 2002
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Elektrik-Elektronik Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. 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

    Doktora

    Türkçe

    Türkçe

    2019

    Mimarlıkİstanbul Teknik Üniversitesi

    Mimarlık Ana Bilim Dalı

    PROF. DR. HAKAN YAMAN

  2. 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

    Türkçe

    2018

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKaradeniz Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. TUĞRUL ÇAVDAR

  3. 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

    Türkçe

    2021

    Sivil Havacılıkİstanbul Medipol Üniversitesi

    Yönetim ve Strateji Bilim Dalı

    DOÇ. DR. SERHAT YÜKSEL

  4. 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

    Türkçe

    2015

    Eğitim ve ÖğretimDokuz Eylül Üniversitesi

    Yönetim Bilişim Sistemleri Ana Bilim Dalı

    YRD. DOÇ. DR. ÇİĞDEM TARHAN

  5. 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

    İngilizce

    2022

    Makine MühendisliğiMarmara Üniversitesi

    Makine Mühendisliği Ana Bilim Dalı

    PROF. DR. ZEYNEP SİBEL ÖZDOĞAN