Thème COM -Systèmes communicants Projets Mascotte

Keywords: P2P storage system, data placement, performance evaluation, data durability système de stockage pair-à-pair, P2P, placement de donnés, évaluation de performance, durabilité des données

Large scale peer-to-peer systems are foreseen as a way to provide highly reliable data storage at low cost. To achieve high durability, such P2P systems encode the user data in a set of redundant fragments and distribute them among the peers. We study here the impact of different data placement strategies on the system performance when using erasure codes redundancy schemes. Several practical factors (easier control, software reuse, latency) tend to favor data placement strategies that preserve some degree of locality. In this paper, we compare three policies: two of them local, in which the data are stored in logical neighbors, and the other one, global, in which the data are spread randomly in the whole system. We focus on the study of the probability to lose a data block and the bandwidth consumption to maintain such redundancy. We use simulations to show that, without resource constraints, the average values are the same no matter which placement policy is used. However, the variations in the use of bandwidth are much more bursty under the local policies. When the bandwidth is limited, these bursty variations induce longer maintenance time and henceforth a higher risk of data loss. We then show that a suitable degree of locality could be introduced in order to combine the efficiency of the global policy with the practical advantages of a local placement. Finally, we propose a new external reconstruction strategy that greatly improves the performance of local placement strategies.

Introduction

The key concept of Peer-to-Peer storage systems is to distribute redundant data among peers to achieve high reliability and fault tolerance at low cost. The addition of redundant data could be done by trivial Replication [START_REF] Rowstron | Storage management and caching in past, a large-scale, persistent peer-to-peer storage utility[END_REF][START_REF] Dabek | Wide-area cooperative storage with CFS[END_REF][START_REF] Bolosky | Feasibility of a serverless distributed file system deployed on an existing set of desktop pcs[END_REF], in which identical copies of data are sent to different nodes in the system; or be based on Erasure Codes [START_REF] Luby | Practical loss-resilient codes[END_REF][START_REF] Weatherspoon | Erasure coding vs. replication: A quantitative comparison[END_REF], such as Reed Solomon and Tornado, as used by some RAID schemes [START_REF] Patterson | A case for redundant arrays of inexpensive disks (raid)[END_REF]. When using Erasure Codes, the original user data (e.g. files, raw data, etc.) is cut into data-blocks that are divided into s initial fragments (or pieces). The encoding scheme produces s + r fragments that can tolerate r failures. In other words, the original data-block can be recovered from any s of the s + r encoded fragments. In a P2P storage system, these fragments are then placed on s + r different peers of the network. In this work, we focus on the analysis of systems that uses Erasure Codes as they are usually more efficient in terms of storage overhead (see [START_REF] Weatherspoon | Erasure coding vs. replication: A quantitative comparison[END_REF]).

To keep a durable long-term storage despite disk failures, the system must be capable to maintain a minimum number of fragments available in the network. This means that the system continuously monitors the number of fragments of each data-block. This control is done in a distributed way by the means of a Distributed Hash Table (DHT) [START_REF] Liben-Nowell | Analysis of the evolution of peerto-peer systems[END_REF]. If this number of fragments drops below a certain level, the block is reconstructed. After the reconstruction, the regenerated missing pieces are spread among different nodes. A fundamental question for such systems is how much resource (bandwidth and storage space) is necessary to maintain redundancy and to ensure a given level of reliability?

It has been shown that fragment (or replica) placement has a strong impact on the system performance [START_REF] Douceur | Competitive hill-climbing strategies for replica placement in a distributed file system[END_REF][START_REF] Lian | On the impact of replica placement to the reliability of distributed brick storage systems[END_REF]. In this paper, we study three different strategies of data placement. The first, a global & random placement policy, spreads the fragments on peers taken randomly among all the peers of the system (see [START_REF] Alouf | Performance analysis of peer-to-peer storage systems[END_REF][START_REF] Van Renesse | Efficient reliable internet storage[END_REF][START_REF] Chun | Efficient replica maintenance for distributed storage systems[END_REF]). The other two, namely Chain policy and Buddy policy, distribute the fragments among a closed set of neighbor peers, and henceforth are designated as local. The Chain policy corresponds to what is done in most distributed systems implementing a DHT (see [START_REF] Rowstron | Storage management and caching in past, a large-scale, persistent peer-to-peer storage utility[END_REF][START_REF] Dabek | Wide-area cooperative storage with CFS[END_REF][START_REF] Douceur | Large-scale simulation of replica placement algorithms for a serverless distributed file system[END_REF]). The Buddy policy roughly corresponds to RAID systems.

The use of the Global strategy allows to distribute more uniformly the load among peers, leading to a faster reconstruction and a smoother operation of the system [START_REF] Chun | Efficient replica maintenance for distributed storage systems[END_REF]. However, the use of local strategies brings practical advantages [START_REF] Dabek | Designing a DHT for low latency and high throughput[END_REF]. For instance, the DHT update mechanisms of the leafset can be used to simplify the management of the system (e.g. to know the states of the blocks stored locally). Also, the management traffic and the amount of meta-information to be stored by the nodes are kept low. Basically, their complexities (i.e. time, bandwidth, and space overhead) are all in O(s + r). Conversely, for the Global placement, it is O(N ), with N the number of peers in the system. Since routing is done directly among known nodes of the leafset, there is no massive use of the slow routing algorithms. Hence, the induced delay of the control traffic is kept low and this gives a better latency to access the data.

We study these policies for two different scenarios. In the first one, provisioning scenario, peers do not have bandwidth constraints. It allows to estimate the bandwidth use for different sets of parameters. The second scenario, where peers have resource constraints, corresponds to the operation of practical systems.

Our contributions are the following:

• As far as we know, we present the first practical study of data placement for systems using Erasure Codes. We show that, even for local policies, they experience less data loss than replication schemes with the same resources.

• We show that, without bandwidth constraints, the distribution of the bandwidth usage among peers is much more smoother for the Global policy, moreover, all policies have the same average bandwidth consumption and probability to lose data. However, the mean time between data loss events is much longer for the local policies.

• When limiting the maximum available bandwidth per peer, we exhibit that the Global policy experiences a lot fewer data loss than the local policies for similar available resource. In addition, the loss events for local policies are much more frequent when compared to the provisioning scenario (in certain cases even more frequent than for the Global).

• We then discuss the size of the leafset in the local policies. We show that these policies can be adapted to achieve performances close to the Global placement, while keeping the practical advantages of locality.

• Finally, we propose a new reconstruction scheme, namely external reconstruction, which reduces by 40 to 50 percent the number of block losses when using the local policies.

The remainder of this paper is organized as follows: after presenting the related work, we describe the system characteristics in the next section. In Section 3.1 we study the behavior of the system without resource constraints, and then under bandwidth constraints in Section 3.2. Finally, we propose some improvements of the placement and reconstruction architectures in Section 4, followed by our conclusions.

Related Work.

