Eric Larose
email: eric.larose@ujf-grenoble.fr

Arnaud Derode

Dominique Clorennec

Ludovic Margerin

Michel Campillo

Passive Retrieval of Rayleigh Waves in Disordered Elastic Media

When averaged over sources or disorder, cross-correlation of diffuse fields yield the Green's function between two passive sensors. This technique is applied to elastic ultrasonic waves in an open scattering slab mimicking seismic waves in the Earth's crust. It appears that the Rayleigh wave reconstruction depends on the scattering properties of the elastic slab. Special attention is paid to the specific role of bulk to Rayleigh wave coupling, which may result in unexpected phenomena like a persistent time-asymmetry in the diffuse regime.

I. INTRODUCTION

Whatever the type of waves involved, knowing the Green's function of an heterogeneous medium is the key to many essential applications like imaging, communication or detection. In the last twenty years or so, mesoscopic physics has intensely studied wave phenomena in strongly disordered media: weak and strong localization, radiative transfer and diffusion approximation etc. [1]. But the exact Green's function of a complex medium is not easily tractable, and usually theoreticians study ensemble-averaged quantities like statistical correlations of intensities or wave fields. Moreover, from an experimental point of view, it is not always possible to measure the Green's functions of a complex medium because it requires controllable arrays of sources and receivers that do not perturb the medium. In the context of laboratory ultrasound, this is (nearly) routine; but in other fields of wave physics like seismology, distant sources are not controllable. In that respect, a good deal of publications followed recent works by Weaver. He proposed to cross-correlate the diffuse wave fields obtained at two passive sensors and showed it yields the elastic Green's function between the two receivers, as if one of the receivers was a source [2,3]. That correlations performed on passive sensors should yield the wave travel times is not that new. This principle was applied to helioseismology in the 90's where it provided tomographic images of the Sun's interior [4,5]. Beyond travel time reconstruction, Weaver's experimental retrieval of exact Green's functions was a real breakthrough.

Weaver's work has been followed by different contributions. Some theoretical works are based on the ergodic approximation where time and ensemble average coincide. This approach is very useful for estimating the role of scattering in the correlation asymmetry [6,7].

When several sources are available, another possibility is to average correlations over sources without moving the receivers. This was done in underwater acoustics [8]. Sabra et al [9] showed the possibility of recovering the entire Green's function of the sea waveguide (especially the late contributions of multiples) and proposed a model for estimating the signal-to-noise ratio of the correlations. Derode et al [10] proposed to interpret the Green's function reconstruction in terms of a Time-Reversal analogy, and showed that all the benefits of time-reversal devices in multiple scattering media could be fruitfully applied to "passive imaging" from correlations [11,12]. This idea is based on the mathematical principle of the representation theorem [START_REF] Aki | Quantitative Seismology[END_REF], equivalently referred to as the Helmholtz-Kirchhoff theorem [START_REF] Cassereau | [END_REF]: if a perfect series of receivers has been sensing the wave field for ages, then one can mathematically have access to the wave field anytime and anywhere in the area enclosed by the sensors. Very recently, this principle was fully developed and applied to elastic waves in open media by Wapenaar [15].

From the very start of Weaver's work, the correlation principle was successfully applied to seismic waves [17,18,19]. The most energetic part of the Green's function between two seismic stations (Rayleigh and Love wave trains) was retrieved from passive correlations of either coda waves or records of seismic noise. As we mentioned earlier, obtaining impulse responses without a controllable source is of high interest in seismology since it gives the possibility of simulating very energetic and punctual earthquakes everywhere around the Earth, and do imaging without a controllable source ("passive imaging"). Results are quite encouraging although several theoretical problems remain unsolved. They concern issues very specific to the Earth. In particular elastic sources (earthquakes) are naturally never arranged in such a way that they would perfectly surround a couple of seismic stations. In addition, for distant earthquakes, the propagation directions of incident bulk waves are mostly vertical, and in a vertically layered medium they would not couple with Rayleigh waves.

FIG. 1: 10 6 → 1 scaled analogy between the Earth crust and our ultrasonic experiment. In the crust, the scattering mean free path was estimated in Mexico [16] at 1 Hz: ℓ * = 30 km. In the aluminum waveguide we numerically found ℓ * = 5.5 mm at 1 MHz.

So, why do we observe a Rayleigh wave train in the correlation of waves generated by bulk sources? The Green's Function retrieval is linked to equipartition, which is due to wave scattering. So, what is the influence of scattering within the Earth crust in that process?

Here we present experimental results obtained in the lab with laser-induced and laser-detected ultrasonic waves propagating in a heterogeneous slab mimicking the Earth crust. Lots of previous experimental articles applied the "passive imaging" technique to acoustic waves. Here we propose to investigate the emergence of the Green's function in the correlations of elastic waves propagating in a solid heterogeneous medium with a free surface. Because field experiments are tedious and natural environment are mostly unknown (especially the scattering properties), we propose to build an Earth crust model at the scale 1/10 -6 (presented in fig. 1). Waves will be sensed at ultrasonic frequencies at the free-surface of an elastic open medium. In our experiment surface waves are not initially excited. This is different from the work of Malcolm et al [7], where ultrasonic Rayleigh waves were generated on the same surface they were measured. In addition they used a finite cylindrical medium with possibly round trip wave trains whereas our experiment is conducted in a nearly open medium. In our configuration, we would not expect the Rayleigh wave to be reconstructed in the correlation, except if scattering is present and mode conversion between Rayleigh and bulk waves occurs. To verify this assumption and study the role of mode conversion, we used two samples of identical dimensions, one with scatterers the other without.

The next section describes the experimental setup and the propagation medium. Section III presents a short theoretical study of the scattering properties (scatteringcross sections σ of a single scatterer and the transport mean-free paths ℓ * P and ℓ * S of the heterogeneous sample). This study is supported by experimental measurements. In section IV, the passive imaging technique is applied to records acquired at the free surface. Time and frequency analysis are proposed, and a brief discussion on the timesymmetry of the correlations concludes the article.

II. EXPERIMENTAL SET-UP

FIG. 2: Experimental setup : The propagation medium is an aluminum block drilled with 54 vertical cylindrical holes (diameter: 4 mm). A Q-switched Nd:YAG laser shoots on the bottom side 100 pulses (24 ns duration and 280 MW/cm 2 intensity each). On the top side a heterodyne interferometer senses the vertical displacement of the aluminum/air interface. This measure is repeated at 7 different locations (X0 = 0 mm→ X6 = 60 mm) for each source position. Plasticine was stuck on the edges and the four lateral sides to mimic absorbing boundary conditions and avoid the generation of Rayleigh waves by mode conversion at the edges.

The experimental setup is depicted in fig. 2. It was designed to mimic the propagation and scattering of elastic waves through the Earth crust, at ultrasonic frequencies (0.8-3.2 MHz). A duraluminum slab whose dimensions are roughly 10 -6 those of the crust was used. Fifty-four cylindrical holes (radius a = 2 mm) were drilled at random along direction y so that the waves propagating through the slab could undergo multiple scattering. The 2-D spatial Fourier transform of the hole positions was calculated and is almost perfectly flat in the range of ultrasonic wavelengths involved in the experiment, which confirms the absence of spatial correlation between the holes. The density of scatterers was n = 0.0105 mm -2 . Ideally, the slab should have had infinite dimensions along x and y. To approach this condition, we stuck a thick layer of dense plasticine on the lateral sides and edges of the duraluminum sample. It was aimed at creating absorbing boundary conditions and avoiding the generation of Rayleigh waves by mode conversion at the edges. The energy decay time τ abs was initially found to be 23,000 µs. With the plasticine it decreased to 120 µs (see next section for a detailed discussion on the absorption time). We therefore simulated an open slab in the x and y direction with a free surface at the top. Rigorously, the earth crust is a waveguide that partially leaks energy through the Moho to the underlying mantle. To perfectly match this feature we should have placed a infinite medium with a different impedance at the bottom side of the aluminum slab. Yet we think that our results and conclusions do not suffer too much from this omission: the central point of our set-up is to mimic an elastic and scattering medium, infinite in the horizontal directions with a free surface on the top.

