M.-N Avettand-Fènoël
email: noelle.avettand-fenoel@univ-lille.fr

X Sauvage

M Marinova

A Addad

Multiscale investigation of the crystallization mechanisms and solute redistribution during annealing of a Fe 64 B 24 Y 4 Nb 6 Al 0.4 metallic glass

Keywords: A. Fe based metallic glass, primary crystallization, atom probe tomography, D. transmission electron microscopy, D. X-ray diffractometry

The mechanisms and the sequence of crystallization of a Fe 64 B 24 Y 4 Nb 6 Al 0.4 metallic glass were investigated experimentally. To this end, the microstructure of the metallic glass after interrupted isothermal treatments at a temperature between glass transition and primary crystallization was studied by complementary techniques, namely atom probe tomography, transmission electron microscopy and X-ray diffractometry. During the early stages of crystallization of the glass, some nanometric (Fe,Nb)B crystals nucleate first by rejecting Y at their interface, which hinders their growth. The Fe 62 B 14 Y 3 dendritic phase starts growing in a second step. Longer annealings lead to the development of chemical gradients in the amorphous matrix surrounding Fe 62 B 14 Y 3 crystals, which favors the nucleation of additional nanometric (Fe,Nb) 2.4 B crystals.

Introduction

Fe based metallic glasses are widely used in various applications such as sensors, inductor cores or radio-frequency identification systems. They are relatively cheap to produce and they exhibit unique combination of mechanical, electric and magnetic properties (namely high mechanical strength, high electrical resistivity and high saturation magnetization) [1-2]. However, since these properties are connected to their amorphous structure, the thermal stability and especially the crystallization process upon annealing beyond the glass transition temperature is extremely important. It is well known that during primary crystallization, the partitioning of alloying elements plays a key role on both the nucleation and the growth mechanisms [START_REF] Fillon | On the direct nucleation and growth of ferrite and cementite without austenite[END_REF][START_REF] Clavaguera-Mora | Crystallization kinetics and microstructure development in metallic systems[END_REF]. They are mainly controlled by the atomic mobility in the amorphous phase which could give rise to concentration gradients near crystal/amorphous interface boundaries.

We have recently shown that in the Fe based Fe 64 B 24 Y 4 Nb 6 Al 0.4 metallic glass, the crystallization process ends up with a complex multi-crystalline structure with various phases [START_REF] Avettand-Fènoël | Thermal stability, phase transformations and mechanical properties of a Fe64B24Y4Nb6 metallic glass[END_REF]. Detailed investigations carried out by electron diffraction at the peak onset of primary crystallization suggested that the first crystals to nucleate are FeB or Fe 2 B [5]. The exact nature of these primary crystals in such Fe based metallic glasses is however still a controversial issue. Some authors have reported the Fe 23 B 6 phase [1,6-10], even in alloys with very similar compositions [6], while others suggest Fe 62 B 14 Y 3 [START_REF] De Mooij | A metastable compound in the Y-B-Fe system[END_REF], Fe bcc solid solution Thus, the present study aims at identifying for the first time the sequence of crystallization and the mechanisms of the early stages of primary crystallization in the Fe 64 B 24 Y 4 Nb 6 Al 0.4 metallic glass. Amorphous ribbons of Fe 64 B 24 Y 4 Nb 6 Al 0.4 were thus systematically investigated after short time annealings, down to the atomic scale. Experimental data were collected using X-ray diffractometry and a combination of advanced techniques, namely high resolution transmission electron microscopy and atom probe tomography. This latter technique has never been applied to the metallic glass of the present study and relatively scarcely to other kinds of Fe based metallic glasses [3,14,1517] although it may provide critical information about the three dimensional redistribution of solute atoms during crystallization.

Experimental procedure

The Fe 64 B 24 Y 4 Nb 6 Al 0.4 master alloy was produced by arc melting from high purity metallic elements, under a high purity argon atmosphere. In order to remove residual oxygen, a piece of titanium was set next to the crucible containing the master alloy. The production of metallic glass began as soon as titanium was melt. The chemical homogeneity of the alloy was ensured by four re-meltings of the alloy. Quenched alloys with the Fe 64 B 24 Y 4 Nb 6 Al 0.4 stoichiometry were then elaborated as melt spun ribbons. The 2 mm wide, 50 µm thick and 30 mm long ribbons were prepared by single-roller melt spinning on a Cu rotating wheel.

The measured chemical composition of the metallic glass is given in Table 1. The C, N and O contents were measured by LECO, while the B, Nb and Y amounts were evaluated after mineralization by Inductively Coupled Plasma -Atomic Emission Spectrometry (ICP-AES). The Fe content was finally estimated doing the balance. According to differential scanning calorimetry (DSC) analysis (performed in a DSC404C Netzsch TM apparatus), the glass transition temperature (T g ) of this metallic glass is 5852°C and the onset temperature of primary crystallization (T x ) is 6772°C for a heating rate of 10 °C/min (Fig. 1a and[5]). Three metallic glass ribbons were heated up to 667°C (between glass transition and primary crystallization onset temperatures) at 10°C/min under argon in an Al 2 O 3 crucible positioned in the DSC apparatus. Ribbons were kept at 667°C during 1, 15 or 120 min and finally cooled down to room temperature at -50°C/min. Corresponding DSC plots are exhibited in Fig. 1b. Some X-ray diffraction (XRD) analyses of the metallic glasses after the 3 interrupted heat treatments at 667°C were performed with a Cu anticathod ( Cu = 1.5406 Å) and a Bragg-Brentano configuration on a Si low background support using a Rigaku Smartlab TR diffractometer. These analyses carried out under air at room temperature enabled to identify the structure of the first crystals.

TEM samples were prepared by Focused Ionic Beam (FIB) with a FEI Strata DB 235 TR instrument for the quenched state and a FEI Helios 600 Nanolab TR for the heat-treated states. Thin foils were observed by high resolution scanning transmission electron microscopy (HR-S/TEM) using a ThermoFisher Titan Themis 300 TR microscope, equipped with a probe aberration corrector and a monochromator, allowing spatial resolution of 70 pm and energy resolution of 150 meV. Scanning TEM (STEM) observations were carried out with an accelerating voltage of 300 kV with a spot size of about 500 pm, semi-convergence angle of 21 mrad and probe current of approximately 100 pA. High angle annular dark field (HAADF) images were recorded with collection angles ranging from 50 mrad to 200 mrad. The microscope has also a super-X windowless 4 quadrant SDD (silicon drift detector) detection system for the STEM-EDX (Scanning Transmission Electron Microscopy -Energy Dispersive Spectroscopy) mapping and several annular dark field detectors. These TEM data revealed the spatial distribution of the crystals at the sub-micrometric scale as well as the atomic arrangements and crystal lattices.

Atom Probe Tomography (APT) samples were prepared by FIB, with a P-FIB Helios instrument. They were analyzed with a Cameca Leap 4000 HR TR instrument at a temperature of 80K with electric pulses (pulse repetition rate of 200 kHz, pulse fraction of 20%). Threedimensional (3D) reconstructions were performed using IVAS Software and further data processing was done with the Gpm3dSoft Software. APT analyses provided information about the partitioning of alloying elements and the 3D morphology and the spatial distribution of the crystals.

Results

As quenched metallic glass

The quenched metallic glass exhibits the typical features of an amorphous state on parallel electron beam HRTEM images (Fig. 2a) and selected area electron diffraction pattern (Fig. 2b), and XRD data (Fig. 2c). Local measurements carried by APT (Tab. 2) revealed a composition close to the initial composition measured by ICP (Tab. 1). And two-dimensional chemical maps (Fig. 2d-e) clearly show that there are no significant chemical heterogeneities at the nanometer scale. The homogeneous distribution of elements was also confirmed by a statistical analysis (see supplementary material S1).

Metallic glass after annealing

Crystallography of phases nucleated during isothermal holding at 667°C

Irrespective of the duration of the isothermal holding, the DSC analyses did not show any obvious exothermic signal corresponding to an eventual crystallization (Fig. 1b), which is very likely due to the lack of sensitivity of the equipment. Indeed, the XRD patterns with well-defined Bragg peaks corresponding to crystalline phases are clearly exhibited for the three annealing times at 667°C (Fig. 3). Peak indexation is complex due to many possible overlaps, but it seems to suggest the presence of Fe 62 B 14 Y 3 , FeB, Fe 2 B and Fe 3 B phases in the heat treated metallic glass (Fig. 3). Besides, the sample annealed during 1 min at 667°C and thus corresponding to the early stage of crystallization is obviously not fully crystallized and since only very few peaks could be identified out of the background, it is impossible to conclude about the nature of the first crystals formed. Therefore, APT and HRTEM analyses were performed to shed light on the early stage of crystallization steps.

Effect of isothermal annealing duration at 667°C on the 3D atomic distribution

According to APT analyses, the isosurfaces drawn in Figs. 4a and5a-c show that 3 phases could be detected after 1 and 15 min annealings at 667°C, namely: i) a phase that contains less than 75 at.% Fe and less than 12 at.% Nb. This is the major phase after 1 min in Fig. 4 and the left hand side phase in Fig. 5 (15 min). It will be referred as phase 1 in the following.

ii) a phase with more than 75 at.% Fe. This is the biggest "particle" (purple) surrounded by phase 1 in Fig. 4 (1 min) and the right hand side phase in Fig. 5 (15 min). It will be referred as phase 2 in the following. iii) a phase containing more than 12 at.% Nb. This is the smallest "particle" (brown) surrounded by phase 1 in Fig. 4 (1 min) and surrounded by both phases 1 and 2 in Fig. 5 (15 min). It will be referred as phase 3 in the following.

APT quantitative analyses indicate that phase 1 exhibits a composition close to that of the matrix (Tab. 3). Its composition range is similar whatever the holding duration at 667°C but a slight Fe depletion and a B enrichment can be noted in phase 1 after the 15 min holding as compared to 1 min (Tab. 3).

The Fe rich phase 2 contains more Y but lower amounts of B, Nb and Al than phase 1 (Tab. 3). Composition measured after 1 and 15 min at 667°C are quite similar with only a slight B enrichment after 15 min at 667°C (Tab. 3).

According to atomic analyses of the sample after 1 min at 667°C, phase 3 is rich in Fe, Nb and B (Figs. 4 d-g and Tab. 3). After 15 min at 667°C, two kinds of phase 3, more or less Fe rich but with a rather stable Nb content, are detected and their ranges of compositions are far narrower than after 1 min at 667°C (Tab. 3). In addition, it is worth noting that these B, Fe and Nb bearing crystals are rather Al and Y free. Some enrichment in Y can be noticed at their surfaces (see Figs. 4e, 5g-h).

During the growth of the Fe-rich crystalline phase 2, some composition gradients develop in the amorphous matrix as revealed by concentration profiles (Figs. 4f and5h). At the early stage of crystallization (shortest duration at 667°C), a small Nb enrichment and a Fe depletion, both of approximately 3 at.%, of the amorphous matrix are clearly exhibited over a distance of about 3 nm from the interface (Fig. 4f). After 15 min at 667°C, these chemical gradients spread over much longer distances (about 40 nm), and are more pronounced (about 10 at.% difference, see Fig. 5h). ** The spatial distribution, the size and the volume fraction of crystals undoubtedly govern the chemical composition of the amorphous matrix. It is believed that the measured chemical composition of the amorphous matrix is not significantly different after 1 min annealing because of the very low volume fraction of small crystallized particles.

Size, morphology, spatial distribution and "identification" of crystals formed during isothermal holding at 667°C

Since APT analyses do not supply information about the crystalline structure of phases, HRTEM and electron diffraction analyses were performed to identify the 3 phases identified by APT and also to correlate with XRD data.

HRTEM indeed shows the presence of two kinds of crystals embedded in a glassy matrix (Fig. 6) whose volume decreases with an increase of the holding time at 667°C (Figs. 3,4,5,).

First, some rather polygonal small crystals are detected by HRTEM (Fig. 6d-e). They have a size similar to particles of phase 3 detected by APT, ranging from 4 to 8 nm (Fig. 4 and Fig. 6d-e). Given its localization (Fig. 4), phase 3 seems to nucleate heterogeneously.

HRTEM analyses also prove the presence of bigger crystals (Fig. 6a-c,f-g) whose nucleation seems to be also heterogeneous (Fig. 6a). EDX analyses show that these crystals contain more Fe and less Nb than the matrix (Fig. 6h-l). The HAADF and the respective fast Fourier transforms (FFT) suggest that these crystals correspond to the Fe 62 B 14 Y 3 phase after 1 min, 15 min and 2 h holding at 667°C (Fig. 7a-g): experimental crystal lattice distances of the big crystals are consistent with those of Fe 62 B 14 Y 3 phase and the distances ratios and angles are characteristic of a body-centered cubic structure. After 1 min at 667°C, these 50 nm sized crystals exhibit a cauliflowered morphology in 2 dimensions (Fig. 6a,f). Their surfacic density estimated by two dimensional TEM data, is close to 26 crystals per µm² (Fig. 6a) with a spacing of about 160 nm between crystals. With an increase of the isothermal holding duration, the biggest crystals reach a size close to 100 nm after 15 min of holding (Fig. 6b andg) and are separated from each other by about 100 nm. A prolongation of the isothermal holding up to 2 h generates biggest crystals (170 nm mean size) with a mean interspace of about 15 nm (Fig. 6c). After 15 min and 2 h at 667°C, these crystals appear as polygonal agglomerates in 2 dimensions (Fig. 6b-c andg), which proves that they nucleate and grow in the matrix. Thus, there is a good agreement between APT and TEM data. It should be however noted that measured compositions do not exactly fit the theoretical stoichiometry of identified crystallographic structures. This specific point will be discussed in the following section.

Discussion

4.1.

Nature of primary crystals