The majority of existing or proposed systems, e.g. Intermemory [START_REF] Goldberg | Towards an archival intermemory[END_REF], CFS [START_REF] Dabek | Wide-area cooperative storage with CFS[END_REF], Farsite [START_REF] Douceur | Large-scale simulation of replica placement algorithms for a serverless distributed file system[END_REF], Pastry [START_REF] Rowstron | Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems[END_REF], TotalRecall [START_REF] Bhagwan | Total recall: System support for automated availability management[END_REF], Glacier [START_REF] Haeberlen | Glacier: highly durable, decentralized storage despite massive correlated failures[END_REF], use a local placement policy. For example, in PAST [START_REF] Rowstron | Storage management and caching in past, a large-scale, persistent peer-to-peer storage utility[END_REF], the authors use the Pastry DHT to store replicas of data into logical neighbors. In the opposite way, some systems use a Global policy, as OceanStore [START_REF] Kubiatowicz | OceanStore: an architecture for global-scale persistent storage[END_REF] or GFS [START_REF] Ghemawat | The google file system[END_REF]. GFS spreads chunks of data on any server of the system using a pseudo-random placement.

Chun et al. in [START_REF] Chun | Efficient replica maintenance for distributed storage systems[END_REF] also discuss the local placement (namely small scope) impacts. They state that local placement is easy to maintain but induces higher reconstruction times. Conversely, larger scope (Global policy) has lower reconstruction time and henceforth higher durability. However, they do not address the impact of different bandwidth limits, neither Erasure Codes redundancy. In [START_REF] Lian | On the impact of replica placement to the reliability of distributed brick storage systems[END_REF] the authors study the impact of data placement on the Mean Time to Data Loss (MTTDL) metric. They show that the MTTDL is lower for the Global policy (called random placement) when compared to the local policy (called sequence). But they do not discuss other very important metrics: the probability to lose a block and the bandwidth usage.

INRIA

There are also other studies that evaluate the replica placement, however with focus on the lookup latency and/or throughput performance [START_REF] Van Renesse | Chain replication for supporting high throughput and availability[END_REF]. Others are focused on Content Delivery Networks [START_REF] Karlsson | Do we need replica placement algorithms in content delivery networks[END_REF], which is not our case here. We aim at analyzing P2P storage systems to achieve high durability and availability at low cost in bandwidth usage.

System Description

The System

The detailed characteristics of the studied P2P storage system are presented in this section. Data Redundancy. Erasure Codes schemes [START_REF] Luby | Practical loss-resilient codes[END_REF] are used to introduce data redundancy in the system. The user data is cut into data-blocks. Each data-block is divided into s initial pieces, then r pieces of redundancy are added, in such a way that the initial block can be reconstructed from any subset of s pieces among the s + r. The pieces are then sent to s + r different peers according to one of the three data placement policies of study. Failures. It is assumed that the nodes stay connected almost all the time into the system. So, we model the case of peer failures, mainly caused by a disk crash or by a peer that definitively leaves the system. In both cases, it is assumed that all the data on the peer's disk are lost. Following most works on P2P storage systems [START_REF] Alouf | Performance analysis of peer-to-peer storage systems[END_REF][START_REF] Lian | On the impact of replica placement to the reliability of distributed brick storage systems[END_REF][START_REF] Ramabhadran | Analysis of long-running replicated systems[END_REF][START_REF] Picconi | Predicting durability in dhts using markov chains[END_REF], peers get faulty independently according to a memoryless Poisson process. Given a peer failure rate λ, the probability for a peer to be alive after a time T is given by e -λT . To avoid the problem of transient failures and deal with churn, a peer is just considered lost if it has left the system for a period longer than a given timeout [START_REF] Rodrigues | High availability in dhts: Erasure coding vs. replication[END_REF] (set to θ = 12 hours in our simulations). As failures happen continuously in a large system, it is essential to the system to monitor the data-blocks' state and maintain the redundancy by rebuilding the lost fragments. Reconstruction Strategy. Different reconstruction strategies can be considered. Delaying the reconstruction (i.e. waiting for the block to lose more than one fragment before rebuilding it) amortizes the costs over several failures. Hence, we study a saddle based pol-b1 b2 b1 b2 b1 b2

Global Chain Buddy

Figure 1: Placement of two blocks b1 and b2 in the system. Global: s + r fragments are placed at random among all peers; Chain: fragments are placed on s + r neighboring peers; Buddy: many small subsystems of size s + r, in this case all peers inside each small group contain the same data.

icy in this paper. When the number of fragments of a block drops to a threshold value r 0 , the reconstruction starts. Note that, when r 0 is set to r -1, the reconstruction starts as soon as a first piece is lost. This special case is called eager policy. Setting a low value for r 0 decreases the number of reconstructions (as the reconstruction starts only after that r -r 0 pieces are lost), but increases the probability to lose a block. The reconstruction is done in three consecutive phases: the retrieval, the recoding and the sending. First, the peer in charge of the reconstruction has to download s fragments among the remaining block's fragments (retrieval). It then recodes the block (decoding). Last, it sends the reconstructed fragments to peers (sending). We consider here that the CPU recoding time is negligible. Therefore the reconstruction time is the sum of the retrieval and sending phases. Control. Some sort of Distributed Hash Table substrate is assumed to be implemented, so the management of the system is distributed. In this paradigm, the control traffic per peer has order of Θ(log N ). As an example, to monitor a peer, it is sufficient to have log N other peers in charge of it, e.g. pinging it periodically: if it stops to answer, this information is forwarded to all the peers, which could be done using the standard error tolerant broadcasting. The factor log N is a classical redundancy factor to handle failures in DHT, that allows to maintain the redundancy level of the data-blocks and peers' state. Since the traffic induced by the fragments transfers of the reconstructions is much bigger than the control traffic, this later can be considered negligible here.

Data Placement Policies

The different placement policies studied in this paper are detailed in the following and depicted in Figure 1.

INRIA

• Global Policy: The s + r pieces of a block are sent to s + r peers chosen uniformly at random among all the N peers present in the system. In this case, the peer in charge of monitoring the state of a block and reconstructing it is also selected among all peers in the system;

• Chain Policy: In this local policy, each block is managed by a given peer (e.g., the peer with id in the DHT closest to the block id). Its fragments are stored on the s + r "logically" closest (consecutive) neighbors. Note that these neighbors are also in charge of monitoring and reconstructing these blocks.

• Buddy (or RAID) Policy: This is an extreme case of a local policy, in which the system is composed of small independent subsystems with s + r peers each. It could be seen as a collection of local RAID like storage. In this situation, each peer stores pieces that belong to the s + r peers in the group. To simplify the analysis, we only study system sizes multiple of s + r. In this way, each Buddy group contains the same number of peers (otherwise, one of the group has more peers). This does not change the analysis as soon as N is large enough.

Simulations

To evaluate such a system, we developed a custom cycle-based simulator that implements all the characteristics described in Section 2.1. The simulator models a detailed view of the system, as it monitors the state and the localisation of each fragment individually. Monitored metrics. The simulator keeps detailed traces of different performance metrics.

To be sure that we are studying a system in a steady state, the first part of the simulation traces is thrown away. We focus our analysis on three main metrics:

• Bandwidth: Average bandwidth consumption per peer, i.e., estimated from the number of pieces transmitted and received per hour due to the reconstruction process;

• FDLPY: Fraction of Data Loss Per Year, which gives the probability to lose a datablock per year;

• MTTDL: Mean Time To Data Loss, i.e., the period of time between two occurrences of data loss in the system.

