General resource sharing problems in overlay networks

Leblet, Jimmy; Michiardi, Pietro; Simon, Gwendal
Research report RR-08-210

In this paper we propose a theoretical framework to analyze and assess the properties of overlay networks with the goal of studying problems related to rival resource sharing. We study optimality goals for the construction of such overlay networks and focus on fairness issues by de ning perfectly reciprocal overlays, in which every peer receives exactly the same amount of resources it o ers. We focus on answering the following key question : is it possible to determine whether a perfectly reciprocal overlay exists for a given physical network con guration? First, we prove that deciding whether there exists a perfectly reciprocal overlay given a xed underlay can be veri ed in polynomial time. We also propose an algorithm to compute an optimal overlay network, if one exists. Second, we prove that the same decision problem becomes NP-complete if one looks for bounded degree overlays. This last result is of paramount importance because overlay designers frequently constrain peer outdegree. Finally, we present a practical application of our framework: throughout numerical simulations we assess the optimality of overlay networks constructed using distributed algorithms akin to stable matching theory.

Digital Security
Eurecom Ref:
© EURECOM. Personal use of this material is permitted. The definitive version of this paper was published in Research report RR-08-210 and is available at :
See also: