J Va'vra

N Arnaud

A Yu Barnyakov

M Yu Barnyakov

C Beigbeder

M Benettoni

M El Berni

M Borsato

D Breton

L Burmistrov

G Collazuol

B Dey

F Gargano

F Giordano

H Jawahery

E A Kravchenko

S A Kononov

H Lebbolo

D W G S Leith

F Loparco

M N Mazziotta

J Maalmi-Di Bello

K Nishimura

A P Onuchin

M Posocco

V Puill

B Ratcliff

D Roberts

G Simi

A Stocchi

D Shtol

R Stroili

V Tocut

E Twedt

G S Varner

Progress on development of the new FDIRC PID detector

Keywords: Particle identification detectors, DIRC, RICH detectors PACS: 29.40.Cs, 29.40.Gx

We present a progress status of a new concept of PID detector called FDIRC, intended to be used at the SuperB experiment, which requires π/K separation up to a few GeV/c. The new photon camera is made of the solid fused-silica optics with a volume 25× smaller and speed increased by a factor of ten compared to the BaBar DIRC, and therefore will be much less sensitive to electromagnetic and neutron background.

Introduction

The BaBar experiment has used very successfully the DIRC PID detector (DIRC = Detector of Internally Reflected Cherenkov light) [START_REF] Ratcliff | SLAC-PUB-5946[END_REF]. The original DIRC had one weak point: its huge photon camera, filled with 6,000 liters of ultra-pure water, was sensitive to electromagnetic and neutron background. This needs to be improved as the SuperB luminosity will increase 100×. Therefore we have exchanged this simple pinhole camera at the heart of the DIRC detector into a focusing camera with sophisticated, solid fused-silica optics, while shrinking it to 1/25th of its former size and increasing its speed by a factor of ten [START_REF] Va'vra | FDIRC design for SuperB[END_REF]. The new detector is called FDIRC (Focused Detection of Internally Reflected Cherenkov light). Each of the 12 FDIRC Photon cameras will have 48 H-8500 MaPMTs, providing excellent timing capability for single photons (σ T T S ∼140 ps, TTS is a transit time spread). It is also necessary to implement new front-end electronics (FEE) with much higher timing precision (σ Electronics ∼100 ps), higher hit rate capability (few MHz hit rate per pixel), and small dead time (less than 5% at 1MHz rate) [START_REF] Beigbeder | PID electronics for SuperB[END_REF]. These improvements will compensate for the increase in luminosity (×100) and background between the two generations of experiments. A full scale FDIRC prototype module covering 1/12 of the barrel azimuth will be tested in the cosmic ray telescope (CRT) [START_REF] Va'vra | SLAC Cosmic Ray Telescope Facility[END_REF] at SLAC with 3D tracking using muons.

FDIRC design and construction

A very important design feature of FDIRC photon camera is to measure the Cherenkov angle with x-y pixels alone (the detector coordinate system where the y-direction is vertical and the x-direction is horizontal), i.e., a high resolution timing is not needed. Time is used, however, to cut the background, perform the chromatic correction by timing, and be part of PID maximum likelihood.

Figures 1 and2 show the new FDIRC photon camera design. The camera was designed with one important constraint: it has to reuse the BaBar DIRC radiators (bar boxes). This reduced possible design choices. The optics was designed using a graphical manual ray tracing [START_REF] Va'vra | Focusing DIRC design for Su-perB[END_REF], then checked by computer ray tracing using Mathematica program, and then checked with MC simulation [START_REF] Roberts | Geant4 simulation of FDIRC[END_REF]. The photon camera consists of two parts: (a) a focusing block (FBLOCK) with cylindrical and flat mirror surfaces, and (b) a new wedge. The wedge at the end of the bar rotates rays with large transverse angles (in the focusing plane) before they emerge into the focusing structure. The old wedge is too short so that an additional wedge element must be added to insure that all rays strike the cylindrical mirror. The cylindrical mirror is rotated appropriately to make sure that all rays reflect onto the FBLOCK flat mirror, preventing reflections back into the bar box itself; the flat mirror then reflects rays onto the detector focal plane with an incidence angle of almost 90 degrees. The focal plane is located in a slightly under-focused position to reduce the FBLOCK size and therefore its weight. Precise focusing is unnecessary, as the finite pixel size would not take advantage of it.

There are several important advantages gained in moving from the BaBar pinhole focused design with water coupling to a focused optical design made of solid fused silica: (a) the design is modular; (b) sensitivity to background, especially to neutrons, is significantly reduced; (c) the pinhole-size component of the angular resolution in the focusing plane can be removed by focusing with cylindrical mirror, and timing can be used to measure the chromatic dispersion, thus improving performance; (d) the total number of photomultipliers is reduced by about one half compared to a non-focusing design with equivalent performance; (e) there is no risk of water leaks into the SuperB detector, and no time-consuming maintenance of a water system, as was required to operate BaBar safely.

Each new camera will be attached to its BaBar bar box with an optical RTV glue, which will be injected in a liquid form between the bar box window and the new camera and cure in place. As Fig. 1 shows, the cylindrical mirror focuses in the radial (y) direction, while pinhole focusing is used in the direction out of the plane of the schematic (the x-direction). Photons that enter the FBLOCK at large x-angles reflect from the parallel sides, leading to an additional ambiguity. However, the folded design makes the optical piece small, and places the photon detectors in an accessible location, improving both the mechanics and the background sensitivity. Since a given photon bounces inside the FBLOCK only 2-4 times, the requirements on surface quality and polishing for the optical pieces are much less stringent than that required for the DIRC bar box radiator bars.

Figure 3 shows the new Wedge (glued to bar box), and Fig. 4 shows the FBLOCK. They are made of radiation hard fused silica (Corning 7980). The manufacturing was done in three steps: (a) grinding final shapes about 1-2 mm oversized, (b) polishing to final size and surface polish of better than 30A rms, (c) coating two FBLOCK's reflecting surfaces with aluminum with a SiO 2 overcoat to protect it. Figure 5 shows the coupling between FBLOCK and new Wedge with a 1 mm thick RTV. This coupling can be cut with a razor wire enabling a possible separation of the photon camera from the bar box. Figure 6 shows the final FDIRC full size prototype located in CRT.

Choice of photodetectors and electronics

There were three Hamamatsu photon detectors under consideration, the H-8500 (64 pixels) and the H-9500 (256 pixels), and very recently R-11265-00-M64 (64 pixels) multianode PMTs (MaPMT) by Hamamatsu. At present, our nominal choice is a 12-stage H-8500 tube. It has a sufficient single electron timing spread (σ T T S ∼ 140 ps), it can be obtained with somewhat enhanced quantum efficiency QE of ∼ 24%, it has more acceptable uniform gain response across its face (1:2.5), and it has been studied quite throughly (see, for example, [START_REF] Field | Development of photon detectors for FDIRC[END_REF] and [START_REF] Gargano | Study of H8500 MaPMT for the FDIRC detector at SuperB[END_REF]). Very recently another Hamamatsu tube, R-11265-00-M64, came up for a consideration. Its main attractions are (a) super-bialkali QE of 36%, (b) small 2.8 mm pixels, which would allow small binning in y-direction, and therefore better Cherenkov angle resolution, and (c) small dead space around tube boundaries. We are also considering a SiPMT-arrays, such as Hamamatsu C11206-0808FA, because of a small pixel size and high QE. However, its present noise performance is a concern, which could further increase if neutron doses would reach 10 10 n/cm 2 .

With a H-8500 MaPMT choice, one photon camera would have 48 tubes, the entire FDIRC system 576 tubes and 18,432 pixels (here we assume that two horizontal neighboring pixels would be shorted together, thus making 6 mm × 12 mm pad). If a detector with smaller pixel would be chosen, we would still maintain the total pixel count the same by shorting more small pixels together horizontally where FDIRC optics is a simple pin hole camera, while maintaining small pixels in the y-direction where we do focusing.

One strong point of our design is that we share a total photon background load from a single bar box among 48 H-8500 detectors, and this results in acceptable rate even at the highest luminosity, and an acceptable total charge load after 10 years of operation. After adding shielding appropriately, a preliminary MC simulation [START_REF] Perez | FDIRC background[END_REF] indicates that the contribution from the active detector region inside the magnet is ∼ 50 kHz/double-pixel, and a contribution from the photon camera, which is located outside of magnet, is ∼ 60 kHz/double-pixel.

The final FDIRC electronics will do timing with pseudo-CFD on a chip providing 100 ps resolution per channel, 1 MHz maximum background rate, 50 ps double pulse resolution. There will also be an ADC measurement, allowing PMT monitoring and some improvement of the Cherenkov resolution with the charge sharing. The TDC parameters has 200 ps/count, expected resolution of ∼ 100 ps resolution, dead time at the input of ∼ 25 ns, maximum rate (all channels firing) of 5 MHz/channel, maximum rate (1 channel firing) of 20 MHz/channel, 1% dead time at 500 kHz input rate on all channels, and 3% dead time at 1 MHz input rate on all channels [START_REF] Beigbeder | PID electronics for SuperB[END_REF].

A summary of R&D results up to now

It was very important to build a first FDIRC prototype with a single bar and oil-filled photon camera [START_REF] Benitez | Status of the FDIRC[END_REF]. We learned how to operate new fast highly pixilated detectors [START_REF] Field | Development of photon detectors for FDIRC[END_REF], how to design a new optics, how to do the chromatic correction by timing (this was the very first RICH detector to achieve this). To be able to do such correction, one needs to achieve a timing resolution at a level of 200-250 ps per single photon, and the photon path length needs to be longer than 2-3 meters. The fact that FDIRC bars are longer (due to a penetration of the magnet iron) helps to improve the effect of this correction. We also learned that with 3 mm size pixels we could substantially improve on the FDIRC performance, and realized the role of photon path ambiguities on the Cherenkov angle tail [START_REF] Nishimura | A detailed study of FDIRC prototype with waveform digitizing electronics in cosmic ray telescope using 3D tracks[END_REF].

Expected performance of the final FDIRC

Contributions to the Cherenkov angle resolution per photon and per track are shown in Table 1. Figure 8 shows the expected performance relative to the BaBar DIRC for various photodetector design choices. Figure 7 shows MC simulation of FDIRC expected Cherenkov angle resolution in CRT for H-8500 tube with 6 mm pixels and no chromatic correction. Clearly, a small pixel size and high QE efficiency is crucial to obtain the best possible performance, although a nominal design with H-8500 tube and well-done chromatic corrections is not far back. The FDIRC performance with H-8500 tube and no chromatic corrections would be approximately equivalent to the BaBar DIRC performance. At the end, we will make a conservative choice to make sure that the detector operation is smooth.