The source we employed to simulate earthquakes was a Q-switched Nd:YAG laser that shot 24 ns pulses at the bottom side of the slab (each pulse energy : 9 mJ). Two regimes of elastic wave generation are possible with a laser source [START_REF] Scruby | Laser ultrasonics -Techniques and Application[END_REF]. When the surfacic intensity of the pulse is weak (< 15 MW/cm 2 ), the surface is locally heated up and its dilation creates Rayleigh waves (thermoelastic regime). At higher intensity, the laser evaporates part of the metal. In this ablation regime, both Rayleigh and bulk waves are generated. Theoretical radiation patterns are displayed on fig. 3 for compressional and shear waves. Rigorously, such a source is not truly reproducible since the laser impact can damage the surface. To make the experiment as reproducible as possible while staying in the ablation regime, the shot intensity was no more than 280 MW/cm 2 . A 1 ms record was acquired 100 times without any observable change. In the following experiments, for a satisfactory signal to noise ratio, each impulse response was averaged over 100 consecutive shots.

As to the detection of the free surface motion, it was achieved with a contactless and quasi-punctual device: a heterodyne optical interferometer developed by Royer et al [START_REF] Royer | [END_REF] which has the advantage of a very broadband response (20 kHz-45 MHz) and a sensitivity of 10 -4 Å/ √ Hz. It was mounted perpendicularly to the slab and then provided us with the absolute vertical component of the free surface displacement (top side), with a fine spatial resolution; the size of the laser spot was ∼ 100 µm whereas the typical elastic wavelengths here are ranging between 1 and 10 mm. This is similar to seismology, where sensors are nearly punctual compared to the wavelengths considered (several kilometers at 1 Hz). However seismic sensors usually provide time records of the three components of the displacement field. Here the interferometer only measured the vertical movements of the free surface.

In an elastic body, three different kinds of wave polarization are possible. Compressional (or longitudinal) waves are analogous to acoustic waves in fluids (velocity v P = 6.32 mm/µs in duraluminum). Shear (transverse) waves have two possible polarizations (velocity v S = 3.13 mm/µs): one we call SV (Vertical) in the x-z plane (see fig. 1) and one SH (Horizontal) in the x-y plane. SH waves have no contribution in the z direction and therefore will not be detected by the interferometer. In addition to bulk waves, surface waves exist but here only Rayleigh waves (v R = 2.9 mm/µs) will be taken into account since the others cannot be detected (no vertical displacement). The shortest wavelength in the aluminium slab is 0.9 mm, which is much greater than the duraluminum alloy grain size. Since the orientation of the grains is random, we consider the alloy to be isotropic for elastic waves in the frequency band of interest. Scattering at the grain edge is presumably also negligible compared to scattering by the void cylinders. The overall translational symmetry along y of both the free surface and the cylindrical scatterers avoid any coupling between SH mode and the other SV and P modes. Therefore SH waves will not be considered in our article and SV waves will be referred to as S (shear) waves. The wave propagation in our experiment will be treated as 2-dimensional (and quasi 1-D for the surface Rayleigh waves). Waves initially propagating in the y direction are rapidly absorbed by the plasticine and lost.

The laser source and the laser interferometer could be translated independently: 35 sources and 7 sensing positions were used during the experiment, providing us with a set of 35 × 7 impulse responses. A typical waveform is depicted on fig. 4. Around 1 MHz it is lasting nearly 800 µs, and shows a long diffusive decay comparable to the seismic coda. Due to the strong scattering on the cylindrical cavities, no top-bottom reflection was observed in the data. This confirms the Hz corresponding the optimal level of optical reflection on the sensed surface. After averaging over 100 records we reached the precision of 10 -2 Å. Bottom: intensity averaged over several source/sensor positions.

high diffusive nature of the propagation in the scattering slab. The relevant scattering properties are discussed and evaluated in the next section.

III. WAVE SCATTERING AND TRANSPORT PROPERTIES A. Scattering cross-section of an empty cylinder

In order to evaluate the amount of scattering and mode conversion, we calculated the differential cross-section ∂σ ∂θ and the total scattering cross-section σ of a cylindrical void in a elastic medium excited by a compressional or shear plane wave. A brief description of the calculation is given in the Appendix. For a detailed derivation we refer to [START_REF] Pao | Diffraction of Elastic Waves and Dynamic Stress Concnetration[END_REF][START_REF] Faran | [END_REF]24]. The differential scattering cross-section gives the angular distribution of the scattered surfacic intensity, normalized by the incident surfacic intensity. The total elastic cross-section is σ = ∂σ ∂θ dθ. In 2D it has the dimensions of a length. It corresponds to the scattering strength of an object at a given frequency. In an elastic medium, mode conversion can occur and different cross-sections must be considered. In the case of an incident compressional wave, they are noted σ P P , σ P S and σ P = σ P P + σ P S , respectively for the P to P, P to S and total P elastic cross-sections. We also calculated the elastic cross-sections for an incident shear wave (S), σ SP , σ SS and σ S = σ SP + σ SS .

The differential cross-sections plotted on fig. 5 frequencies ranging from 0.1 MHz to 200 MHz. In average in the frequency band of interest (0.8-3.2 MHz), we obtained σ P = 9.2 mm. This value is comparable to measurements by White [25]. The same calculations were conducted for an incident shear wave, we found an average of σ S = 12 mm in the 0.8-3.2 MHz frequency band. FIG. 6: Elastic (σ) scattering cross-sections calculated for shear (S) and compressional (P) plane wave impinging on a cylindrical void with diameter 4 mm. Between 0.8 and 3.2 MHz, scattering is stronger for shear waves. At high frequencies the elastic cross-sections tend to the limit of twice the geometrical diameter.

B. Transport properties

