Wiktor Jakowluk
email: w.jakowluk@pb.edu.pl

Fractional-Order Linear Systems Modeling in Time and Frequency Domains

Keywords: fractional calculus, Oustaloup filter, fractional dynamic systems, parameter estimation

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Fractional-order calculus was not especially popular in previous decades when its concepts have a lot of attention in various scientific fields, including more accurate system modeling and automatic control assignment [START_REF] Monje | Fractional orders Systems and Controls: Fundamentals and Applications[END_REF][START_REF] Chen | Fractional order control -a tutorial[END_REF]. Utilising the notion of noninteger order should be more appropriate step because real-life processes appear to be fractional [START_REF] Torvik | On the appearance of the fractional derivative in the behaviour of real materials[END_REF][START_REF] Oustaloup | Frequency-Band Complex Noninteger Differentiator: Characterization and Synthesis[END_REF]. The fractional-order calculus is the generalisation of the classical calculus, where the order of integration and differentiation is not an integer index [START_REF] Miller | An introduction to the fractional calculus and fractional differential equations[END_REF].

There have been some reports on non-integer calculus, applied to various areas of the applications, e.g.: bioengineering [START_REF] Magin | Fractional Calculus in Bioengineering[END_REF], physics [START_REF] Hilfer | Applications of Fractional Calculus in Physics[END_REF][START_REF] West | Physics of Fractal Operators[END_REF], chaos theory [START_REF] Petras | Fractional-Order Nonlinear Systems[END_REF], control systems [START_REF] Monje | Fractional-Order Systems and Controls[END_REF][START_REF] Podlubny | Fractional Differential Equations[END_REF][START_REF] Valério | An Introduction to Fractional Control[END_REF] and fractional signal processing [START_REF] Sheng | Fractional Processes and Fractional-order Signal Processing[END_REF][START_REF] Mozyrska | Modified optimal energy and initial memory of fractional continuous-time linear systems[END_REF]. It is clear that the rise of interest in the fractional calculus domain is related to the increasing availability of high-performance and advanced computational tools. Fractional order calculus was applied in robotics and automation, taking into account system identification and automatic control [START_REF] Chen | Fractional order control -a tutorial[END_REF]. The control performance assessment has a large influance on the economic aspect of the real-life processes. It was reported that conventional PID controller, in industral applications, is worse than fractional order PID controller according to the tuning flexibility [START_REF] Monje | Tuning and autotuning of fractional order controllers for industry applications[END_REF].

For fractional order system analysis one of existing packages for non-integer order modeling and controller synthesis tasks, such as CRONE, Ninteger or FOMCON [START_REF] Tepljakov | FOMCON: a MATLAB toolbox for fractionalorder system identification and control[END_REF], can be employed. Above packages are implemented in Matlab environment and have effective tools for solving various fractional order problems and can be easily connected with other Matlab facilities (e.g. simulation of models in Simulink environment utilising graphical interface).

The non-integer order differentiation is equivalent to infinite dimensional filter that is why the selection of appropriate approximation factors is very important. The goal of this study is to verify fitting the Outsaloup filter to the fractional inertial model approximation in a specified narrow frequency range. The proper Oustaloup's approximation could be then used for modelling the non-integer order differentiation operator in an integer order state-space form. The fractional order control problem would be then reformulated to solve optimal input signal design task [START_REF] Jakowluk | Plant friendly input design for parameter estimation in an inertial system with respect to D-efficiency constraints[END_REF][START_REF] Jakowluk | Optimal input signal design for a second order dynamic system identification subject to D-efficiency constraints[END_REF]. For non-integer order system modeling in frequency and time domains the Fomcon toolbox was utilised [START_REF] Tepljakov | FOMCON: a MATLAB toolbox for fractionalorder system identification and control[END_REF].

Fractional Calculus

The idea of the differentiation operator is a fundamental tool in the study of the ordinary differential equations. Fractional calculus is a special case of integration and differentiation to non-integer order operator  t a D as follows:

                          t a t a d dt d D 0 , 0 1 0         (1)
where: a, t -denote the limits of the process and α is the set for all complex numbers. There are different definitions of the fractional derivative operator [START_REF] Monje | Fractional orders Systems and Controls: Fundamentals and Applications[END_REF].

The Riemann-Liouville fractional derivative (α > 0) of a function f(t) is defined as:

                        t a m m t a d t f dt d m dt t f d t f D , 1 1         (2)
where: Γ(•) stands for Euler's gamma function and .