Concerning the smallest crystals, according to Fig. 4-5 and Tab. 3 and by comparison with Fe, B, Nb bearing phases reported in literature (table A in appendix), phase 3a presents a stoichiometry close to FeB, and phase 3b a Fe 2.4 B stoichiometry which is intermediate between Fe 2 B and Fe 3 B. X-ray diffraction analyses seem to confirm the presence of FeB, Fe 2 B and Fe 3 B (Fig. 3). Actually, in such structures, there would be a substitution of Fe atoms by Nb atoms since Fe and Nb exhibit similar atomic radii. The Goldschmidt radii of Fe, Nb, B and Y atoms are indeed 128 pm, 147 pm, 97 pm and 181 pm respectively [START_REF] Brandes | Smithells Metals Reference Book[END_REF]. These results seem to confirm authors' previous results on the suspected formation of FeB and Fe 2 B phases in such glasses during continuous heating up to 1400°C [5]. In addition, phase 3 (3a and 3b) is Y depleted (Tab. 3) and its nucleation leads to significant rejection of Y at interfaces (Figs. 4b-e, 5d-g). The resulting Y enrichment around phase 3 can be explained by thermodynamical considerations. Nb and Y are indeed repulsive (the heat of mixing for Y-Nb is positive (30 kJ/mol) [6,1820]) while it is negative for Y-B, Fe-B, Nb-B and Fe-Nb systems (heat of mixing of -50 to -35 kJ/mol, -26 to -16 kJ/mol, -39 kJ/mol and -16 kJ/mol, respectively [2,12,19,2021,22]).

With regard to big crystals (Fig. 6a andf), lattice distances extracted from electron diffraction patterns seem to be typical of the Fe 62 B 14 Y 3 crystal structure (Fig. 7). This crystallographic structure was also revealed by XRD analyses (Fig. 3). Fe 62 B 14 Y 3 phase is a metastable body centered cubic structure, space group 229 with a lattice parameter of 12.36 Angströms [START_REF] De Mooij | A metastable compound in the Y-B-Fe system[END_REF][START_REF] Mihalkovic | Ab initio calculations of cohesive energies of Fe-based glass-forming alloys[END_REF]. As shown on EDX maps (Fig. 6), these crystals are Fe rich, thus they correspond to phase 2 detected by APT (see Tab. 3) but surprisingly they do not exhibit the stoichiometry of Fe 62 B 14 Y 3. According to its atomic composition, phase 2 presents a deviation from stoichiometry of Fe 62 B 14 Y 3 . Indeed, in the Fe 62 B 14 Y 3 phase, expected Fe/B, Fe/Y and B/Y ratios are 4.4, 20.6 and 4.7 respectively, while those extracted from APT data are 10±0.3, 14.4±1. [START_REF] Lee | Excellent thermal stability and bulk glass forming ability of Fe-B-Nb-Y soft magnetic metallic glass[END_REF] Besides, as the thermodynamic driving force for crystallization of a glass is high and the atomic mobility low, metastable phases form very often before equilibrium is reached [START_REF] Mihalkovic | Cohesive energies of Fe-based glass-forming alloys[END_REF]. XRD analyses of the present metallic glass up to 1400°C indeed suggested the formation of the stable Fe 14 BY 2 phase [5] which would replace the metastable Fe 62 B 14 Y 3 phase formed at the beginning of crystallization.

Crystallization mechanism

APT data revealed that B, Fe, Nb and Y are randomly distributed in the quenched state (see Fig. 2 and figure in Supplementary data). There could be some short range order but it cannot be evaluated by this technique. Some fluctuations and heterogeneities of composition have been reported in literature in similar Fe-B glasses [START_REF] Kim | Phase separation in metallic glasses[END_REF] and in Fe-Nb-Y-B quaternary glasses with distinct compositions from ours [START_REF] Yu | Atomic packing in Fe-based metallic glasses[END_REF]. Such fluctuations of composition can then affect the nucleation and growth of competing crystalline phases during solidification.

The comparison of crystals sizes after 1 and 15 min at 667°C clearly indicates that the growth kinetic of phase 2 is much faster than that of phase 3 (Figs. 4 and5). However, the nucleation sequence of the different crystals must be discussed and a schematic representation of two different possible scenari is given in Fig. 8: (i) Primary crystallization of phase 3 followed by the formation of phase 2 (Fig. 8a). Three points are in favor of this mechanism. First, the small size of B atom may promote its mobility in the glass; second, the formation of Fe 2 B and FeB is consistent with their low energy of formation (-67. Formation of phase 2 followed by crystallization of phase 3 (Fig. 8b). Such a scenario would be favored by Y clusters in the quenched glass and relative high mobility of Fe atoms. This scenario (ii) seems however less realistic than scenario (i) since Fe atomic diffusion may be sluggish given the Fe big atomic size. When phase 3 starts nucleating (called 3a), it rejects Y since Nb-Y heat mixing is positive [6,7]. However, due to their low atomic mobility in the glassy matrix (related to the large atomic size, 181 pm for Y [1719]), Y atoms cannot diffuse far and stay near crystal/amorphous matrix interfaces (Figs. 4 and5). The resulting local Y enrichment in the amorphous phase combined with the low atomic mobility affect the growth rate of these crystals and they remain nanoscaled. The mobility of phase 3glass interface is smaller than atomic diffusion rate, which explains the spherical morphology of phase 3. But, when phase 3 nucleates and starts growing, it also gives rise to a local Fe enrichment and B+Nb depletion in the neighboring amorphous phase. This obviously favors the formation of crystals of phase 2. Once nucleated, phase 2 exhibits a faster growth kinetic as compared to phase 3. It is very likely because it is Fe rich, like the glassy matrix. Besides, composition differences between phase 2 (Fe 62 B 14 Y 3 ) and the amorphous matrix give rise to chemical composition gradients. They have a low amplitude and extend over a distance of only 3 nm at the beginning of crystallization of phase 2 (see intermediate zone in Fig. 4f) and over a much larger length scale after 15 min at 667°C (up to 50 nm, see Fig. 5h). Assuming that the effective diffusion distance of atoms is equal to the radius of phase 2 particles, then an estimate of the minimum atomic diffusion coefficient at 667°C would be on the order of 10 -17 m²/s after 1 min and 10 -18 m²/s after 15 min. Finally, the local atomic redistribution at the vicinity of phase 2 promotes the local nucleation of novel crystals of phase 3 (labelled "3b") with a composition slightly different from initial crystals of this phase (labelled 3a) (Fig. 5h, Tab. 3). Thus crystals of phase 3 could exhibit different chemical compositions as measured experimentally and displayed in Fig. 9. There is no systematic connection with the particle size, but it simply depends on its location, namely either embedded in the glassy matrix (phase 3a) or close to a crystal of phase 2 (phase 3b). The formation of crystals 3b thus leads to a depletion in B and Nb at the neighborhood of phase 2. These conditions become once again favorable for the growth of phase 2.

The growth of cauliflower shaped phase 2 (Figs. 6f and5a-c) is very likely due to the chemical gradients and high driving force and the dendritic shape of phase 2 very likely results from growth instabilities; the mobility of phase 2 -glass interface is indeed only slightly smaller than atomic diffusion rate. Actually, the crystallization of a glass is known to be very much slower than conventional solidification of a liquid and the crystal growth is so slow that the transformation can be isothermal with negligible temperature gradients [START_REF] Greer | Metallic Glasses[END_REF]. In conclusion, phase 3 appears as a catalyst of phase 2 nucleation and growth, and conversely.

Among the 4 phase transformations, namely polymorphous, primary, eutectic and spinodal, which can occur at the devitrification of the glassy alloys [24,2626,28] and according to our current results, the Fe 64 B 24 Y 4 Nb 6 Al 0.4 metallic glass experienced primary crystallizations.

Conclusions

The early stages of crystallization in a Fe 64 B 24 Y 4 Nb 6 Al 0.4 metallic glass after various holding durations at 667°C were analyzed at the atomic scale by using complementary devices, namely APT, HRTEM and XRD. This study enabled to unveil the mechanism of crystallization in such a metallic glass:

1) some (Fe,Nb)B crystals nucleate first by rejecting Y at their interface with the glassy matrix, which hinders their growth, 2) then crystals with the Fe 62 B 14 Y 3 stoichiometry nucleate, 3) the B and Nb enrichment and Fe depletion close to the Fe 62 B 14 Y 3 crystals promote the nucleation of (Fe,Nb) 2.4 B phase, 4) the chemical gradients resulting from the formation of Fe 62 B 14 Y 3 crystals and the high driving force favor dendritic growth of the latter crystals.

