Projekt

Zurück zur Übersicht

P2PImpulse: Fully Decentralized Estimation of Global Properties of Peer-to-Peer Networks

Titel Englisch P2PImpulse: Fully Decentralized Estimation of Global Properties of Peer-to-Peer Networks
Gesuchsteller/in Carzaniga Antonio
Nummer 132565
Förderungsinstrument Projektförderung (Abt. I-III)
Forschungseinrichtung Facoltà di scienze informatiche Università della Svizzera italiana
Hochschule Università della Svizzera italiana - USI
Hauptdisziplin Informatik
Beginn/Ende 01.10.2010 - 28.02.2014
Bewilligter Betrag 153'744.00
Alle Daten anzeigen

Keywords (6)

peer-to-peer systems, distributed estimation, spectral network properties, network property estimation, mixing time, spectral gap

Lay Summary (Englisch)

Lead
Lay summary
A peer-to-peer system is essentially a network of applications used to communicate and share resources. The nodes in this network, generally called "peers," are typically interconnected through point-to-point overlay links. A fundamental feature of peer-to-peer networks is that each peer maintains only a local view of the network. Although this absence of a centralized point of control is very advantageous, sometimes it is still necessary or desirable that peers be able to measure some global properties of the network. The general goal of this project is to study ways to measure some global properties of a peer-to-peer network in a completely decentralized and efficient manner. Specifically, we propose to study properties of peer-to-peer networks that can be derived from the spectrum of the network. By spectrum of the network we mean the eigenvalues of a chosen descriptive matrix closely related to the adjacency matrix of the network graph. For example, the mixing time of a network -- the minimal length of a random walk necessary to obtain a desired approximation of the asymptotic visitation probabilities -- can be derived from the second eigenvalue of the transition-probability matrix. The starting point of this research is the intuition that each peer in a network can, with a simple efficient and fully decentralized algorithm, compute the impulse response of a particular linear dynamic system whose state-transformation matrix corresponds to the chosen descriptive matrix derived from the network graph. In other words, a peer can not see or use the whole network graph (efficiently) but can compute the impulse response of a dynamic system whose behavior is defined by the structure of that graph. The impulse response can then be used to compute the desired salient spectral properties of the network graph by applying well-established identification and realization techniques developed within the theory of dynamic systems. In general, a complete and exact identification would require a very large number of steps of the impulse response (at least n for a network of n peers). However, a much shorter, truncated impulse response might still reveal useful information, as it could effectively distill the dominant properties of the network. In synthesis, we view a peer-to-peer network as a large linear dynamic system whose impulse response can be computed efficiently, and we propose to research the applicability of system-identification theory to estimate some global properties of the network.
Direktlink auf Lay Summary Letzte Aktualisierung: 21.02.2013

Verantw. Gesuchsteller/in und weitere Gesuchstellende

Mitarbeitende

Name Institut

Publikationen