1 , 0 ( for N, , 1         m m m
Such a definition can also be reformulated to fractional-order derivative in the form:

                t a t a d t f dt d dt t f d t f D , 1 1         (3)
The Laplace transform of the Riemann-Liouville derivative (2) for a = 0 is:

          , 0 1 1 0        m k k a k t f s s F s t f D L   (4) where:      . t f L s F 
The Caputo's definition of fractional-order derivative (α > 0) is defined as follows:

                    t m p t a d t f m dt t f d t f D 0 1 , 1         (5)
where:

        . 1 , m m t f dt d t f m m m      This definition for   1
, 0 (  can be reformulated to fractional-order derivative in the following form:

          . 1 1 0       t t a d t f dt t f d t f D         (6)
The Laplace transform of the Caputo derivative (5) for a = 0 is:

          . 0 1 1 0        m k k k t f s s F s t f D L    (7)
It was reported that for real functions, the fractional-order derivative from the Riemann -Liouville and Grünwald -Letnikov definitions are identical [START_REF] Podlubny | Fractional Differential Equations[END_REF].

Finally, the Grünwald -Letnikov definition would be considered:

     , 1 1 lim 0 0 jh t f j h t f D k j j h t a                  (8)
where:

            j j j    1
describes polynomial factors, which can be received recursively from:

,..., 2 , 1 , 1 1 , 1 1 0               j j j j        (9)
Utilising equation ( 9) the fractional-order derivative (8) can be suitably modified as:

   , 1 0 jh t f h t f D k j j t a         ( 10
)
where a = 0, t = kh is the step number and h is the step duration. The Laplace transform assuming zero initial conditions of derivative [START_REF] West | Physics of Fractal Operators[END_REF] with

  R  is as follows [1]:      . 0 s F s t f D L t    (11)
Linear fractional-order continuous-time SISO dynamic system can be expressed by a fractional-order differential equation [START_REF] Monje | Fractional orders Systems and Controls: Fundamentals and Applications[END_REF][START_REF] Chen | Fractional order control -a tutorial[END_REF]:

         n k m k t k t k t u D b t y D a i i 0 0 ,   (12)
where: a k , b k are real numbers. The discrete-time version for various orders one can find in [START_REF] Mozyrska | Multiparameter Fractional Difference Linear Control Systems[END_REF]. Applying the Laplace transform to [START_REF] Valério | An Introduction to Fractional Control[END_REF] with zero initial conditions the input-output description of the fractional-order system can be expressed in the transfer function form:

      . 0 1 0 1 0 1 0 1       s a s a s a s b s b s b s U s Y s G n n m m n n m m               (13)
The transfer function ( 13) is commensurate order if all orders of the fractional operator s are integer multiples of base order q in such a way: . , ,

1 0 , R kq q q k k       
The above continuous-time transfer function can be modified to give to the pseudo-rational function H(λ) in the form:

  , 0 0      n k k k m k k k a b H    (14)
where: λ = s q . Using the pseudo-rational notation a fractional-order linear timeinvariant system can be easily expressed by a state-space model given by:

           . , 0 t Du t Cx t y t Bu t Ax t x D t      (15)
For system parameters identification purposes the difference equation representing input-output dynamic of the system is more convenient than the state-space description. However the state-space model notation provides of multiple input and multiple output (MIMO) fractional-order systems representation.

Oustaloup Filter to Approximation of Fractional-Order Operators

The potentiality of approximating the fractional-order plant model by an integer-order one is presented in [START_REF] Monje | Fractional orders Systems and Controls: Fundamentals and Applications[END_REF]. For linear fractional-order model identification purposes the Oustaloup filter method, which is often used in practical applications, should be considered. We focus our attention on the clasical Oustaloup approximation algorithm. To solve the problem of approximation of a fractional differentiator or a fractional integrator the following equations should be used:

     N k k k s s K s 1 ,    ' ( 16
)
where: poles, zeros and gain of the filter can be obtained from:

  , 1 2 N k u b k         ' (17)   , 1 2 N k u b k        (18)
,

  h K  (19) , b h u     (20)
where: N is the order of approximation and (ω b , ω h ) is the expected frequency fitting range. The order of the resulting filter is 2N+1, taking into account a higher orders of N the resulting approximation should be more accurate.

The Oustaloup filter provides very good approximation results of fractional operators in an expected fitting range and a wide orders interval. Thus, for the fractional order operators where α ≥ 1 the following equation should be adopted:

,   s s s n  (21)
where: n = α -γ indicates the integer part of α and s γ is evaluated according to [START_REF] Monje | Tuning and autotuning of fractional order controllers for industry applications[END_REF] utilisig Oustaloup filter method.

Problem Formulation

To illustrate the properties of the above approach to fractional-order system parameter estimation, using the Oustaloup filter, we have selected FOMCON toolbox, which provides time-domain and frequency-domain non-integer order system analysis, as well as system stability checking [START_REF] Tepljakov | FOMCON: a MATLAB toolbox for fractionalorder system identification and control[END_REF]. The goal of this study is to verify the accuracy of the Oustaloup filter to the fractional inertial system transfer function parameters estimation in a specified frequency range ω = [ω b , ω h ] and order of the filter 2N+1.

To justify the idea of this approach to integer model parameter estimation, an inertial object was selected as:

  . 0 , 1      T s k s G (22)
The fractional-order linear time invariant system can be then described by the following single input, single output state-space model:

         , , 0 t x t y t Bu t Ax t x D t     (23)
with assumed values of the matrix parameters: A = -1, B = 1 and zero initial conditions. The specified wide bandwidth would cause a large computational burden as N is increased. Therefore, the choice of N is based on following rule:

   . log log b h N     ( 24
)
The results of the Oustaloup filter approximation of the fractional transfer function [START_REF] Matignon | Generalized fractional differential and difference equations: Stability properties and modeling issues[END_REF] for different values α from the interval 0.5 ≤ α ≤ 1.9 and arbitrary selected bandwidth ω = [10 -1 , 10

              s s s s s s s s s s s s G s s G o (31)
As it can be seen the resulting filters can be displayed in the Laplace domain, as reasonable approximations of the non-integer order operators. Additionally, this method exhibit practical property: it has zeros and poles interlaced on the negative real axis of the s plane, and the length between following poles and zeros decreases as the estimation is improved by increasing the order of the polynomials' numerator and denominator, as it is displayed in Figure 6.

5

The Experimental Results for Time and Frequency Domains

The time-domain simulation of the evaluated model of the fractional system, utilising step input signal, is based on the Grünwald-Letnikov definition shown in equation [START_REF] West | Physics of Fractal Operators[END_REF]. The solution of the numerical problem ( 22) is performed utilising modified Grünwald-Letnikov definition [START_REF] Chen | Fractional order control -a tutorial[END_REF]:

  , 1 0 / 1 0                  n i h t j jh t j i t n i i t y h a u h a y j i i     (32)
where h = 0.01 is the numerical step-size. The frequency-domain simulation is executed by replacing s = jω. This substitution was applied to Eqs. ( 25), ( 27), (29-31) to obtain frequency domain diagrams. In order to verify the stability of the approximated systems we obtained a step responses (at t = [0, t end ] with dt = 0.1) and Bode diagrams (for frequency axis range ω = [10 -3 , 10 2 ] and N= 2) shown in Figures 12345. Step and frequency responses comparison for inertial (α = 1.9) system The Figures 12345show the Oustaloup filter step responses compared with the exact fractional inertial model step responses and frequency plots (Bode diagrams) of the real plant and obtained approximations.

Stability of the non-integer order state-space system (15) should be established from the following inequality:

    , 2 eig arg    A (33)
where: 0 < α < 1 is the fractional state-space system commensurate order and eig(A) describes the eigenvalues of the related matrix A. If this requirement is satisfied, then the system is stable [START_REF] Matignon | Generalized fractional differential and difference equations: Stability properties and modeling issues[END_REF]. The fractional order state-space system (23) is stable because the eigenvalue of the matrix A equals -1.

Pole-Zero Map

Real Axis (seconds -1 ) Imaginary Axis (seconds -1 where Δy (w) , e (w) , M and R 2 are respectively: absolute error, relative error, root-meansquare error and coefficient of determination. The comparision of the performance indices for Oustaloup filter approximation are displayed in Table1. The estimated transfer functions parameters and obtained indices show high accuracy of the Oustaloup filter approximation. The slight fitting errors could be observed in the range of fractional order from the interval 0.9 ≤ α ≤ 1.7.

In some applications, a zero-pole transfer functions (25-31) as a result of fractional order systems approximation are not helpful. Instead of this, the state-space realisation (23) is desirable. The examples of the approximated integer order state-space matrices for α = 0.5 and α = 1.5 are given by: Step responses comparison for inertial system with different order values α A step responses of the fractional inertial system [START_REF] Matignon | Generalized fractional differential and difference equations: Stability properties and modeling issues[END_REF] in the time duration t = [0, 30] seconds with a step size of h = 0.01 are obtained utilising the Grünwald-Letnikov method (32). The step responses for α ≤ 1 are aperiodic (Fig. 7), however conventional first order inertial system step response can be observed for α = 1. The step responses are oscillating for non-integer system orders α ≥ 1.

   , 2 . 0 , 5 . 0 0 . 4 2 . 8 3 . 5 9 . 0 , 0 0 0 0 1 , 0 0 . 1 0 0 0 0 0 0 . 1 0 0 0 0 0 0 . 1 0 0 0 0 0 0 . 1 0 . 1 4 . 9 0 . 26 0 . 26 9.4 -                                         D C B A      . 0 . 1 2 . 8 0 . 19 1 . 15 1 . 4 3 . 0 , 0 0 0 0 0 1 , 0 0 . 1 0 0 0 0 0 0 0 . 1 0 0 0 0 0 0 0 . 1 0 0 0 0 0 0 0 . 1 0 0 0 0 0 0 0 . 1 0 . 1 6 . 8 2 . 23 3 . 30 2 . 23 6 . 8                                                  C B A    0 5 10

Conclusions

In this paper the accuracy of the approximation of the Outsaloup filter yielding transfer functions for a given fractional-order inertial model have been verified. The results of the Oustaloup filter approximation of the non-integer inertial model for different values α from the interval 0.5 ≤ α ≤ 1.9 and arbitrary selected narrow bandwidth ω = [10 -1 , 10 1 ] was presented. The simulation results in time and frequency domains confirm high accuracy of the Oustaloup estimation to the selected frequency range and order. The comparison of the performance indices for the Oustaloup approximation model and original plant shows a slight fitting errors for fractional order from the interval 0.9 ≤ α ≤ 1.8. The pole and zero diagrams show that for different values of α, obtained integer order models are stable. The choice of the approximation method depends on established requirements (e.g. accurate frequency behavior or precise time response). The proper Oustaloup's approximation can be utilised for modelling the fractional order operator in an integer order state-space form. Then, it is possible to use one of the existing optimal control packages to solve fractional order optimal input problem.

Fig. 1 .Fig. 2 .Fig. 3 .Fig. 4 .

 1234 Fig. 1. Step and frequency responses comparison for inertial (α = 0.5) system

1  = 1 . 9 Fig. 6 .

 1196 Fig. 6. Pole and zero maps of the approximated systems for different values of α

  Fig. 7. Step responses comparison for inertial system with different order values α

  1 ] with N= 2 according to (24), are displayed by transfer functions G o (s) given by:

	G	  s		s	. 0	1 5		1	,		G o		(	s	)		0	.	24	s s	5 5	 	4 . 14 . 3 9 4 s s	98 5 . 11 . 25   4 s s 3 3	98 . 48 . 25 14   s s 2 2	1 0   s s 26 4 . . 9 6  	76 .	,	(25)
	G	  s		s		1 7 . 0		1	,		G o	(	s	)		0	.	17 s	5 s	8   5	65 . 38 . 2 4 s s	78 57 . 22 . 9   4	s s	3 3	 	78 . 21 . 22 13 s s 2 2	 	65 27 . 8 . 6 s s	 	1 0	.	83	,	(26)
	G	  s		s	. 0	1 99		1	,	G o	(	s	)		0	.	09 5 s s	49 52 . 1 . 7   5 s s 4	99 . 97 . 17 6   4	s s	3 3	 	17 11	99 . 01 . s s 2 2	 	49 97 . 7 . 5 s s	 	1 0	.	91	,	(27)
	G	  s		. 1 s	1 3		1	,	G o	(	s	)		s	6	0 	54 50 . 9 . 5 s s	5 	5 	88 2  s s . 28 91 . 22 3   91 3 s s . 39 95 .  19 4  88 4 s s . 22 97 .	54  s . 04 9  . 9 2	1 s		1	,	(28)
	G	  s		. 1 s	1 5		1		,		G o		(	s	)		s	6	0 	56 32 . 8 . 5 s s	19 4 s . 23 13 . 4   5	27 3  s s . 30 14 . 15 4   s	. 19 3 	19 2  s s . 23 05	8 2	56 1  s s . 8 24  .		1	,	(29)
	G	  s		. 1 s	1 7		1	,		G o	(	s	)		s	6	72 20 . 7 . 0 5  s  5 s	96 3  s s . 22 48 . 11 4   71 4 s s . 18 86 .  2	72  s 1  s . 7 52  . 7 2  71 2 s s . 18 85 . 15 3 	1	,	(30)
		 		1 9 . 1				1	,			(				)	. 0 6	. 35 02 5	9	1 5	.	260 97 4	49 4	5 3 . 487 18 .	4 2 . 465 6 . 289 3	417 9 . 402 2	2 2 . 112 . 112	.

Table 1 .

 1 The comparision of the approximation errors and factors.

	α	0.5	0.7	0.9	1.0	1.1	1.3	1.5	1.7	1.9
	  w y min 	0.016 0.013 0.008 0.000 0.000 0.000 0.000 0.000 0.000
	  w y max 	0.139 0.133 0.106 0.018 0.017 0.020 0.035 0.060 0.080
	  [%] min w e	3.26	4.50	3.83	0.00	0.00	0.00	0.04	0.00	0.00
	  [%] avg w e	11.13 11.02 9.72	0.25	0.55	0.75	0.68	0.93	0.97
	  [%] max w e	15.48 13.77 10.70 4.45	6.04	4.99	6.71	7.43	7.59
	M	0.101 0.106 0.096 0.004 0.006 0.009 0.010 0.017 0.018
	R	2	0.942 0.973 0.995 0.999 0.999 0.998 0.997 0.996 0.965

Acknowledgement

The present study was supported by a grant S/WI/1/13 from Bialystok University of Technology and founded from resources for research by Ministry of Science and Higher Education.


Walenty Oniszczuk
email: w.oniszczuk@pb.edu.pl

Service strategies in two-server tandem configurationsmodeling and investigation

Keywords: Internet tandem configurations, open queuing network, blocking probabilities, performance measures

In this document, two different service strategies in an Internet service station, which consists of with two separated servers (tandem), are investigated. At beginning the Internet tandem under study is first formulated as an open three-station queuing network with blocking assuming that there are finite capacity buffers at front of each server. For each Internet station configurations, the two-dimensional state graphs ware constructed and set of steady-state equations are created. These equations allow for calculating the state probabilities vectors for each tandem configurations, using an equation solving techniques. Many useful performance measures regarding the tandem configurations under study can be extracted from the steady-state probability vectors. The numerical part of this paper contains example for the investigation of different tandem configurations, where are presented the results of the calculation of the main measures of effectiveness and quality of service (QoS) parameters.

Introduction

A traditional Internet server processes requests in FIFO manner. During a high load period, each task has to wait in a queue for a long time before getting serviced. Overhead from tasks competing for limited resources, such as open connections and network bandwidth, is increased. Retry from impatient clients worsens the load situation and causes the snowball effect. More elaborate resource allocation schemas, rather than best-effort service model, need to be adopted to provide predictable services during high load periods. The existing best-effort service with the FIFO scheduling mode and dropping tasks (requests) if the queue is full of the Internet servers leads to misallocation of scarce and expensive network and CPU resources during heavy load periods, causing unpredictable response delay. The next generation Internet will demand differentiated services from Internet servers. The most important function of the future Internet is to support the provisioning of reliable real-time services on a wide scale. In order to achieve this goal, peraggregate resource management is, nowadays, regarded as a mandatory choice. The classical example of the modern approach to service users tasks is divided they service processes onto several separated servers (for example, as mechanisms for resolving some security problems), which processes some independent parts of incoming tasks. In this paper, we analyze two different tandem configurations, which consists of with two separated servers, in specific way connected each other. At each server, FIFO multiplexing is in place, meaning that all tasks traversing the server are buffered in a single queue First-Come-First-Served. Nowadays the tandem networks have been studied extensively and applied in the evaluation of various systems as in design, capacity planning and performance evaluation of computer and communication systems, call centers, flexible manufacturing systems, etc. Some examples of their application in real systems (two transmitter communication networks with Dynamic Bandwidth Allocation, service facility with front and back room operations) can be found in [START_REF] Raghavendran | Tandem communication network model with DBA having Non Homogeneous Poisson arrivals and feedback for first node[END_REF], [START_REF] Arivudainambi | Analysis of a service facility with cross trained servers and optional feedback[END_REF] respectively. The behavior of various systems, including communication and computer systems, as well as production and manufacturing procedures, can be represented and analyzed through queuing network models to evaluate their performance [START_REF] Legros | Optimal scheduling in call centers with a callback option[END_REF][START_REF] Malekian | Novel packet queuing algorithm on packet delivery in mobile internet protocol version 6 networks[END_REF][START_REF] Mangili | Performance analysis of Content-Centric and Content-Delivery networks with evolving object popularity[END_REF], [START_REF] Sunitha | A pre-emptive multiple queue congestion control for different traffic classes in WSN[END_REF][START_REF] Tikhonenko | On the queue-size distribution in the multi-server system with bounded capacity and packet dropping[END_REF]. System performance analysis usually includes the queue length distribution and various performance indicators such as response time, throughput and utilization [START_REF] Atencia | A discrete-time system with service control and repairs[END_REF], [START_REF] Gemikonakli | Exploring service and buffer management issues to provide integrated voice and data services in single and multichannel wireless networks[END_REF]7], [START_REF] Kwiecień | Firefly algorithm in optimization of queueing systems[END_REF].

The theory behind tandem queues is well developed, see, e.g. [START_REF] Balsamo | Analysis of Queueing Networks with Blocking[END_REF][START_REF] Clo | MVA for product-form cyclic queueing networks with blocking[END_REF][START_REF] Economou | Product form stationary distributions for queueing networks with blocking and rerouting[END_REF], [START_REF] Martin | Large tandem queueing networks with blocking[END_REF], [START_REF] Onvural | Survey of closed queuing networks with blocking[END_REF][START_REF] Perros | Queuing Networks with Blocking. Exact and Approximate Solution[END_REF]. However, there is still a great interest around more complicated setups involving blocking phenomena as well as different mechanisms for offering services. An excellent survey may be found in the well known of Perros [START_REF] Onvural | Survey of closed queuing networks with blocking[END_REF] and Balsamo [START_REF] Balsamo | Analysis of Queueing Networks with Blocking[END_REF] books. Over the years high quality research has appeared in diverse journals and conference proceeding in the field of computer science, traffic engineering and communication engineering [START_REF] Clo | MVA for product-form cyclic queueing networks with blocking[END_REF], [START_REF] Martin | Large tandem queueing networks with blocking[END_REF], and [START_REF] Onvural | Survey of closed queuing networks with blocking[END_REF]. In particular, the two-node tandem queuing model with the Batch Markovian Arrival Process input flow and non-exponential service time distribution described in the paper [START_REF] Kim | The BMAP/G/1-> •/PH/1/M tandem queue with feedback and losses[END_REF]. Additionally, systems with finite capacity queues under various blocking mechanisms and scheduling constraints are analyzed by the author in [START_REF] Oniszczuk | Quality of service requirements in computer networks with blocking[END_REF][START_REF] Oniszczuk | Modeling of dynamical flow control procedures in closed type queuing models of a computer network with blocking[END_REF][START_REF] Oniszczuk | Tandem models with blocking in the computer subnetworks performance analysis[END_REF][START_REF] Oniszczuk | Blocking and deadlock factors in series linked servers with HOL priority feedback service[END_REF][START_REF] Oniszczuk | Analysis of an open linked series three-station network with blocking[END_REF][START_REF] Oniszczuk | An intelligent service strategy in linked networks with blocking and feedback[END_REF][START_REF] Oniszczuk | Semi-Markov-based approach for analysis of open tandem networks with blocking and truncation[END_REF][START_REF] Oniszczuk | Analysis of linked in series servers with blocking, priority feedback service and threshold policy[END_REF][START_REF] Oniszczuk | Loss tandem networks with blocking analysis -a semi-Markov approach[END_REF][START_REF] Oniszczuk | Open tandem networks with blocking analysis -two approaches[END_REF][START_REF] Oniszczuk | Blocking and deadlocking phenomena in two-server tandem configuration with optional feedback -modeling and parameter sensitivity investigation[END_REF]. In [START_REF] Oniszczuk | Quality of service requirements in computer networks with blocking[END_REF][START_REF] Oniszczuk | Modeling of dynamical flow control procedures in closed type queuing models of a computer network with blocking[END_REF], the closed type, multi-center computer networks with different blocking strategies are investigated and measures of effectiveness based on Quality of Service (QoS) are studied. Markovian and semi-Markovian approaches for analysis of open tandem networks with blocking are presented in [START_REF] Oniszczuk | Tandem models with blocking in the computer subnetworks performance analysis[END_REF], [START_REF] Oniszczuk | Analysis of an open linked series three-station network with blocking[END_REF], [START_REF] Oniszczuk | Semi-Markov-based approach for analysis of open tandem networks with blocking and truncation[END_REF], [START_REF] Oniszczuk | Loss tandem networks with blocking analysis -a semi-Markov approach[END_REF] [24] and [START_REF] Oniszczuk | Blocking and deadlocking phenomena in two-server tandem configuration with optional feedback -modeling and parameter sensitivity investigation[END_REF]. Some two-stage tandem queues with blocking and an optional feedback are presented in [START_REF] Oniszczuk | An intelligent service strategy in linked networks with blocking and feedback[END_REF] and [START_REF] Oniszczuk | Analysis of linked in series servers with blocking, priority feedback service and threshold policy[END_REF]. In such systems, feedback is the likelihood of a task return, with fixed probability to the first server of the tandem immediately after the service at the second one [START_REF] Kim | The BMAP/G/1-> •/PH/1/M tandem queue with feedback and losses[END_REF]. Tandems with feedback are usually more complex than the ones without and they are mostly investigated given stationary Poisson arrival process and exponential service time distribution [START_REF] Arivudainambi | Analysis of a service facility with cross trained servers and optional feedback[END_REF], [START_REF] Raghavendran | Tandem communication network model with DBA having Non Homogeneous Poisson arrivals and feedback for first node[END_REF]. Blocking and deadlocking phenomena in an open series, linked network model with HOL (head-of-line) priority feedback service was investigated and presented by the author in [START_REF] Oniszczuk | Blocking and deadlock factors in series linked servers with HOL priority feedback service[END_REF].

The remainder of this paper is organized as follows: Section 2 presents and explains the models specification and description. Section 3, analyzes a tandem as an open linked series three-station network with blocking. Section 4 explains a tandem as a linked rerouting two-server network the same with blocking. Section 5 describes the numerical results obtained using our solution technique, followed by the concluding remarks in Section 6.

Models specification and description

In this research, two different configuration of Internet tandem is presented. Each of these kinds of tandem networks has a single service line at the main server, and the other (additional) server with a single service line. Between these servers is a common waiting buffer with finite capacity, for example equal to m2. When this buffer is full, the accumulation of new tasks from the main server is temporarily suspended and a phenomenon called blocking occurs until the queue empties and allows new inserts. Similarly, if the first buffer (with capacity m1) ahead of the main server is full, then the Internet source node (station) is blocked. This is the classical mechanism for controlling the intensity of an arriving task stream, which comes from the Internet users to the servicing tandem. In this kind of network configuration, no more than m1+m2+2 tasks can be processed simultaneously and the Internet tandem network becomes idle, if there are no tasks in both servers.

Let us consider the Internet two-server tandems with blocking, both configurations, as shown in Figure 1 and Figure 2. On these figures we present models of generalized Internet tandem networks and analyze the feasibility of service with blocking and rerouting. These networks contain of four major logical components: 1. Main server, for the first or the first and the second stage tasks processing with a task initiator, a task controller (realization ON-OFF strategy for incoming requests) and a task dispatcher. 2. Second sever -for the second stage tasks processing. 3. Communication channels. 4. Internet source and λ represents the request arrival process from the clients.

After processing the responses are sent back to the clients through the communication channels. To simplify the model, we assume that the tandem of servers connect to the client through a high speed network. We have ignored the channel delay and flow control on a client side as they are beyond the scope of the proposed study.

The input task stream comes from the Internet source to the main server. This server has a finite capacity buffer and it can accept only m1+1 tasks. A new task, which arrives at the full main server buffer, is forced to wait in the Internet source station and blocks it. For linked in series servers configuration of tandem (see Fig. 1), each task at the main server is processed on the service line and upon service completion sent to the second server. If there is a free service line on this server, the service process starts immediately, if not, the task must wait in the buffer. If the buffer is full, any task upon service completion at the main server is forced to wait and blocks this server. In case of tandem with rerouting configuration (see Fig. 2), after service completion at the main server, the task proceeds to the second server with probability 1-σ, and with probability σ the task departs from tandem. Tasks leaving the second server are always feed back to the main server. If the main server buffer is full, similarly as in the previous configuration, the tasks block the second server. The general assumptions for these two-server tandem models are: 1. Internet tasks stream arriving to the main server is assumed to be a Poisson stream, with rate λ =1/a, where a is the mean inter-arrival time, 2. a single service line is on the main server, 3. a single service line is available on the second server, 4. in both servers the service time represents exponentially distributed random variables, with mean s A = 1/µ A and s B = 1/µ B , where µ is the mean service rate, 5. the buffers capacities are finite, for example equal to m1 and m2, respectively to the main and the second servers, 6. service strategies restrict and forbid tasks truncations, if the buffers are full in any case (strategy network drop-tail is forbidden) and tasks lose In this special type of multi-stage network with blocking a deadlock may occur. We assume that a deadlock is detected instantaneously and resolved without any delay time by simultaneously exchanging both blocked tasks [START_REF] Oniszczuk | Blocking and deadlocking phenomena in two-server tandem configuration with optional feedback -modeling and parameter sensitivity investigation[END_REF]. Generally, blocking phenomena is a very important mechanism for controlling and regulating intensity of arriving tasks from the Internet source (users) to the Internet tandem servers. A blocking strategies in the main server are realized by a Controller mechanism, it means that controller temporarily suspend and resume (ON-OFF strategy) transfer process from users, because "network drop-tail strategy is forbidden" must be realized. The arrival rate to the main server depends on the state of the tandem and blocking factor that reduces the rate at which users are sending tasks to the tandems.

Tandem as an open linked series servers

Let us consider the Internet two-server tandem shown in figure 1 as the three-station queuing network with blocking. Each queuing system can, in principle, be mapped onto an instance of a Markov process and then mathematically evaluated in terms of this process. According to general assumptions, a continuous-time homogeneous Markov chain can represent a tandem network. The queuing network model reaches a steady-state condition and the underlying Markov chain has a stationary state distribution. Also, such queuing network with finite capacity queues has finite state space. The solution of the Markov chain representation may then be computed and the desired performance characteristics, as queue length distribution, utilizations, and throughputs, obtained directly from the stationary probability vector.

In theory, any Markov model can be solved numerically. In particular, solution algorithm for Markov queuing networks with blocking is a five-step procedure: 1. Definition of the series network state space (choosing a state space representation). 2. Enumerating all the transitions that can possible occur among the states. 3. Definition of the transition rate matrix Q that describes the network evaluation (generating the transition rate). 4. Solution of linear system of the global balance equations to derive the stationary state distribution vector (computing appropriate probability vector). 5. Computation from the probability vector of the average performance indices.

In this type of an open series network we may denote its state by the pair (i,j), where i represents the number of tasks in main server and j denotes the number in second server, including all tasks in service and in blocking. Here some blocked tasks, physically, are located on the Internet source station or on the main server, but the nature of the service process in both servers, allows one to treat them as located in additional places in the buffers and they belong to the main server or the second server. In this case, there can be a maximum of m1+2 tasks assigned to the main server including the task in the Internet source that can be blocked. Similarly, there can be a maximum of m2+2 tasks assigned to second server with a task blocked in the main server. For any non-negative integer values of i and j, (i,j) represent a feasible state of this queuing network, and p i,j denotes the probability for that state in equilibrium. These states and the possible transitions among them are shown in Figure 3. This state diagram of the series server network contains all possible non-blocked states (marked by ovals) as well as the blocking states (marked by rectangles).

Based on an analysis the state space diagrams, the process of constructing the corresponding differential-difference equations, differential equations in t, and difference in (i,j) state, can be divided into several independent steps, which describe some similar, repeatable schemas (see Fig. 3).

These equations are: a) for states without blocking factor:

p ' 0,0 (t) = -λ • p 0,0 (t) + µ B • p 0,1 (t) p ' 0,j (t) = -(λ + µ B ) • p 0,j (t) + µ A • p 1,j-1 (t) + µ B • p 0,j+1 (t) for j = 1, ... , m2+1 p ' i,0 (t) = -(λ + µ A ) • p i,0 (t) + λ • p i-1,0 (t) + µ B • p i,1 (t) for i = 1, ... , m1+1 p ' i,j (t) = -(λ + µ B + µ A ) • p i,j (t) + λ • p i-1,j (t) + µ A • p i+1,j-1 (t) + µ B • p i,j+1 (t) (1)
for i = 1, ... , m1+1, j = 1, ... , m2+1 b) for states with Main Server blocking:

p ' 0,m2+2 (t) = -(λ + µ B ) • p 0,m2+2 (t) + µ A • p 1,m2+1 (t) p ' i,m2+2 (t) = -(λ + µ B ) • p i,m2+2 (t) + λ • p i-1,m2+2 (t) + µ A • p i+1,m2+1 (t)
(2) for i = 1, ... , m1 c) for states with both Internet source and Main Server simultaneous blocking: [START_REF] Gemikonakli | Exploring service and buffer management issues to provide integrated voice and data services in single and multichannel wireless networks[END_REF] this leads to the set of equilibrium equations.