When the elastic wave propagates through the aluminum slab drilled with holes, it undergoes multiple scattering. Let ϕ(t) (resp. ϕ 0 (t)) be the vertical displacements sensed at the free surface through the scattering (resp. homogeneous) medium. Classically, this field is split into two contributions: the coherent and the incoherent part. The coherent wave is the ensemble-averaged field ϕ(t) (averaged over disorder configurations, here: cylinder's positions). We underline the difference between the coherent and the ballistic wave (i.e. the first arrival). For a detailed discussion about scattering effect on coherent and ballistic waves, see [26]. Away from resonances, the coherent wave can be roughly thought of as an attenuated version of the direct wavefront ϕ 0 (t). When there is no intrinsic dissipation, the energy of the coherent wave decays with the slab thickness H as e -H/ℓ , where ℓ is the elastic mean free path. Assuming a dilute set of scatterers, the elastic mean-free path is simply related to the scatterers density n and their elastic crosssection σ:

ℓ = 1 nσ
From the theoretical scattering cross section calculated above, we find ℓ P = 10.3 mm. In order to measure the mean-free path experimentally, we used two aluminum slabs of exactly the same dimensions. The first served as a reference and provided measurements of ϕ 0 (t) for different source-sensors positions. The second one was drilled with holes. By translating the source-receiver device along the slab, we achieved something very similar to a configurational averaging and measured the energy of the coherent wave ϕ(t) 2 . Between 0.8 and 3.2 MHz, we obtained ℓ P = 9 ± 2.5 mm from these experiments. The intensity of the incoherent part was also studied. The time evolution of the averaged incoherent intensity I(t) = ϕ(t) 2 is governed by another parameter: the transport mean free path ℓ * . In an elastic body, transport quantities have been theoretically defined by [27]:

ℓ * P = 1 n σ S -σ * SS + σ * P S (σ P -σ * P P )(σ S -σ * SS ) -σ P S σ * SP (1)
ℓ * S = 1 n σ P -σ * P P + σ * SP (σ P -σ * P P )(σ S -σ * SS ) -σ * P S σ * SP (2)
with σ * = ∂σ ∂θ cos(θ)dθ. It was evaluated numerically: ℓ * P ≈ ℓ * S = 5.5 mm. In an experiment, this parameter is very hard to measure with a reasonable precision. The coherent backscattering effect [28,29,30,31] (also referred to as weak localization) does give a direct estimation of the transport mean free path but our experimental configuration did not allow this special measurement since we could not place a laser sensor in the vicinity of the laser source. Yet we checked that the experimental intensity decay I(t) gives an order of magnitude for ℓ * that is consistent with the theoretical value.

For the sake of simplicity we propose a 2-D scalar wave model for I(t) [32], under the diffusion approximation. In an infinite slab of thickness H with perfect reflections on both sides, the averaged transmitted intensity reads:

I(X, t) = I 0 1 2H √ πDt + ∞ n=1 (-1) n H √ πDt e -n 2 π 2 Dt H 2 e -X 2 4Dt -t τ abs
with τ abs the absorption time (taking into account the intrinsic absorption in the aluminum and the lateral leaking due to the plasticine) and D the diffusion constant. X is the lateral distance between source and receiver. This formula is obtained using a modal decomposition of the diffusion equation in the z direction. The intensity I(t) is a mix of compressional and shear waves, each mode traveling with its own parameters (velocity, ℓ * , diffusion constant) and interchanging their energy through scattering events. In our experiment ℓ * S and ℓ * P are of the same order. The diffusion constant was approximated by D =

1 2(1+2v 2 P /v 2 S ) (v P ℓ * P + 2v S ( vp vs ) 2 ℓ * S )
≈ 40 mm 2 /µs. This assumption is valid after a couple of mean free times, when the equipartition regime [33] is set. Equipartition means that the density of compressional and trans-verse modes equilibrates. Considering the specific velocities of each mode [34], we infer that 80% of the energy is transported by S waves, and only 19% by P waves (and an additional 1% for surface waves). Hence our best fit (fig. 7) of the intensity decay in the coda gives τ abs = 120 µs±10% and ℓ * = 5 -20 mm.

IV. TWO-POINT CORRELATION OF DIFFUSE FIELDS

In this section we focus on the experimental reconstruction of the direct Green's function from "passive" correlations. The main idea is to correlate diffuse fields sensed at two different locations on the top side when a source generates bulk waves at the bottom. Since we record the vertical component of the surface displacements, the two-point correlations should simulate a vertical source at the surface, which mainly generates surface waves. Indeed, the experimental correlations we obtained reveal a wave packet that travels at the speed of a Rayleigh wave. We insist that our sources do not generate surface waves at the top side of the slab. Moreover if a surface wave happened to be generated anywhere, it would be completely absorbed by the plasticine. Under these conditions no Rayleigh wave should travel on the top surface, and no Rayleigh wave should be passively retrieved by correlations. Why then should passive imaging give rise to a Rayleigh wave train in our experiment?

We propose first to examine the role of scatterers for the emergence of the direct Rayleigh wavefront in the correlations. To that end we separately correlated coda records obtained through two different aluminum slabs: the first drilled with holes, the second without. Each impulse response was lasting ≈ 800 µs before reaching the noise level (see fig. 4). We underline that these record lengths are far from the Heisenberg time (break time) at which the modes of the aluminum block would be resolved (here T H ≈ 10 6 µs) and correlations would naturally converge to the Green's function. This modal approach is unrelevant to our experiment. The records were correlated and averaged over the 35 available sources. For the scattering slab, this reads:

C ij (τ ) = 35 S=1 t=600 µs t=0 µs ϕ(S, X i , t)ϕ(S, X j , t + τ )dt
where X i and X j are the sensors points (running from X 0 = 0 mm to X 6 = 60 mm along the array). And for the homogeneous slab: To enhance the signal-to-noise ratio, each correlation is time symmetrized (= C(+τ ) + C(-τ ) ) and normalized by its maximum. Results are displayed in fig. 8 and9. A propagating wavefront (traveling at the Rayleigh wave velocity v R = 2.9 mm/µs) is clearly visible in the presence of scatterers, whereas it does not appear in the homogeneous slab. We also summed the 6 normalized propagating peaks after having delayed each signal according to the Rayleigh wave travel time. The summation is displayed in the enclosed box on each figure. In the scattering slab, its amplitude nearly corresponds to the coherent addition of 6 pulses. In the homogeneous device, the amplitude of the summation is ≈ 2.5 (incoherent addition of 6 uncorrelated fields). We conclude on the necessity of mode coupling due to scattering for the Rayleigh wave to emerge from the passive correlations of diffuse fields generated by bulk waves sources. This is especially relevant for applications to seismology. Therefore, it appears once again [11] that the role of scattering is crucial in "passive imaging". Firstly, because of multiple scattering, at late times the equipartition regime can be attained whatever the sources/receivers positions. Secondly, because of mode conversions due to the scatterers, a Rayleigh wave emerges from the passive correlations even though no Rayleigh wave was generated by the sources. Note that the bandwidth in the upper band record is a little wider than in the lower band. This was done to compensate for the coda shortening (< 600 µs) so that the product T ∆f is kept constant.

C 0 ij (τ ) = 35
We can go a little further and catch a glimpse of the time symmetry properties.

We performed the correlations into two consecutive time windows: from 0 to 45 µs and from 45 µs to 600 µs, and did not time-symmetrize the correlations (fig. 10 and11). 45 µs is twice the time after which the diffuse energy spreads homogeneously along the array of receivers (length L = 30 mm) : L 2 /4D ≈ 22 µs in an open 2D scattering medium. The time series were filtered in two frequency bands: 0.8-1.6 MHz and 1.6-3.2 MHz.

In the first time-window, from 0 to 45 µs, correlations are asymmetric in time. This means that the causal part (τ > 0) and the acausal part (τ < 0) of the correlations are different (see left part of fig. 10 and fig. 11). In the causal part, a Rayleigh wavefront is clearly visible whereas noise is dominating the acausal part. This is due to the preferential direction of Rayleigh wave propagation (waves traveling from X 0 to X 3 in our experiment). There is a net flux of energy from X 0 to X 1 , X 2 and X 3 (distances 10, 20 and 30 mm in fig. 10 and fig. 11). This flux is due to the uneven distribution of sources in comparison to the receiver couples X 0 -X 1 , X 0 -X 2 and X 0 -X 3 : most of the sources are on the X 0 's side. At the early times of the coda (from 0 to 45 µs), the diffusion regime is not yet attained.

Later in the coda, from 45 µs to 600 µs, the wave field in the bulk of the aluminum slab is very likely to be equipartitioned. In the low frequency band (0.8-1.6 MHz), the time-symmetry of the correlation is indeed restored [6,[START_REF] Paul | [END_REF] (see right part of fig. 10): Rayleigh waves travel in all directions. Nevertheless and surprisingly, the asymmetry persists in the high frequency band (from 1.6 MHz to 3.2 MHz, see right part of fig. 11). To interpret this observation, we have carefully studied the location of the scattering sources around the array. In the high frequency band, the Rayleigh wavelength is ∼ 1.5 mm. The generation of Rayleigh waves by scattering necessarily occurs in the first half-wavelength beneath the free surface [START_REF] Maeda | Proceedings of the Workshop on 'Probing Earth Media Having Small-Scale Heterogeneities[END_REF]. In our scattering slab, one hole was nearly showing on the surface (position X < 0), another one was 0.61 mm beneath (position X > 60 mm), the others being located much deeper. Rayleigh wave trains are mainly generated by the hole nearest to the surface, then propagate along the array of receivers (from X 0 to X 6 point). These waves are almost not perturbed (attenuated) until they reach the edges of the slab and the absorbing plasticine. They contribute to a very clear propagating pulse in the positive part of the correlation. The weak coupling due to the deeper hole (z = -0.61 mm) on the X 6 side contributes to a smaller pulse propagating from X 6 to X 0 in the negative part of the correlations.

This interpretation is in agreement with observations in the low frequency band (0.8-1.6 MHz), where the average Rayleigh wavelength is 3 mm (fig. 10). At least 5 holes are present in the first half wavelength and should cause significant scattering of Rayleigh waves and coupling between surface and bulk waves. This time, the holes are evenly distributed along the sensor array. In the late coda, correlations X 0 × X 1 , X 0 × X 2 and X 0 × X 3 are nearly symmetric. The time symmetry is obtained thanks to scattering by a symmetric distribution of scatterers. Under these conditions, a global equipartition among bulk and surface waves is guaranteed. Furthermore the reconstructed surface wave is strongly attenuated along its path because it senses many scatterrers along the array. In addition, these scatterers contribute signals around τ = 0 in the correlations, which degrade the reconstruction. We think this interpretation explains why the symmetric wavefront is much more noisy at low frequencies (fig. 8), where lots of cavities are encountered in the first half wavelength, than at higher frequencies where the Rayleigh wavefront can propagate freely (fig. 10).

Finally, we comment on the possible misidentification of the waves that are reconstructed in our experiment. Indeed, if many scatterers are present within a wavelength, the overall wave velocity may be different (effective medium).

In the heterogeneous plate, a reduced-speed shear wave might propagate with the same wavespeed as a Rayleigh wave in the bulk aluminium plate (i.e. without cavities). In our experiment, the hole interspacing is 10 mm on average, which is larger than the largest ultrasonic wavelength. Thus, it is reasonable to assume that the shear waves propagate in the aluminium plate with the same wavespeed as in the bulk. The measured wave velocity is 2.9 mm/µs at all frequencies (from 0.8 MHz to 3.2 MHz) and indeed corresponds to the velocity of the Rayleigh wave.

V. CONCLUSION

In this paper were presented laboratory experiments of elastic wave propagation in heterogeneous media at ultrasonic frequencies. An aluminum slab was made quasi-infinite by the use of absorbing boundaries to mimic the Earth's crust, in which scattering was obtained drilling cylindrical cavities. A relatively simple theoretical model for wave scattering properties was proposed. Wave field generation and detection was achieved using contactless and quasi-punctual laser devices. The cross-correlation of diffuse fields was performed, allowing us to retrieve passively the Rayleigh wave between two sensors only when scattering was present. Without scatterers, and in the case of bulk wave generation and surface detection, no Rayleigh wave was reconstructed. This illustrates the role of scattering and mode conversion in the Green's function passive reconstruction.

Analysis for different time-windows and frequency bands were conducted. Previous works in acoustics [37] and seismology [17] observed that the Rayleigh wave reconstruction was harder with increasing frequency. Here we found that the Rayleigh wave reconstruction was more efficient in the high frequency band. In addition we observed that even in the late coda where waves are expected to be equipartitioned, asymmetry in the correlations may remain. Both observations are due to the very specific coupling between bulk and Rayleigh waves, which occurs if scatterers are present in the first wavelength beneath the free surface. We emphasize that equipartition of bulk waves does not always mean equipartition of surface waves. On the one hand, our experiments show the need of scattering to passively retrieve the impulse response between two sensors, on the other hand they show that scattering occurring between the sensors degrade the reconstructed Rayleigh waves. The trade-off between the two effects should be further investigated. Though our experiment was designed for seismological applications, results should be applicable to other fields of wave physics where both surface and bulk waves are present. Here follows a brief calculation of the wave field scattered by a cylindrical cavity insonified by a plane compressional wave. Three displacement potentials are relevant: Φ i is the displacement potential of the incident P wave, Φ s is the scattered P wave potential and Ψ s is the scattered S wave potential. They can be expanded as: where J m and H

m are respectively the Bessel and Hankel functions both of first kind and of order m and ε m is the Neumann factor. Taking into account the null traction condition at the surface of the cylinder allows the calculation of the A m and B m coefficients. Those coefficients are given in [START_REF] Pao | Diffraction of Elastic Waves and Dynamic Stress Concnetration[END_REF][START_REF] Faran | [END_REF]24]. The scattering crosssections are

σ P →P = 2 k P [2|A 0 | 2 + ∞ m=1 |A m | 2 ] σ P →S = 2 k S [ ∞ m=1 |B m | 2 ]
σ P = σ P →P + σ P →S

The corresponding differential scattering cross-sections are given by:

FIG. 3 :

 3 FIG.3: Directivity pattern (linear scale) of the laser source. Rayleigh waves are not taken into account since they are absorbed at the edges. The experiments were carried out in the ablation regime, where bulk waves are much more energetic than in the thermoelastic regime. Compressional wave directivity: thick line, shear wave directivity: dotted line.

FIG. 4 :

 4 FIG.4: Top: typical waveform obtained through the scattering slab around 1 MHz. The sensitivity of the heterodyne interferometer is 10 -4 Å/ √ Hz corresponding the optimal level of optical reflection on the sensed surface. After averaging over 100 records we reached the precision of 10 -2 Å. Bottom: intensity averaged over several source/sensor positions.

FIG. 5 :

 5 FIG.5: Differential scattering cross-sections of a cylindrical cavity calculated for a compressional (P) or shear (S) incident plane wave around 1.2 MHz (top) and 2.4 MHz (bottom). The scattered wave is either compressional (P) or transverse (S). Each pattern is normalized by its maximum.

FIG. 7 :

 7 FIG. 7: Averaged intensity I(t) and theoretical fit for scalar wave diffusion in a 2-D semi-infinite slab with thickness H = 24 mm. ℓ * = 5.5 mm and τ abs = 120 µs.

FIG. 8 :

 8 FIG. 8: Green's function reconstruction for different pairs of receivers. Correlations are averaged over the 35 sources and filtered in the 0.8-1.6 MHz frequency band. On the left (a) are displayed the 7 cross-correlations Cij (τ ) in the diffusive aluminum plate. On the right (b) the 7 cross-correlations C 0 ij (τ ) are obtained in an equivalent aluminum block without any hole, where the mode conversion possibly occurring at the edges was suppressed by the plasticine. The insets show the summation of the 6 wavefronts from X0 = 10 mm to X6 = 60 mm after a time-reduction based on the Rayleigh wave speed (dotted line, vR = 2.9 mm/µs).

FIG. 9 :

 9 FIG. 9: Same figure as fig. 8 except correlations are filtered in the 1.6-3.2 MHz frequency band. The signal-to-noise ratio in (a) is increased compared to the results obtained at lower frequencies.

FIG. 10 :

 10 FIG. 10: Evolution of the asymmetry in the reconstructedGreen's function in the low frequency regime (0.8-1.6 MHz), for early (a) and late (b) times. At early times, the waves are exciting scatterers on one side of the receiving array more than the other. The energy flux is clearly going from the source to the rest of the medium. After 45 µs the field is equipartitioned and the scattering halo fills the array, leading to a more symmetric correlation.

FIG. 11 :

 11 FIG. 11: Evolution of the asymmetry in the reconstructedGreen's function in the high frequency regime (1.6-3.2 MHz), for early (a) and late (b) time windows. At early times, the waves are exciting scatterers preferably on one side of the receiving array. After 45 µs, bulk waves are expected to be equipartitioned, but not Rayleigh waves. Mode conversion to Rayleigh waves mainly occurs at one scattering cavity, leading to an anisotropic energy flux, and an asymmetric correlation.

  APPENDIX A: CALCULATION OF THE SCATTERING CROSS-SECTION OF ACYLINDRICAL CAVITY.

Φ

  i (r, t) = ∞ m=0 ε m i m J m (k P r)cos(mθ)e -iωt Φ s (r, t) = ∞ m=0 A m H (1) m (k P r)cos(mθ)e -iωt Ψ s (r, t) = ∞ m=1 B m H (1) m (k S r)sin(mθ)e -iωt

B

  m i -m sin(mθ)| 2

ACKNOWLEDGMENTS

The authors wish to thank Richard Weaver and Julien de Rosny for fruitful discussions, Xavier Jacob and Samir Guerbaoui for experimental help. This work was supported by the Groupement de Recherche CNRS "Imagerie, Communication et Désordre" (GdR IMCODE 2253) and the CNRS program "DyETI".


A C Resmi

François Taiani
email: francois.taiani@irisa.fr

Fluidify: Decentralized Overlay Deployment in a Multi-Cloud World

As overlays get deployed in large, heterogeneous systems-ofsystems with stringent performance constraints, their logical topology must exploit the locality present in the underlying physical network. In this paper, we propose a novel decentralized mechanism-Fluidify-for deploying an overlay network on top of a physical infrastructure while maximizing network locality. Fluidify uses a dual strategy that exploits both the logical links of an overlay and the physical topology of its underlying network. Simulation results show that in a network of 25,600 nodes, Fluidify is able to produce an overlay with links that are on average 94% shorter than that produced by a standard decentralized approach based on slicing, while demonstrating a sub-linear time complexity.

Introduction

Overlays are increasingly used as a fundamental building block of modern distributed systems, with numerous applications [START_REF] Frey | Heterogeneous gossip[END_REF][START_REF] Gupta | Meghdoot: content-based publish/subscribe over p2p networks[END_REF][START_REF] Kermarrec | Xl peer-to-peer pub/sub systems[END_REF][START_REF] Lakshman | Cassandra: a decentralized structured storage system[END_REF][START_REF] Li | Inside the new coolstreaming: Principles, measurements and performance implications[END_REF][START_REF] Ratnasamy | A scalable contentaddressable network[END_REF][START_REF] Stoica | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF]. Unfortunately, many popular overlay construction protocols [START_REF] Bertier | The gossple anonymous social network[END_REF][START_REF] Jelasity | T-man: Gossip-based fast overlay topology construction[END_REF][START_REF] Voulgaris | Epidemic-style management of semantic overlays for content-based searching[END_REF] do not usually take into account the underlying network infrastructure on which an overlay is deployed, and those that do tend to be limited to a narrow family of applications or overlays [START_REF] Xu | Building topology-aware overlays using global softstate[END_REF][START_REF] Zhang | A construction of localityaware overlay network: moverlay and its performance[END_REF]. This is particularly true of systems running in multiple clouds, in which latency may vary greatly, and ignoring this heterogeneity can have stark implications in terms of performance and latency.