Publikation
Fully Decentralized Estimation of Some Global Properties of a Network
Carzaniga Antonio, Hall Cyrus, Papalini Michele (2012), Fully Decentralized Estimation of Some Global Properties of a Network, in Proceedings of IEEE INFOCOM 2012, Orlando, Florida, USAIEEE, Piscataway, New Jersey, USA.
Content-Based Publish/Subscribe Networking and Information-Centric Networking
Antonio Carzaniga, Mchele Papalini, Alexander L. Wolf (2011), Content-Based Publish/Subscribe Networking and Information-Centric Networking, in Proceedings of the ACM SIGCOMM Workshop on Information-Centric Networking, Toronto, CanadaACM, New York, NY, USA.
Is Information-Centric Multi-Tree Routing Feasible?
Carzaniga Antonio, Khazaei Koorosh, Papalini Michele, Wolf Alexander (2013), Is Information-Centric Multi-Tree Routing Feasible?, in ACM SIGCOMM Workshop on Information-Centric Networking (ICN'13), Hong Kong, ChinaACM, New York, NY, USA.
Measuring the Mixing Time of a Network
Foukas Xenofon, Carzaniga Antonio, Wolf Alexander L. (2015), Measuring the Mixing Time of a Network, in Proceedings of IEEE INFOCOM 2015, Hobg Kong, ChinaIEEE, Piscataway, New Jersey, USA.
Scalable Routing for Tag-Based Information-Centric Networking
Papalini Michele, Carzaniga Antonio, Khazaei Koorosh, Wolf Alexander L. (2014), Scalable Routing for Tag-Based Information-Centric Networking, in Proceedings of the 1st international conference on Information-centric networking (ICN'14), Paris, FranceACM, New York, NY, USA.

Zusammenarbeit

Gruppe / Person Land
Felder der Zusammenarbeit
Imperial College London Grossbritannien und Nordirland (Europa)
- vertiefter/weiterführender Austausch von Ansätzen, Methoden oder Resultaten
- Publikation
- Forschungsinfrastrukturen
Alcatel Lucent Frankreich (Europa)
- vertiefter/weiterführender Austausch von Ansätzen, Methoden oder Resultaten
- Publikation
- Austausch von Mitarbeitern

Wissenschaftliche Veranstaltungen

Aktiver Beitrag

Titel Art des Beitrags Titel des Artikels oder Beitrages Datum Ort Beteiligte Personen
ACM SIGCOMM Workshop on Information-Centric Networking (ICN'13) Vortrag im Rahmen einer Tagung Is Information-Centric Multi-Tree Routing Feasible? 12.08.2013 Hong Kong, China Carzaniga Antonio; Papalini Michele
Second CCNx Community Meeting 2012 Poster A Backward-Compatible CCNx Extension for Improved Support for Notifications and Content-Based Addresses 12.09.2012 Sophia Antipolis, France, Frankreich Papalini Michele
INFOCOM 2012 Vortrag im Rahmen einer Tagung Fully Decentralized Estimation of Some Global Properties of a Network 27.03.2012 Orlando, Florida, Vereinigte Staaten von Amerika Carzaniga Antonio; Papalini Michele
ACM SIGCOMM Workshop on Information-Centric Networking (ICN-2011) Vortrag im Rahmen einer Tagung Content-Based Publish/Subscribe Networking and Information-Centric Networking 19.08.2011 Toronto, Kanada Papalini Michele; Carzaniga Antonio


Auszeichnungen

Titel Jahr
Best Paper Award for the paper "Is Information-Centric Multi-Tree Routing Feasible?" by A. Carzaniga, K. Khazaei, M. Papalini, and A.L. Wolf. 2013

Abstract

A peer-to-peer system is essentially a network of applications used to communicate and share resources. The nodes in this network, generally called ``peers,'' are typically interconnected through point-to-point overlay links. A fundamental feature of peer-to-peer networks is that each peer maintains only a local view of the network, typically consisting of a little more than a list of adjacent peers. So, the network as a whole is not maintained by, nor directly visible from, any single peer. Although this absence of a centralized point of control is very advantageous, sometimes it is still necessary or desirable that peers be able to measure some global properties of the network. The general goal of this project is to study ways to measure some global properties of a peer-to-peer network in a completely decentralized and efficient manner, where decentralized and efficient in essence means that the memory required at each peer, and the traffic on each link, are asymptotically sublinear in, and practically much lower than, the size of the network. Specifically, we propose to study properties of peer-to-peer networks that can be derived from the spectrum of the network. By spectrum of the network we mean the eigenvalues of a chosen descriptive matrix closely related to the adjacency matrix of the network graph. For example, the mixing time of a network, which indicates the minimal length of a random walk necessary to obtain a desired approximation of the asymptotic visitation probabilities, can be derived from the second-largest eigenvalue modulus of the transition probability matrix, which is simply a weighted adjacency matrix of the network graph. Similarly, other useful properties of the network can be derived from the spectrum of the same or other related matrices. The starting point of this research is the intuition that each peer in a peer-to-peer network can, with a simple efficient and fully decentralized algorithm, compute the impulse response of a particular linear dynamic system whose state-transformation matrix corresponds to the chosen descriptive matrix derived from the network graph. In other words, a peer can not see or use the whole network graph (efficiently) but can compute the impulse response of a dynamic system whose behavior is defined by the structure of that graph. The impulse response can then be used to compute the desired salient spectral properties of the network graph by applying well-established identification and realization techniques developed within the theory of dynamic systems. In general, a complete and exact identification would require a very large number of steps of the impulse response (at least n for a network of n peers). However, a much shorter, truncated impulse response might still reveal useful information, as it could effectively distill the dominant properties of the network. In synthesis, we view a peer-to-peer network as a large linear dynamic system whose ``impulse response'' can be computed efficiently, and we propose to research the applicability of system-identification theory to estimate some global properties of the network. We have initial experimental evidence (through simulation) that the notion of the impulse response of a peer-to-peer network outlined here can be the basis for the effective estimation of a global network property such as the mixing time. With this project we want to fully develop this notion, solidifying its foundations and widening its scope. This development raises a number of research questions that define the high-level research plan of this proposal. First, we plan to research the theoretical limits of the estimation method based on the impulse response. Intuitively, since peer-to-peer graphs are often strongly connected and of low-diameter, the response computed at one peer is affected by every other peer within a few steps, and should therefore contain enough information to approximate the system-theoretic observable properties of the network. We propose to formalize and validate this and other relevant intuitions. Second, we plan to study the practical effectiveness of this estimation method. This amounts to characterizing the trade-offs between accuracy and cost of the estimation. We already know that, in general, longer impulse-response sequences lead to better estimates. However, we do not yet know how fundamental properties of peer-to-peer systems, such as the type of topology and, crucially, its evolution over time (or "churn"), affect the estimation. We propose to study these trade-offs with an extensive simulation analysis. Third, we propose to develop a prototype of a generic estimator for peer-to-peer systems. Such a system should provide, in a modular way, various types of spectral measurements, which would be integrated and used, with minimal effort, within existing peer-to-peer networks.