p ' m1+1,m2+2 (t) = -µ B • p m1+1,m2+2 (t) + λ • p m1,m2+2 (t) + µ A • p m1+2,m2+1 (t) (3)
Here, a queuing network with blocking linked in series, under appropriate assumptions, is formulated as a Markov process and the stationary probability vector can be obtained using numerical methods for linear systems of equations. If there is a model network with finite number of states, its steady-state probabilities can be found directly from equations ( 1) -( 6) by using some iteration method and the normalizing condition for the sum of state probabilities. In the second table, the λ-decl is the declared inter-arrival input stream intensities from the Internet source to the tandems, λ-s-eff and λ-r-eff are effective input stream intensities for series and rerouting tandems, w-s and w-r are the mean waiting times for series and rerouting tandems, ro-s and ro-r are the second server utilization factors for series and rerouting tandems.

In the next table, the λ is the inter-arrival rate from the Internet source to the tandems, v-M-s and v-M-r are the number of tasks in the Main server buffer for series and rerouting tandems, v-S-s and v-S-r are the number of tasks in the Second server buffer for series and rerouting tandems, ro-s and ro-r are the main server utilization factor for series and rerouting tandems.

Table 3. Measures of effectiveness -the occupation parameters The results of the experiments clearly show that the effect of the properly chosen service strategy in Internet tandem network must be taken into account when analyzing performance such computer networks. Also, results of these calculations evidently show that the blocking phenomena must be taken into account because variation of inter-arrival rate drastically changes the main performace parameters. Which tandem configurations and service strategies are better? It all depends, which measures or time parameters are more preferable during our analysis and obtained results applications.