In the past, several works have sought to take into account the topology of the underlying infrastructure to realise network-aware overlays [START_REF] Ratnasamy | Topologically-aware overlay construction and server selection[END_REF][START_REF] Waldvogel | Efficient topology-aware overlay network[END_REF][START_REF] Xu | Building topology-aware overlays using global softstate[END_REF][START_REF] Zhang | A construction of localityaware overlay network: moverlay and its performance[END_REF]. However, most of the proposed solutions are service-specific and they do not translate easily to other overlays. To address this lack, we propose a novel decentralized mechanism-called Fluidify-that seeks to maximize network locality when deploying an overlay network. Fluidify uses a dual strategy that exploits both the logical links of an overlay and the physical topology of its underlying infrastructure to progressively align one with the other. Our approach is fully decentralized and does not assume any global knowledge or central form of co-ordination.

The resulting protocol is generic, efficient, scalable. Simulation results show that in a network of 25,600 nodes, Fluidify is able to produce an overlay with links that are on average 94% shorter than that produced by a standard decentralized approach based on slicing, while converging to a stable configuration in a time that is sub-linear (≈ O(n 0.6 )) in the size of the system. The remainder of the paper is organized as follows. We first present the problem we address and our intuition (Sec. 2). We then present our algorithm (Sec. 3), and its evaluation (Sec. 4). We finally discuss related work (Sec. 5), and conclude (Sec. 6).

