Nacira Guerouahane
email: naciraro@hotmail.fr

Djamil Aissani

Nadir Farhi
email: nadir.farhi@ifsttar.fr

Louiza Bouallouche-Medjkoune

M/G/c/c state dependent queuing model for a road traffic system of two sections in tandem

Keywords: Traffic flow modeling, finite queuing systems, M/G/c/c state dependent

We propose in this article a M/G/c/c state dependent queuing model for road traffic flow. The model is based on finite capacity queuing theory which captures the stationary density-flow relationships. It is also inspired from the deterministic Godunov scheme for the road traffic simulation.

We first present a reformulation of the existing linear case of M/G/c/c state dependent model, in order to use flow rather than speed variables. We then extend this model in order to consider upstream traffic demand and downstream traffic supply. After that, we propose the model for two road sections in tandem where both sections influence each other. In order to deal with this mutual dependence, we solve an implicit system given by an algebraic equation. Finally, we derive some performance measures (throughput and expected travel time). A comparison with results predicted by the M/G/c/c state dependent queuing networks shows that the model we propose here captures really the dynamics of the road traffic.

Introduction

Congestion is a phenomenon that arises in a variety of contexts. The most familiar representation is urban traffic congestion. Congested networks involve complex traffic interactions.

Providing an analytical description of these intricate interactions is challenging. The dynamics of traffic flows is submitted to stochastic nature of traffic demand and supply functions of vehicles 5 passing from one section to another.

One of the well known macroscopic traffic model on a road section is the LWR (Lighthill-Whitham-Richards) first-order continuum one [START_REF] Lighthill | On kinematic waves: A theory of traffic flow on long, crowded roads[END_REF][START_REF] Richards | Shock waves on the highway[END_REF], which assumes the existence of a steadystate relationship for the traffic, called the fundamental diagram, giving the traffic flow in function of the vehicular density in the road section. In this paper, we present a reformulation of the a stochastic traffic model based on this new formulation and inspired from the Godunov scheme [START_REF] Godunov | A Difference Scheme for Numerical Solution of Discontinuous Solution of Hydrodynamic Equations[END_REF][START_REF] Lebacque | The Godunov scheme and what it means for first order traffic flow models[END_REF] of the LWR traffic model. We derive a stationary probability distribution of the M/G/c/c state dependent queuing model on a road section, by considering density-flow fundamental diagrams rather than density-speed ones. The model assumes a quadratic fundamental diagram which correctly captures the stationary density-flow relationships in both non-congested and congestion conditions. By this, we consider the traffic demand and supply functions for the section, and distinguish three road section systems, an open road section, a constrained road section and a closed road section. Finally, we present a model of two road sections in tandem, derive some performance measures and show on an academic example that the model captures the dynamics of the road traffic. The model we present here can be used to the analysis of travel times through road traffic networks (derive probability distributions, reliability indexes, etc), as in [START_REF] Farhi | Modélisation minplus et commande du trafic de villes régulières[END_REF][START_REF] Farhi | Algebraic approach for performance bound calculus on Transportation networks[END_REF][START_REF] Farhi | Upper bounds for the travel time on linear traffic systems, 17th meeting of the EWGT[END_REF],

where an algebraic deterministic approach is used. The approach present here remains also valid with a triangular fundamental diagram (which is the most used), but the formulas will change [START_REF] Guerrouahane | A queuing model for road traffic simulation[END_REF].

The remainder of this article is organized as follows. In Section 2, we first present a review of the existing works. In this regard, we present in Section 3 a short review of the M/G/c/c state dependent queuing model of Jain and Smith [START_REF] Jain | Modeling vehicular traffic flow using M/G/C/C state dependent queueing models[END_REF]. We then propose a new reformulation of this model by working with flows rather than speeds. We rewrite the stationary probability distribution of the number of cars on the road section. In Section 4, we present a model of two road sections in tandem where both road sections influence each other. An implicit system given by an algebraic equation is solved, in order to deal with this mutual dependence. We derive some performance measures of both road sections (throughput and expected travel time) and compare our simulation results with those of existing M/G/c/c state dependent queuing models (Kerbache and Smith model). In Section 5, we briefly summarize our findings and future work.

Literature review

Congestion is a phenomenon that arises on local as well as large areas, whenever traffic demand exceeds traffic supply. Traffic flow on freeways is a complex process with many interacting components and random perturbations such as traffic jams, stop-and-go waves, hysteresis phenomena, etc. These perturbations propagate from downstream to upstream sections. During traffic jams, drivers are slowing down when they observe traffic congestion in the downstream section, causing upstream propagation of a traffic density perturbation. A link of the network is modeled as a sequence of road sections, for which fundamental diagrams are given. As the sequence of sections is in series, if any section is not performing optimally, the whole link will not be operating efficiently. We base here on the LWR first order model [START_REF] Lighthill | On kinematic waves: A theory of traffic flow on long, crowded roads[END_REF][START_REF] Richards | Shock waves on the highway[END_REF], for which numerical schemes have been performed since decades [START_REF] Daganzo | The cell transmission model: A dynamic representation of highway traffic consistent with the hydrodynamic theory[END_REF][START_REF] Godunov | A Difference Scheme for Numerical Solution of Discontinuous Solution of Hydrodynamic Equations[END_REF][START_REF] Lebacque | The Godunov scheme and what it means for first order traffic flow models[END_REF]. In the Godunov scheme [START_REF] Lebacque | The Godunov scheme and what it means for first order traffic flow models[END_REF], as well as in the cell transmission model (CTM) [START_REF] Daganzo | The cell transmission model: A dynamic representation of highway traffic consistent with the hydrodynamic theory[END_REF], traffic demand and supply functions are defined and used.

The demand-supply framework provides a comprehensive foundation for the LWR first order node models. Flow interactions in these models result from limited inflow capacities of the downstream links. Recently, in [START_REF] Tampere | Link transmission model: an efficient dynamic network loading algorithm with realistic node and link behaviour[END_REF] framework has been supplemented with richer features such as conflicts within the node. In [START_REF] Osorio | Mitigating Network Congestion: Analytical Models, Optimization Methods and their Applications[END_REF], a dynamic network loading model that yields queue length distributions was presented. This model is a discretized, stochastic instance of the kinematic wave model (KWM). In [START_REF] Boel | A compositional stochastic model for real time freeway traffic simulation[END_REF], the compositional stochastic model extends the cell transmission model [START_REF] Daganzo | The cell transmission model: A dynamic representation of highway traffic consistent with the hydrodynamic theory[END_REF] by defining demand and supply functions explicitly as random variables, and describing how speed evolves dynamically in each link of the road network. Several simulation models based on queueing theory have been developed, but few studies have explored the potential of the queueing theory framework to develop analytical traffic models. The development of analytical, differentiable, and computationally tractable probabilistic traffic models is of wide interest for traffic management.

The most common approach is the development of analytical stationary models [START_REF] Osorio | Mitigating Network Congestion: Analytical Models, Optimization Methods and their Applications[END_REF]. A review of stationary queueing models for highway traffic and exact analytical stationary queueing models of unsignalized intersections is given in deferent literatures [START_REF] Heidemann | Queue length and delay distributions at traffic signals[END_REF][START_REF] Van Woensel | Vehicle routing with dynamic travel times: A queueing approach[END_REF][START_REF] Vandaele | A queueing based traffic flow model[END_REF]. In [START_REF] Balsamo | On the cycle time distribution in a two-stage cyclic network with blocking[END_REF][START_REF] Guerrouahane | Urban congestion: Arrangement of Aamriw Intersection in Bejaia's City. In: Business process management: Process-Aware Logistics Systems[END_REF][START_REF] Heidemann | Queueing at unsignalized intersections[END_REF], the authors contributed to the study of signalized intersections and presented a unifying approach to both signalized and unsignalized intersections. These approaches resort to infinite capacity queues, and thus fail to account for the occurrence of breakdown and their effects on upstream links. Modeling and calculating traffic flow breakdown probability remains an important issue when analyzing the stability and reliability of transportation system [START_REF] Brilon | Reliability of freeway traffic flow: a stochastic concept of capacity[END_REF][START_REF] Wang | Calculation of traffic flow breakdown probability to optimize 405 link throughput[END_REF].