Simulation parameters. We did a large number of simulations for different sets of the parameters. The default parameter values used in the simulations are given in Table 1, otherwise they are explicitly indicated. The amount of stored data and the number of peers are kept constant during the simulation, this means that dead blocks are re-injected in the system. Crashed disks reappear empty. The size of a user data block is 3.6MB. Thus, with s = 9, the fragment size is 400KB. With redundancy r = 6, the system block size will be 6MB. Two remarks on the choice of the parameter values:

Remark 1 (Size of the simulated system) In practice, peers have huge disks of tens of Gigabytes, each one containing tens of thousands of blocks. Furthermore a real system with 1000 peers would deal with tens of millions of fragments. As we want to be able to simulate a storage system for several years in a reasonable time (for instance, our simulations correspond to 20 simulated years and the time granularity is 1 hour), we chose a disk size around 100 times smaller than the one expected in practice. Each peer stores only 1500 fragments in the system, which still corresponds to a total of 1.5 millions of fragments and 571GB of data. Note that the upload bandwidth (BW up spans from 6 to 18 kbit/s in our experiments) directly derives from this choice: disks containing 100 times more data would need a peer bandwidth 100 times larger to maintain the redundancy, that is already in order of Mbits/s and close to the bandwidth limits encountered in practice.

Remark 2 (Measuring block losses) The parameters of real systems are set in such way that the occurrence of a data loss is a very rare event. As it is impossible to simulate in a reasonable time events of very low probability, for example 10 -15 , we chose non realistic values for some parameters (in particular, the reconstruction saddle r 0 = 2 and the disk M T BF = 90 days are set very low). In this way, we experience data loss in our simulations. Of course, real systems would have a completely different probability to lose blocks than the one reported here for the sake of comparison.

Peer bandwidth. We model the bandwidth as a resource constraint per peer, and not as a global shared link constraint as is done in [START_REF] Lian | On the impact of replica placement to the reliability of distributed brick storage systems[END_REF][START_REF] Ramabhadran | Analysis of long-running replicated systems[END_REF]. Each peer has a maximum upload and download bandwidth, resp. BW up and BW down . We assume asymmetric capacities, as often encountered in practice, e.g. ADSL lines (in our experiments BW down = 5BW up ). So the limiting resource is the upload bandwidth and it is the one presented in our results.

When the peer's bandwidth is limited, not all blocks can be reconstructed at the same time. To model a peer's bandwidth, we implemented a non blocking FIFO queue with one server: when there is a peer failure, the blocks to be reconstructed are put in the queues of the peers in charge of the reconstruction.

Simulation Results

In this section, we evaluate the three data placement policies for the three following metrics: use of bandwidth, number of dead blocks, and mean time to data loss. First, we study the provisioning scenario (unlimited bandwidth) in Section 3.1, which is important to measure the required bandwidth to maintain the system. In the following, we use these values to analyse scenarios with constrained resources, in Section 3.2.

Without Resource Constraints

Briefly, the results shown here are: (1) the three placement strategies have the same value of average bandwidth demand; [START_REF] Bhagwan | Total recall: System support for automated availability management[END_REF]

Average Bandwidth Usage

The left column of Table 2 shows the average value of upload bandwidth usage across peers during time (i.e., at each time step we measure the average number of fragments transmitted by each peer), along with the experimental standard deviation (in parenthesis). First, as expected, the average bandwidth use across peers is roughly the same for all policies, 1.99 kbit/s. The reason is that the different placement policies do not change the number of pieces that have to be reconstructed, but they change the repartition of these pieces among peers. However, the variations are not the same. The Chain policy and Buddy policy variations are significantly higher, respectively, 9.5 and 11.8 times more than the Global policy. Figure 2 gives an explanation of this behavior. It depicts the bandwidth usage of the 1005 users of the system at a typical instant of time for the three different policies under the same fault scenario. We see that the load is around 2 kbit/s for all the users and all strategies. However, we see that the distributions of the bandwidth are not the same at all.

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •
Global • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • 0

Chain

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •
In the case of the Global policy (top graph), the pieces of the blocks are placed among all the peers in the system. Consequently the load of the retrieval phase of the reconstruction is uniformly distributed among all peers. Furthermore, the peers in charge of a block reconstruction are also randomly chosen among all peers. So the sending phase of the reconstruction is also evenly distributed. In the example, the std. deviation of the bandwidth to the Global is 1.34 kbit/s.

On the opposite (bottom graph), in the Buddy setting, some groups of s + r users have a very high bandwidth demand, e.g. around 1500 kbit/s. We can identify three groups that correspond to three different sets of peer crashes that triggered reconstructions. In the Buddy policy (similarly to RAID systems), when a failure happens, only the immediate neighbors possess the remaining pieces of the blocks. Moreover, these neighbors are also in charge of the reconstructions, leading to a very high bandwidth load on these peers, while the others peers in the system are spared 1 .

The situation for the Chain policy (middle graph) is similar to the Buddy. We also observe three spikes for certain subsets of users. But, differently, these spikes (1) involve more peers and ( 2) have shapes of pyramids. It is explained as follows. (1) A peer stores fragments of blocks that are managed by peers at distance s + r (chain size). In addition, a block reconstruction affects peers at distance s + r. Hence, when a peer crashes, peers at distance 2(s+r)-1 contribute to the reconstruction. [START_REF] Bhagwan | Total recall: System support for automated availability management[END_REF] The spikes corresponds to multiple disk failures. In this scenario, peers close to several failed peers contribute more than peers close to a single failed peer. Hence, the pyramid shaped spikes. To conclude, we see that a peer failure is a quite big local event for the two local policies.

Probability to Lose a Block

We then compare the probability to lose a block in the three different policies. The results are shown in the middle column of the Table 2, normalized as the Fraction of Data Loss Per Year (FDLPY).

When there is no bandwidth limit, the expected number of dead blocks is the same for the three policies (roughly 0.04% of blocks lost per year). As a matter of fact, the probability for a block to die does not depend on where its fragments are placed. It can be easily calculated using a Markov Chain Model, see for example [START_REF] Alouf | Performance analysis of peer-to-peer storage systems[END_REF]. But, we note that the deviations during time of the number of dead blocks is higher for local policies. To explain that, we look at the MTTDL.

Mean Time To Data Loss (MTTDL)

The measure of the time between two occurrences of data loss shows that the three policies have very distinct behaviors, as depicted in the right column of Table 2. In our simulations, the Global policy loses a data-block every 9 days, the Chain policy every 4 years and Buddy every 25.8 years. However, as we have seen before, the three policies have in average the same number of dead blocks per year. In other words, the average quantity of data loss per year is the same, but the distribution across time of these losses is very different. Figure 3: Illustrative example of the cumulative number of dead blocks for a period of three years.

The Figure 3 illustrates an example of the cumulative number of dead blocks for a period of 3 years for the three placement policies under the same fault scenario. We see that the loss occurs regularly for the Global policy. Conversely, they occur very rarely for the Buddy placement, but, when they occur, they affect a large batch of data. Basically, all the blocks of a small buddy subsystem of size s + r peers lose all their blocks at the same time. The behavior of the Chain policy is somewhere in the middle of both.

It has also to be noticed that, due to its very large variations of behavior, the buddy policy has the drawback of being not very predictable. We see in Figure 3 that the Global and the Chain policies experienced around 2,000 block losses after 6 years, when the Buddy policy experienced almost 4,000. Even if they have the same probability to lose data. The values for the local policies (Chain and Buddy) are higher, and decrease gradually with the increase of the available bandwidth. The unlimited value of 1 is the granularity of our simulator (one hour).

