| Summary: | 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
ho)$-approximation for
all canonical utility functions simultaneously, i.e. without any knowledge
of $U$. The algorithm needs at most $O(log^2
ho)$ 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 $
ho$ is $max left{n, m, R
ight}$.
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
ho)$ approximation for
all canonical utility functions.
|
