Thomas Bonald

Céline Comte

Fabien Mathieu

Performance of Balanced Fairness in Resource Pools: A Recursive Approach Sigmetrics 2018 -POMACS (Author version)

Keywords: Balanced fairness, parallel computing, performance evaluation. CSS 2012: Mathematics of computing → Markov processes ; Computer systems organization → Cloud computing

Understanding the performance of a pool of servers is crucial for proper dimensioning. One of the main challenges is to take into account the complex interactions between servers that are pooled to process jobs. In particular, a job can generally not be processed by any server of the cluster due to various constraints like data locality. In this paper, we represent these constraints by some assignment graph between jobs and servers. We present a recursive approach to computing performance metrics like mean response times when the server capacities are shared according to balanced fairness. While the computational cost of these formulas can be exponential in the number of servers in the worst case, we illustrate their practical interest by introducing broad classes of pool structures that can be exactly analyzed in polynomial time. This extends considerably the class of models for which explicit performance metrics are accessible.

Introduction

Today, computing infrastructures consist of thousands of servers interacting in a complex way. For example, MapReduce is able to process massive data sets by distributing

The authors are members of LINCS, see http://www.lincs.fr. Emails: thomas.bonald@telecom-paristech.fr, {celine.comte,fabien.mathieu}@nokia.com 1 the load over a large number of computers where data are located [START_REF] Lee | Parallel data processing with mapreduce: a survey[END_REF]. Similarly, the Berkeley Open Infrastructure for Network Computing (BOINC [START_REF] Anderson | Boinc: A system for public-resource computing and storage[END_REF]) offers a generic infrastructure to disseminate various tasks requiring multiple types of resources (CPU, memory, bandwidth, storage,. . . ) over a large pool of heterogeneous devices (computers, game consoles,. . . ). This approach based on resource pooling also emerges in content delivery networks, where file replication allows requests to be satisfied by multiple servers concurrently. Download tools like JDownloader1 are a basic example of this technique: they can accelerate the download of a large file by retrieving different pieces of that file, called chunks, in parallel over multiple hosting servers. In these new paradigms where resources are not isolated anymore, the performance of the underlying scheduling policy is still poorly understood, so that the service providers often rely on over-dimensioning to guarantee proper quality of service. There is a clear need to better understand the impact of scheduling and load on response times in large resource pools.

In this paper, we consider a pool of servers whose resources (like CPU or bandwidth) are shared dynamically by ongoing jobs. Each job can only be processed by some subset of servers, which represents various constraints like data locality. Grouping jobs in classes so that all jobs of the same class are served by the same subset of servers, these constraints can be represented as an assignment graph between job classes and servers. We assume that the service capacities are shared according to balanced fairness [START_REF] Bonald | Insensitive Bandwidth Sharing in Data Networks[END_REF] under these constraints, as considered in [START_REF] Shah | High-Performance Centralized Content Delivery Infrastructure: Models and Asymptotics[END_REF][START_REF] Shah | Asymptotic independence of servers' activity in queueing systems with limited resource pooling[END_REF] in the context of content-delivery networks.

Balanced fairness, which is closely related to proportional fairness [START_REF] Massoulié | Structural properties of proportional fairness: Stability and insensitivity[END_REF], has the double practical interest of leading to explicit expressions for the stationary distribution, due to the reversibility of the underlying Markov process, and to have the insensitivity property, in the sense that the stationary distribution does not depend on the service-time distribution beyond the mean. Thus, it is often considered as a desirable sharing objective, yielding simple and robust performance results. Moreover, it has recently been shown that balanced fairness naturally emerges from some simple scheduling policies. A first example is the redundant requests approach introduced in [START_REF] Gardner | Queueing with redundant requests: exact analysis[END_REF][START_REF] Gardner | Redundancy-d: The Power of d Choices for Redundancy[END_REF][START_REF] Gardner | Scheduling for efficiency and fairness in systems with redundancy[END_REF], where a given job is replicated over all servers that can process it, and the first instance to complete stops the others. Redundant requests are well suited to jobs that cannot be parallelized due to their nature or time scale, like the elementary tasks of a fine-grain computation running in a computer cluster. When jobs can be sliced into multiple chunks, balanced fairness can also be achieved under parallel processing, as shown in [START_REF] Bonald | Balanced fair resource sharing in computer clusters[END_REF]. This is typically the case in BOINC, where a given task can be split into work units, or in content distribution networks, where small parts of a file can be retrieved independently.

Unfortunately, just knowing the expression of the stationary distribution is not enough to derive performance metrics like the mean response times, even just numerically. As usual, this requires the computation of the normalizing constant, which is a notoriously hard problem [START_REF] Harrison | On normalizing constants in queueing networks[END_REF]. This is why existing results consider either small systems (e.g., 3 servers) or symmetric systems (e.g., all servers have the same service rate and each job can be processed by k servers chosen uniformly at random) [START_REF] Gardner | Queueing with redundant requests: exact analysis[END_REF][START_REF] Gardner | Redundancy-d: The Power of d Choices for Redundancy[END_REF][START_REF] Gardner | Scheduling for efficiency and fairness in systems with redundancy[END_REF]. The notion of poly-symmetry has recently been introduced to enlarge the class of tractable models but it still relies on some specific (poly-)symmetric properties of the system [START_REF] Bonald | Poly-symmetry in processor-sharing systems[END_REF].

The main contribution of this paper is a new recursive approach for computing the normalizing constant (equivalently, the probability that the system is empty) and thus the mean response times of systems under balanced fairness. Our recursive formula applies to any constraint structure, that is, any assignment graph between job classes and servers. Of course, its complexity depends on the degree of symmetry of the system, but it is not limited to strictly symmetric or poly-symmetric models. In particular, we exhibit two large classes of assignment graphs where the complexity of the formula is polynomial in the number of servers, instead of exponential: randomized assignments and local assignments. We show that these classes can be seen as generalizations of examples previously identified and analyzed in [START_REF] Gardner | Redundancy-d: The Power of d Choices for Redundancy[END_REF][START_REF] Gardner | Scheduling for efficiency and fairness in systems with redundancy[END_REF] in the context of redundant requests, and we illustrate them by a number of new examples that are practically interesting and computationally tractable. Thus, our work extends considerably the set of systems for which closed-form performance metrics are accessible, which will hopefully provide very useful insights into the behavior of large-scale resource pools.

The rest of the paper is organized as follows. In the following section, we introduce the model of a resource pool under balanced fairness and describe the sequential implementation of this policy. The recursive formula is presented in Section 3. The applications to randomized assignment and local assignment are presented in Sections 4 and 5, respectively. Numerical results are provided in Section 6. Section 7 concludes the paper.

Resource pool

We consider a model of resource pool that applies to a large variety of systems, like computer clusters or content delivery networks.

Model

Consider a resource pool with I job classes and K servers. The sets of class and server indices are denoted by I and K, respectively. For each i ∈ I, class-i jobs enter the system as a Poisson process with rate λ i . The corresponding vector of arrival rates is denoted by λ = (λ i : i ∈ I). Each job leaves the system as soon as its service is complete. For each k ∈ K, the service capacity of server k is denoted by µ k .

The class of a job defines the set of servers that are assigned to this job. It may be determined by practical constraints like data locality or result from some load balancing scheme, as explained in Sections 4 and 5. For each i ∈ I, K i ⊂ K denotes the set of servers assigned to each job of class i. Reciprocally, for each k ∈ K, I k ⊂ I denotes the set of job classes that are assigned server k, i.e., i ∈ I k if and only if k ∈ K i . All assignments can be described by a bipartite graph between classes and servers, where there is an edge between class i and server k if and only if server k is assigned to class i. We assume without loss of generality that each server is assigned at least one class. An example, referred to as the M model [START_REF] Gardner | Queueing with redundant requests: exact analysis[END_REF], is shown in Figure 1: there are 3 servers and 2 job classes; servers 1 and 2 are dedicated to job classes 1 and 2 respectively, while server 3 can serve both classes.

λ 1 λ 2 µ 1 µ 3 µ 2 Servers Job classes
Figure 1: Example of assignment graph: the M model

The system state is described by the vector x = (x i : i ∈ I) of numbers of jobs of each class. Throughout the paper, a server is said to be idle if it has no job to process while a class is said to be idle if it has no ongoing job (neither queued nor in service).

Our main notations are summarized in Table

Balanced fairness

We assume that the resources are allocated according to balanced fairness [START_REF] Bonald | Insensitive Bandwidth Sharing in Data Networks[END_REF]. Each server shares its service capacity among its assigned jobs, in a way that depends on the system state x. For each i ∈ I, we denote by φ i (x) the total service rate received by class-i jobs in state x. This is the sum of all service rates allocated by servers in K i to class-i jobs in state x. Under balanced fairness, all class-i jobs are assumed to be served at the same rate, namely φ i (x)/x i in any state x such that x i > 0 (we detail in §2.3 how this allocation may be achieved in practice.). We adopt the convention that φ i (x) = 0 if x i = 0. The capacity set C of the system is defined as the set of all feasible allocations,

C = φ ∈ R I + : i∈A φ i ≤ M i∈A K i , ∀A ⊂ I ,
where for any L ⊂ K, M (L) = k∈L µ k denotes the total service capacity of the servers in L. Under balanced fairness, the service rates are given by

φ i (x) = Φ(x -e i ) Φ(x) , ∀x ∈ N I , ∀i : x i > 0,
where e i is the I-dimensional vector with 1 in component i and 0 elsewhere, and Φ is the balance function, defined recursively by Φ(0) = 1 and

Φ(x) = 1 M i:x i >0 K i i:x i >0 Φ(x -e i ), ∀x = 0. ( 1
)
Observe that the corresponding vector φ(x) belongs to the capacity set C. Moreover,

i∈I φ i (x) = M i:x i >0 K i ,
so that each non-idle server is fully utilized. Now if job sizes are i.i.d. exponential with unit mean, the underlying Markov process is reversible and the stationary measure of the system state is given by

π(x) = π(0)Φ(x)λ x , ∀x ∈ N I , (2)
where we use the notation λ x = i∈I λ i x i .

Sequential implementation of balanced fairness

