Resource Allocation in Communication Networks with Large Number of Users: The Dual Stochastic Gradient Method
Dmitry Borisovich Rokhlin · Theory of Probability and Its Applications · 2021
We consider a communication network with a fixed set of links that are shared by a large number of users. The resource allocation is performed on the basis of the aggregate utility maximization in accordance with the popular approach proposed by F. Kelly and coauthors in 1998. The problem is to construct a pricing mechanism for transmission rates in order 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. This algorithm's 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 stochastic gradient projection method. For a special class of utility functions $u_i$, we obtain upper bounds for the constraint residuals and for the deviation of the objective function from the optimal value. These estimates are uniform in $N$ and of order $O(T^{-1/4})$ in the number $T$ of measured user reactions. We present the results of computer experiments for quadratic functions $u_i$, which are the differences between the linear utilities, which are individual for each user, and the quadratic penalty assigned by the network.