domain: info math

text:
A Izagirre
email: ane.izagirre@laas.fr

U Ayesta

I M Verloop
email: maaike.verloop@enseeiht.fr

Sojourn time approximations for a discriminatory-processor-sharing queue *

We study a multi-class time-sharing discipline with relative priorities known as Discriminatory Processor Sharing (DPS), which provides a natural framework to model service differentiation in systems. The analysis of DPS is extremely challenging and analytical results are scarce. We develop closed-form approximations for the mean conditional (on the service requirement) and unconditional sojourn times. The main benefits of the approximations lie in its simplicity, the fact that it applies for general service requirements with finite second moments, and that it provides insights into the dependency of the performance on the system parameters. We show that the approximation for the mean conditional and unconditional sojourn time of a customer is decreasing as its relative priority increases. We also show that the approximation is exact in various scenarios, and that it is uniformly bounded in the second moments of the service requirements. Finally we numerically illustrate that the approximation for exponential, hyperexponential and Pareto service requirements is accurate across a broad range of parameters.

Introduction

The Discriminatory Processor Sharing queue (DPS) is a versatile queueing model providing a natural framework to model service differentiation in systems. It is a multi-class extension of the well-studied egalitarian Processor Sharing (PS) policy, where the various classes are assigned positive weight factors. The service capacity is shared simultaneously among all customers present in proportion to the respective class-dependent weights. More precisely, given there are K classes of customers, if at time t there are n k (t) class-k customers present in the system, k = 1, . . . , K, under DPS each class-k customer is served at rate g k / K j=1 g j n j (t), where g 1 , . . . , g K , are the class-dependent weights. The DPS queue has received lot of attention due to its application to model the impact of service differentiation in systems. When all the weights are equal, the DPS queue is equivalent to the PS queue. The PS queue has gained a prominent role in evaluating the performance of a variety of resource allocation mechanisms (see for example [START_REF] Kleinrock | Queueing Systems[END_REF][START_REF] Kelly | Stochastic Networks and Reversibility[END_REF][START_REF] Yashkov | Processor sharing queues: Some progress in analysis[END_REF]), and in recent years it has received renewed attention as a convenient abstraction for modeling the flow-level performance of bandwidth-sharing protocols in packet-switched networks, in particular TCP, see for example [START_REF] Ben Fredj | Statistical bandwidth sharing: A study of congestion at flow level[END_REF][START_REF] Roberts | A survey on statistical bandwidth sharing[END_REF]. In multiple practical situations, the actual service shares that users obtain may show substantial variation among users with heterogeneous characteristics. For example, TCP flows that share a common bottleneck link but traverse distinct routes, may experience diverse packet loss rates and round-trip delays. Besides TCP-related effects, the heterogeneity in bandwidth shares may also be due to deliberate service differentiation among competing flows (for example different qualityof-service in the Internet). For instance packet scheduling algorithms, such as Weighted Fair Queueing (WFQ) and Weighted Round-Robin (WRR), have been proposed as potential instruments to implement differentiated bandwidth sharing. In this context, the Discriminatory Processor-Sharing (DPS) provides a natural approach for modeling the flow-level performance of TCP. The DPS model was introduced by Kleinrock in [START_REF] Kleinrock | Time-shared systems: A theoretical treatment[END_REF]. Despite the simplicity of the model description and the fact that the properties of the egalitarian PS queue are quite thoroughly understood, the analysis of DPS has proven to be extremely difficult. For example, results on an important basic metric like the mean sojourn time in the system have only been derived in a very implicit manner or under certain limiting regimes (time-scale decomposition, heavy-traffic, overload etc.). In a seminal paper Fayolle, Mitrani & Iasnogorodski [START_REF] Fayolle | Sharing a processor among many job classes[END_REF] studied the mean conditional (on the service requirement) and unconditional sojourn time. For general service time distributions, the authors obtained the mean conditional sojourn time as the solution of a system of integro-differential equations. In addition, the authors provided a thorough analysis for the case of exponentially distributed service requirements. However, except for the case of two classes, no closed-form expression is available and numerical analysis is needed in order to calculate the mean sojourn times. Since we use the results of [START_REF] Fayolle | Sharing a processor among many job classes[END_REF] in order to evaluate the accuracy of our approximation, we will give further details on them in Section 2. Avrachenkov et al. [START_REF] Avrachenkov | Discriminatory processor sharing revisited[END_REF] established that the mean queue lengths of all classes are finite under the usual stability condition, regardless of the higher-order moments of the service requirements. Asymptotics of the sojourn time have also received considerable attention for example in [START_REF] Borst | Tail asymptotics for discriminatory processor sharing queues with heavy-tailed service requirements[END_REF] and [START_REF] Borst | Sojourn time asymptotics in processor sharing queues[END_REF]. An important result in this area establishes the asymptotic equivalence between the sojourn time distribution and the service time distribution. Time-scale separations have been studied in [START_REF] Van Kessel | Differentiated bandwidth sharing with disparate flow sizes[END_REF] and [START_REF] Boxma | Exact and approximate analysis of sojourn times in finite discriminatory processor sharing queues[END_REF]. In particular, the authors of [START_REF] Boxma | Exact and approximate analysis of sojourn times in finite discriminatory processor sharing queues[END_REF] approximate the distribution of the sojourn time for a DPS queue with admission control. However the expressions derived in [START_REF] Boxma | Exact and approximate analysis of sojourn times in finite discriminatory processor sharing queues[END_REF] need to be solved numerically. The performance of DPS in overload and its application to model TCP flows is considered in [START_REF] Altman | DPS queues with stationary ergodic service times and the performance of TCP in overload[END_REF]. The application of DPS to analyse the performance of TCP is also considered in [START_REF] Kherani | TCP as an implementation of age-based scheduling: fairness and performance[END_REF]. For more applications of DPS in communication networks see [START_REF] Bu | Fixed point approximation for TCP behaviour in an AQM network[END_REF][START_REF] Cheung | An analytical packet/flow-level modelling approach for wireless LANs with quality-of-service support[END_REF][START_REF] Hayel | Pricing for heterogeneous services at a discriminatory processor sharing queue[END_REF]. DPS under a heavy-traffic regime (when the traffic load approaches the available capacity) was analysed in Grishechkin [START_REF] Grishechkin | On a relationship between processor sharing queues and Crump-Mode-Jagers branching processes[END_REF] assuming finite second moments of the service requirement distributions. Subsequently, assuming exponential service requirement distributions, a direct approach to establish a heavy-traffic limit for the joint queue length distribution was described by Rege & Sengupta [START_REF] Rege | Queue length distribution for the discriminatory processor sharing queue[END_REF] and extended to phase-type distributions in [START_REF] Verloop | Heavy-traffic analysis of a multiple-phase network with discriminatory processor sharing[END_REF]. We refer to Section 2 for more details on heavy-traffic results. Gametheoretic aspects of DPS have been studied in [START_REF] Wu | Heavy traffic approximation of equilibria in resource sharing games[END_REF] and [START_REF] Hassin | To Queue or not to Queue: Equilibrium Behavior in Queueing Systems[END_REF]. For an extensive overview of the literature on DPS we refer to the survey [START_REF] Altman | A survey on discriminatory processor sharing[END_REF]. Motivated by the difficulty in analyzing the system in exact form, in this paper we derive a closed-form approximation for the mean conditional and unconditional sojourn time in the system. We first obtain a light-traffic approximation using the framework obtained in [START_REF] Reiman | Open queueing systems in light traffic[END_REF]. To the best of our knowledge, we are the first to obtain a light-traffic approximation of a time-sharing system, that is, when all users in the system simultaneously get served. We then use results from the heavy-traffic literature in order to obtain a polynomial approximation for any value of the load of the mean conditional sojourn time for service requirements with finite second moments. Unconditioning on the service time distribution, this allows us to readily obtain an approximation for the mean unconditional sojourn time. We will show that in some cases our approximation becomes exact, for example when there is only one class in the system or when all the weights are the same. The approximation provides insights into the performance of the system. We show that the approximation for the mean conditional sojourn time of a class-k user is decreasing (resp. increasing) as the weight g k (resp. g j , j = k) increases. Another important observation is that the approximation is uniformly bounded in the second moments of the service requirements. This was a major property of PS, which is in sheer contrast with FCFS queues, where the mean waiting time explodes as the second moment grows. In the particular case of exponential service time distributions we see that the expression greatly simplifies and that the approximation for the mean unconditional sojourn time is exact when the mean service times for all classes are the same. Finally, we numerically investigate the accuracy of the approximation by comparing it with the exact results obtained in [START_REF] Fayolle | Sharing a processor among many job classes[END_REF]. We consider exponential, hyper-exponential and Pareto service time distributions, and our results show that our approximation works extremely well across various parameter values. An important benefit of the approximation is that it provides insights into the dependency of the performance on the system parameters (weights, service time distributions, etc), and we thus believe it will provide an interesting tool in order to implement service-differentiation in real systems. The remainder of the paper is organized as follows. In Section 2 we provide a detailed model description and gather results from Fayolle et al. [START_REF] Fayolle | Sharing a processor among many job classes[END_REF] and Grishechkin [START_REF] Grishechkin | On a relationship between processor sharing queues and Crump-Mode-Jagers branching processes[END_REF] that will be used in the paper. In Section 3 we develop a light-traffic analysis. The light and heavy-traffic interpolation approximation for the conditional and unconditional sojourn time is presented in Section 4. Section 5 presents the results for the particular case of exponentially distributed service requirements. In Section 6 we numerically test the accuracy of the obtained approximations.

Model description and preliminaries

We consider a multi-class single-server queue with K classes of customers. Class-k customers, k = 1, . . . , K, arrive according to independent Poisson processes with rate λ k ≥ 0. We denote the overall arrival rate by

ρ := K k=1 ρ k = K k=1 λ k E[B k ] = λ K k=1 α k E[B k ] = λE[B],
where α k = λ k /λ denotes the probability that an arrival is of class k and the random variable B is the service requirement of an arbitrary arriving customer. The K customer classes share a common resource of capacity one. There are strictly positive weights g 1 , . . . , g K associated with each of the classes. Whenever there are n k class-k customers, k = 1, . . . , K, in the system, each class-k customer is served at rate The analysis of DPS is extremely difficult compared to that of egalitarian PS, which arises as a special case when all g k are equal. Fayolle et al. [START_REF] Fayolle | Sharing a processor among many job classes[END_REF] obtained that the derivatives of the mean conditional sojourn times of the various classes satisfy the following system of integro-differential equations:

∂S k (λ, b) ∂b = 1 + λ K j=1 ∞ 0 α j g j g k ∂S j (λ, y) ∂y [1 -F j (y + g j g k b)]dy + λ b 0 ∂S k (λ, y) ∂y K j=1 α j g j g k [1 -F j ( g j g k (b -y))]dy, (1)
for k = 1, . . . , K. The natural boundary conditions are S k (λ, 0) = 0, k = 1, . . . , K.

The only known analytical solution for this system of equations has been obtained under the assumption of exponentially distributed service requirements. In this case we denote by µ j := 1/E[B j ], ∀j. In [START_REF] Fayolle | Sharing a processor among many job classes[END_REF] it is proved that

S k (λ, b) = b 1 -ρ + m j=1 g k c j β j + d j β 2 j 1 -e -βj b/g k , (2)
where -β j , j = 1, 2, . . . , m, are the m distinct negative roots of

K j=1 λ j g j µ j g j + s = 1, (3)
and where c j and d j , j = 1, . . . , m, are a function of the input parameters and β j , j = 1, . . . , m. Furthermore, for the mean unconditional sojourn time with exponentially distributed service requirements, it is shown in [START_REF] Fayolle | Sharing a processor among many job classes[END_REF] that S k (λ), k = 1, . . . , K, is the unique solution of the following system of equations:

S k (λ)   1 - K j=1 λ j g j µ j g j + µ k g k   - K j=1 λ j g j S j (λ) µ j g j + µ k g k = 1 µ k . (4)
A closed-form solution for this system of equations ( 4) is available only for the case of K = 2, and is given by

S 1 (λ) = 1 µ 1 (1 -ρ) 1 + µ 1 ρ 2 (g 2 -g 1 ) D (5)
and

S 2 (λ) = 1 µ 2 (1 -ρ) 1 + µ 2 ρ 1 (g 1 -g 2 ) D , (6)
where

D = µ 1 g 1 (1 -ρ 1 ) + µ 2 g 2 (1 -ρ 2 ).
The above shows how hard and challenging it is to study analytically the DPS model. For this reason, as mentioned in the introduction, research has focused on analysing the DPS queue in limiting regimes, like tail asymptotics, heavy-traffic limits, fluid limits etc. In this paper, we take a different approach, and we develop a light and heavy-traffic interpolation based approximations for S k (λ, b) and S k (λ). In the numerical section we will use Equations ( 2), ( 4)-( 6) in order to numerically verify the accuracy of our interpolation approximations. The approximation is obtained by interpolating the mean sojourn times obtained under the light-traffic regime and the heavy-traffic regime. The light-traffic regime consists in letting ρ ↓ 0, or equivalently λ ↓ 0. Hence, it concerns the performance when the system is almost empty. Therefore, in Section 3 we analyze the mean conditional sojourn time in the light-traffic regime.

The heavy-traffic regime consists in letting ρ ↑ 1, or equivalently λ ↑ 1/E[B]. Hence, it concerns the performance when the system is close to congestion. Heavy-traffic results have been obtained in [START_REF] Grishechkin | On a relationship between processor sharing queues and Crump-Mode-Jagers branching processes[END_REF][START_REF] Rege | Queue length distribution for the discriminatory processor sharing queue[END_REF][START_REF] Verloop | Heavy-traffic analysis of a multiple-phase network with discriminatory processor sharing[END_REF]. For our analysis, we use the results by Grishechkin [START_REF] Grishechkin | On a relationship between processor sharing queues and Crump-Mode-Jagers branching processes[END_REF]Theorem 4.1] who studied a general M/G/1/GPS system of which our model is a particular case. In particular, for the DPS queue as studied in this paper Grishechkin derives the distribution of the conditional sojourn times, scaled by

1 -λE[B] = 1 -ρ, as λ ↑ 1/E[B].
In particular, the mean of this distribution is given by

E[ lim λ↑1/E[B] (1 -λE[B])S k (λ, b)] = b g k E[B 2 ] K j=1 α j E[B 2 j ]/g j . (7)
For our interpolation result, we are interested in lim

λ↑1/E[B] (1 -λE[B])S k (λ, b) = lim λ↑1/E[B] (1 - λE[B])E[S k (λ, b)].
Although we cannot verify that the limit and expectation can be interchanged, we use the expression in [START_REF] Bu | Fixed point approximation for TCP behaviour in an AQM network[END_REF] as an approximation for lim

λ↑1/E[B] (1 -λE[B])S k (λ, b).
Numerical experiments as performed in [START_REF] Verloop | Heavy-traffic analysis of a multiple-phase network with discriminatory processor sharing[END_REF] indicate that indeed the limits can be interchanged.

Light-traffic analysis

In this section we analyse the mean conditional sojourn time of the tagged class-k customer under the light-traffic regime. The light-traffic regime concerns the performance of the system for small values of the arrival rate λ, i.e., when the system is almost empty. We will approximate S k (λ, b) by a Taylor series expansion of S k (λ, b) at λ = 0. Assuming that the first n derivatives of S k (λ, b) with respect to λ at λ = 0 exist we have the following approximation for the mean conditional sojourn time of a class-k customer when λ is close to zero:

S LT k (λ, b) := S (0) k (0, b) + λS (1) k (0, b) + • • • + λ n n! S (n) k (0, b). (8)
We will refer to this as the light-traffic approximation of order n. Here S . We have based our analysis on Reiman and Simon [START_REF] Reiman | Open queueing systems in light traffic[END_REF] where it is shown how to obtain the derivatives of arbitrary order m ≥ 0 at λ = 0 under a general admissibility condition. Following the discussion in [23, Appendix A] we make an assumption on the service requirements B k , that is,

E[e ηB k ] < ∞ (9)
for some η > 0, ∀k. This finite exponential moment condition entails admissibility; it is likely stronger than needed but its purpose here is to provide a convenient framework where calculations can be justified. In this paper we set n = 1 in (8) as this will already provide us with an accurate approximation of the performance. Let A(s, t) denote the number of arrivals in the interval [s, t) in addition to the tagged customer who is assumed to arrive at time 0. Then, the zeroth and first light-traffic derivatives satisfy

S k (0, b) := E S k (0, b) A(-∞, ∞) = 0 (10)
and

S (1) k (0, b) := ∞ -∞ E S k (0, b) A(-∞, ∞) = 1, τ = t -E S k (0, b) A(-∞, ∞) = 0 dt, ( 11
)
where τ is the arrival time of the first customer, see [START_REF] Reiman | Open queueing systems in light traffic[END_REF]. In Section 3.1 we provide a brief intuitive approach of how to obtain the light-traffic derivatives [START_REF] Ben Fredj | Statistical bandwidth sharing: A study of congestion at flow level[END_REF] and [START_REF] Grishechkin | On a relationship between processor sharing queues and Crump-Mode-Jagers branching processes[END_REF] and we refer to Reiman and Simon [START_REF] Reiman | Open queueing systems in light traffic[END_REF] for more details. In Section 3.2 we then calculate the first order light-traffic approximation for the DPS queue.

Light-traffic approach

In this section we provide an intuitive approach of how to obtain the zeroth and first light-traffic derivatives. This approach is based on the analysis of J. Walrand in [START_REF] Walrand | An introduction to queueing networks[END_REF]Chapter 6.3.]. Higher order light-traffic derivatives can be obtained in a similar way. Consider a system that starts at time -Z and that keeps going until time T, being Z, T > 0 given. Let S k (λ, b, -Z) denote in this case the sojourn time of the tagged class-k customer who arrives in the system at time t = 0 and note that lim Z→∞ S k (λ, b, -Z) = S k (λ, b). Let A(s, t) denote the number of arrivals in the interval [s, t) in addition to the tagged customer who is assumed to arrive at time 0. Throughout this section we assume that the limits (with respect to Z and T ) and expectations can be interchanged.

We then have

E [min{S k (λ, b, -Z), T }] = ∞ a=0 E min{S k (λ, b, -Z), T } A(-Z, T ) = a • (λ(T + Z)) a a! e -λ(T +Z) , (12)
where E min{S k (λ, b, -Z), T } A(-Z, T ) = a is the expected minimum between the sojourn time and T , conditioned that there are exactly a arrivals. Evaluating it at λ = 0 gives

E [min{S k (λ, b, -Z), T }] λ=0 = E min{S k (0, b, -Z}, T } A(-Z, T ) = 0 , (13)
and now taking the limit Z, T → ∞ we obtain the zeroth light-traffic derivative

S k (0, b) := lim Z,T →∞ E [min{S k (λ, b, -Z), T }] λ=0 = E S k (0, b) A(-∞, ∞) = 0 ,
where the second equality follows from [START_REF] Hayel | Pricing for heterogeneous services at a discriminatory processor sharing queue[END_REF].

Next, consider the derivative with respect to λ in Equation [START_REF] Hassin | To Queue or not to Queue: Equilibrium Behavior in Queueing Systems[END_REF] and evaluate it at λ = 0. This gives

∂ ∂λ E [min{S k (λ, b, -Z), T }] λ=0 = -E min{S k (0, b, -Z), T } A(-Z, T ) = 0 • (T + Z) + E min{S k (0, b, -Z), T } A(-Z, T ) = 1 • (T + Z) = T -Z E min{S k (0, b, -Z), T } A(-Z, T ) = 1, τ = t -E min{S k (0, b, -Z), T } A(-Z, T ) = 0 dt, ( 14
)
where τ is the arrival time of the first customer. The second equality holds because the arrivals follow a Poisson process. Hence given that the number of arrivals in [-Z, T ) is one (A(-Z, T ) = 1), we have that τ is uniformly distributed on [-Z, T ). Now taking Z, T → ∞ we obtain the first light-traffic derivative

