Dynamic algorithms for cooperation in user-provided network services

Abstract

The ever increasing demand for Internet access, and the proliferation of advanced user-owned network equipment have given rise to collaborative schemes, where users satisfy each other's communication needs whenever they have spare network resources. In this paper, we consider such an autonomous model where users have random resource availability and decide independently how to serve each other. For this dynamic setting, we find that a myopic proportional allocation strategy, applied by each node in an asynchronous fashion based only on local information, converges to a stable equilibrium point. Moreover, we show through numerical examples, that the equilibrium exhibits a rich structure and coincides with the lexicographically maximum allocation of the users' resources. Accordingly, we consider a more sophisticated model where each user can pay for the services she receives, with service credits. This enhances the cooperation beyond those users that can directly exchange resources. For this setting, we propose a backpressure-inspired heuristic algorithm for implementing a lightweight, decentralized service exchange scheme, based on the credit backlogs, that balances as much as possible the service allocation across the different users. © 2014 University of Trento.