=Paper=
{{Paper
|id=Vol-2064/paper03
|storemode=property
|title=
Mean-field approximation for large-scale queueing systems with a small parameter
|pdfUrl=https://ceur-ws.org/Vol-2064/paper03.pdf
|volume=Vol-2064
|authors=Sergey Vasilyev,Galina Tsareva
}}
==
Mean-field approximation for large-scale queueing systems with a small parameter
==
https://ceur-ws.org/Vol-2064/paper03.pdf
УДК 517.937, 517.928.2, 519.217.2
Васильев С.А., Царева Г.О.
Российский университет дружбы народов, г. Москва, Россия
ИСПОЛЬЗОВАНИЕ ПРИБЛИЖЕНИЯ СРЕДНЕГО ПОЛЯ ДЛЯ АНАЛИЗА
КРУПНОМАСШТАБНЫХ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ С МАЛЫМ
ПАРАМЕТРОМ*
Аннотация
В данной статье рассматривается система массового обслуживания, которая состоит из
бесконечного числа идентичных серверов FCFS с буфером, который способен хранить очередь
бесконечной длины, и с пуассоновским входящим потоком заявок в систему массового
обслуживания с интенсивностью N . Каждый запрос, поступающий в систему массового
обслуживания, случайным образом выбирает и опрашивает два произвольных сервера этой
системы, а затем мгновенно отправляется на один из них, где более короткая очередь.
Динамика изменения доли серверов в системе uk (t ) , имеющих длину очередей не менее k ,
можно описать с помощью бесконечной системы дифференциальных уравнений. Для этой
бесконечной системы дифференциальных уравнений поставлена задача Коши тихоновского
типа с начальными условиями и малым параметром, который присутствует перед
производными, начиная с уравнения, описывающего функцию uk (t ) . Наличие малого
параметра в бесконечной системе дифференциальных уравнений позволяет описывать
быстроизменяющиеся процессы в крупномасштабных системах массового обслуживания,
что дает возможность анализировать переходные процессы в системах такого типа. Для
рассматриваемой сингулярно возмущенной задачи Коши тихоновского типа с начальными
условиями и малым параметром доказана теорема существования.
Ключевые слова
Аналитические методы в теории массового обслуживания; системы дифференциальных
уравнений бесконечного порядка; малый параметр; счетные цепи Маркова;
крупномасштабные системы массового обслуживания; метод Добрушина; приближение
среднего поля.
Tsareva G.O., Vasilyev S.A.
Peoples' Friendship University of Russia, Moscow, Russia
MEAN-FIELD APPROXIMATION FOR LARGE-SCALE QUEUEING SYSTEMS WITH A SMALL
PARAMETER
Abstract
In this paper it is considered the queueing system, consisting of an infinite number of identical servers
with FCFS buffer, which can store a queue of infinite length, with Poisson input flow of requests in a
queueing system with intensity N . Every request entering the queuing system, randomly selects and
uses any of two servers of the system, and then is instantly sent to one of them, where a shorter queue.
A share dynamics uk (t ) of servers in the system having the queue length is not less than k can be
described by infinite system of differential equations. It is possible to formulate Tikhonov type Cauchy
problem with initial conditions and small parameter for this infinite system of differential equations.
A small parameter in the infinite system of differential equations allows describing rapidly changing
processes in large-scale queueing systems. The existence theorem is proved for the considered
singularly perturbed Tikhon type Cauchy problem with initial conditions and small parameter.
* Труды II Международной научной конференции «Конвергентные когнитивно-
информационные технологии» (Convergent’2017), Москва, 24-26 ноября, 2017
Proceedings of the II International scientific conference "Convergent cognitive information
technologies" (Convergent’2017), Moscow, Russia, November 24-26, 2017
19
Keywords
Analytical methods in queueing theory; systems of differential equations of infinite order; small
parameter; countable Markov chains; large-scale queueing systems; Dobrushin mean-field
approximation.
Introduction
The recent research of queueing systems with complex routing discipline in [16], [25], [26], [27] transport
networks [1], [7], [8] and the asymptotic behavior of Jackson networks [21] faced with the problem of proving the
global convergence of the solutions of certain infinite queueing systems of ordinary differential equations to a
time-independent solution. Scattered results of these studies, however, allow a common approach to their
justification. This approach will be expounded here. In work [17] the countable systems of differential equations
with bounded Jacobi operators are studied and the sufficient conditions of global stability and global asymptotic
stability are obtained. In [15] it was considered finite closed Jackson networks with N first come, first serve nodes
and M customers. In the limit M , N , M / N > 0 , it was got conditions when mean queue lengths
are uniformly bounded and when there exists a node where the mean queue length tends to under the above
limit (condensation phenomena, traffic jams), in terms of the limit distribution of the relative utilizations of the
nodes. It was deriven asymptotics of the partition function and of correlation functions. In papers [5], [11], [20]
the authors built various models of large-scale queueing systems and considered their dynamics.
Cauchy problems for the systems of ordinary differential equations of infinite order was investigated
A.N.Tihonov [22], K.P.Persidsky [18], O.A.Zhautykov [28-29], Ju.Korobeinik [10], A.M.Samoilenko, Yu.V.Teplinskii
[19] other researchers. For example, Markus Kreer, Aye Kzlers and Anthony W. Thomas [13] investigated
fractional Poisson processes, a rapidly growing area of non-Markovian stochastic processes, that are useful in
statistics to describe data from counting processes when waiting times are not exponentially distributed. They
showed that the fractional Kolmogorov-Feller equations for the probabilities at time t could be represented by an
infinite linear system of ordinary differential equations of first order in a transformed time variable. These new
equations resemble a linear version of the discrete coagulation fragmentation equations, well-known from the
non-equilibrium theory of gelation, cluster-dynamics and phase transitions in physics and chemistry.
It was studied the singular perturbed systems of ordinary differential equations by A.N. Tihonov [23],
A.B.Vasil'eva [24], S.A. Lomov [14] other researchers.
In paper [2] we investigated the singular perturbed systems of ordinary differential equations of infinite order
of Tikhonov-type x = F ( x(t , g x ), y (t , g y ), t ) , y = f ( x(t , g x ), y (t , g y ), t ) with the initial conditions x(t0 ) = g x ,
y (t0 ) = g y , where x, g x X , X l1 and y , g y Y , Y R n , t t0 , t1 ( t0 < t1 ), t0 , t1 T , T R , g x and g y are
given vectors, > 0 is a small real parameter.
In this paper we apply Dobrushin mean-field approaches from [26] for the singular perturbed systems of
ordinary differential equations of infinite order of Tikhonov type. We considered a system that consists of infinite
number of servers with a Poisson input flow of requests of intensity N . Each request arriving to the system
randomly selects two servers and is instantly sent to the one with the shorter queue. In this case a share uk (t ) of
the servers that have the queues lengths with not less than k can be described using an infinite system of
differential equations. It is possible to investigate Tikhonov type Cauchy problem for this system with small
parameter and initial conditions. It is studying the singular perturbed Tikhonov systems of ordinary differential
equations of infinite order u = f (u(t , gu ),U (t , gU ), t ) , U = F (u (t , gu ), U (t , gU ), t ) with the initial conditions
u(0, gu ) = gu , U (0, gU ) = gU , where u, f X , X Rn are n -dimensional functions; U , F Y , Y l1 are infinite-
dimensional functions and t 0, T0 ( 0 < T0 ), t T , T R ; gu X and gU Y are given vectors, > 0 is a
small real parameter. The evolution analysis of uk (t ) (k = 1, 2, ) be applied to application in large-scale queueing
systems.
Large-scale queueing systems model
The basic model considered there is a queueing system S N , with N identical infinite-buffer FCFS (First-Come,
First-Served) single-servers, with a Poisson arrival flow of rate N and with i.i.d. exponential service times of
mean 1/ , where 0 < < . Upon its arrival each task chooses m servers at random (i.e., independently of the
pre-history of the queueing system (QS) and with probability 1/ ( N ) ) and then selects, among the chosen ones,
m
the server with the lowest queue-size, i.e., the lowest number of tasks in the buffer (including the task in service).
If there happen to be more than one server with lowest queue-size, the task selects one of them randomly.
One is interested in the 'typical' behavior of a server in S N , as N . Formally, it means that t 0 and
20
k = 0,1, , we consider the fraction qk (t ) = M k (t ) / N where M k (t ) is the random number of servers with the
queue-size k at time t . Clearly, 0 qk (t ) 1 , kqk (t ) = 1 ; and Q(t ) = (qk (t )),t 0 , forms a Markov process (MP).
Technically, it is more convenient to pass to the tail probabilities rk (t ) = j kQk (t ) ; the state space of the
corresponding MP U N (t ) = ( fk (t )), t 0 , is the set U N of non-increasing non-negative sequences
u = (uk , k = 0,1, ) with u0 = 1 , k >1uk < and with the uk 's multiple of 1/ N , which implies that uk = 0 for all
k large enough. It is convenient to prolong the sequences u U N to the negative k 's by the value 1 .
The generator of U N (t ) is an operator A acting on functions f : U N C1 and given by
e
AN f (u ) = N uk uk 1 f u k f (u ) (1)
k >0 N
e
N (uk 1 )2 (uk ) 2 f u k f (u ) .
k >0 N
Here, ek stands for the sequence with the k -th entry 1 and all others 0 , the addition of the sequences is
componentwise. Process U N (t ) is positive-recurrent and thus possess a unique invariant distribution, N ;
given any initial distribution , the distribution of U N (t ) approaches N as t . The main result of [25] is
that, as N , the expected value E rk (t ) converges to the value ak , where
N
( mk 1)/( m1)
ak = k 0. (2)
Pictorially speaking, it means that, as N , an 'average' server in the QS will have k or more tasks in the
buffer with probability ak .
It is interesting to compare S N with another queueing system L , where the arriving task chooses the server
completely randomly (i.e., independently of the pre-history and with probability 1/ N ). Clearly, L is equivalent
to an isolated M / M / queue with the arrival and service rates and , respectively, which justifies omitting
subscript N in this notation. More precisely, the average server in L will have k or more tasks in the buffer with
the geometrical probability
k
ak0 = k 1, (3)
independently of N , which is much larger than ak .
In fact, as was shown in [25], the whole process U N (t ) is asymptotically deterministic as N . More
precisely, let U denote the set of the non-increasing non-negative sequences u = (uk ,k Z ) with uk = 1 for k 0
and u < .Then, if the distribution of initial state U N (0) approaches a Dirac delta-measure
k 0 k
concentrated at a point g = g k U , the distribution of U N (t ) is concentrated in the limit at the trajectory
u(t ) = uk (t ),t 0 , giving the solution to the following system of differential equations
uk (t ) = uk 1 (t ) uk (t ) (uk 1 (t )) 2 (uk (t )) 2 , k 1,
u0 (t ) = 0, (4)
uk (0) = g k 0, k = 1, 2, ,t 0.
Point a = (ak ) (see (2)) is a (unique) fixed point for system (4) in U .
These results illustrate the essence of the mean-field approximation for QS S N . Equations (4) describe a 'self-
compatible' evolution of vector u (t ) , or, equivalently, of the probability distribution q(t ) = qk (t ) defined by
qk (t ) = uk (t ) uk 1 (t ) , t 0 , k = 0,1, As before, u (t ) is simply the sequence of the tail probabilities for q(t ) .
We will compare system (4) with the linear system
yk (t ) = yk 1 (t ) yk (t ) yk 1 (t ) yk (t ) , k 1, (5)
describing the evolution of the probability distribution q (t ) = (qk (t )), qk (t ) = yk (t ) yk 1 (t ) in a standard
0 0 0
M / M /1/ queue with the arrival and service rates and , respectively. The -terms in (4) and (5) are the
21
same; they correspond with the departure of the tasks and 'push' the probability mass in q(t ) and q (0) (t ) towards
k = 0 . On the other hand, the -terms (different in both SQ) correspond with the arrival of the tasks; these terms
shift the probability mass to larger k 's. The -term in (4) is smaller than the one in (5) when uk (t ) is small;
pictorially speaking, system (4) provides (for the same values of and ) more 'protection', for large k , against
the shift to the right, which may lead to an 'explosion', when the relation k >1uk (t ) < or k >1yk (t ) < may fail
as t . Because of this, the entries ak of sequence a (see (2)) giving the fixed point of (4) decrease 'super-
exponentially', in contrast with the exponential decay of the tail probabilities in the fixed point a 0 = (ak0 ) of (5).
Large-scale queueing systems model with a small parameter
Let's consider a system that consists of N servers with a Poisson input flow of requests of intensity N . Each
request arriving to the system randomly selects two servers and is instantly sent to the one with the shorter queue.
The service time is distributed exponentially with mean t = 1/ . Let uk (t ) be a share servers that have the queues
lengths with not less than k . It is possible to investigate the asymptotic distribution of the queue lengths as
N and < 1 [25]. The considered system of the servers is described by ergodic Markov chain. There is a
stationary probability distribution for the states of the system and if N the evolution of the values uk (t )
becomes deterministic and the Markov chain asymptotically converges to a dynamic system the evolution of which
is described by infinite system of differential-difference equations for which we can formulate the Cauchy problem
of such type
uk (t ) = uk 1 (t ) uk (t ) (uk 1 (t )) 2 (uk (t )) 2 ,
u0 (t ) = 0, (6)
uk (0) = g k 0, k = 1, 2, ,t 0.
where g = g k k =1 is a numerical sequence ( 1 = g1 g2 ,
) [25].
We can investigate infinite system of differential-difference equations with small parameter such form
uk (t ) = uk 1 (t ) uk (t ) (uk 1 (t )) 2 (uk (t )) 2 ,
k = 0,1, , n 1,
2
un (t ) = U n 1 (t ) un (t ) (un 1 (t )) (un (t )) ,
2
(7)
s
k U k (t ) = U k 1 (t ) U k (t ) (U k 1 (t )) 2 (U k (t )) 2 ,
k = n 1, n 1, ,
uk (0) = g k 0, k = 0,1, 2, ,
where > 0 is a small parameter that bring a singular perturbation to the system (6), which allows us to describe
the processes of rapid change of the systems, and s = sk k = n 1 ,( sk > 0) is a numerical sequence.
Using (7) we can write Tikhonov problems for systems of ordinary differential equations of infinite order with
a small parameter and initial conditions
u = f (u (t , , , gu ), U (t , , gU ), t ),
k U = F (U (t , , , gU ), t );
s
(8)
u (0, , , g ) = g ,U (0, , , g ) = g ,
u u U U
where u, f X , X Rn are n-dimensional functions; U , F Y , Y l1 are infinite-dimensional functions and
t 0, T0 ( 0 < T0 ), t T , T R ; gu X and gU Y are given vectors ( gu = g k k =0 , gU = g k k = n 1 ) , > 0
n
is a small real parameter; u (t , gu ) = gu = uk k =0 and U (t , gU ) = uk k = n 1 are solutions of (8). Given functions
n
f (u(t , , , gu ),U (t , , , gU ), t ) and F (U (t , , , gU ), t ) are continuous functions for all variables
22
f k (u (t , , , gu ), t ) = uk 1 (t ) uk (t )
(uk 1 (t )) 2 (uk (t )) 2 , k = 0,1, , n 1,
f n (u (t , , , gu ), U (t , , , gU ), t ) = U n 1 (t ) un (t )
(9)
(un 1 (t )) 2 (un (t )) 2 ,
Fk (U (t , , , gU ), t ) = U k 1 (t ) U k (t )
(U k 1 (t )) 2 (U k (t )) 2 , k = n 1, n 1,
Let S is an integral manifold of the system (8) in X Y T . If any point t * 0, T0 (u (t * ),U (t * ), t * ) S of
trajectory of this system has at least one common point on S this trajectory (u(t , G),U (t, g ), t ) S belongs the
integral manifold S totally.
If we assume in (8) that = 0 than we have a degenerate system of the ordinary differential equations and a
problem of singular perturbations
u = f (u (t , , , g u ),U (t ), t ),
0 = F (u (t , , gu ), U (t , , ), t ); (10)
u (0, , gu ) = gu ,
where the dimension of this system is less than the dimension of the system (8), since the relations
F (u(t , ),U (t , ), , t ) = 0 in the system (10) are the algebraic equations (not differential equations). Thus for the
system (9) we can use limited number of the initial conditions then for system (8). Most natural for this case we
can use the initial conditions u(0, , gu ) = gu for the system (10) and the initial conditions U (0, ,U y ) = gU
disregard otherwise we get the overdefined system. We can solve the system (10) if the equation
F (u(t , ),U (t , ), , t ) = 0 has roots. If it is possible to solve we can find a finite set or countable set of the roots
U q (t , , gu ) = uq (u (t , , gu ), t ) where q N . If the implicit function F (u(t , ),U (t , ), , t ) = 0 has not simple
structure we must investigate the question about the choice of roots. Hence we can use the roots
U q (t , , gu ) = uq (u (t , , gu ), t ) ( q N ) in (10) and solve the degenerate system
ud = f (ud (t , , gu ), uq (ud (t , , gu ), t ), , t );
(11)
U d (0, , gu ) = gu .
Since it is not assumed that the roots U q (t , , gu ) = uq (u (t , , gu ), , t ) satisfy the initial conditions of the Cauchy
problem (8) ( U q (0) gu , q N ), the solutions U (t , , gU ) (8) and U q (t , , gu ) do not close to each other at the
initial moments of time t > 0 . Also there is a very interesting question about behaviors of the solutions u(t , , gu )
of the singular perturbed problem (8) and the solutions ud (t , , gu ) of the degenerate problem (10). When t = 0
we have u(0, , gu ) = ud (0, , gu ) . Do these solutions close to each other when t 0, T0 ? The answer to this
question depends on using roots U q (t , , gu ) = uq (u (t , , gu ), t ) and the initial conditions, which we apply for the
systems (8) and (11).
Analysis of infinite order system of differential equations
We can rewrite Tikhonov problems (8) for systems of ordinary differential equations of infinite order with a
small parameter and initial conditions in the form
v = FR (v(t , , , , v ), t ),
0
(12)
v(0, , , , v0 ) = v ,
0
where
v = (u0 , u1 , , un ,U n1 ,U n 2 , ),
FRk = uk 1 (t ) uk (t ) (uk 1 (t ))2 (uk (t ))2 , k = 0,1, , n 1 ,
FRn = U n 1 (t ) un (t ) (un 1 (t )) (un (t ))
2 2
, (13)
U k 1 (t ) U k (t ) (U k 1 (t )) 2 (U k (t )) 2 , k = n 1, n 1,
s s
FRk = k k
,
0 0
v = ( gu , gU ); (v = g k ,k = 0,1, ) k
Using methods from [19], [28-19] we can consider Tikhonov-type problems (12)
23
v = FR (v0 , v1 , , vn , , , , , t ),
(14)
v(0, , , , v0 ) = v0 ,
Definition. A function FR v0 , v1 , , vn , , , , , t is called strongly continuous if for any 0 > 0 , there exist N 0
'
and 0 > 0 such that the inequality | v v |< 0 , i = 0,1, 2,
'
i i , N 0 , implies the estimate for any 0, 0, > 0
| FR v , v , '
0
'
1 , , FR v , v1' , , , , |< 0 .
'
0 (15)
Theorem. Assume that the right-hand sides of the system of equations (14)
• are defined for any vi ( , , , t ) R1 , i = 0,1, 2, , 0, 0, > 0 and all t T0 = 0, t R1 ;
• are strongly continuous in v0 , v1 , for fixed t T0 , 0 , 0 , > 0 and measurable in t T0 for fixed
vi (, , , t ), i = 0,1, 2, ;
• satisfy the inequalities
| FRi t , v0 , v1 , , , , |< M i (t ) (16)
for all i = 0,1, 2, , where M i (t ) are functions summable on the segment T0 and for any 0, 0, > 0 .
Then, for any vector v , v , with real coordinates, there exists at least one solution
0
0
0
1
v0 ( , , , t ), v1 ( , , , t ), of the system of equations (14) such that vi (0) = vi0 , i = 0,1, 2, .
Proof. We replace the system of equations (14) by the following system of integral equations:
t
vi (t ) = vi0 FRi t , v0 (t ), v1 (t ), , , , dt , i = 0,1, 2, , (17)
0
and consider a mapping ( A )
t
zi (t ) = vi0 FRi t , v0 (t ), v1 (t ), , , , dt , i = 0,1, 2, , (18)
0
which establishes a correspondence between an arbitrary countable system of continuous functions vi (t )i =0 and
another system of this sort zi (t )i =0 . Note that if FR (t , v0 ,
, vn , , , ) is a continuous function of finitely many
variables vi (t )i =0 measurable with respect to t for fixed vi , i = 0, n , then the function
n
(t ) = FR (t, 0 (t ), , n (t ), , , )
is measurable if i (t ), i = 0, n , are measurable.
Thus, the function
n (t ) = FR (t , 0 (t ), , n (t ),0,0, , , , )
is measurable and, therefore, the function
FR (t ,0 (t ),1 (t ), , , , ) = (t, , , )
is also measurable because
(t ) = lim n (t , , , ), (19)
n
which readily follows from the condition of strong continuity. The requirement of summability follows from
condition 3 of Theorem. We consider a system of functions vi (t )i =0 as a point P of an abstract space R . If there
exists a point P invariant under mapping ( A ) (18), then it specifies a solution of the system of equations (17)
and, hence, of system (14).
Consider a set M 0 formed by three points P for which vi (t )i =0 satisfy the conditions
t t
| vk (t ) vk0 | M k (t )dt , | vk (t ) vk (t ) | M k (t ) dt , k = 0,1, 2, .
0 t
It is easy to see that mapping ( A ) (18) maps the set M 0 into itself. We now introduce mapping ( B ) by putting
every point P in correspondence with a set of numbers
a00 an
, , 0 , ,
N0 N0
, (20)
24
a1n ann
, , , ,
nN n nN n
,
t
where N i = vi0 M i (t ) dt and the numbers anr ( an0 , , ann , ) are the coefficients of the Fourier expansion
n , r =0
0
of a function vn (t ) in a certain complete orthogonal system of functions on the segment T0 . By ordering the set of
numbers (20), we obtain a numerical sequence b0 , b1 , , bn , . Moreover, we have
2
t
t
t
a = vn (t ) dt vn0 M k (t )dt dt
2 2
k
n (21)
k =0 0 0 0
t
N n2 dt = aN n2 ,
0
whence it follows that
2
ank
1 a 2
i =0
b = i
2
0=1 k =0 nN n
a
n =0 n
2
=
6
. (22)
Thus, mapping ( B ) maps the set M 0 into a subset M 0* of the Hilbert space l2 . Therefore, mapping ( A )
induces a mapping ( A* ) of the set M 0* into itself. Further, if mapping ( A* ) has a fixed point P* M 0* , then the
corresponding point P* M 0 determines the solution of equation (17) and, hence, (14). To use the Schauder
theorem, it suffices to show that the set M 0* is compact and convex. If P* = (b0' , , bn' , ) and P* = (b0' , , bn' , )
are points from M 0* , then the point
P* P* = ( b0' b0' , b1' b1' , ), = 1, > 0, > 0, (23)
belongs to M 0* because it corresponds to the system of functions
v0' (t ) v0' (t ), v1' (t ) v1' (t ), . (24)
specifying a point from the set M 0 . Indeed,
t t
vk' (t ) vk' (t ) vk0 = (vk' (t ) vk0 ) (vk' (t ) vk0 ) ( ) M k (t )dt = M k (t ) dt , (25)
0 0
i.e., condition 1 is satisfied. Similarly, the inequality
t
vk' (t ' ) vk' (t ' ) vk' (t ' ) vk' (t ' ) ( ) M k (t )dt (26)
0
implies condition 2. Hence, the set M 0 is convex. In this set, we choose an arbitrary sequence of points Pi . This
* *
sequence corresponds to the sequence of points Pi v0 (t ), v1 (t ), (i ) (i )
in the set M . According to conditions 1 and
0
2, the sequence 0 , is uniformly bounded and equicontinuous and, consequently, it contains a
(i )
v (t ), i = 0,1, 2,
( ) ( ) ( )
subsequence v0 0 (t ), v0 1 (t ), ,v0
s
(t ), that converges uniformly in t T0 . However, the sequence
( )
v1
h
(t ), h , is also uniformly bounded and equicontinuous and, hence, it also contains a convergent
subsequence
( ) ( ) ( )
v1 0 (t ), v1 1 (t ), , v1 s (t ), . (27)
This process can be continued infinitely.
We compose the table
( ) ( ) ( )
v0 0 (t )v0 1 (t )v0 2 (t )
( ) ( ) ( )
v1 0 (t )v1 1 (t )v1 2 (t ) (28)
(
0
) (
1
) (
2
)
v2 (t )v 2 (t )v 2 (t )
and rewrite the set of sequences row by row
( ) ( ) ( )
v0 0 (t )v0 1 (t )v0 2 (t )
25
( ) ( ) ( )
v1 0 (t )v1 1 (t )v1 2 (t ) (29)
( ) ( ) ( )
0 1 2
v2 (t )v
2 (t )v
2 (t )
Each of these sequences converges as a subsequence of a convergent sequence supplemented by finitely many
elements. Thus, the sequence of points
P , P , P , M 0 (30)
0 1 2
converges weakly (coordinatewise) to a point P0 M 0 (uniformly in t T0 ). For the sake of convenience, we
rewrite sequence (30) as
P0 , P1 , P2 , , Pn , (31)
Let us show that the sequence of the corresponding points P0* , P1* , P2* , from the set M 0* converges to the
point P0* M 0* in the norm of the Hilbert space l2 . Indeed, the distance between the points P* and P* from M 0*
is given by the formula
t
P* , P* =
1
(bi' bi' )2 =
i =0
2 2 n
n =0 n N n 0
(v ' vn' ) 2 dt , (32)
whence it follows that
n t 1
P , P
0
1
0
*
k
*
n =0 n N
(v 0 vnk )2 dt t 2
2 2 n
n=n n
(33)
n 0 0
is arbitrarily small for sufficiently large n0 and k . This means that the set M 0* is compact. Note that one can easily
prove that mapping (B) is a homeomorphism, i.e., the sets M 0 and M 0* are topologically equivalent. Theorem is
proved.
Conclusions
We investigated the large-scale queueing system model that consists of infinite number of servers with a
Poisson input flow of requests of intensity N . We assume that each request arriving to the system randomly
selects two servers and is instantly sent to the one with the shorter queue. The service time is distributed
exponentially with mean 1/ . In this case a share uk (t ) of the servers that have the queues lengths with not less
than k can be described using an infinite system of differential equations. Tikhonov type Cauchy problem for this
system with small parameter is investigated. The theorems of existence of solutions for this Cauchy problem is
proved with taking into account parameters , , .
Acknowledments
The publication was prepared with the support of the “RUDN University Program 5-100” and partially funded
by RFBF grants № 15-07-08795, № 16-07-00556.
References
1. Sukhomlin V.A. Mezhdunarodnye obrazovatel'nye standarty v oblasti informatsionnykh tekhnologiy // Prikladnaya informatika. — 2012.
— № 1(37), — S. 33-54.
2. Sukhomlin V.A., Andropova E.V. Diversifikatsiya programm professional'noy podgotovki v mezhdunarodnykh obrazovatel'nykh
standartakh v oblasti informatsionnykh tekhnologiy // Vestnik Moskovskogo universiteta. Seriya 20. Pedagogicheskoe obrazovanie. —
2013. — № 1. — S. 73-87.
3. Sukhomlin V.A., Zubareva E.V. Kurrikulumnaya paradigma — metodicheskaya osnova sovremennogo obrazovaniya // Sovremennye
informatsionnye tekhnologii i IT-obrazovanie. — 2015. — T. 1, № 11. — S. 54-61.
4. Afanassieva L.G., Fayolle G., Popov S. Yu. Models for Transportation Networks // J. Math. Science. — 1997. — Vol.84, Issue 3. — P. 1092-
1103.
5. Bolotova G.O., Vasilyev S.A., Udin D.N. Systems of Differential Equations of Infinite Order with Small Parameter and Countable Markov
Chains // Distributed Computer and Communication Networks – 19th International Conference, DCCN 2016 Communications in
Computer and Information Science. (Moscow, November 21-25, 2016). — Vol. 678. Publisher: Springer Verlag, 2016. — P. 565-576.
6. McDonald D.R., Reynier J. A mean-field model for multiple TCP connections through a buffer implementing RED // Performance Evaluation.
— 2002. — Vol. 49, Issues 14. — P. 77-97.
7. Daletsky Y.L., Krein M.G. Stability of solutions of differential equations in Banach space. — Moscow, Science Pub.,1970.
8. Gaidamaka Y., Sopin E., Talanova M. Approach to the analysis of probability measures of cloud computing systems with dynamic scaling
// Communications in Computer and Information Science. — 2016. — Vol. 601. — P. 121-131.
9. Henry D. Geometric theory of semilinear parabolic equations // Lecture Notes in Mathematics. — Berlin, Springer-Verlag, 1981.
10. Khmelev D. V., Oseledets V.I. Mean-field approximation for stochastic transportation network and stability of dynamical system. —
Preprint № 434 of University of Bremen, 1999.
11. Khmelev D. V. Limit theorems for nonsymmetric transportation networks // Fundamentalnaya i Priklladnaya Matematika. — 2001. —
26
Vol. 7, № 4. — P. 1259-1266.
12. Kirstein B. M., Franken D. E., Stoian D. Comparability and monotonicity of Markov processes // Theory of probability and its applications.
— 1977. — Vol. 22, Issue 1. — P. 43-54.
13. Korobeinik Ju. Differential equations of infinite order and infinite systems of differential equations // Izv. Akad. Nauk SSSR Ser. Mat. —
1970. — Vol. 34. — P. 881- 922.
14. Korolkova A.V., Eferina E.G., Laneev E.B., Gudkova I.A., Sevastianov L.A., Kulyabov D.S. Stochastization of one-step processes in the
occupations number representation // Proceedings – 30th European Conference on Modelling and Simulation, ECMS 2016 (Regensburg,
Germany, May 31- June 3, 2016). — European Council for Modeling and Simulation, 2016. — P. 565-576.
15. Krasnoselsky M.A., Zabreyko P.P. Geometrical methods of nonlinear analysis. — Berlin, Springer-Verlag, 1984.
16. Kreer M., Klersu Ayseand, Anthony W. Thomas Fractional Poisson processes and their representation by infinite systems of ordinary
differential equations // Statistics and Probability Letters. — 2014. — Vol. 84. — P. 27-32.
17. Lomov S. A. The construction of asymptotic solutions of certain problems with parameters // Izv. Akad. Nauk SSSR Ser. Mat. — 1968. —
Vol. 32. — P. 884-913.
18. Malyshev V. and Yakovlev A. Condensation in large closed Jackson networks // Ann. Appl. Probab. — 1996. — Vol. 6, № 1. — pp. 92-115.
19. Mitzenmacher M. The Power of Two Choices in Randomized Load Balancing // PhD thesis, University of California at Berkley, 1996.
20. Oseledets V. I., Khmelev D. V. Global stability of infinite systems of nonlinear differential equations, and nonhomogeneous c ountable
Markov chains // Problemy Peredachi Informatsii (Russian). — 2000. — Vol. 36, Issue 1. — P. 60-76.
21. Persidsky K.P. Izv. AN KazSSR, Ser. Mat. Mach. — 1946. — Issue 2. — P. 3-34.
22. Samoilenko A. M., Teplinskii Yu. V. Countable Systems of Dierential Equations. — Utrecht, Springer, 2003.
23. Samouylov K., Naumov V., Sopin E., Gudkova I., Shorgin S. Sojourn time analysis for processor sharing loss system with unreliable server
// Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics).
— 2016. — Vol. 9845. — P. 284-297.
24. Scherbakov V.V. Time scales hierarchy in large closed Jackson networks // Preprint No. 4. Moscow: French-Russian A.M. Liapunov
Institute of Moscow State University, 1997.
25. Tihonov A. N. Uber unendliche Systeme von Differentialgleichungen // Rec. Math. — 1934. — Vol. 41, Issue 4. — P. 551-555.
26. Tihonov A. N. Systems of differential equations containing small parameters in the derivatives // Mat. Sbornik N. S. — 1952. — Vol. 31,
Issue 73. — P. 575-586.
27. Vasil'eva A. B. Asymptotic behaviour of solutions of certain problems for ordinary non-linear differential equations with a small parameter
multiplying the highest derivatives // Uspehi Mat. Nauk. — 1963. — Vol. 18, Issie 111, №. 3. — P. 15-86.
28. Vvedenskaya N.D., Dobrushin R.L., Kharpelevich F.I. Queueing system with a choice of the lesser of two queues — the asymptotic
approach // Probl. inform. — 1996. — Vol. 32, Issue 1. — P.15-27.
29. Vvedenskaya N.D., Suhov Yu.M. Dobrushin's Mean-Field Approximation for a Queue with Dynamic Routing // Markov Processes and
Related Fields. — 1997. — Issue 3. — P. 493-526.
30. Vvedenskaya N.D. A large queueing system with message transmission along several routes // Problemy Peredachi Informatsii. — 1998.
— Vol. 34, № 2. — P. 98-108.
31. Zhautykov O. A. On a countable system of differential equations with variable parameters // Mat. Sb. (N.S.). — 1959. — Vol. 49, Issue 91.
— P. 317-330.
32. Zhautykov O. A. Extension of the Hamilton-Jacobi theorems to an infinite canonical system of equations // Mat. Sb. (N.S.). — 1961. — Vol.
53, Issue 95. — P. 313-328.
Об авторах:
Васильев Сергей Анатольевич, кандидат физико-математических наук, доцент кафедры прикладной
информатики и теории вероятностей, Российский университет дружбы народов,
svasilyev@sci.pfu.edu.ru
Царева Галина Олеговна, аспирантка кафедры прикладной информатики и теории вероятностей,
Российский университет дружбы народов, gotsareva@gmail.com
Note on the authors:
Vasilyev Sergey А., Candidate of Physico-mathematical Sciences, Associate Professor, Department of Applied
Probability and Informatics, Peoples' Friendship University of Russia, svasilyev@sci.pfu.edu.ru
Tsareva Galina О., Postgraduate Student, Department of Applied Probability and Informatics, Peoples' Friendship
University of Russia, gotsareva@gmail.com
27