S (1) k (0, b) := lim Z,T →∞ ∂ ∂λ E [min{S k (λ, b, -Z), T }] λ=0 = ∞ -∞ E S k (0, b) A(-∞, ∞) = 1, τ = t -E S k (0, b) A(-∞, ∞) = 0 dt,
where the second equality follows from ( 14).

As stated above, higher order light-traffic derivatives can be obtained in a similar way.

In the next section we use the expressions [START_REF] Ben Fredj | Statistical bandwidth sharing: A study of congestion at flow level[END_REF] and [START_REF] Grishechkin | On a relationship between processor sharing queues and Crump-Mode-Jagers branching processes[END_REF] to calculate the zeroth and first light-traffic derivatives of the DPS model.

Light-traffic approximation

In this section we derive the first-order light-traffic approximation. As we will see in Sections 4, 5 and 6, the first order light-traffic approximation provides us with an insightful and accurate approximation of the performance.

Equation [START_REF] Ben Fredj | Statistical bandwidth sharing: A study of congestion at flow level[END_REF] represents the situation where nobody enters the system except the tagged customer. Therefore, S k (0, b) is equal to the service requirement of the tagged customer, which we denote by b. Hence,

S k (0, b) = b. (15)
Let us denote by S k,t,ut,bu t the sojourn time of the tagged class-k customer when there is exactly one arrival at time t on R, u t describing the class of the customer arriving at time t and b ut denoting the service requirement of the customer arriving at time t. Hence,

E S k (0, b) A(-∞, ∞) = 1, τ = t and E[S k,t,Ut,B U t ]
are equivalent, where U t and B Ut are dependent random variables and are distributed as follows: with probability α i we have U t = i and B Ut is distributed as B i , i = 1, . . . , K. We can write S k,t,ut,bu t as follows:

S k,t,ut,bu t =                    t + b ut + b if t ≤ 0 ≤ t + b ut and b g k > t+bu t gu t g k +gu t g k b if t ≤ 0 ≤ t + b ut and b g k ≤ t+bu t gu t b if t + b ut < 0 b + b ut if 0 < t < b and b-t g k > bu t gu t t + (b -t) g k +gu t g k if 0 < t < b and b-t g k ≤ bu t gu t b if 0 < b < t. (16)
The first expression describes the case where the customer arrives before the tagged customer and leaves after the tagged customer arrives, but before the tagged customer leaves. Hence, by the work conserving property, the tagged customer stays in the system until all the work present at time 0 is done, that is, b ut -(-t)+b. We recall that the work-conserving property states that as long as the system is non-empty, the server does not idle. The second term describes the case where the other customer is in the system at time 0 and is still present as the tagged customer departs. Hence, the tagged class-k customer is served

at rate g k g k +gu t
, so that its sojourn time is b

g k g k +gu t -1
. The fourth expression describes the case where the customer arrives after the tagged customer and leaves before the tagged customer. Hence, by the work-conserving property of the system, the sojourn time of the tagged class-k customer is given by the total amount of work that needs to be done, that is, b + b ut . The fifth term describes the case where the customer arrives after the tagged customer, and departs after the tagged customer departs. Then, the sojourn time of the tagged customer is composed of t, the time it was in the system until the customer arrived, plus (b -t)

g k g k +gu t -1
, the remaining service requirement multiplied by the inverse of the rate at which the the tagged class-k customer is served. The third and sixth case is when the tagged customer does not coincide with the other customer. Hence, the sojourn time is given by its service requirement, b. From Equations ( 11), ( 15) and ( 16) we then obtain the following expression for the first derivative. Lemma 3.1. We have

S (1) k (0, b) = R E S k (0, b) A(-∞, ∞) = 1, τ = t -b dt = R (E[S k,t,Ut,B U t ] -b)dt = E 1 2 1 + g k g Ut min{B Ut , b g Ut g k } 2 -b g Ut g k + g k g Ut B Ut min{B Ut , b g Ut g k } + g k + g Ut g k bB Ut . ( 17
)
See Appendix A for the proof.

From ( 8), ( 15) and ( 17) we now derive the following approximation for the mean conditional sojourn time when λ is small.

Corollary 3.2. The light-traffic approximation (of order 1) of the mean conditional sojourn time for a tagged class-k customer with service requirement b is given by

S LT k (λ, b) = S k (0, b) + λS (1) k (0, b) = b(1 + ρ) + λE 1 2 1 + g k g Ut min{B Ut , b g Ut g k } 2 -b g Ut g k + g k g Ut B Ut min{B Ut , b g Ut g k } + g Ut g k bB Ut . ( 18
)
Remark 1. We consider in the paper the light-traffic approximation of order 1. Calculating the second light-traffic derivative would imply having to consider events that either 0, 1, or 2 customers arrive in the system (besides the tagged customer). The latter would result in going through 22 different cases, while for the first derivate we only needed to go through 6 cases, see Equation ( 16). We will see in Sections 4, 5 and 6 that already the first order light-traffic approximation provides an insightful and accurate approximation of the performance

We can infer several nice properties from [START_REF] Kleinrock | Time-shared systems: A theoretical treatment[END_REF]. For instance, we will show in Section 4 that ( 18) is decreasing in g k and increasing in g j , j = k. In other words, the approximation for the mean sojourn time reduces as its own weight increases, and it increases as the weight of any other class increases.

Another interesting observation is that the light-traffic approximation of the mean conditional sojourn time can be uniformly bounded in the second moment. This important feature helps obtaining a good performance in the presence of highly variable service distributions (like the ones observed in nowadays communication systems). See Section 4.4 for details.

Light and heavy-traffic interpolation

In this section we present the light and heavy-traffic interpolation result. This technique was popularized by Reiman and Simon [START_REF] Reiman | An interpolation approximation for queueing systems with Poisson input[END_REF][START_REF] Reiman | Light traffic limits of sojourn time distributions in Markovian queueing networks[END_REF][START_REF] Reiman | Open queueing systems in light traffic[END_REF] and consists in interpolating

t k (λ) := (1 -ρ)S k (λ, b) = (1 -λE[B])S k (λ, b),
by a polynomial tk (λ) of order n + 1:

tk (λ) = h 0 + h 1 λ + . . . + h n+1 λ n+1 . ( 19
)
To determine the coefficients h 0 , . . . , h n we use the so-called light-traffic conditions

tk (0) = t k (0) and t(m) k (0) = t (m) k (0), for m = 1, . . . , n, (20)
and the heavy-

traffic condition tk (1/E[B]) -= t k (1/E[B]) -, (21)
where

t k (1/E[B]) -is given by b g k E[B 2 ] K j=1 α j E[B 2 j ]/g j , see (7).
Once we have obtained the coefficients we undo the normalisation so that

S IN T k (λ, b) := tk (λ) 1 -λE[B] , 0 ≤ λ < 1/E[B], (22)
provides an approximation for the mean conditional sojourn time S k (λ, b). We refer to this approximation as the light and heavy-traffic interpolation of order n + 1.

In the following proposition we characterise [START_REF] Reiman | Light traffic limits of sojourn time distributions in Markovian queueing networks[END_REF] in terms of the light-traffic derivatives and the heavytraffic equation. To the best of our knowledge, this is a new result and it applies to any model, i.e., it is not restricted to the DPS model.

Proposition 4.1. The light and heavy-traffic interpolation of order n + 1 can be written as

S IN T k (λ, b) = n i=0 λ i i! S (i) k (0, b) + t k (1/E[B]) -(λE[B]) n+1 1 -λE[B] . ( 23
)
Proof. From the light-traffic condition (20) we obtain

h 0 = S (0) k (0, b) and h i = S (i) k (0, b) i! -E[B] S (i-1) k (0, b) (i -1)! , i = 1, 2, ..., n,
and from the heavy-traffic condition [START_REF] Reiman | An interpolation approximation for queueing systems with Poisson input[END_REF] we obtain

h n+1 = E[B] n+1 t k (1/E[B]) -- n i=0 h i E[B] i = E[B] n+1 t k (1/E[B]) --S (0) k (0, b) - n i=1 1 E[B] i S (i) k (0, b) i! -E[B] S (i-1) k (0, b) (i -1)! = E[B] n+1 t k (1/E[B]) -- 1 E[B] n S (n) k (0, b) n! .
Equation ( 23) follows after substituting these expressions in [START_REF] Reiman | Light traffic limits of sojourn time distributions in Markovian queueing networks[END_REF].

Notice that in the previous section we derived the light-traffic derivatives up to order 1. Hence, this allows us to obtain the light and heavy-traffic interpolation of order 2 as stated in the following proposition.

Proposition 4.2. The light and heavy-traffic interpolation (of order 2) of the mean conditional sojourn time for a tagged class-k customer with service requirement b is given by

S IN T k (λ, b) = b + λbE[B] + λE 1 2 1 + g k g Ut min{B Ut , b g Ut g k } 2 -b g Ut g k + g k g Ut B Ut min{B Ut , b g Ut g k } + b g Ut g k B Ut + (λE[B]) 2 (1 -λE[B]) b g k E[B 2 ] K j=1 α j E[B 2 j ]/g j . ( 24
)
Proof. This follows from Equation ( 23) together with ( 15), ( 17) and [START_REF] Bu | Fixed point approximation for TCP behaviour in an AQM network[END_REF].

In [START_REF] Izagirre | Sojourn time approximations in a multi-class time-sharing system[END_REF] Proposition 4.2 was proved by calculating the coefficients h 0 , h 1 , h 2 using Equations ( 20) and [START_REF] Reiman | An interpolation approximation for queueing systems with Poisson input[END_REF]. Thanks to Proposition 4.1, the proof of Proposition 4.2 is now immediate.

In Section 6 we will numerically evaluate the accuracy of the approximation formulas derived in Proposition 4.2. In the subsections below, we first make several interesting observations. Remark 2. In Appendix B we describe an alternative way to obtain the light-traffic derivatives. This method makes use of Equation ( 1), and hence it applies only to the DPS model. It allows us to derive higher order light-traffic approximations. We observe numerically, see Figures 14151617, that the light-traffic approximation (of order 2) gets more accurate, whereas the accuracy of the interpolation (of order 3) for intermediate loads does not necessarily get better.

Processor Sharing