Balanced fairness assumes that each server has the ability to arbitrarily split its capacity. Yet, many real-life servers can only process jobs sequentially. We now show how to conciliate the two viewpoints by considering a sequential implementation that behaves like balanced fairness, although each server processes only one job at a time, in First-Come, First-Served (FCFS) order. In details, we exhibit two variants, introduced respectively in [START_REF] Gardner | Queueing with redundant requests: exact analysis[END_REF] and [START_REF] Bonald | Balanced fair resource sharing in computer clusters[END_REF]:

Redundant requests. Each class-i job is replicated over all servers in K i . When a job is in service on several servers at the same time, each of these servers works on a copy of the job, independently of the other servers. The service times of the copies of the same job are independent and exponential, with parameter µ k at server k.

A job leaves the system whenever any of its copies has completed its service, so after an exponential time with parameter k∈A µ k , where A is the (time-varying) set of servers working on the same job; the services of all other copies of this job are then interrupted and these copies are removed from the corresponding queues.

Parallel processing. When a job is in service on several servers at the same time, these servers are pooled to process (a single copy of) this job in parallel. The parallel processing is assumed to be perfect, so that the service rate of a job is the sum of the service capacities of the servers that are processing it. The job sizes are i.i.d. exponential with unit mean, so that the service time of a job is exponential with parameter k∈A µ k , where A is the (time-varying) set of servers processing this job.

These two variants are described by the same Markov process but rely on different assumptions. In the first model, the servers are independent and the work done by some server on some copy of a job cannot be used by the other servers; the gain of redundancy relies on the independence of the service times of the copies of each job and their specific (exponential) distribution. In the second model, the servers need to coordinate to process the same job, so that the work done by a server doesn't need to be done by other servers. This coordination can be achieved by dividing each job into small chunks that are distributed dynamically among active servers, say by some master server elected at the job arrival.

The system state defines a Markov process provided it includes the arrival order of jobs. We consider the sequence c = (c 1 , . . . , c n ) of job classes in order of arrival of the jobs, where n is the total number of jobs in the system and c p ∈ I is the class of the job in position p, for each p = 1, . . . , n, so that job in position 1 is the oldest job of the system. The state space is the set I * of all finite sequences on I. The corresponding queueing model is an order-independent queue, as introduced in [START_REF] Berezner | Order independent loss queues[END_REF][START_REF] Krzesinski | Order Independent Queues[END_REF]. The system state has the following stationary measure π [START_REF] Berezner | Order independent loss queues[END_REF][START_REF] Krzesinski | Order Independent Queues[END_REF][START_REF] Gardner | Queueing with redundant requests: exact analysis[END_REF][START_REF] Bonald | Balanced fair resource sharing in computer clusters[END_REF]:

π(c) = π(∅) n p=1 λ cp M p q=1 K cq , ∀c = (c 1 , . . . , c n ) ∈ I * . (3)
Now consider the aggregate state x = (x i : i ∈ I) of the number of jobs of each class, independently of the order of arrival of these jobs. With a slight abuse of notation, we also denote by π the stationary measure of this aggregate state and get

π(x) = c:|c|=x π(c), ∀x ∈ N I , (4)
where |c| denotes the aggregate state associated to state c. The following result shows that this stationary measure is also that obtained under balanced fairness. The proof is borrowed from [START_REF] Berezner | Order independent loss queues[END_REF][START_REF] Krzesinski | Order Independent Queues[END_REF][START_REF] Bonald | Balanced fair resource sharing in computer clusters[END_REF].

Proposition 1. The stationary measures (2) and (4) coincide.

Proof. For each x ∈ N N , the stationary measure (3) satisfies:

c:|c|=x π(c) = c:|c|=x π(∅) n p=1 λ cp M p q=1 K cq = π(0)   c:|c|=x n p=1 1 M p q=1 K cq   λ x .
The result follows by letting

Φ(x) = c:|c|=x n p=1 1 M p q=1 K cq
and partitioning the sum depending on the value of c n , which gives [START_REF] Anderson | Boinc: A system for public-resource computing and storage[END_REF].

In view of Proposition 1, the results derived in the rest of the paper equally predict the performance under balanced fairness and the sequential scheduling described above. Proposition 2 goes one step further by showing that balanced fairness is the average per-class resource allocation obtained under the sequential scheduling. The proof can be found in [START_REF] Bonald | Balanced fair resource sharing in computer clusters[END_REF]. Proposition 2. For each i ∈ I, the mean service rate of class-i jobs under the above sequential scheduling, conditioned on the number of jobs of each class in the system, is the service rate obtained under balanced fairness:

φ i (x) = c:|c|=x π(c) π(x) n p=1 cp=i (µ(c 1 , . . . , c p ) -µ(c 1 , . . . , c p-1 )) .
This proposition relates the average per-class service rates but it does not say anything about the rate perceived by each job. However, it is observed in [START_REF] Bonald | Balanced fair resource sharing in computer clusters[END_REF] that balanced fairness can be effectively realized in sequential systems by enforcing frequent job interruptions and resumptions on top of the FCFS scheduling. This extends the way Processor Sharing (PS) policy can be implemented by a round-robin scheduler in the single-server case. In the queueing model, these interruptions and resumptions are modeled by adding random routing, which leaves unchanged the stationary measure of the system state. If the interruptions are enough frequent, all jobs tend to be served at the same rate on average, which is precisely the service rate φ i (x)/x i considered in balanced fairness.

Additionally, interrupting jobs frequently allows to reach some approximate insensitivity to the job size distribution. In the limit, the resource allocation is exactly balanced fairness and the assumption of exponential service times is not required anymore. In fact, it is not even necessary to assume unit mean job sizes. The results remain the same for any mean job sizes provided λ i is interpreted as the traffic intensity of class i (quantity of work brought by class-i jobs per time unit) rather than the arrival rate of class-i jobs.

Stability condition

It is known that balanced fairness stabilizes the system whenever the vector of arrival rates λ lies in the interior of the capacity set C [START_REF] Bonald | A queueing analysis of max-min fairness, proportional fairness and balanced fairness[END_REF]. This shows that the system is stable whenever

Λ (A) < M i∈A K i , ∀A ⊆ I with A = ∅,
where for any A ⊂ I, Λ(A) = i∈A λ i denotes the total arrival rate of classes A. Equivalently, focusing on servers instead of jobs, the stability condition can be written

Λ   I \ k∈K\L I k   < M (L), ∀L ⊆ K with L = ∅. (5)
We assume that this condition is satisfied in the following and we let π denote the stationary distribution of the system state.

Performance metrics

We are interested in the mean response time T i of each job of class i. By Little's law, we have T i = L i /λ i , where L i denotes the mean number of jobs of class i.

It follows from (2) that L i = x∈N I x i π(x) = π(0) x∈N I x i Φ(x)λ x .
This expression involves the probability

ψ = π(0) = 1 x∈N I Φ(x)λ x
that the system is empty, which is the inverse of the normalizing constant. Considering ψ as a function of λ, the mean numbers of jobs follow by taking the derivative. This result was already stated for balanced fairness in [START_REF] Bonald | Calculating the flow level performance of balanced fairness in tree networks[END_REF]. The proof is recalled for the sake of completeness. Proposition 3. For each i ∈ I, we have

L i = ψλ i ∂ 1 ψ ∂λ i , ∀i ∈ I. (6)
Proof. Let i ∈ I. We have successively

L i = ψ x∈N I x i Φ(x)λ x = ψλ i x:x i >0 x i Φ(x)λ x-e i = ψλ i ∂ 1 ψ ∂λ i .

Recursive formula

We now present the main result of the paper, that is a recursive formula for computing the probability ψ that the system is empty. We then derive other recursive formulas for the mean number of jobs of each class.

Conditioning

The key idea of the recursion is to condition on the fact that some server k ∈ K is idle.

Observing that server k is idle if and only if there are no active jobs of classes I k , this occurs with probability:

ψ k = ψ x: i∈I k x i =0 Φ(x)λ x . (7)
Now consider the same pool of servers but without any traffic generated by jobs of classes I k , that is, for the vector of arrival rates λ |-k defined by λ i|-k = λ i 1 {i ∈I k } for all i ∈ I. The stationary distribution of the state of this reduced system is

π |-k (x) = ψ |-k Φ(x)λ |-k x ,
where ψ |-k is the probability that this system is empty, given by

ψ |-k = 1 x Φ(x)λ x |-k . Note that ψ |-k = 1 if I = I k .
In view of ( 7), we have:

ψ = ψ k ψ |-k , (8)
so that ψ |-k can also be interpreted as the probability that the initial system is empty given that server k is idle. Similarly, π |-k can be viewed as the conditional stationary distribution of the system state, given that server k is idle. All our results rely on this simple but powerful observation.

Probability of an empty system

The following theorem relates the probability that the system is empty to the conditional probability that it is empty, given that some server is idle. This gives a method to compute ψ recursively.

Theorem 1. The probability that the system is empty is given by

ψ = M (K) -Λ(I) k∈K µ k ψ |-k , ( 9
)
which can also be expressed as

ψ = (1 -ρ) M (K) k∈K µ k ψ |-k , ( 10
)
where ρ = Λ(I) M (K) is the overall load of the system.

Proof. We first write the conservation equation, which states that the total arrival rate must be equal to the total average service rate (accounting for idle periods):

Λ(I) = k∈K µ k (1 -ψ k ), that is, k∈K µ k ψ k = M (K) -Λ(I). (11)
Combining ( 8) and ( 11) yields ( 9), from which [START_REF] Gardner | Queueing with redundant requests: exact analysis[END_REF] follows.

The probability ψ can be computed by recursively applying ( 9) or [START_REF] Gardner | Queueing with redundant requests: exact analysis[END_REF], conditioning on the server activity. The base case of the recursion corresponds to a pool without any input, which is idle with probability 1. For each set L ⊂ K of active servers, we need to evaluate M (L) and

Λ   I \ k∈K\L I k   ,
which takes O(I +K) operations, where I is the number of job classes and K the number of servers. The overall complexity is thus in O (I + K)2 K in the worst case. Sections 4 and 5 give practically interesting examples where the complexity is polynomial in the number of servers thanks to symmetries or topological properties.

Theorem 1 and its proof reveal some important properties of the system, which we briefly detail here.

Stability The stability condition (5) appears when expanding recursion (9): the system is stable if and only if its conditional probability of being empty is positive, given any set of idle servers.

