Linear Time-Varying (Max,+) Representation of Conflicting Timed Event Graphs

Keywords: Timed Event Graph, (Max, +) algebra, Conflict, Linear-Time Varying Systems, Repetitive Systems

Timed Event Graphs (TEGs) are a specific class of Petri nets that have been thoroughly studied given their useful linear state representation in (Max,+) algebra. Unfortunately, TEGs are generally not suitable for modeling systems displaying resources sharing (or conflicts). In this paper, we show that if a system with conflicts is modeled using an extended class of TEGs: Conflicting Timed Event Graphs (CTEGs), then it is quite possible to obtain an equivalent (Max,+) representation. More precisely, we prove that the evolution of a CTEG satisfies linear time-varying (Max,+) equations. In case of cyclic CTEGs, which are a natural model of many repetitive systems, we provide a standard timeinvariant (Max,+) representation. Finally, a practical example (a Jobshop) is used for illustration to exhibit the interest of this investigation.

INTRODUCTION

Petri nets are a powerful tool for discrete events systems modeling and analysis. They are often used to represent phenomena like synchronization, parallelism and concurrency [START_REF] Murata | Petri nets: properties analysis and applications[END_REF]. Their domain of application is very large, including manufacturing systems, communication systems, transportation, etc. Many classes of Petri nets with more or less elaborated semantics are used according to the context of the study. Generally speaking, the more their structure and semantics are elaborated the more complex is their study. The relatively simple class of Petri nets called Timed Event Graphs (TEGs) is then the most investigated one. Indeed, TEGs are easily represented in the form of linear equations in (Max,+) algebra provided that the places and the transitions be overtaking free (FIFO places and FIFO transitions as defined in [START_REF] Baccelli | Synchronization and linearity: an algebra for discrete event systems[END_REF]. This linear (Max,+) form being very similar to the state representation of the classical discrete linear systems, the main related results are mostly straightforwardly applied [START_REF] Cohen | Max plus algebra and systems theory: where we are and where to go now[END_REF]. Unfortunately, TEGs are Petri nets with places displaying at most one upstream transition and one downstream transition. Thus, they are not suitable for modeling systems with resources sharing or conflicts. Note nonetheless that some particular systems involving shared resources (e.g. flowshops), can be modelled using TEGs with time-varying parameters [START_REF] Lahaye | Linear periodic systems over dioids[END_REF]. The authors had however to change the usual FIFO rule to prevent tokens from overtaking and finally to get to linear (Max,+) equations. Such a consideration is possible in some cases but it is unfortunately not always the case. In literature, a number of other efforts have been undertaken to tackle differently the problem of conflicts. The authors in [START_REF] Hillion | Performance evaluation of jobshop systems using timed event graphs[END_REF] investigated the problem of repetitive systems i.e. with a cyclic allocation of the shared resources. They proposed to transform the original Petri net with conflicts into a TEG, the (Max,+) representation of this latter being easily obtained. In [START_REF] Gaubert | Modeling and analysis of timed Petri nets using heaps of pieces[END_REF], an algebraic modeling, based on the heaps-ofpieces theory and (Max,+) automata, is provided for safe Petri nets. For the case of Free Choice Petri nets, a very complete analytic study is proposed in [START_REF] Baccelli | Free choice Petri nets: an algebraic approach[END_REF]. The case of processes that switch between different functioning modes is investigated in [START_REF] Van Den Boom | Modeling and control of discrete event systems using switching Max-Plus linear systems[END_REF] using switching (Max,+) linear systems. We can also quote Correïa et al. (2009) where local (Max,+) equations are written without taking into account the conflicts. A constraint (inequality) is then added to represent only the admissible evolutions of the global system. In Naït et al. (2006), a method introducing the concept of virtual firing of transitions is proposed for a transportation system. More recently [START_REF] Boutin | Modeling systems with periodic routing functions in dioid (Min,+)[END_REF], an approach based on the dioid of intervals is used to represent extreme behaviors of a manufacturing system (with shared resources i.e. conflicts context) and provide the bounds of its production rate.

In this paper, we propose a novel approach to model a large category of systems involving shared resources. The main idea of our work has been first introduced in [START_REF] Addad | Modélisation de réseaux de graphes d'événement temporisés avec conflits dans l'algèbre (Max,+)[END_REF] but has been limited to systems with one shared resource. In this paper, we present a generalization of this approach and consider systems with multiple resources. The purpose of the study is to extend the use of (Max,+) algebra to a class of Petri nets larger than TEGs: Conflicting Timed Event Graphs (CTEGs). Moreover, some of the previously exposed hypotheses in the existing works are relaxed:

i) the TEGs that constitute the CTEG are not necessarily safe (they, by the way, display input transitions).

ii) the conflicting transitions can have more than one upstream place (unlike Free Choice Petri nets).

iii) resources allocation policy is not necessarily cyclic. The remainder of this paper is organized as follows: Section 2 recalls some basic notions about TEGs and their linear (Max,+) representation. Section 3 is dedicated to the study of CTEGs in (Max,+) algebra: Section 3.1 introduces some definitions and notations with regard to CTEGs and Section 3.2 presents their modeling using (Max,+) equations. Thereafter, a linear time-varying reformulation is provided in Section 4. Hence, a standard time-invariant linear state form is provided for cyclic CTEGs in Section 5. Finally, Section 6 concludes this paper with some outlooks for future work.

LINEAR (MAX,+) EQUATIONS OF TEGs

In this section, we recall the linear (Max,+) representation of TEGs that will be useful in the sequel of this paper. Note that a mix of timed places and timed transitions is considered in our study and if their delays are not précised, then they are null. Let's consider the simple example below (t-timed):

G 4 1 2 t 1 t u t G 4 1 2 t 1 t u t Fig. 1. Example of TEG. Let ( ) i x k ( ) i t 1 2 1
( ) 1 max( ( ), ( 1)) ( ) 4 ( )

x k u k x k x k x k = + - ⎧ ⎨ = + ⎩
(resp. u k ) be the date of firing transition (resp. ) for the time. If firing is performed at maximal speed (as soon as possible), we can write the equations:

u t th k 2 (1)
The equations above can be rewritten using (Max,+) algebra operators: the maximum noted ⊕ and addition noted ⊗ . These operators are defined on the set and have respectively

max { } = ∪ -∞ ε = -∞ 1 2 1 ( ) 1 ( ) 1 ( 1) ( ) 4 ( ) x k u k x k x k x k = ⊗ ⊕ ⊗ - ⎧ ⎨ = ⊗ ⎩ ˆ( ) ( ) (
and as identity elements. Equations (1) become:

0 e = 2 1) ( ) (2)
Using a matrix notation, we finally get to:

X k A X k A X k ′ = ⊗ ⊕ ⊗ - B U k ⊕ ⊗
(3) with:

( )

1 2 t X x x = = 4 Â ,U u, ε ε ε ⎛ ⎞ = ⎜ ⎟ ⎝ ⎠ 1 Â ε , ε ε ⎛ ⎞ ′ = ⎜ ⎟ ⎝ ⎠ 1 B , ε ⎛ ⎞ = ⎜ ⎟ ⎝ ⎠ .
Equation (3) can also be brought to an explicit form thanks to the following theorem:

Theorem 2.1 [START_REF] Baccelli | Synchronization and linearity: an algebra for discrete event systems[END_REF]): The minimal solution of equation:

X A X B = ⊗ ⊕ max n n A × ∈ max n m B with , × ∈ is: * X A B = ⊗ * i i with A A ∈ = ⊕
being the Kleene star of A .

By applying the previous theorem to equations (3), we get to the following explicit form:

( ) ( 1) ( ) X k A X k B U k = ⊗ -⊕ ⊗ (4) with: * 4 ˆe e A ε ⎛ ⎞ = ⎜ ⎟ ⎝ ⎠ , , and . * 1 5 ˆÂ A A ε ε ⎛ ′ = ⋅ = ⎜ ⎝ ⎠ ⎞ ⎟ * 1 5 ˆB A B ⎛ ⎞ = ⋅ = ⎜ ⎟ ⎝ ⎠
Remark 2.1: Equation (3) and its explicit form (4) feature every TEG. It is a standard state representation like the classical representation of linear systems. Thus, it is widely used alike to solve many problems of performance evaluation or control synthesis [START_REF] Cohen | Max plus algebra and systems theory: where we are and where to go now[END_REF].

MODELING CTEGs IN (MAX,+) ALGEBRA

Definitions and notations

A net of Conflicting Timed Event Graphs or CTEG is a set of TEGs noted = G G G G 1 2 { , , , } N = i R
(e.g. products, jobs, users…) connected to each other by a set of conflict places (e.g. shared resources) noted . Each

timed event graph G i is connected to a subset of conflict places (or resources) noted ( ). With place 1 2 { , , , } M R p p p i R R ⊆ j i p R
∈ , we get the generic structure of CTEG on Fig. 2(a): For the sake of simplicity, we will adopt the following hypotheses and notations:

4 1 1 t 1 1 1 t G2 1 p 2 3 j p G i j i t j i t j τ j i τ 1 2 t 1 2 t G1 5 ( ) a ( ) b 4 1 1 t 1 1 1 t G2 1 p 2 3 j p G i j i t j i t j τ j i τ 1 2 t 1 2 t G1 5 ( ) a ( ) b
-H1) the unique transition of G i upstream place j p is noted j i t and the unique downstream transition is noted j i t (Fig. 2(a)). We suppose also, without loss of generality (since we can always get to this case by duplicating the transition j i t ) that j i t has a unique upstream place of conflict j p .

-H2) a shared resource is used by at most one user at a time. So, in terms of Petri nets, each circuit j j i i ji t t p t j is safe and the sum of markings of all the circuits involving a place -H4) each TEG G i is alive, represented by its state form:

