domain: chim spi

text:
Johannes Theisen

Julien Rey

Christophe Penisson

Jean Duhamet

Véronique Dubois

Nicolas Verplanck

Olivier Diat

S Pellet-Rostaing

Jean-François Dufrêche

Daniel Meyer

la diffusion de documents scientifiques de niveau

recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

A high throughput method to determine selectivity of ion phase transfer in multi-component chemical systems: towards predictive modelling of extraction

Liquid-liquid extraction is a crucial process for recycling chemistry. In order to reuse and to avoid mining of rare earths, recycling has often to be performed by separating and purifying the rare earths from iron. This known technology relies on ion equilibria in coexisting phases located between binodal tie-lines in the Winsor II regime of a microemulsion with excess brine. Since the systems contain ten components, the phase diagram in seven dimensions must be projected in tetrahedron.

The selectivity and differences of free energy of transfer can be determined with good reliability and with reasonable time: days instead of months needed by batch methods.

Availability of data with variable composition allows to challenge the very few predictive models based on first principles and evaluating the free energy of transfer terms.

We show here first results obtained with a micro-fluidic device allowing continuous exploration of lines in a complex phase diagram. We model the ion and extractant distribution and separation, and compare to expected values from available theories.

Finally we discuss how to further speed up the process by electroacoustic fields.

A

  high throughput method to determine selectivity of ion phase transfer in multicomponent chemical systems: towards predictive modelling of extraction Johannes Theisen, Julien Rey, Christophe Penisson, Jean Duhamet, Véronique Dubois, Nicolas Verplanck, Olivier Diat, Stéphane Pellet-Rostaing, Jean-Francois Dufrêche, Daniel Meyer, Helmuth Möhwald, Jean-Christophe Gabriel, Thomas Zemb Institut de Chimie Séparative de Marcoule ICSM UMR5257 CEA/CNRS/UM/ENSCM F30207 Bagnols-sur-Cèze Cedex


domain: chim phys spi

text:
J Theisen

J Rey

C Penisson

A Wilk

V Kokoric

N Verplanck

S Dourdain

B Mizaikoff

J Duhamet

S Pellet-Rostaing

J-F Dufrêche

D Meyer

H Möhwald

T Zemb

J-C P Gabriel

An instrumented microfluidic tool for complex fluid phase diagram determination: Enabling in-line and real-time screening of solvent extraction processes

Keywords: Solvent extraction, rare earth, phase diagram, screening, process development, recycling

Scientific and technological background: Solvent extraction of metal ions and circular economy

If Richard Feynman is often cited as a pioneer in Nanosciences, one should also cite Glenn Seaborg, 1951's Nobel prize in chemistry who stated in 1980 in a visionary conference that: « In the future, chemistry will be called upon to extend our natural resources of copper, lead, zinc, and other non-ferrous metals by making it possible to recover these metals more economically from low-grade ores or to recycle materials now discarded as waste » [1].

And indeed, rare earth elements as trivalent cations are absolutely irreplaceable for strong magnets, "energysaving" light bulbs and high capacity batteries, amongst other applications. They are in fact not rare, just highly diluted in the earth crust. They are also chemically very similar. For these two reasons, their extraction and separation is a lengthy and very polluting process. Consequently, cost and environmental constraints led to the closure of most mining facilities in western countries over the past few decades, leading to today's quasi-monopoly of China which controls approximately 97% of the world's rare earth element market as per 2012 figures [2]. The same year, the first industrial recycling of rare earth elements by solvent extraction was started in Saint-Fons and La Rochelle, France, showing that supply autonomy, economical and ecological considerations are of importance in today's society. Following 2011 figures [3], Japan detains 300 kT of WEEE, corresponding to nearly three times the annual global production of rare earths. In order to recycle these ressources, solvent extraction processes need to be rendered ecologically friendly, and be rapidly adapted to each kind of urban mining material.

Solvent extraction, i.e. control of the reversible transfer of cations between feed and extraction phases, is a core chemical process for metal purification and recycling in hydrometallurgy. These processes are very complex chemical two-phase systems, where slight changes in parameters may imply huge effects on the phase behavior of the involved complex fluids. This may lead to so-called "third-phase accidents", representing huge financial losses for a production plant. The overall behavior of these complex fluids is analyzed in multi-dimensional phase diagrams, requiring several years of thorough analysis by techniques ranging from simple pH measurements to scattering techniques implying consequent instrumental and time efforts. Thus, solvent extraction process tweaking is frequently based on empirical data.

The objective of the "REE-CYCLE" project (Rare Earth Element reCYCling with Low harmful Emissions) [4] is to develop the fundamental understanding involved in the process' complex fluids (both experimental and theoretical) in order to enable a quantum leap in process analysis and thereby rapidly innovating environmentally friendly and economically competitive processes.

Instrumented microfluidic device for complex fluid phase diagram exploration

If extraction microfluidic devices have already been reported [5], the presented work takes this approach beyond the state of the art. Indeed, we will describe the instrumented and computer-controlled microfluidic device enabling the first steps towards simultaneous fast measurement of the free energy of mass transfer per ion pair between complex fluids. In the longer run, high-througput screening in this lab-on-a-chip tool, and complete automation and robotization of the experimental setup, will enable:

1) Rapid evaluation for innovative "green" processes issued of synthetic chemistry, 2) Benchmarking for numerical approaches and predictive theories, e.g. ienaics [6],

3) Process intensification and ecologilization regarding principles of green chemistry and circular economy. Screening of a manifold parameter set, including e.g. multi-component phase composition, pH, temperature, etc., will be enabled by integrating inline and real-time measurements into a fully robotized system. Ultimately, the

Les Rencontres Scientifiques d'IFP Energies nouvelles Microfluidics: from laboratory tools to process development

Rueil-Malmaison, France, 4-5 November 2015 device will be designed to deliver continuous, in-line and real-time exploration of phase diagrams by combining several miniaturized spectroscopy and sensing methods for characterization of kinetic & thermodynamic time scales, partition coefficents of extraction, chemical potential differences and constituent activities, without user intervention.

Here, we show first results of the microfluidic device (cf. Figure 1) and compare these with batch mode assays concerning temperature and pH variation. Examples will be shown on TODGA reverse micelles diluted in dodecane as model system, and extraction of five rare earth elements: La, Nd, Eu, Dy and Yb; in the presence of iron. Partition coefficients and kinetics data for different parameters will be addressed as well as pathways explored to enhance separation and selectivity. First data on solvent activity coefficient measurements will also be presented, giving insight on molecule aggregation, solvent chemical potentials and constituents' vapor pressures.

Conclusions

The microfluidic device stands as a first pillar of the REE-CYCLE project, enabling benchmarking for mesoscale modelling and numerical analysis, testing of newly synthesized extraction agents, and paving the way to assisted pertraction devices. On the longer time range, a semi-industrial prototype device for solvent extraction will be conceived gathering the results of all working groups. Furthermore, the microchemistry and -analysis activity is meant to be developed and extended beyond solvent extraction, involving research as well as industrial partners.

Fig. 1 .

 1 Fig. 1. Microfluidic chip for solvent extraction with in-line measurement sites.

Acknowledgements

The research leading to these results has received funding from the European Research Council under the European Union's Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement n. [320915] "REE-CYCLE": Rare Earth Element reCYCling with Low harmful Emissions [4].

PREFERRED TOPIC:

Oral Poster


text:
N Kokoric

Sandrine Verplanck

J Theisen

J Rey

C Penisson

A Wilk

V Kokoric

N Verplanck

S Dourdain

B Mizaikoff

J Duhamet

S Pellet-Rostaing

D Meyer

H Möhwald

T Zemb

J-C P Gabriel

An instrumented microfluidic tool for complex fluid phase diagram determination: Inline and real-time exploration of solvent extraction

An instrumented microfluidic tool for complex fluid phase diagram determination: Inline and real-time exploration of solvent extraction

Liquid-liquid extraction, i.e. control of the reversible transfer of cations between phases, is a core chemical process for metal purification and recycling. The objective of the "REE-CYCLE" project (Rare Earth Element reCYCling with Low harmful Emissions)[1] is to develop the fundamental understanding of complex fluid processing in order to innovate environmentally friendly, economically competitive processes.

The presented work on micro-solvent-extraction takes this approach beyond the state-ofthe-art [2]: An instrumented and computer-controlled microfluidic device is described, enabling the first steps towards fast measurement of the free energy of ion transfer between complex fluids [3]. Continuous screening of a manifold parameter set, including e.g. multi-component phase composition, pH, temperature, will be enabled by integrating inline, real-time measurements into a robotized lab-on-a-chip. Miniaturized spectroscopic and sensing methods will allow automated characterization of kinetics/thermodynamics, partition coefficients, chemical potential differences and constituent's activity coefficients. First results of the microfluidic device, compared to batch mode assays, are presented concerning temperature and pH variation. Examples are shown on N,N,N′,N′-tetraoctyl-3-oxapentane-1,5-diamide (TODGA) reverse micelles diluted in dodecane for lanthanide extraction in the presence of iron. Partition coefficients and kinetics data for different parameters are addressed and resulting pathways explored to enhance separation and selectivity. First data on solvent activity coefficient measurements will also be presented, giving insight on molecule aggregation [4], constituents' chemical potentials and solvent vapour pressure.

Microfluidic device with on-line measurement sites.


O Laguerre A
email: laguerre@irstea.fr

V Osswald

H M Hoang

I Souchon Bc

C Trelea

C Hartmann

D Flick

Experimental study of airflow and heat transfer above a hot liquid surface simulating a cup of drink

Keywords: convection, evaporation, airflow, hot drink, air Nomenclature

This work was carried out to study the airflow and heat transfer above a cup of hot drink. The experiment was undertaken in a device in which the air temperature and velocity were controlled representing a room condition. The influence of heat exchange by convection and evaporation between the hot drink (at different temperatures) and air on the velocity and temperature fields above the cup is presented. An experimental methodology was developed to evaluate the heat transfer coefficient between the air and hot drink with and without evaporation.

