Effect of overlay topology on peer-to-peer data dissemination and buffer management

Abstract

Enerjik ve hızlı değişen ağ ortamlarında, yeni gelen her bir bilgi hakkında, ağdaki kullanıcıları bilgilendirme işlemi, çeşitli bilgi yayılımı algoritmalarıyla sağlanır. Güvenilirliği ve sağlamlığı ile, dedikodu yayılımı algoritmaları, bu algoritmalar arasında en yaygın olanlardan biridir. İçerik dağıtımı sırasındaki güvenilirliğin sağlanması için, herhangi bir mesaj kaybı durumunda, kaybolan mesajların yeniden temini, çesitli ara bellek yönetimi yöntemleri ile sağlanır. Sınırlı bellek kaynaklarının etkili bir şekilde kullanımı, ara bellek yönetiminin en temel amaçlarından biridir.Bu tez çalışmasında, bilgi yayılımı ve ara bellek yönetimi olmak üzere, görevdeş ağlardaki iki temel fenomen, topolojik yönlerden analiz edilmektedir. Bilgi yayılımı için, görevdeş ağlarda, verilen herhangi bir topoloji ile, komşuluk bilgisine bağlı, entropi-önler algoritmalarıyla yayılım incelenmektedir. Ağdaki bütün düğümlerin, her bir salgın döngüsü esnasındaki enfekte olma olasılıkları bulunmaktadır. Ara bellek yönetimi için, sistemdeki bellek kaynaklarını etkin bir biçimde kullanan ve bellek yükünü sistem üzerindeki kullanıcılar üzerine dengeli bir biçimde dağıtan bir algoritma olan, Adımsal Eşit Dağılımlı Ara Bellek algoritması ile bellek dağıtımı incelenmektedir. İnterneti örnekleyen sıra-düzensel ve üs kanunu temel topolojilerinin, ara bellek yönetimine olan farklı etkileri incelenmektedir.Topolojik özelliklerin bilgi yayılımına olan etkileri, sayısal hesaplamalarla incelenmiştir. Yayılım hızının, komşuluk matrisine, doğrusal olmayan bir yolla bağlı olduğu bulunmuştur. Ara bellek modelinin, sıra-düzensel ve üs kanunu topolojilerdeki başarım hesaplamaları benzetim sonuçlarıyla bulunmuştur. Temel başarım parametreleri olarak, ölçeklenebilirlik, güvenilirlik, yayılım gecikme zamanları ve dengeli dağılım dikkate alınmıştır. Adımsal Eşit Dağılımlı Ara Bellek algoritmasının, bellek yükünü sistem üzerindeki kullanıcılara dengeli bir biçimde dağıttığı benzetim sonuçlarıyla gösterilmiştir. Ara bellek seçimindeki karar verme sürecinin gecikmeye sebep olmasınıbeklediğimiz halde, üs kanunu topolojileri ele alındığında, bu gecikmenin büyük ölçüde giderildiği görülmüştür.

Keeping every node updated about the newly generated data in the dynamic and rapidly changing environment of a network is achieved via different data dissemination algorithms. Epidemics is one of the widely accepted algorithms because of its reliability and robustness. Message loss recovery for maintaining the reliability of the content delivery in case of message losses is achieved via several buffer management techniques. Efficient usage of limited memory resources is the basic deal for buffer management.In this thesis, we present our analysis of peer-to-peer (P2P) networking phenomena, namely data dissemination and buffer management, focusing on topological perspectives. For data dissemination, we examine spreading of epidemics for anti-entropy algorithms on several overlay network topologies, considering peer proximity. We derive nodes' exact probability distributions of being infected in each epidemic cycle of data dissemination. For buffer management, we examine buffering with an efficient algorithm, Stepwise Fair-share Buffering, that uses memory resources effectively and distributes the buffering load uniformly throughout the system. We analyze the effect of different topologies on buffer management, using hierarchical and power-law topologies, two basic types of topology modeling the Internet.For data dissemination, the effect of topological properties is studied using numerical evaluations. The rate of dissemination is found to be related to the adjacency matrix in a nonlinear way. For buffering, performance evaluations of various models with hierarchical and power-law topologies are conducted. Scalability, reliability, dissemination delays and uniformity are considered as basic performance parameters. We have shown that Stepwise Fair-share Buffering method facilitate better uniformity in distribution of buffering load, in view of our simulations. We expect to have higher delays due to decision process performed for bufferer selection; however, it is also shown that dissemination delay performance drawback is eliminated when power-law topologies are considered.