For the standard Processor Sharing queue the mean conditional sojourn time is known and is given by b/(1-ρ), [START_REF] Kelly | Charging and rate control for elastic traffic[END_REF]. If either (i) there is only one class or (ii) all weights are the same, our model is equivalent to a processor-sharing queue. Below we will verify that our approximation as stated in ( 24) indeed coincides with b/(1 -ρ).

We first consider the case of one class, that is, α i = 0, ∀i = k and α k = 1. Then Equation ( 24) is equal to

b(1 + ρ) + λ k E min{B Ut , b} 2 -b + B Ut min{B Ut , b} + bB Ut + b ρ 2 (1 -ρ) = b(1 + ρ + ρ 2 (1 -ρ) ) = b 1 -ρ ,
where we used that min{B Ut , b} 2 -b + B Ut min{B Ut , b} + bB Ut = 0. We now assume all weights are the same, i.e., g i = g k , ∀i, k = 1, . . . , K. Equation ( 24) is then equal to

b(1 + ρ) + λE min{B Ut , b} 2 -b + B Ut min{B Ut , b} + bB Ut + bρ 2 (1 -ρ) E[B 2 ] K j=1 α j E[B 2 j ] = b(1 + ρ + ρ 2 (1 -ρ) ) = b 1 -ρ .
Hence, both cases coincide with the PS queue.

Priority queue

We now consider the case when the weight of the tagged customer grows large, i.e., g k → ∞. Hence, class k is prioritized in the limit. Then, the approximation simplifies to lim

g k →∞ b(1 + ρ) + K ut=1 λ ut E 1 2 min{B ut , b g ut g k } 2 + g k g ut min{B ut , b g ut g k } 2 -b g ut g k min{B ut , b g ut g k } + B ut min{B ut g k g ut , b} + g ut g k bB ut + b(λE[B]) 2 (1 -λE[B]) E[B 2 ] g k K j=1 j =k α j E[B 2 j ]/g j + α k E[B 2 k ] = b(1 + ρ) + E K ut=1 ut =k λ ut 1 2 0 + 0 -0 + bB ut + 0 = b(1 + ρ k ).
Note that the conditional sojourn time as g k → ∞ is known and its given by b/(1-ρ k ). Since 1/(1-ρ k ) = ∞ i=0 ρ i k , we directly see that the approximation is the first order approximation of the exact expression. The relative error is equal to 100%

(b/(1 -ρ k ) -b(1 + ρ k )) /b/(1 -ρ k ) = ρ 2
k 100%, and we thus see that the relative error increases as the load of class k increases.

Monotonicity in the weights

It can be checked that the approximation for the mean conditional sojourn time of a tagged class-k customer, S

IN T k

(λ, b), is decreasing in g k and increasing in g i , i = k. This can be seen as follows. Conditioning on U t we can write

S IN T k (λ, b) = b(1 + ρ) + K i=1,i =k λ i E 1 2 1 + g k g i min{B i , b g i g k } 2 -b g i g k + g k g i B i min{B i , b g i g k } + b g i g k B i + (λE[B]) 2 (1 -λE[B]) b g k E[B 2 ] K j=1 α j E[B 2 j ]/g j ,
where for

U t = k we used that min{B k , b} 2 -b + B k min{B k , b} + bB k = 0. Now, if B i ≤ gi g k b, then 1 2 1 + g k g i min{B i , b g i g k } 2 -b g i g k + g k g i B i min{B i , b g i g k } + b g i g k B i = 1 2 B 2 i (1 - g k g i ),
which is decreasing in g k and increasing in

g i . If B i > gi g k b, then 1 2 1 + g k g i min{B i , b g i g k } 2 -b g i g k + g k g i B i min{B i , b g i g k } + b g i g k B i = 1 2 b 2 g i g k (1 - g i g k ) + bB i ( g i g k -1),
which is decreasing in g k and increasing in g i (can be derived by taking the derivative and the fact that

B i > gi g k b)
. The monotonicity of S

IN T k

(λ, b) in g k and g i now follows immediately.

Uniformly bounded in the second moment

A very relevant property of processor sharing is that the mean sojourn time depends on the service time distribution only through its mean [START_REF] Kelly | Stochastic Networks and Reversibility[END_REF]. This has been an important argument to claim the interest of time-sharing disciplines with respect to more classical scheduling policies like FCFS. Indeed, the classical Pollaczek-Khinchine formula for the mean waiting time in a FCFS queue shows that it explodes as the second moment of the service time distribution grows large. For a DPS queue, Equation (1) does not allow to reach any conclusion regarding the dependence of the mean conditional sojourn time on the moments of the service time distribution. It then becomes interesting to observe that the approximation ( 24) is uniformly bounded in the second moments of the service time distribution. To see this, we first note that min{B Ut , b

g U t g k } 2 ≤ B Ut b g U t g k ,
which directly implies that the first three terms in [START_REF] Roberts | A survey on statistical bandwidth sharing[END_REF] are uniformly bounded by a function that depends on the service requirements only through its first moment. We are now left with the heavy-traffic

term E[B 2 ] K j=1 α j E[B 2 j ]/g j . Let j * be such that E[B 2 j * ] ≥ E[B 2 j ], ∀j. We then have E[B 2 ] K j=1 α j E[B 2 j ]/g j = j α j E[B 2 j ] K j=1 α j E[B 2 j ]/g j ≤ E[B 2 j * ] α j * E[B 2 j * ]/g j * = g j * α j *
. We thus finally conclude that (24) can be upper bounded by an expression that depends only on the first moment of the service time distributions. This indicates that the DPS queue provides a satisfactory performance even in the presence of service time distributions with a high variability.

Mean unconditional sojourn time

As a corollary of Proposition 4.2, we obtain the mean unconditional sojourn time of the tagged class-k customer.

Corollary 4.3. The light and heavy-traffic interpolation (of order 2) of the mean unconditional sojourn time for a tagged class-k customer is given by

S IN T k (λ) := ∞ 0 S IN T k (λ, b)dF k (b) = E[B k ](1 + ρ) +λE 1 2 1 + g k g Ut min{B Ut , B k g Ut g k } 2 -B k g Ut g k + g k g Ut B Ut min{B Ut , B k g Ut g k } + B k g Ut g k B Ut + (λE[B]) 2 (1 -λE[B]) E[B k ] g k E[B 2 ] K j=1 α j E[B 2 j ]/g j . ( 25
)

Exponential service requirements

In this section we focus on the case in which the service requirements of the customers are exponentially distributed. We recall that a random variable

B i is exponentially distributed if P(B i ≤ b i ) = 1-e -bi/E[Bi] .
In Section 5.1, we further simplify the expression for the light and heavy-traffic interpolation of the mean conditional and unconditional sojourn time and compare the latter for two classes of customers with the exact formulas as stated in Equations ( 5) and [START_REF] Boxma | Exact and approximate analysis of sojourn times in finite discriminatory processor sharing queues[END_REF]. In Section 5.2, we calculate the relative error (for different service requirements) and we verify that our approximation for the mean unconditional sojourn time for an arbitrary customer is exact when the service requirements of all customers are the same.

Mean conditional and unconditional sojourn time

In the case of exponentially distributed service requirements, our approximations for the mean conditional and unconditional sojourn time can be significantly simplified. This is a direct consequence of Proposition 4.2 and Corollary 4.3, respectively.

Corollary 5.1. Assume class-k customers have an exponentially distributed service requirement with mean 1/µ k , k = 1, . . . , K. The light and heavy-traffic interpolation (of order 2) of the mean conditional sojourn time for a tagged class-k customer with service requirement b is given by

S IN T k (λ, b) = b + λE[B]b + λ K j=1 α j µ 2 j 1 - g k g j 1 -e -b g j g k µj + (λE[B]) 2 (1 -λE[B]) b g k K j=1 α j /µ 2 j K j=1 α j /(µ 2 j g j )
, and the mean unconditional sojourn time is given by

S IN T k (λ) := ∞ 0 S IN T k (λ, b)dF k (b) = 1 µ k + 1 µ k λE[B] + λ K j=1 α j 1 µ j (g j -g k ) g j µ j + g k µ k + (λE[B]) 2 (1 -λE[B]) 1 g k µ k K j=1 α j /µ 2 j K j=1 α j /(µ 2 j g j ) , (26)
where E[B] = K j=1 α j /µ j . Proof. These results can be derived from Proposition 4.2 and Corollary 4.3 after doing some manipulations.

In the case of two classes of customers, Fayolle et al [START_REF] Fayolle | Sharing a processor among many job classes[END_REF] have closed-form expressions for the mean unconditional sojourn time, see Equation ( 5) and [START_REF] Boxma | Exact and approximate analysis of sojourn times in finite discriminatory processor sharing queues[END_REF]. Rewriting [START_REF] Verloop | Heavy-traffic analysis of a multiple-phase network with discriminatory processor sharing[END_REF] for K = 2 in such a way so that the similarity with Equations ( 5) and ( 6) is clear, we obtain

S IN T k (λ) = 1 µ k (1 -ρ) 1 + ρ 2 -1 + K j=1 α j /µ 2 j g k K j=1 α j /(µ 2 j g j ) + µ k ρ -k (g -k -g k ) D (1 -ρ)D µ 1 g 1 + µ 2 g 2 , (27)
with k = 1, 2, -k = mod(k, 2) + 1 and where

D = µ 1 g 1 (1 -ρ 1 ) + µ 2 g 2 (1 -ρ 2 ).
We directly observe that the difference with respect to the exact expression for the mean unconditional sojourn time (( 5) and ( 6)) is in the terms ρ 2 -1

+ K j=1 α j /µ 2 j g k K j=1 α j /(µ 2 j g j ) and (1 -ρ)D µ 1 g 1 + µ 2 g 2 .
It can easily be seen that our approximation is exact for the two extreme values of the traffic intensity, ρ = 0 and ρ = 1. That is, the expressions

S IN T k (0) = 1/µ k and lim λ→1/E[B] (1 -ρ)S IN T k (λ) = 1 µ k 1 + µ k ρ -k (g -k -g k ) D are satisfied.
Let us denote by Rel.Error k the relative error of a class-k customer, that is, Rel.