The airflow visualisation by PIV (Particle Imagery Velocimetry) above the cup shows that the flow is complex with unsteady plumes detachment and vortex formation. The combined convection and evaporation lead to upward airflow with temperature fluctuations which become significant for drink temperature above 55°C. This can be explained by the non-

I. Introduction

Odour during food consumption largely influences perception of foods and is thus determinant in consumer preference. Food aroma compounds are released to ambient air and are responsible for the ambient smell of the room where the food is consumed. The ambient smell greatly influences food intake and food choice (Stroebele and De Castro, 2004). To be able to better understand the impact of smell ambient due to food on consumer behaviour, it is first necessary to identify key room factors impacting aroma release to ambient air. Aroma release phenomena involve multi-factorial and complex processes. In the case of a cup of hot drink, it consists in aroma diffusion to liquid surface, aroma transportation to the surrounding air due to diffusion, convection and compounds/water mixture evaporation through a boundary layer (located above liquid surface). Then, aroma compounds follow airflow in the room and arrive to the consumer nose. This study focuses only on the airflow, heat and vapour transfer just above the cup. The understanding of these mechanisms is a first step useful for understanding and controlling the aroma perception by consumer.

Studies on aroma compounds in foods

Aroma, which is one of the key components of food flavour, depends on the type and concentration of volatile compounds present in the air above the food and in the oral cavity during eating, and how they interact with appropriate sensory receptors in nose when they are carried by the breath of the individual [START_REF] Overbosch | Flavor release in the mouth[END_REF]Taylor and Linforth, 1996).

Many studies highlighted the influence of physicochemical properties of aroma compounds (volatility, hydrophobicity), the released amounts and kinetics, for model food [START_REF] Landy | Thermodynamic and kinetic aspects of the transport of small molecules in dispersed systems[END_REF][START_REF] Marin | Volatile release from aqueous solutions under dynamic headspace dilution conditions[END_REF][START_REF] Carey | Modeling the partition of volatile aroma compounds from a cloud emulsion[END_REF][START_REF] Philippe | Behavior of flavor compounds in model food systems: a thermodynamic study[END_REF][START_REF] Rabe | Dynamic flavour release from miglyol/water emulsions: modelling and validation[END_REF][START_REF] Meynier | Emulsification enhances the retention of esters and aldehydes to a greater extent than changes in the droplet size distribution of the emulsion[END_REF][START_REF] Giroux | Characterization of hydrophobic flavour release profile in oil-in-water emulsions[END_REF] and real food [START_REF] Doulia | A knowledge base for the apparent mass diffusion coefficient (DEFF) in foods[END_REF][START_REF] Doyen | Volatile release from an emulsion: headspace and in-mouth studies[END_REF][START_REF] Roberts | Comparison of nosespace, headspace, and sensory intensity ratings for the evaluation of flavour absorption by fat[END_REF][START_REF] Relkin | Effect of fat nature and aroma compound hydrophobicity on flavor release from complex food emulsions[END_REF][START_REF] Deleris | Calculation of apparent diffusion coefficients of aroma compounds in dairy emulsions based on fat content and physicochemical properties in each phase[END_REF]. In the case of real food, products are generally complex. Thus, global characterization and determination of apparent properties are often the most convenient ways to represent transport properties and explain release profiles. For solid foods, aroma release is often limited by the diffusion inside the food. For liquid foods, especially drinks of low viscosity, release is also controlled by the transport phenomena from the liquid/air interface to surrounding air [START_REF] Marin | Volatile release from aqueous solutions under dynamic headspace dilution conditions[END_REF].

Airflow and heat transfer between object and air

The exchange between the hot drink and the ambient air can be due to natural or forced convection. To understand the airflow, heat and water transfer between a cup of hot drink and air, the simplest way is to consider the similar phenomena occurring above a heated horizontal flat plate. Another way is to consider the cup as a cylindrical obstacle of airflow. A literature review of air flows over a flat plate and around a cylinder is, thus, presented below.

Over an isothermal flat plate, a laminar flow is first observed, then after a certain flow length (called critical length) the flow becomes unstable and turbulent. This instability occurs usually when 5 10 . 3 Re ≈ [START_REF] Incropera | Fundamentals of Heat and Mass Transfer[END_REF].

Different flow patterns occur around a cylinder in function of air velocity. For Re<<1, the flow smoothly divides and reunites around the cylinder. For 10 Re ≈ , the flow separates in the downstream and the wake is formed by two symmetric eddies. The eddies remain steady and symmetrical but grow in size up to a Reynolds number of about 90. At 90 Re ≥ , the symmetry between the two eddies is broken. The downstream vortices become unstable, separate from the body and are alternately shed downstream for which means that the frequency of vortex shedding is proportional to the air velocity [START_REF] Hall | Laws and Models: Science, Engineering and Technology[END_REF].

For natural convection, the driving force is the temperature difference between the drink and air, the flow regime is characterised by the Rayleigh number: Ra (warm air flows upward from the drink surface and this air is replaced by cooler air flowing downward from the ambient). For forced convection which may occur in ventilated room, the driving force is air velocity, the flow regime is characterised by the Reynolds number Re. The intensity of heat exchange is characterised by Nusselt number (Nu) which can be related to mass exchange by Lewis analogy. [START_REF] Incropera | Fundamentals of Heat and Mass Transfer[END_REF] The Richardson number (Ri = Gr/Re 2 ) indicates the importance of natural convection relative to the forced convection. Typically, the natural convection is considered when Ri>10

(negligible forced convection), mixed convection when 0.1 < Ri < 10 and forced convection is considered when Ri<0.1 (negligible natural convection) (Incropera and Dewitt, 1966).

Most of the studies found in the literature about fluid flow and heat transfer around complex obstacles are applied to building air conditioning, heat exchangers and electronic equipment cooling. In these applications, various obstacles are employed to alter the flow pattern and which leads to locally increase or decrease heat exchange. The experimental studies are rare in comparison with the numerical ones because of the metrology difficulties and cost. Several authors reported that the fluid flow over blocks is complicated unsteady motion and the average flow often looks very different from the instantaneous flow [START_REF] Rahman | Mixed convection in a vented square cavity with a heat conducting horizontal solid circular cylinder[END_REF]2009;[START_REF] Chyu | Heat transfer on the base surface of three dimensional protruding elements[END_REF]. Although the geometry has a symmetry plane, the instantaneous velocity field is not symmetric while the time average flow must be symmetric.

Looking only the time-averaged flow may give an erroneous impression.

Wietrzak and Poulikakos (1990), Yong and Vafai (1998), [START_REF] Alamyane | Simulation of forced convection in a channel with extended surfaces by the lattice Boltzmann method[END_REF], [START_REF] Moussaoui | MRT-Lattice Boltzmann simulation of forced convection in a plane channel with an inclined square cylinder[END_REF] and the heating method can produce significant effects on the flow characteristic and heat transfer coefficient. Increase in the obstacle height strengthened fluid recirculation before, after and upon the top surface of obstacle, thus increasing the Nusselt number. The changes in obstacle size or shape can lead to Nusselt number increases as high as 40% [START_REF] Jubran | Convective heat transfer and pressure drop characteristics of various array configurations to simulate the cooling of electronic equipment[END_REF] and mass transfer enhancements up to two times (Sparrow et al. 1982(Sparrow et al. , 1984)). Heat transfer and airflow by mixed convection around a hollow cylinder placed in a ventilated cavity was studied by [START_REF] Mamun | A numerical study on the effect of a heated hollow cylinder on mixed convection in a ventilated cavity[END_REF]. A wide range of pertinent parameters such as

Rayleigh number (0-105), Richardson number (0.0-5.0), dimensionless cylinder diameter (0.2-0.5) and the solid-fluid thermal conductivity ratio (0.2-10.0) are considered for Reynolds number = 100. It is observed that the cylinder diameter has significant effect on both the flow and thermal fields but the solid-fluid thermal conductivity ratio has significant effect only on the thermal field. As our best knowledge, few studies were carried out in the case of partially hollow cylinder which corresponds to a cup partially filled with drink.

Our literature study has shown a lack of knowledge on the mechanism of the combined airflow, heat and water transfer around an obstacle applied to the case of a cup of hot drink.

To complete this knowledge, this study was carried out. The objectives of this work were, firstly, to develop a methodology of measurement of air velocity field above a cup filled with hot water by PIV (Particle Imagery Velocimetry) and to study the influence of water temperature on air velocity field above the cup. Secondly, to measure the heat transfer coefficient between the water in the cup and the surrounding air. This coefficient determines the water temperature decreasing rate. It is to be reminded that two heat transfer modes take place between the water in the cup and the air: convection and evaporation. The natural convection is related to the temperature difference between water and air, forced convection has also to be considered if the ambient air circulates due to room ventilation. The final practical objective of this work is to optimize the serving manner and the cup design in such a way that the consumer perceives as much as possible the aroma of hot drink.

II. Material and Methods

Experimental device

To represent room condition, the experiment was carried out in a device specifically developed for this study, in which the ambient temperature and velocity were controlled (Figure 1). This device is composed of 2 parts. In the part 1, a honeycomb was used over a cross section in order to avoid developing flow effects. In the part 2, the work zone was equipped with two glass walls (front and top). Two fans located at the vertical right hand side wall allow low air velocities in the work zone by air extraction. The work zone is equipped with an anemometer (air velocity sensor), thermocouple (temperature sensor) and hygrometer (air humidity sensor).

Air velocity field measured by PIV (Particle Image Velocimetry)

Oil smoke was use as tracer for the air velocity measurement by PIV. The diameter of smoke particles (∼1 µm, manufacturer data) is very small so that they follow the airflow.

