On the algorithmization of construction of the transition intensity matrix in systems with a large number of same elements

Full Text

1. Introduction Quite often, when constructing mathematical models of complex information and computing systems, developers are faced with the problem of the presence of a large number of similar elements in the system under study. This is especially true for multi-threaded systems or systems with a large number of servicing devices [1-7]. If the functioning of the system has a complex multivariate scenario, then the task of constructing a state space of a random process modeling the system under study becomes impossible without developing a special software product. In this article, using the example of a multi-channel queuing system with reordering of requests [8, 9], an algorithm will be developed for the automated construction of the state space and transition intensity matrix. 2. System description A multi-channel queuing system (QS) is considered with m service devices, 2 m < ∞ and a common storage device of limited capacity r. The system receives a Poisson flow of requests of intensity λ. The service times on device j are independent of each other, and also do not depend on the duration of service on other devices and are distributed according to an exponential law with the parameter µj , j = 1, . . . , m. An application entering the system when there are m + r applications in it is lost. We will further assume that the devices are arranged in non-decreasing order of service intensity: µ1 ?: · · · ?: µm and that a request that has the ability to select a device selects the device with the lowest serial number. The selection of applications from the storage occurs in accordance with the FIFO discipline [10]. It is assumed that all applications upon entry into the system are assigned a serial number. Moreover, if at the moment of completion of servicing of a request with number n (n-request), servicing of at least one request with a number less than n continues, the n-request is placed in the reordering buffer (RB). Otherwise, request n leaves the system and all requests with numbers differing by one, starting from n + 1 (if there are any in the RB), leave the RB behind it. This assumption allows us to model the mechanism for maintaining the order in which applications leave the system in accordance with the order in which they arrive. Systems of this kind are called systems with reordering of requests [8, 9]. 3. Construction of a mathematical model Let us assume that all applications in the system are numbered in accordance with the order in which they were received, starting with one. Then the stochastic behavior of the considered QS can be described by a homogeneous Markov process X(t), t ?: 0, over the state space xm = m+r k l xm, m xk = {(k, i1, . . . , im), ij = 0, k, k=0 m '\" u(ij ) = k, j=1 in this case, if ij is > 0, then ij /= is, j, s = 1, mr, k = 0, m - 1, m xk = {(k, i1, . . . , im), ij = 0, m, ij /= is, j, s = 1, mr, k = m, m + r, where u(x) is the Heaviside function. Here for some time t: X(t) = (k, i1, . . . , im), if there are k requests in the system, k = 0, . . . , m + r and device j is free if ij = 0. Otherwise, ij is the serial number of the request served on device j, j = 1, . . . , m. k In what follows, we will call the subset xm the k-th group of states. It’s easy to see that k |xm| = (m)k , k = 0, m, m!, k = m, m + r, where (m)k is the number of placements from m to k. Hence, m |xm| = '\"(m)k + rm! . k=0 334 DCM&ACS. 2023, 31 (4) 332-344 It is obvious that as m increases, the dimension of the state space increases rapidly. So when m ?: 5 and k ?: 10 it exceeds 103. Therefore, to construct a matrix of transition intensities and solve a system of equilibrium equations, it is necessary to develop an algorithm for constructing a space xm. 4. Algorithm for constructing the state space Let Ys be a set of sequences of length s + 1 of non-negative integers. Definition 1. We will call the operator Lj the j-insertion operator defined on the set Ys if for (i0, . . . , is) ∈ Ys Lj (i0, i1, . . . , is) = (i0+1, i1, . . . , i-1, max{i1, . . . , is}+1, ij , . . . , is), j-1, s + 1. Next, let Ys,ν be the subset Ys of power ν, i.e. Ys,ν = {y1, . . . , yν }, where s s yn n n s = (i0 , . . . , is ), n = 1, ν. Definition 2. We will call the operator L the insertion operator defined on the set of different finite subsets of the set Ys, if for Ys,ν ∈ Ys L(Ys,ν ) = {L1y1, . . . , L1yν , L2y1, . . . , L2yν , . . . , Ls+1y1, . . . , Ls+1yν r. s s s s s s Definition 3. k-th degree Lk operator L will be called an operator whose action consists of k successive applications of the operator L, k = 1, 2, 3, . . . . By the zero degree of the operator L we mean the identity operator. j Definition 4. We will call L-1 a j-removal operator defined on the set Ys if for (i0, . . . , is) ∈ Ys: L-1 j (i0, . . . , ij-1, ij , ij+1, . . . , , is) = (i0 - 1, i1, . . . , ij-1, ij+1, . . . , , is), j = 1, s. Let’s define a subset Y˜s as set Ys such that for (i0, i1, . . . , is) ∈ Ys among the numbers there is at least one that is not equal to zero and all non-zero numbers are distinct. Definition 5. We will call the operator M a maximum selection operator defined on the set Y˜s if for (i0, i1, . . . , is) ∈ Y˜s: M (i0, i1, . . . , is) = l, where l is such that il = max{i1, . . . , is}. And, finally, let Yˆs is subset of the set Ys, such that (i1, . . . , is) ∈ Yˆs, if among the numbers i1, . . . , is there is at least one that is equal to zero. Definition 6. We will call the operator Z the zero selection operator on the set Yˆs if for (i0, i1, . . . , is) ∈ Y˜s: Z(i1, . . . , is) = n, where n is the number of the first zero element in the sequence i1, . . . , is. Let us now proceed to constructing the state space and prove the validity of the following lemma. 1. I. Matyushenko, I. S. Zaryadov, On the algorithmization of … 335 Lemma 1. For any fixed m, m ?: 2: xm Lk k = (0, 0 m-k ), k = 0, m - 1, (1) Lm-1(k - m + 1, 1), k = m, m + r, where 0s = (0, . . . , 0). Proof. We will carry out the proof using the method of mathematical induction. Let m = 2. Then (0, 0, 0), k = 0; x2 k = L1(0, 0), k = 1; L1(k - 1, 1), k = 2, r + 2. Hence, = {(0, 0, 0); (1, 1, 0); (1, 0, 1); (k, 1, 2); (k, 2, 1), k = 2, . . . , r + 2r. It is obvious that the resulting set is the state space for the process X(t) in the case of m = 2 [4]. Let the statement of the lemma be true for m = l. Then for m = l + 1 we get k = xl+1 Lk (0, 0 l+1-k ), k = 0, l; = Ll(k - l, 1), k = l + 1, l + r + l (0, 0l+1), k = 0; = L(Lk-1(0, 0l+1-k )), k = 1, l; L(Ll-1(k - l, 1)), k = l + 1, l + r + l. Replace k with k + 1 and get: (0, 0l+1), k = -1; (0, 0l+1), k = -1; xl+1 k+1 = L(Lk (0, 0l-k )), k = 0, l - 1; = k L(xl ), k = 0, l - 1; L(Ll-1(k - l + 1, 1)), k = l, l + r k Next we note that if (k, i1, . . . , il) ∈ xl , then k L(xl ), k = l, l + r. - k, k = 0, l 1; max{i1, . . . , il} = l, k = l, l + r. 336 DCM&ACS. 2023, 31 (4) 332-344 Hence, (0, 0l+1), k = -1; 1 1 2 {(k + 1, k + 1, i1, . . . , il ); (k + 1, k + 1, . . . , il ); . . . ; xl+1 ν l k+1 = (k + 1, i1 , . . . , k + 1)}, k = 0, l - 1, ν = |xk |; 1 1 2 {(k + 1, l + 1, i1, . . . , il ); (k + 1, l + 1, . . . , il ); . . . ; (k + 1, iν , . . . , l + 1)}, k = l, l + r, ν = |xl |. 1 k k Given the definition of a group of states xl , the last relation can be written as: {(k + 1, i1, . . . , il) : l+1 '\" xl+1 k+1 = ij = 0, k + 1, u(ij ) = k + 1, in this case, j=1 r if ij is > 0, then ij /= is, j, s = 1, l + 1 { (k + 1, i1, . . . , il+1) : , k = -1, l - 1; ij = 1, l + 1, ij /= is, j, s = 1, l + 1r, k = l, l + r. And finally, having made the reverse replacement of k by k - 1, we come to the definition of the k-th group of states for the case m = l + 1. Thus, the lemma is proven. D It obviously follows from lemma 1 that the proposed method of constructing xm is recurrent in m. In addition, in the state space a certain order of the elements of this space is specified. For clarity, let us consider the diagram for constructing the state space in the case when m = 4 and r = 1 (figure 1). xm Analysis of the diagram helps to notice that for any fixed m, the k-th group of states is divided into m subgroups of the same dimension. A sign that a state belongs to the n-th subgroup of the k-th group is that the request with the highest number is served on device n, n = 1, . . . , m. Let us denote k,n by the n-th subgroup of the k-th group. It is easy to calculate that |x m k,n | = (m - 1)min{k,m -1}- 1, n = 1, m, k = 1, m + r. (2) The recurrent principle of constructing the state space and dividing groups into subgroups makes it possible to determine the serial number of the state in xm. Lemma 2. The ordinal number of the state (k, i1, . . . , im) in the state space xm is determined by the expression min{k-1,m-1} min{k,m-1} n = '\" j=0 (m)j + u(k - m)m! + '\" j=1 (sj - 1)(m - j)min{k,m }-j + 1, (3) where s1 = M (k, i1, . . . , im), sj = M (L-1 . . . L-1L-1(k, i1, . . . , im)), j = 2, min{m - 1, k}. sj-1 s2 s1 S. I. Matyushenko, I. S. Zaryadov, On the algorithmization of … 337 Figure 1. Diagram of the process of constructing a state space for a system with 4 devices 338 DCM&ACS. 2023, 31 (4) 332-344 Proof. Note that the first two terms in our formula determines the total number of states in groups xm, . . . , xm . Therefore, it remains to show that min{k,m-1} 0 k-1 j=1 (sj - 1)(m - j)min{k,m}-j determines the number of states of the k-th group preceding a given state. To do this, let us clarify the meaning of each term of this sum. k Notice, that s1 = M (k, i1, . . . , im) is the number in the subgroup xm that belongs to state (k, i1, . . . , im), and the size of each of the subgroups is equal (m-1)min{k,m}-1. Therefore, the expression (s1 -1)(m-1)min{k,m}-1 determines the total number of states in the subgroups xm , . . . , xm , preceding the k,1 k,s1-1 k,s1 subgroup xm . Moreover, if k = 1 or m = 2, then each of the subgroups contains one element and, therefore, the calculation process will be completed. k,s1 Otherwise, you need to define the state number in the subgroup xm . We note that in the process of recurrent construction of the state space, k,s1 the subgroup xm is obtained as a result of the action of the operator Ls1 k-1 on the group xm-1. Therefore, the ordinal number of state (k, i1, . . . , im) in k,s1 the subgroup xm s1 is equal to the ordinal number of state L-1(k, i1, . . . , im) in the group xm-1. To determine it, we find s2 = M (L-1(k, i1, . . . , im)) - the k-1 s1 number of the subgroup in the group xm-1 to which state L-1(k, i1, . . . , im) k-1 s1 belongs. The size of each of these subgroups is equal (m - 2)min{k,m}-2. So expression (s2 - 1)(m - 2)min{k,m}-2 determines total number of states in the subgroups xm-1 , . . . , xm-1 , preceding the subgroup xm-1 . Moreover, if k-1,1 k-1,s2-1 k-1,s2 k = 2 or m = 3, then each of the subgroups contains one element and the calculation process will be completed. Otherwise, it is necessary to continue similar reasoning, which will ultimately lead us to the desired result. Thus the lemma is proven. D In the future, we will need not only a formula for calculating the serial number of a state, but also an algorithm for the reverse action - restoring a state by its serial number. This task in our case is divided into two stages: determining the number of the group to which a given state belongs and calculating the serial number of the state in the group. The first stage is simple. Let n be the serial number of the state, and N = |xm|. Next, it is necessary to arrange a partition of the segment [0, N ] into m + r + 1 interval (nk , nk+1], k = 0, . . . , m + r in such a way that the condition n ∈ (nk , nk+1] means that the state with number n belongs to the k-th group. Obviously, as the boundaries of the indicated intervals it is necessary to take the numbers: 0, s = 0; ns = ns-1 + (m)s-1, s = 1, m; (4) ns+1 + m!, s = m + 1, m + r + 1. Further, carrying out arguments similar to those that took place in the proof of lemma 2, we arrive at the following result. S. I. Matyushenko, I. S. Zaryadov, On the algorithmization of … 339 Lemma 3. Let n be the serial number of the state, and k be the number of the group to which this state belongs, and let the sequence of numbers s1, . . . , smin{k,m-1} be defined by the following recurrence relations lj = n - nk , j = 1; lj-1 - (sj-1 - 1)tj-1, j = 2, min{m - 1, k}; lj (5) tj = (m - j)min{k,m}-j , sj = t , j = 1, min{m - 1, k}. j Then the state of the system is determined by the expression: (k, i1, . . . , im) = Ls1 . . . Lsk (0, 0 m-k ), k = 0, m - 1; (6) - Ls1 . . . Lsm 1 (k - m + 1, 1), k = m, m + r. To illustrate the operation of our algorithm, we give an example of restoring a state by its serial number. Let m = 4, r = 2, n = 61. j=0 Then N = 6 (4)j = 1 + 4 + 12 + 24 + 24 + 24 = 89 and the segment (0, 89] is divided into intervals: (n0, n1] ≡ (0, 1]; (n1, n2] ≡ (1, 5]; (n2, n3] ≡ (5 , 17]; (n3, n4] ≡ (17, 41]; (n4, n5] ≡ (41, 65]; (n5, n6] ≡ (65, 89]. The number 61 belongs to the interval (n4, n5]. Therefore, group number k = 4. Next, we calculate the sequence of numbers. l1 = 61 - 41 = 20, t1 = (4 - 1)4-1 = 6, s1 = 120/61 = 4; l2 = 20 - (4 - 1) · 6 = 2, t2 = (4 - 2)4-2 = 2, s2 = 12/21 = 1; l3 = 2 - (1 - 1) · 2 = 2, t3 = (4 - 3)4-3 = 1, s3 = 12/11 = 2. And finally, the desired state is determined by the expression: (4, i1, i2, i3, i4) = L4L1L2(1, 1) = L4L1(2, 1, 2) = L4(3, 3, 1, 2) = (4, 3, 1, 2, 4). Using lemma 2, we check the result: s1 = M (4, 3, 1, 2, 4) = 4; 4 s2 = M (L-1(4, 3, 1, 2, 4)) = M (3, 3, 1, 2) = 1; 1 s3 = M (L-1(3, 3, 1, 2)) = M (2, 1, 2) = 2; 3 3 - n = '\"(4)j + '\"(sj - 1)(4 - j)4 j + 1 = 41 + 20 = 61. j=0 j=1 340 DCM&ACS. 2023, 31 (4) 332-344 5. Algorithm for constructing the matrix of transition intensities Let us develop an algorithm for constructing the matrix of MP transition intensities X(t). Note that MP transitions are possible only for states from k 1 neighboring groups: transition from the group xm - k to a group xm due to the k+1 receipt of an application, and from group xm k to group xm - due to service on one of the devices. Consequently, the transition intensity matrix A will have a 3-diagonal form. Let us introduce notation for non-zero blocks A. We denote over-diagonal blocks by Λk-1,k , sub-diagonal - through Mk,k-1, and diagonal - through Nkk . It is not difficult to notice that in each column of the block Λk-1,k there can be only one non-zero element equal to λ. In each line of the block m Mk,k-1 corresponding to state (k, i1, . . . , im) there will be no more than m elements for j such that ij /= 0. Finally, the blocks Nk,k are diagonal matrices with the diagonal element corresponding to state (k, i1, . . . , im) equal to j=1 u(ij )µj - u(m + r - k)λk . Thus, to construct matrix A it is necessary: o develop an algorithm E0 that determines for any state of the system the transition conditions and the state of the system from which one can get to the given one due to the receipt of an application; o develop an algorithm Ej , which defines the transition conditions and the state of the system to which it is possible to move from this state due to servicing on device j. The implementation of these algorithms will make it possible to determine non-zero elements of blocks Λk-1,k and Mk,k-1. Before moving on to a step-by-step description of the algorithm E0, we will give some explanation of one of the conditions that will be checked in this algorithm. We are talking about when it is impossible to transition to state (k, i1, . . . , im), from any other due to the arrival of a request, except for the trivial case k = 0. In the description of the system it was said that an application that has the ability to select a device selects the device with the lowest serial number. Consequently, due to the receipt of a request, it is impossible to get into a state for which the number of the device busy servicing the request with the maximum sequence number is greater than the number of the first of the free devices. Formally, for any state (k, i1, . . . , im), this condition can be written as follows M (k, i1, . . . , im) > Z(k, i1, . . . , im), where M and Z are the maximum and zero selection operators, respectively. Moreover, this condition makes sense to check when k < m. Otherwise the check is trivial. The meaning of the remaining steps of the algorithm is quite obvious, so we will not give a detailed explanation. So, algorithm E0: Start: enter state (k, i1, . . . , im). Step 1. Check the condition k > m. If the condition is met, then go to step 5. S. I. Matyushenko, I. S. Zaryadov, On the algorithmization of … 341 Step 2. Check the condition k = m. If the condition is met, then go to step 4. Step 3. Check the condition M (k, i1, . . . , im) > Z(k, i1, . . . , im). If the condition is met, then the end of the algorithm. Step 4. l := Z(k, i1, . . . , im), il := 0. Step 5. k := k - 1. Step 6. Output values k, i1, . . . , im. End algorithm. Now let’s move on to the algorithm Ej . Note that from any state (k, i1, . . . , im) you can get to another due to servicing on device j if this device was busy with servicing, i.e. if ij /= 0. After the end of service on device j, the number of requests decreases by one. In addition, the serial numbers of those applications that entered the system later than the serviced application are reduced. Further, if at the time of the end of service there were requests in the queue awaiting service, then the first of them will arrive at device j and will be assigned a serial number m. Otherwise, device j will become free. Considering the above, the algorithm Ej can be written as: Start: Enter state (k, i1, . . . , im). Step 1. Check condition ij = 0. If the condition is met, then the end of the algorithm. Step 2. k := k - 1, l := 0. Step 3. l := l + 1. Step 4. Check the condition ((il > 0) and (il < ij )). If the condition is met, then go to step 6. Step 5. il := il - 1. Step 6. Check the condition l /= m. If the condition is met, then go to step 3. Step 7. ij := 0. Step 8. Check the condition k < m. If the condition is met, then go to step 10. Step 9. ij := m. Step 10. Print values k, i1, . . . , im. End algorithm. And finally, we will describe the algorithm E for constructing matrix A. In fact, we need to perform the following actions for all serial numbers of states of the system n: Step 1. Using lemma 3, from the ordinal number n, restore the state of the system (k, i1, . . . , im). Step 2. Using an algorithm E0 (algorithms Ej ), determine the transition conditions, and if they are fulfilled, the state of the system from which (to which) one can get to the given one (from the given one). Step 3. Using lemma 2, determine the serial numbers of states nj , j = 0, 1, . . . , m, defined in the previous step, and perform the following assignment operations: an0n := λ, (7) annj := µj , (8) 342 DCM&ACS. 2023, 31 (4) 332-344 m ann := -u(m + rk)λ - '\" u(ij )µj . (9) j=1 Thus, the main result of our study has been obtained. Let us formulate it in the form of a theorem. Theorem 1. The numbering of non-zero elements of the matrix A of the intensities of transitions of the MP X(t), which describes the functioning of the system under consideration, is determined in accordance with the algorithm E, and their values are calculated using formulas (7)-(9). 6. Conclusion Despite the fact that in this work we were constructing a matrix of transition intensities for a very specific system, we can note a number of patterns and formulate recommendations for solving problems of this type when considering other systems with a large number of similar elements. Let’s list the main stages: 1. Describe all possible states of the system in the form of sequences of corresponding numerical parameters. 2. Identify the main patterns of formation of the state space with an increase in the number of similar elements in the system and describe them using special operators. 3. To develop an algorithm for constructing a state space recurrently by the number of elements of the same type. 4. Define and formalize with the help of logical operators all possible transitions between different states of the system. 5. Develop an algorithm that allows you to determine the ordinal number of a state in the state space. 6. Develop an inverse algorithm that allows, using the serial number of a state, to restore the state itself in the form of a sequence of parameters. 7. Write down formulas for determining non-zero elements of the matrix of intensities of transitions between states of the system depending on the serial numbers of these states. 8. Enumerate all states of the system in accordance with their serial numbers and, restoring them using the inverse algorithm, calculate all non-zero elements of the matrix using the formulas from the previous paragraph.

About the authors

Sergey I. Matyushenko

RUDN University

Author for correspondence.
Email: matyushenko-si@rudn.ru
ORCID iD: 0000-0001-8247-8988

Candidate of Physical and Mathematical Sciences, Assistant professor of Department of Probability Theory and Cyber Security

6 Miklukho-Maklaya St., Moscow, 117198, Russian Federation

Ivan S. Zaryadov

RUDN University

Email: zaryadov_is@rudn.ru
ORCID iD: 0000-0002-7909-6396

Candidate of Physical and Mathematical Sciences, Assistant professor of Department of Probability Theory and Cyber Security

6 Miklukho-Maklaya St., Moscow, 117198, Russian Federation

References