In the paper we consider the problem of allocation of network resources in telecommunication networks with respect to both utility and reliability goals. We suggest a solution method based on a proximal point method for this problem. We present results of numerical results for the suggested method on test examples.
In [KKL21], we considered a problem of allocation of link resources in telecommunication networks with respect to both utility and reliability goal. However, unlike [KKL20], we do not indicated any pre-de ned non-reliability level. For this problem were suggested a dual decomposition method method.
In this paper, we consider the same problem of allocation of link resources in telecommunication networks as in [KKL21]. Here we describe another solution method. First we suggest to use a proximal point method. Then by using the dual Lagrangian method with respect to the balance constraint, we replace the new formulated problem with an unconstrained optimization problem, where calculation of the cost function value leads to independent solution of single-dimensional problems. We present results of computational experiments which con rm the applicability of the new methods. 2
We rst take the optimal link distribution problem in computer and telecommunication data transmission networks, which was suggested in [KMT98]. This model describes a network that contains a set of transmission links (arcs) L and accomplishes some submitted data transmission requirements from a set of selected pairs of origin-destination vertices I within a xed time period. Denote by xi and i the current and maximal value of data transmission for pair demand i, respectively, and by cl the capacity of link l. Each pair demand is associated with a unique data transmission path of links from the set of Li, hence each link l is associated uniquely with the set Il of pairs of origin-destination vertices, whose transmission paths contain this link. For each pair demand xi we denote by ui(xi) the utility value at this data transmission volume. Then we can write the network utility maximization problem as follows: max !
X xi i2Il 0 xi
X ui(xi) cl; l 2 L; If the functions ui(xi) are concave, this is a convex optimization problem.
Let us now consider the same telecommunication network where the reliability factor should be taken into account. Namely, we associate the reliability to each arc ow and determine l(fl) as the non-reliability of the l-th arc having the ow fl for l 2 L. Then Pl2L l(fl) is the total network non-reliability and we formulate the network manager problem as follows: min ! X l(fl) l2L
X ui(xi) or max ! i2I
X ui(xi) i2I
! X l(fl) ; l2L X xi = fl; l 2 L; i2Il 0 0 fl xi c) and sequence of numbers f"kg
nd (xk+1; f k+1) as min ! ( Each of one-dimensional problem of (10) can be solved easily by explicit formulas.
Function '(y) in (9) is concave, These properties enable us to apply the usual Uzawa gradient method to nd a solution of the dual problem (9): 4
As part of the work, a numerical study of the suggested method was carried out. The method was implemented in C++ with a PC with the following facilities: Intel(R) Core(TM) i7-4500, CPU 1.80 GHz, RAM 6 Gb.
In the experiments, we used quadratic functions of utility of origin-destination pairs linear functions of utility of origin-destination pairs and quadratic functions of non-reliability of arcs ui(xi) = u1;ixi2 + u0;ixi; u1;i < 0; u0;i > 0; i 2 I; ui(xi) = u1;ixi + u0;i; u1;i; u0;i > 0; i 2 I; l(fl) = 1;lfl2 + 0;lfl; 1;l; 0;l > 0; l 2 L:
All the arcs and origin-destination pairs were indexed as l = 0; : : : ; jLj i = 0; : : : ; jIj 1 (jIj is the cardinality I), respectively.
The coe cients 1;l, 0;l, u0;i, and u1;i were formed on the basis of trigonometric functions: 1 (jLj is the cardinality of L) and (5) (6) (i) for the case of quadratic functions ui (ii) for the case of linear functions ui (ii) for the functions l u0;i = 2j sin(2i + 2)j + 2; u1;i = j cos(2i + 1)j
1; u0;i = j sin(2i + 2)j + 1; u1;i = j2 sin(i + 2)j + 1; 0;l = j cos(l + 1)j + 3; 1;l = 2j sin(2l + 2)j + 1: Let us denote the case of linear functions ui as L-case and the case of quadratic functions ui as Q-case.
The maximal arc ow capacity cl was selected in [
i = 7 j sin(i)j + 1: The parameter was xed. We used three xed values: 0.9, 0.5 and 5.0. The stepsize parameter k in the gradient method was also xed and set to 0.6.
The distribution of the available arcs across the origin-destination pairs was carried out either uniformly or according to the normal distribution law. In the gradient method we used two di erent initial points: the vector e of units and vector 100e.
We now introduce additional notations: 1. "k is the accuracy of nding solution of the problem of k-th iteration, 2. T"k;1 and T"k;100 are the time (in seconds) of the method with the starting point e and 100e, respectively, 3. I"k;1 and I"k;100 are the numbers of iterations spent searching for a solution to the problem with the starting point e and 100e, respectively.
The gradient method was stopped if the norm k'0(yk)k appeared less than "k. We used next sequence of "k: "0 = 1, "k = "k 1 0:9, k = 1; 2; : : :.
In Tables 1{4 we give the results of nding a solution of the problem with Q-case combination of functions and in Tables 5{6 - the results of nding a solution of the problem with L-case combination of functions.
In Tables 1 and 5, we give the results for the case where jLj = 310, = 0:9 and for di erent values jIj. In Tables 2{4 and 6, we give the results for the case where jIj = 310, = 0:5 (in Table 3), = 0:9 (in Tables 2 and 6), = 5:0 (in Table 4) and for di erent values jLj.
In Tables 7{8, we give results of Q-case for described method and result for dual method from [KKL21]. For that let us introduce additional notations from [KKL21]: 1. " is the accuracy of nding solution of the problem, 2. T";1 and T";100 are the time (in seconds) of the method with the starting point e and 100e, respectively, 3. I";1 and I";100 are the numbers of iterations spent searching for a solution to the problem with the starting point e and 100e, respectively.
The results of computational experiments con rmed rather stable performance of the method.
From comparing the results in Tables 7{8 we see that in some cases dual method was slightly faster. Here we should note, that in dual method was used static accuracy for nding solution, but in proximal point method we used sequence of accuracies. This sequence can be generated in another way, which perhaps can improve speed of nding solution. We should also note that, unlike [KKL21], proximal point method can nd solution when functions are linear. L j j 620 930 1240
Acknowledgments In this work, the rst author was supported by Russian Foundation for Basic Research, project No. 19-01-00431. The work of the second author was performed within the Russian Government Program of Competitive Growth of Kazan Federal University. The rst and third authors were also supported by grant No. 331833 from Academy of Finland.