ˆˆ( ) ( ) ( 1) ( ) i i i i i i i i i i i X k A X k A X k B U k ′ = ⊗ ⊕ ⊗ -⊕ ⊗ (5)
where:

( )

1 2 i t n i i i i X x x x = 1 i n × is an state vector and
(

1 2 i t m i i i i U u u u =
) is an input vector. In the remaining of this study, the row of a matrix

1 i m × th i A is denoted ( , :) A i th j
whereas the intersection element of the row and the column is denoted th i ( , ) A i j .

CTEG modeling using (Max,+) equations

In studying TEGs, daters are usually associated to the transitions. In our approach however, we also associate a dater to the token of every place of conflict . The date of availability of this token for the

j p R ∈ th j l time is denoted ( ) j j l ψ
. Intuitively, this is the date of availability of the shared resource j p after being used j l th i k times.

Let's suppose that every transition of TEG G i has already fired times. To fire for the time, each transition needs all its upstream places to have at least one available token. So, a conflicting transition

( 1) i k - j i
t needs the token of its upstream place of conflict j p to be available too. Suppose that the token of this place is attributed effectively to G i when it is available for the th j l time. If j i x is the dater of vector i X associated to transition

j i t ˆ( ) ( ,:) ( ) ˆ( ,:) ( ) j i i i i i j i i i i x k A j X k B j U k τ ψ = ⊗ ⊕ ⊗ ⊕ '
, then we can write:

( ,:)

( ) i j A j l ( i i j X k ⊗ 1) - ′ ⊕ ⊗ (6)
Equation ( 6) is written for every dater associated to a transition downstream a place of conflict belonging to .

The other daters i R j i

x however, whose transitions are not downstream places of conflict, are unchanged in (5) since they do not depend directly on ( )

j j l ψ ',:) X ⊗ ( ) i i j j X k l
. So, we have:

(7)
By combining ( 6) and ( 7), we get to the new state form:

(8)

' ( ) ( ',:) ( ) ˆ( ',:) ( )

j i i i i i i i i x k A j X k B j U k = ⊗ ⊕ ⊗ ( ) ( ) ˆ( ) j i i i i i i i i i p R X k A X k B U k F ∈ = ⊗ ⊕ ⊗ ⊕ ⊕ ( ) ˆ( i A j ′ ⊕ i A ψ ′ ⊗ ⊗ ( 1) i i k 1) ⊕ - - ˆˆ( i j
with all the involved matrices and vectors are exactly the same as in (5). The only new elements are the availability dates j j l ψ defined previously and matrices ˆij F . We can note that the components of the matrix 1 By applying Theorem 2.1 to (8), we finally obtain:

( ) ( 1)
i i i i ( ) i i ( j i j j p R i ij X k A X k = ⊗ - * ˆî i i B U k F ψ ⊗ l ∈ ⊕ ⊗ ⊕ ⊕ (9)
where: A A A′ = ⊗ , and

* î i B A = ˆi B ⊗ * îj i ˆij F A F ⊗ = .
On the other hand, since the token of j p is consumed by

G i (or j i t )
j j j i i k ) l x ⊗ ψ τ + = (10)
This equation can be rewritten as:

( 1) (

j j i j i l G X i k ψ + = ⊗ (11) with is a 1 ij G i n ×
matrix whose all components are null except for one (equal to j τ ) corresponding to transition j i t .

To sum up, if the th j l token of j p th contributes to firing the transitions of TEG G i for the time (note that because of resources invariance we have:

), then the following recurrent (max,+) equations are verified:

i k ( 1 j i j i p R l k ∈ = ∑ ) - ( ) ( 1) ( ) ( )
( 1) ( )

j i i i i i i i i i ij j j p R j j ij i i j i X k A X k B U k F l l G X k fo ral l p R ψ ψ ∈ ⎧ = ⊗ -⊕ ⊗ ⊕ ⊗ ⎪ ⎨ ⎪ + = ⊗ ∈ ⎩ ⊕ (12)
As can be seen, equations ( 12) include a parameter, j l in ( )

j j l ψ
, that defines entirely the policy of resources allocation.

Hence, these equations represent all the admissible evolutions of CTEGs. All the involved elements are systematically calculated according to the method explained before. These equations are important and will be the cornerstone of all the results provided later in this paper.

Example 3.1: to illustrate the previous method, let us consider the following example (note that if the holding time or firing time is not mentioned, then it is equal to 0):

G2 1 1 2 t 2 2 2 t G1 5 2 1 t 3 1 1 t 2 p 1 p 1 u t 1 4 G2 1 1 2 t 2 2 2 t G1 5 2 1 t 3 1 1 t 2 p 1 p 1 u t 1 4
Fig. 3. A CTEG with two conflict places shared by two TEGs (note that in this example

j j i i t t ≡ , i j ∀
).

By assigning daters 1

1 x , 2 1 x , 1 2
x and 2 2

x to transitions , , and , G 1 (without conflicts) is represented by equations:

1 1 t 2 1 t 1 2 t 2 2 t ( ) x k G 1 : 1 2 x 1 1 1 1 1 1 2 1 1 1 1 1 3 ( ( ) 5 ( ) u k x k x k ⎧ (k ) 3 1) = ⊗ ⊕ ⊗ - ⎪ ⎨ = ⊗ ⎪ ⎩ (13)
Now, let's take into account the places of conflict. If the token of (available for the time) and the token of (available for the time) are attributed to G 1 to enable its transitions to fire for the time, then we have:

2 th l 1 1 1 1 ) ( ) ( 1 th k 1 2 1 2 5 , 1 1 1 1 1 1 2 1 1 1 1 2 2 1 1 1 2 1 1 ( ) 3 ( 3 ( 1) 3 ( ) ( ) 5 ( ) ( 1) 4 ) ( 1) 1 ( ) 2 x k u x k x k x l l x l x ψ ⎧ = ⊗ -⊕ ⊗ ⎪ = ⊗ ⎨ ⎪ + = ⊗ + = ⊗ ⎩ k k ⊕ ⊕ 1 B = l k k ψ ψ ψ ⊗ ⊗ 3 8 ⎛ ⎞ ⎜ ⎟ ⎝ ⎠ (14)
These equations are easily brought to form (12). We let the reader write the equations relative to G 2 and get to (12) with:

1 3 8 A ε ε ⎛ ⎞ = ⎜ ⎟ ⎝ ⎠ , , 2 3 2 A ε ε ⎛ ⎞ = ⎜ ⎟ ⎝ ⎠ , 2 B ε ε ⎛ ⎞ = ⎜ ⎟ ⎝ ⎠ , , , ( 11 3 8
t F = ) ( ) 5 t ε 12 F = ( ) 11 4 G ε = , ( ) 12 1 ε = G , ( )
21 1 t F ε = , , G
( )

3 2 t 22 = F ( ) 21 4 ε = , G .
( )

1 ε 22 =
Note that all these matrices are constant and independent of resources allocation policy.

LINEAR TIME-VARYING (MAX,+) EQUATIONS OF CTEGs

Let's recall that a linear time-varying system is of the form:

( ) ( 1) ( ) ( ) ( 1) X k A k B k U k = - ⊕ ⊗ X ⊗ k- ( 15
) This equation would be more suitable than form (12) for most problems resolution. So, one can ask question: is it possible to bring form (12) to form (15)? Answering this question is indeed crucial since modeling many existing systems using CTEGs is quite easy (e.g. the TEGs are products and the conflict places are machines) but obtaining directly (15) is not so obvious for some reasons exposed later (Remark 4.1).

Definitions

-D1) In practice, resources are usually allocated according to a sequence (periodic or not). So, we say that a CTEG evolves

according to sequence σ - G G G G 1 2
( 1) j j j k jk = (this does not sweep all admissible evolutions of CTEGs), if for each resource represented by j p and shared between two TEGs and G , the token of

G jk + ( j k ) q j p ) k
is first attributed to G and subsequently to for all , . We therefore say that the realization of sequence

jk + G ( j k q 1 ≥ 1 q ≥ th k σ is TEG G i if: = G G i . jk Example 4.1: , , , , 1 2 , p 3 } p 1 1 3 { , } R p p = 2 2 3 { , } R p p = { , } R p p = { , R p = 3 1 2 σ = G , } G G G 1 2 2 N G G G G G 1 3 3 3 2 1 1 ( p R R ∈ ∩ {1, 2, S= 1 3 )
. According to this sequence, the token of is to be attributed Fre ( p ,i ,k ) provides the index of the TEG that frees resource j p th i to be used by G i for the k time. Example 4.1 (continued): Let's return to example 4.1 and build the following table to explain this function (a cross in a box of the row of

σ = G 1 G 2 G 2 G 1 G 3 G 3 G 3 G 2 G 1 1 p x x x x x x 2 p x x x x x x 3 p x x x x x x
The arrows in the table simplify the following samples: and3 2 3 1 Fre ( p , , ) = . For instance 3 2 3 1 Fre ( p , , ) = means that G 1 frees to be used by G 2 for the 3 rd time.

1 1 2 1 Fre ( p , , ) = , , 2 2 3 3 Fre ( p , , ) = 3 2 2 2 Fre ( p , , ) = ,
- = G G G G 1 2 ( 1) j j j k jk
, has an equivalent Linear Time-Varying (Max,+) representation.

Proof: Let's suppose that a CTEG verifies the hypotheses of Section 3.1 and evolves according to a sequence σ . So, we can write, from 1 st equation in ( 12), the following form: ( )

j i i i i i i i i i ij j j p R X k A X k B U k F l ψ ∈ = ⊗ -⊕ ⊗ ⊕ ⊗ ⊕ ( 1) ( ) ( )
Also, using the 2 nd equation in ( 12) and function Fre we get:

(

j i j i j i j j Fre p i k j Fre p i k Fre p i k l G X k ψ = ⊗ - , , ) ( , , ) ( , , ) ( ) ( 1)
So, by replacing ( 17) in ( 16), we

( j i j i j i j i i i i i i i i i ij Fre p i k j Fre p i k Fre p i k p R X k A X k B U k F G X k ∈ = ⊗ -⊕ ⊗ ⊕ 1 ) ⊗ ⊗ - ⊕ obtain: ( , , ) ( , , ) ( , , ) ( ) ( 1) ( )
Let us define the

1 i n ∑ × (resp. ) vector 1 i m ∑ × ( ) X k (resp.
( ) U k ) that contains all the state vectors (resp. input vectors) of all TEGs at the ( realization of sequence 1) th k σ :

( )

1 1 2 2 (k ( 1) ( ( 1) t N N X k X k X k -= - 1) X - 1) - and
( )

1 1 2 2 (k ( 1) ( ( 1) t N N U k U k U k -= - 1) U - 1 ) 1) - where: 1 1 ( N p p k k = -= - ∑ . If the realization of th k σ is TEG G i ,
then we also (according to the previous definition) have:

( )

1) t - 1 1 ( ) ( 1 ) ( N N X k X k X k = - 2 ) ( X k 2 1) - ( i i X k
Using (18), we can therefore deduce that:

( ) ( 1) ( 1) ( ) ( ) X k A k X k B k U k = -⊗ -⊕ ⊗ (19)
where the components of ( 1) A kand ( ) B k are defined as:

( , , ) ( , , ) ( ) ( ) ( )
( 1)( , )

j i j i d i i j i j Fre p i k i ij qj Fre p i k q if p q and p i if p q i if p i and q i otherwise I A F G A k p q F G I ε = = = ≠ = = = ≠ ⎧ ⎪ ⊕ ⊗ ⎪ ⎪ - = ⎨ ⊗ ⎪ ⎪ ⎪ ⎩ ⊕ ⊕ (20) ( ) ( )( , ) i B if p q i B k p q I otherwise ε = = ⎧ = ⎨ ⎩ (21)
Obviously, ( 19) is a linear time-varying (Max,+) system. □ Note that ( 1)( , ) A k p q and ( )( , ) B k p q are not scalars but matrices. They are multiplied by the elements of X and U j p and column of

G i means j i p R ∈ ):
which are vectors. The p q n n × matrix d I (resp. I ε ) in ( 20) and ( 21) is the identity (resp. null) matrix.

Remark 4.1: It could be thought that since we can represent a system using a CTEG and subsequently equations ( 19), then why not do it from the beginning without passing through the CTEG modeling? Indeed, equations ( 19) might represent a TEG (with time-varying parameters nevertheless), equivalent to the CTEG. However, if we look closely at matrix ( )

A k , we will notice that some of its components are, over time, sometimes null (equals ε ) and sometimes not.

This means literally that some places of the TEG sometimes exist and sometimes disappear. This is obviously not a usual feature with regard to Petri nets and therefore not a natural modeling of systems (see Example 5.1).

(MAX,+) EQUATIONS OF CYCLIC CTEGs

Equation ( 19) can be obtained whatever is the CTEG evolution sequence. In practice nonetheless, many systems are repetitive and evolve according to a periodic sequence of the form 0 0 0 σ σ σ σ = where 0 σ is the basic sequence to be repeated. Let's suppose:

σ - = G j j G G 0 1 2 jT T G (
( ) ( ) A k T k + = A and ( ) T + = ( B k) B k
. Hence, we can apply a well known result in conventional theory related to periodic linear systems [START_REF] Bolzern | Zeros of discrete time linear periodic systems[END_REF]), [START_REF] Misra | Time-Invariant representation of discrete periodic systems[END_REF] and similarly used in (Max,+) algebra [START_REF] Lahaye | Linear periodic systems over dioids[END_REF]). This result is a transformation of a periodic timevarying linear system into an invariant-time one using the notion of monodromy. Let's define the transition matrix relative to matrix A as:

1 ≥ )= Φ 0 d if q = eriodic - ( 1) ( 2) ) ( , ) if q A i A i A i i i q I ⎧ -⊗ -⊗ ⎪ Φ -= ⎨ ( q - i T + ⎪ ⎩ .
Fig. 6. A CTEG model of a manufacturing system (jobshop) involving three machines producing three types of parts.

Let us associate daters 1 1

x , 2 1

x , 3 1

x to transitions , , and availability dates

1 1 t 2 1 t 3 1 t 1 ψ , 2
ψ , 3 ψ to the tokens of places , and . So, we can write:

1 p 2 p 3 p 1 3 1 1 1 1 1 1 2 1 1 1 2 2 1 1 3 2 1 1 3 3 1 1 ( ) 1 [ ( 1) ( )] ( ) 3 [ ( ) ( )] ( ) 3 [ ( ) ( )] x k x k x k l x k x k l x k ψ ψ ψ ⎧ = ⊗ -⊕ ⎪ ⎪ = ⊗ ⊕ ⎨ ⎪ = ⊗ ⊕ ⎪ ⎩ l ,
The equations above can be brought to form (12) with:

1 1 4 7 A ε ε ε ε ε ε ⎛ ⎞ ⎜ ⎟ = ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ , , 11 1 4 7 F ⎛ ⎞ ⎜ ⎟ = ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ 12 3 6 F ε ⎛ ⎞ ⎜ ⎟ = ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ and 13 3 F ε ε ⎛ ⎞ ⎜ ⎟ = ⎜ ⎟ ⎜ ⎟ ⎝ ⎠
.

On the other hand, we have: , , and . So, we get:

1 1 1 1 ( 1) ( l e x ψ + = ⊗ 3 3 3 1 ( 1) ( ) l e x k ψ + = ⊗ ) k ) k 2 2 2 1 ( 1) ( l e x ψ + = ⊗ ( ) 11 e G ε ε = , ( ) e 12 G ε ε = , and
( ) e ε ε 13 G = .

X

We let the reader write the other equations relative to the other TEGs (add a 3 rd variable in case of G 3 ) to get finally to: (4) A can be calculated according to (20

2 1 3 A ε ε ⎛ ⎞ = ⎜ ⎟ ⎝ ⎠ , 22 2 F ε ⎛ ⎞ = ⎜ ⎟ ⎝ ⎠ , , and
23 1 3 F ⎛ ⎞ = ⎜ ⎟ ⎝ ⎠ ( 22 e G ε = ) ( ) 23 e G ε = , 3 A 2 3 e ε ε ε ε ε ε ⎛ ⎞ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ 31 F = , 2 3 ε ⎛ ⎞ ⎜ ⎟ = ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ 33 F , 1 ε ε ⎛ ⎞ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ = , (
⎜ ⎟ ⋅ ⋅ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ . . . .
⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ ⎜ ⎟ . . . .
⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ ⎜ ⎟ 3
⋅ ⋅ ⎛ ⎜ ⋅ ⋅ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ . 4 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ .
The unique finite eigenvalue of A is equal to 9. The asymptotic production rate of G 1 and G 2 is therefore 1 2 1/ 9 λ λ = = whereas the production rate of G 3 is 3 2 / 9 λ = . As expected, this gives the same result as in the aforementioned works. Note however that the CTEG of Fig. 6 is not a safe Petri net and therefore the authors in Gaubert et al. (1999) used an equivalent safe one to make possible the application of the method based on heaps-of-pieces. Finding such an equivalent safe net is not always possible especially in case of presence of input transitions. The advantage of our method is also to avoid building a heap-of-pieces automaton. We can also note that the proposed approach can be applied even with infinite sequences without any effect on the CTEG structure. This is actually not the case with the method in [START_REF] Hillion | Performance evaluation of jobshop systems using timed event graphs[END_REF] since the initial Petri net must be transformed into an equivalent TEG. Unfortunately, the resulting TEG depends dramatically on the length of the sequence and becomes very voluminous even with not long sequences (see an example in [START_REF] Gaubert | Modeling and analysis of timed Petri nets using heaps of pieces[END_REF]).

CONCLUSION

In this study, we extended the use of (Max,+) algebra to Conflicting Timed Event Graphs or CTEGs which are a natural model of a large category of practical systems involving shared resources. We proved that CTEGs can be represented using a system of (Max,+) Linear Time-Varying equations while the policy of resources allocation is arbitrary. In case of a cyclic CTEG, we used the notion of monodromy to get to a standard (Max,+) state space representation. For future work, it would be interesting to look for the relevant modifications to bring to the proposed approach so as to relax the hypotheses of Section 3.1.

Fig

  Fig. 2. (a) Generic structure of a CTEG ( j

  twice to G 1 then 3 times to G 3 and finally one time to G 1 .-D2) Let us define the set of indices

  1: A CTEG verifying the hypotheses of Section 3.1 and evolving according to an arbitrary sequence σ

  when it is available for the th

							j l time, then it is
	available for the ( l + 1) th j	time by the firing of transition	j t for i
	the	i k	th	time (recall from hypothesis H2 that circuit
	i t	j	j t ji i p t is safe). Let j	'' x be the component of j i	X	i
	associated to transition j i t . Thus, we can write:
		(		1)	j	'' (	)

Note that Φ is T p : . ( , ( , ) i T q i i q Φ + -- Using (19), it follows that:

(2)

U By recurrence, we get to:

Then by replacing 1 with (1 ( ) in (23) and using the periodicity of , we get to: 24) is therefore a standard time-invariant system:

The state matrix A is called monodromy matrix.

Example 5.1: To illustrate how to use systematically the results above, we consider an example studied in [START_REF] Hillion | Performance evaluation of jobshop systems using timed event graphs[END_REF] and [START_REF] Gaubert | Modeling and analysis of timed Petri nets using heaps of pieces[END_REF]. It is a manufacturing system constituted of three machines represented by , and that produce three types of parts represented by TEGs G 1 , G 2 and G 3 (Fig. 6). Note that: , , and

All these matrices are calculated once and for all, whatever is the considered sequence. As an application, we will consider a periodic case and calculate the asymptotic production rate.

Let us consider the basic sequence:

Fre ( p ,i,k )

Fre ( p , relative to the three resources: , , , 1 11 , )

Fre( p ,

, , p , = Pre(

(1) A , (2)

A , (3) A and


A Chacravarty

Editor M B Zhou

Addad

S Amari
email: said.amari@lurpa.ens-cachan.fr

J J Lesage

Analytic Calculus of Response Time in

Networked Automation Systems B. Addad, S. Amari and J-J. Lesage, Member, IEEE Abstract -This paper presents a novel approach to evaluate the response time in networked automation systems (NAS) that use a client/server protocol. The developments introduced are derived from modeling the entire architecture in the form of timed event graphs (TEGs), as well as from the resulting state representation in Max-Plus algebra. The various architectural stages are actually modeled in a very abstract pattern, which yields just those TEG models where local delays are sufficient to perform the overall evaluation. In this manner, linear Max-Plus equations are obtained. A thorough analysis of these equations has led to analytical formulas for direct calculus of NAS response time. As a final step, experimental measurements taken on a laboratory facility have been used to verify the validity of the results. In conclusion, the benefit and effectiveness of this novel method have been demonstrated.

Note to Practitioners-In this work, we present an overall

study of networked automation systems working according to client/server paradigm. Unlike systems where a global scheduling of the shared resources is available and the delays well handled, in such systems it is not the case and the investigations to evaluate their real-time performances are required. Actually, these systems are very present in industry but the efforts to deal with this issue are rare and often informal, based on simulation of particular cases. In our work, we assess a major criterion of their time performances, the response time. We give a formal evaluation of this feature through an analytic approach. The results we present are generic and fit the experimental observations in different cases.

Index Terms-Networked Automation Systems, Response Time Evaluation, Max-Plus Algebra, Timed Events Graph, Switched Ethernet Networks.

I. INTRODUCTION

HE new trend within industrial organization networks consists of using the same technology at all levels of communication. A network solution supporting such a transparent vertical integration must be flexible and capable of simultaneously providing a high rate of data transfer in the upper levels and fast response times in the lower levels. The industrial Ethernet has established itself as such a new generation of fieldbuses, and many of them are currently meeting the needs of most automation applications. The increase in information transfer speed (Giga Ethernet), along with both the use of fully-duplex networks that prevent frames from colliding and low component costs, offered the major incentives behind the use of Ethernet in industry. Every Ethernet solution in fact features its own set of advantages and disadvantages. Generally speaking, as the solution becomes more compatible with standard Ethernet, its real-time performance achievement actually drops and vice versa [START_REF] Neumann | Communication in industrial automation -what is going on?[END_REF]. These solutions include "Modbus over Ethernet", an application protocol that makes use of the client/server paradigm. It is simple, accessible and open enough to facilitate vertical integration [START_REF]MODBUS Messaging on TCP/IP Implementation Guide V1.0b[END_REF]; however, it is not suitable for strict real-time applications like motion control, yet entirely adequate for the majority of industrial automation systems. With such a protocol therefore, resource scheduling is unavailable and considerable delays due to unsynchronized or unavailable resources are caused, complicating the evaluation of message delay encountered in each system component and consequently impeding an evaluation of the entire system response time. A number of research efforts have been undertaken to assess these NAS delays through the use, for example, of widely-accepted network calculus [START_REF] Cruz | A calculus for network delay, Part I: network in isolation[END_REF], [START_REF] Le Boudec | Network calculus: a theory of deterministic queuing systems for internet[END_REF], [START_REF] Georges | Confronting the performances of switched Ethernet network with industrial constraints by using Network Calculus[END_REF], worst case methods [START_REF] Fan | Guaranteed real-time communication in packet switched networks with FCFS queuing[END_REF], [START_REF] Lee | Performance evaluation of switched Ethernet for real-time industrial communications[END_REF] and simulation [START_REF] Zaitsev | Switched LAN simulation by colored Petri nets[END_REF], [START_REF] Jasperneite | Switched Ethernet for Factory Communication[END_REF]. Like the majority of studies however, these efforts have focused on just the end-to-end delays or network effect and neglect both the controllers (e.g. PLCs or programmable logic controllers) and RIOMs (remote input output modules). As a matter of fact, the PLC modules are not synchronized and RIOMs may be shared across many applications, which leads to delays that must then be incorporated. To the best of our knowledge, studies that consider the entire architecture (both field devices and the network) are still quite rare and often informally based on case simulation or experimental measurements targeting a limited number of systems [START_REF] Greifeneder | Optimizing Quality of Control in Networked Automation Systems using Probabilistic Models[END_REF], [START_REF] Denis | Measuring the impact of vertical integration on response times in Ethernet fieldbuses[END_REF]. The only formal method developed has been based on model-checking [START_REF] Witsch | Performance analysis of industrial Ethernet networks by means of timed model-checking[END_REF] aiming to check if a timing property holds or not. The disadvantage of this approach is its failure to provide the response times distribution and its classical state explosion problem, limiting its applicability to relatively simple cases. This method was enhanced afterwards in [START_REF] Greifeneder | Probabilistic Timed Automata for Modeling Networked Automation Systems[END_REF] and used to calculate the distribution of response times. The complexity of NAS is reduced by focusing on the important events but the state explosion problem still exists.

The objective of the present study is therefore twofold: to offer a formal method of evaluation, and to avoid the state explosion problem. Moreover, a novel method will be proposed in order to analytically assess both the response time bounds (i.e. min and max bounds) and the distribution shape. For this purpose, we have employed a special class of Petri nets (Timed Events Graphs or TEGs) to model the system. The behavior of TEGs can indeed be studied using linear equations (within Max-Plus algebra), making it suitable to analytically evaluate the temporal properties.

The current study extends our preliminary work [START_REF] Addad | Modeling and response time evaluation of Ethernet-based automation systems using Max-plus algebra[END_REF]. We relax many hypotheses (variable network delays, variable processing delays …) while considering more complex architectures (many servers).

The remainder of our study has been organized as follows. In Section II, some of the fundamentals regarding TEGs and Max-Plus algebra will be recalled. Next, Section III and Section IV will explore architectural modeling through the use of TEGs. We will begin by studying a system whose controller sends requests to just one server or RIOM in Section III, before considering a more complex architecture involving any number of servers in Section IV. Following resolution of the Max-Plus equations and fusion of the resulting solutions, a calculus algorithm and analytic formulae will be given. Since the delays caused by the network are needed to complete the evaluation, a method for accurately assessing these delays will be developed in Section V. Afterwards, Section VI will be devoted to validating results using real measurements recorded on a patented experimental platform 1 . Lastly, the outlook for future work will be discussed in Section VII as a conclusion to this paper.

II. TIMED EVENT GRAPHS AND MAX-PLUS ALGEBRA

An event graph is an ordinary Petri net with all places displaying at most one upstream and one downstream transition. So, a TEG is a Petri net without the presence of any conflicts or resource sharing. TEG behavior is deterministic and depends solely on the source transitions and initial conditions (TEG marking and tokens availability times) [START_REF] Baccelli | Recursive equations and basic properties of timed Petri nets[END_REF].

An event graph is timed if the places or transitions are assigned with delays. In our study, we are only considering timed-place graphs, yet we are still able to transform a timed place into a timed transition and vice versa [START_REF] Murata | Petri nets Properties analysis and applications[END_REF]. For the modeling carried out in the sequel, we will only assign delays to places, and each place will be ascribed a delay

denoted k p k τ .
In studying TEGs, the variable generally denotes the number of regular transitions with at least one place upstream, while represents the number of source transitions without upstream places. To study the dynamic behavior of TEG, we have associated the firing date for the time of each transition. This term is denoted for a source transition and n 1 French patent #01 110 933. This platform is used to perform behavioral identification of discrete event systems and to measure time performances of networked automation systems. With an initial marking of places as shown in Fig. 1 and given the dates 1 [START_REF] Neumann | Communication in industrial automation -what is going on?[END_REF] u k -, of firing respectively, of transitions and for the time, then the date

2 ( 1) u k - 1 u t 2 u t ( 1) th k - 1 ( ) k θ
of firing the transition for the time at maximum speed can be deduced using the following equation ("at maximal speed" means as soon as all upstream place tokens are available).

1 t th k 1 1 1 2 2 ( ) max( ( 1), ( 1)
) k u k u k θ τ τ = + - + - (1)
The above equation is actually a linear equation in Max-Plus algebra. A new algebraic structure has indeed emerged around two laws: the classical maximum denoted in general by " ⊕ " with identity element ε = -∞ ; and the classical addition denoted by " ⊗ " with identity element 0 e = . The previous equation (1) can then be rewritten as:

1 1 1 2 2 ( ) ( ( 1)) ( ( 1
)) k u k u k θ τ τ = ⊗ -⊕ ⊗ - (2)
In general, TEG behavior can be expressed by the following Max-Plus linear equation:

0 ( ) ( ( ) ( )) k A k B u k ϕ ϕ ϕ θ θ ϕ ϕ ≥ = ⊕ ⊗ -⊕ ⊗ - (3)
where the components of vectors thus obtain an extended system with a state vector

1 ij ϕ -) ( ) ( ( ) ( )) T x k k k θ θ =
, where θ is the vector of added transitions. TEG can therefore be described by the first-order recursive equation (or standard form [START_REF] Baccelli | Recursive equations and basic properties of timed Petri nets[END_REF]):

( ) ( 1) ( ), x k A x k B u k = ⊗ -⊕ ⊗ (4
) This first-order form is quite similar to the state representation of linear systems in classical algebra and proves very useful for studying the time properties of discrete event systems [START_REF] Mairesse | Graphical Approach of the Spectral Theory in the (max,+) Algebra[END_REF], [START_REF] Stanczyk | The max-plus algebra approach to the prototyping of concurrent processes[END_REF]. Further details on this algebra are available in [START_REF] Baccelli | Synchronization and Linearity: An algebra for Discrete Event Systems[END_REF].

The form (4) can now be rewritten in an explicit form with both the source transitions and initial conditions clarified:

2 1 0 ( ) (1) ( )
k k i i x k A x A B u k i - - = ⎡ = ⊗ ⊕ ⊕ ⊗ ⊗ - ⎢ ⎣ ⎦ ⎤ ⎥ (5)
Example II.1: TEG in Fig. 2 represents a manufacturing system with a machine capable of processing two parts at once (two tokens in place

). The parts entering the upstream stock (place ) become available to the machine The behavior of this system depends on the initial marking and the source transition of TEG (Fig. 2a). The dates of firing transitions and for the time (at maximum speed) are expressed as:

u t 1 t 2 t th k 1 2 2 2 1 1 ( ) ( 2) ( ) ( ) ( ) u k k k k θ τ θ τ θ τ θ = ⊗ -⊕ ⊗ ⎧ ⎨ = ⊗ ⎩ uk ( 6
)
The equations ( 6) are linear but not of the form (4). The decomposition process explained previously is needed to get to this first order form. After decomposition (Fig. 2b), the transition is added to yield just those places with at most one token. The system can then be described by:

3 t 1 3 2 1 1 3 2 2 ( ) ( 1) ( )) ( ) ( ) ( ) ( 1) u k e k u k k k k k θ θ τ θ τ θ θ τ θ = ⊗ -⊕ ⊗ ⎧ ⎪ = ⊗ ⎨ ⎪ = ⊗ - ⎩ (7)
The standard first-order form (4) is ultimately written with:

1 2 , e A ε ε ε ε τ ε τ ε ⎛ ⎞ ⎜ ⎟ = ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ 1 u u B τ τ τ ε ⎛ ⎞ ⎜ ⎟ = + ⎜ ⎟ ⎜ ⎟ ⎝ ⎠ and 1 2 3 ( ) ( ) ( ) ( ) k x k k k θ θ θ ⎛ ⎞ ⎜ ⎟ = ⎜ ⎟ ⎜ ⎟ ⎝ ⎠
The behavior of this system can thus be completely determined if we were to consider the initial conditions (i.e. initial marking and tokens availability). A scenario of the system (all tokens are available initially) at maximum speed has been depicted in Fig. 3.

If the system (Fig. 2b) is not constrained (the upstream stock is never empty and parts remain available at all times), then the system can be expressed by:

( ) ( 1) x k A x k = ⊗ - (8)
Such is the case in our study since data stemming from the plant are available at the sensor output as long as devices do not fail. This observation explains the absence of source transitions within the NAS model of the next section (Fig. 6).

III. MODELING AND RESPONSE TIME EVALUATION: CASE OF A

SINGLE RIOM In our study, we consider NAS based on client/server paradigm. The PLC is the client and the RIOM (remote input output module) is the server. While the PLC sends requests periodically, the server does not send any message autonomously but does only answer the received requests: only synchronous transmissions from the RIOM are then considered. The considered PLC contains a CPU (central processing unit) module to execute the user program and a network board (NETb) to send requests (combined requests: read and write data) to the RIOM. At each scanning cycle, the NETb sends a message to the RIOM either requesting information on the plant (e.g. is the maximum level of water reached?) or providing the control signal (e.g. close the valve). Neither the CPU nor the NETb are in fact synchronized even though they do belong to the same component, i.e. the PLC; they are both time-driven and operate independently. The CPU periodically accomplishes the tasks of: reading inputs, executing the user program to produce a control signal, and updating outputs. Regardless of the CPU, the NETb sends requests to the RIOM and awaits the replies. Once a reply has been received, the NETb waits further until the period time has elapsed in order to begin a new cycle.

Besides supposing the CPU and the NETb to work periodically without clocks drift, we consider neither frame loss nor timeouts. Such assumptions are often taken for granted in the context of NAS [START_REF] Denis | Measuring the impact of vertical integration on response times in Ethernet fieldbuses[END_REF], as is the case in our study, for two main reasons:

-The exchanged data packets are of a short length, and just a few bytes are sufficient to transmit data. With Modbus for instance, the request can reach up to 256 bytes only [START_REF]MODBUS Messaging on TCP/IP Implementation Guide V1.0b[END_REF].

-Such automation systems are necessarily divided into many local automation cells so as to achieve traffic isolation, especially from non-real time traffic (long packets, videos, etc.). Only a few packets are in fact exchanged between the various cells and serve to limit congestion or packet drops within real-time domains. Such is true for the case of vertical integration of high-level functions (e.g. supervision) [START_REF] Denis | Measuring the impact of vertical integration on response times in Ethernet fieldbuses[END_REF].

Regardless of the protocol used in NAS, one major criterion of real-time performance evaluation is response time, which reflects the delay between the occurrence of an event in the plant (e.g. the maximum water level has been reached) and the arrival of the consequence event generated by the controller (e.g. close the valve) at the plant (Fig. 4). Two cases need to be distinguished depending on whether this action/reaction loop concerns a simple control event or an event involved in a system safety. In the former case, the designer is merely required to evaluate the time performance of the control architecture (e.g. through knowledge of the response times mean and standard deviation), whereas in the latter case, the maximum response time bound becomes the top priority. In our work, we consider the general case regardless of the consequences of the events occurring in the plant. Both the bounds and distribution of response times will be calculated.

A) Architecture Modeling

According to the client/server protocol described above, we derived the architectural model shown in Fig. 6. This model is highly abstract and only represents the applicative aspect of the architecture protocol, i.e. the top layer in the OSI representation of network systems. So, rather than representing the network in a lower level including the problem of resources sharing that would prevent us from using TEGs, we only consider the delays, even variable, due to that network.

On the model depicted on Fig. 6, we consider just the timed places and simply assign a delay i τ to place (thus, only the delays i p i τ are represented on Fig. 6). The system is assumed to be work conserving and all transitions are fired at maximum speed, as explained in Section II.

Places and with CPU delays of respectively). The only assumption regarding these delays is the fact that they are bounded. Unlike the majority of studies and our preliminary work [START_REF] Addad | Modeling and response time evaluation of Ethernet-based automation systems using Max-plus algebra[END_REF], in which the network has been represented with constant delays, we now assume that these delays are variable in a given domain, with both a minimum and maximum (finite) bound. At the scanning cycle, the network delays experienced by the request and its reply in the network are: and , respectively. In assessing the maximum NAS response time bound, only the Fig. 6. Mono-RIOM networked automation system modelling using TEGs (Case 1).

upper bounds of these delays are required. This observation will be explained more thoroughly further below when the analytical evaluation is performed.

Once the network has been crossed, the returned response arrives in the NETb input buffer at and is copied into the memory shared with CPU in a time 13 p 13 τ , denoted (much smaller than the other PLC delays since its order of magnitude remains in the microseconds, whereas the others reach the milliseconds). This time period is indeed necessary to copy just those few bytes carrying the application data (without any of the lower layers headers). A place could be added to represent this memory, yet its token would be available at all times and thus exert no impact on the system behavior. To sum up (Fig. 5), an event occurs at any time (1) in the plant (source S) and waits until a request arrives to RIOM to take it into account. Once the request is received, an answer is processed while considering this event and then returned to PLC ( 2). This answer crosses the network and gets to NETb [START_REF] Cruz | A calculus for network delay, Part I: network in isolation[END_REF]. At the beginning of a new CPU cycle, this answer is used to execute the user program (4) to perform the reaction event (5) that will be sent to its destination at the next scanning cycle [START_REF] Fan | Guaranteed real-time communication in packet switched networks with FCFS queuing[END_REF]. Again, this answer crosses the network to get to RIOM [START_REF] Lee | Performance evaluation of switched Ethernet for real-time industrial communications[END_REF] and finally to the plant (8) (destination D).

Remark III. 1:

The gray hatched arrows on Fig. 6 (in the RIOM model) that intended to represent both the source (data stemming from the sensor) and output (data transmitted towards the actuator) are not being considered since the system has not been constrained. The RIOM is always responding to a request using the latest information provided by the sensor. This situation remains valid as long as the devices are functional, which serves to justify the absence of source transitions first on the model and consequently in the subsequent Max-Plus equations (explanation of Section II with unconstrained systems).

Thus, by applying the method described in Section II to the model shown in Fig. 6 with all tokens available at the beginning, we obtain the Max-Plus equations:

1 2 1 3 2 1 2 3 1 3 ( ) ( ( 1)
) ( ( 1) ) ( ) ( ( 1)

( ) ( ) ( ) ( ) k k k k k k k 4 θ θ τ θ θ θ τ θ θ τ = -⊗ ⊕ -⊗ ⎧ ⎪ = ⊗ ⎨ ⎪ = ⊗ ⎩ τ 6 (9)
) ( ( 1) ) ( ) ( ) ( ) ( ) ( ) ( ( ) ) ( ( 1) ) ( ) ( ) ( ) ( ) ( ) ( )
( ) ( ( ) ) ( ( ) ) ( ) ( ) l l l l l l l l l l l l l l l l τ θ θ τ = -⊗ ⊕ -⊗ ⎧ ⎪ = ⊗ ⎪ ⎪ = ⊗ ⎪ = ⊗ ⊕ -⊗ ⎪ ⎪ = ⊗ ⎨ ⎪ = ⊗ ⎪ ⎪ = ⊗ ⎪ = ⊗ ⊕ ⊗ ⎪ ⎪ = ⊗ ⎩ τ (10) TABLE I
Equations systems [START_REF] Jasperneite | Switched Ethernet for Factory Communication[END_REF] and [START_REF] Greifeneder | Optimizing Quality of Control in Networked Automation Systems using Probabilistic Models[END_REF] are linear in Max-Plus algebra and may be written in the form (4). We have assigned them different indices (k and l) due to their nonsynchronization, just like the CPU and the NETb. This step constitutes an additional difficulty in our study.

B) Principle behind the proposed approach

As a first step, we must solve the systems of equations ( 9) and [START_REF] Greifeneder | Optimizing Quality of Control in Networked Automation Systems using Probabilistic Models[END_REF] in order to determine the transition firing dates as functions of indices k and l. This resolution step is somewhat complex since the systems are time-variant (the involved delays are variable). Yet, this complexity can be overcome under the aforementioned hypotheses: i) the periodic operations of both the CPU and NETb (without clock drift); and ii) zero frame loss or component failure. In this case, we are only searching for the two cycles beginnings at 1 ( ) k θ and 4 ( ) l θ . The other transitions will be deduced accordingly using equations ( 9) and [START_REF] Greifeneder | Optimizing Quality of Control in Networked Automation Systems using Probabilistic Models[END_REF]. The following solutions are therefore obtained: ( ) ( 1)