Goals of the final FDIRC prototype test in CRT

The FDIRC prototype will be tested at SLAC in CRT using 3D tracks. The tracking system has an angular resolution of ∼ 1.5 mrad, track position resolution of ∼ 5-6 mm, start time resolution of better than ∼ 90 ps (with tracking corrections it may reach ∼ 70 ps), a 1.6 GeV muon low energy cut-off thanks to a 46 inch-thick iron absorber, and a large iron area of 55 inch x 90 inch allowing to reach large range of dip angles. The 3Dtracking capability is very important to understand tails of the Cherenkov angle distribution [START_REF] Nishimura | A detailed study of FDIRC prototype with waveform digitizing electronics in cosmic ray telescope using 3D tracks[END_REF].

We will initially use SLAC amplifier and IRS2 electronics, which is a variant of waveform digitizing electronics [START_REF] Ruckman | [END_REF]. Next year we will incorporate the final SuperB electronics [START_REF] Beigbeder | PID electronics for SuperB[END_REF].

The aim of the CRT test is to (a) verify that the new FDIRC optics works by measuring the Cherenkov angle resolution and its tail, and comparing it with the first FDIRC prototype results, (b) study a role of ambiguities on the Cherenkov angle tail, (c) study the chromatic error correction using 3D tracks, (d) study of several new detector options, and (e) study the FDIRC Cherenkov angle resolution and its tails by adding a random light noise while taking normal CRT data.

Conclusion

We have clearly demonstrated that the photon camera, made of solid fused silica, is build-able. Its main advantage is the radiation hardness, small size, stability and practically no maintenance. It is more expensive compared to oil-based or waterbased designs, but they require a long-term maintenance, which is at the end more expensive if one integrates over 10 years of operation. And fluid-based systems represent higher risk to other subsystems.

Figure 1 :

 1 Figure 1: Optical design of FDIRC photon camera.

Figure 2 :

 2 Figure 2: Parts of the FDIRC photon camera.

Figure 3 :

 3 Figure 3: New wedge glued to the bar box window.

Figure 4 :

 4 Figure 4: Finished FBLOCK, made of solid Corning 7980 fused silica.

Figure 5 :

 5 Figure 5: Details of coupling between FBLOCK, new wedge and bar box. A gap between FBLOCK and new wedge is filled with the RTV.

Figure 6 :

 6 Figure 6: The photon camera and 5m-long bar box installed in the SLAC CRT. The picture shows the FBLOCK focal plane yet to be populated with detectors.

Figure 7 :

 7 Figure 7: MC simulation of FDIRC expected Cherenkov angle resolution in CRT for H-8500 tube with 6 mm pixels and no chromatic correction.

Figure 8 :

 8 Figure 8: Final FDIRC expected PID performance for various detector options compared to the BaBar DIRC performance.

  mm pixels, chromatic correction and R11256-M64 with QE ∼ 36% 1.9

Table 1 :

 1 FDIRC Cherenkov angle error contributions.

Acknowledgments

The authors would like to thank M. McCulloch for help in final assembly of the optics and prototype, M. Zago for the mechanical design of the Fbox and the Padova University mechanical workshop personnel for Fbox construction and assembly. We also thank M. Mongelli and V. Valentini of Bari for Fbox mechanical support structure design and M. Franco for helping to construct it. This work was supported in part by the Department of Energy, Contract DEAC02-76SF00515.

Work supported by US Department of Energy contract DE-AC02-76SF00515.


Steve Jiekak

Anne-Marie Kermarrec

Nicolas Le Scouarnec

Gilles Straub

Alexandre Van Kempen

Regenerating Codes: A System Perspective

The explosion of the amount of data stored in cloud systems calls for more efficient paradigms for redundancy. While replication is widely used to ensure data availability, erasure correcting codes provide a much better trade-off between storage and availability. Regenerating codes are good candidates for they also offer low repair costs in term of network bandwidth. While they have been proven optimal, they are difficult to understand and parameterize. In this paper we provide an analysis of regenerating codes for practitioners to grasp the various tradeoffs. More specifically we make two contributions: (i) we study the impact of the parameters by conducting an analysis at the level of the system, rather than at the level of a single device; (ii) we compare the computational costs of various implementations of codes and highlight the most efficient ones. Our goal is to provide system designers with concrete information to help them choose the best parameters and design for regenerating codes.

I. INTRODUCTION

As cloud-based solutions for backup and sharing are being offered to users, the amount of storage needed for cloud services keeps increasing. In order to lower the costs (e.g., hardware, energy) for operating such systems, it is important to rely on efficient paradigms. Currently, many systems still rely on well-proven replication [START_REF] Ghemawat | The Google File System[END_REF] to provide high availability from non-reliable devices. While easy to understand and implement, replication is far from being optimal with respect to the trade-off between storage and availability [START_REF] Weatherspoon | Erasure Coding Vs. Replication: A Quantitative Comparison[END_REF]- [START_REF] Rodrigues | High Availability in DHTs: Erasure Coding vs. Replication[END_REF]. Arguably, erasure correcting codes can significantly lower the amount of storage needed in data-centers. However, with classical erasure codes (e.g., Reed-Solomon), repairing after a device failure generates many I/Os and requires transferring a large amount of information over the network. In large-scale multisite data-centers, the background network traffic due to repairs can become prohibitive for large amounts of data stored. In this paper, we focus on an attractive alternative, namely regenerating codes [START_REF] Dimakis | Network Coding for Distributed Storage Systems[END_REF], to lower such network costs.