Results under Resource Constraints

In this section, we study the behavior of the system with bandwidth limitation per peer (meaning that now each peer has a maximum upload and download bandwidth). In this context we show that, using similar available resources, the amount of data loss is no more the same for the three data placement policies. The Global policy behaves considerably better in comparison to the Chain and Buddy policy. Furthermore, the local policies now experience more loss events (smaller MTTDL).

Reconstruction Time versus Bandwidth

Figure 4 gives the average reconstruction time for different upload bandwidth limits BW up , ranging from 6 kbit/s to 18 kbit/s. The unlimited bandwidth value is given for the sake of comparison.

We see that the average reconstruction time is a lot longer for the Chain policy and even more for the Buddy policy when compared to the Global one. As an example, for a maintenance bandwidth of 6 kbit/s, the reconstruction time is around 49 hours for the Chain policy and 82 hours for the Buddy, but only 2 hours for the Global policy. This bandwidth limit corresponds to three times the average bandwidth usage of the system (as computed without resource constraints). Hence, we see that the irregularity of the reconstruction load among peers has a very strong impact on the reconstruction time, even if each policy has the same average bandwidth demand. For a bandwidth limit of 18 kbit/s, which represents 9 times the average bandwidth needed, the difference is still very large: 1, 14, and 30 times for the Global, Chain and Buddy, respectively. Thus, under resource constraints, the big local events constituted by peer failures induce longer reconstruction time and henceforth an increase of data loss when using the local policies, as shown in the following.

FDLPY versus Bandwidth

A critical performance measure of a P2P storage architecture is the probability to lose a block for a given amount of bandwidth. Figure 5 compares the trade-offs of the three policies for different values of BW up . We see that the Global policy behaves a lot better for any bandwidth limit than the Chain policy, which itself is more efficient than the Buddy policy. For example, for a bandwidth limit of 18 kbit/s (which represents 9 times the average bandwidth need of the system), the Global experiences 0.04% of data loss per year, to compare with 0.78% and 3.2% for the Chain and the Buddy, respectively.

MTTDL versus Bandwidth

Opposed to what was showed without bandwidth constraints, the Global policy behaves better than the others with low bandwidth limitations. For instance, without resource constraints, the time between data loss were 0.02, 4.0, and 25.8 years respectively for the Global, Chain and Buddy. Conversely, with an available bandwidth of 6 kbit/s, these values are 166, 53, and 75 (in hours), many orders of magnitude less. These results show that the impact of the bandwidth limits per peer needs to be taken into account when analysing such systems.

Proposition for P2P Storage System Architectures

In this section, we suggest some modifications of the architecture of systems implementing local policies. We also discuss the best choice of their parameters. First, we propose an external reconstruction strategy for the local policies, and show that it can lower the duration of the sending phase of reconstructions, and thus improve the probability to lose data. Second, we show that having a larger neighborhood is sufficient to greatly improve the Chain policy performance. Hence, an architecture with the advantage of locality and performance close to the ones of a Global strategy can be obtained. Finally, we carry out some comparisons between Replication and Erasure Code schemes. We show by simulations that, for the same amount of bandwidth and space overhead, the Erasure Codes are better even for the Chain policy.

External Reconstruction Strategy

We propose here a new reconstruction architecture for the Chain policy, namely external reconstruction. The idea is to use peers outside the Chain group to carry out the reconstruction process. In this way, the bandwidth usage is more uniformly spread among peers. More precisely, only the upload bandwidth of the retrieval phase of the reconstruction is needed locally, while the bandwidth for the sending phase is provided by all the peers of the system. Hence, the External Reconstruction has two main advantages:

• a local control for discovering failed peers and updating the data-blocks' states;

• a more uniform distribution of resources among peers, which lowers the reconstruction time.

However, a small cost is paid: in the internal reconstruction, the peer in charge may be chosen in such a way that it possesses a piece of the block to be reconstructed. It reduces by a factor of (s -1)/s the bandwidth needed for the retrieval phase of the reconstruction. Conversely, in the external reconstruction, the reconstructor does not contain any piece. A rough estimate of the gain in terms of reconstruction time can be given. In the internal reconstruction, local peers have to support s + r -r 0 uploads of pieces. However, when using the external reconstruction, they only have to support s uploads of pieces. As the local peers basically are the bottleneck of the reconstruction, the gains in terms of bandwidth and hence of reconstruction time are roughly 1 -s/(s -1 + r -r 0 ). With the parameters chosen in our experiments, this factor would be 0.25. Note that the gains in terms of data loss will be significantly higher (see Section 4.2).

Figure 6 compares the internal and external policies. It gives the trade-off between the average number of dead blocks per year and the available bandwidth. For the same bandwidth, the fraction of data loss decreases by a factor between 0.5 and 0.6 for this set of parameters. We see that, by choosing to carry out the reconstructions externally, the chain policy behaves substantially better.

What Should Be the Size of the Neighborhood?

We showed above that the Global policy in practice (under tight resource constraints) behaves significantly better than the local policies. Nevertheless, as already stated in the introduction, there exist important practical considerations that explain the choice of local placement. Would it be possible to obtain the same practical advantages of the local policies (a small sub-network to monitor) without paying the high cost of the Chain and Buddy in terms of probability of data loss?

In this section, we study the impact of the size of the block neighborhood on the system performance. The block neighborhood is defined as the peers that can receive pieces of this block (of size s + r for Buddy and Chain, and of size N for Global).

• • • • • • • • • • • • • • • •
Chain size (number of nodes) Fraction of dead blocks per year (%) Figure 7 shows the average number of dead blocks per year for different sizes of the neighborhood. The sizes range from s + r = 15 (corresponding to the size of the neighborhood for the Chain policy) to 90. The experiment was done for different amounts of data per disk (i.e., number of blocks per disk), from 40 to 200, which is, as we will see, an important parameter when choosing the neighborhood size. We see that barely increasing the neighborhood from 15 to 20 has a striking impact on the data loss: with 120 blocks per disk, the fraction of data loss drops from 4.1% to 1.6%, representing a decrease of almost 61 percent. Thus, increasing the size even by few units leads to strong improvements of the system performance. However, the number of dead blocks decreases from 0.17% to 0.16% for neighborhoods of sizes 85 and 90 nodes. The marginal improvement strongly decreases.

The shapes of the curves may be explained as follows. When there is a peer failure, its neighbors are in charge of reconstructing the lost fragments. Hence the reconstruction time (minus the discovery time) depends almost linearly on the neighborhood size. This dependence can be directly translated to the probability to lose data: Exponential relation between the probability to die and the reconstruction time. During a reconstruction, a block dies if it loses r 0 + 1 fragments before it finishes. The probability for a peer to be alive after a time T is exp(-λT ), where λ is the peer failure rate. Hence a good approximation of the probability to die during a reconstruction lasting a time T is given by Pr[die|Rtime = T ] = s + r 0 r 0 + 1 (1 -e -λT ) r0+1 (e -λT ) s-1 .

INRIA

Hence we have an exponential relationship between the number of block losses and the neighborhood size.