λ v-M-s v-M-r v-S-s v-S-

Conclusions

An approach to compare the effectiveness of two service strategies in Internet servers linked to tandem with blocking has been presented. Tasks blocking probabilities and some other fundamental performance characteristics of such networks are derived, followed by numerical examples. The results confirm importance of a special treatment for the models with blocking, which justifies this research. Moreover, our proposal is useful in designing buffer sizes or channel capacities for a given blocking probability requirement constraint. The results can be used for capacity planning and performance evaluation of real-time computer networks where blocking are present.

Fig. 1 .

 1 Fig. 1. Tandem configuration as open linked series servers.

Fig. 2 .

 2 Fig. 2. Tandem configuration as rerouting networks.

Fig. 3 .

 3 Fig. 3. State transmission diagram for linked series serversSome specialized software for the solution of nonsymmetrical linear systems of equations by using iterative methods was created by the author. The package is written entirely in the C programming language, and data structures are managed dynami-

Table 2 .

 2 Measures of effectiveness -the responses (the time parameters)

	λ-decl	λ-s-eff	λ-r-eff	w-s	w-r	ro-s	ro-r
	1.0	1.000	1.000	0.010	0.010	0.200	0.200
	2.0	2.000	2.000	0.053	0.053	0.400	0.400
	3.0	3.000	3.000	0.180	0.180	0.600	0.600
	4.0	4.000	4.000	0.640	0.640	0.800	0.800
	5.0	4.992	4.942	3.331	4.512	0.972	0.986
	6.0	5.836	5.000	5.469	5.791	0.999	1.000
	7.0	6.408	5.000	5.829	5.792	1.000	1.000
	8.0	6.774	5.000	5.928	5.792	1.000	1.000
	9.0	7.064	5.000	5.978	5.792	1.000	1.000
	10.0	7.372	5.000	6.004	5.792	1.000	1.000

cally. This package allows efficiently calculate the steady-state probability vectors in Markovian models and automatically generates more than twenty different performance measures for analyzed linked series queuing network.

4

Tandem as rerouting networks

The same, as in the Section 3, let us consider the Internet two-server tandem shown in figure 2 as the three-station queuing network with blocking. The state diagram of this rerouting network is presented on the Figure 4. Here are shown all possible nonblocked states (marked by ovals) as well as the blocking states (marked by rectangles). Based on an analysis this state space diagrams, the process of constructing the corresponding differential-difference equations, differential equations in t, and difference in (i,j) state, can be divided into several independent steps, which describe some similar, repeatable schemas. These equations are: a) for states without blocking factor:

for states with Main Server blocking:

for i = 1, ... , m1 c) for states with both Internet source and Main Server simultaneous blocking:

e) for states with Second Server blocking:

The solution of these equations for the equilibrium states, if it exists, must satisfy formulas ( 5) and [START_REF] Gemikonakli | Exploring service and buffer management issues to provide integrated voice and data services in single and multichannel wireless networks[END_REF] and this leads to the set of stationary equations. In this case a queuing rerouting network with blocking is formulated as a Markov process and the stationary probability vector can be obtained using numerical methods for linear systems of equations using equations ( 7) -( 11) with ( 5) and ( 6) and dedicated software for the solution of linear systems of equations was created by the author. This soft-ware allows efficiently calculate the steady-state probability vectors and automatically generates more than twenty different performance measures for analyzed queuing network.

Numerical Results

In this section, to demonstrate our analysis of two service strategies in the different Internet two-serves tandem configurations presented in Sections 3 and Section 4, we have performed numerous calculations. We will concentrate on the several important performance descriptors, such as the probabilities that the different tandem configurations are blocked, it means how are blocked separated servers or blocked Internet sources or how are changed various time measures and how are changed buffers filling parameters if the inter-arrival rate λ from the Internet source (users) to tandems are changed within a range from 1.0 to 10.0 per time unit. To demonstrate this, the following tandem parameters were chosen: the service rates in main server and second server are equal to: µ A = 8.0, µ B = 5.0 respectively. The buffer capacities are chosen as equal to: m1 = 40, m2 = 30. The depart probability σ for rerouting tandem configuration is chosen as 0.5 and in this configuration the service rates for main server is chosen as equal to: µ A = 16.0 per time unit. This is necessary for guarantee the same main server utilization parameter, as in the series tandem model. In this case the mean service rate for tandem rerouting model, must be equal to previous service rate divided by depart probability, e.g. µ A / σ. Based on such chosen parameters the following results were obtained and the majority of them are presented in Tables 1, 2 and 3. In all of these tables the columns marked as "italic" contain the results for the first tandem configuration, e.g. the open linked series servers (first service strategy). The columns marked as "bold" contains the results for the second tandem configuration, e.g. the rerouting tandem (second service strategy).

In the first table, the λ is the inter-arrival rate from the Internet source to the both tandems, Idle-s and Idle-r are the idle tandem probabilities for series and rerouting tandems, Bl-M-s and Bl-M-r are the main server blocking probabilities for series and rerouting tandems, Bl-S-s and Bl-S-r are the source blocking probabilities for series and rerouting tandems.


Ireneusz Mrozek
email: i.mrozek@pb.edu.pl

Vyacheslav Yarmolik
email: yarmolik10ru@yahoo.com

Optimal Controlled Random Tests

Keywords: random tests, controlled tests, multi-run tests, Hemming distance, Euclidean distance, pattern sensitive faults, RAM

Controlled random tests, methods of their generation, main criteria used for their synthesis, such as the Hamming distance and the Euclidean distance, as well as their application to the testing of both hardware and software systems are discussed. Available evidences suggest that high computational complexity is one of the main drawbacks of these methods. Therefore we propose a technique to overcome this problem. In the paper we propose the algorithm for optimal controlled random tests generation. Both experimental and analytical investigation clearly show the high efficiency of proposed solution especially for the multi-run tests with small number of iterations. The given tests can be applied for hardware and software testing but it seems they may be particularly interesting from the perspective of the effective detection of pattern sensitive faults in RAMs.

Introduction

It is known that the testing problem is computationally most expensive and mathematically NP-complete [START_REF] Venkatasubramanian | Failures guide probabilistic search for a hard-to-find test[END_REF][START_REF] Fujiwara | The complexity of fault detection problems for combinational logic circuits[END_REF]. The same time the complexity of the modern embedded systems is steadily growing. It is, therefore, important to consider how testing can be performed more effectively.

In case of single hard to detect faults that may have just a handful of unique tests in the entire search space there have been proposed probability based algorithms where new test vectors are generated based on the input probability correlation of previously unsuccessful test vectors [START_REF] Venkatasubramanian | A new test vector search algorithm for a single stuck-at fault using probabilistic correlation[END_REF].

In case of systems with limited number of inputs we can use exhaustive testing. However the exponential growth of the test length restricts the concept of the exhaustive testing to circuits with a limited number of inputs [START_REF] Tang | Exhaustive test pattern generation with constant weight vectors[END_REF].

Locally exhaustive [START_REF] Furuya | A probabilistic approach to locally exhaustive testing[END_REF] or pseudo exhaustive [START_REF] Kuhn | Pseudo-exhaustive testing for software[END_REF][START_REF] Das | Exhaustive and near-exhaustive memory testing techniques and their BIST implementations[END_REF][START_REF] Yarmolik | Iterative near pseudoexhaustive random testing[END_REF] testing is a concept to avoid the restricted number of inputs of the circuit under test. These approaches are the real alternatives to exhaustive testing. They allow for sufficiently reducing the number of the test vectors. It is possible by taking advantage of the fact that often many or all output variables depend only on a small subset of input variables [START_REF] Furuya | A probabilistic approach to locally exhaustive testing[END_REF].

As a good approximation of exhaustive and pseudo exhaustive testing the random testing have been widely used [START_REF] Duran | An evaluation of random testing[END_REF][START_REF] Grindal | Combination testing strategies -a survey[END_REF][START_REF] Seth | A statistical theory of digital circuit testability[END_REF][START_REF] Sosnowski | Experimental evaluation of pseudorandom test effectiveness[END_REF]. The advantages of random testing include its low cost, ease of implementation, ability to generate numerous test cases automatically, generation of test cases in the absence of the object specification and apart from these; it brings randomness into the testing process. Random testing and its variations have been extensively used and studied for both hardware and software systems. Unfortunately random testing is much less effective than other testing techniques such as equivalence partition testing, boundary value analysis testing [START_REF] Reid | An empirical analysis of equivalence partitioning, boundary value analysis and random testing[END_REF].

