Introduction

The current development of information technologies and telecommunications gives rise to new control problems related to efficient transmission of information and allocation of limited network resources. All these problems are determined on distributed systems where the spatial location of elements is taken into account. Due to strong variability and increasing demand of different wireless telecommunication services, fixed allocation rules usually lead to serious congestion effects and inefficient utilization of network resources despite the presence of very powerful processing and transmission devices. This situation forces one to replace the fixed allocation rules with more flexible mechanisms, which are based on proper mathematical models; see e.g. [CW03]- [WNH10]. For example, solution methods for network resource allocation based on optimization formulations of network manager problems and decomposition techniques were presented in [KKL18,KK19]. In these problems, the goal function is the total network profit obtained from the total income of users payments and the implementation costs of the network. Otherwise, the total network users utility can serve as a goal function.

At the same time, wireless networks should be reliable with respect to various attacks. The most commonly seen attack in wireless networks are eavesdropping in which attackers aim at acquiring important/private information of users, jamming and distributed DDoS attacks which attempt to interfere and disrupt network operations by exhausting the resources available to legitimate systems and users. These attacks may lead to degrading the network performance and quality of service (QoS) as well as losing important data, reputations, and revenue; see e.g. [ZJT13, MZA13, ZJT13, LHW17]. Hence, the network resource allocation problem should take into account reliability estimates.

In [KKL20], we considered a problem of telecommunication network link resources allocation among users under reliability control of network connections with the pre-defined non-reliability level. For this problem were suggested a penalty method. This method attained a solution, but its convergence does not allow one to attain high accuracy of solutions.

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-defined 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 confirm the applicability of the new methods.

Problem Description

We first 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 fixed time period. Denote by x i and α i the current and maximal value of data transmission for pair demand i, respectively, and by c l the capacity of link l. Each pair demand is associated with a unique data transmission path of links from the set of L i , hence each link l is associated uniquely with the set I l of pairs of origin-destination vertices, whose transmission paths contain this link. For each pair demand x i we denote by u i (x i ) the utility value at this data transmission volume. Then we can write the network utility maximization problem as follows:

max

→ i∈I u i (x i ) subject to i∈I l x i ≤ c l , l ∈ L; 0 ≤ x i ≤ α i , i ∈ I.

If the functions u i (x i ) 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 flow and determine µ l (f l ) as the non-reliability of the l-th arc having the flow f l for l ∈ L. Then l∈L µ l (f l ) is the total network non-reliability and we formulate the network manager problem as follows:

min → l∈L µ l (f l ) − i∈I u i (x i ) or max → i∈I u i (x i ) − l∈L µ l (f l ) ,(1)

subject to

i∈I l x i = f l , l ∈ L; (2) 0 ≤ f l ≤ c l , l ∈ L; (3) 0 ≤ x i ≤ α i , i ∈ I.(4)

If the functions u i (x i ) and −µ l (f l ) are concave, this is a convex optimization problem with the polyhedral feasible set. However, solution of problem (1)-( 4) is not so easy due to large dimensionality and inexact data. In this paper we consider the case where the functions u i (x i ) and −µ l (f l ) are concave.

Solution Method

Take number θ > 0, points x 0 (0

≤ x 0 ≤ α), f 0 (0 ≤ f 0 ≤ c) and sequence of numbers {ε k } ({ε k } ↓ 0, ∞ k=0 ε k < ∞).

At the k-th iteration, k = 0, 1, ..., we have a pair (x k , f k ). We find (x k+1 , f k+1 ) as a solution of the problem min

→ l∈L µ l (f l ) + θ 2 (f l − f k l ) 2 + i∈I θ 2 (x i − x k i ) 2 − u i (x i ) (5) subject to i∈I l x i = f l , l ∈ L; (6) 0 ≤ f l ≤ c l , l ∈ L; (7) 0 ≤ x i ≤ α i , i ∈ I. (8)

with the accuracy ε k .

Let us define the Lagrange function of problem ( 5)-(8) as follows:

L k (x, f, y) = l∈L µ l (f l ) + θ 2 (f l − f k l ) 2 + i∈I θ 2 (x i − x k i ) 2 − u i (x i ) + l∈L y l f l − i∈I l x i .

By duality, we can replace problem (5)-( 8) with the dual unconstrained optimization problem:

max y → ϕ(y),(9)

where

ϕ(y) = min 0≤x≤α,0≤f ≤c L k (x, f, y) = l∈L min 0≤f l ≤c l µ l (f l ) + θ 2 (f l − f k l ) 2 + y l f l + i∈I min 0≤xi≤αi θ 2 (x i − x k i ) 2 − u i (x i ) − x i l∈Li y l .(10)

Each of one-dimensional problem of (10) can be solved easily by explicit formulas. Function ϕ(y) in ( 9) is concave,

∂ϕ(y) ∂y l = i∈I l x i (y) − f l (y l ), l ∈ L.

These properties enable us to apply the usual Uzawa gradient method to find a solution of the dual problem (9):

y k+1 = y k + λ k ϕ (y k ), λ k > 0.

Numerical Experiments

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

u i (x i ) = u 1,i x 2 i + u 0,i x i , u 1,i < 0, u 0,i > 0, i ∈ I,

linear functions of utility of origin-destination pairs

u i (x i ) = u 1,i x i + u 0,i , u 1,i , u 0,i > 0, i ∈ I,

and quadratic functions of non-reliability of arcs

µ l (f l ) = µ 1,l f 2 l + µ 0,l f l , µ 1,l , µ 0,l > 0, l ∈ L.

All the arcs and origin-destination pairs were indexed as l = 0, . . . , |L| − 1 (|L| is the cardinality of L) and i = 0, . . . , |I| − 1 (|I| is the cardinality I), respectively.

The coefficients µ 1,l , µ 0,l , u 0,i , and u 1,i were formed on the basis of trigonometric functions:

(i) for the case of quadratic functions

u i u 0,i = 2| sin(2i + 2)| + 2, u 1,i = −| cos(2i + 1)| − 1, (ii) for the case of linear functions u i u 0,i = | sin(2i + 2)| + 1, u 1,i = |2 sin(i + 2)| + 1, (ii) for the functions µ l µ 0,l = | cos(l + 1)| + 3, µ 1,l = 2| sin(2l + 2)| + 1.

Let us denote the case of linear functions u i as L-case and the case of quadratic functions u i as Q-case.

The maximal arc flow capacity c l was selected in [1, 10] as follows:

c l = 10 * | cos(l + 3)| + 1.

The maximal path flow capacity α i associated with a origin-destination pair was selected in [1, 7] as follows:

α i = 7 * | sin(i)| + 1.

The parameter θ was fixed. We used three fixed values: 0.9, 0.5 and 5.0. The stepsize parameter λ k in the gradient method was also fixed 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 different initial points: the vector e of units and vector 100e.

We now introduce additional notations:

1. ε k is the accuracy of finding 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 ϕ (y 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 finding a solution of the problem with Q-case combination of functions and in Tables 5-6 -the results of finding a solution of the problem with L-case combination of functions.

In Tables 1 and 5, we give the results for the case where |L| = 310, θ = 0.9 and for different values |I|. In Tables 2-4 and 6, we give the results for the case where |I| = 310, θ = 0.5 (in Table 3), θ = 0.9 (in Tables 2 and 6), θ = 5.0 (in Table 4) and for different values |L|.

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 finding 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 confirmed 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 finding 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 finding solution. We should also note that, unlike [KKL21], proximal point method can find solution when functions are linear.