Finite capacity queueing theory imposes a finite upper bound on the length of a queue. This allows to account for finite link lengths, which enables the modeling and analysis of breakdowns.

Finite capacity queueing network (FCQN) model are of interest for a variety of applications such as the study of hospital patient flow, manufacturing networks, software architecture networks, circulation systems, prison networks [START_REF] Cheah | Generalized M/G/C/C state dependent queuing models and pedestrian traffic flows[END_REF], etc. The methods in [START_REF] Bedell | Topological arrangements of m/g/c/k, m/g/c/c queues in transportation and material handling systems[END_REF][START_REF] Cheah | Generalized M/G/C/C state dependent queuing models and pedestrian traffic flows[END_REF][START_REF] Jain | Modeling vehicular traffic flow using M/G/C/C state dependent queueing models[END_REF] resort to finite capacity queueing theory and derive stationary performance measures. The stationary distribution of finite capacity queueing network exist only for networks with two or three queues with specific topologies [START_REF] Grassman | An analytical solution for a tandem queue with blocking[END_REF][START_REF] Langaris | On the waiting time of a two-stage queueing system with blocking[END_REF][START_REF] Latouche | Efficient algorithmic solutions to exponential tandem queues with blocking[END_REF]. An analytic queueing network model that preserves the finite capacity for two queues, under a set of service rate scenarios proposed in [START_REF] Osorio | An analytic finite capacity queueing network model capturing the propagation of congestion and blocking[END_REF].

For more general networks, approximation methods are used to evaluate the stationary distributions, and the General Expansion Method (GEM) was developed [START_REF] Kerbache | The generalized expansion method for open finite queueing networks[END_REF][START_REF] Kerbache | Asymptotic behavior of the expansion method for open finite queueing networks[END_REF]. The GEM characterized by an artificial holding node, which is added and preceded each finite queue in the network in order to register all blocked cars caused by the downstream section. The interested reader may check details in [START_REF] Kerbache | Asymptotic behavior of the expansion method for open finite queueing networks[END_REF]. In [START_REF] Cruza | Approximate analysis of M/G/c/c state-dependent queueing networks[END_REF], the authors describe a methodology for approximate analysis of open state dependent M/G/c/c queueing networks, and a system of two queues in tandem topology was analyzed. The evacuation problem was analyzed using M/G/c/c state dependent queuing networks in [START_REF] Cruza | Service and capacity allocation in M/G/c/c state-dependent queueing networks[END_REF] when an algorithm was proposed to optimize the stairwell case and increase evacuation times towards the upper stories. In [START_REF] Guerrouahane | A queuing model for road traffic simulation[END_REF], the authors present another version of M/G/c/c state dependent queuing model, where a triangular fundamental diagram is considered, which leads to apply the demand and supply functions in order to analyze a system of two queues in tandem topology.

Review on the M/G/c/c state dependent queuing model

In this section, we present the M/G/c/c state dependent queuing model [START_REF] Cheah | Generalized M/G/C/C state dependent queuing models and pedestrian traffic flows[END_REF][START_REF] Jain | Modeling vehicular traffic flow using M/G/C/C state dependent queueing models[END_REF]. A link of a road network is modeled with c servers set in parallel, where c is the maximum number of cars that can move on the road (density-like). The car-speed is assumed to be dependent on the number of cars n on the road, according to a non-increasing density-speed relationship. Two cases of speed are considered, linear and exponential. In the linear case, we have

v n = v 1 c -n + 1 c , (1)
where v i is the speed corresponding to i cars moving on the road, and v 1 is the free flow speed.

In the exponential case, we have

v n = v 1 exp - n -1 β γ , (2)
in which β and γ are shape and scale parameters respectively.

β = a-1 [ln(v1/va)] 1/γ = b-1 [ln(v1/v b )] 1/γ . γ = ln[ ln(va/v1) ln(v b /v1) ]/ ln( a-1 b-1 ).
The values a and b are arbitrary points, used to adjust the exponential curve [START_REF] Cheah | Generalized M/G/C/C state dependent queuing models and pedestrian traffic flows[END_REF][START_REF] Jain | Modeling vehicular traffic flow using M/G/C/C state dependent queueing models[END_REF]. The arrival process of cars into the link is assumed to be Poisson with rate λ, while the service rate of the c servers depend on the number n of cars on the road. A normalized service rate f (n) is considered,

and is taken f (n) = v n /v 1 ≤ 1. In the linear case, we have f (n) = (c -n + 1)/c. In the exponential case, we have f (n) = exp[-((n -1)/β) γ ].
We notice here that v 1 is the speed corresponding to one car in the road (ie. the free speed).

The stationary probability distribution P n = P rob (N = n) of the number of cars N in the M/G/c/c state dependent model have been developed and shown in [START_REF] Cheah | Generalized M/G/C/C state dependent queuing models and pedestrian traffic flows[END_REF] to be stochastic equivalent to M/M/c/c queueing model. Therefore, these probabilities can be written as follows.

P n = (λL/v 1 ) n n i=1 if (i) P 0 , P 0 = 1 + c n=1 (λL/v 1 ) n n i=1 if (i) -1 , n = 1, ..., c. ( 3
)
where L is the length of the road section.

From P n , other important performance measures can be easily derived.

1. The blocking probability : In the following section, we rewrite the model presented in this section, by considering a car density-flow relationship rather than a density-speed one. This reformulation permits us to consider demand and supply functions which model limit conditions for car-traffic, and by that, to model two road sections in tandem, in Section 4.

P c = P 0 (λL/v 1 ) c / c i=1 if (i). 2. The throughput : θ = λ(1 -P c ).

Reformulation of the M/G/c/c state dependent model

In this section, we first reformulate the M/G/c/c state dependent model of Jain and Smith, by considering car-flows rather than car-speeds. Indeed, the linear case of that model considers a linear relationship of the speed as a function of the car-density. This is equivalent to considering a quadratic relationship of the car-flow as a function of the car-density; see Figure 1. It is easy to check that this quadratic relationship is written as follows.

q n = q max 1 - c -2n + 1 c + 1 2 . (4)
Indeed, one can for example verify that parting from (4), we retrieve (1)

v n v 1 := q n /ρ n q 1 /ρ 1 = c -n + 1 c ,
where ρ n = n/L. The stationary probabilities (3) are then rewritten as follows.

P n = (λ/q max ) n n i=1 ig(i) P 0 , P 0 = 1 + c n=1 (λ/q max ) n n i=1 ig(i) -1 , n = 1, ..., c. (5)
where

g(i) = q i /q max i .
The objective of working with flows rather than speeds here is to consider the demand and supply functions which we will use in the following sections, for the model of two road-sections in tandem. From ( 1) and ( 4), the relationship between the free speed v 1 and the maximum car-flow q max is given as follows.

q max = v ( c+1 2 ) ρ ( c+1 2 ) = v 1 Lc c + 1 2 2 . ( 6
)
The demand ∆ n and the supply Σ n functions are given as follows.