Regenerating codes offer the same properties as erasure correcting codes with respect to storage and availability. Yet, as opposed to erasure correcting codes, regenerating codes significantly lower the network traffic upon repairs. The seminal paper [START_REF] Dimakis | Network Coding for Distributed Storage Systems[END_REF] on regenerating codes applies network coding to storage systems and defines the optimal trade-off between the amounts of data stored and transferred. Regenerating codes, designed to be as generic as possible, rely on many parameters, difficult to grasp in practice where device availability vary from a system to another; let alone the fact that many variants of regenerating codes exist (e.g., [START_REF] Ho | A Random Linear Network Coding Approach to Multicast[END_REF]- [START_REF] Rouayheb | Fractional Repetition Codes for Repair in Distributed Storage Systems[END_REF]).

In order to help choose the right parameters and coding scheme, we make the following contributions:

• We study the influence of the various parameters at the system level, depending on storage device availability. We show that the optimum at device level does not always apply at system level. (Section III) • We compare the computational costs of various coding schemes for regenerating codes (random codes [START_REF] Ho | A Random Linear Network Coding Approach to Multicast[END_REF], product-matrix codes [START_REF] Rashmi | Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction[END_REF], and exact linear codes [START_REF] Suh | Exact-Repair MDS code construction using interference alignment[END_REF]) to the costs of classical erasure correcting codes (Reed-Solomon codes). (Section IV) Previous practical work on regenerating codes focused either only on random codes [START_REF] Duminuco | A Pratical Study of Regenerating Codes for Peer-to-Peer Backup Systems[END_REF] while we consider several other codes; or on a specific system with a specific code [START_REF] Hu | NCFS: On the Practicality and Extensibility of a Network-Coding-Based Distributed File System[END_REF], [START_REF] Hu | NCCloud: Applying Network Coding for the Storage Repair in a Cloud-of-Clouds[END_REF] while we study several codes and give conclusions that can be applied broadly.

II. MODEL AND BACKGROUND

We consider a system of n devices connected by a network. The system stores files of size M that are immutable (i.e., data is appended to the system and once written cannot be modified, as in [START_REF] Calder | Windows Azure storage: A highly available cloud storage service with strong consistency[END_REF]). Devices are available with a probability p due to temporary disconnections (e.g., reboot, software upgrade, short-term network disruption). Devices fail permanently with a rate of λ failures per month per device (e.g., disk crash, device replacement, long-term network disruption).

When using erasure correcting codes, the file is divided into k blocks and n encoded blocks are produced so that any k encoded blocks allow recovering the file: the file remains available as long as at least k devices are available. Hence, the resulting system availability is

A = n i=k n i p i (1 -p) n-i .
Whenever a block is permanently lost, a repair mechanism is used to regenerate it. The repair procedure in erasure correcting codes consists in contacting k live devices, recovering the file and encoding it again to produce a new block. Since the whole data is read from disks and transferred over the network, this procedure has both high I/O costs, which can be reduced using specific codes [START_REF] Khan | Rethinking Erasure Codes for Cloud File Systems: Minimizing I/O for Recovery and Degraded Reads[END_REF], and high network cost, which can be reduced using regenerating codes [START_REF] Dimakis | Network Coding for Distributed Storage Systems[END_REF]. In this paper, we focus on the latter codes reducing network costs.

Regenerating codes apply network coding to storage systems to offer the best trade-off between network bandwidth repair cost γ and storage cost α. The file is divided into k∆ sub-blocks. These k∆ original sub-blocks are encoded into nα encoded sub-blocks which are then spread on the n devices arXiv:1204.5028v2 [cs.DC] 16 Jul 2012

. . × × MBR ∆ = (2d -k + 1)/2 α = d β = 1 MSR ∆ = d -k + 1 α = d -k + 1 β = 1 Storage Repair bandwidth (a) Tradeoff curve     x 1 x 2 x 3 x 4     x 2 + x 3 x 1 + x 2 + x 4 x 1 + x 3 x 2 + x 4 x 3 x 4 x 1 x 2
Encode and spread

x 1 x 2 x 2 + x 3 x 1 + x 3 x 3 Collect Store Repair (b) General scheme (MSR, k = 2, n = 4, d = 3, α = ∆ = 2)
Figure 1. Regenerating codes are optimal with respect to storage and repair cost thanks to efficient repair methods.

(i.e., one group of α sub-blocks is stored on each device) so that contacting any k devices allows recovering the file. Regenerating codes rely on an additional parameter d, which is the number of devices involved in a repair. Whenever a failure occurs, if the number of available devices is at least d, the following optimal repair method, shown in Figure 1b, can be used: (i) the device being repaired fetches β sub-blocks1 from each of d available devices (thus γ = dβ), (ii) the device stores α sub-blocks computed from the dβ sub-blocks it received.

Regenerating codes, as explained in [START_REF] Dimakis | Network Coding for Distributed Storage Systems[END_REF], can be parameterized by the values ∆ and α to minimize either the storage (MSR, Minimum Storage Regenerating) or the bandwidth (i.e., network repair cost) (MBR, Minimum Bandwidth). This tradeoff is illustrated on Figure 1a.

