Konstantin Avrachenkov
email: konstantin.avrachenkov@inria.fr

Jasper Goseling
email: j.goseling@utwente.nl

Berksan Serbetci
email: serbetci@eurecom.fr

Distributed Cooperative Caching for VoD with Geographic Constraints

We consider caching of video streams in a cellular network in which each base station is equipped with a cache. Video streams are partitioned into multiple substreams and the goal is to place substreams in caches such that the residual backhaul load is minimized. We consider two coding mechanisms for the substreams: Layered coding (LC) mechanism and multiple description coding (MDC). We develop a distributed asynchronous algorithm for deciding which files to store in which cache to minimize the residual bandwidth, i.e., the cost for downloading the missing substreams of the user's requested video with a certain video quality from the gateway (i.e., the main server). We show that our algorithm converges rapidly. Finally, we show that MDC partitioning is better than the LC mechanism when the most popular content is stored in caches; however, our algorithm enables to use the LC mechanism as well without any performance loss.

I. INTRODUCTION

Data traffic in cellular networks is rapidly expanding and one of the main reasons is the explosive growth in the demand for Video-on-Demand (VoD) content. Recent studies show that existing network infrastructures will not be able to support the demand [START_REF]Cisco VNI global mobile data traffic forecast[END_REF]. One of the bottlenecks will be formed by the backhaul links that connect base stations to the core network and we need to utilize these links as efficiently as possible. A promising means to efficiently handle this issue is to proactively cache data in the base stations. The idea is to store part of the popular data at the wireless edge and use the backhaul to refresh the stored data at off-peak hours since users' demand distribution over time is varying slowly. In order to embody this, content and network service providers are deploying Video Hub Offices (VHOs) serving as caches in metropolitan areas to serve VoD subscribers in that area. In this way, caches containing popular content serve as helpers to the overall system and decrease the backhaul load.

Our goal in this paper is on developing low-complexity distributed and asynchronous content placement algorithms for VoD. As content and network service providers would like to optimize the cached content in caches (i.e., base stations, or more specifically VHOs) while keeping the communication in the network to a minimum, the problem is of practical relevance in cellular networks. Our low-complexity distributed and asynchronous algorithm is designed to optimize the content and keeping the communication between caches to a minimum as the caches exchange information only locally.

Let us first provide a brief discussion of the related works. Caching has been receiving a lot of attention in the literature lately. Here we provide a brief overview of the work on caching that is most closely related to the current paper. A general outline of a distributed caching architecture for wireless networks considering a network model in which a bipartite graph indicates how users are connected to base stations has been presented in [START_REF] Shanmugam | FemtoCaching: wireless content delivery through distributed caching helpers[END_REF]. Works in [START_REF] Altman | Distributed storage in the plane[END_REF], [START_REF] Avrachenkov | Optimization of caching devices with geometric constraints[END_REF], [START_REF] Błaszczyszyn | Optimal geographic caching in cellular networks[END_REF], [START_REF] Serbetci | Optimal geographical caching in heterogeneous cellular networks[END_REF] consider placement of base stations in the plane according to a stochastic geometry where the main aim is to find the optimal placement strategy for the network for various performance measures. In [START_REF] Avrachenkov | A low-complexity approach to distributed cooperative caching with geographic constraints[END_REF] we have developed a distributed asynchronous algorithm that deals with the miss probability minimization by casting the problem into the framework of potential games for such networks where caches are located at arbitrary locations, and showed that our algorithm converges to a Nash equilibrium, and in fact to the best Nash equilibrium in most practical scenarios. Works in [START_REF] Pellegrini | A pracing scheme for content caching in 5G mobile edge clouds[END_REF], [START_REF] Pellegrini | Competitive caching of contents in 5G edge cloud networks[END_REF] also consider the problem of caching from a game-theoretic perspective for different cost functions. Finally in [START_REF] Applegate | Optimal content placement for a large-scale VoD system[END_REF], authors present an approach for optimal content placement for a large-scale VoD by formulating the problem as a mixed integer problem. The main difference between [START_REF] Avrachenkov | A low-complexity approach to distributed cooperative caching with geographic constraints[END_REF], [START_REF] Applegate | Optimal content placement for a large-scale VoD system[END_REF] and the present work is the considered performance measures, the concept of video partitioning and the heterogeneity of the video popularities over the network. For a more thorough review of the existing caching work, the reader is strongly encouraged to refer to papers [START_REF] Avrachenkov | A low-complexity approach to distributed cooperative caching with geographic constraints[END_REF], [START_REF] Paschos | The Role of caching in future communication systems and networks[END_REF].

In the remainder of the introduction we will give an overview of the model and contributions.

We consider a network with caches located at arbitrary locations in the plane. Caches know their own coverage area as well as the coverage areas of other caches that overlap with this region. There is a content catalog from which users request videos with a certain video quality according to a known probability distribution. Videos are partitioned into chunks (i.e., substreams) by using two coding mechanisms: Layered coding (LC) mechanism [START_REF] Wiegand | Overview of the H.264/AVC video coding standard[END_REF] and Multiple Description Coding (MDC) [START_REF] Goyal | Multiple description coding: compression meets the network[END_REF]. Each cache can store a limited number of chunks and the goal is to minimize the residual bandwidth, i.e., the cost for downloading the missing video chunks of the users' requested videos with certain video qualities from the main server. We develop low-complexity asynchronous distributed cooperative content placement caching algorithms that require communication only between caches with overlapping coverage areas. In the basic algorithm, at each iteration a cache will selfishly update its cache content by minimizing the local residual bandwidth and by considering the content stored by neighbouring caches. We show that our basic algorithm can be formulated as providing the best response dynamics in a potential game. We show that our algorithm is guaranteed to converge to a Nash equilibrium in finite time. We analyze the structure of the best response dynamics and provide the closed-form optimal solutions for the content placement by solving the linear optimization problem. Finally, we illustrate our results by a number of numerical results with various video quality request distributions for real world network models.

To specify, our contributions are as follows:

• We provide the partitioning models for the two aforementioned coding mechanisms and formulate problems in order to minimize the residual bandwidth for both mechanisms; • We provide a distributed asynchronous algorithm for optimizing the content placement which can be interpreted as giving the best response dynamics in a potential game for both partitioning mechanisms; • We prove that the best response dynamics can be obtained as a solution of a linear optimization problem; • We prove that our algorithm converges in finite time, and in fact rapidly; • We evaluate our algorithm through numerical examples using the base station locations from a real wireless network for the cellular network topology. We study the residual bandwidth evolution on a real network numerically for both coding mechanisms and show that our distributed caching algorithm strongly suggests using the LC mechanism for video partitioning in VoD systems; Let us outline the organization of the paper. In Section II we give the formal model and problem definitions. In Section III we provide the game formulation of the problem, analyze the structures of the best response dynamics and Nash equilibria.In Section IV, we present practical implementations of our lowcomplexity algorithms for various video quality distributions and show the resulting performance for a real network. In Section V we conclude the paper with some discussions and provide an outlook on future research.

II. MODEL AND PROBLEM DEFINITION

We consider a network of N base stations that are located in the plane R 2 . We will use the notation [1 : N ] = {1, . . . , N } and Θ = P ([1 : N ]) \ ∅, where P ([1 : N ]) is the power set of [1 : N ]. We specify the geometric configuration of the network through A s , s ∈ Θ, which denotes the area of the plane that is covered only by the caches in subset s, namely A s = (∩ ∈s Ā ) ∩ (∩ ∈s Āc ), where Ā is the complete coverage region of cache .

As a special case we will consider the case that all base stations have same circular coverage region with radius r. In this case we specify the location of each base station, with x m for the location of base station m ∈ [1 : N ]. We then obtain Ām as the disc of radius r around x m .

The content library consists of videos from the set C = {c 1 , . . . , c J }, where J < ∞. Each element c j represents a video, where j is the file index. The size of video c j is denoted by w j . Next, videos are partitioned into chunks. We assume that video c j is partitioned into Q chunks and consequently, the chunk library consists of video chunks C c = {c 1,1 , . . . , c 1,Q , . . . , c J,1 , . . . , c J,Q }, where J, Q < ∞. Each element c j,q represents a video chunk, where j is the file index and q is the chunk index. The chunk size for the element c j,q is denoted by w j,q . Each base station is equipped with a cache that can be used to store video chunks from C c .

The motivation behind partitioning videos into chunks is as follows. In this work we will consider various coding mechanisms. If the video is partitioned by using layered coding (LC) mechanisms (e.g., MPEG-2, MPEG-4, etc.), there is a base layer and enhancement layers. The base layer is necessary for the media stream to be decoded. Accordingly, the further enhancement layers are applied to improve the video quality. Hence, for the layered coding mechanism, the element c j,1 represents the base layer for video j, and c j,2 is the first enhancement layer required to obtain a better video quality, and so forth. For the LC mechanism, Q = Q LC and the chunk size w j,q will then depend on the average base size of the different video qualities, and the total size of the video j with the highest video quality is equal to

w j = Q LC q=1 w j,q . (1)
Another coding mechanism that we will consider is multiple description coding (MDC). For MDC, the video stream is partitioned into multiple substreams, referred to as descriptions. Any description can be used to decode the media stream. As the number of received substreams increases, the received video quality increases. Since there is no hierarchical layered coding system, each received unique description is equally beneficial to increase the video quality. For the MDC mechanism, Q = Q M DC and the chunk size w j,q is constant for any chunk q for fixed video j, and the total size of the video j with the highest video quality is equal to

w j = Q M DC w j,q . ( 2
)
Our interest is in users located in the plane over the area that is covered by the base stations, i.e., uniformly distributed in A cov = ∪ s∈Θ A s . The probability of a user in the plane being covered by caches s ∈ Θ (and is not covered by additional caches) is denoted by

p s = |A s |/|A cov |. A user located in A s , s ∈ Θ can connect
to all caches in subset s, and has access to all video chunks stored in these caches.

We assume that there are R video quality levels. The probability that video j is requested with video quality ρ by a user at x u ∈ s is denoted by a j,ρ,s . Here ρ = 1 refers to the video with the lowest quality and ρ = R refers to the case where the video has the highest quality. There is an obvious relation between the required chunks and the desired video quality. For the LC mechanism, files can be divided into Q LC = R layers with the proper size selections (w j,q ) and receiving all layers gives the video with the highest quality. On the other hand, for the MDC mechanism, in practice Q M DC is not equal to R since all chunks have equal size. We define a new parameter D ρ that represents the required number of chunks to get the video quality ρ.