Resource pooling Assume complete resource pooling, that is, K i = K for all i ∈ I. Then, balanced fairness coincides with PS policy while the sequential scheduling coincides with First-In, First-Out (FIFO) policy, where whenever a job is served, it is served by all servers. In other words, the system boils down to an M/M/1 queue of load ρ.

This queue is empty with probability 1-ρ, which is the first factor in [START_REF] Gardner | Queueing with redundant requests: exact analysis[END_REF]. In general, the second factor, which can be written:

k∈K µ k k∈K µ k ψ |-k
, quantifies the overhead due to incomplete resource pooling. This is the harmonic mean of the conditional probabilities ψ |-k for k ∈ K, weighted by the service rates µ k for k ∈ K.

Activity rates For each i ∈ I, denote by ψ i the probability that class i is idle and by ψ |-i the probability that the system without class i is empty. As in §3.1, one can show that ψ = ψ i ψ |-i . Applying (9) to both ψ and ψ |-i , we get

ψ i = ψ ψ |-i = M (K) -Λ(I) M (K) -Λ(I \ {i}) k∈K µ k ψ |-k,i k∈K µ k ψ |-k = (1 -ρ i ) k∈K µ k ψ |-k,i k∈K µ k ψ |-k , (12)
where

ρ i = λ i M (K)-Λ(I\{i})
corresponds the load associated to class i and ψ |-k,i denotes the conditional probability that the system is empty given that class i and server k are idle, for each k ∈ K. Again, the first factor, 1ρ i , is the probability that class i is idle under complete resource pooling while the second factor quantifies the overhead due to incomplete resource pooling.

Server occupancies In view of ( 8), the recursion (10) applied to both ψ and ψ |-k gives an effective way of computing ψ k , the probability that server k is idle, for each k ∈ K. From this we can easily compute the mean number of active servers in steady state, given by K -k∈K ψ k .

Mean number of jobs

We now extend the recursion of Theorem 1 to get the mean number of jobs of each class in the system, from which we can derive the mean response times. The notations are the same as above. Theorem 2. For each i ∈ I, the mean number of class-i jobs in the system is given by

L i = λ i + k∈K\K i µ k ψ k L i|-k M (K) -Λ(I) , ( 13
)
and the mean number of jobs in the system is

L = Λ(I) + k∈K µ k ψ k L |-k M (K) -Λ(I) . ( 14
)
Equivalent expressions are

L i = ρ i 1 -ρ i + 1 1 -ρ k∈K\K i µ k ψ k L i|-k M (K) ( 15
)
and

L = ρ 1 -ρ + 1 1 -ρ k∈K µ k ψ k L |-k M (K) , ( 16
)
where ρ i = λ i M (K)-Λ(I\{i})
is the load associated to class i and ρ = Λ(I) M (K) is the overall load in the system.

Proof. Let i ∈ I. In view of (9), we have

∂ ∂λ i 1 ψ = 1 (M (K) -Λ(I)) 2 k∈K µ k ψ |-k + 1 M (K) -Λ(I) k∈K\K i µ k ∂ ∂λ i 1 ψ |-k .
We recognize the expression of the inverse of ψ given by ( 9) in the first term. Injecting this in (6) yields

L i = λ i M (K) -Λ(I) + 1 M (K) -Λ(I) k∈K\K i µ k λ i ψ ∂ ∂λ i 1 ψ |-k .
Additionally, for each k ∈ K \ K i , we have by ( 6) and ( 8),

λ i ψ ∂ ∂λ i 1 ψ |-k = ψ ψ |-k × λ i ψ |-k ∂ ∂λ i 1 ψ |-k = ψ k L i|-k .
Hence we obtain [START_REF] Lee | Parallel data processing with mapreduce: a survey[END_REF]. ( 14) follows by observing that

i∈I k∈K\K i µ k ψ k L i|-k = i∈I k∈K µ k ψ k L i|-k = k∈K µ k ψ k i∈I L i|-k = k∈K µ k ψ k L |-k .
Finally, ( 15) is a simple rewriting of (13), using

λ i M (K) -Λ(I) = λ i M (K) -Λ(I \ {i}) -λ i = ρ i 1 -ρ i and 1 M (K) -Λ(I) = M (K) M (K) -Λ(I) . 1 M (K) = 1 1 -ρ . 1 M (K) .
(16) follows by summation, observing that

i∈I ρ i 1 -ρ i = i∈I λ i M (K) -Λ(I) = ρ 1 -ρ .
As in Theorem 1, the complexity of each of these recursive formulas is O (I + K)2 K in the worst case but, again, polynomial in a number of practically interesting cases. Moreover, expressions [START_REF] Shah | High-Performance Centralized Content Delivery Infrastructure: Models and Asymptotics[END_REF] and ( 16) reveal the impact of incomplete resource pooling on performance, as the first terms of each expression, ρ i /(1ρ i ) and ρ/(1ρ), are the number of class-i jobs and the total number of jobs under complete resource pooling.

Toy example

Before presenting practically interesting applications of our recursive formula in the following two sections, we illustrate it on the M model pictured in Figure 1. Its analysis, already performed in [START_REF] Gardner | Queueing with redundant requests: exact analysis[END_REF], is now simplified by a direct application of Theorems 1 and 2. Let λ = λ 1 + λ 2 and µ = µ 1 + µ 2 + µ 3 be the total arrival and service rates in the system. The system load is ρ = λ/µ. Using the fact that

ψ |-1 = 1 - λ 2 µ 2 + µ 3 , ψ |-2 = 1 - λ 1 µ 1 + µ 3 , ψ |-3 = 1,
we get from [START_REF] Gardner | Queueing with redundant requests: exact analysis[END_REF]:

ψ = (1 -ρ) µ µ ′ ,
where

µ ′ = µ 1 µ 2 + µ 3 µ 2 + µ 3 -λ 2 + µ 2 µ 1 + µ 3 µ 1 + µ 3 -λ 1 + µ 3 .
For the mean number of jobs in the system, we have

L |-1 = λ 2 µ 2 + µ 3 -λ 2 , L |-2 = λ 1 µ 1 + µ 3 -λ 1 , L |-3 = 0, so that ψ 1 L |-1 = ψ λ 2 (µ 2 + µ 3 ) (µ 2 + µ 3 -λ 2 ) 2 , ψ 2 L |-2 = ψ λ 1 (µ 1 + µ 3 ) (µ 1 + µ 3 -λ 1 ) 2 ,
and, in view of ( 16),

L = ρ 1 -ρ + ψ µ(1 -ρ) λ 2 µ 1 (µ 2 + µ 3 ) (µ 2 + µ 3 -λ 2 ) 2 + λ 1 µ 2 (µ 1 + µ 3 ) (µ 1 + µ 3 -λ 1 ) 2 .

Randomized Assignment

We first apply our results to randomized load balancing schemes, where each incoming job is assigned to a set of servers chosen at random, independently of their current occupancy. This oblivious load balancing may cause a loss of performance compared to more sophisticated schemes, but it has the advantage of involving no central authority to dispatch jobs. As we will see, it is possible to leverage the symmetries of the system to compute performance metrics with a complexity which is polynomial in the number of servers while allowing for some heterogeneity. The complexity of the recursive formulas presented in this section and the following one, for randomized and local assignment schemes, respectively, are summarized in Table 2.

Homogeneous pool

We consider a pool of K servers, each with service rate µ. Jobs arrive at rate Kλ. Upon arrival, each job is assigned to d ≤ K servers chosen uniformly at random, independently

Randomized assignment

Local assignment Hom.

Het. degrees Het. pool Nested Hom. Het.

O(K) O(N K) O (N SK 1 • • • K S ) O(KI) O(K 2 ) O(K 3 )
Table 2: Complexities of the recursive formulas for different pool structures. Hom. and Het. stand for homogeneous and heterogeneous, respectively. K is the number of servers, N the number of job types, S the number of server groups, K s the number of servers in group s, and I the number of job classes. Each entry gives the complexity to compute the global metric L. In all structures but the homogeneous line, it is also the complexity to compute the metric L i for a specific class i.

of the current state of the system, so that all jobs have the same degree of parallelism d. Since all servers are exchangeable, the load ρ = λ/µ of the system is also the load of each server. This model was considered in [START_REF] Gardner | Redundancy-d: The Power of d Choices for Redundancy[END_REF], where is was shown that the system is stable if and only if ρ < 1. We will now apply Theorems 1 and 2 to give a simple proof of the following results given in [9, Theorems 1 and 2]:

µ µ µ K = 3 Kλ d = 2 (a) Compact representation µ µ µ Kλ Kλ ( K d ) Kλ ( K d ) Kλ ( K d ) (b) Expanded representa- tion
ψ = K ℓ=d 1 -ρ |ℓ and L = K ℓ=d ρ |ℓ 1 -ρ |ℓ , (17)
where

ρ |ℓ = 1 ℓµ ℓ d K d Kλ = ρ ℓ-1 d-1 K-1 d-1
denotes the load in the system restricted to ℓ arbitrary servers, that is, the aggregate load generated by the job classes that can only be served by these ℓ servers. These formulas can be evaluated with a complexity O(K) if we compute the binomial coefficients by recursion as follows:

ℓ -1 d -1 = 1 + d -1 ℓ -d ℓ -2 d -1 , ∀ℓ = d + 1, . . . , K,
with the base case d-1 d-1 = 1 when ℓ = d. In our framework, the class of a job defines the set of servers to which it was assigned upon arrival. There are I = K d job classes, one for each possible assignment of d servers among K. This is illustrated in Figure 2 with K = 3 servers and a degree d = 2. Since the assignment is uniform, all classes have the same arrival rate Kλ/ K d . Thanks to the exchangeability of the servers, we only need to keep track of the number of active servers and not of their exact index when conditioning on the activity of the servers.

Specifically, for each ℓ = d, . . . , K, let ψ |ℓ denote the probability that a system restricted to jobs processed by ℓ arbitrary servers is empty. In this system, the arrival rate is that of the jobs which are assigned to d of these ℓ servers, namely Kλ ℓ d / K d . The total service rate is ℓµ. Applying (10) then yields

ψ |ℓ = 1 -ρ |ℓ ℓµ ℓ µ ψ |ℓ-1 = 1 -ρ |ℓ ψ |ℓ-1 .
When there are ℓ = 1, . . . , d -1 servers left, there are no more arrivals and the system is empty with probability 1, i.e., ψ |ℓ = 1. The result announced for ψ = ψ |K follows by expanding the recursion.