The neighborhood size should mainly be chosen in function of two parameters: the disk size (or the number of fragments per disk) and the peer bandwidth. Note that a size of D (r-r0)BWup allows to reconstruct the blocks in one time step and is sufficient to get the benefits of Global (with D the number of fragments per disk, BW up expressed in blocks/time step and 1/(r -r 0 ) the fraction of blocks of the lost disk that go beyond the saddle value).

Concluding, to implement a local policy, the neighborhood should at least be a little bit larger than s + r, as the marginal utility of increasing the block neighborhood is tremendous for very small sizes. In addition, the neighborhood size should be chosen in function of the disk size: The larger the number of fragments per disk, the larger the block neighborhood should be.

Replication versus Erasure Codes

Other experimental studies on data placement analyze the case of replication instead of Erasure Codes, see e.g. [START_REF] Van Renesse | Efficient reliable internet storage[END_REF][START_REF] Douceur | Large-scale simulation of replica placement algorithms for a serverless distributed file system[END_REF][START_REF] Dabek | Wide-area cooperative storage with CFS[END_REF][START_REF] Lian | On the impact of replica placement to the reliability of distributed brick storage systems[END_REF]. It is shown in [START_REF] Weatherspoon | Erasure coding vs. replication: A quantitative comparison[END_REF] that Erasure Codes could be used to achieve a high availability of data storage with low space overhead, but these studies assume a Global and random placement strategy. Rodrigues and Liskov, in [START_REF] Rodrigues | High availability in dhts: Erasure coding vs. replication[END_REF], state that in high-churn systems, Erasure Codes may demand high bandwidth usage, which could be impractical. This is not relevant to our study since we assume the use of storage "bricks" that stay turned on almost all the time. We show here that, even for local policies, the Erasure Codes scheme is more efficient, meaning that it has less probability to lose data for the same storage and bandwidth usage. Hence, we confirm the pertinence to carry out an analysis of data placement when using Erasure Codes.

Note first that replication is a special case of Erasure Codes, but with only one initial fragment (s = 1). Hence, we used exactly the same simulator to carry out the experiments. We evaluated the system for different number of replicas k, with values varying from 1 to 4. To have the same storage overhead factor, we compare the scenarios using k replicas with a system with r = k * s erasure coded fragments. Then we choose the reconstruction saddle value equals to r 0 = r -s ( k 0 = k -1 to the case of replication), so that we experience the same number of reconstructions, that is, roughly the same bandwidth usage. We present in Table 3 the average bandwidth use and fraction of data loss per year for both techniques. In the case of Erasure Codes, the number of initial pieces is s = 4. For instance, for a value of replication k = 3 (this means r = 12 to the case of Erasure Codes), the reconstruction starts when k = k 0 = 2 (and when r = r 0 = 8 for the Erasure Codes).

We see that, for k = 1, the system with replicas behaves better than Erasure Codes, while using less bandwidth. But, as soon as k ≥ 2, systems with Erasure Codes behave strikingly better: they experience a lot fewer block losses while using a little less bandwidth. In practice, to have a very low probability to lose data, real systems use values of k larger than 4, see e.g. [START_REF] Van Renesse | Efficient reliable internet storage[END_REF]. Thus, systems with Erasure Codes have less probability to lose data for the same amount of resources and realistic levels of redundancy.

Figure 2 :

 2 Figure 2: Variations of bandwidth usage across users for the three different strategies for a typical timestep and under the same fault scenario.

Figure 4 :

 4 Figure 4: Average reconstruction time for different bandwidth limits for the three strategies. The values for the local policies (Chain and Buddy) are higher, and decrease gradually with the increase of the available bandwidth. The unlimited value of 1 is the granularity of our simulator (one hour).

INRIA

6

 6

Figure 5 :

 5 Figure 5: Fraction of block losses per year (see Remark 2) for different bandwidth limits for the three strategies. The differences between policies are stronger than for the reconstruction times of Fig 4, as explained in Section 4.2.

Figure 6 :

 6 Figure 6: Comparison between the Chain policy with internal reconstruction and with external reconstruction. The fraction of block losses (see Remark 2) for different bandwidth limits is presented. There is an improvement of about 50% on the fraction of data losses.

Figure 7 :

 7 Figure 7: Study of the size of the block neighborhood. Fraction of block losses (see Remark 2) per year for different sizes of neighborhood and different number of fragments per disks.

Table 1 :

 1 Summary of main notations and their default values in our experiments. See Remarks 1 and 2 for the choice of the parameter values.

	N	# of peers	1, 005
	F	total of fragments in the system	1.5 • 10 6
	s	# of fragments in the initial block	9
	r	# of redundancy fragments	6
	r0	reconstruction threshold value	2
	τ	time step of the model	1 hour
	M T BF	Peer mean time between failures	90 days
	BWup	Upload bandwidth per peer	6-18 kbit/s and Unlim.

Table 2 :

 2 however local policies exhibit strong variations in resource Summary of results (without bandwidth constraints).

	Policy	Bandwidth (kbit/s)	FDLPY (blocks)	MTTDL (years)
	Global 1.99 (± 1.34)	4.1 • 10 -4 (± 0.6 • 10 -4 )	0.02 (± 0.02)
	Chain	1.99 (± 12.83)	4.1 • 10 -4 (± 8.6 • 10 -4 )	4.0 (± 3.0)
	Buddy 1.99 (± 15.92)	4.4 • 10 -4 (± 25.4 • 10 -4 ) 25.8 (± 21.7)
	usage across peers; (3) they have the same probability to lose a data-block, (4) but the
	MTTDLs of the Buddy and the Chain policies are longer.

INRIA

  The following table shows the MTTDL for the three policies under resource constraints.

	MTTDL (hours)
	Max.BW (kbit/s) =	6	9	12	15
	Global	166 180 193 219
	Chain	53 160 323 565
	Buddy	75 178 341 550

Table 3 :

 3 Comparison of Replication and Erasure Codes when using the Chain placement. Number of dead blocks per year and avg. bandwidth usage for different values of redundancy k. Repl. 2.2 • 10 1 3.0 • 10 -1 3.8 • 10 -4 1.9 • 10 -4 Erasure 6.9 • 10 1 2.5 • 10 -6 3.2 • 10 -17 4.3 • 10 -29 In the case of Erasure Codes s = 4 and r = s * k

	Estimated Fraction of Data Loss per Year (%)
	k =	1	2	3	4
		Upload Bandwidth usage (kbit/s)
	k =	1	2	3	4
	Repl.	1.08	3.24	4.34	5.40
	Erasure	1.45	2.47	3.42	4.37

RR n°7006

There are two groups of peers in each spike of the Buddy. A bigger one around 1500 kbit/s, that corresponds to peers doing the retrieval and sending phases of the reconstruction (i.e., s + rr 0 uploads for each block). The smaller one, with an upload bandwidth around 400 kbit/s, correspond to peers that have failed and were replaced with empty disks. As they are empty, they do not send fragments to the reconstructors (no retrieval upload), but they are in charge of some reconstructions, so we see their sending upload (i.e. r -r0 pieces for each block).INRIA

Conclusion

In this paper, we show that placement policies strongly impact the performance of P2P storage systems. We study three different policies, a Global and two local, and show that under resource constraints, the Global policy behaves better in terms of probability to lose data and MTTDL than the local policies.

We suggest architectural choices to improve the performances of local policies. We show that, by using a new reconstruction strategy, namely external reconstruction, and by increasing the size of the neighborhood, local policies can have performances almost equivalent to the ones of the Global, while keeping their practical advantages.