We assume that the distribution for the requested video's quality depends on the user's location. To validate this assumption, one might think that users travelling in the bus will more likely request watching videos in a lower resolution compared to those located in residential areas. Similarly, users located in a residential area may request watching videos in different qualities as some users may watch videos via their ultra highdefinition televisions, whereas others watch videos via their mobile phones with a lower resolution. We assume that the requested video quality for a user located in s ∈ Θ follows a known and fixed probability mass function (pmf) f (s) (ρ).

For the file popularities, we assume that a 1 ≥ a 2 ≥ • • • ≥ a J for any video quality ρ. We assume that the video popularities do not vary as ρ changes. Even though any popularity distribution can be used, most of our numerical results will be based on the Zipf distribution for the video popularities for any video quality ρ. For any video quality indicator ρ, the probability that a user will ask for content j is equal to

a j = j -γ J j=1 j -γ , (3)
where γ > 0 is the Zipf parameter. Since a j and f (s) (ρ) represent statistically independent random variables, we conclude that the probability that video j is requested by a user located at x u ∈ s with video quality ρ is equal to

a j,ρ,s = j -γ J j=1 j -γ f (s) (ρ). (4)
Content is placed in caches using knowledge of the request statistics a j,ρ,s , but without knowing the actual request made by the user. We denote the placement policy for cache m as b (m)

j,q := 1, if c j,q is stored in cache m, 0, if c j,q is not stored in cache m, (5)
and the overall placement strategy for cache m as

B (m) =     b (m) 1,1 . . . b (m) J,1 . . . . . . . . . b (m) 1,Q . . . b (m) J,Q    
as a Q × J matrix. The overall placement strategy for the network is denoted by B = B (1) ; . . . ; B (N ) as an Q×J ×N three-dimensional matrix.

Caches have capacity K, i.e.,

J j=1 Q q=1 w j,q b (m) j,q ≤ K, ∀m.
For clarity of presentation, we assume homogeneous capacity for the caches. However, our work can immediately be extended to the network topologies where caches have different capacities.

The user requests to watch one of the videos from the content library with certain quality. The aim is to place content in the caches ahead of time in order to minimize the residual bandwidth, i.e., the cost for downloading the missing video chunks of the user's requested video with a certain video quality from the gateway in order to serve the users. Next, we will design cache placement strategies for residual bandwidth minimization for the LC and MDC mechanisms.

A. Layered coding mechanism

For the LC mechanism, the residual bandwidth f LC (B) is equal to

f LC (B) = s∈Θ J j=1 R ρ=1 p s a j,ρ,s ρ q=1 w j,q ∈s 1 -b ( ) j,q . (6)
Our goal is to find the optimal placement strategy minimizing the residual bandwidth as follows:

Problem 1. min f LC (B) s.t. J j=1 Q q=1 w j,q b (m) j,q ≤ K, ∀m, (7) b (m)
j,q ∈ {0, 1}, ∀j, q, m.

It is easy to verify that Problem 1 is not convex. We will provide a distributed asynchronous algorithm to address Problem 1 in which we iteratively update the placement policy at each cache. In [START_REF] Avrachenkov | A low-complexity approach to distributed cooperative caching with geographic constraints[END_REF] we have showed for a different performance measure that we can define an algorithm that can be viewed as the best response dynamics in a potential game. We will present a similar algorithm here. We make use of the following notation. Denote by B (-m) the placement policies of all caches except cache m. We will write f LC (B (m) , B (-m) ) to denote f LC (B). Also, for the sake of simplicity for the potential game formulation that will be presented in the following section, let f

(m) LC denote the residual bandwidth of cache m, i.e., f (m) LC (B) = s∈Θ m∈s J j=1 R ρ=1 ρ q=1 p s a j,ρ,s w j,q 1 -b (m) j,q ∈s\{m} 1 -b ( ) j,q = s∈Θ m∈s J j=1 R ρ=1 ρ q=1 p s a j,ρ,s w j,q 1 -b (m) j,q ζ (m) (j, q) , (9)
where

ζ (m) (j, q) = ∈s\{m} 1 -b ( ) j,q . (10)

B. Multiple description coding

In MDC, receiving all Q M DC descriptions will provide the highest expected video quality experience for the users. For the sake of simplicity, we define a new parameter y j,ρ,s denoting the total number of descriptions that needs to be fetched from the backhaul in order to satisfy the expected video quality ρ for video j in s ∈ Θ as

y j,ρ,s = max 0, D ρ -Q + Q q=1 ∈s 1 -b ( ) j,q . ( 11
)
For the MDC mechanism, the residual bandwidth f M DC (B), i.e., the cost for downloading the missing chunks of the user's requested video from the gateway is equal to

f M DC (B) = 1 Q s∈Θ J j=1 R ρ=1
p s a j,ρ,s w j y j,ρ,s .

Our goal is to find the optimal placement strategy minimizing the total number of descriptions that needs to be fetched from the backhaul, equivalently minimizing the residual bandwidth as follows:

Problem 2. min f M DC (B) s.t. J j=1 Q q=1 w j b (m) j,q ≤ KQ, ∀m, (13) b (m)
j,q ∈ {0, 1}, ∀j, q, m, .

As in the LC mechanism, Problem 2 is not convex either. Therefore, we will provide a distributed asynchronous algorithm to address Problem 2 (similar to the procedure we followed for the layered mechanism) in which we iteratively update the placement policy at each cache. We will make use of the following notation. Denote by B (-m) the placement policies of all caches except cache m. We will write f M DC (B (m) , B (-m) ) to denote f M DC (B). Also, for the sake of simplicity for the potential game formulation that will be presented in the following section, let f

(m) M DC denote the residual bandwidth of cache m, i.e., f (m) M DC (B) = 1 Q s∈Θ m∈s J j=1 R ρ=1 p s a j,ρ,s w j max 0, D ρ -Q + Q q=1 1 -b (m) j,q ζ (m) (j, q) , (15)
where ζ (m) (j, q) is given in [START_REF] Paschos | The Role of caching in future communication systems and networks[END_REF].

III. POTENTIAL GAME FORMULATION

In this section we provide a distributed asynchronous algorithm to address Problems 1 and 2 in which we iteratively update the placement policy at each cache. We will show that this algorithm can be formulated as providing the best response dynamics in a potential game.

In our algorithm, each cache tries selfishly to minimize its residual bandwidth f

f (m) LC B (m) , B (-m) s.t. J j=1 Q q=1 w j,q b (m) j,q ≤ K, (16) b
(m) j,q ∈ [0, 1], ∀j, q, (17)
for the LC mechanism and,

Problem 4. min f (m) M DC B (m) , B (-m) s.t. J j=1 Q q=1 w j b (m) j,q ≤ KQ, ∀m, (18) b (m)
j,q ∈ [0, 1], ∀j, q, (19)
for the MDC mechanism. Each cache continues to optimize its placement strategy until no further improvements can be made. At this point B is a Nash equilibrium strategy that minimizes the overall residual bandwidth satisfying

f (m) LC (B (m) , B (-m) ) ≤ f (m) LC ( B(m) , B (-m) ), ∀m, B(m) ,
(20) for the LC mechanism and,

f (m) M DC (B (m) , B (-m) ) ≤ f (m) M DC ( B(m) , B (-m) ), ∀m, B(m) , (21)
for the MDC mechanism.

For both coding mechanisms, we will refer to these games as the content placement games and demonstrate in the next subsections that both games are potential games [START_REF] Monderer | Potential games[END_REF] with many nice properties.

A. Convergence analysis

In this section, we will prove for both coding mechanisms that if the caches repeatedly update their placement strategies it is guaranteed to converge to a Nash equilibrium in finite time. Note that the order of the updates is not important as long as all caches are scheduled infinitely often.

Theorem 1. The content placement games defined by payoff functions [START_REF] Monderer | Potential games[END_REF] and (15) are potential games with the potential function given in (6) and (12), respectively. For both games, if we schedule each cache infinitely often, the best response dynamics converges to a Nash equilibrium in finite time.

Proof. In order to show that both games are potential with the potential functions f LC (B) and f M DC (B), it is easy to verify that

f (m) LC B(m) , B (-m) -f (m) LC B (m) , B (-m) = f LC B(m) , B (-m) -f LC B (m) , B (-m) , and
f (m) M DC B(m) , B (-m) -f (m) M DC B (m) , B (-m) = f M DC B(m) , B (-m) -f M DC B (m) , B (-m) ,
which completes the proof of the first statement. The proof states that the improvement in the residual bandwidth by the best response after each update is equal to the improvement in the residual bandwidth in the overall network. The detailed analysis is trivial and skipped due to space constraints. Now, since there exists only a finite number of placement strategies, none of the caches will be missed in the long-run. Moreover, each non-trivial best response provides a positive improvement in the potential function in a potential game. Hence, we are guaranteed to converge to a Nash equilibrium in finite time for both games.

B. Structure of the best response dynamics

In this subsection we will analyze the structure of the best response dynamics. We will show that solutions to Problem 3 and to Problem 4 can be obtained by solving a linear optimization problem and we provide the solutions in closed form.

For notational purposes, let us first define the set Ω = {(j, q), (j ∈ [1, J]) , (q ∈ [1 : Q])} that consists of all video index-video quality tuples.

Theorem 2. The optimal solution to Problem 3 is given by b(m) j,q = 1, if π -1 m (j, q) ≤ K/w j,q , 0, if π -1 m (j, q) > K/w j,q ,

where

π m : Ω → [1 : J × Q] satisfies s∈Θ m∈s R ρ=πm(1,2)
p s a πm(1,1),ρ,s w πm(1,1),πm(1,2)

ζ (m) (π m (1, 1), π m (1, 2)) ≥ s∈Θ m∈s R ρ=πm(2,2)
p s a πm(2,1),ρ,s w πm(2,1),πm(2,2)

ζ (m) (π m (2, 1), π m (2, 2)) ≥ . . . ≥ s∈Θ m∈s R ρ=πm(J×Q,2)
p s a πm(J×Q,1),ρ,s w πm(J×Q,1),πm(J×Q,2)

ζ (m) (π m (J × Q, 1), π m (J × Q, 2)) ,
where π m (i, 1) is the file index j of the i th sorted tuple, and π m (i, 2) is the video quality index q of the i th sorted tuple.

Proof. The objective function f