[ 7 , 9 ,

 79 10,12], Fe 2 B, NbB combined with Fe 3 B [13] or at last Fe 14 Y 2 B [14]. Slight changes of chemical composition can indeed modify the crystallization stages and kinetics as well as the crystals nature as exemplified in a Fe 41 Co 7 Cr 15 Mo 14 Y 2 C 15 B 6 metallic glass [15-16].

Figure 1 :

 1 Figure 1: DSC signal of the metallic glass (a) at a heating rate of 10°C/min and (b) at a heating rate of 10°C/min and for holding times of 1 min, 15 min or 120 min at 667°C.

Figure 2 :

 2 Figure 2: HRTEM image of the quenched metallic glass (a), selected area electron diffraction pattern showing continuous hallo rings typical of an amorphous structure (b), X-ray diffraction pattern of the quenched metallic glass (c), 2D Fe (d) and B (e) concentration maps computed with sampling volumes of 1x1x1 nm 3 in a selection of 50×50×20 nm 3 extracted from a reconstructed volume analyzed by APT in the quenched metallic glass.

  Fig 3a

Figure 4 :

 4 Figure 4: APT analyses on a 59×68×68 nm 3 volume of a specimen after a 1 min holding treatment at 667°C: 75% Fe -12% Nb 3D isosurfaces (a) [Fe isosurface in purple and Nb isosurface in orange; blue dots are B atoms in the analyzed volume]. Fe (b), B (c), Nb (d) and Y (e) quantitative maps of a 40×40×20 nm 3 volume. Erosion of phase 2 (f).

Figure 5 :

 5 Figure 5: APT analyses of a specimen after a 15 min holding treatment at 667°C: 75% Fe -12% Nb (a), 13%B -58%Fe (b) and 30%B -80%Fe (c) 3D isosurfaces [B isosurface is in blue, Fe isosurface in purple and Nb isosurface in orange; Blue dots are B atoms in the analyzed volume]. Quantitative Fe (d), B (e), Nb (f), Y (g) maps of a 25×25×120 nm 3 volume of the specimen. Quantitative profile through phases 1, 2 and 3 (Each point of analysis corresponds to the information of a 5×5×2 nm 3 volume of material) (h).

Figure 6 :

 6 Figure 6: Sample after holding at 667°C for 1 min (a, d and f), 15 min (b, e and g) and 2 h (c) (HAADF (d-f) and bright field, TEM (a-c,g)). Example of STEM-EDX mapping (i-l) and the corresponding HAADF image (h) of the sample annealed for 15 min where panels (i-l) are respectively Fe, B, Nb and Y X-ray maps.

Figure 7 :

 7 Figure 7: Lattice images of crystals detected in the amorphous phase: STEM-HAADF (a and c) and respective FFT (b and d) of the biggest crystals in samples after 1 min (a-b) and 2 h (cd) holding at 667°C. They all have been attributed to Fe 62 B 14 Y 3 phase. The inserts in HAADF images are simulated HAADF of Fe 62 B 14 Y 3 structure (ICSD file 68327) with Dr. Probe software [1618] by considering a 40 nm thick sample and multislice model with 10 multislices per scan pixel and images of 124124 pixels. TEM parallel beam bright field micrograph of sample after 15 min at 667°C (e), corresponding dark field image (f) obtained with the diffracted beam circled on the diffraction pattern (g).

Figure 8 :

 8 Figure 8: Schematics of the first steps of crystallization in the Fe 64 B 24 Y 4 Nb 6 Al 0.4 metallic glass during isothermal holding at 667°C.

Figure 9 :

 9 Figure 9: Chemical composition of crystals of phase 3 vs. size (number of atoms detected in the particle) in the sample after a 15 min holding treatment at 667°C (APT analyses).

Table 1 :

 1 Measured chemical composition of the metallic glass (at.%).

	Element	Fe	B	Nb	Y	C	Bi	Cr
	at.%	64.305	24.600	6.037	4.346	0.113	0.002	0.010
		±0.009	±0.050	±0.005	±0.006	±0.042	±0.002	±0.009
	Cu	Mn	Al	Pb	Si	As	N	O
	0.033	0.031	0.429	0.077	0.015	0.004	<0.036	<0.031
	±0.008	±0.009	±0.018	±0.002	±0.008	±0.007

Table 2 :

 2 Chemical composition of the metallic glass measured by APT (at.%).

	Element	Fe	B	Nb	Y	C	Al	N	Mn
	at.%	67.940	21.607	5.970	3.730	0.156	0.501	0.067	0.030
		±0.059	±0.052	±0.030	±0.024	±0.005	±0.009	±0.003	±0.002

Table 3 :

 3 Chemical composition (at.%) of the quenched metallic glass and of the phases vs. holding time at 667°C. The contents of other detected elements (C, N, Mn, P, Cr) are lower than 0.3 at.% and are not given. The total chemical compositions of analyzed volumes in heat treated states are given to show that they are similar to the quench state and thus fully representative.

	State		Fe	B	Nb	Y	Al
	Quenched	Matrix*	67.94  0.06	21.61  0.05	5.97  0.03	3.73  0.02	0.50  0.01
	state
	1 min	Analyzed	66.68  0.05	22.32  0.05	6.00  0.03	3.97  0.02	0.53  0.01
	holding	volume*,**
	time at	Phase 1	66.14  2.12	22.04  1.85	6.98  1.14	3.96  0.87	0.60  0.34
	667°C	Phase 2	82.43  1.52	8.52  1.11	2.51  0.62	5.09  0.88	1.11  0.42
			81.75  3.17	7.93  2.22	1.86  1.11	6.41  2.01	1.12  1.00
		Phase 3 (=3a)	33.98  9.33	44.66  9.79	19.41  7.79	-	-
	15 min	Analyzed	70.92  0.03	18.71  0.03	6.48  0.02	2.89  0.01	0.54  0.01
	holding	volume*
	time at	Phase 1	64.91  2.48	24.90  2.25	5.13  1.14	3.64  0.97	0.67  0.42
	667°C	Phase 2	81.46  1.93	10.66  1.53	3.53  0.91	3.10  0.86	0.68  0.41
		Phase 3a	32.29  3.12	43.32  3.31	21.94  2.76	1.45  0.79	0.33  0.38
		Phase 3b	45.38  3.36	28.84  3.06	23.71  2.87	1.59  0.84	-

* the use of different ribbons of metallic glass, but stemming from the same master alloy, for the quenched state and the annealing states after different durations may be the reason for the slightly different chemical composition of the analyzed volume after 15 minutes of annealing as compared to others.

