Geodesic
Resource allocation in communication networks with large number of users:
Teoriâ veroâtnostej i ee primeneniâ, Tome 66 (2021) no. 1, pp. 129-148

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: network utility maximization, duality, stochastic gradient projection method, large number of users. 
D. B. Rokhlin. Resource allocation in communication networks with large number of users:. Teoriâ veroâtnostej i ee primeneniâ, Tome 66 (2021) no. 1, pp. 129-148. http://geodesic.mathdoc.fr/item/TVP_2021_66_1_a6/
@article{TVP_2021_66_1_a6,
     author = {D. B. Rokhlin},
     title = {Resource allocation in communication networks with large number of users:},
     journal = {Teori\^a vero\^atnostej i ee primeneni\^a},
     pages = {129--148},
     year = {2021},
     volume = {66},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TVP_2021_66_1_a6/}
}
TY  - JOUR
AU  - D. B. Rokhlin
TI  - Resource allocation in communication networks with large number of users:
JO  - Teoriâ veroâtnostej i ee primeneniâ
PY  - 2021
SP  - 129
EP  - 148
VL  - 66
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/TVP_2021_66_1_a6/
LA  - ru
ID  - TVP_2021_66_1_a6
ER  - 
%0 Journal Article
%A D. B. Rokhlin
%T Resource allocation in communication networks with large number of users:
%J Teoriâ veroâtnostej i ee primeneniâ
%D 2021
%P 129-148
%V 66
%N 1
%U http://geodesic.mathdoc.fr/item/TVP_2021_66_1_a6/
%G ru
%F TVP_2021_66_1_a6

[1] A. Beck, Introduction to nonlinear optimization: theory, algorithms, and applications with MATLAB, MOS–SIAM Ser. Optim., 19, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Optimization Society (MOS), Philadelphia, PA, 2014, xii+282 pp. | DOI | MR | Zbl

[2] A. Beck, First-order methods in optimization, MOS–SIAM Ser. Optim., 25, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Optimization Society (MOS), Philadelphia, PA, 2017, xii+475 pp. | DOI | MR | Zbl

[3] A. Beck, A. Nedić, A. Ozdaglar, M. Teboulle, “An $O(1/k)$ gradient method for network resource allocation problems”, IEEE Trans. Control Netw. Syst., 1:1 (2014), 64–73 | DOI | MR | Zbl

[4] D. P. Bertsekas, Nonlinear programming, Athena Sci. Optim. Comput. Ser., 2nd ed., Athena Scientific, Belmont, MA, 1999, xiv+777 pp. | MR | Zbl

[5] D. P. Bertsekas, Convex optimization theory, 2nd ed., Athena Scientific, Nashua, NH, 2009, x+246 pp. | MR | Zbl

[6] Mung Chiang, S. H. Low, A. R. Calderbank, J. C. Doyle, “Layering as optimization decomposition: a mathematical theory of network architectures”, Proc. IEEE, 95:1 (2007), 255–312 | DOI

[7] E. Hazan, “Introduction to online convex optimization”, Foundations and Trends in Optimization, 2:3-4 (2016), 157–325 | DOI

[8] F. P. Kelly, A. K. Maulloo, D. K. H. Tan, “Rate control for communication networks: shadow prices, proportional fairness and stability”, J. Oper. Res. Soc., 49:3 (1998), 237–252 | DOI

[9] S. H. Low, D. E. Lapsley, “Optimization flow control. I. Basic algorithm and convergence”, IEEE/ACM Trans. Netw., 7:6 (1999), 861–874 | DOI

[10] A. Nedić, A. Ozdaglar, “Cooperative distributed multi-agent optimization”, Convex optimization in signal processing and communications, Ch. 10, Cambridge Univ. Press, Cambridge, 2010, 340–386 | MR | Zbl

[11] Yu. E. Nesterov, “{\vrule width0pt height8pt A method of solving a convex programming problem with convergence rate $O\bigl(\frac1{k^2}\bigr)$}”, Soviet Math. Dokl., 27 (1983), 372–376 | MR | Zbl

[12] Yu. Nesterov, V. Shikhman, “Dual subgradient method with averaging for optimal resource allocation”, European J. Oper. Res., 270:3 (2018), 907–916 | DOI | MR | Zbl

[13] S. Shakkottai, R. Srikant, “Network optimization and control”, Foundations and Trends in Networking, 2:3 (2008), 271–379 | DOI

[14] R. Srikant, The mathematics of internet congestion control, Systems Control Found. Appl., Birkhäuser Boston, Inc., Boston, MA, 2004, xii+164 pp. | DOI | MR | Zbl

[15] R. Srikant, Lei Ying, Communication networks. An optimization, control, and stochastic networks perspective, Cambridge Univ. Press, Cambridge, 2014, xii+352 pp. | MR | Zbl

[16] Junshan Zhang, Dong Zheng, Mung Chiang, “The impact of stochastic noisy feedback on distributed network utility maximization”, IEEE Trans. Inform. Theory, 54:2 (2008), 645–665 | DOI | MR | Zbl