(m)
LC (B) is an affine function and we have several inequality constraints. It is easy to verify that we also have affine functions in the constraints. Therefore, we can conclude that Problem 3 is a linear problem. It can then be easily solved using the dual problem. We have Lagrange dual function

inf B    s∈Θ m∈s J j=1 R ρ=1 ρ q=1 p s a j,ρ,s w j,q 1 -b (m) j,q ζ (m) (j, q) + λ   J j=1 Q q=1 w j,q b (m) j,q -K   - J j=1 Q q=1 µ j,q b (m) j,q + J j=1 Q q=1 ν j,q b (m) j,q -1   .
For notational convenience we introduce the functions Ψ j,q : R → [0, 1], j = 1, . . . , J, and q = 1, . . . , Q as follows

Ψ j,q (λ) =    1, if λ < s∈Θ m∈s R ρ=q p s a j,ρ,s w j,q ζ (m) (j, q) , 0, if λ ≥ s∈Θ m∈s R ρ=q p s a j,ρ,s w j,q ζ (m) (j, q) . ( 23
)
We also define Ψ : R → [0, K], where

Ψ(λ) = J j=1 Q q=1 w j,q Ψ j,q (λ) = K for λ ∈   -∞, s∈Θ m∈s R ρ=q p s a j,ρ,s w j,q ζ (m) (j, q)    ,
and

Ψ(λ) = J j=1 Q q=1 w j,q Ψ j,q (λ) = 0 for λ ∈    s∈Θ m∈s R ρ=q p s a j,ρ,s w j,q ζ (m) (j, q) , ∞    .
It is then possible to check all possible combinations from the video content-video quality tuples Ω → [1 : J × Q] to confirm if the condition given in ( 23) is satisfied. In order to satisfy the capacity constraint ( 16) the above solution is guaranteed to exist. The proof is completed by validating that with the strategy above, λ solving the Lagrange dual is satisfying Ψ( λ) = K.

The intuition behind Theorem 2 is as follows. The ordering is simply made based on the weights of the tuples consisting of the probability of being located in a specific region, the summation coming from the effect of the difference between requests with different video qualities (and the summation index difference due to the effect of the layered coding mechanism), and the effect of the possibility of receiving the chunks from the neighbours.

(m) j,q = 1, if π -1 m (j, q) ≤ KQ/w j , 0, if π -1 m (j, q) > KQ/w j , (24)
where

π m : Ω → [1 : J × Q] satisfies s∈Θ m∈s R ρ=1 p s a πm(1,1),ρ,s w πm(1,1) ζ (m) (π m (1, 1), π m (1, 2)) 1(D ρ -Q + Q i=1 ζ (m) (π m (1, 1), i) > 0) ≥ s∈Θ m∈s R ρ=1 p s a πm(2,1),ρ,s w πm(2,1) ζ (m) (π m (2, 1), π m (2, 2)) 1(D ρ -Q + Q i=1 ζ (m) (π m (2, 1), i) > 0) ≥ . . . ≥ s∈Θ m∈s R ρ=1 p s a πm(J×Q,1),ρ,s w πm(J×Q,1) ζ (m) (π m (J × Q, 1), π m (J × Q, 2)) 1(D ρ -Q + Q i=1 ζ (m) (π m (J × Q, 1), i) > 0),
where π m (i, 1) is the file index j of the i th sorted tuple, and π m (i, 2) is the video quality index q of the i th sorted tuple., and 1(.) is the indicator function, i.e., it is equal to 1 if the condition is satisfied and 0 otherwise.

Proof. The objective function f

M DC (B) is a linear function and we have several inequality constraints. It is easy to verify that we also have linear functions in the constraints. Therefore, we can conclude that Problem 4 is a linear problem. It can then be easily solved using the dual problem. We have Lagrange dual function

inf B    s∈Θ m∈s J j=1 R ρ=1 p s a j,ρ,s w j max 0, D ρ -Q + Q q=1 1 -b (m) j,q ζ (m) (j, q) + λ   J j=1 Q q=1 w j b (m) j,q -KQ   - J j=1 Q q=1 µ j,q b (m) j,q + J j=1 Q q=1 ν j,q b (m) j,q -1   .
For notational convenience we introduce the functions Φ j,q : R → [0, 1], j = 1, . . . , J, and q = 1, . . . , Q as follows

Φ j,q (λ) =    1, if λ < s∈Θ m∈s R ρ=q p s a j,ρ,s ζ (m) (j, q) , 0, if λ ≥ s∈Θ m∈s R ρ=q p s a j,ρ,s ζ (m) (j, q) , (25)
when

D ρ -Q+ Q i=1 ζ (m) (j, i) > 0. We also define Φ : R → [0, K], where Φ(λ) = J j=1 Q q=1 w j Φ j,q (λ)/Q = K for λ ∈   -∞, s∈Θ m∈s R ρ=q p s a j,ρ,s w j,q ζ (m) (j, q)    , and Φ(λ) = J j=1 Q q=1 w j Φ j,q (λ) = 0 for λ ∈    s∈Θ m∈s R ρ=q p s a j,ρ,s w j,q ζ (m) (j, q) , ∞    .
It is then possible to check all possible combinations from the video content-video quality tuples Ω → [1 : J × Q] to confirm if the condition given in (25) is satisfied. In order to satisfy the capacity constraint [START_REF]OpenMobileNetwork[END_REF] the above solution is guaranteed to exist. The proof is completed by validating that with the strategy above, λ solving the Lagrange dual is satisfying Φ( λ) = K.

C. Structure of Nash equilibria

In this subsection we provide insight into the structure of the Nash equilibria of the content placement games. We know from the previous subsection that both games are potential games. Hence, the Nash equilibria for the games correspond to the optimal placement strategies satisfy the solutions of the dual problems of Problem 1 and Problem 2, respectively. Corollary 1. Let B denote a placement strategy at a Nash equilibrium of the content placement game for the LC mechanism. Then, B satisfies (22) ∀m = 1, . . . , N .

Proof. The proof is similar to the proof of Theorem 2, where in this case the optimal placement strategies must hold for all 1 ≤ m ≤ N simultaneously.

Corollary 2. Let B denote a placement strategy at a Nash equilibrium of the content placement game for the MDC mechanism. Then, B satisfies (24) ∀m = 1, . . . , N .

Proof. The proof is similar to the proof of Theorem 3, where in this case the optimal placement strategies must hold for all 1 ≤ m ≤ N simultaneously.

IV. NUMERICAL EVALUATION

In this section we will present practical implementations of our algorithm for the content placement games for the LC and MDC mechanisms and evaluate our theoretical results according to a network of caches with their geographical locations following a real wireless network.

A. The ROBR algorithm

We will use the Random Order Best Response (ROBR) algorithm [START_REF] Avrachenkov | A low-complexity approach to distributed cooperative caching with geographic constraints[END_REF] for the content placement games for both coding mechanisms to minimize the residual bandwidth. The basic idea of our algorithm is to repeatedly perform best response dynamics presented in Section III-B. For ROBR algorithm, at each iteration step, a random cache is chosen uniformly from the set [1 : N ] and updated by applying best response dynamics. We assume that all caches are initially empty (i.e., B (m) = 0 Q,J , where 0 Q,J represents a Q × J zero matrix, ∀m ∈ [1 : N ].). The algorithm stops when f

B. A real wireless network: Berlin network

In this section we will evaluate our theoretical results for the topology of a real wireless network. We have taken the positions of the base stations provided by the OpenMobileNetwork project [START_REF]OpenMobileNetwork[END_REF]. The base stations are located in the area 1.95 × 1.74 kms around the TU-Berlin campus. We will consider these base stations as our caches with certain cache capacities. The coverage radius of the base stations is equal to r = 700 m. The locations of the base stations is shown in Figure 1.

We consider the content library of size J = 200. We assume a Zipf distribution for the video popularities, setting γ = 1 and taking a j according to (3). We consider the case where videos have R = 5 different video qualities. We use the video quality bandwidth requirements and the base size data given in [START_REF] Krishnappa | DASHing YouTube: An analysis of using DASH in YouTube video service[END_REF] for the chunk sizes, where the base size is the average of the sizes of a large set of tracked videos in certain video qualities given in megabytes per minute (MB/min). We assume that videos in the content library are all 40 minutes long. The corresponding video quality specifications are shown in Table I. The first column shows the video quality index ρ, the second column shows the base sizes of the videos and the third column shows the 40 minutes long video sizes with different qualities.

The videos are partitioned into Q LC = 5 chunks by the LC mechanism. From the third column of Table I, it immediately follows that w j,1 = 102.4 MB, w j,2 = 69.6 MB, w j,3 = 99.6 MB, w j,4 = 348.0 MB, and w j,5 = 688.4 MB, ∀j. By the MDC mechanism, the videos are partitioned into Q M DC = 38 chunks and w j,q = 34.42 MB ∀j, q. Consequently, D 1 = 3, D 2 = 5, D 3 = 8, D 4 = 18, and D 5 = 38. Note that the selection of Q M DC is based on the least common multiple of the third column of Table I. Finally, we set K = 6.54 GB, i.e., each cache can store five 1080p movies.

For the distribution of the requested video qualities, we have

f (s) (ρ) = 1+tρθs 5+10θs , if ρ ∈ 1, 2, 3, 4, 5, 0, otherwise, (26)
where t ρ is the parameter representing the direction of the increment of the requested video qualities and θ s is the slope of the linear increment.

We will now evaluate our theoretical results for three different video quality trends.

1) Uniform: For this trend, we set θ s = 0, ∀s ∈ Θ. This trend reflects the case where users request videos in all qualities equally likely throughout the whole network.

2) Linear correlation: For this trend, we set t ρ = 5 -ρ for |s| < E 3) Inverse correlation: We use the same parameters as in linear correlation case with the reversed t ρ 's, i.e., t ρ = ρ -1 for |s| < E[|s|], and t ρ = 5 -ρ for |s| > E[|s|]. This trend reflects the case where users covered by many caches request videos in lower quality.