Error k = S k (λ) -S IN T k (λ) S k (λ) , k = 1, 2. Now, let us consider g 1 + g 2 = 1.
We then obtain lim g1↑1 Rel.Error

1 = ρ 2 1 • 100% and lim g1↑1 Rel.Error 2 = µ 2 ρ 1 -(1 -ρ 1 ) ρ 2 ρ 1 µ 2 ρ 2 + µ 2 ρ 1 (1 -ρ) µ 1 (1 -ρ 1 ) + µ 2 ρ 1 • 100%.
Hence, the relative error of class-1 customers (when g 1 ↑ 1) increases as the load of class 1 increases but does not depend on the parameter of class 2. The same result was obtained in Section 4.2 for the mean conditional sojourn time for an arbitrary number of classes and general service requirements. Moreover, the absolute relative error of class-2 customers (when g 1 ↑ 1) increases as the load of class 2 decreases.

In Figure 1 we plot the relative error of the mean unconditional sojourn time for K = 2 with respect to g 1 . The parameters considered are ρ 1 = 0.2, ρ 2 = 0.4, µ 1 = 1, µ 2 = 1, g 2 = 1 -g 1 and from the formulas presented above we obtain lim g1↑1 Rel. Error 1 = 4%, lim g1↑1 Rel. Error 2 = -0.8%, lim g1↓0 Rel. Error 1 = -12.8%, lim g1↓0 Rel. Error 2 = 16%, which coincide with the extreme points in the figure.

Mean unconditional sojourn time for an arbitrary customer

In this section we calculate the relative error of the mean unconditional sojourn time for an arbitrary customer when K = 2 and µ 1 or µ 2 takes extreme values, and we verify that our approximation for the mean unconditional sojourn time of an arbitrary customer is exact when the service requirements of all customers are the same.

We denote by Rel.Error the relative error of an arbitrary customer, that is, Rel.Error = 1 -

2 k=1 α k S IN T k (λ) 2 k=1 α k S k (λ)
• 100%, where S 1 (λ) and S 2 (λ) are given in Equations ( 5) and ( 6), respectively. Then, if we keep constant ρ 1 and ρ 2 , such that λ 1 = ρ 1 µ 1 and λ 2 = ρ 2 µ 2 change, we obtain lim µ2↓0

Rel.Error =

ρ 1 ρ 2 (g 2 -g 1 ) g 1 1 1 -ρ 1 -1 + ρ -ρ 2 -1 + g 2 g 1 ρ 1 1 + ρ2(g2-g1) g1(1-ρ1) + ρ 2 • 100% (28)
and lim µ1↑∞ Rel.Error = lim µ2↓0 Rel.Error. The intuition behind the latter equation can be seen as follows: having µ 1 → ∞ and λ 1 → ∞, i.e., having many class-1 arrivals of small size, is equivalent to having µ 2 → 0 and λ 2 → 0, i.e., having very few class-2 arrivals of large size.

In Figure 2 we plot the relative error of the mean unconditional sojourn time for an arbitrary customer.

We fix ρ 1 , ρ 2 and µ 1 and we let µ 2 and λ 2 = ρ 2 µ 2 change. The chosen parameters are ρ 1 = 0.2, ρ 2 = 0.6, µ 1 = 1, g 1 = 1, g 2 = 2. We observe that the results obtained from Equation ( 28), lim µ2↓0 Rel.Error = -0.2105% and lim µ2↑∞ Rel.Error = 8.307%, coincide with the extreme points in the figures. We know the expression of the latter equality because lim µ2↑∞ = lim µ1↑0 and the symmetry of the latter with Equation ( 28). We now show that our light-traffic approximation for the mean unconditional sojourn time of an arbitrary customer is exact under the assumption that the mean service requirements of all customers are the same, i.e., E[B j ] = 1/µ, ∀j = 1, . . . , K. This result holds for an arbitrary number of classes. As stated earlier, the mean unconditional sojourn time of an arbitrary customer is defined as S(λ) := K k=1 α k S k (λ). Since we assume exponentially distributed service requirements and E[B k ] = 1/µ, ∀k = 1, . . . , K, the total number of customers in the system is distributed as that in a processor sharing queue with arrival rate λ = K k=1 λ k and service rate µ. By Little's law, we therefore have that the total mean unconditional sojourn time is given by that of an M/M/1 queue, i.e, 1/µ 1 -ρ .

For our light and heavy-traffic interpolation we have

S IN T (λ) = K k=1 α k S IN T k (λ) = 1 + ρ µ + λ K k=1 α k K j=1 α j µ (g j -g k ) g j µ + g k µ + (λ/µ) 2 (1 -λ/µ) K k=1 α k 1 µg k K j=1 α j /µ 2 K j=1 α j /(µ 2 g j ) = 1 + ρ µ + 1 µ ρ 2 1 -ρ K k=1 α k g k 1 K j=1 α j /g j = 1/µ 1 -ρ , ( 29
)
where we used that

K k=1 α k K j=1 α j (g j -g k ) g j µ + g k µ = 1 µ K k=1 K j=1 α k α j g j -g k g j + g k = 1 µ K k=1 K-1 j=1 α k α j g j -g k g j + g k + g k -g j g j + g k = 0.
Hence, the obtained light and heavy-traffic interpolation is exact.

In Figure 2 (left) we observe that when µ 2 = 1, so when the service requirements of both classes coincide, the relative error is 0, as proven in Equation ( 29).

Numerical results

In this section we numerically investigate the accuracy of the approximations obtained in this paper. In Section 6.1 we consider the mean conditional sojourn time and in Section 6.2 the mean unconditional sojourn time, whose approximations are stated in Proposition 4.2 and Corollary 4.3, respectively. As stated in Section 2, Fayolle et al. [START_REF] Fayolle | Sharing a processor among many job classes[END_REF] obtain analytical expressions of the mean conditional and unconditional sojourn time under the assumption of exponentially distributed service requirements. For exponentially distributed service requirements, we will evaluate the accuracy of the approximations by comparing the exact formulas as obtained in [START_REF] Fayolle | Sharing a processor among many job classes[END_REF], see Equations ( 2) and ( 4), with the approximations as given in ( 24) and [START_REF] Van Kessel | Differentiated bandwidth sharing with disparate flow sizes[END_REF].

In order to obtain a more complete understanding on the accuracy of the approximation, we will also consider hyperexponential and Pareto distributions. Hyperexponential and Pareto distributions have a decreasing hazard-rate, and their second moment can be made arbitrarily large, and because of these features it has been proposed as an appropriate distribution to model service time distributions in the Internet.

We say that B i has a hyperexponential distribution with m i phases if

P(B i ≤ b i ) = 1- mi k=1 p ik e (-bi/E[B ik ])
, where p ik is the probability that a class-i customer is exponentially distributed with mean E[B ik ]. In order to derive exact expressions for the mean sojourn time when the service requirements are hyperexponentially distributed, we make the observation that if classes k = 1, . . . , m i are exponentially distributed (where class k has arrival rate λ k and mean service requirement E[B k ]) and have the same DPS weight, g 1 = . . . = g mi , then they can be seen as a single (merged) class i with a hyperexponential distribution with parameters

p ik = λ k / mi l=1 λ l and E[B ik ] = E[B k ],
for each phase k = 1, . . . , m i . This allows us to calculate the performance with hyperexponential distribution using Equations ( 2) and ( 4) which are derived for exponential distributions. We say that B i has Pareto distribution with scale parameter c i and shape parameter

γ i if P(B i ≤ b i ) = 1 - 1 1 + c i b i γi .
In order to derive exact expressions for the mean unconditional sojourn time we solved numerically Equation (1). However, the output was not stable enough and therefore we opted to simulate the DPS queue instead (using MATLAB). The simulation results are based on averaging 10 runs with each run comprising 5 • 10 5 busy periods. A busy period is defined as the interval of time between two consecutive time epochs when the system becomes empty, such points being regenerative points for the stochastic process of interest. Note that the hyperexponential distribution satisfies the sufficient condition to hold admissibility (Equation ( 9)), whereas Pareto does not satisfy it; for any value of γ i in the Pareto distribution, higher order moments than γ i are unbounded. In the latter we show that even thought condition ( 9) is not satisfied the light-traffic interpolation remains accurate. Throughout this section the performance criteria will be the relative error. For instance, for the mean conditional sojourn time, we will calculate 100% ×

S k (λ,b)-S IN T k (λ,b) S k (λ,b)
, and for the mean unconditional

sojourn time 100% × S k (λ)-S IN T k (λ) S k (λ)
. Before explaining in detail the numerical results we have obtained, we summarize our main conclusions:

• The approximation is accurate over a broad range of parameter values.

• For a given set of parameters, the relative error for the mean conditional sojourn time increases as the service requirement of the tagged customer increases.

• The error increases as the disparity among the weights increases.

• For any given scenario, the largest relative error occurs in an intermediate load between 0 and 1.

• The largest relative errors for the mean conditional sojourn time occur for service requirements b that are very unlikely to occur. This also explains the high accuracy of our approximation for the mean unconditional sojourn time.

Conditional sojourn time

In this section we measure the accuracy of the mean conditional sojourn time given in Proposition 4.2.

Scenario 1. In Figure 3 we consider four classes K = 4 with exponentially distributed service requirements. The parameters of the classes are fixed, and we vary the total arrival rate in order for the load to cover the range of stable values. We consider

E[B 1 ] = 2, E[B 2 ] = 5, E[B 3 ] = 7, E[B 4 ] = 10, g 1 = 30, g 2 = 25
, g 3 = 20, g 4 = 10, and α 1 = 10/36, α 2 = 5/36, α 3 = 8/36, α 4 = 13/36 such that λ i = α i * λ, i = 1, . . . , 4, where λ is the total arrival rate. In Figure 3 we plot the relative error of our approximation for the mean conditional sojourn time of a tagged class-i customer, for i = 1, . . . , 4, where the size of the tagged class-i customer, b i , is selected such that the probability of the event is P(B i ≤ b i ) = 0.01, P(B i ≤ b i ) = 0.50 and P(B i ≤ b i ) = 0.99, respectively. As can be seen, the relative error for the mean conditional sojourn time remains small and always below 6%.