7,9,10,12,13],

  and 1.45±0.25 for Fe/B, Fe/Y and B/Y, respectively (see table A in appendix). Thus the composition of phase 2 would be more consistent with stoichiometries close to Fe 24 B 2 Y 2 or Fe 23 B 3 Y 2 (see table A in appendix), which are metastable according to ab-initio calculations at 0 K in the B-Fe-Y system [2123]. Fe 24 B 2 Y 2 presents a tetragonal centered structure (space group 139) with lattice parameters: a of 8.449 Angströms and c of 4.869 Angströms, while Fe 23 B 3 Y 2 has a body centered cubic structure, space group 220 with a lattice parameter of 13.853 Angströms [21-2323-25]. But the special frequencies observed in the FFT patterns given in Fig. 7 do not correspond to any lattice distances indexed for those Fe 24 B 2 Y 2 and Fe 23 B 3 Y 2 phases. It is worth noting that the compositions of primary crystals are rather consistent with Fe 62 B 14 Y 3 observed by De Mooij et al. in Fe 124 B 28 Y 9 glasses [11] and with Fe 2 B and Fe 3 B observed by Chang et al. in Fe 72 B 2 Y 6 and Fe 70.56 B 21.56 Nb 2 Y 5.88 glasses [13]. They however differ from others reported in literature, namely (i) Fe 23 B 6 in Fe based metallic glasses [1,6-10] among which metallic glasses with similar compositions as ours [6], (ii) Fe solid solution [(iii) NbB [13] or (iv) Fe 14 Y 2 B [14]. Such differences must be linked to both the quenching conditions and the chemical compositions of the metallic glasses.

  4 kJ/mol and -65.8 kJ/mol respectively at 727°C, i.e. close to the temperature of current isothermal holding [1719]). Conversely, Fe 62 B 14 Y 3 is metastable and exhibits an energy of formation of -34.3 kJ/mol at least at 0K according to ab initio calculations

	[2123].
	(ii)

The authors are very thankful to Wei Jiang from Hefei University of Technology, China for the provision of the samples and Florent Blanchard, UCCS, Lille University, France for having performed the X-ray diffraction experiments. The authors acknowledge financial support from the CNRS-CEA "METSA" French network (FR CNRS 3095 « IRMA ») on the platform GPM (Rouen). Fabien Cuvilly is gratefully acknowledged for the APT sample preparation. The TEM facility in Lille (France) is supported by the Conseil Régional du Nord-Pas de Calais, and the European Regional Development Fund (ERDF).

Appendix

Aknowledgments


Hicham Lesfari

Frédéric Giroire

Giuseppe Di Lena

Chidung Lac

A multidimensional colored packing approach for network slicing with dedicated protection

Network Function Virtualization (NFV) enables the virtualization of core-business network functions on top of a NFV infrastructure. NFV has gained an increasing attention in the telecommunication field these last few years. Virtual network functions (VNFs) can be represented by a set of virtual network function components (VNFCs). These VNFCs are typically designed with a redundancy scheme and need to be deployed against failures of, e.g., compute servers. However, such deployment must respect a particular resiliency mechanism for protection purposes. Therefore, choosing an efficient mapping of VNFCs to the compute servers is a challenging problem in the optimization of the software-defined, virtualization-based next generation of networks. In this paper, we model the problem of reliable VNFCs placement under anti-affinity constraints using several optimization techniques. A novel approach based on an extension of bin packing is proposed. We perform a comprehensive evaluation in terms of performance under realworld ISP networks along with synthetic traces. We show that our methods can calculate rapidly efficient solutions for large instances.

I. INTRODUCTION

A technology which has gained an important momentum in the networking arena is the Network Function Virtualization (NFV) paradigm. The main idea is to dissociate the dependency on dedicated hardware, such as proprietary software appliances, by allowing network functions such as load balancing, firewall, content filtering and deep packet inspection, to be virtualized and executed on generic servers. As such, Virtual Network Functions (VNFs) can be instantiated and scaled on demand without the need to install new equipment, increasing flexibility to accompany user demands [START_REF]Network functions virtualisation (nfv) -network operator perspectives on industry progress[END_REF]. Another fundamental and arising technology is Software-Defined Networking (SDN) that simplifies network monitoring and management. It enables to decouple the control plane from the data plane, and provides global vision and control of the network [START_REF] Kim | Improving network management with software defined networking[END_REF]. The synergy of SDN and NFV gives rise to highly dynamic, programmable and flexible networks where both network infrastructures and resources are shared between the various network services.

Network slices are usually provided in the form of an endto-end logical network provisioned with a set of isolated virtual resources on a shared physical infrastructure. Specifically, a network slice is composed of a set of VNFs, and each VNF is made up of several Virtual Network Function Components This work has been supported by the French government through the UCA JEDI (ANR-15-IDEX-01) and EUR DS4H (ANR-17-EURE-004) Investments in the Future projects.

(VNFCs). Some of these components are anticipated to host services which usually operate at high velocity. Therefore, a short-lived network outage can disrupt significantly these slices. Reliable placement of these VNFCs is a vital part of the virtual resources allocation and remains one of the key challenges of network slicing. A viable solution for the placement of VNFCs with respect of network slicing consists in having a dedicated backup instance for each component such that some instances handle the service traffic, while others are used as a protection mechanism against failures of compute servers. Indeed, for resiliency purposes, some VNFCs have to be run in parallel such that different replicas of a same VNFC are concurrently deployed as a dedicated protection mechanism. Such resiliency constraints belong to the class of anti-affinity rules and are often related to the hosts that are anticipated to provision them. In particular, the network infrastructure across Internet Service Providers consists of compute servers made up of different capacity constraints zones as part of the horizontal scaling. An example of such zones are the NUMA zones [START_REF] Gureya | Bandwidth-aware page placement in numa[END_REF] which are used as a protection mechanism for the host and are practically being deployed as such on physical motherboards.

Our work consists in finding an efficient placement strategy to map the network slices with the infrastructure, while ensuring a dedicated protection. Such protection usually follows some design models according to the pre-provisioning, along with deployment models according to the type of traffic regulating the slice demands. Such slices are, for instance, handled in the OpenStack cloud computing infrastructure in an online fashion without any sorting mechanism. However, giving priority to resolving capacity constraints and ignoring the conflicting aspects of the problem addressed may lead to an overestimation of the necessary number of compute servers.

In this paper, we propose different algorithms for the reliable allocation of resources for network slicing, and compare them with the placement algorithm used by the main computing engine behind the OpenStack infrastructure. Moreover, we propose a coloring based algorithm which extends over multiple dimensions, while satisfying the dedicated protection mechanism for the components. We also take into consideration the distribution of free resources across the compute servers after the provisioning while devising our algorithms. In particular, we consider the effect of the sorting criteria of the network slice over the total performance.

The rest of this paper is organized as follows. We first

Rc||Ac

Design resiliency scheme for c TABLE I: Glossary of notations discuss the relevant research literature in Section II. We then formulate in Section III the problem statement and describe different algorithms. In Section IV, we evaluate our approach over synthetic and real-world network slices and discuss the obtained results. Conclusions are drawn in Section V, together with open questions for future work.