Similarly, let L |ℓ denote the mean number of jobs in the system restricted to ℓ arbitrary servers, for each ℓ = 1, . . . , K. (16) yields

L |ℓ = ρ |ℓ 1 -ρ |ℓ + 1 1 -ρ |ℓ ℓµ ψ |ℓ ψ |ℓ-1 L |ℓ-1 ℓµ = 1 1 -ρ |ℓ + L |ℓ-1 ,
for each ℓ = d, . . . , K, with the base cases L |ℓ = 0 for all ℓ = 1, . . . , d -1, from which (17) follows.

Although the proof for ψ is very close to that of [START_REF] Gardner | Redundancy-d: The Power of d Choices for Redundancy[END_REF], the proof for L is greatly simplified by Theorem 2. We now see how to generalize the results to other classes of pools.

Heterogeneous degrees

Consider a first extension where jobs can have different parallelism degrees. There are still K servers in the pool, each with service rate µ, but jobs are now divided into N types. For each u = 1, . . . , N , type-u jobs arrive at rate Kλp u , with p 1 + . . . + p N = 1, so that the total arrival rate is still Kλ. Upon arrival, a job of type u is assigned to d u servers chosen uniformly at random, independently of the current state of the system. The load ρ = λ/µ of the system is also that of each server. An example with N = 2 job types is given in Figure 3.

Using Theorems 1 and 2, we can easily extend the results of the previous section. For each u = 1, . . . , N , there are K du classes associated to type u, one for each possible assignment of a type-u job to d u servers among K. All type-u classes have the same arrival rate Kλp u / K du . The exchangeability of the servers still ensures that we simply need to keep track of the number of active servers when conditioning on their activity.

For each ℓ = 1, . . . , K, let ψ |ℓ denote the probability that the system restricted to ℓ arbitrary servers is empty. For each u = 1, . . . , N with d u ≥ ℓ, there are ℓ du type-u

µ µ µ µ µ K = 5 Kλp 1 Kλp 2 d 1 = 1 d 2 = 2
Figure 3: A homogeneous pool with two degree types.

classes which are assigned to these ℓ servers, so that the remaining arrival rate of type-u jobs is Kλp u ℓ du / K du . For each u = 1, . . . , N with d u < ℓ, there are no classes associated to type u which are assigned to these ℓ servers only, so that the arrival rate for type u is zero. In this case, we adopt the convention that ℓ du = 0, so that we can still write Kλp u ℓ du / K du for the arrival rate. The total load in the system restricted to ℓ servers is then given by

ρ |ℓ = 1 ℓµ N u=1 ℓ du K du Kλp u = ρ N u=1 ℓ-1 du-1 K-1 du-1 p u .
Observe that ρ |ℓ < 1 whenever ρ < 1 because ℓ du / K du ≤ ℓ/K for each u = 1, . . . , N . Hence the system is stable whenever ρ < 1. Using the exchangeability of the servers, we can apply the same simplifications in ( 10) and ( 16) as in the homogeneous case, so that ψ and L are still given by ( 17) where ρ |ℓ is given by the expression above. These formulas can be evaluated with a complexity O(N K). If a high number R of values of the load ρ is to be considered, it is possible to precompute ρ |ℓ /ρ for each ℓ = 1, . . . , K with complexity O(N K) and then compute the results for each value of ρ with complexity O(RK), so that the overall complexity is O((N + R)K) instead of O(RN K).

Since the jobs are differentiated by their degree, it is also interesting to evaluate the performance for each type of jobs individually. It can be derived by applying [START_REF] Shah | High-Performance Centralized Content Delivery Infrastructure: Models and Asymptotics[END_REF] to each class and then summing over all classes of the same type. We obtain that the mean number of jobs of type u in the system is given by

L u = K ℓ=du ρ u|ℓ 1 -ρ u|ℓ ,
where, for each ℓ = d u , . . . , K, ρ u|ℓ is the load associated to type-u jobs in the system with ℓ servers left:

ρ u|ℓ = ( ℓ du ) ( K du ) Kλp u ℓµ - N v=1 v =u ( ℓ dv ) ( K dv ) Kλp v = ρ ( ℓ-1 du-1 ) ( K-1 du-1 ) p u 1 -ρ N v=1 v =u ( ℓ-1 dv -1 ) ( K-1 dv -1 ) p v .
The mean number of jobs of a given type can be evaluated with a complexity O(N K).

It is again possible to make some precomputations when several values of the load ρ are to be considered. These results will be used in §6.1.

Heterogeneous servers

We can further extend the model by considering server heterogeneity. We distinguish S groups of servers. For each s = 1, . . . , S, there are K s servers in group s, each with capacity µ s . Like in §4.2, we also distinguish N types of jobs. For each u = 1, . . . , N , type-u jobs arrive in the system at rate Kλp u , with p 1 + . . . + p N = 1. Upon arrival, each job of type u is assigned to d u,s servers chosen uniformly at random among the K s servers of group s, independently of the current state of the system, for each s = 1, . . . , S.

The load of the system is now given by ρ = Kλ/ S s=1 K s µ s . Such a configuration is illustrated in Figure 4, with N = 2 types of jobs and S = 2 groups of servers.

µ 1 . . . µ 1 µ 2 . . . µ 2 K 1 K 2
Type-1 jobs Type-2 jobs We now apply our framework to this heterogeneous pool. For each u = 1, . . . , N , a class associated to type u is defined by choosing independently d u,s servers within group s, for each s = 1, . . . , S. Thus there are S s=1 Ks du,s classes associated to type-u jobs, each with the same arrival rate. Since the servers from different groups are not exchangeable, we need to keep track of the number of servers within each group when conditioning on their activity.

d 1,1 d 1,2 d 2,1 d 2,2
For each ℓ = (ℓ s : s = 1, . . . , S), with ℓ s ≤ K s for each s = 1, . . . , S, we let ψ |ℓ denote the probability that the system restricted to ℓ s arbitrary servers of group s for each s = 1, . . . , S is empty. We also let L |ℓ denote the mean number of jobs in this system. By an argument similar to those of the previous sections, we obtain that the load in this restricted system is

ρ |ℓ = ρ N u=1 p u S s=1 ℓs du,s Ks du,s S s=1 K s µ s S s=1 ℓ s µ s .
Accounting for the server exchangeability within each group in [START_REF] Gardner | Queueing with redundant requests: exact analysis[END_REF] and ( 16) yields directly

ψ |ℓ = 1 -ρ |ℓ S s=1 ℓ s µ s S s=1 ℓ s µs ψ |ℓ-es and L |ℓ = ρ |ℓ 1 -ρ |ℓ + 1 1 -ρ |ℓ S s=1 ℓ s µ s ψ |ℓ ψ |ℓ-es L |ℓ-es S s=1 ℓ s µ s .
Hence we can compute ψ and L by recursion, with complexity O(N SK 1 • • • K S ), which is O(N S( K S ) S ) in the worst case. While still polynomial in K, the complexity suggests to limit the study to small values of S. If a high number R of values of the load ρ is to be considered, it is possible to precompute ρ |ℓ /ρ for each ℓ with complexity O(N SK 1 • • • K S ) and then compute the results for each value of ρ with complexity O(RSK

1 • • • K S ), so that the overall complexity is O((N + R)SK 1 • • • K S ) instead of O(RN SK 1 • • • K S ).
Similarly, applying [START_REF] Shah | High-Performance Centralized Content Delivery Infrastructure: Models and Asymptotics[END_REF] per class and then summing over all classes associated to the same type give the following recursion for the mean number of jobs of type u, for each u = 1, . . . , N :

L u|ℓ = ρ u|ℓ 1 -ρ u|ℓ + 1 1 -ρ |ℓ S s=1 ℓ s µ s ψ |ℓ ψ |ℓ-1 L u|ℓ-es S s=1 ℓ s µ s
, where ρ u|ℓ is the load associated to type-u jobs in the system with ℓ s servers left in group s, for each s = 1, . . . , S, given by

ρ u|ℓ = ρ S s=1 ( ℓs du,s ) ( Ks du,s ) p u S s=1 Ksµs S s=1 ℓsµs 1 -ρ    N v=1 v =u S s=1 ( ℓs dv,s ) ( Ks dv,s ) p v    S s=1 Ksµs S s=1 ℓsµs
.

It is again possible to make some precomputations when several values of the load ρ are to be considered.

Local Assignment

In the previous section, we have assumed that a job could be assigned to an arbitrary subset of servers. This large degree of freedom can be difficult to implement in practice. For example, one may want to select physically-close servers in order to minimize the communication overhead. This is what we call local assignment.

In this section, we abstract the concept of localization by introducing line pools, where servers are assumed to be located along a line and indexed by the integers 1, . . . , K so that servers i and j are at physical distance |i -j|. The locality constraint is modeled by the assignment graph: each job class is assigned to an integer interval. For ease of notation, we identify a class and its assigned range: i, j denotes the class that is assigned servers i to j. An illustration of a line pool is given in Figure 5.

The rest of the section is organized as follows. We first introduce nested pools, a special type of line pools introduced in [START_REF] Gardner | Scheduling for efficiency and fairness in systems with redundancy[END_REF]. We then study arbitrary line pools, followed by a local version of the randomized schemes studied above. We conclude the section by giving the behavior for a ring structure.

λ 1,3 λ 2,5 λ 1,2 λ 4,5 µ 1 µ 2 µ 3 µ 4 µ 5
Figure 5: A line pool

Nested structures

A pool is said to be nested if the following property is verified:

∀i, j ∈ I, K i ∩ K j = ∅ =⇒ K i ⊂ K j or K j ⊂ K i .
Thus, if two jobs share a server, then the servers assigned to one of these jobs form a subset of the servers assigned to the other job. Without loss of generality, we can always assume that class 1, K, which is assigned to all servers, exists. Otherwise, as observed in [START_REF] Gardner | Scheduling for efficiency and fairness in systems with redundancy[END_REF], we can split the pool into smaller, independent, nested pools, and consider each sub-pool separately. While a line pool is not necessarily a nested pool (consider for example classes 1, 3 and 2, 5 in Figure 5), the converse holds:

Proposition 4. A nested pool is a line pool.
Proof. We first remark that a nested pool has a natural tree structure, which can be built as follows. The nodes are the servers and the job classes. The parent of a server is the smallest class, in the sense of inclusion, assigned to it. The parent of a class is the smallest class that includes it, if any. By construction, servers are always leaves, while the tree root is exactly the class that is maximal for the inclusion, i.e., class 1, K.

To conclude, we just have to label the servers in their order of appearance in a depthfirst traversal of the tree. By construction, the servers assigned to a given class, which are exactly the leaves of the subtree rooted in that class, will have consecutive labels.

An example of nested pool is given in Figure 6. Nested pools are another good example of application of our recursive formula. It was shown in [START_REF] Gardner | Scheduling for efficiency and fairness in systems with redundancy[END_REF] that a nested system is empty with probability

ψ = i∈I (1 -ρ |i ), (18)
where

ρ |i = λ i k∈K i µ k -j:K j K i λ j λ 1,5 λ 1,3 λ 1,1 λ 2,3 λ 4,4 µ 1 µ 2 µ 3 µ 4 µ 5
Figure 6: Tree representation of a nested pool is the load associated to class i in the system restricted to servers K i . With our recursive approach, proving (18) becomes quite straightforward. Using (9), we get

ψ = M (K) -Λ(I) k∈K µ k ψ |-k = (1 -ρ |1,K ) M (K) -Λ(I \ {1, K}) k∈K µ k ψ |-k .
We then remark that if any server k is idle, so is class 1, K. Hence the second factor of the expression above is exactly the right-hand side of (9) for a system where class

1, K is removed, that is ψ |-1,K . Thus, ψ = (1 -ρ |1,K )ψ |-1,K , from which (18) follows.
Note that (18) can also be proved with a more class-oriented approach. Conditioning on the activity of class 1, K, we get the conservation equation:

i∈I λ i = k∈K µ k (1 -ψ 1,K ) +   i∈I\{1,K} λ i   ψ 1,K .
Rearranging the terms gives:

ψ 1,K = M (K) -Λ(I) M (K) -Λ(I \ {1, K}) = 1 -ρ |1,K .
The result then follows from the equality ψ = ψ 1,K ψ |-1,K . These proofs give some insight on the factors in (18). For example, we see that the equality ψ i,j = 1ρ |i,j is only true when i, j = 1, K. Indeed, the proof consists in removing the classes one after the other in a graph traversal, showing that 1ρ |i,j is the probability that class i, j is idle, given that all its ancestors in the tree (if any) are idle.

The mean number of jobs of each class, which was also given in [START_REF] Gardner | Scheduling for efficiency and fairness in systems with redundancy[END_REF], can be derived using [START_REF] Lee | Parallel data processing with mapreduce: a survey[END_REF]. It is a special case of (20) that will be stated for the line pools.

Line structures

We now remove the nested assumption and show how to apply the recursive formula to any line pool.

Proposition 5. The probability that a line system is empty is given by

ψ = M (K) -Λ(I) K k=1 µ k ψ |1..k-1 ψ |k+1..K , (19)
where for each k, ℓ, |k..ℓ denotes the system reduced to servers k to ℓ.

For each i, j ∈ I, the mean number of class-i, j jobs satisfies

L i,j = λ i,j + ψ i-1 k=1 µ k L i,j|k+1..K ψ |1..k-1 ψ |k+1..K + K k=j+1 µ k L i,j|1..k-1 ψ |1..k-1 ψ |k+1..K M (K) -Λ(I) , ( 20
)
while the total mean number of jobs satisfies

L = Λ(I) + ψ K k=1 µ k L |1..k-1 +L |k+1..K ψ |1..k-1 ψ |k+1..K M (K) -Λ(I) . ( 21
)
Proof. The key of the proof is that when we remove some server k from a line pool, we get two independent line pools, in the sense that the remaining classes I \ I k are split into two sets: those processed by servers 1 to k -1 and those processed by servers k + 1 to K. This yields ψ |-k = ψ |1...k-1 ψ |k+1...K . Equation ( 19) then follows from [START_REF] Gardner | Redundancy-d: The Power of d Choices for Redundancy[END_REF].

For the mean number of jobs, we have In view of Proposition 5, the computation of ψ can be done in time O(K 3 ). First, we precompute the total arrival and service rates of all pools reduced to servers k to ℓ, for all k and ℓ such that 1 ≤ k ≤ ℓ ≤ K, which incurs a cost in O(K 2 ). Then, the computational cost of each term ψ |k..ℓ is in O(K), and there are O(K 2 ) such terms, hence a global cost O(K 3 ). Keeping the different values of ψ |k..ℓ in memory, the same complexity argument holds for (20) and (21). The mean number of jobs of any class i, j and the total number of jobs can be computed in time O(K 3 ).

L i,j|-k =    L i,j|k+1..K if k < i, L i,j|1..k-1 if k > j, 0
Note that Proposition 4 ensures that the above recursive formulas also apply to nested pools. However, the equations derived in §5.1 for nested pools are simpler to compute: for example, using the tree structure of the classes, one can verify that the computational cost of (18) is O(IK), against O(K 3 ) for a generic line pool. Reminding that I = O(K 2 ), with I possibly much lower than K 2 , nested formulas should be preferred when the pool is nested.

It is tempting to adapt the method presented here for line pools to other topologies. For example, one could consider a grid structure where job classes would correspond to rectangles of servers. However, the method does not apply, as removing a server does not yield to independent sub-systems in general. A notable exception, considered in §5.4, is the ring topology.

Load balancing

Section 4 investigated randomized assignment where a fixed number of servers were chosen at random in a pool. We show here that these results can be transposed to line pools. We only consider the homogeneous case; the cases of heterogeneous degrees or servers can be treated in the same way. As in §4.1, we consider K servers, each with service rate µ. Jobs arrive at rate Kλ, so that the system load is ρ = λ/µ. Upon arrival, each job is assigned to a range of d ≤ K servers chosen uniformly at random among the I = Kd + 1 possible ranges of size d, so that the arrival rate for each of the I classes is Kλ K-d+1 . An example is pictured in Figure 7. As d is constant, we label a class by its lowest server, i.e., i instead of i, i + d -1. Remark that, unlike what happens for the non-local case considered in §4.1, the classes are not equivalent. For example, in Figure 7, class 1 has an exclusive use of server 1, while class 3 shares its three servers.

Kλ µ µ µ µ µ µ λ 1-d-1 K λ 1-d-1 K λ 1-d-1 K λ 1-d-1 K
ψ |1..ℓ = 1 -ρ |1..ℓ 1 ℓ ℓ k=1 1 ψ |1..k-1 ψ |1..ℓ-k , ( 22
)
for ℓ ≥ d, where

ρ |1..ℓ = 1 -d-1 ℓ 1 -d-1 K ρ.
For each i ∈ 1, . . . , I, the mean number of class-i jobs is L i = L i|1..K , where L i|1..ℓ can be computed recursively by L i|1..ℓ = 0 for ℓ < d and

L i|1..ℓ = ρ |1..K 1-d-1 K + ψ |1..ℓ i-1 k=1 L i-k|1..ℓ-k ψ |1..k-1 ψ |1..ℓ-k + ℓ k=i+d L i|1..k-1 ψ |1..k-1 ψ |1..ℓ-k ℓ(1 -ρ |1..ℓ ) ( 23
)
for ℓ ≥ d.

The total mean number of jobs in the system is L = L |1..K , with L |1..ℓ = 0 if ℓ < d and

L |1..ℓ = ρ |1..ℓ + ψ |1..ℓ ℓ ℓ k=1 L |1..k-1 +L |1..ℓ-k ψ |1..k-1 ψ |1..ℓ-k 1 -ρ |1..ℓ (24)
otherwise.

Proof. The result follows from Proposition 5 on observing that the pool restricted to servers ℓ + 1 to K is equivalent to the pool restricted to servers 1 to Kℓ, for any ℓ < K.

The recursions ( 22) and (24) use O(K) values of ψ and L, and each of them can be computed in O(K) if previous results are kept in memory, resulting in O(K 2 ) time complexity. For (23), there are O(K 2 ) values to compute, hence a computational cost in O(K 3 ). Despite important symmetries, there is no complexity gain for per-class performance compared to the general case, because classes remain heterogeneous. However, an improvement of factor K is achieved for the global indicators ψ and L.

It is worth noting that, despite heterogeneity, the stability condition is simply ρ < 1. The reason is that the sub-systems are less loaded than the main system: the sub-system restricted to servers 1 to ℓ has load ρ |1..ℓ ≤ ρ.

Ring structure

To suppress the class asymmetry inherent to line pools, we now consider a ring pool where servers 1 and K are at distance 1, as illustrated in Figure 8. To simplify formulas, we use implicit congruence modulo K: server K + i is server i, and for 1 ≤ j < i ≤ K, i, . . . , j denotes the servers i to K and 1 to j. For example, in Figure 8, class-5, 2 jobs are assigned servers 5, 1 and 2. The following result is a simple consequence of Proposition 5, after noticing that removing server k from a ring gives the line pool k + 1, . . . , k -1.

µ 1 µ 2 µ 3 µ 4 µ 5 λ 2,3 λ 3,1 λ 5,2
Proposition 7. The probability that a ring system is empty is given by

ψ = M (K) -Λ(I) K k=1 µ k ψ |k+1..k-1 , ( 25
)
where ψ |k+1..k-1 is obtained using (19).

For each i, j ∈ I, the mean number of class-i, j jobs in the system is given by

L i,j = λ i,j + ψ k∈j+1..i-1 µ k L i,j|k+1..k-1 ψ |k+1..k-1 M (K) -Λ(I) , ( 26
)
and the total mean number of jobs in the system is

L = Λ(I) + ψ K k=1 µ k L |k+1..k-1 ψ |k+1..k-1 M (K) -Λ(I) , ( 27
)
where L i,j|k+1..k-1 and L |k+1..k-1 are obtained using (20) and (21).

The complexity of each of these recursions is in O(K 3 ). For a homogeneous ring of load ρ and range size d < K, the complexity is reduced to O(K 2 ). In this case, all classes are equivalent and we only need to focus on the global metrics ψ and L, given by

ψ = (1 -ρ)ψ |1..K-1 and L = ρ 1 -ρ + L |1..K-1 , (28)
where ψ |1..K-1 and L |1..K-1 are the metrics associated with the line system restricted to servers 1, . . . , K -1, with load

