Design and analysis of a novel buffer management model for reliable content dissemination

Abstract

Dağıtık içerik dağıtım servislerinde güvenilirliğin sağlanması için, etkin bir ara bellek yönetimi yoluyla başarılmış bir kayıp mesaj kurtarım mekanizması vazgeçilmez bir bileşendir. Ara bellek yönetimi konusundaki mevcut yaklaşımlar, akış kontrolü, bellek kullanımının azaltılması, mesaj dengesinin sağlanması ve bellek parçalarının yer değiştirmesi gibi çok sayıda problem bileşeni üzerinde yoğunlaşmaktadır.Bu tez çalışmasında, geniş ölçekli biyolojiden esinlenen eşler arası veri dağıtım servislerine yönelik ara bellek yönetimi problemi ele alınmıştır. Biyolojiden esinlenen epidemik protokoller; ağ hatalarına karşı dayanıklı ve ölçeklenir olmaları ve olasılıksal güvenilirlik garantisi sağlamaları açısından kayda değer avantajlara sahiptir. Bu tip protokollerde güvenilirlik ve ölçeklenirlik sağlamasının yanı sıra, etkin bir ara bellek mekanizması ile birleştirildiğinde, sistem genelindeki bellek kullanımı da iyileştirilebilir. Önceki yaklaşımlarla karşılaştırıldığında tekdüze bir yük dağılımı sağladığı kanıtlanan ve eşlerin her birinin sistemin kısmi bir görünümüne sahip olduğu bir koşulda genel ara bellek kullanımını azaltan ve Adımsal Eşit Dağılımlı Ara Bellek olarak adlandırılan yeni bir algoritma önermekteyiz. Bu yaklaşımın başlıca hedeflerinden biri; sistem içerisindeki ara bellek tutucularının ara bellek yükü mevcut eşler arasında dengelenecek şekilde seçilmesi ve bunun sonucunda içerik dağıtımının etkinliğinin arttırılmasıdır. Bu yaklaşım; her bir mesajın ara bellek tutucusu olarak yalnızca eşlerin küçük bir alt kümesi seçildiğinden, bellek kullanımını da azaltmaktadır. Aynı zamanda, geniş ölçekli senaryolara uygulanabilir, güvenilir bir dağıtım sağlar ve dinamik sistem giriş ve çıkışlarına adapte olabilir. Ara bellek boyutunu ayarlayarak, yüksek olasılıkla mesaj dengesini sağlar.Ara bellek modelinin başarım değerlendirmesi ve önceki yaklaşımlarla kapsamlı bir karşılaştırması gerçekleştirilmiştir. Değerlendirmeler; ölçeklenirlik, güvenilirlik, hatalara uyumluluk ve tekdüzelik analizlerini içermektedir. Ara bellek düzeylerinin bir fonksiyonu olarak dağıtım güvenilirliğine ilişkin analitik sonuçlar da türetilmiştir. İlgili sonuçlarda Markov zincir analizi temel alınmıştır ve bu sonuçlar sayısal olarak değerlendirilmiştir. Benzetimlerle gerçekleştirilen karşılaştırmalar, sonuçların güvenilirlik açısından iyi bir alt sınır oluşturduğunu göstermektedir. Yüksek düzeyli güvenilirlik değerleri için, elde edilen analitik sınırların benzetim sonuçları ile tutarlılığı gösterilmiştir.

For supporting reliability in distributed content dissemination services, message loss recovery mechanism achieved via efficient buffer management is an indispensable component. The available approaches for buffer management concentrate on several aspects of the problem such as flow control, reducing the memory usage, providing message stability and the replacement of buffer items.In this thesis study, we consider buffer management problem in support of large-scale bio-inspired peer-to-peer data dissemination services. Bio-inspired epidemic protocols have considerable benefits as they are robust against network failures, scalable and provide probabilistic reliability guarantees. Coupled with an efficient buffering mechanism, system wide buffer usage can be optimized while providing reliability and scalability in such protocols. We propose a novel algorithm, Stepwise Fair-share Buffering, that is shown to provide uniform load distribution in comparison to earlier approaches and reduces the overall buffer usage where every peer has the partial view of the system. A major aim of our approach is to be able to choose bufferers uniformly throughout the system so that the load of buffering will be well balanced among participating peers and the efficiency of content dissemination will be improved as a result. This also reduces the memory usage since only a small subset of the peers is chosen as bufferers for each message. Furthermore, it is applicable to large-scale scenarios, provides reliable delivery and is adaptable to dynamic join and leaves to the system. It adjusts the buffer size to achieve message stability with a high probability.Performance evaluation of the buffering model and extensive comparisons with earlier approaches are performed. The evaluations include scalability, reliability, adaptivity to failures and uniformity analysis. We also derive analytical results for reliability of dissemination as a function of buffer levels. These results are based on a Markov chain analysis and are evaluated numerically. Comparison with simulations shows that they provide a good lower bound for reliability. For high level of reliability values, the bounds are very close to the simulation results.