Global Optimisation Problems in P2P Networks

This page aims to collect different global optimisation problems arising in peer-to-peer networks.

Global optimisation is, generally speaking, the task of finding the absolutely best value of a (usually) nonlinear function under given constraints.

Neighbor-selection strategy

The paper

S.G.M.Koo, K.Kannan and C.S.G.Lee: On neighbor-selection strategy in hybrid peer-to-peer networks. Future Generation Computer Systems 22 (2006) 732-741

discusses the problem of neighbor-selection (NS) which is the process where one or more entities in the P2P network police the system and determines the "neighbors", the other peers that they will connect to for obtaining and/or distributing the content, for each peer. The NS process has great influence on the network efficiency. The related problem, which appers in the paper cited above, is to maximise the disjointness of content from peer i to peer j (which means the collection of content pieces that peer i has but peer j does not, or in another interpretation, means the pieces that peer i can upload to peer j). The proposed solution is to maximise the number of content pieces each peer can contribute to its neighbors by determining the connections between the peers. Using mathematical formalism this leads to a constrained integer programming formalism. The paper applies genetic algorithm to solve the problem.

Two quesions:

  • (Not so important:) Can we use better algorithms to solve the problem?
  • (More important:) The problem statement above is in networks with tracker server. Can we formulate the similar problem in a server-free network?

Other paper on this topic is

S.Sun, A.Abraham, G.Zhang, H.Liu: A Particle Swarm Optimization Algorithm for Neighbor Selection in Peer-to-Peer Networks

which, as the title says, aims to solve the same problem using a different algorith. Of course, the authors conclude their paper as PSO is better that GA based on 3(!) test examples and using a kind-of-standard set up of the two different algorithms.

Yet another paper

A.Abraham, B.Yue, C.Xian: Multi-objective Peer-to-Peer Neighbor-Selection Strategy Using Genetic Algorithm

formulates the problem as before, but with an additional objective function, the downloading cost to improve the overall throughput of the system, which is to be minimized.

Efficient Content Replication

The paper

C.Cervellera, L.Caviglione: Optimization of a peer-to-peer system for efficient content replication, EJOR (2008) in press

discusses a formal framework for the optimization of the overall performance of the p2p content replication. It takes advantage of the presence of the tracker and proposes an optimisation procedure from the point of view of this centralized component. The evolution of a swarm is characterized with a discrete-time system, where decisions are taken by the tracker at the beginning of each temporal stage. The paper proposes a myopic optimisation approach (i.e. given any partial solution, assign another value that improves the objective the most (algorithms that produce solutions based on myopic optimization are called greedy algorithms).).