Standard random testing does not exploit some information that is available in black box testing environment. Therefore controlled approach to random testing (Controlled Random Tests) may be used. One of the approaches for controlled random testing is Antirandom Testing [START_REF] Malaiya | Antirandom testing: Getting the most out of black-box testing[END_REF]. Antirandom Testing is based on various empirical observations showing that many faults result in failures in contiguous areas of the input domain [START_REF] Chen | Adaptive random testing: The art of test case diversity[END_REF]. Therefore one way to improve the failure-detection effectiveness of random testing is somehow taking advantage of this fact. In this case each test vector is chosen such that its total distance from all previous vectors is maximum [START_REF] Malaiya | Antirandom testing: Getting the most out of black-box testing[END_REF][START_REF] Wu | Antirandom testing: a distance-based approach[END_REF]. This approach has proved more efficient than random testing [START_REF] Malaiya | Antirandom testing: Getting the most out of black-box testing[END_REF]. Unfortunately the basic antirandom method essentially requires enumeration of the input space and computation of distances for each potential input vector [START_REF] Malaiya | Antirandom testing: Getting the most out of black-box testing[END_REF]. Therefore many modification of antirandom tests have been proposed [START_REF] Chen | Adaptive random testing: The art of test case diversity[END_REF][START_REF] Wu | Antirandom testing: a distance-based approach[END_REF][START_REF] Feldt | Test set diameter: Quantifying the diversity of sets of test cases[END_REF][START_REF] Choi | Distance-integrated combinatorial testing[END_REF][START_REF] Mrozek | Analysis of multibackground memory testing techniques[END_REF][START_REF] Mrozek | Antirandom test vectors for BIST in hardware/software systems[END_REF][START_REF] Mrozek | Iterative antirandom testing[END_REF][START_REF] Yiunn | Scalable test pattern generation (STPG)[END_REF][START_REF] Zhou | Using coverage information to guide test case selection in adaptive random testing[END_REF][START_REF] Yarmolik | Controlled method of random test synthesis[END_REF]. But even for improved version of the method, very often computations become too expensive for real dimension N of the test vectors [START_REF] Mayrhauser | Fast antirandom (FAR) test generation[END_REF].

In this paper the efficiency of controlled random tests is investigated and validated. Unlike our parallel proposals presented in [START_REF] Mrozek | Method for generating multiple controlled random tests[END_REF][START_REF] Yarmolik | Controlled method of random test synthesis[END_REF] where we focus on multiple controlled random tests consisting of r single controlled random tests, in this paper we investigate a single optimal controlled random test and we present the greedy-like algorithm for its generation. By optimal controlled random test we understand the set of test patterns where each pattern is chosen such that its total distance from all previous patterns is the greatest possible value. So, unlike the known solutions, our approach keeps the distances between the current and previous test patterns as large as possible. All the analytical results are validated through extensive simulation-based experiments. This paper is divided into four more sections. Section 2 provides a brief overview of the principle concept behind Controlled Random Tests. Section 3 highlights the main idea of our algorithm. We analyze and discuss the experimental results in Section 4, and make a conclusion in Section 5.

Controlled Random Tests Investigations

The key feature of controlled random tests generation is the information, which can be obtained from the test and used for test patterns generation. There are numerous different useful approaches which exploited the information from the test itself [START_REF] Malaiya | Antirandom testing: Getting the most out of black-box testing[END_REF][START_REF] Mayrhauser | Fast antirandom (FAR) test generation[END_REF][START_REF] Xu | Orderly random testing for both hardware and software[END_REF]. For all this methods, considering the binary case, the next definitions can be done. Definition 1. Test (T ) is a set of test patterns {T 0 , T 1 , T 2 , . . . , T q-1 }, where T i = t i,N -1 , t i,N -2 , . . . , t i,2 , t i,1 , t i,0 , with t i,l ∈ {0, 1}, and N is the size of patterns in bits. Definition 2. Controlled Random Test T = {T 0 , T 1 , T 2 , . . . , T q-1 } (CRT) is a test with randomly chosen the test patterns T i , i ∈ {0, 1, 2, . . . , q -1}, such that T i satisfies some criterion.

The first formally define approach for controlled random test generation have been presented in [START_REF] Malaiya | Antirandom testing: Getting the most out of black-box testing[END_REF] by Y. Malaiya. The proposed approach was called antirandom testing, since selection of each test explicitly depends on the test patterns already generated. The next formal definition for antirandom tests have been used: Definition 3. Antirandom test (AT) is a test with a test pattern T i , i ∈ {0, 1, 2, . . . , q -1}, is chosen such that it satisfies some criterion with respect to all patterns T 0 , T 1 , T 2 , . . . , T i-1 have been obtained before.

To make each new pattern different compare with previously generated the Hamming and Cartesian distances as the measure of differences have been chosen, which can be defined as [START_REF] Malaiya | Antirandom testing: Getting the most out of black-box testing[END_REF]. Definition 4. The Hamming Distance HD(T i ,T j ) (HD) between two binary vectors T i and T j is calculated as a weight w(T i ⊕ T j ) (number of ones) of vector

T i ⊕ T j . HD(T i , T j ) = w(T i ⊕ T j ) = N -1 l=0 (t i,l ⊕ t j,l ). ( 1
)
Definition 5. The Cartesian Distance CD(T i , T j ) (CD) between two binary vectors T i and T j is given by:

CD(T i , T j ) = (t i,0 -t j,0 ) 2 + (t i,1 -t j,1 ) 2 + . . . + (t i,N -1 -t j,N -1 ) 2 = = |t i,0 -t j,0 | + |t i,1 -t j,1 | + . . . + |t i,N -1 -t j,N -1 | = (2)
= HD(T i , T j ).

The antirandom testing scheme attempts to keep testing procedure as efficient as possible, taking into account the hypothesis that if two patterns have only a small distance between them then the sets of faults encountered by the two patterns is likely to have a number of faults in common. Conversely, if the distance between two patterns is large, then the set of faults detected by one is likely to contain only a few of the faults detected by the other [START_REF] Malaiya | Antirandom testing: Getting the most out of black-box testing[END_REF][START_REF] Wu | Antirandom vs. pseudorandom testing[END_REF]. For the set of more then two test patterns the next definitions have been proposed [START_REF] Malaiya | Antirandom testing: Getting the most out of black-box testing[END_REF].

Definition 6. Total Hamming Distance (THD), Total Cartesian Distance (TCD) for any pattern T i is the sum of its Hamming (Cartesian) distances with respect to all previous patterns T 0 , T 1 , T 2 , . . . , T i-1 .

THD(T i ) = i-1 j=0 HD(T i , T j ), TCD(T i ) = i-1 j=0 CD(T i , T j ). ( 3
)
Definition 7. Maximal Distance Antirandom Test (MDAT) is a test such that each pattern T i is chosen to make the total distance THD or TCD between T i and patterns T 0 , T 1 , T 2 , . . . , T i-1 maximal.

The main properties of MHDAT and MCDAT are the following:

any permutation the patterns bits t i,j within the antirandom test T MHDAT (MCDAT) for all i patterns simultaneously will results in new MHDAT (MCDAT) antirandom test [START_REF] Malaiya | Antirandom testing: Getting the most out of black-box testing[END_REF][START_REF] Wu | Antirandom vs. pseudorandom testing[END_REF],

any MHDAT (MCDAT) will always contain complementary pair of patterns, i.e. T 2k will always be followed by T 2k+1 which is complementary for all bits in T 2k where k = 1, 2, . . . , [START_REF] Malaiya | Antirandom testing: Getting the most out of black-box testing[END_REF][START_REF] Wu | Antirandom vs. pseudorandom testing[END_REF].

Above presented properties allow reducing the complexity of MHDAT (MC-DAT) generation but, for general case, unfortunately the basic antirandom method essentially requires enumeration of the input space and computation of distances for each potential input pattern [START_REF] Malaiya | Antirandom testing: Getting the most out of black-box testing[END_REF][START_REF] Wu | Antirandom vs. pseudorandom testing[END_REF]. Even for improved version of the method computations, it becomes too expensive for real dimension N of the test patterns [START_REF] Wu | Antirandom testing: a distance-based approach[END_REF].

Optimal Controlled Random Test Generation

The key feature of controlled random test generation is the information obtained from the test and used for the current pattern T i generation.

