A framework for distributed bandwidth allocation in peer-to-peer networks

Abstract

In peer-to-peer networks, each peer plays the role of client and server. As a server, it receives content requests of others and decides to what extent it will satisfy them by allocating upload bandwidth. As a client, it sends its own requests to others to download content. We consider a star topology network with the capacity bottleneck being the peer access link to the backbone. Peers are assumed to be cooperative but with different resource needs and valuations, captured by their utility function, as well as with different service capabilities. We consider the problem of maximizing total network utility (social welfare) through controlling the bandwidth portion allocated to downloaders and uploaders of each peer. For autonomous unsupervised network operation, the fundamental challenge is to achieve the goal above in a distributed fashion. However, the global bandwidth sharing problem is difficult to solve in a decentralized fashion because of coupled utility functions and constraints, since the utility of a peer depends on allocation decisions of others. By defining new auxiliary variables and constraints, we transform the problem into one that is amenable to distributed solution by dual decomposition methods. The iterative algorithm involves solving separate optimization problems by each peer and updating Lagrange multipliers. Interestingly, the Lagrangian multipliers corresponding to new constraints can be interpreted as metrics for the level of pairwise resource contribution. The solution of the social welfare problem consists of the optimal pairwise amounts of allocated bandwidth and the optimal dual variables that induce these allocations. This leads to a meaningful lightweight algorithm which converges to the globally optimum bandwidth allocation. (C) 2009 Elsevier B.V. All rights reserved.