Abstract

In this paper, we present a simple distributed algorithm for resource allocation which simultaneously approximates the optimum value for a large class of objective functions. In particular, we consider the class of canonical utility functions U that are symmetric, non-decreasing, concave, and satisfy U(0) = 0. Our distributed algorithm is based on primal-dual updates. We prove that this algorithm is an O(log ρ)approximation for all canonical utility functions simultaneously, i.e. without any knowledge of U. The algorithm needs at most O(log 2 ρ) iterations. Here n is the number of flows, m is the number of edges, R is the ratio between the maximum capacity and the minimum capacity of the edges in the network, and ρ is max {n, m, R}. We extend this result to multi-path routing, and also to a natural pricing mechanism that results in a simple and practical protocol for bandwidth allocation in a network. When the protocol reaches equilibrium, the allocated bandwidths are the same as when the distributed algorithm converges; hence the protocol is also an O(log ρ) approximation for all canonical utility functions