A cost-based analysis of overlay routing geometries

In this paper, we propose a cost-based model to evaluate the resources that each node has to contribute for participating in an overlay network. Such a cost model allows to gauge potential disincentives for nodes to collaborate, and provides a measure of the "total cost" of a network, which is a possible benchmark to distinguish between different network architectures. We characterize the cost imposed on a node as a parameterized function of the experienced load and of the node connectivity, and express benefits in terms of cost reductions. We discuss the notions of social optimum and Nash equilibrium with respect to the proposed cost model. We show that the social optimum may significantly deviate from a Nash equilibrium when nodes value the resources they use to forward traffic on behalf of other nodes. Through analytical and numerical results, we then use the proposed cost model to evaluate some of the topologies recently proposed for overlay networks, and to exhibit some of the challenges systems designers may face. We conclude by outlining some of the open questions this research has raised.