The seminal paper about regenerating codes relies on randomized code constructions, namely random linear network codes [START_REF] Ho | A Random Linear Network Coding Approach to Multicast[END_REF]. With such codes, the repaired data is not strictly equal to the lost data. As a first consequence, such codes cannot be maintained in a systematic form. Systematic codes suppresses decoding costs and allows direct access to small parts of the file since the file can be read directly from the k first blocks (or kα first sub-blocks) without decoding. As a second consequence, checking the integrity of such randomized codes requires to use complex techniques. In order to solve these two issues, it has been proposed to rely on exact regenerating codes [START_REF] Dimakis | A Survey on Network Codes for Distributed Storage[END_REF]. Various code constructions have been proposed with two of the most advanced ones being by Suh et al. [START_REF] Suh | Exact-Repair MDS code construction using interference alignment[END_REF] and by Rashmi et al. [START_REF] Rashmi | Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction[END_REF]. In Section IV, we will compare the computational costs of these schemes with the randomized code constructions [START_REF] Ho | A Random Linear Network Coding Approach to Multicast[END_REF] and regular Reed-Solomon erasure correcting codes.

Finally, in regenerating codes [START_REF] Dimakis | Network Coding for Distributed Storage Systems[END_REF], the number d of devices to contact during repairs is chosen once for all and cannot be changed. Adaptive regenerating codes [START_REF] Kermarrec | Repairing Multiple Failures with Coordinated and Adaptive Regenerating Codes[END_REF] relax this constraint and allow d to adapt to each repair. However, adaptive regenerating codes currently can only be implemented with random linear network codes, which have a high complexity and require costly schemes for integrity checking. In the following section, adaptive regenerating codes are included for they show the best achievable theoretical bound, yet further research is needed before they can be used in practice. To repair "static" regenerating codes when less than d devices are available, k available devices must be chosen and the repair must be carried by decoding the file before encoding it again leading to a cost γ ′ = k∆ as with regular erasure correcting codes. Hence, finding the right value for d is important to avoid using this expensive repair by decoding method.

In the sequel of the paper, we study regenerating codes and focus on MSR codes, which offer the same trade-off between storage and availability as Reed-Solomon codes.

III. SYSTEM LEVEL ANALYSIS

In this section, we consider several levels of device availability and study regenerating codes by performing an analysis at the system level for it matches the real costs observed. At the device level, the storage cost is α and the repair cost (i.e., network bandwidth) is γ. Hence, at the system level, the storage cost is nα and the repair cost is Γ = nλγ. The cost at the device level is known for decreasing as n increases. However, this conclusion does not apply at the system level. This section shows some interesting interactions between parameters. In the settings shown on the plots in the rest of the paper, we consider one file of size M = 64MB and a failure rate of λ = 1 failure per month. The repair cost is given in MB per month per file stored. This cost scales linearly with the number of files, the file size M, and the failure rate λ (i.e., if 10 files are stored or if λ = 10 failures per month, the cost is 10 times higher) thus allowing extrapolating results.

A. How many devices to repair from?

Let us consider that k and n are chosen to reach a given system availability [START_REF] Weatherspoon | Erasure Coding Vs. Replication: A Quantitative Comparison[END_REF]- [START_REF] Rodrigues | High Availability in DHTs: Erasure Coding vs. Replication[END_REF]. Regenerating codes require choosing an additional parameter d, which is the number of live devices contacted during a repair. Theoretical papers suggest that the best value for d is d opt = n -1. However, it turns out that this choice is not the best as soon as the device availability is p < 1 as we explain in this section.

Let us define the probability that exactly i devices are available as P (X = i) = n i p i (1 -p) n-i . We define G = g(X) as the cost of the repair when X devices are available. If i ≥ d, we repair using the optimal method (i.e., g(i) = M k d ∆ ), otherwise we repair by decoding the whole file (i.e., g(i) = M). The expected cost at the system level is available2 , the repair is simply delayed. To this end, we plot the system repair cost as nλ E(G) P (k≤X≤n-1) . According to theoretical studies [START_REF] Dimakis | Network Coding for Distributed Storage Systems[END_REF], a high value for d helps reducing the cost of repairs at the device level. Yet, this also increases the probability that less than d devices are available thus leading to more frequent repairs by decoding. Hence, there should be an optimal value for d. For always available devices (p = 1), it appears that d opt = n -1, as stated in [START_REF] Dimakis | Network Coding for Distributed Storage Systems[END_REF].

E(G) = n-1 i=k P (X = i)g(i).
On Figure 2a, we consider a system relying on an MSR code with n = 32 and k = 16. We consider various device availabilities p and plot the system level cost as a function of d. We observe that the cost function admits an optimal value for d. For low to medium availabilities (p = 0.5 to p = 0.9), the optimal value for d is rather low (much lower than n -1 value suggested by the literature [START_REF] Dimakis | Network Coding for Distributed Storage Systems[END_REF]). For high availability p = 0.99, the optimal value is close to n -1 but is still d opt = 29 (d opt = n -3). Moreover, choosing d = 31 instead of d = 29 when p = 0.99 more than doubles the repair cost. Hence, as soon as devices are not highly available (p = 1), the designer must choose d according to the device availability observed in the system to best leverage regenerating codes.

The repair cost for erasure correcting codes is the same as the cost for regenerating codes with d = k = 16. For high device availability (p = 0.99), regenerating codes with d = d opt offer a 10 time improvement over erasure correcting codes. For medium availability (p = 0.7), with relatively low d opt = 19, regenerating codes still offer a 3 time improvement over erasure correcting codes.