Background, Problem, and Intuition

Overlay networks organize peers in logical topologies on top of an existing network to extend its capabilities, with application to storage [START_REF] Ratnasamy | A scalable contentaddressable network[END_REF][START_REF] Stoica | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF], routing [START_REF] Gupta | Meghdoot: content-based publish/subscribe over p2p networks[END_REF][START_REF] Kermarrec | Xl peer-to-peer pub/sub systems[END_REF], recommendation [START_REF] Bertier | The gossple anonymous social network[END_REF][START_REF] Voulgaris | Epidemic-style management of semantic overlays for content-based searching[END_REF], and streaming [START_REF] Frey | Heterogeneous gossip[END_REF][START_REF] Li | Inside the new coolstreaming: Principles, measurements and performance implications[END_REF]. Although overlays were originally proposed in the context of peer-to-peer (P2P) systems, their application today encompasses wireless sensor networks [START_REF] Grace | Experiences with open overlays: A middleware approach to network heterogeneity[END_REF] and cloud computing [START_REF] Decandia | Dynamo: amazon's highly available key-value store[END_REF][START_REF] Lakshman | Cassandra: a decentralized structured storage system[END_REF].

The problem: building network-aware overlays

One of the challenges when using overlays, in particular structured ones, is to maintain desirable properties within the topology, in spite of failures, churn, and request for horizontal scaling. This challenge can be addressed through decentralized topology construction protocols [START_REF] Jelasity | T-man: Gossip-based fast overlay topology construction[END_REF][START_REF] Leitao | Epidemic broadcast trees[END_REF][START_REF] Montresor | Chord on demand[END_REF][START_REF] Voulgaris | Epidemic-style management of semantic overlays for content-based searching[END_REF], which are scalable and highly flexible. Unfortunately, such topology construction solutions are not usually designed to take into account the infrastructure on which an overlay is deployed. This brings clear advantages in terms of fault-tolerance, but is problematic from a performance perspective, as overlay links may in fact connect hosts that are far away in the physical topology. This is particularly likely to happen in heterogeneous systems, such as multi-cloud deployment, in which latency values might vary greatly depending on the location of individual nodes.

For instance, Fig. 1(a) depicts a randomly connected overlay deployed over two cloud providers (rounded rectangles). All overlay links cross the two providers, which is highly inefficient. By contrast, in Fig. 1(b), the same logical overlay only uses two distant links, and thus minimizes latency and network costs.

This problem has been explored in the past [START_REF] Qiu | Towards location-aware topology in both unstructured and structured p2p systems[END_REF][START_REF] Ratnasamy | Topologically-aware overlay construction and server selection[END_REF][START_REF] Waldvogel | Efficient topology-aware overlay network[END_REF][START_REF] Xu | Building topology-aware overlays using global softstate[END_REF][START_REF] Zhang | A construction of localityaware overlay network: moverlay and its performance[END_REF], but most of the proposed solutions are either tied to a particular service or topology, or limited

(0) (1) (2) (3) (4) (5)
Fig. 2. Example of basic Fluidify approach on a system with n=6 and d=2

to unstructured overlays, and therefore cannot translate to the type of systems we have just mentioned, which is exactly where the work we present comes in.

Our intuition: a dual approach

Our proposal, Fluidify, uses a dual strategy that exploits both an overlay's logical links and its physical topology to incrementally optimize its deployment.

We model a deployed overlay as follows: each node possesses a physical index, representing the physical machine on which it runs, and a logical index, representing its logical position in the overlay. Each node also has a physical and logical neighbourhood: the physical neighbors of a node are its d closest neighbors in the physical infrastructure, according to some distance function d net () that captures the cost of communication between nodes. The logical neighbors of a node are the node's neighbors in the overlay being deployed. For simplicity's sake, we model the physical topology as an explicit undirected graph between nodes, with a fixed degree. We take d to be the fixed degree of the graph, and the distance function to be the number of hops in this topology.