1 2 3 ( ) ( 1) ( ) (( 1) ) ( ) CPU CPU CLC CPU k k T k k T T k k T θ θ θ = -⋅ ⎧ ⎪ = -⋅ ⊗ ⎨ ⎪ = ⋅ ⎩ (11)
( ) ( ) ( ) ( ) ( ) ( ) ( ( ) ) ( ( 1) ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ( ) ) ( ( ) ) ( ) ( ) SCN l l T l l l l l l l l l l l l l l l τ θ θ τ = -⋅ ⎧ ⎪ = ⊗ ⎪ ⎪ = ⊗ ⎪ = ⊗ ⊕ -⊗ ⎪ ⎪ = ⊗ ⎨ ⎪ = ⊗ ⎪ ⎪ = ⊗ ⎪ = ⊗ ⊕ ⊗ ⎪ ⎪ = ⊗ ⎩ (12)
The next step of this method consists of fusing solutions [START_REF] Denis | Measuring the impact of vertical integration on response times in Ethernet fieldbuses[END_REF] and ( 12) so as to clarify the link between the CPU and the NETb. Among these solutions, only the equations representing the following events are then of interest (at this stage): -Beginning of processing in the CPU or reading inputs Let's set as the wait time between transmitting a request and receiving the corresponding response (i.e. the round-trip time). The following equations are then derived:

r T 1 2 ( ) ( 1) ( ) ( 1) CPU CPU CLC k k T k k T T θ θ = -⋅ ⎧ ⎨ = -⋅ ⊕ ⎩ (13) 4 11 ( ) ( 1)
( ) ( 1)

SCN SCN r l l T l l T T θ θ = -⋅ ⎧ ⎨ = -⋅ ⊗ ⎩ (14)
At the scanning cycle, the request reply is received at date . The condition to verify thus becomes:

1 1 1 1 1 1 / ( ) ( ) min ( ( ) ( )) l i i l m Arg i l θ θ θ θ ∈ > = -
, where " " is the converse function yielding the index that minimizes the positive term min Arg ( ) ( ) ( )

MIN l filt D l n l d θ θ = - + (16)
where filt d is the delay due to data filtering in the sensor.

On the other hand, the response time is maximal if the data arrive immediately after the beginning of processing in the RIOM, with respect to the previous scanning cycle, i.e.:

8 7 ( ) ( ) ( 1)
MAX l filt D l n l d θ θ = - -+ (17)
As can be seen, the formulas ( 16) and ( 17) provide the response time bounds relative to the scanning cycle while [START_REF] Murata | Petri nets Properties analysis and applications[END_REF] gives the response time relative to an event generated at time th l ( ) e l θ . Actually, these formulas can be used in calculus provided that the index is calculated. The previous steps to find this index can be achieved using the algorithm depicted on Fig. 7: In conclusion, the method development has been achieved by means of the following steps: modeling the architecture through the use of TEGs; writing the corresponding Max-Plus equations; and resolving these equations. After finding the transitions firing dates (through the previous Max-Plus equations resolution or simply by simulating the system behaviour using the recursive equations ( 9) and ( 10)), an algorithm (let's call it ALGO as in Fig. 7) was provided to evaluate the architecture response time relative to any occurring event at any cycle; this algorithm is fast and easily implemented. Besides measurements, this algorithm is used to verify the validity of the formulae (explicit formulas that can be used directly in calculus) derived later in this study.

l n Initialization : 1, 1, 1 l l l m n = = = 1 1 1 ( ) ( ) l m l θ θ > 1 l l m m = + 1 2 1 ˆ( ) ( ) ( ) . l l C L C l m m T θ θ θ = = + yes 8 8 7 8 7 ( ) ( ) ( ), ( ) ( ) ( ) ( ) ( ) ( 1)

Lemma

This architecture contains two periodic, yet nonsynchronized, processes. In spite of this fact, the entire system remains periodic with a period that verifies:

, where always exist.

CR T 1 2 CR SCN CPU T k T k T = ⋅ = ⋅ 1 2 , k k ∈ Proof:
The main PLC parameters of interest are the two module periods and , chosen by the system user from among only the multiples of a basis unit, which is generally on the order of a few milliseconds. These parameters can thus be considered as integers under the assumption of zero clock drift. Now let's set: n n ω = can be written, it is sufficient to take: (

) and (

1 k n = 2 1 2 2 k n n ρ = ⋅ + ) in order to reach: 1 1 2 2 ( / ) CPU CPU k n n T k T ρ ⋅ + ⋅ = ⋅ ; hence: 2 1 (
)