ρ |1..K-1 = ρ 1 - d -1 K -1 .
The ring topology is commonly used in Distributed Hash Tables (DHT) to access resources in a decentralized fashion, as in the Chord protocol [START_REF] Stoica | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF]. In the ring space, a portion is a connected subset. We can easily imagine how to use a DHT to dispatch jobs to a pool of servers: it would be enough to let the DHT index the servers; when a job enters the system, it contacts one indexing node that returns the set of servers that are mapped to its monitoring area. The resulting pool would behave exactly like a ring pool.

Numerical Evaluation

We now illustrate the previous results through two studies: relevance of the parallelism degree to achieve implicit service differentiation, and performance degradation due to localized load balancing. Observe that, given the complexity of the involved performance metrics, these studies would not have been possible without our recursive formulas.

For easing the display of the results, the performance of class-i jobs is quantified by the inverse of the mean response time, 1

T i . This metric also happens to be the mean service rate γ i received by the jobs of class i, as we have

γ i = x π(x)φ i (x) x π(x)x i = λ i x π(x)x i = λ i L i = 1 T i ,
where the second equality holds by the conservation equation.

Gain of differentiation

Consider a resource pool with two types of jobs called regular and premium. A natural way of differentiating services consists in assigning premium jobs to more servers than regular jobs. We are interested in assessing the actual impact of this approach on performance.

For the numerical results, we consider K = 100 servers with unit service rates; regular jobs have a parallelism degree 6 while premium jobs have a degree 12. This corresponds to the model of §4.2, with N = 2 job types, regular and premium. We first focus on the influence of load on the efficiency of the service differentiation.

Impact of load Figure 9 shows the mean service rates as a function of the system load ρ, for three population distributions: regular jobs only, premium jobs only, and a mixed population where regular and premium jobs generate half of the load. The service qualities of the two types are clearly different. When the load is low, the service rate of premium jobs is roughly twice that of regular jobs. Intuitively, if the arrivals are rare, then it is likely that a new job finds all its servers free upon arrival. The ratio between the service rates of premium and regular jobs decreases with the load but remains significant until the load is extreme. Premium and regular jobs results are shown in Figure 12. First observe that the hierarchy between line, ring and global allocations is preserved throughout the experiments. Figure 12a shows the impact of the load ρ on performance. The mean service rate in the ring is close to that of the line when the load is low, but it has the same asymptotic as the mean service rate in the global scenario when the load tends to 1. Intuitively, the cost of locality prevails at low load and impacts both the line and the ring; when the load is higher, the cost of heterogeneity is the main source of performance degradation and impacts only the line.

Figure 12b studies the impact of the parallelism degree d on performance. First observe that the mean service rate increases with the degree in each case. This increase is much faster in the global and ring scenarios than in the line scenario. Our interpretation is the following. In the line scenario, the total number Kd + 1 of classes decreases with d, hence performance suffers from a lack of diversity in the assignment compared to the global and ring cases.

Lastly, Figure 12c gives the evolution of the performance as a function of the number K of servers. It was proved in [START_REF] Gardner | Redundancy-d: The Power of d Choices for Redundancy[END_REF] that the mean service rate in the global scenario has a limit when K tends to infinity. This is consistent with the results of Figure 12c, which suggests that a limit also exists in the ring and line scenarios. Note that the convergence is quite fast in the ring, and non-monotonic in the line. The behavior for the line can be intuitively explained by the heterogeneity of the number of classes per server: for example, when K is close to d, a majority of the servers can serve all Kd + 1 classes; when K = 2d, there are exactly two servers that can serve k classes for each k = 1, . . . , d, so there is a lot of heterogeneity between servers. For larger values of K, the cost of heterogeneity in the line fades away as it becomes a border effect from classes and servers located near the edges; this explains why it seems that the line and ring scenarios share the same limit: as K increases, only the cost of locality prevails.

All these results show that local load balancing has a cost in terms of performance that depends on the parameters. However, keeping in mind that a local allocation may be more simple to implement in a real system and has no impact on the stability, we believe that it can be a viable option. Remark that whenever possible, a ring structure should be preferred to a line structure.

Conclusion

In this paper, we have considered a resource pool model where operational constraints like data availability, locality, or allowed degree of parallelism are represented by an assignment graph between job classes and servers. Resources are allocated by applying balanced fairness under these constraints. Although ideal, this resource allocation can be implemented in practice by some sequential FCFS scheduling at each server. Our main contribution is a new recursive formula to compute the performance metrics under an arbitrary assignment graph. The key ingredient is the observation that the idling probability of each server can be derived by comparing the behavior of the system with and without this server.

Although the complexity of our formula is exponential in the number of servers in general, it provides a unified framework for analyzing balanced fairness in resource pools, which allows to simplify the study in many practically interesting cases. Specifically, we have identified two classes of models where the equivalence of the servers or the structure of the assignment graph lead to simplifications making the complexity polynomial, enabling an exact evaluation of their behavior.

For future works, we would like to identify other classes of resource pools where performance is made tractable by our formula. We are also interested in deriving more intuition on the impact of the assignment graph on performance. We hope that our work will stimulate further studies on resource pools under balanced fairness.

Figure 2 :

 2 Figure 2: A homogeneous pool

Figure 4 :

 4 Figure 4: A heterogeneous pool with two degree types.

  otherwise, and L |-k = L |1..k-1 + L |k+1..K . The recursive formulas (20) and (21) then follow from (13) and (14), respectively.

Figure 7 :

 7 Figure 7: A homogeneous line pool

Figure 8 :

 8 Figure 8: A ring pool

Figure 9 :

 9 Figure 9: Impact of load on service differentiation for different populations. Top plotsgive the performance of premium jobs and bottom plots that of the regular jobs.

Figure 12 :

 12 Figure 12: Overall impact of the parameters (default values: K = 100, d = 10, ρ = 0.9)

Table 1 :

 1 . Table of notation.

		Servers		Job classes
	K	Set of servers	I	Set of classes
	K	Number of servers	I	Number of classes
	µ k	Service rate of server k	λ i	Arrival rate of class-i jobs
	M (L) Total service rate of servers	Λ(A)	Total arrival rate of classes
		L ⊂ K		A ⊂ I
		Assignment graph
	K Performance metrics
	ψ	Probability that the system is idle
	L	Mean number of jobs

i Servers assigned to class-i jobs I k Classes that are assigned server k |k System reduced to servers in K \ {k} and to jobs that are not assigned server k |L System reduced to servers in L and to jobs that are assigned servers in L ⊂ K only

http://jdownloader.org

seem to have asymptotically the same service rate as ρ tends to 1. This convergence is somehow expected, as maintaining a minimal ratio greater than 1 at very high load could jeopardize the stability of the system for regular jobs.

Interestingly, the service rate of premium jobs is lower when half of the population consists of regular jobs. The reason is that the slowness of regular jobs penalizes premium jobs, as they stay longer in the system. This also explains the gain of performance for regular jobs when population is mixed. This is particularly visible at higher load, when the job interactions intensify.

Impact of distribution Following up with the last observation, we focus on the impact of the proportion of regular and premium jobs in the population. Since we observed that this impact is stronger when the load is high, Figure 10 gives the mean service rate under loads ρ = 0.9 and ρ = 0.99, as a function of the ratio of the arrival rate of regular jobs to that of premium jobs. This figure confirms that the differentiation ratio decreases with the load, and shows that the population distribution has a limited impact on performance. When ρ = 0.9, both regular and premium jobs suffer about 25% rate degradation between the best (premium only) and worst (regular only) scenarios. When ρ = 0.99, the loss is limited to 14% approximately. This relative insensitivity of performance with respect to the population distribution is a positive result since this distribution may not be known a priori by the service provider.

Overall, these results show that randomized load balancing with variable degree of parallelism is an efficient way of achieving service differentiation despite its simplicity. We also saw in Section 4 that it guarantees stability as soon as the overall load is less than 1.

For other degree parameters, numerical results (not displayed here) are qualitatively similar: there is a differentiation proportional to the degree ratio when the load is low, which tends to fade at extreme loads.

Impact of locality

We now study the impact of locality on the performance of randomized load balancing. We consider a pool of K homogeneous servers with unit service rate. Each incoming job is assigned to a set of d servers chosen uniformly at random among the authorized assignments. We consider the following assignment configurations, which were studied in §4.1, §5. We first investigate the general performance hierarchy between these three configurations.

Costs of heterogeneity and locality

As observed in §5.3, the performance experienced by a job in a line scenario depends on its assignment. Figure 11 shows the mean service rate per class in the line, compared to the overall mean service rate in each scenario. Performance heterogeneity in the line increases with the load, which leads to a degradation of the overall performance compared to the other scenarios. We call this the cost of heterogeneity. The ring scenario performs better than the line but not as well as the global case. This is the cost of locality, which we interpret as follows: the locality of assignments in line and ring scenarios reduces the diversity of classes compared to a global assignment; it is more frequent to have two classes sharing a high number of servers, which degrades the overall performance.

Impact of parameters To better understand these phenomena, we let the parameters K, d and ρ vary around the following default values: K = 100, d = 10 and ρ = 0.9. The


Driss Sadoun

Catherine Dubois

Yacine Ghamri-Doudane

Brigitte Grau

From Natural Language Requirements to Formal Specification using an Ontology

Keywords: Knowledge representation, Ontology population, Ontology reasoning, Requirement specification

In order to check requirement specifications written in natural language, we have chosen to model domain knowledge through an ontology and to formally represent user requirements by its population. Our approach of ontology population focuses on instance property identification from texts. We do so using extraction rules automatically acquired from a training corpus and a bootstrapping terminology. These rules aim at identifying instance property mentions represented by triples of terms, using lexical, syntactic and semantic levels of analysis. They are generated from recurrent syntactic paths between terms denoting instances of concepts and properties. We show how centring on instance property identification allows us to precisely identify concept instances explicitly or implicitly mentioned in texts.

I. INTRODUCTION

