The study is devoted to one of the tasks related to information and computer systems with a different discipline of establishing connections between its nodes. Cases of systems with and without queues are considered. The efficiency of the systems (the relative load, the number of busy nodes, etc.) is calculated. To calculate the probability of the communication system being in one of the possible enlarged states, the corresponding Markov process is introduced and its asymptotic characteristics are determined.
Here deserve attention such characteristics as the distribution of the number of simultaneously established connections and the number of waiting in the queue, the distribution of the waiting time for the customer to provide him with the required connection, and in case of limitation on the queue length, also the probability of request’s loss.
There are N customers; all of them can request for the communication with any (but only one) of N-1 other customers. If the i-th customer has made a request for communication with the j-th customer, then the communication between them begins immediately if the j-th customer is free, otherwise the ith customer is put on the waiting list (waiting line) of j-th customer and waiting for his request to be satisfied in a fair (sequential) order. If the customer has made a request for the communication, then the probability that this is a request for a communication with a specific customer is equal to 1/(N-1). The queue length for each customer is unlimited (it is enough to set the number of places in the queue equal to N-2). The duration of the communication session between any two customers is exponentially distributed with the parameter µ.
The event that any free customer will not make a request for the communication with any other customer during time τ has a probability of exp(-λτ), λ>0. It is required to determine the parameters characterizing the number of simultaneous communications and the number of busy customers depending on the total number of system customers, the intensity of generation and the duration of the service of incoming connection requests. Due to the lack of accurate analytical formulas describing the parameters of this kind of communication systems, in practice, researchers often resort to methods of numerical or simulation modeling [8]. In our case, to study the described class of communication systems, it is proposed to use a probabilistic software approach based on the analysis of their enlarged states.
The state of the system at an arbitrary point of time will be characterized by the vector α=(α1, α2,…, αk,αm), m = [N/2], where [x] = entire (x); αk – the number of busy customers at time t, «belonging» to k-th communication (that includes customers who are in the process of the k-th communication and those who are in line with above customers). It is assumed that N≥α1≥…≥αm≥ 0 (so, communications are ordered by the number of customers they own). The random process introduced by the above method is Markovian with the transition probability matrix determined from the relations: P{(α 1,α 2 ,…,α k ,α m )t+Δt /(β 1, β 2 ,…, β m )t } = 1−λγ (β )Δt − μω (β )Δt, if α k = β k (k = 1, m); (1.1) λβ iγ (βN)ξ−1i(β )Δt , if α k = β k (k = 1,..., i −1, i +1,..., m), (1.2) α i = β i +1, 2 ≤ β i ≤ N −1 λ (γ (β ) −1)γ (β )Δt
, if α k = β k (k = 1,..., i −1, i +1,..., m), α i = 2,β i = 0; (1.3) N −1 μξ i (β )(2 −δ (q,β i − q))Δt = β i −1 , (1.4) if the set of nonzero vector's coordinates (α 1,...,α m ) coincides with the set of nonzero components of the selection {β 1,...,β i−1,β i+1,...,β m , q,β i - q},β i ≤ 4, 2 ≤ q ≤ [β i /2]; 2μξ i (β )Δt , if α k = β k (k = 1,..., i −1, i +1,..., m),α i = β i −1,β i ≥ 3; (1.5) β i −1 μξ i (β )Δt, if α k = β k (k = 1,..., i −1,i +1,..., m), α i = 0,β i = 2; (1.6) 0, otherwise (1.7) The following notation is introduced here: δ (i, j) = –
Kronecker symbol; m m γ (β ) = (N − ∑β k ) – the total number of free customers; ω (β ) = (m − ∑δ (β k ,0)) – the total k =1 k=1
m number of current communications; ξ i (β ) = ∑δ (β i ,β k ) – the multiplicity of occurring of the k =1 component (numerically equal to βi) in the vector β = (β1,...,β m ).
The rationale of the elements (1.1)-(1.7) for the transition probability matrix is given below. The transition probability (1.1), i.e., the probability that the system remains in the same state for an infinitely small time interval ∆t, is 1,i = j 0, i ≠ j exp(−λγ (β )Δt) exp(−μωΔt) = 1 − λγ (β )Δt − μω (β )Δt + o(Δt).
Transition probability (1.2), that is, the probability that none of the communications ω(β) will be over during time ∆t, and one of the free customers will make a request for communication with one of the customers belonging to the i-th communication, is equal to exp(−μω (β )Δt) exp(−λ (γ (β ) −1)Δt)(1− exp(−λ Δt) × × γ (1β ) Nβ −i1 + o(Δt) = λβ iNγ(−β1)Δt + o(Δt).
The transition probability (1.3), that is, the probability that no communications will be completed during time ∆t and one of the free customers will make a request for communication with another free customer is exp(−μω (β )Δt) exp(−λ (γ (β ) − 1)Δt)(1 − exp(−λ Δt) × × γ (β ) γ (β ) − 1 = 1 N − 1 λ (γ (β ) − 1)γ (β )Δt
N − 1 + o(Δt).
The transition probability (1.4), that is, the probability that i-th communication will end within a period of time ∆t, and the end of this communication will immediately lead to the organization of two new ones (special cases when the end of a communication leads to the creation of only one new or a new communication does not form at all, are described by transitional probabilities (1.5) and (1.6), respectively).
To calculate the transition probability (1.4), we use the following technique. We assign each of customers βi to one of two subgroups – left or right (it depends on the line in which it stands – to the first or second customer doing i-th communication). Then the group of βi customers can be formed in (βi-1) different ways: (j,βi-j), j=1,…,βi -1. We prove by induction that all methods are equally probable, that is, the probability of each of them is equal to 1/(βi-1). So, let P(j,n-j) be the probability that a group of n customers belonging to one communication consists of j left and n-j right (j=1,…,n-1) customers. Let us note (this will be needed later) that P(n,0)=P(0,n)=0 for any n≥2. Now suppose that for some n and arbitrary j=1,…,n-1 probability P(j,n-j) is equal 1/(n-1). For n=2 the validity of the assumption is obvious. Then the group of (n+1) customers consisting of j left and (n+1-j) right could be constructed in two ways: either the last customer was added to (j-1) left, or to (n-j) right. Considering that all customers can be demanded with equal probability,
P( j, n +1− j) =
P( j −1, n +1− j)( j −1) n +
P( j, n − j)(n − j) n .
Since by assumption of induction P(j+1,n+1-j)=P(j,n-j)=1/(n-1), then, P(j,n+1-j)=1/n for any j=1,…,n. Thus, the validity of the induction hypothesis is proved for the arbitrary n.
In the transition probability formula (1.4), a factor (2-δ(q, βi -q)) requires some explanation: since in the group of βi customers the subgroups (q left, βi -q right) and (βi -q left, q right) do not differ, the corresponding probability should be doubled, except for the case q=βi –q.
Transitional probability (1.5) is, as already noted, a special case of transitional probability (1.4) with the only difference that the i-th communication that ends during interval ∆t has either a single left or a single right customer. In this case, instead of one ending, one new communication is formed.
Transitional probability (1.6) is the probability of termination of a communication between two customers of the system, where both customers had no queue. In this case, of course, a new communication does not form. Since the transition probabilities are independent of t, the introduced Markov process with a finite number of states is homogeneous and there are limit probabilities for it π (α1,...,α m ) = lim P(α1,...,α m )t ,
t→∞ being a solution to a system of equations [9] π (α1 ,...,α m )= ∑π (α1 ,...,α m )=1. (α1,...,αm )
∑π (β1 ,...,β m )P{(α1 ,...,α m )/ (β1 ,...,β m )},
(β1,...,βm )
(
The transition probabilities in (
N N Λ(N ) = ∑ s n, ,
n=0 2
where s(n, [N/2]) – the number of distinguishable locations of n balls in [N/2] boxes, and any box may
contain 0,2,3, ...,t balls, but it is forbidden to place one ball in the box. To estimate the complexity of
the system of algebraic equations (
N n Λ( N ) = 1 + ∑ + ∑ ∑ n=2 2 r =3 v1 =2 v2 =v1
n−v1 −...−vr−2 n n n−v1 n−v1 −...−vi−1 2 r r−1 r −(i −1) 2 ∑... ∑ ... ∑1 vi =vi−1 vr−1 =vr−2
The number of states of the system according to formula (
It should be noted that estimation of the number of system states in this task is equivalent to the
well-known problem of partition of the integer number N. Indeed, it can be easily verified if, in order
to obtain all possible enlarged states of the communication system described by the transition
probability matrix (
Generally speaking, the problem of decomposing the natural number N into natural terms was
formulated by Gottfried Leibniz as early as 1654, and the recurrence formula was obtained and proved
by Leonard Euler in 1740. Nevertheless, a closed analytical solution to this problem is unknown today.
Accordingly, the exact analytical formula for expression described by relation (
Calculations were made on modern computing systems based on Matlab using parallel computing
up to N=20, and for systems with N>20, the results were determined using extrapolation of the
obtained data. Since a proportional increase of the values λ and µ does not affect the final solution of
system (
Let us briefly consider the main ideas of the algorithm. After entering the data, the matrix is calculated IA(i,j), each line of which characterizes one of the possible states of the system. The structure of the string is shown in Figure 2.
Here NRCi – total number of active customers in this particular state (in communication and in line), KRCi – number of communications in this state, nij – the number of groups of customers related to one communication, each of which contains exactly j customers. Some redundancy of information (cells NRCi and KRCi) is used to increase the speed of the calculation. For the same purpose, the rows of the matrix IA are ordered in ascending NRCi order, and inside the rows with the same NRCi value – in ascending KRCi order.
Next, a pointer matrix IND (NRC, KRC) is created, it's elements are the minimum row numbers i,
for which IA(i,0)=NRC, IA(i,1)=KRC. To be precise, there are several such lines, but they are all
arranged sequentially, starting from i-th string. The construction of the matrix of infinitesimal
coefficients (
The calculation of stationary probabilities π(α1,…,αm) is completed by solving the system of linear
equations (
The state of the system in this case, in contrast to the situation described in paragraph 2, is completely determined by the number of ongoing communications ω. We denote by Pt(ω) the probability that the system is in state ω at time t. Then the following relations are valid:
To calculate the stationary probabilities π (ω ) = lt→im∞ Pt (ω ) , we have a system of linear algebraic equations: π (ω −1) +π (ω + 1)μ (ω + 1) = 0 [ N / 2] ∑π (k ) = 1 k =0
N − 2(ω − 1))(N − 2(ω −1) − 1)λ
N −1 −π (ω )(λ ( N − 2ω )
N − 2ω − 1
N −1
+ μω ) +
(ω = 0,1,...,[ N / 2])
(
In contrast to the system of equations (
Calculations on modern computer systems based on the classical parallel Thomas algorithm [12], allowed us to get results up to N = 10000. As well as for a system without restrictions on the length of the queues, the stationary probabilities π(ω) do not change with a proportional increase in the parameters µ and λ. Relative system load (this is, as already noted, the ratio of the average number of stationary communications to the [N/2] – maximum possible number of communications) almost doesn’t depend on N. This graph is presented in Figure 5.
A comparison of the two systems described in this paper shows that the operational efficiency (the number of communications per time unit) of the system where queues are prohibited (for the same values of N and µ/λ) is higher than the efficiency of the system with queues for µ/λ≤1, that is, when the communication sessions are long enough (the intensity λ is considered to be fixed). At large ratio µ/λ (µ/λ →∞), the efficiency of both systems naturally drops to zero, and at moderate ratio µ/λ, the systems with queues are somewhat more efficient.
As shown in this paper, with a certain correlation of the parameters of the system, queues are more efficient than systems in which queues are prohibited. Important factor here is average communication session length. If it is known in advance, then this information can be used to configure the parameters of the telecommunication system for its more efficient functioning. It should be noted that the systems discussed here can be proposed as a model of the functioning of a usual telephone network.
An interesting direction for further research is to take into account information (for example, statistics of past periods) about the average time of a communication session of each individual customer. It is also interesting to evaluate the effectiveness of using the “combined scheme”: queues are allowed for some customers and forbidden for others.
This work was supported in part by the Russian Foundation for Basic Research (project 19-01-00128), and Ministry of Science and Higher Education of the Russian Federation (project no. AAA-A17117052410034-6).