Figure 2 shows the 2-Dimensional PIV system (LaVision Company). It is composed of CCD camera (12 bits double matrices of 1376 x 1024 pixels) allowing the acquisition of 2 images successively within a short time interval. The sequence of images taken by the camera is synchronised with the 2 laser impulsions (4 couples of images per second). An instantaneous air velocity field is obtained by inter-correlation of 2 successive images of smoke particles presented in a strongly enlightened plan. In our case, a good velocity estimation could be obtained with 6.5 ms between 2 laser pulses for the image dimension (width x height) of 7.2 cm x 8.7 cm. Vector calculation was undertaken from interrogate windows of dimension 32 x 32 pixels with 50% of overlap between windows. Thus, there are 16 pixels (∼1 mm) between 2 calculated vectors in both horizontal and vertical directions. A mean velocity field was calculated from 700 couples of images. These images were taken on the symmetry plane and just above a black cup (height x diameter = 11 cm x 8 cm) filled with oil or water (10 cm height). This is because the time average velocity vectors belong to this plan. In this way, the effect of 3D pattern is reduced.

Air temperature fluctuations measurement

To avoid as much as possible the flow disturbance in horizontal direction (air flows by fan aspiration ≈ 0.03 m/s) and in vertical one (air flows by natural convection and by evaporation)

because of the presence of thermocouples, calibrated T-type fine thermocouples (200 µm diameter, precision ±0.2°C) were used to follow the air temperature fluctuations with time.

These thermocouples were tightened on a Plexiglas support (5 ± 0.1 mm space between thermocouples shown in Fig. 3a). This support was placed at right angle to the airflow direction to avoid the flow perturbation. Because of the very fine thermocouple diameter, airflow was very slightly disturbed by their presence (the thermocouples occupy only 4% of the flow cross-section). In our experiment, the air temperature was measured every second for y varying from 5 mm to 40 mm from the top of the cup while x was fixed at 68.5mm (Fig. 3b).

Experimental conditions

The device was located in a test room with the controlled ambient temperature of 20°C

(relative humidity about 60%). The fan tension of 2.5V allowed obtaining an air velocity of about 0.03 m/s in the work zone which is the order of magnitude of the one in a room [START_REF] Plana-Fattori | A novel approach for studying the indoor dispersion of aroma through computational fluid dynamics[END_REF]. During experiment, the air velocity near the entrance of the work zone was measured using an anemometer to assure that it was not modified because of the presence of the cup.

In order to study the influence of convection and evaporation on the airflow, the air velocity field was measured (using PIV) above a cup filled with vegetable oil (boiling temperature 165°C) and with water. The temperature of the oil was controlled at 20°C or 65°C. The temperature of water was controlled at several temperatures varying from 35 to 65°C

(temperature of hot drink in general) using a heating resistance. An experiment was also carried out without any cup.

Measurement of convective heat transfer coefficient

The convective heat transfer coefficient between the liquid in the cup and air was measured in the work zone (Figure 4). The liquid (oil or water) in the cup was heated by a resistance (supply power: Q) until 65°C ±1°C and this temperature was maintained during the measurement (steady state). Once the steady state was reached, the air and liquid temperatures (T air , T liq respectively) were recorded every 10s for about 50min using a data logger, and then the mean values were calculated. Two conditions were used: cup covered with an insulating plate made of polystyrene (8 cm diameter, 1 cm thickness, Figure 4a) and un-covered cup (Figure 4b). In the case of un-covered cup, the weight of the cup before and after experiment was recorded in order to obtain the weight of evaporated water (∆m).

It is to be reminded that the convective heat transfer coefficient is an average value over the whole liquid surface. This coefficient determined at the liquid/air interface (h) can be calculated by the following manner:

Cup covered with insulating plate

This experiment was carried out in order to quantify heat losses through the cup's wall (Q loss )

while the heat loss through the insulating plate was neglected. At steady state, the heating power supply to the resistance (Q 1 ) is equal to the heat losses.

Un-covered cup

At steady state, the heating power supply to the resistance (Q 2 ) is equal to the sum of the heat losses (Q loss ) through the cup wall, heat exchange by convection from the liquid surface to the surrounding air (Q conv ) and heat exchange by water evaporation (Q evap ). The convective heat transfer coefficient, h (Wm -2 K -1 ) can be calculated as below:

Q 1 =Q loss Q 2 = Q loss + Q conv + Q evap Q conv = h * A * (T liq -T air ) Q evap = ∆m * ∆h evap /∆t Q 1 , Q 2 , Q conv ,
(5) It is to be reminded that for water at atmospheric pressure and for the temperature range used in our study (35 -65°C), Δh evap is considered to be constant (2.38.10 6 J/kg) because the variation is low in this temperature range (2.35.10 6 -2.42.10 6 J/kg).