In Figure 2 the residual bandwidth evolution for three different video quality trends for the proposed algorithm for both coding mechanisms is shown. In all video quality trends, storing the most popular content for the MDC mechanism gives a lower residual bandwidth compared to the LC mechanism since chunks have identical size and any received chunk increases the video quality for MDC. However, after running ROBR, the advantage of using MDC vanishes as both coding mechanisms give the same residual bandwidth performance. One might easily think that MDC would perform better than LC for a VoD system since any received chunk would increase the video quality. However, we see that LC can perform as good as MDC by applying ROBR and placing the chunks optimally. This is a crucial observation due to following reason. From a technical point of view, at a given bitrate budget, there is a quality loss in MDC with respect to LC and chunks are more difficult to encode [START_REF] Vitali | Multiple description coding -a new technology for video streaming over the Internet[END_REF]. In fact [START_REF] Wang | Multiple description coding for video delivery[END_REF] shows that some serious portion of the bitrate budget is reserved for forward error correction in MDC and the actual residual bandwidth will be higher for MDC to obtain the exact same quality. Finally, the residual bandwidth performance is the best for the linear correlation case as the requested video quality increases as the number of caches that users can connect to increases.

V. DISCUSSION AND CONCLUSION In this paper we have provided a low-complexity asynchronously distributed cooperative caching algorithm for VoD when there is communication only between caches with overlapping coverage areas. We have related our algorithm to a best response dynamics in a game and have shown with practical examples that it converges rapidly. We have demonstrated the residual bandwidth evolution on a real network and have shown that our algorithm diminishes the advantage of using MDC over the LC mechanism. Due to technical details, MDC suffers from quality loss since the chunks are more difficult to encode. Hence, we conclude that using LC for video partitioning is better for a VoD system as long as ROBR is applied for the optimal placement of the video chunks.

In future work we will look into this problem from the users' perspective and focus on maximizing the user utilities.

  This work was supported by the European Research Council under the EU Horizon 2020 research and innovation program / ERC grant agreement no. 725929.

M

  DC defined in[START_REF] Monderer | Potential games[END_REF] and[START_REF] Vitali | Multiple description coding -a new technology for video streaming over the Internet[END_REF] for the LC and MDC mechanisms respectively. Given a placement B(-m) by the other caches, cache m solves for B (m) in Problem 3.

  min

Theorem 3 .

 3 The optimal solution to Problem 4 is given by b

Algorithm 1 :

 1 LC B (m) , B(-m) converges for the LC mechanism, andf (m) M DC B (m) , B (-m) converges for the MDC mechanism. ROBR algorithm is shown in Algorithm 1. Random Order Best Response (ROBR) initialize B (m) = 0 Q,J , ∀m ∈ [1 : N ]; set imp(m) = 1, ∀m ∈ [1 : N ] ; set imp = [imp(1), . . . , imp(N )]; while imp = 0 do m = Uniform(N); Set imp(m) = 0; Solve Problem 3* for cache m and find B(m) using the information coming from neighbours; Compute f (m)LC ( B(m) , B (-m) )*; if f (m) LC ( B(m) , B (-m) ) -f (m) LC (B (m) , B (-m) ) = 0* then imp(m) =1 end end *For the MDC mechanism, the algorithm solves Problem 4 and uses the performance measure f (m) M DC ( B(m) , B (-m) ).

Fig. 1 .

 1 Fig. 1. Locations of Base Stations from the OpenMobileNetwork dataset.

  [|s|], and t ρ = ρ -1 for |s| > E[|s|], and θ s = 0.1 ||s| -E[|s|]|, where |s| is the cardinality of the subset s ∈ Θ, E[|s|] is the mean of the cardinalities of the all subsets, and ||s| -E[|s|]| is the absolute value of the difference of them. This trend reflects the case where users covered by many caches request videos in higher quality.

Fig. 2 .

 2 Fig. 2. The residual bandwidth evolution.


Gergely Molnar

Guillaume Kermouche

Etienne Barthel

Gergely Molnár

Plastic response of amorphous silicates, from atomistic simulations to experiments -A general constitutive relation

Keywords: Silica glass, Yield criterion, Multi-scale modeling, Micro-compression, Nano-indentation

come

Plastic response of amorphous silicates, from atomistic simulations to experiments -A general constitutive relation

Introduction

Fracture and strength of silicate glasses have been investigated with renewed vigor in the past decade. A large number of papers have dealt with the relation between composition, structure, physical and also more advanced mechanical properties -see [START_REF] Wondraczek | Towards ultrastrong glasses[END_REF] for a recent review of the latter. Much sparser have been the efforts towards constitutive relations which could properly account for the plastic response under both simple and more complex loadings [START_REF] Kermouche | Mechanical modelling of indentation-induced densification in amorphous silica[END_REF]; [START_REF] Keryvin | Constitutive modeling of the densification process in silica glass under hydrostatic compression[END_REF]). However, the sound understanding of extreme mechanical response such as strength or cracking, and their composition dependence, would greatly benefit from a reliable description of the response at the continuum scale.

In fact, investigation of the plastic response of silicate glasses at the continuum scale has been limited by two major issues. First, in terms of measurements, it is difficult to obtain quantitative experimental data because large scale plastic deformations are preceded by cracking in most circumstances [START_REF] Cook | Direct observation and analysis of indentation cracking in glasses and ceramics[END_REF]). Therefore, only local (ie micron-scale) measurements can be performed. Secondly, in terms of description, it has long been known that material density may change during plastic deformation, ie there is irreversible volumetric strain also called densification or compaction [START_REF] Ernsberger | Role of densification in deformation of glasses under point loading[END_REF]). Therefore, we are confronted by a non conventional type of plasticity, in the sense that it does not conserve volume. Moreover, this second observation also points to the significance of hardening in the continuum scale response, which changes as the structure of the material evolves with plastic strain.

Faced with the issues of measurement difficulties, evolving structure and unconventional plasticity, alternative strategies are welcome. One of them is to resort to numerical simulations. In this field, pioneering work deduced a macroscopic yield criterion using numerical methods for bulk metallic glasses (BMGs): [START_REF] Schuh | Atomistic basis for the plastic yield criterion of metallic glass[END_REF] were able to capture the pressure dependence of the deviatoric yield strength shown experimentally [START_REF] Mukai | Effect of strain rate on compressive behavior of a Pd 40 Ni 40 P 20 bulk metallic glass[END_REF]; [START_REF] Zhang | Difference in compressive and tensile fracture mechanisms of Zr 59 Cu 20 Al 10 Ni 8 Ti 3 bulk metallic glass[END_REF], using only atomic scale simulations. Due to the complexity of the topic, only a limited number of papers have appeared, for metallic glasses [START_REF] Lund | Yield surface of a simulated metallic glass[END_REF]; [START_REF] Schuh | Atomistic basis for the plastic yield criterion of metallic glass[END_REF]; [START_REF] Shimizu | Yield point of metallic glass[END_REF]), nano-crystaline metals [START_REF] Lund | The Mohr-Coulomb criterion from unit shear processes in metallic glass[END_REF]; [START_REF] Salehinia | Molecular dynamics simulations of plastic deformation in nb/nbc multilayers[END_REF][START_REF] Van Swygenhoven | Competing plastic deformation mechanisms in nanophase metals[END_REF]), glassy polymers [START_REF] Mott | Atomistic modelling of plastic deformation of glassy polymers[END_REF]; [START_REF] Rottler | Yield conditions for deformation of amorphous polymer glasses[END_REF]) and other model materials [START_REF] Mcdowell | A perspective on trends in multiscale plasticity[END_REF]; [START_REF] Xu | Finite hyperelastic-plastic constitutive equations for atomistic simulation of dynamic ductile fracture[END_REF]). Recently, we have shown that yield surfaces can be calculated by atomic scale simulations for amorphous silicates (Molnár et al. (2016a)). However, this approach is not widespread because of some shortcomings of these simulations. With key issues such as calibration of the potential, size effects and time scale effects, atomistic simulations usually provide at most qualitative results. Here we investigate a method to turn the yield surfaces obtained from molecular statics (MS) into usable continuum scale descriptions of the material response of silicate glasses. We start from a parametric shape for the yield surface, inferred from MS, which duly reproduces the known evolutions with irreversible strain and we calibrate the parameters of the yield function from the available experimental results. Then the predictions of the resulting constitutive model are compared to other experiments and models. We also discuss the missing experimental results which would be most useful in this context.

Model

A generic analytical form for the yield criteria of silicate glasses has been evaluated numerically using Molecular Dynamics (or more precisely Molecular Statics) following the methodology reported in Molnár et al. (2016b) and Molnár et al. (2016a). In brief, through numerical experiments, different loading combinations have been applied to various systems modeling several binary glass compositions. The deformation was applied in a quasi-static manner, therefore no rate dependent effect is observable. The residual density and residual shear strain have been mapped as a function of applied stress and pressure. From these maps, a pressure dependent yield strength clearly appeared. We have therefore derived an analytical expression for the yield criterion as a function of pressure. The flow data obtained in the simulations have not been directly used for the constitutive relation but it was found that assuming associated plasticity we obtained a reasonable rendering of the computed irreversible strains (Molnár et al. (2017b); Molnár et al. (2016a)).

A typical yield surface is shown in the p -q plane (Fig. 1) for a model amorphous silica1 . The yield surfaces are plotted for different material densities ranging between pristine to fully densified material. In contrast to usual metal plasticity, the yield surface for the pristine, undensified material, forms a dome which reflects the strong coupling between shear and hydrostatic pressure, as observed experimentally [START_REF] Mackenzie | High-pressure effects on oxide glasses: I. densification in rigid state[END_REF]; [START_REF] Meade | Effect of a coordination change on the strength of amorphous SiO 2[END_REF]). Above some value of hydrostatic pressure (ca -5 GPa in this case) shear strength decreases with increasing pressure. The strength curve crosses the pressure axis at the compressive (hydrostatic) strength which is the threshold for plastic deformation under pure hydrostatic pressure. Below a pressure of ca -5 GPa, the shear strength decreases as pressure decreases, similarly defining the tensile (hydrostatic) strength when the curve crosses the pressure axis. As a result a peak deviatoric strength arises, equal to about 16 GPa here. As expected, this yield surface is found to evolve significantly with permanent volumetric strain ε pl V : as density increases, the peak deviatoric strength decreases moderately, as well as the tensile (hydrostatic) strength (in absolute value), while the compressive (hydrostatic) strength increases dramatically. This strong increase of the hydrostatic compression strength reflects hardstress tensor: the pressure (p = -(σ x + σ y + σ z )/3) and the equivalent ening with densification: as density saturates, the plastic response becomes shear dominated, analogous to BMGs. On the tensile side, the threshold signals instability: a homogeneous pressure state can not be maintained and macroscopic voids nucleate (Molnár et al. (2016c)). This phenomenon should be modeled with an appropriate damage model [START_REF] Molnár | 2d and 3d abaqus implementation of a robust staggered phase-field solution for modeling brittle fracture[END_REF]; [START_REF] Moös | A finite element method for crack growth without remeshing[END_REF]) rather than basic computational plasticity.