As shown in the previous section, the controlled random tests are generated based on a restricted number of metrics, including the Hamming distance between two patterns T i and T j (HD(T i , T j )), the Cartesian distance (CD(T i , T j )), the total Hamming distance for the next test pattern T i (THD(T i )), the total Cartesian distance (TCD(T i )), the total Hamming distance for the test T (THD(T )), and the total Cartesian distance (TCD(T )) [START_REF] Malaiya | Antirandom testing: Getting the most out of black-box testing[END_REF][START_REF] Xu | Orderly random testing for both hardware and software[END_REF][START_REF] Wu | Antirandom vs. pseudorandom testing[END_REF]. These metrics are used for proposed greedy-like methods of controlled random test generation [START_REF] Malaiya | Antirandom testing: Getting the most out of black-box testing[END_REF][START_REF] Wu | Antirandom testing: a distance-based approach[END_REF][START_REF] Mayrhauser | Fast antirandom (FAR) test generation[END_REF][START_REF] Xu | Orderly random testing for both hardware and software[END_REF][START_REF] Wu | Antirandom vs. pseudorandom testing[END_REF][START_REF] Xu | Maximum distance testing[END_REF]. In all these algorithms, the best immediate, or local, solution has been taken to reach a globally optimal solution. The optimal choice at each stage based on simple metrics has been performed with the hope of finding the global optimum. The greedy-like algorithm was the only solution for controlled random test generation because it is faster than other optimization methods, like dynamic programming for example.

Based on the presented metrics, an optimal controlled random test (OCRT) will be constructed. Step by step, starting from one test pattern T 0 , the consecutive patterns will be selected in terms of adopted earlier metrics according to the greedy-like algorithm.

At the beginning, the first test pattern T 0 is chosen as any arbitrary random N -bit binary vector out of 2 N possible. For example, let T 0 = 000. . .0. This does not result in any loss of generality [START_REF] Malaiya | Antirandom testing: Getting the most out of black-box testing[END_REF][START_REF] Wu | Antirandom testing: a distance-based approach[END_REF][START_REF] Xu | Orderly random testing for both hardware and software[END_REF].

As the second pattern T 1 , according to all metrics, an optimal value is the complement of T 0 , then T 1 = T 0 , and T = {T 0 , T 1 } for the previously adopted example T 1 = 111. . .1. The optimality of this choice is supported by the maximal values of all metrics: HD(T 0 , T 1 ) = THD(T 1 ) = THD(T ) = N , and CD(T 0 , T 1 ) = TCD(T 1 ) = TCD(T ) = √ N . To obtain the third pattern T 2 , the HD(T i , T j ) and CD(T i , T j ) measures cannot be used because the maximization of this value leads to the confusing result that T 2 = T 0 . That is why, in our investigation, both characteristics will not be used. The same conclusion can be made for THD(T i ) and THD(T ). It follows from the fact that for T = {T 0 , T 1 , T 2 }, where T 1 = T 0 , any value of T 2 gives THD(T 2 ) = N and THD(T ) = 2N . It should be noticed that, even in cases T 2 = T 0 and T 2 = T 1 , these metrics have the same values THD(T 2 ) = N and THD(T ) = 2N .

As the candidate for the third optimal pattern T 2 , any pattern that satisfies to the next relations T 2 = T 0 and T 2 = T 1 can be chosen. For example, we take T 2 with HD(T 0 , T 2 ) = Z, then HD(T 1 , T 2 ) = N -Z. For Cartesian functions, the following results are TCD(T

i ) = CD(T 0 , T 2 ) + CD(T 1 , T 2 )= √ Z + √ N -Z, TCD(T )=CD(T 0 , T 1 ) + CD(T 0 , T 2 ) + CD(T 1 , T 2 ) = √ N + √ Z + √ N -Z .
Then, maxTCD(T i ) and maxTCD(T ) can be achieved as the solution Z = N/2 of the equation δ( √ Z + √ N -Z)/δZ = 0. For further investigation, suppose that N is an even number, so that, in our example, the first N/2 bits of pattern T 2 = 000. . .01111 take the value 0, and the rest take value 1.

To summarize the third pattern construction, it is quite important to emphasize that, for our test T = {T 0 , T 1 , T 2 } = {000. . .0, 111. . .1, 000. . .0111. . .1}, the next patterns (fourth, fifth, and so on) should be selected from the set of patterns with the weight w(T i ) = N/2 due to the maximum values of TCD(T 2 ) = 2 N/2 and TCD(T ) = √ N + 2 N/2 for three pattern tests T . In this case, for new consecutive pattern T i , the Hamming distances HD(T i , T 0 ) and HD(T i , T 1 ) have the values N/2, which allow for TCD(T i ) and TCD(T ) maximization.

According to the previous discussion, as the potential fourth pattern, T 3 is the pattern with the weight w(T 3 ) = N/2 and should maximize the value of TCD(T 3 ) and TCD(T ). The obvious solution exists, namely, T 3 = T 2 and for our example T 3 = 111. . .1000. . .0.

The same result can be obtained based on the FAR algorithm [START_REF] Mayrhauser | Fast antirandom (FAR) test generation[END_REF]. According to this algorithm, using three previous patterns T 0 = 000. . .0, T 1 = 111. . .1 and T 2 = 000. . .0111. . .1, a centroid pattern will be obtained C = c N -1 , c N -2 , . . . , c 2 , c 1 , c 0 = 1/3, 1/3, 1/3, . . . , 1/3, 2/3, 2/3, 2/3, . . ., 2/3. Thus, the FAR algorithm creates a binary centroid pattern 000. . . 01111 [START_REF] Mayrhauser | Fast antirandom (FAR) test generation[END_REF]. At the final step of the FAR algorithm, a new anti-random pattern T 3 = 111. . .10000 is constructed by complementing each bit of the binary centroid pattern.

For the pattern T 3 , the total Cartesian distance is TCD(T 3 ) = √ N + 2 N/2 and TCD(T ) = 2 √ N + 4 N/2 for four pattern tests T . This procedure can be generalized for the following steps. At all consecutive stages, the next pattern will be chosen to maximize two metrics TCD(T i ) and TCD(T ). When pattern T i with an even subscript number i ∈ {0, 2, 4, . . . , 2k-2} is chosen, the following relation should be true:

maxTCD(T i ) = i × N/2 maxTCD(T ) = (i/2) × √ N + (i 2 /2) × N/2. ( 4
)
The pattern with the even subscript i is chosen so that HD(T i , T j ) = N/2 between pattern T i and all previous patterns T j , j < i. The pattern with an odd subscript i ∈ {1, 3, . . . , 2k -1} is the complement value of the previous pattern with an even subscript (i.e., T i = T i-1 ). Then, both metrics are