III. Results and discussion

) T T ( A t / h m Q Q ) T T ( A Q h air liq evap 1 2 air liq conv - ∆ ∆ × ∆ - - = - =

Analysis of airflow, heat and mass transfer above a cup of hot drink

As cited previously, the airflow and heat transfer above a cup of hot drink can be characterised by several dimensionless numbers. A drink cup can be considered as a truncated cylinder with the hot walls at the top and the side. Our first approach consists in a calculation of the order of magnitude of Re, Ra and Ri allowing the information on the flow regimes (laminar, turbulent) and the heat transfer mode (natural, forced and mixed convection). The following values were used to estimate the dimensionless numbers; for the room: air temperature 20°C, velocity 0.03 1 s . m -; for the cup: hot drink temperature 65°C, cup dimension 8cm diameter x 11cm height. The order of magnitude of the dimensionless number is presented in Table 1.

Taking into account this analysis based on the dimensionless numbers, the airflow, heat and vapour exchange between the drink and the air is expected to be a result of the interaction of several phenomena. Considering the similarity with the flow along flat plate, since Re < 5.10 5 and according to [START_REF] Incropera | Fundamentals of Heat and Mass Transfer[END_REF], the boundary layer at the top should remain laminar. In fact, the liquid/air interface is not at the top of the cup, so that the vortices could appear behind the upper part of the cup wall. Considering the similarity to a partially hollow cylinder in our case, since Re ≥ 90, Karmann vortex detachment is expected. According to Rayleigh and Richardson numbers, natural convection is a determinant effect. So, to summarised, there is an upward warm air flow from the drink surface and this air is replaced by cooler air flowing downward from the ambient. There is instable airflow with vortex shedding behind the cup. Additionally, water evaporates from the surface which contributes to upward gas motion. The natural convection related to the temperature difference between the hot drink and air should be more significant than the forced convection.

With the cup of vegetable oil at 20°C, the airflow modification is only due to the presence of an obstacle. In the case of vegetable oil at 65°C, the difference of airflows compared to the one at 20°C is related to the heat exchange by natural convection. This exchange is influenced by the temperature difference between oil and air in the work zone. In the case of hot water at 65°C, the airflow is related to the combined heat exchange by convection and evaporation.

This evaporation can significantly contribute to the vertical velocity component at the surface of the liquid.

Visualisation of airflow

The images of airflow above the cup filled with water (65°C) at 3 different moments are shown in Figure 5. The heating resistance cable can be seen on the bottom right of these images. The air flows upward because of water evaporation and the flow is oriented to the right side because of air extraction by fans. It can be observed the unsteady flow with vortices formation. From these images, pulse volatile aroma releases can be expected because the plumes and vortices transport them from the liquid surface to the air.

Influence of convection and evaporation on airflow

The mean (time -averaged) velocity field calculated from 700 couple of images is presented in Fig. 6 for 3 different cases: oil at 20°C, oil at 65°C and water at 65°C. The mean field is used to facilitate the comparison of different situations in spite that it gives incomplete information. The instantaneous field for given conditions can be significantly different but they correspond to too large amount of information.

The cup of oil at 20°C (Fig. 6a) shows the influence of obstacle on airflow. In this case, air flows above the cup with acceleration, first upward (at left) then downward (at right). Just above the liquid surface inside the cup, there is an air recirculation. The recirculation above obstacle was also observed by [START_REF] Martinuzzi | The flow around surfaced-mounted, prismatic obstacles placed in a fully developed channel flow[END_REF].

For the cup of oil at 65°C (Fig. 6b), air recirculation just above the liquid surface is observed as in the case of oil at 20°C. In this case, one can expect that air flows upward along the cup by natural convection. This can explain why no downward airflow was observed in this case at right.

For the cup of water at 65°C (Fig. 6c), the air recirculation just above the liquid surface disappears while the upward flow is more noticeable.

Three profiles of horizontal ( x v , main air flow direction) and vertical velocity ( y v ) were extracted from the mean air velocity field along a vertical line above the cup and just downstream (x=68.5 mm). The results are shown in Fig. 7.

All values of horizontal velocity x v are positive (Fig. 7a), this means that air flows in the horizontal direction from the left to the right. x v decreases form y=0 to cm 5 y ≈ , this represents the zone of influence of the obstacle. Airflow is less disturbed by the presence of the cup for y > 5cm. The x v profiles are similar for the 3 cases: oil (20°C), oil (65°C), water (65°C).

The vertical velocity profiles y v are quite different (Fig. 7b). Only the case of oil at 20°C

shows negative velocity for 0 < y < 4 cm. This is a result of downward airflow behind the cup after the flow above it. When the temperature of the liquid is higher than the one of upstream air, air flows upward because of the effect of natural convection. This effect is more significant for evaporable liquid.

Influence of water temperature on airflow

The mean air velocity field for cup filled with water at 35°C, 45°C, 55°C and 65°C is shown in Fig. 8. The effect of water temperature on the airflow pattern (upward flow) becomes really significant when temperature is higher than 55°C. This can be explained by the non linearity between saturated pressure of water and its temperature. Indeed, at 35°C, for example, the saturation vapour pressure is only about 6 kPa, that means that at the liquid/air interface water vapour represents only 6% of the molar fraction. Therefore the evaporation effect is small.

Increasing the temperature from 35°C to 45°C increases the vapour fraction by only 4%. At 55°C, the vapour fraction becomes about 16% and a slight modification of flow pattern can be observed. At 65°C, water vapour represents 25% of molar fraction at the liquid/air interface.

The evaporation effect becomes obvious.

= = ≈ - ≈ ρ ρ ∆ . From
the flow pattern at 65°C, it can be expected that aroma compounds can be entrained efficiently by the evaporated water.

Air temperature and velocity fluctuations

The air temperature measured every second for y=5, 10, 20, 30 and 40mm and x=68.5 mm is presented in Fig. 9 for the cups of oil and water at 65°C. The same variation cycles can be observed for every position. This figure also shows the air velocity magnitude extracted from 20 PIV images measured every 0.25s, fluctuations are also observed. This is because of the strong relation between air temperature and velocity when natural convection is the dominant heat transfer mode.

The mean and standard deviation of temperature (3600 measurements, duration 3600s) and velocity (800 measurements, duration 200s) are reported in Table 2. For both cases (oil and water), the air temperature decreases with the height (y) while the air velocity increases.

The difference of temperature fluctuations for the cups of oil and water can be explained by the difference of involved phenomena. The main heat exchange for the cup of oil is natural convection. For the cup of water, the combined natural convection and water evaporation leads to the intermittent detachment of hot and humid air plumes above it. The upward flow of hot and humid air is balanced by the downward flow of cold and dry ambient air. This explains the more temperature variations with time and the higher temperature decrease with the height for the water cup.

For an isothermal flow around an infinite cylinder of the same diameter as the cup, ( 150 Re D = , see Table 1), Strouhal number is about 0.18 and the frequency of vortex shedding of 0.07 Hz is estimated. This frequency is in the range of the observed fluctuations of several seconds. But the interaction with the detachment of the plumes (due to the combined natural convection and evaporation) and the airflow near the upper surface made certainly the phenomena more complex and un-periodic. It is to be emphasized that a Fourier Transform was carried out; however, no specific frequency could be identified. This means that these fluctuations are rather random.

Heat transfer coefficient between air and water

The experimental values of the heat flux (Q) are shown in Table 3. Without evaporation, the convective heat transfer coefficient at the liquid/air interface is 18.7 W.m -2 K -1 (cup of oil at 65°C). For laminar flow over an isothermal horizontal flat plate, heat transfer coefficients by natural and forced convection of were obtained respectively (calculation based on the equations 1 and 3 and for D = 8 cm). The experimental value is almost equal to the sum of these values. For the cup of water at 65°C, it can be observed that the heat flux due to the latent heat of evaporation (Q evap ) is more than 3 times higher than the convective flux. The presence of evaporation enhance also the convective flux, the heat transfer coefficient is indeed increased from 18.7 to 24.9 W.m -2 K -1 .

The air velocity due to evaporative airflow is about 0.003 m.s -1 . This estimation is based on the weight loss during the experiment of the cup filled with water (

A t m v ρ ∆ ∆ =
).

From these results, the cooling rate of a well-insulated cup of hot drink or of a non-insulated cup can be estimated. In the first case, the heat loss is only by convection and evaporation at the top (liquid/air interface, h≈25 Wm -2 K -1 , cf. Table 3), the heat loss is about 6W and the cooling rate about 0.35°C/min. In the second case, there are also heat losses through the side walls (h≈10 Wm -2 K -1 ) and the cooling rate is about 1°C/min.

Conclusion

An attempt was carried out in this study to understand the mechanism of airflow above the cup with the objective to have a quantitative heat and mass transfer analysis and to gain knowledge which will be transposable to indoor aroma compound dispersion in relation with the ambient smell perceived by consumer. The airflow measurement by PIV over the cup filled with hot water shows that the flow is unsteady with vortex formation. This suggests pulsative release of aroma compounds from a hot drink. The air velocity varies both due to the position and the time. This complexity is related to the instantaneous heat exchanges by convection and evaporation between the water and surrounding air coupled with the unsteady flow expected behind the cup.

An experimental methodology was developed to determine the heat transfer coefficient between a cup of hot drink and ambient air. This parameter allows the prediction of the cooling rate of a drink in room condition.

characteristics of arrays of rectangular modules encountered in electronic equipment. h (W.m -2 .K -1 ) 18.7 24.9

  numerically studied the forced convection of a heated obstacle mounted on a channel wall. The characterisation of flow field surrounding the obstacle and the local Nusselt number (Nu) distribution were presented. It was shown that the obstacle height/width ratio, the thermal conductivity of solid and fluid ratio, the flow rate (Re number)

Figure 1 :Figure 4 :Figure 6 :Figure 7 :Figure 8 :Figure 9 :

 146789 Figure 1: Experimental device

  The natural convection effect is due partly to the

	temperature		difference		ρ ∆	/	ρ	≈	T ∆	/	T	≈	% 7		and		partly	to	molar	weight
	difference	/	x	(	M	air	M	water	)	/	M	air	10	%	(	M	air	29	g	/	, mol	M	water	18	g	/	) mol

  International JournalHeat and Mass Transfer, 25,[961][962][963][964][965][966][967][968][969][970][971][972][973]

	Sparrow E.M., Yanezmoreno A.A., Otis D.R., 1984. Convective heat transfer response to
	height differences in an array of block like electronic components. International Journal Heat
	and Mass Transfer, 27, 469-473.
	Stroebele N, De Castro JM., 2004. Effect of ambience on food intake and food choice.
	Nutrition, 20(9) 821-38.
	Taylor, A.J., Linforth, R.S.T., 1996. Flavour release in the mouth. Trends in Food Science
	and Technology, 7 (12), 444-448.

Yong T.J. and Vafai K., 1998. Convective cooling of a heated obstacle in a channel, International Journal

Heat and Mass Transfer, 41, 3131-3148. Wietrzak A. and Poulikakos D., 1990

. Turbulent forced convective cooling of microelectronic devices, International Journal

Heat and Mass Transfer, 11,[105][106][107][108][109][110][111][112][113]

Table 1 :

 1 Order of magnitude of dimensionless numbers for a cup of hot drink placed in a room.

	Dimensionless	Value									Interpretation
	number
	Re	D	150		Re ≤ 5.10 5 , laminar airflow over the hot drink cup
					90 Re ≥ , Karman vortex street downstream of the
					cylinder (unsteady-oscillating vortices).
	Ra	D	10 x 1 . 2	6	10	4	≤	Ra	≤	10	7	, laminar airflow by natural convection
					over the hot drink cup
	Ri	124		Ri>10, natural convection between the drink and the
					surrounding air is the dominant heat transfer mode.

Table 2 :

 2 Mean and standard deviation of air temperature and velocity at various heights (y)

	for x=68.5cm.
	y (mm)		Cup of oil (65°C)			Cup of water (65°C)
		Temperature (°C)	Velocity	Temperature (°C)	Velocity
				magnitude(m/s)			magnitude(m/s)
		Mean	Std	Mean	Std	Mean	Std	Mean	Std
	5	38.43	0.94	0.0043	0.0103	39.24	0.65	0.0396	0.0430
	10	38.68	0.93	0.0481	0.0515	36.73	1.04	0.0529	0.0517
	20	38.40	0.83	0.0668	0.0576	34.89	1.35	0.0539	0.0535
	30	37.20	0.77	0.0732	0.0566	31.23	1.68	0.0619	0.0539
	40	33.47	1.19	0.0732	0.0520	26.24	1.36	0.0663	0.0546

Table 3 :

 3 Convective heat transfer coefficient between oil-air and water-air.

	Parameter	Convection	Convection+ evaporation
			(cup filled with oil at 65°C)	(cup filled with water at 65°C)
	Q Conv /A (W.m -2 )	795	1099
	Q Evap /A (W. m -2 )	0	3547
	t m ∆ ∆	(kg/s)	0	5.73 x 10 -6

ACKNOWLEDGEMENTS

The authors thank Daniel Picque, David Leveque and Jerome Bussière for their help in the construction of the device allowing temperature and air velocity in controlled conditions. They also thank Gail Wagman for her precious help in revising the English.


F Bonnet

A.-M Kermarrec
email: marie.kermarrec@irisa.fr

M Raynal
email: raynal@irisa.fr

SMALL-WORLD NETWORKS: IS THERE A MISMATCH BETWEEN THEORY AND PRACTICE?

Keywords: Clustering protocol, Complexity analysis, Epidemic protocol, Grid, Kleinberg's shortcut selection, Large scale system, Overlay network, Peer to peer system, Random-based sampling, Random topology, Routing, Shortcut, Simulation experiment, Small-world Analyse de complexité, protocole épidémique, Grille, Sélection des liens longs à la Kleinberg, Système à grande échelle, Réseau couvrant, Système pair à pair, Echantillonage aléatoire, Topologie aléatoire, Routage, Lien long, Expérimentation, Petit monde

In small-world networks, each peer is connected to its closest neighbors in the network topology, as well as to additional long-range contact(s), also called shortcut(s). In 2000, Kleinberg showed that greedy routing in a n peer small-world network, performs in O(n 1 3 ) steps when the distance to shortcuts is chosen uniformly at random, and in O(log 2 n) when the distance to shortcuts is chosen according to a harmonic distribution in a d-dimensional mesh. Yet, we observe through experimental results that peer to peer gossip-based protocols achieving small-world topologies where shortcuts are randomly chosen, perform well in practice.

The motivation of this paper is to explore this mismatch and attempt to reconcile theory and practice in the context of small-world overlay networks. More precisely, based on the observation that, despite the fact that the routing complexity of gossip-based small-world overlay networks is not polylogarithmic (as proved by Kleinberg), this type of networks ultimately provide reasonable results in practice. This leads us to think that the asymptotic big O() complexity alone might not always be sufficient to assess the practicality of a system. The paper consequently proposes a refined routing complexity measure for small-world networks. Simulation results confirm that random selection of shortcuts can achieve "practical" systems. Then, given that Kleinberg proved that the distribution of shortcuts has a strong impact on the routing complexity, arises the question of leveraging this result to improve upon current gossip-based protocols. We show that it is possible to design gossip-based protocols providing a good approximation of Kleinberg-like small-world topologies. Along, are presented simulation results that demonstrate the relevance of the proposed approach.

I R I S A 1 Introduction

Distributed systems have experienced a dramatic scale shift over the past decade. Peer to peer (P2P) overlay networks have been at the center of distributed systems research both in the theoretical and practical communities, often in a fully de-correlated manner though. The research yields rather different expectations whether theory or practice is considered. On one hand, practical implementations target effectiveness for the most frequent cases, potentially at the price of lack of theoretical "worst-case" guarantees. On the other hand, theoretical analysis provides lower bound guarantees without always leading to solutions viable in practice. Routing is one of the main issues encountered in these systems. Focusing on the cost of routing in 2-dimensional torus topologies, this paper is an attempt to (i) reconcile theory and practice in the context of small-world overlay networks, where each peer is connected to its closest neighbors in the topology and additional long-range contact(s) (shortcut(s)) and (ii) leverage both areas to provide provably-efficient systems. Its main contributions are the following.

• The paper first confronts lower bound results of routing in small-world networks with the efficiency achieved in practice using epidemic (also called gossip-based) protocols. We observe through simulations that the expected gap in the routing performance between the two approaches to select shortcuts in a small-world network, is not entirely reflected when it comes to practice. Based on this observation, we argue that the asymptotic complexity analysis alone is not sufficient to assess the practicality of a small-world topology. The paper refines this analysis and characterizes the cost of routing, in terms of the average number of hops in both the grid and uniform topologies. • Indirectly, the paper provides a fresh look at epidemic-based overlay networks and argue that they can achieve small-world topologies. We investigate the improvement of epidemic-based small-world networks to fully leverage Kleinberg's results in practical settings. More specifically, we provide the design and preliminary results of a gossip-based protocol, biasing the peer sampling component used to create shortcuts, so that it provides a good approximation of Kleinberg's harmonic distribution.

Small-world networks Small-world networks have been introduced as an analytical way of understanding and exploiting the six degrees of separation stating that two random individuals are separated by small chains of acquaintances [START_REF] Milgram | The Small-World Problem[END_REF].

When applied to computing networks, this can be achieved by each node in a mesh, knowing its closest neighbors and having additional shortcuts in the graph. While Watts and Strogatz [START_REF] Watts | Collective Dynamics of Small-World Networks[END_REF] considered shortcuts as picked up uniformly at random, Kleinberg refined this result, demonstrating that meshes augmented with shortcuts provide a polylogarithmic routing and navigation under a greedy routing protocol, as long as the distances from the peers to their shortcuts follow a specific distribution (d-harmonic) [START_REF] Kleinberg | Navigation in a Small World[END_REF][START_REF] Kleinberg | The Small-World Phenomenon: an Algorithmic Perspective[END_REF]. One of the main results of Kleinberg's work is the determination of the magnitude order of the routing complexity in such networks (this model is further detailed in Section 2). This result has been of the up-most importance in the community, leading to a full range of works improving upon the routing complexity based on an increase knowledge of the system or a slightly different greedy algorithm (e.g., [START_REF] Barrière | Efficient Routing in Networks with Long Range Contacts[END_REF][START_REF] Fraigniaud | Eclecticism Shrinks even Worlds[END_REF][START_REF] Naor | Know Thy Neighbor's Neighbor: Better Routing for Skip-Graphs and Small Worlds[END_REF]).