shear stress: q = (σ x -σ y ) 2 + (σ x -σ z ) 2 + (σ y -σ z ) 2 + 6 τ 2 xy + τ 2 xz + τ 2 yz 2).
Based on this evolution, we have proposed a generic shape for the yield surface (Molnár et al. (2016a)):

p p y,-+ q c b -1 = 0 if p ≤ p int p-h d 2 + q e 2 -1 = 0 if p int < p (1)
In this yield surface, the tensile side of the dome is modeled by an extended Drucker-Prager model. This power law function is closed by an elliptic cap on the compression side. Under the assumption of associated plasticity, densification sets in under pure hydrostatic compression. This model will be subsequently referred to as DP-cap.

For simplicity, we have chosen to work with an associated rule. Thus equation (1) will be considered both as yield function and flow potential. This is common practice for microscopic yield criteria [START_REF] Kermouche | Mechanical modelling of indentation-induced densification in amorphous silica[END_REF]; [START_REF] Keryvin | Constitutive modeling of the densification process in silica glass under hydrostatic compression[END_REF]; [START_REF] Lambropoulos | Constitutive law for the densification of fused silica, with applications in polishing and microgrinding[END_REF]; [START_REF] Schuh | Atomistic basis for the plastic yield criterion of metallic glass[END_REF]).

The parameters for the DP-cap model are as follows (Fig. 2a). p y,-sets the tensile strength and b the power law exponent of the extended Drucker-Prager function: for b = 1 we find the standard linear Drucker-Prager model while curvature increases with b (Fig. 3a). Parameter c sets the cohesion (Fig. 3b). The three parameters of the elliptic cap d, e and h are set by the compressive strength p y,+ and the requirement that the two component functions meet smoothly at some pressure p int (Fig. 2a). Details on the governing equations can be found in our previous work Molnár et al. (2016a). As a result, the following equations can be used:

d = ∆p 2 + b • ∆p (p y,+ -∆p -p y,-) 2∆p + b • (p y,+ -∆p -p y,-) , (2)
e = c [∆p + b (p y,+ -∆p -p y,-)] p y,-• b [2∆p + b (p y,+ -∆p -p y,-)] p y,+ -∆p-p y,- p y,- b-2 2b , (3)
h = p y,+ -d. (4)
Within this framework, two simple additional features are introduced to model the complex evolution shown in Fig. 1. First the strength in compression p y,+ increases with densification as measured experimentally. Therefore irreversible volumetric strain ε pl V is used as an internal variable, as is standard in some recent constitutive relations for amorphous silica [START_REF] Kermouche | Mechanical modelling of indentation-induced densification in amorphous silica[END_REF]; [START_REF] Keryvin | Constitutive modeling of the densification process in silica glass under hydrostatic compression[END_REF]). As a result, when density saturates, the cap slides to infinity and the yield function evolves smoothly into a standard BMG-like behavior (Fig. 2b). Second, we observe that the choice of pressure p int at which Drucker-Prager and elliptic functions meet has a strong impact on the overall shape of the yield function because it sets the slope of the ellipse on the tension side. As a result, if p int is close to the tensile strength p y,-, then the elliptic cap will be prominent. If p int is far away from p y,-, then the elliptic cap is fully included inside the Drucker-Prager function which it simply closes off on the compressive side. An interesting feature is that, although the evolution shown in Fig. 1 is complicated, with a decreasing bump with increasing density, it can be modeled very simply within the DP-cap model if we define p int = p y,+ ε pl V -∆p where ∆p is a constant.

Then p int increases with p y,+ as density increases and if p int is initially close to p y,-, the initially prominent bump will decrease to finally blend into the Drucker-Prager function as densification proceeds (Fig. 2b).

The implementation of pressure and densification coupled shear models have been extensively studied in literature, thus only the main issues are addressed here. Let us note that such constitutive models have been used for granular materials, such as geological materials by [START_REF] Borja | Cam-clay plasticity, part 1: Implicit integration of elasto-plastic constitutive relations[END_REF], pharmaceutical powders by [START_REF] Wu | Numerical and experimental investigation of capping mechanisms during pharmaceutical tablet compaction[END_REF] and [START_REF] Han | A modified drucker-prager cap model for die compaction simulation of pharmaceutical powders[END_REF]. One essential -and perhaps misleading feature -of the present work is that it addresses pressure-dependence of bulk materials, which are not usually considered porous contrary to those mentioned above. However, some similarities can be found between the yield properties of granular and bulk materials. For instance, it has been shown by Nemat-Nasser and Okada (2001) that continuous shearing induces irreversible anisotropy and densification (Nemat-Nasser ( 2004)) in cohesionless sand, which was surprisingly also observed in silicate glasses using atomic scale simulations by Molnár et al. (2016a).

To implement the DP-Cap yield function in ABAQUS/Standard (ABAQUS (2011)) a user defined material model scheme (UMAT) is used. Details concerning the algorithm can be found in Appendix A.

Experimental calibration

In practice, to model a given amorphous silicate, p y,-, b, c, p y,+ ε pl V and ∆p must be determined. This quantitative evaluation of the numerical parameters -ie the calibration of the model -can be performed by comparison between numerical trials and experimental results. To that end, we need quantitative measurements for as many different types of loadings as possible. However, as stated before, one of the major constraints is the necessity to carry out these measurements at the micron-scale.

This calibration is necessary not only because of the limitations of the potentials used in the Molecular Statics calculations but also because the calculations are done without thermal activation. The experiments are conducted at room temperature, which is well below the glass transition temperature of silica, so that temperature is not expected to play a significant role in the shape of the yield ciriterion. Therefore, it may be assumed that the form of the yield function is unchanged, however the yield strength could actually be lower due to more active plastic zones.

Experimental data sets

An extensive set of possible experiments is shown schematically in Fig. 4 along with an indication of the average loading path in the p-q plane. Among these tests, we find the well known diamond anvil cell (DAC -hydrostatic compression -6) and indentation (4) experiments, along with more recently developed tests such as pillar (5) and sphere (3) compression. Also shown is uniaxial traction (1), a test of considerably greater difficulty [START_REF] Luo | Size-dependent brittle-to-ductile transition in silica glass nanofibers[END_REF]), and pure shear (2) which has not been attempted (or at least achieved) so far. Due to experimental difficulties, a reasonably consistent series of results are available only for amorphous silica, which is why we have attempted calibration of the DP-cap model for silica glass only.

Calibration procedure

The compressive strength of silica under pure hydrostatic pressure and especially its evolution with density p y,+ ε pl V (exp. (6) in Fig. 4) has been extensively studied by anvil methods, either DAC or multi-anvil devices. To take this abundant data into account we use the approximate analytical dependence proposed earlier by [START_REF] Keryvin | Constitutive modeling of the densification process in silica glass under hydrostatic compression[END_REF]: where p 0 is the initial yield pressure and p m , k and m are material parameters (see Tab. 2). We chose this function to describe the hydrostatic hardening of silica, because it fits well with atomistic simulations, where almost no pure elastic domain was found (Molnár et al. (2016a)). Different experiments put the elastic limit (p 0 ) of silica to different pressure values depending on their precision. For example densification is found around 7-8 GPa [START_REF] Rouxel | Indentation deformation mechanism in glass: Densification versus shear flow[END_REF]) indentation, and 9 GPa [START_REF] Vandembroucq | Density hardening plasticity and mechanical ageing of silica glass under pressure: a Raman spectroscopic study[END_REF]) for diamond anvil cells. Therefore to create a smooth transition between elastic and hardening domains we chose the most up to date function proposed recently by [START_REF] Keryvin | Constitutive modeling of the densification process in silica glass under hydrostatic compression[END_REF]. However, it needs to be strengthened that this sigmoidal function with p 0 = 3 GPa is only an approximation. This slight shortcoming is of no consequence for the kind of mechanical tests we are interested in here, but may lead to significant error for detailed mechanical studies near the threshold. In this case a more accurate description of the threshold is in order.The determination of p y,-is a bit more difficult to carry out since in this regime there is almost no data available at all. We therefore assume a reasonable value of -5 GPa. This choice turns out to be consistent with the (very scattered) data available [START_REF] Luo | Size-dependent brittle-to-ductile transition in silica glass nanofibers[END_REF] -exp. (1) in Fig. 4).

p y,+ ε pl V =    -ln 1 - ε pl V ε pl,max V 1 k 1/m • (p m -p 0 ) + p 0 ifε pl V > ε pl,max V ∞ otherwise, (5)
The evaluation of ∆p is more tricky and we will comment more extensively on the impact of this parameter in the discussion. Since we know that a purely elliptic model reasonably fits indentation and pillar experiments (Kermouche et al. ( 2008)), we do not expect a strong bump contribution. Therefore, we assume an intermediate value for ∆p (7 GPa) which puts the model in the monotonically increasing strength regime (Fig. 2a).

Finally, we are left with the determination of b and c. Examination of Fig. 2 and4 suggests that sphere compression (exp. ( 3)) and indentation (exp (4)) can be used for that purpose: these two types of experiments lie in a somewhat different area of the loading space where b and c both affect the response directly. As a result, we can expect a differentiation of these two parameters.

The elastic material properties for all models are taken according to Tab. 1. The finite element geometries for each test is summarized in Fig. 5. Indentation tests were computed using fully integrated 3D solid elements. To save computational time the half of the actual test is modeled. Therefore, as shown in Fig. 5a, the y-displacement is constrained on the middle plane. The remaining sides and the bottom of the sample were constrained completely. The load was applied on the top of the indenter using a displacement controlled method. For each indenter tip α and r are fixed (g = 5000 nm and α = 65.3 • for Berkovich), and the rest of the geometry is calculated according to: f = tan (α) • g √ 3 and j = tan (α) • 3g. The average finite element size of 200 nm was taken around the indenter tip.

To model sphere compression 2D axis-symmetric elements were used. The rotational symmetry is defined around axis y, as shown in Fig. 5b. The bottom of the silicon substrate is constrained in both x and y directions, while the load is applied on the top of the diamond indenter. An average of 50 nm finite element mesh size is used on the contact surface and 300 nm elsewhere.