Scenario 2. In Figure 4 we consider two classes K = 2 with exponentially distributed service requirements. We fixed the parameters

E[B 1 ] = 2, E[B 2 ] = 1, g 1 = 1, g 2 = 3
, α 1 = 0.415, α 2 = 0.585 and λ i = α i * λ. We let the service requirement of the class-i tagged customer span between 0 and b i,max where P(B i ≤ b i,max ) = 0.99 and for each b we plot the largest absolute relative error that can be found

i such that P(B i ≤ b i ) = 0.01 (left), P(B i ≤ b i ) = 0.50 (middle), P(B i ≤ b i ) = 0.99 (right).
for a ρ ∈ [0, 1). We observe a largest error of at most 6%. Scenario 3. In Figure 5 we consider again two classes with exponentially distributed service requirements. As parameters we fix:

E[B 1 ] = 2, E[B 2 ] = 1, λ 1 = 0.2, λ 2 = 1.5λ 1 and b = 1.
We chose g 2 = 1-g 1 and let g 1 vary on the horizontal axis. In the figure we plot the mean conditional sojourn time and our approximation. We see that the property stated in Section 4.3 is satisfied, namely as g 1 increases S . We assume that an arriving customer is of class 1 (class 2) with probability α 1 = 7/12 (α 2 = 5/12). As in Scenario 1, we select the service requirement of the tagged customer such that P(B i ≤ b i ) = 0.01, 0.5 and 0.99. We see that the error increases as the size of the tagged customer increases. However it is remarkable how accurate the approximation is.

In Figure 6 we consider Scenario 4. We vary the service requirement of the class-i tagged customer between 0 and b i,max where P(B i ≤ b i,max ) = 0.99 and for each b we plot the largest absolute relative error that can be found for a ρ ∈ [0, 1). We observe that the error increases as the size of the tagged customer increases. The largest absolute relative error is of the order of 22% for the class with the smallest weight and of the order of 3% for the class with the highest weight.

Unconditional sojourn time

In this section we evaluate the accuracy of the mean unconditional sojourn time given in Corollary 4.3.

In Figure 8 we consider the same parameter setting as in Scenario 1, and we observe that the largest relative error for the mean unconditional sojourn time is less than 3.5%.

In Figure 9 we consider two classes with hyper-exponentially distributed service requirements. The parameters are the ones considered in Scenario 4. We conclude that the largest relative error for the mean unconditional sojourn time is around 3%.

As pointed out in the beginning of the section, we observe that the relative error for the mean unconditional sojourn time tends to be smaller than the ones observed for the mean conditional sojourn time. This can be explained by noting that the largest errors in the mean conditional sojourn time tend to occur for service requirements that happen with a very low probability.

In Figure 10 we consider two classes with hyper-exponentially distributed service requirements. The parameters are the same as in Scenario 4. We chose g 2 = 1 -g 1 and let g 1 vary on the horizontal axis. For each given g 1 we calculate the largest absolute relative error for the mean unconditional sojourn time as we let ρ range from 0 to 1. We observe that the relative error for the unconditional sojourn time is at most of 30%, and that this happens when class 2 receives full priority. Scenario 5. In Figure 12 we consider Scenario 1 but in this case with Pareto distributed service requirements. We consider four classes with c 1 = 1/4, c 2 = 1/10, c 3 = 1/14, c 4 = 1/20 and γ 1 = 3, γ 2 = 3,

γ 3 = 3, γ 4 = 3, such that, E[B 1 ] = 2, E[B 2 ] = 5, E[B 3 ] = 7, E[B 4 ] =
10, the weights are set to g 1 = 30, g 2 = 25, g 3 = 20, g 4 = 10 and α 1 = 10/36, α 2 = 5/36, α 3 = 8/36, α 4 = 13/36 such that λ i = α i * λ, i = 1, . . . , 4, where λ is the total arrival rate. Notice that E[B i ], g i , α i , i = 1, . . . , 4 are the same as in Scenario 1. We note that the point ρ = 1 is not obtained from simulations, and that instead it comes from the heavy-traffic condition and it is therefore exact. We conclude that the largest relative error for the mean unconditional sojourn time is around 5%. Scenario 6. In Figure 13 we consider Scenario 4 but in this case with Pareto distributed service requirements. We consider two classes with c 1 = 3/22, c 2 = 3/88 and γ 1 = 3, γ 2 = 3, such that, E[B 1 ] = 11/3, E[B 2 ] = 44/3 and the weights are set to g 1 = 2 and g 2 = 5. We assume that an arriving customer is of class 1 (class 2) with probability α 1 = 7/12 (α 2 = 5/12). Notice that E[B i ], g i , α i , i = 1, . . . , 2 are the same as in Scenario 4. We note that the point ρ = 1 is not obtained from simulations, and that instead it comes from the heavy-traffic condition and it is therefore exact. We conclude that the largest relative error for the mean unconditional sojourn time is less than 5%. We can now consider two cases. If B Ut -

g U t g k b > 0, then Equation (30) is equal to - t 2 2 + B Ut t + bt B U t B U t - g U t g k b = - B 2 Ut 2 + B Ut B Ut + bB Ut -   - B Ut - g U t g k b 2 2 + B Ut B Ut - g Ut g k b + b B Ut - g Ut g k b    = 1 2 g Ut b g k 2 + g Ut b 2 g k . If B Ut - g U t g k b < 0, then Equation (30) is equal to - t 2 2 + B Ut t + bt B U t 0 = - B 2 Ut 2 + B Ut B Ut + bB Ut = B 2 Ut 2 + bB Ut .
We thus obtain

E ∞ 0 1 B Ut ≥ t > B Ut - g Ut g k b (-t + B Ut + b) dt = E 1 2 min{B Ut , b g Ut g k } 2 + b min{B Ut , b g Ut g k } . (31)
Second, we focus on the calculation corresponding to the second term of ( 16), that is, the case when t ≤ 0 ≤ t + B Ut and

g U t g k b -t ≤ B Ut . We have 0 -∞ E 1 g Ut g k b -B Ut ≤ t g k + g Ut g k b dt = ∞ 0 E 1 g Ut g k b -B Ut ≤ -t g k + g Ut g k b dt = E ∞ 0 1 g Ut g k b -B Ut ≤ -t g k + g Ut g k bdt ,
as we make use of Tonelli's Theorem. It follows that

∞ 0 1 t ≤ B Ut - g Ut g k b g k + g Ut g k bdt = g k + g Ut g k B U t - g U t g k b + 0 bdt = b g k + g Ut g k B Ut - g Ut g k b + . (32)
We can now consider two cases. If B Ut -

g U t g k b > 0, then Equation (32) is equal to b g k + g Ut g k B Ut - g Ut g k b . If B Ut - g U t
g k b ≤ 0, then Equation (32) is equal to 0. We thus obtain

E ∞ 0 1 g Ut g k b -B Ut ≤ -t g k + g Ut g k bdt = E g k + g Ut g k b B Ut -min{B Ut , g Ut g k b} . (33)
Third, we focus on the calculation corresponding to the third term of ( 16), that is, the case when t + B Ut < 0 . We have

0 -∞ E[1 [t < -B Ut ] b -b]dt = ∞ 0 E[1 [-t < -B Ut ] b -b]dt = E b ∞ 0 (1 [B Ut < t] -1)dt
as we make use of Tonelli's Theorem. It follows that b

∞ 0 (1 [B Ut < t] -1)dt = b ∞ 0 -1 [B Ut > t] dt = -b B U t 0 dt = -bB Ut .
We thus obtain

E ∞ 0 (1 [B Ut < t] b -b)dt = -bE[B Ut ]. (34)
Fourth, we focus on the calculation corresponding to the fourth term of [START_REF] Kelly | Charging and rate control for elastic traffic[END_REF], that is, the case when 0 < t < b and b-t g k >

B U t g U t . We have ∞ 0 E 1 t < b - g k B Ut g ut (b + B Ut ) dt = E ∞ 0 1 t < b - g k B Ut g Ut (b + B Ut ) dt ,
as we make use of Tonelli's Theorem. It follows that

∞ 0 1 t < b - g k B Ut g Ut (b + B Ut ) dt = b- g k B U t g U t + 0 (b + B Ut ) dt. ( 35
) If b - g k B U t g U t > 0 then Equation (35) is equal to b- g k B U t g U t 0 (b + B Ut ) dt = (b + B Ut ) b - g k B Ut g Ut = b 2 + 1 - g k g Ut bB Ut - g k g Ut B 2
Ut .

If b -

g k B U t g U t
≤ 0 then Equation ( 35) is equal to 0. We thus obtain

∞ 0 E 1 t < b - g k B Ut g Ut (b + B Ut ) dt = E b 2 + (B Ut -min{b, g k g Ut B Ut })b -min{b, g k g Ut B Ut }B Ut . (36)
Fifth, we focus on the calculation corresponding to the fifth term of ( 16), that is, the case when 0 < t < b and b-t

g k ≤ B U t g U t . We have ∞ 0 E 1 b - g k B Ut g Ut ≤ t < b -t g Ut g k + b g k + g Ut g k dt = E ∞ 0 1 b - g k B Ut g Ut ≤ t < b -t g Ut g k + b g k + g Ut g k dt
as we make use of Tonelli's Theorem. It follows that

∞ 0 1 b - g k B Ut g ut ≤ t < b -t g Ut g k + b g k + g Ut g k dt = b b- g k B U t g U t + -t g Ut g k + b g k + g Ut g k dt = - t 2 2 g Ut g k + tb g k + g Ut g k b b- g k B U t g U t + . ( 37
) If b - g k B U t g U t > 0 then Equation (37) is equal to ∞ 0 1 b - g k B Ut g Ut ≤ t < b -t g Ut g k + b g k + g Ut g k dt = - t 2 2 g Ut g k + tb g k + g Ut g k b b- g k B U t g U t = g k g Ut B Ut (b + B Ut 2 ). If b - g k B U t g U t ≤ 0 then Equation (37) is equal to ∞ 0 1 b - g k B Ut g Ut ≤ t < b -t g Ut g k + b g k + g Ut g k dt = - t 2 2 g Ut g k + tb g k + g Ut g k b 0 = b 2 g Ut 2g k + 1 .
We thus obtain