Epidemic-based overlay networks

Epidemic-based (or gossip-based) protocols were first introduced to reliably disseminate data in large-scale networks [START_REF] Birman | Bimodal Multicast[END_REF][START_REF] Demers | Epidemic Algorithms for Replicated Database Maintenance[END_REF]. In the practical world, epidemic-based protocols have received an increasing attention as a scalable and reliable solution to build and maintain P2P overlay networks of arbitrary structure [START_REF] Jelasity | T-Man: Gossip-based Overlay Topology Management[END_REF][START_REF] Jelasity | The Peer Sampling Service: Experimental Evaluation of Unstructured Gossip-based Implementations[END_REF]. Their convergence properties, reliability and simplicity make them however attractive for much more than data dissemination [START_REF] Eugster | Epidemic Information Dissemination in Distributed Systems[END_REF][START_REF] Jelasity | Gossip-Based Aggregation in Large Dynamic Networks[END_REF]. More specifically, they have been applied in a wide variety of settings and are now turned into a generic tool to build and maintain large-scale overlay networks. It turns out that depending on the peer locally chosen for the interaction and the information exchanged, gossip-based protocols can be used to build overlay networks ranging from fully randomlike unstructured networks to fully (DHT-like) structured networks (e.g., [START_REF] Fraigniaud | Combining the Use of Clustering and Scale-free Nature of User Exchanges into a Simple and Efficient P2P System[END_REF]). In this paper, we take a fresh look at overlay networks based on epidemic protocols and consider them with respect to small-world networks. Epidemic protocols may be used to construct P2P overlay networks achieving graph properties very close to those of random graphs [START_REF] Eugster | Lightweight Probabilistic Broadcast[END_REF][START_REF] Jelasity | The Peer Sampling Service: Experimental Evaluation of Unstructured Gossip-based Implementations[END_REF][START_REF] Voulgaris | CYCLON: Inexpensive Membership Management for Unstructured P2P Overlays[END_REF]. Typically, a gossip-based peer sampling service provides each peer with a set of long range contacts in a large-scale overlay network [START_REF] Jelasity | The Peer Sampling Service: Experimental Evaluation of Unstructured Gossip-based Implementations[END_REF]. Resulting graphs are extremely robust and remain connected even in the presence of a large number of failures. In the context of this paper, we consider such a peer sampling service to be a way to implement randomly chosen shortcuts of small-world networks. Gossip-based protocols have also been used to create overlays optimized with respect to application-specific metric (e.g., clustering peers according to a proximity metric). It is actually relatively straightforward to use such gossip-based clustering protocols [START_REF] Voulgaris | Sub-2-Sub: Self-Organizing Content-Based Publish and Subscribe for Dynamic and Large Scale Collaborative Networks[END_REF][START_REF] Voulgaris | Epidemic-style Management of Semantic Overlays for Content-Based Searching[END_REF] to choose the local neighbors in a small-world network.

Motivation

The paper focuses on systems provided with (i) an underlying peer sampling gossip-based protocol that provides each peer with a random sample of the system (i.e., each peer is provided with shortcuts randomly chosen), and (ii) a gossip-based clustering protocol that provides each peer with a set of close neighbors (according to the considered

PI n ˚1849 F. Bonnet & A.-M Kermarrec & M. Raynal
underlying topology). Such a combination creates therefore a small-world topology according to the Watts and Strogatz model [START_REF] Watts | Collective Dynamics of Small-World Networks[END_REF].

While, as proved in [START_REF] Kleinberg | The Small-World Phenomenon: an Algorithmic Perspective[END_REF], the routing expectation (expected number of hops) is O(n

3 ) (n being the total number of peers), it appears that performance results in practical settings turn out to be reasonable and follow the exponential convergence time of epidemic-based protocols, thus qualifying such networks for efficient routing. On another side, would the peer sampling service provide a sample following the distribution as defined in the Kleinberg model [START_REF] Kleinberg | The Small-World Phenomenon: an Algorithmic Perspective[END_REF], the routing cost should greatly improve to O(log 2 n). The previous observations constitute the starting point of our work. Simulating a system whose size ranges from 5000 to 500, 000 peers, using six close neighbors and 1 or 10 shortcut(s) in a uniform topology, we first compared the random selection of shortcuts against Kleinberg's selection, and computed the average number of hops between any pair of peers in the system (this is depicted on the figure on the left). It appears that (as expected) the average number of hops between two peers is significantly improved when using the latter choice. The discrepancy increases with the size of the system and the number of shortcuts. These results show however that a random selection of neighbors keeps the average number of hops within reasonable bounds. This gives the motivation of our work, namely, understand the mismatch between practice and theory and leveraging the theory to influence and improve practical systems, thus bridging a gap between theory and practice in small-world networks. Contributions Kleinberg's results were obtained on a d-dimensional grid topology. As such a topology is not always encountered in practice, we consider in this paper an additional topology where peers are randomly and uniformly distributed. Accordingly, the paper refers to the grid topology and the uniform topology, respectively.

Based on the observed mismatch, we argue that relying on the magnitude order of the complexity analysis is not sufficient to draw conclusions on the practicality of an approach. The results obtained in practical systems tend to show that the system performs well regardless of the O(n 1 3 ) expected complexity of the greedy routing strategy. Using random shortcuts, the first contribution provides a refinement of the analysis of the routing cost in both the grid and uniform topologies. Simulations results demonstrate the good accuracy of the number of hops provided by the proposed analysis. As Kleinberg's selection of shortcuts yields an improved routing, we apply our approach to that model too. While we have not been able to provide results for the grid topology, we give an analysis for the uniform topology. We have also conducted simulations, the results of which are extremely encouraging. The table on the right summarizes the paper contributions. Finally, we propose the design and preliminary evaluations of a gossip-based protocol leveraging the theory to achieve an approximation of a Kleinberg-like small-world network.

Routing cost according to the way shortcuts are selected Topology Random Kleinberg's model Grid O(n

1 3 ) + Section 3.2 (Eq 3) O(log 2 n) Uniform O(n 1 3 ) + Section 3.3 (Eq 5) O(log 2 n) + Section 4 (Eq 8)

Roadmap

The paper is organized as follows. System models are defined in Section 2. Section 3 refines the routing analysis of the random selection of shortcuts in both the grid and the random topology. Section 4 applies this analysis to a small-world network where the selection of shortcuts follows the distribution proposed by Kleinberg, in the context of a uniform topology. Section 5 proposes to improve gossip-based sampling protocols by providing them with shortcuts defined from an approximation of Kleinberg's shortcuts selection. Finally, Section 6 concludes the paper.