Fig. 2(a) shows an initial configuration in which the overlay has been deployed without taking into account the underlying physical infrastructure. In this example, both the overlay (solid line) and the physical infrastructure (represented by the nodes' positions) are assumed to be rings. The two logical indices 0 and 1 are neighbors in the overlay, but are diametrically placed in the underlying infrastructure. By contrast Fig. 2(c) shows an optimal deployment in which the logical and physical links overlap.

Our intuition, in Fluidify, consists of exploiting both the logical and physical neighbors of individual nodes, in a manner inspired from epidemic protocols, to move from the configuration of Fig. 2(a) to that of Fig. 2(c). Our basic algorithm is organized in asynchronous rounds and implements a greedy approach as follows: in each round, each node n randomly selects one of its logical neighbors (noted p) and considers the physical neighbor of p (noted q) that is closest to itself. n evaluates the overall benefit of exchanging its logical index with that of q. If positive, the exchange occurs (Fig. 2(b) and then Fig. 2(c)).

Being a greedy algorithm, this basic strategy carries the risk of ending in a local minimum (Fig. 3). To mitigate such situations, we use simulated annealing (taking inspiration from recent works on epidemic slicing [START_REF] Pasquet | Autonomous multi-dimensional slicing for large-scale distributed systems[END_REF]), resulting in a decentralized protocol for the deployment of overlay networks that is generic, efficient and scalable. 3 The Fluidify algorithm

(0) (1) (9) (3) (2) (7) (8) (4) (5)

System model

We consider a set of nodes N = {n 1 , n 2 , .., n N } in a message passing system. Each node n possesses a physical (n.net) and a logical index (n.data). n.net represents the machine on which a node is deployed. n.data represents the role n plays in the overlay, e.g. a starting key in a Chord ring [START_REF] Montresor | Chord on demand[END_REF][START_REF] Stoica | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF]. Table 1 summarizes the notations we use. We model the physical infrastructure as an undirected graph G net = (N, E net ), and capture the proximity of nodes in this physical infrastructure through the distance function d net (). In a first approximation, we use the hop distance between two nodes in G net for d net (), but any other distance would work. Similarly, we model the overlay being deployed as an undirected graph G data = (N, E data ) over the nodes N .

Our algorithms use the k-NN neighborhood of a node n in a graph G x , i.e. the k nodes closest to n in hop distance in G x , which we note as Γ k

x (n) . We assume that these k-NN neighborhoods are maintained with the help of a topology construction protocol [START_REF] Bertier | The gossple anonymous social network[END_REF][START_REF] Jelasity | T-man: Gossip-based fast overlay topology construction[END_REF][START_REF] Voulgaris | Epidemic-style management of semantic overlays for content-based searching[END_REF]. In the rest of the paper, we discuss and evaluate our approach independently of the topology construction used, to clearly isolate its workings and benefits. Under the above model, finding a good deployment of G data onto G net can be seen as a graph mapping problem, in which one seeks to optimize the cost function (n,m)∈E data d net (n, m).

Fluidify

The basic version of Fluidiy (termed Fluidify (basic)) directly implements the ideas discussed in Sec. 2.2 (Fig. 4): each node n first chooses a random logical neighbor (noted p, line 2), and then searches for the physical neighbor of p (noted q) that offers the best reduction in cost (argmin operator at line 3)1 . The code shown slightly generalises the principles presented in Sec. 2, in that the nodes p and q are chosen beyond the 1-hop neighborhood of n and p (lines 2 and 3), and consider nodes that are k data and k net hops away, respectively.

G data the logical graph (N, E data ) Γ k net (n) k closest nodes to n in Gnet, in hop distance Γ k data (n)k closest nodes to n in G data , in hop distance
p ← random node from Γ k data data (n) 3: q ← argmin u∈Γ k net net (p) ∆(n, u) 4:
conditional swap(n, q, 0) The potential cost reduction is computed by the procedure ∆(n, u) (lines 5-8), which returns the cost variation if n and u were to exchange their roles in the overlay. The decision whether to swap is made in conditional swap(n, q, δ lim ) (with δ lim = 0 in Fluidify Basic).