CR CPU T n n T ρ = ⋅ + ⋅ (18)
This period is minimized if and are relatively prime numbers.

1 n 2 n
Hence, we can conclude that the method (or ALGO) is formal and all possible states are scanned if the simulation length of the system covers the critical period . The resultant response time bounds are thus formal as well. CR T Remark III. 2: the previous method can be used to obtain the shape of the response times distribution as follows: at each scanning cycle , the different delays l ( ) i l τ of TEG are taken randomly from their domain of variation. For example, the network delay 7 ( ) l τ is randomly chosen from .

Then using the max-plus equation and ALGO, the index is calculated. Finally, by generating randomly an event at date , the response time relative to this event is calculated using [START_REF] Murata | Petri nets Properties analysis and applications[END_REF]. By repeating this operation a large amount of times, histograms giving the response times distribution shape is obtained (see example of Section VI).

C) Analytical calculus of response time

The previous algorithm enables the calculation of both the response time bounds and the distribution shape. It is preferable however to develop analytical formulae that yield these results trivially. Moreover, such formulae will facilitate analyzing the influence of individual architecture parameters on overall performance and serve to answer the "what if" questions. This attribute is very valuable when seeking, for example, an adequate automation system configuration so as to guarantee the stability or safety. Such an analytical evaluation will be the focus of this section.

The results from ( 13) and ( 14) along with the algorithm principle will be used for this exercise.

Let's take: , For the calculus complexity to be proven later, let's begin with the case r ∈ and generalize it for r + ∈

(for recall,

SCN CPU T r T = ⋅ with r ρ ω = + , ρ ∈ , 1 ω < and ω + ∈ ). a) ( 0 r ) ω ∈ =
At the scanning cycle, the request response is received at the following date:

th l 11 ( ) ( 1) CPU CPU r l l r T T θ α τ = -⋅ ⋅ + ⋅ + (19)
In order to be taken into account, the response must wait for the next CPU cycle beginning, which entails waiting for the minimum number (previously denoted ) that verifies

k l m 1 1 1 ( ) ( ) k l θ θ > .
By taking 1 ( 1) 1 k l r α -= -⋅ + + , we then obtain:

1 1 1 ( ) ( ) CPU r k l T θ θ τ = + - (20)
Since [ ]

0 CPU r CPU T T τ < -< , 1 1 1 ( ) (
1 1 ˆ( ) ( ) 1 ( 1)
[ ] 4 1 ( ) ( ) (1 ) CPU n k r T θ θ α β = + -+ + ⋅ (22)
In relying on condition C 1 :

(1 ) r α β > + + , verifies and thus , which justifies writing: (including buffering at the input port, data filtering, processing and buffering at the output port).

n 4 1 ( ) ( ) n θ θ > l 1 l n l = + 2 4 4 ˆ( ) ( ) ( 1)
In practice, condition C 1 is often verified and results (24) are valid given that the scanning period is much longer than the CPU period (

). If such were not the case, then it would be necessary to identify the integer that

verifies condition C SCN CPU T T 1 q ≥ q :
(1 ) ( 1) r q r q α β ⋅ > + + > ⋅ -. We thus obtain and ultimately the general formulae:

l n l q = + / / 8 ( ) ( , ) ( ) ( 1) ( 1, 1) ( ) ( ) ( ) MIN SCN I O MAX SCN I O r e D l q T l q T D l q T l q T D l l q l θ θ = ⋅ +Δ + ⎧ ⎪ = + ⋅ +Δ - + + ⎨ ⎪ = + - ⎩ (25)
It can be noted that if condition C 1 is verified, i.e.

(1 ) r

α β > + + , then
, which in turn yields exactly the same results as in (24). 1 q = Discussion: From the above analysis and formulae, some of the points not trivially expected deserve to be mentioned:

-The network delays are assumed not to be constant (i.e.

variable α ) as is the user program execution time (variable β ). Moreover, according to C q , the response time reaches its worst case (maximum value) when α and β are maximized.

We actually needed to search for the minimum number such that condition C q q was verified, or (1 ) r q α β ⋅ > + + . The number therefore assumes its worst value when parameters q α and β are maximized. In order to calculate the upper response time bound using these formulae, only the local worst case CPU calculus and network delays are required.

-The same remarks apply to the effect of delay . At the scanning cycle, we find:

th l 11 ( ) ( 1) ( ) CPU CPU l l r T T θ α γ = -⋅ ⋅ + + ⋅ (26)
Let's now set , where: [ ]

i ∈ ( 1) ( 1) i l i γ ω ≤ + ⋅ -< + (*) For 1 ( 1) 1 k l i ρ α -= -⋅ + + + , it follows that: [ ] 1 1 1 ( ) ( ) 1 ( ( 1)) CPU k l i l T θ θ γ ω = + + -+ ⋅ - ⋅ (27) Since in (*), ( 1
) ( 1) i l i γ ω ≤ + ⋅ -< + , then ( 1)
1 1 1 ˆ( ) ( ) 1 ( ( 1
)) CPU l l i l T θ θ β γ ω = + + + -+ ⋅ - ⋅ (28)
We also find that: 4 ( ) ( 1)

CPU n n r T θ = -⋅ ⋅ and for 1 n l = + , then: 4 ( ) CPU n l r T θ = ⋅ ⋅ , i.e.: [ ] 4 1 ( ) ( ) 1 ( 1) CPU n k r i l T θ θ α β ω ⎡ ⎤ = + -+ + + -⋅ - ⋅ ⎣ ⎦ (29)
From (*), it can be deduced that:

1 ( 1) 1 i l γ ω γ < + -⋅ -≤ + .
Let's set: , 1 ( 1

l i i l ) ω Γ = + -⋅ -, with , 1 l i γ γ < Γ ≤ + , , , min ( ) MIN l i i l ∈ ∈ Γ = Γ and , , max ( ) MAX l i i l ∈ ∈ Γ = Γ .
Equation ( 29) can then be rewritten as:

4 1 , ( ) ( ) ( ) l i CPU n k r T θ θ α β ⎡ = + -+ +Γ ⋅ ⎣ ⎤ ⎦ (
{ 1 1 2 2 3 , 3 ( 1) : ( 1 :
( ) ( MIN MAX l i r q r q Global r q r q Local r q r q α β α β α β ⋅ > Γ + + > ⋅ - ⎧ ⎨ ) 1 ) ⋅ > Γ + + > ⋅ - ⎩ ⋅ > Γ + + > ⋅ -
The response times are then written as:

1 1 / 2 2 8 3 ( , ) ( 1)
( 1, 1) will thus serve to satisfy condition C 1 and will surely lead to 2 1 q = , which means that the relatively simple results (24) can be used directly for calculus.

( ) ( ) ( ) MIN SCN I O / MAX SCN I O r e D q T l q T D q T l q T D l l q l θ θ = ⋅ +Δ + ⎧ ⎪ = + ⋅ +Δ - + + ⎨ ⎪ = + - ⎩ (

Example III.1:

Suppose that the CPU period equals 5 ms, the user program lasts at most 3. . The minimal number satisfying is this time q 1.7 r q ⋅ > 1 q = . The maximum bound is then / 2 10

MAX I O D T = × + Δ +
, which is less than the previous one. This phenomenon is paradoxical since a faster element may lead to a more significant delay. This consideration can be explained intuitively as follows: when a response is returned during the scanning cycle, with a sufficiently long scanning period the consequence derived from the CPU will be transmitted to the actuator during the scanning cycle. However on the other hand if scanning were faster, then the consequence would not be sent during that particular cycle but instead wait until the next one, i.e.

or even later, thus explaining the incremental delay with a scanning period . This phenomenon has also been pointed out in [START_REF] Greifeneder | Reactivity Analysis of different Networked Automation System Architectures[END_REF].

IV. MODELING AND RESPONSE TIME EVALUATION: CASE OF MULTIPLE RIOMS

The system modeling is different in this case since N RIOMs are to be scanned. Information is obtained from many sensors and multiple control signal destinations are observed as well. The PLC is thus transmitting a burst of requests to the RIOMs and waiting for responses (Fig. 8). When a response has been received, it is copied into the memory shared with the CPU. Once all responses have been received, NETb remains in a waiting mode until the scanning period has fully elapsed and then begins another cycle. All received responses are copied as a block (all at once) from the shared memory and then used to update control signals within the same CPU cycle. Only one token is necessary therefore to model CPU operations. CPU model of Case 1 thus remains valid for our second case but the remainder of this system however is much more complex than before.

In this general NAS configuration, requests are sent from NETb in an invariant order (throughout NAS operations), as revealed on the new model in Fig. 9. The RIOMs are assigned indices according to their scanning order. We associate index to the RIOM receiving the request from the NETb. As an example, Fig. 7 shows RIOMs being scanned in the order Furthermore, places represent the FIFO queue delay affecting responses in the NETb input buffer. Once again, these network delays are not presumed to be constant, but rather variable within a bounded domain; they may be due to any kind of network, and their only condition is to be bounded so as to ensure suitability for real-time systems. 13i p All that is necessary to write the equations of the model has been presented, and we now derive the Max-Plus system of equations (N is the number of scanned RIOMs):

τ θ θ τ = -⊗ ⊕ -⊗ ⎧ ⎪ = ⊗ ⎨ ⎪ = ⊗ ⎩ τ j l ⎤ ⎥ ⎦ (32)
i i i i i i i i i i i i i i i i i i i i f l l l i to N l l l l l l l or en l l l l l l θ τ θ - = -⊗ ⊕ -⊗ = = ⊗ = ⊗ = ⊗ ⊕ -⊗ = ⊗ = = ⊗ = ⊗ = 5 1 4 1 0 1 3 1 12 4 ( ) ( ( 1) ) ( ( 1) ) 1 ( ) ( ) ( ) ( ) ( ) ( ) ( ( ) ) ( ( 1) ) ( ) ( ) ( ) ( ) ( ) // ( ( ) ( ) ( ) ) ( )
N j j N l l l l θ τ θ τ θ θ τ ≤ ≤ ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎡ ⎪ ⊗ ⊕ ⊕ ⊗ ⎢ ⎪ ⎣ ⎪ = ⊗ ⎪ ⎩ (33) 4 15 ( ( ) ) ( ( ) ( )) ( ) ( )
According to this new model (Fig. 9), the transition models only the fact that a new cycle cannot begin while all responses have not been received. The key event to consider is the completion of copying the response emanating from (S) to the memory shared with the CPU. For this purpose, we have introduced a virtual transition fired at date In a similar manner and using the same notations as in Case 1, the solutions to be used for the analysis are as follows: By respecting the same analytical principle as in the first case with one RIOM, for an event generated at time ( ) e l θ and taken into account during the scanning cycle, we obtain:

th l / 1 1 / 1 1 8 ( ) ( , ) ( ) ( ) ( 1) ( 1, 1) ( ) ( ) ( ) ( ) S D D S D D D N N N i i MIN SCN EM EM I O i i N N N i i MAX SCN EM EM I O i i r N e D l q T T T l q T l q D l q T T T l q T l q D l l q l θ θ = = = = ⎧ ⎪ = ⋅ + - +Δ + + ⎪ ⎪ ⎪ = + ⋅ + - +Δ -+ + + ⎨ ⎪ ⎪ = + - ⎪ ⎪ ⎩ ∑ ∑ ∑ ∑ (37)
where: , ( 1) The results (37) fit the first case with one RIOM, where

l i r q r q α β ⋅ > Γ + + > ⋅ -, 7 7 ( , ) ( ) ( )
D S N N =
, since the event source is also the destination. Discussion: From the results in (37), it can be observed that to minimize response time, a higher index value should be assigned to the event source and a lower value to the destination so as to make the term ( )

D S N N -
as highly negative as possible: the RIOMs scanning order is indeed important. This result matches some of the conclusions drawn experimentally in [START_REF] Greifeneder | Optimizing Quality of Control in Networked Automation Systems using Probabilistic Models[END_REF], where it is stated that if the PLC were loaded with requests (yet remaining below a threshold), response time bounds would decrease. Loading the PLC and therefore delaying request transmission (to S) or simply increasing the request transmission order to RIOM (S) yields exactly the same phenomenon. Regarding the load threshold, the formulae also match experimental results. We must keep in mind that the delay calculus condition depends on α or ( ) S l θ , and should be decreased (see (34)). The optimal case is derived by increasing while maintaining equal to 1, i.e. remaining under the threshold. Once again, this phenomenon is paradoxical since delaying the time of request transmission to the event source would lead to faster response times. This scenario can be explained more intuitively by the fact that it would be preferable to delay request transmission by a small amount of time and therefore wait for an event to occur rather than acting too hastily, sending the request too early and potentially missing the event. The event must therefore wait until the next request to be considered, which might necessitate a substantial wait since the scanning period is often relatively long.

V. NETWORK DELAYS EVALUATION IN A SWITCHED ETHERNET CLIENT/SERVER NAS

The analytical method developed above is applicable easily but the delays caused by the network ( 7i τ and 12i τ ) are required in our formulae. This section will focus on their evaluation. In the case of a standard full duplex switched Ethernet network, existing methods can be used for this purpose. Unfortunately, in the context of our study, accurate assessments are required. A pessimistic method may cause significant overestimations of the maximum response time as illustrated in the following example.

Example , the maximum response time bound is slightly greater than 20ms, compared to a value of 30ms including the network delay overestimation. This is very pessimistic (approx. 50% overestimation) and unacceptable in the majority of automation systems.

For this reason, new methods had to be investigated in an effort to evaluate network delays with as limited an overestimation as possible, and the present section is devoted to this objective.

In this study, we have considered a client/server automation system (as in Case 2) over a standard full duplex Ethernet switch (Fig. 10). The switch is modeled as in [START_REF] Jasperneite | Switched Ethernet for Factory Communication[END_REF] with a central dispatcher forwarding the frames according to FCFS policy (first come first served), at a speed (bits/s) noted C . In considering a "store & forward" switch, a frame is completely received before being forwarded by the dispatcher to the appropriate output port. The data are exchanged with the end stations (PLC or RIOMs) at a bit rate (bits/s) corresponding to physical link capacity, noted (link of port ). As aforementioned, the frames entering the switch are forwarded in a FCFS manner without any flow classification or prioritization. At any time, the only criterion therefore for frames differentiation is their order of arrival at the switch. The principle behind the method is to consider a function of order for arbitration when many frames at different input ports are waiting to be forwarded. correspond to notations used in the modeling sections i.e. 5 j θ and 6 j θ (resp. 9 j θ and 10 j θ ) if the ( 1 frame is the request (resp. reply). To express the equations ( 38) and (39) in a more explicit way, we introduce a function denoted , whereby is the order of arrival of the request at the switch whereas is the order of arrival at the switch of the corresponding reply. At the beginning, this function is initialized: Example IV.2 (numerical application): a PLC scans three RIOMs (R 1 , R 2 and R 3 ), with requests of lengths and , respectively (overheads included). All of the numerical values used have been chosen arbitrarily and only serve an explanatory purpose: II.

) th i + th j th j order ( ) req order i th i ( resp order i ) (1 ) 1, , ( )
Discussion: As can be seen on Table II (the shaded column), the order function at the last iteration is no longer in its initialized form. We can in fact note that the response to the first request enters completely into the switch ( 91 1082 s θ μ = ) shortly before the arrival of the third request ( 53 1084 θ =

). Therefore, and , while at the beginning and ord .

(

VI. APPLICATION AND VALIDATION

To verify the validity of both the models and results generated previously, we will focus on the two automation architectures described previously (see Fig. 4 and Fig. 8). By using the experimental facilities of our laboratory, we have studied these two architectures. Let's now compare the results obtained with ALGO, the formulae and an experimental measurement of the response time.

The second configuration focuses on the delay between an event generated on the input of remote module R 15 and its consequence on R 16 output. The histograms in Fig. 11 show a series of 10,000 experimental measurements and response times obtained using ALGO for this configuration.

The CPU period of the PLC has been set at 5 ms and the scanning period at 10ms. In practice, this architecture presents a jitter of approx. 15% with an average value of 10 ms. This feature has been taken into account in the different calculations. Also, to calculate the response times histograms, about 10,000 events were generated. To avoid any underestimation of the response times due to generating events at discrete dates, a random event generator is used. The event is generated at date . The simulation was run many times, yielding the results presented in Fig. 11 and Table III. On the other hand, if we compare the results of both configurations (Fig. 4 and Fig. 8), a difference of 0.25 ms is detected between the maximum (as well as minimum) bounds. This corresponds exactly to the value of the frame emission time ; moreover, since the switches are very fast, the considered configurations turn out to be very similar. The main difference lies in the use of one RIOM as an event source and another as the destination, with a difference of one in the scanning order (R EM T 15 and R 16 ). This result corroborates the general formulae obtained in Section IV. In this work, we have presented a new approach to evaluating the response time in networked automation architectures using client/server protocol. All delays experienced during the various system stages have been taken into account. A simple algorithm and analytical formulae for a trivial evaluation of response time have been developed; both the response time bounds and the distribution shape could thus be assessed. Afterwards, a comparison of results with experimental measurements enabled us to verify the validity of this method. Moreover, the analytical results obtained can be easily used a priori, during the design phase of an architecture, with application to choosing an adequate configuration for components in order to satisfy the desired time requirements of the plant. These results can also be used a posteriori to evaluate the response time of an existing architecture, as displayed in the previous examples. Throughout the study, many of the important results presented have been shown to match experimental observations.

For future studies, it would be worthwhile to consider more general automation architectures along with other protocols, a wide array of control loops with many clients and naturally relax some of our hypotheses like clocks drift of frame loss. The challenge then is to develop an efficient method so as to accurately evaluate the network delays in the presence not only of many loops, but also with acyclic and non-real time traffic, as encountered in modern NAS.

1 Fig. 1 .

 11 Fig. 1. A timed event graph.

  before the finished part exits the machine.

Fig. 2 .

 2 Fig. 2. Timed event graph decomposition.

1

 1

Fig. 3 .

 3 Fig. 3. Chronogram of TEG (Fig. 2b) behavior at maximal speed.

Fig. 4 .

 4 Fig. 4. Mono-RIOM networked automation system (Case 1).

and 4 τ 15 τ

 415 respectively model the waiting phases to begin a new CPU cycle; user program execution during (including updates to both reading inputs and outputs); busy CPU; and lastly, idle CPU. Since the CPU calculus always finishes before the CPU period has elapsed, periodic CPU operations can easily be indicated by a cycle period denoted (represents the NETb scanning period (denoted ), and a token in place indicates a busy status during this period. Transmitting a request therefore starts by firing the transition and ends by firing . required to transmit the request. A token in means the request has been sent and the NETb is waiting for the response. Places and model the network delays imposed upon the transmitted request and the returned response

10 τFig. 5 .

 105 Fig. 5. Experienced delays at the different stages of NAS.

3 τ 6 τ/ 7 τ 12 τ 13 τ

 3671213 Time to send a request (emission) EM T Delay to cross the network by the sent request Time to process a request by RIOM / the network by the returned answer Time to copy an answer into shared memory of NETb/CPU CPY T Network

  ( 1 θ ) -End of processing in the CPU and output update ( 2 θ ) -Beginning of scanning cycle and transmitting a request ( 4 θ ) -Reception of a response in the shared memory ( 11 θ ). These are indeed the events representative of communication between the CPU and the NETb. When a response arrives ( 11 θ ), it is taken into account at the next CPU cycle beginning ( 1 θ ) and then read and used in CPU calculus. Once processing has been completed, the result is put in the NETb memory ( 2 θ ) before being transmitted to the RIOM at the next scanning cycle beginning ( 4 θ ).

  account by the CPU; it must then wait for the CPU cycle beginning. This cycle however must be immediately subsequent with respect to

  During the next scanning cycle (with respect to), which is the cycle, the updated result is encapsulated into a request packet and sent to the RIOM. Similarly, another new transition response time in[START_REF] Murata | Petri nets Properties analysis and applications[END_REF] is minimal provided that the data originating from the sensor are used for processing in the RIOM immediately after being generated, i.e. at the date

Fig. 7 .

 7 Fig. 7. Response times calculus algorithm (ALGO).

  + + , which leads to the following result:

1 β

 1 fast NAS response times, the ratio r ∈ should be increased by either reducing or raising . The optimal configuration is attained by minimizing the period while maintaining < (i.e. the user program must be completely executed before the CPU cycle has elapsed). The reasoning regarding the period is not so obvious given its direct correlation with the formulae in (25). Nevertheless, certain details about this point are provided in the section discussion below (Case b).

  + + + and therefore:

C 1 .

 1 31)Discussion: In this general case, it is noted that the optimality condition This result is an important about the response time calculus. It suggests, in the event the network effect is smaller than (often the case in such NAS and which then implies CPU T 0 α = ), setting the scanning period at twice the CPU period (while naturally first minimizing , as previously explained). If , we then return to case (a), where

Fig. 8 .

 8 Fig. 8. Multi-RIOMs NAS (Case2).

  indices assigned respectively to the event source (S) and

  t

τ 2 τ 1 Fig. 9 .

 19 Fig. 9. TEGs based model of the multi-RIOMs NAS (Case2).

16 R

 16 consequence destination (D) involved in the targeted NAS loop. In Fig.7We have introduced the delay experienced by each frame during the various NAS stages: a delay to be sent to the network, a delay occurring in the RIOM and naturally the delays caused by the network represented by places and .

.

  This reply is used in the calculus of the subsequent CPU cycle, and the control signal is updated and then sent to destination (D) upon the next RIOMs scanning cycle.

Fig. 10 .

 10 Fig. 10. Client/server automation system over an Ethernet switch.

  order is known from the beginning and invariant, as previously mentioned in Section IV. Since the responses do not yet exist (at time 0 t = ), then: first frame to enter the switch is the request, of length , sent to R1), using (38)-(39) we have: is received by R 1 at date 61 θ and the corresponding response is therefore returned at date , which means that another frame is waiting at an input port, requiring the order function to be updated. The order is no longer equal to infinity. The other orders ( may also be modified if, for example, this response enters before the last request is sent (see example below). In this case, order function being updated, the frame whose order equals 2 can be found and the equations (38)-(39) used accordingly. These equations are used for the third frame and so forth until all requests have been sent and their responses received (in all, 2 N ⋅ frames have to be switched). Meanwhile, delays 7i τ or IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ANGINEERING 12 12i τ (depending if a request or response is selected in the arbitration) are calculated.

  using the previous FCFS strategy and equations (38)-(39) have been reported in Table

Fig. 11 .

 11 Fig. 11. Histograms of the assessed response times.

  Discussion of results:In both cases, a conclusion can be drawn regarding the validity of both the formulae and ALGO since the maximum calculated delays exceed those obtained experimentally (overestimation), and the minimum delays are less than the measured values. As expected, results of ALGO and the formulae are identical in all cases, given that they have been based on the same principle. The discrepancies in delays, with respect to measurements, are less than 3.27% in all cases for either the analytical formulae or ALGO. Both the overestimation and accuracy of the response time assessment have thus been achieved simultaneously. The discrepancies in mean response time calculus are less than 2.01% and the shapes of both the experimental measurement and ALGO histograms are in fact very similar.

			TABLE III
	RESULTS OF THE FORMULAS, ALGO AND MEASURES
			Response times in ms
			Minimum Maximum	Mean
		Measures	10.40	21.90	16.10
	Case 1	ALGO	10.06	22.24	15.82
		Formulae	10.06	22.24	/
		Measures	10.65	22.25	16.40
	Case 2	ALGO	10.31	22.49	16.07
		Formulae	10.31	22.49	/