∆ n =      q n if 0 ≤ n ≤ c+1 2 , q max if c+1 2 < n ≤ c + 1. ( 7
) Σ n =      q max if 0 ≤ n ≤ c+1 2 , q n if c+1 2 < n ≤ c + 1. (8)
Demand and supply diagrams are shown in Figure 2, where the parameters of Table 1 are considered. In the following section, we consider three configuration models of a road section: open, constrained and closed road section. We will explain the role of each model, and tell how these models will be used for the model of two sections in tandem.

Open, constrained and closed road sections

We distinguish here three road section systems.

• An open road section is a road section where the traffic out-flow from the section is only constrained by the traffic demand of the section, given in function of the number of cars in the section. It is equivalent to the traffic system presented above in Section 3.1, where the traffic fundamental diagram is restrained to only its traffic demand part (ie with infinite traffic supply). In such a road section, which we index by i, if we denote by ∆ i and Σ i the traffic demand and supply of the section (induced by the car-density of the section) respectively, and q out the outflow from the section, then we have (see Figure 3)

q out = ∆ i . (9)
• A constrained road section is a road section out flowing to another downstream section, and where the outflow of the considered road section is constrained by the traffic demand of that section, and by the traffic supply of the downstream section. If we index the downstream section by the index i + 1, denote by Σ i+1 the traffic supply of the downstream section, and consider the same notations used above, then we have (see Figure 3)

q out = min(∆ i , Σ i+1 ). ( 10
)
• A closed road section is the road section system presented above in Section 3.1, for which the outflow is given by the fundamental traffic diagram with both demand and supply parts, and where both the parts are constrained by the car-density of the section. Using the same notation as above, the out-flow from the section is given as follows (see Figure 3)

q out = min(∆ i , Σ i ). ( 11
)
Figure 3: open, constrained and closed road section systems, respectively from left to right sides.

Basing on the three systems presented above, we present in the following section, a model of two road sections in tandem. It is a kind of a constrained section where the downstream section is a closed one.

Two road sections in tandem

We propose in this section a state-dependent M/G/c/c model for two road sections in tandem.

The whole system is a concatenation of two road sections: a M/G/c/c state dependent constrained section (section 1), with an M/G/c/c state dependent closed section (section 2); see Figure 4.

Since the downstream section (section 2) is a closed one, which corresponds to the traffic system presented in Section 3.1, the supply flow of section 2 is stochastic, and is given in function of the probability distribution of the number of cars in section 2. We assume quadratic flow-density fundamental diagrams for the two sections. The car-flow outgoing from section 1 and entering to section 2 (q 12 (n 1 , n 2 )) is given by the minimum between the traffic demand on section 1 and the traffic supply of section 2.

q 12 (n 1 , n 2 ) = min(∆ 1 (n 1 ), Σ 2 (n 2 )). ( 12
)
The car-flow outgoing from section 2, and also from the whole system is denoted by q 2 . The objective here is to determine the stationary probability distributions P (1) and P (2) of the number of cars in section 1 and section 2 respectively, as well as the stationary probability distribution P (1,2) of the couple (n 1 , n 2 ) of numbers of cars in sections 1 and 2 respectively.

We notice here that this cannot be calculated directly since both road sections influence each other. Indeed, P (2) depends on q 12 which depends on the traffic demand of section 1. Similarly, P (1) depends on the traffic supply of section 2, since section 1 is constrained by section 2. We propose below an iterative approach for the calculus of such probabilities.

The model

The procedure we propose here for the determination of P (1) , P (2) and P (1,2) consists in solving an implicit system given by an algebraic equation, in order to deal with the mutual dependence between sections 1 and 2. We denote by θ the average outflow from section 1 (average of q 12 ), which is also the average inflow to section 2; and by δ the average outflow from section 2 (average of q 2 ), which is the average outflow of the whole system.

We notice that if θ is known, then the probability distributions P (1) , P (2) and P (1,2) can be obtained in function of θ. Indeed, section 2 being a M/G/c/c state dependent closed section with an average arrival flow θ), P (2) can be obtained in function of θ. After that, section 1 being constrained by the supply of section 2 (with known P (2) ), P (1,2) and then P (1) can be obtained in function of P (2) and thus in function of θ. Moreover, from P (1) we can obtain q 12 in function of θ, and then the expectation of q 12 gives θ in function of itself.

From the latter remark, we propose the following iterative algorithm for the calculus of θ and of the probabilities P (1) , P (2) and P (1,2) .

Step 0. Initialize θ = θ 0 .

Step k (for k ≥ 1).

(1) P (2) is obtained in function of θ = θ k-1 .

Section 2 is a M/G/c/c state dependent closed section, with an average arrival flow θ, which is unknown. According to (5), the stationary probability distribution of the number n 2 of cars on section 2 is given, in function of θ, as follows.

P

(2)

n2 (θ) = (θ/qmax 2 ) n 2 n 2 i=1 ig2(i) P (2) 0 (θ), n 2 = 1, ..., c 2 . P (2) 0 (θ) = 1 + c2 n2=1 (θ/qmax 2 ) n 2 n 2 i=1 ig2(i) -1 . ( 13
)
where g 2 (i) = q 2 (i)/q max2 i .

(2) P (1,2) and then P (1) are obtained from λ and P (2) , and thus in function of θ = θ k-1 .

Section 1 is constrained by the supply of section 2. As the normalized service rate g 1 (i 1 , i 2 )

of section 1 depends on the number of cars on section 2, which itself depends on θ, the stationary probability distribution P (1) of the number of cars in section 1, is also given in function θ. The normalized service rate g 1 (i 1 , i 2 ) of section 1 is given as follows.

g 1 (i 1 , i 2 ) = q 12 /q max1 i 1 = min(∆ 1 (i 1 ), Σ 2 (i 2 ))/q max1 i 1 . (14)
In order to write P (1) , let us first write the stationary probability distribution of the number of cars on section 1, conditioned by the number of cars on section 2, which we denote by ) , and which is independent of θ.