As explained, the system is rather sensitive to the choice of value d. This calls for codes where d can be changed on the fly, namely adaptive regenerating codes [START_REF] Kermarrec | Repairing Multiple Failures with Coordinated and Adaptive Regenerating Codes[END_REF], which are similar to MSR codes. These codes may seem more practical since they can self-adapt to the system, yet they currently lack practical code designs.

Figure 2b plots repair costs for optimal adaptive regenerating codes (ARC) in bold lines alongside regular codes in thin lines 3 . An interesting observation is that adaptive regenerating codes, initially designed for highly dynamic systems, perform particularly well in rather stable systems. Indeed, when compared to MSR with optimal d, they provide an improvement of 80% in rather stable systems (p = 0.99), whereas in highly dynamic systems (p = 0.5) the improvement is only 10%.

B. How to choose the redundancy level?

As with classical codes, the amount of redundancy must be chosen so that the resulting availability

P (X ≥ k) = n i=k n i p i (1 -p) n-i is at least the desired availability A.
This guides the values of the parameters k and n as studied in [START_REF] Weatherspoon | Erasure Coding Vs. Replication: A Quantitative Comparison[END_REF]- [START_REF] Rodrigues | High Availability in DHTs: Erasure Coding vs. Replication[END_REF]. Yet, with regenerating codes, it might be interesting to sacrifice storage efficiency in favor of repair cost by either increasing n or relying on MBR codes instead of MSR codes. The first approach increases the number of devices redundant data is spread on, while the latter increases the amount of redundant data on each device without changing n. We study MSR codes and set n to get the lowest possible repair cost without constraints on the system availability A.

Let us consider that p ≈ 1 and hence d = n -1. As initially observed by Dimakis et al. [START_REF] Dimakis | Network Coding for Distributed Storage Systems[END_REF], very large n, thus allowing very large d = n -1 does not necessarily helps in reducing costs. Indeed, the system level repair cost nλγ admits a minimum at

n opt = k + √ k 2 -k.
When k is large enough, n opt ≈ 2k. We perform a similar study when p < 1. For each possible value n, we choose the corresponding value d that offers the lowest cost. This effect is shown on Figure 2c. When applying this procedure for multiple values of p and k, we observe that d opt ≈ 2k and n opt ≈ k × c(p) where c(p) is a constant that depends only on p as shown on Figure 3a. n opt is chosen so that on average, the number of devices available for repair is approximately d opt . These curves also show that for low values (p, k), regenerating codes cannot operate efficiently for any value (n, d) and erasure-correcting codes (n = k + 1, d = k) offer the lowest repair cost (but also a low reliability) for such (p, k). However, slightly increasing k is sufficient to leverage regenerating codes in spite of low device availabilities p.

We now study MBR as an alternative to MSR. Indeed, increasing n beyond the value needed to ensure the required availability for the file, consists in globally increasing the redundancy above the minimal level. Using MBR also increases the redundancy but avoids increasing n (and hence the system failure rate nλ). To this end, we compare storage and repair bandwidth of MSR, MBR and Adaptive codes (ARC) for various system unavailabilities (Fig. 3b) given a device availability of p = 0.99. Overall, MBR consumes twice the storage space needed for MSR or ARC. MBR significantly reduce the bandwidth consumption. The system designer should choose MBR or MSR depending on resources she wishes to save. ARC 4 approach and even outperform MBR with respect to bandwidth without sacrificing the storage efficiency (as efficient as MSR) thus significantly improving high availability systems. Yet, currently, no practical code designs for ARC are known. This represents a challenging research agenda for theoretical work.

IV. COMPUTATIONAL PERFORMANCE

Various code designs exist to implement regenerating codes. These codes rely on various algorithms and data structures, leading to different costs when implemented. In this section, we consider both CPU processing and memory costs. We compare the following most significant codes, which are Reed-Solomon codes for erasure correcting codes, and random linear network codes [START_REF] Ho | A Random Linear Network Coding Approach to Multicast[END_REF], exact linear codes [START_REF] Suh | Exact-Repair MDS code construction using interference alignment[END_REF] and product-matrix codes [START_REF] Rashmi | Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction[END_REF] for MSR regenerating codes.

A. Memory costs

We briefly study the costs associated with the data structures needed to be loaded in memory for encoding and decoding.

Reed-Solomon codes are linear codes which rely on an n×k matrix containing elements of q bits. For k = 16, n = 32, q = 16, the resulting encoding matrice is of size 1 Kbytes.

Linear network codes (random linear network codes [START_REF] Ho | A Random Linear Network Coding Approach to Multicast[END_REF] or exact linear codes [START_REF] Suh | Exact-Repair MDS code construction using interference alignment[END_REF]) rely on an kα × n∆ (approximately k 2 × nk for MSR codes). For k = 16, n = 32, q = 16, the resulting encoding matrice is of size 256 Kbytes.

The product-matrix codes [START_REF] Rashmi | Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction[END_REF] rely on a more compact scheme and the encoding matrix is of size n × 2α (approximately n × 2k for MSR codes). For k = 16, n = 32, q = 16, the resulting encoding matrice is only 2 Kbytes.