Furthermore, to verify the calibrated parameters, micro-pillars were tested. Similarly to the sphere compression, axis-symmetric elements were used. The rotational symmetry was defined on axis y. The bottom and the right side of the substrate was constrained, while the load was applied on the top of the indenter. The pillar was meshed with an element size of 200 nm.

For all contacts a 0.1 friction coefficient was used with a Penalty formulation. We have calculated the flat punch compression of a sphere to emulate available data [START_REF] Romeis | Local densification of a single micron sized silica sphere by uniaxial compression[END_REF]). Based on the experimental results, we plot the maximum reaction force for a 0.927 micron punch penetration on a 4.17 micron silica sphere in Fig. 6b. We find that the calculated maximum reaction force is almost insensitive to the Drucker-Prager exponent b. This finding is in agreement with the quasi pure shear type of loading experienced in sphere compression. In contrast, the calculated maximum reaction force for a 2 micron deep Berkovich indentation (Fig. 6a) displays a clear dependence upon Drucker-Prager exponent b as well as cohesion c because the stress state involves more hydrostatic component. Based on the experimental values of reaction force, an optimum set of (b, c) parameters can be established (Fig. 6c and Table 2). The full loading-unloading curves calculated for the final values of the model parameters are shown in Fig. 7 for Berkovich indentation (a) and sphere compression (b). Good agreement is found with the experiments, further demonstrating that the form of the yield function is reasonable and the parameter values adequate. Yield properties b c ∆p p y,- p y,+ 5 5.7 GPa 7 GPa -5 GPa according to eq. ( 5) Initial (undensified) cap parameters d e h 4.42 GPa 5.09 GPa -1.42 GPa Positive yield pressure (p y,+ )

p 0 p m k m ε pl,max V 3 GPa 20 GPa 3 4 -0.196

Discussion

To assess the predictive power of the calibrated DP-cap model, we have performed additional calculations for other loading configurations. Results for indentation with sharper tips are shown in Fig. 8a and compared with experimental results [START_REF] Field | Determination of fracture toughness from the extra penetration produced by indentation-induced pop-in[END_REF]). Good agreement is found although the loading curve is slightly underestimated in our calculations. We also considered pillar compression. The results are shown in Fig. 8b along with the data from [START_REF] Kermouche | Perfectly plastic flow in silica glass[END_REF]. A similarly good agreement is found although the predictions again slightly underestimate the loading curve.

We observe that the results of the DP-cap model do not differ significantly from the results of the standard elliptic model by [START_REF] Kermouche | Mechanical modelling of indentation-induced densification in amorphous silica[END_REF]. When dealing with mainly compressive loadings, such as the presently available data, the models turn out very similar in effect. For silica we observe only a small pressure dependence (b = 5) in the DP-Cap model, while this can be much larger for other compositions. This is fully consistent with the atomistic simulations (Molnár et al. (2016a)). In the DP-cap model, the cohesion c = 5.7 GPa (ie the strength at zero pressure) is somewhat lower than in the elliptic model (6.5 GPa). In the DP-cap model, the derivative of the strength with pressure is positive at zero pressure, in contrast to the elliptic model where this derivative is zero. To maintain the same average response, the cohesion is therefore lower in the DP-cap model.

Along the same line of thought, we note that in the atomic scale simulations of pure silica [START_REF] Mantisi | Impact of pressure on plastic yield in amorphous solids with open structure[END_REF]), a significant bump contributes to the low hydrostatic pressure region, quite similar to Fig. 1. However we were able to model silica response with a large value of the ∆p parameter, i.e. with no bump. One reason for this discrepancy could be that strain hardening rapidly induces a reduction of the bump. More likely, the reason is that the sole datum of reaction force vs. displacement for different experimental configurations cannot discriminate between all combinations of parameter values.

A maybe more differentiating way to analyze the calculation results is to plot the spatial distribution of the stress state in the p-q plane for a given experimental configuration. As an example, three different configurations are shown in Fig. 9. For indentation, a marked high pressure tail clearly appears in the stress state distribution, which is absent in pillar compression [START_REF] Lacroix | Plastic deformation and residual stresses in amorphous silica pillars under uniaxial loading[END_REF]). This tail is due to confinement by the surrounding elastic medium which strongly limits radial plastic flow, resulting in hydro- static pressure build-up and finally densification. Indeed care must be taken that tests which occupy roughly the same region in the stress state diagram (Fig. 4) may still differ markedly because of the spread in the stress states. In this respect it is interesting to note that sphere compression is somewhat intermediate between pillar compression and indentation, with some extension of the stress state into the high pressure regime. This result is not obvious from the bare inspection of Fig. 4. In fact, the sphere geometry restores some of the confinement which was lost in the pillar. From these considerations, it appears that sphere compression may be a truly fruitful pursuit in the present field.

These results suggest that beyond force displacement data, which are the result of spatial integration over a stress state distribution, full field measurements should be developed for refined definition of constitutive relations in silicate glasses. Residual strain maps are an example of this strategy [START_REF] Perriot | Raman microspectroscopic characterization of amorphous silica plastic behavior[END_REF]). For this reason, we have investigated the impact of parameter ∆p on density distribution in Berkovich indentation. All other model parameters have been kept constant. Fig. 10 shows: a) the load displacement curves for the various values of ∆p tested; b) the density along the vertical axis (z) in the symmetry plane under the indenter. We find that increasing ∆p enhances densification. This was to be expected since densification pro- ceeds only when the elliptic cap is reached in the yield criterion, and since for large ∆p, the cap is active in a larger range of pressure. This verifies our original assumption of ∆p = 7 GPa, showing a maximum of ε pl V = 15.4 %, which compares favorably with previous experiments [START_REF] Perriot | Raman microspectroscopic characterization of amorphous silica plastic behavior[END_REF]). It is remarkable, however, that this variation is obtained without measurable impact on the load displacement curve.

Conclusion

Based on our previous atomic scale modeling of the plastic deformation of various silicate glasses, we have shown how a quantitative constitutive relation can be built by calibration of the analytical form to experimental results. Additional loading configurations have been calculated to test the reliability of the model. This generic form for constitutive relations of amorphous silicates is fully consistent with more specific phenomenological constitutive models proposed recently to model amorphous silica. It also provides relevant criteria for a larger variety of silicate glasses, with a well established physical basis. We have also shown that we can identify the constitutive parameters using a small set of micromechanical experiments which have been developed recently. Although the full set of data is only available for silica presently, it can relatively easily be extended to other silicate glasses in a near-future. Due to the increasing complexity of the constitutive models, we have also emphasized that the simpler datum of load displacement curves under various relevant loadings must be complemented by richer data sets such as strain distribution measurements. Our work also points out that experiments in the tensile regime, which are very difficult, would be most valuable at present, and that even in the case of silicate glasses (ie with modifiers) the paucity of micromechanics experiments strongly limits the accuracy of the possible descriptions. Finally, several interesting issues have not been considered here. For example, a detailed analysis of the flow rule as derived from the MD results would be a challenging increment to the present method. In a different direction, softening and the formation of shear bands would deserve specific developments as well. where C is the elastic stiffness tensor, ∇F and ∇ 2 F are the first and second gradients of the yield surface with respect to the stress tensor at the internal step j (calculated from the actual stress state σ j = σ A + ∆σ j ). The stress (∆σ) and the plastic multiplier (∆λ) increments are updated in each j iterations as follows: ∆σ j+1 = ∆σ j + δσ j+1 ∆λ j+1 = ∆λ j + δλ j+1 .

(A.4)

The aim of the above iteration is to minimize the stress residue (s) and the value of the yield function (r). Therefore, after each internal step their value is updated as well. To solve the linear equation system an LU decomposition is used The plastic strain increment is defined using an associated flow rule: dε pl = dλ∇F . Finally, when the residues are eliminated, all quantities are updated to calculate the tangent stiffness according to the following equation:

C tan = C - C∇F ∇F T C ∇F T C∇F -∂F /∂λ . (A.5)
Further information about the algorithm can be found in several textbooks discussing computational plasticity (de [START_REF] De Souza-Neto | Computational Methods for Plasticity: Theory and Applications[END_REF]; [START_REF] Krabbenhøft | Basic computational plasticity[END_REF]; [START_REF] Nemat-Nasser | Plasticity: A Treatise On Finite Deformation of Heterogeneous Inelastic Materials[END_REF]; [START_REF] Oñate | Computational Plasticity[END_REF]).

Figure 1 :

 1 Figure 1: Shear strength as a function pressure for different material densities for silica. After Molnár et al. (2016a) and Mantisi et al. (2016).

Figure 2 :

 2 Figure 2: DP-cap yield criterion in the p (pressure) -q (equivalent shear stress) space, part (a) shows the parameters of the yield function. Part (b) shows how the hardening takes place and the bump disappears with densification.

Figure 3 :

 3 Figure 3: Effect of parameters b and c on the DP-cap yield criterion.

Figure 4 :

 4 Figure 4: DP-Cap yield criterion in the space of pressure and equivalent shear stress. Different stress paths and domains are shown: 1) uniaxial tension; 2) pure shear; 3) sphere compression; 4) indentation; 5) uniaxial compression; 6) hydrostatic compression.

Figure 5

 5 Figure 5: a) 3D finite element geometry and mesh for indentation tests. α shows the angle of the indenter tip. b) Axis symmetric finite element geometry for nanosphere compression. c) Axis symmetric finite element geometry for micropillar compression tests.

Figure 6

 6 Figure 6: a) Maximum reaction force (P max ) for Berkovich indentation at h max = 2000 nm as a function of parameter c for different b values. Blue dashed line shows the experimental value ( 515 mN Field et al. (2003); Iwashita and Swain (2002)). b) Maximum reaction force (P max ) for nanosphere compression at h max = 927 nm as a function of parameter c for different b values. Blue dashed line shows the experimental value ( 34.36 mN Romeis et al. (2015)). c) Combination of parameter b and c which reproduces the experimental values correctly.

Figure 7 :

 7 Figure 7: Reaction force as a function of displacement (h). Solid black line shows the results of present work, red dashed line the results calculated using the yield criterion of Kermouche et al. (2008) and symbols represent the experimental measurements: a) Berkovich test[START_REF] Field | Determination of fracture toughness from the extra penetration produced by indentation-induced pop-in[END_REF];[START_REF] Iwashita | Elasto-plastic deformation of silica glass and glassy carbons with different indenters[END_REF]); b) Nanosphere compression[START_REF] Romeis | Local densification of a single micron sized silica sphere by uniaxial compression[END_REF]).