This work was partially funded by the European project ist fet Aeolus and the ANR projects SPREADS and DIMAGREEN.


Thomas Pellegrini
email: pellegri@irit.fr

Lionel Fontan
email: fontan@irit.fr

Julie Mauclair
email: mauclair@irit.fr

Jérôme Farinas
email: jfarinas@irit.fr

Marina Robert

The Goodness of Pronunciation algorithm applied to disordered speech

Keywords: pronunciation automatic assessment, Goodness of Pronunciation, disordered speech

In this paper, we report on a study with the aim of automatically detecting phoneme-level mispronunciations in 32 French speakers suffering from unilateral facial palsy at four different clinical severity grades. We sought to determine if the Goodness of Pronunciation (GOP) algorithm, which is commonly used in Computer-Assisted Language Learning systems to detect learners' individual errors, could also detect segmental deviances in disordered speech. For this purpose, speech read by the 32 speakers was aligned and GOP scores were computed for each phone realization. The highest scores, which indicate large dissimilarities with standard phone realizations, were obtained for the most severely impaired speakers. The corresponding speech subset was manually transcribed at phone-level. 8.3% of the phones differed from standard pronunciations extracted from our lexicon. The GOP technique allowed to detect 70.2% of mispronunciations with an equal rate of about 30% of false rejections and false acceptances. The phone substitutions detected by the algorithm confirmed that some of the speakers have difficulties to produce bilabial plosives, and showed that other sounds such as sibilants are prone to mispronunciation. Another interesting finding was the fact that speakers diagnosed with a same pathology grade do not necessarily share the same pronunciation issues.

Introduction

Unilateral facial palsy (UFP) can result from a variety of causes, such as trauma, infection or tumors [START_REF] Ljostad | Acute peripheral facial palsy in adults[END_REF]. Among its numerous consequences on patients' lives, UFP often cause articulatory disorders than can greatly impact on communication ability [START_REF] Gatignol | Paralysies faciales[END_REF]. However, the assessment of the severity of impairment generally relies on physical criteria only, such as in the House-Brackmann scale [START_REF] House | Facial nerve grading system[END_REF][START_REF] Evans | Reliability of the House and Brackmann grading system for facial palsy[END_REF]. This clinical tool evaluates the degree to which patients can activate mouth, eyelids and forehead muscles when executing voluntary or involuntary movements, and leads to a score ranging from grade I (normal facial activity) to grade VI (total palsy).

For high pathology grades, the inability to control the lips hinders a proper control of the air flow. Phonemes most impacted are consonants: bilabials /p, b, m/ may lose their burst phase, labiodentals /f, v/ and fricatives /s, S/ 1 are also impacted due to an unilateral stretching/ closing of the lips [START_REF] Robert | Analyse des troubles articulatoires au cours des paralysies faciales périphériques[END_REF]. A qualitative study showed that the most affected consonants are /p/ and /f/ [START_REF] Albinhac | Analyse quantitative et qualitative des troubles d'articulation dans les paralysies faciales périphériques[END_REF]. To a lesser extent, vowels may also be affected, in 1 We will use the SAMPA phonetic alphabet [START_REF] Wells | Sampa computer readable phonetic alphabet[END_REF] throughout the paper particular vowels that imply a certain control of the lips' movements such as /e, i, o, u, y/ and nasal rounded vowels /o~, e~/. If studies reported a clear correlation between the severity of impairment and the articulatory disorders, a large variability in the articulation abilities of impaired speakers was also observed, even among speakers sharing a same palsy grade [START_REF] Robert | Analyse des troubles articulatoires au cours des paralysies faciales périphériques[END_REF].

Having an automatic tool to assess pronunciation at phonelevel would allow to easily gather individualized information about each patient. Assessment of speech abilities is indeed very time-consuming, which does not necessarily fit clinical means for patients' evaluation. Such tools are widely used in Computer-Assisted Language Learning (CALL) systems, with early works reported in the 1990s [START_REF] Bernstein | Automatic evaluation and training in English pronunciation[END_REF]. CALL systems use Automatic Speech Recognition (ASR) techniques to assess nonnative pronunciation both at suprasegmental and segmental levels, two domains respectively referred to as overall pronunciation assessment and individual error detection [START_REF] Eskenazi | An overview of spoken language technology for education[END_REF]. Within the latter scope, several scoring approaches can be used to detect phoneme mispronunciations. They range from the analysis of raw recognition scores [START_REF] Sevenster | Evaluation and training of second-language learners' pronunciation using phoneme-based HMMs[END_REF], likelihood ratios such as nativelikeness and Goodness of Pronunciation (GOP), to the definition of scores derived from classification methods such as linear discriminant analysis and alike [START_REF] Strik | Comparing classifiers for pronunciation error detection[END_REF]. Contrary to nativelikeness scores that imply the use of non-native acoustic models, the Goodness of Pronunciation (GOP) algorithm is solely based on the comparison of speakers' realizations with native phone models. It calculates a likelihood ratio indicating the degree to which a phone may be the realization of a specific phoneme of the target language [START_REF] Witt | Use of Speech Recognition in Computer-Assisted Language Learning[END_REF][START_REF] Witt | Phone-level Pronunciation Scoring and Assessment for Interactive Language Learning[END_REF]. In other words, GOP scores give an idea of how distinguishable is a specific phone realization compared to other phones, and can thus be thought of as intelligibility indexes [START_REF] Kawahara | Tutorial on CALL Systems at Interspeech[END_REF]. As a consequence, the relevance of GOP scores for speakers' evaluation may not be limited to the framework of foreign language learning, but possibly applies to any kind of articulatory deviances, such as in motor speech disorders.

Studies found in the literature mostly focus on ASR system performance and limits when processing disordered speech, especially concerning dysarthric speech [START_REF] Coleman | Computer recognition of the speech of adults with cerebral palsy and dysarthria[END_REF][START_REF] Rosen | Automatic speech recognition and a review of its functioning with dysarthric speech[END_REF][START_REF] Sanders | Automatic recognition of dutch dysarthric speech: A pilot study[END_REF][START_REF] Rudzicz | Articulatory Knowledge in the Recognition of Dysarthric Speech[END_REF]. In [START_REF] Schuster | Evaluation of speech intelligibility for children with cleft lip and palate by means of automatic speech recognition[END_REF], ASR word accuracy was correlated with subjective speech intelligibility for children with cleft lip and palate. However, to the best of our knowledge, the present study is a first attempt to use both ASR and CALL techniques to assess the pronunciation skills of impaired speakers -in the particular case of patients suffering from unilateral facial palsy. The two main questions addressed in this study are: Can the GOP algorithm be used to identify and characterize individual mispronunciations in the context of peripheral paralysis impairments? Does the GOP scores correlate with clinical impairment grades?

The paper is organized as follows. First, an overview of the GOP algorithm is given. Sections 3 and 4 describe the methodology and the speech corpus used in this work, followed by a listening analysis of the corpus. Statistics on manual transcriptions at phone level are then described. Finally, GOP experiments are reported and discussed in Section 7.

The GOP algorithm