II. RELATED WORK A large number of works has been devoted to the deployment and management of network services. We refer the reader to the surveys in [START_REF] Juliver | Resource allocation in nfv: A comprehensive survey[END_REF] and [START_REF] Mijumbi | Network function virtualization: Stateof-the-art and research challenges[END_REF]. Failure protection. The problem of providing network protection against failures has been studied for different use cases such as bandwidth-optimal recovery placement [START_REF] Tomassilli | Design of robust programmable networks with bandwidth-optimal failure recovery scheme[END_REF] and reliable service function chaining [START_REF] Tomassilli | Resource requirements for reliable service function chaining[END_REF]. In [START_REF] Kong | Guaranteed-availability network function virtualization with network protection and vnf replication[END_REF], the problem of distributing VNF replicas between both primary and backup paths while maximizing the availability has been considered, based on a heuristic algorithm. The setting where slicing placement requires multiple network functions, which require a different amount of each resource to process a unit of flow has been studied in [START_REF] Sallam | Placement and allocation of virtual network functions: Multi-dimensional case[END_REF]. Different from previous studies on failure recovery, we present a resilience mechanism for VNFCs placement to protect against compute server failures where the network slicing is deployed over an infrastructure of NUMA zones. Vector Bin packing. The classical bin packing (BP) problem has been extensively studied. While for its one dimensional setting, [START_REF] Fernandez De | Bin packing can be solved within 1+ ε in linear time[END_REF] showed an asymptotic polynomial time approximation scheme (APTAS) which was later improved by [START_REF] Karmarkar | An efficient approximation scheme for the one-dimensional bin-packing problem[END_REF], it turned out that there is no APTAS for square packing [START_REF] Woeginger | There is no asymptotic ptas for two-dimensional vector packing[END_REF]. The approximability of the multidimensional setting of BP has been studied in [START_REF] Chekuri | On multidimensional packing problems[END_REF] and [START_REF] Bansal | Improved approximation algorithms for multidimensional bin packing problems[END_REF], where improved approximation algorithms were designed. Some variants of BP [START_REF] Jansen | An approximation scheme for bin packing with conflicts[END_REF], [START_REF] Epstein | On bin packing with conflicts[END_REF], [START_REF] Epstein | Two-dimensional packing with conflicts[END_REF] have been studied ever since, where some pair of items are in conflict, i.e. not allowed to be packed together in the same bin. However, a setting under conflicts over an arbitrary number of dimensions has not been considered in previous works.

To the best of our knowledge, a general multidimensional setting under conflict constraints for reliable network slicing has not been explored. We combine both the multidimensional aspect with the capacity and resiliency constraints, and provide fast and efficient combinatorial algorithms.

III. PROBLEM STATEMENT A. Problem definition

In order to deploy a network service, Internet Service Providers (ISPs), Content Delivery Providers (CDPs) and other Telco operators usually buy or rent a technical solution from a vendor. Such solution is composed of a set of VNFs, each VNF being itself a set of VNFCs. Each VNFC requires for its operations a certain amount of virtual CPU and memory. To run the solution, the customer uses an infrastructure composed of compute servers, networking resources, and storage assets. Compute servers, used for illustration in this study, are made up of several zones, each of these zones being characterized by a maximum amount of CPU and memory.

The deployment of VNFs/VNFCs must respect a set of rules. First, since the capacity of a compute server is limited, only a subset of VNFCs can be hosted in any compute. Moreover, each single VNFC cannot be split across different zones. Last, for resiliency purposes, each VNFC is usually subject to an anti-affinity rule which is defined by a design redundancy model. Let us suppose that a certain VNFC has some design scheme denoted by R||A. Such a scheme implies that the vendor has decided that R replicas (replica and instance are used interchangeably in this paper) of the VNFC are needed to handle the traffic, but A additional ones have to be deployed for protection purposes. Alternatively, every R instances must be protected by A backups such that if a single compute server fails, at least R instances of the VNFC always run. Such redundancy protection is therefore designed against single failures of the compute servers.

The main aim is to find the minimal number of compute servers needed to host the VNFs of the network service, by piling up the VNFC instances in these computes, while respecting the anti-affinity rule for the redundant instances. We refer to this problem by VNFC-PROTEC.

We use the notations in Table I in the rest of this paper, to make it self-contained. Network vector. We represent a network service by a set C of VNFCs, such that an instance C k c from C denotes the kth replica of the VNFC c. Moreover, for each component c,

let α(c) = {C k c , 1 ≤ k ≤ T c
} denote the set of its available replicas. We associate with c a network vector f k c which acts as a summary indicator for the network characteristics required by the VNFC. Since all replicas of a same VNFC are similar, it holds that, for each component c fixed:

∀k, k ∈ α(c) : f k c = f k c
. Therefore, we can drop the subscript k for ease of notation and assimilate

f c = f k c for each copy k ∈ α(c) of c. For the VNFC-PROTEC problem, we consider a three- dimensional network vector f c = (f cpu c , f ram c , f res c ) ∈ R 3 such that, for each VNFC c, f cpu c ∈ (0, 1] is its normalized amount of needed CPU, f ram c ∈ (0, 1]
is its normalized amount of needed memory and f res c ∈ N is its deployment resiliency factor as described hereafter. Deployment resiliency factor. Let us consider a VNFC c with a design scheme N c ||R c = 3||1 decided by the vendor. Thus, every three instances of c needed to manage the traffic, must be protected by one additional instance. Moreover, let us assume that there are a total of T c = 7 replicas of the VNFC. It implies that the compute servers in the infrastructure must host seven instances of c such that: 3 instances are protected by one backup and 2 instances are protected by one backup. Therefore, the deployment scheme induced by (N c ||R c , T c ) would be: 5||2. The deployment resiliency factor associated with the aforementioned VNFC c is defined as f res c = 2 from the deployment scheme.

More generally, the deployment resiliency factor for a component c under the design scheme N c ||R c is defined as:

f res c = T c N c + R c
The factor corresponds therefore to the maximum number of replicas for the VNFC c allocable to a single compute server. It captures the anti-affinity rule induced by the traffic for a given VNFC. Note that the deployment scheme for a VNFC c can be thus expressed as T c -f res c ||f res c .

B. Exact ILP

We describe an exact Integer Linear Program which computes the optimal solution by minimizing the number of hosts needed. The main variables are the boolean variables x s and z kcsz defined as follows:

x s = 1 if there is a VNFC instance assigned to the compute server s ∈ S and 0 otherwise. -z kcsz = 1 if the copy k of the VNFC c ∈ C is assigned to the host s ∈ S in the zone z ∈ Z and 0 otherwise. The objective is to minimize the number of compute servers, i.e., min

s∈S x s (1)
The maximum capacity for each zone is then:

c∈C,k∈α(c) z kcsz • f cpu c ≤ z C ∀s ∈ S, z ∈ Z (2) c∈C,k∈α(c) z kcsz • f ram c ≤ z R ∀s ∈ S, z ∈ Z (3)
All instances of each VNFC must be assigned:

s∈S,z∈Z,k∈α(c)

z kcsz = T c ∀c ∈ C (4)
The anti-affinity rule for each VNFC is expressed as:

z∈Z,k∈α(c) z kcsz ≤ f res c ∀c ∈ C, s ∈ S (5)
A compute is used if at least one instance is assigned to:

z kcsz ≤ x s ∀s ∈ S, z ∈ Z, c ∈ C, k ∈ α(c) (6)
The binary constraints are as follows:

z kcsz ∈ {1, 0} ∀s ∈ S, z ∈ Z, c ∈ C, k ∈ α(c) (7)
x s ∈ {1, 0} ∀s ∈ S