Figure 8

 8 Figure 8: a) Reaction force as a function of indentation depth for α = 45 • (red circles), cube corner (green triangle) tests (Field et al. (2003)). Black solid line shows the results of the simulation. b) Reaction force as a function of displacement for micropillar compression tests. Symbols show the experimental values (Kermouche et al. (2016)) and solid line the simulated ones.

Figure 9 :

 9 Figure 9: Stress state distribution for three types of loading at maximum penetration. (a) Berkovich indentation (b) microsphere compression (c) pillar compression. The figure also shows the yield criteria in the initial state and at full densification.

Figure 10

 10 Figure 10: a) Reaction force for Berkovich indentation for different ∆p values. b) Plastic volumetric strain (ε pl V ) after unloading under the indenter tip in the silica specimen for different ∆p values.

Figure

  Figure A.11: Implicit non-radial return algorithm.

Table 1 :

 1 Elastic material properties used in the finite element models.

Table 2 :

 2 Material parameters identified and used in present work.

The criterion is written as a function of two invariants of the Cauchy

Acknowledgment

This work was supported by the French Research National Agency program MultiSil (ANR-13-BS09-0012).

Appendix A. Implementation details

We divide the criterion into three parts: the extended Drucker-Prager part (p y,-< p < p int ), the left side of the ellipse (p int < p < h, where h is the center of the ellipse) and the right side of the ellipse (h < p < p y,+ ). In the first two parts the slope is positive, thus the plastic volume change is positive as well, whereas, if the slope is negative, the material densifies (ε pl V < 0, where ε pl V can be calculated by taking the trace of the plastic Hencky strain tensor). According to atomistic simulations (Molnár et al. (2016a)) positive plastic volume change does not affect the positive yield pressure, therefore when the stress path reaches the left side (either the Drucker-Prager curve or the left side of the ellipse) the equivalent plastic strain (ε pl V ), controlling the hardening, remains unchanged. As a result the implementation and the return algorithm can be separated into a left (perfectly plastic) and right (hardening) part. On the left (p < h) side a radial return algorithm is used both for the Drucker-Prager and the ellipse. On the other hand, the increasing positive yield pressure complicates the implementation even with an associated flow rule since the ellipse changes in a non-radial way. Therefore, to follow the changing gradient of the yield function, a Newton-Raphson iteration is applied to satisfy the following conditions:

Equation A.1 stands for the stress condition, namely that the vectorial sum of the predicted increment (C∆ε) and return (C∆λ∇F σ A + ∆σ ) must be equal to the final stress increment (see Fig. A.11). Unfortunately, if the gradient of the yield surface (∇F ) is different in point A and point B, this equation cannot be solved directly. Thus the yield criterion also needs to be satisfied (eq. A.2).

The equation system is solved iteratively by minimizing gradually the residues (s, r). The Jacobian of the system is updated in each j internal iteration step: .3)


Gaëlle Guigon
email: gaelle.guigon@imt-lille-douai.fr

Mathieu Vermeulen
email: mathieu.vermeulen@imt-lille-douai.fr

Jérémie Humeau
email: jeremie.humeau@imt-lille-douai.fr

A Creation Tool for Serious Puzzle Games

Keywords: Puzzle Game, Serious Game, Escape Game, Design, Tool

This article aims to present a tool for designing serious games with riddles, such as escape games. This multilingual tool will be available online freely and presented as a form on a website with a database to save and share one's projects. After completing the form, a graphic overview of the project is presented to the user. It is based on different Serious Escape Games and Serious Puzzle Games realized in the past three years and on several websites giving advice to create this type of activity. This tool is at its early stages and the prototype has been tested by a few Serious Escape Games designers on their previous projects. Feedback will be used to improve the tool. Following the validation of the prototype, computer development has begun: the tool meets the needs of the designers and fits to the different tested projects. Intended initially for teaching after a few requests, it is expected to be used by a wide audience and to respond to the various needs related to the creation of this type of activity.

INTRODUCTION

For several years, serious games have regularly been used in the field of education. Many games exist in various fields and their usefulness is no longer to justify. More recently, the Serious Escape Games (SEG) (also called Educational Escape Games), have appeared in this field [START_REF] Sanchez | Teaching and Learning with Escape Games from Debriefing to Institutionalization of Knowledge[END_REF][START_REF] Eukel | Educational Gaming for Pharmacy Students -Design and Evaluation of a Diabetes-themed Escape Room[END_REF][START_REF] Dietrich | Escape Classroom: The Leblanc Process-An Educational "Escape Game[END_REF][START_REF] Guigon | Escape Classroom : un escape game pour l'enseignement[END_REF][START_REF] Connelly | Escape Room Recruitment Event: Description and Lessons Learned[END_REF][START_REF] Paspallis | Hacking the Research Library: Wikipedia, Trump, and Information Literacy in the Escape Room at Fresno State[END_REF] and brought many benefits: cooperation, collaboration, organization, communication, reasoning, teambuilding, application of the course in a different context ... Indeed, this activity likened to a serious game, is a multi-player life-size escape game, which typically involves escaping from a room or a succession of rooms in a limited amount of time [START_REF] Borrego | Room escape at class: Escape games activities to facilitate the motivation and learning in computer science[END_REF]. To do this, a group of players must find and collect a number of clues and objects in order to solve riddles [START_REF] Guigon | A Model to Design Learning Escape Games: SEGAM[END_REF]. However, designing this type of activity is not always easy for teachers which prevents them from designing this type of activity for their students. To overcome this obstacle, we decided to create a tool to help the teachers in the designing process. The problem is to define whether a Serious Escape Game model and its reification into a tool facilitates the design of SEG for teachers? Based on the previously created SEGAM model (Serious Escape GAme Model) [START_REF] Guigon | A Model to Design Learning Escape Games: SEGAM[END_REF] (Figure 1), the tool presented in this article allows to build step by step an educational escape game or another serious game with riddles and to obtain a preview of the organization of steps, riddles and clues. To quickly present the SEGAM model, it is inspired by the DISC model (an acronym for Domain, Interaction, Scenario, Context) created by [START_REF] Vermeulen | Teachers at the heart of the learning games design: the DISC model[END_REF][START_REF] Vermeulen | Vers une approche Meta-Design des Learning Games avec le modèle DISC : de la conception à l'analyse des traces d'usage des étudiants par les enseignants[END_REF] to produce role-playing serious games with steps. SEGAM kept from the DISC model the separation between levels and the case studies are represented as riddles. Riddles are independent and a red thread is present throughout the scenario, as in the DISC model. In our knowledge, no model (other than SEGAM) and no specific tool to design SEG have been published. However, there is a real need for it, in particular for teachers and novice designers. This article propose a tool to co-design SEG with them. A first experiment made it possible to test this tool as a prototype on already realized SEG. Firstly, we present our tool and its features. The second part deals with the testing phase of the prototype and the associated feedback. Finally, we conclude with the perspectives of the project.

PROPOSITION

As a result of SEG's growing production, the creation of a tool to structure and collect all the information needed to design escape games quickly became a necessity for many teachers. In addition, most of them have no instructional designer or game designer to help them in this process. When creating such activity by themselves, teachers can get easily overwhelmed by the quantity of information to deal with. A lot of websites give tips and tricks to help build this type of activity but the information is scattered across the web. The tool proposed in this article is therefore intended to guide them step by step so that they can create a serious game with riddles (escape game type) more easily and in an organized way. The methodological approach used to conduct this research is based on Mandran's work (Mandran and Dupuy-Chessa, 2017): the THEDRE research method for Traceable Human Experiment Design REsearch. This method is based on the improvement process Plan-Do-Check-Act [START_REF] Sokovic | Quality improvement methodologies -PDCA cycle, RADAR matrix, DMAIC and DFSS[END_REF] and thus on iterative cycle with indicators to evaluate the quality of the research. Furthermore, THEDRE was developed for human centered research. In this article, we propose the results of the first research cycle and thus, the first iteration of a tool to help teachers to design SEG. The prototype (the first iteration of the tool) proposed here first appears as a form (Figure 2) written in HTML and CSS to use it on the web.

Different types of criteria are requested in simple fields:

Pedagogical. The purpose of this section is to define the general educational objective of the activity as well as the skills or learning objectives to be achieved during the course of the game. There may be prerequisites that are important to define beforehand to conceive the riddles. For a serious game, these elements are essential because they will guide all the riddles and help select the content to be treated during the activity. It is important to focus on this aspect as the riddles will be the pillars of the activity and these will be based on the educational content.

Various Constraints.

Many constraints are to be taken into account for the creation of this type of activity and will affect in particular the format of the game: the available time, the number of sessions, the number of learners, the place, the budget, the supervisors during the session, etc.

Background. Here, it is a question of defining the global plot, the scenario in which the learners will evolve: what is the initial situation, the goal of the game, what will happen in case of failure ? Are there any important characters in the script? Is the game collaborative or competitive? Keeping in mind that the game can be competitive and educational, several teams fighting for the same goal.

Organization. In this part, the designers will define their project team, information concerning the tests and the reengineering to be carried out before the implementation of the activity. Indeed, the tests are a key step in the design of an activity of this type because the testers (having a profile as close as possible to the target audience) will be able to give their feedback on the activity and each riddle will then be tested: are the clues explicit enough ? Is there any challenge inducing a state of flow [START_REF] Csikszentmihalyi | Flow: The Psychology of Optimal Experience[END_REF])? This step will also show the robustness of the clues and if the reasoning of the designers is the same as the users'. Then, it is the reengineering step, and thus the changes needed. Some may be done quickly, others may be only done for the next session, requiring more time to achieve them.

Structure. Once the previous elements are defined, the designer will be able to structure his activity: how many steps will be necessary, what will be the riddles that will compose them. The latter will be associated with prerequisites and pedagogical objectives defined beforehand. Another important element is the definition of the clues to solve the riddles: their form, the cost they represent, the step in which they will be discovered in the game and where will they be hidden.

Educational and Financial Report.

Finally, once all the elements are defined, the tool offers a financial statement to check that the forecasts for the equipment are compatible with the allocated budget. And there is also a pedagogical review to make sure that all the objectives and skills initially defined are properly treated during the activity.