To compute GOP scores on a given utterance, two phases are needed: 1) a free speech recognition phase and 2) a forced alignment phase. Without giving any information to the ASR system about the target sentence, the free speech recognition phase determines the most likely phone sequence matching the audio input (i.e. the output is that of a free phone loop recognizer). On the contrary, the forced alignment phase implies to provide the ASR system with the orthographic transcription of the input sentence. It then consists of forcing the system to align the speech signal with the expected phone sequence.

For each phone realization aligned to the speech signal, a GOP score is calculated by taking the absolute value of the difference between the log-likelihood of the forced alignment phase and the one of the free recognition phase. When the expected and the freely recognized phones are the same, the GOP score is zero. Otherwise, the larger the GOP score, the greater the probability of a mispronunciation. In order to decide whether a phone was mispronounced ("rejected") or not ("accepted"), phone-specific thresholds need to be defined. In this work, we used the baseline implementation of the GOP algorithm, described in [START_REF] Witt | Use of Speech Recognition in Computer-Assisted Language Learning[END_REF][START_REF] Witt | Phone-level Pronunciation Scoring and Assessment for Interactive Language Learning[END_REF].

Methodology

First, a preliminary auditory analysis of the speech corpus was conducted in order to identify pronunciation trends that could discriminate between speakers suffering from several palsy severity grades. Second, the GOP algorithm was run over the corpus. The forced alignments were constrained by standard pronunciations taken from a 62K French words lexicon. The aligned phone sequences were manually edited by an annotator with a solid background in phonetics and experience in transcribing speech in the context of French as a foreign language (FFL) teaching. Phones that were edited by the annotator differed from standard pronunciations and therefore were considered as mispronunciations. The resulting manual phone transcriptions were taken as groundtruth reference to quantify the pronunciation issues observed during the listening analysis, and also to assess the effectiveness of the GOP algorithm.

In this study, we limited this manual effort to the group of most impaired speakers group (grades V&VI UFP, cf. next section), since we expected more mispronunciations in this population. Furthermore, we made the assumption that all the phone sequences aligned automatically for the control group (no pathology) were correct and then taken as phone realizations that the GOP algorithm should accept. We set phonedependent GOP score thresholds by limiting the false rejection (FR) rate below 10% on the control group. We will also report results for the operating point where false rejection and acceptance rates are equal.

Corpus description

The experiments have been carried out on a subset of a read speech database recorded at the La Pitié Salpétrière Hospital in Paris, France. This database was used in previous studies [START_REF] Robert | Analyse des troubles articulatoires au cours des paralysies faciales périphériques[END_REF][START_REF] Mauclair | Burst-based features for the classification of pathological voices[END_REF]. It was collected from 32 French speakers suffering from UFP at five different grades according to the House and Brackmann scale, namely grades I, III, IV, V and VI. As the patients whose UFP grade had been rated as V or VI did not differ in terms of lips mobility, we regrouped them into a single group. As a result, 4 speaker groups were defined for this study. To simplify the notation in the remainder of the article, we will refer to the groups G1 (control group), G2 (grade III), G3 (grade IV) and G4 (grades V&VI). The 32 speakers are evenly distributed into these four groups, with equal proportions of male and female speakers, and a mean age of 45 years.

