=Paper=
{{Paper
|id=Vol-2928/paper4
|storemode=property
|title=Application of Proximal Point Method to the Problem of Allocation of Arcs in Telecommunication Networks
|pdfUrl=https://ceur-ws.org/Vol-2928/paper4.pdf
|volume=Vol-2928
|authors=Igor V. Konnov,,Alexey Yu. Kashuba,,Erkki Laitinen
}}
==Application of Proximal Point Method to the Problem of Allocation of Arcs in Telecommunication Networks==
https://ceur-ws.org/Vol-2928/paper4.pdf
Application Of Proximal Point Method To The Problem
Of Allocation Of Arcs In Telecommunication Networks
Igor V. Konnov Alexey Yu. Kashuba Erkki Laitinen
Kazan Federal University Kazan Federal University University of Oulu
Kazan, Russia 420008 Kazan, Russia 420008 Oulu, Finland FI-90014
konn-igor@ya.ru leksser@rambler.ru erkki.laitinen@oulu.fi
Abstract
In the paper we consider the problem of allocation of network resources
in telecommunication networks with respect to both utility and relia-
bility 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.
1 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 in-
formation 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.
Copyright c by the paper’s authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
In: Sergei S. Goncharov, Yuri G. Evtushenko (eds.): Proceedings of the Workshop on Applied Mathematics and Fundamental
Computer Science 2021 , Omsk, Russia, 24-04-2021, published at http://ceur-ws.org
1
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.
2 Problem Description
We first take the optimal link distribution problem in computer and telecommunication data transmission net-
works, 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 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: X
max → ui (xi )
i∈I
subject to
X
xi ≤ cl , l ∈ L;
i∈Il
0 ≤ xi ≤ αi , i ∈ I.
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 P to each arc flow and determine µl (fl ) as the non-reliability of the
l-th arc having the flow fl for l ∈ L. Then l∈L µl (fl ) is the total network non-reliability and we formulate the
network manager problem as follows:
!
X X X X
min → µl (fl ) − ui (xi ) or max → ui (xi ) − µl (fl ) , (1)
l∈L i∈I i∈I l∈L
subject to
X
xi = fl , l ∈ L; (2)
i∈Il
0 ≤ fl ≤ cl , l ∈ L; (3)
0 ≤ xi ≤ αi , i ∈ I. (4)
If the functions ui (xi ) and −µl (fl ) 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 ui (xi ) and −µl (fl ) are concave.
3 Solution Method
Take number θ > 0, points x0 (0 ≤ x0 ≤ α), f 0 (0 ≤ f 0 ≤ c) and sequence of numbers {εk }
∞
εk < ∞). At the k-th iteration, k = 0, 1, ..., we have a pair (xk , f k ). We find (xk+1 , f k+1 ) as
P
({εk } ↓ 0,
k=0
a solution of the problem
2
( )
X θ
X
θ
k 2 k 2
min → µl (fl ) + (fl − fl ) + (xi − xi ) − ui (xi ) (5)
2 2
l∈L i∈I
subject to
X
xi = fl , l ∈ L; (6)
i∈Il
0 ≤ fl ≤ cl , l ∈ L; (7)
0 ≤ xi ≤ αi , i ∈ I. (8)
with the accuracy εk .
Let us define the Lagrange function of problem (5)–(8) as follows:
!
X θ
X
θ
X X
Lk (x, f, y) = µl (fl ) + (fl − flk )2 + (xi − xki )2 − ui (xi ) + yl fl − xi .
2 2
l∈L i∈I l∈L i∈Il
By duality, we can replace problem (5)–(8) with the dual unconstrained optimization problem:
max → ϕ(y), (9)
y
where
min µl (fl ) + θ2 (fl − flk )2 + yl fl +
P
ϕ(y) = min Lk (x, f, y) =
0≤x≤α,0≤f ≤c l∈L 0≤fl ≤cl
( )
(10)
θ k 2
P P
min 2 (xi − xi ) − ui (xi ) − xi yl .
i∈I 0≤xi ≤αi l∈Li
Each of one-dimensional problem of (10) can be solved easily by explicit formulas.
Function ϕ(y) in (9) is concave,
∂ϕ(y) X
= xi (y) − fl (yl ), l ∈ L.
∂yl
i∈Il
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 ϕ0 (y k ), λk > 0.
4 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
ui (xi ) = u1,i x2i + u0,i xi , u1,i < 0, u0,i > 0, i ∈ I,
linear functions of utility of origin-destination pairs
ui (xi ) = u1,i xi + u0,i , u1,i , u0,i > 0, i ∈ I,
and quadratic functions of non-reliability of arcs
µl (fl ) = µ1,l fl2 + µ0,l fl , µ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 , u0,i , and u1,i were formed on the basis of trigonometric functions:
3
(i) for the case of quadratic functions ui
u0,i = 2| sin(2i + 2)| + 2, u1,i = −| cos(2i + 1)| − 1,
(ii) for the case of linear functions ui
u0,i = | sin(2i + 2)| + 1, u1,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 ui as L-case and the case of quadratic functions ui as Q-case.
The maximal arc flow capacity cl was selected in [1, 10] as follows:
cl = 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 kϕ0 (y k )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.
4
Table 1: Computations for |L| = 310, θ = 0.9, Q-case
|I| Tεk ,1 Iεk ,1 Tεk ,100 Iεk ,100
620 0.031 41 0.139 464
930 0.021 48 0.138 339
1240 0.027 48 0.188 340
Table 2: Computations for |I| = 310, θ = 0.9, Q-case
|L| Tεk ,1 Iεk ,1 Tεk ,100 Iεk ,100
620 0.015 41 0.452 1220
930 0.014 28 0.623 1191
1240 0.097 117 1.263 1804
Table 3: Computations for |I| = 310, θ = 0.5, Q-case
|L| Tεk ,1 Iεk ,1 Tεk ,100 Iεk ,100
620 0.016 45 0.454 1232
930 0.018 34 0.638 1222
1240 0.043 59 1.230 1786
Table 4: Computations for |I| = 310, θ = 5.0, Q-case
|L| Tεk ,1 Iεk ,1 Tεk ,100 Iεk ,100
620 0.007 17 0.426 1151
930 0.005 11 0.604 1177
1240 0.042 51 1.166 1667
Table 5: Computations for |L| = 310, θ = 0.9, L-case
|I| Tεk ,1 Iεk ,1 Tεk ,100 Iεk ,100
620 0.023 75 0.122 419
930 0.047 109 0.116 278
1240 0.072 133 0.174 316
Table 6: Computations for |I| = 310, θ = 0.9, L-case
|L| Tεk ,1 Iεk ,1 Tεk ,100 Iεk ,100
620 0.028 77 0.367 1043
930 0.026 53 0.263 526
1240 0.098 119 1.063 1519
5
Table 7: Computations for ε = 10−2 , εk = εk−1 ∗ 0.9, |L| = 310
|I| Tεk ,1 Iεk ,1 Tεk ,100 Iεk ,100 Tε,1 Iε,1 Tε,100 Iε,100
620 0.031 41 0.139 464 0.023 51 0.093 229
930 0.021 48 0.138 339 0.032 48 0.094 159
1240 0.027 48 0.188 340 0.031 51 0.094 150
Table 8: Computations for |I| = 310, θ = 0.9, ε = 10−2 , εk = εk−1 ∗ 0.9, |I| = 310
|L| Tεk ,1 Iεk ,1 Tεk ,100 Iεk ,100 Tε,1 Iε,1 Tε,100 Iε,100
620 0.015 41 0.452 1220 0.031 58 0.365 691
930 0.014 28 0.623 1191 0.047 53 0.640 815
1240 0.097 117 1.263 1804 0.078 66 0.797 856
4.0.1 Acknowledgments
In this work, the first 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 first and third authors were also supported by grant No. 331833 from Academy
of Finland.
References
[CW03] C. Courcoubetis, R. Weber. Pricing Communication Networks: Economics, Technology and Modelling.
Chichester: John Wiley & Sons, 2003.
[SWB06] S. Stanczak, M. Wiczanowski, H. Boche. Resource Allocation in Wireless Networks. Theory and Algo-
rithms. Berlin: Springer, 2006.
[WNH10] A. M. Wyglinski, M. Nekovee, Y. T. Hou (eds.) Cognitive Radio Communications and Networks:
Principles and Practice. Amsterdam: Elsevier, 2010.
[KKL18] I. Konnov, A. Kashuba, E. Laitinen. Dual methods for optimal allocation of telecommunication network
resources with several classes of users. Math. Comput. Appl., 23, Art. No 31: 1–14, 2018.
[KK19] I. V. Konnov, A. Yu. Kashuba. Application of the conditional gradient method to a network resource
allocation problem with several classes of users. Journal of Physics: Conference Series. 1158, Art. No
032015: 1–8, 2019.
[ZJT13] S.T. Zargar, J. Joshi, D. Tipper. A survey of defense mechanisms against distributed denial of service
(ddos) flooding attacks. IEEE Communications Surveys & Tutorials, 15 (4): 2046–2069, Mar. 2013.
[MZA13] M.H. Manshaei, Q. Zhu, T. Alpcan, T. Bacsar, J.-P. Hubaux. Game theory meets network security
and privacy. ACM Computing Surveys (CSUR), 45 (3): 25–64, Jun. 2013.
[ZJT13] S. Vadlamani, B. Eksioglu, H. Medal, A. Nandi. Jamming attacks on wireless networks: A taxonomic
survey. International Journal of Production Economics, 172: 76–94, Feb. 2016.
[LHW17] N.C. Luong, D.T. Hoang, P. Wang, D. Niyato, Z.Han. Applications of economic and pricing models
for wireless network security: a survey. IEEE Communications Surveys & Tutorials, 19 (4): 2735–2767,
Jul. 2017.
[KKL20] I.V. Konnov, A.Yu. Kashuba, E. Laitinen. Penalty method for reliable allocations of wireless network
resources. CEUR Workshop Proceedings, 2642, 2020.
6
[KKL21] I. Konnov, A. Kashuba, E. Laitinen. Dual Decomposition Method for Reliable Allocations of Wireless
Network Resources. Mobility 2021: The Eleventh International Conference on Mobile Services, Resources,
and Users, 2021.
[KMT98] F.P. Kelly, A. Maulloo, D. Tan. Rate control for communication networks: shadow prices, proportional
fairness and stability. J. Oper. Res. Soc., 49 (3): 237–252, 1998.
7