Overall, when considering 64 MB data blocks (typical in cloud storage systems), the memory requirements for these matrices is negligible. Moreover, apart for random linear network codes, which are non-deterministic codes, the encoding matrices, which are the same for all files, are created using a deterministic process and need not be stored since they can be re-created on the fly when needed. As a consequence, memory costs, even if higher for regenerating codes than for erasure correcting codes, are only a minor issue and are not relevant for choosing one particular code design over another. However, as we will explain hereafter, the processing costs are a true limitation and vary greatly from one code design to another.

B. CPU costs

To compare the processing costs, we implemented in Java several MSR codes. All codes implementations have similar levels of optimization and rely on a log-table based finite field implementation 5 . We ran these mono-threaded implementations on a Pentium E2200.

We implemented (i) random linear network codes (RL) [START_REF] Ho | A Random Linear Network Coding Approach to Multicast[END_REF], (ii) exact linear codes (EL) [START_REF] Suh | Exact-Repair MDS code construction using interference alignment[END_REF] 6 , (iii) product-matrix codes that use a compact representation of codes with efficient encoding and decoding algorithms (PM) [START_REF] Rashmi | Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction[END_REF], and (iv) Reed-Solomon erasure correcting codes (RS) [START_REF] Reed | Polynomial Codes Over Certain Finite Fields[END_REF].

Regular erasure correcting codes (e.g., Reed-Solomon) involve linear operations on matrices of size k × k. Such operations have a reasonable complexity Ω(k 2 ). However, regenerating codes involve the same linear operations but on matrices of size kα × n∆ (approximately 2k 2 × k 2 when n = 2k and d = n-1). Consequently, naive linear implementations (EL, RL) [START_REF] Ho | A Random Linear Network Coding Approach to Multicast[END_REF], [START_REF] Suh | Exact-Repair MDS code construction using interference alignment[END_REF], [START_REF] Duminuco | A Pratical Study of Regenerating Codes for Peer-to-Peer Backup Systems[END_REF] suffer from a complexity of Ω(k 4 ) and have high computational costs even for low values of k. It can be observed that Product-Matrix codes [START_REF] Rashmi | Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction[END_REF] (PM) rely on efficient algorithms departing from classical linear approaches thus lowering costs as shown here.

Figure 4 shows the time needed to process a file of size M = 16MB depending on the parameter k. When considering the encoding (Figure 4a), all regenerating codes (PM, EL, RL) perform worse than regular erasure correcting codes (RS). However, it is interesting to notice that product-matrix codes (PM) clearly outperform regular linear regenerating codes codes (EL, RL). The two linear regenerating codes rely on the same encoding and decoding algorithm, yet, exact linear codes (EL) clearly outperform random linear network codes (RL). Indeed, the encoding matrix of exact linear codes (EL) is much sparser than the one of random linear network codes (RL). Overall, these results are consistent with the asymptotic complexities discussed in the previous paragraph. When considering the repair time (Figure 4b), all regenerating codes (PM, EL and RL) exhibit similar costs, with a slight advantage for random linear network codes (RL) because their randomized repair procedure is simpler. Reed-Solomon codes, whose repair rely on a costly decoding followed by an encoding suffer a cost that increase with k and that is higher than the cost of all regenerating codes schemes. As a consequence, when repair are frequent, it can be more interesting from a computational point of view, to use regenerating codes even if encoding and decoding are more costly.

When considering the decoding time, Reed-Solomon (RS) codes have a low cost thanks to a specific decoding algorithm and small encoding matrices. Product-matrix codes (PM) have a reasonable cost that is much lower than the other regenerating codes (EL, RL). Indeed, product-matrix codes use a specific decoding algorithm much more efficient than the algorithm used for other regenerating codes (EL, RL).

Figure 5 shows that the encoding time, the repair time and the decoding time scale linearly with the file size M, and confirms the relatively good performance of product matrix codes (PM), and the poor performance of linear codes (EL, RL) when compared to classical erasure correcting codes (RS).

Figure 6 studies the additional cost of relying on systematic codes. Systematic codes are interesting because the k first devices store non-encoded data. As a result, when performing a read on such codes, no decoding is needed (i.e., the decoding cost is null). Reed-Solomon codes use a specific encoding matrix that encodes directly to a systematic form. As this matrix is sparser than the matrix for the non-systematic version, the systematic Reed-Solomon (S RS) is faster than the non-systematic version (RS). On the contrary exact linear regenerating codes (S EL) use a matrix that is costly to create and that is denser than the original one leading to higher costs.

Finally, product matrix codes rely on a pre-coding step that is performed before the encoding step. This precoding step uses an algorithm similar to the decoding algorithm and as such increases the costs: the systematic product matrix codes (S PM) are more costly than the non-systematic ones (PM).

Hence, product-matrix codes are good candidates for replacing Reed-Solomon codes in practical systems. Their impact on memory and CPU remains limited. As shown on Figure 5b, their non-systematic form only doubles the encoding costs and quadruples the decoding costs when compared to nonsystematic Reed-Solomon codes. Their systematic form multiplies by 7 the encoding costs when compared to systematic Reed-Solomon codes. Systematic product-matrix codes should be preferred when data is read more frequently than it is written, otherwise non-systematic codes are more efficient.