5: Procedure ∆(n, u) 6: δn ← (n,r)∈E data dnet(u, r) -(n,r)∈E data dnet(n, r) 7: δu ← (u,r) ∈E data dnet(n, r) -(u,r) ∈E data dnet(u,
To mitigate the risk of local minimums, we extend it with simulated annealing [START_REF] Pasquet | Autonomous multi-dimensional slicing for large-scale distributed systems[END_REF], which allows two nodes to be swapped even if there is an increase in the cost function. We call the resulting protocol Fluidify (SA), shown in Figure 5. In this version, we swap nodes if the change in the cost function is less than a limit, ∆ limit (r), that gradually decreases to zero as the rounds progress (line 4). ∆ limit (r) is controlled by two parameters, K 0 which is the initial threshold value, and r max which is the number of rounds in which it is decreased to 0. In the remainder of this paper, we use Fluidify to mean Fluidify (SA).

1: In round(r) do 2: p ← random node from Γ k data data (n) 3: q ← argmin u∈Γ k net net (p) ∆(n, u) 4:
conditional swap(n, q, ∆ limit (r))

5: Procedure ∆ limit (r) 6: return max 0, K0 × (1 -r/rmax) Fig. 5. Fluidify (SA)

4 Evaluation

Experimental Setting and Metrics

Unless otherwise indicated, we use rings for both infrastructure graph G net and overlay graph G data . We assume that the system has converged when the system remains stable for 10 rounds. The default simulation scenario is one in which the system consists of 3200 nodes, and use 16-NN logical and physical neighborhoods (k net = k data = 16) when selecting p and q. The initial threshold value for simulated annealing (K 0 ) is taken as |N |. r max is taken as |N | 0.6 where 0.6 was chosen based on the analysis of the number of rounds Fluidify (basic) takes to converge.

We assess the protocols using two metrics:

-Proximity -captures the quality of the overlay constructed by the topology construction algorithm. Lower value denotes a better quality. -Convergence time -measures the number of rounds taken by the system to converge.

Proximity is defined as the average network distance of logical links normalized by the diameter of the network graph G net :

proximity = E (n,m)∈E data d net (n, m) diameter(G net ) (1)
where E represents the expectation operator, i.e. the mean of a value over a given domain, and diameter() returns the longest shortest path between pairs of vertices in a graph, i.e. its diameter. In a ring, it is equal to N/2.

Baselines

The performance of our approach is compared against three other approaches.

One is Randomized (SA) (Fig. 6) where each node considers a set of random nodes from N for a possible swap. The other is inspired from epidemic slicing [START_REF] Jelasity | Ordered slicing of very large-scale overlay networks[END_REF][START_REF] Pasquet | Autonomous multi-dimensional slicing for large-scale distributed systems[END_REF], and only considers the physical neighbors of a node n for a possible swap (Slicing (SA), in Figure . 8). The third approach is similar to PROP-G [START_REF] Qiu | Towards location-aware topology in both unstructured and structured p2p systems[END_REF], and it only considers logical neighbours of a node n for a possible swap (PROP-G (SA),

1: In round(r) do 2: S ← knet random nodes from N 3:

q ← argmin u∈S ∆(n, u) 4:

conditional swap n, q, ∆ limit (r) Fig. 6. Randomized (SA)

1: In round(r) do 2: S ← Γ k data data (n) 3:
q ← argmin u∈S ∆(n, u) 4:

conditional swap(n, q, 0)

Fig. 7. PROP-G 1: In round(r) do 2: q ← argmin u∈Γ k net net (n) ∆(n, u)
3: conditional swap n, q, ∆ limit (r) Fig. 8. Slicing (SA)

1: In round(r) do 2: p ← random node from Γ k data data (n) 3: S ← Γ k net 2 net (p) ∪ Γ k net 2 net (n) 4:
q ← argmin u∈S ∆(n, u) 5:

conditional swap(n, q, 0)

Fig. 9. Data-Net & Net 1: In round(r) do 2: p ← random node from Γ k data data (n) 3: S ← Γ k net 2 net (p) ∪ k net 2 rand. nodes ∈ N \ Γ k net 2 net (p) 4:
q ← argmin u∈S ∆(n, u) 5:

conditional swap(n, q, 0)

Fig. 10. Data-Net & R
in Figure . 7). In all these approaches simulated annealing is used as indicated by (SA). The only difference between the above four approaches is the way in which the swap candidates are taken.

To provide further comparison points, we also experimented with some combinations of the above approaches. Fig. 9 (termed Data-Net & Net) is a combination of Fluidify (basic) with Slicing (SA). Fig. 10 (termed Data-Net & R) is a combination of Fluidify (basic) with Randomized (SA). We also tried a final variant, combination-R, in which once the system has converged using Fluidify (basic) (no more changes are detected for a pre-determined number of rounds), nodes look for random swap candidates like we did in Fig. 6.

Results

All the results (Figs. 11-18 and Tables 345) are computed with Peersim [START_REF] Montresor | Peersim: A scalable p2p simulator[END_REF] and are averaged over 30 experiments. The source code is made available in http://armi.in/resmi/fluidify.zip. When shown, intervals of confidence are computed at 95% confidence level using a student t-distribution.

Evaluation of Fluidify (SA)

The results obtained by Fluidify (SA) and the three baselines on a ring/ring topology are given in Table 3 and charted in Figs. 12 and 13. In addition, Fig. 11 illustrate some of the rounds that Fluidify (SA) and Slicing (SA) perform. Fig. 12 shows that Fluidify clearly outperforms the other three approaches in terms of proximity over a wide range of network sizes. Fig 13 charts the convergence time against network size in loglog scale for Fluidify and its competitors. Interestingly all approaches show a polynomial convergence time. This shows the scalability of Fluidify even for very large networks. If we turn to Tab. 3, it is evident that as the network size increases, the time taken for the system to converge also increases. Both Fluidify and Slicing (SA) converges around the same time with Slicing (SA) converging a bit faster than Fluidify. Randomized (SA) takes much longer (almost twice as many rounds). PROP-G (SA) converges faster in comparison to all other approaches. The better convergence of PROP-G (SA) and Slicing (SA) can be explained by the fact that both approaches run out of interesting swap candidates more rapidly than Fluidify. It is important to note that all approaches are calibrated to consider the same number of candidates per round. This suggests that PROP-G (SA) and Slicing (SA) runs out of potential swap candidates because they consider candidates of lesser quality, rather than considering more candidates faster.

Fig. 14 shows how the proximity varies with round for our default system settings. Initial avg. link distance was around N/4 where N is the network size and this is expected as the input graphs are randomly generated. So the initial proximity was approximately equal to 50%. Fluidify was able to bring down the proximity from 50% to 0.7%. A steep decrease in proximity was observed in initial rounds and later it decreases at a lower pace and finally settles to a were able to perform well in the initial stages but later on the gain in proximity decreases. Slicing (SA) is unable to get much gain in proximity from the start itself and converges to a proximity value of 8.4%. Cumulative distribution of nodes based on the avg. link distance in a converged system for all the three approaches is depicted in Fig. 15. It is interesting to see that nearly 83% of the nodes are having an average link distance less than 10 and 37% were having an average link distance of 1 in the case of Fluidify. But for Slicing (SA) even after convergence, a lot of nodes are having an average link distance greater than 200. Slicing (SA) clearly fails in improving the system beyond a limit. The maximum, minimum and the mean gain obtained per swap in a default system setting using Fluidify is shown in Fig. 16(a). As the simulation progresses the maximum, minimum and the mean value of the cost function per swap in each round starts getting closer and closer and finally becomes equal on convergence. Maximum gain per swap (negative cost) is obtained in the initial rounds of the simulation. Maximum value obtained by the cost function is expected to gradually decrease from a value less than or equal to 3200, which is the initial threshold value for simulated annealing, to 0. Variation of cost function for Randomized (SA) (Fig. 16(b)) and PROP-G (SA) also shows a similar behaviour where the system progresses with a very small gain for a long period of time. The most interesting behaviour is that of Slicing (SA) (Fig. 16(c)) which does not benefit much with the use of simulated annealing. The maximum gain that can be obtained per swap is 32 and the maximum negative gain is 2. This is because only the physically closer nodes of a given node are considered for a swap and the swap is done with the best possible candidate.

The message cost per round per node will be equal to the amount of data that a node exchanges with another node. In our approach the nodes exchange their logical index and the logical neighbourhood. We assume that each index value amounts to 1 unit of data. So the message cost will be 1+k data which will be 17 in default case. The communication overhead in the network per cycle will be equal to the average number of swaps occurring per round times the amount of data exchanged per swap. A single message costs 17 units. So a swap will cost 34 units. In default setting, an average of 2819 swaps happen per round and this amounts to around 95846 units of data per round.

All the four approaches that we presented here are generic and can be used for any topologies. Table . 4 shows how the three approaches fares for various topologies in a default setting. Fluidify clearly out performs the other approaches.

Effects of variants Figure. 17 shows that compared to its variants like Fluidify (basic), combination-R, Data-Net & Net (Fig. 9), Data-Net & R (Fig. 10), Fluidify (SA) is far ahead in quality of convergence. Here also we consider a ring/ring topology with default setting. The convergence time taken by Fluidify is slightly higher compared to its variants as shown in Fig. 18.

Table 5 shows how varying the initial threshold value for Fluidify affects its performance. From the table it is clear that as the initial threshold value increases the proximity that we obtain also become better and better. With a higher threshold value, more swaps will occur and therefore there is a higher chance of getting closer to the global minimum. The threshold value that gives the best performance is used for all our simulations.

Related Work

Fully decentralized systems are being extensively studied by many researchers. Many well known and widely used P2P systems are unstructured. However, there are several overlay networks in which the node locality is taken into account. Structured P2P overlays, such as CAN [START_REF] Ratnasamy | A scalable contentaddressable network[END_REF], Chord [START_REF] Stoica | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF], Pastry [START_REF] Rowstron | Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems[END_REF], and Tapestry [START_REF] Zhao | Tapestry: An infrastructure for fault-tolerant wide-area location and routing[END_REF], are designed to enhance the searching performance by giving some importance to node placement. But, as pointed out in [START_REF] Ratnasamy | Can heterogeneity make gnutella scalable?[END_REF], structured designs are likely to be less resilient, because it is hard to maintain the structure required for routing to function efficiently when hosts are joining and leaving at a high rate. Chord in its original design, does not consider network proximity at all. Some modification to CAN, Pastry, and Tapestry are made to provide locality to some extent. However, these results come at the expense of a significantly more expensive overlay maintenance protocol. One of the general approaches used to bridge the gap between physical and overlay node proximity is landmark clustering. Ratnasamy et al. [START_REF] Ratnasamy | Topologically-aware overlay construction and server selection[END_REF] use landmark clustering in an approach to build a topology-aware CAN [START_REF] Ratnasamy | A scalable contentaddressable network[END_REF] overlay network. Although the efficiency can be improved, this solution needs extra deployment of landmarks and produces some hotspots in the underlying network when the overlay is heterogeneous and large. Some [START_REF] Zhang | A construction of localityaware overlay network: moverlay and its performance[END_REF] [29] have proposed methods to fine tune the landmark clustering for overlay creation. The main disadvantage with landmark system is that there needs to be a reliable infrastructure to offer these landmarks at high availability. Application layer multicast algorithms construct a special overlay network that exploits network proximity. The protocol they use are often based on a tree or mesh structure. Although they are highly efficient for small overlays, they are not scalable and creates hotspots in the network as a node failure can make the system unstable and difficult to recover. Later proximity neighbour selection [START_REF] Castro | Topology-aware routing in structured peer-to-peer overlay networks[END_REF] was tried to organise and maintain the overlay network which improved the routing speed and load balancing. Waldvogel and Rinaldi [12] [28] propose an overlay network(Mithos) that focuses on reducing routing table sizes. It is a bit expensive and only very small overlay networks are used for simulations and the impact of digression is not considered.