For small sized instances of the VNFC-PROTEC problem, the ILP provides good solutions (see Section IV). However, finding an optimal solution requires a prohibitive computation time as the problem is NP-complete. For large size instances, it is even impossible to find feasible solutions using the ILP. We thus propose, in the following, efficient heuristics and a coloring algorithm to solve the VNFC-PROTEC problem.

C. Lower bounds

In order to boost the subsequent algorithms, we provide a lower bound denoted by L B on the minimum number of needed compute servers. Let z C (respectively z R ) denote the maximum amount of virtual CPU cores (respectively memory units) available in a single zone. Since a feasible deployment must satisfy a set of constraints, it holds that:

L B = max c T c f cpu c |Z| • z C , c T c f ram c |Z| • z R , max c T c f res c (9)
While the first two quantities are derived from the resource allocation of the VNFCs under the capacity constraints of the computes nodes, the third quantity stems from the anti-affinity deployment constraint.

D. Heuristics

Slice sorting. Since the network vector is multidimensional, we study the effect of sorting the set of VNFCs that occur within a slice over the placement allocation. A widely used approach in one-dimensional placement algorithms consists in sorting the instances in decreasing order by their size. We thus consider a descending lexicographical ordering rule denoted by R based on the network vector dimensions: f cpu , f ram and f res . Each of the six possible rules alternates between giving priority to capacity constraints satisfaction and anti-affinity resolving. Let F R denote the first dimension over which the instances are sorted within the slice according to R.

Compute scheduling. In addition to minimizing the number of compute servers, it is also of relevant importance to allocate the VNFCs evenly across the infrastructure with respect to the resources. We propose different algorithms which determine differently how to dispatch the VNFCs across the computes.

• The ORDERED-VECTOR greedy algorithm extends the First Fit Decreasing approach which was shown to be an efficient fast heuristic for one-dimensional resource placement. It operates by first sorting the slice according to a rule R. Then, at each step, a VNFC is always placed over the first compute server which satisfies both the capacity and resiliency constraints. Furthermore, we increment this algorithm with a swap procedure which first finds the set P min of compute nodes with the minimum number of assigned set C reallocate of VNFCs. Then, it attempts to reallocate randomly each instance c in C reallocate across the computes in S\P min by swapping c with a random feasible instance among the already placed instances in C \ C reallocate . We obtain a new algorithm denoted by ORDERED-VECTOR-SWAP. • The LEAST-LOAD algorithm considers a sorted slice according to R. Then, it sorts the compute servers in the decreasing order based on the free amount of available load along F R where the load of a compute is defined as the total sum of the resource F R across the instances that it currently hosts. For every VNFC, the instance is placed at the least loaded compute which doesn't break the resiliency constraint after sorting the computes. While the algorithm starts with the predetermined lowerbound in Eq. ( 9), the SLIDING-LEAST-LOAD algorithm (see Algorithm 1) increases the L B every time L B computes are not enough to host the network slice. • We consider the default placement algorithm used by the Nova scheduler, which is the main computing engine behind the OpenStack cloud computing infrastructure, denoted by OS-NOVA. The algorithm is similar to LEAST-LOAD with the following differences. First, the network slice is not sorted. Second, the load of the computes is defined as the average sum of the CPU and RAM resources. We increment OS-NOVA with two variants. While ORDERED-OS-NOVA sorts according to the rule R, HEURISTIC-RANDOM does the same but also chooses randomly a compute from a subset of the least loaded computes by uniformly shuffling a fraction γ of the first sorted computes.

E. Colored Bin Packing

We model the VNFC-PROTECT problem by a generalized version of bin packing that we denote by COLOURED-BIN-PACKING. We consider an undirected graph G = (V, E) where V = {1, ..., n} represents the set of items of respective sizes s 1 , ..., s n such that s i ∈ [0, 1] d (for d > 0) and E the set of links between the items. The goal is to find a minimumsize partition of the items into independent sets (or bins)

B 1 , ..., B m of G such that i∈B k s i ∞ ≤ 1, where . ∞ denotes the standard l ∞ norm.
When E = ∅, COLOURED-BIN-PACKING reduces to the standard bin packing problem (d = 1). Therefore, the problem is NP-complete, APX-hard and no algorithm can achieve a better approximation ratio than 3 2 (unless P=NP). It comes from the approximation hardness of standard bin packing through a reduction from the partition problem [START_REF] Michael | Computers and intractability[END_REF]. Moreover, if i∈V s i ≤ 1, we obtain the special case of the graph coloring problem, i.e., determining the chromatic number χ(G), which cannot be approximated within factor N 1-ε for an input of N items, for all ε > 0 (unless P=NP) [START_REF] Zuckerman | Linear degree extractors and the inapproximability of max clique and chromatic number[END_REF]. Equivalence. For each VNFC c with a given deployment scheme T c -f res c ||f res c , we dispatch its replicas in α(c) into f res c partitions where each partition is represented by a clique graph denoted by K c i , for i = 1, ..., f res c . The resiliency graph G is therefore a disjoint union of graphs K 1 , ..., K Γ where

K 1 = f res c i=1 K c i .
By making the set of edges E depend on the deployment resiliency factor, we thus directly represent the anti-affinity rules of the VNFCs. In order to solve the COLOURED-BIN-PACKING, we leverage upon efficient algorithms for the bin packing tailored for a certain class of graphs. Since the resiliency graph is clearly a perfect graph, it belongs to the class of graphs for which one can find in polynomial time a coloring that uses a minimum number of colors. Therefore, we propose COLOURED-APPROX (see Algorithm 2) which operates over multi-dimensional network vectors by using different weighting systems. The main idea is to carefully remove small subgraphs of items which induce problematic instances due to the anti-affinity rule. for each compute node s in S do 9:

for each zone z(s) do 10:

β cpu z ← Free available CPU in z 11: β ram z ← Free available RAM in z 12: A(s) ← (max z(s) β cpu z , max z(s) β ram z ) 13:
S ← sort S decreasingly per (A, F R )

14:

for each compute node s in S do Run ORDERED-VECTOR over the items in κ 13:

Add the obtained computes to S 14: return S Weighting. The technique of weights has been used for one-dimensional bin packing problems and produces efficient algorithms [START_REF] Jansen | Approximation algorithms for time constrained scheduling[END_REF], [START_REF] Eg Co Man Jr | Approximation algorithms for bin packing: A survey[END_REF]. Each item i is assigned a weight w i based on its size s i and its packing in some fixed solution, such that the number of bins of the algorithm is close to the total sum of weights. We denote by D the set of network characteristics such as CPU, memory, disk usage.

The COLOURED-APPROX algorithm operates in several steps. First, an item i is said to be large (resp. small) if the quantity max{f d i , d ∈ D} in [0, 1] is larger (resp. smaller or equal) than 1/2. The set of items V of the resiliency graph G is then partitioned into (H 1 , H 2 ) such that H 1 (resp. H 2 ) collects the large (resp. small) items. Next, an edge (i, j) between two items i, j with i in H 1 and j in H 2 is added if the following conditions are satisfied:

∀ ∈ D, f d i + f d j ≤ 1 and (i, j) / ∈ E (10)
Eq. ( 10) captures both the capacity and resiliency constraints characterizing the situation where two items can be jointly placed in a bin. The edge (i, j) is associated with a weight w ij defined as:

w i,j = F(f i , f j ) + b j (11)
where f i , f j are the network vectors, F is an aggregator function (e.g., maximum, mean, weighted sum) such that it outputs a value in [0, 1], and b j is a bias term associated with the small item. Several values of b j were proposed in such a way to classify the items into intervals, then a weight is associated by either giving the same weight to all items in the same interval, or scaling them by a multiplicative factor [START_REF] Steven S Seiden | On the online bin packing problem[END_REF], [START_REF] Brenda | A tight asymptotic bound for next-fit-decreasing bin-packing[END_REF]. We adopt the special weight function in [START_REF] Epstein | On bin packing with conflicts[END_REF] which has the benefit of not rounding up the size (along each dimension) of an item to the next unit fraction. For each d in D, let p d be the integer such that f d j ∈ (

1 p d (p d +p d ) , 1 p d ].
The term b j is set to 1 ρ(ρ+1) where ρ = max(p d , d ∈ D). Note that as a special case, when |D| = 1, the network vector is one-dimensional and COLOURED-APPROX is a 5 2 -approximation algorithm [START_REF] Epstein | On bin packing with conflicts[END_REF].

IV. PERFORMANCE EVALUATION

In this section, we first present our evaluation setup. Then, we provide a broader assessment of the various solutions proposed under different scenarios.

A. Evaluation setup

Slide demands. We consider the design and deployment of several slices in the network. Each slice has to implement a set of VNFs where each VNF is composed of a given number VNFCs. Each VNFC requires a specific amount of CPU, memory, and has anti-affinity constraints. Our aim is to evaluate the performance of the different placement algorithms (see Sec. III) over the resource allocation of a given slice across an infrastructure. The latter is made up of a given number of compute servers where each compute is composed of a set of zones with a given CPU and memory capacities.

Metrics. We compare the different algorithms in terms of the expected number of bins obtained, the running time, and the distribution of free resources (referred to by wastage) across the different bins. Since the number of bins varies across the algorithms under the same slice, to analyze the wastage, we consider the variation coefficient C v which is the ratio of the standard deviation to the mean and captures the level of dispersion around the mean of free resources of the compute servers after the placement.

B. Evaluation scenario

Generation. We run our experiments over a synthetic scenario based on a random generator of network slices. For a fixed number of zones (between 1 and 5), the generator provides a network slice made up from a random number of VNFCs. A VNFC has a given cost determined by its network vector where f cpu , f ram are selected uniformly at random between 0 and 1, the number of replicas T c (which comprises the backup instances) randomly between 1 and 10, and the resiliency factor f res randomly between 1 and T c . Therefore, a given slice is made up of σ instances where σ = Γ c=1 T c . We also validate our results over a real scenario based on traces from a real ISP network. Settings. We set γ = 0.25 and the time limit for the ILP solver to 10 hours. Moreover, we chose among two families of aggregators:

F d mean (f i , f j ) = f d i +f d j 2 for each dimension d and F mean (f i , f j ) = d f d i +f d j 4
, in addition to

F d max (f i , f j ) = max(f d i + f d j ) for each dimension d and F max (f i , f j ) = max({f d i , f d j , d ∈ D}).
Results. As shown in Fig. 1 and Fig. 2, only a limited subset of our instances have been submitted to the ILP solver, which turned out to need a generous time-limit of 9 hours to be able to solve optimally a mere subset of 34 instances (the starting point of the red straight lines indicate the moments where we stopped taking into account the ILP algorithm). Therefore, the ILP does not scale and becomes quickly irrelevant as the size of the slice increases. Fig. 2 shows that, unlike the ILP, all the various algorithms remain very fast as the difficulty of the network slices increases.

We note that the quality of OS-NOVA regularly deteriorates in terms of bins. Moreover, ORDERED-OS-NOVA being relatively better than OS-NOVA shows the importance of sorting the slice before the placement. On top of the VNFCs sorting, shuffling the top least loaded compute nodes provides an apparent improvement as demonstrated by HEURISTIC-RANDOM. This is explained by the fact that in the default version of OS-NOVA, the compute servers are sorted evenly by f cpu and f ram . However, the pre-sorting of the slice implies that sorting the computes by F (R) of the ordering rule is more beneficial as SLIDING-LEAST-LOAD unveils. The latter records quite honorable results and, as expected, spreads the components evenly across the compute nodes (Fig. 3 considers the CPU as in the given slice F (R) =CPU). While the algorithm remains fast, it is outperformed by the others (aside the ILP). This shows that even an overestimation L B of the necessary number of compute notes does not affect the minimization problem of the least load paradigm.

As expected, the swap procedure improves over ORDERED-VECTOR while remaining fast. On the other hand, while COLOURED-APPROX and ORDERED-VECTOR-SWAP obtain the best performances in bins, the coloring approach spreads the wastage evenly in contrast with the ORDERED-VECTOR-SWAP which obtains the worst performance with a relatively high C v . We recall that in the one-dimensional case, the latter provides a guaranteed theoretical approximation performance. The benefit of the weighting techniques lies in not giving the priority to resolving capacity constraints, but also taking into account in a joint manner the anti-affinity rule. We observed that the scenario studied under the real ISP traces provided a similar assessment with, in particular, the scalability and efficiency of the COLOURED-APPROX as the number of zones increases. Last, we note that when the matching is empty, COLOURED-APPROX becomes equivalent to ORDERED-VECTOR with the major difference that making the feasible coloring over the resiliency graph depend on R ensures that the distribution of wastage remains reasonable.

V. CONCLUSION AND FUTURE WORK

In this paper, we presented a coloring based approach to carry out an efficient placement of network slices under a general protection mechanism which preserves failure tolerance of the virtual components. Our experiments over synthetic and real traces show that the proposed algorithms outperform the default placement algorithm in OpenStack while remaining very fast. A future work will investigate the asymptotic approximation performance of our algorithms and adapt them under an online provisioning of network slices.

Algorithm 1 6 :

 16 SLIDING-LEAST-LOAD Input: VNFC set C, Ordering rule R Output: A set of compute nodes S and a mapping of VNFC nodes to compute nodes m R : C → S 1: Set L B according to Eq. (9) Lower bound 2: C R ← sort C decreasingly using R 3: unfeasible = True 4: while unfeasible do 5: Add L B compute nodes to S for each VNFC c in C R do

Algorithm 2 7 :

 27 COLOURED-APPROXInput: Resiliency graph G = (V, E), Ordering rule R Output: A set of compute nodes S and a mapping of VNFC nodes to compute nodes m R :V → S 1: Partition V into P H = (H 1 , H 2 ) (See Sec. III-E) 2:Set the pairs E H with w H according to Eq. (10) and[START_REF] Karmarkar | An efficient approximation scheme for the one-dimensional bin-packing problem[END_REF] 3: Create a weighted bipartite graph B = (P H , E H , w H ) 4: Find a maximum weight matching M in B 5: for each (c 1 , c 2 ) in M do 6:S ← S ∪ {c 1 , c 2 } Joint placement Collect in M the nodes from M 8: N = V \ MComponents not yet placed 9: Compute a feasible coloring with χ R (G[N ]) colors 10: K χ ← classes from the obtained coloring 11: for each class κ in K do 12:

Fig. 1 :

 1 Fig. 1: Performance in terms of bins.

Fig. 2 :

 2 Fig. 2: Performance in terms of running time.

Fig. 3 :

 3 Fig. 3: Performance in terms of CPU wastage.