Peer-to-peer (P2P) computing already accounts for a large part of the traffic on the Internet, and it is likely to become as ubiquitous as current client/server architectures in next generation information systems. This paper addresses a central problem of P2P systems: the design of an optimal overlay communication network for a set of processes on the Internet. Such a network defines membership to the P2P group and allows for members to disseminate information within the group. The problem, named the membership overlay problem (MOP), can be formulated as a dynamic optimization problem where classical combinatorial optimization techniques must face the further challenge of time-varying input data. This paper proposes an innovative, fully distributed, and asynchronous subgradient optimization algorithm for the Lagrangean relaxation of the MOP, which can run online in fully decentralized P2P systems, and integrates it with a distributed heuristic that can achieve sound hot-start states for fast response to varying network structures.

A Fully Distributed Lagrangean Solution for a Peer-to-Peer Overlay Network Design Problem

BOSCHETTI, MARCO ANTONIO;MANIEZZO, VITTORIO;
2011

Abstract

Peer-to-peer (P2P) computing already accounts for a large part of the traffic on the Internet, and it is likely to become as ubiquitous as current client/server architectures in next generation information systems. This paper addresses a central problem of P2P systems: the design of an optimal overlay communication network for a set of processes on the Internet. Such a network defines membership to the P2P group and allows for members to disseminate information within the group. The problem, named the membership overlay problem (MOP), can be formulated as a dynamic optimization problem where classical combinatorial optimization techniques must face the further challenge of time-varying input data. This paper proposes an innovative, fully distributed, and asynchronous subgradient optimization algorithm for the Lagrangean relaxation of the MOP, which can run online in fully decentralized P2P systems, and integrates it with a distributed heuristic that can achieve sound hot-start states for fast response to varying network structures.
M.A. Boschetti; V. Maniezzo; M. Roffilli
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11585/87228
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 3
social impact