The patients were recorded in a soundproof booth. They read aloud 17 declarative sentences, which included all standard French consonants and semi-consonants 2 . Each sentence was constructed in order a) to include different realizations of a target consonant (i.e. alliterations) or b) to lead the speaker to produce several times a specific phonetic contrast (e.g. voicing). As an example, the sentence "Le moteur de ma moto n'a pas démarré" (The engine of my motorbike did not start) used an alliteration of the bilabial consonant /m/, and the sentence "Le catalogue de Paul est tombé" (Paul's catalog fell down) relied on the production of voiced/voiceless stop pairs (/g/ vs. /k/, /d/ vs. /t/ and /b/ vs. /p/). More details about the speech corpus can be found in [START_REF] Robert | Analyse des troubles articulatoires au cours des paralysies faciales périphériques[END_REF].

Listening analysis

A preliminary listening analysis was conducted by two researchers familiar with pathological speech analysis. As occurred to both listeners, G3 speakers' performance seemed less impacted than that of G2 speakers. Their reading was more fluent. Although differences with the control group were found for these two groups, the deviances for the eight G4 speakers were much more important. Another general impression was that these deviances strongly depend on the speaker, even among speakers in the same group.

Perceptively, bilabial and labiodental consonants /p, f, b/, and /v/ were identified as the most impacted phonemes. Voiced phonemes (/b, v/) realizations were judged very hard to perceive, and their voiceless counterparts (/p, f/) realizations were often perceived as too breathy. A lack of control of the air flow -often referred to as breathiness factor in clinical tools for disordered speech evaluation -could explain this impression. Moreover, the patients' difficulties to move their lips in order to produce explosions may explain why occlusive consonants (/p, b/) were sometimes perceived as constrictive ones (/f, v/). For example, the first name Paul (/pOl/) was sometimes perceived as [fOl]. For some speakers /b/ realizations often sounded as [v], as in the word bu (/by/, drunk) perceived as [vy]. Concerning the fricative /v/ realizations, they have been perceived as the semi consonant /H/ in some speakers. More generally, exaggerated breathiness impacted all voiceless occlusive consonants (/p, t, k/), which were perceived with an aspiration such as in English realizations. A tendency to produce retroflex variants of phonemes /S/ and /d/ was also perceived for some speakers. This could be the result of a strategy to compensate the lack of articulation possibilities in the mouth and lips by lifting the tongue towards the post-alveolar area.

Quite unexpectedly, no peculiarities were identified for /m/ and /n/ realizations, although their place of articulation could have been thought as problematic for patients suffering from UFP. This might be explained by the fact that these two nasal consonants generate much weaker bursts than their oral counterparts, and thus that their intelligibility may be less impacted by speakers' lips hypokinesia.

Manual phone-level transcription

In this section, only speakers from group G4 are concerned since manual corrections were realized for this group only. Of the total 4K phones that were automatically aligned, 8.3% differ after manual corrections, with 3.6%, 2.5%, and 2.2% of substitutions, insertions, and deletions, respectively. The annotator was free to use phonetic symbols borrowed to phonological systems other than French, but we limited the present study to the French phonemic inventory. For instance, he introduced aspirated variants of /p, t, k/ phonemes that are not taken into account in the numbers reported here.

Insertions were mainly additions of schwas (1.3%). The lexicon comprises pronunciation alternates with and without schwas, whose realization is optional in French. Hence, the automatic recognizer seems to have the tendency to use pronunciations with eluded schwas when aligning. The most frequent manual editions were, in decreasing importance, deletions of voiced and unvoiced plosive closures (1.1%), substitutions of [p] by [f] (0.7%), by [b] (0.1%), by [w] and [v] (0.05%), deletions of [t] (0.6%), insertions of [Z] (0.2%) after a [d], substitutions of [b] by [v]. These results confirmed most of the observations made during the listening analysis, concerning both the impacted phonemes and the inter-speaker variability. The frequent substitutions of [p] by [f] concerned half of the speakers of G4. This observation confirms our previous study, in which the presence of a burst for /p/ was a crucial feature used in determining automatically the UFP grade [START_REF] Mauclair | Burst-based features for the classification of pathological voices[END_REF].

GOP experiments 7.1. Setup

The alignment and recognition setup consists of three state leftto-right HMMs with 32 Gaussian mixture components trained on the ESTER corpus [START_REF] Galliano | The ESTER phase II evaluation campaign for the rich transcription of French broadcast news[END_REF]. Context-independent acoustic models (39 monophones) were used since they have been found to be more suitable for CALL applications than context-dependent units [START_REF] Kawahara | Tutorial on CALL Systems at Interspeech[END_REF]. This work was carried out with HTK [START_REF] Young | The HTK Hidden Markov Model Toolkit: Design and Philosophy[END_REF].

Inter-group results

In Table 1, we report the average and standard deviations of GOP values for each speaker group. It appeared that means and standard deviations globally increased with the impairment grade (t-tests gave p-values<0.01), except for group G3. A relative increase of about 34% was found between groups G1 and G4, for instance. Group G3 showed a smaller GOP mean compared to G2, which confirmed our impression that speakers from this group sounded less impacted than G2 speakers.

Figure 1 shows the most frequent substitutions of the sibilant /s/ with other consonants, as found by the phone recognizer. Average GOP scores are also given for the four groups. As one can see, confusions with [f] and [S] increase with the impairment grade, such as the average GOP for this phone, except for G3. Nevertheless, the GOP score evolution was not always that clear for other phones. An attempt to cluster the speakers according to their GOP values revealed unsuccessful, confirming our impression gained during the listening analysis that the speakers of our database, even the most impaired ones, do not share the same pronunciation issues.

GOP algorithm accuracy

The GOP algorithm was evaluated in terms of Scoring Accuracy (SA), which is the percentage of Correct Acceptances (CA) and Correct Rejections (CR) divided by the total number of tokens (N): SA = 100% * (CA + CR)/N . Correct acceptances are phones that were correctly pronounced and whose GOP scores were below a given threshold. Correct rejections are phones that were pronounced incorrectly and whose GOP scores were above a given threshold. To give an idea of performance obtained in CALL applications, SAs of about 80% obtained on Dutch non-native speech, with 50% for CA and 32% for CR, were reported on a test set [START_REF] Kanters | The Goodness of Pronunciation Algorithm: a Detailed Performance Study[END_REF]. In Section 6, we reported that 8.3% of the 4K phones aligned with speech of the G4 speakers were edited by the annotator, of which 2.5% were insertions. Insertions cannot be handled by the algorithm since no GOP scores are computed for them. Hence, the algorithm should detect at most 233 mispronunciations, which correspond to 5.8% of 4K realizations.

We set phone-specific thresholds based on the GOP scores obtained on the phone realizations from the control group speakers (G1). We considered all their realizations to be correct. As a consequence, rejections are only due to misrecognitions or misalignments made by the system. Thresholds were defined by carrying out an exhaustive search for each phone, starting from a zero value with a step size of 0.1. To illustrate the detection performance, Figure 2 shows a Detection Error Tradeoff (DET) curve obtained on the G4 data. In [START_REF] Kanters | The Goodness of Pronunciation Algorithm: a Detailed Performance Study[END_REF], the use of a false rejection (FR) rate below 10% was justified by the fact that false rejections are more detrimental than false acceptances for a learner. With such a criterion applied on our data, we achieved SA, CA, and CR rates of 84.0%, 84.6%, and 49.6%, respectively. This operating point is indicated on the DET curve by a cross. Correct acceptance rate depends on the phones. The GOP threshold for /p/, for instance, was set to 0.7 with this configuration, and the most frequent mispronunciation, /p/ pronounced as an [f], was correctly detected in 60% of the cases. Another operating point is highlighted by a circle on the graph. It corresponds to the point with equal FR and FA rates (about 30%) obtained on the G4 test data. At this point, the system detected 70.2% mispronunciations, but the correct acceptance rate decreased to 70.7% compared to 84.6% obtained at the previous operating point. Figure 3 illustrates an example of GOP scores obtained on the utterance "Paul prépare la purée de petits pois" (Paul is preparing mashed peas) for a speaker of group G4 with difficulties to produce /p/ consonants. This figure compares two sets of GOP scores computed with two different phone transcriptions given below the x-axis: one with standard pronunciations, indicated by the label "Lexicon", and the manual one, indicated by the label "Groundtruth". Six differences between the two sequences were highlighted with a Gray background color: four /p/ realizations and two /a/ realizations transcribed by [f] and [O] respectively. The horizontal dashed line of equation GOP=0.7 was added to indicate the threshold for phone [p]. Ev-ery Lexicon GOP score (bars in blue color) above this line gives a rejection. As can be seen, all the mispronunciations of the phoneme /p/ were correctly rejected with this threshold, but one correct pronunciation (in the middle of the utterance) was incorrectly rejected (score=0.72). Since Groundtruth corresponds to phones that were actually pronounced, the corresponding GOP scores are expected to be smaller than the lexicon-based ones. Indeed the GOP average values for the whole subcorpus were 2.03 and 2.25 for Groundtruth and Lexicon, respectively.

Conclusions

In this paper, we reported our findings from a detailed analysis of pronunciation at phone-level of speakers suffering from unilateral facial palsy at different clinical severity grades. A read speech corpus recorded from 32 French native speakers was used at this purpose. Mispronunciations were identified automatically by using the GOP algorithm originating from the CALL research area. It proved to be effective by correctly detecting 49.6% and 84.6% of mispronunciations (CR rate) and correct pronunciations, respectively, when allowing a false rejection rate of only 10% on the control group speech used to set the GOP phone-specific thresholds. CR rate increased to 70.2% with equal FR and FA rates of about 30%. The highest average GOP scores, which indicate large deviances from standard phone realizations, were obtained with speech of the most impaired speakers.

Nevertheless, average GOP scores did not strongly correlate with clinical severity grades, as measured through the House-Brackmann scale. In our opinion, this result might reflect that (a) the H&B scale has been designed to evaluate the overall facial mobility -i.e. not that of speech articulators only -and (b) that some patients may employ efficient compensatory strategies in order to remain intelligible despite the motor deficiencies they are suffering from. In this perspective an automatic tool such as the GOP would constitute an interesting means to easily collect relevant data pertaining to the communication ability of patients.

As a consequence, future work will be conducted in order to study further the validity of GOP measures for clinical applications, both concerning Unilateral Facial Palsies and other motor speech disorders.

Figure 1 :

 1 Figure 1: GOP average scores and most frequent substitutions of the sibilant /s/, as found by the phone recognizer.

Figure 2 :

 2 Figure 2: DET curve for G4. Two special operating points are represented: 'x' with FR=10% on G1 data, and 'o' with equal FR and FA on G4 data.

Figure 3 :

 3 Figure 3: Example of GOP scores for the utterance "Paul prépare la purée de petits pois". "Lexicon": phones extracted from a French lexicon, "Groundtruth": phones identified by the annotator. Horizontal dashed line: rejection threshold for phone /p/ (0.7).

Table 1 :

 1 Average and standard deviation (std) GOP values per group

	Group Average GOP (std)
	G1	1.68 (2.98)
	G2	1.94 (3.12)
	G3	1.72 (2.86)
	G4	2.25 (3.50)

Standard French phonological system includes bilabial (/p/, /b/, /m/), labiodental (/f/, /v/), alveodental (/t/, /d/, /n/), alveolar (/s/, /z/, /l/), palatal (/S/, /Z/), velar (/k/, /g/) and uvular (/R/) consonants, as well as the three semi-consonants /w/, /H/ and /j/