It has to be noted that most fields are optional, so the designer can only enter information that interest him. Only some information concerning the steps, the riddles and the clues are required because they make it possible to generate the representation with the SEGAM model. Moreover, there is no order to fill the form, the designer can fill the fields in the order of his choice. Thus, in a second step, thanks to the filled criteria, the model SEGAM is completed with the different elements of the escape game: steps, riddles and clues (Figure 3). Clues referring to the same riddle have the same background color. They can be distributed in the steps preceding the solving of the riddle in question and not only at the step of the riddle to be solved. This brings some complexity for the players who must then use them at the appropriate moment. Notice that the SEGAM model has evolved from its original version and now the term "Levels" is replaced by "Steps"". The term "steps" is more representative because the concept of level could induce a notion of difficulty, which is not necessarily the case from one activity to another.

The tool must be practical and functional, but also intuitive and quick to take in hand in order to be used by everyone. Based on the prototype, the first version consists in obtaining a form as complete as possible and meeting the expectations of the target audience (mainly teachers originally). The basic outcome of the form is the pdf export to keep track of the work done or to print it if necessary. A second version is being developed. It will make the tool more ergonomic and easier to use, offering the possibility to add or delete steps, riddles or clues directly from the SEGAM model and affecting the associated fields in the form. Moreover, the technology used to create the tool has evolved in order to have a fast and efficient deployment. Angular allowed that, it is a maintainable framework, with a large community. The project will be easier to manage for the next evolutions. Finally, the tool will remain in responsive design, and therefore easily accessible on smartphones, tablets and computers.

TESTS AND FEEDBACK

The tool was tested at first with several Serious Escape Games and treasure hunts made by our team. Three of them were created according to the SEGAM model. The co-organizers of these SEG were the first testers. Then the tests were expanded to other puzzle games not designed with the SEGAM model. Here is some feedback from these tests: Overall, the tool is comprehensive and the user understands easily its operation. He feels guided and all the information necessary to the conception of the activity is present. This tool seems to give inspiration to the designers, discovering fields in the form they did not think about. Here are some improvements for each section of the form:

Background. Basically the activity is intended to have only one end goal, assuming that all learners play for a common purpose. However, by giving them the idea that there may be multiple goals, this can inspire designers to create different scenarios: teams fight for different goals, or some players have different roles and goals from the other players. The target audience of this tool is looking for inspiration to create such activities and will therefore be fond of tracks for their scenario.

Organisation. It would be interesting to have a checklist in order to make the management of the changes easier in the "Reengineering" part. The progress of the improvements would thus be more visual and practical. • If the activity has to be played by several teams simultaneously, it is possible that riddles are nearly the same (to avoid cheating for instance). To save time for designers, the clues and riddles should therefore be duplicable and the possibility of indicating whether a particular piece of data changes from one team to another should be added. 5 is the same for all, but the electrical signals being different for the three entries, the final solution will be different for each group, while treating exactly the same course notions.

• For the sake of clarity and to decrease the mass of displayed information, it would be wise when you enter the number of steps in the tool, to have the corresponding number of buttons below. Thus, when one clicks on one of these buttons, the part "Riddles" of the form appears. In this way, each riddle is placed in the corresponding step. This avoids having a very long form with all the riddles of the game afterwards, making the navigation very ergonomic.

• Moreover, in the same spirit, the fact of displaying the questions by groups for the riddle part would make this part less impressive by the number of criteria to be informed. Indeed, it would be possible to display the questions step by step and thus the questionnaire would seem lighter and easier to handle.

• To have a better visualization of the construction of the activity, having the representation with the SEGAM model always visible (on computer and tablet) would help to see the progress of the structure of the game. The designer would thus have a direct return of his actions making easier the reading of the model. Representation. This is the most attractive part of the tool, one that users will want to take in hand quickly.

During the creation of the tool this part was the focus of the design. The aim was to get the designer motivated to use this tool rather than a sheet of paper. Rolland Viau's works [START_REF] Viau | La motivation en contexte scolaire[END_REF], showed that motivation is necessary to persevere and to reach one's goal, that's why this tool put the emphasis on that matter through its practical and ergonomic aspects. The fact that the tool is accessible online at any time on any device, shareable and recordable will provide a significant advantage for users. They will be able to print only the elements useful for them.

• To facilitate the understanding that each riddle unlocks a new step, one could add a padlock icon opened at the end of a riddle on the line between the last step of the riddle in question and the next step. When hovering or clicking on this padlock, the detail of the unlocked object would be displayed.

• The user may want to consult the constraints quickly from the "Representation" part, an option to display the list of these constraints could be useful (mainly on the computer and tablet version but less convenient on the mobile version).

• From the moment the user deletes a clue in the SEGAM model, he should have the possibility to reorder clues numbers. If he chooses to do so, then he could do it manually: choose which clue takes the number of another deleted or automatic: all numbers are shifted to compensate for missing numbers.

• Then, to facilitate the management of items in the SEGAM model, it would be interesting to be able to drag and drop clues from one step to another or to reorder the riddles by dragging a line and place it elsewhere.

• Finally, to facilitate the management of groups, it would be practical to be able to duplicate riddles or clues and thus manage the different parameters from one team to another. Knowing that all changes made within the representation with the SEGAM model would be reflected in the form.

Operation

• It would be interesting for new users to have access to an optional tutorial to briefly explain the functions of the tool.

• Some fields of the form may not have the same meaning for different users, so it would be useful for them to have an example of the form filled with a real project to be inspired and understand what is expected.

• In the same spirit, it might be interesting to have an explanatory bubble next to each field for a better understanding of the criteria.

Extension

• The tool can be used for puzzle games without educational purpose, some sections of the form will be no longer essential in this case.

• It may be interesting to add a menu with improvements planned in future versions of the tool, as well as a place for users to make suggestions for enhancement. The version of the tool would thus be displayed and would make it possible to realize if the tool has benefited from improvements since the last use.

• The goal is to give a maximum of elements so that the designers can take in hand riddles activities.

For example regarding the escape game type, it would be useful to add advice, tips and tricks to the "Help" category. For instance with elements concerning the introduction of the game to the public like security advice classically stated, or useful elements for the final debriefing. Indeed, debriefing is essential [START_REF] Lederman | Debriefing: Toward a Systematic Assessment of Theory and Practice[END_REF][START_REF] Crookall | Serious Games, Debriefing, and Simulation/Gaming as a Discipline[END_REF] because the teacher will come back on each riddle met during the activity and explain the course notions and expected objectives. Rewinding each riddle will allow people who have not solved this riddle (as they were solving another one in parallel for example) to return to the course notions that he could not address and get feedback on the notions seen by those who solved them.

Thus the debriefing will make them aware of their learning, they will realize as well that they do not come only to "play" but also to review several notions of course and their detail.

Following these tests, the most relevant changes to help designers create their activity will be integrated in the next version of the tool, the others will be added later. For now, a tester wanted to keep the prototype to start a new project. Then, an instructional designer heard about the project. She would like to have quick access to this tool to test if her previous Escape Games fit in the tool and to help her designing the next ones. These first returns seem to confirm the important need of this type of tool and will allow to develop it according to feedback from the user community.

CONCLUSION

Given the first tests, this tool seems to facilitate the design of SEG for teachers, being more guided to address all the elements essential to the creation of this type of activity. This tool will evolve with time and user feedback, especially those mentioned above in the "Tests and feedback" section. Improvements are already planned: the third version of the tool will ask to be authenticated on the site thus allowing to save the project. Designers will be able to work on it in several times. It is planned to include an automatic backup to prevent unexpected data loss. Thanks to a database, each user will be able to manage several projects, to share them with other people, in public or private mode, giving the rights of modification or not. Another function will be the ability to archive a completed project: it will be saved separately, and available read-only. People with access could then find it if necessary without cluttering their list of projects in progress. Finally, users will have the option to delete or duplicate a project if they want to create a variant. Other more technical improvements are planned to improve ergonomics and to consult, create, modify or delete elements even more quickly with greater ease than before, especially thanks to the SEGAM model. To facilitate the organization of the project, it is also planned to select the parts of the form that you want to export in pdf: for example only riddles and clues, or the list of clues, the place of their hiding place as well as associated codes for better management of the elements on site during the activity. These first elements were inspired by the different SEG realized in various contexts as well as some websites helping to design escape games (AcadémieDeParis, 2018;[START_REF]Aide pour créer son escape game ou jeu d'évasion pédagogique[END_REF][START_REF] Lelivrescolaire | THEDRE: A Traceable Process for High Quality in Human Centred Computer Science Research[END_REF][START_REF] Quesne | Escape n'games | Ressources pour jeux d'évasion[END_REF]. The SEGAM model was used to build the structure, but many other elements were written on separate sheets and were useful during the design or implementation of our SEG. This tool makes it possible to centralize all the data concerning the escape game, to be accessible on mobiles, tablets and computers, by several people and the content can be updated regularly and easily. The next step is to spread it widely to help as many people as possible create serious puzzle games and get their feedback to make it evolve and meet the needs of as many users as possible. Then, based on the escape games that were designed with the tool, an analysis will be made thanks to the collection of user traces (students and teachers). This analysis will help to classify the SEG and to determine what type of SEG to use based on: educational objectives, the type of activity (discovery, learning or evaluation) or the type of skill (soft or hard). The results of this analysis will also allow to classify the riddles (for example, based on intrinsic or extrinsic metaphor [START_REF] Fabricatore | Learning and videogames: An unexploited synergy[END_REF]). Thus, it would be interesting that the tool, through these elements, guides users to create riddles according to their needs by proposing similar generic elements.

Figure 1 :

 1 Figure 1: SEGAM, Serious Escape GAme Model.

Figure 2 :

 2 Figure 2: Screenshot of the tool.

Figure 3 :

 3 Figure 3: Representation of the project.

Structure•

  In the current version, the possibility of having a clue used in several riddles is missing. This option should be selected in the edition of the clue in the form, giving a multicolored background to this type of clue in the representation with the SEGAM model. Each clue of the SEGAM model would have a different number, except those present in several riddles, which would then be duplicated in the SEGAM model but not in the form.

  Figures 4 and 5 illustrate this possibility with a riddle on logic gates for the purpose of displaying a digit. Indeed, Figure 4 shows the different parameters depending on the groups: Group 1 has the parameters: a = 0, b = 0, c = 0; group 2 has: a = 0, b = 0, c = 1 etc. Thus the diagram in Figure

Figure 4 :

 4 Figure 4: Settings of the riddle.

Figure 5 :

 5 Figure 5: Riddle on logic gates.