∞ 0 E 1 b - g k B Ut g Ut ≤ t < b -t g Ut g k + b g k + g Ut g k dt = E g k g Ut min{ g Ut g k b, B Ut } 1 2 min{ g Ut g k b, B Ut } + b . (38)
Sixth, we focus on the subtraction between the sixth term of [START_REF] Kelly | Charging and rate control for elastic traffic[END_REF], that is, the case when 0 < b < t, and

E S k (0, b) A = 0 = b. We then have ∞ 0 E [1 [b < t] b -b] dt = -E ∞ 0 1 [0 < t < b] bdt
as we make use of Tonelli's Theorem. It follows that

- ∞ 0 1 [0 < t < b] bdt = - b 0 bdt = -b 2 .
We thus have

∞ 0 E [1 [b < t] b -b] dt = -b 2 . (39)
In conclusion, summing Equations ( 31), ( 33), ( 34), ( 36), ( 38) and (39) we obtain

S (1) k (0, b) = R E S k (0, b) A(-∞, ∞) = 1, τ = t -E S k (0, b) A(-∞, ∞) = 0 dt = E 1 2
α i g i g k b 0 d b E[B i ] E[B j ] + g k g j -1 E[min{B j , g j g k b}] + g k g i -1 ∞ g j g k b E[min{B i , g i g k (x - g j g k b)}] • [1 -F j (x)]dx + g k g j g k g i -1 g j g k b g j g k ( b-b) E[min{B i , g i g k ( b - g k g j z)}] • [1 -F j (z)]dz . ( 43
)
We observe that r 0 (b) coincides with the zeroth light-traffic derivative obtained in Equation ( 15) and we verified that r 1 (b), obtained in Equation ( 42), coincides with the first light-traffic derivative shown in Equation [START_REF] Kherani | TCP as an implementation of age-based scheduling: fairness and performance[END_REF].

We can now derive the following light-traffic approximation (of order 2) of the mean conditional sojourn time for a tagged class-k customer with service requirement b when λ is small

We next assess the impact of having the second light-traffic derivative, thus obtaining a second order light-traffic approximation and a third order light and heavy-traffic interpolation. Then, we numerically compare the accuracy of Equations ( 18) and (44), and Equations ( 24) and (45).

In Figures 14 and15 we plot the difference of the relative errors of Equations ( 18) and (44). Since we know that all relative errors are positive and since the resulting functions are also positive, this implies that the higher order light-traffic approximation is always more accurate. However, if we focus on Figures 16 and17 and compare them with Figures 3 and11, respectively, we conclude that the accuracy of the interpolation for intermediate loads does not necessarily improve as the degree of the interpolation increases. In both cases, having a third order light and heavy-traffic interpolation reduces the largest relative error only for the case P(B i ≤ b i ) = 0.99.

  k . A class-k customer has a generally distributed service requirement denoted by B k and we assume E[B 2 k ] < ∞, k = 1, . . . , K. The traffic intensity for class-k customers is denoted by ρ k := λ k E[B k ] and the total traffic intensity is denoted by

.

  We denote by S k (λ, b) the conditional sojourn time of a tagged class-k customer with a given service requirement b, when the arrival rate is λ. We are interested in approximatingS k (λ, b) := E[S k (λ, b)],the mean conditional sojourn time of the tagged class-k customer. We further denote by S k (λ) := ∞ 0 S k (λ, b)dF k (b) the mean unconditional sojourn time of the tagged class-k customer, where P(B k ≤ b) = F k (b) is the distribution function of B k , and S(λ) := K k=1 α k S k (λ) is the mean unconditional sojourn time of an arbitrary customer.

  b) = S k (0, b) and we refer to it as the zeroth light-traffic derivative. Moreover, S (m) k (0, b), m = 1, 2, . . . , denotes the m-th derivative of S k (λ, b) with respect to λ at λ = 0, i.e., ∂ m S k (λ,b) ∂λ m λ=0

Figure 1 :Figure 2 :

 12 Figure 1: Relative error for the mean unconditional sojourn time for K = 2 with respect to g 1 .

Figure 3 :

 3 Figure 3: Scenario 1: Relative error for the mean conditional sojourn time for a tagged class-i customer with service requirement b i such that P(B i ≤ b i ) = 0.01 (left), P(B i ≤ b i ) = 0.50 (middle), P(B i ≤ b i ) = 0.99 (right).

Figure 4 :

 4 Figure 4: Scenario 2. Largest absolute relative error for the mean conditional sojourn time as a function of P(B i ≤ b i ).

Figure 6 :

 6 Figure 5: Scenario 3: Mean conditional sojourn time as a function of g 1 .

Figure 7 :

 7 Figure 7: Scenario 4: Relative error for the mean conditional sojourn time for a tagged class-i customer with service requirement b i such that P(B i ≤ b i ) = 0.01 (left), P(B i ≤ b i ) = 0.50 (middle), P(B i ≤ b i ) = 0.99 (right).

IN T 1 (

 1 λ, b) decreases and S IN T 2(λ, b) increases. Besides, it can be observed from the figure that the approximation looses accuracy as one class is given more priority, i.e., g 1 → 0 or g 1 → 1.

Scenario 4 .

 4 In Figure 11 we consider two classes with hyperexponential distributed service requirements with E[B 1 ] = 11/3, E[B 2 ] = 44/3. Each of the hyperexponential distributions has 3 phases. The parameters are as follows: for class 1 we take E[B 11 ] = 3.5, E[B 12 ] = 2, E[B 13 ] = 5, p 11 = 10/21, p 12 = 5/21, p 13 = 6/21, and for class 2 we take E[B 21 ] = 10, E[B 22 ] = 15, E[B 23 ] = 20, p 21 = 4/15, p 22 = 8/15, p 23 = 3/15. The weights are set to g 1 = 2 and g 2 = 5

Figure 8 :Figure 9 :Figure 10 :Figure 11 :

 891011 Figure 8: Relative error for the mean unconditional sojourn time in Scenario 1.

Figure 12 :Figure 13 :

 1213 Figure 12: Relative error for the mean unconditional sojourn time in Scenario 5.