P (1|2
P (1|2) (n1|n2) (λ) = P rob (N 1 = n 1 | N 2 = n 2 ) = (λ/qmax 1 ) n 1 n 1 i=1 ig1(i1,n2) P (1|2) (0|n2) (λ), P (1|2) (0|n2) (λ) = P rob (N 1 = 0 | N 2 = n 2 ) = 1 + c1 n1=1 (λ/qmax 1 ) n 1 n 1 i=1 ig1(i1,n2) -1 . ( 15
)
Thus, the stationary probability distribution P (1) of the number of cars in section 1, which depends on λ and θ, is given as follows.

P

(1)

n1 (λ, θ) = c2 n2=1 P (1|2) (n1|n2) (λ)P (2) n2 (θ), P (1) 0 (λ, θ) = c2 n2=1 P (1|2) (0|n2) (λ)P (2) n2 (θ). ( 16
)
(3) q 12 is obtained from P (1) , and in function of θ = θ k , and finally θ k+1 = E(q 12 (θ k )).

The average outflow from section 1, θ, is given in function of P (1) as follows.

θ k = λ 1 -P (1) c1 (λ, θ k-1 ) . ( 17
)
The procedure consists then in solving the following implicit equation on the scalar θ.

θ = λ 1 -P (1) c1 (λ, θ) . ( 18
)
The solution of that equation, if it exists, and if it is unique, gives the value of the asymptotic average flow passing from section 1 to section 2, and by that, the stationary probability distributions P (2) , P (1|2) and P (1) . The stationary probability distribution P (1,2) can be easily deduced from P (1|2) and P (2) . We notice here that equation ( 18) is a fixed-point-like equation.

In the following section, we give some results on the fixed-point equation solving.

Fixed-point equation solving

We use the following notations.

• h(θ) = λ 1 -P

c1 (λ, θ) ,

• e(θ) = h(θ) -θ.

Equation ( 18) is written θ = h(θ), and it is equivalent to e(θ) = 0.

Below, we give some results on the resolution of equation [START_REF] Kerbache | The generalized expansion method for open finite queueing networks[END_REF].

Theorem 4.1. A solution for equation [START_REF] Kerbache | The generalized expansion method for open finite queueing networks[END_REF] exists and is unique.

Proof. See AppendixA.

The following result gives a condition on the couple (λ, θ), under which the sequence θ k , k ∈ N defined by fixed point iteration (17

) (i.e. θ k = h(θ k-1 )) converges for every initial value θ 0 ∈ [0, λ].
Theorem 4.2. If ∃ε > 0 such that ε < θ/λ, and if

c2 n2=1 P (1|2) c1|n2 (λ)P (2) n2 (θ) n 2 - c2 k2=1 k 2 P (2) k2 (θ) ≤ ε,
then the fixed point iteration converges to the unique fixed point of the fixed point equation.

Proof. See AppendixB.

We do not have other explicit formulas than the condition of Theorem 4.2. We know that for low values of λ, we have -1 < d h(θ)/dθ ≤ 0, ∀θ ∈ [0, λ], and the iteration of the fixed point equation converges, independently of the initial value of θ, to the unique fixed point. However, we also know that for high values of λ, there exists an interval (θ 1 , θ 2 ) where d h(θ)/dθ < -1. In such cases, the fixed point is unstable. Nevertheless, the sequence θ k , k ∈ N oscillates between two adherence values h(0) = λ and h(λ), giving (λ + h(λ))/2 as the asymptotic average value of θ, see Figures 5 and6.

In Figure 5, we give in blue color the function h(θ) for different values of λ. The red line is the first bisector. The fixed point verifying h(θ) = θ is then the intersection of the blue curve with the red one. We see in this figure that the derivative of h(θ) with respect to θ on the fixed point is decreasing with λ, starting from zero. Indeed, for low values of λ, we have dh(θ)/θ = 0. As λ increases, dh(θ)/θ decreases. As explained above, while dh(θ)/θ > -1, we know that the fixed point is stable. However, once dh(θ)/θ > -1, the fixed point is unstable.

Figure 6 illustrates the two cases of stable and unstable fixed points, depending on the value of λ. In the first case (left side of the figure), we have λ = 2000 veh/h; see also Figure 5. In this case, the fixed point is stable, and the iteration converges to it. In the second case (right side of Figure 6), we have λ = 3000 veh/h; see also Figure 5. In this case, the fixed point is unstable, and the iteration oscillates from the two values h(0) = λ and h(λ).

In the following section, we explain how to compute the stationary probability distributions in function of the average flow θ, calculated by the fixed point iteration.

The stationary probability distributions

Once θ is obtained, the whole stationary regime of the system of two road sections in tandem is determined. Indeed, the stationary probability distributions P (1) , P (2) and P (1|2) are given by ( 16), ( 13) and ( 15) respectively. The stationary joint probability distribution P (1,2) of the couple (n 1 , n 2 ) of the number of cars in sections 1 and 2 respectively, is then easily deduced.

P (1,2) (n1,n2) = P (1|2) n1|n2 P (2) n2 , ∀0 ≤ n 1 ≤ c 1 , 0 ≤ n 2 ≤ c 2 .
In the following, we illustrate those probability distributions for given parameters of the system. On the right side: λ = 3000 veh/h and the iteration oscillates between two values h(0) = λ and h(λ).

Table 1 gives the fixed parameters for the illustrations, where L, v 1 , ρ j and q max denote respectively section length, free speed, jam-density and maximum car-flow. Section i L (km) v 1 (km/h) ρ j (veh/km) q max (veh/h) Let us notice that ρ cr = ρ j /2 (quadratic fundamental diagram), and c = Lρ j .

ρ cr and c denote respectively critical car-density and road section capacity in term of maximum number of cars.

Figure 7 compares the stationary distribution probability of the two following cases.

• One closed road section (Jain and Smith model), with parameters of section 2 in Table 1.

(Blue color in Figure 7).

• One constrained road section, with parameters of section 1 in Table 1. The section is assumed to be constrained by a closed road section whose parameters are those of section 2 in Table 1. (Red color in Figure 7).

The average car inflow λ is varied from one illustration to another in Figure 7.

We notice here that the constrained road has a maximum flow capacity of 5000 veh/h, but it is constrained by a closed road with a maximum flow capacity of 2500 veh/h. We remark from Figure 7, that the constrained section is more likely to be congested than the closed one, even though a priori they are both constrained by a maximum flow capacity of 2500 veh/h. Figure 8 gives the stationary probability distributions P (1,2) of the couple (n 1 , n 2 ) of numbers determined.

δ = θ 1 -P (2) c2 (θ) .

Figure 9 displays for an increasing arrival rate, λ, the throughput through sections 1 and 2 of the whole system of two road sections in tandem. The parameters of each road section are those given in Table 1. We remark from Figure 9, that throughput through the sections 1 and 2 is equal to the arrival rate λ up to roughly 2200 veh/h. This comes directly from the fact that the capacities are not restrictive. However, the trend changes at about 2300 veh/h (well below 2500 veh/h), and the throughput does not increase anymore.

Performance measures of two sections in tandem topology

We consider the system of two sections in tandem topology presented in Figure 4, with parameters of Table 1. The bottleneck in section 2 is most difficult to be analyzed because of the mutual dependence between the two sections set in tandem. In the next, we compare the throughput and the expected service time of our method with the method of Kerbache and Smith [START_REF] Kerbache | Asymptotic behavior of the expansion method for open finite queueing networks[END_REF]. We remark from Figure 10, that when the arrival rate λ is low, our throughputs (θ of section 1 and σ of section 2) are similar to the throughputs of the expansion method of Kerbache and Smith. In this case, the arrival rate is very light and easily accepted by section 2 without any blocking. When the arrival rate λ is large, our throughputs is low as compared to the throughputs of M/G/c/c state dependent queueing networks, because the constrained section (section 1 of our model ) is more likely to be congested than the open section (section 1 in the expansion method of Kerbache and Smith). One can easily show that dP We have P (1|2) c1|n2 (λ) is increasing with respect to n 2 ; see [START_REF] Guerrouahane | A queuing model for road traffic simulation[END_REF] where S is given by (A.1) in the proof of Theorem 4.1.

The condition of Theorem 4.2 can be written ∃0 ≤ ε < θ/λ such that S ≤ ε. Therefore, if this condition is satisfied, then ∃0 ≤ η < 1 such that d h(θ)/dθ > -1.

Then since we have already shown in the proof of Theorem 4.1 ( AppendixA) that s ≥ 0, and by that, d h(θ)/dθ ≤ 0, then, under the condition of Theorem 4.2, we have 0 ≤ d h(θ)/dθ < 1.

Hence the fixed point iteration converges to the unique fixed point of the fixed point equation.

3 .

 3 The expected number of cars in the section : N = c n=1 nP n . 4. The expected service time : W = N /θ.

Figure 1 :

 1 Figure 1: In the left side, the car-density -speed relationship. In the right side, the corresponding car-densityflow relationship.

Figure 2 :

 2 Figure 2: Demand diagram (left). Supply diagram (right).

Figure 4 :

 4 Figure 4: The system of two sections in tandem.

Figure 5 :

 5 Figure 5: On the x-axis: θ. On the y-axis: in blue the function h(θ) for different values of λ: 1000, 2000 and 3000; in red: θ.

Figure 6 :

 6 Figure 6: Fixed point iteration. On the left side: λ = 2000 veh/h and the iteration converges to the fixed point.

Figure 7 :

 7 Figure 7: Stationary probability distributions. λ = 1000 veh/h, 2000 veh/h and 3000 veh/h respectively from left to right sides.

Figure 9 :

 9 Figure 9: Throughputs θ in red color and δ in blue color in function of the average arrival rate λ. The two road sections are set in tandem.

Figure 10 compares

 10 Figure 10 compares the throughputs of sections 1 and 2 of our method with the expansion method of Kerbache and Smith (open M/G/c/c state dependent queueing networks) [19].

Figure 10 :

 10 Figure 10: Comparison of the throughputs. In left, section 1 (θ). In right, section 2 (σ). In red color, our model of two sections in tandem. In blue color, open M/G/c/c state dependent queueing networks in tandem

Figure 11 : 1 1.

 111 Figure 11: Comparison of the expected service time. In left, section 1. In right, section 2. In red color, our model of two sections in tandem. In blue color, open M/G/c/c state dependent queueing networks in tandem.

  n2 (θ) (n 2 -n2 (θ)) , where n2 (θ) = E P (2) (n 2 ) = c1|n2 (λ)P (2) n2 (θ)(n 2 -n2 (θ)) ≥ 0. (A.1)

2 Following

 2 n2 (θ)(n 2 -n2 (θ)) = 0.Hence d e(θ)/dθ < 0, and the fixed point is unique.AppendixB. Proof of Theorem 4.

Table 1 :

 1 Parameters for sections 1 and 2.

  and[START_REF] Godunov | A Difference Scheme for Numerical Solution of Discontinuous Solution of Hydrodynamic Equations[END_REF].Let n * 2 = n * 2 (θ) be defined as follows n * 2 = max{n 2 ≤ c 2 , n 2 -n2 (θ) < 0}. Then

	S =	n * 2 n2=1 P c1|n2 (λ)P (1|2) n2 (θ)(n 2 -n2 (θ)) + (2)	c2 n2=n * 2	P c1|n2 (λ)P (1|2) n2 (θ)(n 2 -n2 (θ)) (2)
	≥	n * 2 n2=1 P c1|n * (1|2) 2	(λ)P	(2) n2 (θ)(n 2 -n2 (θ)) +	c2 n2=n * 2	P c1|n * (1|2) 2	(λ)P

Acknowledgements

The authors wish to thank the editor-in-chief, and the anonymous reviewers whose constructive suggestions helped improve this paper.

of cars in sections 1 and 2 respectively. The average arrival rate λ is varied from one illustration to another. Parameters of Table 1 are used. λ takes the values of 1000 veh/h, 2000 veh/h, 2500 veh/h and 3000 veh/h. In Figure 9, we give the throughputs of sections 1 and 2 in the case where the two sections are 265 set in tandem. The throughput θ of section 1 is given by ( 18), and it is the solution of the fixed point iteration. The throughput δ (see 4) is computed by the same way (Little's law), once θ is


Nicolas Richer
email: nicolas.richer@inria.fr

Marc Shapiro
email: marc.shapiro@inria.fr

The Memory Behavior of the WWW, or The WWW Considered as a Persistent Store

This paper presents the performance evaluation of five memory allocation strategies for the PerDiS Persistent Distributed Object store in the context of allocating two different web sites in the store. The evaluation was conducted using (i) a web gathering tool, to log the web objects graph, and (ii) a PerDiS memory simulator that implements the different allocation strategies. Our results show that for all the strategies and parameters we have evaluated, reference and cycle locality are quiet poor. The best policy seems to be first sequential fits. Results are linear with the size of the garbage collection Unit (a bunch). There is no clear optimum, but 64K to 128K appear to be good choices.

Introduction

PerDiS [FSB + 98] is a new technology for sharing information over the Internet: Its abstraction is a Persistent Distributed Object Store. PerDiS provide a simple, efficient and safe abstraction to the application programmer. To attain this goal, it is necessary to understand the way target applications use the persistent store and how the different mechanisms and heuristics perform. This study is the target of task T.C 3 of the PerDiS project. This paper presents the results we have obtained.

The PerDiS persistent store is logically divided into clusters. A cluster is the naming and security unit visible by the programmer. A cluster is attached to a "home" site1 but can be accessed from any site. From the garbage collection point of view, cluster is further subdivided into bunches, i.e. garbage collection Units. The Garbage Collector always runs on whole bunch and this unit will be completely replicated at one site in order for the GC to run on2 . This means also that bunches will be stored in a contiguous area in memory. A reference inside a bunch is cheaper than between two bunches (an inter-bunch reference). The latter needs using stubs and scions. The fewer references will be inter-bunch, the better the PerDiS system will perform.

What Are Garbage Collection Components

A Garbage Collection components is a set of objects reclaimed by the garbage collector all at the same time. This could be a single object or several objects link together in a way that they become unreachable all at the same time. Typically, this can be a set of objects with circular references between them. In this context, Strongly Connected component is an approximation for Garbage Collection component. Rigorously, Garbage Collection components are Strongly Connected component plus all the objects reachable only from this components, but we don't make the difference in this study, because, unfortunately, we are not able to extract real Garbage Collection components from an object graph yet. This approximation may grow up the overall proportion of objects and bytes included in Garbage Collection components. Studying Strongly Connected component provide only minimum proportions, and we don't currently know the maximums.

Note also that Garbage Collection components are often called cycles in this paper because it's shorter.

The PerDiS Garbage Collector

The PerDiS Garbage Collector use a reference counting algorithm to handle inter-bunches references, this to avoid costly distributed Garbage Collection Algorithms. In consequences, some garbage could not be reclaimed in some situation. This is the case of Garbage Collection components composed by several objects spread between different bunches. This kind of garbage could be reclaimed on the of all the bunch is containing the objects were run located at the same site. This is, unfortunately, the drawback of using reference counting.

The assumption we have made during the design of the PerDiS Garbage Collector is that such kind of unreclaimable components are sufficiently rare to be forgotten and we don't put any kind of global tracing collector for them. Of course, this assumption should be verified in practice and this is precisely why we are interested by Garbage Collection components in this study. Depending of our experimental results, the need for a global tracing collector mechanism will be reconsidered. The important point here is the fewer cycles are inter-bunches, the less garbage will remain unreclaimable. This suggest that object placement strategies (i.e. allocation algorithms) should minimize interbunch Garbage Collection components and inter-bunch references. A secondary goal will be to minimize also the number of scions and store fragmentation.

In the current PerDiS implementation, the initial allocator clustering is permanent, because PerDiS support the uncooperative C++ language that does not provide natively all the informations required to perform object relocation. In the future, we plan to implement object relocation in PerDiS using type information extracted by typedesc [START_REF] Salcianu | Extraction et utilisation des informations de type pour le support des objets répartis[END_REF], a tool we have specifically implemented for that.

A complete description of the PerDiS Garbage Collection Algorithm is available in [FS94,FS96]. [START_REF] Blondel | Implementing garbage collection in the perdis system[END_REF] describe more deeply the implementation.

Analysis Methodology

Our methodology is to record the persistent object graph during application runs, using a log mechanism. The log subsequently supports simulation of different strategies and parameters. We focus primarily on evaluating memory allocation and clustering strategies. Many studies of memory allocation and clustering strategies already exist [WJNB95,WJ98,ZG92a,ZG92b,DDZ93], but none has been conducted in the context of a persistent distributed garbage collected memory3 . This is probably related to the very few number of existing persistent store, but even for those that exists, most of them rely on manual memory deallocation. For example, one of the most advanced distributed persistent stores, ObjectStore [START_REF] Lamb | The ObjectStore database system[END_REF] is based on manual persistence, in contrast with persistence by reachability [ABC + 83] using a distributed garbage collector as in PerDiS.

Why Study the Web ?

Wilson in [START_REF] Wilson | Dynamic storage allocation: A survey and critical review[END_REF] demonstrates the low representativity of synthetically generated allocation requests. Therefore, we chose to evaluate the memory allocation and clustering strategies using inputs from real applications. Consequently, we need some significant persistent applications for our evaluation. Unfortunately, applications that use persistent objects store are rare, and a few that exists are not easily accessible. Furthermore, PerDiS is designed to provide easy access to persistent data over a geographically widely-distributed network. We need applications running in such a large-scale context. The Web application has attracted our attention because it is easily accessible and widely distributed. Hence our decision was to study the behavior of PerDiS as a distributed storage medium for web sites.

Practically, we have not actually stored the full web sites in the PerDiS memory, although it is perfectly feasible to do so4 . Instead, we have used the PerDiS memory simulator. This simulator has been designed specifically to reproduce the PerDiS memory behavior against several allocation strategies and parameters.

Gathering the Web Object Graph

We briefly present in this section how we gather a graph of objects from a web server in order to study it. The basic gathering algorithm is a depth-first top-down traversal implemented using a stack:

1. Push some root document URL on the fetch stack. 2. Pop an URL from the fetch stack, retrieve the corresponding document, and parse it to extract the URL it contains. 3. Push all the contained URLs that are in scope on to the fetch stack. 4. Return to step 2 until fetch stack becomes empty.

Starting from an existing mirroring tool seemed a reasonable approach. We chose the w3mir5 all purpose HTTP copying tool because its source code is freely available and we have good experience with it.

The web objects graph is recorded in the generic log format version 2 of our generic log handling library6 . Since w3mir is written in PERL7 , we created a PERL interface for the generic log library.

We first integrated the recording of the web objects and references to w3mir by minimizing the modifications in the mirror algorithm in less than three days. The result was not acceptable as is because many processes and fetch was duplicated, so in a second step we have modified the w3mir algorithm to remove this.

The following problems, which are inherent to the World Wide Web, should be noted:

-A document's "last modified date" is often not correctly returned by web servers. When this occurs, we take the current date as the "last modified date".

-Recording the evolution of the Web Objects Graph is difficult in practice. Since there is no reliable protocol for change notification, we need to keep a local full copy of the web site. Furthermore, many web sites are modified rarely; therefore measurements would have to be repeated over very long periods (maybe 6 months or more) in order to see significant modifications. Instead, the results presented in this paper concern a single snapshot of each studied web site. -The graph that we obtain, using the mirroring method, is different from the real Web graph. Several kinds of document (CGI scripts, Java applets, Netscape Java-script, etc) could not be handled and furthermore, since documents of this types are sometimes used to provide the menu to navigate through the entire web site, a large part of this kind of web sites could not be visible. As far as we know, all existing indexing engines has the same problem with this kind of documents. Nevertheless our partial graph should be sufficient for evaluation purposes and we have to take care of this problem when we choose the web sites to study.

Characteristics of the Web Sites Studied

This initial study involves the two web sites: http:// www.perdis.esprit.ec.org/ and http://www-sor. inria.fr/. This choice was motivated by three criteria:

1. Network connection quality. Since we need to fetch the full web site contents each time we gather the graph, a very fast connection to the servers is crucial. 2. Prior knowledge. Since there are several kinds of documents that our web gathering tool can't handle, having some previous knowledge of the web site content should avoid choosing, for instance, a site where most of the document cannot bet considered because they are all only accessible from a Java applet menu. 3. Total Size. To be able to perform our simulations sufficient memory resources should be available on the simulation machine. In our current setup, this limits the total web site to approximatively 1 Gigabyte.

All the relevant characteristics of the two studied sites are presented in the next two sections.

3.1 Site 1: http://www.perdis.esprit.ec.org/

The PerDiS web site was studied on Thursday September 23 1999. At this date, it contained 3302 objects, with 31408 valid references8 for a total size of 109 Mbytes.

The smallest object size is 0 byte and the largest 10 Mbytes. The median is 2.4 Kbytes, for an arithmetic mean of 33 Kbytes, and a variation coefficient of 9.7. We present the size frequency distribution in Fig. 1. Objects in the PerDiS web site are aged between 6 seconds old to a little more than 3 years. The median age is 1.5 years, for an arithmetic mean of 1.3 years and a variation coefficient of 0.59. We present the age frequency distribution in Fig. 2. The average density of references 9 is 9.5 per object and 0.28 per Kbyte.

There are 22 Strongly Connected components that contain 2284 objects (69.2% of total) for a total size of 15 Mbytes (13.5% of total). The smallest S.C component contains 3 objects (7 Kbytes) and the largest 1758 objects (13.6 Mbytes) 10 . Figure 3 shows the size frequency, in number of objects, of strongly connected components. This figure appear quite uniform because there is only 22 components for 19 size ranges, so there is only one component in each size range, except for the seventh bar where there is two and the first bar where there is three. Figure 4 shows strongly connected size frequency in bytes. Objects in the SOR web site are aged from 10 seconds to 4 years. Median age is 0.9 years, the arithmetic mean 0.8 years for a variation coefficient of 0.67. We present the age frequency distribution in Fig. 6.

The average density of references is 25.2 per object, and 0.78 per Kbyte.

There are 89 Strongly Connected components, containing 2819 objects (31.9% of total) for a total size of 40 Mbytes (14.56% of total). The smallest S.C component contains 2 objects (1 Kbytes) and the largest 381 The PerDiS store simulator has been originally implemented to take a graph log, sort the memory allocation to simulate by document last modifications time, replay the allocations using the simulated allocation policy and finally generate a new log with all the old object locations in the heap replaced by the simulated new ones. Sorting document by "last modifications time" introduced an error in the allocation replaying order because "last modifications time" returned by the web server is not reliable for every documents. Documents with unknown real modification dates exist and in this case, most of the web server return the current date as "last modifications time". To put a bound on the error introduced, we have measured the proportion of documents that have their "last modifications time" younger than the time the snapshot gathering begin. 4% of the documents are in this case in the PerDiS web site and 16% in the SOR web site. Other measurements on several other web sites shows a very high variability (2,3% to 100%) of this proportion.

The PerDiS store simulator is also able to replay the memory allocation in log order. According to the gathering algorithm we currently use (top-down depthfirst traversal), log is ordered top-down depth-first.

PerDiS Memory Allocation Strategies

The current PerDiS API has applications explicitly place a specific object in a specific cluster. A cluster allocates an object in one of two kinds of bunches, depending on size. Under a certain threshold, it is allocated in a "standard" bunch of fixed size. Any layer object in a "special" bunch, containing only this object. This structure is based on the assumption that big objects are rare. This seems to be confirmed in our measurements (Fig. 1 for site 1 and Fig. 5 for site 2). In our simulations, the maximum proportion of large objects remain under 8% (with standard bunches of 32K). Bunches are referenced in two doubly linked list, one for the standard bunches and one for the special ones. In the two following sections, we compare different strategies to allocate inside standard bunches and to select the standard bunch to allocate. Since standard bunch have a fixed size, we evaluate the allocation strategies using seven typical bunch size: 32K, 64K, 128K, 256K, 512K, 1024K and 2048Kbytes.

Strategies for Allocation Inside Bunches

In our PerDiS memory simulator, five strategies to allocate an object inside a bunch are currently implemented.

The fixed size strategy allows only allocation of object of the same size (or of the same size class) in the bunch. The free list uses a bitmap that keeps track of allocated and free blocks. This strategy is used in the PerDiS memory simulator in conjunction with the segregated bunches selection (see Sect. 5.2).

The other four use an address-ordered free list with deferred coalescing of the free block. The free list is doubly linked. When an allocation request can not be successfully completed because there is no large enough free block, contiguous free blocks in memory are coalesced and the free list is scanned again. There are four strategies to search for a free block in the free list:

-first fit: Walk through the free list from the beginning to first large enough free block, and allocate there. -best fit: Walk through the whole list and allocate in the smallest large enough free block. -roving pointer: Walk through the free list from the position where the last allocated object was taken from the free list. -linear allocator: the same as roving pointer but never re-use the memory. This kind of allocator could be used only in conjunction with a copying garbage collection algorithm.

Strategies for Bunch Selection

The five strategies for selecting a standard bunch available in our simulator are all inspired by the strategies for allocating inside bunch:

-First available bunch: Bunches are stored in a list and allocation is done in the first satisfactory bunch. -Best available bunch: Bunches are stored in a list and allocation is done in the best satisfactory bunch.

-Last available bunch: Bunches are also stored in a list but it is scanned from the last bunch where an allocation has been successfully completed.

Allocation Simulations Using Significant Strategies

For the simulations presented in this section, five allocation strategies have been selected. They correspond to the five available bunches selection strategies. The inside bunch allocation strategy is not significant in this set of simulations because only one single snapshot is considered and, by the way, there is no memory deallocation.

In the rest of the paper, the five strategies will be referenced using the following names:

1. cluster first: allocate in the clusters using First available bunch strategy. 2. cluster best: allocate in the clusters using Best available bunch strategy. 3. cluster roving: allocate in the clusters using Last available bunch strategy. 4. cluster linear: allocate in the clusters using linear bunch strategy. 5. cluster segregated: allocate in the clusters using segregated bunch strategy.

Memory Allocation Simulations in Order of Last Modifications Date

In this section, the simulation results we present has been obtained using the five selected allocation strategies with data allocation ordered by last modifications date.

Site 1: http://www.perdis.esprit.ec.org/ Figure 9 shows the proportion of inter-bunch references for the five allocation strategies and for seven bunch sizes. Proportion of inter-bunch references is the percentage of all references that are to objects in a different bunch.

Clearly cluster segregated is the worse strategy from the

+ + + + + + + × × × × × × × ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ◊ ◊ ◊ ◊ ◊ ◊ ◊ 32K 64K 128K 256K 512K 1024K 2048K Ratio(%)
Bunch Size (KBytes)

+ + + + + + + × × × × × × × ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ◊ ◊ ◊ ◊ ◊ ◊ ◊ 32K 64K 128K 256K 512K 1024K 2048K Ratio(%)
Bunch Size (KBytes) Fig. 10. PerDiS: proportion of inter-bunches cycles point of view of reference locality but this is not a surprise. The best strategies from locality point of view (cluster linear or cluster roving, depending on bunch size) have proportion of inter-bunch references between 50%, for 2048K bunches, to 70%, for 32K ones, that is very high. The good locality results of the cluster roving policy should be taken with care, because there is no freeing in our simulations and unfortunately, the roving policy is known to strew new objects among the old ones whose neighbors have been freed. The inter-bunches cycles proportion is the percentage of cycles which span bunches. Looking at this proportion, in Fig. 10, it appear that they are not more encouraging. cluster segregated still give the worse results with 100% of inter-bunches cycles but the best strategy gives a proportion between 30% to 78% depends on bunch size. Figure 11 shows the number of scions, i.e. the number of objects that have incoming references from different bunches. This number is comparable to the number of objects for small bunches and go down by only 20% for large bunch and best allocation policy.

This signify that, even in the best case, 80% of the objects have incoming references from different bunch, that is a high proportion.

+ + + + + + + × × × × × × × ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ◊ ◊ ◊ ◊ ◊ ◊ ◊ 32K 64K 128K 256K 512K 1024K 2048K
Bunch Size (KBytes)

Number of scions Fig. 11. PerDiS: number of scions Finally, Fig. 12 gives an overview of memory fragmentation (internal and external combined) at the end of a snapshot simulation. This is the moment where the maximum of memory is allocated. Since there is no deallocation in our single snapshot, results about memory fragmentation are not significant, but they show that fragmentation increase with bunch size, as expected. They show also that policy known to be poor on fragmentation, the cluster segregated strategy [START_REF] Wilson | The memory fragmentation problem: Solved?[END_REF], give the worse fragmentation result, even for small standard bunch sizes. This last result need to be confirmed by other simulations using several snapshots, representing the evolution (including deallocation) of the web site.

+ + + + + + + × × × × × × × ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ◊ ◊ ◊ ◊ ◊ ◊ ◊ 32K 64K 128K 256K 512K 1024K 2048K
Bunch Size (KBytes) Ratio(%)

+ + + + + + + × × × × × × × ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ◊ ◊ ◊ ◊ ◊ ◊ ◊ 32K 64K 128K 256K 512K 1024K 2048K Ratio(%)
Bunch Size (KBytes)

+ + + + + + + × × × × × × × ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ◊ ◊ ◊ ◊ ◊ ◊ ◊ 32K 64K 128K 256K 512K 1024K 2048K
Ratio(%)

Bunch Size (KBytes)

Fig. 14. SOR: proportion of inter-bunches cycles

Site 2: http://www-sor.inria.fr/ The second set of simulations, (on the second studied web site) shows many similarities with results for Site 1. Figure 13 shows the proportion of inter-bunches references. Cluster segregated is still the worse strategy. The best proportion is between 30% to 79% for bunches respectively from 2048K to 32K. The inter-bunch cycles proportion, in Fig. 14, gives mostly the same results as for site 1, cluster segregated is the worse and best proportion vary between 80% for 32K bunches to 50% for 2048K ones.

Figure 15 show the number of scions. As for the PerDiS site, this number is comparable to the number of objects for small bunches, but go down more significantly (40%) for large bunch.

On the fragmentation front (Fig. 16), the tendency is almost the same as for site 1, except that the cluster linear strategy gives worse results than cluster first, cluster best or cluster roving. However, cluster segregated is still the worse.

+ + + + + + + × × × × × × × ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ◊ ◊ ◊ ◊ ◊ ◊ ◊ 32K 64K 128K 256K 512K 1024K 2048K Ratio(%)
Bunch Size (KBytes) Fig. 16. SOR: memory fragmentation

Memory Allocation Simulations in Depth-first Top-down Order

The simulation results presented here has been obtained using the same five selected allocation strategies as in Sect. 6.1 but with data allocation ordered by graph topology, in depth-first top-down order. For both PerDiS and SOR web site, we present only results about proportion of inter-bunch references and proportion of inter-bunch cycles as they are the most significant. Results about number of scions and fragmentation are omitted because they are almost similar to those presented in Sect. 6.1, using data allocation ordered by last modifications date and by the way there is not enough space in the paper for them.

Site 1: http://www.perdis.esprit.ec.org/ Figure 17 and Fig. 18 shows respectively proportion of inter-bunch references and proportion of inter-bunch cycles for the PerDiS web site. The proportion of inter-bunch references is 1% to 7% lower than the proportion we have using the last modifications date order, depend on the bunch size. For proportion of inter-bunch cycles, the difference is between 10% higher for 32K bunches to 10% lower for bunches of 1024K and 2048K. shows respectively proportion of inter-bunch references and proportion of inter-bunch cycles for the SOR web site. The proportion of inter-bunch references is 0% to 10% lower than the proportion we have using the last modifications date order, depend on the bunch size.

For proportion of inter-bunch cycles, the difference is between 3% lower for 32K bunches to 15% lower for 2048K bunches.

+ + + + + + + × × × × × × × ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ◊ ◊ ◊ ◊ ◊ ◊ ◊ 32K 64K 128K 256K 512K 1024K 2048K
Bunch Size (KBytes) Ratio(%)

+ + + + + + + × × × × × × × ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ♦ ♦ ♦ ♦ ♦ ♦ ♦ ◊ ◊ ◊ ◊ ◊ ◊ ◊ 32K 64K 128K 256K 512K 1024K 2048K
Bunch Size (KBytes) Ratio(%)

Fig. 20. SOR: proportion of inter-bunches cycles

In this paper, we have analyzed the intrinsic graph characteristics of two web sites (see Sect. 3) and evaluated the respective performance of five memory allocation strategies for a persistent store by simulating their behavior against the two web sites.

From the analysis of graph characteristics, we learned that most of the objects are small (around 80% are less than 50 Kbytes) and reference density is low. This confirms some known results. On the other hand, we learned that a large proportion of the objects is included in cycles (70% for site 1 and 30% for site 2) and the proportion of bytes involved is not negligible (12% to 14%). If we look at the characteristics of the individual cycles, it appears that most cycles are relatively small, both in number of objects and in bytes. This result contradict our assumption of a relatively small proportion of cycles. However, since the cycles are quiet small, this is not really a problem.

From the memory allocation simulations, we learned that a large proportion of references are inter-bunch: a large proportion of the cycles are inter-bunches whatever the bunch size and whatever allocation strategies we choose. This is not the results we expected. However these results need to be interpreted with caution because, first, we have studied only two web sites, which are not guaranteed to be representative of other web sites. Second, web application might not be representative of applications that use a persistent object store.

Finally, the simulation we have done with the allocation sorted by graph topology in depth-first topdown order shows that this order give always better locality results than the last modifications date order, but the difference is not so big. Most often, it stay between 5% to 10% and by the way using the allocationorder clustering policy seem to be feasible according to this set of simulations.

Future Work

This paper presented a first evaluation of the memory allocation strategies for the PerDiS Persistent Distributed Object Store. Future work direction are numerous.

One is to study the evolution of web sites over a long time period, by recording several snapshot until we are able to see significant graph modifications and deallocations. This is especially relevant for the measurements of memory fragmentation. Another direction is to implement more allocation strategies in our simulator, such as Buddy Systems [Kno65,PN77], Indexed Fits [START_REF] Stephenson | Fast Fits: New methods for dynamic storage allocation[END_REF], or Bit-mapped Fits [START_REF] Boehm | Mostly parallel garbage collection[END_REF]. Extending our measurements on the web to many other web sites will be also interesting in the future. Another point is to study applications specifically targeting a persistent objects store and written in an object oriented fashion. More specifically, we plan to study the port to PerDiS of the Atlantis application from IEZ 11 . Comparing many other known dynamic re-clustering strategies (breath-first, depth-first, hierarchical decomposition, type directed, other ?) with our current allocation time placement strategy will be very interesting. In the more distant future, we may design and evaluate a new strategy where the specific target will be to minimize cross-bunches references. Those re-clustering strategies may be used in the PerDiS store if it appears that the static heuristics we have evaluated first are not efficient enough.

Fig. 5 .

 5 Fig. 5. SOR: object size class frequency distribution

Fig. 9 .

 9 Fig. 9. PerDiS: proportion of inter-bunch references

Fig. 12 .

 12 Fig. 12. PerDiS: memory fragmentation

Fig. 13 .

 13 Fig. 13. SOR: proportion of inter-bunch references

  Fig. 15. SOR: number of scions

Fig. 17 .

 17 Fig. 17. PerDiS: proportion of inter-bunch references

Fig. 18 .

 18 Fig. 18. PerDiS: proportion of inter-bunches cycles

Fig. 19 .

 19 Fig. 19. SOR: proportion of inter-bunch references

  The SOR web site was studied on Thursday October 14 1999. At this date, it contained 8823 objects and 222714 valid references, for a total size of 277 Mbytes.The smallest object is 8 bytes and the largest one is 8.4 Mbytes. Median is 5.3 Kbytes for an arithmetic mean of 32 Kbytes and a variation coefficient of 5.4. We present the size frequency distribution in Fig.5.

																							72.7
																							65.5
																							58.2
																							50.9
																						Freq(%)	29.1 36.4 43.6
																							21.8
																							14.5
																							7.3
																							0.0	.	7.0e+03	4.6e+04	8.6e+04	1.3e+05	1.6e+05	2.0e+05	2.4e+05	2.8e+05	3.2e+05	3.6e+05	4.0e+05	4.4e+05	4.8e+05	5.2e+05	5.6e+05	6.0e+05	6.4e+05	6.8e+05	7.2e+05	1.4e+07 +	Bytes
																						Fig. 4. PerDiS: size frequency, in bytes, of strongly con-
																						nected components
		13.64
		12.27
		10.91																				3.2 Site 2: http://www-sor.inria.fr/
		9.55
	Freq(%)	6.82 8.18
		5.45
		4.09
		2.73
		1.36
		0.00	.
			3.0e+00	4.0e+00	5.0e+00	6.0e+00	7.0e+00	9.0e+00	1.3e+01	1.5e+01	1.7e+01	1.9e+01	2.5e+01	2.7e+01	3.7e+01	4.1e+01	4.5e+01	4.7e+01	4.9e+01	1.4e+02	1.8e+03	of Objects Number
																							53.81
	Fig. 3. PerDiS: size frequency, in number of objects, of	48.43
	strongly connected components										43.05
																							37.67
																						Freq(%)	26.91 32.29
																							21.53
																							16.14
																							10.76
																							5.38
																							0.00	.	8.0e+00	6.4e+03	1.3e+04	1.9e+04	2.6e+04	3.2e+04	3.9e+04	4.5e+04	5.1e+04	5.8e+04	6.4e+04	7.1e+04	7.7e+04	8.4e+04	9.0e+04	9.7e+04	1.0e+05	1.1e+05	1.2e+05	1.2e+05 +	Bytes

9

The density of reference is the number of references contained in one object, respectively in one Kilobyte. 10 This component is in reality a mail archive with each message as an HTML document and this documents contained each a link to the previous and the next message.

-

  Linear bunch: Basically the same than Last available bunch, but never re-use the previous bunch in the list, allocate a new one. The same remark than for linear inside bunch allocation strategy apply. -Segregated bunch: Use different bunches to allocate object of different size classes. Sizes are rounded up to the nearest power of two. The first four strategies can be used in conjunction with first fit, best fit, roving pointer or linear allocator inside bunch allocation strategies. Segregated bunch can be used only with fixed size inside bunch allocation strategy.

The home site ensures data security and reliability.

For latency reasons, bunches could be divided in pages but the page forming a bunch should be fully located at a site for the Garbage Collection to operate on.

Data in persistent and transient memory is typically not the same. A lot of data in transient memory (used by graphical library for example), for intermediate results will never be persistent.

QMW, a partner of the PerDiS project, did that for another purpose (http://www.dcs.qmw.ac.uk/research/ distrib/perdis/docs/perdisweb.html).

5 http://www.math.uio.no/~janl/

w3mir/ 6 The documentation of this library is available from ftp://ftp.inria.fr/INRIA/Projects/SOR/ misc/analysis/doc/

log_facilities.ps.gz 7 http://www.perl.com/

references that points to documents that exists, not including dangling references that point to unexisting documents (or protected documents that are not available for us).