System models and simulation setup

This section describes the system models considered in the paper. Dealing with failures is out of the scope of this paper (the reader interested in fault-tolerant routing can consult [START_REF] Aspnes | Fault-tolerant Routing in Peer-to-Peer Systems[END_REF]). Network dynamic is also left out for this study and left for future work (robustness in face of high dynamics is one of the main strengths of epidemic-based protocols and we are confident that resulting protocols should sustain high dynamic).

Irisa

Grid topology

Uniform topology As announced in the Introduction, we consider the grid and the uniform topologies. When compared to the grid topology, the uniform topology is more practical in the sense that it is easier to achieve in a practical setting and applicable to a wider variety of applications. Theory has shown that Kleinberg's selection of shortcuts achieves polylogarithmic routing complexity. Yet, we observe that a random selection of shortcuts achieves lower but close enough performance. Consequently, these two shortcut selection processes are considered, resulting in four system models.

Base topologies

Both the grid and the uniform topologies considered here are based on a 2-dimensional torus. They differ in the way the peers are positioned on that torus (see Figure 1). In the following, a peer A is denoted by its name or its coordinates in the corresponding topology.

Grid topology

That topology consists of a network made up of n = × peers corresponding to the points of a × square. The location of each peer in the grid is defined by coordinates (i, j) with i, j ∈ {0, 1, . . . , -1}. As we consider a torus, it should be noted that the peer located at (0, 0) is in between the peers located at (0, 1) and (0, -1). More generally, in this topology, the distance between two peers A and B located at (i 1 , j 1 ) and d (i 2 , j 2 ) is defined as their Manhattan distance, i.e.,

d m = min(|i 2 -i 1 |, -|i 2 -i 1 |) + min(|j 2 -j 1 |, -|j 2 -j 1 |).
Uniform topology In this topology, the positions of the n peers are chosen uniformly at random in a 2-dimensional torus [0 : 1] × [0 : 1]. More precisely, the pair of coordinates (A x , A y ) associated with a peer A are chosen from the set [0 : 1] following a uniform random distribution. In this topology, the distance between two peers located at (i 1 , j 1 ) and (i 2 , j 2 ) is the classical Euclidean distance, i.e.,

d e = min(|i 2 -i 1 |, 1 -|i 2 -i 1 |) 2 + min(|j 2 -j 1 |, 1 -|j 2 -j 1 |) 2 .

Neighbor selection

In a small-world network, each peer, fully characterized by its location in the torus, maintains a view of the system. That view is made up of two sets of neighbors: a set of local neighbors (or local contacts), which are close neighbors in the graph and a set of long-range neighbors, called shortcuts, chosen according to a selection distribution. We consider a greedy routing algorithm to navigate a small-world network. This means that, at each hop, a message is routed to a peer, the position of which is closer to the destination (according to the metric relevant to the considered topology), thus ensuring that the distance to the destination always decreases as the routing process progresses. At each routing peer, the neighbors from these two sets are considered to select the peer to which a message has to be routed.

Local contact selection

To ensure the effectiveness of a greedy routing, a peer needs to know about its closest neighbors according to the distance measured in the corresponding topology. Figure 1 represents local contacts with plain lines. The local contacts differ between the grid and the uniform topology. More explicitly, we have the following.

• Grid topology: To allow for a greedy routing, each peer must know at least its four closest neighbors which all are at distance 1. The local contacts of a peer (i, j) are peers (i, j + 1 mod ), (i, j -1 mod ), (i + 1 mod , j), and (i -1 mod , j).

PI n ˚1849

• Uniform topology: To allow for a a greedy routing, each peer must know at least six of its closest neighbors, one in each wedge of the space as shown in the right part of Figure 1. (If a node does not have a contact belonging to one of these wedges, it can easily been shown that the greedy routing may fail [START_REF] Yao | On Constructing Minimum Spanning Trees in k-dimensional Space and Related Problems[END_REF] 1 .) Partitioning evenly the space around each peer into 60 • wedges, and assigning a local contact belonging to each of these wedges ensures that the greedy routing can be implemented using only local contacts.

Shortcut selection

Shortcuts are added to the view of each peer to speed up the routing process, providing them with candidates to perform "large" routing steps. The complexity achieved by a greedy routing is highly sensitive to the way such shortcuts are chosen. We consider two selection algorithms in this paper, providing each peer with q shortcuts. In Figure 1, we have q = 2, and the two shortcuts are depicted with dashed lines.

• Random selection: As introduced in the Watts and Strogatz model [START_REF] Watts | Collective Dynamics of Small-World Networks[END_REF] and implemented using the peer sampling protocol in the context of epidemic-based algorithms, the selection is done uniformly at random. Each peer A is provided with q shortcuts by choosing q peers uniformly at random from the set of all the peers of the network that are not local contacts of A. • Kleinberg's selection: As proposed in [START_REF] Kleinberg | Navigation in a Small World[END_REF], shortcuts can be added according to a non-uniform distribution. Selecting shortcuts this way has proven to significantly reduce the cost of a greedy routing, achieving polylogarithmic complexity. In Kleinberg's model, a peer A selects a peer B as a shortcut with a probability proportional to the value δ(B) = B ∈S δ(B ) where S denotes the set of all the peers that are not a local contact of A. In the following, this selection mode will be referred as Kleinberg's selection.

Simulation setup

Due to page limitation, the simulation setup is not described in detail. The results are illustrated by comparing analytical results against simulation results obtained using the simulator PeerSim [21]. This simulator allows us to choose the topology, the number of nodes, the number of local contacts p, and the number of shortcuts q. For each generated network, a high number (500, 000 if not specified otherwise) of pairs of peers have been randomly selected to evaluate the cost of the routing. The simulator also implements the gossip-based protocols evaluated in Section 5.

3 Small-worlds with randomly selected shortcuts

Preliminaries

As already noticed, studying the complexity of greedy routing in a grid topology in [START_REF] Kleinberg | Navigation in a Small World[END_REF][START_REF] Kleinberg | The Small-World Phenomenon: an Algorithmic Perspective[END_REF], Kleinberg proved that a random selection of shortcuts in a small-world network gives rise to a routing cost with an expected number of hops that is at least αn 1 3 , where n denotes the number of peers and α is a coefficient -not explicitly determined-that is independent of n.

The good performance achieved in small-world networks by epidemic protocols (and more specifically by the random selection of shortcuts achieved by peer sampling protocols), led us to think that knowing the value of α is actually interesting. The idea here is that knowing more precisely that value enables us to analyze efficient implementations, and allows consequently for a better understanding of why gossip-based protocols are practically efficient.

Although Kleinberg's study is only on the grid topology, we are confident that the same kind of results can be extended to the uniform topology. As an attempt to check this experimentally, we conducted simulations to compare the routing cost using shortcuts defined from a random selection in both the grid and the uniform topology.

The corresponding results are presented in the figure on the right. We observe that, in both cases, the simulation results match Kleinberg's analysis for the grid topology. As we can see, the 1 3 coefficient of the complexity appears in both topologies (as expected by the theoretical analysis). When considering the grid topology, these simulations are in perfect agreement with the corresponding theoretical results. So, we are pretty confident that Kleinberg's analysis in the context of a grid topology can certainly be applied to the random topology as well.

Routing analysis in the grid topology

In order to understand the unexpected good performance of practical implementations of the grid topology, we evaluate the routing cost in this network model more accurately. To that end, rather than dealing only with the magnitude order of the complexity, the routing cost has been analyzed by determining the number of hops needed to route from any peer to any other peer. As previously described, the n = 2 peers are positioned on a × square over a torus. Let r denotes the radius of the local contacts: each peer knows the other peers that are within distance r of it. Let us recall that q denotes the number of shortcuts each peer randomly chooses in the network. For the purpose of the analysis, we first introduce the notion of k-neighborhood of a peer.

Evaluating the size of the k-neighborhood

The k-neighborhood corresponds to the set of peers that are at distance k of a given peer. The size of k-neighborhood is required to compute probabilities related to the location of shortcuts. Due to the regularity of the grid topology, let us observe that, for any peer, there is one peer at distance 0 (itself, obviously), there are 4 peers at distance 1, 8 peers at distance 2, and more generally 4d peers at distance d for d < 2 . For d ≥ 2 the number of peers at distance d depends on the parity of . If is odd, there are 4(d) peers at distance d for d ≥ 2 . If is even, there are 2 -2 peers at distance 2 and 4(d) peers at distance d for 2 < d < and 1 node at distance . These values are summarized in the table at the right. For the sake of simplicity, we assume that is odd. Thus, the previous numbers can be easily written as follows: each peer has 4 min(d, d) peers at distance d,

1 ≤ d < . odd even d = 0 1 1 0 < d < 2 4d 4d d = 2 2 -2 2 < d < 4( -d) 4( -d) d = 0 1
Expected number of hops for r = q = 1 The average number of hops needed to route from a peer to another peer depends solely on the distance between these peers. Intuitively, if the destination is near to the source, the routing process will be faster than if the peers are far from each other. So, let us define f (d), a function that gives the average number of routing hops between any two peers that are at distance d. We have the following when r = q = 1.

• d = 0: The destination is the source. Obviously the number of required hop is f (0) = 0.

• d = 1:
The destination is at distance 1 from the source. The destination belongs to the local contacts of the source peer. Then the number of required hop is consequently

f (1) = 1. • d > 1:
The destination peer does not belong to the local contacts of the source peer (since d > r = 1). As, for the next hop, a greedy algorithm takes either a shortcut or a local contact, two cases need to be studied. If a local contact is chosen, the distance to the destination decreases only by one at each hop. If a shortcut is chosen, the distance can be greatly reduced if the shortcut is close to the destination. Interestingly, it is possible to evaluate the benefit of the shortcut (i.e., the distance between the shortcut and the destination). Let d(i) be the probability that the shortcut is at distance i to the destination. We obtain the following recursive expression for f (d):