r m (b) = lim λ→0 1 λ 1 (

 11 m S k (λ, b) -Equation (1) in the above formula, one can easily derive the terms r m (b), m = 1, . . . , recursively. For the first and second order derivatives we obtain in this way r

2 m=0λ

 2 m r m (b) = r 0 (b) + r 1 (b)λ + r 2 (b)λ 2 , (44) where r 0 (b), r 1 (b) and r 2 (b) are given in Equations (41), (42) and (43), respectively. Using this result together with Proposition 4.1 and the heavy-traffic result[START_REF] Bu | Fixed point approximation for TCP behaviour in an AQM network[END_REF] we obtain the third order light and heavytraffic interpolation immediatelyS IN T k (λ, b) = r 0 (b) + r 1 (b)λ + r 2 (b)λ 2 + b g k E[B 2 ] K j=1 α j E[B 2 j ]/g j (λE[B]) 3 1 -λE[B].

Figure 14 :

 14 Figure 14: Scenario 1: Difference of the relative errors of Equations (18) and (44) for a tagged class-i customer with service requirement b i such that P(B i ≤ b i ) = 0.01 (left), P(B i ≤ b i ) = 0.50 (middle), P(B i ≤ b i ) = 0.99 (right).

Figure 15 :

 15 Figure 15: Scenario 4: Difference of the relative errors of Equations (18) and (44) for a tagged class-i customer with service requirement b i such that P(B i ≤ b i ) = 0.01 (left), P(B i ≤ b i ) = 0.50 (middle), P(B i ≤ b i ) = 0.99 (right).

Figure 16 :

 16 Figure 16: Scenario 1: Relative error for the 3rd order mean conditional sojourn time for a tagged class-i customer with service requirement b i such that P(B i ≤ b i ) = 0.01 (left), P(B i ≤ b i ) = 0.50 (middle), P(B i ≤ b i ) = 0.99 (right).

Figure 17 :

 17 Figure 17: Scenario 4: Relative error for the 3rd order mean conditional sojourn time for a tagged class-i customer with service requirement b i such that P(B i ≤ b i ) = 0.01 (left), P(B i ≤ b i ) = 0.50 (middle), P(B i ≤ b i ) = 0.99 (right).

  min{B Ut , b g Ut g k } 2 + b min{B Ut , b g Ut g k } + g k + g Ut g k b B Ut -min{B Ut , g Ut g k b} -bB Ut +b 2 + B Ut -Ut } + b -b 2 Ut g k bB Ut -bB Ut + b 2 + bB Ut -b 2

			g k g Ut	min{	g Ut g k	b, B Ut } b -	g k g Ut	min{	g Ut g k	b, B Ut }B Ut
	+ b, B = E g k g Ut min{ g Ut g k b, B Ut } 1 2 min{ g Ut g k 1 2 1 + g k g Ut min{B Ut , b g Ut g k } 2 + b -	g k + g Ut g k	b -	g k g Ut	b -	g k g Ut	B Ut +	g k g Ut	b min{B Ut , b	g Ut g k	}
	+ g k + g = E 1 2 1 +	g k g Ut	min{B Ut , b	g Ut g k	} 2 -b	g Ut g k	+	g k g Ut	B Ut min{B Ut , b	g Ut g k	} +	g k + g Ut g k	bB Ut .

Acknowledgements

The authors are thankful to Professor A.M. Makowski (University of Maryland at College Park) for helpful discussions.

Appendix A: Proof of Lemma 3.1

To calculate S [START_REF] Altman | A survey on discriminatory processor sharing[END_REF] k (0, b) we need to calculate ∞ -∞ E[S k,t,Ut,B U t ]dt, where S k,t,ut,bu t is as given in Equation [START_REF] Kelly | Charging and rate control for elastic traffic[END_REF]. We first focus on the calculation corresponding to the first term of [START_REF] Kelly | Charging and rate control for elastic traffic[END_REF], that is, the case when t ≤ 0 ≤ t + B Ut and t < g U t g k b -B Ut , (where the inequalities of the random variables hold sample-path wise). We have

as we make use of Tonelli's Theorem. It follows that

Appendix B: Alternative way to derive light-traffic derivatives

In this section we show that the light-traffic derivatives can also be obtained from the integro-differential equation [START_REF] Altman | A survey on discriminatory processor sharing[END_REF]. The calculations below are only valid for the DPS model, while our approach is constructive and can easily be adapted to other models. As explained at the beginning of Section 3, for λ small enough, S k (λ, b) can be approximated by a polynomial

where

In Section 3.1 we described how the coefficients r m (b) could be derived. This holds true for a large class of models. We now show how the coefficients could alternatively be obtained for the DPS model. This can be done using the expression for the mean conditional sojourn time by Fayolle et al (Equation ( 1)).


Pauline Folz
email: pauline.folz@univ-nantes.fr

Gabriela Montoya
email: gabriela.montoya@univ-nantes.fr

Hala Skaf-Molli

Pascal Molli
email: pascal.molli@univ-nantes.fr

Maria-Esther Vidal
email: mvidal@ldc.usb.ve

SemLAV: Querying Deep Web and Linked Open Data with SPARQL

SemLAV allows to execute SPARQL queries against the Deep Web and Linked Open Data data sources. It implements the mediatorwrapper architecture based on view definitions over remote data sources. SPARQL queries are expressed using a mediator schema vocabulary, and SemLAV selects relevant data sources and rank them. The ranking strategy is designed to deliver results quickly based only on view definitions, i.e., no statistics, nor probing on sources are required. In this demonstration, we validate the effectiveness of SemLAV approach with real data sources from social networks and Linked Open Data. We show in different setups that materializing only a subset of ranked relevant views is enough to deliver significant part of expected results.

Introduction

The Deep Web is constituted from data that are not indexed by traditional search engines, and may not have static URL links; it is around 500 times the size of the Surface Web [START_REF] He | Accessing the Deep Web[END_REF]. Performing SPARQL queries without considering the Deep Web can deliver poor results. For example, the execution of the SPARQL query: Which members of the Semantic Web community are interested in Dalai Lama, Barack Obama, or Rihanna? (cf figure 1) without the Deep Web support, will deliver no answer. Some semantic data-warehouses such as Virtuoso with SPONGER [START_REF]White paper, OpenLink Software[END_REF] address this issue by declaring wrappers able to query unsemantified data including web service calls, CSV files, and so on. Such approach is relevant if the number of sources used to answer the query remains low. However, the time for first answers can be very high because the query engine has to contact all the declared wrappers for a query.

Contrary, SemLAV [START_REF] Montoya | SemLAV: Local-As-View Mediation for SPARQL[END_REF] is able to deliver answers quickly for this query. It follows the mediator-wrapper approach where the Deep Web data can be retrieved through view definitions and wrappers. A view constitutes a data source for the mediator. Given a SPARQL query, SemLAV selects relevant views and most importantly, it ranks them without requiring costly statistics. SemLAV Fig. 1: Which members of the Semantic Web community are interested in Dalai Lama, Barack Obama, or Rihanna? uses wrappers to semantify data of the selected data sources on-demand during query execution. It retrieves data from the ranked sources in a smart order that gives a high probability of delivering results. Consequently, even in the presence of a large number of relevant views, SemLAV is able to deliver results in a reasonable time. In this paper, we demonstrate how SemLAV is able to quickly deliver results for SPARQL queries mixing Deep Web data sources and Linked Open Data defined using around 250 views. A video of the demo is available at https://www.youtube.com/channel/UCMQO5QVq5UcztE8kkkRRXKQ/videos.

SemLAV Overview

Given a query and a set of views, SemLAV computes a ranked set of relevant views for answering the query. Ranking is computed using the number of equivalent covered rewritings detailed in [START_REF] Montoya | SemLAV: Local-As-View Mediation for SPARQL[END_REF]. Views are materialized by calling traditional wrappers such as those defined in SPONGER [START_REF]White paper, OpenLink Software[END_REF] in sequence or in parallel. Each time a new view is fully materialized, the original query is executed to deliver results as fast as possible. Views used in SemLAV could be also generated by tools like Karma [START_REF] Taheriyan | Rapidly Integrating Services into the Linked Data Cloud[END_REF]. To illustrate the benefits of SemLAV, consider the query defined in Figure 1, and the following five views: v1 (P , A , I , C , L ) :-made (P , A) , a f f i l i a t i o n (P , I ) , member (P , C) , l a b e l (C , L ) v2 (A , T , P , N, C) :-t i t l e (A , T) , made (P , A) , name (P , N) , member (P , C) v3 (P , N, R ,M) :-name (P , N) , name (R ,M) , knows (P , R) v4 (P , N, G , R , C) :-name (P , N) , g e n d e r (P , G) , knows (P , R) , member (P , C) v5 (P , N, R , C , L ) :-name (P , N) , knows (P , R) , member (P , C) , l a b e l (C , L )

SemLAV will compute the following sorted bucked for each query subgoal:

member(P, C) label(C, L) knows(P, WKP) name(WKP, N) v5(P,N,R,C,L) v5(P,N,R,C,L) v5(P,N,R,C,L) v5(P,N,R,C,L) v4(P,N,G,R,C) v1(P,A,I,C,L) v4(P,N,G,R,C) v4(P,N,G,R,C) v1(P,A,I,C,L) v3(P,N,R,M) v2(A,T,P,N,C) v2(A,T,P,N,C) v3(P,N,R,M)
The execution of all possible combinations produces the complete answers for the query. To deliver answers quickly, SemLAV ranks the relevant views according to their contribution to cover the query subgoals, i.e., first ranked views are those that cover maximum number of subgoals. Therefore, the number of covered combinations grows as fast as possible.

# Included

SemLAV ranking

Random order views (k) Included views (

V k ) # Covered rewritings Included views (V k ) # Covered rewritings 1 v5 1 × 1 × 1 × 1 = 1 v1 1 × 1 × 0 × 0 = 0 2 v5, v4 2 × 1 × 2 × 2 = 8 v1, v2 2 × 1 × 0 × 1 = 0 3 v5, v4, v1 3 × 2 × 2 × 2 = 24 v1, v2, v3 2 × 1 × 1 × 2 = 4 4 v5, v4, v1, v3 3 × 2 × 3 × 3 = 54 v1, v2, v3, v4 3 × 1 × 2 × 3 = 18 5 v5, v4, v1, v3, v2 4 × 2 × 3 × 4 =

Queries

We will demonstrate the behavior of SemLAV with the following four queries:

-Query 1: Semantic Web community members who know well-known personalities (e.g., Dalai Lama, Barack Obama, or Rihanna); for these persons show their affiliation, localization, and number of contributions that have done to the community.

-Query 2: Members of different scientific communities that know Tim Berners-Lee; for these persons show their affiliation and localization. -Query 3: The Semantic Web members that have been more active in Twitter posting tweets about ESWC2014. -Query 4: Members of the Database community that are known by Semantic Web members. For these persons, show their affiliation and localization.

Figure 3 presents the demonstration interface; all the reported results are computed and plotted dynamically. Queries can be selected at the top. The area enclosed in the blue rectangle (number 1) displays the query, and the Run and Stop buttons that starts and interrupts the query processing, respectively. Additionally, the number of relevant views and the total number of views are reported, as well as, view definitions and ranking are displayed using the buttons in the upper right side of this area. Area enclosed in the red rectangle (number 2) shows the interface state after 10 minutes running Query 1; the SemLAV ranking and a random sorting of the views are also shown. Line charts illustrate relationships between the number of produced answers and the number sources whose data have been retrieved. The number of produced answers has impressively grown before retrieving data from 6% of the sources (15 out of 250 selected sources), such that more than 50% of the answers has been delivered. Additionally, for the same amount of retrieved views, for example for 10 views, SemLAV was able to produce 819 answers, whereas the random sorting could not produce any answer so far. In the area enclosed in the green rectangle (number 3), query results are displayed in a map based on the retrieved locations. Attendees will observe the benefits of the SemLAV strategies in action and how SemLAV is able to deliver a considerable number of answers in a relatively low amount of time.

Conclusions

In this demonstration, we validate the effectiveness of the SemLAV approach, and illustrate how SPARQL queries can be efficiently executed against realworld sources from social networks and the Linked Open Data cloud. In different setups, sources are selected and ranked by SemLAV in a way that it benefits the incremental delivery of answers, while only a small number of views are retrieved.

Fig. 2 :

 2 Fig. 2: Description of the followers of ESWC Conferences Twitter account

Fig. 3 :

 3 Fig. 3: Snapshots for Query 1 execution. During the demonstration all the reported results will be computed on-the-fly.

  In this demonstration, we use well known Deep Web sites such as social networks Twitter and Facebook, and Linked Open Data sources such as DBLP, Semantic Web Dog Food, and DBpedia. We define 253 views data sources (views) over Twitter, Facebook, DBLP, Semantic Web Dog Food, and DBpedia. We use several RDF vocabularies to describe the members of a community, and the links between them and the Linked Open Data cloud. The following are our assump-

	96 v1, v2, v3, v4, v5 4 × 2 × 3 × 4 = 96
	3 Demonstration Setup

tions: i) a person is member of a community if there is a link between the person and the community. This link is represented with the foaf:member predicate. Links of this type are established, for example, when someone follows a community conference Twitter account, or someone is member of a community group in Facebook, or someone has published a paper in a community conference. ii) A person knows another person if there exists a link between them. This link is represented with the foaf:knows predicate. Links of this type are established, for example, when: a user is following someone in Twitter, two persons are coauthors of a paper. Sources are described by SPARQL queries, e.g., query in SELECT DISTINCT * WHERE { ? f o l l o w e r <h t t p : / / x m l n s . com/ f o a f / 0 . 1 / name> ? name . ? f o l l o w e r <h t t p : / / x m l n s . com/ f o a f / 0 . 1 / knows> ? f o l l o w e d . ? f o l l o w e r <h t t p : / / x m l n s . com/ f o a f / 0 . 1 / member> ? community . ? community <h t t p : / /www . w3 . o r g /2000/01/ r d f -schema#l a b e l > " S e m a n t i c Web" }