maxTCD(T i ) = √ N + (i -1) × N/2 maxTCD(T ) = ((i + 1)/2) × √ N + ((i 2 -1)/2) × N/2. (5)
As an example, we take N = 2 m , then the number q of patterns within the OCRT T = {T 0 , T 1 , T 2 , . . . T q-1 } equals 2(m + 1). For m = 3, OCRT consisting of 2(m + 1) = 2(3 + 1) = 8 patterns with both metrics (maxTCD(T i ) and maxTCD(T ) are presented in Table 1.

Table 1: Optimal controlled random test for q = 8.

Ti ti,7 ti,6 ti,5 ti,4 ti,3 ti,2 ti,1 ti,0 maxTCD(Ti) maxTCD(T ) T0 0 0 0 0 0 0 0 0 --

T1 1 1 1 1 1 1 1 1 √ 8 √ 8 T2 0 0 0 0 1 1 1 1 2 √ 4 √ 8 + 2 √ 4 T3 1 1 1 1 0 0 0 0 √ 8 + 2 √ 4 2 √ 8 + 4 √ 4 T4 0 0 1 1 0 0 1 1 4 √ 4 2 √ 8 + 8 √ 4 T5 1 1 0 0 1 1 0 0 √ 8 + 4 √ 4 3 √ 8 + 12 √ 4 T6 0 1 0 1 0 1 0 1 6 √ 4 3 √ 8 + 18 √ 4 T7 1 0 1 0 1 0 1 0 √ 8 + 6 √ 4 4 √ 8 + 24 √ 4
For the general case, the number OCRT patterns is calculated as q = 2(⌈log 2 N ⌉+ 1), and the constructive algorithm for pattern generation is presented in [START_REF] Das | Exhaustive and near-exhaustive memory testing techniques and their BIST implementations[END_REF].

The presented procedure of OCRT construction, based on the greedy-like algorithm, is the best solution that can be obtained according to the procedure of all known algorithms for controlled random test generation, namely, anti-random test generation [START_REF] Malaiya | Antirandom testing: Getting the most out of black-box testing[END_REF], fast anti-random test generation [START_REF] Mayrhauser | Fast antirandom (FAR) test generation[END_REF], orderly random test construction [START_REF] Xu | Orderly random testing for both hardware and software[END_REF], and numerous modifications, like the maximal distance antirandom test, maximal Hamming distance test, and so on.

To summarize, the optimal controlled random test generation (Algorithm 1) for construction of OCRT for N = 2 m is proposed. By optimal controlled random test we understand the set of test patterns where each pattern is chosen such that its total distance (TCD(T i ) and TCD(T )) from all previous patterns is the greatest possible value. ALGORITHM 1: Construction of OCRT for N = 2 m 1. Initial matrix M with N columns and q = 2(m + 1) rows should be constructed based on the trivial divide and conquer algorithm [START_REF] Knuth | The art of computer programming[END_REF]. The first row M0 takes the value with N zeros, and the second row (M1) is all ones. The consecutive rows with even subscripts i > 0 are the set of even number blocks, where half are all zero blocks and another half are all blocks with one. The next row with an odd subscript is the negation of the previous row with an even subscript (e.g., M1 is complement of M0). On each iteration of this algorithm, the current row of matrix M with an even subscript is constructed from the previous row with an even subscript, so that all its blocks are divided into two equal blocks, when the first new block is all zeros and the second is all ones. 2. Based on some permutations, the algorithm conducts column reordering for matrix M to obtain matrix M * , which is called a mask vector matrix. 3. Randomly chosen N bits pattern P out of 2 N possible patterns is regarded as the first pattern T0 = P . 4. Each new i-th pattern T1, T2, T3, . . . , T2m+1 is the bit-wise exclusive or sum Ti = P M * i .

Repeat

Step 4 until all 2(m + 1) patterns have been constructed.

It should be mentioned that column reordering for any matrix does not change the value of the Hamming distance between any two rows (patterns), which follows from the equation (1). We consider the random matrix M with three rows and four columns and the matrix M 1 * that is obtained by column reordering from the matrix M .

M C 1 C 2 C 3 C 4 T 0 0 0 1 0 T 1 1 0 0 1 T 2 1 1 0 0 M 1 * C 3 C 4 C 1 C 2 T 0 * 1 0 0 0 T 1 * 0 1 1 0 T 2 * 0 0 1 1
We notice that the value of the Hamming distance between any two rows of matrix M equals the distance between corresponding rows of matrix M 1 * :

HD(T 0 , T 1 ) = HD(T 0 * , T 1 * ) = 3, HD(T 0 , T 2 ) = HD(T 0 * , T 2 * ) = 3 HD(T 1 , T 2 ) = HD(T 1 * , T 2 * ) = 2.
The same observation can be made for the operation used in Step 4 of Algorithm 1. Let us again consider the random matrix M , the random pattern T r , and the matrix M 2 * , where each row is bit-wise exclusive of the corresponding row of matrix M and pattern T .

M C 1 C 2 C 3 C 4 T 0 0 0 1 0 T 1 1 0 0 1 T 2 1 1 0 0 T r = 1 0 1 1 M 2 * C 1 * C 2 * C 3 * C 4 * T 0 * 1 0 0 1 T 1 * 0 0 1 0 T 2 * 0 1 1 1
We again notice that the value of the Hamming distance between any two rows of matrix M equals the distance between the corresponding rows of matrix M 2 * :

HD(T 0 , T 1 ) = HD(T 0 * , T 1 * ) = 3, HD(T 0 , T 2 ) = HD(T 0 * , T 2 * ) = 3 HD(T 1 , T 2 ) = HD(T 1 * , T 2 * ) = 2.
We conclude that Steps 2-4 of the Algorithm 1 do not affect the main characteristic of the test patterns generated in Step 1. However, at the same time, the above steps allow us to generate different sets of test patterns characterized by maximum distances between the patterns. We can use those patterns to effectively detect different sorts of faults, for example, pattern sensitive faults in RAM. Now, as an example, we generate OCRT for N = 2 m = 2 3 using Algorithm 1, Example 3.1. OCRT generating for N = 2 m = 2 3 1. Initial matrix M with N = 8 columns and q = 8 rows is constructed, so that M 0 = 00000000 and M 1 = 11111111. The new M 2 row is obtained from M 0 by the dividing it on two blocks: one with all zero code and the second with all ones, where M 3 is the complement value of M 2 , The next rows of matrices M (M 4 , ..., M 7 ) are obtained in the same way (see Table 1). 2. Mask vector matrices M * , as a result of column reordering of M (Table 1) are presented in Table 2. 3. If the randomly chosen N = 8-bit pattern is P = 01111010, then T 0 = P = 01111010. 4. Each new i-th pattern T 1 , T 2 , T 3 , . . . , T 7 is the bit-wise exclusive or sum T i = P ⊕ M * i , where M * i is taken from Table 2. 5. All q = 2(m + 1) = 8 patterns for OCRT are presented in Table 3 with the corresponding values of the metrics. M * i ti,2 ti,6 ti,1 ti,4 ti,3 ti,7 ti,5 ti,0 M * 0 0 0 0 0 0 0 0 0

M * 1 1 1 1 1 1 1 1 1 M * 2 1 0 1 0 1 0 0 1 M * 3 0 1 0 1 0 1 1 0 M * 4 0 0 1 1 0 0 1 1 M * 5 1 1 0 0 1 1 0 0 M * 6 1 1 0 1 0 0 0 1 M * 7 0 0 1 0 1 1 1 0
Table 3: OCRT patterns for m = 3

Ti ti,7 ti,6 ti,5 ti,4 ti,3 ti,2 ti,1 ti,0 maxTCD(Ti) maxTCD(T )

T0 0 1 1 1 1 0 1 0 - - T1 1 0 0 0 0 1 0 1 √ 8 √ 8 T2 1 1 0 1 0 0 1 1 2 √ 4 √ 8 + 2 √ 4 T3 0 0 1 0 1 1 0 0 √ 8 + 2 √ 4 2 √ 8 + 4 √ 4 T4 0 1 0 0 1 0 0 1 4 √ 4 2 √ 8 + 8 √ 4 T5 1 0 1 1 0 1 1 0 √ 8 + 4 √ 4 3 √ 8 + 12 √ 4 T6 1 0 1 0 1 0 1 1 6 √ 4 3 √ 8 + 18 √ 4 T7 0 1 0 1 0 1 0 0 √ 8 + 6 √ 4 4 √ 8 + 24 √ 4
The brief analyses demonstrate that the presented procedure can construct a set of OCRT depending on the initial pattern P . For the general case, the number of OCRT patterns is calculated as q = 2(⌈log 2 N ⌉+1), and the algorithm for OCRT pattern generation is slightly different for the mask vector matrix generation. The proposed algorithm seems to be efficient in terms of computation complexity. For any value of N , the most difficult procedure is the mask vector matrix (M ) generation and performing column reordering to obtain M * . Indeed, increasing N by two times needs only two additional rows for M . Then, the new M is constructed so that all N -bit rows for the previous M are extended to 2N bits using the simple doubling of all blocks with the same values 0 or 1 and adding two final rows M 2m-2 = 010101. . .01 and M 2m-1 = 101010. . .10.

Experimental results

Finally, to confirm the proposed solution we have compared the coverage of several controlled random tests strategy (OCRT, pure antirandom tests [START_REF] Malaiya | Antirandom testing: Getting the most out of black-box testing[END_REF], concatenated antirandom tests [START_REF] Malaiya | Antirandom testing: Getting the most out of black-box testing[END_REF], STPG [START_REF] Yiunn | Scalable test pattern generation (STPG)[END_REF]) and random one in terms of number of generated binary combinations for all arbitrary k out of N bits. Using different methods, we had generated test sets consisting of eight test patterns and then we compared their coverage with each other. In the case of pure antirandom tests T HD was used as a fitness function whilst concatenated antirandom vectors were employed from Example 7 in [START_REF] Malaiya | Antirandom testing: Getting the most out of black-box testing[END_REF]. Due to the fact that the authors of STPG algorithm have not indicated how to determine the adding factors [START_REF] Yiunn | Scalable test pattern generation (STPG)[END_REF], a random value was used. The experiments have been done for k = 3 and k = 4. The obtained results are shown in the Figure 1a the number of the test patterns, and the y-axis -the number (in percent) of binary combinations for all arbitrary k = 3 and k=4 out of N = 64 bits. For Fig. 1, we observe that all coverages curves rise sharply and them exhibits a smooth behavior. We observe high efficiency of OCRT especially for the first few patterns of the test. At the end of the test process OCRT gives us the same or slightly lower (see Fig. 1b) level of fault coverage as in case of pure antirandom patterns. The same time we should noted that OCRT is characterized by easier computational method in compare to other analyzed techniques. Most known antirandom techniques still need a lot of resources (strong CPU for computation of distances between vectors, additional memory to collect generated vectors, etc) that may be unavailable in case of embedded systems and BIST technique.

Conclusions

In the paper a new approach called as Optimal Controlled Random Test has been introduced. It uses previously adopted metrics attempting to make all known Greedy like controlled random testing more effective. Unlike the known solutions the new approach keeps the distances TCD(T i ) and TCD(T ) as large as possible. Both experimental and analytical investigation clearly show the high efficiency of proposed solution especially for the first few iterations of the multirun test. However the OCRT has an obvious advantageous compare with all known methods. It is more efficient in terms of computation complexity.

Fig. 1 :

 1 Fig. 1: The coverage of all arbitrary k out of N bits for different antirandom test schemes: a) k=3 and N =64, b) k=4 and N =64

Table 2 :

 2 Masks vector matrices M * for m = 3

This paper was supported by grant S/WI/3/13 from Faculty of Computer Science at