Any software system development process is based on a primary phase involving requirement specifications. Usually, formal methods only apply to formal specifications in order to verify their correctness and consistency. However, experience shows that requirement specifications are mostly written in natural language (NL) and thus are informal. Their verification then requires them to be transformed into formal specifications. Hence, it is quite natural to question the possibility of automatizing the transformation of NL requirement specifications into formal requirement specifications. This now long-standing issue has been addressed in different ways [START_REF] Gordon | Generating executable scenarios from natural language[END_REF], [Kof, 2010], [Njonko and El Abed, 2012]. These studies underline the common difficulty in obtaining a direct transformation and the need of an intermediate model to bridge the gap between NL specifications and formal specifications. The generally proposed intermediate representations do not check the consistency of what they model, such as for message sequence charts (MSCs) [Kof, 2010], live sequence charts (LSCs) [START_REF] Gordon | Generating executable scenarios from natural language[END_REF] or Semantics of Business Vocabulary and Business Rules (SBVR) [START_REF] Bajwa | Resolving syntactic ambiguities in natural language specification of constraints[END_REF].

We have chosen an OWL ontology to model formally the domain knowledge and to represent the requirement specifications by its population so that its formal context and its reasoning capability allows us to make verifications at an early stage. An ontology models concepts and properties, defining the conceptual vocabulary of a domain and gives a formal framework which associates semantics to terms in NL. The joining of concepts and properties with their formulations in texts is done by using a lexical ontology in Simple Knowledge Organization System (SKOS) that contains the terminology associated to the conceptual vocabulary.

Populating an ontology consists in adding new instances, associated to concepts and properties recognized in texts, without changing its conceptual structure. Their identification may focus on the recognition of concept instances [START_REF] Thongkrau | Ontopop: An ontology population system for the semantic web[END_REF], or on the recognition of relation instances [Nakamura-Delloye, 2011]. In both cases the recognition is limited to the surface of the text, whereas the recognition of identical instances and implicit knowledge requires to infer its meaning at a semantic level.

In this article, we propose a new method which guides the ontology population process by the identification of triples in texts. These triples correspond to mentions of property instances. We distinguish two types of triples: complete and partial. Complete triples contain the mentions of a property and the two concepts it links while partial triples aim at recognizing properties in which one of the linked instances is not explicitly mentioned. Triples of terms corresponding to property instances are extracted using extraction rules formed from recurrent syntactico-semantic forms appearing in a training corpus using a bootstrapping terminology. By guiding the ontology population through the identification of property instances we can resolve ambiguities of terms and infer implicit informations in the ontology. In this way, the identification of instances of concepts not only relies on the recognition of their mentions in texts but also takes into account the conceptual properties where they are involved, providing a semantic context of interpretation.

We show how our approach allows us to reliably identify property instances, and then to infer the associated instances of concepts. Furthermore, the consistency of identified instances is checked using the OWL reasoner before the creation of consistent operation rules in order to represent the user requirements. Throughout the paper examples are taken from our application domain: smart spaces.

II. RELATED WORK

It is commonly adopted that a direct transition between NL specifications and formal specifications is not conceivable. Intermediate representations aim at restricting [START_REF] Gordon | Generating executable scenarios from natural language[END_REF] or structuring [START_REF] Ilieva | Representing textual requirements as graphical natural language for uml diagram generation[END_REF] the NL specifications, as well as overcoming their inherent lack of context [START_REF] Bajwa | Resolving syntactic ambiguities in natural language specification of constraints[END_REF]. However most of the proposed representations remain semi-formal. In our approach, we use an OWL ontology to formally represent the background knowledge to tackle ambiguities resulting from the mismatch between lexical and conceptual meaning.

The usual assumption for the recognition of concept and property mentions in texts is that pairs of entities appearing in the same context can be considered as instances of the same relationship. Some methods restrain the definition of the context on the presence of a verb and the recognition of its neighbourhood [START_REF] Lin | Discovery of inference rules for question answering[END_REF], [START_REF] Makki | Ontology Population via NLP Techniques in Risk Management[END_REF]. Other methods rely on the classification of pairs of entities known to be linked by a semantic relationship [START_REF] Hasegawa | Discovering relations among named entities from large corpora[END_REF], [Nakamura-Delloye, 2011], [START_REF] Thongkrau | Ontopop: An ontology population system for the semantic web[END_REF]. The majority of these approaches exploit lexical and syntactic knowledge. However the context is more likely to be captured by exploiting semantic as a third level of knowledge. Thus, we propose to acquire automatically rules based on three levels.

Extracting from text pieces of information necessary to represent requirements such as operation rules may consist in matching lexical formulation with their semantic meaning [Njonko and El Abed, 2012], [START_REF] Bajwa | Resolving syntactic ambiguities in natural language specification of constraints[END_REF]. We propose to represent these pieces by means of ontology population. Reasoning on the ontology allows us to infer the semantic classes to which instances of concepts belong. We propose to go beyond instance classification, by identifying instances representing identical individuals, through the use of unique constraints formed on instance properties. This way, the consistency of matched elements is checked.

III. EXTRACTION RULES ACQUISITION

We use the following notations throughout the article. Concept and property names appear in italic and begin with a capital letter. Instances of concept names appear in italic and are written in lower case. A concept is noted C i and an instance of a concept is noted i Ci . Properties are defined on a domain and a range1 . Properties linking concepts are noted P k (C i , C j ) and an instance of a property is noted P k (i Ci , i Cj ). In texts, instances of concepts and properties are denoted by terms. Thus, mentions of an instance of a property between two instances of concepts is a triplet noted (t P k , t Ci , t Cj ) with t P k , t Ci and t Cj terms denoting respectively instances of the property P k and the concepts C i and C j .

A. Two kinds of rules

Identification of concept instances is guided by the identification of instance properties. Hence, each extraction rule aims at identifying a mention of a property defined in the ontology. We distinguish two sorts of triples. On the one hand complete triples where both mentions of domain and range of the property are explicit in the text, (t P k , t Ci , t Cj ). On the other hand partial triples where one of these mentions is not explicit in the text. It is then marked as unknown in the triple, with either (t P k , ?i, t Cj ) or (t P k , t Ci , ?i). For example, in the sentence: when a person moves into the kitchen, switch on the light., we can identify the triple (Occurred-in, move, kitchen) which denotes an instance of the property Occurred-in linking an instance of a concept P henomenon to an instance of a concept Location. However, the agent which has to turn on the light is not explicit. In this case the triple to be identified is (Turn-on 2 ,?A,light) which denotes an instance of the property Turn-on linking an instance of a concept Actuator to an instance of a concept Physicalprocess.

B. Acquisition method of extraction rules

The acquisition of extraction rules is performed automatically by bootstrapping using a training corpus and a starting terminology. Rules are acquired from the most frequent syntactic paths between pairs of terms. These terms are issued from the semantic classes defined in the ontology. The extraction of the two sorts of triples implies the acquisition of two sorts of extraction rules. Partial triples are acquired from the most frequent paths between terms denoting instances of a property and an instance of its domain or range. Complete triples are formed using two partial paths between pairs of terms denoting an instance of a property and its domain and the same property and its range.

Algorithm 1 describes the rule acquisition process. Each sentence is analysed and its syntactic dependency tree generated. Then, three functions are called for path extraction between pairs of terms. These functions identifies paths linking three sorts of pairs: pairs of terms denoting instances of domain and range of a same property, pairs of terms denoting instances of a property and its range and pairs of terms denoting instances of a property and its domain. Extracted paths are compared according to their syntactic dependencies and the lemmatized form of their terms. Identical paths are grouped and the n most frequent paths of each sort of pairs are returned. Finally, extraction rules are generated from the features of the returned paths.

C. Syntactic path

A syntactic path is a sequence of syntactic dependencies in a dependency tree, linking two terms that can be related by the mention of the studied property. Each node in the tree is labelled by a term and its morpho-syntactic category. Figure 1 represents the syntactic dependency tree of the sentence When a person moves into the kitchen, switch on the light. The dependency path between the terms moves denoting an instance of a concept Phenomenon and kitchen denoting an instance of a concept Location is prep(moves, into)-pobj(into, kitchen) (bold in figure 1).

D. Generation of extraction rules

Extraction rules aim at identifying property instances. Hence, they model the semantic context in which terms denoting instances of concepts appear. The generation of extraction rules is automatically done and exploit the features of the selected paths. These features are of three forms:

1) syntactic dependencies, transformed into predicates; 2) morpho-syntactic categories.

3) termino-ontological categories (semantic features); Example: One of the recurrent paths between the two sets of terms of the concept Phenomenon and Location which are the domain and range of the property Occurred-in is prep(t P , t O ) ∧ pobj(t O , t L ), as in figure 1, thereby generating the extraction rule associated to the property Occurredin(Phenomenon,Location) with T Loc , T Occ-in , T P hen three sets of terms from the lexical ontology.

prep(t P , t O ) ∧ pobj(t O , t L ) (1) ∧isV erb(t P ) ∧ isP rep(t O ) ∧ isN oun(t L ) (2) ∧T P hen (t P ) ∧ T Occ-in (t O ) ∧ T Loc (t L ) (3) → Occurred -in(t P , t L ) IV. TERMINOLOGY EXPANSION
The terminology is represented in SKOS. This formalism enables to define for each term a preferred formulation as well as a list of synonyms. In order to enlarge the starting terminology, we apply the acquired rules on the training corpus for extracting new terms. Each rule is applied three times. Each application aims at extracting terms denoting a semantic set involved in the rule. For example, let R an extraction rule and T Domain , T Range , T P rop three sets of terms. From rules that extract complete triples, we generate:

R(T Domain + T P rop ) → T Range R(T Range + T P rop ) → T Domain R(T Domain + T Range ) → T P rop
When all possible rules have been applied, we compute the pertinence of a term t extracted by the rules R i through the formula: P ertinence(t) = ( n i=1 f req(t, R i )) * n with f req the frequency of t relative to a rule, n the number of rules of the same type from which it was extracted. Thus, a term extracted twice by three rules has a greater score than a term extracted six times by the same rule. This formula aims to promote the terms extracted by several rules.

V. ONTOLOGY POPULATION

The aim of NL specification analysis is to recognize user requirements of a system in order to formalize them. These requirements describe the behaviour of the system as needed by the user and are created according to the property instances extracted by the extraction rules. These requirements correspond to operation rules of the form antecedent → consequent. Such a rule means that if the antecedent hold then the consequent must also hold. Each of the antecedent and consequent is a conjunction of predicates that match concepts and properties modelled in the ontology. Our final aim is to check the consistency of these rules according to their interactions. However, these verifications cannot be done by an OWL reasoner, which cannot reason on different sequencing of rules or represent state changes due to OWL open world assumption. Thus we have choose to represent the operation rules in the ontology so that they can be translated into a formal specification language in order to perform model checking.