∀d > 1 : f (d) = 1 + d-2 i=0 d(i)f (i) + 1 - d-2 i=0 d(i) f (d -1). (1)
The first term (value 1) corresponds to the hop the algorithm has to perform to progress towards the destination. The second term d(i)f (i) corresponds to the use of the shortcut by the algorithm: after using the shortcut, a distance i remains to the destination with a probability d(i). The last term corresponds to the case when a local contact is used; the distance decreases then only by one as explained before.

PI n ˚1849

F. Bonnet & A.-M Kermarrec & M. Raynal

From f (0), f (1), and the recursive definition of f (d), it is possible to compute f (d) for any value of d. It remains however to determine d(i). In fact, d(i) is already known, as we show it. The number of peers that are at distance i of a given peer has been determined previously: it is the i-neighborhood of that peer. The value of d(i) is related to this number: since shortcuts are randomly chosen, the probability that the shortcut is at distance i of the destination is equal to the number of peers at distance i divided by the total number of peers. Consequently, we have d(i) = 4 min(i, -i) n (2 ) for i > 0 and d(0) = 1. Despite the fact that we do not know a closed formula for f (d), that function can be efficiently computed using a mathematical software. Figure 2(a) shows that the average value of f (d) over all possible distances, i.e., Expected number of hops for any r, q The previous analysis can be generalized by taking a larger set of local contacts or more than one shortcut. To that end, appropriate adaptations in the recurrence formula have to be considered.

• r > 1: All the peers at distance r (or less) of a peer are its local contacts. It follows that for a distance i to the destination such that i ≤ r, only one hop is required and consequently f (i) = 1. Moreover, in any other case where the routing uses a local contact, the distance to the destination decreases by at least r in one hop. • q > 1: Each peer chooses q shortcuts. It follows that the probability to have a shortcut close to the destination increases. Let d q (i) denote the probability that the closest shortcut to the destination is at distance i. The function d q () can easily be recursively computed as follows:

d q (i) = d q-1 (i) 1 - i-1 k=0 d 1 (k) + 1 - i k=0 d q-1 (k) d 1 (i). (2)
The first term corresponds to the case when the best shortcut amongst q -1 shortcuts is at distance i and the last shortcut is at least at distance i. The second term corresponds to the case when q -1 shortcuts are at distance greater than i and the last shortcut is at distance i. These two cases describe all the possibilities.

We consequently obtain the following generalized recurrence formula for the grid topology:

∀d > r : f (d) = 1 + d-r-1 i=0 d q (i)f (i) + 1 - d-r-1 i=0 d q (i) f (d -r). (3)
Figure 2(b) represents the routing cost for a system with r = 2 and q = 2. Again, we observe an almost perfect match between simulations and computations.

Routing analysis in the uniform topology

The analysis for the uniform topology is a little bit more involved. The main difference with the grid is related to the distance between peers. Instead of being integers, distances are now real numbers in [0, √

2 ] (let us recall that the nodes are on a [0 : 1] × [0 : 1] torus). Thus, the analysis has to be adapted to take in account this new constraint. The function f () has to accept real numbers instead of integers as input.

Let us recall that p denotes the number of local contacts and q denotes the number of (randomly chosen) shortcuts. In the grid topology, the local contacts are defined from a radius; we need now to estimate the corresponding radius r p . As the torus [0 : 1] × [0 : 1] represents an area of 1 unit, the average surface is p n when considering p peers. If a disk is used to approximate that area, its radius is r p = p nπ . In the first previous analysis, there were probabilities on the position of the best shortcut: d q (i) corresponded to the probability that the best shortcut (among q possible shortcuts) is at distance i of the destination. Here, as f (d), the function d() is a function with real inputs: d q (i) denotes the density of probability that the best shortcut is at distance i of the destination. As proved in appendix A the function d 1 () is as follow:

0 ≤ i ≤ 1 2 : d 1 (i) = 2πi, 1 2 < i ≤ √ 2 2 : d 1 (i) = -2πi + 8i arcsin 1 2i .
The other functions d q () can be computed recursively from d 1 () using the same method as in the grid topology (see Equation 2), namely (the derivative symbol dk is omitted in order not to overload the formulas):

d q (i) = d q-1 (i) 1 - i k=0 d 1 (k) + 1 - i k=0 d q-1 (k) d 1 (i). (4)
Taking into account these modifications, we obtain the following recurrence formula for the uniform topology:

0 < d ≤ r p : f (d) = 1, ∀d > r p : f (d) = 1 + d-rp i=0 d q (i)f (i) + 1 - d-rp i=0 d q (i) f (d -r p ). (5)
Figure 3 compares simulations wrt the formula for networks of size ranging from 4, 000 up to one million. Each peer knows p = 20 local contacts and q = 2 random shortcuts are chosen. We observe a slight discrepancy between our formula and the simulation results. This comes from the fact we always consider that a local contact is located on the circle of radius r p , and consequently the distance to the destination is reduced by r p each time a local contact is used. In a real setting, as a local contact may be within the disk of radius r p , the gain may be smaller (it would actually be possible to take this fact into account at the price of a much more complicated formula).

Small-worlds with shortcuts according to Kleinberg's distribution

Section 3 has investigated the routing cost of greedy routing in small-world networks where shortcuts are randomly chosen. Here, the performance of routing algorithms based on Kleinberg's shortcut selection is analyzed. The analysis is presented only for the uniform topology. This is due to the fact that, when one wants to determine the location of the best shortcuts in the grid topology, the absence of symmetry generates an extremely large number of cases, which makes such a computation "unfeasible". As opposed to the cases studied so far, the distribution of these locations does not depend only on the distance between two peers. (This problem does not appear in the uniform distribution, rendering the analysis feasible.)

Local contacts analysis

The effect of the p local contacts on the routing performance is the same, be the q shortcuts selected randomly or according to Kleinberg's distribution. So, in our analysis, the study of locals contacts remains the same, namely, there is an estimated radius r p = p nπ which corresponds to the area approximately covered by the local contacts.

Distribution of shortcut locations

Since the shortcuts are no longer chosen following the uniform distribution, that distribution becomes more complex. As described in Section 2, a shortcut B is selected by a peer A following a probability proportional to the inverse of the square of the distance between A and B. We already know the distribution of the distance between two peers, that is expressed by the function d 1 (). We consequently obtain the density of probability dist() that the shortcut B is at distance i from A from the following formula (defined only for i > r p since shortcuts can not be taken amongst local contacts):

∀r p < i ≤ √ 2 2 : dist(i) = d1(i) i 2 √ 2 2 k=rp d1 (k) k 2 . (6)
Expected number of hops As in the previous analysis, we need to compute the probability for a peer to use one of its shortcuts in the routing process. The previous recurrence formulas remain correct if the function d() is appropriately adapted. Let us start with only one shortcut (q = 1). We are looking for the density of probability d 1 () that the shortcut is at distance i to the destination. The figure on the right depicts the following situation: S is the source node, D the destination, and P the shortcut; d, i, and j denotes the distances SD, DP , and SP , respectively. From a geometrical analysis we conclude that j = d 2 + i 2 -2di cos(α). Summing all the possible positions of P over the circle gives:

d 1 (d, i) = i 2π α=0 dist d 2 + i 2 -2di cos(α) . S D P d i j α
Let us notice that, as opposed to the previous analysis, where the function d 1 () depends on a single parameter (i), this function now depends also on a second parameter measuring the Euclidean distance d between the source and the destination. More generally, the function d q (), for more shortcuts q > 1, can be computed (similarly to Relation 4) from the value of d 1 (). We then obtain the following value:

d q (d, i) = d q-1 (d, i) * 1 - i k=0 d 1 (d, k) + 1 - i k=0 d q-1 (d, k) d 1 (d, i). (7)
Finally, similarly to Equation 5, the routing cost can be computed with the following recurrence:

∀d > r p : f (d) = 1 + d-rp i=0 d q (d, i)f (i) + 1 - d-rp i=0 d q (d, i) f (d -r p ). (8)
Figure 4 shows the impact of the number of shortcuts on the average number of hops in a 200, 000 peer system and compares the random shortcut selection against the Kleinberg's one. As expected, the routing performance improves with the number of shortcuts regardless of the shortcuts selection. However, we observe that the routing performance decreases faster with Kleinberg's selection: with one shortcut only, Kleinberg's selection improves the number of hops of 16% with one shortcuts and 48% with 10 shortcuts. Although the average number of hops is less than 20 in a 200,000 peer system using randomly selected shortcuts, and therefore qualify for a practical system, there is still room for improvement by leveraging the Kleinberg's selection method in practice. Gossip-based protocols have been recognized as a sensible and efficient paradigm for building peer to peer overlay networks of arbitrary structure. Current gossip-based protocols can achieve already small-world topologies with random shortcuts. This section presents the design of a gossip-based protocol implementing a small-world overlay network where shortcuts are selected according to an approximation of Kleinberg's selection.

A generic gossip-based protocol

Let us consider a system made up of n peers uniquely defined by their coordinates 3 . Each peer maintains a set of neighbors (IP address of other peers in the system) called its view, reflecting its knowledge of the membership of the system 4 . This creates a connection graph, where an edge between two peers A and B means that each of them belongs to the view of the other one. Each peer executes an active thread and a passive thread. The size of a view is c (c being a parameter of the system). Periodically each peer A runs the active thread: (i) it selects from its view a peer B to gossip with, (ii) sends a message to B containing a subset of its view, and (iii) merges its own view with the information received from B, truncating its view back to c. The passive thread on A (i) sends to B a subset of its view upon receiving a gossip message from B and (ii) merges its own view with the information received from B, truncating its view back to c. (Many details of the protocol are omitted due to space limitations, but full details can be found in [START_REF] Jelasity | The Peer Sampling Service: Experimental Evaluation of Unstructured Gossip-based Implementations[END_REF].) It turns out that the resulting connection graph strongly depends on the peer selection, the state exchanged during the gossip and the processing of the state to compute the resulting view.

