CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

A least resistance path to the analysis of unstructured overlay networks

Marina Papatriantafilou (Institutionen för data- och informationsteknik, Datavetenskap, Datakommunikation och distribuerade system (Chalmers)) ; Giorgos Georgiadis (Institutionen för data- och informationsteknik, Datavetenskap, Datakommunikation och distribuerade system (Chalmers))
Göteborg : Chalmers University of Technology, 2008. - 16 s.
[Rapport]

Unstructured overlay networks for peer-to-peer applications combined with stochastic algorithms for interest-based clustering and resource location are attractive due to low-maintenance costs and inherent fault-tolerance properties. Moreover, there is a relatively large volume of experimental evidence that these methods are efficiency-wise a good alternative to structured methods, which require more sophisticated algorithms for maintenance and fault-tolerance. Specifically in the case of interest-based clustering, it has been recently suggested that a resource location strategy based on non-trivial randomwalks can be used to construct an overlay network with scale-free and clustering properties, which can be navigated efficiently. However, currently there is a very limited selection of appropriate tools to use in evaluating performance and other properties of such non-trivial methods. We present a framework for analyzing unstructured overlays and stochastic algorithms on them, connecting the corresponding graphs, random walks and resistor networks by using elementary linear algebra calculations. We express the framework in a way that can be used in various contexts regarding the overlay network and statistical methods. Furthermore, we demonstrate its usage by studying non-trivial random walks in overlays with power-law node degree distribution; in particular we address a broad set of topics of interest for peer-to-peer overlays, including content-replication efficiency, fault-tolerance, query-replication efficiency and resource constraint handling.

Nyckelord: random walks, peer-to-peer networks



Denna post skapades 2008-02-27.
CPL Pubid: 68712

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)


Institutioner (Chalmers)

Institutionen för data- och informationsteknik, Datavetenskap, Datakommunikation och distribuerade system (Chalmers) (2005-2007)

Ämnesområden

Datavetenskap (datalogi)

Chalmers infrastruktur