A. Requirement pattern

Analogically to LSCs [START_REF] Gordon | Generating executable scenarios from natural language[END_REF], MSCs [Kof, 2010] representations used to guide requirement identification, but bearing in mind the need for consistency, we propose to model requirement patterns formed on ontology predicates whose consistency has been previously verified. Therefore, we defined a concept named Requirement-pattern with two data properties, Antecedent and Consequent, the values of which being a predicate that is either a unary predicate corresponding to a concept or a binary predicate corresponding to a property. Predicate arguments are either variables (Variable names start by "?") or constants (individuals or data type values). An instance of the concept Requirement-pattern will have as many values for the property Antecedent than it has predicates. However, value of the property Consequent is only a binary predicate which corresponds to the property to deduce between concept instances of the antecedent. Predicates of the Consequent part and constants are text dependent elements that we call the dynamic part of the pattern in the rest of the paper.

Each instance of Requirement-pattern corresponds to a type of operation rule. These instances will guide the identification of user requirements. It consists in replacing elements of the dynamic part by the corresponding elements extracted from specifications. For example, the instance of Requirement-pattern illustrated in Figure 2, defines a type of operation rules which states that a phenomenon ?e that occurs in the zone of sensing l of a sensor ?s and shares the same type t, will entail the corresponding actuator ?a (same location and same managed type) to perform an action Actuate-on on the physical-process p. Dynamic predicates that have to be retrieved from text are those of the property Antecedent containing the constants l or t, and for the property Consequent a predicate representing a sub-property of Actuate-on i.e. Turn-on, Turn-off, Increase or Decrease.

B. User requirement recognition

A user requirement is created if one of the requirementpattern can apply i.e. if all elements of the dynamic part are identified. The algorithm 2 describes the ontology population process. We apply all acquired extraction rules on each sentence of the NL specifications. Extracted property instances are then checked according to the dynamic parts of the requirement patterns. Each predicate of the dynamic parts is searched in the set of property instances. When a dynamic predicate is found, we replace its dynamic elements by the values in the corresponding property instance, then we add it to the list of found predicates. After all dynamic predicates are checked, if no predicate is missing for some types of requirement, property instances are created in the ontology. Finally, if no inconsistency occurs when reasoning on them, the user requirement is created. A user requirement is represented by an instance which has the same description as the Requirement-pattern where dynamic elements are replaced by arguments of a corresponding property instance. After property instances are identified, concept instances have to be classified in the ontology. OWL formal semantics allows us to do inferences on individuals according to properties in which they are involved. The reasoning process is done on the whole set of individuals of the ontology in order to infer implicit knowledge and also to detect errors. Hence, ambiguous terms are solved according to their semantic context. Classifying instances in the ontology is not enough to represent the knowledge derived from texts in a consistent way. It is also necessary to determine which instances refer to the same individuals.

Input
A. Instance classification 1) Domain and range of a property: Each instance participating to a property is associated to the semantic class denoted by the domain or the range of the property.

2) Necessary and sufficient conditions (NSC): Equivalences between a concept and some of its properties can be defined, forming NSC that make possible to infer the concept to which an instance belongs from its properties.

B. Instance identification

In OWL, identical instances are identified using the property SameAs. Inference of SameAs exploits the property which, like the primary key defined in databases, enables us to identify individuals in a unique way. Properties representing a unique constraint can be defined using two ways.

1) Functional properties: associate to each individual of the domain, a unique individual as a range. Let P n a functional property, i i , i j and i k three individuals.

P n (i i , i j ) ∧ P n (i i , i k ) → SameAs(i j , i k ) An inverse functional property associates to each individual of the range, a unique individual as a domain. Let P n an inverse functional property, i i , i j and i k three individuals.

P n (i j , i i ) ∧ P n (i k , i i ) → SameAs(i j , i k )
2) SWRL constraints: More than one property may be needed to represent a unique constraint, in which case the constraint has to define properties that two individuals must share to be inferred as one. These constraints are defined using SWRL rules. For example, the rule below states that two individuals i x and i y are a same individual if they share the same values through properties P 1 and P 2 , P 1

(i x , i C1 ) ∧ P 1 (i y , i C1 ) ∧ P 2 (i x , i C2 ) ∧ P 2 (i y , i C2 ) → SameAs(i x , i y )

VII. EXPERIMENTATION

In this section, we present the application domain, the used resources, and the evaluations of term acquisition and property instance extraction.

A smart space is composed of a set of communicating objects (sensors, actuators and control processes), with a general behaviour. A sensor detects the occurrence of a phenomenon or measures a quantifiable phenomenon in a confined zone. A phenomenon to be detected or measured by a sensor must be located in the zone of sensing of this sensor and shares the same type (temperature, movement, ...) with this sensor. An actuator is connected to a physical process within the environment and can actuate it. When a phenomenon (or a set of phenomena) is measured or detected, the collected information is controlled. This control can lead to the activation of one or more actuators that will trigger one or more actions on the devices or physical processes it or they control. The possible actions are the following ones: turn on, turn off, decrease or increase. An actuator can be activated by a sensor (or a set of sensors), if it is located in the its control zone. Furthermore the actuator has the same type than this sensor (or set of sensors).

In order to model this domain we defined an ontology containing 12 concepts, 15 properties between concepts and 9 between concepts and data types, where all individuals are identifiable from their properties of location and type.

In the absence of a sufficiently large corpus of specifications of requirements in the field of smart spaces, we have constituted a training corpus with e-books from the Anacleto Digital Library (http://www.gutenberg.us/) covering different domains and literary styles. This diversity permits the acquisition of rules from different writing styles and thus is well-founded for the recognition of extraction rules, properties being transdomains. However its generality limits the extraction of the terminology for the specific concepts of the domain. In order to have an evaluation corpus, we developed a platform for collecting specifications. We collected approximately 80 sentences (1558 words) describing requirement specifications, that was annotated to form a gold standard.

We have acquired 126 extraction rules, including 31 for the identification of complete triples and 95 for the identification of partial triples. Obviously, the application of complete rules has priority over partial rules. Each rule has been generated from the n most frequent syntactic paths, with n fixed experimentally to 4. However, depending on the domain, mentions of certain properties are less frequent in texts. So this number may be too high and thus non pertinent paths may generate rules. In order to avoid this potential noise, we set a second limit corresponding to the number of syntactic dependencies involved in the path. Indeed, the longer a path is and thus terms are distant, the less likely that the path represents a semantic property. In our experiments, we fix the maximal number of dependencies in a path at 4.

The starting terminology contains 109 terms, 18 preferred terms and 91 synonyms. Table I illustrates the acquisition of terms on three semantic categories: phenomena, the physical processes and the possible actions. Extraction rules have been applied on the training corpus as described in Section IV. The first column indicates starting terms of the terminology, the second column, the number of different extracted terms and the third column pertinent terms which were selected by hand by examining the n first terms returned from the formula given in Section IV, with n fixed at 25%. Results of the extraction of triple candidates are described in Table II. The first column indicates the number of instances to recognize. The next column indicates the number of correctly identified triples, next the triples not correctly identified. The last three columns describe precision, recall and F-measure respectively. Extraction is performed considering only pertinent terms from the terminology. The first line represents the results for the three properties Locatedin, Fixed-in and Occurred-in, which associate a location to each of the concepts of Location, Physical-process and Phenomenon respectively. The property Has-type associates a Type to a Phenomenon. The last two lines represent instances of concepts Phenomenon and Actuator which are classified and identified during the reasoning process.

We clearly observe a high accuracy (0.95), which shows the pertinence of the acquired rules. Moreover, the obtained recall (0.63) is relatively high considering that rule and terminology acquisition were done on a non specific corpus. From the instances of property created in the ontology, we correctly classified 22 instances of the concept Phenomenon as belonging to 10 different individuals and 17 instances of the concept Actuator as belonging to 7 different individuals, with no incorrectly classified instances. 15 user requirements out of 42 were created automatically from identified instances. Other requirements came out with insufficient information or as inconsistent, in which case the user is asked to revise the requirements set aside.

The ontology population and the reasoning process are implemented under a Java application using Jena, a Java framework for building Semantic Web applications.

VIII. CONCLUSION

We described an approach for ontology population which aims at representing in a formal manner user requirements specified in texts. Our approach centres on the identification of property instance mentions in texts, using extraction rules, acquired from recurrent syntactic paths linking terms which denote concept and property instances. Rules exploit lexical, syntactic and semantic knowledge. They identify property instances even if their domain or range is implicit. Moreover, these rules permit to avoid any ambiguity of extracted terms by capturing the semantic context in which terms appear. By guiding the identification of concept instances through property instance identification, we can then recognize them in context. Thus, we do not only rely on a lexical recognition but also take into account their semantic roles. Furthermore, we demonstrate how using the inference power of OWL, allows us to classify concept instances and identify them in a unique way. The proposed approach has been designed to be independent of the domain and easily adapted to other languages. From a modelled ontology, it requires only a training corpus and a set of starting terms. In future work, we plan to apply our approach to other domains.

  Figure 1. Syntactic dependency tree

Figure 2 .

 2 Figure 2. An instance of Requirement-pattern

  : corpus, ontology, skos for each sentence S in corpus do P I ← ApplyExtractionRules(S); patterns ← getReqP atterns(ontology); for each pattern in patterns do P F ix ← getF ixP art(pattern); P Dyn ← getDynamicP art(pattern); for each p Dyn in P Dyn do if not P I.contain(p Dyn ) then P

	else print(P I associated + "generate inconsistences." ); else print(P missing +" are missing !"); Algorithm 2: Ontology population
	VI. REASONING PROCESS

missing .add(p Dyn ); else for each pi in P I do if pi.name = p.name then p f ound ← replaceElements(p, pi); P f ound .add(p f ound ); P I associated ← pi; if P missing .isEmpty() then createInstances(P I associated ); if Reasoning(ontology) then createRequirement(P F ix , P f ound );

The domain is a concept or a set of concepts and the range is a concept, a set of concepts or a data type.