Optimizing resource sharing in node-capacitated overlay networks

Jimmy Leblet (1) , Fabio Pianese (1) , Gwendal Simon (2, 1)

1 INFO - Département informatique
2 REOP - Réseaux d'opérateurs

A frequently occurring problem in the field of distributed systems is to determine an allocation of a generic resource so that the demand of every node in the system is fulfilled. Node-capacitated graphs, i.e. graphs where the weight of a node corresponds to the amount of resources it can give to the system, provide an appealing model that can be readily applied to real-world applications, such as peer-to-peer and grid-based systems. In this paper, we propose a model for this problem and show that it can be reduced to a problem of maximizing a flow in a bipartite network. We then describe a distributed fault-tolerant algorithm which allows each peer to compute the allocation of its resources using only local knowledge. Finally, we show that computing the maximal flow in a bounded-degree graph is NP-complete, which means that optimizing resource sharing in bounded-degree overlays is still an open problem.

Mots clés: Overlay network; Distributed algorithm

Domaines: Interface homme-machine [cs.HC]; Réseaux et télécommunications [cs.NI]

Jimmy Leblet, Fabio Pianese, Gwendal Simon. Optimizing resource sharing in node-capacitated overlay networks. Autonomous and Spontaneous Networks Symposium, Nov 2008, Paris, France. pp.1-17. ⟨hal-02367564⟩