## Kontakt

Schweizerischer Nationalfonds (SNF)

Wildhainweg 3Postfach

CH-3001 Bern

Tel. +41 31 308 22 22

Fax +41 31 301 30 09

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 |

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

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 |

Name | Institut |
---|

Publikation |
---|

Measuring the Mixing Time of a Network |

Scalable Routing for Tag-Based Information-Centric Networking |

Is Information-Centric Multi-Tree Routing Feasible? |

Fully Decentralized Estimation of Some Global Properties of a Network |

Content-Based Publish/Subscribe Networking and Information-Centric Networking |

Gruppe / Person | Land |
---|

Formen 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 |

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; |

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 |

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.

Schweizerischer Nationalfonds (SNF)

Wildhainweg 3Postfach

CH-3001 Bern

Tel. +41 31 308 22 22

Fax +41 31 301 30 09

Gesuche eingeben und verwalten

E-Mail eintragen und Sie erhalten regelmässig den SNF-Newsletter

© SNF 2016