Resource allocation in communication networks with large number of users: the stochastic gradient descent method

Abstract

We consider a communication network with fixed number of links, shared by large number of users. The resource allocation is performed on the basis of an aggregate utility maximization in accordance with the popular approach, proposed by Kelly and coauthors (1998). The problem is to construct a pricing mechanism for transmission rates to stimulate an optimal allocation of the available resources. In contrast to the usual approach, the proposed algorithm does not use the information on the aggregate traffic over each link. Its inputs are the total number $N$ of users, the link capacities and optimal myopic reactions of randomly selected users to the current prices. The dynamic pricing scheme is based on the dual projected stochastic gradient descent method. For a special class of utility functions $u_i$ we obtain upper bounds for the amount of constraint violation and the deviation of the objective function from the optimal value. These estimates are uniform in $N$ and are of order $O(T^{-1/4})$ in the number $T$ of reaction measurements. We present some computer experiments for quadratic utility functions $u_i$.

19 pages