Network aware overlays are used to increase the efficiency of network services like routing, resource allocation and data dissemination. Works like [START_REF] Matos | Lightweight, efficient, robust epidemic dissemination[END_REF] and [START_REF] Doerr | Epidemic algorithms and processes: From theory to applications[END_REF] combines the robustness of epidemics with the efficiency of structured approaches in order to improve the data dissemination capabilities of the system. Gossip protocols which are scalable and inherent to network dynamics can do efficient data dissemination. Frey et al. [START_REF] Frey | Heterogeneous gossip[END_REF] uses gossip protocols to create a system where nodes dynamically adapt their contribution to the gossip dissemination according to the network characteristics like bandwidth and delay. Kermarrec et al. [START_REF] Giakkoupis | Gossip protocols for renaming and sorting[END_REF] use gossip protocols for renaming and sorting. Here nodes are given id values and numerical input values. Nodes exchange these input values so that in the end the input of rank k is located at the node with id k. Slicing method [START_REF] Pasquet | Autonomous multi-dimensional slicing for large-scale distributed systems[END_REF] [START_REF] Jelasity | Ordered slicing of very large-scale overlay networks[END_REF] was made use of in resource allocation. Specific attributes of network(memory, bandwidth, computation power) are taken into account to partition the network into slices. Network aware overlays can be used in cloud infrastructure [START_REF] Tudoran | Bridging Data in the Clouds: An Environment-Aware System for Geographically Distributed Data Transfers[END_REF] to provide efficient data dissemination.

Most of the works on topology aware overlays are aimed at improving a particular service such as routing, resource allocation or data dissemination. What we are proposing is a generalized approach for overlay creation giving importance to data placement in the system. It has higher scalability and robustness and less maintenance cost compared to other approaches. The simulated annealing and slicing approach is motivated mainly by the works [START_REF] Pasquet | Autonomous multi-dimensional slicing for large-scale distributed systems[END_REF], [START_REF] Giakkoupis | Gossip protocols for renaming and sorting[END_REF], [START_REF] Jelasity | Ordered slicing of very large-scale overlay networks[END_REF]. But these works concentrated mainly on improving a single network service while we concentrate on a generalized solution that can significantly improve all the network services.

Conclusion and Future Work

In this paper, we present-Fluidify-a novel decentralized mechanism for overlay deployment. Fluidify works by exploiting both the logical links of an overlay and the physical topology of its underlying network to progressively align one with the other and thereby maximizing the network locality. The proposed approach can be used in combination with any topology construction algorithm. The resulting protocol is generic, efficient, scalable and can substantially improve network overheads and latency in overlay based-systems. Simulation results show that in a ring/ring network of 25,600 nodes, Fluidify is able to produce an overlay with links that are on average 94% shorter than that produced by a standard decentralized approach based on slicing.

One aspect we would like to explore in future is to deploy Fluidify in a real system and see how it fares. A thorough analytical study of the behaviour of our approach is also intended.

Fig. 1 .

 1 Fig. 1. Illustration of a randomly connected overlay and a network-aware overlay

Fig. 3 .

 3 Fig. 3. Example of local minimum of a system with n=10 and d=2

Fig. 11 .

 11 Fig. 11. Illustrating the convergence of Fluidify (SA) & Slicing (SA) on a ring/ring topology. The converged state is on the right. (N = K0 = 400, knet = k data = 16)

Fig. 12 .

 12 Fig. 12. Proximity. Lower is better. Fluidify (SA) clearly outperforms the baselines in terms of deployment quality.

Fig. 13 .

 13 Fig. 13. Convergence time. All three approaches have a sublinear convergence (≈ 1.237 × |N | 0.589 for Fluidify).

Fig. 14 .

 14 Fig. 14. Proximity over time (N = K0 = 3200, knet = k data = 16). Fluidify (SA)'s optimization is more aggressive than those of the other baselines.

Fig. 15 .

 15 Fig. 15. Average link distances in converged state (N = K0 = 3200, knet = k data = 16). Fluidify (SA)'s links are both shorter and more homogeneous.

Fig. 16 .

 16 Fig.[START_REF] Matos | Lightweight, efficient, robust epidemic dissemination[END_REF]. Variation of the cost function per swap over time. Lower is better. (N = K0 = 3200, knet = k data = 16, note the different scales) Fluidify (SA) shows the highest amplitude of variations, and fully exploits simulated annealing, which is less the case for Randomized (SA), and not at all for slicing.

Fig. 17 .Fig. 18 .

 1718 Fig. 17. Comparison of different variants of Fluidify -Proximity

Table 1 .

 1 Notations and Entities n.net physical index of node n n.data logical index of node n dnet distance function to calculate the distance between two nodes in physical space Gnet the physical graph (N, Enet)

Table 2 .

 2 Parameters of Fluidify

	knet	size of the physical neighborhood explored by Fluidify
	k data	size of the logical neighborhood explored by Fluidify
	K0	initial threshold value for simulated annealing
	rmax	fade-off period for simulated annealing (# rounds)

1:

In round(r) do 2:

Table 3 .

 3 Performance of Fluidify against various baselines

	Nodes	Proximity(%) Fluid(SA) Slicing(SA) Rand(SA) PROP-G(SA) Fluid(SA) Slicing(SA) Rand(SA) PROP-G(SA) Convergence (rounds)
	100	4.06	10.46	7.70	13.88	18.10	17.16	23.80	17.03
	200	2.70	10.12	6.27	12.99	28.50	26.33	43.43	25.13
	400	1.71	9.76	5.35	12.65	42.50	39.20	85.36	38.06
	800	1.26	9.34	4.83	12.14	64.13	58.93	136.76	57.16
	1,600	0.86	8.80	4.41	11.57	96.80	90.56	198.03	85.13
	3,200	0.69	8.47	3.82	11.31	144.40	138.20	274.80	128.14
	6,400	0.51	8.13	3.07	11.27	216.10	203.40	382.10	198.24
	12,800	0.46	7.66	2.28	11.01	324.00	292.10	533.67	263.32
	25,600	0.43	6.99	1.79	10.02	485.00	418.60	762.13	392.81

Table 4 .

 4 Performance on various topologies

		Approach		Physical topology Logical topology Proximity(%) Convergence(#Rounds)
		Fluidify(SA)		torus	torus	2.4(±0.05)	162(±2.34)
		Fluidify(SA)		torus	ring	2.6(±0.03)	171(±3.6)
		Fluidify(SA)		ring	torus	1.8(±0.06)	156(±2.36)
		Slicing(SA)		torus	torus	4.5(±0.05)	130(±2.16)
		Slicing(SA)		torus	ring	5.2(±0.02)	128(±3.26)
		Slicing(SA)		ring	torus	9.5(±0.08)	143(±4.1)
	Randomized(SA)	torus	torus	3.82(±0.08)	423(±2.41)
	Randomized(SA)	torus	ring	4.05(±0.04)	464(±3.28)
	Randomized(SA)	ring	torus	2.7(±0.05)	442(±3.82)
		PROP-G(SA)		torus	torus	4.6(±0.05)	132(±2.34)
		PROP-G(SA)		torus	ring	5.6(±0.03)	130(±3.6)
		PROP-G(SA)		ring	torus	10.1(±0.06)	128(±2.36)
		12
						Fluidify (SA)
						Fluidify (basic)
		10				Data-Net & Net Data-Net & R
						Combination-R
	Proximity ( in %)	4 6 8
		2
		0
		100	200	400	800 1600 3200 6400 12800 25600
						Network Size

Table 5 .

 5 Impact of K0 on Fluidify (SA)

	K0 Proximity (%) Convergence (rounds)
	320	2.4	156
	640	1.6	145
	1600	1.1	146
	3200	0.7	144

argmin x∈S f (x) returns one of the x in S that minimizes f (x).

Acknowledgments

This work was partially funded by the DeSceNt project granted by the Labex CominLabs excellence laboratory of the French Agence Nationale de la Recherche (ANR-10-LABX-07-01).