Local contact selection Using the generic protocol described above, a clustering gossip-based protocol may be used to create the local contacts in a small-world. Let us consider the uniform topology case. As shown in Figure 1, each peer needs to maintain a peer in each of the six wedges attached to each peer (recall that each wedge covers 60 • ). In such a context, a gossip-based algorithm may easily be implemented as follows. Peer selection: the closest peer, according to the Euclidean distance, in one of the wedge of the circle, is chosen to gossip with (at random if several candidates). State exchanged: in this preliminary version, the whole views are exchanged. State processing: the closest peers, according to the Euclidean distance and optimizing along all directions, are kept. (In a dynamic system, such a clustering protocol might be run in parallel with a random peer sampling protocol.)

Random shortcuts It has been shown in [START_REF] Jelasity | The Peer Sampling Service: Experimental Evaluation of Unstructured Gossip-based Implementations[END_REF] that such a gossip-based protocol can be used to provide a random sample to each peer. (Running the Cyclon [START_REF] Voulgaris | CYCLON: Inexpensive Membership Management for Unstructured P2P Overlays[END_REF] protocol for example results in a graph, the properties of which are close to those of random graphs with respect to the average path length, clustering coefficient and diameter.) Therefore, this gossipbased protocol can be run together with the clustering protocol mentioned above in a straightforward manner, thereby implementing the random shortcuts of a small-world random graph. For the purpose of comparison, we use the Cyclon protocol in our simulations of gossip-based random small-world overlays (Figure 5).

Creating Kleinberg 's shortcuts

In order to leverage the potential of the d-harmonic distribution as defined in [START_REF] Kleinberg | Navigation in a Small World[END_REF], we bias the peer sampling service in order to approximate the distribution advocated by Kleinberg. To that end, we propose to change the nature of the state exchanged between peers upon gossip, in order to match as closely as possible this distribution. The algorithm on peer A is implemented as follows. Peer selection: a peer B is chosen uniformly at random from A's view (of size c). State exchanged: c 2 peers are chosen in A's view to reflect the Kleinberg's distribution. More specifically, a peer A keeps a peer C from its view with a probability proportional to δ(C) (as defined in 2.2.2, i.e., δ(C) = 1 d(A,C) 2 where d is the distance separating A and C). The remaining c 2 peers are sent to B during the gossip operation. This enables to minimize the loss of information during the gossip operation. State processing: the view is purged from the c 2 non chosen entries from the view, sent over during the gossip operation. (This is described in more details in Appendix B.)

Figure 5 compares the routing performance of a gossip-based protocol implementing an approximation of Kleinberg distribution against a gossip-based protocol implementing the random selection (peer sampling service). In addition we compared those simulations with the hypothetical ideal simulation mode 5 . Those preliminary results confirm that gossipbased protocols can be used to achieve in a fully decentralized way a close approximation of Kleinberg-like small-world overlay networks. We are currently investigating a broader exploration of the parameter space.

Conclusion

This work has been motivated by the observation that, despite theoretical evidence that a random selection of shortcuts in small-world networks should lead to poor routing performances, such systems are reasonably efficient in practice. To have a better understanding of this gap between theory and practice, we (i) precisely analyzed the average number of routing hops (required in a greedy routing strategy), both in the grid topology and the uniform topology, and (ii) compared the random selection and Kleinberg's selection of shortcuts. Not surprisingly, this analysis confirms the superiority of Kleinberg's selection, but nonetheless demonstrates that the random selection of shortcuts can be considered in practice. Simulation results show that there is an almost perfect match between the results observed in practice and our analysis. Small-world topologies can already be implemented using a two layer gossip-based protocol. We then propose the design and preliminary evaluation of a gossip-based protocol to implement a Kleinberg small-world topology in a fully decentralized way, biasing the peer sampling service to approximate a Kleinberg selection of shortcuts. To conclude, we believe that, contrarily to what could have been a priori suspected, there is no mismatch between theory and practice. This study emphasizes the need to go beyond the big O complexity analysis to evaluate the practicality of small-world overlay networks. Further investigation is now needed to refine the biased gossip-based protocol, explore arbitrary topologies, apply such techniques to other routing strategies and consider dynamic settings.

Notation

• n is the total number of nodes.

• d and d() denote distances.

• p denotes the number of local contacts of a peer.

• r denotes the radius within which are located the local contacts.

• q denotes the number of shortcuts of a peer.

PI n ˚1849

A Determination of d 1 ()

Let us recall that d 1 (i) denote the density of probability that the random shortcut is at distance i from the considered node. Since the selection is done by random, we just have to evaluate the function that gives the proportion of nodes at distance less than i from a source. d 1 is simply the differentiate of this function. For 0 ≤ i ≤ 1 2 the proportion of nodes at distance less than i is easy to calculate. Indeed it corresponds to the average number of peers included in the disk of radius i divided by the total number of peers. As represented on the left side of Figure 6, we have to determine the average number of peers in the grey zone. It is easy to see that this number of peers is πi 2 n . Consequently, for 0 ≤ i ≤ 1 2 , we have d 1 (i) = 2πi.

For 1 2 < i ≤ √ 2
2 , the calculation is a little bit more involved. This is because, as shown in the right part of Figure 6, the disk goes out of the torus. We have consequently to evaluate the average number of peers included only in the light grey zone. We determine that number by subtracting the area of the dark grey zones from the area of the disk. More precisely, the light grey area S(i) is equal to: With a differentiation, we obtain the result, namely, d 1 (i) = -2πi + 8i arcsin 1 2i , for 1 2 < i ≤ √ 2 2 .

S(i) = πi 2 -4 i x= 1 2 √ i 2 -x 2 y=- √ i 2 -x 2 1, = πi 2 -8 i x= 1 2 √ i 2 -x 2

B Creating Kleinberg's shortcuts in a gossip-based protocol

Both Cyclon and the proposed protocol follow the same pattern. They differ only in the way a peer selects the set of peers it sends to another peer during a round (steps denoted (2) and (3) in the following). While these peers are randomly selected in Cyclon, they are selected according to their distance in the proposed protocol. The behavior of each protocol is explained through the following example. Let A and B be two peers whose views (of size c = 6) are v A = {B, C, D, E, F, G} and v B = {U, V, W, X, Y, Z}, respectively.

A round in Cyclon

1 A randomly selects a peer from its view (say B). Irisa

  A T O I R E S P U B L I C A T I O N I N T E R N E N o

Figure 1 :

 1 Figure 1: The grid topology and the uniform topology (n = 2 = 25)

1 d

 1 (A,B) 2 (d() denotes the Manhattan distance or the Euclidean distance, according to the network model). More precisely, a peer B is chosen by a peer A with probability δ(B)

- 1 i=0

 1 d(i)f (i), matches almost exactly the results obtained from simulations.

  r = q = 2

Figure 2 :

 2 Figure 2: Comparison between simulations results and the formula, grid topology

Figure 3 :˚1849 10 F

 310 Figure 3: Comparison between simulations results and the formula (for p = 20 and q = 2), uniform topology

Irisa

Figure 4 :

 4 Figure 4: Impact of the number of shortcuts on the routing performance in a 200,000 peer system

Figure 5 :

 5 Figure 5: Ideal versus gossip-based selection of random and Kleinberg shorcuts in small-world overlay networks

Figure 6 :

 6 Figure 6: Determination of the probabilty density d 1 (i)

i 2 -x 2 ,= πi 2 -

 222 2πi 2 + 4i 2 -1 + 4i 2 arcsin 1 2i , = -πi 2 + 4i 2 -1 + 4i 2 arcsin 1 2i.

2 A randomly selects c 2 - 1

 21 other peers from its view, say C and E, and sends to B the set A to B = {B, C, E}. 3 When B receives the set A to B from A, it randomly selects c 2 peers from it view (e.g., the set B to A = {U, W, Z}), and sends it to A. It executes v B ← (v B \ B to A) ∪ A to B to obtain its new view. So, the view of B is now v B = {A, V, C, X, Y, E}. 4 Finally, when A receives the set B to A from B, it executes v A ← (v A \ A to B) ∪ B to A to obtain its new view, that becomes v A = {U, W, D, Z, F, G}.

In practice, there is no need of this condition if the algorithm takes enough local contacts. It is possible to show that the probability of these special cases is then close to 0.Irisa

The denominator should be n -5 because a shortcut can not be chosen amongst the local contacts of a peer. However, in a large scale network, n is a reasonable approximation of n -5.Irisa

Peers could join and leave the system dynamically although we do not consider dynamics in our experiments.

As, in this paper, we consider the use of gossip-protocols for overlay maintenance only, the state of a peer is fully represented by its view.PI n ˚1849

In this mode, all nodes are considered in the simulator to select the shortcuts. Irisa

Acknowledgment

We would like to thank Rachid Guerraoui and Etienne Rivière for their constructive comments on a draft of this paper.

A round in the proposed peer sampling protocol 1 A randomly selects a peer from its view (say B).

Among the other peers in

2 peers to be kept in its view and sends the other peers to B. The peer selection is done according to Kleinberg's distribution. A computes the value 1 d(A,x) 2 for each peer x ∈ v A . Then A keeps a peer in its view according to a probability proportionnal to the previous value. More precisely, a peer x is chosen with probability

For example A keeps the peers {D, E, F } and then sends to B the set A to B = {B, C, G}.

3 When B received the set A to B from A, it keeps c 2 peers in its view (according to Kleinberg's distribution), e.g., the set {U, V, Z}, and sends the remaining peers to A, i.e., the set

4 Finally, when A receives the set B to A from B, it executes v A ← (v A \ A to B) ∪ B to A to update its view, that becomes v A = {W, X, D, E, F, Y }.

PI n ˚1849