For MBR codes, which are not the focus of this paper, Fractional Repetition Codes [START_REF] Rouayheb | Fractional Repetition Codes for Repair in Distributed Storage Systems[END_REF], not implemented in this benchmark, perform very well since they rely on an efficient systematic pre-code (e.g. Reed-Solomon) to produce encoded sub-blocks that are then replicated on several devices. Repairs and reads are performed using simple transfers without any computation. The two other implementations of MBR codes are random linear network codes based [START_REF] Ho | A Random Linear Network Coding Approach to Multicast[END_REF] or product-matrix codes based [START_REF] Rashmi | Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction[END_REF], and since they use the same algorithms at the MBR and the MSR point, they will behave similarly to their MSR implementation (PM and RL).

V. CONCLUSION AND DISCUSSION

We study the impact of various parameters of regenerating codes since they can have significant impact at the system scale. First, despite common belief, d opt is not necessarily d opt = n -1 and instead should be carefully tuned due to its high impact on the repair method efficiency at the . Performance for systematic codes. The repair procedure remains unchanged (see Figure 4). No decoding is needed when accessing the file.

system level. Even for high device availability p = 0.99 where d = n -1 seems reasonable, we get a two time improvement by choosing d = n -3. Second, the lowest repair cost for MSR codes is obtained with d = 2k and n = k × c(p) with c(p) a constant depending on the device availability. Third, if sufficient system availability is achieved with a rather low n, the designer needing to further lower repair cost should favor MBR over using MSR with artificially increased n because MBR allows achieving lower repair cost at the system scale. Finally, since adaptive regenerating codes theoretically outperform both MSR and MBR at the system level when looking at the amount of data transferred; providing exact code designs for ARC can be a promising theoretical research area that would allow implementing ARC in practical systems. We also study the computational costs associated with the various coding schemes available. We show that the additional cost of using regenerating codes (product-matrix codes [START_REF] Rashmi | Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction[END_REF]) is reasonable. We have shown that non-systematic productmatrix codes outperform other linear code designs and only double (resp. quadruple) the cost of encoding (resp. decoding) when compared to Reed-Solomon codes. Systematic productmatrix codes multiply by seven the cost of encoding when compared to systematic Reed-Solomon codes. Hence productmatrix codes keep computational costs within reasonable values given the savings in term of network bandwidth they allow to achieve. As a perspective, to lower systematic codes computational costs, it would be interesting to design productmatrix like codes that encode directly to a systematic form without requiring a pre-processing step.

Interesting perspectives and ongoing theoretical work for applying regenerating codes to practical system concern the minimization of I/Os jointly with network repair cost and storage cost. Indeed, we focused on regular regenerating codes minimizing the network cost. In some systems, minimizing the I/O (disk reads) is equally important. Regenerating codes are not incompatible with this consideration and this research subject is active. Recent work has optimized I/O cost by relying either on specific coding schemes [START_REF] Cadambe | Optimal Repair of MDS Codes in Distributed Storage via Subspace Interference Alignement[END_REF], [START_REF] Rouayheb | Fractional Repetition Codes for Repair in Distributed Storage Systems[END_REF] or considering variations of regenerating codes [START_REF] Kiani | Selective Regenerating Codes[END_REF], [START_REF] Papailiopoulos | Simple Regenerating Codes: Network Coding for Cloud Storage[END_REF]. Also, reducing I/O is an interesting application for coordinated regenerating codes [START_REF] Kermarrec | Repairing Multiple Failures with Coordinated and Adaptive Regenerating Codes[END_REF] that support repairing multiple devices at once. Indeed, if instead of performing t successive repairs, t repairs are slightly delayed and performed at once in a coordinated way, the I/O for repairs are factored thus reducing the overall I/O by a factor t without jeopardizing the optimality with respect to network.

  When less than k devices are k = 16, n = 32 (MSR) k = 16, n = 32 (ARC in bold, MSR in thin)

Figure 2 .

 2 Figure 2. System level repair cost as a function of d and n. The repair cost admits a minimum that is not dopt = n -1.

16 Figure 3 .

 163 Figure 3. The lowest repair cost is for dopt ≈ 2k and nopt ≈ k × c(p) (3a). Optimal storage and bandwidth (3b).

Figure 4 .Figure 5 .

 45 Figure 4. Performance for M = 16MB. Reed-Solomon decode the file and encode the lost block at each repair.

Figure 6

 6 Figure 6. Performance for systematic codes. The repair procedure remains unchanged (see Figure4). No decoding is needed when accessing the file.

In the rest of the paper, we will focus on scalar codes (β = 1) for the sake of clarity and for they have lower computational costs. Vector codes (β > 1) have higher computational costs but are useful for reducing I/Os.

This case remains rare as the system availability P (X ≥ k) is high.

When using adaptive regenerating codes[START_REF] Kermarrec | Repairing Multiple Failures with Coordinated and Adaptive Regenerating Codes[END_REF], repairs are performed independently to compare to MSR and MBR on a fair basis (i.e., no coordinated multiple repairs).

Again, for the comparison to be fair, repairs are performed independently without relying on coordinated multiple repairs capability of ARC, which would reduce bandwidth consumption even more.

Computational costs using multiplication-table based finite field implementations are 30% lower but with such finite field implementation k is limited because of constraints on field size. These plots, as well as plots showing that all computational costs scale linearly with the file size, were omitted due to limited space.

[START_REF] Ho | A Random Linear Network Coding Approach to Multicast[END_REF] We use a linear implementation of product-matrix codes[START_REF] Rashmi | Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction[END_REF], leading to constructions similar to[START_REF] Suh | Exact-Repair MDS code construction using interference alignment[END_REF].