Про деякі методи розв’язання задачі розподілу потужності каналів передавання даних з урахуванням нечітких обмежень на обсяги споживання
The article deals with the mathematical formulation of the problem of optimal distribution of the power of data transmission channels in information and computer networks with a three-level architecture and fuzzy restrictions on consumption volumes. An efficient algorithm has been developed for solv...
Збережено в:
| Дата: | 2022 |
|---|---|
| Автори: | , , , |
| Формат: | Стаття |
| Мова: | Англійська |
| Опубліковано: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2022
|
| Теми: | |
| Онлайн доступ: | https://journal.iasa.kpi.ua/article/view/254733 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | System research and information technologies |
| Завантажити файл: |  |
Репозитарії
System research and information technologies| _version_ | 1867334424612306944 |
|---|---|
| author | Ivokhin, Eugene Adzhubey, Larisa Vavryk, Petro Makhno, Mykhailo |
| author_facet | Ivokhin, Eugene Adzhubey, Larisa Vavryk, Petro Makhno, Mykhailo |
| author_institution_txt_mv | [
{
"author": "Eugene Ivokhin",
"institution": "Taras Shevchenko National University of Kyiv, Kyiv"
},
{
"author": "Larisa Adzhubey",
"institution": "Taras Shevchenko National University of Kyiv, Kyiv"
},
{
"author": "Petro Vavryk",
"institution": "Taras Shevchenko National University of Kyiv, Kyiv"
},
{
"author": "Mykhailo Makhno",
"institution": "Taras Shevchenko National University of Kyiv, Kyiv"
}
] |
| author_sort | Ivokhin, Eugene |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2023-05-21T20:04:38Z |
| description | The article deals with the mathematical formulation of the problem of optimal distribution of the power of data transmission channels in information and computer networks with a three-level architecture and fuzzy restrictions on consumption volumes. An efficient algorithm has been developed for solving the problem, the peculiarity of which is the inability to meet the end user’s needs at the expense of the resources of different suppliers. A standard solution method based on a fuzzy optimization problem of mathematical programming is considered. A constructive variant of finding a solution based on the backtracking method is proposed. Computational experiments have been carried out. The developed approach was used to determine the optimal configuration of a three-level information and computer network with a given number of communication servers. |
| doi_str_mv | 10.20535/SRIT.2308-8893.2022.4.08 |
| first_indexed | 2025-07-17T10:27:47Z |
| format | Article |
| fulltext |
E.V. Ivokhin, L.T. Adzhubey, P.R. Vavryk, M.F. Makhno, 2022
88 ISSN 1681–6048 System Research & Information Technologies, 2022, №4
UDC 519.87:004.02
DOI: 10.20535/SRIT.2308-8893.2022.4.08
ON SOME METHODS FOR SOLVING THE PROBLEM OF
POWER DISTRIBUTION OF DATA TRANSMISSION CHANNELS
TAKING INTO ACCOUNT FUZZY CONSTRAINTS ON
CONSUMPTION VOLUMES
E.V. IVOKHIN, L.T. ADZHUBEY, P.R. VAVRYK, M.F. MAKHNO
Abstract. The article deals with the mathematical formulation of the problem of op-
timal distribution of the power of data transmission channels in information and
computer networks with a three-level architecture and fuzzy restrictions on con-
sumption volumes. An efficient algorithm has been developed for solving the prob-
lem, the peculiarity of which is the inability to meet the end user’s needs at the ex-
pense of the resources of different suppliers. A standard solution method based on a
fuzzy optimization problem of mathematical programming is considered. A con-
structive variant of finding a solution based on the backtracking method is proposed.
Computational experiments have been carried out. The developed approach was
used to determine the optimal configuration of a three-level information and com-
puter network with a given number of communication servers.
Keywords: data transfer, power distribution, fuzzy constraints, optimal solution,
backtracking algorithm.
INTRODUCTION
The tasks of finding optimal solutions arise in the process of development and
practical implementation of methods for effective management of various organiza-
tional, technological and information systems.
An important characteristic of optimization problems is the desire to find the
optimal solution (optimality principle). In practice, there are a number of con-
straints that do not allow finding such a solution. In these cases, the question is
raised of finding not optimal, but rational (compromise, effective) solutions that
satisfy the problem statement. It is often necessary to find a compromise between
the effectiveness of solutions and the cost of finding them. Serious difficulties
arise when solving optimization problems under conditions of incomplete infor-
mation, as well as in the case when random or subjective factors (parameters)
play a significant role.
One of the applied problems in which there can be uncertainty in setting the
parameters is the problem of distributing the limited capacities of data transmis-
sion channels between different nodes of the Internet providers network. Suppose
that there is a local computer network of an enterprise (organization, educational
institution) that provides users with access to the Internet. User access to the
global network and obtaining the necessary information is carried out using several
communication servers located on the territory of the information and computer
center of the enterprise and connected by high-speed external communication
channels with Internet providers. The bandwidth levels of the servers are within the
bandwidth (bandwidth) of the local network (for example, 1Gb per second).
On some methods for solving the problem of power distribution of data transmission …
Системні дослідження та інформаційні технології, 2022, № 4 89
It is assumed that the network implements the conditions for efficient
channel switching (relative to their bandwidth), which are provided by
programmable network devices (communication servers, routers). The structure
of the network and the information distributed in it in the general case can be very
diverse. In this case, we consider the problem of distribution of limited capacities
with the following constraints:
information is distributed from the provider to subscribers (nodes)
through switching servers via communication channels with a bandwidth that
takes into account the specified bandwidth;
each network subscriber is serviced by one switching server;
the throughput of receiving information for switching nodes and subscribers
is limited both from above (fundamental limitations of the provider’s capabilities)
and from below (the minimum need for subscribers to receive information).
The problem of determining the bandwidth of an external connection is con-
sidered, which makes it possible to maximize the total bandwidth of user commu-
nication channels by changing the total power of communication servers, taking
into account both the needs and wishes of subscribers (users) and the capabilities
of the information and computing center.
The solution of the formulated problem was considered in [1–7] on the basis
of solving problems of optimal resource allocation. The problems of efficient use
of a homogeneous resource were considered using the example of time distribu-
tion in the form of a classical problem of distributing resources of a given volume
over a set of categories (works) [8]. The setting of such tasks consists in finding a
cost plan for the available resource (such a resource is most often considered
time) for the execution of a group of tasks, in which the total (final) use of the
resource is optimal.
In a number of papers [9–11] to find a solution, an approach is proposed that
uses multi-index problems of the transport type [11]. In the noted works, meaningful
formulations of such applied problems are given and their mathematical models
are constructed.
When solving applied multi-index optimization problems, special interest is
given to formulations related to the class of problems of integer linear program-
ming [11]. One of the approaches to the development of algorithms for solving
such optimization problems is the use of streaming methods. Known efficient
flow algorithms [12] make it possible to construct solution methods that have ac-
ceptable estimates of computational complexity compared to estimates of general
methods for solving linear programming problems.
Solutions obtained on the basis of models of three-index transport problems
[10] allow solving the problem of distribution of a homogeneous resource for cas-
es where the cost and resource consumption factors are known a priori.
In [13,14], a model of a two-level production and transport problem was
considered with a criterion that takes into account the optimal cost indicators for
the production and transportation of resources, the volumes of production and
consumption of which are given.
PROBLEM FORMALIZATION OF THE DATA TRANSMISSION CHANNELS
OPTIMAL DISTRIBUTION POWER
An information and computer network is considered, including 1N data transmis-
sion channels (global network providers), 2N communication servers and 3N
E.V. Ivokhin, L.T. Adzhubey, P.R. Vavryk, M.F. Makhno
ISSN 1681–6048 System Research & Information Technologies, 2022, № 4 90
end users (subscribers). We denote by
iA , 1,1 Ni , the values of the maximum
bandwidth of the data transmission channel that provider i, 1,1 Ni , is able to
provide;
jB , 2,1 Nj — the value of the maximum bandwidth of the data
transmission channel that the communication node j, 2,1 Nj , can provide;
kk CC , , 3,1 Nk — values of the minimum and maximum bandwidth of the
data transmission channel, which must be provided to the subscriber k, 3,1 Nk ;
kt — throughput of the k-th subscriber station, 3,1 Nk . Then, assuming that the
power distribution of communication channels satisfies the conditions of additiv-
ity and proportionality, we can consider the problem of distributing a limited ho-
mogeneous resource (bandwidth of communication channels) with transport-type
constraints in order to find the optimal data transmission plan. This ensures the
effective functioning of the system for providing users with Internet access, which
consists in finding the optimal values of data transmission bandwidths iT of
the i-th information provider (provider), 1,1 Ni , and the optimal values of the
bandwidths kt of using local communication channels of the k-th user, 3,1 Nk .
Formally, the statement of problem can be written as
1max t ; 2max t ; …
3
max Nt ,
with the following constraints
;
13
11
N
i
i
N
k
k At
jk Bt , 2,1 Nj , 3,1 Nk ; kkk CtC , 3,1 Nk ;
312
111
N
k
k
N
i
i
N
j
j CAB .
SOLVING METHODS OF THE PROBLEM OF DATA TRANSMISSION
CHANNELS OPTIMAL DISTRIBUTION POWER TAKING INTO ACCOUNT
FUZZY CONSTRAINTS ON CONSUMPTION VOLUMES
Let’s assume that the needs of network subscribers to increase the speed of ob-
taining one or another amount of information are known. The wishes (prefer-
ences) of subscribers are set regarding a possible increase in consumption vol-
umes (bandwidths) for transmitting information from the provider to the user
node. To implement the changes, it is necessary to update the capacities of the
switching servers of the network by deploying new, more powerful computers or
by increasing the number of existing servers. In other words, it is necessary to
conduct a study on updating the resources of the server park of the information
and computing center, which makes it possible to increase the total bandwidth of
a group of switching servers. At the same time, the value of the total capacity of
servers, both in the case of an increase in the capacity of the existing fleet of
computers, and in the case of an increase in the number of servers, is assumed to
be the same.
On some methods for solving the problem of power distribution of data transmission …
Системні дослідження та інформаційні технології, 2022, № 4 91
If the values of consumption parameters are random variables with known
distribution functions, then it can be solved by stochastic programming methods.
However, in practice these parameters are often unknown and only the range of
possible values can be determined for them. A problem of this type can be called
a problem with multiple values of the coefficients. Within the framework of this
problem, it makes no sense to talk about maximizing the objective function, since
the values of this function are not numbers, but sets of numbers. In this case, it is
necessary to find out what preference relation this function generates on the set of
alternatives, and then determine which products should be considered rational in
the sense of this preference relation.
The next step on the way of detailing and refining the model considered here
is the description of the problem parameters in the form of fuzzy sets (numbers)
[15]. Additional information is introduced into the model in the form of a mem-
bership function of these fuzzy sets. These functions can be considered as a way
for an expert to approximate his unformalized idea of the real value of a given
parameter. Membership function values are the weights that experts assign to the
various possible values of this parameter.
Fuzzy sets are a mathematical model of object classes with fuzzy or blurry
boundaries. In other words, an element can have some degree of membership in
the set, and it is intermediate between full membership and complete non-
membership.
Traditional (ordinary) set theory can be viewed as a special case of fuzzy set
theory. An ordinary subset A of a set X can be represented as a fuzzy set, which
is given by the characteristic function }1,0{: XχA :
.:1
;:0
)(
Ax
Ax
xA
In accordance with the idea of Zadeh [15], a fuzzy subset of a given univer-
sal set X is formulated as follows.
Definition 1. A fuzzy subset A
~
of the universal set X , is a collection of
pairs )}),({(
~
~ xxA A , where ]1,0[:)(~ XxA is the mapping of the set X into
the unit segment [0,1], which is called the membership function of the fuzzy set.
The value of the membership function )(~ xA for an element Xx is called
the degree of membership. The interpretation of the degree of membership )(~ xA
is a subjective measure of how much an element Xx corresponds to a concept,
the meaning of which is formalized by a fuzzy set A
~
.
Let 1RX is a universal set.
Definition 2. [16] A fuzzy triangular number (triplet) A
~
is an ordered triplet
of numbers (а, b, c), cba , defining a membership function )(~ xA of the form:
ab
ax
xA
)(~ , ],[ bax ;
bc
xc
xA
)(~ , ],[ cbx ; ],[ cax . (1)
A fuzzy triangular number of the form ( , , )a b b , called a left fuzzy trian-
gular number, is determined by the membership function of the form:
E.V. Ivokhin, L.T. Adzhubey, P.R. Vavryk, M.F. Makhno
ISSN 1681–6048 System Research & Information Technologies, 2022, № 4 92
,0)(~ xA
ax ;
ab
ax
xA
)(~ , ],[ bax ; 1)(~ xA , bx ,
and the fuzzy triangular number of the form (b, b, c), called the right fuzzy trian-
gular number, is the membership function nRx :
1)(~ xA , bx ;
bc
xc
xA
)(~ , ],[ cbx ; ,0)(~ xA
cx . (2)
After such clarification, we can proceed to the next statement of the problem
of fuzzy mathematical programming [17]. A linear view model is specified
max~
1
n
j
jj xc , (3)
in which the values of the coefficients jc~ , nj ,1 , are given fuzzy in the form of
fuzzy sets of given universal sets. In addition, there are constraints:
i
n
j
jij bxa
~~
1
, mi ,1 , 0jx , nj ,1 , (4)
and the values of the coefficients ija~ , ib
~
, mi ,1 , nj ,1 , are also described in
the form of the corresponding fuzzy sets. It is required to make a rational choice
of a solution nRx , that, in a certain sense, maximizes the given fuzzy linear form (3).
We call such a statement of the fuzzy optimization problem a linear pro-
gramming problem with fuzzy parameters. One of its variants is a problem with
fuzzy resource constraints on the right side.
Consider now a linear programming problem with a given goal function
x
max
n
j
jj xc
1
(5)
and fuzzy constraints on resources of the form
n
j
ijij bxa
1
~
, mi ,1 , nRxx ;0 , (6)
where the right parts of constraints (6) are given as fuzzy right triangular numbers
with corresponding membership functions of the form (1). Here, the allowable
deviations determine the values of the boundary changes of the model resources.
This formulation does not restrict the general form of optimization problems
with fuzzy constraints [18, 19]. Indeed, one can consider a linear programming
problem with fuzzy resources in the form of an optimization problem for the goal
function (5) in the presence of a system of mixed constraints:
n
j
ijij bxa
1
~
, 1,1 mi ;
n
j
ijij bxa
1
~
, 21 ,1 mmi ;
n
j
ijij bxa
1
~
, mmi ,12 ,
where the right parts of the first 1m constraints are given by left fuzzy triangular
numbers ib
~
= ),,( 0
iiii bbbb , 00 ib , 1,1 mi , the right parts of the next group of
On some methods for solving the problem of power distribution of data transmission …
Системні дослідження та інформаційні технології, 2022, № 4 93
constraints are given by right fuzzy triangular numbers ib
~
= ),,( 0
iiii bbbb ,
00 ib , 21 ,1 mmi , and the right parts of the last m – 2m constraints are given
by fuzzy triangular numbers ib
~
= ),,( r
iii
l
ii bbbbb , with allowable deviations
i
l
i bb 0 , 0r
ib , mmi ,12 .
This LP model can be rewritten in the form (4)–(5) by replacing the first 1m
conditions with the next constraints
n
j
ijij bxa
1
~
)( , ib
~
= ),,( 0
iiii bbbb ,
1,1 mi , and the last m – 2m conditions — with a system of constraints
n
j
ijij bxa
1
~
)( , ib
~
= ),,( l
iiii bbbb ;
n
j
ijij bxa
1
~
, ib
~
= ),,( r
iiii bbbb ;
mmi ,12 . Thus, we can assume that the general form of a linear programming
problem with fuzzy resource constraints on the right side is given by model
(5)–(6).
The optimization problem under consideration can be solved as a parametric
linear programming problem [20]. This method is universal, not always taking
into account the specifics of the task.
We use an approach based on the defuzzification of problem (5)–(6). To do
this, we calculate the optimal values of the levels of the objective function lZ and
uZ by solving two linear programming problems:
lZ =
x
max
n
j
jj xc
1
(7)
with constraints
n
j
ijij bxa
1
, mi ,1 , nRxx ;0 ; (8)
uZ =
x
max
n
j
jj xc
1
(9)
under condition
n
j
iijij bbxa
1
0 , mi ,1 , nRxx ;0 . (10)
Let be L = ),min( ul ZZ ,U = ),max( ul ZZ . The fuzzy set of optimal values of
problem (5)–(6) specified in nR (we denote it by G
~
) is described by the mem-
bership function of the form:
,,1
;),/()(
;,0
)(
1
11
1
~
Uxc
UxcLLULxc
Lxc
x
n
j
jj
n
j
jj
n
j
jj
n
j
jj
G (11)
E.V. Ivokhin, L.T. Adzhubey, P.R. Vavryk, M.F. Makhno
ISSN 1681–6048 System Research & Information Technologies, 2022, № 4 94
and the fuzzy sets of each constraint (we denote them by iF
~
, mi ,1 ) from (6)
are determined by the membership functions:
.,0
,,/)(
;,1
)(
0
1
0
1
0
1
0
1
~
ii
n
j
jij
ii
n
j
jijii
n
j
jijii
i
n
j
jij
F
bbxa
bbxabbxabb
bxa
x
i
mi ,1 ; (12)
Based on the definition of the Bellman-Zadeh fuzzy solution [21], the fuzzy
linear programming problem (5)–(6) can be written in the form of an optimization
problem of the following form: find the value of the parameter ,1,0 that is
the solution of the linear programming problem
x
max
with constraints
;)(~ x
G
;)(~ x
iF
.0x mi ,1 . (13)
Substituting (11) and (12) into (13), we write the final form of the optimiza-
tion problem
x
max
with constraints
;0)(
1
LxcLU
n
j
jj
;,1,00
1
mibbbxa iii
n
j
jij
.10,0 x (14)
This problem is a classical linear programming problem, for finding
solutions to which any variant of the simplex method can be applied.
Let us assume that in the formulation of the problem of distributing the
power of data transmission channels, the current values of the throughput of
communication channels of each subscriber k, kC , 3,1 Nk , are known, and the
values of
kC , 3,1 Nk , determine the values of the bandwidths that are planned
by users as a result of updating communication equipment. Obviously, it is
possible to fully satisfy the expansion of the bandwidth of subscriber channels
only under the condition
32
11
N
k
k
N
j
j CB .
Formally, the statement of problem can be written as
1max t ; 2max t ; …
3
max Nt , (15)
with the following constraints
On some methods for solving the problem of power distribution of data transmission …
Системні дослідження та інформаційні технології, 2022, № 4 95
],[~supp kkkk ССtt , 3,1 Nk ; ;At
N
i
i
N
k
k
13
11
jk Bt , 2,1 Nj , 3,1 Nk ;
312
111
N
k
k
N
i
i
N
j
j CAB . (16)
We will assume that the capacities of communication channels available to
users satisfy the conditions
133
111
N
i
i
N
k
k
N
k
k AtC , and the values of the possible
expansion of the channel capacity are determined by right-hand fuzzy triangular
numbers in the form ),,(
kkk CCC , 3,1 Nk , with linear membership functions (2).
This problem is a multiobjective optimization problem. To solve it, methods
are used that allow finding a compromise (effective) solution by reducing the
problem to a single-criterion one in the form of a convolution of criteria or to a
sequence of single-criteria optimization problems [22]. In the case of fuzzy con-
straints, each such problem can be reduced to an optimization problem of the
form (13) or (14) with subsequent solution by the method proposed above.
Taking into account the specifics of the obtained problem, the most rational
method is the sequential introduction of constraints [22]. A characteristic feature
of this method, which makes it possible to use it to find an effective solution, is
the sequential (at each step) introduction of constraints on the width of the
communication channel, at which unsatisfactory values of the criteria are achieved.
Following the search methodology, at each algorithm’s step ,...2,1p , an
“ideal assessment” ),...,,( )*()*(
2
)*(
1
)*(
3
p
N
ppp tttt , ,...2,1p , is formed, where )*( p
kt ,
3,1 Nk , are the optimal values of each of the criteria (19) ktmax , 3,1 Nk , on
a given range of acceptable values pG , },1;{ 31 NkСtG kk , 1pG
}|,1;{ 3 sspk tNkGt , },...,2,1{ 3Ns is the number of the criterion, the
value of which is the least consistent with the compromise solution. It is clarified
to what level s the value of this criterion should be changed, and a search for a
new solution is performed, taking into account the additional constraint.
This method allows solving the problem of efficient distribution of channel
capacities, taking into account fuzzy constraints on consumption volumes, how-
ever, to use it at each step, it is necessary to evaluate the compliance of the cur-
rent solution with a certain “ideal” solution, which, as a rule, is formed with the
participation of an expert. In addition, the solution procedure turns out to be cum-
bersome, leading to the multiple solution of optimization problems of the form
(7)–(10) and the construction of a Bellman-Zade fuzzy solution (14).
Additionally it is easy to formalize this process by applying the back track-
ing solution search procedure [23].
From the condition of the problem of optimizing the distribution of channel
powers, taking into account fuzzy constraints on consumption volumes (15)–(16),
it follows that
323
111
N
k
k
N
j
j
N
k
k CBC .
E.V. Ivokhin, L.T. Adzhubey, P.R. Vavryk, M.F. Makhno
ISSN 1681–6048 System Research & Information Technologies, 2022, № 4 96
Obviously, in this case, it is impossible to allocate the maximum expected
power of communication channels to all subscribers. We will look for a solution
on rational distribution based on the scheme of the back tracking algorithm.
Algorithm.
Step 0. Without loss of generality, we will assume that the order of users is
ordered in non-increasing order of the planned capacities of communication
channels. We put the required values in the initial solution kk Сt , 3,1 Nk .
Step 1,2,s s=1,2,... We check the fulfillment of condition
23
11
N
j
j
N
k
k Bt . (17)
If inequality (17) is satisfied, the algorithm terminates, otherwise:
a) determine the q, ],1[ 3Nq , largest (first of 3N ) values kt , 3,1 Nk ;
b) decrease the values kt , qk ,1 , by 0t : kt = ttk , qk ,1 .
Obviously, the total demand in this case decreases.
Change 1 ss and move on to the next step.
RESULTS OF COMPUTATIONAL EXPERIMENTS
The algorithm proposed above for finding a solution in the problem of rational
distribution of the power of communication channels, taking into account fuzzy
constraints on consumption volumes (15)–(16), was used to calculate the values
of throughput resources in a network with 1 Internet provider, 2 (3, 4) routers
(communication servers ) and 17 end users (collective subscribers).
The bandwidth of user connections to communication servers was initially
350, 250, 250, 245, 180, 180, 165, 165, 160, 145, 140, 140, 140, 120, 110, 80, 80
Mb/s (total capacity 2900 Mb/s). In order to expand consumer traffic, it is proposed to
upgrade equipment in the form of a possible increase in the number of servers
or/and increase their capacity. The bandwidth of the communication channel with
the provider remains constant and equals 10 Gb/s. The total throughput capacity
of communication servers after the upgrade is planned to be 3 Gb/s.
To determine the rational distribution of the size of communication channels,
consumers were asked to determine the required size of connections to
communication servers. Based on the given amount of traffic, it was planned to
use 2, 3 or 4 servers with a total capacity of 3 Gb/s.
Computational experiments on the efficient distribution of the power of
communication channels were carried out using the above algorithm for the
classical solution of optimization problems with fuzzy constraints on consumption
levels (fuzzy approach) and the algorithm using the backtracking approach. In the
latter case, both a consistent uniform decrease in consumer requests by the value
0t (app1) and a proportional decrease in the values of requests were applied,
taking into account the required volumes of traffic increase (app2).
The results of the numerical experiments performed are shown in Table.
On some methods for solving the problem of power distribution of data transmission …
Системні дослідження та інформаційні технології, 2022, № 4 97
T a b l e 1 . The results of numerical experiments on the efficient distribution of
the power of communication channels
Сonsumers
p1 p 2 p 3 p 4 p 5 p 6 p 7 p 8 p 9 p 10 p 11 p 12 p 13 p 14 p15 p16 p 17 Sum
Init Power, Мb/s (Max Sum Power=2900 Mb/s)
350 250 250 245 180 180 165 165 160 145 140 140 140 120 110 80 110 2900
Plan Power, Мb/s (Max Sum Power=3000 Mb/s )
370 275 275 260 195 185 180 175 165 155 150 150 145 125 115 90 115 3100
Results for K communication servers, Mb/s
Approuch: app1
CommunicationPower*K=1500×2
363 268 268 253 188 183 173 168 158 148 143 143 138 118 108 85 108 2995
CommunicationPower*K=1000×3
359 264 264 249 184 179 169 164 154 144 139 139 134 114 105 83 105 2934
CommunicationPower*K=750×4
357 262 262 247 182 177 167 162 152 142 137 137 132 112 107 89 107 2914
Approuch: app2
CommunicationPower*K=1500×2
354 254 254 254 184 184 174 169 164 149 149 149 144 124 114 89 114 2999
CommunicationPower*K=1000×3
352 252 252 252 182 182 172 167 162 147 147 147 142 122 112 87 112 2967
CommunicationPower*K=750×4
350 250 250 250 180 180 170 165 160 145 145 145 140 120 110 85 110 2935
Approuch: fuzzy
CommunicationPower*K=1500×2
361 266 266 251 186 181 171 166 160 150 146 144 141 121 110 83 110 2985
CommunicationPower*K=1000×3
362 267 267 252 187 182 173 167 160 150 147 142 140 120 110 82 110 2989
CommunicationPower*K=750×4
355 260 260 245 180 175 165 160 150 150 145 140 135 118 108 79 108 2900
As follows from the results obtained, the application of the proposed
algorithm made it possible to obtain the most efficient (close to optimal) solutions
in the considered distribution problem for a configuration with two
communication servers with a maximum bandwidth of 1500 Mb/s. The best
solution to the problem using the method of efficient channel power distribution,
taking into account fuzzy constraints, was obtained for the connection option with
3 routers. At the same time, it slightly differs from the solution with two servers,
which suggests that the best option in the considered distribution problem is the
variant with two communication servers. It should also be noted that the solution
based on the algorithm using the return scheme does not require significant
computational resources, which allows us to speak about the constructiveness of
the method. The resulting solution was used as the basis for the technical
modernization of equipment to ensure the operation of network subscribers.
DISCUSSION AND CONCLUSIONS
Several remarks should be noted. First, the amount t of change in the power of
communication channels in the backtracking algorithm, which is set at the begin-
ning of the work, depends on the values of the optimized data transfer volumes
E.V. Ivokhin, L.T. Adzhubey, P.R. Vavryk, M.F. Makhno
ISSN 1681–6048 System Research & Information Technologies, 2022, № 4 98
and affects the rate of convergence of the algorithm. The choice of small values
t leads to a more accurate rational distribution of powers, but slows down con-
vergence. Otherwise, for large values t , the solution is reached faster, but its
quality in terms of the obtained volumes, as a rule, turns out to be lower.
In addition, in the proposed version of the algorithm, a rational solution is sought
at the expense of the most demanding subscribers in terms of volume. Obviously,
the search procedure can be restructured to use other similar principles or to
evenly distribute the redundancy of the total traffic request among all network users.
The problem of optimal power distribution of communication channels in
information-computer networks with a three-level architecture is considered.
Approaches for its solution are studied, the problem statement with fuzzy
constraints on the consumption volumes of end users is considered. A fuzzy
optimization problem is formulated, which allows taking into account the interval
specified volumes for the connection values. A variant of solving fuzzy
optimization problems in the case of using fuzzy numbers is proposed. A multi-
objective problem of efficient power distribution of communication channels with
fuzzy constraints is formulated. A variant of the algorithm with a return is
proposed, which allows solving the obtained problem. The approach is illustrated
by a number of numerical examples of a problem with a given number of end
users and different allowable bandwidths of communication servers.
The results obtained were analyzed, which made it possible to make a
decision on the method of upgrading the communication equipment. The
proposed approach based on the method using the return scheme turned out to be
a constructive way to solve the problem considered in the article.
REFERENCES
1. L.G. Afraimovich and M.Kh. Prilutskii, “Multiindex Resource Distributions for Hierar-
chical Systems,” Automation and remote control, vol. 67, no. 6, pр. 1007–1016, 2006.
2. M.Kh. Prilutskii, “Many-Criteria Distribution of a Homogeneous Resource in Hierarchi-
cal Systems,” Automation and Remote Control, no. 2, pp. 24–29, 1996.
3. M.Kh. Prilutskii, “Distribution of a Homogeneous Resource in Tree-Structured Hierar-
chical Systems,” Proc. III Int. Conf. Identification of Systems and Control Problems
(SICPRO’2000), pp. 2038–2049.
4. M.Kh. Prilutskii and A.G. Kartomin, “Flow Algorithms for Allocation of Resources in
Hierarchical Systems,” Investigated in Russia, 39, pp. 444–452, 2003. Available:
http://zhurnal.ape.relarn.ru/articles/2003 /039.pdf
5. A. Schrijver, Theory of Linear and Integer Programming. Wiley, 1998, 484 p.
6. E.G. Zhdanova, Schedule theory. M., 2000, 136 p.
7. D.W. Pentico, “Assignment problems: A golden anniversary survey,” European Journal
of Operational Research, vol. 176, pp. 774–793, 2007. doi: 10.1016/j.ejor.2005.09.014.
8. Е. Ivokhin and M. Makhno, “On an approach to construction of structured fuzzy sets and
their application for description of fuzzy time response,” Journal of Automation and In-
formation Science, 49(10), pp. 55–63, 2017. doi: 10.1615/JAutomatInfScien. v49.i10.60.
9. F.C.R. Spieksma, “Multi index assignment problems: complexity, approximation, appli-
cations,” Nonlinear Assignment Problems. Algorithms and Applications; P.M. Pardalos,
L.S. Pitsoulis (Eds.). Dordrecht: Kluwer Academic Publishers, 2000, pp. 1–11. doi:
10.1007/978-1-4757-3155-2_1.
10. Y.Crama and F.C.R. Spieksma, “Approximation algorithms for three-dimensional as-
signment problems with triangle inequalities,” European Journal of Operational Re-
search, vol. 60, pp. 273–279, 1992. doi: 10.1016/0377-2217(92)90078-N.
11. L.G. Raskin and I.O. Kirichenko, Multi-index problems of linear programming. M.: Ra-
dio and communication, 1982, 240 p.
12. J.B. Orlin, “A Faster strongly polynomial minimum cost flow algorithm,” Operations
research, vol. 41, iss. 2, pp. 338–350, 1993. doi: 10.1145/62212.62249.
On some methods for solving the problem of power distribution of data transmission …
Системні дослідження та інформаційні технології, 2022, № 4 99
13. Z. Lukac, D. Hunjet, and L. Neralic, “Solving the production-transportation problem in the
Petroleum Industry,” Revista Investigacion Operacional, vol. 29, iss. 1, pp. 63–70, 2008.
14. Е. Іvokhin, D. Аpanasenko, and V. Navrodskiy, “About production-transport problem
reduction to the two-level problem of discrete optimization and its application,” Вulletin
of Taras Shevchenko Nathional University of Kiev: Еkonomics, no. 3(198), pp. 48–53,
2018. doi: 10.17721/1728-2667.2018/198-3/6.
15. L.A. Zadeh, “Fuzzy sets,” Information and Control, vol. 8, pp. 338–353, 1965. doi:
10.1016/S0019-9958(65)90241-X.
16. R.E. Bellman and L.A. Zadeh, “Local and fuzzy logics,” Modern Uses of Multiple-
Valued Logics; edited by J.M. Dunn, G. Epstein, D. Reidel. Dordrecht-Holland, 1977,
pp. 103–165. doi: 10.1007/978-94-010-1161-7_6
17. D. Dubois, “Linear programming with fuzzy data,” Analysis of Fuzzy Information; J.C.
Bezdek (ed.). Boca Raton: CRC Press, 1987, vol. 3: Applications in Engineering and Sci-
ence, pp. 241–263.
18. Bablu Jana and Tapan Kumar Roy, “Multi-Objective Fuzzy Linear Programming and Its
Application in Transportation Model,” Tamsui Oxford Journal of Mathematical Sciences,
21(2), pp. 243–268, 2005.
19. H.J. Zimmermann, “Fuzzy programming and linear programming with several objective
functions,” Fuzzy Sets and System, no. 1, pp. 45–55, 1978. doi: 10.1016/0165-
0114(78)90031-3
20. D.B. Yudin and E.G. Golshtein, Linear programming. M.: Nauka, 1969, 424 p.
21. R.E. Bellman and L.A. Zadeh, “Decision making in a fuzzy environment,” Management
Science, no. 17, pp. 141–164, 1970. doi: 10.1287/mnsc.17.4.B141.
22. O.F. Voloshin and S.O. Mashchenko, Models and methods for decision making. K.:
“Kiev University”, 2010, 336 p.
23. D. Watson, A Practical Approach to Compiler Construction. Springer, 2017, 254 p.
Received 02.05.2022
INFORMATION ON THE ARTICLE
Eugene V. Ivokhin, ORCID: 0000-0002-5826-7408, Taras Shevchenko National
University of Kyiv, Ukraine, e-mail: ivohin@univ.kiev.ua
Larisa T. Adzhubey, ORCID: 0000-0002-8103-9657, Taras Shevchenko National
University of Kyiv, Ukraine, e-mail: adzhubey@ukr.net
Petro R. Vavryk, ORCID: 0000-0003-4989-7544, Taras Shevchenko National University
of Kyiv, Ukraine, e-mail: petro.vavryk@knu.ua
Mykhailo F. Makhno, ORCID: 0000-0001-9694-2200, Taras Shevchenko National
University of Kyiv, Ukraine, e-mail: makhnom@gmail.com
ПРО ДЕЯКІ МЕТОДИ РОЗВ’ЯЗАННЯ ЗАДАЧІ РОЗПОДІЛУ ПОТУЖНОСТІ
КАНАЛІВ ПЕРЕДАВАННЯ ДАНИХ З УРАХУВАННЯМ НЕЧІТКИХ
ОБМЕЖЕНЬ НА ОБСЯГИ СПОЖИВАННЯ / Є.В. Івохін, Л.T. Aджубей,
П.Р. Ваврик, M.Ф. Maхнo
Анотація. Розглянуто математичну постановку задачі оптимального розподілу
потужностей каналів передавання даних в інформаційно-комп’ютерних мере-
жах з трирівневою архітектурою та нечіткими обмеженнями на обсяги спожи-
вання. Розроблено ефективний алгоритм розв’язання задачі, особливістю якої
є неможливість забезпечувати запити кінцевого споживача за рахунок ресурсів
різних постачальників. Розглянуто стандартний метод розв’язання на основі
нечіткої оптимізаційної задачі математичного програмування. Запропоновано
конструктивний варіант пошуку розв’язку на основі методу з поверненням.
Проведено обчислювані експерименти. Розроблено підхід, використаний для
визначення оптимальної конфігурації трирівневої інформаційно-комп’ютерної
мережі із заданою кількістю комунікаційних серверів.
Kлючові слова: передавання даних, розподіл потужності, нечіткі обмеження,
оптимальний розв’язок, алгоритм з поверненням.
|
| id | journaliasakpiua-article-254733 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | English |
| last_indexed | 2025-07-17T10:27:47Z |
| publishDate | 2022 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/8e/11080ba4d9778e6bf906b64fa839138e.pdf |
| spelling | journaliasakpiua-article-2547332023-05-21T20:04:38Z On some methods for solving the problem of power distribution of data transmission channels taking into account fuzzy constraints on consumption volumes О НЕКОТОРЫХ МЕТОДАХ РЕШЕНИЯ ЗАДАЧИ РАСПРЕДЕЛЕНИЯ МОЩНОСТИ КАНАЛОВ ПЕРЕДАЧИ ДАННЫХ С УЧЕТОМ НЕЧЕТКИХ ОГРАНИЧЕНИЙ НА ОБЪЕМЫ ПОТРЕБЛЕНИЯ Про деякі методи розв’язання задачі розподілу потужності каналів передавання даних з урахуванням нечітких обмежень на обсяги споживання Ivokhin, Eugene Adzhubey, Larisa Vavryk, Petro Makhno, Mykhailo data transfer power distribution fuzzy constraints optimal solution backtracking algorithm передавання даних розподіл потужності нечіткі обмеження оптимальний розв’язок алгоритм з поверненням The article deals with the mathematical formulation of the problem of optimal distribution of the power of data transmission channels in information and computer networks with a three-level architecture and fuzzy restrictions on consumption volumes. An efficient algorithm has been developed for solving the problem, the peculiarity of which is the inability to meet the end user’s needs at the expense of the resources of different suppliers. A standard solution method based on a fuzzy optimization problem of mathematical programming is considered. A constructive variant of finding a solution based on the backtracking method is proposed. Computational experiments have been carried out. The developed approach was used to determine the optimal configuration of a three-level information and computer network with a given number of communication servers. В статье рассматривается математическая постановка задачи оптимального распределения мощности каналов передачи данных в информационно-компьютерных сетях с трехуровневой архитектурой и нечеткими ограничениями на объемы потребления. Разработан эффективный алгоритм для решения задачи, особенностью которой является отсутствие возможности для обеспечения запросов конечного потребителя за счет ресурсов разных поставщиков. Рассмотрен стандартный метод решения на основе нечеткой оптимизационной задачи математического программирования. Предложен конструктивный вариант поиска решения на основе метода з возвратом. Проведены вычислительные эксперименты. Разработанный подход использовался для определения оптимальной конфигурации трехуровневой информационно-компьютерной сети с заданным количеством коммуникационных серверов.  Розглянуто математичну постановку задачі оптимального розподілу потужностей каналів передавання даних в інформаційно-комп’ютерних мережах з трирівневою архітектурою та нечіткими обмеженнями на обсяги споживання. Розроблено ефективний алгоритм розв’язання задачі, особливістю якої є неможливість забезпечувати запити кінцевого споживача за рахунок ресурсів різних постачальників. Розглянуто стандартний метод розв’язання на основі нечіткої оптимізаційної задачі математичного програмування. Запропоновано конструктивний варіант пошуку розв’язку на основі методу з поверненням. Проведено обчислювані експерименти. Розроблено підхід, використаний для визначення оптимальної конфігурації трирівневої інформаційно-комп’ютерної мережі із заданою кількістю комунікаційних серверів. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2022-12-27 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/254733 10.20535/SRIT.2308-8893.2022.4.08 System research and information technologies; No. 4 (2022); 88-99 Системные исследования и информационные технологии; № 4 (2022); 88-99 Системні дослідження та інформаційні технології; № 4 (2022); 88-99 2308-8893 1681-6048 en https://journal.iasa.kpi.ua/article/view/254733/270321 |
| spellingShingle | передавання даних розподіл потужності нечіткі обмеження оптимальний розв’язок алгоритм з поверненням Ivokhin, Eugene Adzhubey, Larisa Vavryk, Petro Makhno, Mykhailo Про деякі методи розв’язання задачі розподілу потужності каналів передавання даних з урахуванням нечітких обмежень на обсяги споживання |
| title | Про деякі методи розв’язання задачі розподілу потужності каналів передавання даних з урахуванням нечітких обмежень на обсяги споживання |
| title_alt | On some methods for solving the problem of power distribution of data transmission channels taking into account fuzzy constraints on consumption volumes О НЕКОТОРЫХ МЕТОДАХ РЕШЕНИЯ ЗАДАЧИ РАСПРЕДЕЛЕНИЯ МОЩНОСТИ КАНАЛОВ ПЕРЕДАЧИ ДАННЫХ С УЧЕТОМ НЕЧЕТКИХ ОГРАНИЧЕНИЙ НА ОБЪЕМЫ ПОТРЕБЛЕНИЯ |
| title_full | Про деякі методи розв’язання задачі розподілу потужності каналів передавання даних з урахуванням нечітких обмежень на обсяги споживання |
| title_fullStr | Про деякі методи розв’язання задачі розподілу потужності каналів передавання даних з урахуванням нечітких обмежень на обсяги споживання |
| title_full_unstemmed | Про деякі методи розв’язання задачі розподілу потужності каналів передавання даних з урахуванням нечітких обмежень на обсяги споживання |
| title_short | Про деякі методи розв’язання задачі розподілу потужності каналів передавання даних з урахуванням нечітких обмежень на обсяги споживання |
| title_sort | про деякі методи розв’язання задачі розподілу потужності каналів передавання даних з урахуванням нечітких обмежень на обсяги споживання |
| topic | передавання даних розподіл потужності нечіткі обмеження оптимальний розв’язок алгоритм з поверненням |
| topic_facet | data transfer power distribution fuzzy constraints optimal solution backtracking algorithm передавання даних розподіл потужності нечіткі обмеження оптимальний розв’язок алгоритм з поверненням |
| url | https://journal.iasa.kpi.ua/article/view/254733 |
| work_keys_str_mv | AT ivokhineugene onsomemethodsforsolvingtheproblemofpowerdistributionofdatatransmissionchannelstakingintoaccountfuzzyconstraintsonconsumptionvolumes AT adzhubeylarisa onsomemethodsforsolvingtheproblemofpowerdistributionofdatatransmissionchannelstakingintoaccountfuzzyconstraintsonconsumptionvolumes AT vavrykpetro onsomemethodsforsolvingtheproblemofpowerdistributionofdatatransmissionchannelstakingintoaccountfuzzyconstraintsonconsumptionvolumes AT makhnomykhailo onsomemethodsforsolvingtheproblemofpowerdistributionofdatatransmissionchannelstakingintoaccountfuzzyconstraintsonconsumptionvolumes AT ivokhineugene onekotoryhmetodahrešeniâzadačiraspredeleniâmoŝnostikanalovperedačidannyhsučetomnečetkihograničenijnaobʺemypotrebleniâ AT adzhubeylarisa onekotoryhmetodahrešeniâzadačiraspredeleniâmoŝnostikanalovperedačidannyhsučetomnečetkihograničenijnaobʺemypotrebleniâ AT vavrykpetro onekotoryhmetodahrešeniâzadačiraspredeleniâmoŝnostikanalovperedačidannyhsučetomnečetkihograničenijnaobʺemypotrebleniâ AT makhnomykhailo onekotoryhmetodahrešeniâzadačiraspredeleniâmoŝnostikanalovperedačidannyhsučetomnečetkihograničenijnaobʺemypotrebleniâ AT ivokhineugene prodeâkímetodirozvâzannâzadačírozpodílupotužnostíkanalívperedavannâdanihzurahuvannâmnečítkihobmeženʹnaobsâgispoživannâ AT adzhubeylarisa prodeâkímetodirozvâzannâzadačírozpodílupotužnostíkanalívperedavannâdanihzurahuvannâmnečítkihobmeženʹnaobsâgispoživannâ AT vavrykpetro prodeâkímetodirozvâzannâzadačírozpodílupotužnostíkanalívperedavannâdanihzurahuvannâmnečítkihobmeženʹnaobsâgispoživannâ AT makhnomykhailo prodeâkímetodirozvâzannâzadačírozpodílupotužnostíkanalívperedavannâdanihzurahuvannâmnečítkihobmeženʹnaobsâgispoživannâ |